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