1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18package java.math;
19
20/**
21 * Static library that provides all the <b>bit level</b> operations for
22 * {@link BigInteger}. The operations are:
23 * <ul type="circle">
24 * <li>Left Shifting</li>
25 * <li>Right Shifting</li>
26 * <li>Bit clearing</li>
27 * <li>Bit setting</li>
28 * <li>Bit counting</li>
29 * <li>Bit testing</li>
30 * <li>Getting of the lowest bit set</li>
31 * </ul>
32 * All operations are provided in immutable way, and some in both mutable and
33 * immutable.
34 */
35class BitLevel {
36
37    /** Just to denote that this class can't be instantiated. */
38    private BitLevel() {}
39
40    /** @see BigInteger#bitLength() */
41    static int bitLength(BigInteger val) {
42        val.prepareJavaRepresentation();
43        if (val.sign == 0) {
44            return 0;
45        }
46        int bLength = (val.numberLength << 5);
47        int highDigit = val.digits[val.numberLength - 1];
48
49        if (val.sign < 0) {
50            int i = val.getFirstNonzeroDigit();
51            // We reduce the problem to the positive case.
52            if (i == val.numberLength - 1) {
53                highDigit--;
54            }
55        }
56        // Subtracting all sign bits
57        bLength -= Integer.numberOfLeadingZeros(highDigit);
58        return bLength;
59    }
60
61    /** @see BigInteger#bitCount() */
62    static int bitCount(BigInteger val) {
63        val.prepareJavaRepresentation();
64        int bCount = 0;
65
66        if (val.sign == 0) {
67            return 0;
68        }
69
70        int i = val.getFirstNonzeroDigit();
71        if (val.sign > 0) {
72            for ( ; i < val.numberLength; i++) {
73                bCount += Integer.bitCount(val.digits[i]);
74            }
75        } else {// (sign < 0)
76            // this digit absorbs the carry
77            bCount += Integer.bitCount(-val.digits[i]);
78            for (i++; i < val.numberLength; i++) {
79                bCount += Integer.bitCount(~val.digits[i]);
80            }
81            // We take the complement sum:
82            bCount = (val.numberLength << 5) - bCount;
83        }
84        return bCount;
85    }
86
87    /**
88     * Performs a fast bit testing for positive numbers. The bit to to be tested
89     * must be in the range {@code [0, val.bitLength()-1]}
90     */
91    static boolean testBit(BigInteger val, int n) {
92        val.prepareJavaRepresentation();
93        // PRE: 0 <= n < val.bitLength()
94        return ((val.digits[n >> 5] & (1 << (n & 31))) != 0);
95    }
96
97    /**
98     * Check if there are 1s in the lowest bits of this BigInteger
99     *
100     * @param numberOfBits the number of the lowest bits to check
101     * @return false if all bits are 0s, true otherwise
102     */
103    static boolean nonZeroDroppedBits(int numberOfBits, int[] digits) {
104        int intCount = numberOfBits >> 5;
105        int bitCount = numberOfBits & 31;
106        int i;
107
108        for (i = 0; (i < intCount) && (digits[i] == 0); i++) {
109            ;
110        }
111        return ((i != intCount) || (digits[i] << (32 - bitCount) != 0));
112    }
113
114    static void shiftLeftOneBit(int[] result, int[] source, int srcLen) {
115        int carry = 0;
116        for (int i = 0; i < srcLen; i++) {
117            int val = source[i];
118            result[i] = (val << 1) | carry;
119            carry = val >>> 31;
120        }
121        if(carry != 0) {
122            result[srcLen] = carry;
123        }
124    }
125
126    static BigInteger shiftLeftOneBit(BigInteger source) {
127        source.prepareJavaRepresentation();
128        int srcLen = source.numberLength;
129        int resLen = srcLen + 1;
130        int[] resDigits = new int[resLen];
131        shiftLeftOneBit(resDigits, source.digits, srcLen);
132        return new BigInteger(source.sign, resLen, resDigits);
133    }
134
135    /** @see BigInteger#shiftRight(int) */
136    static BigInteger shiftRight(BigInteger source, int count) {
137        source.prepareJavaRepresentation();
138        int intCount = count >> 5; // count of integers
139        count &= 31; // count of remaining bits
140        if (intCount >= source.numberLength) {
141            return ((source.sign < 0) ? BigInteger.MINUS_ONE : BigInteger.ZERO);
142        }
143        int i;
144        int resLength = source.numberLength - intCount;
145        int[] resDigits = new int[resLength + 1];
146
147        shiftRight(resDigits, resLength, source.digits, intCount, count);
148        if (source.sign < 0) {
149            // Checking if the dropped bits are zeros (the remainder equals to
150            // 0)
151            for (i = 0; (i < intCount) && (source.digits[i] == 0); i++) {
152                ;
153            }
154            // If the remainder is not zero, add 1 to the result
155            if ((i < intCount)
156                    || ((count > 0) && ((source.digits[i] << (32 - count)) != 0))) {
157                for (i = 0; (i < resLength) && (resDigits[i] == -1); i++) {
158                    resDigits[i] = 0;
159                }
160                if (i == resLength) {
161                    resLength++;
162                }
163                resDigits[i]++;
164            }
165        }
166        return new BigInteger(source.sign, resLength, resDigits);
167    }
168
169    /**
170     * Shifts right an array of integers. Total shift distance in bits is
171     * intCount * 32 + count.
172     *
173     * @param result
174     *            the destination array
175     * @param resultLen
176     *            the destination array's length
177     * @param source
178     *            the source array
179     * @param intCount
180     *            the number of elements to be shifted
181     * @param count
182     *            the number of bits to be shifted
183     * @return dropped bit's are all zero (i.e. remaider is zero)
184     */
185    static boolean shiftRight(int[] result, int resultLen, int[] source, int intCount, int count) {
186        int i;
187        boolean allZero = true;
188        for (i = 0; i < intCount; i++)
189            allZero &= source[i] == 0;
190        if (count == 0) {
191            System.arraycopy(source, intCount, result, 0, resultLen);
192            i = resultLen;
193        } else {
194            int leftShiftCount = 32 - count;
195
196            allZero &= ( source[i] << leftShiftCount ) == 0;
197            for (i = 0; i < resultLen - 1; i++) {
198                result[i] = ( source[i + intCount] >>> count )
199                | ( source[i + intCount + 1] << leftShiftCount );
200            }
201            result[i] = ( source[i + intCount] >>> count );
202            i++;
203        }
204
205        return allZero;
206    }
207
208
209    /**
210     * Performs a flipBit on the BigInteger, returning a BigInteger with the the
211     * specified bit flipped.
212     */
213    static BigInteger flipBit(BigInteger val, int n){
214        val.prepareJavaRepresentation();
215        int resSign = (val.sign == 0) ? 1 : val.sign;
216        int intCount = n >> 5;
217        int bitN = n & 31;
218        int resLength = Math.max(intCount + 1, val.numberLength) + 1;
219        int[] resDigits = new int[resLength];
220        int i;
221
222        int bitNumber = 1 << bitN;
223        System.arraycopy(val.digits, 0, resDigits, 0, val.numberLength);
224
225        if (val.sign < 0) {
226            if (intCount >= val.numberLength) {
227                resDigits[intCount] = bitNumber;
228            } else {
229                //val.sign<0 y intCount < val.numberLength
230                int firstNonZeroDigit = val.getFirstNonzeroDigit();
231                if (intCount > firstNonZeroDigit) {
232                    resDigits[intCount] ^= bitNumber;
233                } else if (intCount < firstNonZeroDigit) {
234                    resDigits[intCount] = -bitNumber;
235                    for (i=intCount + 1; i < firstNonZeroDigit; i++) {
236                        resDigits[i]=-1;
237                    }
238                    resDigits[i] = resDigits[i]--;
239                } else {
240                    i = intCount;
241                    resDigits[i] = -((-resDigits[intCount]) ^ bitNumber);
242                    if (resDigits[i] == 0) {
243                        for (i++; resDigits[i] == -1 ; i++) {
244                            resDigits[i] = 0;
245                        }
246                        resDigits[i]++;
247                    }
248                }
249            }
250        } else {//case where val is positive
251            resDigits[intCount] ^= bitNumber;
252        }
253        return new BigInteger(resSign, resLength, resDigits);
254    }
255}
256