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