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