/* 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