001/** 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, software 013 * distributed under the License is distributed on an "AS IS" BASIS, 014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 015 * See the License for the specific language governing permissions and 016 * limitations under the License. 017 */ 018package org.apache.hadoop.hbase.util; 019 020import static org.apache.hbase.thirdparty.com.google.common.base.Preconditions.checkArgument; 021import static org.apache.hbase.thirdparty.com.google.common.base.Preconditions.checkNotNull; 022import static org.apache.hbase.thirdparty.com.google.common.base.Preconditions.checkPositionIndex; 023 024import java.io.DataInput; 025import java.io.DataOutput; 026import java.io.IOException; 027import java.io.UnsupportedEncodingException; 028import java.math.BigDecimal; 029import java.math.BigInteger; 030import java.nio.ByteBuffer; 031import java.nio.charset.StandardCharsets; 032import java.security.SecureRandom; 033import java.util.ArrayList; 034import java.util.Arrays; 035import java.util.Collection; 036import java.util.Collections; 037import java.util.Comparator; 038import java.util.Iterator; 039import java.util.List; 040 041import org.apache.hadoop.hbase.Cell; 042import org.apache.hadoop.hbase.CellComparator; 043import org.apache.hadoop.hbase.KeyValue; 044import org.apache.hadoop.io.RawComparator; 045import org.apache.hadoop.io.WritableComparator; 046import org.apache.hadoop.io.WritableUtils; 047import org.apache.yetus.audience.InterfaceAudience; 048import org.slf4j.Logger; 049import org.slf4j.LoggerFactory; 050 051import org.apache.hbase.thirdparty.com.google.common.annotations.VisibleForTesting; 052import org.apache.hbase.thirdparty.org.apache.commons.collections4.CollectionUtils; 053 054import com.google.protobuf.ByteString; 055 056import sun.misc.Unsafe; 057 058/** 059 * Utility class that handles byte arrays, conversions to/from other types, 060 * comparisons, hash code generation, manufacturing keys for HashMaps or 061 * HashSets, and can be used as key in maps or trees. 062 */ 063@SuppressWarnings("restriction") 064@InterfaceAudience.Public 065@edu.umd.cs.findbugs.annotations.SuppressWarnings( 066 value="EQ_CHECK_FOR_OPERAND_NOT_COMPATIBLE_WITH_THIS", 067 justification="It has been like this forever") 068public class Bytes implements Comparable<Bytes> { 069 070 // Using the charset canonical name for String/byte[] conversions is much 071 // more efficient due to use of cached encoders/decoders. 072 private static final String UTF8_CSN = StandardCharsets.UTF_8.name(); 073 074 //HConstants.EMPTY_BYTE_ARRAY should be updated if this changed 075 private static final byte [] EMPTY_BYTE_ARRAY = new byte [0]; 076 077 private static final Logger LOG = LoggerFactory.getLogger(Bytes.class); 078 079 /** 080 * Size of boolean in bytes 081 */ 082 public static final int SIZEOF_BOOLEAN = Byte.SIZE / Byte.SIZE; 083 084 /** 085 * Size of byte in bytes 086 */ 087 public static final int SIZEOF_BYTE = SIZEOF_BOOLEAN; 088 089 /** 090 * Size of char in bytes 091 */ 092 public static final int SIZEOF_CHAR = Character.SIZE / Byte.SIZE; 093 094 /** 095 * Size of double in bytes 096 */ 097 public static final int SIZEOF_DOUBLE = Double.SIZE / Byte.SIZE; 098 099 /** 100 * Size of float in bytes 101 */ 102 public static final int SIZEOF_FLOAT = Float.SIZE / Byte.SIZE; 103 104 /** 105 * Size of int in bytes 106 */ 107 public static final int SIZEOF_INT = Integer.SIZE / Byte.SIZE; 108 109 /** 110 * Size of long in bytes 111 */ 112 public static final int SIZEOF_LONG = Long.SIZE / Byte.SIZE; 113 114 /** 115 * Size of short in bytes 116 */ 117 public static final int SIZEOF_SHORT = Short.SIZE / Byte.SIZE; 118 119 /** 120 * Mask to apply to a long to reveal the lower int only. Use like this: 121 * int i = (int)(0xFFFFFFFF00000000L ^ some_long_value); 122 */ 123 public static final long MASK_FOR_LOWER_INT_IN_LONG = 0xFFFFFFFF00000000L; 124 125 /** 126 * Estimate of size cost to pay beyond payload in jvm for instance of byte []. 127 * Estimate based on study of jhat and jprofiler numbers. 128 */ 129 // JHat says BU is 56 bytes. 130 // SizeOf which uses java.lang.instrument says 24 bytes. (3 longs?) 131 public static final int ESTIMATED_HEAP_TAX = 16; 132 133 private static final boolean UNSAFE_UNALIGNED = UnsafeAvailChecker.unaligned(); 134 135 /** 136 * Returns length of the byte array, returning 0 if the array is null. 137 * Useful for calculating sizes. 138 * @param b byte array, which can be null 139 * @return 0 if b is null, otherwise returns length 140 */ 141 final public static int len(byte[] b) { 142 return b == null ? 0 : b.length; 143 } 144 145 private byte[] bytes; 146 private int offset; 147 private int length; 148 149 /** 150 * Create a zero-size sequence. 151 */ 152 public Bytes() { 153 super(); 154 } 155 156 /** 157 * Create a Bytes using the byte array as the initial value. 158 * @param bytes This array becomes the backing storage for the object. 159 */ 160 public Bytes(byte[] bytes) { 161 this(bytes, 0, bytes.length); 162 } 163 164 /** 165 * Set the new Bytes to the contents of the passed 166 * <code>ibw</code>. 167 * @param ibw the value to set this Bytes to. 168 */ 169 public Bytes(final Bytes ibw) { 170 this(ibw.get(), ibw.getOffset(), ibw.getLength()); 171 } 172 173 /** 174 * Set the value to a given byte range 175 * @param bytes the new byte range to set to 176 * @param offset the offset in newData to start at 177 * @param length the number of bytes in the range 178 */ 179 public Bytes(final byte[] bytes, final int offset, 180 final int length) { 181 this.bytes = bytes; 182 this.offset = offset; 183 this.length = length; 184 } 185 186 /** 187 * Copy bytes from ByteString instance. 188 * @param byteString copy from 189 * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0. 190 */ 191 @Deprecated 192 public Bytes(final ByteString byteString) { 193 this(byteString.toByteArray()); 194 } 195 196 /** 197 * Get the data from the Bytes. 198 * @return The data is only valid between offset and offset+length. 199 */ 200 public byte [] get() { 201 if (this.bytes == null) { 202 throw new IllegalStateException("Uninitialiized. Null constructor " + 203 "called w/o accompaying readFields invocation"); 204 } 205 return this.bytes; 206 } 207 208 /** 209 * @param b Use passed bytes as backing array for this instance. 210 */ 211 public void set(final byte [] b) { 212 set(b, 0, b.length); 213 } 214 215 /** 216 * @param b Use passed bytes as backing array for this instance. 217 * @param offset 218 * @param length 219 */ 220 public void set(final byte [] b, final int offset, final int length) { 221 this.bytes = b; 222 this.offset = offset; 223 this.length = length; 224 } 225 226 /** 227 * @return the number of valid bytes in the buffer 228 * @deprecated use {@link #getLength()} instead 229 */ 230 @Deprecated 231 public int getSize() { 232 if (this.bytes == null) { 233 throw new IllegalStateException("Uninitialiized. Null constructor " + 234 "called w/o accompaying readFields invocation"); 235 } 236 return this.length; 237 } 238 239 /** 240 * @return the number of valid bytes in the buffer 241 */ 242 public int getLength() { 243 if (this.bytes == null) { 244 throw new IllegalStateException("Uninitialiized. Null constructor " + 245 "called w/o accompaying readFields invocation"); 246 } 247 return this.length; 248 } 249 250 /** 251 * @return offset 252 */ 253 public int getOffset(){ 254 return this.offset; 255 } 256 257 /** 258 * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0. 259 */ 260 @Deprecated 261 public ByteString toByteString() { 262 return ByteString.copyFrom(this.bytes, this.offset, this.length); 263 } 264 265 @Override 266 public int hashCode() { 267 return Bytes.hashCode(bytes, offset, length); 268 } 269 270 /** 271 * Define the sort order of the Bytes. 272 * @param that The other bytes writable 273 * @return Positive if left is bigger than right, 0 if they are equal, and 274 * negative if left is smaller than right. 275 */ 276 @Override 277 public int compareTo(Bytes that) { 278 return BYTES_RAWCOMPARATOR.compare( 279 this.bytes, this.offset, this.length, 280 that.bytes, that.offset, that.length); 281 } 282 283 /** 284 * Compares the bytes in this object to the specified byte array 285 * @param that 286 * @return Positive if left is bigger than right, 0 if they are equal, and 287 * negative if left is smaller than right. 288 */ 289 public int compareTo(final byte [] that) { 290 return BYTES_RAWCOMPARATOR.compare( 291 this.bytes, this.offset, this.length, 292 that, 0, that.length); 293 } 294 295 /** 296 * @see Object#equals(Object) 297 */ 298 @Override 299 public boolean equals(Object right_obj) { 300 if (right_obj instanceof byte []) { 301 return compareTo((byte [])right_obj) == 0; 302 } 303 if (right_obj instanceof Bytes) { 304 return compareTo((Bytes)right_obj) == 0; 305 } 306 return false; 307 } 308 309 /** 310 * @see Object#toString() 311 */ 312 @Override 313 public String toString() { 314 return Bytes.toString(bytes, offset, length); 315 } 316 317 /** 318 * @param array List of byte []. 319 * @return Array of byte []. 320 */ 321 public static byte [][] toArray(final List<byte []> array) { 322 // List#toArray doesn't work on lists of byte []. 323 byte[][] results = new byte[array.size()][]; 324 for (int i = 0; i < array.size(); i++) { 325 results[i] = array.get(i); 326 } 327 return results; 328 } 329 330 /** 331 * Returns a copy of the bytes referred to by this writable 332 */ 333 public byte[] copyBytes() { 334 return Arrays.copyOfRange(bytes, offset, offset+length); 335 } 336 /** 337 * Byte array comparator class. 338 */ 339 @InterfaceAudience.Public 340 public static class ByteArrayComparator implements RawComparator<byte []> { 341 /** 342 * Constructor 343 */ 344 public ByteArrayComparator() { 345 super(); 346 } 347 @Override 348 public int compare(byte [] left, byte [] right) { 349 return compareTo(left, right); 350 } 351 @Override 352 public int compare(byte [] b1, int s1, int l1, byte [] b2, int s2, int l2) { 353 return LexicographicalComparerHolder.BEST_COMPARER. 354 compareTo(b1, s1, l1, b2, s2, l2); 355 } 356 } 357 358 /** 359 * A {@link ByteArrayComparator} that treats the empty array as the largest value. 360 * This is useful for comparing row end keys for regions. 361 */ 362 // TODO: unfortunately, HBase uses byte[0] as both start and end keys for region 363 // boundaries. Thus semantically, we should treat empty byte array as the smallest value 364 // while comparing row keys, start keys etc; but as the largest value for comparing 365 // region boundaries for endKeys. 366 @InterfaceAudience.Public 367 public static class RowEndKeyComparator extends ByteArrayComparator { 368 @Override 369 public int compare(byte[] left, byte[] right) { 370 return compare(left, 0, left.length, right, 0, right.length); 371 } 372 @Override 373 public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) { 374 if (b1 == b2 && s1 == s2 && l1 == l2) { 375 return 0; 376 } 377 if (l1 == 0) { 378 return l2; //0 or positive 379 } 380 if (l2 == 0) { 381 return -1; 382 } 383 return super.compare(b1, s1, l1, b2, s2, l2); 384 } 385 } 386 387 /** 388 * Pass this to TreeMaps where byte [] are keys. 389 */ 390 public final static Comparator<byte []> BYTES_COMPARATOR = new ByteArrayComparator(); 391 392 /** 393 * Use comparing byte arrays, byte-by-byte 394 */ 395 public final static RawComparator<byte []> BYTES_RAWCOMPARATOR = new ByteArrayComparator(); 396 397 /** 398 * Read byte-array written with a WritableableUtils.vint prefix. 399 * @param in Input to read from. 400 * @return byte array read off <code>in</code> 401 * @throws IOException e 402 */ 403 public static byte [] readByteArray(final DataInput in) 404 throws IOException { 405 int len = WritableUtils.readVInt(in); 406 if (len < 0) { 407 throw new NegativeArraySizeException(Integer.toString(len)); 408 } 409 byte [] result = new byte[len]; 410 in.readFully(result, 0, len); 411 return result; 412 } 413 414 /** 415 * Read byte-array written with a WritableableUtils.vint prefix. 416 * IOException is converted to a RuntimeException. 417 * @param in Input to read from. 418 * @return byte array read off <code>in</code> 419 */ 420 public static byte [] readByteArrayThrowsRuntime(final DataInput in) { 421 try { 422 return readByteArray(in); 423 } catch (Exception e) { 424 throw new RuntimeException(e); 425 } 426 } 427 428 /** 429 * Write byte-array with a WritableableUtils.vint prefix. 430 * @param out output stream to be written to 431 * @param b array to write 432 * @throws IOException e 433 */ 434 public static void writeByteArray(final DataOutput out, final byte [] b) 435 throws IOException { 436 if(b == null) { 437 WritableUtils.writeVInt(out, 0); 438 } else { 439 writeByteArray(out, b, 0, b.length); 440 } 441 } 442 443 /** 444 * Write byte-array to out with a vint length prefix. 445 * @param out output stream 446 * @param b array 447 * @param offset offset into array 448 * @param length length past offset 449 * @throws IOException e 450 */ 451 public static void writeByteArray(final DataOutput out, final byte [] b, 452 final int offset, final int length) 453 throws IOException { 454 WritableUtils.writeVInt(out, length); 455 out.write(b, offset, length); 456 } 457 458 /** 459 * Write byte-array from src to tgt with a vint length prefix. 460 * @param tgt target array 461 * @param tgtOffset offset into target array 462 * @param src source array 463 * @param srcOffset source offset 464 * @param srcLength source length 465 * @return New offset in src array. 466 */ 467 public static int writeByteArray(final byte [] tgt, final int tgtOffset, 468 final byte [] src, final int srcOffset, final int srcLength) { 469 byte [] vint = vintToBytes(srcLength); 470 System.arraycopy(vint, 0, tgt, tgtOffset, vint.length); 471 int offset = tgtOffset + vint.length; 472 System.arraycopy(src, srcOffset, tgt, offset, srcLength); 473 return offset + srcLength; 474 } 475 476 /** 477 * Put bytes at the specified byte array position. 478 * @param tgtBytes the byte array 479 * @param tgtOffset position in the array 480 * @param srcBytes array to write out 481 * @param srcOffset source offset 482 * @param srcLength source length 483 * @return incremented offset 484 */ 485 public static int putBytes(byte[] tgtBytes, int tgtOffset, byte[] srcBytes, 486 int srcOffset, int srcLength) { 487 System.arraycopy(srcBytes, srcOffset, tgtBytes, tgtOffset, srcLength); 488 return tgtOffset + srcLength; 489 } 490 491 /** 492 * Write a single byte out to the specified byte array position. 493 * @param bytes the byte array 494 * @param offset position in the array 495 * @param b byte to write out 496 * @return incremented offset 497 */ 498 public static int putByte(byte[] bytes, int offset, byte b) { 499 bytes[offset] = b; 500 return offset + 1; 501 } 502 503 /** 504 * Add the whole content of the ByteBuffer to the bytes arrays. The ByteBuffer is modified. 505 * @param bytes the byte array 506 * @param offset position in the array 507 * @param buf ByteBuffer to write out 508 * @return incremented offset 509 */ 510 public static int putByteBuffer(byte[] bytes, int offset, ByteBuffer buf) { 511 int len = buf.remaining(); 512 buf.get(bytes, offset, len); 513 return offset + len; 514 } 515 516 /** 517 * Returns a new byte array, copied from the given {@code buf}, 518 * from the index 0 (inclusive) to the limit (exclusive), 519 * regardless of the current position. 520 * The position and the other index parameters are not changed. 521 * 522 * @param buf a byte buffer 523 * @return the byte array 524 * @see #getBytes(ByteBuffer) 525 */ 526 public static byte[] toBytes(ByteBuffer buf) { 527 ByteBuffer dup = buf.duplicate(); 528 dup.position(0); 529 return readBytes(dup); 530 } 531 532 private static byte[] readBytes(ByteBuffer buf) { 533 byte [] result = new byte[buf.remaining()]; 534 buf.get(result); 535 return result; 536 } 537 538 /** 539 * @param b Presumed UTF-8 encoded byte array. 540 * @return String made from <code>b</code> 541 */ 542 public static String toString(final byte [] b) { 543 if (b == null) { 544 return null; 545 } 546 return toString(b, 0, b.length); 547 } 548 549 /** 550 * Joins two byte arrays together using a separator. 551 * @param b1 The first byte array. 552 * @param sep The separator to use. 553 * @param b2 The second byte array. 554 */ 555 public static String toString(final byte [] b1, 556 String sep, 557 final byte [] b2) { 558 return toString(b1, 0, b1.length) + sep + toString(b2, 0, b2.length); 559 } 560 561 /** 562 * This method will convert utf8 encoded bytes into a string. If 563 * the given byte array is null, this method will return null. 564 * 565 * @param b Presumed UTF-8 encoded byte array. 566 * @param off offset into array 567 * @return String made from <code>b</code> or null 568 */ 569 public static String toString(final byte[] b, int off) { 570 if (b == null) { 571 return null; 572 } 573 int len = b.length - off; 574 if (len <= 0) { 575 return ""; 576 } 577 try { 578 return new String(b, off, len, UTF8_CSN); 579 } catch (UnsupportedEncodingException e) { 580 // should never happen! 581 throw new IllegalArgumentException("UTF8 encoding is not supported", e); 582 } 583 } 584 585 /** 586 * This method will convert utf8 encoded bytes into a string. If 587 * the given byte array is null, this method will return null. 588 * 589 * @param b Presumed UTF-8 encoded byte array. 590 * @param off offset into array 591 * @param len length of utf-8 sequence 592 * @return String made from <code>b</code> or null 593 */ 594 public static String toString(final byte[] b, int off, int len) { 595 if (b == null) { 596 return null; 597 } 598 if (len == 0) { 599 return ""; 600 } 601 try { 602 return new String(b, off, len, UTF8_CSN); 603 } catch (UnsupportedEncodingException e) { 604 // should never happen! 605 throw new IllegalArgumentException("UTF8 encoding is not supported", e); 606 } 607 } 608 609 /** 610 * Write a printable representation of a byte array. 611 * 612 * @param b byte array 613 * @return string 614 * @see #toStringBinary(byte[], int, int) 615 */ 616 public static String toStringBinary(final byte [] b) { 617 if (b == null) 618 return "null"; 619 return toStringBinary(b, 0, b.length); 620 } 621 622 /** 623 * Converts the given byte buffer to a printable representation, 624 * from the index 0 (inclusive) to the limit (exclusive), 625 * regardless of the current position. 626 * The position and the other index parameters are not changed. 627 * 628 * @param buf a byte buffer 629 * @return a string representation of the buffer's binary contents 630 * @see #toBytes(ByteBuffer) 631 * @see #getBytes(ByteBuffer) 632 */ 633 public static String toStringBinary(ByteBuffer buf) { 634 if (buf == null) 635 return "null"; 636 if (buf.hasArray()) { 637 return toStringBinary(buf.array(), buf.arrayOffset(), buf.limit()); 638 } 639 return toStringBinary(toBytes(buf)); 640 } 641 642 private static final char[] HEX_CHARS_UPPER = { 643 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' 644 }; 645 646 /** 647 * Write a printable representation of a byte array. Non-printable 648 * characters are hex escaped in the format \\x%02X, eg: 649 * \x00 \x05 etc 650 * 651 * @param b array to write out 652 * @param off offset to start at 653 * @param len length to write 654 * @return string output 655 */ 656 public static String toStringBinary(final byte [] b, int off, int len) { 657 StringBuilder result = new StringBuilder(); 658 // Just in case we are passed a 'len' that is > buffer length... 659 if (off >= b.length) return result.toString(); 660 if (off + len > b.length) len = b.length - off; 661 for (int i = off; i < off + len ; ++i) { 662 int ch = b[i] & 0xFF; 663 if (ch >= ' ' && ch <= '~' && ch != '\\') { 664 result.append((char)ch); 665 } else { 666 result.append("\\x"); 667 result.append(HEX_CHARS_UPPER[ch / 0x10]); 668 result.append(HEX_CHARS_UPPER[ch % 0x10]); 669 } 670 } 671 return result.toString(); 672 } 673 674 private static boolean isHexDigit(char c) { 675 return 676 (c >= 'A' && c <= 'F') || 677 (c >= '0' && c <= '9'); 678 } 679 680 /** 681 * Takes a ASCII digit in the range A-F0-9 and returns 682 * the corresponding integer/ordinal value. 683 * @param ch The hex digit. 684 * @return The converted hex value as a byte. 685 */ 686 public static byte toBinaryFromHex(byte ch) { 687 if (ch >= 'A' && ch <= 'F') 688 return (byte) ((byte)10 + (byte) (ch - 'A')); 689 // else 690 return (byte) (ch - '0'); 691 } 692 693 public static byte [] toBytesBinary(String in) { 694 // this may be bigger than we need, but let's be safe. 695 byte [] b = new byte[in.length()]; 696 int size = 0; 697 for (int i = 0; i < in.length(); ++i) { 698 char ch = in.charAt(i); 699 if (ch == '\\' && in.length() > i+1 && in.charAt(i+1) == 'x') { 700 // ok, take next 2 hex digits. 701 char hd1 = in.charAt(i+2); 702 char hd2 = in.charAt(i+3); 703 704 // they need to be A-F0-9: 705 if (!isHexDigit(hd1) || 706 !isHexDigit(hd2)) { 707 // bogus escape code, ignore: 708 continue; 709 } 710 // turn hex ASCII digit -> number 711 byte d = (byte) ((toBinaryFromHex((byte)hd1) << 4) + toBinaryFromHex((byte)hd2)); 712 713 b[size++] = d; 714 i += 3; // skip 3 715 } else { 716 b[size++] = (byte) ch; 717 } 718 } 719 // resize: 720 byte [] b2 = new byte[size]; 721 System.arraycopy(b, 0, b2, 0, size); 722 return b2; 723 } 724 725 /** 726 * Converts a string to a UTF-8 byte array. 727 * @param s string 728 * @return the byte array 729 */ 730 public static byte[] toBytes(String s) { 731 try { 732 return s.getBytes(UTF8_CSN); 733 } catch (UnsupportedEncodingException e) { 734 // should never happen! 735 throw new IllegalArgumentException("UTF8 decoding is not supported", e); 736 } 737 } 738 739 /** 740 * Convert a boolean to a byte array. True becomes -1 741 * and false becomes 0. 742 * 743 * @param b value 744 * @return <code>b</code> encoded in a byte array. 745 */ 746 public static byte [] toBytes(final boolean b) { 747 return new byte[] { b ? (byte) -1 : (byte) 0 }; 748 } 749 750 /** 751 * Reverses {@link #toBytes(boolean)} 752 * @param b array 753 * @return True or false. 754 */ 755 public static boolean toBoolean(final byte [] b) { 756 if (b.length != 1) { 757 throw new IllegalArgumentException("Array has wrong size: " + b.length); 758 } 759 return b[0] != (byte) 0; 760 } 761 762 /** 763 * Convert a long value to a byte array using big-endian. 764 * 765 * @param val value to convert 766 * @return the byte array 767 */ 768 public static byte[] toBytes(long val) { 769 byte [] b = new byte[8]; 770 for (int i = 7; i > 0; i--) { 771 b[i] = (byte) val; 772 val >>>= 8; 773 } 774 b[0] = (byte) val; 775 return b; 776 } 777 778 /** 779 * Converts a byte array to a long value. Reverses 780 * {@link #toBytes(long)} 781 * @param bytes array 782 * @return the long value 783 */ 784 public static long toLong(byte[] bytes) { 785 return toLong(bytes, 0, SIZEOF_LONG); 786 } 787 788 /** 789 * Converts a byte array to a long value. Assumes there will be 790 * {@link #SIZEOF_LONG} bytes available. 791 * 792 * @param bytes bytes 793 * @param offset offset 794 * @return the long value 795 */ 796 public static long toLong(byte[] bytes, int offset) { 797 return toLong(bytes, offset, SIZEOF_LONG); 798 } 799 800 /** 801 * Converts a byte array to a long value. 802 * 803 * @param bytes array of bytes 804 * @param offset offset into array 805 * @param length length of data (must be {@link #SIZEOF_LONG}) 806 * @return the long value 807 * @throws IllegalArgumentException if length is not {@link #SIZEOF_LONG} or 808 * if there's not enough room in the array at the offset indicated. 809 */ 810 public static long toLong(byte[] bytes, int offset, final int length) { 811 if (length != SIZEOF_LONG || offset + length > bytes.length) { 812 throw explainWrongLengthOrOffset(bytes, offset, length, SIZEOF_LONG); 813 } 814 if (UNSAFE_UNALIGNED) { 815 return UnsafeAccess.toLong(bytes, offset); 816 } else { 817 long l = 0; 818 for(int i = offset; i < offset + length; i++) { 819 l <<= 8; 820 l ^= bytes[i] & 0xFF; 821 } 822 return l; 823 } 824 } 825 826 private static IllegalArgumentException 827 explainWrongLengthOrOffset(final byte[] bytes, 828 final int offset, 829 final int length, 830 final int expectedLength) { 831 String reason; 832 if (length != expectedLength) { 833 reason = "Wrong length: " + length + ", expected " + expectedLength; 834 } else { 835 reason = "offset (" + offset + ") + length (" + length + ") exceed the" 836 + " capacity of the array: " + bytes.length; 837 } 838 return new IllegalArgumentException(reason); 839 } 840 841 /** 842 * Put a long value out to the specified byte array position. 843 * @param bytes the byte array 844 * @param offset position in the array 845 * @param val long to write out 846 * @return incremented offset 847 * @throws IllegalArgumentException if the byte array given doesn't have 848 * enough room at the offset specified. 849 */ 850 public static int putLong(byte[] bytes, int offset, long val) { 851 if (bytes.length - offset < SIZEOF_LONG) { 852 throw new IllegalArgumentException("Not enough room to put a long at" 853 + " offset " + offset + " in a " + bytes.length + " byte array"); 854 } 855 if (UNSAFE_UNALIGNED) { 856 return UnsafeAccess.putLong(bytes, offset, val); 857 } else { 858 for(int i = offset + 7; i > offset; i--) { 859 bytes[i] = (byte) val; 860 val >>>= 8; 861 } 862 bytes[offset] = (byte) val; 863 return offset + SIZEOF_LONG; 864 } 865 } 866 867 /** 868 * Put a long value out to the specified byte array position (Unsafe). 869 * @param bytes the byte array 870 * @param offset position in the array 871 * @param val long to write out 872 * @return incremented offset 873 * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0. 874 */ 875 @Deprecated 876 public static int putLongUnsafe(byte[] bytes, int offset, long val) { 877 return UnsafeAccess.putLong(bytes, offset, val); 878 } 879 880 /** 881 * Presumes float encoded as IEEE 754 floating-point "single format" 882 * @param bytes byte array 883 * @return Float made from passed byte array. 884 */ 885 public static float toFloat(byte [] bytes) { 886 return toFloat(bytes, 0); 887 } 888 889 /** 890 * Presumes float encoded as IEEE 754 floating-point "single format" 891 * @param bytes array to convert 892 * @param offset offset into array 893 * @return Float made from passed byte array. 894 */ 895 public static float toFloat(byte [] bytes, int offset) { 896 return Float.intBitsToFloat(toInt(bytes, offset, SIZEOF_INT)); 897 } 898 899 /** 900 * @param bytes byte array 901 * @param offset offset to write to 902 * @param f float value 903 * @return New offset in <code>bytes</code> 904 */ 905 public static int putFloat(byte [] bytes, int offset, float f) { 906 return putInt(bytes, offset, Float.floatToRawIntBits(f)); 907 } 908 909 /** 910 * @param f float value 911 * @return the float represented as byte [] 912 */ 913 public static byte [] toBytes(final float f) { 914 // Encode it as int 915 return Bytes.toBytes(Float.floatToRawIntBits(f)); 916 } 917 918 /** 919 * @param bytes byte array 920 * @return Return double made from passed bytes. 921 */ 922 public static double toDouble(final byte [] bytes) { 923 return toDouble(bytes, 0); 924 } 925 926 /** 927 * @param bytes byte array 928 * @param offset offset where double is 929 * @return Return double made from passed bytes. 930 */ 931 public static double toDouble(final byte [] bytes, final int offset) { 932 return Double.longBitsToDouble(toLong(bytes, offset, SIZEOF_LONG)); 933 } 934 935 /** 936 * @param bytes byte array 937 * @param offset offset to write to 938 * @param d value 939 * @return New offset into array <code>bytes</code> 940 */ 941 public static int putDouble(byte [] bytes, int offset, double d) { 942 return putLong(bytes, offset, Double.doubleToLongBits(d)); 943 } 944 945 /** 946 * Serialize a double as the IEEE 754 double format output. The resultant 947 * array will be 8 bytes long. 948 * 949 * @param d value 950 * @return the double represented as byte [] 951 */ 952 public static byte [] toBytes(final double d) { 953 // Encode it as a long 954 return Bytes.toBytes(Double.doubleToRawLongBits(d)); 955 } 956 957 /** 958 * Convert an int value to a byte array. Big-endian. Same as what DataOutputStream.writeInt 959 * does. 960 * 961 * @param val value 962 * @return the byte array 963 */ 964 public static byte[] toBytes(int val) { 965 byte [] b = new byte[4]; 966 for(int i = 3; i > 0; i--) { 967 b[i] = (byte) val; 968 val >>>= 8; 969 } 970 b[0] = (byte) val; 971 return b; 972 } 973 974 /** 975 * Converts a byte array to an int value 976 * @param bytes byte array 977 * @return the int value 978 */ 979 public static int toInt(byte[] bytes) { 980 return toInt(bytes, 0, SIZEOF_INT); 981 } 982 983 /** 984 * Converts a byte array to an int value 985 * @param bytes byte array 986 * @param offset offset into array 987 * @return the int value 988 */ 989 public static int toInt(byte[] bytes, int offset) { 990 return toInt(bytes, offset, SIZEOF_INT); 991 } 992 993 /** 994 * Converts a byte array to an int value 995 * @param bytes byte array 996 * @param offset offset into array 997 * @param length length of int (has to be {@link #SIZEOF_INT}) 998 * @return the int value 999 * @throws IllegalArgumentException if length is not {@link #SIZEOF_INT} or 1000 * if there's not enough room in the array at the offset indicated. 1001 */ 1002 public static int toInt(byte[] bytes, int offset, final int length) { 1003 if (length != SIZEOF_INT || offset + length > bytes.length) { 1004 throw explainWrongLengthOrOffset(bytes, offset, length, SIZEOF_INT); 1005 } 1006 if (UNSAFE_UNALIGNED) { 1007 return UnsafeAccess.toInt(bytes, offset); 1008 } else { 1009 int n = 0; 1010 for(int i = offset; i < (offset + length); i++) { 1011 n <<= 8; 1012 n ^= bytes[i] & 0xFF; 1013 } 1014 return n; 1015 } 1016 } 1017 1018 /** 1019 * Converts a byte array to an int value (Unsafe version) 1020 * @param bytes byte array 1021 * @param offset offset into array 1022 * @return the int value 1023 * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0. 1024 */ 1025 @Deprecated 1026 public static int toIntUnsafe(byte[] bytes, int offset) { 1027 return UnsafeAccess.toInt(bytes, offset); 1028 } 1029 1030 /** 1031 * Converts a byte array to an short value (Unsafe version) 1032 * @param bytes byte array 1033 * @param offset offset into array 1034 * @return the short value 1035 * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0. 1036 */ 1037 @Deprecated 1038 public static short toShortUnsafe(byte[] bytes, int offset) { 1039 return UnsafeAccess.toShort(bytes, offset); 1040 } 1041 1042 /** 1043 * Converts a byte array to an long value (Unsafe version) 1044 * @param bytes byte array 1045 * @param offset offset into array 1046 * @return the long value 1047 * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0. 1048 */ 1049 @Deprecated 1050 public static long toLongUnsafe(byte[] bytes, int offset) { 1051 return UnsafeAccess.toLong(bytes, offset); 1052 } 1053 1054 /** 1055 * Converts a byte array to an int value 1056 * @param bytes byte array 1057 * @param offset offset into array 1058 * @param length how many bytes should be considered for creating int 1059 * @return the int value 1060 * @throws IllegalArgumentException if there's not enough room in the array at the offset 1061 * indicated. 1062 */ 1063 public static int readAsInt(byte[] bytes, int offset, final int length) { 1064 if (offset + length > bytes.length) { 1065 throw new IllegalArgumentException("offset (" + offset + ") + length (" + length 1066 + ") exceed the" + " capacity of the array: " + bytes.length); 1067 } 1068 int n = 0; 1069 for(int i = offset; i < (offset + length); i++) { 1070 n <<= 8; 1071 n ^= bytes[i] & 0xFF; 1072 } 1073 return n; 1074 } 1075 1076 /** 1077 * Put an int value out to the specified byte array position. 1078 * @param bytes the byte array 1079 * @param offset position in the array 1080 * @param val int to write out 1081 * @return incremented offset 1082 * @throws IllegalArgumentException if the byte array given doesn't have 1083 * enough room at the offset specified. 1084 */ 1085 public static int putInt(byte[] bytes, int offset, int val) { 1086 if (bytes.length - offset < SIZEOF_INT) { 1087 throw new IllegalArgumentException("Not enough room to put an int at" 1088 + " offset " + offset + " in a " + bytes.length + " byte array"); 1089 } 1090 if (UNSAFE_UNALIGNED) { 1091 return UnsafeAccess.putInt(bytes, offset, val); 1092 } else { 1093 for(int i= offset + 3; i > offset; i--) { 1094 bytes[i] = (byte) val; 1095 val >>>= 8; 1096 } 1097 bytes[offset] = (byte) val; 1098 return offset + SIZEOF_INT; 1099 } 1100 } 1101 1102 /** 1103 * Put an int value out to the specified byte array position (Unsafe). 1104 * @param bytes the byte array 1105 * @param offset position in the array 1106 * @param val int to write out 1107 * @return incremented offset 1108 * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0. 1109 */ 1110 @Deprecated 1111 public static int putIntUnsafe(byte[] bytes, int offset, int val) { 1112 return UnsafeAccess.putInt(bytes, offset, val); 1113 } 1114 1115 /** 1116 * Convert a short value to a byte array of {@link #SIZEOF_SHORT} bytes long. 1117 * @param val value 1118 * @return the byte array 1119 */ 1120 public static byte[] toBytes(short val) { 1121 byte[] b = new byte[SIZEOF_SHORT]; 1122 b[1] = (byte) val; 1123 val >>= 8; 1124 b[0] = (byte) val; 1125 return b; 1126 } 1127 1128 /** 1129 * Converts a byte array to a short value 1130 * @param bytes byte array 1131 * @return the short value 1132 */ 1133 public static short toShort(byte[] bytes) { 1134 return toShort(bytes, 0, SIZEOF_SHORT); 1135 } 1136 1137 /** 1138 * Converts a byte array to a short value 1139 * @param bytes byte array 1140 * @param offset offset into array 1141 * @return the short value 1142 */ 1143 public static short toShort(byte[] bytes, int offset) { 1144 return toShort(bytes, offset, SIZEOF_SHORT); 1145 } 1146 1147 /** 1148 * Converts a byte array to a short value 1149 * @param bytes byte array 1150 * @param offset offset into array 1151 * @param length length, has to be {@link #SIZEOF_SHORT} 1152 * @return the short value 1153 * @throws IllegalArgumentException if length is not {@link #SIZEOF_SHORT} 1154 * or if there's not enough room in the array at the offset indicated. 1155 */ 1156 public static short toShort(byte[] bytes, int offset, final int length) { 1157 if (length != SIZEOF_SHORT || offset + length > bytes.length) { 1158 throw explainWrongLengthOrOffset(bytes, offset, length, SIZEOF_SHORT); 1159 } 1160 if (UNSAFE_UNALIGNED) { 1161 return UnsafeAccess.toShort(bytes, offset); 1162 } else { 1163 short n = 0; 1164 n = (short) ((n ^ bytes[offset]) & 0xFF); 1165 n = (short) (n << 8); 1166 n = (short) ((n ^ bytes[offset+1]) & 0xFF); 1167 return n; 1168 } 1169 } 1170 1171 /** 1172 * Returns a new byte array, copied from the given {@code buf}, 1173 * from the position (inclusive) to the limit (exclusive). 1174 * The position and the other index parameters are not changed. 1175 * 1176 * @param buf a byte buffer 1177 * @return the byte array 1178 * @see #toBytes(ByteBuffer) 1179 */ 1180 public static byte[] getBytes(ByteBuffer buf) { 1181 return readBytes(buf.duplicate()); 1182 } 1183 1184 /** 1185 * Put a short value out to the specified byte array position. 1186 * @param bytes the byte array 1187 * @param offset position in the array 1188 * @param val short to write out 1189 * @return incremented offset 1190 * @throws IllegalArgumentException if the byte array given doesn't have 1191 * enough room at the offset specified. 1192 */ 1193 public static int putShort(byte[] bytes, int offset, short val) { 1194 if (bytes.length - offset < SIZEOF_SHORT) { 1195 throw new IllegalArgumentException("Not enough room to put a short at" 1196 + " offset " + offset + " in a " + bytes.length + " byte array"); 1197 } 1198 if (UNSAFE_UNALIGNED) { 1199 return UnsafeAccess.putShort(bytes, offset, val); 1200 } else { 1201 bytes[offset+1] = (byte) val; 1202 val >>= 8; 1203 bytes[offset] = (byte) val; 1204 return offset + SIZEOF_SHORT; 1205 } 1206 } 1207 1208 /** 1209 * Put a short value out to the specified byte array position (Unsafe). 1210 * @param bytes the byte array 1211 * @param offset position in the array 1212 * @param val short to write out 1213 * @return incremented offset 1214 * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0. 1215 */ 1216 @Deprecated 1217 public static int putShortUnsafe(byte[] bytes, int offset, short val) { 1218 return UnsafeAccess.putShort(bytes, offset, val); 1219 } 1220 1221 /** 1222 * Put an int value as short out to the specified byte array position. Only the lower 2 bytes of 1223 * the short will be put into the array. The caller of the API need to make sure they will not 1224 * loose the value by doing so. This is useful to store an unsigned short which is represented as 1225 * int in other parts. 1226 * @param bytes the byte array 1227 * @param offset position in the array 1228 * @param val value to write out 1229 * @return incremented offset 1230 * @throws IllegalArgumentException if the byte array given doesn't have 1231 * enough room at the offset specified. 1232 */ 1233 public static int putAsShort(byte[] bytes, int offset, int val) { 1234 if (bytes.length - offset < SIZEOF_SHORT) { 1235 throw new IllegalArgumentException("Not enough room to put a short at" 1236 + " offset " + offset + " in a " + bytes.length + " byte array"); 1237 } 1238 bytes[offset+1] = (byte) val; 1239 val >>= 8; 1240 bytes[offset] = (byte) val; 1241 return offset + SIZEOF_SHORT; 1242 } 1243 1244 /** 1245 * Convert a BigDecimal value to a byte array 1246 * 1247 * @param val 1248 * @return the byte array 1249 */ 1250 public static byte[] toBytes(BigDecimal val) { 1251 byte[] valueBytes = val.unscaledValue().toByteArray(); 1252 byte[] result = new byte[valueBytes.length + SIZEOF_INT]; 1253 int offset = putInt(result, 0, val.scale()); 1254 putBytes(result, offset, valueBytes, 0, valueBytes.length); 1255 return result; 1256 } 1257 1258 1259 /** 1260 * Converts a byte array to a BigDecimal 1261 * 1262 * @param bytes 1263 * @return the char value 1264 */ 1265 public static BigDecimal toBigDecimal(byte[] bytes) { 1266 return toBigDecimal(bytes, 0, bytes.length); 1267 } 1268 1269 /** 1270 * Converts a byte array to a BigDecimal value 1271 * 1272 * @param bytes 1273 * @param offset 1274 * @param length 1275 * @return the char value 1276 */ 1277 public static BigDecimal toBigDecimal(byte[] bytes, int offset, final int length) { 1278 if (bytes == null || length < SIZEOF_INT + 1 || 1279 (offset + length > bytes.length)) { 1280 return null; 1281 } 1282 1283 int scale = toInt(bytes, offset); 1284 byte[] tcBytes = new byte[length - SIZEOF_INT]; 1285 System.arraycopy(bytes, offset + SIZEOF_INT, tcBytes, 0, length - SIZEOF_INT); 1286 return new BigDecimal(new BigInteger(tcBytes), scale); 1287 } 1288 1289 /** 1290 * Put a BigDecimal value out to the specified byte array position. 1291 * 1292 * @param bytes the byte array 1293 * @param offset position in the array 1294 * @param val BigDecimal to write out 1295 * @return incremented offset 1296 */ 1297 public static int putBigDecimal(byte[] bytes, int offset, BigDecimal val) { 1298 if (bytes == null) { 1299 return offset; 1300 } 1301 1302 byte[] valueBytes = val.unscaledValue().toByteArray(); 1303 byte[] result = new byte[valueBytes.length + SIZEOF_INT]; 1304 offset = putInt(result, offset, val.scale()); 1305 return putBytes(result, offset, valueBytes, 0, valueBytes.length); 1306 } 1307 1308 /** 1309 * @param vint Integer to make a vint of. 1310 * @return Vint as bytes array. 1311 */ 1312 public static byte [] vintToBytes(final long vint) { 1313 long i = vint; 1314 int size = WritableUtils.getVIntSize(i); 1315 byte [] result = new byte[size]; 1316 int offset = 0; 1317 if (i >= -112 && i <= 127) { 1318 result[offset] = (byte) i; 1319 return result; 1320 } 1321 1322 int len = -112; 1323 if (i < 0) { 1324 i ^= -1L; // take one's complement' 1325 len = -120; 1326 } 1327 1328 long tmp = i; 1329 while (tmp != 0) { 1330 tmp = tmp >> 8; 1331 len--; 1332 } 1333 1334 result[offset++] = (byte) len; 1335 1336 len = (len < -120) ? -(len + 120) : -(len + 112); 1337 1338 for (int idx = len; idx != 0; idx--) { 1339 int shiftbits = (idx - 1) * 8; 1340 long mask = 0xFFL << shiftbits; 1341 result[offset++] = (byte)((i & mask) >> shiftbits); 1342 } 1343 return result; 1344 } 1345 1346 /** 1347 * @param buffer buffer to convert 1348 * @return vint bytes as an integer. 1349 */ 1350 public static long bytesToVint(final byte [] buffer) { 1351 int offset = 0; 1352 byte firstByte = buffer[offset++]; 1353 int len = WritableUtils.decodeVIntSize(firstByte); 1354 if (len == 1) { 1355 return firstByte; 1356 } 1357 long i = 0; 1358 for (int idx = 0; idx < len-1; idx++) { 1359 byte b = buffer[offset++]; 1360 i = i << 8; 1361 i = i | (b & 0xFF); 1362 } 1363 return (WritableUtils.isNegativeVInt(firstByte) ? ~i : i); 1364 } 1365 1366 /** 1367 * Reads a zero-compressed encoded long from input buffer and returns it. 1368 * @param buffer Binary array 1369 * @param offset Offset into array at which vint begins. 1370 * @throws java.io.IOException e 1371 * @return deserialized long from buffer. 1372 * @deprecated Use {@link #readAsVLong(byte[],int)} instead. 1373 */ 1374 @Deprecated 1375 public static long readVLong(final byte [] buffer, final int offset) 1376 throws IOException { 1377 return readAsVLong(buffer, offset); 1378 } 1379 1380 /** 1381 * Reads a zero-compressed encoded long from input buffer and returns it. 1382 * @param buffer Binary array 1383 * @param offset Offset into array at which vint begins. 1384 * @return deserialized long from buffer. 1385 */ 1386 public static long readAsVLong(final byte [] buffer, final int offset) { 1387 byte firstByte = buffer[offset]; 1388 int len = WritableUtils.decodeVIntSize(firstByte); 1389 if (len == 1) { 1390 return firstByte; 1391 } 1392 long i = 0; 1393 for (int idx = 0; idx < len-1; idx++) { 1394 byte b = buffer[offset + 1 + idx]; 1395 i = i << 8; 1396 i = i | (b & 0xFF); 1397 } 1398 return (WritableUtils.isNegativeVInt(firstByte) ? ~i : i); 1399 } 1400 1401 /** 1402 * @param left left operand 1403 * @param right right operand 1404 * @return 0 if equal, < 0 if left is less than right, etc. 1405 */ 1406 public static int compareTo(final byte [] left, final byte [] right) { 1407 return LexicographicalComparerHolder.BEST_COMPARER. 1408 compareTo(left, 0, left.length, right, 0, right.length); 1409 } 1410 1411 /** 1412 * Lexicographically compare two arrays. 1413 * 1414 * @param buffer1 left operand 1415 * @param buffer2 right operand 1416 * @param offset1 Where to start comparing in the left buffer 1417 * @param offset2 Where to start comparing in the right buffer 1418 * @param length1 How much to compare from the left buffer 1419 * @param length2 How much to compare from the right buffer 1420 * @return 0 if equal, < 0 if left is less than right, etc. 1421 */ 1422 public static int compareTo(byte[] buffer1, int offset1, int length1, 1423 byte[] buffer2, int offset2, int length2) { 1424 return LexicographicalComparerHolder.BEST_COMPARER. 1425 compareTo(buffer1, offset1, length1, buffer2, offset2, length2); 1426 } 1427 1428 interface Comparer<T> { 1429 int compareTo( 1430 T buffer1, int offset1, int length1, T buffer2, int offset2, int length2 1431 ); 1432 } 1433 1434 @VisibleForTesting 1435 static Comparer<byte[]> lexicographicalComparerJavaImpl() { 1436 return LexicographicalComparerHolder.PureJavaComparer.INSTANCE; 1437 } 1438 1439 /** 1440 * Provides a lexicographical comparer implementation; either a Java 1441 * implementation or a faster implementation based on {@link Unsafe}. 1442 * 1443 * <p>Uses reflection to gracefully fall back to the Java implementation if 1444 * {@code Unsafe} isn't available. 1445 */ 1446 @VisibleForTesting 1447 static class LexicographicalComparerHolder { 1448 static final String UNSAFE_COMPARER_NAME = 1449 LexicographicalComparerHolder.class.getName() + "$UnsafeComparer"; 1450 1451 static final Comparer<byte[]> BEST_COMPARER = getBestComparer(); 1452 /** 1453 * Returns the Unsafe-using Comparer, or falls back to the pure-Java 1454 * implementation if unable to do so. 1455 */ 1456 static Comparer<byte[]> getBestComparer() { 1457 try { 1458 Class<?> theClass = Class.forName(UNSAFE_COMPARER_NAME); 1459 1460 // yes, UnsafeComparer does implement Comparer<byte[]> 1461 @SuppressWarnings("unchecked") 1462 Comparer<byte[]> comparer = 1463 (Comparer<byte[]>) theClass.getEnumConstants()[0]; 1464 return comparer; 1465 } catch (Throwable t) { // ensure we really catch *everything* 1466 return lexicographicalComparerJavaImpl(); 1467 } 1468 } 1469 1470 enum PureJavaComparer implements Comparer<byte[]> { 1471 INSTANCE; 1472 1473 @Override 1474 public int compareTo(byte[] buffer1, int offset1, int length1, 1475 byte[] buffer2, int offset2, int length2) { 1476 // Short circuit equal case 1477 if (buffer1 == buffer2 && 1478 offset1 == offset2 && 1479 length1 == length2) { 1480 return 0; 1481 } 1482 // Bring WritableComparator code local 1483 int end1 = offset1 + length1; 1484 int end2 = offset2 + length2; 1485 for (int i = offset1, j = offset2; i < end1 && j < end2; i++, j++) { 1486 int a = (buffer1[i] & 0xff); 1487 int b = (buffer2[j] & 0xff); 1488 if (a != b) { 1489 return a - b; 1490 } 1491 } 1492 return length1 - length2; 1493 } 1494 } 1495 1496 @VisibleForTesting 1497 enum UnsafeComparer implements Comparer<byte[]> { 1498 INSTANCE; 1499 1500 static final Unsafe theUnsafe; 1501 static { 1502 if (UNSAFE_UNALIGNED) { 1503 theUnsafe = UnsafeAccess.theUnsafe; 1504 } else { 1505 // It doesn't matter what we throw; 1506 // it's swallowed in getBestComparer(). 1507 throw new Error(); 1508 } 1509 1510 // sanity check - this should never fail 1511 if (theUnsafe.arrayIndexScale(byte[].class) != 1) { 1512 throw new AssertionError(); 1513 } 1514 } 1515 1516 /** 1517 * Lexicographically compare two arrays. 1518 * 1519 * @param buffer1 left operand 1520 * @param buffer2 right operand 1521 * @param offset1 Where to start comparing in the left buffer 1522 * @param offset2 Where to start comparing in the right buffer 1523 * @param length1 How much to compare from the left buffer 1524 * @param length2 How much to compare from the right buffer 1525 * @return 0 if equal, < 0 if left is less than right, etc. 1526 */ 1527 @Override 1528 public int compareTo(byte[] buffer1, int offset1, int length1, 1529 byte[] buffer2, int offset2, int length2) { 1530 1531 // Short circuit equal case 1532 if (buffer1 == buffer2 && 1533 offset1 == offset2 && 1534 length1 == length2) { 1535 return 0; 1536 } 1537 final int stride = 8; 1538 final int minLength = Math.min(length1, length2); 1539 int strideLimit = minLength & ~(stride - 1); 1540 final long offset1Adj = offset1 + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET; 1541 final long offset2Adj = offset2 + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET; 1542 int i; 1543 1544 /* 1545 * Compare 8 bytes at a time. Benchmarking on x86 shows a stride of 8 bytes is no slower 1546 * than 4 bytes even on 32-bit. On the other hand, it is substantially faster on 64-bit. 1547 */ 1548 for (i = 0; i < strideLimit; i += stride) { 1549 long lw = theUnsafe.getLong(buffer1, offset1Adj + i); 1550 long rw = theUnsafe.getLong(buffer2, offset2Adj + i); 1551 if (lw != rw) { 1552 if(!UnsafeAccess.littleEndian) { 1553 return ((lw + Long.MIN_VALUE) < (rw + Long.MIN_VALUE)) ? -1 : 1; 1554 } 1555 1556 /* 1557 * We want to compare only the first index where left[index] != right[index]. This 1558 * corresponds to the least significant nonzero byte in lw ^ rw, since lw and rw are 1559 * little-endian. Long.numberOfTrailingZeros(diff) tells us the least significant 1560 * nonzero bit, and zeroing out the first three bits of L.nTZ gives us the shift to get 1561 * that least significant nonzero byte. This comparison logic is based on UnsignedBytes 1562 * comparator from guava v21 1563 */ 1564 int n = Long.numberOfTrailingZeros(lw ^ rw) & ~0x7; 1565 return ((int) ((lw >>> n) & 0xFF)) - ((int) ((rw >>> n) & 0xFF)); 1566 } 1567 } 1568 1569 // The epilogue to cover the last (minLength % stride) elements. 1570 for (; i < minLength; i++) { 1571 int a = (buffer1[offset1 + i] & 0xFF); 1572 int b = (buffer2[offset2 + i] & 0xFF); 1573 if (a != b) { 1574 return a - b; 1575 } 1576 } 1577 return length1 - length2; 1578 } 1579 } 1580 } 1581 1582 /** 1583 * @param left left operand 1584 * @param right right operand 1585 * @return True if equal 1586 */ 1587 public static boolean equals(final byte [] left, final byte [] right) { 1588 // Could use Arrays.equals? 1589 //noinspection SimplifiableConditionalExpression 1590 if (left == right) return true; 1591 if (left == null || right == null) return false; 1592 if (left.length != right.length) return false; 1593 if (left.length == 0) return true; 1594 1595 // Since we're often comparing adjacent sorted data, 1596 // it's usual to have equal arrays except for the very last byte 1597 // so check that first 1598 if (left[left.length - 1] != right[right.length - 1]) return false; 1599 1600 return compareTo(left, right) == 0; 1601 } 1602 1603 public static boolean equals(final byte[] left, int leftOffset, int leftLen, 1604 final byte[] right, int rightOffset, int rightLen) { 1605 // short circuit case 1606 if (left == right && 1607 leftOffset == rightOffset && 1608 leftLen == rightLen) { 1609 return true; 1610 } 1611 // different lengths fast check 1612 if (leftLen != rightLen) { 1613 return false; 1614 } 1615 if (leftLen == 0) { 1616 return true; 1617 } 1618 1619 // Since we're often comparing adjacent sorted data, 1620 // it's usual to have equal arrays except for the very last byte 1621 // so check that first 1622 if (left[leftOffset + leftLen - 1] != right[rightOffset + rightLen - 1]) return false; 1623 1624 return LexicographicalComparerHolder.BEST_COMPARER. 1625 compareTo(left, leftOffset, leftLen, right, rightOffset, rightLen) == 0; 1626 } 1627 1628 1629 /** 1630 * @param a left operand 1631 * @param buf right operand 1632 * @return True if equal 1633 */ 1634 public static boolean equals(byte[] a, ByteBuffer buf) { 1635 if (a == null) return buf == null; 1636 if (buf == null) return false; 1637 if (a.length != buf.remaining()) return false; 1638 1639 // Thou shalt not modify the original byte buffer in what should be read only operations. 1640 ByteBuffer b = buf.duplicate(); 1641 for (byte anA : a) { 1642 if (anA != b.get()) { 1643 return false; 1644 } 1645 } 1646 return true; 1647 } 1648 1649 1650 /** 1651 * Return true if the byte array on the right is a prefix of the byte 1652 * array on the left. 1653 */ 1654 public static boolean startsWith(byte[] bytes, byte[] prefix) { 1655 return bytes != null && prefix != null && 1656 bytes.length >= prefix.length && 1657 LexicographicalComparerHolder.BEST_COMPARER. 1658 compareTo(bytes, 0, prefix.length, prefix, 0, prefix.length) == 0; 1659 } 1660 1661 /** 1662 * @param b bytes to hash 1663 * @return Runs {@link WritableComparator#hashBytes(byte[], int)} on the 1664 * passed in array. This method is what {@link org.apache.hadoop.io.Text} 1665 * use calculating hash code. 1666 */ 1667 public static int hashCode(final byte [] b) { 1668 return hashCode(b, b.length); 1669 } 1670 1671 /** 1672 * @param b value 1673 * @param length length of the value 1674 * @return Runs {@link WritableComparator#hashBytes(byte[], int)} on the 1675 * passed in array. This method is what {@link org.apache.hadoop.io.Text} 1676 * use calculating hash code. 1677 */ 1678 public static int hashCode(final byte [] b, final int length) { 1679 return WritableComparator.hashBytes(b, length); 1680 } 1681 1682 /** 1683 * @param b bytes to hash 1684 * @return A hash of <code>b</code> as an Integer that can be used as key in 1685 * Maps. 1686 */ 1687 public static Integer mapKey(final byte [] b) { 1688 return hashCode(b); 1689 } 1690 1691 /** 1692 * @param b bytes to hash 1693 * @param length length to hash 1694 * @return A hash of <code>b</code> as an Integer that can be used as key in 1695 * Maps. 1696 */ 1697 public static Integer mapKey(final byte [] b, final int length) { 1698 return hashCode(b, length); 1699 } 1700 1701 /** 1702 * @param a lower half 1703 * @param b upper half 1704 * @return New array that has a in lower half and b in upper half. 1705 */ 1706 public static byte [] add(final byte [] a, final byte [] b) { 1707 return add(a, b, EMPTY_BYTE_ARRAY); 1708 } 1709 1710 /** 1711 * @param a first third 1712 * @param b second third 1713 * @param c third third 1714 * @return New array made from a, b and c 1715 */ 1716 public static byte [] add(final byte [] a, final byte [] b, final byte [] c) { 1717 byte [] result = new byte[a.length + b.length + c.length]; 1718 System.arraycopy(a, 0, result, 0, a.length); 1719 System.arraycopy(b, 0, result, a.length, b.length); 1720 System.arraycopy(c, 0, result, a.length + b.length, c.length); 1721 return result; 1722 } 1723 1724 /** 1725 * @param arrays all the arrays to concatenate together. 1726 * @return New array made from the concatenation of the given arrays. 1727 */ 1728 public static byte [] add(final byte [][] arrays) { 1729 int length = 0; 1730 for (int i = 0; i < arrays.length; i++) { 1731 length += arrays[i].length; 1732 } 1733 byte [] result = new byte[length]; 1734 int index = 0; 1735 for (int i = 0; i < arrays.length; i++) { 1736 System.arraycopy(arrays[i], 0, result, index, arrays[i].length); 1737 index += arrays[i].length; 1738 } 1739 return result; 1740 } 1741 1742 /** 1743 * @param a array 1744 * @param length amount of bytes to grab 1745 * @return First <code>length</code> bytes from <code>a</code> 1746 */ 1747 public static byte [] head(final byte [] a, final int length) { 1748 if (a.length < length) { 1749 return null; 1750 } 1751 byte [] result = new byte[length]; 1752 System.arraycopy(a, 0, result, 0, length); 1753 return result; 1754 } 1755 1756 /** 1757 * @param a array 1758 * @param length amount of bytes to snarf 1759 * @return Last <code>length</code> bytes from <code>a</code> 1760 */ 1761 public static byte [] tail(final byte [] a, final int length) { 1762 if (a.length < length) { 1763 return null; 1764 } 1765 byte [] result = new byte[length]; 1766 System.arraycopy(a, a.length - length, result, 0, length); 1767 return result; 1768 } 1769 1770 /** 1771 * @param a array 1772 * @param length new array size 1773 * @return Value in <code>a</code> plus <code>length</code> prepended 0 bytes 1774 */ 1775 public static byte [] padHead(final byte [] a, final int length) { 1776 byte [] padding = new byte[length]; 1777 for (int i = 0; i < length; i++) { 1778 padding[i] = 0; 1779 } 1780 return add(padding,a); 1781 } 1782 1783 /** 1784 * @param a array 1785 * @param length new array size 1786 * @return Value in <code>a</code> plus <code>length</code> appended 0 bytes 1787 */ 1788 public static byte [] padTail(final byte [] a, final int length) { 1789 byte [] padding = new byte[length]; 1790 for (int i = 0; i < length; i++) { 1791 padding[i] = 0; 1792 } 1793 return add(a,padding); 1794 } 1795 1796 /** 1797 * Split passed range. Expensive operation relatively. Uses BigInteger math. 1798 * Useful splitting ranges for MapReduce jobs. 1799 * @param a Beginning of range 1800 * @param b End of range 1801 * @param num Number of times to split range. Pass 1 if you want to split 1802 * the range in two; i.e. one split. 1803 * @return Array of dividing values 1804 */ 1805 public static byte [][] split(final byte [] a, final byte [] b, final int num) { 1806 return split(a, b, false, num); 1807 } 1808 1809 /** 1810 * Split passed range. Expensive operation relatively. Uses BigInteger math. 1811 * Useful splitting ranges for MapReduce jobs. 1812 * @param a Beginning of range 1813 * @param b End of range 1814 * @param inclusive Whether the end of range is prefix-inclusive or is 1815 * considered an exclusive boundary. Automatic splits are generally exclusive 1816 * and manual splits with an explicit range utilize an inclusive end of range. 1817 * @param num Number of times to split range. Pass 1 if you want to split 1818 * the range in two; i.e. one split. 1819 * @return Array of dividing values 1820 */ 1821 public static byte[][] split(final byte[] a, final byte[] b, 1822 boolean inclusive, final int num) { 1823 byte[][] ret = new byte[num + 2][]; 1824 int i = 0; 1825 Iterable<byte[]> iter = iterateOnSplits(a, b, inclusive, num); 1826 if (iter == null) 1827 return null; 1828 for (byte[] elem : iter) { 1829 ret[i++] = elem; 1830 } 1831 return ret; 1832 } 1833 1834 /** 1835 * Iterate over keys within the passed range, splitting at an [a,b) boundary. 1836 */ 1837 public static Iterable<byte[]> iterateOnSplits(final byte[] a, 1838 final byte[] b, final int num) 1839 { 1840 return iterateOnSplits(a, b, false, num); 1841 } 1842 1843 /** 1844 * Iterate over keys within the passed range. 1845 */ 1846 public static Iterable<byte[]> iterateOnSplits( 1847 final byte[] a, final byte[]b, boolean inclusive, final int num) 1848 { 1849 byte [] aPadded; 1850 byte [] bPadded; 1851 if (a.length < b.length) { 1852 aPadded = padTail(a, b.length - a.length); 1853 bPadded = b; 1854 } else if (b.length < a.length) { 1855 aPadded = a; 1856 bPadded = padTail(b, a.length - b.length); 1857 } else { 1858 aPadded = a; 1859 bPadded = b; 1860 } 1861 if (compareTo(aPadded,bPadded) >= 0) { 1862 throw new IllegalArgumentException("b <= a"); 1863 } 1864 if (num <= 0) { 1865 throw new IllegalArgumentException("num cannot be <= 0"); 1866 } 1867 byte [] prependHeader = {1, 0}; 1868 final BigInteger startBI = new BigInteger(add(prependHeader, aPadded)); 1869 final BigInteger stopBI = new BigInteger(add(prependHeader, bPadded)); 1870 BigInteger diffBI = stopBI.subtract(startBI); 1871 if (inclusive) { 1872 diffBI = diffBI.add(BigInteger.ONE); 1873 } 1874 final BigInteger splitsBI = BigInteger.valueOf(num + 1); 1875 //when diffBI < splitBI, use an additional byte to increase diffBI 1876 if(diffBI.compareTo(splitsBI) < 0) { 1877 byte[] aPaddedAdditional = new byte[aPadded.length+1]; 1878 byte[] bPaddedAdditional = new byte[bPadded.length+1]; 1879 for (int i = 0; i < aPadded.length; i++){ 1880 aPaddedAdditional[i] = aPadded[i]; 1881 } 1882 for (int j = 0; j < bPadded.length; j++){ 1883 bPaddedAdditional[j] = bPadded[j]; 1884 } 1885 aPaddedAdditional[aPadded.length] = 0; 1886 bPaddedAdditional[bPadded.length] = 0; 1887 return iterateOnSplits(aPaddedAdditional, bPaddedAdditional, inclusive, num); 1888 } 1889 final BigInteger intervalBI; 1890 try { 1891 intervalBI = diffBI.divide(splitsBI); 1892 } catch(Exception e) { 1893 LOG.error("Exception caught during division", e); 1894 return null; 1895 } 1896 1897 final Iterator<byte[]> iterator = new Iterator<byte[]>() { 1898 private int i = -1; 1899 1900 @Override 1901 public boolean hasNext() { 1902 return i < num+1; 1903 } 1904 1905 @Override 1906 public byte[] next() { 1907 i++; 1908 if (i == 0) return a; 1909 if (i == num + 1) return b; 1910 1911 BigInteger curBI = startBI.add(intervalBI.multiply(BigInteger.valueOf(i))); 1912 byte [] padded = curBI.toByteArray(); 1913 if (padded[1] == 0) 1914 padded = tail(padded, padded.length - 2); 1915 else 1916 padded = tail(padded, padded.length - 1); 1917 return padded; 1918 } 1919 1920 @Override 1921 public void remove() { 1922 throw new UnsupportedOperationException(); 1923 } 1924 1925 }; 1926 1927 return new Iterable<byte[]>() { 1928 @Override 1929 public Iterator<byte[]> iterator() { 1930 return iterator; 1931 } 1932 }; 1933 } 1934 1935 /** 1936 * @param bytes array to hash 1937 * @param offset offset to start from 1938 * @param length length to hash 1939 * */ 1940 public static int hashCode(byte[] bytes, int offset, int length) { 1941 int hash = 1; 1942 for (int i = offset; i < offset + length; i++) 1943 hash = (31 * hash) + bytes[i]; 1944 return hash; 1945 } 1946 1947 /** 1948 * @param t operands 1949 * @return Array of byte arrays made from passed array of Text 1950 */ 1951 public static byte [][] toByteArrays(final String [] t) { 1952 byte [][] result = new byte[t.length][]; 1953 for (int i = 0; i < t.length; i++) { 1954 result[i] = Bytes.toBytes(t[i]); 1955 } 1956 return result; 1957 } 1958 1959 /** 1960 * @param t operands 1961 * @return Array of binary byte arrays made from passed array of binary strings 1962 */ 1963 public static byte[][] toBinaryByteArrays(final String[] t) { 1964 byte[][] result = new byte[t.length][]; 1965 for (int i = 0; i < t.length; i++) { 1966 result[i] = Bytes.toBytesBinary(t[i]); 1967 } 1968 return result; 1969 } 1970 1971 /** 1972 * @param column operand 1973 * @return A byte array of a byte array where first and only entry is 1974 * <code>column</code> 1975 */ 1976 public static byte [][] toByteArrays(final String column) { 1977 return toByteArrays(toBytes(column)); 1978 } 1979 1980 /** 1981 * @param column operand 1982 * @return A byte array of a byte array where first and only entry is 1983 * <code>column</code> 1984 */ 1985 public static byte [][] toByteArrays(final byte [] column) { 1986 byte [][] result = new byte[1][]; 1987 result[0] = column; 1988 return result; 1989 } 1990 1991 /** 1992 * Binary search for keys in indexes. 1993 * 1994 * @param arr array of byte arrays to search for 1995 * @param key the key you want to find 1996 * @param offset the offset in the key you want to find 1997 * @param length the length of the key 1998 * @param comparator a comparator to compare. 1999 * @return zero-based index of the key, if the key is present in the array. 2000 * Otherwise, a value -(i + 1) such that the key is between arr[i - 2001 * 1] and arr[i] non-inclusively, where i is in [0, i], if we define 2002 * arr[-1] = -Inf and arr[N] = Inf for an N-element array. The above 2003 * means that this function can return 2N + 1 different values 2004 * ranging from -(N + 1) to N - 1. 2005 * @deprecated {@link Bytes#binarySearch(byte[][], byte[], int, int)} 2006 */ 2007 @Deprecated 2008 public static int binarySearch(byte [][]arr, byte []key, int offset, 2009 int length, RawComparator<?> comparator) { 2010 return binarySearch(arr, key, offset, length); 2011 } 2012 2013 /** 2014 * Binary search for keys in indexes using Bytes.BYTES_RAWCOMPARATOR. 2015 * 2016 * @param arr array of byte arrays to search for 2017 * @param key the key you want to find 2018 * @param offset the offset in the key you want to find 2019 * @param length the length of the key 2020 * @return zero-based index of the key, if the key is present in the array. 2021 * Otherwise, a value -(i + 1) such that the key is between arr[i - 2022 * 1] and arr[i] non-inclusively, where i is in [0, i], if we define 2023 * arr[-1] = -Inf and arr[N] = Inf for an N-element array. The above 2024 * means that this function can return 2N + 1 different values 2025 * ranging from -(N + 1) to N - 1. 2026 */ 2027 public static int binarySearch(byte[][] arr, byte[] key, int offset, int length) { 2028 int low = 0; 2029 int high = arr.length - 1; 2030 2031 while (low <= high) { 2032 int mid = (low + high) >>> 1; 2033 // we have to compare in this order, because the comparator order 2034 // has special logic when the 'left side' is a special key. 2035 int cmp = Bytes.BYTES_RAWCOMPARATOR 2036 .compare(key, offset, length, arr[mid], 0, arr[mid].length); 2037 // key lives above the midpoint 2038 if (cmp > 0) 2039 low = mid + 1; 2040 // key lives below the midpoint 2041 else if (cmp < 0) 2042 high = mid - 1; 2043 // BAM. how often does this really happen? 2044 else 2045 return mid; 2046 } 2047 return -(low + 1); 2048 } 2049 2050 /** 2051 * Binary search for keys in indexes. 2052 * 2053 * @param arr array of byte arrays to search for 2054 * @param key the key you want to find 2055 * @param comparator a comparator to compare. 2056 * @return zero-based index of the key, if the key is present in the array. 2057 * Otherwise, a value -(i + 1) such that the key is between arr[i - 2058 * 1] and arr[i] non-inclusively, where i is in [0, i], if we define 2059 * arr[-1] = -Inf and arr[N] = Inf for an N-element array. The above 2060 * means that this function can return 2N + 1 different values 2061 * ranging from -(N + 1) to N - 1. 2062 * @return the index of the block 2063 * @deprecated Use {@link Bytes#binarySearch(Cell[], Cell, CellComparator)} 2064 */ 2065 @Deprecated 2066 public static int binarySearch(byte[][] arr, Cell key, RawComparator<Cell> comparator) { 2067 int low = 0; 2068 int high = arr.length - 1; 2069 KeyValue.KeyOnlyKeyValue r = new KeyValue.KeyOnlyKeyValue(); 2070 while (low <= high) { 2071 int mid = (low+high) >>> 1; 2072 // we have to compare in this order, because the comparator order 2073 // has special logic when the 'left side' is a special key. 2074 r.setKey(arr[mid], 0, arr[mid].length); 2075 int cmp = comparator.compare(key, r); 2076 // key lives above the midpoint 2077 if (cmp > 0) 2078 low = mid + 1; 2079 // key lives below the midpoint 2080 else if (cmp < 0) 2081 high = mid - 1; 2082 // BAM. how often does this really happen? 2083 else 2084 return mid; 2085 } 2086 return - (low+1); 2087 } 2088 2089 /** 2090 * Binary search for keys in indexes. 2091 * 2092 * @param arr array of byte arrays to search for 2093 * @param key the key you want to find 2094 * @param comparator a comparator to compare. 2095 * @return zero-based index of the key, if the key is present in the array. 2096 * Otherwise, a value -(i + 1) such that the key is between arr[i - 2097 * 1] and arr[i] non-inclusively, where i is in [0, i], if we define 2098 * arr[-1] = -Inf and arr[N] = Inf for an N-element array. The above 2099 * means that this function can return 2N + 1 different values 2100 * ranging from -(N + 1) to N - 1. 2101 * @return the index of the block 2102 */ 2103 public static int binarySearch(Cell[] arr, Cell key, CellComparator comparator) { 2104 int low = 0; 2105 int high = arr.length - 1; 2106 while (low <= high) { 2107 int mid = (low+high) >>> 1; 2108 // we have to compare in this order, because the comparator order 2109 // has special logic when the 'left side' is a special key. 2110 int cmp = comparator.compare(key, arr[mid]); 2111 // key lives above the midpoint 2112 if (cmp > 0) 2113 low = mid + 1; 2114 // key lives below the midpoint 2115 else if (cmp < 0) 2116 high = mid - 1; 2117 // BAM. how often does this really happen? 2118 else 2119 return mid; 2120 } 2121 return - (low+1); 2122 } 2123 2124 /** 2125 * Bytewise binary increment/deincrement of long contained in byte array 2126 * on given amount. 2127 * 2128 * @param value - array of bytes containing long (length <= SIZEOF_LONG) 2129 * @param amount value will be incremented on (deincremented if negative) 2130 * @return array of bytes containing incremented long (length == SIZEOF_LONG) 2131 */ 2132 public static byte [] incrementBytes(byte[] value, long amount) 2133 { 2134 byte[] val = value; 2135 if (val.length < SIZEOF_LONG) { 2136 // Hopefully this doesn't happen too often. 2137 byte [] newvalue; 2138 if (val[0] < 0) { 2139 newvalue = new byte[]{-1, -1, -1, -1, -1, -1, -1, -1}; 2140 } else { 2141 newvalue = new byte[SIZEOF_LONG]; 2142 } 2143 System.arraycopy(val, 0, newvalue, newvalue.length - val.length, 2144 val.length); 2145 val = newvalue; 2146 } else if (val.length > SIZEOF_LONG) { 2147 throw new IllegalArgumentException("Increment Bytes - value too big: " + 2148 val.length); 2149 } 2150 if(amount == 0) return val; 2151 if(val[0] < 0){ 2152 return binaryIncrementNeg(val, amount); 2153 } 2154 return binaryIncrementPos(val, amount); 2155 } 2156 2157 /* increment/deincrement for positive value */ 2158 private static byte [] binaryIncrementPos(byte [] value, long amount) { 2159 long amo = amount; 2160 int sign = 1; 2161 if (amount < 0) { 2162 amo = -amount; 2163 sign = -1; 2164 } 2165 for(int i=0;i<value.length;i++) { 2166 int cur = ((int)amo % 256) * sign; 2167 amo = (amo >> 8); 2168 int val = value[value.length-i-1] & 0x0ff; 2169 int total = val + cur; 2170 if(total > 255) { 2171 amo += sign; 2172 total %= 256; 2173 } else if (total < 0) { 2174 amo -= sign; 2175 } 2176 value[value.length-i-1] = (byte)total; 2177 if (amo == 0) return value; 2178 } 2179 return value; 2180 } 2181 2182 /* increment/deincrement for negative value */ 2183 private static byte [] binaryIncrementNeg(byte [] value, long amount) { 2184 long amo = amount; 2185 int sign = 1; 2186 if (amount < 0) { 2187 amo = -amount; 2188 sign = -1; 2189 } 2190 for(int i=0;i<value.length;i++) { 2191 int cur = ((int)amo % 256) * sign; 2192 amo = (amo >> 8); 2193 int val = ((~value[value.length-i-1]) & 0x0ff) + 1; 2194 int total = cur - val; 2195 if(total >= 0) { 2196 amo += sign; 2197 } else if (total < -256) { 2198 amo -= sign; 2199 total %= 256; 2200 } 2201 value[value.length-i-1] = (byte)total; 2202 if (amo == 0) return value; 2203 } 2204 return value; 2205 } 2206 2207 /** 2208 * Writes a string as a fixed-size field, padded with zeros. 2209 */ 2210 public static void writeStringFixedSize(final DataOutput out, String s, 2211 int size) throws IOException { 2212 byte[] b = toBytes(s); 2213 if (b.length > size) { 2214 throw new IOException("Trying to write " + b.length + " bytes (" + 2215 toStringBinary(b) + ") into a field of length " + size); 2216 } 2217 2218 out.writeBytes(s); 2219 for (int i = 0; i < size - s.length(); ++i) 2220 out.writeByte(0); 2221 } 2222 2223 /** 2224 * Reads a fixed-size field and interprets it as a string padded with zeros. 2225 */ 2226 public static String readStringFixedSize(final DataInput in, int size) 2227 throws IOException { 2228 byte[] b = new byte[size]; 2229 in.readFully(b); 2230 int n = b.length; 2231 while (n > 0 && b[n - 1] == 0) 2232 --n; 2233 2234 return toString(b, 0, n); 2235 } 2236 2237 /** 2238 * Copy the byte array given in parameter and return an instance 2239 * of a new byte array with the same length and the same content. 2240 * @param bytes the byte array to duplicate 2241 * @return a copy of the given byte array 2242 */ 2243 public static byte [] copy(byte [] bytes) { 2244 if (bytes == null) return null; 2245 byte [] result = new byte[bytes.length]; 2246 System.arraycopy(bytes, 0, result, 0, bytes.length); 2247 return result; 2248 } 2249 2250 /** 2251 * Copy the byte array given in parameter and return an instance 2252 * of a new byte array with the same length and the same content. 2253 * @param bytes the byte array to copy from 2254 * @return a copy of the given designated byte array 2255 * @param offset 2256 * @param length 2257 */ 2258 public static byte [] copy(byte [] bytes, final int offset, final int length) { 2259 if (bytes == null) return null; 2260 byte [] result = new byte[length]; 2261 System.arraycopy(bytes, offset, result, 0, length); 2262 return result; 2263 } 2264 2265 /** 2266 * Search sorted array "a" for byte "key". I can't remember if I wrote this or copied it from 2267 * somewhere. (mcorgan) 2268 * @param a Array to search. Entries must be sorted and unique. 2269 * @param fromIndex First index inclusive of "a" to include in the search. 2270 * @param toIndex Last index exclusive of "a" to include in the search. 2271 * @param key The byte to search for. 2272 * @return The index of key if found. If not found, return -(index + 1), where negative indicates 2273 * "not found" and the "index + 1" handles the "-0" case. 2274 */ 2275 public static int unsignedBinarySearch(byte[] a, int fromIndex, int toIndex, byte key) { 2276 int unsignedKey = key & 0xff; 2277 int low = fromIndex; 2278 int high = toIndex - 1; 2279 2280 while (low <= high) { 2281 int mid = (low + high) >>> 1; 2282 int midVal = a[mid] & 0xff; 2283 2284 if (midVal < unsignedKey) { 2285 low = mid + 1; 2286 } else if (midVal > unsignedKey) { 2287 high = mid - 1; 2288 } else { 2289 return mid; // key found 2290 } 2291 } 2292 return -(low + 1); // key not found. 2293 } 2294 2295 /** 2296 * Treat the byte[] as an unsigned series of bytes, most significant bits first. Start by adding 2297 * 1 to the rightmost bit/byte and carry over all overflows to the more significant bits/bytes. 2298 * 2299 * @param input The byte[] to increment. 2300 * @return The incremented copy of "in". May be same length or 1 byte longer. 2301 */ 2302 public static byte[] unsignedCopyAndIncrement(final byte[] input) { 2303 byte[] copy = copy(input); 2304 if (copy == null) { 2305 throw new IllegalArgumentException("cannot increment null array"); 2306 } 2307 for (int i = copy.length - 1; i >= 0; --i) { 2308 if (copy[i] == -1) {// -1 is all 1-bits, which is the unsigned maximum 2309 copy[i] = 0; 2310 } else { 2311 ++copy[i]; 2312 return copy; 2313 } 2314 } 2315 // we maxed out the array 2316 byte[] out = new byte[copy.length + 1]; 2317 out[0] = 1; 2318 System.arraycopy(copy, 0, out, 1, copy.length); 2319 return out; 2320 } 2321 2322 public static boolean equals(List<byte[]> a, List<byte[]> b) { 2323 if (a == null) { 2324 if (b == null) { 2325 return true; 2326 } 2327 return false; 2328 } 2329 if (b == null) { 2330 return false; 2331 } 2332 if (a.size() != b.size()) { 2333 return false; 2334 } 2335 for (int i = 0; i < a.size(); ++i) { 2336 if (!Bytes.equals(a.get(i), b.get(i))) { 2337 return false; 2338 } 2339 } 2340 return true; 2341 } 2342 2343 public static boolean isSorted(Collection<byte[]> arrays) { 2344 if (!CollectionUtils.isEmpty(arrays)) { 2345 byte[] previous = new byte[0]; 2346 for (byte[] array : arrays) { 2347 if (Bytes.compareTo(previous, array) > 0) { 2348 return false; 2349 } 2350 previous = array; 2351 } 2352 } 2353 return true; 2354 } 2355 2356 public static List<byte[]> getUtf8ByteArrays(List<String> strings) { 2357 if (CollectionUtils.isEmpty(strings)) { 2358 return Collections.emptyList(); 2359 } 2360 List<byte[]> byteArrays = new ArrayList<>(strings.size()); 2361 strings.forEach(s -> byteArrays.add(Bytes.toBytes(s))); 2362 return byteArrays; 2363 } 2364 2365 /** 2366 * Returns the index of the first appearance of the value {@code target} in 2367 * {@code array}. 2368 * 2369 * @param array an array of {@code byte} values, possibly empty 2370 * @param target a primitive {@code byte} value 2371 * @return the least index {@code i} for which {@code array[i] == target}, or 2372 * {@code -1} if no such index exists. 2373 */ 2374 public static int indexOf(byte[] array, byte target) { 2375 for (int i = 0; i < array.length; i++) { 2376 if (array[i] == target) { 2377 return i; 2378 } 2379 } 2380 return -1; 2381 } 2382 2383 /** 2384 * Returns the start position of the first occurrence of the specified {@code 2385 * target} within {@code array}, or {@code -1} if there is no such occurrence. 2386 * 2387 * <p>More formally, returns the lowest index {@code i} such that {@code 2388 * java.util.Arrays.copyOfRange(array, i, i + target.length)} contains exactly 2389 * the same elements as {@code target}. 2390 * 2391 * @param array the array to search for the sequence {@code target} 2392 * @param target the array to search for as a sub-sequence of {@code array} 2393 */ 2394 public static int indexOf(byte[] array, byte[] target) { 2395 checkNotNull(array, "array"); 2396 checkNotNull(target, "target"); 2397 if (target.length == 0) { 2398 return 0; 2399 } 2400 2401 outer: 2402 for (int i = 0; i < array.length - target.length + 1; i++) { 2403 for (int j = 0; j < target.length; j++) { 2404 if (array[i + j] != target[j]) { 2405 continue outer; 2406 } 2407 } 2408 return i; 2409 } 2410 return -1; 2411 } 2412 2413 /** 2414 * @param array an array of {@code byte} values, possibly empty 2415 * @param target a primitive {@code byte} value 2416 * @return {@code true} if {@code target} is present as an element anywhere in {@code array}. 2417 */ 2418 public static boolean contains(byte[] array, byte target) { 2419 return indexOf(array, target) > -1; 2420 } 2421 2422 /** 2423 * @param array an array of {@code byte} values, possibly empty 2424 * @param target an array of {@code byte} 2425 * @return {@code true} if {@code target} is present anywhere in {@code array} 2426 */ 2427 public static boolean contains(byte[] array, byte[] target) { 2428 return indexOf(array, target) > -1; 2429 } 2430 2431 /** 2432 * Fill given array with zeros. 2433 * @param b array which needs to be filled with zeros 2434 */ 2435 public static void zero(byte[] b) { 2436 zero(b, 0, b.length); 2437 } 2438 2439 /** 2440 * Fill given array with zeros at the specified position. 2441 * @param b 2442 * @param offset 2443 * @param length 2444 */ 2445 public static void zero(byte[] b, int offset, int length) { 2446 checkPositionIndex(offset, b.length, "offset"); 2447 checkArgument(length > 0, "length must be greater than 0"); 2448 checkPositionIndex(offset + length, b.length, "offset + length"); 2449 Arrays.fill(b, offset, offset + length, (byte) 0); 2450 } 2451 2452 private static final SecureRandom RNG = new SecureRandom(); 2453 2454 /** 2455 * Fill given array with random bytes. 2456 * @param b array which needs to be filled with random bytes 2457 */ 2458 public static void random(byte[] b) { 2459 RNG.nextBytes(b); 2460 } 2461 2462 /** 2463 * Fill given array with random bytes at the specified position. 2464 * @param b 2465 * @param offset 2466 * @param length 2467 */ 2468 public static void random(byte[] b, int offset, int length) { 2469 checkPositionIndex(offset, b.length, "offset"); 2470 checkArgument(length > 0, "length must be greater than 0"); 2471 checkPositionIndex(offset + length, b.length, "offset + length"); 2472 byte[] buf = new byte[length]; 2473 RNG.nextBytes(buf); 2474 System.arraycopy(buf, 0, b, offset, length); 2475 } 2476 2477 /** 2478 * Create a max byte array with the specified max byte count 2479 * @param maxByteCount the length of returned byte array 2480 * @return the created max byte array 2481 */ 2482 public static byte[] createMaxByteArray(int maxByteCount) { 2483 byte[] maxByteArray = new byte[maxByteCount]; 2484 for (int i = 0; i < maxByteArray.length; i++) { 2485 maxByteArray[i] = (byte) 0xff; 2486 } 2487 return maxByteArray; 2488 } 2489 2490 /** 2491 * Create a byte array which is multiple given bytes 2492 * @param srcBytes 2493 * @param multiNum 2494 * @return byte array 2495 */ 2496 public static byte[] multiple(byte[] srcBytes, int multiNum) { 2497 if (multiNum <= 0) { 2498 return new byte[0]; 2499 } 2500 byte[] result = new byte[srcBytes.length * multiNum]; 2501 for (int i = 0; i < multiNum; i++) { 2502 System.arraycopy(srcBytes, 0, result, i * srcBytes.length, 2503 srcBytes.length); 2504 } 2505 return result; 2506 } 2507 2508 private static final char[] HEX_CHARS = { 2509 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' 2510 }; 2511 2512 /** 2513 * Convert a byte range into a hex string 2514 */ 2515 public static String toHex(byte[] b, int offset, int length) { 2516 checkArgument(length <= Integer.MAX_VALUE / 2); 2517 int numChars = length * 2; 2518 char[] ch = new char[numChars]; 2519 for (int i = 0; i < numChars; i += 2) 2520 { 2521 byte d = b[offset + i/2]; 2522 ch[i] = HEX_CHARS[(d >> 4) & 0x0F]; 2523 ch[i+1] = HEX_CHARS[d & 0x0F]; 2524 } 2525 return new String(ch); 2526 } 2527 2528 /** 2529 * Convert a byte array into a hex string 2530 */ 2531 public static String toHex(byte[] b) { 2532 return toHex(b, 0, b.length); 2533 } 2534 2535 private static int hexCharToNibble(char ch) { 2536 if (ch <= '9' && ch >= '0') { 2537 return ch - '0'; 2538 } else if (ch >= 'a' && ch <= 'f') { 2539 return ch - 'a' + 10; 2540 } else if (ch >= 'A' && ch <= 'F') { 2541 return ch - 'A' + 10; 2542 } 2543 throw new IllegalArgumentException("Invalid hex char: " + ch); 2544 } 2545 2546 private static byte hexCharsToByte(char c1, char c2) { 2547 return (byte) ((hexCharToNibble(c1) << 4) | hexCharToNibble(c2)); 2548 } 2549 2550 /** 2551 * Create a byte array from a string of hash digits. The length of the 2552 * string must be a multiple of 2 2553 * @param hex 2554 */ 2555 public static byte[] fromHex(String hex) { 2556 checkArgument(hex.length() % 2 == 0, "length must be a multiple of 2"); 2557 int len = hex.length(); 2558 byte[] b = new byte[len / 2]; 2559 for (int i = 0; i < len; i += 2) { 2560 b[i / 2] = hexCharsToByte(hex.charAt(i),hex.charAt(i+1)); 2561 } 2562 return b; 2563 } 2564 2565 /** 2566 * @param b 2567 * @param delimiter 2568 * @return Index of delimiter having started from start of <code>b</code> moving rightward. 2569 */ 2570 public static int searchDelimiterIndex(final byte[] b, int offset, final int length, 2571 final int delimiter) { 2572 if (b == null) { 2573 throw new IllegalArgumentException("Passed buffer is null"); 2574 } 2575 int result = -1; 2576 for (int i = offset; i < length + offset; i++) { 2577 if (b[i] == delimiter) { 2578 result = i; 2579 break; 2580 } 2581 } 2582 return result; 2583 } 2584 2585 /** 2586 * Find index of passed delimiter walking from end of buffer backwards. 2587 * 2588 * @param b 2589 * @param delimiter 2590 * @return Index of delimiter 2591 */ 2592 public static int searchDelimiterIndexInReverse(final byte[] b, final int offset, 2593 final int length, final int delimiter) { 2594 if (b == null) { 2595 throw new IllegalArgumentException("Passed buffer is null"); 2596 } 2597 int result = -1; 2598 for (int i = (offset + length) - 1; i >= offset; i--) { 2599 if (b[i] == delimiter) { 2600 result = i; 2601 break; 2602 } 2603 } 2604 return result; 2605 } 2606 2607 public static int findCommonPrefix(byte[] left, byte[] right, int leftLength, int rightLength, 2608 int leftOffset, int rightOffset) { 2609 int length = Math.min(leftLength, rightLength); 2610 int result = 0; 2611 2612 while (result < length && left[leftOffset + result] == right[rightOffset + result]) { 2613 result++; 2614 } 2615 return result; 2616 } 2617}