src/libhaunp.c

   1 /***********************************************************************
   2  * This file is part of HA, a general purpose file archiver.
   3  * Copyright (C) 1995 Harri Hirvola
   4  * Modified by Ketmar // Invisible Vector
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  ***********************************************************************/
  20 #include <setjmp.h>
  21 #include <stddef.h>
  22 #include <stdint.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include "libhaunp.h"
  27
  28
  29 /******************************************************************************/
  30 enum {
  31   ERR_READ = 1,
  32   ERR_BAD_DATA
  33 };
  34
  35
  36 /******************************************************************************/
  37 #define POSCODES   (31200)
  38 #define SLCODES    (16)
  39 #define LLCODES    (48)
  40 #define LLLEN      (16)
  41 #define LLBITS     (4)
  42 #define LENCODES   (SLCODES+LLCODES*LLLEN)
  43 #define LTCODES    (SLCODES+LLCODES)
  44 #define CTCODES    (256)
  45 #define PTCODES    (16)
  46 #define LTSTEP     (8)
  47 #define MAXLT      (750*LTSTEP)
  48 #define CTSTEP     (1)
  49 #define MAXCT      (1000*CTSTEP)
  50 #define PTSTEP     (24)
  51 #define MAXPT      (250*PTSTEP)
  52 #define TTSTEP     (40)
  53 #define MAXTT      (150*TTSTEP)
  54 #define TTORD      (4)
  55 #define TTOMASK    (TTORD-1)
  56 #define LCUTOFF    (3*LTSTEP)
  57 #define CCUTOFF    (3*CTSTEP)
  58 #define CPLEN      (8)
  59 #define LPLEN      (4)
  60
  61
  62 /******************************************************************************/
  63 #define RD_BUF_SIZE  (32*1024)
  64 struct haunp_s {
  65   /* hup */
  66   uint16_t ltab[2*LTCODES];
  67   uint16_t eltab[2*LTCODES];
  68   uint16_t ptab[2*PTCODES];
  69   uint16_t ctab[2*CTCODES];
  70   uint16_t ectab[2*CTCODES];
  71   uint16_t ttab[TTORD][2];
  72   uint16_t accnt, pmax, npt;
  73   uint16_t ces;
  74   uint16_t les;
  75   uint16_t ttcon;
  76   /* swd */
  77   uint8_t dict[POSCODES];
  78   uint16_t dict_pos;
  79   uint16_t dict_pair_len;
  80   uint16_t dict_pair_pos;
  81   /* ari */
  82   uint16_t ari_h, ari_l, ari_v;
  83   int16_t ari_s;
  84   int16_t ari_gpat, ari_ppat;
  85   int ari_init_done;
  86   /* reader */
  87   haunp_bread_fn_t reader;
  88   uint8_t rd_buf[RD_BUF_SIZE];
  89   int rd_size;
  90   int rd_pos;
  91   int rd_max;
  92   int no_more; /* high-level flag: don't call read callback anymore  */
  93   /* for unpack-from-mem */
  94   const uint8_t *buf;
  95   size_t buf_left;
  96   /* other */
  97   void *udata;
  98   /* unpacker */
  99   int done;
 100   /* error exit */
 101   jmp_buf errJP;
 102 };
 103
 104
 105 /******************************************************************************/
 106 /* udata: haunp_t */
 107 static int haunp_buf_reader (void *buf, int buf_len, void *udata) {
 108   if (buf_len < 0) return 0;
 109   haunp_t hup = (haunp_t)udata;
 110   if (hup->buf_left > 0) {
 111     if ((size_t)buf_len > hup->buf_left) buf_len = hup->buf_left;
 112     memcpy(buf, hup->buf, buf_len);
 113     hup->buf += buf_len;
 114     hup->buf_left -= buf_len;
 115     return buf_len;
 116   }
 117   return 0;
 118 }
 119
 120
 121 /******************************************************************************/
 122 static inline void tabinit (uint16_t t[], uint16_t tl, uint16_t ival) {
 123   uint16_t i, j;
 124   for (i = tl; i < 2*tl; ++i) t[i] = ival;
 125   for (i = tl-1, j = (tl<<1)-2; i; --i, j -= 2) t[i] = t[j]+t[j+1];
 126 }
 127
 128
 129 static inline void tscale (uint16_t t[], uint16_t tl) {
 130   uint16_t i, j;
 131   for (i = (tl<<1)-1; i >= tl; --i) if (t[i] > 1) t[i] >>= 1;
 132   for (i = tl-1, j = (tl<<1)-2; i; --i, j -= 2) t[i] = t[j]+t[j+1];
 133 }
 134
 135
 136 static inline void tupd (uint16_t t[], uint16_t tl, uint16_t maxt, uint16_t step, uint16_t p) {
 137   int16_t i;
 138   for (i = p+tl; i; i >>= 1) t[i] += step;
 139   if (t[1] >= maxt) tscale(t, tl);
 140 }
 141
 142
 143 static inline void tzero (uint16_t t[], uint16_t tl, uint16_t p) {
 144   int16_t i, step;
 145   for (i = p+tl, step = t[i]; i; i >>= 1) t[i] -= step;
 146 }
 147
 148
 149 static inline void ttscale (haunp_t hup, uint16_t con) {
 150   hup->ttab[con][0] >>= 1;
 151   if (hup->ttab[con][0] == 0) hup->ttab[con][0] = 1;
 152   hup->ttab[con][1] >>= 1;
 153   if (hup->ttab[con][1] == 0) hup->ttab[con][1] = 1;
 154 }
 155
 156
 157 /******************************************************************************/
 158 /* return number of bytes copied (can be less thatn olen) */
 159 static inline int swd_do_pair (haunp_t hup, uint8_t *obuf, int olen) {
 160   int todo = (olen > hup->dict_pair_len ? hup->dict_pair_len : olen), res = todo;
 161   hup->dict_pair_len -= todo;
 162   while (todo-- > 0) {
 163     hup->dict[hup->dict_pos] = hup->dict[hup->dict_pair_pos];
 164     *obuf++ = hup->dict[hup->dict_pair_pos];
 165     if (++hup->dict_pos == POSCODES) hup->dict_pos = 0;
 166     if (++hup->dict_pair_pos == POSCODES) hup->dict_pair_pos = 0;
 167   }
 168   return res;
 169 }
 170
 171
 172 /******************************************************************************/
 173 /* Arithmetic decoding                                                        */
 174 /******************************************************************************/
 175 /* read next byte (buffered) */
 176 #define getbyte(bto)  do { \
 177   if (hup->rd_pos >= hup->rd_max && !hup->no_more) { \
 178     hup->rd_pos = 0; \
 179     hup->rd_max = hup->reader(hup->rd_buf, hup->rd_size, hup->udata); \
 180     hup->no_more = (hup->rd_max <= 0); \
 181     if (hup->rd_max < 0) longjmp(hup->errJP, ERR_READ); \
 182   } \
 183   bto = (!hup->no_more ? hup->rd_buf[hup->rd_pos++] : -1); \
 184 } while (0)
 185
 186
 187 #define getbit(b)  do { \
 188   hup->ari_gpat <<= 1; \
 189   if (!(hup->ari_gpat&0xff)) { \
 190     getbyte(hup->ari_gpat); \
 191     if (hup->ari_gpat&0x100) { \
 192       hup->ari_gpat = 0x100; \
 193     } else { \
 194       hup->ari_gpat <<= 1; \
 195       hup->ari_gpat |= 1; \
 196     } \
 197   } \
 198   b |= (hup->ari_gpat&0x100)>>8; \
 199 } while (0)
 200
 201
 202 static void ac_in (haunp_t hup, uint16_t low, uint16_t high, uint16_t tot) {
 203   uint32_t r;
 204   if (tot == 0) longjmp(hup->errJP, ERR_BAD_DATA);
 205   r = (uint32_t)(hup->ari_h-hup->ari_l)+1;
 206   hup->ari_h = (uint16_t)(r*high/tot-1)+hup->ari_l;
 207   hup->ari_l += (uint16_t)(r*low/tot);
 208   while (!((hup->ari_h^hup->ari_l)&0x8000)) {
 209     hup->ari_l <<= 1;
 210     hup->ari_h <<= 1;
 211     hup->ari_h |= 1;
 212     hup->ari_v <<= 1;
 213     getbit(hup->ari_v);
 214   }
 215   while ((hup->ari_l&0x4000) && !(hup->ari_h&0x4000)) {
 216     hup->ari_l <<= 1;
 217     hup->ari_l &= 0x7fff;
 218     hup->ari_h <<= 1;
 219     hup->ari_h |= 0x8001;
 220     hup->ari_v <<= 1;
 221     hup->ari_v ^= 0x8000;
 222     getbit(hup->ari_v);
 223   }
 224 }
 225
 226
 227 static inline uint16_t ac_threshold_val (haunp_t hup, uint16_t tot) {
 228   uint32_t r = (uint32_t)(hup->ari_h-hup->ari_l)+1;
 229   if (r == 0) longjmp(hup->errJP, ERR_BAD_DATA);
 230   return (uint16_t)((((uint32_t)(hup->ari_v-hup->ari_l)+1)*tot-1)/r);
 231 }
 232
 233
 234 /******************************************************************************/
 235 int haunp_reset_io (haunp_t hup, haunp_bread_fn_t reader, void *udata) {
 236   if (hup != NULL) {
 237     memset(hup, 0, sizeof(*hup));
 238     hup->reader = reader;
 239     hup->udata = udata;
 240     /* init dictionary */
 241     hup->dict_pos = 0;
 242     /* init model */
 243     hup->ces = CTSTEP;
 244     hup->les = LTSTEP;
 245     hup->accnt = 0;
 246     hup->ttcon = 0;
 247     hup->npt = hup->pmax = 1;
 248     for (int i = 0; i < TTORD; ++i) hup->ttab[i][0] = hup->ttab[i][1] = TTSTEP;
 249     tabinit(hup->ltab, LTCODES, 0);
 250     tabinit(hup->eltab, LTCODES, 1);
 251     tabinit(hup->ctab, CTCODES, 0);
 252     tabinit(hup->ectab, CTCODES, 1);
 253     tabinit(hup->ptab, PTCODES, 0);
 254     tupd(hup->ptab, PTCODES, MAXPT, PTSTEP, 0);
 255     /* init arithmetic decoder */
 256     hup->ari_h = 0xffff;
 257     hup->ari_l = 0;
 258     hup->ari_gpat = 0;
 259     hup->ari_init_done = 0; /* defer initialization */
 260     /* read buffer */
 261     hup->rd_size = RD_BUF_SIZE;
 262     hup->no_more = 0;
 263     return 0;
 264   }
 265   return -1;
 266 }
 267
 268
 269 int haunp_reset_buf (haunp_t hup, const void *buf, int buf_len) {
 270   if (hup != NULL) {
 271     haunp_reset_io(hup, haunp_buf_reader, NULL);
 272     hup->udata = hup;
 273     hup->buf = buf;
 274     hup->buf_left = (buf_len > 0 ? buf_len : 0);
 275     hup->no_more = (hup->buf_left == 0);
 276     return 0;
 277   }
 278   return -1;
 279 }
 280
 281
 282 haunp_t haunp_open_io (haunp_bread_fn_t reader, void *udata) {
 283   haunp_t hup = calloc(1, sizeof(*hup));
 284   if (hup != NULL) haunp_reset_io(hup, reader, udata);
 285   return hup;
 286 }
 287
 288
 289 haunp_t haunp_open_buf (const void *buf, int buf_len) {
 290   haunp_t hup = calloc(1, sizeof(*hup));
 291   if (hup != NULL) haunp_reset_buf(hup, buf, buf_len);
 292   return hup;
 293 }
 294
 295
 296 int haunp_close (haunp_t hup) {
 297   if (hup != NULL) free(hup);
 298   return 0;
 299 }
 300
 301
 302 /******************************************************************************/
 303 static void libha_unpack (haunp_t hup, uint8_t *obuf, int olen) {
 304   //uint16_t l, p, tv, i, lt;
 305   hup->done = 0;
 306   if (hup->no_more) return;
 307   /* complete defered ari initialization */
 308   if (!hup->ari_init_done) {
 309     uint8_t b;
 310     hup->ari_init_done = 1;
 311     getbyte(b);
 312     hup->ari_v = b<<8;
 313     getbyte(b);
 314     hup->ari_v |= b;
 315   }
 316 do_pair:
 317   /* if we have some data in dictionary, copy it */
 318   if (hup->dict_pair_len) {
 319     int d = swd_do_pair(hup, obuf, olen);
 320     hup->done += d;
 321     if ((olen -= d) == 0) return;
 322     obuf += d;
 323   }
 324   /* main unpacking loop; olen is definitely positive here */
 325   do {
 326     uint16_t l, p, lt;
 327     uint16_t tv = ac_threshold_val(hup, hup->ttab[hup->ttcon][0]+hup->ttab[hup->ttcon][1]+1);
 328     uint16_t i = hup->ttab[hup->ttcon][0]+hup->ttab[hup->ttcon][1];
 329     if (hup->ttab[hup->ttcon][0] > tv) {
 330       ac_in(hup, 0, hup->ttab[hup->ttcon][0], i+1);
 331       hup->ttab[hup->ttcon][0] += TTSTEP;
 332       if (i >= MAXTT) ttscale(hup, hup->ttcon);
 333       hup->ttcon = (hup->ttcon<<1)&TTOMASK;
 334       tv = ac_threshold_val(hup, hup->ctab[1]+hup->ces);
 335       if (tv >= hup->ctab[1]) {
 336         ac_in(hup, hup->ctab[1], hup->ctab[1]+hup->ces, hup->ctab[1]+hup->ces);
 337         tv = ac_threshold_val(hup, hup->ectab[1]);
 338         l = 2;
 339         lt = 0;
 340         for (;;) {
 341           if (lt+hup->ectab[l] <= tv) { lt += hup->ectab[l]; ++l; }
 342           if (l >= CTCODES) { l -= CTCODES; break; }
 343           l <<= 1;
 344         }
 345         ac_in(hup, lt, lt+hup->ectab[CTCODES+l], hup->ectab[1]);
 346         tzero(hup->ectab, CTCODES, l);
 347         if (hup->ectab[1] != 0) hup->ces += CTSTEP; else hup->ces = 0;
 348         for (i = (l < CPLEN ? 0 : l-CPLEN); i < (l+CPLEN >= CTCODES-1 ? CTCODES-1 : l+CPLEN); ++i) {
 349           if (hup->ectab[CTCODES+i]) tupd(hup->ectab, CTCODES, MAXCT, 1, i);
 350         }
 351       } else {
 352         l = 2;
 353         lt = 0;
 354         for (;;) {
 355           if (lt+hup->ctab[l] <= tv) { lt += hup->ctab[l]; ++l; }
 356           if (l >= CTCODES) { l -= CTCODES; break; }
 357           l <<= 1;
 358         }
 359         ac_in(hup, lt, lt+hup->ctab[CTCODES+l], hup->ctab[1]+hup->ces);
 360       }
 361       tupd(hup->ctab, CTCODES, MAXCT, CTSTEP, l);
 362       if (hup->ctab[CTCODES+l] == CCUTOFF) hup->ces -= (CTSTEP < hup->ces ? CTSTEP : hup->ces-1);
 363       /* literal char from dictionary */
 364       hup->dict[hup->dict_pos] = l;
 365       if (++hup->dict_pos == POSCODES) hup->dict_pos = 0;
 366       /* asc decoder */
 367       if (hup->accnt < POSCODES) ++hup->accnt;
 368       /* output char */
 369       *obuf++ = l;
 370       --olen;
 371       ++hup->done;
 372     } else if (i > tv) {
 373       ac_in(hup, hup->ttab[hup->ttcon][0], i, i+1);
 374       hup->ttab[hup->ttcon][1] += TTSTEP;
 375       if (i >= MAXTT) ttscale(hup, hup->ttcon);
 376       hup->ttcon = ((hup->ttcon<<1)|1)&TTOMASK;
 377       while (hup->accnt > hup->pmax) {
 378         tupd(hup->ptab, PTCODES, MAXPT, PTSTEP, hup->npt++);
 379         hup->pmax <<= 1;
 380       }
 381       tv = ac_threshold_val(hup, hup->ptab[1]);
 382       p = 2;
 383       lt = 0;
 384       for (;;) {
 385         if (lt+hup->ptab[p] <= tv) { lt += hup->ptab[p]; ++p; }
 386         if (p >= PTCODES) { p -= PTCODES; break; }
 387         p <<= 1;
 388       }
 389       ac_in(hup, lt, lt+hup->ptab[PTCODES+p], hup->ptab[1]);
 390       tupd(hup->ptab, PTCODES, MAXPT, PTSTEP, p);
 391       if (p > 1) {
 392         for (i = 1; p; i <<= 1, --p) ;
 393         i >>= 1;
 394         l = (i == hup->pmax>>1 ? hup->accnt-(hup->pmax>>1) : i);
 395         p = ac_threshold_val(hup, l);
 396         ac_in(hup, p, p+1, l);
 397         p += i;
 398       }
 399       tv = ac_threshold_val(hup, hup->ltab[1]+hup->les);
 400       if (tv >= hup->ltab[1]) {
 401         ac_in(hup, hup->ltab[1], hup->ltab[1]+hup->les, hup->ltab[1]+hup->les);
 402         tv = ac_threshold_val(hup, hup->eltab[1]);
 403         l = 2;
 404         lt = 0;
 405         for (;;) {
 406           if (lt+hup->eltab[l] <= tv) { lt += hup->eltab[l]; ++l; }
 407           if (l >= LTCODES) { l -= LTCODES; break; }
 408           l <<= 1;
 409         }
 410         ac_in(hup, lt, lt+hup->eltab[LTCODES+l], hup->eltab[1]);
 411         tzero(hup->eltab, LTCODES, l);
 412         if (hup->eltab[1] != 0) hup->les += LTSTEP; else hup->les = 0;
 413         for (i = l < LPLEN ? 0 : l-LPLEN; i < (l+LPLEN >= LTCODES-1 ? LTCODES-1 : l+LPLEN); ++i) {
 414           if (hup->eltab[LTCODES+i]) tupd(hup->eltab, LTCODES, MAXLT, 1, i);
 415         }
 416       } else {
 417         l = 2;
 418         lt = 0;
 419         for (;;) {
 420           if (lt+hup->ltab[l] <= tv) { lt += hup->ltab[l]; ++l; }
 421           if (l >= LTCODES) { l -= LTCODES; break; }
 422           l <<= 1;
 423         }
 424         ac_in(hup, lt, lt+hup->ltab[LTCODES+l], hup->ltab[1]+hup->les);
 425       }
 426       tupd(hup->ltab, LTCODES, MAXLT, LTSTEP, l);
 427       if (hup->ltab[LTCODES+l] == LCUTOFF) hup->les -= (LTSTEP < hup->les ? LTSTEP : hup->les-1);
 428       if (l == SLCODES-1) {
 429         l = LENCODES-1;
 430       } else if (l >= SLCODES) {
 431         i = ac_threshold_val(hup, LLLEN);
 432         ac_in(hup, i, i+1, LLLEN);
 433         l = ((l-SLCODES)<<LLBITS)+i+SLCODES-1;
 434       }
 435       l += 3;
 436       if (hup->accnt < POSCODES) {
 437         hup->accnt += l;
 438         if (hup->accnt > POSCODES) hup->accnt = POSCODES;
 439       }
 440       /* pair from dictionary */
 441       if (hup->dict_pos > p) {
 442         hup->dict_pair_pos = hup->dict_pos-1-p;
 443       } else {
 444         hup->dict_pair_pos = POSCODES-1-p+hup->dict_pos;
 445       }
 446       hup->dict_pair_len = l;
 447       goto do_pair; /* recursive tail call */
 448     } else {
 449       /*EOF*/
 450       /*ac_in(hup, i, i+1, i+1); don't need this*/
 451       hup->no_more = 1;
 452       break;
 453     }
 454   } while (olen > 0);
 455 }
 456
 457
 458 /* return number of bytes read (<len: end of data) or -1 on error */
 459 int haunp_read (haunp_t hup, void *buf, int len) {
 460   if (buf == NULL && len < 1) return 0;
 461   if (hup != NULL) {
 462     volatile int jr = setjmp(hup->errJP);
 463     if (jr == 0) {
 464       hup->done = 0;
 465       libha_unpack(hup, buf, len);
 466     }
 467     return hup->done;
 468   }
 469   return -1;
 470 }
 471
 472
 473 /******************************************************************************/
 474 #ifndef LIBHAUNP_DISABLE_CRC
 475 static const uint32_t crctab[16] = {
 476   0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac,
 477   0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,
 478   0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c,
 479   0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c,
 480 };
 481
 482
 483 unsigned int haunp_crc32 (const void *src, int len) {
 484   uint32_t crc = 0xffffffffUL;
 485   if (src != NULL && len > 0) {
 486     const uint8_t *buf = (const uint8_t *)src;
 487     while (len--) {
 488       crc ^= *buf++;
 489       crc = crctab[crc&0x0f]^(crc>>4);
 490       crc = crctab[crc&0x0f]^(crc>>4);
 491     }
 492   }
 493   return crc^0xffffffffUL;
 494 }
 495
 496
 497 unsigned int haunp_crc32_begin (void) {
 498   return 0xffffffffUL;
 499 }
 500
 501
 502 unsigned int haunp_crc32_end (unsigned int crc) {
 503   return crc^0xffffffffUL;
 504 }
 505
 506
 507 unsigned int haunp_crc32_part (unsigned int crc, const void *src, int len) {
 508   if (src != NULL && len > 0) {
 509     const uint8_t *buf = (const uint8_t *)src;
 510     while (len--) {
 511       crc ^= *buf++;
 512       crc = crctab[crc&0x0f]^(crc>>4);
 513       crc = crctab[crc&0x0f]^(crc>>4);
 514     }
 515   }
 516   return crc;
 517 }
 518 #endif