1/*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 2000,2008 Oracle.  All rights reserved.
5 *
6 * $Id: PackedInteger.java,v 12.5 2008/01/08 20:58:39 bostic Exp $
7 */
8
9package com.sleepycat.util;
10
11/**
12 * Static methods for reading and writing packed integers.
13 *
14 * <p>Note that packed integers are not sorted naturally for a byte-by-byte
15 * comparison because they have a preceding length and are little endian;
16 * therefore, they are typically not used for keys.</p>
17 *
18 * <p>Values in the inclusive range [-119,119] are stored in a single byte.
19 * For values outside that range, the first byte stores the sign and the number
20 * of additional bytes.  The additional bytes store (abs(value) - 119) as an
21 * unsigned little endian integer.</p>
22 *
23 * <p>To read and write packed integer values, call {@link #readInt} and {@link
24 * #writeInt} or for long values {@link #readLong} and {@link #writeLong}.  To
25 * get the length of a packed integer without reading it, call {@link
26 * #getReadIntLength} or {@link #getReadLongLength}.  To get the length of an
27 * unpacked integer without writing it, call {@link #getWriteIntLength} or
28 * {@link #getWriteLongLength}.</p>
29 *
30 * <p>Because the same packed format is used for int and long values, stored
31 * int values may be expanded to long values without introducing a format
32 * incompatibility.  You can treat previously stored packed int values as long
33 * values by calling {@link #readLong} and {@link #getReadLongLength}.</p>
34 *
35 * @author Mark Hayes
36 */
37public class PackedInteger {
38
39    /**
40     * The maximum number of bytes needed to store an int value (5).
41     */
42    public static final int MAX_LENGTH = 5;
43
44    /**
45     * The maximum number of bytes needed to store a long value (9).
46     */
47    public static final int MAX_LONG_LENGTH = 9;
48
49    /**
50     * Reads a packed integer at the given buffer offset and returns it.
51     *
52     * @param buf the buffer to read from.
53     *
54     * @param off the offset in the buffer at which to start reading.
55     *
56     * @return the integer that was read.
57     */
58    public static int readInt(byte[] buf, int off) {
59
60        boolean negative;
61        int byteLen;
62
63        int b1 = buf[off++];
64        if (b1 < -119) {
65            negative = true;
66            byteLen = -b1 - 119;
67        } else if (b1 > 119) {
68            negative = false;
69            byteLen = b1 - 119;
70        } else {
71            return b1;
72        }
73
74        int value = buf[off++] & 0xFF;
75        if (byteLen > 1) {
76            value |= (buf[off++] & 0xFF) << 8;
77            if (byteLen > 2) {
78                value |= (buf[off++] & 0xFF) << 16;
79                if (byteLen > 3) {
80                    value |= (buf[off++] & 0xFF) << 24;
81                }
82            }
83        }
84
85        return negative ? (-value - 119) : (value + 119);
86    }
87
88    /**
89     * Reads a packed long integer at the given buffer offset and returns it.
90     *
91     * @param buf the buffer to read from.
92     *
93     * @param off the offset in the buffer at which to start reading.
94     *
95     * @return the long integer that was read.
96     */
97    public static long readLong(byte[] buf, int off) {
98
99        boolean negative;
100        int byteLen;
101
102        int b1 = buf[off++];
103        if (b1 < -119) {
104            negative = true;
105            byteLen = -b1 - 119;
106        } else if (b1 > 119) {
107            negative = false;
108            byteLen = b1 - 119;
109        } else {
110            return b1;
111        }
112
113        long value = buf[off++] & 0xFFL;
114        if (byteLen > 1) {
115            value |= (buf[off++] & 0xFFL) << 8;
116            if (byteLen > 2) {
117                value |= (buf[off++] & 0xFFL) << 16;
118                if (byteLen > 3) {
119                    value |= (buf[off++] & 0xFFL) << 24;
120                    if (byteLen > 4) {
121                        value |= (buf[off++] & 0xFFL) << 32;
122                        if (byteLen > 5) {
123                            value |= (buf[off++] & 0xFFL) << 40;
124                            if (byteLen > 6) {
125                                value |= (buf[off++] & 0xFFL) << 48;
126                                if (byteLen > 7) {
127                                    value |= (buf[off++] & 0xFFL) << 56;
128                                }
129                            }
130                        }
131                    }
132                }
133            }
134        }
135
136        return negative ? (-value - 119) : (value + 119);
137    }
138
139    /**
140     * Returns the number of bytes that would be read by {@link #readInt}.
141     *
142     * <p>Because the length is stored in the first byte, this method may be
143     * called with only the first byte of the packed integer in the given
144     * buffer.  This method only accesses one byte at the given offset.</p>
145     *
146     * @param buf the buffer to read from.
147     *
148     * @param off the offset in the buffer at which to start reading.
149     *
150     * @return the number of bytes that would be read.
151     */
152    public static int getReadIntLength(byte[] buf, int off) {
153
154        int b1 = buf[off];
155        if (b1 < -119) {
156            return -b1 - 119 + 1;
157        } else if (b1 > 119) {
158            return b1 - 119 + 1;
159        } else {
160            return 1;
161        }
162    }
163
164    /**
165     * Returns the number of bytes that would be read by {@link #readLong}.
166     *
167     * <p>Because the length is stored in the first byte, this method may be
168     * called with only the first byte of the packed integer in the given
169     * buffer.  This method only accesses one byte at the given offset.</p>
170     *
171     * @param buf the buffer to read from.
172     *
173     * @param off the offset in the buffer at which to start reading.
174     *
175     * @return the number of bytes that would be read.
176     */
177    public static int getReadLongLength(byte[] buf, int off) {
178
179        /* The length is stored in the same way for int and long. */
180        return getReadIntLength(buf, off);
181    }
182
183    /**
184     * Writes a packed integer starting at the given buffer offset and returns
185     * the next offset to be written.
186     *
187     * @param buf the buffer to write to.
188     *
189     * @param offset the offset in the buffer at which to start writing.
190     *
191     * @param value the integer to be written.
192     *
193     * @return the offset past the bytes written.
194     */
195    public static int writeInt(byte[] buf, int offset, int value) {
196
197        int byte1Off = offset;
198        boolean negative;
199
200        if (value < -119) {
201            negative = true;
202            value = -value - 119;
203        } else if (value > 119) {
204            negative = false;
205            value = value - 119;
206        } else {
207            buf[offset++] = (byte) value;
208            return offset;
209        }
210        offset++;
211
212        buf[offset++] = (byte) value;
213        if ((value & 0xFFFFFF00) == 0) {
214            buf[byte1Off] = negative ? (byte) -120 : (byte) 120;
215            return offset;
216        }
217
218        buf[offset++] = (byte) (value >>> 8);
219        if ((value & 0xFFFF0000) == 0) {
220            buf[byte1Off] = negative ? (byte) -121 : (byte) 121;
221            return offset;
222        }
223
224        buf[offset++] = (byte) (value >>> 16);
225        if ((value & 0xFF000000) == 0) {
226            buf[byte1Off] = negative ? (byte) -122 : (byte) 122;
227            return offset;
228        }
229
230        buf[offset++] = (byte) (value >>> 24);
231        buf[byte1Off] = negative ? (byte) -123 : (byte) 123;
232        return offset;
233    }
234
235    /**
236     * Writes a packed long integer starting at the given buffer offset and
237     * returns the next offset to be written.
238     *
239     * @param buf the buffer to write to.
240     *
241     * @param offset the offset in the buffer at which to start writing.
242     *
243     * @param value the long integer to be written.
244     *
245     * @return the offset past the bytes written.
246     */
247    public static int writeLong(byte[] buf, int offset, long value) {
248
249        int byte1Off = offset;
250        boolean negative;
251
252        if (value < -119) {
253            negative = true;
254            value = -value - 119;
255        } else if (value > 119) {
256            negative = false;
257            value = value - 119;
258        } else {
259            buf[offset++] = (byte) value;
260            return offset;
261        }
262        offset++;
263
264        buf[offset++] = (byte) value;
265        if ((value & 0xFFFFFFFFFFFFFF00L) == 0) {
266            buf[byte1Off] = negative ? (byte) -120 : (byte) 120;
267            return offset;
268        }
269
270        buf[offset++] = (byte) (value >>> 8);
271        if ((value & 0xFFFFFFFFFFFF0000L) == 0) {
272            buf[byte1Off] = negative ? (byte) -121 : (byte) 121;
273            return offset;
274        }
275
276        buf[offset++] = (byte) (value >>> 16);
277        if ((value & 0xFFFFFFFFFF000000L) == 0) {
278            buf[byte1Off] = negative ? (byte) -122 : (byte) 122;
279            return offset;
280        }
281
282        buf[offset++] = (byte) (value >>> 24);
283        if ((value & 0xFFFFFFFF00000000L) == 0) {
284            buf[byte1Off] = negative ? (byte) -123 : (byte) 123;
285            return offset;
286        }
287
288        buf[offset++] = (byte) (value >>> 32);
289        if ((value & 0xFFFFFF0000000000L) == 0) {
290            buf[byte1Off] = negative ? (byte) -124 : (byte) 124;
291            return offset;
292        }
293
294        buf[offset++] = (byte) (value >>> 40);
295        if ((value & 0xFFFF000000000000L) == 0) {
296            buf[byte1Off] = negative ? (byte) -125 : (byte) 125;
297            return offset;
298        }
299
300        buf[offset++] = (byte) (value >>> 48);
301        if ((value & 0xFF00000000000000L) == 0) {
302            buf[byte1Off] = negative ? (byte) -126 : (byte) 126;
303            return offset;
304        }
305
306        buf[offset++] = (byte) (value >>> 56);
307        buf[byte1Off] = negative ? (byte) -127 : (byte) 127;
308        return offset;
309    }
310
311    /**
312     * Returns the number of bytes that would be written by {@link #writeInt}.
313     *
314     * @param value the integer to be written.
315     *
316     * @return the number of bytes that would be used to write the given
317     * integer.
318     */
319    public static int getWriteIntLength(int value) {
320
321        if (value < -119) {
322            value = -value - 119;
323        } else if (value > 119) {
324            value = value - 119;
325        } else {
326            return 1;
327        }
328
329        if ((value & 0xFFFFFF00) == 0) {
330            return 2;
331        }
332        if ((value & 0xFFFF0000) == 0) {
333            return 3;
334        }
335        if ((value & 0xFF000000) == 0) {
336            return 4;
337        }
338        return 5;
339    }
340
341    /**
342     * Returns the number of bytes that would be written by {@link #writeLong}.
343     *
344     * @param value the long integer to be written.
345     *
346     * @return the number of bytes that would be used to write the given long
347     * integer.
348     */
349    public static int getWriteLongLength(long value) {
350
351        if (value < -119) {
352            value = -value - 119;
353        } else if (value > 119) {
354            value = value - 119;
355        } else {
356            return 1;
357        }
358
359        if ((value & 0xFFFFFFFFFFFFFF00L) == 0) {
360            return 2;
361        }
362        if ((value & 0xFFFFFFFFFFFF0000L) == 0) {
363            return 3;
364        }
365        if ((value & 0xFFFFFFFFFF000000L) == 0) {
366            return 4;
367        }
368        if ((value & 0xFFFFFFFF00000000L) == 0) {
369            return 5;
370        }
371        if ((value & 0xFFFFFF0000000000L) == 0) {
372            return 6;
373        }
374        if ((value & 0xFFFF000000000000L) == 0) {
375            return 7;
376        }
377        if ((value & 0xFF00000000000000L) == 0) {
378            return 8;
379        }
380        return 9;
381    }
382}
383