• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 *******************************************************************************
5 *
6 *   Copyright (C) 1999-2015, International Business Machines
7 *   Corporation and others.  All Rights Reserved.
8 *
9 *******************************************************************************
10 *   file name:  collationweights.cpp
11 *   encoding:   UTF-8
12 *   tab size:   8 (not used)
13 *   indentation:4
14 *
15 *   created on: 2001mar08 as ucol_wgt.cpp
16 *   created by: Markus W. Scherer
17 *
18 *   This file contains code for allocating n collation element weights
19 *   between two exclusive limits.
20 *   It is used only internally by the collation tailoring builder.
21 */
22 
23 #include "unicode/utypes.h"
24 
25 #if !UCONFIG_NO_COLLATION
26 
27 #include "cmemory.h"
28 #include "collation.h"
29 #include "collationweights.h"
30 #include "uarrsort.h"
31 #include "uassert.h"
32 
33 #ifdef UCOL_DEBUG
34 #   include <stdio.h>
35 #endif
36 
37 U_NAMESPACE_BEGIN
38 
39 /* collation element weight allocation -------------------------------------- */
40 
41 /* helper functions for CE weights */
42 
43 static inline uint32_t
getWeightTrail(uint32_t weight,int32_t length)44 getWeightTrail(uint32_t weight, int32_t length) {
45     return (uint32_t)(weight>>(8*(4-length)))&0xff;
46 }
47 
48 static inline uint32_t
setWeightTrail(uint32_t weight,int32_t length,uint32_t trail)49 setWeightTrail(uint32_t weight, int32_t length, uint32_t trail) {
50     length=8*(4-length);
51     return (uint32_t)((weight&(0xffffff00<<length))|(trail<<length));
52 }
53 
54 static inline uint32_t
getWeightByte(uint32_t weight,int32_t idx)55 getWeightByte(uint32_t weight, int32_t idx) {
56     return getWeightTrail(weight, idx); /* same calculation */
57 }
58 
59 static inline uint32_t
setWeightByte(uint32_t weight,int32_t idx,uint32_t byte)60 setWeightByte(uint32_t weight, int32_t idx, uint32_t byte) {
61     uint32_t mask; /* 0xffffffff except a 00 "hole" for the index-th byte */
62 
63     idx*=8;
64     if(idx<32) {
65         mask=((uint32_t)0xffffffff)>>idx;
66     } else {
67         // Do not use uint32_t>>32 because on some platforms that does not shift at all
68         // while we need it to become 0.
69         // PowerPC: 0xffffffff>>32 = 0           (wanted)
70         // x86:     0xffffffff>>32 = 0xffffffff  (not wanted)
71         //
72         // ANSI C99 6.5.7 Bitwise shift operators:
73         // "If the value of the right operand is negative
74         // or is greater than or equal to the width of the promoted left operand,
75         // the behavior is undefined."
76         mask=0;
77     }
78     idx=32-idx;
79     mask|=0xffffff00<<idx;
80     return (uint32_t)((weight&mask)|(byte<<idx));
81 }
82 
83 static inline uint32_t
truncateWeight(uint32_t weight,int32_t length)84 truncateWeight(uint32_t weight, int32_t length) {
85     return (uint32_t)(weight&(0xffffffff<<(8*(4-length))));
86 }
87 
88 static inline uint32_t
incWeightTrail(uint32_t weight,int32_t length)89 incWeightTrail(uint32_t weight, int32_t length) {
90     return (uint32_t)(weight+(1UL<<(8*(4-length))));
91 }
92 
93 static inline uint32_t
decWeightTrail(uint32_t weight,int32_t length)94 decWeightTrail(uint32_t weight, int32_t length) {
95     return (uint32_t)(weight-(1UL<<(8*(4-length))));
96 }
97 
CollationWeights()98 CollationWeights::CollationWeights()
99         : middleLength(0), rangeIndex(0), rangeCount(0) {
100     for(int32_t i = 0; i < 5; ++i) {
101         minBytes[i] = maxBytes[i] = 0;
102     }
103 }
104 
105 void
initForPrimary(UBool compressible)106 CollationWeights::initForPrimary(UBool compressible) {
107     middleLength=1;
108     minBytes[1] = Collation::MERGE_SEPARATOR_BYTE + 1;
109     maxBytes[1] = Collation::TRAIL_WEIGHT_BYTE;
110     if(compressible) {
111         minBytes[2] = Collation::PRIMARY_COMPRESSION_LOW_BYTE + 1;
112         maxBytes[2] = Collation::PRIMARY_COMPRESSION_HIGH_BYTE - 1;
113     } else {
114         minBytes[2] = 2;
115         maxBytes[2] = 0xff;
116     }
117     minBytes[3] = 2;
118     maxBytes[3] = 0xff;
119     minBytes[4] = 2;
120     maxBytes[4] = 0xff;
121 }
122 
123 void
initForSecondary()124 CollationWeights::initForSecondary() {
125     // We use only the lower 16 bits for secondary weights.
126     middleLength=3;
127     minBytes[1] = 0;
128     maxBytes[1] = 0;
129     minBytes[2] = 0;
130     maxBytes[2] = 0;
131     minBytes[3] = Collation::LEVEL_SEPARATOR_BYTE + 1;
132     maxBytes[3] = 0xff;
133     minBytes[4] = 2;
134     maxBytes[4] = 0xff;
135 }
136 
137 void
initForTertiary()138 CollationWeights::initForTertiary() {
139     // We use only the lower 16 bits for tertiary weights.
140     middleLength=3;
141     minBytes[1] = 0;
142     maxBytes[1] = 0;
143     minBytes[2] = 0;
144     maxBytes[2] = 0;
145     // We use only 6 bits per byte.
146     // The other bits are used for case & quaternary weights.
147     minBytes[3] = Collation::LEVEL_SEPARATOR_BYTE + 1;
148     maxBytes[3] = 0x3f;
149     minBytes[4] = 2;
150     maxBytes[4] = 0x3f;
151 }
152 
153 uint32_t
incWeight(uint32_t weight,int32_t length) const154 CollationWeights::incWeight(uint32_t weight, int32_t length) const {
155     for(;;) {
156         uint32_t byte=getWeightByte(weight, length);
157         if(byte<maxBytes[length]) {
158             return setWeightByte(weight, length, byte+1);
159         } else {
160             // Roll over, set this byte to the minimum and increment the previous one.
161             weight=setWeightByte(weight, length, minBytes[length]);
162             --length;
163             U_ASSERT(length > 0);
164         }
165     }
166 }
167 
168 uint32_t
incWeightByOffset(uint32_t weight,int32_t length,int32_t offset) const169 CollationWeights::incWeightByOffset(uint32_t weight, int32_t length, int32_t offset) const {
170     for(;;) {
171         offset += getWeightByte(weight, length);
172         if((uint32_t)offset <= maxBytes[length]) {
173             return setWeightByte(weight, length, offset);
174         } else {
175             // Split the offset between this byte and the previous one.
176             offset -= minBytes[length];
177             weight = setWeightByte(weight, length, minBytes[length] + offset % countBytes(length));
178             offset /= countBytes(length);
179             --length;
180             U_ASSERT(length > 0);
181         }
182     }
183 }
184 
185 void
lengthenRange(WeightRange & range) const186 CollationWeights::lengthenRange(WeightRange &range) const {
187     int32_t length=range.length+1;
188     range.start=setWeightTrail(range.start, length, minBytes[length]);
189     range.end=setWeightTrail(range.end, length, maxBytes[length]);
190     range.count*=countBytes(length);
191     range.length=length;
192 }
193 
194 /* for uprv_sortArray: sort ranges in weight order */
195 static int32_t U_CALLCONV
compareRanges(const void *,const void * left,const void * right)196 compareRanges(const void * /*context*/, const void *left, const void *right) {
197     uint32_t l, r;
198 
199     l=((const CollationWeights::WeightRange *)left)->start;
200     r=((const CollationWeights::WeightRange *)right)->start;
201     if(l<r) {
202         return -1;
203     } else if(l>r) {
204         return 1;
205     } else {
206         return 0;
207     }
208 }
209 
210 UBool
getWeightRanges(uint32_t lowerLimit,uint32_t upperLimit)211 CollationWeights::getWeightRanges(uint32_t lowerLimit, uint32_t upperLimit) {
212     U_ASSERT(lowerLimit != 0);
213     U_ASSERT(upperLimit != 0);
214 
215     /* get the lengths of the limits */
216     int32_t lowerLength=lengthOfWeight(lowerLimit);
217     int32_t upperLength=lengthOfWeight(upperLimit);
218 
219 #ifdef UCOL_DEBUG
220     printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength);
221     printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength);
222 #endif
223     U_ASSERT(lowerLength>=middleLength);
224     // Permit upperLength<middleLength: The upper limit for secondaries is 0x10000.
225 
226     if(lowerLimit>=upperLimit) {
227 #ifdef UCOL_DEBUG
228         printf("error: no space between lower & upper limits\n");
229 #endif
230         return FALSE;
231     }
232 
233     /* check that neither is a prefix of the other */
234     if(lowerLength<upperLength) {
235         if(lowerLimit==truncateWeight(upperLimit, lowerLength)) {
236 #ifdef UCOL_DEBUG
237             printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit);
238 #endif
239             return FALSE;
240         }
241     }
242     /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */
243 
244     WeightRange lower[5], middle, upper[5]; /* [0] and [1] are not used - this simplifies indexing */
245     uprv_memset(lower, 0, sizeof(lower));
246     uprv_memset(&middle, 0, sizeof(middle));
247     uprv_memset(upper, 0, sizeof(upper));
248 
249     /*
250      * With the limit lengths of 1..4, there are up to 7 ranges for allocation:
251      * range     minimum length
252      * lower[4]  4
253      * lower[3]  3
254      * lower[2]  2
255      * middle    1
256      * upper[2]  2
257      * upper[3]  3
258      * upper[4]  4
259      *
260      * We are now going to calculate up to 7 ranges.
261      * Some of them will typically overlap, so we will then have to merge and eliminate ranges.
262      */
263     uint32_t weight=lowerLimit;
264     for(int32_t length=lowerLength; length>middleLength; --length) {
265         uint32_t trail=getWeightTrail(weight, length);
266         if(trail<maxBytes[length]) {
267             lower[length].start=incWeightTrail(weight, length);
268             lower[length].end=setWeightTrail(weight, length, maxBytes[length]);
269             lower[length].length=length;
270             lower[length].count=maxBytes[length]-trail;
271         }
272         weight=truncateWeight(weight, length-1);
273     }
274     if(weight<0xff000000) {
275         middle.start=incWeightTrail(weight, middleLength);
276     } else {
277         // Prevent overflow for primary lead byte FF
278         // which would yield a middle range starting at 0.
279         middle.start=0xffffffff;  // no middle range
280     }
281 
282     weight=upperLimit;
283     for(int32_t length=upperLength; length>middleLength; --length) {
284         uint32_t trail=getWeightTrail(weight, length);
285         if(trail>minBytes[length]) {
286             upper[length].start=setWeightTrail(weight, length, minBytes[length]);
287             upper[length].end=decWeightTrail(weight, length);
288             upper[length].length=length;
289             upper[length].count=trail-minBytes[length];
290         }
291         weight=truncateWeight(weight, length-1);
292     }
293     middle.end=decWeightTrail(weight, middleLength);
294 
295     /* set the middle range */
296     middle.length=middleLength;
297     if(middle.end>=middle.start) {
298         middle.count=(int32_t)((middle.end-middle.start)>>(8*(4-middleLength)))+1;
299     } else {
300         /* no middle range, eliminate overlaps */
301         for(int32_t length=4; length>middleLength; --length) {
302             if(lower[length].count>0 && upper[length].count>0) {
303                 // Note: The lowerEnd and upperStart weights are versions of
304                 // lowerLimit and upperLimit (which are lowerLimit<upperLimit),
305                 // truncated (still less-or-equal)
306                 // and then with their last bytes changed to the
307                 // maxByte (for lowerEnd) or minByte (for upperStart).
308                 const uint32_t lowerEnd=lower[length].end;
309                 const uint32_t upperStart=upper[length].start;
310                 UBool merged=FALSE;
311 
312                 if(lowerEnd>upperStart) {
313                     // These two lower and upper ranges collide.
314                     // Since lowerLimit<upperLimit and lowerEnd and upperStart
315                     // are versions with only their last bytes modified
316                     // (and following ones removed/reset to 0),
317                     // lowerEnd>upperStart is only possible
318                     // if the leading bytes are equal
319                     // and lastByte(lowerEnd)>lastByte(upperStart).
320                     U_ASSERT(truncateWeight(lowerEnd, length-1)==
321                             truncateWeight(upperStart, length-1));
322                     // Intersect these two ranges.
323                     lower[length].end=upper[length].end;
324                     lower[length].count=
325                             (int32_t)getWeightTrail(lower[length].end, length)-
326                             (int32_t)getWeightTrail(lower[length].start, length)+1;
327                     // count might be <=0 in which case there is no room,
328                     // and the range-collecting code below will ignore this range.
329                     merged=TRUE;
330                 } else if(lowerEnd==upperStart) {
331                     // Not possible, unless minByte==maxByte which is not allowed.
332                     U_ASSERT(minBytes[length]<maxBytes[length]);
333                 } else /* lowerEnd<upperStart */ {
334                     if(incWeight(lowerEnd, length)==upperStart) {
335                         // Merge adjacent ranges.
336                         lower[length].end=upper[length].end;
337                         lower[length].count+=upper[length].count;  // might be >countBytes
338                         merged=TRUE;
339                     }
340                 }
341                 if(merged) {
342                     // Remove all shorter ranges.
343                     // There was no room available for them between the ranges we just merged.
344                     upper[length].count=0;
345                     while(--length>middleLength) {
346                         lower[length].count=upper[length].count=0;
347                     }
348                     break;
349                 }
350             }
351         }
352     }
353 
354 #ifdef UCOL_DEBUG
355     /* print ranges */
356     for(int32_t length=4; length>=2; --length) {
357         if(lower[length].count>0) {
358             printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count);
359         }
360     }
361     if(middle.count>0) {
362         printf("middle   .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count);
363     }
364     for(int32_t length=2; length<=4; ++length) {
365         if(upper[length].count>0) {
366             printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count);
367         }
368     }
369 #endif
370 
371     /* copy the ranges, shortest first, into the result array */
372     rangeCount=0;
373     if(middle.count>0) {
374         uprv_memcpy(ranges, &middle, sizeof(WeightRange));
375         rangeCount=1;
376     }
377     for(int32_t length=middleLength+1; length<=4; ++length) {
378         /* copy upper first so that later the middle range is more likely the first one to use */
379         if(upper[length].count>0) {
380             uprv_memcpy(ranges+rangeCount, upper+length, sizeof(WeightRange));
381             ++rangeCount;
382         }
383         if(lower[length].count>0) {
384             uprv_memcpy(ranges+rangeCount, lower+length, sizeof(WeightRange));
385             ++rangeCount;
386         }
387     }
388     return rangeCount>0;
389 }
390 
391 UBool
allocWeightsInShortRanges(int32_t n,int32_t minLength)392 CollationWeights::allocWeightsInShortRanges(int32_t n, int32_t minLength) {
393     // See if the first few minLength and minLength+1 ranges have enough weights.
394     for(int32_t i = 0; i < rangeCount && ranges[i].length <= (minLength + 1); ++i) {
395         if(n <= ranges[i].count) {
396             // Use the first few minLength and minLength+1 ranges.
397             if(ranges[i].length > minLength) {
398                 // Reduce the number of weights from the last minLength+1 range
399                 // which might sort before some minLength ranges,
400                 // so that we use all weights in the minLength ranges.
401                 ranges[i].count = n;
402             }
403             rangeCount = i + 1;
404 #ifdef UCOL_DEBUG
405             printf("take first %ld ranges\n", rangeCount);
406 #endif
407 
408             if(rangeCount>1) {
409                 /* sort the ranges by weight values */
410                 UErrorCode errorCode=U_ZERO_ERROR;
411                 uprv_sortArray(ranges, rangeCount, sizeof(WeightRange),
412                                compareRanges, NULL, FALSE, &errorCode);
413                 /* ignore error code: we know that the internal sort function will not fail here */
414             }
415             return TRUE;
416         }
417         n -= ranges[i].count;  // still >0
418     }
419     return FALSE;
420 }
421 
422 UBool
allocWeightsInMinLengthRanges(int32_t n,int32_t minLength)423 CollationWeights::allocWeightsInMinLengthRanges(int32_t n, int32_t minLength) {
424     // See if the minLength ranges have enough weights
425     // when we split one and lengthen the following ones.
426     int32_t count = 0;
427     int32_t minLengthRangeCount;
428     for(minLengthRangeCount = 0;
429             minLengthRangeCount < rangeCount &&
430                 ranges[minLengthRangeCount].length == minLength;
431             ++minLengthRangeCount) {
432         count += ranges[minLengthRangeCount].count;
433     }
434 
435     int32_t nextCountBytes = countBytes(minLength + 1);
436     if(n > count * nextCountBytes) { return FALSE; }
437 
438     // Use the minLength ranges. Merge them, and then split again as necessary.
439     uint32_t start = ranges[0].start;
440     uint32_t end = ranges[0].end;
441     for(int32_t i = 1; i < minLengthRangeCount; ++i) {
442         if(ranges[i].start < start) { start = ranges[i].start; }
443         if(ranges[i].end > end) { end = ranges[i].end; }
444     }
445 
446     // Calculate how to split the range between minLength (count1) and minLength+1 (count2).
447     // Goal:
448     //   count1 + count2 * nextCountBytes = n
449     //   count1 + count2 = count
450     // These turn into
451     //   (count - count2) + count2 * nextCountBytes = n
452     // and then into the following count1 & count2 computations.
453     int32_t count2 = (n - count) / (nextCountBytes - 1);  // number of weights to be lengthened
454     int32_t count1 = count - count2;  // number of minLength weights
455     if(count2 == 0 || (count1 + count2 * nextCountBytes) < n) {
456         // round up
457         ++count2;
458         --count1;
459         U_ASSERT((count1 + count2 * nextCountBytes) >= n);
460     }
461 
462     ranges[0].start = start;
463 
464     if(count1 == 0) {
465         // Make one long range.
466         ranges[0].end = end;
467         ranges[0].count = count;
468         lengthenRange(ranges[0]);
469         rangeCount = 1;
470     } else {
471         // Split the range, lengthen the second part.
472 #ifdef UCOL_DEBUG
473         printf("split the range number %ld (out of %ld minLength ranges) by %ld:%ld\n",
474                splitRange, rangeCount, count1, count2);
475 #endif
476 
477         // Next start = start + count1. First end = 1 before that.
478         ranges[0].end = incWeightByOffset(start, minLength, count1 - 1);
479         ranges[0].count = count1;
480 
481         ranges[1].start = incWeight(ranges[0].end, minLength);
482         ranges[1].end = end;
483         ranges[1].length = minLength;  // +1 when lengthened
484         ranges[1].count = count2;  // *countBytes when lengthened
485         lengthenRange(ranges[1]);
486         rangeCount = 2;
487     }
488     return TRUE;
489 }
490 
491 /*
492  * call getWeightRanges and then determine heuristically
493  * which ranges to use for a given number of weights between (excluding)
494  * two limits
495  */
496 UBool
allocWeights(uint32_t lowerLimit,uint32_t upperLimit,int32_t n)497 CollationWeights::allocWeights(uint32_t lowerLimit, uint32_t upperLimit, int32_t n) {
498 #ifdef UCOL_DEBUG
499     puts("");
500 #endif
501 
502     if(!getWeightRanges(lowerLimit, upperLimit)) {
503 #ifdef UCOL_DEBUG
504         printf("error: unable to get Weight ranges\n");
505 #endif
506         return FALSE;
507     }
508 
509     /* try until we find suitably large ranges */
510     for(;;) {
511         /* get the smallest number of bytes in a range */
512         int32_t minLength=ranges[0].length;
513 
514         if(allocWeightsInShortRanges(n, minLength)) { break; }
515 
516         if(minLength == 4) {
517 #ifdef UCOL_DEBUG
518             printf("error: the maximum number of %ld weights is insufficient for n=%ld\n",
519                    minLengthCount, n);
520 #endif
521             return FALSE;
522         }
523 
524         if(allocWeightsInMinLengthRanges(n, minLength)) { break; }
525 
526         /* no good match, lengthen all minLength ranges and iterate */
527 #ifdef UCOL_DEBUG
528         printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1);
529 #endif
530         for(int32_t i=0; i<rangeCount && ranges[i].length==minLength; ++i) {
531             lengthenRange(ranges[i]);
532         }
533     }
534 
535 #ifdef UCOL_DEBUG
536     puts("final ranges:");
537     for(int32_t i=0; i<rangeCount; ++i) {
538         printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .count=%ld\n",
539                i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].count);
540     }
541 #endif
542 
543     rangeIndex = 0;
544     return TRUE;
545 }
546 
547 uint32_t
nextWeight()548 CollationWeights::nextWeight() {
549     if(rangeIndex >= rangeCount) {
550         return 0xffffffff;
551     } else {
552         /* get the next weight */
553         WeightRange &range = ranges[rangeIndex];
554         uint32_t weight = range.start;
555         if(--range.count == 0) {
556             /* this range is finished */
557             ++rangeIndex;
558         } else {
559             /* increment the weight for the next value */
560             range.start = incWeight(weight, range.length);
561             U_ASSERT(range.start <= range.end);
562         }
563 
564         return weight;
565     }
566 }
567 
568 U_NAMESPACE_END
569 
570 #endif /* #if !UCONFIG_NO_COLLATION */
571