001/**
002 * Java Web Archive Toolkit - Software to read and validate ARC, WARC
003 * and GZip files. (http://jwat.org/)
004 * Copyright 2011-2012 Netarkivet.dk (http://netarkivet.dk/)
005 *
006 * Licensed under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.jwat.common;
019
020import java.util.ArrayList;
021import java.util.List;
022
023/**
024 * Helper class to work with numbers and their string representation.
025 *
026 * @author nicl
027 */
028public class Numbers {
029
030    /** Integer array for integer string length binary search. */
031    protected static int[] islArr;
032
033    /** Long array for long string length binary search. */
034    protected static long[] lslArr;
035
036    protected static int[] imArr;
037
038    protected static long[] lmArr;
039
040    /*
041     * Initialize the internal comparison arrays for binary search.
042     */
043    static {
044        boolean b;
045        // Pre-calc for integer value string length.
046        List<Integer> islList = new ArrayList<Integer>();
047        islList.add(0);
048        islList.add(0);
049        int i = 1;
050        int li;
051        int lm = Integer.MAX_VALUE;
052        b = true;
053        while (b) {
054            if (i < lm) {
055                li = i;
056                i = (i << 3) + (i << 1);
057                if (i / 10 == li) {
058                    islList.add(i);
059                }
060                else {
061                    b = false;
062                }
063            }
064            else {
065                b = false;
066            }
067        }
068        islArr = new int[islList.size()];
069        for (i=0; i<islList.size(); ++i) {
070            islArr[i] = islList.get(i);
071            //System.out.println(islList.get(i));
072        }
073        // Pre-calc for long value string length.
074        List<Long> lslList = new ArrayList<Long>();
075        lslList.add(0L);
076        lslList.add(0L);
077        long l = 1;
078        long ll;
079        long ml = Long.MAX_VALUE;
080        b = true;
081        while (b) {
082            if (l < ml) {
083                ll = l;
084                l = (l << 3) + (l << 1);
085                if (l / 10 == ll) {
086                    lslList.add(l);
087                }
088                else {
089                    b = false;
090                }
091            }
092            else {
093                b = false;
094            }
095        }
096        lslArr = new long[lslList.size()];
097        for (i=0; i<lslList.size(); ++i) {
098            lslArr[i] = lslList.get(i);
099            //System.out.println(lslList.get(i));
100        }
101        // Pre-calc for modulo methods.
102        imArr = new int[10];
103        int idx = 0;
104        imArr[idx++] = 0;
105        i = 1;
106        while (idx < imArr.length) {
107            i = (i << 3) + (i << 1);
108            imArr[idx++] = i;
109        }
110        lmArr = new long[19];
111        idx = 0;
112        lmArr[idx++] = 0;
113        l = 1L;
114        while (idx < lmArr.length) {
115            l = (l << 3) + (l << 1);
116            lmArr[idx++] = l;
117        }
118    }
119
120    /**
121     * Find the string length of the integer without leading zeroes.
122     * @param i integer value
123     * @return string length of the integer
124     */
125    public static int intStrLen(int i) {
126        int min = 1;
127        int max = 10;
128        int idx = 0;
129        int c;
130        boolean bLoop = true;
131        while (bLoop) {
132            idx = min + ((max - min + 1) >> 1);
133            //System.out.println(l + " " + min + " " + max + " " + islArr[min] + " " + i + " " + islArr[max]);
134            c = islArr[idx];
135            if (i < c) {
136                max = --idx;
137            }
138            else {
139                min = idx;
140            }
141            bLoop = (max - min) != 0;
142            //System.out.println(l + " " + min + " " + max + " " + islArr[min] + " " + i + " " + islArr[max]);
143        }
144        return idx;
145    }
146
147    /**
148     * Find the string length of the long without leading zeroes.
149     * @param l long value
150     * @return string length of the long
151     */
152    public static int longStrLen(long l) {
153        int min = 1;
154        int max = 19;
155        int idx = 0;
156        long c;
157        boolean bLoop = true;
158        while (bLoop) {
159            idx = min + ((max - min + 1) >> 1);
160            //System.out.println(l + " " + min + " " + max + " " + lslArr[min] + " " + i + " " + lslArr[max]);
161            c = lslArr[idx];
162            if (l < c) {
163                max = --idx;
164            }
165            else {
166                min = idx;
167            }
168            bLoop = (max - min) != 0;
169            //System.out.println(l + " " + min + " " + max + " " + lslArr[min] + " " + i + " " + lslArr[max]);
170        }
171        return idx;
172    }
173
174    /**
175     * Returns the number of trailing zeroes in an integer, or zero if the number is 0.
176     * @param i number to count trailing zeroes in
177     * @return the number of trailing zeroes in an integer, or zero if the number is 0
178     */
179    public static int intTrailingZeros(int i) {
180        int cnt = 0;
181        if (i != 0) {
182            while (i % 10 == 0) {
183                i = i / 10;
184                ++cnt;
185            }
186        }
187        return cnt;
188    }
189
190    public static int intModulo(int i, int digits) {
191        if (digits > 0) {
192            if (digits < imArr.length) {
193                i = i - (i % imArr[digits]);
194            }
195            else {
196                throw new IllegalArgumentException("Out of bounds!");
197            }
198        }
199        return i;
200    }
201
202    public static long longModulo(long l, int digits) {
203        if (digits > 0) {
204            if (digits < lmArr.length) {
205                l = l - (l % lmArr[digits]);
206            }
207            else {
208                throw new IllegalArgumentException("Out of bounds!");
209            }
210        }
211        return l;
212    }
213
214    /**
215     * Divu10 from Hackers Delight.
216     * @param n integer to divide by 10
217     * @return integer divided by 10
218     */
219    public static int divu10hd(int n) {
220        int q, r;
221        q = (n >> 1) + (n >> 2);        // q=n/2+n/4 = 3n/4
222        q = q + (q >> 4);               // q=3n/4+(3n/4)/16 = 3n/4+3n/64 = 51n/64
223        q = q + (q >> 8);               // q=51n/64+(51n/64)/256 = 51n/64 + 51n/16384 = 13107n/16384
224        q = q + (q >> 16);              // q= 13107n/16384+(13107n/16384)/65536=13107n/16348+13107n/1073741824=858993458n/1073741824
225        // note: q is now roughly 0.8n
226        q = q >> 3;                     // q=n/8 = (about 0.1n or n/10)
227        r = n - (((q << 2) + q) << 1);  // rounding: r= n-2*(n/10*4+n/10)=n-2*5n/10=n-10n/10
228        return q + ((r > 9) ? 1 : 0);   // adjust answer by error term
229    }
230
231    /**
232     * Divu10 from GNU GCC.
233     * @param n integer to divide by 10
234     * @return integer divided by 10
235     */
236    public static int divu10gcc(int n) {
237        return (int)((((long)n) * 0xcccccccdL) >>> 35);
238    }
239
240    /* This does not seem to work in Java, most likely dues to missing unsigned multiplication.
241    public static long divu10(long l) {
242        return (l * 0xcccccccccccccccdL) >>> 3;
243    }
244    */
245
246}