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