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
37U_NAMESPACE_BEGIN
38
39/* collation element weight allocation -------------------------------------- */
40
41/* helper functions for CE weights */
42
43static inline uint32_t
44getWeightTrail(uint32_t weight, int32_t length) {
45 return (uint32_t)(weight>>(8*(4-length)))&0xff;
46}
47
48static inline uint32_t
49setWeightTrail(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
54static inline uint32_t
55getWeightByte(uint32_t weight, int32_t idx) {
56 return getWeightTrail(weight, idx); /* same calculation */
57}
58
59static inline uint32_t
60setWeightByte(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
83static inline uint32_t
84truncateWeight(uint32_t weight, int32_t length) {
85 return (uint32_t)(weight&(0xffffffff<<(8*(4-length))));
86}
87
88static inline uint32_t
89incWeightTrail(uint32_t weight, int32_t length) {
90 return (uint32_t)(weight+(1UL<<(8*(4-length))));
91}
92
93static inline uint32_t
94decWeightTrail(uint32_t weight, int32_t length) {
95 return (uint32_t)(weight-(1UL<<(8*(4-length))));
96}
97
98CollationWeights::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
105void
106CollationWeights::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
123void
124CollationWeights::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
137void
138CollationWeights::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
153uint32_t
154CollationWeights::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
168uint32_t
169CollationWeights::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
185void
186CollationWeights::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 */
195static int32_t U_CALLCONV
196compareRanges(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
210UBool
211CollationWeights::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
391UBool
392CollationWeights::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
422UBool
423CollationWeights::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 */
496UBool
497CollationWeights::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
547uint32_t
548CollationWeights::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
568U_NAMESPACE_END
569
570#endif /* #if !UCONFIG_NO_COLLATION */
571