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