001/* 002 * Java Genetic Algorithm Library (jenetics-8.0.0). 003 * Copyright (c) 2007-2024 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 operations 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] |= (byte)(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] &= (byte)~(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> 157 * start end 158 * | | 159 * data: +---+---+---+---+---+---+---+---+---+---+---+---+ 160 * +---------------+ 161 * +---------------+ 162 * otherData: +---+---+---+---+---+---+---+---+---+---+---+---+ 163 * | 164 * otherStart 165 * </pre> 166 * 167 * @param data the first byte array which is 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 if (end - start <= Byte.SIZE) { 210 int count = 0; 211 for (int i = start; i < end; ++i) { 212 if (get(bits, i)) { 213 ++count; 214 } 215 } 216 return count; 217 } 218 219 final int byteStart = start/Byte.SIZE + 1; 220 final int byteEnd = end/Byte.SIZE; 221 222 int count = 0; 223 for (int i = byteStart; i < byteEnd; ++i) { 224 count += count(bits[i]); 225 } 226 227 for (int i = start, n = byteStart*Byte.SIZE; i < n; ++i) { 228 if (get(bits, i)) { 229 ++count; 230 } 231 } 232 for (int i = byteEnd*8; i < end; ++i) { 233 if (get(bits, i)) { 234 ++count; 235 } 236 } 237 238 return count; 239 } 240 241 /** 242 * Returns the number of one-bits in the given {@code byte} {@code value}. 243 * 244 * @param value the value for which the one bits should be counted. 245 * @return the number of one bits in the given value 246 */ 247 public static int count(final byte value) { 248 return BIT_SET_TABLE[value + BIT_SET_TABLE_INDEX_OFFSET]; 249 } 250 251 /** 252 * Shifting all bits in the given {@code data} array the given 253 * {@code shift} to the right. The bits on the left side are filled with 254 * zeros. 255 * 256 * @param data the data bits to shift. 257 * @param shift the number of bits to shift. 258 * @return the given {@code data} array. 259 * @throws NullPointerException if the {@code data} array is {@code null}. 260 */ 261 public static byte[] shiftRight(final byte[] data, final int shift) { 262 final int bytes = min(shift >>> 3, data.length); 263 final int bits = shift & 7; 264 265 if (bytes > 0) { 266 for (int i = 0, n = data.length - bytes; i < n; ++i) { 267 data[i] = data[i + bytes]; 268 } 269 for (int i = data.length, n = data.length - bytes; --i >= n;) { 270 data[i] = (byte)0; 271 } 272 } 273 if (bits > 0 && bytes < data.length) { 274 int carry = 0; 275 int nextCarry = 0; 276 277 for (int i = data.length; --i >= 0;) { 278 int d = data[i] & 0xFF; 279 nextCarry = d << (Byte.SIZE - bits); 280 281 d >>>= bits; 282 d |= carry; 283 data[i] = (byte)(d & 0xFF); 284 285 carry = nextCarry; 286 } 287 } 288 289 return data; 290 } 291 292 /** 293 * Shifting all bits in the given {@code data} array the given 294 * {@code shift} to the left. The bits on the right side are filled with 295 * zeros. 296 * 297 * @param data the data bits to shift. 298 * @param shift the number of bits to shift. 299 * @return the given {@code data} array. 300 * @throws NullPointerException if the {@code data} array is {@code null}. 301 */ 302 public static byte[] shiftLeft(final byte[] data, final int shift) { 303 final int bytes = min(shift >>> 3, data.length); 304 final int bits = shift & 7; 305 306 if (bytes > 0) { 307 for (int i = 0, n = data.length - bytes; i < n; ++i) { 308 data[data.length - 1 - i] = data[data.length - 1 - i - bytes]; 309 } 310 for (int i = 0; i < bytes; ++i) { 311 data[i] = (byte)0; 312 } 313 } 314 if (bits > 0 && bytes < data.length) { 315 int carry = 0; 316 int nextCarry = 0; 317 318 for (int i = bytes; i < data.length; ++i) { 319 int d = data[i] & 0xFF; 320 nextCarry = d >>> (Byte.SIZE - bits); 321 322 d <<= bits; 323 d |= carry; 324 data[i] = (byte)(d & 0xFF); 325 326 carry = nextCarry; 327 } 328 } 329 330 return data; 331 } 332 333 /** 334 * Increment the given {@code data} array. 335 * 336 * @param data the given {@code data} array. 337 * @return the given {@code data} array. 338 * @throws NullPointerException if the {@code data} array is {@code null}. 339 */ 340 public static byte[] increment(final byte[] data) { 341 for (int i = 0; i < data.length && (data[i] += (byte)1) == 0; ++i); 342 return data; 343 } 344 345 /** 346 * Invert the given {@code data} array. 347 * 348 * @param data the given {@code data} array. 349 * @return the given {@code data} array. 350 * @throws NullPointerException if the {@code data} array is {@code null}. 351 */ 352 public static byte[] invert(final byte[] data) { 353 for (int i = data.length; --i >= 0;) { 354 data[i] = (byte)~data[i]; 355 } 356 return data; 357 } 358 359 /** 360 * Make the two's complement of the given {@code data} array. 361 * 362 * @param data the given {@code data} array. 363 * @return the given {@code data} array. 364 * @throws NullPointerException if the {@code data} array is {@code null}. 365 */ 366 public static byte[] complement(final byte[] data) { 367 return increment(invert(data)); 368 } 369 370 /** 371 * Flip the bit at the given index. 372 * 373 * @param data the data array. 374 * @param index the index of the bit to flip. 375 * @return the input array, for command chaining 376 * @throws IndexOutOfBoundsException if the index is 377 * {@code index >= max || index < 0}. 378 * @throws NullPointerException if the {@code data} array is {@code null}. 379 */ 380 public static byte[] flip(final byte[] data, final int index) { 381 return get(data, index) ? unset(data, index) : set(data, index); 382 } 383 384 public 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 * Copies the specified range of the specified array into a new array. 403 * 404 * @param data the bits from which a range is to be copied 405 * @param start the initial index of the range to be copied, inclusive 406 * @param end the final index of the range to be copied, exclusive. 407 * @return a new array containing the specified range from the original array 408 * @throws ArrayIndexOutOfBoundsException if start < 0 or 409 * start > data.length*8 410 * @throws IllegalArgumentException if start > end 411 * @throws NullPointerException if the {@code data} array is 412 * {@code null}. 413 */ 414 public static byte[] copy(final byte[] data, final int start, final int end) { 415 if (start > end) { 416 throw new IllegalArgumentException(String.format( 417 "start > end: %d > %d", start, end 418 )); 419 } 420 if (start < 0 || start > data.length << 3) { 421 throw new ArrayIndexOutOfBoundsException(String.format( 422 "%d < 0 || %d > %d", start, start, data.length*8 423 )); 424 } 425 426 final int to = min(data.length << 3, end); 427 final int byteStart = start >>> 3; 428 final int bitStart = start & 7; 429 final int bitLength = to - start; 430 431 final byte[] copy = new byte[toByteLength(to - start)]; 432 433 if (copy.length > 0) { 434 // Perform the byte wise right shift. 435 System.arraycopy(data, byteStart, copy, 0, copy.length); 436 437 // Do the remaining bit wise right shift. 438 shiftRight(copy, bitStart); 439 440 // Add the 'lost' bits from the next byte, if available. 441 if (data.length > copy.length + byteStart) { 442 copy[copy.length - 1] |= (byte)(data[byteStart + copy.length] 443 << (Byte.SIZE - bitStart)); 444 } 445 446 // Trim (delete) the overhanging bits. 447 copy[copy.length - 1] &= (byte)(0xFF >>> ((copy.length << 3) - bitLength)); 448 } 449 450 return copy; 451 } 452 453 public static boolean getAndSet(final byte[] array, final int index) { 454 final boolean result = get(array, index); 455 set(array, index); 456 return result; 457 } 458 459 /** 460 * Convert a binary representation of the given byte array to a string. The 461 * string has the following format: 462 * <pre> 463 * Byte: 3 2 1 0 464 * | | | | 465 * Array: "11110011|10011101|01000000|00101010" 466 * | | | | 467 * Bit: 23 15 7 0 468 * </pre> 469 * <i>Only the array string is printed.</i> 470 * 471 * @see #fromByteString(String) 472 * 473 * @param data the byte array to convert to a string. 474 * @return the binary representation of the given byte array. 475 */ 476 public static String toByteString(final byte... data) { 477 final StringBuilder out = new StringBuilder(); 478 479 if (data.length > 0) { 480 for (int j = 7; j >= 0; --j) { 481 out.append((data[data.length - 1] >>> j) & 1); 482 } 483 } 484 for (int i = data.length - 2; i >= 0 ;--i) { 485 out.append('|'); 486 for (int j = 7; j >= 0; --j) { 487 out.append((data[i] >>> j) & 1); 488 } 489 } 490 491 return out.toString(); 492 } 493 494 /** 495 * Convert a string which was created with the {@link #toByteString(byte...)} 496 * method back to a byte array. 497 * 498 * @see #toByteString(byte...) 499 * 500 * @param data the string to convert. 501 * @return the byte array. 502 * @throws IllegalArgumentException if the given data string could not be 503 * converted. 504 */ 505 public static byte[] fromByteString(final String data) { 506 final String[] parts = data.split("\\|"); 507 final byte[] bytes = new byte[parts.length]; 508 509 for (int i = 0; i < parts.length; ++i) { 510 if (parts[i].length() != Byte.SIZE) { 511 throw new IllegalArgumentException( 512 "Byte value doesn't contain 8 bit: " + parts[i] 513 ); 514 } 515 516 try { 517 bytes[parts.length - 1 - i] = (byte)parseInt(parts[i], 2); 518 } catch (NumberFormatException e) { 519 throw new IllegalArgumentException(e); 520 } 521 } 522 523 return bytes; 524 } 525 526 /** 527 * Create a new {@code byte[]} array which can store at least the number 528 * of bits as defined by the given {@code length} parameter. 529 * 530 * @param length the number of bits, the returned byte array can store. 531 * @return the new byte array.s 532 */ 533 public static byte[] newArray(final int length) { 534 return new byte[toByteLength(length)]; 535 } 536 537 /** 538 * Create a new {@code byte[]} array which can store at least the number 539 * of bits as defined by the given {@code length} parameter. The returned 540 * byte array is initialized with ones according to the given ones 541 * probability {@code p}. 542 * 543 * @param length the number of bits, the returned byte array can store. 544 * @param p the ones probability of the returned byte array. 545 * @return the new byte array.s 546 * @throws IllegalArgumentException if {@code p} is not a valid probability. 547 */ 548 public static byte[] newArray(final int length, final double p) { 549 final byte[] bytes = newArray(length); 550 551 Randoms.indexes(RandomRegistry.random(), length, p) 552 .forEach(i -> bytes[i >>> 3] |= (byte)(1 << (i & 7))); 553 554 return bytes; 555 } 556 557 /** 558 * Return the minimum number of bytes to store the given number of bits. 559 * 560 * @param bitLength the number of bits 561 * @return the number of bytes needed to store the given number of bits. 562 */ 563 public static int toByteLength(final int bitLength) { 564 if (bitLength < 0) { 565 throw new IllegalArgumentException( 566 "Bit length must not smaller then zero: " + bitLength 567 ); 568 } 569 570 return (bitLength & 7) == 0 // Is a multiple of Byte.SIZE (8) 571 ? (bitLength >>> 3) // divided by Byte.SIZE (8) 572 : (bitLength >>> 3) + 1; // divide by Byte.SIZE and add one 573 } 574 575 public static int toInt(final byte[] data) { 576 return 577 ((data[0] & 255) << 24) + 578 ((data[1] & 255) << 16) + 579 ((data[2] & 255) << 8) + 580 (data[3] & 255); 581 } 582 583 public static byte[] toBytes(final int value) { 584 final byte[] bytes = new byte[4]; 585 bytes[0] = (byte)(value >>> 24); 586 bytes[1] = (byte)(value >>> 16); 587 bytes[2] = (byte)(value >>> 8); 588 bytes[3] = (byte) value; 589 return bytes; 590 } 591 592 public static long toLong(final byte[] data) { 593 return 594 ((long)data[0] << 56) + 595 ((long)(data[1] & 255) << 48) + 596 ((long)(data[2] & 255) << 40) + 597 ((long)(data[3] & 255) << 32) + 598 ((long)(data[4] & 255) << 24) + 599 ((data[5] & 255) << 16) + 600 ((data[6] & 255) << 8) + 601 (data[7] & 255); 602 } 603 604 public static byte[] toBytes(final long value) { 605 final byte[] bytes = new byte[8]; 606 bytes[0] = (byte)(value >>> 56); 607 bytes[1] = (byte)(value >>> 48); 608 bytes[2] = (byte)(value >>> 40); 609 bytes[3] = (byte)(value >>> 32); 610 bytes[4] = (byte)(value >>> 24); 611 bytes[5] = (byte)(value >>> 16); 612 bytes[6] = (byte)(value >>> 8); 613 bytes[7] = (byte) value; 614 return bytes; 615 } 616 617}