libc/string/_collate.c

   1 /*
   2  * Copyright (C) 2002     Manuel Novoa III
   3  * Copyright (C) 2000-2005 Erik Andersen <andersen@uclibc.org>
   4  *
   5  * Licensed under the LGPL v2.1, see the file COPYING.LIB in this tarball.
   6  */
   7
   8 /*  Dec 20, 2002
   9  *  Initial test implementation of strcoll, strxfrm, wcscoll, and wcsxfrm.
  10  *  The code needs to be cleaned up a good bit, but I'd like to see people
  11  *  test it out.
  12  *
  13  */
  14
  15 #include "_string.h"
  16 #include <ctype.h>
  17 #include <locale.h>
  18 #include <stdlib.h>
  19 #include <errno.h>
  20 #include <assert.h>
  21
  22 #ifdef __UCLIBC_HAS_LOCALE__
  23 #if defined(L_strxfrm) || defined(L_strxfrm_l) || defined(L_wcsxfrm) || defined(L_wcsxfrm_l)
  24
  25 #ifdef L_strxfrm
  26 #ifndef WANT_WIDE
  27 #error WANT_WIDE should be defined for L_strxfrm
  28 #endif
  29 #ifdef L_wcsxfrm
  30 #error L_wcsxfrm already defined for L_strxfrm
  31 #endif
  32 #endif /* L_strxfrm */
  33
  34 #if defined(L_strxfrm) || defined(L_strxfrm_l)
  35
  36 #define wcscoll   strcoll
  37 #define wcscoll_l strcoll_l
  38 #define wcsxfrm   strxfrm
  39 #define wcsxfrm_l strxfrm_l
  40
  41 #undef WANT_WIDE
  42 #undef Wvoid
  43 #undef Wchar
  44 #undef Wuchar
  45 #undef Wint
  46
  47 #define Wchar char
  48
  49 #endif /* defined(L_strxfrm) || defined(L_strxfrm_l) */
  50
  51 #if defined(__UCLIBC_HAS_XLOCALE__) && !defined(__UCLIBC_DO_XLOCALE)
  52
  53
  54 int wcscoll (const Wchar *s0, const Wchar *s1)
  55 {
  56         return wcscoll_l(s0, s1, __UCLIBC_CURLOCALE );
  57 }
  58 libc_hidden_def(wcscoll)
  59
  60
  61 size_t wcsxfrm(Wchar *__restrict ws1, const Wchar *__restrict ws2, size_t n)
  62 {
  63         return wcsxfrm_l(ws1, ws2, n, __UCLIBC_CURLOCALE );
  64 }
  65
  66 #else  /* defined(__UCLIBC_HAS_XLOCALE__) && !defined(__UCLIBC_DO_XLOCALE) */
  67
  68
  69 #if 0
  70 #define CUR_COLLATE (&__UCLIBC_CURLOCALE->collate)
  71 #else
  72 #define CUR_COLLATE (& __LOCALE_PTR->collate)
  73 #endif
  74
  75 #define MAX_PENDING 8
  76
  77 typedef struct {
  78         const Wchar *s;
  79         const Wchar *eob;                       /* end of backward */
  80
  81         __uwchar_t weight;
  82         __uwchar_t ui_weight;           /* undefined or invalid */
  83         int colitem;
  84         int weightidx;
  85         int rule;
  86         size_t position;
  87         /* should be wchar_t.  if wchar < 0 do EILSEQ? */
  88         __uwchar_t *cip;
  89         __uwchar_t ci_pending[MAX_PENDING];     /* nul-terminated */
  90
  91         char *back_buf;
  92         char *bbe;                                      /* end of back_buf (actual last... not 1 past end) */
  93         char *bp;                                       /* ptr into backbuf, NULL if not in backward mode */
  94         char ibb[128];
  95         size_t bb_size;
  96
  97         int ru_pushed;
  98 } col_state_t;
  99
 100
 101 #define WEIGHT_MASK     0x3fffU
 102 #define RULE_MASK       0xc000U
 103
 104 #define RULE_FORWARD  (1 << 14)
 105 #define RULE_POSITION (1 << 15)
 106
 107 #define UI_IDX          (WEIGHT_MASK-6)
 108 #define POSIT_IDX       (WEIGHT_MASK-5)
 109 #define RANGE_IDX       (WEIGHT_MASK-4)
 110 #define UNDEF_IDX       (WEIGHT_MASK-3)
 111 #define INVAL_IDX       (WEIGHT_MASK-2)
 112 #define DITTO_IDX   (WEIGHT_MASK-1)
 113
 114
 115 #undef TRACE
 116 #if 0
 117 #define TRACE(X)        printf X
 118 #else
 119 #define TRACE(X)        ((void)0)
 120 #endif
 121
 122 static int lookup(wchar_t wc   __LOCALE_PARAM )
 123 {
 124         unsigned int sc, n, i0, i1;
 125
 126         if (((__uwchar_t) wc) > 0xffffU) {
 127                 return 0;
 128         }
 129
 130         sc = wc & CUR_COLLATE->ti_mask;
 131         wc >>= CUR_COLLATE->ti_shift;
 132         n = wc & CUR_COLLATE->ii_mask;
 133         wc >>= CUR_COLLATE->ii_shift;
 134
 135         i0 = CUR_COLLATE->wcs2colidt_tbl[wc];
 136         i0 <<= CUR_COLLATE->ii_shift;
 137         i1 = CUR_COLLATE->wcs2colidt_tbl[CUR_COLLATE->ii_len + i0 + n];
 138         i1 <<= CUR_COLLATE->ti_shift;
 139         return CUR_COLLATE->wcs2colidt_tbl[CUR_COLLATE->ii_len + CUR_COLLATE->ti_len + i1 + sc];
 140
 141 }
 142
 143 static void init_col_state(col_state_t *cs, const Wchar *wcs)
 144 {
 145         memset(cs, 0, sizeof(col_state_t));
 146         cs->s = wcs;
 147         cs->bp = cs->back_buf = cs->ibb;
 148         cs->bb_size = 128;
 149         cs->bbe = cs->back_buf + (cs->bb_size -1);
 150 }
 151
 152 static void next_weight(col_state_t *cs, int pass   __LOCALE_PARAM )
 153 {
 154         int r, w, ru, ri, popping_backup_stack;
 155         ssize_t n;
 156         const uint16_t *p;
 157 #ifdef WANT_WIDE
 158 #define WC (*cs->s)
 159 #define N (1)
 160 #else  /* WANT_WIDE */
 161         wchar_t WC;
 162         size_t n0, nx = 0;
 163 #define N n0
 164
 165 #endif /* WANT_WIDE */
 166
 167         do {
 168
 169                 if (cs->ru_pushed) {
 170                         ru = cs->ru_pushed;
 171                         TRACE(("ru_pushed = %d\n", ru));
 172                         cs->ru_pushed = 0;
 173                         goto POSITION_SKIP;
 174                 }
 175
 176 #ifdef __UCLIBC_MJN3_ONLY__
 177 #warning should we walk pendings backwards?
 178 #endif
 179                 if (cs->cip) {                  /* possible pending weight */
 180                         if ((r = *(cs->cip++)) == 0) {
 181                                 cs->cip = NULL;
 182                                 continue;
 183                         }
 184                         cs->weightidx = r & WEIGHT_MASK;
 185                         assert(cs->weightidx);
 186 /*                      assert(cs->weightidx != WEIGHT_MASK); */
 187                 } else {                                /* get the next collation item from the string */
 188                         TRACE(("clearing popping flag\n"));
 189                         popping_backup_stack = 0;
 190
 191                 IGNORE_LOOP:
 192                         /* keep first pos as 0 for a sentinal */
 193                         if (*cs->bp) {                          /* pending backward chars */
 194                         POP_BACKUP:
 195                                 popping_backup_stack = 1;
 196                                 TRACE(("setting popping flag\n"));
 197                                 n = 0;
 198                                 if (*cs->bp > 0) {              /* singles pending */
 199                                         cs->s -= 1;
 200                                         if ((*cs->bp -= 1) == 0) {
 201                                                 cs->bp -= 1;
 202                                         }
 203                                 } else {                                /* last was a multi */
 204                                         cs->s += *cs->bp;
 205                                         cs->bp -= 1;
 206                                 }
 207                         } else if (!*cs->s) { /* not in backward mode and end of string */
 208                                 cs->weight = 0;
 209                                 return;
 210                         } else {
 211                                 cs->position += 1;
 212                         }
 213
 214                 BACK_LOOP:
 215 #ifdef WANT_WIDE
 216                         n = 1;
 217                         cs->colitem = r = lookup(*cs->s   __LOCALE_ARG );
 218 #else  /* WANT_WIDE */
 219                         n = n0 = __locale_mbrtowc_l(&WC, cs->s, __LOCALE_PTR);
 220                         if (n < 0) {
 221                                 __set_errno(EILSEQ);
 222                                 cs->weight = 0;
 223                                 return;
 224                         }
 225                         cs->colitem = r = lookup(WC   __LOCALE_ARG );
 226 #endif /* WANT_WIDE */
 227
 228                         TRACE((" r=%d WC=%#lx\n", r, (unsigned long)(WC)));
 229
 230                         if (r > CUR_COLLATE->max_col_index) { /* starting char for one or more sequences */
 231                                 p = CUR_COLLATE->multistart_tbl;
 232                                 p += p[r-CUR_COLLATE->max_col_index -1];
 233                                 do {
 234                                         n = N;
 235                                         r = *p++;
 236                                         do {
 237                                                 if (!*p) {              /* found it */
 238                                                         cs->colitem = r;
 239                                                         TRACE(("    found multi %d\n", n));
 240                                                         goto FOUND;
 241                                                 }
 242 #ifdef WANT_WIDE
 243                                                 /* the lookup check here is safe since we're assured that *p is a valid colidx */
 244                                                 if (!cs->s[n] || (lookup(cs->s[n]   __LOCALE_ARG ) != *p)) {
 245                                                         do {} while (*p++);
 246                                                         break;
 247                                                 }
 248                                                 ++p;
 249                                                 ++n;
 250 #else  /* WANT_WIDE */
 251                                                 if (cs->s[n]) {
 252                                                         nx = __locale_mbrtowc_l(&WC, cs->s + n, __LOCALE_PTR);
 253                                                         if (nx < 0) {
 254                                                                 __set_errno(EILSEQ);
 255                                                                 cs->weight = 0;
 256                                                                 return;
 257                                                         }
 258                                                 }
 259                                                 if (!cs->s[n] || (lookup(WC   __LOCALE_ARG ) != *p)) {
 260                                                         do {} while (*p++);
 261                                                         break;
 262                                                 }
 263                                                 ++p;
 264                                                 n += nx; /* Only gets here if cs->s[n] != 0, so nx is set. */
 265 #endif /* WANT_WIDE */
 266                                         } while (1);
 267                                 } while (1);
 268                         } else if (r == 0) {            /* illegal, undefined, or part of a range */
 269                                 if ((CUR_COLLATE->range_count)
 270 #ifdef __UCLIBC_MJN3_ONLY__
 271 #warning .. need to introduce range as a collating item?
 272 #endif
 273                                         && (((__uwchar_t)(WC - CUR_COLLATE->range_low)) <= CUR_COLLATE->range_count)
 274                                         ) {                                     /* part of a range */
 275                                         /* Note: cs->colitem = 0 already. */
 276                                         TRACE(("    found range\n"));
 277                                         ru = CUR_COLLATE->ruletable[CUR_COLLATE->range_rule_offset*CUR_COLLATE->MAX_WEIGHTS + pass];
 278                                         assert((ru & WEIGHT_MASK) != DITTO_IDX);
 279                                         if ((ru & WEIGHT_MASK) == WEIGHT_MASK) {
 280                                                 ru = (ru & RULE_MASK) | RANGE_IDX;
 281                                                 cs->weight = CUR_COLLATE->range_base_weight + (WC - CUR_COLLATE->range_low);
 282                                         }
 283                                         goto RANGE_SKIP_TO;
 284                                 } else if (((__uwchar_t)(WC)) <= 0x7fffffffUL) { /* legal but undefined */
 285                                 UNDEFINED:
 286                                         /* Note: cs->colitem = 0 already. */
 287                                         ri = CUR_COLLATE->undefined_idx;
 288                                         assert(ri != 0); /* implicit undefined isn't supported */
 289
 290                                         TRACE(("    found explicit UNDEFINED\n"));
 291 #ifdef __UCLIBC_MJN3_ONLY__
 292 #warning right now single weight locales do not support ..
 293 #endif
 294                                         if (CUR_COLLATE->num_weights == 1) {
 295                                                 TRACE(("    single weight UNDEFINED\n"));
 296                                                 cs->weightidx = RANGE_IDX;
 297                                                 cs->weight = ri;
 298                                                 cs->s += n;
 299                                                 goto PROCESS_WEIGHT;
 300                                         }
 301
 302                                         ri = CUR_COLLATE->index2ruleidx[ri - 1];
 303                                         ru = CUR_COLLATE->ruletable[ri * CUR_COLLATE->MAX_WEIGHTS + pass];
 304                                         assert((ru & WEIGHT_MASK) != WEIGHT_MASK); /* TODO: handle ".." */
 305                                         if ((ru & WEIGHT_MASK) == DITTO_IDX) {
 306                                                 cs->colitem = CUR_COLLATE->undefined_idx;
 307                                         }
 308                                         goto RANGE_SKIP_TO;
 309                                 } else {                /* illegal */
 310                                         TRACE(("    found illegal\n"));
 311                                         __set_errno(EINVAL);
 312                                         /* We put all illegals in the same equiv class with maximal weight,
 313                                          * and ignore them after the first pass. */
 314                                         if (pass > 0) {
 315                                                 cs->s += n;
 316                                                 goto IGNORE_LOOP;
 317                                         }
 318                                         ru = (RULE_FORWARD | RANGE_IDX);
 319                                         cs->weight = 0xffffU;
 320                                         goto RANGE_SKIP_TO;
 321                                 }
 322                         } else if (CUR_COLLATE->num_weights == 1) {
 323                                 TRACE(("    single weight\n"));
 324                                 cs->weightidx = RANGE_IDX;
 325                                 cs->weight = cs->colitem;
 326                                 cs->s += n;
 327                                 goto PROCESS_WEIGHT;
 328                         } else {
 329                                 TRACE(("    normal\n"));
 330                         }
 331
 332                         /* if we get here, it is a normal char either singlely weighted, undefined, or in a range */
 333                 FOUND:
 334                         ri = CUR_COLLATE->index2ruleidx[cs->colitem - 1];
 335                         TRACE((" ri=%d ", ri));
 336 #ifdef __UCLIBC_MJN3_ONLY__
 337 #warning make sure this is correct
 338 #endif
 339                         if (!ri) {
 340                                 TRACE(("NOT IN THIS LOCALE\n"));
 341                                 goto UNDEFINED;
 342                         }
 343                         ru = CUR_COLLATE->ruletable[ri * CUR_COLLATE->MAX_WEIGHTS + pass];
 344
 345                 RANGE_SKIP_TO:
 346
 347 #ifdef __UCLIBC_MJN3_ONLY__
 348 #warning ignoreables probably should not interrupt backwards processing, but this is wrong
 349 #endif
 350 /*                      if (!(ru & WEIGHT_MASK)) { */
 351 /*                              TRACE(("IGNORE\n")); */
 352 /*                              cs->s += n; */
 353 /*                              continue; */
 354 /*                      } */
 355
 356
 357                         TRACE((" rule = %#x  weight = %#x  popping = %d  s = %p  eob = %p\n",
 358                                    ru & RULE_MASK, ru & WEIGHT_MASK, popping_backup_stack,
 359                                    cs->s, cs->eob));
 360                         /* now we need to check if we're going backwards... */
 361
 362                         if (!popping_backup_stack) {
 363                                 if (!(ru & RULE_MASK)) { /* backward */
 364                                         TRACE(("backwards\n"));
 365                                         assert(cs->bp <= cs->bbe);
 366                                         if (cs->bp == cs->bbe) {
 367                                                 if (cs->back_buf == cs->ibb) { /* was using internal buffer */
 368                                                         cs->bp = malloc(cs->bb_size + 128);
 369                                                         if (!cs->bp) {
 370                                                                 /* __set_errno(ENOMEM); */
 371 #ifdef __UCLIBC_MJN3_ONLY__
 372 #warning what to do here?
 373 #endif
 374                                                                 cs->weight = 0;
 375                                                                 return;
 376                                                         }
 377                                                         memcpy(cs->bp, cs->back_buf, cs->bb_size);
 378
 379                                                 } else {
 380                                                         cs->bp = realloc(cs->back_buf, cs->bb_size + 128);
 381                                                         if (!cs->bp) {
 382                                                                 /* __set_errno(ENOMEM); */
 383 #ifdef __UCLIBC_MJN3_ONLY__
 384 #warning what to do here?
 385 #endif
 386                                                                 cs->weight = 0;
 387                                                                 return;
 388                                                         }
 389                                                 }
 390                                                 cs->bb_size += 128;
 391                                                 cs->bbe = cs->bp + (cs->bbe - cs->back_buf);
 392                                                 cs->back_buf = cs->bp;
 393                                                 cs->bp = cs->bbe;
 394
 395                                         }
 396                                         if (n==1) {                     /* single char */
 397                                                 if (*cs->bp && (((unsigned char)(*cs->bp)) < CHAR_MAX)) {
 398                                                         *cs->bp += 1; /* increment last single's count */
 399                                                 } else {          /* last was a multi, or just starting */
 400                                                         if (!cs->bp) {
 401                                                                 cs->bp = cs->back_buf;
 402                                                         } else {
 403                                                                 assert(cs->bp < cs->bbe);
 404                                                                 ++cs->bp;
 405                                                         }
 406                                                         *cs->bp = 1;
 407                                                 }
 408                                         } else {                        /* multichar */
 409                                                 assert(n>1);
 410                                                 assert(cs->bp < cs->bbe);
 411                                                 *++cs->bp = -n;
 412                                         }
 413                                         cs->s += n;
 414                                         if (*cs->s) {
 415                                                 goto BACK_LOOP;
 416                                         }
 417                                         /* end-of-string so start popping */
 418                                         cs->eob = cs->s;
 419                                         TRACE(("popping\n"));
 420                                         goto POP_BACKUP;
 421                                 } else if (*cs->bp) { /* was going backward but this element isn't */
 422                                         /* discard current and use previous backward element */
 423                                         assert(!cs->cip);
 424                                         cs->eob = cs->s;
 425                                         TRACE(("popping\n"));
 426                                         goto POP_BACKUP;
 427                                 } else {                                /* was and still going forward */
 428                                         TRACE(("forwards\n"));
 429                                         if ((ru & (RULE_POSITION|WEIGHT_MASK)) > RULE_POSITION) {
 430                                                 assert(ru & WEIGHT_MASK);
 431                                                 cs->ru_pushed = ru;
 432                                                 cs->weight = cs->position;
 433 #ifdef __UCLIBC_MJN3_ONLY__
 434 #warning devel code
 435 #endif
 436                                                 cs->position = 0;       /* reset to reduce size for strcoll? */
 437                                                 cs->s += n;
 438                                                 cs->weightidx = RANGE_IDX;
 439                                                 goto PROCESS_WEIGHT;
 440                                         }
 441                                 }
 442                         } else {                                        /* popping backwards stack */
 443                                 TRACE(("popping (continued)\n"));
 444                                 if (!*cs->bp) {
 445                                         cs->s = cs->eob;
 446                                 }
 447                                 cs->s -= n;
 448                         }
 449
 450                         cs->s += n;
 451                 POSITION_SKIP:
 452                         cs->weightidx = ru & WEIGHT_MASK;
 453                         cs->rule = ru & RULE_MASK;
 454                 }
 455
 456 #ifdef __UCLIBC_MJN3_ONLY__
 457 #warning for pending we only want the weight... _not_ the rule
 458 #endif
 459                 if (!cs->weightidx) {   /* ignore */
 460                         continue;
 461                 }
 462
 463         PROCESS_WEIGHT:
 464                 assert(cs->weightidx);
 465
 466
 467                 if (((unsigned int)(cs->weightidx - UI_IDX)) <= (INVAL_IDX-UI_IDX)) {
 468                         if (cs->weightidx == UI_IDX) {
 469                                 cs->weight = cs->ui_weight;
 470                         }
 471                         return;
 472                 }
 473
 474                 assert(cs->weightidx != WEIGHT_MASK);
 475                 if (cs->weightidx == DITTO_IDX) { /* want the weight of the current collating item */
 476                         TRACE(("doing ditto\n"));
 477                         w = CUR_COLLATE->index2weight[cs->colitem -1];
 478                 } else if (cs->weightidx <= CUR_COLLATE->max_col_index) { /* normal */
 479                         TRACE(("doing normal\n"));
 480                         w = CUR_COLLATE->index2weight[cs->weightidx -1];
 481                 } else {                                /* a string */
 482                         TRACE(("doing string\n"));
 483                         assert(!(cs->weightidx & RULE_MASK));
 484                         /* note: iso14561 allows null string here */
 485                         p = CUR_COLLATE->weightstr + (cs->weightidx - (CUR_COLLATE->max_col_index + 2));
 486                         if (*p & WEIGHT_MASK) {
 487                                 r = 0;
 488                                 do {
 489                                         assert(r < MAX_PENDING);
 490                                         cs->ci_pending[r++] = *p++;
 491                                 } while (*p & WEIGHT_MASK);
 492                                 cs->cip = cs->ci_pending;
 493                         }
 494                         continue;
 495                 }
 496
 497                 cs->weight = w;
 498                 return;
 499         } while (1);
 500 }
 501
 502 int __XL_NPP(wcscoll) (const Wchar *s0, const Wchar *s1   __LOCALE_PARAM )
 503 {
 504         col_state_t ws[2];
 505         int pass;
 506
 507         if (!CUR_COLLATE->num_weights) { /* C locale */
 508 #ifdef WANT_WIDE
 509                 return wcscmp(s0, s1);
 510 #else
 511                 return strcmp(s0, s1);
 512 #endif
 513         }
 514
 515         pass = 0;
 516         do {                                            /* loop through the weights levels */
 517                 init_col_state(ws, s0);
 518                 init_col_state(ws+1, s1);
 519                 do {                                    /* loop through the strings */
 520                         /* for each string, get the next weight */
 521                         next_weight(ws, pass   __LOCALE_ARG );
 522                         next_weight(ws+1, pass   __LOCALE_ARG );
 523                         TRACE(("w0=%lu  w1=%lu\n",
 524                                    (unsigned long) ws[0].weight,
 525                                    (unsigned long) ws[1].weight));
 526
 527                         if (ws[0].weight != ws[1].weight) {
 528                                 return ws[0].weight - ws[1].weight;
 529                         }
 530                 } while (ws[0].weight);
 531         } while (++pass < CUR_COLLATE->num_weights);
 532
 533         return 0;
 534 }
 535 libc_hidden_def(__XL_NPP(wcscoll))
 536
 537 #ifdef WANT_WIDE
 538
 539 size_t __XL_NPP(wcsxfrm)(wchar_t *__restrict ws1, const wchar_t *__restrict ws2,
 540                                          size_t n   __LOCALE_PARAM )
 541 {
 542         col_state_t cs;
 543         size_t count;
 544         int pass;
 545
 546         if (!CUR_COLLATE->num_weights) { /* C locale */
 547                 return __wcslcpy(ws1, ws2, n);
 548         }
 549
 550 #ifdef __UCLIBC_MJN3_ONLY__
 551 #warning handle empty string as a special case
 552 #endif
 553
 554         count = pass = 0;
 555         do {                                            /* loop through the weights levels */
 556                 init_col_state(&cs, ws2);
 557                 do {                                    /* loop through the string */
 558                         next_weight(&cs, pass   __LOCALE_ARG );
 559                         TRACE(("weight=%lu (%#lx)\n", (unsigned long) cs.weight, (unsigned long) cs.weight));
 560                         if (count < n) {
 561                                 ws1[count] = cs.weight +1;
 562                         }
 563                         ++count;
 564                         TRACE(("--------------------------------------------\n"));
 565                 } while (cs.weight);
 566                 if (count <= n) {               /* overwrite the trailing 0 end-of-pass marker */
 567                         ws1[count-1] = 1;
 568                 }
 569                 TRACE(("--------------------  pass %d  --------------------\n", pass));
 570         } while (++pass < CUR_COLLATE->num_weights);
 571         if (count <= n) {                       /* oops... change it back */
 572                 ws1[count-1] = 0;
 573         }
 574         return count-1;
 575 }
 576 #if defined L_strxfrm_l || defined L_wcsxfrm_l
 577 libc_hidden_def(__XL_NPP(wcsxfrm))
 578 #endif
 579
 580 #else  /* WANT_WIDE */
 581
 582 static const unsigned long bound[] = {
 583         1UL << 7,
 584         1UL << 11,
 585         1UL << 16,
 586         1UL << 21,
 587         1UL << 26,
 588 };
 589
 590 static unsigned char first[] = {
 591         0x0, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc
 592 };
 593
 594 /* Use an extension of UTF-8 to store a 32 bit val in max 6 bytes. */
 595
 596 static size_t store(unsigned char *s, size_t count, size_t n, __uwchar_t weight)
 597 {
 598         int i, r;
 599
 600         i = 0;
 601         do {
 602                 if (weight < bound[i]) {
 603                         break;
 604                 }
 605         } while (++i < sizeof(bound)/sizeof(bound[0]));
 606
 607         r = i+1;
 608         if (i + count < n) {
 609                 s += count;
 610                 s[0] = first[i];
 611                 while (i) {
 612                         s[i] = 0x80 | (weight & 0x3f);
 613                         weight >>= 6;
 614                         --i;
 615                 }
 616                 s[0] |= weight;
 617         }
 618
 619         return r;
 620 }
 621
 622 size_t __XL_NPP(strxfrm)(char *__restrict ws1, const char *__restrict ws2, size_t n
 623                                          __LOCALE_PARAM )
 624 {
 625         col_state_t cs;
 626         size_t count, inc;
 627         int pass;
 628
 629         if (!CUR_COLLATE->num_weights) { /* C locale */
 630                 return strlcpy(ws1, ws2, n);
 631         }
 632
 633 #ifdef __UCLIBC_MJN3_ONLY__
 634 #warning handle empty string as a special case
 635 #endif
 636
 637         inc = count = pass = 0;
 638         do {                                            /* loop through the weights levels */
 639                 init_col_state(&cs, ws2);
 640                 do {                                    /* loop through the string */
 641                         next_weight(&cs, pass   __LOCALE_ARG );
 642                         TRACE(("weight=%lu (%#lx)\n", (unsigned long) cs.weight, (unsigned long) cs.weight));
 643                         inc = store((unsigned char *)ws1, count, n, cs.weight + 1);
 644                         count += inc;
 645                         TRACE(("--------------------------------------------\n"));
 646                 } while (cs.weight);
 647                 /* overwrite the trailing 0 end-of-pass marker */
 648                 assert(inc == 1);
 649                 if (count <= n) {
 650                         ws1[count-1] = 1;
 651                 }
 652                 TRACE(("--------------------  pass %d  --------------------\n", pass));
 653         } while (++pass < CUR_COLLATE->num_weights);
 654         if (count <= n) {                       /* oops... change it back */
 655                 ws1[count-1] = 0;
 656         }
 657         return count-1;
 658 }
 659 #ifdef L_strxfrm_l
 660 libc_hidden_def(__XL_NPP(strxfrm))
 661 #endif
 662
 663 #endif /* WANT_WIDE */
 664
 665 #endif /* defined(__UCLIBC_HAS_XLOCALE__) && !defined(__UCLIBC_DO_XLOCALE) */
 666
 667 #endif /* defined(L_strxfrm) || defined(L_strxfrm_l) || defined(L_wcsxfrm) || defined(L_wcsxfrm_l) */
 668
 669 #endif /* __UCLIBC_HAS_LOCALE__ */
 670 /**********************************************************************/