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