2
*******************************************************************************
4
* Copyright (C) 1999-2001, International Business Machines
5
* Corporation and others. All Rights Reserved.
7
*******************************************************************************
8
* file name: ucol_wgt.c
10
* tab size: 8 (not used)
13
* created on: 2001mar08
14
* created by: Markus W. Scherer
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.
25
/* we are using qsort() */
28
#include "unicode/utypes.h"
33
#if defined(UCOL_DEBUG) && defined(WIN32)
34
/* turn off "unreferenced formal parameter" */
35
# pragma warning(disable: 4100)
38
/* collation element weight allocation -------------------------------------- */
40
/* helper functions for CE weights */
43
lengthOfWeight(uint32_t weight) {
44
if((weight&0xffffff)==0) {
46
} else if((weight&0xffff)==0) {
48
} else if((weight&0xff)==0) {
56
getWeightTrail(uint32_t weight, int32_t length) {
57
return (uint32_t)(weight>>(8*(4-length)))&0xff;
61
setWeightTrail(uint32_t weight, int32_t length, uint32_t trail) {
63
return (uint32_t)((weight&(0xffffff00<<length))|(trail<<length));
67
getWeightByte(uint32_t weight, int32_t index) {
68
return getWeightTrail(weight, index); /* same calculation */
72
setWeightByte(uint32_t weight, int32_t index, uint32_t byte) {
73
uint32_t mask; /* 0xffffffff except a 00 "hole" for the index-th byte */
76
mask=0xffffffff>>index;
78
mask|=0xffffff00<<index;
79
return (uint32_t)((weight&mask)|(byte<<index));
83
truncateWeight(uint32_t weight, int32_t length) {
84
return (uint32_t)(weight&(0xffffffff<<(8*(4-length))));
88
incWeightTrail(uint32_t weight, int32_t length) {
89
return (uint32_t)(weight+(1UL<<(8*(4-length))));
93
decWeightTrail(uint32_t weight, int32_t length) {
94
return (uint32_t)(weight-(1UL<<(8*(4-length))));
98
incWeight(uint32_t weight, int32_t length, uint32_t maxByte) {
102
byte=getWeightByte(weight, length);
104
return setWeightByte(weight, length, byte+1);
106
/* roll over, set this byte to UCOL_BYTE_FIRST_TAILORED and increment the previous one */
107
weight=setWeightByte(weight, length, UCOL_BYTE_FIRST_TAILORED);
114
lengthenRange(WeightRange *range, uint32_t maxByte, uint32_t countBytes) {
117
length=range->length2+1;
118
range->start=setWeightTrail(range->start, length, UCOL_BYTE_FIRST_TAILORED);
119
range->end=setWeightTrail(range->end, length, maxByte);
120
range->count2*=countBytes;
121
range->length2=length;
125
/* for qsort: sort ranges in weight order */
127
compareRanges(const void *left, const void *right) {
130
l=((const WeightRange *)left)->start;
131
r=((const WeightRange *)right)->start;
142
* take two CE weights and calculate the
143
* possible ranges of weights between the two limits, excluding them
144
* for weights with up to 4 bytes there are up to 2*4-1=7 ranges
147
getWeightRanges(uint32_t lowerLimit, uint32_t upperLimit,
148
uint32_t maxByte, uint32_t countBytes,
149
WeightRange ranges[7]) {
150
WeightRange lower[5], middle, upper[5]; /* [0] and [1] are not used - this simplifies indexing */
151
uint32_t weight, trail;
152
int32_t length, lowerLength, upperLength, rangeCount;
154
/* assume that both lowerLimit & upperLimit are not 0 */
156
/* get the lengths of the limits */
157
lowerLength=lengthOfWeight(lowerLimit);
158
upperLength=lengthOfWeight(upperLimit);
161
printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength);
162
printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength);
165
if(lowerLimit>=upperLimit) {
167
printf("error: no space between lower & upper limits\n");
172
/* check that neither is a prefix of the other */
173
if(lowerLength<upperLength) {
174
if(lowerLimit==truncateWeight(upperLimit, lowerLength)) {
176
printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit);
181
/* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */
183
/* reset local variables */
184
uprv_memset(lower, 0, sizeof(lower));
185
uprv_memset(&middle, 0, sizeof(middle));
186
uprv_memset(upper, 0, sizeof(upper));
189
* With the limit lengths of 1..4, there are up to 7 ranges for allocation:
190
* range minimum length
199
* We are now going to calculate up to 7 ranges.
200
* Some of them will typically overlap, so we will then have to merge and eliminate ranges.
203
for(length=lowerLength; length>=2; --length) {
204
trail=getWeightTrail(weight, length);
206
lower[length].start=incWeightTrail(weight, length);
207
lower[length].end=setWeightTrail(weight, length, maxByte);
208
lower[length].length=length;
209
lower[length].count=maxByte-trail;
211
weight=truncateWeight(weight, length-1);
213
middle.start=incWeightTrail(weight, 1);
216
for(length=upperLength; length>=2; --length) {
217
trail=getWeightTrail(weight, length);
218
if(trail>UCOL_BYTE_FIRST_TAILORED) {
219
upper[length].start=setWeightTrail(weight, length, UCOL_BYTE_FIRST_TAILORED);
220
upper[length].end=decWeightTrail(weight, length);
221
upper[length].length=length;
222
upper[length].count=trail-UCOL_BYTE_FIRST_TAILORED;
224
weight=truncateWeight(weight, length-1);
226
middle.end=decWeightTrail(weight, 1);
228
/* set the middle range */
230
if(middle.end>=middle.start) {
231
middle.count=(int32_t)((middle.end-middle.start)>>24)+1;
233
/* eliminate overlaps */
236
/* remove the middle range */
239
/* reduce or remove the lower ranges that go beyond upperLimit */
240
for(length=4; length>=2; --length) {
241
if(lower[length].count>0 && upper[length].count>0) {
242
start=upper[length].start;
243
end=lower[length].end;
245
if(end>=start || incWeight(end, length, maxByte)==start) {
246
/* lower and upper ranges collide or are directly adjacent: merge these two and remove all shorter ranges */
247
start=lower[length].start;
248
end=lower[length].end=upper[length].end;
250
* merging directly adjacent ranges needs to subtract the 0/1 gaps in between;
251
* it may result in a range with count>countBytes
254
(int32_t)(getWeightTrail(end, length)-getWeightTrail(start, length)+1+
255
countBytes*(getWeightByte(end, length-1)-getWeightByte(start, length-1)));
256
upper[length].count=0;
258
lower[length].count=upper[length].count=0;
268
for(length=4; length>=2; --length) {
269
if(lower[length].count>0) {
270
printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count);
274
printf("middle .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count);
276
for(length=2; length<=4; ++length) {
277
if(upper[length].count>0) {
278
printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count);
283
/* copy the ranges, shortest first, into the result array */
286
uprv_memcpy(ranges, &middle, sizeof(WeightRange));
289
for(length=2; length<=4; ++length) {
290
/* copy upper first so that later the middle range is more likely the first one to use */
291
if(upper[length].count>0) {
292
uprv_memcpy(ranges+rangeCount, upper+length, sizeof(WeightRange));
295
if(lower[length].count>0) {
296
uprv_memcpy(ranges+rangeCount, lower+length, sizeof(WeightRange));
304
* call getWeightRanges and then determine heuristically
305
* which ranges to use for a given number of weights between (excluding)
309
ucol_allocWeights(uint32_t lowerLimit, uint32_t upperLimit,
312
WeightRange ranges[7]) {
313
/* number of usable byte values 3..maxByte */
314
uint32_t countBytes=maxByte-UCOL_BYTE_FIRST_TAILORED+1;
316
uint32_t lengthCounts[6]; /* [0] unused, [5] to make index checks unnecessary */
318
int32_t i, rangeCount, minLength, maxLength;
320
/* countBytes to the power of index */
322
/* gcc requires explicit initialization */
324
powers[1] = countBytes;
325
powers[2] = countBytes*countBytes;
326
powers[3] = countBytes*countBytes*countBytes;
327
powers[4] = countBytes*countBytes*countBytes*countBytes;
333
rangeCount=getWeightRanges(lowerLimit, upperLimit, maxByte, countBytes, ranges);
336
printf("error: unable to get Weight ranges\n");
341
/* what is the maximum number of weights with these ranges? */
343
for(i=0; i<rangeCount; ++i) {
344
maxCount+=(uint32_t)ranges[i].count*powers[4-ranges[i].length];
348
printf("the maximum number of %lu weights is sufficient for n=%lu\n", maxCount, n);
352
printf("error: the maximum number of %lu weights is insufficient for n=%lu\n", maxCount, n);
357
/* set the length2 and count2 fields */
358
for(i=0; i<rangeCount; ++i) {
359
ranges[i].length2=ranges[i].length;
360
ranges[i].count2=(uint32_t)ranges[i].count;
363
/* try until we find suitably large ranges */
365
/* get the smallest number of bytes in a range */
366
minLength=ranges[0].length2;
368
/* sum up the number of elements that fit into ranges of each byte length */
369
uprv_memset(lengthCounts, 0, sizeof(lengthCounts));
370
for(i=0; i<rangeCount; ++i) {
371
lengthCounts[ranges[i].length2]+=ranges[i].count2;
374
/* now try to allocate n elements in the available short ranges */
375
if(n<=(lengthCounts[minLength]+lengthCounts[minLength+1])) {
376
/* trivial cases, use the first few ranges */
380
maxCount+=ranges[rangeCount].count2;
384
printf("take first %ld ranges\n", rangeCount);
387
} else if(n<=ranges[0].count2*countBytes) {
388
/* easy case, just make this one range large enough by lengthening it once more, possibly split it */
389
uint32_t count1, count2, power_1, power;
392
maxLength=minLength+1;
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;
400
/* split the range */
402
printf("split the first range %ld:%ld\n", count1, count2);
405
/* lengthen the entire range to maxLength */
406
lengthenRange(ranges, maxByte, countBytes);
408
/* really split the range */
411
/* create a new range with the end and initial and current length of the old one */
413
ranges[1].end=ranges[0].end;
414
ranges[1].length=ranges[0].length;
415
ranges[1].length2=minLength;
417
/* set the end of the first range according to count1 */
419
byte=getWeightByte(ranges[0].start, i)+count1-1;
422
* ranges[0].count and count1 may be >countBytes
423
* from merging adjacent ranges;
424
* byte>maxByte is possible
427
ranges[0].end=setWeightByte(ranges[0].start, i, byte);
428
} else /* byte>maxByte */ {
429
ranges[0].end=setWeightByte(incWeight(ranges[0].start, i-1, maxByte), i, byte-countBytes);
432
/* set the bytes in the end weight at length+1..length2 to maxByte */
433
byte=(maxByte<<24)|(maxByte<<16)|(maxByte<<8)|maxByte; /* this used to be 0xffffffff */
434
ranges[0].end=truncateWeight(ranges[0].end, i)|
435
((byte>>(8*i))&(byte<<(8*(4-minLength))));
437
/* set the start of the second range to immediately follow the end of the first one */
438
ranges[1].start=incWeight(ranges[0].end, minLength, maxByte);
440
/* set the count values (informational) */
441
ranges[0].count=count1;
442
ranges[1].count=count2;
444
ranges[0].count2=count1*power_1;
445
ranges[1].count2=count2*power_1; /* will be *countBytes when lengthened */
447
/* lengthen the second range to maxLength */
448
lengthenRange(ranges+1, maxByte, countBytes);
453
/* no good match, lengthen all minLength ranges and iterate */
455
printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1);
457
for(i=0; ranges[i].length2==minLength; ++i) {
458
lengthenRange(ranges+i, maxByte, countBytes);
463
/* sort the ranges by weight values */
464
qsort(ranges, rangeCount, sizeof(WeightRange), compareRanges);
468
puts("final ranges:");
469
for(i=0; i<rangeCount; ++i) {
470
printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .length2=%ld .count=%ld .count2=%lu\n",
471
i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].length2, ranges[i].count, ranges[i].count2);
475
/* set maxByte in ranges[0] for ucol_nextWeight() */
476
ranges[0].count=maxByte;
482
* given a set of ranges calculated by ucol_allocWeights(),
483
* iterate through the weights
486
ucol_nextWeight(WeightRange ranges[], int32_t *pRangeCount) {
487
if(*pRangeCount<=0) {
490
uint32_t weight, maxByte;
492
/* get maxByte from the .count field */
493
maxByte=ranges[0].count;
495
/* get the next weight */
496
weight=ranges[0].start;
497
if(weight==ranges[0].end) {
498
/* this range is finished, remove it and move the following ones up */
499
if(--*pRangeCount>0) {
500
uprv_memmove(ranges, ranges+1, *pRangeCount*sizeof(WeightRange));
501
ranges[0].count=maxByte; /* keep maxByte in ranges[0] */
504
/* increment the weight for the next value */
505
ranges[0].start=incWeight(weight, ranges[0].length2, maxByte);
515
testAlloc(uint32_t lowerLimit, uint32_t upperLimit, uint32_t n, UBool enumerate) {
516
WeightRange ranges[8];
519
rangeCount=ucol_allocWeights(lowerLimit, upperLimit, n, ranges);
524
weight=ucol_nextWeight(ranges, &rangeCount);
525
if(weight==0xffffffff) {
526
printf("error: 0xffffffff with %lu more weights to go\n", n);
529
printf(" 0x%08lx\n", weight);
536
main(int argc, const char *argv[]) {
539
testAlloc(0x364214fc, 0x44b87d23, 5, FALSE);
540
testAlloc(0x36421500, 0x44b87d23, 5, FALSE);
541
testAlloc(0x36421500, 0x44b87d23, 20, FALSE);
542
testAlloc(0x36421500, 0x44b87d23, 13700, FALSE);
543
testAlloc(0x36421500, 0x38b87d23, 1, FALSE);
544
testAlloc(0x36421500, 0x38b87d23, 20, FALSE);
545
testAlloc(0x36421500, 0x38b87d23, 200, TRUE);
546
testAlloc(0x36421500, 0x38b87d23, 13700, FALSE);
547
testAlloc(0x36421500, 0x37b87d23, 13700, FALSE);
548
testAlloc(0x36ef1500, 0x37b87d23, 13700, FALSE);
549
testAlloc(0x36421500, 0x36b87d23, 13700, FALSE);
550
testAlloc(0x36b87122, 0x36b87d23, 13700, FALSE);
551
testAlloc(0x49000000, 0x4a600000, 13700, FALSE);
552
testAlloc(0x9fffffff, 0xd0000000, 13700, FALSE);
553
testAlloc(0x9fffffff, 0xd0000000, 67400, FALSE);
554
testAlloc(0x9fffffff, 0xa0030000, 67400, FALSE);
555
testAlloc(0x9fffffff, 0xa0030000, 40000, FALSE);
556
testAlloc(0xa0000000, 0xa0030000, 40000, FALSE);
557
testAlloc(0xa0031100, 0xa0030000, 40000, FALSE);
added
removed
source/i18n/ucol_wgt.c
