View Javadoc

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