src/libdernc.c

   1 /*
   2  * dernc.c   decompress RNC data
   3  *
   4  * Compiled normally, this file is a well-behaved, re-entrant code
   5  * module exporting only `rnc_ulen', `rnc_unpack' and `rnc_error'.
   6  * Compiled with MAIN defined, it's a standalone program which will
   7  * decompress argv[1] into argv[2].
   8  */
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12
  13 #include "libdernc.h"
  14
  15
  16 ////////////////////////////////////////////////////////////////////////////////
  17 typedef struct {
  18   unsigned int bitbuf; /* holds between 16 and 32 bits */
  19   int bitcount;        /* how many bits does bitbuf hold? */
  20 } bit_stream;
  21
  22
  23 typedef struct {
  24   int num;             /* number of nodes in the tree */
  25   struct {
  26     unsigned int code;
  27     int codelen;
  28     int value;
  29   } table[32];
  30 } huf_table;
  31
  32
  33 ////////////////////////////////////////////////////////////////////////////////
  34 /*
  35  * Return the big-endian longword at p.
  36  */
  37 static inline unsigned int blong (unsigned char *p) {
  38   unsigned int n;
  39   //
  40   n = p[0];
  41   n = (n<<8)+p[1];
  42   n = (n<<8)+p[2];
  43   n = (n<<8)+p[3];
  44   return n;
  45 }
  46
  47
  48 /*
  49  * Return the little-endian longword at p.
  50  */
  51 /*
  52 static inline unsigned int llong (unsigned char *p) {
  53   unsigned int n;
  54   //
  55   n = p[3];
  56   n = (n<<8)+p[2];
  57   n = (n<<8)+p[1];
  58   n = (n<<8)+p[0];
  59   return n;
  60 }
  61 */
  62
  63
  64 /*
  65  * Return the big-endian word at p.
  66  */
  67 static inline unsigned int bword (unsigned char *p) {
  68   unsigned int n;
  69   //
  70   n = p[0];
  71   n = (n<<8)+p[1];
  72   return n;
  73 }
  74
  75
  76 /*
  77  * Return the little-endian word at p.
  78  */
  79 static inline unsigned int lword (unsigned char *p) {
  80   unsigned int n;
  81   //
  82   n = p[1];
  83   n = (n<<8)+p[0];
  84   return n;
  85 }
  86
  87
  88 /*
  89  * Mirror the bottom n bits of x.
  90  */
  91 static inline unsigned int mirror (unsigned int x, int n) {
  92   unsigned int top = 1<<(n-1), bottom = 1;
  93   //
  94   while (top > bottom) {
  95     unsigned int mask = top|bottom;
  96     unsigned int masked = x&mask;
  97     //
  98     if (masked != 0 && masked != mask) x ^= mask;
  99     top >>= 1;
 100     bottom <<= 1;
 101   }
 102   return x;
 103 }
 104
 105
 106 /*
 107  * Initialises a bit stream with the first two bytes of the packed
 108  * data.
 109  */
 110 static inline void bitread_init (bit_stream *bs, unsigned char **p) {
 111   bs->bitbuf = lword (*p);
 112   bs->bitcount = 16;
 113 }
 114
 115
 116 /*
 117  * Fixes up a bit stream after literals have been read out of the
 118  * data stream.
 119  */
 120 static inline void bitread_fix (bit_stream *bs, unsigned char **p) {
 121   bs->bitcount -= 16;
 122   bs->bitbuf &= (1<<bs->bitcount)-1; /* remove the top 16 bits */
 123   bs->bitbuf |= (lword(*p)<<bs->bitcount); /* replace with what's at *p */
 124   bs->bitcount += 16;
 125 }
 126
 127
 128 /*
 129  * Returns some bits.
 130  */
 131 static inline unsigned int bit_peek (bit_stream *bs, unsigned int mask) {
 132   return bs->bitbuf&mask;
 133 }
 134
 135
 136 /*
 137  * Advances the bit stream.
 138  */
 139 static inline void bit_advance (bit_stream *bs, int n, unsigned char **p) {
 140   bs->bitbuf >>= n;
 141   bs->bitcount -= n;
 142   if (bs->bitcount < 16) {
 143     (*p) += 2;
 144     bs->bitbuf |= (lword(*p)<<bs->bitcount);
 145     bs->bitcount += 16;
 146   }
 147 }
 148
 149
 150 /*
 151  * Reads some bits in one go (ie the above two routines combined).
 152  */
 153 static inline unsigned int bit_read (bit_stream *bs, unsigned int mask, int n, unsigned char **p) {
 154   unsigned int result = bit_peek(bs, mask);
 155   //
 156   bit_advance(bs, n, p);
 157   return result;
 158 }
 159
 160
 161 /*
 162  * Read a Huffman table out of the bit stream and data stream given.
 163  */
 164 static void read_huftable (huf_table *h, bit_stream *bs, unsigned char **p) {
 165   int k, num;
 166   int leaflen[32];
 167   int leafmax;
 168   unsigned int codeb; /* big-endian form of code */
 169   //
 170   num = bit_read(bs, 0x1f, 5, p);
 171   if (!num) return;
 172   leafmax = 1;
 173   for (int i = 0; i < num; ++i) {
 174     leaflen[i] = bit_read(bs, 0x0F, 4, p);
 175     if (leafmax < leaflen[i]) leafmax = leaflen[i];
 176   }
 177   codeb = 0L;
 178   k = 0;
 179   for (int i = 1; i <= leafmax; ++i) {
 180     for (int j = 0; j < num; ++j) {
 181       if (leaflen[j] == i) {
 182         h->table[k].code = mirror(codeb, i);
 183         h->table[k].codelen = i;
 184         h->table[k].value = j;
 185         ++codeb;
 186         ++k;
 187       }
 188     }
 189     codeb <<= 1;
 190   }
 191   h->num = k;
 192 }
 193
 194
 195 /*
 196  * Read a value out of the bit stream using the given Huffman table.
 197  */
 198 static unsigned int huf_read (huf_table *h, bit_stream *bs, unsigned char **p) {
 199   int i;
 200   unsigned int val;
 201   //
 202   for (i = 0; i < h->num; i++) {
 203     unsigned int mask = (1<<h->table[i].codelen)-1;
 204     //
 205     if (bit_peek(bs, mask) == h->table[i].code) break;
 206   }
 207   if (i == h->num) return -1;
 208   bit_advance(bs, h->table[i].codelen, p);
 209   val = h->table[i].value;
 210   if (val >= 2) {
 211     val = 1<<(val-1);
 212     val |= bit_read (bs, val-1, h->table[i].value-1, p);
 213   }
 214   return val;
 215 }
 216
 217
 218 ////////////////////////////////////////////////////////////////////////////////
 219 /*
 220  * Decompress a packed data block. Returns the unpacked length if
 221  * successful, or negative error codes if not.
 222  *
 223  * If COMPRESSOR is defined, it also returns the leeway number
 224  * (which gets stored at offset 16 into the compressed-file header)
 225  * in `*leeway', if `leeway' isn't NULL.
 226  */
 227 int rnc_unpack (void *packed, void *unpacked, int *leeway) {
 228   unsigned char *input = packed;
 229   unsigned char *output = unpacked;
 230   unsigned char *inputend, *outputend;
 231   bit_stream bs;
 232   huf_table raw, dist, len;
 233   unsigned int ch_count;
 234   unsigned int ret_len;
 235   unsigned out_crc;
 236   int lee = 0;
 237   //
 238   if (blong(input) != RNC_SIGNATURE) return RNC_FILE_IS_NOT_RNC;
 239   ret_len = blong(input+4);
 240   outputend = output+ret_len;
 241   inputend = input+18+blong(input+8);
 242   input += 18; /* skip header */
 243   // check the packed-data CRC. Also save the unpacked-data CRC for later
 244   if (rnc_crc(input, inputend-input) != bword(input-4)) return RNC_PACKED_CRC_ERROR;
 245   out_crc = bword(input-6);
 246   bitread_init(&bs, &input);
 247   bit_advance(&bs, 2, &input); /* discard first two bits */
 248   // process chunks
 249   while (output < outputend) {
 250     int this_lee;
 251     //
 252     read_huftable(&raw, &bs, &input);
 253     read_huftable(&dist, &bs, &input);
 254     read_huftable(&len, &bs, &input);
 255     ch_count = bit_read(&bs, 0xffff, 16, &input);
 256     //
 257     for (;;) {
 258       int length, posn;
 259       //
 260       length = huf_read(&raw, &bs, &input);
 261       if (length == -1) return RNC_HUF_DECODE_ERROR;
 262       if (length) {
 263         while (length--) *output++ = *input++;
 264         bitread_fix(&bs, &input);
 265       }
 266       if (--ch_count <= 0) break;
 267       posn = huf_read(&dist, &bs, &input);
 268       if (posn == -1) return RNC_HUF_DECODE_ERROR;
 269       length = huf_read(&len, &bs, &input);
 270       if (length == -1) return RNC_HUF_DECODE_ERROR;
 271       posn += 1;
 272       length += 2;
 273       while (length--) {
 274         *output = output[-posn];
 275         ++output;
 276       }
 277       this_lee = (inputend-input)-(outputend-output);
 278       if (lee < this_lee) lee = this_lee;
 279     }
 280   }
 281   //
 282   if (outputend != output) return RNC_FILE_SIZE_MISMATCH;
 283   if (leeway) *leeway = lee;
 284   // check the unpacked-data CRC
 285   if (rnc_crc(outputend-ret_len, ret_len) != out_crc) return RNC_UNPACKED_CRC_ERROR;
 286   return ret_len;
 287 }
 288
 289
 290 ////////////////////////////////////////////////////////////////////////////////
 291 /*
 292  * Return the uncompressed length of a packed data block, or a
 293  * negative error code.
 294  */
 295 int rnc_ulen (void *packed) {
 296   unsigned char *p = packed;
 297   //
 298   if (blong(p) != RNC_SIGNATURE) return RNC_FILE_IS_NOT_RNC;
 299   return blong(p+4);
 300 }
 301
 302
 303 ////////////////////////////////////////////////////////////////////////////////
 304 /*
 305  * Calculate a CRC, the RNC way.
 306  */
 307 int rnc_crc (void *data, int len) {
 308   static int initialized = 0;
 309   static unsigned short crctab[256];
 310   unsigned short val;
 311   unsigned char *p = data;
 312   //
 313   if (!initialized) {
 314     for (int i = 0; i < 256; ++i) {
 315       val = i;
 316       for (int j = 0; j < 8; ++j) if (val&1) val = (val>>1)^0xA001; else val = (val>>1);
 317       crctab[i] = val;
 318     }
 319   }
 320   //
 321   val = 0;
 322   while (len-- > 0) {
 323     val ^= *p++;
 324     val = (val>>8)^crctab[val&0xFF];
 325   }
 326   //
 327   return val;
 328 }
 329
 330
 331 ////////////////////////////////////////////////////////////////////////////////
 332 /*
 333  * Return an error string corresponding to an error return code.
 334  */
 335 const char *rnc_error (int errcode) {
 336   static const char *const errors[] = {
 337     "No error",
 338     "File is not RNC-1 format",
 339     "Huffman decode error",
 340     "File size mismatch",
 341     "CRC error in packed data",
 342     "CRC error in unpacked data",
 343     "Unknown error"
 344   };
 345   //
 346   errcode = -errcode;
 347   if (errcode < 0) errcode = 0;
 348   if (errcode > sizeof(errors)/sizeof(*errors)-1) errcode = sizeof(errors)/sizeof(*errors)-1;
 349   return errors[errcode];
 350 }