oldpakerz/haunpack.d

   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 // stand-alone unpacker
  21 module iv.oldpakerz.haunpack /*is aliced*/;
  22 private:
  23 import iv.alice;
  24
  25
  26 // ////////////////////////////////////////////////////////////////////////// //
  27 // <0: error; 0: EOF; >0: bytes read (can be less that buf_len)
  28 // buf_len can never be negative or zero; it will not be more that INT_MAX/2-1 either
  29 public alias haunp_bread_fn_t = int delegate (void* buf, int buf_len);
  30
  31
  32 public alias haunp_t = haunp_s*;
  33
  34
  35 // ////////////////////////////////////////////////////////////////////////// //
  36 enum POSCODES = 31200;
  37 enum SLCODES = 16;
  38 enum LLCODES = 48;
  39 enum LLLEN = 16;
  40 enum LLBITS = 4;
  41 enum LENCODES = SLCODES+LLCODES*LLLEN;
  42 enum LTCODES = SLCODES+LLCODES;
  43 enum CTCODES = 256;
  44 enum PTCODES = 16;
  45 enum LTSTEP = 8;
  46 enum MAXLT = 750*LTSTEP;
  47 enum CTSTEP = 1;
  48 enum MAXCT = 1000*CTSTEP;
  49 enum PTSTEP = 24;
  50 enum MAXPT = 250*PTSTEP;
  51 enum TTSTEP = 40;
  52 enum MAXTT = 150*TTSTEP;
  53 enum TTORD = 4;
  54 enum TTOMASK = TTORD-1;
  55 enum LCUTOFF = 3*LTSTEP;
  56 enum CCUTOFF = 3*CTSTEP;
  57 enum CPLEN = 8;
  58 enum LPLEN = 4;
  59
  60
  61 // ////////////////////////////////////////////////////////////////////////// //
  62 struct haunp_s {
  63   enum RD_BUF_SIZE = 1024;
  64   // hup
  65   ushort[2*LTCODES] ltab;
  66   ushort[2*LTCODES] eltab;
  67   ushort[2*PTCODES] ptab;
  68   ushort[2*CTCODES] ctab;
  69   ushort[2*CTCODES] ectab;
  70   ushort[2][TTORD] ttab;
  71   ushort accnt, pmax, npt;
  72   ushort ces;
  73   ushort les;
  74   ushort ttcon;
  75   // swd
  76   ubyte[POSCODES] dict;
  77   ushort dict_pos;
  78   ushort dict_pair_len;
  79   ushort dict_pair_pos;
  80   // ari
  81   ushort ari_h, ari_l, ari_v;
  82   short ari_s;
  83   short ari_gpat, ari_ppat;
  84   int ari_init_done;
  85   // reader
  86   haunp_bread_fn_t reader;
  87   ubyte[RD_BUF_SIZE] rd_buf;
  88   int rd_pos;
  89   int rd_max;
  90   bool no_more; // high-level flag: don't call read callback anymore
  91   // unpacker
  92   int done;
  93 }
  94 version(oldpack_sizes) pragma(msg, haunp_s.sizeof);
  95
  96
  97 // ////////////////////////////////////////////////////////////////////////// //
  98 void tabinit (ushort[] t, ushort tl, ushort ival) {
  99   /*ushort*/uint i, j;
 100   for (i = tl; i < 2*tl; ++i) t[i] = ival;
 101   for (i = tl-1, j = (tl<<1)-2; i; --i, j -= 2) t[i] = cast(ushort)(t[j]+t[j+1]);
 102 }
 103
 104
 105 void tscale (ushort[] t, ushort tl) {
 106   /*ushort*/uint i, j;
 107   for (i = (tl<<1)-1; i >= tl; --i) if (t[i] > 1) t[i] >>= 1;
 108   for (i = tl-1, j = (tl<<1)-2; i; --i, j -= 2) t[i] = cast(ushort)(t[j]+t[j+1]);
 109 }
 110
 111
 112 void tupd (ushort[] t, ushort tl, ushort maxt, ushort step, ushort p) {
 113   int i;
 114   for (i = p+tl; i; i >>= 1) t[i] += step;
 115   if (t[1] >= maxt) tscale(t, tl);
 116 }
 117
 118
 119 void tzero (ushort[] t, ushort tl, ushort p) {
 120   int i;
 121   short step;
 122   for (i = p+tl, step = t[i]; i; i >>= 1) t[i] -= step;
 123 }
 124
 125
 126 void ttscale (haunp_t hup, ushort con) {
 127   hup.ttab[con][0] >>= 1;
 128   if (hup.ttab[con][0] == 0) hup.ttab[con][0] = 1;
 129   hup.ttab[con][1] >>= 1;
 130   if (hup.ttab[con][1] == 0) hup.ttab[con][1] = 1;
 131 }
 132
 133
 134 // ////////////////////////////////////////////////////////////////////////// //
 135 // return number of bytes copied (can be less thatn olen)
 136 int swd_do_pair (haunp_t hup, ubyte* obuf, int olen) {
 137   int todo = (olen > hup.dict_pair_len ? hup.dict_pair_len : olen);
 138   int res = todo;
 139   hup.dict_pair_len -= todo;
 140   while (todo-- > 0) {
 141     hup.dict[hup.dict_pos] = hup.dict[hup.dict_pair_pos];
 142     *obuf++ = hup.dict[hup.dict_pair_pos];
 143     if (++hup.dict_pos == POSCODES) hup.dict_pos = 0;
 144     if (++hup.dict_pair_pos == POSCODES) hup.dict_pair_pos = 0;
 145   }
 146   return res;
 147 }
 148
 149
 150 // ////////////////////////////////////////////////////////////////////////// //
 151 // Arithmetic decoding
 152
 153 // read next byte (buffered)
 154 enum getbyte(string bto) = "{
 155   if (hup.rd_pos >= hup.rd_max && !hup.no_more) {
 156     hup.rd_pos = 0;
 157     hup.rd_max = hup.reader(hup.rd_buf.ptr, hup.RD_BUF_SIZE);
 158     hup.no_more = (hup.rd_max <= 0);
 159     if (hup.rd_max < 0) throw new Exception(`read error`);
 160   }
 161   "~bto~" = (!hup.no_more ? hup.rd_buf[hup.rd_pos++] : -1);
 162 }";
 163
 164
 165 enum getbit(string b) = "{
 166   hup.ari_gpat <<= 1;
 167   if (!(hup.ari_gpat&0xff)) {
 168     "~getbyte!"hup.ari_gpat"~"
 169     if (hup.ari_gpat&0x100) {
 170       hup.ari_gpat = 0x100;
 171     } else {
 172       hup.ari_gpat <<= 1;
 173       hup.ari_gpat |= 1;
 174     }
 175   }
 176   "~b~" |= (hup.ari_gpat&0x100)>>8;
 177 }";
 178
 179
 180 void ac_in (haunp_t hup, ushort low, ushort high, ushort tot) {
 181   uint r;
 182   if (tot == 0) throw new Exception("bad data");
 183   r = cast(uint)(hup.ari_h-hup.ari_l)+1;
 184   hup.ari_h = cast(ushort)(cast(ushort)(r*high/tot-1)+hup.ari_l);
 185   hup.ari_l += cast(ushort)(r*low/tot);
 186   while (!((hup.ari_h^hup.ari_l)&0x8000)) {
 187     hup.ari_l <<= 1;
 188     hup.ari_h <<= 1;
 189     hup.ari_h |= 1;
 190     hup.ari_v <<= 1;
 191     mixin(getbit!"hup.ari_v");
 192   }
 193   while ((hup.ari_l&0x4000) && !(hup.ari_h&0x4000)) {
 194     hup.ari_l <<= 1;
 195     hup.ari_l &= 0x7fff;
 196     hup.ari_h <<= 1;
 197     hup.ari_h |= 0x8001;
 198     hup.ari_v <<= 1;
 199     hup.ari_v ^= 0x8000;
 200     mixin(getbit!"hup.ari_v");
 201   }
 202 }
 203
 204
 205 ushort ac_threshold_val (haunp_t hup, ushort tot) {
 206   uint r = cast(uint)(hup.ari_h-hup.ari_l)+1;
 207   if (r == 0) throw new Exception("bad data");
 208   return cast(ushort)(((cast(uint)(hup.ari_v-hup.ari_l)+1)*tot-1)/r);
 209 }
 210
 211
 212 // ////////////////////////////////////////////////////////////////////////// //
 213 void libha_unpack (haunp_t hup, ubyte* obuf, int olen) {
 214   //ushort l, p, tv, i, lt;
 215   hup.done = 0;
 216   if (hup.no_more) return;
 217   // complete defered ari initialization
 218   if (!hup.ari_init_done) {
 219     int b;
 220     hup.ari_init_done = 1;
 221     mixin(getbyte!"b");
 222     if (b < 0) throw new Exception("read error");
 223     hup.ari_v = cast(ushort)(b<<8);
 224     mixin(getbyte!"b");
 225     if (b < 0) throw new Exception("read error");
 226     hup.ari_v |= b;
 227   }
 228  do_pair:
 229   // if we have some data in dictionary, copy it
 230   if (hup.dict_pair_len) {
 231     int d = swd_do_pair(hup, obuf, olen);
 232     hup.done += d;
 233     if ((olen -= d) == 0) return;
 234     obuf += d;
 235   }
 236   // main unpacking loop; olen is definitely positive here
 237   do {
 238     ushort l, p, lt;
 239     ushort tv = ac_threshold_val(hup, cast(ushort)(hup.ttab[hup.ttcon][0]+hup.ttab[hup.ttcon][1]+1));
 240     ushort i = cast(ushort)(hup.ttab[hup.ttcon][0]+hup.ttab[hup.ttcon][1]);
 241     if (hup.ttab[hup.ttcon][0] > tv) {
 242       ac_in(hup, 0, hup.ttab[hup.ttcon][0], cast(ushort)(i+1));
 243       hup.ttab[hup.ttcon][0] += TTSTEP;
 244       if (i >= MAXTT) ttscale(hup, hup.ttcon);
 245       hup.ttcon = (hup.ttcon<<1)&TTOMASK;
 246       tv = ac_threshold_val(hup, cast(ushort)(hup.ctab[1]+hup.ces));
 247       if (tv >= hup.ctab[1]) {
 248         ac_in(hup, hup.ctab[1], cast(ushort)(hup.ctab[1]+hup.ces), cast(ushort)(hup.ctab[1]+hup.ces));
 249         tv = ac_threshold_val(hup, hup.ectab[1]);
 250         l = 2;
 251         lt = 0;
 252         for (;;) {
 253           if (lt+hup.ectab[l] <= tv) { lt += hup.ectab[l]; ++l; }
 254           if (l >= CTCODES) { l -= CTCODES; break; }
 255           l <<= 1;
 256         }
 257         ac_in(hup, lt, cast(ushort)(lt+hup.ectab[CTCODES+l]), hup.ectab[1]);
 258         tzero(hup.ectab, CTCODES, l);
 259         if (hup.ectab[1] != 0) hup.ces += CTSTEP; else hup.ces = 0;
 260         for (i = cast(ushort)(l < CPLEN ? 0 : l-CPLEN); i < (l+CPLEN >= CTCODES-1 ? CTCODES-1 : l+CPLEN); ++i) {
 261           if (hup.ectab[CTCODES+i]) tupd(hup.ectab, CTCODES, MAXCT, 1, i);
 262         }
 263       } else {
 264         l = 2;
 265         lt = 0;
 266         for (;;) {
 267           if (lt+hup.ctab[l] <= tv) { lt += hup.ctab[l]; ++l; }
 268           if (l >= CTCODES) { l -= CTCODES; break; }
 269           l <<= 1;
 270         }
 271         ac_in(hup, lt, cast(ushort)(lt+hup.ctab[CTCODES+l]), cast(ushort)(hup.ctab[1]+hup.ces));
 272       }
 273       tupd(hup.ctab, CTCODES, MAXCT, CTSTEP, l);
 274       if (hup.ctab[CTCODES+l] == CCUTOFF) hup.ces -= (CTSTEP < hup.ces ? CTSTEP : hup.ces-1);
 275       // literal char from dictionary
 276       hup.dict[hup.dict_pos] = cast(ubyte)l;
 277       if (++hup.dict_pos == POSCODES) hup.dict_pos = 0;
 278       // asc decoder
 279       if (hup.accnt < POSCODES) ++hup.accnt;
 280       // output char
 281       *obuf++ = cast(ubyte)l;
 282       --olen;
 283       ++hup.done;
 284     } else if (i > tv) {
 285       ac_in(hup, hup.ttab[hup.ttcon][0], i, cast(ushort)(i+1));
 286       hup.ttab[hup.ttcon][1] += TTSTEP;
 287       if (i >= MAXTT) ttscale(hup, hup.ttcon);
 288       hup.ttcon = ((hup.ttcon<<1)|1)&TTOMASK;
 289       while (hup.accnt > hup.pmax) {
 290         tupd(hup.ptab, PTCODES, MAXPT, PTSTEP, hup.npt++);
 291         hup.pmax <<= 1;
 292       }
 293       tv = ac_threshold_val(hup, hup.ptab[1]);
 294       p = 2;
 295       lt = 0;
 296       for (;;) {
 297         if (lt+hup.ptab[p] <= tv) { lt += hup.ptab[p]; ++p; }
 298         if (p >= PTCODES) { p -= PTCODES; break; }
 299         p <<= 1;
 300       }
 301       ac_in(hup, lt, cast(ushort)(lt+hup.ptab[PTCODES+p]), hup.ptab[1]);
 302       tupd(hup.ptab, PTCODES, MAXPT, PTSTEP, p);
 303       if (p > 1) {
 304         for (i = 1; p; i <<= 1, --p) {}
 305         i >>= 1;
 306         l = cast(ushort)(i == hup.pmax>>1 ? hup.accnt-(hup.pmax>>1) : i);
 307         p = ac_threshold_val(hup, l);
 308         ac_in(hup, p, cast(ushort)(p+1), l);
 309         p += i;
 310       }
 311       tv = ac_threshold_val(hup, cast(ushort)(hup.ltab[1]+hup.les));
 312       if (tv >= hup.ltab[1]) {
 313         ac_in(hup, hup.ltab[1], cast(ushort)(hup.ltab[1]+hup.les), cast(ushort)(hup.ltab[1]+hup.les));
 314         tv = ac_threshold_val(hup, hup.eltab[1]);
 315         l = 2;
 316         lt = 0;
 317         for (;;) {
 318           if (lt+hup.eltab[l] <= tv) { lt += hup.eltab[l]; ++l; }
 319           if (l >= LTCODES) { l -= LTCODES; break; }
 320           l <<= 1;
 321         }
 322         ac_in(hup, lt, cast(ushort)(lt+hup.eltab[LTCODES+l]), hup.eltab[1]);
 323         tzero(hup.eltab, LTCODES, l);
 324         if (hup.eltab[1] != 0) hup.les += LTSTEP; else hup.les = 0;
 325         for (i = cast(ushort)(l < LPLEN ? 0 : l-LPLEN); i < (l+LPLEN >= LTCODES-1 ? LTCODES-1 : l+LPLEN); ++i) {
 326           if (hup.eltab[LTCODES+i]) tupd(hup.eltab, LTCODES, MAXLT, 1, i);
 327         }
 328       } else {
 329         l = 2;
 330         lt = 0;
 331         for (;;) {
 332           if (lt+hup.ltab[l] <= tv) { lt += hup.ltab[l]; ++l; }
 333           if (l >= LTCODES) { l -= LTCODES; break; }
 334           l <<= 1;
 335         }
 336         ac_in(hup, lt, cast(ushort)(lt+hup.ltab[LTCODES+l]), cast(ushort)(hup.ltab[1]+hup.les));
 337       }
 338       tupd(hup.ltab, LTCODES, MAXLT, LTSTEP, l);
 339       if (hup.ltab[LTCODES+l] == LCUTOFF) hup.les -= (LTSTEP < hup.les ? LTSTEP : hup.les-1);
 340       if (l == SLCODES-1) {
 341         l = LENCODES-1;
 342       } else if (l >= SLCODES) {
 343         i = ac_threshold_val(hup, LLLEN);
 344         ac_in(hup, i, cast(ushort)(i+1), LLLEN);
 345         l = cast(ushort)(((l-SLCODES)<<LLBITS)+i+SLCODES-1);
 346       }
 347       l += 3;
 348       if (hup.accnt < POSCODES) {
 349         hup.accnt += l;
 350         if (hup.accnt > POSCODES) hup.accnt = POSCODES;
 351       }
 352       // pair from dictionary
 353       if (hup.dict_pos > p) {
 354         hup.dict_pair_pos = cast(ushort)(hup.dict_pos-1-p);
 355       } else {
 356         hup.dict_pair_pos = cast(ushort)(POSCODES-1-p+hup.dict_pos);
 357       }
 358       hup.dict_pair_len = l;
 359       goto do_pair; // recursive tail call
 360     } else {
 361       // EOF
 362       // ac_in(hup, i, i+1, i+1); don't need this
 363       hup.no_more = true;
 364       break;
 365     }
 366   } while (olen > 0);
 367 }
 368
 369
 370 // ////////////////////////////////////////////////////////////////////////// //
 371 public haunp_t haunp_create () {
 372   import core.stdc.stdlib : calloc;
 373   haunp_t hup = cast(haunp_t)calloc(1, (*haunp_t).sizeof);
 374   if (hup != null) haunp_reset(hup);
 375   return hup;
 376 }
 377
 378
 379 public void haunp_free (haunp_t hup) {
 380   import core.stdc.stdlib : free;
 381   if (hup !is null) free(hup);
 382 }
 383
 384
 385 public void haunp_reset (haunp_t hup) {
 386   if (hup !is null) {
 387     import core.stdc.string : memset;
 388     memset(hup, 0, (*hup).sizeof);
 389     hup.reader = null;
 390     // init dictionary
 391     hup.dict_pos = 0;
 392     // init model
 393     hup.ces = CTSTEP;
 394     hup.les = LTSTEP;
 395     hup.accnt = 0;
 396     hup.ttcon = 0;
 397     hup.npt = hup.pmax = 1;
 398     for (int i = 0; i < TTORD; ++i) hup.ttab[i][0] = hup.ttab[i][1] = TTSTEP;
 399     tabinit(hup.ltab, LTCODES, 0);
 400     tabinit(hup.eltab, LTCODES, 1);
 401     tabinit(hup.ctab, CTCODES, 0);
 402     tabinit(hup.ectab, CTCODES, 1);
 403     tabinit(hup.ptab, PTCODES, 0);
 404     tupd(hup.ptab, PTCODES, MAXPT, PTSTEP, 0);
 405     // init arithmetic decoder
 406     hup.ari_h = 0xffff;
 407     hup.ari_l = 0;
 408     hup.ari_gpat = 0;
 409     hup.ari_init_done = 0; // defer initialization
 410     // read buffer
 411     hup.no_more = false;
 412   }
 413 }
 414
 415
 416 // return number of bytes read (<len: end of data), throws on error
 417 public usize haunp_read (haunp_t hup, void[] buf, haunp_bread_fn_t reader) {
 418   if (buf.length == 0) return 0;
 419   if (hup !is null && reader !is null) {
 420     hup.reader = reader;
 421     scope(exit) hup.reader = null;
 422     usize res = 0;
 423     auto d = cast(ubyte*)buf.ptr;
 424     auto left = buf.length;
 425     while (left > 0) {
 426       hup.done = 0;
 427       auto rd = cast(int)(left > int.max/8 ? int.max/8 : left);
 428       libha_unpack(hup, d, rd);
 429       d += hup.done;
 430       left -= hup.done;
 431       res += hup.done;
 432       if (hup.done != rd) break;
 433     }
 434     return res;
 435   }
 436   throw new Exception("haunpack error");
 437 }