lib/base224.c

   1 /*
   2  *      Base 224 Encoding & Decoding
   3  *
   4  *      (c) 2002 Martin Mares <mj@ucw.cz>
   5  *
   6  *      The `base-224' encoding transforms general sequences of bytes
   7  *      to sequences of non-control 8-bit characters (0x20-0xff). Since
   8  *      224 and 256 are incompatible bases (there is no k,l: 224^k=256^l)
   9  *      and we want to avoid lengthy calculations, we cheat a bit:
  10  *
  11  *      Each base-224 digit can be represented as a (base-7 digit, base-32 digit)
  12  *      pair, so we pass the lower 5 bits directly and use a base-7 encoder
  13  *      for the upper part. We process blocks of 39 bits and encode them
  14  *      to 5 base-224 digits: we take 5x5 bits as the lower halves and convert
  15  *      the remaining 14 bits in base-7 (2^14 = 16384 < 16807 = 7^5) to get
  16  *      the 7 upper parts we need (with a little redundancy). Little endian
  17  *      ordering is used to make handling of partial blocks easy.
  18  *
  19  *      We transform 39 source bits to 40 destination bits, stretching the data
  20  *      by 1/39 = approx. 2.56%.
  21  */
  22
  23 #undef LOCAL_DEBUG
  24
  25 #include "lib/lib.h"
  26 #include "lib/base224.h"
  27
  28 static void
  29 encode_block(byte *w, u32 hi, u32 lo)
  30 {
  31   uns x, y;
  32
  33   /*
  34    *   Splitting of the 39-bit block: [a-e][0-5] are the base-32 digits, *'s are used for base-7.
  35    *   +----------------+----------------+----------------+----------------+----------------+
  36    *   +00******e4e3e2e1|e0******d4d3d2d1|d0******c4c3c2c1|c0******b4b3b2b1|b0****a4a3a2a1a0|
  37    *   +----------------+----------------+----------------+----------------+----------------+
  38    */
  39
  40   w[0] = lo & 0x1f;
  41   w[1] = (lo >> 7) & 0x1f;
  42   w[2] = (lo >> 15) & 0x1f;
  43   w[3] = (lo >> 23) & 0x1f;
  44   w[4] = (lo >> 31) | ((hi << 1) & 0x1e);
  45   x = (lo >> 5)  & 0x0003
  46     | (lo >> 10) & 0x001c
  47     | (lo >> 15) & 0x00e0
  48     | (lo >> 20) & 0x0700
  49     | (hi << 7)  & 0x3800;
  50   DBG("<<< h=%08x l=%08x x=%d", hi, lo, x);
  51   for (y=0; y<5; y++)
  52     {
  53       w[y] += 0x20 + ((x % 7) << 5);
  54       x /= 7;
  55     }
  56 }
  57
  58 uns
  59 base224_encode(byte *dest, byte *src, uns len)
  60 {
  61   u32 lo=0, hi=0;                       /* 64-bit buffer accumulating input bits */
  62   uns i=0;                              /* How many source bits do we have buffered */
  63   u32 x;
  64   byte *w=dest;
  65
  66   while (len--)
  67     {
  68       x = *src++;
  69       if (i < 32)
  70         {
  71           lo |= x << i;
  72           if (i > 24)
  73             hi |= x >> (32-i);
  74         }
  75       else
  76         hi |= x << (i-32);
  77       i += 8;
  78       if (i >= 39)
  79         {
  80           encode_block(w, hi, lo);
  81           w += 5;
  82           lo = hi >> 7;
  83           hi = 0;
  84           i -= 39;
  85         }
  86     }
  87   if (i)                                /* Partial block */
  88     {
  89       encode_block(w, hi, lo);
  90       w += (i+8)/8;                     /* Just check logarithms if you want to understand */
  91     }
  92   return w - dest;
  93 }
  94
  95 uns
  96 base224_decode(byte *dest, byte *src, uns len)
  97 {
  98   u32 hi=0, lo=0;                       /* 64-bit buffer accumulating output bits */
  99   uns i=0;                              /* How many bits do we have accumulated */
 100   u32 h, l;                             /* Decoding of the current block */
 101   uns x;                                /* base-7 part of the current block */
 102   uns len0;
 103   byte *start = dest;
 104
 105   do
 106     {
 107       if (!len)
 108         break;
 109       len0 = len;
 110
 111       ASSERT(*src >= 0x20);             /* byte 0 */
 112       h = 0;
 113       l = *src & 0x1f;
 114       x = (*src++ >> 5) - 1;
 115       if (!--len)
 116         goto blockend;
 117
 118       ASSERT(*src >= 0x20);             /* byte 1 */
 119       l |= (*src & 0x1f) << 7;
 120       x += ((*src++ >> 5) - 1) * 7;
 121       if (!--len)
 122         goto blockend;
 123
 124       ASSERT(*src >= 0x20);             /* byte 2 */
 125       l |= (*src & 0x1f) << 15;
 126       x += ((*src++ >> 5) - 1) * 7*7;
 127       if (!--len)
 128         goto blockend;
 129
 130       ASSERT(*src >= 0x20);             /* byte 3 */
 131       l |= (*src & 0x1f) << 23;
 132       x += ((*src++ >> 5) - 1) * 7*7*7;
 133       if (!--len)
 134         goto blockend;
 135
 136       ASSERT(*src >= 0x20);             /* byte 4 */
 137       l |= *src << 31;
 138       h = (*src & 0x1f) >> 1;
 139       x += ((*src++ >> 5) - 1) * 7*7*7*7;
 140       --len;
 141
 142     blockend:
 143       len0 -= len;
 144       l |= ((x & 0x0003) << 5)          /* Decode base-7 */
 145         |  ((x & 0x001c) << 10)
 146         |  ((x & 0x00e0) << 15)
 147         |  ((x & 0x0700) << 20);
 148       h |=  (x & 0x3800) >> 7;
 149
 150       DBG("<<< i=%d h=%08x l=%08x x=%d len0=%d", i, h, l, x, len0);
 151       lo |= l << i;
 152       hi |= h << i;
 153       if (i)
 154         hi |= l >> (32-i);
 155       i += len0*8 - 1;
 156
 157       while (i >= 8)
 158         {
 159           *dest++ = lo;
 160           lo = (lo >> 8U) | (hi << 24);
 161           hi >>= 8;
 162           i -= 8;
 163         }
 164     }
 165   while (len0 == 5);
 166   return dest-start;
 167 }
 168
 169 #ifdef TEST
 170
 171 #include <stdio.h>
 172
 173 int main(int argc, char **argv)
 174 {
 175 #if 0
 176   byte i[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39 };
 177   byte o[256], w[256];
 178   uns l;
 179   l = base224_encode(o, i, sizeof(i));
 180   fwrite(o, 1, l, stdout);
 181   fputc(0xaa, stdout);
 182   l = base224_decode(w, o, l);
 183   fwrite(w, 1, l, stdout);
 184 #else
 185   if (argc > 1)
 186     {
 187       byte i[BASE224_OUT_CHUNK*17], o[BASE224_IN_CHUNK*17];
 188       uns l;
 189       while (l = fread(i, 1, sizeof(i), stdin))
 190         {
 191           l = base224_decode(o, i, l);
 192           fwrite(o, 1, l, stdout);
 193         }
 194     }
 195   else
 196     {
 197       byte i[BASE224_IN_CHUNK*23], o[BASE224_OUT_CHUNK*23];
 198       uns l;
 199       while (l = fread(i, 1, sizeof(i), stdin))
 200         {
 201           l = base224_encode(o, i, l);
 202           fwrite(o, 1, l, stdout);
 203         }
 204     }
 205 #endif
 206
 207   return 0;
 208 }
 209
 210 #endif