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