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