12d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert// © 2016 and later: Unicode, Inc. and others. 22d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert// License & terms of use: http://www.unicode.org/copyright.html#License 32d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert/* 47935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert******************************************************************************* 57935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert* 6bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert* Copyright (C) 1999-2015, International Business Machines 77935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert* Corporation and others. All Rights Reserved. 87935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert* 97935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert******************************************************************************* 107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert* CollationWeights.java, ported from collationweights.h/.cpp 117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert* 127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert* C++ version created on: 2001mar08 as ucol_wgt.h 137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert* created by: Markus W. Scherer 147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert*/ 157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertpackage com.ibm.icu.impl.coll; 177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.util.Arrays; 197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert/** 217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Allocates n collation element weights between two exclusive limits. 227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Used only internally by the collation tailoring builder. 237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertpublic final class CollationWeights { 257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public CollationWeights() {} 267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void initForPrimary(boolean compressible) { 287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert middleLength=1; 297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[1] = Collation.MERGE_SEPARATOR_BYTE + 1; 307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[1] = Collation.TRAIL_WEIGHT_BYTE; 317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(compressible) { 327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[2] = Collation.PRIMARY_COMPRESSION_LOW_BYTE + 1; 337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[2] = Collation.PRIMARY_COMPRESSION_HIGH_BYTE - 1; 347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[2] = 2; 367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[2] = 0xff; 377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[3] = 2; 397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[3] = 0xff; 407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[4] = 2; 417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[4] = 0xff; 427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void initForSecondary() { 457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // We use only the lower 16 bits for secondary weights. 467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert middleLength=3; 477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[1] = 0; 487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[1] = 0; 497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[2] = 0; 507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[2] = 0; 51f716bda031dccdec5e47bb40e758c5901d209729Fredrik Roubert minBytes[3] = Collation.LEVEL_SEPARATOR_BYTE + 1; 527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[3] = 0xff; 537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[4] = 2; 547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[4] = 0xff; 557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void initForTertiary() { 587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // We use only the lower 16 bits for tertiary weights. 597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert middleLength=3; 607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[1] = 0; 617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[1] = 0; 627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[2] = 0; 637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[2] = 0; 647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // We use only 6 bits per byte. 657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // The other bits are used for case & quaternary weights. 66f716bda031dccdec5e47bb40e758c5901d209729Fredrik Roubert minBytes[3] = Collation.LEVEL_SEPARATOR_BYTE + 1; 677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[3] = 0x3f; 687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minBytes[4] = 2; 697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxBytes[4] = 0x3f; 707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Determine heuristically 747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * what ranges to use for a given number of weights between (excluding) 757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * two limits. 767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param lowerLimit A collation element weight; the ranges will be filled to cover 787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * weights greater than this one. 797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param upperLimit A collation element weight; the ranges will be filled to cover 807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * weights less than this one. 817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param n The number of collation element weights w necessary such that 827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * lowerLimit<w<upperLimit in lexical order. 837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return true if it is possible to fit n elements between the limits 847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public boolean allocWeights(long lowerLimit, long upperLimit, int n) { 867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Call getWeightRanges() and then determine heuristically 877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // which ranges to use for a given number of weights between (excluding) 887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // two limits. 897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // puts(""); 907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(!getWeightRanges(lowerLimit, upperLimit)) { 927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("error: unable to get Weight ranges\n"); 937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* try until we find suitably large ranges */ 977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(;;) { 987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* get the smallest number of bytes in a range */ 997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int minLength=ranges[0].length; 1007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(allocWeightsInShortRanges(n, minLength)) { break; } 1027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(minLength == 4) { 1047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("error: the maximum number of %ld weights is insufficient for n=%ld\n", 1057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // minLengthCount, n); 1067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 1077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(allocWeightsInMinLengthRanges(n, minLength)) { break; } 1107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* no good match, lengthen all minLength ranges and iterate */ 1127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1); 113fe77e7203e518f62b5bd8e8c603bca361e9cf47bFredrik Roubert for (int i = 0; i < rangeCount && ranges[i].length == minLength; ++i) { 1147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lengthenRange(ranges[i]); 1157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* puts("final ranges:"); 1197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int i=0; i<rangeCount; ++i) { 1207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .count=%ld\n", 1217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].count); 1227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } */ 1237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rangeIndex = 0; 1257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(rangeCount < ranges.length) { 1267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[rangeCount] = null; // force a crash when going out of bounds 1277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return true; 1297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 1327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Given a set of ranges calculated by allocWeights(), 1337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * iterate through the weights. 1347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The ranges are modified to keep the current iteration state. 1357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 1367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return The next weight in the ranges, or 0xffffffff if there is none left. 1377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 1387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public long nextWeight() { 1397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(rangeIndex >= rangeCount) { 1407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0xffffffffL; 1417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 1427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* get the next weight */ 1437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert WeightRange range = ranges[rangeIndex]; 1447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert long weight = range.start; 1457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(--range.count == 0) { 1467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* this range is finished */ 1477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ++rangeIndex; 1487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 1497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* increment the weight for the next value */ 1507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert range.start = incWeight(weight, range.length); 1517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert assert(range.start <= range.end); 1527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return weight; 1557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** @internal */ 1597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static final class WeightRange implements Comparable<WeightRange> { 1607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert long start, end; 1617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int length, count; 1627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1632d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 1647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int compareTo(WeightRange other) { 1657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert long l=start; 1667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert long r=other.start; 1677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(l<r) { 1687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return -1; 1697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if(l>r) { 1707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 1; 1717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 1727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0; 1737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* helper functions for CE weights */ 1787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public static int lengthOfWeight(long weight) { 1807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if((weight&0xffffff)==0) { 1817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 1; 1827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if((weight&0xffff)==0) { 1837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 2; 1847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if((weight&0xff)==0) { 1857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 3; 1867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 1877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 4; 1887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static int getWeightTrail(long weight, int length) { 1927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return (int)(weight>>(8*(4-length)))&0xff; 1937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static long setWeightTrail(long weight, int length, int trail) { 1967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert length=8*(4-length); 1977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return (weight&(0xffffff00L<<length))|((long)trail<<length); 1987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static int getWeightByte(long weight, int idx) { 2017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return getWeightTrail(weight, idx); /* same calculation */ 2027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static long setWeightByte(long weight, int idx, int b) { 2057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert long mask; /* 0xffffffff except a 00 "hole" for the index-th byte */ 2067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert idx*=8; 2087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(idx<32) { 2097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mask=0xffffffffL>>idx; 2107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 2117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Do not use int>>32 because on some platforms that does not shift at all 2127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // while we need it to become 0. 2137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // PowerPC: 0xffffffff>>32 = 0 (wanted) 2147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // x86: 0xffffffff>>32 = 0xffffffff (not wanted) 2157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 2167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // ANSI C99 6.5.7 Bitwise shift operators: 2177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // "If the value of the right operand is negative 2187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // or is greater than or equal to the width of the promoted left operand, 2197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // the behavior is undefined." 2207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mask=0; 2217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert idx=32-idx; 2237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mask|=0xffffff00L<<idx; 2247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return (weight&mask)|((long)b<<idx); 2257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static long truncateWeight(long weight, int length) { 2287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return weight&(0xffffffffL<<(8*(4-length))); 2297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static long incWeightTrail(long weight, int length) { 2327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return weight+(1L<<(8*(4-length))); 2337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static long decWeightTrail(long weight, int length) { 2367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return weight-(1L<<(8*(4-length))); 2377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** @return number of usable byte values for byte idx */ 2407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int countBytes(int idx) { 2417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return maxBytes[idx] - minBytes[idx] + 1; 2427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private long incWeight(long weight, int length) { 2457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(;;) { 2467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int b=getWeightByte(weight, length); 2477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(b<maxBytes[length]) { 2487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return setWeightByte(weight, length, b+1); 2497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 2507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Roll over, set this byte to the minimum and increment the previous one. 2517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert weight=setWeightByte(weight, length, minBytes[length]); 2527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert --length; 2537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert assert(length > 0); 2547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private long incWeightByOffset(long weight, int length, int offset) { 2597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(;;) { 2607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert offset += getWeightByte(weight, length); 2617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(offset <= maxBytes[length]) { 2627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return setWeightByte(weight, length, offset); 2637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 2647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Split the offset between this byte and the previous one. 2657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert offset -= minBytes[length]; 2667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert weight = setWeightByte(weight, length, minBytes[length] + offset % countBytes(length)); 2677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert offset /= countBytes(length); 2687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert --length; 2697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert assert(length > 0); 2707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private void lengthenRange(WeightRange range) { 2757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int length=range.length+1; 2767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert range.start=setWeightTrail(range.start, length, minBytes[length]); 2777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert range.end=setWeightTrail(range.end, length, maxBytes[length]); 2787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert range.count*=countBytes(length); 2797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert range.length=length; 2807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 2837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Takes two CE weights and calculates the 2847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * possible ranges of weights between the two limits, excluding them. 2857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * For weights with up to 4 bytes there are up to 2*4-1=7 ranges. 2867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 2877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private boolean getWeightRanges(long lowerLimit, long upperLimit) { 2887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert assert(lowerLimit != 0); 2897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert assert(upperLimit != 0); 2907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* get the lengths of the limits */ 2927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int lowerLength=lengthOfWeight(lowerLimit); 2937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int upperLength=lengthOfWeight(upperLimit); 2947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength); 2967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength); 2977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert assert(lowerLength>=middleLength); 2987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Permit upperLength<middleLength: The upper limit for secondaries is 0x10000. 2997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(lowerLimit>=upperLimit) { 3017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("error: no space between lower & upper limits\n"); 3027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 3037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* check that neither is a prefix of the other */ 3067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(lowerLength<upperLength) { 3077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(lowerLimit==truncateWeight(upperLimit, lowerLength)) { 3087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit); 3097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 3107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */ 3137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert WeightRange[] lower = new WeightRange[5]; /* [0] and [1] are not used - this simplifies indexing */ 3157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert WeightRange middle = new WeightRange(); 3167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert WeightRange[] upper = new WeightRange[5]; 3177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 3197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * With the limit lengths of 1..4, there are up to 7 ranges for allocation: 3207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * range minimum length 3217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * lower[4] 4 3227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * lower[3] 3 3237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * lower[2] 2 3247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * middle 1 3257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * upper[2] 2 3267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * upper[3] 3 3277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * upper[4] 4 3287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 3297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * We are now going to calculate up to 7 ranges. 3307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Some of them will typically overlap, so we will then have to merge and eliminate ranges. 3317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 3327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert long weight=lowerLimit; 3337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int length=lowerLength; length>middleLength; --length) { 3347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int trail=getWeightTrail(weight, length); 3357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(trail<maxBytes[length]) { 3367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lower[length] = new WeightRange(); 3377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lower[length].start=incWeightTrail(weight, length); 3387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lower[length].end=setWeightTrail(weight, length, maxBytes[length]); 3397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lower[length].length=length; 3407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lower[length].count=maxBytes[length]-trail; 3417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert weight=truncateWeight(weight, length-1); 3437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(weight<0xff000000L) { 3457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert middle.start=incWeightTrail(weight, middleLength); 3467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 3477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Prevent overflow for primary lead byte FF 3487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // which would yield a middle range starting at 0. 3497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert middle.start=0xffffffffL; // no middle range 3507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert weight=upperLimit; 3537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int length=upperLength; length>middleLength; --length) { 3547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int trail=getWeightTrail(weight, length); 3557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(trail>minBytes[length]) { 3567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert upper[length] = new WeightRange(); 3577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert upper[length].start=setWeightTrail(weight, length, minBytes[length]); 3587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert upper[length].end=decWeightTrail(weight, length); 3597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert upper[length].length=length; 3607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert upper[length].count=trail-minBytes[length]; 3617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert weight=truncateWeight(weight, length-1); 3637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert middle.end=decWeightTrail(weight, middleLength); 3657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* set the middle range */ 3677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert middle.length=middleLength; 3687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(middle.end>=middle.start) { 3697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert middle.count=(int)((middle.end-middle.start)>>(8*(4-middleLength)))+1; 3707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 3717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* no middle range, eliminate overlaps */ 3727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int length=4; length>middleLength; --length) { 3737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(lower[length] != null && upper[length] != null && 3747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lower[length].count>0 && upper[length].count>0) { 375bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // Note: The lowerEnd and upperStart weights are versions of 376bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // lowerLimit and upperLimit (which are lowerLimit<upperLimit), 377bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // truncated (still less-or-equal) 378bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // and then with their last bytes changed to the 379bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // maxByte (for lowerEnd) or minByte (for upperStart). 380bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert final long lowerEnd=lower[length].end; 381bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert final long upperStart=upper[length].start; 382bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert boolean merged=false; 383bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert 384bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert if(lowerEnd>upperStart) { 385bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // These two lower and upper ranges collide. 386bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // Since lowerLimit<upperLimit and lowerEnd and upperStart 387bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // are versions with only their last bytes modified 388bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // (and following ones removed/reset to 0), 389bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // lowerEnd>upperStart is only possible 390bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // if the leading bytes are equal 391bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // and lastByte(lowerEnd)>lastByte(upperStart). 392bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert assert(truncateWeight(lowerEnd, length-1)== 393bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert truncateWeight(upperStart, length-1)); 394bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // Intersect these two ranges. 395bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert lower[length].end=upper[length].end; 3967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lower[length].count= 397bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert getWeightTrail(lower[length].end, length)- 398bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert getWeightTrail(lower[length].start, length)+1; 399bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // count might be <=0 in which case there is no room, 400bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // and the range-collecting code below will ignore this range. 401bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert merged=true; 402bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert } else if(lowerEnd==upperStart) { 403bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // Not possible, unless minByte==maxByte which is not allowed. 404bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert assert(minBytes[length]<maxBytes[length]); 405bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert } else /* lowerEnd<upperStart */ { 406bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert if(incWeight(lowerEnd, length)==upperStart) { 407bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // Merge adjacent ranges. 408bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert lower[length].end=upper[length].end; 409bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert lower[length].count+=upper[length].count; // might be >countBytes 410bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert merged=true; 411bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert } 412bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert } 413bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert if(merged) { 414bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // Remove all shorter ranges. 415bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert // There was no room available for them between the ranges we just merged. 4167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert upper[length].count=0; 4177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert while(--length>middleLength) { 418bd1cbb618dcaa1ac6ba7c77dece35cb79593a5d7Fredrik Roubert lower[length]=upper[length]=null; 4197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 4217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* print ranges 4277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int length=4; length>=2; --length) { 4287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(lower[length].count>0) { 4297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count); 4307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(middle.count>0) { 4337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert printf("middle .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count); 4347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int length=2; length<=4; ++length) { 4367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(upper[length].count>0) { 4377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count); 4387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } */ 4407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* copy the ranges, shortest first, into the result array */ 4427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rangeCount=0; 4437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(middle.count>0) { 4447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[0] = middle; 4457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rangeCount=1; 4467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int length=middleLength+1; length<=4; ++length) { 4487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* copy upper first so that later the middle range is more likely the first one to use */ 4497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(upper[length] != null && upper[length].count>0) { 4507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[rangeCount++]=upper[length]; 4517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(lower[length] != null && lower[length].count>0) { 4537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[rangeCount++]=lower[length]; 4547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return rangeCount>0; 4577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private boolean allocWeightsInShortRanges(int n, int minLength) { 4607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // See if the first few minLength and minLength+1 ranges have enough weights. 4617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int i = 0; i < rangeCount && ranges[i].length <= (minLength + 1); ++i) { 4627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(n <= ranges[i].count) { 4637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Use the first few minLength and minLength+1 ranges. 4647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(ranges[i].length > minLength) { 4657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Reduce the number of weights from the last minLength+1 range 4667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // which might sort before some minLength ranges, 4677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // so that we use all weights in the minLength ranges. 4687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[i].count = n; 4697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rangeCount = i + 1; 4717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("take first %ld ranges\n", rangeCount); 4727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(rangeCount>1) { 4747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* sort the ranges by weight values */ 4757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Arrays.sort(ranges, 0, rangeCount); 4767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return true; 4787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert n -= ranges[i].count; // still >0 4807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 4827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private boolean allocWeightsInMinLengthRanges(int n, int minLength) { 4857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // See if the minLength ranges have enough weights 4867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // when we split one and lengthen the following ones. 4877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int count = 0; 4887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int minLengthRangeCount; 4897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(minLengthRangeCount = 0; 4907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert minLengthRangeCount < rangeCount && 4917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[minLengthRangeCount].length == minLength; 4927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ++minLengthRangeCount) { 4937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert count += ranges[minLengthRangeCount].count; 4947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int nextCountBytes = countBytes(minLength + 1); 4977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(n > count * nextCountBytes) { return false; } 4987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Use the minLength ranges. Merge them, and then split again as necessary. 5007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert long start = ranges[0].start; 5017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert long end = ranges[0].end; 5027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for(int i = 1; i < minLengthRangeCount; ++i) { 5037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(ranges[i].start < start) { start = ranges[i].start; } 5047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(ranges[i].end > end) { end = ranges[i].end; } 5057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Calculate how to split the range between minLength (count1) and minLength+1 (count2). 5087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Goal: 5097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // count1 + count2 * nextCountBytes = n 5107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // count1 + count2 = count 5117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // These turn into 5127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // (count - count2) + count2 * nextCountBytes = n 5137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // and then into the following count1 & count2 computations. 5147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int count2 = (n - count) / (nextCountBytes - 1); // number of weights to be lengthened 5157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int count1 = count - count2; // number of minLength weights 5167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(count2 == 0 || (count1 + count2 * nextCountBytes) < n) { 5177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // round up 5187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ++count2; 5197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert --count1; 5207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert assert((count1 + count2 * nextCountBytes) >= n); 5217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[0].start = start; 5247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(count1 == 0) { 5267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Make one long range. 5277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[0].end = end; 5287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[0].count = count; 5297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lengthenRange(ranges[0]); 5307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rangeCount = 1; 5317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 5327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Split the range, lengthen the second part. 5337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // printf("split the range number %ld (out of %ld minLength ranges) by %ld:%ld\n", 5347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // splitRange, rangeCount, count1, count2); 5357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Next start = start + count1. First end = 1 before that. 5377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[0].end = incWeightByOffset(start, minLength, count1 - 1); 5387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[0].count = count1; 5397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(ranges[1] == null) { 5417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[1] = new WeightRange(); 5427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[1].start = incWeight(ranges[0].end, minLength); 5447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[1].end = end; 5457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[1].length = minLength; // +1 when lengthened 5467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ranges[1].count = count2; // *countBytes when lengthened 5477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lengthenRange(ranges[1]); 5487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rangeCount = 2; 5497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return true; 5517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int middleLength; 5547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int[] minBytes = new int[5]; // for byte 1, 2, 3, 4 5557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int[] maxBytes = new int[5]; 5567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private WeightRange[] ranges = new WeightRange[7]; 5577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int rangeIndex; 5587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int rangeCount; 5597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert} 560