common/db_compint.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996-2009 Oracle.  All rights reserved.
   5  */
   6
   7 #include "db_config.h"
   8
   9 #include "db_int.h"
  10
  11 #ifdef HAVE_COMPRESSION
  12
  13 /*
  14  * Integer compression
  15  *
  16  *  First byte | Next | Maximum
  17  *  byte       | bytes| value
  18  * ------------+------+---------------------------------------------------------
  19  * [0 xxxxxxx] | 0    | 2^7 - 1
  20  * [10 xxxxxx] | 1    | 2^14 + 2^7 - 1
  21  * [110 xxxxx] | 2    | 2^21 + 2^14 + 2^7 - 1
  22  * [1110 xxxx] | 3    | 2^28 + 2^21 + 2^14 + 2^7 - 1
  23  * [11110 xxx] | 4    | 2^35 + 2^28 + 2^21 + 2^14 + 2^7 - 1
  24  * [11111 000] | 5    | 2^40 + 2^35 + 2^28 + 2^21 + 2^14 + 2^7 - 1
  25  * [11111 001] | 6    | 2^48 + 2^40 + 2^35 + 2^28 + 2^21 + 2^14 + 2^7 - 1
  26  * [11111 010] | 7    | 2^56 + 2^48 + 2^40 + 2^35 + 2^28 + 2^21 + 2^14 + 2^7 - 1
  27  * [11111 011] | 8    | 2^64 + 2^56 + 2^48 + 2^40 + 2^35 + 2^28 + 2^21 + 2^14 +
  28  *             |      | 2^7 - 1
  29  *
  30  * NOTE: this compression algorithm depends
  31  * on big-endian order, so swap if necessary.
  32  *
  33  */
  34
  35 #define CMP_INT_1BYTE_MAX 0x7F
  36 #define CMP_INT_2BYTE_MAX 0x407F
  37 #define CMP_INT_3BYTE_MAX 0x20407F
  38 #define CMP_INT_4BYTE_MAX 0x1020407F
  39
  40 #if defined(_MSC_VER) && _MSC_VER < 1300
  41 #define CMP_INT_5BYTE_MAX 0x081020407Fi64
  42 #define CMP_INT_6BYTE_MAX 0x01081020407Fi64
  43 #define CMP_INT_7BYTE_MAX 0x0101081020407Fi64
  44 #define CMP_INT_8BYTE_MAX 0x010101081020407Fi64
  45 #else
  46 #define CMP_INT_5BYTE_MAX 0x081020407FLL
  47 #define CMP_INT_6BYTE_MAX 0x01081020407FLL
  48 #define CMP_INT_7BYTE_MAX 0x0101081020407FLL
  49 #define CMP_INT_8BYTE_MAX 0x010101081020407FLL
  50 #endif
  51
  52 #define CMP_INT_2BYTE_VAL 0x80
  53 #define CMP_INT_3BYTE_VAL 0xC0
  54 #define CMP_INT_4BYTE_VAL 0xE0
  55 #define CMP_INT_5BYTE_VAL 0xF0
  56 #define CMP_INT_6BYTE_VAL 0xF8
  57 #define CMP_INT_7BYTE_VAL 0xF9
  58 #define CMP_INT_8BYTE_VAL 0xFA
  59 #define CMP_INT_9BYTE_VAL 0xFB
  60 /* CMP_INT_SPARE_VAL is defined in db_int.h */
  61
  62 #define CMP_INT_2BYTE_MASK 0x3F
  63 #define CMP_INT_3BYTE_MASK 0x1F
  64 #define CMP_INT_4BYTE_MASK 0x0F
  65 #define CMP_INT_5BYTE_MASK 0x07
  66
  67 static const u_int8_t __db_marshaled_int_size[] = {
  68         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  69         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  70         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  71         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  72         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  73         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  74         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  75         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  76         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  77         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  78         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  79         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  80         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  81         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  82         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  83         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  84
  85         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  86         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  87         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  88         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  89         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  90         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  91         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  92         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  93
  94         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  95         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  96         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  97         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  98
  99         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
 100         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
 101
 102         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
 103         0x06, 0x07, 0x08, 0x09, 0xFF, 0xFF, 0xFF, 0xFF
 104 };
 105
 106 /*
 107  * __db_compress_count_int --
 108  *      Return the number of bytes that the compressed version
 109  *      of the argument will occupy.
 110  *
 111  * PUBLIC: u_int32_t __db_compress_count_int __P((u_int64_t));
 112  */
 113 u_int32_t
 114 __db_compress_count_int(i)
 115         u_int64_t i;
 116 {
 117         if (i <= CMP_INT_1BYTE_MAX)
 118                 return 1;
 119         else if (i <= CMP_INT_2BYTE_MAX)
 120                 return 2;
 121         else if (i <= CMP_INT_3BYTE_MAX)
 122                 return 3;
 123         else if (i <= CMP_INT_4BYTE_MAX)
 124                 return 4;
 125         else if (i <= CMP_INT_5BYTE_MAX)
 126                 return 5;
 127         else if (i <= CMP_INT_6BYTE_MAX)
 128                 return 6;
 129         else if (i <= CMP_INT_7BYTE_MAX)
 130                 return 7;
 131         else if (i <= CMP_INT_8BYTE_MAX)
 132                 return 8;
 133         else
 134                 return 9;
 135 }
 136
 137 /*
 138  * __db_compress_int --
 139  *      Compresses the integer into the buffer, returning the number of
 140  *      bytes occupied.
 141  *
 142  * PUBLIC: int __db_compress_int __P((u_int8_t *, u_int64_t));
 143  */
 144 int
 145 __db_compress_int(buf, i)
 146         u_int8_t *buf;
 147         u_int64_t i;
 148 {
 149         if (i <= CMP_INT_1BYTE_MAX) {
 150                 /* no swapping for one byte value */
 151                 buf[0] = (u_int8_t)i;
 152                 return 1;
 153         } else {
 154                 u_int8_t *p = (u_int8_t*)&i;
 155                 if (i <= CMP_INT_2BYTE_MAX) {
 156                         i -= CMP_INT_1BYTE_MAX + 1;
 157                         if (__db_isbigendian() != 0) {
 158                                 buf[0] = p[6] | CMP_INT_2BYTE_VAL;
 159                                 buf[1] = p[7];
 160                         } else {
 161                                 buf[0] = p[1] | CMP_INT_2BYTE_VAL;
 162                                 buf[1] = p[0];
 163                         }
 164                         return 2;
 165                 } else if (i <= CMP_INT_3BYTE_MAX) {
 166                         i -= CMP_INT_2BYTE_MAX + 1;
 167                         if (__db_isbigendian() != 0) {
 168                                 buf[0] = p[5] | CMP_INT_3BYTE_VAL;
 169                                 buf[1] = p[6];
 170                                 buf[2] = p[7];
 171                         } else {
 172                                 buf[0] = p[2] | CMP_INT_3BYTE_VAL;
 173                                 buf[1] = p[1];
 174                                 buf[2] = p[0];
 175                         }
 176                         return 3;
 177                 } else if (i <= CMP_INT_4BYTE_MAX) {
 178                         i -= CMP_INT_3BYTE_MAX + 1;
 179                         if (__db_isbigendian() != 0) {
 180                                 buf[0] = p[4] | CMP_INT_4BYTE_VAL;
 181                                 buf[1] = p[5];
 182                                 buf[2] = p[6];
 183                                 buf[3] = p[7];
 184                         } else {
 185                                 buf[0] = p[3] | CMP_INT_4BYTE_VAL;
 186                                 buf[1] = p[2];
 187                                 buf[2] = p[1];
 188                                 buf[3] = p[0];
 189                         }
 190                         return 4;
 191                 } else if (i <= CMP_INT_5BYTE_MAX) {
 192                         i -= CMP_INT_4BYTE_MAX + 1;
 193                         if (__db_isbigendian() != 0) {
 194                                 buf[0] = p[3] | CMP_INT_5BYTE_VAL;
 195                                 buf[1] = p[4];
 196                                 buf[2] = p[5];
 197                                 buf[3] = p[6];
 198                                 buf[4] = p[7];
 199                         } else {
 200                                 buf[0] = p[4] | CMP_INT_5BYTE_VAL;
 201                                 buf[1] = p[3];
 202                                 buf[2] = p[2];
 203                                 buf[3] = p[1];
 204                                 buf[4] = p[0];
 205                         }
 206                         return 5;
 207                 } else if (i <= CMP_INT_6BYTE_MAX) {
 208                         i -= CMP_INT_5BYTE_MAX + 1;
 209                         if (__db_isbigendian() != 0) {
 210                                 buf[0] = CMP_INT_6BYTE_VAL;
 211                                 buf[1] = p[3];
 212                                 buf[2] = p[4];
 213                                 buf[3] = p[5];
 214                                 buf[4] = p[6];
 215                                 buf[5] = p[7];
 216                         } else {
 217                                 buf[0] = CMP_INT_6BYTE_VAL;
 218                                 buf[1] = p[4];
 219                                 buf[2] = p[3];
 220                                 buf[3] = p[2];
 221                                 buf[4] = p[1];
 222                                 buf[5] = p[0];
 223                         }
 224                         return 6;
 225                 } else if (i <= CMP_INT_7BYTE_MAX) {
 226                         i -= CMP_INT_6BYTE_MAX + 1;
 227                         if (__db_isbigendian() != 0) {
 228                                 buf[0] = CMP_INT_7BYTE_VAL;
 229                                 buf[1] = p[2];
 230                                 buf[2] = p[3];
 231                                 buf[3] = p[4];
 232                                 buf[4] = p[5];
 233                                 buf[5] = p[6];
 234                                 buf[6] = p[7];
 235                         } else {
 236                                 buf[0] = CMP_INT_7BYTE_VAL;
 237                                 buf[1] = p[5];
 238                                 buf[2] = p[4];
 239                                 buf[3] = p[3];
 240                                 buf[4] = p[2];
 241                                 buf[5] = p[1];
 242                                 buf[6] = p[0];
 243                         }
 244                         return 7;
 245                 } else if (i <= CMP_INT_8BYTE_MAX) {
 246                         i -= CMP_INT_7BYTE_MAX + 1;
 247                         if (__db_isbigendian() != 0) {
 248                                 buf[0] = CMP_INT_8BYTE_VAL;
 249                                 buf[1] = p[1];
 250                                 buf[2] = p[2];
 251                                 buf[3] = p[3];
 252                                 buf[4] = p[4];
 253                                 buf[5] = p[5];
 254                                 buf[6] = p[6];
 255                                 buf[7] = p[7];
 256                         } else {
 257                                 buf[0] = CMP_INT_8BYTE_VAL;
 258                                 buf[1] = p[6];
 259                                 buf[2] = p[5];
 260                                 buf[3] = p[4];
 261                                 buf[4] = p[3];
 262                                 buf[5] = p[2];
 263                                 buf[6] = p[1];
 264                                 buf[7] = p[0];
 265                         }
 266                         return 8;
 267                 } else {
 268                         i -= CMP_INT_8BYTE_MAX + 1;
 269                         if (__db_isbigendian() != 0) {
 270                                 buf[0] = CMP_INT_9BYTE_VAL;
 271                                 buf[1] = p[0];
 272                                 buf[2] = p[1];
 273                                 buf[3] = p[2];
 274                                 buf[4] = p[3];
 275                                 buf[5] = p[4];
 276                                 buf[6] = p[5];
 277                                 buf[7] = p[6];
 278                                 buf[8] = p[7];
 279                         } else {
 280                                 buf[0] = CMP_INT_9BYTE_VAL;
 281                                 buf[1] = p[7];
 282                                 buf[2] = p[6];
 283                                 buf[3] = p[5];
 284                                 buf[4] = p[4];
 285                                 buf[5] = p[3];
 286                                 buf[6] = p[2];
 287                                 buf[7] = p[1];
 288                                 buf[8] = p[0];
 289                         }
 290                         return 9;
 291                 }
 292         }
 293 }
 294
 295 /*
 296  * __db_decompress_count_int --
 297  *      Return the number of bytes occupied by the compressed
 298  *      integer pointed to by buf.
 299  *
 300  * PUBLIC: u_int32_t __db_decompress_count_int __P((const u_int8_t *));
 301  */
 302 u_int32_t
 303 __db_decompress_count_int(buf)
 304         const u_int8_t *buf;
 305 {
 306         return __db_marshaled_int_size[*buf];
 307 }
 308
 309 /*
 310  * __db_decompress_int --
 311  *      Decompresses the compressed integer pointer to by buf into i,
 312  *      returning the number of bytes read.
 313  *
 314  * PUBLIC: int __db_decompress_int __P((const u_int8_t *, u_int64_t *));
 315  */
 316 int
 317 __db_decompress_int(buf, i)
 318         const u_int8_t *buf;
 319         u_int64_t *i;
 320 {
 321         int len;
 322         u_int64_t tmp;
 323         u_int8_t *p;
 324         u_int8_t c;
 325
 326         tmp = 0;
 327         p = (u_int8_t*)&tmp;
 328         c = buf[0];
 329         len = __db_marshaled_int_size[c];
 330
 331         switch (len) {
 332         case 1:
 333                 *i = c;
 334                 return 1;
 335         case 2:
 336                 if (__db_isbigendian() != 0) {
 337                         p[6] = (c & CMP_INT_2BYTE_MASK);
 338                         p[7] = buf[1];
 339                 } else {
 340                         p[1] = (c & CMP_INT_2BYTE_MASK);
 341                         p[0] = buf[1];
 342                 }
 343                 tmp += CMP_INT_1BYTE_MAX + 1;
 344                 break;
 345         case 3:
 346                 if (__db_isbigendian() != 0) {
 347                         p[5] = (c & CMP_INT_3BYTE_MASK);
 348                         p[6] = buf[1];
 349                         p[7] = buf[2];
 350                 } else {
 351                         p[2] = (c & CMP_INT_3BYTE_MASK);
 352                         p[1] = buf[1];
 353                         p[0] = buf[2];
 354                 }
 355                 tmp += CMP_INT_2BYTE_MAX + 1;
 356                 break;
 357         case 4:
 358                 if (__db_isbigendian() != 0) {
 359                         p[4] = (c & CMP_INT_4BYTE_MASK);
 360                         p[5] = buf[1];
 361                         p[6] = buf[2];
 362                         p[7] = buf[3];
 363                 } else {
 364                         p[3] = (c & CMP_INT_4BYTE_MASK);
 365                         p[2] = buf[1];
 366                         p[1] = buf[2];
 367                         p[0] = buf[3];
 368                 }
 369                 tmp += CMP_INT_3BYTE_MAX + 1;
 370                 break;
 371         case 5:
 372                 if (__db_isbigendian() != 0) {
 373                         p[3] = (c & CMP_INT_5BYTE_MASK);
 374                         p[4] = buf[1];
 375                         p[5] = buf[2];
 376                         p[6] = buf[3];
 377                         p[7] = buf[4];
 378                 } else {
 379                         p[4] = (c & CMP_INT_5BYTE_MASK);
 380                         p[3] = buf[1];
 381                         p[2] = buf[2];
 382                         p[1] = buf[3];
 383                         p[0] = buf[4];
 384                 }
 385                 tmp += CMP_INT_4BYTE_MAX + 1;
 386                 break;
 387         case 6:
 388                 if (__db_isbigendian() != 0) {
 389                         p[3] = buf[1];
 390                         p[4] = buf[2];
 391                         p[5] = buf[3];
 392                         p[6] = buf[4];
 393                         p[7] = buf[5];
 394                 } else {
 395                         p[4] = buf[1];
 396                         p[3] = buf[2];
 397                         p[2] = buf[3];
 398                         p[1] = buf[4];
 399                         p[0] = buf[5];
 400                 }
 401                 tmp += CMP_INT_5BYTE_MAX + 1;
 402                 break;
 403         case 7:
 404                 if (__db_isbigendian() != 0) {
 405                         p[2] = buf[1];
 406                         p[3] = buf[2];
 407                         p[4] = buf[3];
 408                         p[5] = buf[4];
 409                         p[6] = buf[5];
 410                         p[7] = buf[6];
 411                 } else {
 412                         p[5] = buf[1];
 413                         p[4] = buf[2];
 414                         p[3] = buf[3];
 415                         p[2] = buf[4];
 416                         p[1] = buf[5];
 417                         p[0] = buf[6];
 418                 }
 419                 tmp += CMP_INT_6BYTE_MAX + 1;
 420                 break;
 421         case 8:
 422                 if (__db_isbigendian() != 0) {
 423                         p[1] = buf[1];
 424                         p[2] = buf[2];
 425                         p[3] = buf[3];
 426                         p[4] = buf[4];
 427                         p[5] = buf[5];
 428                         p[6] = buf[6];
 429                         p[7] = buf[7];
 430                 } else {
 431                         p[6] = buf[1];
 432                         p[5] = buf[2];
 433                         p[4] = buf[3];
 434                         p[3] = buf[4];
 435                         p[2] = buf[5];
 436                         p[1] = buf[6];
 437                         p[0] = buf[7];
 438                 }
 439                 tmp += CMP_INT_7BYTE_MAX + 1;
 440                 break;
 441         case 9:
 442                 if (__db_isbigendian() != 0) {
 443                         p[0] = buf[1];
 444                         p[1] = buf[2];
 445                         p[2] = buf[3];
 446                         p[3] = buf[4];
 447                         p[4] = buf[5];
 448                         p[5] = buf[6];
 449                         p[6] = buf[7];
 450                         p[7] = buf[8];
 451                 } else {
 452                         p[7] = buf[1];
 453                         p[6] = buf[2];
 454                         p[5] = buf[3];
 455                         p[4] = buf[4];
 456                         p[3] = buf[5];
 457                         p[2] = buf[6];
 458                         p[1] = buf[7];
 459                         p[0] = buf[8];
 460                 }
 461                 tmp += CMP_INT_8BYTE_MAX + 1;
 462                 break;
 463         default:
 464                 break;
 465         }
 466
 467         *i = tmp;
 468         return len;
 469 }
 470
 471 /*
 472  * __db_decompress_int32 --
 473  *      Decompresses the compressed 32 bit integer pointer to by buf into i,
 474  *      returning the number of bytes read.
 475  *
 476  * PUBLIC: int __db_decompress_int32 __P((const u_int8_t *, u_int32_t *));
 477  */
 478 int
 479 __db_decompress_int32(buf, i)
 480         const u_int8_t *buf;
 481         u_int32_t *i;
 482 {
 483         int len;
 484         u_int32_t tmp;
 485         u_int8_t *p;
 486         u_int8_t c;
 487
 488         tmp = 0;
 489         p = (u_int8_t*)&tmp;
 490         c = buf[0];
 491         len = __db_marshaled_int_size[c];
 492
 493         switch (len) {
 494         case 1:
 495                 *i = c;
 496                 return 1;
 497         case 2:
 498                 if (__db_isbigendian() != 0) {
 499                         p[2] = (c & CMP_INT_2BYTE_MASK);
 500                         p[3] = buf[1];
 501                 } else {
 502                         p[1] = (c & CMP_INT_2BYTE_MASK);
 503                         p[0] = buf[1];
 504                 }
 505                 tmp += CMP_INT_1BYTE_MAX + 1;
 506                 break;
 507         case 3:
 508                 if (__db_isbigendian() != 0) {
 509                         p[1] = (c & CMP_INT_3BYTE_MASK);
 510                         p[2] = buf[1];
 511                         p[3] = buf[2];
 512                 } else {
 513                         p[2] = (c & CMP_INT_3BYTE_MASK);
 514                         p[1] = buf[1];
 515                         p[0] = buf[2];
 516                 }
 517                 tmp += CMP_INT_2BYTE_MAX + 1;
 518                 break;
 519         case 4:
 520                 if (__db_isbigendian() != 0) {
 521                         p[0] = (c & CMP_INT_4BYTE_MASK);
 522                         p[1] = buf[1];
 523                         p[2] = buf[2];
 524                         p[3] = buf[3];
 525                 } else {
 526                         p[3] = (c & CMP_INT_4BYTE_MASK);
 527                         p[2] = buf[1];
 528                         p[1] = buf[2];
 529                         p[0] = buf[3];
 530                 }
 531                 tmp += CMP_INT_3BYTE_MAX + 1;
 532                 break;
 533         case 5:
 534                 if (__db_isbigendian() != 0) {
 535                         p[0] = buf[1];
 536                         p[1] = buf[2];
 537                         p[2] = buf[3];
 538                         p[3] = buf[4];
 539                 } else {
 540                         p[3] = buf[1];
 541                         p[2] = buf[2];
 542                         p[1] = buf[3];
 543                         p[0] = buf[4];
 544                 }
 545                 tmp += CMP_INT_4BYTE_MAX + 1;
 546                 break;
 547         default:
 548                 break;
 549         }
 550
 551         *i = tmp;
 552         return len;
 553 }
 554
 555 #endif