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