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