1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 package org.apache.hadoop.hbase.util.vint;
20
21 import java.io.IOException;
22 import java.io.OutputStream;
23
24 import org.apache.hadoop.hbase.classification.InterfaceAudience;
25 import org.apache.hadoop.hbase.nio.ByteBuff;
26
27 /**
28 * UFInt is an abbreviation for Unsigned Fixed-width Integer.
29 *
30 * This class converts between positive ints and 1-4 bytes that represent the int. All input ints
31 * must be positive. Max values stored in N bytes are:
32 *
33 * N=1: 2^8 => 256
34 * N=2: 2^16 => 65,536
35 * N=3: 2^24 => 16,777,216
36 * N=4: 2^31 => 2,147,483,648 (Integer.MAX_VALUE)
37 *
38 * This was created to get most of the memory savings of a variable length integer when encoding
39 * an array of input integers, but to fix the number of bytes for each integer to the number needed
40 * to store the maximum integer in the array. This enables a binary search to be performed on the
41 * array of encoded integers.
42 *
43 * PrefixTree nodes often store offsets into a block that can fit into 1 or 2 bytes. Note that if
44 * the maximum value of an array of numbers needs 2 bytes, then it's likely that a majority of the
45 * numbers will also require 2 bytes.
46 *
47 * warnings:
48 * * no input validation for max performance
49 * * no negatives
50 */
51 @InterfaceAudience.Private
52 public class UFIntTool {
53
54 private static final int NUM_BITS_IN_LONG = 64;
55
56 public static long maxValueForNumBytes(int numBytes) {
57 return (1L << (numBytes * 8)) - 1;
58 }
59
60 public static int numBytes(final long value) {
61 if (value == 0) {// 0 doesn't work with the formula below
62 return 1;
63 }
64 return (NUM_BITS_IN_LONG + 7 - Long.numberOfLeadingZeros(value)) / 8;
65 }
66
67 public static byte[] getBytes(int outputWidth, final long value) {
68 byte[] bytes = new byte[outputWidth];
69 writeBytes(outputWidth, value, bytes, 0);
70 return bytes;
71 }
72
73 public static void writeBytes(int outputWidth, final long value, byte[] bytes, int offset) {
74 bytes[offset + outputWidth - 1] = (byte) value;
75 for (int i = outputWidth - 2; i >= 0; --i) {
76 bytes[offset + i] = (byte) (value >>> (outputWidth - i - 1) * 8);
77 }
78 }
79
80 private static final long[] MASKS = new long[] {
81 (long) 255,
82 (long) 255 << 8,
83 (long) 255 << 16,
84 (long) 255 << 24,
85 (long) 255 << 32,
86 (long) 255 << 40,
87 (long) 255 << 48,
88 (long) 255 << 56
89 };
90
91 public static void writeBytes(int outputWidth, final long value, OutputStream os) throws IOException {
92 for (int i = outputWidth - 1; i >= 0; --i) {
93 os.write((byte) ((value & MASKS[i]) >>> (8 * i)));
94 }
95 }
96
97 public static long fromBytes(final byte[] bytes) {
98 long value = 0;
99 value |= bytes[0] & 0xff;// these seem to do ok without casting the byte to int
100 for (int i = 1; i < bytes.length; ++i) {
101 value <<= 8;
102 value |= bytes[i] & 0xff;
103 }
104 return value;
105 }
106
107 public static long fromBytes(final ByteBuff buf, final int offset, final int width) {
108 long value = 0;
109 value |= buf.get(offset + 0) & 0xff;// these seem to do ok without casting the byte to int
110 for (int i = 1; i < width; ++i) {
111 value <<= 8;
112 value |= buf.get(i + offset) & 0xff;
113 }
114 return value;
115 }
116
117 }