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