ucw/varint.c

   1 /*
   2  *      UCW Library -- Coding of u64 into variable length bytecode.
   3  *
   4  *      (c) 2013 Tomas Valla <tom@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include <ucw/lib.h>
  11 #include <ucw/varint.h>
  12
  13 #define PUTB(j,i)  p[j] = (byte)((u >> (8*(i))));
  14 #define PUTB4(b)   PUTB(0,b-1) PUTB(1,b-2) PUTB(2,b-3) PUTB(3,b-4)
  15 uns varint_put_big(byte *p, u64 u)
  16 {
  17         ASSERT(u >= VARINT_SHIFT_L4);
  18
  19         if (u < VARINT_SHIFT_L5) {
  20                 u -= VARINT_SHIFT_L4;
  21                 PUTB4(5)
  22                 p[0] |= 0xf0;
  23                 PUTB(4,0);
  24                 return 5;
  25         }
  26         if (u < VARINT_SHIFT_L6) {
  27                 u -= VARINT_SHIFT_L5;
  28                 PUTB4(6)
  29                 PUTB(4,1) PUTB(5,0)
  30                 p[0] |= 0xf8;
  31                 return 6;
  32         }
  33         if (u < VARINT_SHIFT_L7) {
  34                 u -= VARINT_SHIFT_L6;
  35                 PUTB4(7)
  36                 p[0] |= 0xfc;
  37                 PUTB(4,2) PUTB(5,1) PUTB(6,0)
  38                 return 7;
  39         }
  40         if (u < VARINT_SHIFT_L8) {
  41                 u -= VARINT_SHIFT_L7;
  42                 p[0] = 0xfe;
  43                 PUTB(1,6) PUTB(2,5) PUTB(3,4) PUTB(4,3)
  44                 PUTB(5,2) PUTB(6,1) PUTB(7,0)
  45                 return 8;
  46         }
  47         u -= VARINT_SHIFT_L8;
  48         p[0] = 0xff;
  49         PUTB(1,7) PUTB(2,6) PUTB(3,5) PUTB(4,4)
  50         PUTB(5,3) PUTB(6,2) PUTB(7,1) PUTB(8,0)
  51         return 9;
  52 }
  53
  54 const byte *varint_get_big(const byte *p, u64 *r)
  55 {
  56         ASSERT((*p & 0xf0) == 0xf0);
  57
  58         byte h = ~*p;
  59         if (h & 0x08) {
  60                 *r = (u64)(p[0] & 7)<<32 | (u64)p[1]<<24 | (u64)p[2]<<16 | (u64)p[3]<<8 | (u64)p[4];
  61                 *r += VARINT_SHIFT_L4;
  62                 return p+5;
  63         }
  64         if (h & 0x04) {
  65                 *r = (u64)(p[0] & 3)<<40 | (u64)p[1]<<32 | (u64)p[2]<<24 | (u64)p[3]<<16 | (u64)p[4]<<8 | (u64)p[5];
  66                 *r += VARINT_SHIFT_L5;
  67                 return p+6;
  68         }
  69         if (h & 0x02) {
  70                 *r = (u64)(p[0] & 1)<<48 | (u64)p[1]<<40 | (u64)p[2]<<32 | (u64)p[3]<<24 | (u64)p[4]<<16 | (u64)p[5]<<8 | (u64)p[6];
  71                 *r += VARINT_SHIFT_L6;
  72                 return p+7;
  73         }
  74         if (h & 0x01) {
  75                 *r = (u64)p[1]<<48 | (u64)p[2]<<40 | (u64)p[3]<<32 | (u64)p[4]<<24 | (u64)p[5]<<16 | (u64)p[6]<<8 | (u64)p[7];
  76                 *r += VARINT_SHIFT_L7;
  77                 return p+8;
  78         }
  79         *r = ((u64)p[1] << 56) | ((u64)p[2] << 48) | ((u64)p[3] << 40) | ((u64)p[4] << 32) | ((u64)p[5] << 24) | ((u64)p[6] << 16) | ((u64)p[7] << 8) | (u64)p[8];
  80         *r += VARINT_SHIFT_L8;
  81         return p+9;
  82 }
  83
  84
  85 #ifdef TEST
  86
  87 #include <string.h>
  88 #include <stdio.h>
  89
  90 int main(int argc, char **argv UNUSED)
  91 {
  92         byte buf[16] = { 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa };
  93         u64 u;
  94
  95         if (scanf("%llx", &u) != 1) {
  96                 fprintf(stderr, "Invalid usage!\n");
  97                 return 1;
  98         }
  99         varint_put(buf, u);
 100         int l = varint_len(buf[0]);
 101         varint_get(buf, &u);
 102         printf("%u %d %jx", varint_space(u), l, (uintmax_t) u);
 103         if (argc > 1) {
 104                 for (int i=0; i<l; i++)
 105                         printf(" %x", buf[i]);
 106         }
 107         printf("\n");
 108
 109         return 0;
 110 }
 111
 112 #endif