View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements. See the NOTICE file distributed with this
4    * work for additional information regarding copyright ownership. The ASF
5    * licenses this file to you under the Apache License, Version 2.0 (the
6    * "License"); you may not use this file except in compliance with the License.
7    * You may obtain a copy of the License at
8    *
9    * http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
13   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
14   * License for the specific language governing permissions and limitations
15   * under the License.
16   */
17  package org.apache.hadoop.hbase.util;
18  
19  import java.io.ByteArrayOutputStream;
20  import java.io.DataInputStream;
21  import java.io.IOException;
22  import java.io.InputStream;
23  import java.io.OutputStream;
24  import java.nio.ByteBuffer;
25  
26  import org.apache.hadoop.hbase.classification.InterfaceAudience;
27  import org.apache.hadoop.hbase.classification.InterfaceStability;
28  import org.apache.hadoop.io.IOUtils;
29  import org.apache.hadoop.io.WritableUtils;
30  
31  /**
32   * Utility functions for working with byte buffers, such as reading/writing
33   * variable-length long numbers.
34   */
35  @InterfaceAudience.Public
36  @InterfaceStability.Evolving
37  public final class ByteBufferUtils {
38  
39    // "Compressed integer" serialization helper constants.
40    private final static int VALUE_MASK = 0x7f;
41    private final static int NEXT_BIT_SHIFT = 7;
42    private final static int NEXT_BIT_MASK = 1 << 7;
43    private static final boolean UNSAFE_AVAIL = UnsafeAccess.isAvailable();
44    private static final boolean UNSAFE_UNALIGNED = UnsafeAccess.unaligned();
45  
46    private ByteBufferUtils() {
47    }
48  
49    /**
50     * Similar to {@link WritableUtils#writeVLong(java.io.DataOutput, long)},
51     * but writes to a {@link ByteBuffer}.
52     */
53    public static void writeVLong(ByteBuffer out, long i) {
54      if (i >= -112 && i <= 127) {
55        out.put((byte) i);
56        return;
57      }
58  
59      int len = -112;
60      if (i < 0) {
61        i ^= -1L; // take one's complement
62        len = -120;
63      }
64  
65      long tmp = i;
66      while (tmp != 0) {
67        tmp = tmp >> 8;
68        len--;
69      }
70  
71      out.put((byte) len);
72  
73      len = (len < -120) ? -(len + 120) : -(len + 112);
74  
75      for (int idx = len; idx != 0; idx--) {
76        int shiftbits = (idx - 1) * 8;
77        long mask = 0xFFL << shiftbits;
78        out.put((byte) ((i & mask) >> shiftbits));
79      }
80    }
81  
82    /**
83     * Similar to {@link WritableUtils#readVLong(DataInput)} but reads from a
84     * {@link ByteBuffer}.
85     */
86    public static long readVLong(ByteBuffer in) {
87      byte firstByte = in.get();
88      int len = WritableUtils.decodeVIntSize(firstByte);
89      if (len == 1) {
90        return firstByte;
91      }
92      long i = 0;
93      for (int idx = 0; idx < len-1; idx++) {
94        byte b = in.get();
95        i = i << 8;
96        i = i | (b & 0xFF);
97      }
98      return (WritableUtils.isNegativeVInt(firstByte) ? (i ^ -1L) : i);
99    }
100 
101 
102   /**
103    * Put in buffer integer using 7 bit encoding. For each written byte:
104    * 7 bits are used to store value
105    * 1 bit is used to indicate whether there is next bit.
106    * @param value Int to be compressed.
107    * @param out Where to put compressed data
108    * @return Number of bytes written.
109    * @throws IOException on stream error
110    */
111    public static int putCompressedInt(OutputStream out, final int value)
112       throws IOException {
113     int i = 0;
114     int tmpvalue = value;
115     do {
116       byte b = (byte) (tmpvalue & VALUE_MASK);
117       tmpvalue >>>= NEXT_BIT_SHIFT;
118       if (tmpvalue != 0) {
119         b |= (byte) NEXT_BIT_MASK;
120       }
121       out.write(b);
122       i++;
123     } while (tmpvalue != 0);
124     return i;
125   }
126 
127    /**
128     * Put in output stream 32 bit integer (Big Endian byte order).
129     * @param out Where to put integer.
130     * @param value Value of integer.
131     * @throws IOException On stream error.
132     */
133    public static void putInt(OutputStream out, final int value)
134        throws IOException {
135      for (int i = Bytes.SIZEOF_INT - 1; i >= 0; --i) {
136        out.write((byte) (value >>> (i * 8)));
137      }
138    }
139 
140   /**
141    * Copy the data to the output stream and update position in buffer.
142    * @param out the stream to write bytes to
143    * @param in the buffer to read bytes from
144    * @param length the number of bytes to copy
145    */
146   public static void moveBufferToStream(OutputStream out, ByteBuffer in,
147       int length) throws IOException {
148     copyBufferToStream(out, in, in.position(), length);
149     skip(in, length);
150   }
151 
152   /**
153    * Copy data from a buffer to an output stream. Does not update the position
154    * in the buffer.
155    * @param out the stream to write bytes to
156    * @param in the buffer to read bytes from
157    * @param offset the offset in the buffer (from the buffer's array offset)
158    *      to start copying bytes from
159    * @param length the number of bytes to copy
160    */
161   public static void copyBufferToStream(OutputStream out, ByteBuffer in,
162       int offset, int length) throws IOException {
163     if (in.hasArray()) {
164       out.write(in.array(), in.arrayOffset() + offset,
165           length);
166     } else {
167       for (int i = 0; i < length; ++i) {
168         out.write(in.get(offset + i));
169       }
170     }
171   }
172 
173   public static int putLong(OutputStream out, final long value,
174       final int fitInBytes) throws IOException {
175     long tmpValue = value;
176     for (int i = 0; i < fitInBytes; ++i) {
177       out.write((byte) (tmpValue & 0xff));
178       tmpValue >>>= 8;
179     }
180     return fitInBytes;
181   }
182 
183   /**
184    * Check how many bytes are required to store value.
185    * @param value Value which size will be tested.
186    * @return How many bytes are required to store value.
187    */
188   public static int longFitsIn(final long value) {
189     if (value < 0) {
190       return 8;
191     }
192 
193     if (value < (1l << 4 * 8)) {
194       // no more than 4 bytes
195       if (value < (1l << 2 * 8)) {
196         if (value < (1l << 1 * 8)) {
197           return 1;
198         }
199         return 2;
200       }
201       if (value < (1l << 3 * 8)) {
202         return 3;
203       }
204       return 4;
205     }
206     // more than 4 bytes
207     if (value < (1l << 6 * 8)) {
208       if (value < (1l << 5 * 8)) {
209         return 5;
210       }
211       return 6;
212     }
213     if (value < (1l << 7 * 8)) {
214       return 7;
215     }
216     return 8;
217   }
218 
219   /**
220    * Check how many bytes is required to store value.
221    * @param value Value which size will be tested.
222    * @return How many bytes are required to store value.
223    */
224   public static int intFitsIn(final int value) {
225     if (value < 0) {
226       return 4;
227     }
228 
229     if (value < (1 << 2 * 8)) {
230       if (value < (1 << 1 * 8)) {
231         return 1;
232       }
233       return 2;
234     }
235     if (value <= (1 << 3 * 8)) {
236       return 3;
237     }
238     return 4;
239   }
240 
241   /**
242    * Read integer from stream coded in 7 bits and increment position.
243    * @return the integer that has been read
244    * @throws IOException
245    */
246   public static int readCompressedInt(InputStream input)
247       throws IOException {
248     int result = 0;
249     int i = 0;
250     byte b;
251     do {
252       b = (byte) input.read();
253       result += (b & VALUE_MASK) << (NEXT_BIT_SHIFT * i);
254       i++;
255       if (i > Bytes.SIZEOF_INT + 1) {
256         throw new IllegalStateException(
257             "Corrupted compressed int (too long: " + (i + 1) + " bytes)");
258       }
259     } while (0 != (b & NEXT_BIT_MASK));
260     return result;
261   }
262 
263   /**
264    * Read integer from buffer coded in 7 bits and increment position.
265    * @return Read integer.
266    */
267   public static int readCompressedInt(ByteBuffer buffer) {
268     byte b = buffer.get();
269     if ((b & NEXT_BIT_MASK) != 0) {
270       return (b & VALUE_MASK) + (readCompressedInt(buffer) << NEXT_BIT_SHIFT);
271     }
272     return b & VALUE_MASK;
273   }
274 
275   /**
276    * Read long which was written to fitInBytes bytes and increment position.
277    * @param fitInBytes In how many bytes given long is stored.
278    * @return The value of parsed long.
279    * @throws IOException
280    */
281   public static long readLong(InputStream in, final int fitInBytes)
282       throws IOException {
283     long tmpLong = 0;
284     for (int i = 0; i < fitInBytes; ++i) {
285       tmpLong |= (in.read() & 0xffl) << (8 * i);
286     }
287     return tmpLong;
288   }
289 
290   /**
291    * Read long which was written to fitInBytes bytes and increment position.
292    * @param fitInBytes In how many bytes given long is stored.
293    * @return The value of parsed long.
294    */
295   public static long readLong(ByteBuffer in, final int fitInBytes) {
296     long tmpLength = 0;
297     for (int i = 0; i < fitInBytes; ++i) {
298       tmpLength |= (in.get() & 0xffl) << (8l * i);
299     }
300     return tmpLength;
301   }
302 
303   /**
304    * Copy the given number of bytes from the given stream and put it at the
305    * current position of the given buffer, updating the position in the buffer.
306    * @param out the buffer to write data to
307    * @param in the stream to read data from
308    * @param length the number of bytes to read/write
309    */
310   public static void copyFromStreamToBuffer(ByteBuffer out,
311       DataInputStream in, int length) throws IOException {
312     if (out.hasArray()) {
313       in.readFully(out.array(), out.position() + out.arrayOffset(),
314           length);
315       skip(out, length);
316     } else {
317       for (int i = 0; i < length; ++i) {
318         out.put(in.readByte());
319       }
320     }
321   }
322 
323   /**
324    * Copy from the InputStream to a new heap ByteBuffer until the InputStream is exhausted.
325    */
326   public static ByteBuffer drainInputStreamToBuffer(InputStream is) throws IOException {
327     ByteArrayOutputStream baos = new ByteArrayOutputStream(4096);
328     IOUtils.copyBytes(is, baos, 4096, true);
329     ByteBuffer buffer = ByteBuffer.wrap(baos.toByteArray());
330     buffer.rewind();
331     return buffer;
332   }
333 
334   /**
335    * Copy from one buffer to another from given offset.
336    * <p>
337    * Note : This will advance the position marker of {@code out} but not change the position maker
338    * for {@code in}
339    * @param out destination buffer
340    * @param in source buffer
341    * @param sourceOffset offset in the source buffer
342    * @param length how many bytes to copy
343    */
344   public static void copyFromBufferToBuffer(ByteBuffer out,
345       ByteBuffer in, int sourceOffset, int length) {
346     if (in.hasArray() && out.hasArray()) {
347       System.arraycopy(in.array(), sourceOffset + in.arrayOffset(),
348           out.array(), out.position() +
349           out.arrayOffset(), length);
350       skip(out, length);
351     } else {
352       for (int i = 0; i < length; ++i) {
353         out.put(in.get(sourceOffset + i));
354       }
355     }
356   }
357 
358   /**
359    * Copy from one buffer to another from given offset. This will be absolute positional copying and
360    * won't affect the position of any of the buffers.
361    * @param out
362    * @param in
363    * @param sourceOffset
364    * @param destinationOffset
365    * @param length
366    */
367   public static void copyFromBufferToBuffer(ByteBuffer out, ByteBuffer in, int sourceOffset,
368       int destinationOffset, int length) {
369     if (in.hasArray() && out.hasArray()) {
370       System.arraycopy(in.array(), sourceOffset + in.arrayOffset(), out.array(), out.arrayOffset()
371           + destinationOffset, length);
372     } else {
373       for (int i = 0; i < length; ++i) {
374         out.put((destinationOffset + i), in.get(sourceOffset + i));
375       }
376     }
377   }
378 
379   /**
380    * Find length of common prefix of two parts in the buffer
381    * @param buffer Where parts are located.
382    * @param offsetLeft Offset of the first part.
383    * @param offsetRight Offset of the second part.
384    * @param limit Maximal length of common prefix.
385    * @return Length of prefix.
386    */
387   public static int findCommonPrefix(ByteBuffer buffer, int offsetLeft,
388       int offsetRight, int limit) {
389     int prefix = 0;
390 
391     for (; prefix < limit; ++prefix) {
392       if (buffer.get(offsetLeft + prefix) != buffer.get(offsetRight + prefix)) {
393         break;
394       }
395     }
396 
397     return prefix;
398   }
399 
400   /**
401    * Find length of common prefix in two arrays.
402    * @param left Array to be compared.
403    * @param leftOffset Offset in left array.
404    * @param leftLength Length of left array.
405    * @param right Array to be compared.
406    * @param rightOffset Offset in right array.
407    * @param rightLength Length of right array.
408    */
409   public static int findCommonPrefix(
410       byte[] left, int leftOffset, int leftLength,
411       byte[] right, int rightOffset, int rightLength) {
412     int length = Math.min(leftLength, rightLength);
413     int result = 0;
414 
415     while (result < length &&
416         left[leftOffset + result] == right[rightOffset + result]) {
417       result++;
418     }
419 
420     return result;
421   }
422 
423   /**
424    * Check whether two parts in the same buffer are equal.
425    * @param buffer In which buffer there are parts
426    * @param offsetLeft Beginning of first part.
427    * @param lengthLeft Length of the first part.
428    * @param offsetRight Beginning of the second part.
429    * @param lengthRight Length of the second part.
430    * @return True if equal
431    */
432   public static boolean arePartsEqual(ByteBuffer buffer,
433       int offsetLeft, int lengthLeft,
434       int offsetRight, int lengthRight) {
435     if (lengthLeft != lengthRight) {
436       return false;
437     }
438 
439     if (buffer.hasArray()) {
440       return 0 == Bytes.compareTo(
441           buffer.array(), buffer.arrayOffset() + offsetLeft, lengthLeft,
442           buffer.array(), buffer.arrayOffset() + offsetRight, lengthRight);
443     }
444 
445     for (int i = 0; i < lengthRight; ++i) {
446       if (buffer.get(offsetLeft + i) != buffer.get(offsetRight + i)) {
447         return false;
448       }
449     }
450     return true;
451   }
452 
453   /**
454    * Increment position in buffer.
455    * @param buffer In this buffer.
456    * @param length By that many bytes.
457    */
458   public static void skip(ByteBuffer buffer, int length) {
459     buffer.position(buffer.position() + length);
460   }
461 
462   public static void extendLimit(ByteBuffer buffer, int numBytes) {
463     buffer.limit(buffer.limit() + numBytes);
464   }
465 
466   /**
467    * Copy the bytes from position to limit into a new byte[] of the exact length and sets the
468    * position and limit back to their original values (though not thread safe).
469    * @param buffer copy from here
470    * @param startPosition put buffer.get(startPosition) into byte[0]
471    * @return a new byte[] containing the bytes in the specified range
472    */
473   public static byte[] toBytes(ByteBuffer buffer, int startPosition) {
474     int originalPosition = buffer.position();
475     byte[] output = new byte[buffer.limit() - startPosition];
476     buffer.position(startPosition);
477     buffer.get(output);
478     buffer.position(originalPosition);
479     return output;
480   }
481 
482   /**
483    * Copy the given number of bytes from specified offset into a new byte[]
484    * @param buffer
485    * @param offset
486    * @param length
487    * @return a new byte[] containing the bytes in the specified range
488    */
489   public static byte[] toBytes(ByteBuffer buffer, int offset, int length) {
490     byte[] output = new byte[length];
491     for (int i = 0; i < length; i++) {
492       output[i] = buffer.get(offset + i);
493     }
494     return output;
495   }
496 
497   public static int compareTo(ByteBuffer buf1, int o1, int len1, ByteBuffer buf2, int o2, int len2) {
498     if (buf1.hasArray() && buf2.hasArray()) {
499       return Bytes.compareTo(buf1.array(), buf1.arrayOffset() + o1, len1, buf2.array(),
500           buf2.arrayOffset() + o2, len2);
501     }
502     int end1 = o1 + len1;
503     int end2 = o2 + len2;
504     for (int i = o1, j = o2; i < end1 && j < end2; i++, j++) {
505       int a = buf1.get(i) & 0xFF;
506       int b = buf2.get(j) & 0xFF;
507       if (a != b) {
508         return a - b;
509       }
510     }
511     return len1 - len2;
512   }
513 
514   /**
515    * Copies specified number of bytes from given offset of 'in' ByteBuffer to
516    * the array.
517    * @param out
518    * @param in
519    * @param sourceOffset
520    * @param destinationOffset
521    * @param length
522    */
523   public static void copyFromBufferToArray(byte[] out, ByteBuffer in, int sourceOffset,
524       int destinationOffset, int length) {
525     if (in.hasArray()) {
526       System.arraycopy(in.array(), sourceOffset + in.arrayOffset(), out, destinationOffset, length);
527     } else if (UNSAFE_AVAIL) {
528       UnsafeAccess.copy(in, sourceOffset, out, destinationOffset, length);
529     } else {
530       int oldPos = in.position();
531       in.position(sourceOffset);
532       in.get(out, destinationOffset, length);
533       in.position(oldPos);
534     }
535   }
536 }