/* Copyright (C) 1995-2018 Free Software Foundation, Inc.
This file is part of the GNU C Library.
Written by Ulrich Drepper <drepper@gnu.org>, 1995.
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, see
<http://www.gnu.org/licenses/>. */
#include <assert.h>
#include <langinfo.h>
#include <locale.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/param.h>
#ifndef STRING_TYPE
# define STRING_TYPE char
# define USTRING_TYPE unsigned char
# define STRXFRM __strxfrm_l
# define STRLEN strlen
# define STPNCPY __stpncpy
# define WEIGHT_H "../locale/weight.h"
# define SUFFIX MB
# define L(arg) arg
#endif
#define CONCAT(a,b) CONCAT1(a,b)
#define CONCAT1(a,b) a##b
/* Maximum string size that is calculated with cached indices. Right now this
is an arbitrary value open to optimizations. SMALL_STR_SIZE * 4 has to be
lower than __MAX_ALLOCA_CUTOFF. Keep localedata/xfrm-test.c in sync. */
#define SMALL_STR_SIZE 4095
#include "../locale/localeinfo.h"
#include WEIGHT_H
/* Group locale data for shorter parameter lists. */
typedef struct
{
uint_fast32_t nrules;
unsigned char *rulesets;
USTRING_TYPE *weights;
int32_t *table;
USTRING_TYPE *extra;
int32_t *indirect;
} locale_data_t;
#ifndef WIDE_CHAR_VERSION
/* We need UTF-8 encoding of numbers. */
static int
utf8_encode (char *buf, int val)
{
int retval;
if (val < 0x80)
{
*buf++ = (char) val;
retval = 1;
}
else
{
int step;
for (step = 2; step < 6; ++step)
if ((val & (~(uint32_t)0 << (5 * step + 1))) == 0)
break;
retval = step;
*buf = (unsigned char) (~0xff >> step);
--step;
do
{
buf[step] = 0x80 | (val & 0x3f);
val >>= 6;
}
while (--step > 0);
*buf |= val;
}
return retval;
}
#endif
/* Find next weight and rule index. Inlined since called for every char. */
static __always_inline size_t
find_idx (const USTRING_TYPE **us, int32_t *weight_idx,
unsigned char *rule_idx, const locale_data_t *l_data, const int pass)
{
int32_t tmp = findidx (l_data->table, l_data->indirect, l_data->extra, us,
-1);
*rule_idx = tmp >> 24;
int32_t idx = tmp & 0xffffff;
size_t len = l_data->weights[idx++];
/* Skip over indices of previous levels. */
for (int i = 0; i < pass; i++)
{
idx += len;
len = l_data->weights[idx++];
}
*weight_idx = idx;
return len;
}
static int
find_position (const USTRING_TYPE *us, const locale_data_t *l_data,
const int pass)
{
int32_t weight_idx;
unsigned char rule_idx;
const USTRING_TYPE *usrc = us;
find_idx (&usrc, &weight_idx, &rule_idx, l_data, pass);
return l_data->rulesets[rule_idx * l_data->nrules + pass] & sort_position;
}
/* Do the transformation. */
static size_t
do_xfrm (const USTRING_TYPE *usrc, STRING_TYPE *dest, size_t n,
const locale_data_t *l_data)
{
int32_t weight_idx;
unsigned char rule_idx;
uint_fast32_t pass;
size_t needed = 0;
size_t last_needed;
/* Now the passes over the weights. */
for (pass = 0; pass < l_data->nrules; ++pass)
{
size_t backw_len = 0;
last_needed = needed;
const USTRING_TYPE *cur = usrc;
const USTRING_TYPE *backw_start = NULL;
/* We assume that if a rule has defined `position' in one section
this is true for all of them. */
int position = find_position (cur, l_data, pass);
if (position == 0)
{
while (*cur != L('\0'))
{
const USTRING_TYPE *pos = cur;
size_t len = find_idx (&cur, &weight_idx, &rule_idx, l_data,
pass);
int rule = l_data->rulesets[rule_idx * l_data->nrules + pass];
if ((rule & sort_forward) != 0)
{
/* Handle the pushed backward sequence. */
if (backw_start != NULL)
{
for (size_t i = backw_len; i > 0; )
{
int32_t weight_idx;
unsigned char rule_idx;
size_t len = find_idx (&backw_start, &weight_idx,
&rule_idx, l_data, pass);
if (needed + i < n)
for (size_t j = len; j > 0; j--)
dest[needed + i - j] =
l_data->weights[weight_idx++];
i -= len;
}
needed += backw_len;
backw_start = NULL;
backw_len = 0;
}
/* Now handle the forward element. */
if (needed + len < n)
while (len-- > 0)
dest[needed++] = l_data->weights[weight_idx++];
else
/* No more characters fit into the buffer. */
needed += len;
}
else
{
/* Remember start of the backward sequence & track length. */
if (backw_start == NULL)
backw_start = pos;
backw_len += len;
}
}
/* Handle the pushed backward sequence. */
if (backw_start != NULL)
{
for (size_t i = backw_len; i > 0; )
{
size_t len = find_idx (&backw_start, &weight_idx, &rule_idx,
l_data, pass);
if (needed + i < n)
for (size_t j = len; j > 0; j--)
dest[needed + i - j] =
l_data->weights[weight_idx++];
i -= len;
}
needed += backw_len;
}
}
else
{
int val = 1;
#ifndef WIDE_CHAR_VERSION
char buf[7];
size_t buflen;
#endif
size_t i;
while (*cur != L('\0'))
{
const USTRING_TYPE *pos = cur;
size_t len = find_idx (&cur, &weight_idx, &rule_idx, l_data,
pass);
int rule = l_data->rulesets[rule_idx * l_data->nrules + pass];
if ((rule & sort_forward) != 0)
{
/* Handle the pushed backward sequence. */
if (backw_start != NULL)
{
for (size_t p = backw_len; p > 0; p--)
{
size_t len;
int32_t weight_idx;
unsigned char rule_idx;
const USTRING_TYPE *backw_cur = backw_start;
/* To prevent a warning init the used vars. */
len = find_idx (&backw_cur, &weight_idx,
&rule_idx, l_data, pass);
for (i = 1; i < p; i++)
len = find_idx (&backw_cur, &weight_idx,
&rule_idx, l_data, pass);
if (len != 0)
{
#ifdef WIDE_CHAR_VERSION
if (needed + 1 + len < n)
{
dest[needed] = val;
for (i = 0; i < len; ++i)
dest[needed + 1 + i] =
l_data->weights[weight_idx + i];
}
needed += 1 + len;
#else
buflen = utf8_encode (buf, val);
if (needed + buflen + len < n)
{
for (i = 0; i < buflen; ++i)
dest[needed + i] = buf[i];
for (i = 0; i < len; ++i)
dest[needed + buflen + i] =
l_data->weights[weight_idx + i];
}
needed += buflen + len;
#endif
val = 1;
}
else
++val;
}
backw_start = NULL;
backw_len = 0;
}
/* Now handle the forward element. */
if (len != 0)
{
#ifdef WIDE_CHAR_VERSION
if (needed + 1 + len < n)
{
dest[needed] = val;
for (i = 0; i < len; ++i)
dest[needed + 1 + i] =
l_data->weights[weight_idx + i];
}
needed += 1 + len;
#else
buflen = utf8_encode (buf, val);
if (needed + buflen + len < n)
{
for (i = 0; i < buflen; ++i)
dest[needed + i] = buf[i];
for (i = 0; i < len; ++i)
dest[needed + buflen + i] =
l_data->weights[weight_idx + i];
}
needed += buflen + len;
#endif
val = 1;
}
else
++val;
}
else
{
/* Remember start of the backward sequence & track length. */
if (backw_start == NULL)
backw_start = pos;
backw_len++;
}
}
/* Handle the pushed backward sequence. */
if (backw_start != NULL)
{
for (size_t p = backw_len; p > 0; p--)
{
size_t len;
int32_t weight_idx;
unsigned char rule_idx;
const USTRING_TYPE *backw_cur = backw_start;
/* To prevent a warning init the used vars. */
len = find_idx (&backw_cur, &weight_idx,
&rule_idx, l_data, pass);
for (i = 1; i < p; i++)
len = find_idx (&backw_cur, &weight_idx,
&rule_idx, l_data, pass);
if (len != 0)
{
#ifdef WIDE_CHAR_VERSION
if (needed + 1 + len < n)
{
dest[needed] = val;
for (i = 0; i < len; ++i)
dest[needed + 1 + i] =
l_data->weights[weight_idx + i];
}
needed += 1 + len;
#else
buflen = utf8_encode (buf, val);
if (needed + buflen + len < n)
{
for (i = 0; i < buflen; ++i)
dest[needed + i] = buf[i];
for (i = 0; i < len; ++i)
dest[needed + buflen + i] =
l_data->weights[weight_idx + i];
}
needed += buflen + len;
#endif
val = 1;
}
else
++val;
}
}
}
/* Finally store the byte to separate the passes or terminate
the string. */
if (needed < n)
dest[needed] = pass + 1 < l_data->nrules ? L('\1') : L('\0');
++needed;
}
/* This is a little optimization: many collation specifications have
a `position' rule at the end and if no non-ignored character
is found the last \1 byte is immediately followed by a \0 byte
signalling this. We can avoid the \1 byte(s). */
if (needed > 2 && needed == last_needed + 1)
{
/* Remove the \1 byte. */
if (--needed <= n)
dest[needed - 1] = L('\0');
}
/* Return the number of bytes/words we need, but don't count the NUL
byte/word at the end. */
return needed - 1;
}
/* Do the transformation using weight-index and rule cache. */
static size_t
do_xfrm_cached (STRING_TYPE *dest, size_t n, const locale_data_t *l_data,
size_t idxmax, int32_t *idxarr, const unsigned char *rulearr)
{
uint_fast32_t nrules = l_data->nrules;
unsigned char *rulesets = l_data->rulesets;
USTRING_TYPE *weights = l_data->weights;
uint_fast32_t pass;
size_t needed = 0;
size_t last_needed;
size_t idxcnt;
/* Now the passes over the weights. */
for (pass = 0; pass < nrules; ++pass)
{
size_t backw_stop = ~0ul;
int rule = rulesets[rulearr[0] * nrules + pass];
/* We assume that if a rule has defined `position' in one section
this is true for all of them. */
int position = rule & sort_position;
last_needed = needed;
if (position == 0)
{
for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
{
if ((rule & sort_forward) != 0)
{
size_t len;
if (backw_stop != ~0ul)
{
/* Handle the pushed elements now. */
size_t backw;
for (backw = idxcnt; backw > backw_stop; )
{
--backw;
len = weights[idxarr[backw]++];
if (needed + len < n)
while (len-- > 0)
dest[needed++] = weights[idxarr[backw]++];
else
{
/* No more characters fit into the buffer. */
needed += len;
idxarr[backw] += len;
}
}
backw_stop = ~0ul;
}
/* Now handle the forward element. */
len = weights[idxarr[idxcnt]++];
if (needed + len < n)
while (len-- > 0)
dest[needed++] = weights[idxarr[idxcnt]++];
else
{
/* No more characters fit into the buffer. */
needed += len;
idxarr[idxcnt] += len;
}
}
else
{
/* Remember where the backwards series started. */
if (backw_stop == ~0ul)
backw_stop = idxcnt;
}
rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
}
if (backw_stop != ~0ul)
{
/* Handle the pushed elements now. */
size_t backw;
backw = idxcnt;
while (backw > backw_stop)
{
size_t len = weights[idxarr[--backw]++];
if (needed + len < n)
while (len-- > 0)
dest[needed++] = weights[idxarr[backw]++];
else
{
/* No more characters fit into the buffer. */
needed += len;
idxarr[backw] += len;
}
}
}
}
else
{
int val = 1;
#ifndef WIDE_CHAR_VERSION
char buf[7];
size_t buflen;
#endif
size_t i;
for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
{
if ((rule & sort_forward) != 0)
{
size_t len;
if (backw_stop != ~0ul)
{
/* Handle the pushed elements now. */
size_t backw;
for (backw = idxcnt; backw > backw_stop; )
{
--backw;
len = weights[idxarr[backw]++];
if (len != 0)
{
#ifdef WIDE_CHAR_VERSION
if (needed + 1 + len < n)
{
dest[needed] = val;
for (i = 0; i < len; ++i)
dest[needed + 1 + i] =
weights[idxarr[backw] + i];
}
needed += 1 + len;
#else
buflen = utf8_encode (buf, val);
if (needed + buflen + len < n)
{
for (i = 0; i < buflen; ++i)
dest[needed + i] = buf[i];
for (i = 0; i < len; ++i)
dest[needed + buflen + i] =
weights[idxarr[backw] + i];
}
needed += buflen + len;
#endif
idxarr[backw] += len;
val = 1;
}
else
++val;
}
backw_stop = ~0ul;
}
/* Now handle the forward element. */
len = weights[idxarr[idxcnt]++];
if (len != 0)
{
#ifdef WIDE_CHAR_VERSION
if (needed + 1+ len < n)
{
dest[needed] = val;
for (i = 0; i < len; ++i)
dest[needed + 1 + i] =
weights[idxarr[idxcnt] + i];
}
needed += 1 + len;
#else
buflen = utf8_encode (buf, val);
if (needed + buflen + len < n)
{
for (i = 0; i < buflen; ++i)
dest[needed + i] = buf[i];
for (i = 0; i < len; ++i)
dest[needed + buflen + i] =
weights[idxarr[idxcnt] + i];
}
needed += buflen + len;
#endif
idxarr[idxcnt] += len;
val = 1;
}
else
/* Note that we don't have to increment `idxarr[idxcnt]'
since the length is zero. */
++val;
}
else
{
/* Remember where the backwards series started. */
if (backw_stop == ~0ul)
backw_stop = idxcnt;
}
rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
}
if (backw_stop != ~0ul)
{
/* Handle the pushed elements now. */
size_t backw;
backw = idxmax - 1;
while (backw > backw_stop)
{
size_t len = weights[idxarr[--backw]++];
if (len != 0)
{
#ifdef WIDE_CHAR_VERSION
if (needed + 1 + len < n)
{
dest[needed] = val;
for (i = 0; i < len; ++i)
dest[needed + 1 + i] =
weights[idxarr[backw] + i];
}
needed += 1 + len;
#else
buflen = utf8_encode (buf, val);
if (needed + buflen + len < n)
{
for (i = 0; i < buflen; ++i)
dest[needed + i] = buf[i];
for (i = 0; i < len; ++i)
dest[needed + buflen + i] =
weights[idxarr[backw] + i];
}
needed += buflen + len;
#endif
idxarr[backw] += len;
val = 1;
}
else
++val;
}
}
}
/* Finally store the byte to separate the passes or terminate
the string. */
if (needed < n)
dest[needed] = pass + 1 < nrules ? L('\1') : L('\0');
++needed;
}
/* This is a little optimization: many collation specifications have
a `position' rule at the end and if no non-ignored character
is found the last \1 byte is immediately followed by a \0 byte
signalling this. We can avoid the \1 byte(s). */
if (needed > 2 && needed == last_needed + 1)
{
/* Remove the \1 byte. */
if (--needed <= n)
dest[needed - 1] = L('\0');
}
/* Return the number of bytes/words we need, but don't count the NUL
byte/word at the end. */
return needed - 1;
}
size_t
STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n, locale_t l)
{
locale_data_t l_data;
struct __locale_data *current = l->__locales[LC_COLLATE];
l_data.nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
/* Handle byte comparison case. */
if (l_data.nrules == 0)
{
size_t srclen = STRLEN (src);
if (n != 0)
STPNCPY (dest, src, MIN (srclen + 1, n));
return srclen;
}
/* Handle an empty string, code hereafter relies on strlen (src) > 0. */
if (*src == L('\0'))
{
if (n != 0)
*dest = L('\0');
return 0;
}
/* Get the locale data. */
l_data.rulesets = (unsigned char *)
current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
l_data.table = (int32_t *)
current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
l_data.weights = (USTRING_TYPE *)
current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
l_data.extra = (USTRING_TYPE *)
current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
l_data.indirect = (int32_t *)
current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
assert (((uintptr_t) l_data.table) % __alignof__ (l_data.table[0]) == 0);
assert (((uintptr_t) l_data.weights) % __alignof__ (l_data.weights[0]) == 0);
assert (((uintptr_t) l_data.extra) % __alignof__ (l_data.extra[0]) == 0);
assert (((uintptr_t) l_data.indirect) % __alignof__ (l_data.indirect[0]) == 0);
/* We need the elements of the string as unsigned values since they
are used as indeces. */
const USTRING_TYPE *usrc = (const USTRING_TYPE *) src;
/* Allocate cache for small strings on the stack and fill it with weight and
rule indices. If the cache size is not sufficient, continue with the
uncached xfrm version. */
size_t idxmax = 0;
const USTRING_TYPE *cur = usrc;
int32_t *idxarr = alloca (SMALL_STR_SIZE * sizeof (int32_t));
unsigned char *rulearr = alloca (SMALL_STR_SIZE + 1);
do
{
int32_t tmp = findidx (l_data.table, l_data.indirect, l_data.extra, &cur,
-1);
rulearr[idxmax] = tmp >> 24;
idxarr[idxmax] = tmp & 0xffffff;
++idxmax;
}
while (*cur != L('\0') && idxmax < SMALL_STR_SIZE);
/* This element is only read, the value never used but to determine
another value which then is ignored. */
rulearr[idxmax] = '\0';
/* Do the transformation. */
if (*cur == L('\0'))
return do_xfrm_cached (dest, n, &l_data, idxmax, idxarr, rulearr);
else
return do_xfrm (usrc, dest, n, &l_data);
}
libc_hidden_def (STRXFRM)
#ifndef WIDE_CHAR_VERSION
weak_alias (__strxfrm_l, strxfrm_l)
#endif