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