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