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  *      This software may be freely distributed and used according to the terms
  23  *      of the GNU Lesser General Public License.
  24  */
  25
  26 #undef LOCAL_DEBUG
  27
  28 #include "lib/lib.h"
  29 #include "lib/base224.h"
  30
  31 static void
  32 encode_block(byte *w, u32 hi, u32 lo)
  33 {
  34   uns x, y;
  35
  36   /*
  37    *   Splitting of the 39-bit block: [a-e][0-5] are the base-32 digits, *'s are used for base-7.
  38    *   +----------------+----------------+----------------+----------------+----------------+
  39    *   +00******e4e3e2e1|e0******d4d3d2d1|d0******c4c3c2c1|c0******b4b3b2b1|b0****a4a3a2a1a0|
  40    *   +----------------+----------------+----------------+----------------+----------------+
  41    */
  42
  43   w[0] = lo & 0x1f;
  44   w[1] = (lo >> 7) & 0x1f;
  45   w[2] = (lo >> 15) & 0x1f;
  46   w[3] = (lo >> 23) & 0x1f;
  47   w[4] = (lo >> 31) | ((hi << 1) & 0x1e);
  48   x = (lo >> 5)  & 0x0003
  49     | (lo >> 10) & 0x001c
  50     | (lo >> 15) & 0x00e0
  51     | (lo >> 20) & 0x0700
  52     | (hi << 7)  & 0x3800;
  53   DBG("<<< h=%08x l=%08x x=%d", hi, lo, x);
  54   for (y=0; y<5; y++)
  55     {
  56       w[y] += 0x20 + ((x % 7) << 5);
  57       x /= 7;
  58     }
  59 }
  60
  61 uns
  62 base224_encode(byte *dest, byte *src, uns len)
  63 {
  64   u32 lo=0, hi=0;                       /* 64-bit buffer accumulating input bits */
  65   uns i=0;                              /* How many source bits do we have buffered */
  66   u32 x;
  67   byte *w=dest;
  68
  69   while (len--)
  70     {
  71       x = *src++;
  72       if (i < 32)
  73         {
  74           lo |= x << i;
  75           if (i > 24)
  76             hi |= x >> (32-i);
  77         }
  78       else
  79         hi |= x << (i-32);
  80       i += 8;
  81       if (i >= 39)
  82         {
  83           encode_block(w, hi, lo);
  84           w += 5;
  85           lo = hi >> 7;
  86           hi = 0;
  87           i -= 39;
  88         }
  89     }
  90   if (i)                                /* Partial block */
  91     {
  92       encode_block(w, hi, lo);
  93       w += (i+8)/8;                     /* Just check logarithms if you want to understand */
  94     }
  95   return w - dest;
  96 }
  97
  98 uns
  99 base224_decode(byte *dest, byte *src, uns len)
 100 {
 101   u32 hi=0, lo=0;                       /* 64-bit buffer accumulating output bits */
 102   uns i=0;                              /* How many bits do we have accumulated */
 103   u32 h, l;                             /* Decoding of the current block */
 104   uns x;                                /* base-7 part of the current block */
 105   uns len0;
 106   byte *start = dest;
 107
 108   do
 109     {
 110       if (!len)
 111         break;
 112       len0 = len;
 113
 114       ASSERT(*src >= 0x20);             /* byte 0 */
 115       h = 0;
 116       l = *src & 0x1f;
 117       x = (*src++ >> 5) - 1;
 118       if (!--len)
 119         goto blockend;
 120
 121       ASSERT(*src >= 0x20);             /* byte 1 */
 122       l |= (*src & 0x1f) << 7;
 123       x += ((*src++ >> 5) - 1) * 7;
 124       if (!--len)
 125         goto blockend;
 126
 127       ASSERT(*src >= 0x20);             /* byte 2 */
 128       l |= (*src & 0x1f) << 15;
 129       x += ((*src++ >> 5) - 1) * 7*7;
 130       if (!--len)
 131         goto blockend;
 132
 133       ASSERT(*src >= 0x20);             /* byte 3 */
 134       l |= (*src & 0x1f) << 23;
 135       x += ((*src++ >> 5) - 1) * 7*7*7;
 136       if (!--len)
 137         goto blockend;
 138
 139       ASSERT(*src >= 0x20);             /* byte 4 */
 140       l |= *src << 31;
 141       h = (*src & 0x1f) >> 1;
 142       x += ((*src++ >> 5) - 1) * 7*7*7*7;
 143       --len;
 144
 145     blockend:
 146       len0 -= len;
 147       l |= ((x & 0x0003) << 5)          /* Decode base-7 */
 148         |  ((x & 0x001c) << 10)
 149         |  ((x & 0x00e0) << 15)
 150         |  ((x & 0x0700) << 20);
 151       h |=  (x & 0x3800) >> 7;
 152
 153       DBG("<<< i=%d h=%08x l=%08x x=%d len0=%d", i, h, l, x, len0);
 154       lo |= l << i;
 155       hi |= h << i;
 156       if (i)
 157         hi |= l >> (32-i);
 158       i += len0*8 - 1;
 159
 160       while (i >= 8)
 161         {
 162           *dest++ = lo;
 163           lo = (lo >> 8U) | (hi << 24);
 164           hi >>= 8;
 165           i -= 8;
 166         }
 167     }
 168   while (len0 == 5);
 169   return dest-start;
 170 }
 171
 172 #ifdef TEST
 173
 174 #include <stdio.h>
 175
 176 int main(int argc, char **argv)
 177 {
 178 #if 0
 179   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 };
 180   byte o[256], w[256];
 181   uns l;
 182   l = base224_encode(o, i, sizeof(i));
 183   fwrite(o, 1, l, stdout);
 184   fputc(0xaa, stdout);
 185   l = base224_decode(w, o, l);
 186   fwrite(w, 1, l, stdout);
 187 #else
 188   if (argc > 1)
 189     {
 190       byte i[BASE224_OUT_CHUNK*17], o[BASE224_IN_CHUNK*17];
 191       uns l;
 192       while (l = fread(i, 1, sizeof(i), stdin))
 193         {
 194           l = base224_decode(o, i, l);
 195           fwrite(o, 1, l, stdout);
 196         }
 197     }
 198   else
 199     {
 200       byte i[BASE224_IN_CHUNK*23], o[BASE224_OUT_CHUNK*23];
 201       uns l;
 202       while (l = fread(i, 1, sizeof(i), stdin))
 203         {
 204           l = base224_encode(o, i, l);
 205           fwrite(o, 1, l, stdout);
 206         }
 207     }
 208 #endif
 209
 210   return 0;
 211 }
 212
 213 #endif