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