View Javadoc

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