001 /*
002 * Java Genetic Algorithm Library (jenetics-1.6.0).
003 * Copyright (c) 2007-2014 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019 */
020 package org.jenetics.util;
021
022 import static java.lang.Math.min;
023
024 import org.jscience.mathematics.number.LargeInteger;
025
026
027 /**
028 * Some bit utils. All operation assume <a href="http://en.wikipedia.org/wiki/Endianness">
029 * <b>little-endian</b></a> byte order.
030 *
031 * <pre>
032 * Byte: 3 2 1 0
033 * | | | |
034 * Array: |11110011|10011101|01000000|00101010|
035 * | | | |
036 * Bit: 23 15 7 0
037 * </pre>
038 *
039 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
040 * @since 1.0
041 * @version 1.5 — <em>$Date: 2014-03-07 $</em>
042 */
043 public final class bit extends StaticObject {
044 private bit() {}
045
046 /**
047 * Lookup table for counting the number of set bits in a {@code byte} value.
048 */
049 private static final byte[] BIT_SET_TABLE = {
050 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
051 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
052 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
053 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
054 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
055 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
056 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
057 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
058 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
059 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
060 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
061 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
062 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
063 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
064 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
065 (byte)5, (byte)6, (byte)6, (byte)7, (byte)6, (byte)7, (byte)7, (byte)8,
066 (byte)0, (byte)1, (byte)1, (byte)2, (byte)1, (byte)2, (byte)2, (byte)3,
067 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
068 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
069 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
070 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
071 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
072 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
073 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
074 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
075 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
076 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
077 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
078 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
079 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
080 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
081 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7
082 };
083 private static final int BIT_SET_TABLE_INDEX_OFFSET = 128;
084
085 /**
086 * Return the (boolean) value of the byte array at the given bit index.
087 *
088 * @param data the byte array.
089 * @param index the bit index.
090 * @return the value at the given bit index.
091 * @throws IndexOutOfBoundsException if the index is
092 * {@code index >= max || index < 0}.
093 * @throws NullPointerException if the {@code data} array is {@code null}.
094 */
095 public static boolean get(final byte[] data, final int index) {
096 return (data[index >>> 3] & (1 << (index & 7))) != 0;
097 }
098
099 /**
100 * Set the bit in the given byte array at the bit position (not the index
101 * within the byte array) to the specified value.
102 *
103 * @param data the byte array.
104 * @param index the bit index within the byte array.
105 * @param value the value to set.
106 * @return the given data array.
107 * @throws IndexOutOfBoundsException if the index is
108 * {@code index >= max || index < 0}.
109 * @throws NullPointerException if the {@code data} array is {@code null}.
110 */
111 public static byte[] set(
112 final byte[] data,
113 final int index,
114 final boolean value
115 ) {
116 return value ? set(data, index) : unset(data, index);
117 }
118
119 /**
120 * Set the bit in the given byte array at the bit position (not the index
121 * within the byte array) to {@code true}.
122 *
123 * @param data the byte array.
124 * @param index the bit index within the byte array.
125 * @return the given data array.
126 * @throws IndexOutOfBoundsException if the index is
127 * {@code index >= max || index < 0}.
128 * @throws NullPointerException if the {@code data} array is {@code null}.
129 */
130 public static byte[] set(final byte[] data, final int index) {
131 data[index >>> 3] |= 1 << (index & 7);
132 return data;
133 }
134
135 /**
136 * Set the bit in the given byte array at the bit position (not the index
137 * within the byte array) to {@code false}.
138 *
139 * @param data the byte array.
140 * @param index the bit index within the byte array.
141 * @return the given data array.
142 * @throws IndexOutOfBoundsException if the index is
143 * {@code index >= max || index < 0}.
144 * @throws NullPointerException if the {@code data} array is {@code null}.
145 */
146 public static byte[] unset(final byte[] data, final int index) {
147 data[index >>> 3] &= ~(1 << (index & 7));
148 return data;
149 }
150
151 /**
152 * Swap a given range with a range of the same size with another array.
153 *
154 * <pre>
155 * start end
156 * | |
157 * data: +---+---+---+---+---+---+---+---+---+---+---+---+
158 * +---------------+
159 * +---------------+
160 * otherData: +---+---+---+---+---+---+---+---+---+---+---+---+
161 * |
162 * otherStart
163 * </pre>
164 *
165 * @param data the first byte array which are used for swapping.
166 * @param start the start bit index of the {@code data} byte array,
167 * inclusively.
168 * @param end the end bit index of the {@code data} byte array, exclusively.
169 * @param otherData the other byte array to swap the elements with.
170 * @param otherStart the start index of the {@code otherData} byte array.
171 * @throws IndexOutOfBoundsException if {@code start > end} or
172 * if {@code start < 0 || end >= data.length*8 || otherStart < 0 ||
173 * otherStart + (end - start) >= otherData.length*8}
174 */
175 public static void swap(
176 final byte[] data, final int start, final int end,
177 final byte[] otherData, final int otherStart
178 ) {
179 for (int i = (end - start); --i >= 0;) {
180 final boolean temp = get(data, i + start);
181 set(data, i + start, get(otherData, otherStart + i));
182 set(otherData, otherStart + i, temp);
183 }
184 }
185
186 /**
187 * Returns the number of one-bits in the given {@code byte} array.
188 *
189 * @param data the {@code byte} array for which the one bits should be
190 * counted.
191 * @return the number of one bits in the given {@code byte} array.
192 */
193 public static int count(final byte[] data) {
194 int count = 0;
195 for (int i = data.length; --i >= 0;) {
196 count += count(data[i]);
197 }
198 return count;
199 }
200
201 /**
202 * Returns the number of one-bits in the given {@code byte} {@code value}.
203 *
204 * @param value the value for which the one bits should be counted.
205 * @return the number of one bits in the given value
206 */
207 public static int count(final byte value) {
208 return BIT_SET_TABLE[value + BIT_SET_TABLE_INDEX_OFFSET];
209 }
210
211 /**
212 * Shifting all bits in the given {@code data} array the given
213 * {@code shift} to the right. The bits on the left side are filled with
214 * zeros.
215 *
216 * @param data the data bits to shift.
217 * @param shift the number of bits to shift.
218 * @return the given {@code data} array.
219 * @throws NullPointerException if the {@code data} array is {@code null}.
220 */
221 public static byte[] shiftRight(final byte[] data, final int shift) {
222 final int bytes = min(shift >>> 3, data.length);
223 final int bits = shift & 7;
224
225 if (bytes > 0) {
226 for (int i = 0, n = data.length - bytes; i < n; ++i) {
227 data[i] = data[i + bytes];
228 }
229 for (int i = data.length, n = data.length - bytes; --i >= n;) {
230 data[i] = (byte)0;
231 }
232 }
233 if (bits > 0 && bytes < data.length) {
234 int carry = 0;
235 int nextCarry = 0;
236
237 for (int i = data.length; --i >= 0;) {
238 int d = data[i] & 0xFF;
239 nextCarry = (d << (8 - bits));
240
241 d >>>= bits;
242 d |= carry;
243 data[i] = (byte)(d & 0xFF);
244
245 carry = nextCarry;
246 }
247 }
248
249 return data;
250 }
251
252 /**
253 * Shifting all bits in the given {@code data} array the given
254 * {@code shift} to the left. The bits on the right side are filled with
255 * zeros.
256 *
257 * @param data the data bits to shift.
258 * @param shift the number of bits to shift.
259 * @return the given {@code data} array.
260 * @throws NullPointerException if the {@code data} array is {@code null}.
261 */
262 public static byte[] shiftLeft(final byte[] data, final int shift) {
263 final int bytes = min(shift >>> 3, data.length);
264 final int bits = shift & 7;
265
266 if (bytes > 0) {
267 for (int i = 0, n = data.length - bytes; i < n; ++i) {
268 data[data.length - 1 - i] = data[data.length - 1 - i - bytes];
269 }
270 for (int i = 0; i < bytes; ++i) {
271 data[i] = (byte)0;
272 }
273 }
274 if (bits > 0 && bytes < data.length) {
275 int carry = 0;
276 int nextCarry = 0;
277
278 for (int i = bytes; i < data.length; ++i) {
279 int d = data[i] & 0xFF;
280 nextCarry = (d >>> (8 - bits));
281
282 d <<= bits;
283 d |= carry;
284 data[i] = (byte)(d & 0xFF);
285
286 carry = nextCarry;
287 }
288 }
289
290 return data;
291 }
292
293 /**
294 * Increment the given {@code data} array.
295 *
296 * @param data the given {@code data} array.
297 * @return the given {@code data} array.
298 * @throws NullPointerException if the {@code data} array is {@code null}.
299 */
300 public static byte[] increment(final byte[] data) {
301 boolean carry = true;
302 for (int i = 0; i < data.length && carry; ++i) {
303 data[i] = (byte)(data[i] + 1);
304 carry = data[i] > 0xFF;
305 }
306
307 return data;
308 }
309
310 /**
311 * Invert the given {@code data} array.
312 *
313 * @param data the given {@code data} array.
314 * @return the given {@code data} array.
315 * @throws NullPointerException if the {@code data} array is {@code null}.
316 */
317 public static byte[] invert(final byte[] data) {
318 for (int i = data.length; --i >= 0;) {
319 data[i] = (byte)~data[i];
320 }
321 return data;
322 }
323
324 /**
325 * Make the two's complement of the given {@code data} array.
326 *
327 * @param data the given {@code data} array.
328 * @return the given {@code data} array.
329 * @throws NullPointerException if the {@code data} array is {@code null}.
330 */
331 public static byte[] complement(final byte[] data) {
332 return increment(invert(data));
333 }
334
335 /**
336 * Flip the bit at the given index.
337 *
338 * @param data the data array.
339 * @param index the index of the bit to flip.
340 * @throws IndexOutOfBoundsException if the index is
341 * {@code index >= max || index < 0}.
342 * @throws NullPointerException if the {@code data} array is {@code null}.
343 */
344 public static byte[] flip(final byte[] data, final int index) {
345 return get(data, index) ? unset(data, index) : set(data, index);
346 }
347
348 /**
349 * Convert the given {@link LargeInteger} value to an byte array.
350 *
351 * @see #toLargeInteger(byte[])
352 *
353 * @param value the value to convert.
354 * @return the byte array representing the given {@link LargeInteger}.
355 * @throws NullPointerException if the given value is {@code null}.
356 *
357 * @deprecated Will be removed.
358 */
359 @Deprecated
360 public static byte[] toByteArray(final LargeInteger value) {
361 final int bytes = (value.bitLength() >>> 3) + 1;
362
363 final byte[] array = new byte[bytes];
364 value.toByteArray(array, 0);
365 return reverse(array);
366 }
367
368 /**
369 * Convert the given byte array into an {@link LargeInteger}.
370 *
371 * @see #toByteArray(LargeInteger)
372 *
373 * @param array the byte array to convert.
374 * @return the {@link LargeInteger} built from the given byte array.
375 *
376 * @deprecated Will be removed.
377 */
378 @Deprecated
379 public static LargeInteger toLargeInteger(final byte[] array) {
380 return LargeInteger.valueOf(reverse(array.clone()), 0, array.length);
381 }
382
383
384 static byte[] reverse(final byte[] array) {
385 int i = 0;
386 int j = array.length;
387
388 while (i < j) {
389 swap(array, i++, --j);
390 }
391
392 return array;
393 }
394
395 private static void swap(final byte[] array, final int i, final int j) {
396 final byte temp = array[i];
397 array[i] = array[j];
398 array[j] = temp;
399 }
400
401 /**
402 * Convert a binary representation of the given byte array to a string. The
403 * string has the following format:
404 * <pre>
405 * Byte: 3 2 1 0
406 * | | | |
407 * Array: "11110011|10011101|01000000|00101010"
408 * | | | |
409 * Bit: 23 15 7 0
410 * </pre>
411 * <i>Only the array string is printed.</i>
412 *
413 * @see #fromByteString(String)
414 *
415 * @param data the byte array to convert to a string.
416 * @return the binary representation of the given byte array.
417 */
418 public static String toByteString(final byte... data) {
419 final StringBuilder out = new StringBuilder();
420
421 if (data.length > 0) {
422 for (int j = 7; j >= 0; --j) {
423 out.append((data[data.length - 1] >>> j) & 1);
424 }
425 }
426 for (int i = data.length - 2; i >= 0 ;--i) {
427 out.append('|');
428 for (int j = 7; j >= 0; --j) {
429 out.append((data[i] >>> j) & 1);
430 }
431 }
432
433 return out.toString();
434 }
435
436 /**
437 * Convert a string which was created with the {@link #toByteString(byte...)}
438 * method back to an byte array.
439 *
440 * @see #toByteString(byte...)
441 *
442 * @param data the string to convert.
443 * @return the byte array.
444 * @throws IllegalArgumentException if the given data string could not be
445 * converted.
446 */
447 public static byte[] fromByteString(final String data) {
448 final String[] parts = data.split("\\|");
449 final byte[] bytes = new byte[parts.length];
450
451 for (int i = 0; i < parts.length; ++i) {
452 if (parts[i].length() != 8) {
453 throw new IllegalArgumentException(
454 "Byte value doesn't contain 8 bit: " + parts[i]
455 );
456 }
457
458 try {
459 bytes[parts.length - 1 - i] = (byte)Integer.parseInt(parts[i], 2);
460 } catch (NumberFormatException e) {
461 throw new IllegalArgumentException(e);
462 }
463 }
464
465 return bytes;
466 }
467
468 /**
469 * Create a new {@code byte[]} array which can store at least the number
470 * of bits as defined by the given {@code length} parameter.
471 *
472 * @param length the number of bits, the returned byte array can store.
473 * @return the new byte array.s
474 *
475 * @deprecated Use {@link #newArray(int)} instead.
476 */
477 @Deprecated
478 public static byte[] newBitArray(final int length) {
479 return newArray(length);
480 }
481
482 /**
483 * Create a new {@code byte[]} array which can store at least the number
484 * of bits as defined by the given {@code length} parameter.
485 *
486 * @param length the number of bits, the returned byte array can store.
487 * @return the new byte array.s
488 */
489 public static byte[] newArray(final int length) {
490 return new byte[toByteLength(length)];
491 }
492
493 /**
494 * Create a new {@code byte[]} array which can store at least the number
495 * of bits as defined by the given {@code length} parameter. The returned
496 * byte array is initialized with ones according to the given ones
497 * probability {@code p}.
498 *
499 * @param length the number of bits, the returned byte array can store.
500 * @param p the ones probability of the returned byte array.
501 * @return the new byte array.s
502 * @throws IllegalArgumentException if {@code p} is not a valid probability.
503 *
504 * @deprecated Use {@link #newArray(int, double)} instead.
505 */
506 @Deprecated
507 public static byte[] newBitArray(final int length, final double p) {
508 return newArray(length, p);
509 }
510
511 /**
512 * Create a new {@code byte[]} array which can store at least the number
513 * of bits as defined by the given {@code length} parameter. The returned
514 * byte array is initialized with ones according to the given ones
515 * probability {@code p}.
516 *
517 * @param length the number of bits, the returned byte array can store.
518 * @param p the ones probability of the returned byte array.
519 * @return the new byte array.s
520 * @throws IllegalArgumentException if {@code p} is not a valid probability.
521 */
522 public static byte[] newArray(final int length, final double p) {
523 final byte[] bytes = newArray(length);
524
525 final IndexStream stream = IndexStream.Random(length, p);
526 for (int i = stream.next(); i != -1; i = stream.next()) {
527 bytes[i >>> 3] |= 1 << (i & 7);
528 }
529
530 return bytes;
531 }
532
533 /**
534 * Return the minimum number of bytes to store the given number of bits.
535 *
536 * @param bitLength the number of bits
537 * @return the number of bytes needed to store the given number of bits.
538 */
539 public static int toByteLength(final int bitLength) {
540 return (bitLength & 7) == 0 ? (bitLength >>> 3) : (bitLength >>> 3) + 1;
541 }
542
543 static long toLong(final byte[] data) {
544 return
545 (((long)data[0] << 56) +
546 ((long)(data[1] & 255) << 48) +
547 ((long)(data[2] & 255) << 40) +
548 ((long)(data[3] & 255) << 32) +
549 ((long)(data[4] & 255) << 24) +
550 ((data[5] & 255) << 16) +
551 ((data[6] & 255) << 8) +
552 ((data[7] & 255)));
553 }
554
555 static byte[] toBytes(final long value) {
556 final byte[] bytes = new byte[8];
557 bytes[0] = (byte)(value >>> 56);
558 bytes[1] = (byte)(value >>> 48);
559 bytes[2] = (byte)(value >>> 40);
560 bytes[3] = (byte)(value >>> 32);
561 bytes[4] = (byte)(value >>> 24);
562 bytes[5] = (byte)(value >>> 16);
563 bytes[6] = (byte)(value >>> 8);
564 bytes[7] = (byte)(value);
565 return bytes;
566 }
567
568 static byte[] writeInt(final int v, final byte[] data, final int start) {
569 if (data.length < 4 + start) {
570 throw new IllegalArgumentException(
571 "Byte array to short: " + data.length
572 );
573 }
574
575 data[start] = (byte)((v >>> 24) & 0xFF);
576 data[1 + start] = (byte)((v >>> 16) & 0xFF);
577 data[2 + start] = (byte)((v >>> 8) & 0xFF);
578 data[3 + start] = (byte)((v) & 0xFF);
579
580 return data;
581 }
582
583 static int readInt(final byte[] data, final int start) {
584 if (data.length < 4 + start) {
585 throw new IllegalArgumentException(
586 "Byte array to short: " + data.length
587 );
588 }
589
590 return ((data[start] << 24) +
591 (data[1 + start] << 16) +
592 (data[2 + start] << 8) +
593 (data[3 + start]));
594 }
595
596 }
|