001: // Copyright (c) 1997 Per M.A. Bothner.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.math;
005:
006: /** Implements logical (bit-wise) operations on infinite-precision integers.
007: * There are no BitOps object - all the functions here are static.
008: * The semantics used are the same as for Common Lisp.
009: * @author Per Bothner
010: */
011:
012: public class BitOps {
013: private BitOps() {
014: }
015:
016: /** Return the value of a specified bit in an IntNum. */
017: public static boolean bitValue(IntNum x, int bitno) {
018: int i = x.ival;
019: if (x.words == null) {
020: return bitno >= 32 ? i < 0 : ((i >> bitno) & 1) != 0;
021: } else {
022: int wordno = bitno >> 5;
023: return wordno >= i ? x.words[i - 1] < 0
024: : (((x.words[wordno]) >> bitno) & 1) != 0;
025: }
026: }
027:
028: /** Return true iff an IntNum and an int have any true bits in common. */
029: public static boolean test(IntNum x, int y) {
030: if (x.words == null)
031: return (x.ival & y) != 0;
032: return (y < 0) || (x.words[0] & y) != 0;
033: }
034:
035: /** Return true iff two IntNums have any true bits in common. */
036: public static boolean test(IntNum x, IntNum y) {
037: if (y.words == null)
038: return test(x, y.ival);
039: else if (x.words == null)
040: return test(y, x.ival);
041: if (x.ival < y.ival) {
042: IntNum temp = x;
043: x = y;
044: y = temp;
045: }
046: for (int i = 0; i < y.ival; i++) {
047: if ((x.words[i] & y.words[i]) != 0)
048: return true;
049: }
050: return y.isNegative();
051: }
052:
053: /** Return the logical (bit-wise) "and" of an IntNum and an int. */
054: public static IntNum and(IntNum x, int y) {
055: if (x.words == null)
056: return IntNum.make(x.ival & y);
057: if (y >= 0)
058: return IntNum.make(x.words[0] & y);
059: int len = x.ival;
060: int[] words = new int[len];
061: words[0] = x.words[0] & y;
062: while (--len > 0)
063: words[len] = x.words[len];
064: return IntNum.make(words, x.ival);
065: }
066:
067: /** Return the logical (bit-wise) "and" of two IntNums. */
068: public static IntNum and(IntNum x, IntNum y) {
069: if (y.words == null)
070: return and(x, y.ival);
071: else if (x.words == null)
072: return and(y, x.ival);
073: if (x.ival < y.ival) {
074: IntNum temp = x;
075: x = y;
076: y = temp;
077: }
078: int i;
079: int len = y.isNegative() ? x.ival : y.ival;
080: int[] words = new int[len];
081: for (i = 0; i < y.ival; i++)
082: words[i] = x.words[i] & y.words[i];
083: for (; i < len; i++)
084: words[i] = x.words[i];
085: return IntNum.make(words, len);
086: }
087:
088: /** Return the logical (bit-wise) "(inclusive) or" of two IntNums. */
089: public static IntNum ior(IntNum x, IntNum y) {
090: return bitOp(7, x, y);
091: }
092:
093: /** Return the logical (bit-wise) "exclusive or" of two IntNums. */
094: public static IntNum xor(IntNum x, IntNum y) {
095: return bitOp(6, x, y);
096: }
097:
098: /** Return the logical (bit-wise) negation of an IntNum. */
099: public static IntNum not(IntNum x) {
100: return bitOp(12, x, IntNum.zero());
101: }
102:
103: /** Return the boolean opcode (for bitOp) for swapped operands.
104: * I.e. bitOp (swappedOp(op), x, y) == bitOp (op, y, x).
105: */
106: public static int swappedOp(int op) {
107: return "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
108: .charAt(op);
109: }
110:
111: /** Do one the the 16 possible bit-wise operations of two IntNums. */
112: public static IntNum bitOp(int op, IntNum x, IntNum y) {
113: switch (op) {
114: case 0:
115: return IntNum.zero();
116: case 1:
117: return and(x, y);
118: case 3:
119: return x;
120: case 5:
121: return y;
122: case 15:
123: return IntNum.minusOne();
124: }
125: IntNum result = new IntNum();
126: setBitOp(result, op, x, y);
127: return result.canonicalize();
128: }
129:
130: /** Do one the the 16 possible bit-wise operations of two IntNums. */
131: public static void setBitOp(IntNum result, int op, IntNum x,
132: IntNum y) {
133: if (y.words == null)
134: ;
135: else if (x.words == null || x.ival < y.ival) {
136: IntNum temp = x;
137: x = y;
138: y = temp;
139: op = swappedOp(op);
140: }
141: int xi;
142: int yi;
143: int xlen, ylen;
144: if (y.words == null) {
145: yi = y.ival;
146: ylen = 1;
147: } else {
148: yi = y.words[0];
149: ylen = y.ival;
150: }
151: if (x.words == null) {
152: xi = x.ival;
153: xlen = 1;
154: } else {
155: xi = x.words[0];
156: xlen = x.ival;
157: }
158: if (xlen > 1)
159: result.realloc(xlen);
160: int[] w = result.words;
161: int i = 0;
162: // Code for how to handle the remainder of x.
163: // 0: Truncate to length of y.
164: // 1: Copy rest of x.
165: // 2: Invert rest of x.
166: int finish = 0;
167: int ni;
168: switch (op) {
169: case 0: // clr
170: ni = 0;
171: break;
172: case 1: // and
173: for (;;) {
174: ni = xi & yi;
175: if (i + 1 >= ylen)
176: break;
177: w[i++] = ni;
178: xi = x.words[i];
179: yi = y.words[i];
180: }
181: if (yi < 0)
182: finish = 1;
183: break;
184: case 2: // andc2
185: for (;;) {
186: ni = xi & ~yi;
187: if (i + 1 >= ylen)
188: break;
189: w[i++] = ni;
190: xi = x.words[i];
191: yi = y.words[i];
192: }
193: if (yi >= 0)
194: finish = 1;
195: break;
196: case 3: // copy x
197: ni = xi;
198: finish = 1; // Copy rest
199: break;
200: case 4: // andc1
201: for (;;) {
202: ni = ~xi & yi;
203: if (i + 1 >= ylen)
204: break;
205: w[i++] = ni;
206: xi = x.words[i];
207: yi = y.words[i];
208: }
209: if (yi < 0)
210: finish = 2;
211: break;
212: case 5: // copy y
213: for (;;) {
214: ni = yi;
215: if (i + 1 >= ylen)
216: break;
217: w[i++] = ni;
218: xi = x.words[i];
219: yi = y.words[i];
220: }
221: break;
222: case 6: // xor
223: for (;;) {
224: ni = xi ^ yi;
225: if (i + 1 >= ylen)
226: break;
227: w[i++] = ni;
228: xi = x.words[i];
229: yi = y.words[i];
230: }
231: finish = yi < 0 ? 2 : 1;
232: break;
233: case 7: // ior
234: for (;;) {
235: ni = xi | yi;
236: if (i + 1 >= ylen)
237: break;
238: w[i++] = ni;
239: xi = x.words[i];
240: yi = y.words[i];
241: }
242: if (yi >= 0)
243: finish = 1;
244: break;
245: case 8: // nor
246: for (;;) {
247: ni = ~(xi | yi);
248: if (i + 1 >= ylen)
249: break;
250: w[i++] = ni;
251: xi = x.words[i];
252: yi = y.words[i];
253: }
254: if (yi >= 0)
255: finish = 2;
256: break;
257: case 9: // eqv [exclusive nor]
258: for (;;) {
259: ni = ~(xi ^ yi);
260: if (i + 1 >= ylen)
261: break;
262: w[i++] = ni;
263: xi = x.words[i];
264: yi = y.words[i];
265: }
266: finish = yi >= 0 ? 2 : 1;
267: break;
268: case 10: // c2
269: for (;;) {
270: ni = ~yi;
271: if (i + 1 >= ylen)
272: break;
273: w[i++] = ni;
274: xi = x.words[i];
275: yi = y.words[i];
276: }
277: break;
278: case 11: // orc2
279: for (;;) {
280: ni = xi | ~yi;
281: if (i + 1 >= ylen)
282: break;
283: w[i++] = ni;
284: xi = x.words[i];
285: yi = y.words[i];
286: }
287: if (yi < 0)
288: finish = 1;
289: break;
290: case 12: // c1
291: ni = ~xi;
292: finish = 2;
293: break;
294: case 13: // orc1
295: for (;;) {
296: ni = ~xi | yi;
297: if (i + 1 >= ylen)
298: break;
299: w[i++] = ni;
300: xi = x.words[i];
301: yi = y.words[i];
302: }
303: if (yi >= 0)
304: finish = 2;
305: break;
306: case 14: // nand
307: for (;;) {
308: ni = ~(xi & yi);
309: if (i + 1 >= ylen)
310: break;
311: w[i++] = ni;
312: xi = x.words[i];
313: yi = y.words[i];
314: }
315: if (yi < 0)
316: finish = 2;
317: break;
318: default:
319: case 15: // set
320: ni = -1;
321: break;
322: }
323: // Here i==ylen-1; w[0]..w[i-1] have the correct result;
324: // and ni contains the correct result for w[i+1].
325: if (i + 1 == xlen)
326: finish = 0;
327: switch (finish) {
328: case 0:
329: if (i == 0 && w == null) {
330: result.ival = ni;
331: return;
332: }
333: w[i++] = ni;
334: break;
335: case 1:
336: w[i] = ni;
337: while (++i < xlen)
338: w[i] = x.words[i];
339: break;
340: case 2:
341: w[i] = ni;
342: while (++i < xlen)
343: w[i] = ~x.words[i];
344: break;
345: }
346: result.ival = i;
347: }
348:
349: /** Extract a bit-field as an unsigned integer. */
350: public static IntNum extract(IntNum x, int startBit, int endBit) {
351: //System.err.print("extract(["); if (x.words!=null) MPN.dprint(x.words);
352: //System.err.println (","+x.ival+"], start:"+startBit+", end:"+endBit);
353: if (endBit < 32) {
354: int word0 = x.words == null ? x.ival : x.words[0];
355: return IntNum.make((word0 & ~((-1) << endBit)) >> startBit);
356: }
357: int x_len;
358: if (x.words == null) {
359: if (x.ival >= 0)
360: return IntNum.make(startBit >= 31 ? 0
361: : (x.ival >> startBit));
362: x_len = 1;
363: } else
364: x_len = x.ival;
365: boolean neg = x.isNegative();
366: if (endBit > 32 * x_len) {
367: endBit = 32 * x_len;
368: if (!neg && startBit == 0)
369: return x;
370: } else
371: x_len = (endBit + 31) >> 5;
372: int length = endBit - startBit;
373: if (length < 64) {
374: long l;
375: if (x.words == null)
376: l = x.ival >> (startBit >= 32 ? 31 : startBit);
377: else
378: l = MPN.rshift_long(x.words, x_len, startBit);
379: return IntNum.make(l & ~((-1L) << length));
380: }
381: int startWord = startBit >> 5;
382: // Allocate a work buffer, which has to be large enough for the result
383: // AND large enough for all words we use from x (including possible
384: // partial words at both ends).
385: int buf_len = (endBit >> 5) + 1 - startWord;
386: int[] buf = new int[buf_len];
387: if (x.words == null) // x < 0.
388: buf[0] = startBit >= 32 ? -1 : (x.ival >> startBit);
389: else {
390: x_len -= startWord;
391: startBit &= 31;
392: MPN.rshift0(buf, x.words, startWord, x_len, startBit);
393: }
394: x_len = length >> 5;
395: buf[x_len] &= ~((-1) << length);
396: return IntNum.make(buf, x_len + 1);
397: }
398:
399: // bit4count[I] is number of '1' bits in I.
400: static final byte[] bit4_count = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2,
401: 3, 2, 3, 3, 4 };
402:
403: public static int bitCount(int i) {
404: int count = 0;
405: while (i != 0) {
406: count += bit4_count[i & 15];
407: i >>>= 4;
408: }
409: return count;
410: }
411:
412: public static int bitCount(int[] x, int len) {
413: int count = 0;
414: while (--len >= 0)
415: count += bitCount(x[len]);
416: return count;
417: }
418:
419: /** Count one bits in an IntNum.
420: * If argument is negative, count zero bits instead. */
421: public static int bitCount(IntNum x) {
422: int i, x_len;
423: int[] x_words = x.words;
424: if (x_words == null) {
425: x_len = 1;
426: i = bitCount(x.ival);
427: } else {
428: x_len = x.ival;
429: i = bitCount(x_words, x_len);
430: }
431: return x.isNegative() ? x_len * 32 - i : i;
432: }
433: }
|