The Tor Browser: intl/icu/source/i18n/ucol_wgt.cpp@6474c204b198 (annotated)

intl/icu/source/i18n/ucol_wgt.cpp@6474c204b198 (annotated)

intl/icu/source/i18n/ucol_wgt.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /*
 *******************************************************************************
 *
 *   Copyright (C) 1999-2011, International Business Machines
 *   Corporation and others.  All Rights Reserved.
 *
 *******************************************************************************
 *   file name:  ucol_wgt.cpp
 *   encoding:   US-ASCII
 *   tab size:   8 (not used)
 *   indentation:4
 *
 *   created on: 2001mar08
 *   created by: Markus W. Scherer
 *
 *   This file contains code for allocating n collation element weights
 *   between two exclusive limits.
 *   It is used only internally by ucol_bld.
 */
 #include "unicode/utypes.h"
 #if !UCONFIG_NO_COLLATION
 #include "ucol_imp.h"
 #include "ucol_wgt.h"
 #include "cmemory.h"
 #include "uarrsort.h"
 #ifdef UCOL_DEBUG
 #   include <stdio.h>
 #endif
 /* collation element weight allocation -------------------------------------- */
 /* helper functions for CE weights */
 static inline int32_t
 lengthOfWeight(uint32_t weight) {
     if((weight&0xffffff)==0) {
         return 1;
     } else if((weight&0xffff)==0) {
         return 2;
     } else if((weight&0xff)==0) {
         return 3;
     } else {
         return 4;
     }
 }
 static inline uint32_t
 getWeightTrail(uint32_t weight, int32_t length) {
     return (uint32_t)(weight>>(8*(4-length)))&0xff;
 }
 static inline uint32_t
 setWeightTrail(uint32_t weight, int32_t length, uint32_t trail) {
     length=8*(4-length);
     return (uint32_t)((weight&(0xffffff00<<length))|(trail<<length));
 }
 static inline uint32_t
 getWeightByte(uint32_t weight, int32_t idx) {
     return getWeightTrail(weight, idx); /* same calculation */
 }
 static inline uint32_t
 setWeightByte(uint32_t weight, int32_t idx, uint32_t byte) {
     uint32_t mask; /* 0xffffffff except a 00 "hole" for the index-th byte */
     idx*=8;
     if(idx<32) {
         mask=((uint32_t)0xffffffff)>>idx;
     } else {
         // Do not use uint32_t>>32 because on some platforms that does not shift at all
         // while we need it to become 0.
         // PowerPC: 0xffffffff>>32 = 0           (wanted)
         // x86:     0xffffffff>>32 = 0xffffffff  (not wanted)
         //
         // ANSI C99 6.5.7 Bitwise shift operators:
         // "If the value of the right operand is negative
         // or is greater than or equal to the width of the promoted left operand,
         // the behavior is undefined."
         mask=0;
     }
     idx=32-idx;
     mask|=0xffffff00<<idx;
     return (uint32_t)((weight&mask)|(byte<<idx));
 }
 static inline uint32_t
 truncateWeight(uint32_t weight, int32_t length) {
     return (uint32_t)(weight&(0xffffffff<<(8*(4-length))));
 }
 static inline uint32_t
 incWeightTrail(uint32_t weight, int32_t length) {
     return (uint32_t)(weight+(1UL<<(8*(4-length))));
 }
 static inline uint32_t
 decWeightTrail(uint32_t weight, int32_t length) {
     return (uint32_t)(weight-(1UL<<(8*(4-length))));
 }
 static inline uint32_t
 incWeight(uint32_t weight, int32_t length, uint32_t maxByte) {
     uint32_t byte;
     for(;;) {
         byte=getWeightByte(weight, length);
         if(byte<maxByte) {
             return setWeightByte(weight, length, byte+1);
         } else {
             /* roll over, set this byte to UCOL_BYTE_FIRST_TAILORED and increment the previous one */
             weight=setWeightByte(weight, length, UCOL_BYTE_FIRST_TAILORED);
             --length;
         }
     }
 }
 static inline int32_t
 lengthenRange(WeightRange *range, uint32_t maxByte, uint32_t countBytes) {
     int32_t length;
     length=range->length2+1;
     range->start=setWeightTrail(range->start, length, UCOL_BYTE_FIRST_TAILORED);
     range->end=setWeightTrail(range->end, length, maxByte);
     range->count2*=countBytes;
     range->length2=length;
     return length;
 }
 /* for uprv_sortArray: sort ranges in weight order */
 static int32_t U_CALLCONV
 compareRanges(const void * /*context*/, const void *left, const void *right) {
     uint32_t l, r;
     l=((const WeightRange *)left)->start;
     r=((const WeightRange *)right)->start;
     if(l<r) {
         return -1;
     } else if(l>r) {
         return 1;
     } else {
         return 0;
     }
 }
 /*
  * take two CE weights and calculate the
  * possible ranges of weights between the two limits, excluding them
  * for weights with up to 4 bytes there are up to 2*4-1=7 ranges
  */
 static inline int32_t
 getWeightRanges(uint32_t lowerLimit, uint32_t upperLimit,
                 uint32_t maxByte, uint32_t countBytes,
                 WeightRange ranges[7]) {
     WeightRange lower[5], middle, upper[5]; /* [0] and [1] are not used - this simplifies indexing */
     uint32_t weight, trail;
     int32_t length, lowerLength, upperLength, rangeCount;
     /* assume that both lowerLimit & upperLimit are not 0 */
     /* get the lengths of the limits */
     lowerLength=lengthOfWeight(lowerLimit);
     upperLength=lengthOfWeight(upperLimit);
 #ifdef UCOL_DEBUG
     printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength);
     printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength);
 #endif
     if(lowerLimit>=upperLimit) {
 #ifdef UCOL_DEBUG
         printf("error: no space between lower & upper limits\n");
 #endif
         return 0;
     }
     /* check that neither is a prefix of the other */
     if(lowerLength<upperLength) {
         if(lowerLimit==truncateWeight(upperLimit, lowerLength)) {
 #ifdef UCOL_DEBUG
             printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit);
 #endif
             return 0;
         }
     }
     /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */
     /* reset local variables */
     uprv_memset(lower, 0, sizeof(lower));
     uprv_memset(&middle, 0, sizeof(middle));
     uprv_memset(upper, 0, sizeof(upper));
     /*
      * With the limit lengths of 1..4, there are up to 7 ranges for allocation:
      * range     minimum length
      * lower[4]  4
      * lower[3]  3
      * lower[2]  2
      * middle    1
      * upper[2]  2
      * upper[3]  3
      * upper[4]  4
      *
      * We are now going to calculate up to 7 ranges.
      * Some of them will typically overlap, so we will then have to merge and eliminate ranges.
      */
     weight=lowerLimit;
     for(length=lowerLength; length>=2; --length) {
         trail=getWeightTrail(weight, length);
         if(trail<maxByte) {
             lower[length].start=incWeightTrail(weight, length);
             lower[length].end=setWeightTrail(weight, length, maxByte);
             lower[length].length=length;
             lower[length].count=maxByte-trail;
         }
         weight=truncateWeight(weight, length-1);
     }
     middle.start=incWeightTrail(weight, 1);
     weight=upperLimit;
     for(length=upperLength; length>=2; --length) {
         trail=getWeightTrail(weight, length);
         if(trail>UCOL_BYTE_FIRST_TAILORED) {
             upper[length].start=setWeightTrail(weight, length, UCOL_BYTE_FIRST_TAILORED);
             upper[length].end=decWeightTrail(weight, length);
             upper[length].length=length;
             upper[length].count=trail-UCOL_BYTE_FIRST_TAILORED;
         }
         weight=truncateWeight(weight, length-1);
     }
     middle.end=decWeightTrail(weight, 1);
     /* set the middle range */
     middle.length=1;
     if(middle.end>=middle.start) {
         middle.count=(int32_t)((middle.end-middle.start)>>24)+1;
     } else {
         /* eliminate overlaps */
         uint32_t start, end;
         /* remove the middle range */
         middle.count=0;
         /* reduce or remove the lower ranges that go beyond upperLimit */
         for(length=4; length>=2; --length) {
             if(lower[length].count>0 && upper[length].count>0) {
                 start=upper[length].start;
                 end=lower[length].end;
                 if(end>=start || incWeight(end, length, maxByte)==start) {
                     /* lower and upper ranges collide or are directly adjacent: merge these two and remove all shorter ranges */
                     start=lower[length].start;
                     end=lower[length].end=upper[length].end;
                     /*
                      * merging directly adjacent ranges needs to subtract the 0/1 gaps in between;
                      * it may result in a range with count>countBytes
                      */
                     lower[length].count=
                         (int32_t)(getWeightTrail(end, length)-getWeightTrail(start, length)+1+
                                   countBytes*(getWeightByte(end, length-1)-getWeightByte(start, length-1)));
                     upper[length].count=0;
                     while(--length>=2) {
                         lower[length].count=upper[length].count=0;
                     }
                     break;
                 }
             }
         }
     }
 #ifdef UCOL_DEBUG
     /* print ranges */
     for(length=4; length>=2; --length) {
         if(lower[length].count>0) {
             printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count);
         }
     }
     if(middle.count>0) {
         printf("middle   .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count);
     }
     for(length=2; length<=4; ++length) {
         if(upper[length].count>0) {
             printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count);
         }
     }
 #endif
     /* copy the ranges, shortest first, into the result array */
     rangeCount=0;
     if(middle.count>0) {
         uprv_memcpy(ranges, &middle, sizeof(WeightRange));
         rangeCount=1;
     }
     for(length=2; length<=4; ++length) {
         /* copy upper first so that later the middle range is more likely the first one to use */
         if(upper[length].count>0) {
             uprv_memcpy(ranges+rangeCount, upper+length, sizeof(WeightRange));
             ++rangeCount;
         }
         if(lower[length].count>0) {
             uprv_memcpy(ranges+rangeCount, lower+length, sizeof(WeightRange));
             ++rangeCount;
         }
     }
     return rangeCount;
 }
 /*
  * call getWeightRanges and then determine heuristically
  * which ranges to use for a given number of weights between (excluding)
  * two limits
  */
 U_CFUNC int32_t
 ucol_allocWeights(uint32_t lowerLimit, uint32_t upperLimit,
                   uint32_t n,
                   uint32_t maxByte,
                   WeightRange ranges[7]) {
     /* number of usable byte values 3..maxByte */
     uint32_t countBytes=maxByte-UCOL_BYTE_FIRST_TAILORED+1;
     uint32_t lengthCounts[6]; /* [0] unused, [5] to make index checks unnecessary */
     uint32_t maxCount;
     int32_t i, rangeCount, minLength/*, maxLength*/;
     /* countBytes to the power of index */
     uint32_t powers[5];
     /* gcc requires explicit initialization */
     powers[0] = 1;
     powers[1] = countBytes;
     powers[2] = countBytes*countBytes;
     powers[3] = countBytes*countBytes*countBytes;
     powers[4] = countBytes*countBytes*countBytes*countBytes;
 #ifdef UCOL_DEBUG
     puts("");
 #endif
     rangeCount=getWeightRanges(lowerLimit, upperLimit, maxByte, countBytes, ranges);
     if(rangeCount<=0) {
 #ifdef UCOL_DEBUG
         printf("error: unable to get Weight ranges\n");
 #endif
         return 0;
     }
     /* what is the maximum number of weights with these ranges? */
     maxCount=0;
     for(i=0; i<rangeCount; ++i) {
         maxCount+=(uint32_t)ranges[i].count*powers[4-ranges[i].length];
     }
     if(maxCount>=n) {
 #ifdef UCOL_DEBUG
         printf("the maximum number of %lu weights is sufficient for n=%lu\n", maxCount, n);
 #endif
     } else {
 #ifdef UCOL_DEBUG
         printf("error: the maximum number of %lu weights is insufficient for n=%lu\n", maxCount, n);
 #endif
         return 0;
     }
     /* set the length2 and count2 fields */
     for(i=0; i<rangeCount; ++i) {
         ranges[i].length2=ranges[i].length;
         ranges[i].count2=(uint32_t)ranges[i].count;
     }
     /* try until we find suitably large ranges */
     for(;;) {
         /* get the smallest number of bytes in a range */
         minLength=ranges[0].length2;
         /* sum up the number of elements that fit into ranges of each byte length */
         uprv_memset(lengthCounts, 0, sizeof(lengthCounts));
         for(i=0; i<rangeCount; ++i) {
             lengthCounts[ranges[i].length2]+=ranges[i].count2;
         }
         /* now try to allocate n elements in the available short ranges */
         if(n<=(lengthCounts[minLength]+lengthCounts[minLength+1])) {
             /* trivial cases, use the first few ranges */
             maxCount=0;
             rangeCount=0;
             do {
                 maxCount+=ranges[rangeCount].count2;
                 ++rangeCount;
             } while(n>maxCount);
 #ifdef UCOL_DEBUG
             printf("take first %ld ranges\n", rangeCount);
 #endif
             break;
         } else if(n<=ranges[0].count2*countBytes) {
             /* easy case, just make this one range large enough by lengthening it once more, possibly split it */
             uint32_t count1, count2, power_1, power;
             /*maxLength=minLength+1;*/
             /* calculate how to split the range between maxLength-1 (count1) and maxLength (count2) */
             power_1=powers[minLength-ranges[0].length];
             power=power_1*countBytes;
             count2=(n+power-1)/power;
             count1=ranges[0].count-count2;
             /* split the range */
 #ifdef UCOL_DEBUG
             printf("split the first range %ld:%ld\n", count1, count2);
 #endif
             if(count1<1) {
                 rangeCount=1;
                 /* lengthen the entire range to maxLength */
                 lengthenRange(ranges, maxByte, countBytes);
             } else {
                 /* really split the range */
                 uint32_t byte;
                 /* create a new range with the end and initial and current length of the old one */
                 rangeCount=2;
                 ranges[1].end=ranges[0].end;
                 ranges[1].length=ranges[0].length;
                 ranges[1].length2=minLength;
                 /* set the end of the first range according to count1 */
                 i=ranges[0].length;
                 byte=getWeightByte(ranges[0].start, i)+count1-1;
                 /*
                  * ranges[0].count and count1 may be >countBytes
                  * from merging adjacent ranges;
                  * byte>maxByte is possible
                  */
                 if(byte<=maxByte) {
                     ranges[0].end=setWeightByte(ranges[0].start, i, byte);
                 } else /* byte>maxByte */ {
                     ranges[0].end=setWeightByte(incWeight(ranges[0].start, i-1, maxByte), i, byte-countBytes);
                 }
                 /* set the bytes in the end weight at length+1..length2 to maxByte */
                 byte=(maxByte<<24)|(maxByte<<16)|(maxByte<<8)|maxByte; /* this used to be 0xffffffff */
                 ranges[0].end=truncateWeight(ranges[0].end, i)|
                               ((byte>>(8*i))&(byte<<(8*(4-minLength))));
                 /* set the start of the second range to immediately follow the end of the first one */
                 ranges[1].start=incWeight(ranges[0].end, minLength, maxByte);
                 /* set the count values (informational) */
                 ranges[0].count=count1;
                 ranges[1].count=count2;
                 ranges[0].count2=count1*power_1;
                 ranges[1].count2=count2*power_1; /* will be *countBytes when lengthened */
                 /* lengthen the second range to maxLength */
                 lengthenRange(ranges+1, maxByte, countBytes);
             }
             break;
         }
         /* no good match, lengthen all minLength ranges and iterate */
 #ifdef UCOL_DEBUG
         printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1);
 #endif
         for(i=0; ranges[i].length2==minLength; ++i) {
             lengthenRange(ranges+i, maxByte, countBytes);
         }
     }
     if(rangeCount>1) {
         /* sort the ranges by weight values */
         UErrorCode errorCode=U_ZERO_ERROR;
         uprv_sortArray(ranges, rangeCount, sizeof(WeightRange), compareRanges, NULL, FALSE, &errorCode);
         /* ignore error code: we know that the internal sort function will not fail here */
     }
 #ifdef UCOL_DEBUG
     puts("final ranges:");
     for(i=0; i<rangeCount; ++i) {
         printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .length2=%ld .count=%ld .count2=%lu\n",
                i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].length2, ranges[i].count, ranges[i].count2);
     }
 #endif
     /* set maxByte in ranges[0] for ucol_nextWeight() */
     ranges[0].count=maxByte;
     return rangeCount;
 }
 /*
  * given a set of ranges calculated by ucol_allocWeights(),
  * iterate through the weights
  */
 U_CFUNC uint32_t
 ucol_nextWeight(WeightRange ranges[], int32_t *pRangeCount) {
     if(*pRangeCount<=0) {
         return 0xffffffff;
     } else {
         uint32_t weight, maxByte;
         /* get maxByte from the .count field */
         maxByte=ranges[0].count;
         /* get the next weight */
         weight=ranges[0].start;
         if(weight==ranges[0].end) {
             /* this range is finished, remove it and move the following ones up */
             if(--*pRangeCount>0) {
                 uprv_memmove(ranges, ranges+1, *pRangeCount*sizeof(WeightRange));
                 ranges[0].count=maxByte; /* keep maxByte in ranges[0] */
             }
         } else {
             /* increment the weight for the next value */
             ranges[0].start=incWeight(weight, ranges[0].length2, maxByte);
         }
         return weight;
     }
 }
 #if 0 // #ifdef UCOL_DEBUG
 static void
 testAlloc(uint32_t lowerLimit, uint32_t upperLimit, uint32_t n, UBool enumerate) {
     WeightRange ranges[8];
     int32_t rangeCount;
     rangeCount=ucol_allocWeights(lowerLimit, upperLimit, n, ranges);
     if(enumerate) {
         uint32_t weight;
         while(n>0) {
             weight=ucol_nextWeight(ranges, &rangeCount);
             if(weight==0xffffffff) {
                 printf("error: 0xffffffff with %lu more weights to go\n", n);
                 break;
             }
             printf("    0x%08lx\n", weight);
             --n;
         }
     }
 }
 extern int
 main(int argc, const char *argv[]) {
 #if 0
 #endif
     testAlloc(0x364214fc, 0x44b87d23, 5, FALSE);
     testAlloc(0x36421500, 0x44b87d23, 5, FALSE);
     testAlloc(0x36421500, 0x44b87d23, 20, FALSE);
     testAlloc(0x36421500, 0x44b87d23, 13700, FALSE);
     testAlloc(0x36421500, 0x38b87d23, 1, FALSE);
     testAlloc(0x36421500, 0x38b87d23, 20, FALSE);
     testAlloc(0x36421500, 0x38b87d23, 200, TRUE);
     testAlloc(0x36421500, 0x38b87d23, 13700, FALSE);
     testAlloc(0x36421500, 0x37b87d23, 13700, FALSE);
     testAlloc(0x36ef1500, 0x37b87d23, 13700, FALSE);
     testAlloc(0x36421500, 0x36b87d23, 13700, FALSE);
     testAlloc(0x36b87122, 0x36b87d23, 13700, FALSE);
     testAlloc(0x49000000, 0x4a600000, 13700, FALSE);
     testAlloc(0x9fffffff, 0xd0000000, 13700, FALSE);
     testAlloc(0x9fffffff, 0xd0000000, 67400, FALSE);
     testAlloc(0x9fffffff, 0xa0030000, 67400, FALSE);
     testAlloc(0x9fffffff, 0xa0030000, 40000, FALSE);
     testAlloc(0xa0000000, 0xa0030000, 40000, FALSE);
     testAlloc(0xa0031100, 0xa0030000, 40000, FALSE);
 #if 0
 #endif
     return 0;
 }
 #endif
 #endif /* #if !UCONFIG_NO_COLLATION */

The Tor Browser / annotate

intl/icu/source/i18n/ucol_wgt.cpp@6474c204b198 (annotated)

intl/icu/source/i18n/ucol_wgt.cpp