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