View Javadoc

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