001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with this
004 * work for additional information regarding copyright ownership. The ASF
005 * licenses this file to you under the Apache License, Version 2.0 (the
006 * "License"); you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
013 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
014 * License for the specific language governing permissions and limitations
015 * under the License.
016 */
017package org.apache.hadoop.hbase.util;
018
019import java.io.ByteArrayOutputStream;
020import java.io.DataInput;
021import java.io.DataInputStream;
022import java.io.DataOutput;
023import java.io.IOException;
024import java.io.InputStream;
025import java.io.OutputStream;
026import java.math.BigDecimal;
027import java.math.BigInteger;
028import java.nio.ByteBuffer;
029import java.util.Arrays;
030
031import org.apache.hadoop.hbase.io.ByteBufferWriter;
032import org.apache.hadoop.hbase.io.util.StreamUtils;
033import org.apache.hadoop.hbase.nio.ByteBuff;
034import org.apache.hadoop.io.IOUtils;
035import org.apache.hadoop.io.WritableUtils;
036import org.apache.yetus.audience.InterfaceAudience;
037import sun.nio.ch.DirectBuffer;
038
039import org.apache.hbase.thirdparty.com.google.common.annotations.VisibleForTesting;
040
041/**
042 * Utility functions for working with byte buffers, such as reading/writing
043 * variable-length long numbers.
044 */
045@SuppressWarnings("restriction")
046@InterfaceAudience.Private
047public final class ByteBufferUtils {
048  // "Compressed integer" serialization helper constants.
049  public final static int VALUE_MASK = 0x7f;
050  public final static int NEXT_BIT_SHIFT = 7;
051  public final static int NEXT_BIT_MASK = 1 << 7;
052  @VisibleForTesting
053  final static boolean UNSAFE_AVAIL = UnsafeAvailChecker.isAvailable();
054  public final static boolean UNSAFE_UNALIGNED = UnsafeAvailChecker.unaligned();
055
056  private ByteBufferUtils() {
057  }
058
059
060  static abstract class Comparer {
061    abstract int compareTo(byte [] buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2);
062    abstract int compareTo(ByteBuffer buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2);
063  }
064
065  static abstract class Converter {
066    abstract short toShort(ByteBuffer buffer, int offset);
067    abstract int toInt(ByteBuffer buffer);
068    abstract int toInt(ByteBuffer buffer, int offset);
069    abstract long toLong(ByteBuffer buffer, int offset);
070    abstract void putInt(ByteBuffer buffer, int val);
071    abstract int putInt(ByteBuffer buffer, int index, int val);
072    abstract void putShort(ByteBuffer buffer, short val);
073    abstract int putShort(ByteBuffer buffer, int index, short val);
074    abstract void putLong(ByteBuffer buffer, long val);
075    abstract int putLong(ByteBuffer buffer, int index, long val);
076  }
077
078  static class ComparerHolder {
079    static final String UNSAFE_COMPARER_NAME = ComparerHolder.class.getName() + "$UnsafeComparer";
080
081    static final Comparer BEST_COMPARER = getBestComparer();
082
083    static Comparer getBestComparer() {
084      try {
085        Class<?> theClass = Class.forName(UNSAFE_COMPARER_NAME);
086
087        @SuppressWarnings("unchecked")
088        Comparer comparer = (Comparer) theClass.getConstructor().newInstance();
089        return comparer;
090      } catch (Throwable t) { // ensure we really catch *everything*
091        return PureJavaComparer.INSTANCE;
092      }
093    }
094
095    static final class PureJavaComparer extends Comparer {
096      static final PureJavaComparer INSTANCE = new PureJavaComparer();
097
098      private PureJavaComparer() {}
099
100      @Override
101      public int compareTo(byte [] buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2) {
102        int end1 = o1 + l1;
103        int end2 = o2 + l2;
104        for (int i = o1, j = o2; i < end1 && j < end2; i++, j++) {
105          int a = buf1[i] & 0xFF;
106          int b = buf2.get(j) & 0xFF;
107          if (a != b) {
108            return a - b;
109          }
110        }
111        return l1 - l2;
112      }
113
114      @Override
115      public int compareTo(ByteBuffer buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2) {
116        int end1 = o1 + l1;
117        int end2 = o2 + l2;
118        for (int i = o1, j = o2; i < end1 && j < end2; i++, j++) {
119          int a = buf1.get(i) & 0xFF;
120          int b = buf2.get(j) & 0xFF;
121          if (a != b) {
122            return a - b;
123          }
124        }
125        return l1 - l2;
126      }
127    }
128
129    static final class UnsafeComparer extends Comparer {
130
131      public UnsafeComparer() {}
132
133      static {
134        if(!UNSAFE_UNALIGNED) {
135          throw new Error();
136        }
137      }
138
139      @Override
140      public int compareTo(byte[] buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2) {
141        long offset2Adj;
142        Object refObj2 = null;
143        if (buf2.isDirect()) {
144          offset2Adj = o2 + ((DirectBuffer)buf2).address();
145        } else {
146          offset2Adj = o2 + buf2.arrayOffset() + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET;
147          refObj2 = buf2.array();
148        }
149        return compareToUnsafe(buf1, o1 + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET, l1,
150                refObj2, offset2Adj, l2);
151      }
152
153      @Override
154      public int compareTo(ByteBuffer buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2) {
155        long offset1Adj, offset2Adj;
156        Object refObj1 = null, refObj2 = null;
157        if (buf1.isDirect()) {
158          offset1Adj = o1 + ((DirectBuffer) buf1).address();
159        } else {
160          offset1Adj = o1 + buf1.arrayOffset() + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET;
161          refObj1 = buf1.array();
162        }
163        if (buf2.isDirect()) {
164          offset2Adj = o2 + ((DirectBuffer) buf2).address();
165        } else {
166          offset2Adj = o2 + buf2.arrayOffset() + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET;
167          refObj2 = buf2.array();
168        }
169        return compareToUnsafe(refObj1, offset1Adj, l1, refObj2, offset2Adj, l2);
170      }
171    }
172  }
173
174
175  static class ConverterHolder {
176    static final String UNSAFE_CONVERTER_NAME =
177            ConverterHolder.class.getName() + "$UnsafeConverter";
178    static final Converter BEST_CONVERTER = getBestConverter();
179
180    static Converter getBestConverter() {
181      try {
182        Class<?> theClass = Class.forName(UNSAFE_CONVERTER_NAME);
183
184        // yes, UnsafeComparer does implement Comparer<byte[]>
185        @SuppressWarnings("unchecked")
186        Converter converter = (Converter) theClass.getConstructor().newInstance();
187        return converter;
188      } catch (Throwable t) { // ensure we really catch *everything*
189        return PureJavaConverter.INSTANCE;
190      }
191    }
192
193    static final class PureJavaConverter extends Converter {
194      static final PureJavaConverter INSTANCE = new PureJavaConverter();
195
196      private PureJavaConverter() {}
197
198      @Override
199      short toShort(ByteBuffer buffer, int offset) {
200        return buffer.getShort(offset);
201      }
202
203      @Override
204      int toInt(ByteBuffer buffer) {
205        return buffer.getInt();
206      }
207
208      @Override
209      int toInt(ByteBuffer buffer, int offset) {
210        return buffer.getInt(offset);
211      }
212
213      @Override
214      long toLong(ByteBuffer buffer, int offset) {
215        return buffer.getLong(offset);
216      }
217
218      @Override
219      void putInt(ByteBuffer buffer, int val) {
220        buffer.putInt(val);
221      }
222
223      @Override
224      int putInt(ByteBuffer buffer, int index, int val) {
225        buffer.putInt(index, val);
226        return index + Bytes.SIZEOF_INT;
227      }
228
229      @Override
230      void putShort(ByteBuffer buffer, short val) {
231        buffer.putShort(val);
232      }
233
234      @Override
235      int putShort(ByteBuffer buffer, int index, short val) {
236        buffer.putShort(index, val);
237        return index + Bytes.SIZEOF_SHORT;
238      }
239
240      @Override
241      void putLong(ByteBuffer buffer, long val) {
242        buffer.putLong(val);
243      }
244
245      @Override
246      int putLong(ByteBuffer buffer, int index, long val) {
247        buffer.putLong(index, val);
248        return index + Bytes.SIZEOF_LONG;
249      }
250    }
251
252    static final class UnsafeConverter extends Converter {
253
254      public UnsafeConverter() {}
255
256      static {
257        if(!UNSAFE_UNALIGNED) {
258          throw new Error();
259        }
260      }
261
262      @Override
263      short toShort(ByteBuffer buffer, int offset) {
264        return UnsafeAccess.toShort(buffer, offset);
265      }
266
267      @Override
268      int toInt(ByteBuffer buffer) {
269        int i = UnsafeAccess.toInt(buffer, buffer.position());
270        buffer.position(buffer.position() + Bytes.SIZEOF_INT);
271        return i;
272      }
273
274      @Override
275      int toInt(ByteBuffer buffer, int offset) {
276        return UnsafeAccess.toInt(buffer, offset);
277      }
278
279      @Override
280      long toLong(ByteBuffer buffer, int offset) {
281        return UnsafeAccess.toLong(buffer, offset);
282      }
283
284      @Override
285      void putInt(ByteBuffer buffer, int val) {
286        int newPos = UnsafeAccess.putInt(buffer, buffer.position(), val);
287        buffer.position(newPos);
288      }
289
290      @Override
291      int putInt(ByteBuffer buffer, int index, int val) {
292        return UnsafeAccess.putInt(buffer, index, val);
293      }
294
295      @Override
296      void putShort(ByteBuffer buffer, short val) {
297        int newPos = UnsafeAccess.putShort(buffer, buffer.position(), val);
298        buffer.position(newPos);
299      }
300
301      @Override
302      int putShort(ByteBuffer buffer, int index, short val) {
303        return UnsafeAccess.putShort(buffer, index, val);
304      }
305
306      @Override
307      void putLong(ByteBuffer buffer, long val) {
308        int newPos = UnsafeAccess.putLong(buffer, buffer.position(), val);
309        buffer.position(newPos);
310      }
311
312      @Override
313      int putLong(ByteBuffer buffer, int index, long val) {
314        return UnsafeAccess.putLong(buffer, index, val);
315      }
316    }
317  }
318
319    /**
320   * Similar to {@link WritableUtils#writeVLong(java.io.DataOutput, long)},
321   * but writes to a {@link ByteBuffer}.
322   */
323  public static void writeVLong(ByteBuffer out, long i) {
324    if (i >= -112 && i <= 127) {
325      out.put((byte) i);
326      return;
327    }
328
329    int len = -112;
330    if (i < 0) {
331      i ^= -1L; // take one's complement
332      len = -120;
333    }
334
335    long tmp = i;
336    while (tmp != 0) {
337      tmp = tmp >> 8;
338      len--;
339    }
340
341    out.put((byte) len);
342
343    len = (len < -120) ? -(len + 120) : -(len + 112);
344
345    for (int idx = len; idx != 0; idx--) {
346      int shiftbits = (idx - 1) * 8;
347      long mask = 0xFFL << shiftbits;
348      out.put((byte) ((i & mask) >> shiftbits));
349    }
350  }
351
352  private interface ByteVisitor {
353    byte get();
354  }
355
356  private static long readVLong(ByteVisitor visitor) {
357    byte firstByte = visitor.get();
358    int len = WritableUtils.decodeVIntSize(firstByte);
359    if (len == 1) {
360      return firstByte;
361    }
362    long i = 0;
363    for (int idx = 0; idx < len - 1; idx++) {
364      byte b = visitor.get();
365      i = i << 8;
366      i = i | (b & 0xFF);
367    }
368    return (WritableUtils.isNegativeVInt(firstByte) ? (i ^ -1L) : i);
369  }
370
371  /**
372   * Similar to {@link WritableUtils#readVLong(DataInput)} but reads from a {@link ByteBuffer}.
373   */
374  public static long readVLong(ByteBuffer in) {
375    return readVLong(in::get);
376  }
377
378  /**
379   * Similar to {@link WritableUtils#readVLong(java.io.DataInput)} but reads from a
380   * {@link ByteBuff}.
381   */
382  public static long readVLong(ByteBuff in) {
383    return readVLong(in::get);
384  }
385
386  /**
387   * Put in buffer integer using 7 bit encoding. For each written byte:
388   * 7 bits are used to store value
389   * 1 bit is used to indicate whether there is next bit.
390   * @param value Int to be compressed.
391   * @param out Where to put compressed data
392   * @return Number of bytes written.
393   * @throws IOException on stream error
394   */
395   public static int putCompressedInt(OutputStream out, final int value)
396      throws IOException {
397    int i = 0;
398    int tmpvalue = value;
399    do {
400      byte b = (byte) (tmpvalue & VALUE_MASK);
401      tmpvalue >>>= NEXT_BIT_SHIFT;
402      if (tmpvalue != 0) {
403        b |= (byte) NEXT_BIT_MASK;
404      }
405      out.write(b);
406      i++;
407    } while (tmpvalue != 0);
408    return i;
409  }
410
411   /**
412    * Put in output stream 32 bit integer (Big Endian byte order).
413    * @param out Where to put integer.
414    * @param value Value of integer.
415    * @throws IOException On stream error.
416    */
417   public static void putInt(OutputStream out, final int value)
418       throws IOException {
419     // We have writeInt in ByteBufferOutputStream so that it can directly write
420     // int to underlying
421     // ByteBuffer in one step.
422     if (out instanceof ByteBufferWriter) {
423       ((ByteBufferWriter) out).writeInt(value);
424     } else {
425       StreamUtils.writeInt(out, value);
426     }
427   }
428
429  public static byte toByte(ByteBuffer buffer, int offset) {
430    if (UNSAFE_AVAIL) {
431      return UnsafeAccess.toByte(buffer, offset);
432    } else {
433      return buffer.get(offset);
434    }
435  }
436
437  /**
438   * Copy the data to the output stream and update position in buffer.
439   * @param out the stream to write bytes to
440   * @param in the buffer to read bytes from
441   * @param length the number of bytes to copy
442   */
443  public static void moveBufferToStream(OutputStream out, ByteBuffer in,
444      int length) throws IOException {
445    copyBufferToStream(out, in, in.position(), length);
446    skip(in, length);
447  }
448
449  /**
450   * Copy data from a buffer to an output stream. Does not update the position
451   * in the buffer.
452   * @param out the stream to write bytes to
453   * @param in the buffer to read bytes from
454   * @param offset the offset in the buffer (from the buffer's array offset)
455   *      to start copying bytes from
456   * @param length the number of bytes to copy
457   */
458  public static void copyBufferToStream(OutputStream out, ByteBuffer in,
459      int offset, int length) throws IOException {
460    if (out instanceof ByteBufferWriter) {
461      ((ByteBufferWriter) out).write(in, offset, length);
462    } else if (in.hasArray()) {
463      out.write(in.array(), in.arrayOffset() + offset, length);
464    } else {
465      for (int i = 0; i < length; ++i) {
466        out.write(toByte(in, offset + i));
467      }
468    }
469  }
470
471  /**
472   * Copy data from a buffer to an output stream. Does not update the position
473   * in the buffer.
474   * @param out the output stream to write bytes to
475   * @param in the buffer to read bytes from
476   * @param offset the offset in the buffer (from the buffer's array offset)
477   *      to start copying bytes from
478   * @param length the number of bytes to copy
479   */
480  public static void copyBufferToStream(DataOutput out, ByteBuffer in, int offset, int length)
481      throws IOException {
482    if (out instanceof ByteBufferWriter) {
483      ((ByteBufferWriter) out).write(in, offset, length);
484    } else if (in.hasArray()) {
485      out.write(in.array(), in.arrayOffset() + offset, length);
486    } else {
487      for (int i = 0; i < length; ++i) {
488        out.write(toByte(in, offset + i));
489      }
490    }
491  }
492
493  public static int putLong(OutputStream out, final long value,
494      final int fitInBytes) throws IOException {
495    long tmpValue = value;
496    for (int i = 0; i < fitInBytes; ++i) {
497      out.write((byte) (tmpValue & 0xff));
498      tmpValue >>>= 8;
499    }
500    return fitInBytes;
501  }
502
503  public static int putByte(ByteBuffer buffer, int offset, byte b) {
504    if (UNSAFE_AVAIL) {
505      return UnsafeAccess.putByte(buffer, offset, b);
506    } else {
507      buffer.put(offset, b);
508      return offset + 1;
509    }
510  }
511
512  /**
513   * Check how many bytes are required to store value.
514   * @param value Value which size will be tested.
515   * @return How many bytes are required to store value.
516   */
517  public static int longFitsIn(final long value) {
518    if (value < 0) {
519      return 8;
520    }
521
522    if (value < (1L << (4 * 8))) {
523      // no more than 4 bytes
524      if (value < (1L << (2 * 8))) {
525        if (value < (1L << (1 * 8))) {
526          return 1;
527        }
528        return 2;
529      }
530      if (value < (1L << (3 * 8))) {
531        return 3;
532      }
533      return 4;
534    }
535    // more than 4 bytes
536    if (value < (1L << (6 * 8))) {
537      if (value < (1L << (5 * 8))) {
538        return 5;
539      }
540      return 6;
541    }
542    if (value < (1L << (7 * 8))) {
543      return 7;
544    }
545    return 8;
546  }
547
548  /**
549   * Check how many bytes is required to store value.
550   * @param value Value which size will be tested.
551   * @return How many bytes are required to store value.
552   */
553  public static int intFitsIn(final int value) {
554    if (value < 0) {
555      return 4;
556    }
557
558    if (value < (1 << (2 * 8))) {
559      if (value < (1 << (1 * 8))) {
560        return 1;
561      }
562      return 2;
563    }
564    if (value <= (1 << (3 * 8))) {
565      return 3;
566    }
567    return 4;
568  }
569
570  /**
571   * Read integer from stream coded in 7 bits and increment position.
572   * @return the integer that has been read
573   * @throws IOException
574   */
575  public static int readCompressedInt(InputStream input)
576      throws IOException {
577    int result = 0;
578    int i = 0;
579    byte b;
580    do {
581      b = (byte) input.read();
582      result += (b & VALUE_MASK) << (NEXT_BIT_SHIFT * i);
583      i++;
584      if (i > Bytes.SIZEOF_INT + 1) {
585        throw new IllegalStateException(
586            "Corrupted compressed int (too long: " + (i + 1) + " bytes)");
587      }
588    } while (0 != (b & NEXT_BIT_MASK));
589    return result;
590  }
591
592  /**
593   * Read integer from buffer coded in 7 bits and increment position.
594   * @return Read integer.
595   */
596  public static int readCompressedInt(ByteBuffer buffer) {
597    byte b = buffer.get();
598    if ((b & NEXT_BIT_MASK) != 0) {
599      return (b & VALUE_MASK) + (readCompressedInt(buffer) << NEXT_BIT_SHIFT);
600    }
601    return b & VALUE_MASK;
602  }
603
604  /**
605   * Read long which was written to fitInBytes bytes and increment position.
606   * @param fitInBytes In how many bytes given long is stored.
607   * @return The value of parsed long.
608   * @throws IOException
609   */
610  public static long readLong(InputStream in, final int fitInBytes)
611      throws IOException {
612    long tmpLong = 0;
613    for (int i = 0; i < fitInBytes; ++i) {
614      tmpLong |= (in.read() & 0xffL) << (8 * i);
615    }
616    return tmpLong;
617  }
618
619  /**
620   * Read long which was written to fitInBytes bytes and increment position.
621   * @param fitInBytes In how many bytes given long is stored.
622   * @return The value of parsed long.
623   */
624  public static long readLong(ByteBuffer in, final int fitInBytes) {
625    long tmpLength = 0;
626    for (int i = 0; i < fitInBytes; ++i) {
627      tmpLength |= (in.get() & 0xffL) << (8L * i);
628    }
629    return tmpLength;
630  }
631
632  /**
633   * Copy the given number of bytes from the given stream and put it at the
634   * current position of the given buffer, updating the position in the buffer.
635   * @param out the buffer to write data to
636   * @param in the stream to read data from
637   * @param length the number of bytes to read/write
638   */
639  public static void copyFromStreamToBuffer(ByteBuffer out,
640      DataInputStream in, int length) throws IOException {
641    if (out.hasArray()) {
642      in.readFully(out.array(), out.position() + out.arrayOffset(),
643          length);
644      skip(out, length);
645    } else {
646      for (int i = 0; i < length; ++i) {
647        out.put(in.readByte());
648      }
649    }
650  }
651
652  /**
653   * Copy from the InputStream to a new heap ByteBuffer until the InputStream is exhausted.
654   */
655  public static ByteBuffer drainInputStreamToBuffer(InputStream is) throws IOException {
656    ByteArrayOutputStream baos = new ByteArrayOutputStream(4096);
657    IOUtils.copyBytes(is, baos, 4096, true);
658    ByteBuffer buffer = ByteBuffer.wrap(baos.toByteArray());
659    buffer.rewind();
660    return buffer;
661  }
662
663  /**
664   * Copy one buffer's whole data to another. Write starts at the current position of 'out' buffer.
665   * Note : This will advance the position marker of {@code out} and also change the position maker
666   * for {@code in}.
667   * @param in source buffer
668   * @param out destination buffer
669   */
670  public static void copyFromBufferToBuffer(ByteBuffer in, ByteBuffer out) {
671    if (in.hasArray() && out.hasArray()) {
672      int length = in.remaining();
673      System.arraycopy(in.array(), in.arrayOffset(), out.array(), out.arrayOffset(), length);
674      out.position(out.position() + length);
675      in.position(in.limit());
676    } else if (UNSAFE_AVAIL) {
677      int length = in.remaining();
678      UnsafeAccess.copy(in, in.position(), out, out.position(), length);
679      out.position(out.position() + length);
680      in.position(in.limit());
681    } else {
682      out.put(in);
683    }
684  }
685
686  /**
687   * Copy from one buffer to another from given offset. This will be absolute positional copying and
688   * won't affect the position of any of the buffers.
689   * @param in
690   * @param out
691   * @param sourceOffset
692   * @param destinationOffset
693   * @param length
694   */
695  public static void copyFromBufferToBuffer(ByteBuffer in, ByteBuffer out, int sourceOffset,
696      int destinationOffset, int length) {
697    if (in.hasArray() && out.hasArray()) {
698      System.arraycopy(in.array(), sourceOffset + in.arrayOffset(), out.array(), out.arrayOffset()
699          + destinationOffset, length);
700    } else if (UNSAFE_AVAIL) {
701      UnsafeAccess.copy(in, sourceOffset, out, destinationOffset, length);
702    } else {
703      ByteBuffer outDup = out.duplicate();
704      outDup.position(destinationOffset);
705      ByteBuffer inDup = in.duplicate();
706      inDup.position(sourceOffset).limit(sourceOffset + length);
707      outDup.put(inDup);
708    }
709    // We used to return a result but disabled; return destinationOffset + length;
710  }
711
712  /**
713   * Copy from one buffer to another from given offset.
714   * <p>
715   * Note : This will advance the position marker of {@code out} but not change the position maker
716   * for {@code in}
717   * @param in source buffer
718   * @param out destination buffer
719   * @param sourceOffset offset in the source buffer
720   * @param length how many bytes to copy
721   */
722  public static void copyFromBufferToBuffer(ByteBuffer in, ByteBuffer out, int sourceOffset,
723      int length) {
724    if (in.hasArray() && out.hasArray()) {
725      System.arraycopy(in.array(), sourceOffset + in.arrayOffset(), out.array(), out.position()
726          + out.arrayOffset(), length);
727      skip(out, length);
728    } else if (UNSAFE_AVAIL) {
729      UnsafeAccess.copy(in, sourceOffset, out, out.position(), length);
730      skip(out, length);
731    } else {
732      ByteBuffer inDup = in.duplicate();
733      inDup.position(sourceOffset).limit(sourceOffset + length);
734      out.put(inDup);
735    }
736  }
737
738  /**
739   * Find length of common prefix in two arrays.
740   * @param left Array to be compared.
741   * @param leftOffset Offset in left array.
742   * @param leftLength Length of left array.
743   * @param right Array to be compared.
744   * @param rightOffset Offset in right array.
745   * @param rightLength Length of right array.
746   */
747  public static int findCommonPrefix(
748      byte[] left, int leftOffset, int leftLength,
749      byte[] right, int rightOffset, int rightLength) {
750    int length = Math.min(leftLength, rightLength);
751    int result = 0;
752
753    while (result < length &&
754        left[leftOffset + result] == right[rightOffset + result]) {
755      result++;
756    }
757
758    return result;
759  }
760
761  /**
762   * Find length of common prefix in two arrays.
763   * @param left ByteBuffer to be compared.
764   * @param leftOffset Offset in left ByteBuffer.
765   * @param leftLength Length of left ByteBuffer.
766   * @param right ByteBuffer to be compared.
767   * @param rightOffset Offset in right ByteBuffer.
768   * @param rightLength Length of right ByteBuffer.
769   */
770  public static int findCommonPrefix(ByteBuffer left, int leftOffset, int leftLength,
771      ByteBuffer right, int rightOffset, int rightLength) {
772    int length = Math.min(leftLength, rightLength);
773    int result = 0;
774
775    while (result < length && ByteBufferUtils.toByte(left, leftOffset + result) == ByteBufferUtils
776        .toByte(right, rightOffset + result)) {
777      result++;
778    }
779
780    return result;
781  }
782
783  /**
784   * Check whether two parts in the same buffer are equal.
785   * @param buffer In which buffer there are parts
786   * @param offsetLeft Beginning of first part.
787   * @param lengthLeft Length of the first part.
788   * @param offsetRight Beginning of the second part.
789   * @param lengthRight Length of the second part.
790   * @return True if equal
791   */
792  public static boolean arePartsEqual(ByteBuffer buffer,
793      int offsetLeft, int lengthLeft,
794      int offsetRight, int lengthRight) {
795    if (lengthLeft != lengthRight) {
796      return false;
797    }
798
799    if (buffer.hasArray()) {
800      return 0 == Bytes.compareTo(
801          buffer.array(), buffer.arrayOffset() + offsetLeft, lengthLeft,
802          buffer.array(), buffer.arrayOffset() + offsetRight, lengthRight);
803    }
804
805    for (int i = 0; i < lengthRight; ++i) {
806      if (buffer.get(offsetLeft + i) != buffer.get(offsetRight + i)) {
807        return false;
808      }
809    }
810    return true;
811  }
812
813  /**
814   * Increment position in buffer.
815   * @param buffer In this buffer.
816   * @param length By that many bytes.
817   */
818  public static void skip(ByteBuffer buffer, int length) {
819    buffer.position(buffer.position() + length);
820  }
821
822  public static void extendLimit(ByteBuffer buffer, int numBytes) {
823    buffer.limit(buffer.limit() + numBytes);
824  }
825
826  /**
827   * Copy the bytes from position to limit into a new byte[] of the exact length and sets the
828   * position and limit back to their original values (though not thread safe).
829   * @param buffer copy from here
830   * @param startPosition put buffer.get(startPosition) into byte[0]
831   * @return a new byte[] containing the bytes in the specified range
832   */
833  public static byte[] toBytes(ByteBuffer buffer, int startPosition) {
834    int originalPosition = buffer.position();
835    byte[] output = new byte[buffer.limit() - startPosition];
836    buffer.position(startPosition);
837    buffer.get(output);
838    buffer.position(originalPosition);
839    return output;
840  }
841
842  /**
843   * Copy the given number of bytes from specified offset into a new byte[]
844   * @param buffer
845   * @param offset
846   * @param length
847   * @return a new byte[] containing the bytes in the specified range
848   */
849  public static byte[] toBytes(ByteBuffer buffer, int offset, int length) {
850    byte[] output = new byte[length];
851    for (int i = 0; i < length; i++) {
852      output[i] = buffer.get(offset + i);
853    }
854    return output;
855  }
856
857  public static boolean equals(ByteBuffer buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2) {
858    if ((l1 == 0) || (l2 == 0)) {
859      // both 0 length, return true, or else false
860      return l1 == l2;
861    }
862    // Since we're often comparing adjacent sorted data,
863    // it's usual to have equal arrays except for the very last byte
864    // so check that first
865    if (toByte(buf1, o1 + l1 - 1) != toByte(buf2, o2 + l2 - 1)) return false;
866    return compareTo(buf1, o1, l1, buf2, o2, l2) == 0;
867  }
868
869  /**
870   * @param buf
871   *          ByteBuffer to hash
872   * @param offset
873   *          offset to start from
874   * @param length
875   *          length to hash
876   */
877  public static int hashCode(ByteBuffer buf, int offset, int length) {
878    int hash = 1;
879    for (int i = offset; i < offset + length; i++) {
880      hash = (31 * hash) + (int) toByte(buf, i);
881    }
882    return hash;
883  }
884
885  public static int compareTo(ByteBuffer buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2) {
886    return ComparerHolder.BEST_COMPARER.compareTo(buf1, o1, l1, buf2, o2, l2);
887  }
888
889  public static boolean equals(ByteBuffer buf1, int o1, int l1, byte[] buf2, int o2, int l2) {
890    if ((l1 == 0) || (l2 == 0)) {
891      // both 0 length, return true, or else false
892      return l1 == l2;
893    }
894    // Since we're often comparing adjacent sorted data,
895    // it's usual to have equal arrays except for the very last byte
896    // so check that first
897    if (toByte(buf1, o1 + l1 - 1) != buf2[o2 + l2 - 1]) return false;
898    return compareTo(buf1, o1, l1, buf2, o2, l2) == 0;
899  }
900
901  // The below two methods show up in lots of places. Versions of them in commons util and in
902  // Cassandra. In guava too? They are copied from ByteBufferUtils. They are here as static
903  // privates. Seems to make code smaller and make Hotspot happier (comes of compares and study
904  // of compiled code via  jitwatch).
905
906  public static int compareTo(byte [] buf1, int o1, int l1, ByteBuffer buf2, int o2, int l2) {
907    return ComparerHolder.BEST_COMPARER.compareTo(buf1, o1, l1, buf2, o2, l2);
908  }
909
910  public static int compareTo(ByteBuffer buf1, int o1, int l1, byte[] buf2, int o2, int l2) {
911    return compareTo(buf2, o2, l2, buf1, o1, l1)*-1;
912  }
913
914  static int compareToUnsafe(Object obj1, long o1, int l1, Object obj2, long o2, int l2) {
915    final int stride = 8;
916    final int minLength = Math.min(l1, l2);
917    int strideLimit = minLength & ~(stride - 1);
918    int i;
919
920    /*
921     * Compare 8 bytes at a time. Benchmarking shows comparing 8 bytes at a time is no slower than
922     * comparing 4 bytes at a time even on 32-bit. On the other hand, it is substantially faster on
923     * 64-bit.
924     */
925    for (i = 0; i < strideLimit; i += stride) {
926      long lw = UnsafeAccess.theUnsafe.getLong(obj1, o1 + (long) i);
927      long rw = UnsafeAccess.theUnsafe.getLong(obj2, o2 + (long) i);
928      if (lw != rw) {
929        if (!UnsafeAccess.LITTLE_ENDIAN) {
930          return ((lw + Long.MIN_VALUE) < (rw + Long.MIN_VALUE)) ? -1 : 1;
931        }
932
933        /*
934         * We want to compare only the first index where left[index] != right[index]. This
935         * corresponds to the least significant nonzero byte in lw ^ rw, since lw and rw are
936         * little-endian. Long.numberOfTrailingZeros(diff) tells us the least significant
937         * nonzero bit, and zeroing out the first three bits of L.nTZ gives us the shift to get
938         * that least significant nonzero byte. This comparison logic is based on UnsignedBytes
939         * from guava v21
940         */
941        int n = Long.numberOfTrailingZeros(lw ^ rw) & ~0x7;
942        return ((int) ((lw >>> n) & 0xFF)) - ((int) ((rw >>> n) & 0xFF));
943      }
944    }
945
946    // The epilogue to cover the last (minLength % stride) elements.
947    for (; i < minLength; i++) {
948      int il = (UnsafeAccess.theUnsafe.getByte(obj1, o1 + i) & 0xFF);
949      int ir = (UnsafeAccess.theUnsafe.getByte(obj2, o2 + i) & 0xFF);
950      if (il != ir) {
951        return il - ir;
952      }
953    }
954    return l1 - l2;
955  }
956
957  /**
958   * Reads a short value at the given buffer's offset.
959   * @param buffer
960   * @param offset
961   * @return short value at offset
962   */
963  public static short toShort(ByteBuffer buffer, int offset) {
964    return ConverterHolder.BEST_CONVERTER.toShort(buffer, offset);
965  }
966
967  /**
968   * Reads an int value at the given buffer's current position. Also advances the buffer's position
969   */
970  public static int toInt(ByteBuffer buffer) {
971    return ConverterHolder.BEST_CONVERTER.toInt(buffer);
972  }
973
974  /**
975   * Reads an int value at the given buffer's offset.
976   * @param buffer
977   * @param offset
978   * @return int value at offset
979   */
980  public static int toInt(ByteBuffer buffer, int offset) {
981    return ConverterHolder.BEST_CONVERTER.toInt(buffer, offset);
982  }
983
984  /**
985   * Converts a ByteBuffer to an int value
986   *
987   * @param buf The ByteBuffer
988   * @param offset Offset to int value
989   * @param length Number of bytes used to store the int value.
990   * @return the int value
991   * @throws IllegalArgumentException
992   *           if there's not enough bytes left in the buffer after the given offset
993   */
994  public static int readAsInt(ByteBuffer buf, int offset, final int length) {
995    if (offset + length > buf.limit()) {
996      throw new IllegalArgumentException("offset (" + offset + ") + length (" + length
997          + ") exceed the" + " limit of the buffer: " + buf.limit());
998    }
999    int n = 0;
1000    for(int i = offset; i < (offset + length); i++) {
1001      n <<= 8;
1002      n ^= toByte(buf, i) & 0xFF;
1003    }
1004    return n;
1005  }
1006
1007  /**
1008   * Reads a long value at the given buffer's offset.
1009   * @param buffer
1010   * @param offset
1011   * @return long value at offset
1012   */
1013  public static long toLong(ByteBuffer buffer, int offset) {
1014    return ConverterHolder.BEST_CONVERTER.toLong(buffer, offset);
1015  }
1016
1017  /**
1018   * Put an int value out to the given ByteBuffer's current position in big-endian format.
1019   * This also advances the position in buffer by int size.
1020   * @param buffer the ByteBuffer to write to
1021   * @param val int to write out
1022   */
1023  public static void putInt(ByteBuffer buffer, int val) {
1024    ConverterHolder.BEST_CONVERTER.putInt(buffer, val);
1025  }
1026
1027  public static int putInt(ByteBuffer buffer, int index, int val) {
1028    return ConverterHolder.BEST_CONVERTER.putInt(buffer, index, val);
1029  }
1030
1031  /**
1032   * Reads a double value at the given buffer's offset.
1033   * @param buffer
1034   * @param offset offset where double is
1035   * @return double value at offset
1036   */
1037  public static double toDouble(ByteBuffer buffer, int offset) {
1038    return Double.longBitsToDouble(toLong(buffer, offset));
1039  }
1040
1041  /**
1042   * Reads a BigDecimal value at the given buffer's offset.
1043   * @param buffer
1044   * @param offset
1045   * @return BigDecimal value at offset
1046   */
1047  public static BigDecimal toBigDecimal(ByteBuffer buffer, int offset, int length) {
1048    if (buffer == null || length < Bytes.SIZEOF_INT + 1 ||
1049      (offset + length > buffer.limit())) {
1050      return null;
1051    }
1052
1053    int scale = toInt(buffer, offset);
1054    byte[] tcBytes = new byte[length - Bytes.SIZEOF_INT];
1055    copyFromBufferToArray(tcBytes, buffer, offset + Bytes.SIZEOF_INT, 0, length - Bytes.SIZEOF_INT);
1056    return new BigDecimal(new BigInteger(tcBytes), scale);
1057  }
1058
1059  /**
1060   * Put a short value out to the given ByteBuffer's current position in big-endian format.
1061   * This also advances the position in buffer by short size.
1062   * @param buffer the ByteBuffer to write to
1063   * @param val short to write out
1064   */
1065  public static void putShort(ByteBuffer buffer, short val) {
1066    ConverterHolder.BEST_CONVERTER.putShort(buffer, val);
1067  }
1068
1069  public static int putShort(ByteBuffer buffer, int index, short val) {
1070    return ConverterHolder.BEST_CONVERTER.putShort(buffer, index, val);
1071  }
1072
1073  public static int putAsShort(ByteBuffer buf, int index, int val) {
1074    buf.put(index + 1, (byte) val);
1075    val >>= 8;
1076    buf.put(index, (byte) val);
1077    return index + Bytes.SIZEOF_SHORT;
1078  }
1079
1080  /**
1081   * Put a long value out to the given ByteBuffer's current position in big-endian format.
1082   * This also advances the position in buffer by long size.
1083   * @param buffer the ByteBuffer to write to
1084   * @param val long to write out
1085   */
1086  public static void putLong(ByteBuffer buffer, long val) {
1087    ConverterHolder.BEST_CONVERTER.putLong(buffer, val);
1088  }
1089
1090  public static int putLong(ByteBuffer buffer, int index, long val) {
1091    return ConverterHolder.BEST_CONVERTER.putLong(buffer, index, val);
1092  }
1093
1094  /**
1095   * Copies the bytes from given array's offset to length part into the given buffer. Puts the bytes
1096   * to buffer's current position. This also advances the position in the 'out' buffer by 'length'
1097   * @param out
1098   * @param in
1099   * @param inOffset
1100   * @param length
1101   */
1102  public static void copyFromArrayToBuffer(ByteBuffer out, byte[] in, int inOffset, int length) {
1103    if (out.hasArray()) {
1104      System.arraycopy(in, inOffset, out.array(), out.arrayOffset() + out.position(), length);
1105      // Move the position in out by length
1106      out.position(out.position() + length);
1107    } else if (UNSAFE_AVAIL) {
1108      UnsafeAccess.copy(in, inOffset, out, out.position(), length);
1109      // Move the position in out by length
1110      out.position(out.position() + length);
1111    } else {
1112      out.put(in, inOffset, length);
1113    }
1114  }
1115
1116  /**
1117   * Copies bytes from given array's offset to length part into the given buffer. Puts the bytes
1118   * to buffer's given position. This doesn't affact the position of buffer.
1119   * @param out
1120   * @param in
1121   * @param inOffset
1122   * @param length
1123   */
1124  public static void copyFromArrayToBuffer(ByteBuffer out, int outOffset, byte[] in, int inOffset,
1125      int length) {
1126    if (out.hasArray()) {
1127      System.arraycopy(in, inOffset, out.array(), out.arrayOffset() + outOffset, length);
1128    } else if (UNSAFE_AVAIL) {
1129      UnsafeAccess.copy(in, inOffset, out, outOffset, length);
1130    } else {
1131      ByteBuffer outDup = out.duplicate();
1132      outDup.position(outOffset);
1133      outDup.put(in, inOffset, length);
1134    }
1135  }
1136
1137  /**
1138   * Copies specified number of bytes from given offset of 'in' ByteBuffer to
1139   * the array. This doesn't affact the position of buffer.
1140   * @param out
1141   * @param in
1142   * @param sourceOffset
1143   * @param destinationOffset
1144   * @param length
1145   */
1146  public static void copyFromBufferToArray(byte[] out, ByteBuffer in, int sourceOffset,
1147      int destinationOffset, int length) {
1148    if (in.hasArray()) {
1149      System.arraycopy(in.array(), sourceOffset + in.arrayOffset(), out, destinationOffset, length);
1150    } else if (UNSAFE_AVAIL) {
1151      UnsafeAccess.copy(in, sourceOffset, out, destinationOffset, length);
1152    } else {
1153      ByteBuffer inDup = in.duplicate();
1154      inDup.position(sourceOffset);
1155      inDup.get(out, destinationOffset, length);
1156    }
1157  }
1158
1159  /**
1160   * Similar to  {@link Arrays#copyOfRange(byte[], int, int)}
1161   * @param original the buffer from which the copy has to happen
1162   * @param from the starting index
1163   * @param to the ending index
1164   * @return a byte[] created out of the copy
1165   */
1166  public static byte[] copyOfRange(ByteBuffer original, int from, int to) {
1167    int newLength = to - from;
1168    if (newLength < 0) throw new IllegalArgumentException(from + " > " + to);
1169    byte[] copy = new byte[newLength];
1170    ByteBufferUtils.copyFromBufferToArray(copy, original, from, 0, newLength);
1171    return copy;
1172  }
1173
1174  // For testing purpose
1175  public static String toStringBinary(final ByteBuffer b, int off, int len) {
1176    StringBuilder result = new StringBuilder();
1177    // Just in case we are passed a 'len' that is > buffer length...
1178    if (off >= b.capacity())
1179      return result.toString();
1180    if (off + len > b.capacity())
1181      len = b.capacity() - off;
1182    for (int i = off; i < off + len; ++i) {
1183      int ch = b.get(i) & 0xFF;
1184      if ((ch >= '0' && ch <= '9') || (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')
1185          || " `~!@#$%^&*()-_=+[]{}|;:'\",.<>/?".indexOf(ch) >= 0) {
1186        result.append((char) ch);
1187      } else {
1188        result.append(String.format("\\x%02X", ch));
1189      }
1190    }
1191    return result.toString();
1192  }
1193
1194  public static String toStringBinary(final ByteBuffer b) {
1195    return toStringBinary(b, 0, b.capacity());
1196  }
1197}