001 /*
002 * Java Genetic Algorithm Library (jenetics-1.5.0).
003 * Copyright (c) 2007-2013 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: 2013-12-05 $</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 public static byte[] toByteArray(final LargeInteger value) {
358 final int bytes = (value.bitLength() >>> 3) + 1;
359
360 final byte[] array = new byte[bytes];
361 value.toByteArray(array, 0);
362 return reverse(array);
363 }
364
365 /**
366 * Convert the given byte array into an {@link LargeInteger}.
367 *
368 * @see #toByteArray(LargeInteger)
369 *
370 * @param array the byte array to convert.
371 * @return the {@link LargeInteger} built from the given byte array.
372 */
373 public static LargeInteger toLargeInteger(final byte[] array) {
374 return LargeInteger.valueOf(reverse(array.clone()), 0, array.length);
375 }
376
377
378 static byte[] reverse(final byte[] array) {
379 int i = 0;
380 int j = array.length;
381
382 while (i < j) {
383 swap(array, i++, --j);
384 }
385
386 return array;
387 }
388
389 private static void swap(final byte[] array, final int i, final int j) {
390 final byte temp = array[i];
391 array[i] = array[j];
392 array[j] = temp;
393 }
394
395 /**
396 * Convert a binary representation of the given byte array to a string. The
397 * string has the following format:
398 * <pre>
399 * Byte: 3 2 1 0
400 * | | | |
401 * Array: "11110011|10011101|01000000|00101010"
402 * | | | |
403 * Bit: 23 15 7 0
404 * </pre>
405 * <i>Only the array string is printed.</i>
406 *
407 * @see #fromByteString(String)
408 *
409 * @param data the byte array to convert to a string.
410 * @return the binary representation of the given byte array.
411 */
412 public static String toByteString(final byte... data) {
413 final StringBuilder out = new StringBuilder();
414
415 if (data.length > 0) {
416 for (int j = 7; j >= 0; --j) {
417 out.append((data[data.length - 1] >>> j) & 1);
418 }
419 }
420 for (int i = data.length - 2; i >= 0 ;--i) {
421 out.append('|');
422 for (int j = 7; j >= 0; --j) {
423 out.append((data[i] >>> j) & 1);
424 }
425 }
426
427 return out.toString();
428 }
429
430 /**
431 * Convert a string which was created with the {@link #toByteString(byte...)}
432 * method back to an byte array.
433 *
434 * @see #toByteString(byte...)
435 *
436 * @param data the string to convert.
437 * @return the byte array.
438 * @throws IllegalArgumentException if the given data string could not be
439 * converted.
440 */
441 public static byte[] fromByteString(final String data) {
442 final String[] parts = data.split("\\|");
443 final byte[] bytes = new byte[parts.length];
444
445 for (int i = 0; i < parts.length; ++i) {
446 if (parts[i].length() != 8) {
447 throw new IllegalArgumentException(
448 "Byte value doesn't contain 8 bit: " + parts[i]
449 );
450 }
451
452 try {
453 bytes[parts.length - 1 - i] = (byte)Integer.parseInt(parts[i], 2);
454 } catch (NumberFormatException e) {
455 throw new IllegalArgumentException(e);
456 }
457 }
458
459 return bytes;
460 }
461
462 /**
463 * Create a new {@code byte[]} array which can store at least the number
464 * of bits as defined by the given {@code length} parameter.
465 *
466 * @param length the number of bits, the returned byte array can store.
467 * @return the new byte array.s
468 *
469 * @deprecated Use {@link #newArray(int)} instead.
470 */
471 @Deprecated
472 public static byte[] newBitArray(final int length) {
473 return newArray(length);
474 }
475
476 /**
477 * Create a new {@code byte[]} array which can store at least the number
478 * of bits as defined by the given {@code length} parameter.
479 *
480 * @param length the number of bits, the returned byte array can store.
481 * @return the new byte array.s
482 */
483 public static byte[] newArray(final int length) {
484 return new byte[toByteLength(length)];
485 }
486
487 /**
488 * Create a new {@code byte[]} array which can store at least the number
489 * of bits as defined by the given {@code length} parameter. The returned
490 * byte array is initialized with ones according to the given ones
491 * probability {@code p}.
492 *
493 * @param length the number of bits, the returned byte array can store.
494 * @param p the ones probability of the returned byte array.
495 * @return the new byte array.s
496 * @throws IllegalArgumentException if {@code p} is not a valid probability.
497 *
498 * @deprecated Use {@link #newArray(int, double)} instead.
499 */
500 @Deprecated
501 public static byte[] newBitArray(final int length, final double p) {
502 return newArray(length, p);
503 }
504
505 /**
506 * Create a new {@code byte[]} array which can store at least the number
507 * of bits as defined by the given {@code length} parameter. The returned
508 * byte array is initialized with ones according to the given ones
509 * probability {@code p}.
510 *
511 * @param length the number of bits, the returned byte array can store.
512 * @param p the ones probability of the returned byte array.
513 * @return the new byte array.s
514 * @throws IllegalArgumentException if {@code p} is not a valid probability.
515 */
516 public static byte[] newArray(final int length, final double p) {
517 final byte[] bytes = newArray(length);
518
519 final IndexStream stream = IndexStream.Random(length, p);
520 for (int i = stream.next(); i != -1; i = stream.next()) {
521 bytes[i >>> 3] |= 1 << (i & 7);
522 }
523
524 return bytes;
525 }
526
527 /**
528 * Return the minimum number of bytes to store the given number of bits.
529 *
530 * @param bitLength the number of bits
531 * @return the number of bytes needed to store the given number of bits.
532 */
533 public static int toByteLength(final int bitLength) {
534 return (bitLength & 7) == 0 ? (bitLength >>> 3) : (bitLength >>> 3) + 1;
535 }
536
537 static long toLong(final byte[] data) {
538 return
539 (((long)data[0] << 56) +
540 ((long)(data[1] & 255) << 48) +
541 ((long)(data[2] & 255) << 40) +
542 ((long)(data[3] & 255) << 32) +
543 ((long)(data[4] & 255) << 24) +
544 ((data[5] & 255) << 16) +
545 ((data[6] & 255) << 8) +
546 ((data[7] & 255)));
547 }
548
549 static byte[] toBytes(final long value) {
550 final byte[] bytes = new byte[8];
551 bytes[0] = (byte)(value >>> 56);
552 bytes[1] = (byte)(value >>> 48);
553 bytes[2] = (byte)(value >>> 40);
554 bytes[3] = (byte)(value >>> 32);
555 bytes[4] = (byte)(value >>> 24);
556 bytes[5] = (byte)(value >>> 16);
557 bytes[6] = (byte)(value >>> 8);
558 bytes[7] = (byte)(value);
559 return bytes;
560 }
561
562 static byte[] writeInt(final int v, final byte[] data, final int start) {
563 if (data.length < 4 + start) {
564 throw new IllegalArgumentException(
565 "Byte array to short: " + data.length
566 );
567 }
568
569 data[start] = (byte)((v >>> 24) & 0xFF);
570 data[1 + start] = (byte)((v >>> 16) & 0xFF);
571 data[2 + start] = (byte)((v >>> 8) & 0xFF);
572 data[3 + start] = (byte)((v) & 0xFF);
573
574 return data;
575 }
576
577 static int readInt(final byte[] data, final int start) {
578 if (data.length < 4 + start) {
579 throw new IllegalArgumentException(
580 "Byte array to short: " + data.length
581 );
582 }
583
584 return ((data[start] << 24) +
585 (data[1 + start] << 16) +
586 (data[2 + start] << 8) +
587 (data[3 + start]));
588 }
589
590 }
591
592
593
|