exp/packed_unsigned.h

   1 /*
   2   Copyright 2008 Kristian Nielsen
   3
   4   This file is part of BeeDB.
   5
   6   Foobar is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 2 of the License, or
   9   (at your option) any later version.
  10
  11   Foobar is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include <stdint.h>
  21
  22
  23 /*
  24   Version of packed_mask.h that uses uint64_t throughout, in an attempt to
  25   avoid sign extension overhead.
  26 */
  27
  28 /*
  29   ToDo: Need big-endian version of this, that will store from high bit down,
  30   so that the trailing bytes of any final partial word will be at the end.
  31 */
  32
  33 struct pack_ptr_unsigned {
  34   /*
  35     Base pointer.
  36     Should be 64-bit aligned, and must be readable as 64-bit words, even
  37     if trailing bits are undefined (ie. for a 9-byte buffer we will read
  38     16 bytes, though we will only actually look at the first 9).
  39   */
  40   uint64_t *b;
  41   /* Current word, equal to b[i-1]. */
  42   uint64_t v;
  43   /* Index of next word. */
  44   uint64_t i;
  45   /* Bit position in current word. */
  46   uint64_t p;
  47
  48   /* Methods, all inline. */
  49   uint64_t used() { return i; }
  50
  51   pack_ptr_unsigned(uint64_t *base);
  52   /* Read the next NUMBITS bits, updating pointer. */
  53   uint64_t getbits(uint64_t numbits);
  54   /*
  55     Put value DATA of size NUMBITS into current position.
  56
  57     Assumes that DATA fits in a word of size NUMBITS, so we don't have to
  58     mask it ourselves.
  59
  60     ToDo: We can have a more efficient version of this that assumes the data
  61     before the write is zero.
  62
  63     Then there is no need to mask off the destination, and we don't have to
  64     write into the destination array except when moving to the next word (in
  65     this case we need a flush() method to be called at the end).
  66
  67     We might want to have another struct for this, as we will need another
  68     constructor to initialise v=0, and we won't mix well with reading anyway.
  69   */
  70   void putbits(uint64_t numbits, uint64_t data);
  71   /* Read/store 64-bit value packed with 3 length bits. */
  72   uint64_t unpack1();
  73   void pack1(uint64_t v);
  74   uint64_t unpack2();
  75   void pack2(uint64_t v);
  76   uint64_t unpack3();
  77   void pack3(uint64_t v);
  78   uint64_t unpack4();
  79   void pack4(uint64_t v);
  80 };
  81
  82 inline
  83 pack_ptr_unsigned::pack_ptr_unsigned(uint64_t *base)
  84 {
  85   b= base;
  86   v= b[0];
  87   i= 1;
  88   p= 0;
  89 }
  90
  91 inline uint64_t
  92 pack_ptr_unsigned::getbits(uint64_t numbits)
  93 {
  94   uint64_t r= v >> p;
  95   p+= numbits;
  96   if (unlikely(p >= 64))
  97   {
  98     /*
  99       ToDo: Hm, seems we might be reading one extra word off the end here.
 100
 101       May be worthwhile, but needs to be taken into account.
 102     */
 103     v= b[i++];
 104     p= p - 64;
 105     /*
 106       Shift by 64 bit is undefined in C.
 107       We make the conditional on numbits==64 so that for compile-time known
 108       value of numbits the compiler can optimize the conditional away.
 109       For numbits < 64 and p = 0, the redundant |= (which is masked away
 110       immediately below) is cheaper than an extra conditional.
 111     */
 112     if (likely(!(numbits == 64 && p == 0)))
 113       r|= v << (numbits - p);
 114   }
 115   r&= (~(uint64_t)0 >> (64 - numbits));
 116 //printf("getbits(%u) -> %lu\n", numbits, (unsigned long)r);
 117   return r;
 118 }
 119
 120 inline void
 121 pack_ptr_unsigned::putbits(uint64_t numbits, uint64_t data)
 122 {
 123 //printf("putbits(%u, %lu)\n", numbits, (unsigned long)data);
 124   uint64_t mask= (~(uint64_t)0 >> (64 - numbits));
 125   v= (v & ~(mask << p)) | (data << p);
 126   b[i-1]= v;
 127   p+= numbits;
 128   if (unlikely(p >= 64))
 129   {
 130     v= b[i];
 131     p= p - 64;
 132     if (likely(!(numbits == 64 && p == 0)))
 133     {
 134       v= (v & (~(uint64_t)0 << p)) | (data >> (numbits - p));
 135       b[i]= v;
 136     }
 137     i++;
 138   }
 139 }
 140
 141 inline uint64_t
 142 pack_ptr_unsigned::unpack1()
 143 {
 144   uint64_t n= getbits(3);
 145   return getbits(n*9+1);
 146 }
 147
 148 inline void
 149 pack_ptr_unsigned::pack1(uint64_t v)
 150 {
 151   /*
 152     Compute the 3-bit header counter C, where we store C*9+1 bits.
 153     We have C = ((#bits - 1) + 8) / 9   [rounding down].
 154     And #bits = 64 - #leading zeroes, and 64 - 1 + 8 == 71.
 155     We use |1 to be sure to get at least a size of one bit (__builtin_clzl is
 156     undefined for argument of zero).
 157   */
 158   uint64_t bits= (71 - COUNT_LEADING_ZEROS_64(v | 1))/9;
 159   putbits(3, bits);
 160   putbits(bits*9+1, v);
 161 }
 162
 163 inline uint64_t
 164 pack_ptr_unsigned::unpack2()
 165 {
 166   uint64_t n= getbits(2);
 167   return getbits(n*20+4);
 168 }
 169
 170 inline void
 171 pack_ptr_unsigned::pack2(uint64_t v)
 172 {
 173   uint64_t bits= (79 - COUNT_LEADING_ZEROS_64(v | 1))/20;
 174   putbits(2, bits);
 175   putbits(bits*20+4, v);
 176 }
 177
 178 /*
 179   BE: 0xxx      LE:    xxx0
 180       10<11x>       <11x>01
 181       110<20x>     <20x>011
 182       111<64x>     <64x>111
 183 */
 184
 185 /* ToDo: Only one copy of this table! */
 186 static struct {
 187   uint64_t bits;
 188   uint64_t or_value;
 189 #ifndef WORDS_BIGENDIAN
 190   uint64_t lshift;
 191 #endif
 192 } unpack3_table_unsigned[8]= {
 193 #ifdef WORDS_BIGENDIAN
 194   /* 0 */ { 1, 0 },
 195   /* 1 */ { 1, 2 },
 196   /* 2 */ { 1, 4 },
 197   /* 3 */ { 1, 6 },
 198   /* 4 */ { 10, 0 },
 199   /* 5 */ { 10, 1024 },
 200   /* 6 */ { 20, 0 },
 201   /* 7 */ { 64, 0}
 202 #else
 203   /* 0 */ {  1, 0, 2 },
 204   /* 1 */ { 10, 0, 1 },
 205   /* 2 */ {  1, 1, 2 },
 206   /* 3 */ { 20, 0, 0 },
 207   /* 4 */ {  1, 2, 2 },
 208   /* 5 */ { 10, 1, 1 },
 209   /* 6 */ {  1, 3, 2 },
 210   /* 7 */ { 64, 0, 0 }
 211 #endif
 212   };
 213
 214 inline uint64_t
 215 pack_ptr_unsigned::unpack3()
 216 {
 217   uint64_t prefix= getbits(3);
 218   return ( getbits(unpack3_table_unsigned[prefix].bits)
 219 #ifndef WORDS_BIGENDIAN
 220            << unpack3_table_unsigned[prefix].lshift
 221 #endif
 222          ) | unpack3_table_unsigned[prefix].or_value;
 223 }
 224
 225 static struct { uint64_t tag_bits; uint64_t data_bits; uint64_t tag_value; }
 226 pack3_table_unsigned[64]= {
 227 #ifdef WORDS_BIGENDIAN
 228   /* 64 */ { 3, 64, 7 },
 229   /* 63 */ { 3, 64, 7 },
 230   /* 62 */ { 3, 64, 7 },
 231   /* 61 */ { 3, 64, 7 },
 232   /* 60 */ { 3, 64, 7 },
 233   /* 59 */ { 3, 64, 7 },
 234   /* 58 */ { 3, 64, 7 },
 235   /* 57 */ { 3, 64, 7 },
 236   /* 56 */ { 3, 64, 7 },
 237   /* 55 */ { 3, 64, 7 },
 238   /* 54 */ { 3, 64, 7 },
 239   /* 53 */ { 3, 64, 7 },
 240   /* 52 */ { 3, 64, 7 },
 241   /* 51 */ { 3, 64, 7 },
 242   /* 50 */ { 3, 64, 7 },
 243   /* 49 */ { 3, 64, 7 },
 244   /* 48 */ { 3, 64, 7 },
 245   /* 47 */ { 3, 64, 7 },
 246   /* 46 */ { 3, 64, 7 },
 247   /* 45 */ { 3, 64, 7 },
 248   /* 44 */ { 3, 64, 7 },
 249   /* 43 */ { 3, 64, 7 },
 250   /* 42 */ { 3, 64, 7 },
 251   /* 41 */ { 3, 64, 7 },
 252   /* 40 */ { 3, 64, 7 },
 253   /* 39 */ { 3, 64, 7 },
 254   /* 38 */ { 3, 64, 7 },
 255   /* 37 */ { 3, 64, 7 },
 256   /* 36 */ { 3, 64, 7 },
 257   /* 35 */ { 3, 64, 7 },
 258   /* 34 */ { 3, 64, 7 },
 259   /* 33 */ { 3, 64, 7 },
 260   /* 32 */ { 3, 64, 7 },
 261   /* 31 */ { 3, 64, 7 },
 262   /* 30 */ { 3, 64, 7 },
 263   /* 29 */ { 3, 64, 7 },
 264   /* 28 */ { 3, 64, 7 },
 265   /* 27 */ { 3, 64, 7 },
 266   /* 26 */ { 3, 64, 7 },
 267   /* 25 */ { 3, 64, 7 },
 268   /* 24 */ { 3, 64, 7 },
 269   /* 23 */ { 3, 64, 7 },
 270   /* 22 */ { 3, 64, 7 },
 271   /* 21 */ { 3, 64, 7 },
 272   /* 20 */ { 3, 20, 6 },
 273   /* 19 */ { 3, 20, 6 },
 274   /* 18 */ { 3, 20, 6 },
 275   /* 17 */ { 3, 20, 6 },
 276   /* 16 */ { 3, 20, 6 },
 277   /* 15 */ { 3, 20, 6 },
 278   /* 14 */ { 3, 20, 6 },
 279   /* 13 */ { 3, 20, 6 },
 280   /* 12 */ { 3, 20, 6 },
 281   /* 11 */ { 2, 11, 2 },
 282   /* 10 */ { 2, 11, 2 },
 283   /*  9 */ { 2, 11, 2 },
 284   /*  8 */ { 2, 11, 2 },
 285   /*  7 */ { 2, 11, 2 },
 286   /*  6 */ { 2, 11, 2 },
 287   /*  5 */ { 2, 11, 2 },
 288   /*  4 */ { 2, 11, 2 },
 289   /*  3 */ { 1,  3, 0 },
 290   /*  2 */ { 1,  3, 0 },
 291   /*  1 */ { 1,  3, 0 },
 292 #else
 293   /* 64 */ { 3, 64, 7 },
 294   /* 63 */ { 3, 64, 7 },
 295   /* 62 */ { 3, 64, 7 },
 296   /* 61 */ { 3, 64, 7 },
 297   /* 60 */ { 3, 64, 7 },
 298   /* 59 */ { 3, 64, 7 },
 299   /* 58 */ { 3, 64, 7 },
 300   /* 57 */ { 3, 64, 7 },
 301   /* 56 */ { 3, 64, 7 },
 302   /* 55 */ { 3, 64, 7 },
 303   /* 54 */ { 3, 64, 7 },
 304   /* 53 */ { 3, 64, 7 },
 305   /* 52 */ { 3, 64, 7 },
 306   /* 51 */ { 3, 64, 7 },
 307   /* 50 */ { 3, 64, 7 },
 308   /* 49 */ { 3, 64, 7 },
 309   /* 48 */ { 3, 64, 7 },
 310   /* 47 */ { 3, 64, 7 },
 311   /* 46 */ { 3, 64, 7 },
 312   /* 45 */ { 3, 64, 7 },
 313   /* 44 */ { 3, 64, 7 },
 314   /* 43 */ { 3, 64, 7 },
 315   /* 42 */ { 3, 64, 7 },
 316   /* 41 */ { 3, 64, 7 },
 317   /* 40 */ { 3, 64, 7 },
 318   /* 39 */ { 3, 64, 7 },
 319   /* 38 */ { 3, 64, 7 },
 320   /* 37 */ { 3, 64, 7 },
 321   /* 36 */ { 3, 64, 7 },
 322   /* 35 */ { 3, 64, 7 },
 323   /* 34 */ { 3, 64, 7 },
 324   /* 33 */ { 3, 64, 7 },
 325   /* 32 */ { 3, 64, 7 },
 326   /* 31 */ { 3, 64, 7 },
 327   /* 30 */ { 3, 64, 7 },
 328   /* 29 */ { 3, 64, 7 },
 329   /* 28 */ { 3, 64, 7 },
 330   /* 27 */ { 3, 64, 7 },
 331   /* 26 */ { 3, 64, 7 },
 332   /* 25 */ { 3, 64, 7 },
 333   /* 24 */ { 3, 64, 7 },
 334   /* 23 */ { 3, 64, 7 },
 335   /* 22 */ { 3, 64, 7 },
 336   /* 21 */ { 3, 64, 7 },
 337   /* 20 */ { 3, 20, 3 },
 338   /* 19 */ { 3, 20, 3 },
 339   /* 18 */ { 3, 20, 3 },
 340   /* 17 */ { 3, 20, 3 },
 341   /* 16 */ { 3, 20, 3 },
 342   /* 15 */ { 3, 20, 3 },
 343   /* 14 */ { 3, 20, 3 },
 344   /* 13 */ { 3, 20, 3 },
 345   /* 12 */ { 3, 20, 3 },
 346   /* 11 */ { 2, 11, 1 },
 347   /* 10 */ { 2, 11, 1 },
 348   /*  9 */ { 2, 11, 1 },
 349   /*  8 */ { 2, 11, 1 },
 350   /*  7 */ { 2, 11, 1 },
 351   /*  6 */ { 2, 11, 1 },
 352   /*  5 */ { 2, 11, 1 },
 353   /*  4 */ { 2, 11, 1 },
 354   /*  3 */ { 1,  3, 0 },
 355   /*  2 */ { 1,  3, 0 },
 356   /*  1 */ { 1,  3, 0 },
 357 #endif
 358   };
 359
 360 inline void
 361 pack_ptr_unsigned::pack3(uint64_t v)
 362 {
 363   uint64_t bits= COUNT_LEADING_ZEROS_64(v | 1);
 364   putbits(pack3_table_unsigned[bits].tag_bits, pack3_table_unsigned[bits].tag_value);
 365   putbits(pack3_table_unsigned[bits].data_bits, v);
 366 }
 367
 368 /*
 369   BE: 00xx      LE:    xx00
 370       01<8x>         <8x>01
 371       10<16x>       <16x>10
 372       110<24x>     <24x>011
 373       111<64x>     <64x>111
 374 */
 375
 376 /* ToDo: Only one copy of this table! */
 377 static struct {
 378   uint64_t bits;
 379   uint64_t or_value;
 380 #ifndef WORDS_BIGENDIAN
 381   uint64_t lshift;
 382 #endif
 383 } unpack4_table_unsigned[8]= {
 384 #ifdef WORDS_BIGENDIAN
 385   /* 0 */ { 1, 0 },
 386   /* 1 */ { 1, 2 },
 387   /* 2 */ { 7, 0 },
 388   /* 3 */ { 7, 128 },
 389   /* 4 */ { 15, 0 },
 390   /* 5 */ { 15, 32768 },
 391   /* 6 */ { 24, 0 },
 392   /* 7 */ { 64, 0}
 393 #else
 394   /* 0 */ {  1, 0, 1 },
 395   /* 1 */ {  7, 0, 1 },
 396   /* 2 */ { 15, 0, 1 },
 397   /* 3 */ { 24, 0, 0 },
 398   /* 4 */ {  1, 1, 1 },
 399   /* 5 */ {  7, 1, 1 },
 400   /* 6 */ { 15, 1, 1 },
 401   /* 7 */ { 64, 0, 0 }
 402 #endif
 403   };
 404
 405 inline uint64_t
 406 pack_ptr_unsigned::unpack4()
 407 {
 408   uint64_t prefix= getbits(3);
 409   return ( getbits(unpack4_table_unsigned[prefix].bits)
 410 #ifndef WORDS_BIGENDIAN
 411            << unpack4_table_unsigned[prefix].lshift
 412 #endif
 413          ) | unpack4_table_unsigned[prefix].or_value;
 414 }
 415
 416 static struct { uint64_t tag_bits; uint64_t data_bits; uint64_t tag_value; }
 417 pack4_table_unsigned[64]= {
 418 #ifdef WORDS_BIGENDIAN
 419   /* 64 */ { 3, 64, 7 },
 420   /* 63 */ { 3, 64, 7 },
 421   /* 62 */ { 3, 64, 7 },
 422   /* 61 */ { 3, 64, 7 },
 423   /* 60 */ { 3, 64, 7 },
 424   /* 59 */ { 3, 64, 7 },
 425   /* 58 */ { 3, 64, 7 },
 426   /* 57 */ { 3, 64, 7 },
 427   /* 56 */ { 3, 64, 7 },
 428   /* 55 */ { 3, 64, 7 },
 429   /* 54 */ { 3, 64, 7 },
 430   /* 53 */ { 3, 64, 7 },
 431   /* 52 */ { 3, 64, 7 },
 432   /* 51 */ { 3, 64, 7 },
 433   /* 50 */ { 3, 64, 7 },
 434   /* 49 */ { 3, 64, 7 },
 435   /* 48 */ { 3, 64, 7 },
 436   /* 47 */ { 3, 64, 7 },
 437   /* 46 */ { 3, 64, 7 },
 438   /* 45 */ { 3, 64, 7 },
 439   /* 44 */ { 3, 64, 7 },
 440   /* 43 */ { 3, 64, 7 },
 441   /* 42 */ { 3, 64, 7 },
 442   /* 41 */ { 3, 64, 7 },
 443   /* 40 */ { 3, 64, 7 },
 444   /* 39 */ { 3, 64, 7 },
 445   /* 38 */ { 3, 64, 7 },
 446   /* 37 */ { 3, 64, 7 },
 447   /* 36 */ { 3, 64, 7 },
 448   /* 35 */ { 3, 64, 7 },
 449   /* 34 */ { 3, 64, 7 },
 450   /* 33 */ { 3, 64, 7 },
 451   /* 32 */ { 3, 64, 7 },
 452   /* 31 */ { 3, 64, 7 },
 453   /* 30 */ { 3, 64, 7 },
 454   /* 29 */ { 3, 64, 7 },
 455   /* 28 */ { 3, 64, 7 },
 456   /* 27 */ { 3, 64, 7 },
 457   /* 26 */ { 3, 64, 7 },
 458   /* 25 */ { 3, 64, 7 },
 459   /* 24 */ { 3, 24, 6 },
 460   /* 23 */ { 3, 24, 6 },
 461   /* 22 */ { 3, 24, 6 },
 462   /* 21 */ { 3, 24, 6 },
 463   /* 20 */ { 3, 24, 6 },
 464   /* 19 */ { 3, 24, 6 },
 465   /* 18 */ { 3, 24, 6 },
 466   /* 17 */ { 3, 24, 6 },
 467   /* 16 */ { 2, 16, 2 },
 468   /* 15 */ { 2, 16, 2 },
 469   /* 14 */ { 2, 16, 2 },
 470   /* 13 */ { 2, 16, 2 },
 471   /* 12 */ { 2, 16, 2 },
 472   /* 11 */ { 2, 16, 2 },
 473   /* 10 */ { 2, 16, 2 },
 474   /*  9 */ { 2, 16, 2 },
 475   /*  8 */ { 2,  8, 1 },
 476   /*  7 */ { 2,  8, 1 },
 477   /*  6 */ { 2,  8, 1 },
 478   /*  5 */ { 2,  8, 1 },
 479   /*  4 */ { 2,  8, 1 },
 480   /*  3 */ { 2,  8, 1 },
 481   /*  2 */ { 2,  2, 0 },
 482   /*  1 */ { 2,  2, 0 },
 483 #else
 484   /* 64 */ { 3, 64, 7 },
 485   /* 63 */ { 3, 64, 7 },
 486   /* 62 */ { 3, 64, 7 },
 487   /* 61 */ { 3, 64, 7 },
 488   /* 60 */ { 3, 64, 7 },
 489   /* 59 */ { 3, 64, 7 },
 490   /* 58 */ { 3, 64, 7 },
 491   /* 57 */ { 3, 64, 7 },
 492   /* 56 */ { 3, 64, 7 },
 493   /* 55 */ { 3, 64, 7 },
 494   /* 54 */ { 3, 64, 7 },
 495   /* 53 */ { 3, 64, 7 },
 496   /* 52 */ { 3, 64, 7 },
 497   /* 51 */ { 3, 64, 7 },
 498   /* 50 */ { 3, 64, 7 },
 499   /* 49 */ { 3, 64, 7 },
 500   /* 48 */ { 3, 64, 7 },
 501   /* 47 */ { 3, 64, 7 },
 502   /* 46 */ { 3, 64, 7 },
 503   /* 45 */ { 3, 64, 7 },
 504   /* 44 */ { 3, 64, 7 },
 505   /* 43 */ { 3, 64, 7 },
 506   /* 42 */ { 3, 64, 7 },
 507   /* 41 */ { 3, 64, 7 },
 508   /* 40 */ { 3, 64, 7 },
 509   /* 39 */ { 3, 64, 7 },
 510   /* 38 */ { 3, 64, 7 },
 511   /* 37 */ { 3, 64, 7 },
 512   /* 36 */ { 3, 64, 7 },
 513   /* 35 */ { 3, 64, 7 },
 514   /* 34 */ { 3, 64, 7 },
 515   /* 33 */ { 3, 64, 7 },
 516   /* 32 */ { 3, 64, 7 },
 517   /* 31 */ { 3, 64, 7 },
 518   /* 30 */ { 3, 64, 7 },
 519   /* 29 */ { 3, 64, 7 },
 520   /* 28 */ { 3, 64, 7 },
 521   /* 27 */ { 3, 64, 7 },
 522   /* 26 */ { 3, 64, 7 },
 523   /* 25 */ { 3, 64, 7 },
 524   /* 24 */ { 3, 24, 3 },
 525   /* 23 */ { 3, 24, 3 },
 526   /* 22 */ { 3, 24, 3 },
 527   /* 21 */ { 3, 24, 3 },
 528   /* 20 */ { 3, 24, 3 },
 529   /* 19 */ { 3, 24, 3 },
 530   /* 18 */ { 3, 24, 3 },
 531   /* 17 */ { 3, 24, 3 },
 532   /* 16 */ { 2, 16, 2 },
 533   /* 15 */ { 2, 16, 2 },
 534   /* 14 */ { 2, 16, 2 },
 535   /* 13 */ { 2, 16, 2 },
 536   /* 12 */ { 2, 16, 2 },
 537   /* 11 */ { 2, 16, 2 },
 538   /* 10 */ { 2, 16, 2 },
 539   /*  9 */ { 2, 16, 2 },
 540   /*  8 */ { 2,  8, 1 },
 541   /*  7 */ { 2,  8, 1 },
 542   /*  6 */ { 2,  8, 1 },
 543   /*  5 */ { 2,  8, 1 },
 544   /*  4 */ { 2,  8, 1 },
 545   /*  3 */ { 2,  8, 1 },
 546   /*  2 */ { 2,  2, 0 },
 547   /*  1 */ { 2,  2, 0 },
 548 #endif
 549   };
 550
 551 inline void
 552 pack_ptr_unsigned::pack4(uint64_t v)
 553 {
 554   uint64_t bits= COUNT_LEADING_ZEROS_64(v | 1);
 555   putbits(pack4_table_unsigned[bits].tag_bits, pack4_table_unsigned[bits].tag_value);
 556   putbits(pack4_table_unsigned[bits].data_bits, v);
 557 }
 558
 559 /*
 560   32-bit: 2+n*10
 561
 562   00 xx
 563   01 xxxxxxxxxxxx
 564   10 xxxxxxxxxxxxxxxxxxxxxx
 565   11 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
 566
 567 */