-/* Copyright (C) 1995-1997,2002,2004-2006,2010,2011
- Free Software Foundation, Inc.
+/* Copyright (C) 1995-2019 Free Software Foundation, Inc.
This file is part of the GNU C Library.
Written by Ulrich Drepper <drepper@gnu.org>, 1995.
# define STRING_TYPE char
# define USTRING_TYPE unsigned char
# define STRXFRM __strxfrm_l
-# define STRCMP strcmp
# define STRLEN strlen
# define STPNCPY __stpncpy
# define WEIGHT_H "../locale/weight.h"
#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
}
#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++];
+ }
-size_t
-STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n, __locale_t l)
+ *weight_idx = idx;
+ return len;
+}
+
+static int
+find_position (const USTRING_TYPE *us, const locale_data_t *l_data,
+ const int pass)
{
- struct __locale_data *current = l->__locales[LC_COLLATE];
- uint_fast32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
- /* We don't assign the following values right away since it might be
- unnecessary in case there are no rules. */
- const unsigned char *rulesets;
- const int32_t *table;
- const USTRING_TYPE *weights;
- const USTRING_TYPE *extra;
- const int32_t *indirect;
+ 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;
+ size_t needed = 0;
size_t last_needed;
- const USTRING_TYPE *usrc;
- size_t srclen = STRLEN (src);
- int32_t *idxarr;
- unsigned char *rulearr;
- size_t idxmax;
- size_t idxcnt;
- int use_malloc;
-#include WEIGHT_H
-
- if (nrules == 0)
+ /* Now the passes over the weights. */
+ for (pass = 0; pass < l_data->nrules; ++pass)
{
- if (n != 0)
- STPNCPY (dest, src, MIN (srclen + 1, n));
+ size_t backw_len = 0;
+ last_needed = needed;
+ const USTRING_TYPE *cur = usrc;
+ const USTRING_TYPE *backw_start = NULL;
- return srclen;
- }
+ /* 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);
- rulesets = (const unsigned char *)
- current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
- table = (const int32_t *)
- current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
- weights = (const USTRING_TYPE *)
- current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
- extra = (const USTRING_TYPE *)
- current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
- indirect = (const int32_t *)
- current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
- use_malloc = 0;
+ 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;
+ }
- assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
- assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
- assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
- assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
+ needed += backw_len;
+ backw_start = NULL;
+ backw_len = 0;
+ }
- /* Handle an empty string as a special case. */
- if (srclen == 0)
- {
- if (n != 0)
- *dest = L('\0');
- return 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;
+ }
+ }
- /* We need the elements of the string as unsigned values since they
- are used as indeces. */
- usrc = (const USTRING_TYPE *) src;
-
- /* Perform the first pass over the string and while doing this find
- and store the weights for each character. Since we want this to
- be as fast as possible we are using `alloca' to store the temporary
- values. But since there is no limit on the length of the string
- we have to use `malloc' if the string is too long. We should be
- very conservative here. */
- if (! __libc_use_alloca ((srclen + 1) * (sizeof (int32_t) + 1)))
- {
- idxarr = (int32_t *) malloc ((srclen + 1) * (sizeof (int32_t) + 1));
- rulearr = (unsigned char *) &idxarr[srclen];
-
- if (idxarr == NULL)
- /* No memory. Well, go with the stack then.
-
- XXX Once this implementation is stable we will handle this
- differently. Instead of precomputing the indeces we will
- do this in time. This means, though, that this happens for
- every pass again. */
- goto try_stack;
- use_malloc = 1;
- }
- else
- {
- try_stack:
- idxarr = (int32_t *) alloca (srclen * sizeof (int32_t));
- rulearr = (unsigned char *) alloca (srclen + 1);
+
+ /* 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;
}
- idxmax = 0;
- do
+ /* 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)
{
- int32_t tmp = findidx (&usrc, -1);
- rulearr[idxmax] = tmp >> 24;
- idxarr[idxmax] = tmp & 0xffffff;
-
- ++idxmax;
+ /* Remove the \1 byte. */
+ if (--needed <= n)
+ dest[needed - 1] = L('\0');
}
- while (*usrc != L('\0'));
- /* This element is only read, the value never used but to determine
- another value which then is ignored. */
- rulearr[idxmax] = '\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. We now use the indeces we found
- before. */
- needed = 0;
+ /* Now the passes over the weights. */
for (pass = 0; pass < nrules; ++pass)
{
size_t backw_stop = ~0ul;
dest[needed - 1] = L('\0');
}
- /* Free the memory if needed. */
- if (use_malloc)
- free (idxarr);
-
/* 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
projects / thirdparty / glibc.git / blobdiff