CollationWeights.java revision 2ae130017183d2f66d55bf0ca51f8da3294644fd
12ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller/* GENERATED SOURCE. DO NOT MODIFY. */ 22ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller/* 32ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller******************************************************************************* 42ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller* 52ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller* Copyright (C) 1999-2015, International Business Machines 62ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller* Corporation and others. All Rights Reserved. 72ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller* 82ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller******************************************************************************* 92ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller* CollationWeights.java, ported from collationweights.h/.cpp 102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller* 112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller* C++ version created on: 2001mar08 as ucol_wgt.h 122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller* created by: Markus W. Scherer 132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller*/ 142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerpackage android.icu.impl.coll; 162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerimport java.util.Arrays; 182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller/** 202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * Allocates n collation element weights between two exclusive limits. 212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * Used only internally by the collation tailoring builder. 222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller */ 232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerpublic final class CollationWeights { 242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller public CollationWeights() {} 252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller public void initForPrimary(boolean compressible) { 272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller middleLength=1; 282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[1] = Collation.MERGE_SEPARATOR_BYTE + 1; 292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[1] = Collation.TRAIL_WEIGHT_BYTE; 302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(compressible) { 312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[2] = Collation.PRIMARY_COMPRESSION_LOW_BYTE + 1; 322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[2] = Collation.PRIMARY_COMPRESSION_HIGH_BYTE - 1; 332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[2] = 2; 352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[2] = 0xff; 362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[3] = 2; 382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[3] = 0xff; 392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[4] = 2; 402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[4] = 0xff; 412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller public void initForSecondary() { 442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // We use only the lower 16 bits for secondary weights. 452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller middleLength=3; 462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[1] = 0; 472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[1] = 0; 482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[2] = 0; 492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[2] = 0; 502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[3] = Collation.LEVEL_SEPARATOR_BYTE + 1; 512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[3] = 0xff; 522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[4] = 2; 532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[4] = 0xff; 542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller public void initForTertiary() { 572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // We use only the lower 16 bits for tertiary weights. 582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller middleLength=3; 592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[1] = 0; 602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[1] = 0; 612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[2] = 0; 622ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[2] = 0; 632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // We use only 6 bits per byte. 642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // The other bits are used for case & quaternary weights. 652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[3] = Collation.LEVEL_SEPARATOR_BYTE + 1; 662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[3] = 0x3f; 672ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minBytes[4] = 2; 682ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller maxBytes[4] = 0x3f; 692ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 702ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 712ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /** 722ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * Determine heuristically 732ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * what ranges to use for a given number of weights between (excluding) 742ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * two limits. 752ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * 762ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * @param lowerLimit A collation element weight; the ranges will be filled to cover 772ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * weights greater than this one. 782ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * @param upperLimit A collation element weight; the ranges will be filled to cover 792ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * weights less than this one. 802ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * @param n The number of collation element weights w necessary such that 812ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * lowerLimit<w<upperLimit in lexical order. 822ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * @return true if it is possible to fit n elements between the limits 832ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller */ 842ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller public boolean allocWeights(long lowerLimit, long upperLimit, int n) { 852ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Call getWeightRanges() and then determine heuristically 862ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // which ranges to use for a given number of weights between (excluding) 872ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // two limits. 882ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // puts(""); 892ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 902ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(!getWeightRanges(lowerLimit, upperLimit)) { 912ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("error: unable to get Weight ranges\n"); 922ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return false; 932ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 942ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 952ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* try until we find suitably large ranges */ 962ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(;;) { 972ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* get the smallest number of bytes in a range */ 982ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int minLength=ranges[0].length; 992ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1002ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(allocWeightsInShortRanges(n, minLength)) { break; } 1012ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1022ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(minLength == 4) { 1032ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("error: the maximum number of %ld weights is insufficient for n=%ld\n", 1042ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // minLengthCount, n); 1052ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return false; 1062ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1072ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1082ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(allocWeightsInMinLengthRanges(n, minLength)) { break; } 1092ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* no good match, lengthen all minLength ranges and iterate */ 1112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1); 1122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int i=0; ranges[i].length==minLength; ++i) { 1132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lengthenRange(ranges[i]); 1142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* puts("final ranges:"); 1182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int i=0; i<rangeCount; ++i) { 1192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .count=%ld\n", 1202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].count); 1212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } */ 1222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller rangeIndex = 0; 1242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(rangeCount < ranges.length) { 1252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[rangeCount] = null; // force a crash when going out of bounds 1262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return true; 1282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /** 1312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * Given a set of ranges calculated by allocWeights(), 1322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * iterate through the weights. 1332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * The ranges are modified to keep the current iteration state. 1342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * 1352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * @return The next weight in the ranges, or 0xffffffff if there is none left. 1362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller */ 1372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller public long nextWeight() { 1382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(rangeIndex >= rangeCount) { 1392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return 0xffffffffL; 1402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 1412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* get the next weight */ 1422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller WeightRange range = ranges[rangeIndex]; 1432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller long weight = range.start; 1442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(--range.count == 0) { 1452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* this range is finished */ 1462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ++rangeIndex; 1472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 1482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* increment the weight for the next value */ 1492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller range.start = incWeight(weight, range.length); 1502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert(range.start <= range.end); 1512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return weight; 1542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /** @internal */ 1582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private static final class WeightRange implements Comparable<WeightRange> { 1592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller long start, end; 1602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int length, count; 1612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1622ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Java 6: @Override 1632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller public int compareTo(WeightRange other) { 1642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller long l=start; 1652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller long r=other.start; 1662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(l<r) { 1672ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return -1; 1682ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else if(l>r) { 1692ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return 1; 1702ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 1712ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return 0; 1722ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1732ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1742ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1752ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1762ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* helper functions for CE weights */ 1772ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1782ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller public static int lengthOfWeight(long weight) { 1792ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if((weight&0xffffff)==0) { 1802ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return 1; 1812ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else if((weight&0xffff)==0) { 1822ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return 2; 1832ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else if((weight&0xff)==0) { 1842ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return 3; 1852ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 1862ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return 4; 1872ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1882ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1892ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1902ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private static int getWeightTrail(long weight, int length) { 1912ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return (int)(weight>>(8*(4-length)))&0xff; 1922ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1932ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1942ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private static long setWeightTrail(long weight, int length, int trail) { 1952ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller length=8*(4-length); 1962ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return (weight&(0xffffff00L<<length))|((long)trail<<length); 1972ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1982ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1992ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private static int getWeightByte(long weight, int idx) { 2002ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return getWeightTrail(weight, idx); /* same calculation */ 2012ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2022ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2032ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private static long setWeightByte(long weight, int idx, int b) { 2042ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller long mask; /* 0xffffffff except a 00 "hole" for the index-th byte */ 2052ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2062ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller idx*=8; 2072ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(idx<32) { 2082ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller mask=0xffffffffL>>idx; 2092ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 2102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Do not use int>>32 because on some platforms that does not shift at all 2112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // while we need it to become 0. 2122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // PowerPC: 0xffffffff>>32 = 0 (wanted) 2132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // x86: 0xffffffff>>32 = 0xffffffff (not wanted) 2142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 2152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // ANSI C99 6.5.7 Bitwise shift operators: 2162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // "If the value of the right operand is negative 2172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // or is greater than or equal to the width of the promoted left operand, 2182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // the behavior is undefined." 2192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller mask=0; 2202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller idx=32-idx; 2222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller mask|=0xffffff00L<<idx; 2232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return (weight&mask)|((long)b<<idx); 2242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private static long truncateWeight(long weight, int length) { 2272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return weight&(0xffffffffL<<(8*(4-length))); 2282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private static long incWeightTrail(long weight, int length) { 2312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return weight+(1L<<(8*(4-length))); 2322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private static long decWeightTrail(long weight, int length) { 2352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return weight-(1L<<(8*(4-length))); 2362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /** @return number of usable byte values for byte idx */ 2392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private int countBytes(int idx) { 2402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return maxBytes[idx] - minBytes[idx] + 1; 2412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private long incWeight(long weight, int length) { 2442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(;;) { 2452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int b=getWeightByte(weight, length); 2462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(b<maxBytes[length]) { 2472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return setWeightByte(weight, length, b+1); 2482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 2492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Roll over, set this byte to the minimum and increment the previous one. 2502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller weight=setWeightByte(weight, length, minBytes[length]); 2512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller --length; 2522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert(length > 0); 2532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private long incWeightByOffset(long weight, int length, int offset) { 2582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(;;) { 2592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller offset += getWeightByte(weight, length); 2602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(offset <= maxBytes[length]) { 2612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return setWeightByte(weight, length, offset); 2622ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 2632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Split the offset between this byte and the previous one. 2642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller offset -= minBytes[length]; 2652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller weight = setWeightByte(weight, length, minBytes[length] + offset % countBytes(length)); 2662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller offset /= countBytes(length); 2672ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller --length; 2682ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert(length > 0); 2692ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2702ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2712ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2722ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2732ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private void lengthenRange(WeightRange range) { 2742ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int length=range.length+1; 2752ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller range.start=setWeightTrail(range.start, length, minBytes[length]); 2762ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller range.end=setWeightTrail(range.end, length, maxBytes[length]); 2772ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller range.count*=countBytes(length); 2782ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller range.length=length; 2792ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2802ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2812ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /** 2822ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * Takes two CE weights and calculates the 2832ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * possible ranges of weights between the two limits, excluding them. 2842ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * For weights with up to 4 bytes there are up to 2*4-1=7 ranges. 2852ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller */ 2862ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private boolean getWeightRanges(long lowerLimit, long upperLimit) { 2872ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert(lowerLimit != 0); 2882ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert(upperLimit != 0); 2892ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2902ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* get the lengths of the limits */ 2912ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int lowerLength=lengthOfWeight(lowerLimit); 2922ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int upperLength=lengthOfWeight(upperLimit); 2932ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2942ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength); 2952ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength); 2962ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert(lowerLength>=middleLength); 2972ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Permit upperLength<middleLength: The upper limit for secondaries is 0x10000. 2982ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2992ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(lowerLimit>=upperLimit) { 3002ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("error: no space between lower & upper limits\n"); 3012ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return false; 3022ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3032ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3042ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* check that neither is a prefix of the other */ 3052ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(lowerLength<upperLength) { 3062ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(lowerLimit==truncateWeight(upperLimit, lowerLength)) { 3072ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit); 3082ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return false; 3092ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */ 3122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller WeightRange[] lower = new WeightRange[5]; /* [0] and [1] are not used - this simplifies indexing */ 3142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller WeightRange middle = new WeightRange(); 3152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller WeightRange[] upper = new WeightRange[5]; 3162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* 3182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * With the limit lengths of 1..4, there are up to 7 ranges for allocation: 3192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * range minimum length 3202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * lower[4] 4 3212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * lower[3] 3 3222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * lower[2] 2 3232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * middle 1 3242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * upper[2] 2 3252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * upper[3] 3 3262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * upper[4] 4 3272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * 3282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * We are now going to calculate up to 7 ranges. 3292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * Some of them will typically overlap, so we will then have to merge and eliminate ranges. 3302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller */ 3312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller long weight=lowerLimit; 3322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int length=lowerLength; length>middleLength; --length) { 3332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int trail=getWeightTrail(weight, length); 3342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(trail<maxBytes[length]) { 3352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length] = new WeightRange(); 3362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].start=incWeightTrail(weight, length); 3372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].end=setWeightTrail(weight, length, maxBytes[length]); 3382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].length=length; 3392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].count=maxBytes[length]-trail; 3402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller weight=truncateWeight(weight, length-1); 3422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(weight<0xff000000L) { 3442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller middle.start=incWeightTrail(weight, middleLength); 3452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 3462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Prevent overflow for primary lead byte FF 3472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // which would yield a middle range starting at 0. 3482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller middle.start=0xffffffffL; // no middle range 3492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller weight=upperLimit; 3522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int length=upperLength; length>middleLength; --length) { 3532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int trail=getWeightTrail(weight, length); 3542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(trail>minBytes[length]) { 3552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller upper[length] = new WeightRange(); 3562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller upper[length].start=setWeightTrail(weight, length, minBytes[length]); 3572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller upper[length].end=decWeightTrail(weight, length); 3582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller upper[length].length=length; 3592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller upper[length].count=trail-minBytes[length]; 3602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller weight=truncateWeight(weight, length-1); 3622ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller middle.end=decWeightTrail(weight, middleLength); 3642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* set the middle range */ 3662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller middle.length=middleLength; 3672ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(middle.end>=middle.start) { 3682ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller middle.count=(int)((middle.end-middle.start)>>(8*(4-middleLength)))+1; 3692ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 3702ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* no middle range, eliminate overlaps */ 3712ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int length=4; length>middleLength; --length) { 3722ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(lower[length] != null && upper[length] != null && 3732ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].count>0 && upper[length].count>0) { 3742ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Note: The lowerEnd and upperStart weights are versions of 3752ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // lowerLimit and upperLimit (which are lowerLimit<upperLimit), 3762ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // truncated (still less-or-equal) 3772ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // and then with their last bytes changed to the 3782ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // maxByte (for lowerEnd) or minByte (for upperStart). 3792ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller final long lowerEnd=lower[length].end; 3802ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller final long upperStart=upper[length].start; 3812ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller boolean merged=false; 3822ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3832ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(lowerEnd>upperStart) { 3842ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // These two lower and upper ranges collide. 3852ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Since lowerLimit<upperLimit and lowerEnd and upperStart 3862ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // are versions with only their last bytes modified 3872ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // (and following ones removed/reset to 0), 3882ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // lowerEnd>upperStart is only possible 3892ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // if the leading bytes are equal 3902ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // and lastByte(lowerEnd)>lastByte(upperStart). 3912ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert(truncateWeight(lowerEnd, length-1)== 3922ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller truncateWeight(upperStart, length-1)); 3932ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Intersect these two ranges. 3942ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].end=upper[length].end; 3952ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].count= 3962ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller getWeightTrail(lower[length].end, length)- 3972ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller getWeightTrail(lower[length].start, length)+1; 3982ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // count might be <=0 in which case there is no room, 3992ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // and the range-collecting code below will ignore this range. 4002ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller merged=true; 4012ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else if(lowerEnd==upperStart) { 4022ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Not possible, unless minByte==maxByte which is not allowed. 4032ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert(minBytes[length]<maxBytes[length]); 4042ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else /* lowerEnd<upperStart */ { 4052ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(incWeight(lowerEnd, length)==upperStart) { 4062ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Merge adjacent ranges. 4072ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].end=upper[length].end; 4082ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length].count+=upper[length].count; // might be >countBytes 4092ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller merged=true; 4102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(merged) { 4132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Remove all shorter ranges. 4142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // There was no room available for them between the ranges we just merged. 4152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller upper[length].count=0; 4162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller while(--length>middleLength) { 4172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lower[length]=upper[length]=null; 4182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller break; 4202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 4252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* print ranges 4262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int length=4; length>=2; --length) { 4272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(lower[length].count>0) { 4282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count); 4292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(middle.count>0) { 4322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller printf("middle .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count); 4332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int length=2; length<=4; ++length) { 4352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(upper[length].count>0) { 4362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count); 4372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } */ 4392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 4402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* copy the ranges, shortest first, into the result array */ 4412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller rangeCount=0; 4422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(middle.count>0) { 4432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[0] = middle; 4442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller rangeCount=1; 4452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int length=middleLength+1; length<=4; ++length) { 4472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* copy upper first so that later the middle range is more likely the first one to use */ 4482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(upper[length] != null && upper[length].count>0) { 4492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[rangeCount++]=upper[length]; 4502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(lower[length] != null && lower[length].count>0) { 4522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[rangeCount++]=lower[length]; 4532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return rangeCount>0; 4562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 4582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private boolean allocWeightsInShortRanges(int n, int minLength) { 4592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // See if the first few minLength and minLength+1 ranges have enough weights. 4602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int i = 0; i < rangeCount && ranges[i].length <= (minLength + 1); ++i) { 4612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(n <= ranges[i].count) { 4622ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Use the first few minLength and minLength+1 ranges. 4632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(ranges[i].length > minLength) { 4642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Reduce the number of weights from the last minLength+1 range 4652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // which might sort before some minLength ranges, 4662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // so that we use all weights in the minLength ranges. 4672ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[i].count = n; 4682ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4692ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller rangeCount = i + 1; 4702ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("take first %ld ranges\n", rangeCount); 4712ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 4722ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(rangeCount>1) { 4732ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller /* sort the ranges by weight values */ 4742ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller Arrays.sort(ranges, 0, rangeCount); 4752ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4762ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return true; 4772ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4782ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller n -= ranges[i].count; // still >0 4792ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4802ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return false; 4812ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4822ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 4832ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private boolean allocWeightsInMinLengthRanges(int n, int minLength) { 4842ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // See if the minLength ranges have enough weights 4852ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // when we split one and lengthen the following ones. 4862ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int count = 0; 4872ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int minLengthRangeCount; 4882ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(minLengthRangeCount = 0; 4892ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller minLengthRangeCount < rangeCount && 4902ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[minLengthRangeCount].length == minLength; 4912ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ++minLengthRangeCount) { 4922ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller count += ranges[minLengthRangeCount].count; 4932ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 4942ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 4952ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int nextCountBytes = countBytes(minLength + 1); 4962ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(n > count * nextCountBytes) { return false; } 4972ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 4982ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Use the minLength ranges. Merge them, and then split again as necessary. 4992ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller long start = ranges[0].start; 5002ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller long end = ranges[0].end; 5012ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for(int i = 1; i < minLengthRangeCount; ++i) { 5022ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(ranges[i].start < start) { start = ranges[i].start; } 5032ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(ranges[i].end > end) { end = ranges[i].end; } 5042ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 5052ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 5062ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Calculate how to split the range between minLength (count1) and minLength+1 (count2). 5072ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Goal: 5082ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // count1 + count2 * nextCountBytes = n 5092ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // count1 + count2 = count 5102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // These turn into 5112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // (count - count2) + count2 * nextCountBytes = n 5122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // and then into the following count1 & count2 computations. 5132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int count2 = (n - count) / (nextCountBytes - 1); // number of weights to be lengthened 5142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int count1 = count - count2; // number of minLength weights 5152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(count2 == 0 || (count1 + count2 * nextCountBytes) < n) { 5162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // round up 5172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ++count2; 5182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller --count1; 5192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller assert((count1 + count2 * nextCountBytes) >= n); 5202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 5212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 5222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[0].start = start; 5232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 5242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(count1 == 0) { 5252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Make one long range. 5262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[0].end = end; 5272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[0].count = count; 5282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lengthenRange(ranges[0]); 5292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller rangeCount = 1; 5302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 5312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Split the range, lengthen the second part. 5322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // printf("split the range number %ld (out of %ld minLength ranges) by %ld:%ld\n", 5332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // splitRange, rangeCount, count1, count2); 5342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 5352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Next start = start + count1. First end = 1 before that. 5362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[0].end = incWeightByOffset(start, minLength, count1 - 1); 5372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[0].count = count1; 5382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 5392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if(ranges[1] == null) { 5402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[1] = new WeightRange(); 5412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 5422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[1].start = incWeight(ranges[0].end, minLength); 5432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[1].end = end; 5442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[1].length = minLength; // +1 when lengthened 5452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ranges[1].count = count2; // *countBytes when lengthened 5462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller lengthenRange(ranges[1]); 5472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller rangeCount = 2; 5482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 5492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return true; 5502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 5512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 5522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private int middleLength; 5532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private int[] minBytes = new int[5]; // for byte 1, 2, 3, 4 5542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private int[] maxBytes = new int[5]; 5552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private WeightRange[] ranges = new WeightRange[7]; 5562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private int rangeIndex; 5572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller private int rangeCount; 5582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller} 559