icuSources/i18n/collationweights.cpp

   1 /*
   2 *******************************************************************************
   3 *
   4 *   Copyright (C) 1999-2014, International Business Machines
   5 *   Corporation and others.  All Rights Reserved.
   6 *
   7 *******************************************************************************
   8 *   file name:  collationweights.cpp
   9 *   encoding:   US-ASCII
  10 *   tab size:   8 (not used)
  11 *   indentation:4
  12 *
  13 *   created on: 2001mar08 as ucol_wgt.cpp
  14 *   created by: Markus W. Scherer
  15 *
  16 *   This file contains code for allocating n collation element weights
  17 *   between two exclusive limits.
  18 *   It is used only internally by the collation tailoring builder.
  19 */
  20
  21 #include "unicode/utypes.h"
  22
  23 #if !UCONFIG_NO_COLLATION
  24
  25 #include "cmemory.h"
  26 #include "collation.h"
  27 #include "collationweights.h"
  28 #include "uarrsort.h"
  29 #include "uassert.h"
  30
  31 #ifdef UCOL_DEBUG
  32 #   include <stdio.h>
  33 #endif
  34
  35 U_NAMESPACE_BEGIN
  36
  37 /* collation element weight allocation -------------------------------------- */
  38
  39 /* helper functions for CE weights */
  40
  41 static inline uint32_t
  42 getWeightTrail(uint32_t weight, int32_t length) {
  43     return (uint32_t)(weight>>(8*(4-length)))&0xff;
  44 }
  45
  46 static inline uint32_t
  47 setWeightTrail(uint32_t weight, int32_t length, uint32_t trail) {
  48     length=8*(4-length);
  49     return (uint32_t)((weight&(0xffffff00<<length))|(trail<<length));
  50 }
  51
  52 static inline uint32_t
  53 getWeightByte(uint32_t weight, int32_t idx) {
  54     return getWeightTrail(weight, idx); /* same calculation */
  55 }
  56
  57 static inline uint32_t
  58 setWeightByte(uint32_t weight, int32_t idx, uint32_t byte) {
  59     uint32_t mask; /* 0xffffffff except a 00 "hole" for the index-th byte */
  60
  61     idx*=8;
  62     if(idx<32) {
  63         mask=((uint32_t)0xffffffff)>>idx;
  64     } else {
  65         // Do not use uint32_t>>32 because on some platforms that does not shift at all
  66         // while we need it to become 0.
  67         // PowerPC: 0xffffffff>>32 = 0           (wanted)
  68         // x86:     0xffffffff>>32 = 0xffffffff  (not wanted)
  69         //
  70         // ANSI C99 6.5.7 Bitwise shift operators:
  71         // "If the value of the right operand is negative
  72         // or is greater than or equal to the width of the promoted left operand,
  73         // the behavior is undefined."
  74         mask=0;
  75     }
  76     idx=32-idx;
  77     mask|=0xffffff00<<idx;
  78     return (uint32_t)((weight&mask)|(byte<<idx));
  79 }
  80
  81 static inline uint32_t
  82 truncateWeight(uint32_t weight, int32_t length) {
  83     return (uint32_t)(weight&(0xffffffff<<(8*(4-length))));
  84 }
  85
  86 static inline uint32_t
  87 incWeightTrail(uint32_t weight, int32_t length) {
  88     return (uint32_t)(weight+(1UL<<(8*(4-length))));
  89 }
  90
  91 static inline uint32_t
  92 decWeightTrail(uint32_t weight, int32_t length) {
  93     return (uint32_t)(weight-(1UL<<(8*(4-length))));
  94 }
  95
  96 CollationWeights::CollationWeights()
  97         : middleLength(0), rangeIndex(0), rangeCount(0) {
  98     for(int32_t i = 0; i < 5; ++i) {
  99         minBytes[i] = maxBytes[i] = 0;
 100     }
 101 }
 102
 103 void
 104 CollationWeights::initForPrimary(UBool compressible) {
 105     middleLength=1;
 106     minBytes[1] = Collation::MERGE_SEPARATOR_BYTE + 1;
 107     maxBytes[1] = Collation::TRAIL_WEIGHT_BYTE;
 108     if(compressible) {
 109         minBytes[2] = Collation::PRIMARY_COMPRESSION_LOW_BYTE + 1;
 110         maxBytes[2] = Collation::PRIMARY_COMPRESSION_HIGH_BYTE - 1;
 111     } else {
 112         minBytes[2] = 2;
 113         maxBytes[2] = 0xff;
 114     }
 115     minBytes[3] = 2;
 116     maxBytes[3] = 0xff;
 117     minBytes[4] = 2;
 118     maxBytes[4] = 0xff;
 119 }
 120
 121 void
 122 CollationWeights::initForSecondary() {
 123     // We use only the lower 16 bits for secondary weights.
 124     middleLength=3;
 125     minBytes[1] = 0;
 126     maxBytes[1] = 0;
 127     minBytes[2] = 0;
 128     maxBytes[2] = 0;
 129     minBytes[3] = Collation::MERGE_SEPARATOR_BYTE + 1;
 130     maxBytes[3] = 0xff;
 131     minBytes[4] = 2;
 132     maxBytes[4] = 0xff;
 133 }
 134
 135 void
 136 CollationWeights::initForTertiary() {
 137     // We use only the lower 16 bits for tertiary weights.
 138     middleLength=3;
 139     minBytes[1] = 0;
 140     maxBytes[1] = 0;
 141     minBytes[2] = 0;
 142     maxBytes[2] = 0;
 143     // We use only 6 bits per byte.
 144     // The other bits are used for case & quaternary weights.
 145     minBytes[3] = Collation::MERGE_SEPARATOR_BYTE + 1;
 146     maxBytes[3] = 0x3f;
 147     minBytes[4] = 2;
 148     maxBytes[4] = 0x3f;
 149 }
 150
 151 uint32_t
 152 CollationWeights::incWeight(uint32_t weight, int32_t length) const {
 153     for(;;) {
 154         uint32_t byte=getWeightByte(weight, length);
 155         if(byte<maxBytes[length]) {
 156             return setWeightByte(weight, length, byte+1);
 157         } else {
 158             // Roll over, set this byte to the minimum and increment the previous one.
 159             weight=setWeightByte(weight, length, minBytes[length]);
 160             --length;
 161             U_ASSERT(length > 0);
 162         }
 163     }
 164 }
 165
 166 uint32_t
 167 CollationWeights::incWeightByOffset(uint32_t weight, int32_t length, int32_t offset) const {
 168     for(;;) {
 169         offset += getWeightByte(weight, length);
 170         if((uint32_t)offset <= maxBytes[length]) {
 171             return setWeightByte(weight, length, offset);
 172         } else {
 173             // Split the offset between this byte and the previous one.
 174             offset -= minBytes[length];
 175             weight = setWeightByte(weight, length, minBytes[length] + offset % countBytes(length));
 176             offset /= countBytes(length);
 177             --length;
 178             U_ASSERT(length > 0);
 179         }
 180     }
 181 }
 182
 183 void
 184 CollationWeights::lengthenRange(WeightRange &range) const {
 185     int32_t length=range.length+1;
 186     range.start=setWeightTrail(range.start, length, minBytes[length]);
 187     range.end=setWeightTrail(range.end, length, maxBytes[length]);
 188     range.count*=countBytes(length);
 189     range.length=length;
 190 }
 191
 192 /* for uprv_sortArray: sort ranges in weight order */
 193 static int32_t U_CALLCONV
 194 compareRanges(const void * /*context*/, const void *left, const void *right) {
 195     uint32_t l, r;
 196
 197     l=((const CollationWeights::WeightRange *)left)->start;
 198     r=((const CollationWeights::WeightRange *)right)->start;
 199     if(l<r) {
 200         return -1;
 201     } else if(l>r) {
 202         return 1;
 203     } else {
 204         return 0;
 205     }
 206 }
 207
 208 UBool
 209 CollationWeights::getWeightRanges(uint32_t lowerLimit, uint32_t upperLimit) {
 210     U_ASSERT(lowerLimit != 0);
 211     U_ASSERT(upperLimit != 0);
 212
 213     /* get the lengths of the limits */
 214     int32_t lowerLength=lengthOfWeight(lowerLimit);
 215     int32_t upperLength=lengthOfWeight(upperLimit);
 216
 217 #ifdef UCOL_DEBUG
 218     printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength);
 219     printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength);
 220 #endif
 221     U_ASSERT(lowerLength>=middleLength);
 222     // Permit upperLength<middleLength: The upper limit for secondaries is 0x10000.
 223
 224     if(lowerLimit>=upperLimit) {
 225 #ifdef UCOL_DEBUG
 226         printf("error: no space between lower & upper limits\n");
 227 #endif
 228         return FALSE;
 229     }
 230
 231     /* check that neither is a prefix of the other */
 232     if(lowerLength<upperLength) {
 233         if(lowerLimit==truncateWeight(upperLimit, lowerLength)) {
 234 #ifdef UCOL_DEBUG
 235             printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit);
 236 #endif
 237             return FALSE;
 238         }
 239     }
 240     /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */
 241
 242     WeightRange lower[5], middle, upper[5]; /* [0] and [1] are not used - this simplifies indexing */
 243     uprv_memset(lower, 0, sizeof(lower));
 244     uprv_memset(&middle, 0, sizeof(middle));
 245     uprv_memset(upper, 0, sizeof(upper));
 246
 247     /*
 248      * With the limit lengths of 1..4, there are up to 7 ranges for allocation:
 249      * range     minimum length
 250      * lower[4]  4
 251      * lower[3]  3
 252      * lower[2]  2
 253      * middle    1
 254      * upper[2]  2
 255      * upper[3]  3
 256      * upper[4]  4
 257      *
 258      * We are now going to calculate up to 7 ranges.
 259      * Some of them will typically overlap, so we will then have to merge and eliminate ranges.
 260      */
 261     uint32_t weight=lowerLimit;
 262     for(int32_t length=lowerLength; length>middleLength; --length) {
 263         uint32_t trail=getWeightTrail(weight, length);
 264         if(trail<maxBytes[length]) {
 265             lower[length].start=incWeightTrail(weight, length);
 266             lower[length].end=setWeightTrail(weight, length, maxBytes[length]);
 267             lower[length].length=length;
 268             lower[length].count=maxBytes[length]-trail;
 269         }
 270         weight=truncateWeight(weight, length-1);
 271     }
 272     if(weight<0xff000000) {
 273         middle.start=incWeightTrail(weight, middleLength);
 274     } else {
 275         // Prevent overflow for primary lead byte FF
 276         // which would yield a middle range starting at 0.
 277         middle.start=0xffffffff;  // no middle range
 278     }
 279
 280     weight=upperLimit;
 281     for(int32_t length=upperLength; length>middleLength; --length) {
 282         uint32_t trail=getWeightTrail(weight, length);
 283         if(trail>minBytes[length]) {
 284             upper[length].start=setWeightTrail(weight, length, minBytes[length]);
 285             upper[length].end=decWeightTrail(weight, length);
 286             upper[length].length=length;
 287             upper[length].count=trail-minBytes[length];
 288         }
 289         weight=truncateWeight(weight, length-1);
 290     }
 291     middle.end=decWeightTrail(weight, middleLength);
 292
 293     /* set the middle range */
 294     middle.length=middleLength;
 295     if(middle.end>=middle.start) {
 296         middle.count=(int32_t)((middle.end-middle.start)>>(8*(4-middleLength)))+1;
 297     } else {
 298         /* no middle range, eliminate overlaps */
 299
 300         /* reduce or remove the lower ranges that go beyond upperLimit */
 301         for(int32_t length=4; length>middleLength; --length) {
 302             if(lower[length].count>0 && upper[length].count>0) {
 303                 uint32_t start=upper[length].start;
 304                 uint32_t end=lower[length].end;
 305
 306                 if(end>=start || incWeight(end, length)==start) {
 307                     /* lower and upper ranges collide or are directly adjacent: merge these two and remove all shorter ranges */
 308                     start=lower[length].start;
 309                     end=lower[length].end=upper[length].end;
 310                     /*
 311                      * merging directly adjacent ranges needs to subtract the 0/1 gaps in between;
 312                      * it may result in a range with count>countBytes
 313                      */
 314                     lower[length].count=
 315                         (int32_t)(getWeightTrail(end, length)-getWeightTrail(start, length)+1+
 316                                   countBytes(length)*(getWeightByte(end, length-1)-getWeightByte(start, length-1)));
 317                     upper[length].count=0;
 318                     while(--length>middleLength) {
 319                         lower[length].count=upper[length].count=0;
 320                     }
 321                     break;
 322                 }
 323             }
 324         }
 325     }
 326
 327 #ifdef UCOL_DEBUG
 328     /* print ranges */
 329     for(int32_t length=4; length>=2; --length) {
 330         if(lower[length].count>0) {
 331             printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count);
 332         }
 333     }
 334     if(middle.count>0) {
 335         printf("middle   .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count);
 336     }
 337     for(int32_t length=2; length<=4; ++length) {
 338         if(upper[length].count>0) {
 339             printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count);
 340         }
 341     }
 342 #endif
 343
 344     /* copy the ranges, shortest first, into the result array */
 345     rangeCount=0;
 346     if(middle.count>0) {
 347         uprv_memcpy(ranges, &middle, sizeof(WeightRange));
 348         rangeCount=1;
 349     }
 350     for(int32_t length=middleLength+1; length<=4; ++length) {
 351         /* copy upper first so that later the middle range is more likely the first one to use */
 352         if(upper[length].count>0) {
 353             uprv_memcpy(ranges+rangeCount, upper+length, sizeof(WeightRange));
 354             ++rangeCount;
 355         }
 356         if(lower[length].count>0) {
 357             uprv_memcpy(ranges+rangeCount, lower+length, sizeof(WeightRange));
 358             ++rangeCount;
 359         }
 360     }
 361     return rangeCount>0;
 362 }
 363
 364 UBool
 365 CollationWeights::allocWeightsInShortRanges(int32_t n, int32_t minLength) {
 366     // See if the first few minLength and minLength+1 ranges have enough weights.
 367     for(int32_t i = 0; i < rangeCount && ranges[i].length <= (minLength + 1); ++i) {
 368         if(n <= ranges[i].count) {
 369             // Use the first few minLength and minLength+1 ranges.
 370             if(ranges[i].length > minLength) {
 371                 // Reduce the number of weights from the last minLength+1 range
 372                 // which might sort before some minLength ranges,
 373                 // so that we use all weights in the minLength ranges.
 374                 ranges[i].count = n;
 375             }
 376             rangeCount = i + 1;
 377 #ifdef UCOL_DEBUG
 378             printf("take first %ld ranges\n", rangeCount);
 379 #endif
 380
 381             if(rangeCount>1) {
 382                 /* sort the ranges by weight values */
 383                 UErrorCode errorCode=U_ZERO_ERROR;
 384                 uprv_sortArray(ranges, rangeCount, sizeof(WeightRange),
 385                                compareRanges, NULL, FALSE, &errorCode);
 386                 /* ignore error code: we know that the internal sort function will not fail here */
 387             }
 388             return TRUE;
 389         }
 390         n -= ranges[i].count;  // still >0
 391     }
 392     return FALSE;
 393 }
 394
 395 UBool
 396 CollationWeights::allocWeightsInMinLengthRanges(int32_t n, int32_t minLength) {
 397     // See if the minLength ranges have enough weights
 398     // when we split one and lengthen the following ones.
 399     int32_t count = 0;
 400     int32_t minLengthRangeCount;
 401     for(minLengthRangeCount = 0;
 402             minLengthRangeCount < rangeCount &&
 403                 ranges[minLengthRangeCount].length == minLength;
 404             ++minLengthRangeCount) {
 405         count += ranges[minLengthRangeCount].count;
 406     }
 407
 408     int32_t nextCountBytes = countBytes(minLength + 1);
 409     if(n > count * nextCountBytes) { return FALSE; }
 410
 411     // Use the minLength ranges. Merge them, and then split again as necessary.
 412     uint32_t start = ranges[0].start;
 413     uint32_t end = ranges[0].end;
 414     for(int32_t i = 1; i < minLengthRangeCount; ++i) {
 415         if(ranges[i].start < start) { start = ranges[i].start; }
 416         if(ranges[i].end > end) { end = ranges[i].end; }
 417     }
 418
 419     // Calculate how to split the range between minLength (count1) and minLength+1 (count2).
 420     // Goal:
 421     //   count1 + count2 * nextCountBytes = n
 422     //   count1 + count2 = count
 423     // These turn into
 424     //   (count - count2) + count2 * nextCountBytes = n
 425     // and then into the following count1 & count2 computations.
 426     int32_t count2 = (n - count) / (nextCountBytes - 1);  // number of weights to be lengthened
 427     int32_t count1 = count - count2;  // number of minLength weights
 428     if(count2 == 0 || (count1 + count2 * nextCountBytes) < n) {
 429         // round up
 430         ++count2;
 431         --count1;
 432         U_ASSERT((count1 + count2 * nextCountBytes) >= n);
 433     }
 434
 435     ranges[0].start = start;
 436
 437     if(count1 == 0) {
 438         // Make one long range.
 439         ranges[0].end = end;
 440         ranges[0].count = count;
 441         lengthenRange(ranges[0]);
 442         rangeCount = 1;
 443     } else {
 444         // Split the range, lengthen the second part.
 445 #ifdef UCOL_DEBUG
 446         printf("split the range number %ld (out of %ld minLength ranges) by %ld:%ld\n",
 447                splitRange, rangeCount, count1, count2);
 448 #endif
 449
 450         // Next start = start + count1. First end = 1 before that.
 451         ranges[0].end = incWeightByOffset(start, minLength, count1 - 1);
 452         ranges[0].count = count1;
 453
 454         ranges[1].start = incWeight(ranges[0].end, minLength);
 455         ranges[1].end = end;
 456         ranges[1].length = minLength;  // +1 when lengthened
 457         ranges[1].count = count2;  // *countBytes when lengthened
 458         lengthenRange(ranges[1]);
 459         rangeCount = 2;
 460     }
 461     return TRUE;
 462 }
 463
 464 /*
 465  * call getWeightRanges and then determine heuristically
 466  * which ranges to use for a given number of weights between (excluding)
 467  * two limits
 468  */
 469 UBool
 470 CollationWeights::allocWeights(uint32_t lowerLimit, uint32_t upperLimit, int32_t n) {
 471 #ifdef UCOL_DEBUG
 472     puts("");
 473 #endif
 474
 475     if(!getWeightRanges(lowerLimit, upperLimit)) {
 476 #ifdef UCOL_DEBUG
 477         printf("error: unable to get Weight ranges\n");
 478 #endif
 479         return FALSE;
 480     }
 481
 482     /* try until we find suitably large ranges */
 483     for(;;) {
 484         /* get the smallest number of bytes in a range */
 485         int32_t minLength=ranges[0].length;
 486
 487         if(allocWeightsInShortRanges(n, minLength)) { break; }
 488
 489         if(minLength == 4) {
 490 #ifdef UCOL_DEBUG
 491             printf("error: the maximum number of %ld weights is insufficient for n=%ld\n",
 492                    minLengthCount, n);
 493 #endif
 494             return FALSE;
 495         }
 496
 497         if(allocWeightsInMinLengthRanges(n, minLength)) { break; }
 498
 499         /* no good match, lengthen all minLength ranges and iterate */
 500 #ifdef UCOL_DEBUG
 501         printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1);
 502 #endif
 503         for(int32_t i=0; ranges[i].length==minLength; ++i) {
 504             lengthenRange(ranges[i]);
 505         }
 506     }
 507
 508 #ifdef UCOL_DEBUG
 509     puts("final ranges:");
 510     for(int32_t i=0; i<rangeCount; ++i) {
 511         printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .count=%ld\n",
 512                i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].count);
 513     }
 514 #endif
 515
 516     rangeIndex = 0;
 517     return TRUE;
 518 }
 519
 520 uint32_t
 521 CollationWeights::nextWeight() {
 522     if(rangeIndex >= rangeCount) {
 523         return 0xffffffff;
 524     } else {
 525         /* get the next weight */
 526         WeightRange &range = ranges[rangeIndex];
 527         uint32_t weight = range.start;
 528         if(--range.count == 0) {
 529             /* this range is finished */
 530             ++rangeIndex;
 531         } else {
 532             /* increment the weight for the next value */
 533             range.start = incWeight(weight, range.length);
 534             U_ASSERT(range.start <= range.end);
 535         }
 536
 537         return weight;
 538     }
 539 }
 540
 541 U_NAMESPACE_END
 542
 543 #endif /* #if !UCONFIG_NO_COLLATION */