diff options
Diffstat (limited to 'Build/source/libs/icu/icu-4.6/i18n/ucol_wgt.cpp')
-rw-r--r-- | Build/source/libs/icu/icu-4.6/i18n/ucol_wgt.cpp | 564 |
1 files changed, 564 insertions, 0 deletions
diff --git a/Build/source/libs/icu/icu-4.6/i18n/ucol_wgt.cpp b/Build/source/libs/icu/icu-4.6/i18n/ucol_wgt.cpp new file mode 100644 index 00000000000..5833ea3183d --- /dev/null +++ b/Build/source/libs/icu/icu-4.6/i18n/ucol_wgt.cpp @@ -0,0 +1,564 @@ +/* +******************************************************************************* +* +* Copyright (C) 1999-2010, International Business Machines +* Corporation and others. All Rights Reserved. +* +******************************************************************************* +* file name: ucol_wgt.c +* 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 U_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 U_INLINE uint32_t +getWeightTrail(uint32_t weight, int32_t length) { + return (uint32_t)(weight>>(8*(4-length)))&0xff; +} + +static U_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 U_INLINE uint32_t +getWeightByte(uint32_t weight, int32_t idx) { + return getWeightTrail(weight, idx); /* same calculation */ +} + +static U_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; + mask=((uint32_t)0xffffffff)>>idx; + idx=32-idx; + mask|=0xffffff00<<idx; + return (uint32_t)((weight&mask)|(byte<<idx)); +} + +static U_INLINE uint32_t +truncateWeight(uint32_t weight, int32_t length) { + return (uint32_t)(weight&(0xffffffff<<(8*(4-length)))); +} + +static U_INLINE uint32_t +incWeightTrail(uint32_t weight, int32_t length) { + return (uint32_t)(weight+(1UL<<(8*(4-length)))); +} + +static U_INLINE uint32_t +decWeightTrail(uint32_t weight, int32_t length) { + return (uint32_t)(weight-(1UL<<(8*(4-length)))); +} + +static U_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 U_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 U_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 */ |