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