Check in the pristine copy of ICU 4.6...

icu46/source/i18n/ucol_wgt.cpp

+/*  
+*******************************************************************************
+*
+*   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 */