icuSources/i18n/ucol_wgt.c

   1 /*
   2 *******************************************************************************
   3 *
   4 *   Copyright (C) 1999-2003, International Business Machines
   5 *   Corporation and others.  All Rights Reserved.
   6 *
   7 *******************************************************************************
   8 *   file name:  ucol_wgt.c
   9 *   encoding:   US-ASCII
  10 *   tab size:   8 (not used)
  11 *   indentation:4
  12 *
  13 *   created on: 2001mar08
  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 ucol_bld.
  19 */
  20
  21 #include "unicode/utypes.h"
  22
  23 #if !UCONFIG_NO_COLLATION
  24
  25 #include "ucol_imp.h"
  26 #include "ucol_wgt.h"
  27 #include "cmemory.h"
  28 #include "uarrsort.h"
  29
  30 #ifdef UCOL_DEBUG
  31 #   include <stdio.h>
  32 #endif
  33
  34 #if defined(UCOL_DEBUG) && defined(WIN32)
  35     /* turn off "unreferenced formal parameter" */
  36 #   pragma warning(disable: 4100)
  37 #endif
  38
  39 /* collation element weight allocation -------------------------------------- */
  40
  41 /* helper functions for CE weights */
  42
  43 static U_INLINE int32_t
  44 lengthOfWeight(uint32_t weight) {
  45     if((weight&0xffffff)==0) {
  46         return 1;
  47     } else if((weight&0xffff)==0) {
  48         return 2;
  49     } else if((weight&0xff)==0) {
  50         return 3;
  51     } else {
  52         return 4;
  53     }
  54 }
  55
  56 static U_INLINE uint32_t
  57 getWeightTrail(uint32_t weight, int32_t length) {
  58     return (uint32_t)(weight>>(8*(4-length)))&0xff;
  59 }
  60
  61 static U_INLINE uint32_t
  62 setWeightTrail(uint32_t weight, int32_t length, uint32_t trail) {
  63     length=8*(4-length);
  64     return (uint32_t)((weight&(0xffffff00<<length))|(trail<<length));
  65 }
  66
  67 static U_INLINE uint32_t
  68 getWeightByte(uint32_t weight, int32_t index) {
  69     return getWeightTrail(weight, index); /* same calculation */
  70 }
  71
  72 static U_INLINE uint32_t
  73 setWeightByte(uint32_t weight, int32_t index, uint32_t byte) {
  74     uint32_t mask; /* 0xffffffff except a 00 "hole" for the index-th byte */
  75
  76     index*=8;
  77     mask=((uint32_t)0xffffffff)>>index;
  78     index=32-index;
  79     mask|=0xffffff00<<index;
  80     return (uint32_t)((weight&mask)|(byte<<index));
  81 }
  82
  83 static U_INLINE uint32_t
  84 truncateWeight(uint32_t weight, int32_t length) {
  85     return (uint32_t)(weight&(0xffffffff<<(8*(4-length))));
  86 }
  87
  88 static U_INLINE uint32_t
  89 incWeightTrail(uint32_t weight, int32_t length) {
  90     return (uint32_t)(weight+(1UL<<(8*(4-length))));
  91 }
  92
  93 static U_INLINE uint32_t
  94 decWeightTrail(uint32_t weight, int32_t length) {
  95     return (uint32_t)(weight-(1UL<<(8*(4-length))));
  96 }
  97
  98 static U_INLINE uint32_t
  99 incWeight(uint32_t weight, int32_t length, uint32_t maxByte) {
 100     uint32_t byte;
 101
 102     for(;;) {
 103         byte=getWeightByte(weight, length);
 104         if(byte<maxByte) {
 105             return setWeightByte(weight, length, byte+1);
 106         } else {
 107             /* roll over, set this byte to UCOL_BYTE_FIRST_TAILORED and increment the previous one */
 108             weight=setWeightByte(weight, length, UCOL_BYTE_FIRST_TAILORED);
 109             --length;
 110         }
 111     }
 112 }
 113
 114 static U_INLINE int32_t
 115 lengthenRange(WeightRange *range, uint32_t maxByte, uint32_t countBytes) {
 116     int32_t length;
 117
 118     length=range->length2+1;
 119     range->start=setWeightTrail(range->start, length, UCOL_BYTE_FIRST_TAILORED);
 120     range->end=setWeightTrail(range->end, length, maxByte);
 121     range->count2*=countBytes;
 122     range->length2=length;
 123     return length;
 124 }
 125
 126 /* for uprv_sortArray: sort ranges in weight order */
 127 static U_INLINE int32_t U_CALLCONV
 128 compareRanges(const void *context, const void *left, const void *right) {
 129     uint32_t l, r;
 130
 131     l=((const WeightRange *)left)->start;
 132     r=((const WeightRange *)right)->start;
 133     if(l<r) {
 134         return -1;
 135     } else if(l>r) {
 136         return 1;
 137     } else {
 138         return 0;
 139     }
 140 }
 141
 142 /*
 143  * take two CE weights and calculate the
 144  * possible ranges of weights between the two limits, excluding them
 145  * for weights with up to 4 bytes there are up to 2*4-1=7 ranges
 146  */
 147 static U_INLINE int32_t
 148 getWeightRanges(uint32_t lowerLimit, uint32_t upperLimit,
 149                 uint32_t maxByte, uint32_t countBytes,
 150                 WeightRange ranges[7]) {
 151     WeightRange lower[5], middle, upper[5]; /* [0] and [1] are not used - this simplifies indexing */
 152     uint32_t weight, trail;
 153     int32_t length, lowerLength, upperLength, rangeCount;
 154
 155     /* assume that both lowerLimit & upperLimit are not 0 */
 156
 157     /* get the lengths of the limits */
 158     lowerLength=lengthOfWeight(lowerLimit);
 159     upperLength=lengthOfWeight(upperLimit);
 160
 161 #ifdef UCOL_DEBUG
 162     printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength);
 163     printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength);
 164 #endif
 165
 166     if(lowerLimit>=upperLimit) {
 167 #ifdef UCOL_DEBUG
 168         printf("error: no space between lower & upper limits\n");
 169 #endif
 170         return 0;
 171     }
 172
 173     /* check that neither is a prefix of the other */
 174     if(lowerLength<upperLength) {
 175         if(lowerLimit==truncateWeight(upperLimit, lowerLength)) {
 176 #ifdef UCOL_DEBUG
 177             printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit);
 178 #endif
 179             return 0;
 180         }
 181     }
 182     /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */
 183
 184     /* reset local variables */
 185     uprv_memset(lower, 0, sizeof(lower));
 186     uprv_memset(&middle, 0, sizeof(middle));
 187     uprv_memset(upper, 0, sizeof(upper));
 188
 189     /*
 190      * With the limit lengths of 1..4, there are up to 7 ranges for allocation:
 191      * range     minimum length
 192      * lower[4]  4
 193      * lower[3]  3
 194      * lower[2]  2
 195      * middle    1
 196      * upper[2]  2
 197      * upper[3]  3
 198      * upper[4]  4
 199      *
 200      * We are now going to calculate up to 7 ranges.
 201      * Some of them will typically overlap, so we will then have to merge and eliminate ranges.
 202      */
 203     weight=lowerLimit;
 204     for(length=lowerLength; length>=2; --length) {
 205         trail=getWeightTrail(weight, length);
 206         if(trail<maxByte) {
 207             lower[length].start=incWeightTrail(weight, length);
 208             lower[length].end=setWeightTrail(weight, length, maxByte);
 209             lower[length].length=length;
 210             lower[length].count=maxByte-trail;
 211         }
 212         weight=truncateWeight(weight, length-1);
 213     }
 214     middle.start=incWeightTrail(weight, 1);
 215
 216     weight=upperLimit;
 217     for(length=upperLength; length>=2; --length) {
 218         trail=getWeightTrail(weight, length);
 219         if(trail>UCOL_BYTE_FIRST_TAILORED) {
 220             upper[length].start=setWeightTrail(weight, length, UCOL_BYTE_FIRST_TAILORED);
 221             upper[length].end=decWeightTrail(weight, length);
 222             upper[length].length=length;
 223             upper[length].count=trail-UCOL_BYTE_FIRST_TAILORED;
 224         }
 225         weight=truncateWeight(weight, length-1);
 226     }
 227     middle.end=decWeightTrail(weight, 1);
 228
 229     /* set the middle range */
 230     middle.length=1;
 231     if(middle.end>=middle.start) {
 232         middle.count=(int32_t)((middle.end-middle.start)>>24)+1;
 233     } else {
 234         /* eliminate overlaps */
 235         uint32_t start, end;
 236
 237         /* remove the middle range */
 238         middle.count=0;
 239
 240         /* reduce or remove the lower ranges that go beyond upperLimit */
 241         for(length=4; length>=2; --length) {
 242             if(lower[length].count>0 && upper[length].count>0) {
 243                 start=upper[length].start;
 244                 end=lower[length].end;
 245
 246                 if(end>=start || incWeight(end, length, maxByte)==start) {
 247                     /* lower and upper ranges collide or are directly adjacent: merge these two and remove all shorter ranges */
 248                     start=lower[length].start;
 249                     end=lower[length].end=upper[length].end;
 250                     /*
 251                      * merging directly adjacent ranges needs to subtract the 0/1 gaps in between;
 252                      * it may result in a range with count>countBytes
 253                      */
 254                     lower[length].count=
 255                         (int32_t)(getWeightTrail(end, length)-getWeightTrail(start, length)+1+
 256                                   countBytes*(getWeightByte(end, length-1)-getWeightByte(start, length-1)));
 257                     upper[length].count=0;
 258                     while(--length>=2) {
 259                         lower[length].count=upper[length].count=0;
 260                     }
 261                     break;
 262                 }
 263             }
 264         }
 265     }
 266
 267 #ifdef UCOL_DEBUG
 268     /* print ranges */
 269     for(length=4; length>=2; --length) {
 270         if(lower[length].count>0) {
 271             printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count);
 272         }
 273     }
 274     if(middle.count>0) {
 275         printf("middle   .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count);
 276     }
 277     for(length=2; length<=4; ++length) {
 278         if(upper[length].count>0) {
 279             printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count);
 280         }
 281     }
 282 #endif
 283
 284     /* copy the ranges, shortest first, into the result array */
 285     rangeCount=0;
 286     if(middle.count>0) {
 287         uprv_memcpy(ranges, &middle, sizeof(WeightRange));
 288         rangeCount=1;
 289     }
 290     for(length=2; length<=4; ++length) {
 291         /* copy upper first so that later the middle range is more likely the first one to use */
 292         if(upper[length].count>0) {
 293             uprv_memcpy(ranges+rangeCount, upper+length, sizeof(WeightRange));
 294             ++rangeCount;
 295         }
 296         if(lower[length].count>0) {
 297             uprv_memcpy(ranges+rangeCount, lower+length, sizeof(WeightRange));
 298             ++rangeCount;
 299         }
 300     }
 301     return rangeCount;
 302 }
 303
 304 /*
 305  * call getWeightRanges and then determine heuristically
 306  * which ranges to use for a given number of weights between (excluding)
 307  * two limits
 308  */
 309 U_CFUNC int32_t
 310 ucol_allocWeights(uint32_t lowerLimit, uint32_t upperLimit,
 311                   uint32_t n,
 312                   uint32_t maxByte,
 313                   WeightRange ranges[7]) {
 314     /* number of usable byte values 3..maxByte */
 315     uint32_t countBytes=maxByte-UCOL_BYTE_FIRST_TAILORED+1;
 316
 317     uint32_t lengthCounts[6]; /* [0] unused, [5] to make index checks unnecessary */
 318     uint32_t maxCount;
 319     int32_t i, rangeCount, minLength/*, maxLength*/;
 320
 321     /* countBytes to the power of index */
 322     uint32_t powers[5];
 323     /* gcc requires explicit initialization */
 324     powers[0] = 1;
 325     powers[1] = countBytes;
 326     powers[2] = countBytes*countBytes;
 327     powers[3] = countBytes*countBytes*countBytes;
 328     powers[4] = countBytes*countBytes*countBytes*countBytes;
 329
 330 #ifdef UCOL_DEBUG
 331     puts("");
 332 #endif
 333
 334     rangeCount=getWeightRanges(lowerLimit, upperLimit, maxByte, countBytes, ranges);
 335     if(rangeCount<=0) {
 336 #ifdef UCOL_DEBUG
 337         printf("error: unable to get Weight ranges\n");
 338 #endif
 339         return 0;
 340     }
 341
 342     /* what is the maximum number of weights with these ranges? */
 343     maxCount=0;
 344     for(i=0; i<rangeCount; ++i) {
 345         maxCount+=(uint32_t)ranges[i].count*powers[4-ranges[i].length];
 346     }
 347     if(maxCount>=n) {
 348 #ifdef UCOL_DEBUG
 349         printf("the maximum number of %lu weights is sufficient for n=%lu\n", maxCount, n);
 350 #endif
 351     } else {
 352 #ifdef UCOL_DEBUG
 353         printf("error: the maximum number of %lu weights is insufficient for n=%lu\n", maxCount, n);
 354 #endif
 355         return 0;
 356     }
 357
 358     /* set the length2 and count2 fields */
 359     for(i=0; i<rangeCount; ++i) {
 360         ranges[i].length2=ranges[i].length;
 361         ranges[i].count2=(uint32_t)ranges[i].count;
 362     }
 363
 364     /* try until we find suitably large ranges */
 365     for(;;) {
 366         /* get the smallest number of bytes in a range */
 367         minLength=ranges[0].length2;
 368
 369         /* sum up the number of elements that fit into ranges of each byte length */
 370         uprv_memset(lengthCounts, 0, sizeof(lengthCounts));
 371         for(i=0; i<rangeCount; ++i) {
 372             lengthCounts[ranges[i].length2]+=ranges[i].count2;
 373         }
 374
 375         /* now try to allocate n elements in the available short ranges */
 376         if(n<=(lengthCounts[minLength]+lengthCounts[minLength+1])) {
 377             /* trivial cases, use the first few ranges */
 378             maxCount=0;
 379             rangeCount=0;
 380             do {
 381                 maxCount+=ranges[rangeCount].count2;
 382                 ++rangeCount;
 383             } while(n>maxCount);
 384 #ifdef UCOL_DEBUG
 385             printf("take first %ld ranges\n", rangeCount);
 386 #endif
 387             break;
 388         } else if(n<=ranges[0].count2*countBytes) {
 389             /* easy case, just make this one range large enough by lengthening it once more, possibly split it */
 390             uint32_t count1, count2, power_1, power;
 391
 392             /*maxLength=minLength+1;*/
 393
 394             /* calculate how to split the range between maxLength-1 (count1) and maxLength (count2) */
 395             power_1=powers[minLength-ranges[0].length];
 396             power=power_1*countBytes;
 397             count2=(n+power-1)/power;
 398             count1=ranges[0].count-count2;
 399
 400             /* split the range */
 401 #ifdef UCOL_DEBUG
 402             printf("split the first range %ld:%ld\n", count1, count2);
 403 #endif
 404             if(count1<1) {
 405                 rangeCount=1;
 406
 407                 /* lengthen the entire range to maxLength */
 408                 lengthenRange(ranges, maxByte, countBytes);
 409             } else {
 410                 /* really split the range */
 411                 uint32_t byte;
 412
 413                 /* create a new range with the end and initial and current length of the old one */
 414                 rangeCount=2;
 415                 ranges[1].end=ranges[0].end;
 416                 ranges[1].length=ranges[0].length;
 417                 ranges[1].length2=minLength;
 418
 419                 /* set the end of the first range according to count1 */
 420                 i=ranges[0].length;
 421                 byte=getWeightByte(ranges[0].start, i)+count1-1;
 422
 423                 /*
 424                  * ranges[0].count and count1 may be >countBytes
 425                  * from merging adjacent ranges;
 426                  * byte>maxByte is possible
 427                  */
 428                 if(byte<=maxByte) {
 429                     ranges[0].end=setWeightByte(ranges[0].start, i, byte);
 430                 } else /* byte>maxByte */ {
 431                     ranges[0].end=setWeightByte(incWeight(ranges[0].start, i-1, maxByte), i, byte-countBytes);
 432                 }
 433
 434                 /* set the bytes in the end weight at length+1..length2 to maxByte */
 435                 byte=(maxByte<<24)|(maxByte<<16)|(maxByte<<8)|maxByte; /* this used to be 0xffffffff */
 436                 ranges[0].end=truncateWeight(ranges[0].end, i)|
 437                               ((byte>>(8*i))&(byte<<(8*(4-minLength))));
 438
 439                 /* set the start of the second range to immediately follow the end of the first one */
 440                 ranges[1].start=incWeight(ranges[0].end, minLength, maxByte);
 441
 442                 /* set the count values (informational) */
 443                 ranges[0].count=count1;
 444                 ranges[1].count=count2;
 445
 446                 ranges[0].count2=count1*power_1;
 447                 ranges[1].count2=count2*power_1; /* will be *countBytes when lengthened */
 448
 449                 /* lengthen the second range to maxLength */
 450                 lengthenRange(ranges+1, maxByte, countBytes);
 451             }
 452             break;
 453         }
 454
 455         /* no good match, lengthen all minLength ranges and iterate */
 456 #ifdef UCOL_DEBUG
 457         printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1);
 458 #endif
 459         for(i=0; ranges[i].length2==minLength; ++i) {
 460             lengthenRange(ranges+i, maxByte, countBytes);
 461         }
 462     }
 463
 464     if(rangeCount>1) {
 465         /* sort the ranges by weight values */
 466         UErrorCode errorCode=U_ZERO_ERROR;
 467         uprv_sortArray(ranges, rangeCount, sizeof(WeightRange), compareRanges, NULL, FALSE, &errorCode);
 468         /* ignore error code: we know that the internal sort function will not fail here */
 469     }
 470
 471 #ifdef UCOL_DEBUG
 472     puts("final ranges:");
 473     for(i=0; i<rangeCount; ++i) {
 474         printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .length2=%ld .count=%ld .count2=%lu\n",
 475                i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].length2, ranges[i].count, ranges[i].count2);
 476     }
 477 #endif
 478
 479     /* set maxByte in ranges[0] for ucol_nextWeight() */
 480     ranges[0].count=maxByte;
 481
 482     return rangeCount;
 483 }
 484
 485 /*
 486  * given a set of ranges calculated by ucol_allocWeights(),
 487  * iterate through the weights
 488  */
 489 U_CFUNC uint32_t
 490 ucol_nextWeight(WeightRange ranges[], int32_t *pRangeCount) {
 491     if(*pRangeCount<=0) {
 492         return 0xffffffff;
 493     } else {
 494         uint32_t weight, maxByte;
 495
 496         /* get maxByte from the .count field */
 497         maxByte=ranges[0].count;
 498
 499         /* get the next weight */
 500         weight=ranges[0].start;
 501         if(weight==ranges[0].end) {
 502             /* this range is finished, remove it and move the following ones up */
 503             if(--*pRangeCount>0) {
 504                 uprv_memmove(ranges, ranges+1, *pRangeCount*sizeof(WeightRange));
 505                 ranges[0].count=maxByte; /* keep maxByte in ranges[0] */
 506             }
 507         } else {
 508             /* increment the weight for the next value */
 509             ranges[0].start=incWeight(weight, ranges[0].length2, maxByte);
 510         }
 511
 512         return weight;
 513     }
 514 }
 515
 516 #ifdef UCOL_DEBUG
 517
 518 static void
 519 testAlloc(uint32_t lowerLimit, uint32_t upperLimit, uint32_t n, UBool enumerate) {
 520     WeightRange ranges[8];
 521     int32_t rangeCount;
 522
 523     rangeCount=ucol_allocWeights(lowerLimit, upperLimit, n, ranges);
 524     if(enumerate) {
 525         uint32_t weight;
 526
 527         while(n>0) {
 528             weight=ucol_nextWeight(ranges, &rangeCount);
 529             if(weight==0xffffffff) {
 530                 printf("error: 0xffffffff with %lu more weights to go\n", n);
 531                 break;
 532             }
 533             printf("    0x%08lx\n", weight);
 534             --n;
 535         }
 536     }
 537 }
 538
 539 extern int
 540 main(int argc, const char *argv[]) {
 541 #if 0
 542 #endif
 543     testAlloc(0x364214fc, 0x44b87d23, 5, FALSE);
 544     testAlloc(0x36421500, 0x44b87d23, 5, FALSE);
 545     testAlloc(0x36421500, 0x44b87d23, 20, FALSE);
 546     testAlloc(0x36421500, 0x44b87d23, 13700, FALSE);
 547     testAlloc(0x36421500, 0x38b87d23, 1, FALSE);
 548     testAlloc(0x36421500, 0x38b87d23, 20, FALSE);
 549     testAlloc(0x36421500, 0x38b87d23, 200, TRUE);
 550     testAlloc(0x36421500, 0x38b87d23, 13700, FALSE);
 551     testAlloc(0x36421500, 0x37b87d23, 13700, FALSE);
 552     testAlloc(0x36ef1500, 0x37b87d23, 13700, FALSE);
 553     testAlloc(0x36421500, 0x36b87d23, 13700, FALSE);
 554     testAlloc(0x36b87122, 0x36b87d23, 13700, FALSE);
 555     testAlloc(0x49000000, 0x4a600000, 13700, FALSE);
 556     testAlloc(0x9fffffff, 0xd0000000, 13700, FALSE);
 557     testAlloc(0x9fffffff, 0xd0000000, 67400, FALSE);
 558     testAlloc(0x9fffffff, 0xa0030000, 67400, FALSE);
 559     testAlloc(0x9fffffff, 0xa0030000, 40000, FALSE);
 560     testAlloc(0xa0000000, 0xa0030000, 40000, FALSE);
 561     testAlloc(0xa0031100, 0xa0030000, 40000, FALSE);
 562 #if 0
 563 #endif
 564     return 0;
 565 }
 566
 567 #endif
 568
 569 #endif /* #if !UCONFIG_NO_COLLATION */