libogc/depackrnc1.c

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