001 /*
002 * Java Genetic Algorithm Library (jenetics-3.5.0).
003 * Copyright (c) 2007-2016 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.internal.util;
021
022 import static java.lang.Integer.parseInt;
023 import static java.lang.Math.min;
024
025 import org.jenetics.internal.math.random;
026
027 import org.jenetics.util.RandomRegistry;
028
029
030 /**
031 * Some bit utils. All operation assume <a href="http://en.wikipedia.org/wiki/Endianness">
032 * <b>little-endian</b></a> byte order.
033 *
034 * <pre>
035 * Byte: 3 2 1 0
036 * | | | |
037 * Array: |11110011|10011101|01000000|00101010|
038 * | | | |
039 * Bit: 23 15 7 0
040 * </pre>
041 *
042 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
043 * @since 1.0
044 * @version 3.0
045 */
046 public final class bit {
047 private bit() {require.noInstance();}
048
049 /**
050 * Lookup table for counting the number of set bits in a {@code byte} value.
051 */
052 private static final byte[] BIT_SET_TABLE = {
053 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
054 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
055 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
056 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
057 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
058 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
059 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
060 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
061 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
062 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
063 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
064 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
065 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
066 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
067 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
068 (byte)5, (byte)6, (byte)6, (byte)7, (byte)6, (byte)7, (byte)7, (byte)8,
069 (byte)0, (byte)1, (byte)1, (byte)2, (byte)1, (byte)2, (byte)2, (byte)3,
070 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
071 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
072 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
073 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
074 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
075 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
076 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
077 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
078 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
079 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
080 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
081 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
082 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
083 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
084 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7
085 };
086 private static final int BIT_SET_TABLE_INDEX_OFFSET = 128;
087
088 /**
089 * Return the (boolean) value of the byte array at the given bit index.
090 *
091 * @param data the byte array.
092 * @param index the bit index.
093 * @return the value at the given bit index.
094 * @throws IndexOutOfBoundsException if the index is
095 * {@code index >= max || index < 0}.
096 * @throws NullPointerException if the {@code data} array is {@code null}.
097 */
098 public static boolean get(final byte[] data, final int index) {
099 return (data[index >>> 3] & (1 << (index & 7))) != 0;
100 }
101
102 /**
103 * Set the bit in the given byte array at the bit position (not the index
104 * within the byte array) to the specified value.
105 *
106 * @param data the byte array.
107 * @param index the bit index within the byte array.
108 * @param value the value to set.
109 * @return the given data array.
110 * @throws IndexOutOfBoundsException if the index is
111 * {@code index >= max || index < 0}.
112 * @throws NullPointerException if the {@code data} array is {@code null}.
113 */
114 public static byte[] set(
115 final byte[] data,
116 final int index,
117 final boolean value
118 ) {
119 return value ? set(data, index) : unset(data, index);
120 }
121
122 /**
123 * Set the bit in the given byte array at the bit position (not the index
124 * within the byte array) to {@code true}.
125 *
126 * @param data the byte array.
127 * @param index the bit index within the byte array.
128 * @return the given data array.
129 * @throws IndexOutOfBoundsException if the index is
130 * {@code index >= max || index < 0}.
131 * @throws NullPointerException if the {@code data} array is {@code null}.
132 */
133 public static byte[] set(final byte[] data, final int index) {
134 data[index >>> 3] |= 1 << (index & 7);
135 return data;
136 }
137
138 /**
139 * Set the bit in the given byte array at the bit position (not the index
140 * within the byte array) to {@code false}.
141 *
142 * @param data the byte array.
143 * @param index the bit index within the byte array.
144 * @return the given data array.
145 * @throws IndexOutOfBoundsException if the index is
146 * {@code index >= max || index < 0}.
147 * @throws NullPointerException if the {@code data} array is {@code null}.
148 */
149 public static byte[] unset(final byte[] data, final int index) {
150 data[index >>> 3] &= ~(1 << (index & 7));
151 return data;
152 }
153
154 /**
155 * Swap a given range with a range of the same size with another array.
156 *
157 * <pre>
158 * start end
159 * | |
160 * data: +---+---+---+---+---+---+---+---+---+---+---+---+
161 * +---------------+
162 * +---------------+
163 * otherData: +---+---+---+---+---+---+---+---+---+---+---+---+
164 * |
165 * otherStart
166 * </pre>
167 *
168 * @param data the first byte array which are used for swapping.
169 * @param start the start bit index of the {@code data} byte array,
170 * inclusively.
171 * @param end the end bit index of the {@code data} byte array, exclusively.
172 * @param otherData the other byte array to swap the elements with.
173 * @param otherStart the start index of the {@code otherData} byte array.
174 * @throws IndexOutOfBoundsException if {@code start > end} or
175 * if {@code start < 0 || end >= data.length*8 || otherStart < 0 ||
176 * otherStart + (end - start) >= otherData.length*8}
177 */
178 public static void swap(
179 final byte[] data, final int start, final int end,
180 final byte[] otherData, final int otherStart
181 ) {
182 for (int i = end - start; --i >= 0;) {
183 final boolean temp = get(data, i + start);
184 set(data, i + start, get(otherData, otherStart + i));
185 set(otherData, otherStart + i, temp);
186 }
187 }
188
189 /**
190 * Returns the number of one-bits in the given {@code byte} array.
191 *
192 * @param data the {@code byte} array for which the one bits should be
193 * counted.
194 * @return the number of one bits in the given {@code byte} array.
195 */
196 public static int count(final byte[] data) {
197 int count = 0;
198 for (int i = data.length; --i >= 0;) {
199 count += count(data[i]);
200 }
201 return count;
202 }
203
204 /**
205 * Returns the number of one-bits in the given {@code byte} {@code value}.
206 *
207 * @param value the value for which the one bits should be counted.
208 * @return the number of one bits in the given value
209 */
210 public static int count(final byte value) {
211 return BIT_SET_TABLE[value + BIT_SET_TABLE_INDEX_OFFSET];
212 }
213
214 /**
215 * Shifting all bits in the given {@code data} array the given
216 * {@code shift} to the right. The bits on the left side are filled with
217 * zeros.
218 *
219 * @param data the data bits to shift.
220 * @param shift the number of bits to shift.
221 * @return the given {@code data} array.
222 * @throws NullPointerException if the {@code data} array is {@code null}.
223 */
224 public static byte[] shiftRight(final byte[] data, final int shift) {
225 final int bytes = min(shift >>> 3, data.length);
226 final int bits = shift & 7;
227
228 if (bytes > 0) {
229 for (int i = 0, n = data.length - bytes; i < n; ++i) {
230 data[i] = data[i + bytes];
231 }
232 for (int i = data.length, n = data.length - bytes; --i >= n;) {
233 data[i] = (byte)0;
234 }
235 }
236 if (bits > 0 && bytes < data.length) {
237 int carry = 0;
238 int nextCarry = 0;
239
240 for (int i = data.length; --i >= 0;) {
241 int d = data[i] & 0xFF;
242 nextCarry = d << (Byte.SIZE - bits);
243
244 d >>>= bits;
245 d |= carry;
246 data[i] = (byte)(d & 0xFF);
247
248 carry = nextCarry;
249 }
250 }
251
252 return data;
253 }
254
255 /**
256 * Shifting all bits in the given {@code data} array the given
257 * {@code shift} to the left. The bits on the right side are filled with
258 * zeros.
259 *
260 * @param data the data bits to shift.
261 * @param shift the number of bits to shift.
262 * @return the given {@code data} array.
263 * @throws NullPointerException if the {@code data} array is {@code null}.
264 */
265 public static byte[] shiftLeft(final byte[] data, final int shift) {
266 final int bytes = min(shift >>> 3, data.length);
267 final int bits = shift & 7;
268
269 if (bytes > 0) {
270 for (int i = 0, n = data.length - bytes; i < n; ++i) {
271 data[data.length - 1 - i] = data[data.length - 1 - i - bytes];
272 }
273 for (int i = 0; i < bytes; ++i) {
274 data[i] = (byte)0;
275 }
276 }
277 if (bits > 0 && bytes < data.length) {
278 int carry = 0;
279 int nextCarry = 0;
280
281 for (int i = bytes; i < data.length; ++i) {
282 int d = data[i] & 0xFF;
283 nextCarry = d >>> (Byte.SIZE - bits);
284
285 d <<= bits;
286 d |= carry;
287 data[i] = (byte)(d & 0xFF);
288
289 carry = nextCarry;
290 }
291 }
292
293 return data;
294 }
295
296 /**
297 * Increment the given {@code data} array.
298 *
299 * @param data the given {@code data} array.
300 * @return the given {@code data} array.
301 * @throws NullPointerException if the {@code data} array is {@code null}.
302 */
303 public static byte[] increment(final byte[] data) {
304 boolean carry = true;
305 for (int i = 0; i < data.length && carry; ++i) {
306 data[i] = (byte)(data[i] + 1);
307 carry = data[i] > 0xFF;
308 }
309
310 return data;
311 }
312
313 /**
314 * Invert the given {@code data} array.
315 *
316 * @param data the given {@code data} array.
317 * @return the given {@code data} array.
318 * @throws NullPointerException if the {@code data} array is {@code null}.
319 */
320 public static byte[] invert(final byte[] data) {
321 for (int i = data.length; --i >= 0;) {
322 data[i] = (byte)~data[i];
323 }
324 return data;
325 }
326
327 /**
328 * Make the two's complement of the given {@code data} array.
329 *
330 * @param data the given {@code data} array.
331 * @return the given {@code data} array.
332 * @throws NullPointerException if the {@code data} array is {@code null}.
333 */
334 public static byte[] complement(final byte[] data) {
335 return increment(invert(data));
336 }
337
338 /**
339 * Flip the bit at the given index.
340 *
341 * @param data the data array.
342 * @param index the index of the bit to flip.
343 * @return the input array, for command chaining
344 * @throws IndexOutOfBoundsException if the index is
345 * {@code index >= max || index < 0}.
346 * @throws NullPointerException if the {@code data} array is {@code null}.
347 */
348 public static byte[] flip(final byte[] data, final int index) {
349 return get(data, index) ? unset(data, index) : set(data, index);
350 }
351
352 public static byte[] reverse(final byte[] array) {
353 int i = 0;
354 int j = array.length;
355
356 while (i < j) {
357 swap(array, i++, --j);
358 }
359
360 return array;
361 }
362
363 private static void swap(final byte[] array, final int i, final int j) {
364 final byte temp = array[i];
365 array[i] = array[j];
366 array[j] = temp;
367 }
368
369 /**
370 * Copies the specified range of the specified array into a new array.
371 *
372 * @param data the bits from which a range is to be copied
373 * @param start the initial index of the range to be copied, inclusive
374 * @param end the final index of the range to be copied, exclusive.
375 * @return a new array containing the specified range from the original array
376 * @throws ArrayIndexOutOfBoundsException if start < 0 or
377 * start > data.length*8
378 * @throws IllegalArgumentException if start > end
379 * @throws NullPointerException if the {@code data} array is
380 * {@code null}.
381 */
382 public static byte[] copy(final byte[] data, final int start, final int end) {
383 if (start > end) {
384 throw new IllegalArgumentException(String.format(
385 "start > end: %d > %d", start, end
386 ));
387 }
388 if (start < 0 || start > data.length << 3) {
389 throw new ArrayIndexOutOfBoundsException(String.format(
390 "%d < 0 || %d > %d", start, start, data.length*8
391 ));
392 }
393
394 final int to = min(data.length << 3, end);
395 final int byteStart = start >>> 3;
396 final int bitStart = start & 7;
397 final int bitLength = to - start;
398
399 final byte[] copy = new byte[toByteLength(to - start)];
400
401 if (copy.length > 0) {
402 // Perform the byte wise right shift.
403 System.arraycopy(data, byteStart, copy, 0, copy.length);
404
405 // Do the remaining bit wise right shift.
406 shiftRight(copy, bitStart);
407
408 // Add the 'lost' bits from the next byte, if available.
409 if (data.length > copy.length + byteStart) {
410 copy[copy.length - 1] |= (byte)(data[byteStart + copy.length]
411 << (Byte.SIZE - bitStart));
412 }
413
414 // Trim (delete) the overhanging bits.
415 copy[copy.length - 1] &= 0xFF >>> ((copy.length << 3) - bitLength);
416 }
417
418 return copy;
419 }
420
421 public static boolean getAndSet(final byte[] array, final int index) {
422 final boolean result = get(array, index);
423 set(array, index);
424 return result;
425 }
426
427 /**
428 * Convert a binary representation of the given byte array to a string. The
429 * string has the following format:
430 * <pre>
431 * Byte: 3 2 1 0
432 * | | | |
433 * Array: "11110011|10011101|01000000|00101010"
434 * | | | |
435 * Bit: 23 15 7 0
436 * </pre>
437 * <i>Only the array string is printed.</i>
438 *
439 * @see #fromByteString(String)
440 *
441 * @param data the byte array to convert to a string.
442 * @return the binary representation of the given byte array.
443 */
444 public static String toByteString(final byte... data) {
445 final StringBuilder out = new StringBuilder();
446
447 if (data.length > 0) {
448 for (int j = 7; j >= 0; --j) {
449 out.append((data[data.length - 1] >>> j) & 1);
450 }
451 }
452 for (int i = data.length - 2; i >= 0 ;--i) {
453 out.append('|');
454 for (int j = 7; j >= 0; --j) {
455 out.append((data[i] >>> j) & 1);
456 }
457 }
458
459 return out.toString();
460 }
461
462 /**
463 * Convert a string which was created with the {@link #toByteString(byte...)}
464 * method back to an byte array.
465 *
466 * @see #toByteString(byte...)
467 *
468 * @param data the string to convert.
469 * @return the byte array.
470 * @throws IllegalArgumentException if the given data string could not be
471 * converted.
472 */
473 public static byte[] fromByteString(final String data) {
474 final String[] parts = data.split("\\|");
475 final byte[] bytes = new byte[parts.length];
476
477 for (int i = 0; i < parts.length; ++i) {
478 if (parts[i].length() != Byte.SIZE) {
479 throw new IllegalArgumentException(
480 "Byte value doesn't contain 8 bit: " + parts[i]
481 );
482 }
483
484 try {
485 bytes[parts.length - 1 - i] = (byte)parseInt(parts[i], 2);
486 } catch (NumberFormatException e) {
487 throw new IllegalArgumentException(e);
488 }
489 }
490
491 return bytes;
492 }
493
494 /**
495 * Create a new {@code byte[]} array which can store at least the number
496 * of bits as defined by the given {@code length} parameter.
497 *
498 * @param length the number of bits, the returned byte array can store.
499 * @return the new byte array.s
500 */
501 public static byte[] newArray(final int length) {
502 return new byte[toByteLength(length)];
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 random.indexes(RandomRegistry.getRandom(), length, p)
520 .forEach(i -> bytes[i >>> 3] |= 1 << (i & 7));
521
522 return bytes;
523 }
524
525 /**
526 * Return the minimum number of bytes to store the given number of bits.
527 *
528 * @param bitLength the number of bits
529 * @return the number of bytes needed to store the given number of bits.
530 */
531 public static int toByteLength(final int bitLength) {
532 return (bitLength & 7) == 0 ? (bitLength >>> 3) : (bitLength >>> 3) + 1;
533 }
534
535 public static long toLong(final byte[] data) {
536 return
537 ((long)data[0] << 56) +
538 ((long)(data[1] & 255) << 48) +
539 ((long)(data[2] & 255) << 40) +
540 ((long)(data[3] & 255) << 32) +
541 ((long)(data[4] & 255) << 24) +
542 ((data[5] & 255) << 16) +
543 ((data[6] & 255) << 8) +
544 (data[7] & 255);
545 }
546
547 public static byte[] toBytes(final long value) {
548 final byte[] bytes = new byte[8];
549 bytes[0] = (byte)(value >>> 56);
550 bytes[1] = (byte)(value >>> 48);
551 bytes[2] = (byte)(value >>> 40);
552 bytes[3] = (byte)(value >>> 32);
553 bytes[4] = (byte)(value >>> 24);
554 bytes[5] = (byte)(value >>> 16);
555 bytes[6] = (byte)(value >>> 8);
556 bytes[7] = (byte) value;
557 return bytes;
558 }
559
560 }
|