src/libha.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 <stdio.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include "libha.h"
  27
  28
  29 /******************************************************************************/
  30 /* some constants                                                             */
  31 /******************************************************************************/
  32 /* ASC */
  33 #define POSCODES   (31200) /* also, dictionary buffer len for SWD */
  34 #define SLCODES    (16)
  35 #define LLCODES    (48)
  36 #define LLLEN      (16)
  37 #define LLBITS     (4)
  38 #define LLMASK     (LLLEN-1)
  39 #define LENCODES   (SLCODES+LLCODES*LLLEN)
  40 #define LTCODES    (SLCODES+LLCODES)
  41 #define CTCODES    (256)
  42 #define PTCODES    (16)
  43 #define LTSTEP     (8)
  44 #define MAXLT      (750*LTSTEP)
  45 #define CTSTEP     (1)
  46 #define MAXCT      (1000*CTSTEP)
  47 #define PTSTEP     (24)
  48 #define MAXPT      (250*PTSTEP)
  49 #define TTSTEP     (40)
  50 #define MAXTT      (150*TTSTEP)
  51 #define TTORD      (4)
  52 #define TTOMASK    (TTORD-1)
  53 #define LCUTOFF    (3*LTSTEP)
  54 #define CCUTOFF    (3*CTSTEP)
  55 #define CPLEN      (8)
  56 #define LPLEN      (4)
  57 #define MINLENLIM  (4096)
  58
  59 /* SWD */
  60 /* Minimum possible match lenght for this implementation */
  61 #define MINLEN   (3)
  62 #define HSIZE    (16384)
  63 #define HSHIFT   (3)
  64 #define HASH(p)  ((swd->b[p]^((swd->b[p+1]^(swd->b[p+2]<<HSHIFT))<<HSHIFT))&(HSIZE-1))
  65 #define MAXCNT   (1024)
  66 /* derived */
  67 #define MAXFLEN  (LENCODES+MINLEN-1)  /* max len to be found  */
  68 #define MAXDLEN  (POSCODES+MAXFLEN)   /* reserved bytes for dict; POSCODES+2*MAXFLEN-1<32768 !!! */
  69
  70
  71 /******************************************************************************/
  72 static int dummy_bread (void *buf, int buf_len, void *udata) { return -1; }
  73 static int dummy_bwrite (const void *buf, int buf_len, void *udata) { return -1; }
  74
  75
  76 static const libha_io_t dummy_iot = {
  77   .bread = dummy_bread,
  78   .bwrite = dummy_bwrite,
  79 };
  80
  81
  82 typedef struct {
  83   libha_io_t *io;
  84   void *udata;
  85   /* input buffer */
  86   uint8_t *bufin;
  87   int bufin_pos;
  88   int bufin_max;
  89   int bufin_size;
  90   /* output buffer */
  91   uint8_t *bufout;
  92   int bufout_pos;
  93   int bufout_size;
  94   /* fuckout */
  95   jmp_buf errJP;
  96 } io_t;
  97
  98
  99 /******************************************************************************/
 100 static inline int get_byte (io_t *io) {
 101   if (io->bufin_pos >= io->bufin_max) {
 102     if (io->bufin_pos < io->bufin_size+1) {
 103       io->bufin_pos = 0;
 104       io->bufin_max = io->io->bread(io->bufin, io->bufin_size, io->udata);
 105       if (io->bufin_max < 0) longjmp(io->errJP, LIBHA_ERR_READ);
 106       if (io->bufin_max == 0) { io->bufin_pos = io->bufin_size+42; return -1; } /* EOF */
 107     } else {
 108       return -1; /* EOF */
 109     }
 110   }
 111   return io->bufin[io->bufin_pos++];
 112 }
 113
 114
 115 static inline void put_byte (io_t *io, int c) {
 116   if (io->bufout_pos >= io->bufout_size) {
 117     int res = io->io->bwrite(io->bufout, io->bufout_pos, io->udata);
 118     if (res != io->bufout_pos) longjmp(io->errJP, LIBHA_ERR_WRITE);
 119     io->bufout_pos = 0;
 120   }
 121   io->bufout[io->bufout_pos++] = c&0xff;
 122 }
 123
 124
 125 static inline void flush (io_t *io) {
 126   if (io->bufout_pos > 0) {
 127     int res = io->io->bwrite(io->bufout, io->bufout_pos, io->udata);
 128     if (res != io->bufout_pos) longjmp(io->errJP, LIBHA_ERR_WRITE);
 129     io->bufout_pos = 0;
 130   }
 131 }
 132
 133
 134 /******************************************************************************/
 135 typedef struct {
 136   uint16_t swd_bpos, swd_mlf;
 137   int16_t swd_char;
 138   uint16_t cblen, binb;
 139   uint16_t bbf, bbl, inptr;
 140   uint16_t ccnt[HSIZE], ll[MAXDLEN], cr[HSIZE], best[MAXDLEN];
 141   uint8_t b[MAXDLEN+MAXFLEN]; // was:-1
 142   uint16_t blen, iblen;
 143   io_t *io;
 144 } swd_t;
 145
 146
 147 static void swd_init (swd_t *swd) {
 148   memset(swd->ccnt, 0, sizeof(swd->ccnt));
 149   memset(swd->ll, 0, sizeof(swd->ll));
 150   memset(swd->cr, 0, sizeof(swd->cr));
 151   memset(swd->best, 0, sizeof(swd->best));
 152   memset(swd->b, 0, sizeof(swd->b));
 153   swd->binb = swd->bbf = swd->bbl = swd->inptr = 0;
 154   swd->swd_mlf = MINLEN-1;
 155 }
 156
 157
 158 /* return -1 on EOF or 0 */
 159 static int swd_first_bytes (swd_t *swd) {
 160   while (swd->bbl < MAXFLEN) {
 161     int b = get_byte(swd->io);
 162     if (b < 0) return -1;
 163     swd->b[swd->inptr++] = b;
 164     ++swd->bbl;
 165   }
 166   return 0;
 167 }
 168
 169
 170 static void swd_accept (swd_t *swd) {
 171   int16_t j = swd->swd_mlf-2;
 172   /* relies on non changed swd->swd_mlf !!! */
 173   do {
 174     int16_t i;
 175     if (swd->binb == POSCODES) --swd->ccnt[HASH(swd->inptr)]; else ++swd->binb;
 176     i = HASH(swd->bbf);
 177     swd->ll[swd->bbf] = swd->cr[i];
 178     swd->cr[i] = swd->bbf;
 179     swd->best[swd->bbf] = 30000;
 180     ++swd->ccnt[i];
 181     if (++swd->bbf == MAXDLEN) swd->bbf = 0;
 182     if ((i = get_byte(swd->io)) < 0) {
 183       --swd->bbl;
 184       if (++swd->inptr == MAXDLEN) swd->inptr = 0;
 185       continue;
 186     }
 187     if (swd->inptr < MAXFLEN-1) {
 188       swd->b[swd->inptr+MAXDLEN] = swd->b[swd->inptr] = i;
 189       ++swd->inptr;
 190     } else {
 191       swd->b[swd->inptr] = i;
 192       if (++swd->inptr == MAXDLEN) swd->inptr = 0;
 193     }
 194   } while (--j);
 195   swd->swd_mlf = MINLEN-1;
 196 }
 197
 198
 199 static void swd_findbest (swd_t *swd) {
 200   uint16_t ref, ptr, start_len;
 201   int ch;
 202   uint16_t i = HASH(swd->bbf);
 203   uint16_t cnt = swd->ccnt[i];
 204   ++swd->ccnt[i];
 205   if (cnt > MAXCNT) cnt = MAXCNT;
 206   ptr = swd->ll[swd->bbf] = swd->cr[i];
 207   swd->cr[i] = swd->bbf;
 208   swd->swd_char = swd->b[swd->bbf];
 209   if ((start_len = swd->swd_mlf) >= swd->bbl) {
 210     if (swd->bbl == 0) swd->swd_char = -1;
 211     swd->best[swd->bbf] = 30000;
 212   } else {
 213     for (ref = swd->b[swd->bbf+swd->swd_mlf-1]; cnt--; ptr = swd->ll[ptr]) {
 214       if (swd->b[ptr+swd->swd_mlf-1] == ref && swd->b[ptr] == swd->b[swd->bbf] && swd->b[ptr+1] == swd->b[swd->bbf+1]) {
 215         unsigned char *p1 = swd->b+ptr+3, *p2 = swd->b+swd->bbf+3;
 216         for (i = 3; i < swd->bbl; ++i) if (*p1++ != *p2++) break;
 217         if (i <= swd->swd_mlf) continue;
 218         swd->swd_bpos = ptr;
 219         if ((swd->swd_mlf = i) == swd->bbl || swd->best[ptr] < i) break;
 220         ref = swd->b[swd->bbf+swd->swd_mlf-1];
 221       }
 222     }
 223     swd->best[swd->bbf] = swd->swd_mlf;
 224     if (swd->swd_mlf > start_len) {
 225       if (swd->swd_bpos < swd->bbf) {
 226         swd->swd_bpos = swd->bbf-swd->swd_bpos-1;
 227       } else {
 228         swd->swd_bpos = MAXDLEN-1-swd->swd_bpos+swd->bbf;
 229       }
 230     }
 231   }
 232   if (swd->binb == POSCODES) --swd->ccnt[HASH(swd->inptr)]; else ++swd->binb;
 233   if (++swd->bbf == MAXDLEN) swd->bbf = 0;
 234   if ((ch = get_byte(swd->io)) < 0) {
 235     --swd->bbl;
 236     if (++swd->inptr == MAXDLEN) swd->inptr = 0;
 237     return;
 238   }
 239   if (swd->inptr < MAXFLEN-1) {
 240     swd->b[swd->inptr+MAXDLEN] = swd->b[swd->inptr] = ch;
 241     ++swd->inptr;
 242   } else {
 243     swd->b[swd->inptr] = ch;
 244     if (++swd->inptr == MAXDLEN) swd->inptr = 0;
 245   }
 246 }
 247
 248
 249 #ifndef LIBHA_DISABLE_UNPACKER
 250 static inline void swd_dpair (swd_t *swd, uint16_t l, uint16_t p) {
 251   if (swd->bbf > p) {
 252     p = swd->bbf-1-p;
 253   } else {
 254     p = POSCODES-1-p+swd->bbf;
 255   }
 256   while (l--) {
 257     swd->b[swd->bbf] = swd->b[p];
 258     put_byte(swd->io, swd->b[p]);
 259     if (++swd->bbf == POSCODES) swd->bbf = 0;
 260     if (++p == POSCODES) p = 0;
 261   }
 262 }
 263
 264
 265 static inline void swd_dchar (swd_t *swd, int16_t c) {
 266   swd->b[swd->bbf] = c;
 267   put_byte(swd->io, c);
 268   if (++swd->bbf == POSCODES) swd->bbf = 0;
 269 }
 270 #endif
 271
 272
 273 /******************************************************************************/
 274 typedef struct {
 275   uint16_t h, l, v;
 276   int16_t s;
 277   int16_t gpat, ppat;
 278   io_t *io;
 279 } ari_t;
 280
 281
 282 /***********************************************************************
 283   Bit I/O
 284 ***********************************************************************/
 285 #define putbit(b)  do { \
 286   ari->ppat <<= 1; \
 287   if (b) ari->ppat |= 1; \
 288   if (ari->ppat&0x100) { \
 289     put_byte(ari->io, ari->ppat&0xff); \
 290     ari->ppat = 1; \
 291   } \
 292 } while (0)
 293
 294
 295 #ifndef LIBHA_DISABLE_UNPACKER
 296
 297 #define getbit(b)  do { \
 298   ari->gpat <<= 1; \
 299   if (!(ari->gpat&0xff)) { \
 300     ari->gpat = get_byte(ari->io); \
 301     if (ari->gpat&0x100) { \
 302       ari->gpat = 0x100; \
 303     } else { \
 304       ari->gpat <<= 1; \
 305       ari->gpat |= 1; \
 306     } \
 307   } \
 308   b |= (ari->gpat&0x100)>>8; \
 309 } while (0)
 310
 311 #endif
 312
 313
 314 /***********************************************************************
 315   Arithmetic encoding
 316 ***********************************************************************/
 317 static void ac_out (ari_t *ari, uint16_t low, uint16_t high, uint16_t tot) {
 318   uint32_t r;
 319   if (tot == 0) longjmp(ari->io->errJP, LIBHA_ERR_BAD_DATA);
 320   r = (uint32_t)(ari->h-ari->l)+1;
 321   ari->h = (uint16_t)(r*high/tot-1)+ari->l;
 322   ari->l += (uint16_t)(r*low/tot);
 323   if (!((ari->h^ari->l)&0x8000)) {
 324     putbit(ari->l&0x8000);
 325     while (ari->s) {
 326       --ari->s;
 327       putbit(~ari->l&0x8000);
 328     }
 329     ari->l <<= 1;
 330     ari->h <<= 1;
 331     ari->h |= 1;
 332     while (!((ari->h^ari->l)&0x8000)) {
 333       putbit(ari->l&0x8000);
 334       ari->l <<= 1;
 335       ari->h <<= 1;
 336       ari->h |= 1;
 337     }
 338   }
 339   while ((ari->l&0x4000) && !(ari->h&0x4000)) {
 340     ++ari->s;
 341     ari->l <<= 1;
 342     ari->l &= 0x7fff;
 343     ari->h <<= 1;
 344     ari->h |= 0x8001;
 345   }
 346 }
 347
 348
 349 static void ac_init_encode (ari_t *ari) {
 350   ari->h = 0xffff;
 351   ari->l = ari->s = 0;
 352   ari->ppat = 1;
 353 }
 354
 355
 356 static void ac_end_encode (ari_t *ari) {
 357   ++ari->s;
 358   putbit(ari->l&0x4000);
 359   while (ari->s--) {
 360     putbit(~ari->l&0x4000);
 361   }
 362   if (ari->ppat == 1) {
 363     flush(ari->io);
 364     return;
 365   }
 366   while (!(ari->ppat&0x100)) ari->ppat <<= 1;
 367   put_byte(ari->io, ari->ppat&0xff);
 368   flush(ari->io);
 369 }
 370
 371
 372 /***********************************************************************
 373   Arithmetic decoding
 374 ***********************************************************************/
 375 #ifndef LIBHA_DISABLE_UNPACKER
 376 static void ac_in (ari_t *ari, uint16_t low, uint16_t high, uint16_t tot) {
 377   uint32_t r;
 378   if (tot == 0) longjmp(ari->io->errJP, LIBHA_ERR_BAD_DATA);
 379   r = (uint32_t)(ari->h-ari->l)+1;
 380   ari->h = (uint16_t)(r*high/tot-1)+ari->l;
 381   ari->l += (uint16_t)(r*low/tot);
 382   while (!((ari->h^ari->l)&0x8000)) {
 383     ari->l <<= 1;
 384     ari->h <<= 1;
 385     ari->h |= 1;
 386     ari->v <<= 1;
 387     getbit(ari->v);
 388   }
 389   while ((ari->l&0x4000) && !(ari->h&0x4000)) {
 390     ari->l <<= 1;
 391     ari->l &= 0x7fff;
 392     ari->h <<= 1;
 393     ari->h |= 0x8001;
 394     ari->v <<= 1;
 395     ari->v ^= 0x8000;
 396     getbit(ari->v);
 397   }
 398 }
 399
 400
 401 static inline uint16_t ac_threshold_val (ari_t *ari, uint16_t tot) {
 402   uint32_t r = (uint32_t)(ari->h-ari->l)+1;
 403   if (r == 0) longjmp(ari->io->errJP, LIBHA_ERR_BAD_DATA);
 404   return (uint16_t)((((uint32_t)(ari->v-ari->l)+1)*tot-1)/r);
 405 }
 406
 407
 408 static void ac_init_decode (ari_t *ari) {
 409   ari->h = 0xffff;
 410   ari->l = 0;
 411   ari->gpat = 0;
 412   ari->v = get_byte(ari->io)<<8;
 413   ari->v |= 0xff&get_byte(ari->io);
 414 }
 415 #endif
 416
 417
 418 /******************************************************************************/
 419 #define BUFIN_SIZE   (64*1024)
 420 #define BUFOUT_SIZE  (64*1024)
 421
 422 struct libha_s {
 423   uint16_t ltab[2*LTCODES];
 424   uint16_t eltab[2*LTCODES];
 425   uint16_t ptab[2*PTCODES];
 426   uint16_t ctab[2*CTCODES];
 427   uint16_t ectab[2*CTCODES];
 428   uint16_t ttab[TTORD][2];
 429   uint16_t accnt, pmax, npt;
 430   uint16_t ces;
 431   uint16_t les;
 432   uint16_t ttcon;
 433   swd_t swd;
 434   ari_t ari;
 435   libha_io_t iot;
 436   io_t io;
 437   uint8_t bufin[BUFIN_SIZE];
 438   uint8_t bufout[BUFOUT_SIZE];
 439   void *udata;
 440 };
 441
 442
 443 static void setup_buffers (libha_t asc) {
 444   asc->io.bufin = asc->bufin;
 445   asc->io.bufin_size = sizeof(asc->bufin);
 446   asc->io.bufin_pos = 0;
 447   asc->io.bufin_max = 0;
 448   asc->io.bufout = asc->bufout;
 449   asc->io.bufout_size = sizeof(asc->bufout);
 450   asc->io.bufout_pos = 0;
 451 }
 452
 453
 454 libha_t libha_alloc (const libha_io_t *iot, void *udata) {
 455   libha_t res = calloc(1, sizeof(struct libha_s));
 456   if (res != NULL) {
 457     res->iot = (iot ? *iot : dummy_iot);
 458     res->udata = udata;
 459   }
 460   return res;
 461 }
 462
 463
 464 void libha_free (libha_t asc) {
 465   if (asc != NULL) free(asc);
 466 }
 467
 468
 469 const libha_io_t *libha_get_iot (libha_t asc) {
 470   return (asc != NULL ? &asc->iot : NULL);
 471 }
 472
 473
 474 int libha_set_iot (libha_t asc, const libha_io_t *iot) {
 475   if (asc != NULL) {
 476     asc->iot = (iot ? *iot : dummy_iot);
 477     return 0;
 478   }
 479   return -1;
 480 }
 481
 482
 483 void *libha_get_udata (libha_t asc) {
 484   return (asc != NULL ? asc->udata : NULL);
 485 }
 486
 487
 488 int libha_set_udata (libha_t asc, void *udata) {
 489   if (asc != NULL) {
 490     asc->udata = udata;
 491     return 0;
 492   }
 493   return -1;
 494 }
 495
 496
 497 static inline void tabinit (uint16_t t[], uint16_t tl, uint16_t ival) {
 498   uint16_t i, j;
 499   for (i = tl; i < 2*tl; ++i) t[i] = ival;
 500   for (i = tl-1, j = (tl<<1)-2; i; --i, j -= 2) t[i] = t[j]+t[j+1];
 501 }
 502
 503
 504 static inline void tscale (uint16_t t[], uint16_t tl) {
 505   uint16_t i, j;
 506   for (i = (tl<<1)-1; i >= tl; --i) if (t[i] > 1) t[i] >>= 1;
 507   for (i = tl-1, j = (tl<<1)-2; i; --i, j -= 2) t[i] = t[j]+t[j+1];
 508 }
 509
 510
 511 static inline void tupd (uint16_t t[], uint16_t tl, uint16_t maxt, uint16_t step, uint16_t p) {
 512   int16_t i;
 513   for (i = p+tl; i; i >>= 1) t[i] += step;
 514   if (t[1] >= maxt) tscale(t, tl);
 515 }
 516
 517
 518 static inline void tzero (uint16_t t[], uint16_t tl, uint16_t p) {
 519   int16_t i, step;
 520   for (i = p+tl, step = t[i]; i; i >>= 1) t[i] -= step;
 521 }
 522
 523
 524 static void model_init (libha_t asc) {
 525   int16_t i;
 526   asc->ces = CTSTEP;
 527   asc->les = LTSTEP;
 528   asc->accnt = 0;
 529   asc->ttcon = 0;
 530   asc->npt = asc->pmax = 1;
 531   for (i = 0; i < TTORD; ++i) asc->ttab[i][0] = asc->ttab[i][1] = TTSTEP;
 532   tabinit(asc->ltab, LTCODES, 0);
 533   tabinit(asc->eltab, LTCODES, 1);
 534   tabinit(asc->ctab, CTCODES, 0);
 535   tabinit(asc->ectab, CTCODES, 1);
 536   tabinit(asc->ptab, PTCODES, 0);
 537   tupd(asc->ptab, PTCODES, MAXPT, PTSTEP, 0);
 538 }
 539
 540
 541 static void pack_init (libha_t asc) {
 542   model_init(asc);
 543   ac_init_encode(&asc->ari);
 544 }
 545
 546
 547 #ifndef LIBHA_DISABLE_UNPACKER
 548 static void unpack_init (libha_t asc) {
 549   model_init(asc);
 550   ac_init_decode(&asc->ari);
 551 }
 552 #endif
 553
 554
 555 static inline void ttscale (libha_t asc, uint16_t con) {
 556   asc->ttab[con][0] >>= 1;
 557   if (asc->ttab[con][0] == 0) asc->ttab[con][0] = 1;
 558   asc->ttab[con][1] >>= 1;
 559   if (asc->ttab[con][1] == 0) asc->ttab[con][1] = 1;
 560 }
 561
 562
 563 static void codepair (libha_t asc, int16_t l, int16_t p) {
 564   uint16_t i, j, lt, k, cf, tot;
 565   i = asc->ttab[asc->ttcon][0]+asc->ttab[asc->ttcon][1];
 566   ac_out(&asc->ari, asc->ttab[asc->ttcon][0], i, i+1);
 567   asc->ttab[asc->ttcon][1] += TTSTEP;
 568   if (i >= MAXTT) ttscale(asc, asc->ttcon);
 569   asc->ttcon = ((asc->ttcon<<1)|1)&TTOMASK;
 570   while (asc->accnt > asc->pmax) {
 571     tupd(asc->ptab, PTCODES, MAXPT, PTSTEP, asc->npt++);
 572     asc->pmax <<= 1;
 573   }
 574   for (i = p, j = 0; i; ++j, i >>= 1) ;
 575   cf = asc->ptab[PTCODES+j];
 576   tot = asc->ptab[1];
 577   for (lt = 0, i = PTCODES+j; i; i >>= 1) {
 578     if (i&1) lt += asc->ptab[i-1];
 579     asc->ptab[i] += PTSTEP;
 580   }
 581   if (asc->ptab[1] >= MAXPT) tscale(asc->ptab, PTCODES);
 582   ac_out(&asc->ari, lt, lt+cf, tot);
 583   if (p > 1) {
 584     for (i = 0x8000U; !(p&i); i >>= 1) ;
 585     j = p&~i;
 586     if (i != (asc->pmax>>1)) {
 587       ac_out(&asc->ari, j, j+1, i);
 588     } else {
 589       ac_out(&asc->ari, j, j+1, asc->accnt-(asc->pmax>>1));
 590     }
 591   }
 592   i = l-MINLEN;
 593   if (i == LENCODES-1) {
 594     i = SLCODES-1, j = 0xffff;
 595   } else if (i < SLCODES-1) {
 596     j = 0xffff;
 597   } else {
 598     j = (i-SLCODES+1)&LLMASK;
 599     i = ((i-SLCODES+1)>>LLBITS)+SLCODES;
 600   }
 601   if ((cf = asc->ltab[LTCODES+i]) == 0) {
 602     ac_out(&asc->ari, asc->ltab[1], asc->ltab[1]+asc->les, asc->ltab[1]+asc->les);
 603     for (lt = 0, k = LTCODES+i; k; k >>= 1) {
 604       if (k&1) lt += asc->eltab[k-1];
 605       asc->ltab[k] += LTSTEP;
 606     }
 607     if (asc->ltab[1] >= MAXLT) tscale(asc->ltab, LTCODES);
 608     ac_out(&asc->ari, lt, lt+asc->eltab[LTCODES+i], asc->eltab[1]);
 609     tzero(asc->eltab, LTCODES, i);
 610     if (asc->eltab[1] != 0) asc->les += LTSTEP; else asc->les = 0;
 611     for (k = i <= LPLEN ? 0 : i-LPLEN; k < (i+LPLEN >= LTCODES-1 ? LTCODES-1 : i+LPLEN); ++k) {
 612       if (asc->eltab[LTCODES+k]) tupd(asc->eltab, LTCODES, MAXLT, 1, k);
 613     }
 614   } else {
 615     tot = asc->ltab[1]+asc->les;
 616     for (lt = 0, k = LTCODES+i; k; k >>= 1) {
 617       if (k&1) lt += asc->ltab[k-1];
 618       asc->ltab[k] += LTSTEP;
 619     }
 620     if (asc->ltab[1] >= MAXLT) tscale(asc->ltab, LTCODES);
 621     ac_out(&asc->ari, lt, lt+cf, tot);
 622   }
 623   if (asc->ltab[LTCODES+i] == LCUTOFF) asc->les -= (LTSTEP < asc->les ? LTSTEP : asc->les-1);
 624   if (j != 0xffff) ac_out(&asc->ari, j, j+1, LLLEN);
 625   if (asc->accnt < POSCODES) {
 626     asc->accnt += l;
 627     if (asc->accnt > POSCODES) asc->accnt = POSCODES;
 628   }
 629 }
 630
 631
 632 static void codechar (libha_t asc, int16_t c) {
 633   uint16_t i, lt, tot, cf;
 634   i = asc->ttab[asc->ttcon][0]+asc->ttab[asc->ttcon][1];
 635   ac_out(&asc->ari, 0, asc->ttab[asc->ttcon][0], i+1);
 636   asc->ttab[asc->ttcon][0] += TTSTEP;
 637   if (i >= MAXTT) ttscale(asc, asc->ttcon);
 638   asc->ttcon = (asc->ttcon<<1)&TTOMASK;
 639   if ((cf = asc->ctab[CTCODES+c]) == 0) {
 640     ac_out(&asc->ari, asc->ctab[1], asc->ctab[1]+asc->ces, asc->ctab[1]+asc->ces);
 641     for (lt = 0, i = CTCODES+c; i; i >>= 1) {
 642       if (i&1) lt += asc->ectab[i-1];
 643       asc->ctab[i] += CTSTEP;
 644     }
 645     if (asc->ctab[1] >= MAXCT) tscale(asc->ctab, CTCODES);
 646     ac_out(&asc->ari, lt, lt+asc->ectab[CTCODES+c], asc->ectab[1]);
 647     tzero(asc->ectab, CTCODES, c);
 648     if (asc->ectab[1] != 0) asc->ces += CTSTEP; else asc->ces = 0;
 649     for (i = c <= CPLEN ? 0 : c-CPLEN; i < (c+CPLEN >= CTCODES-1 ? CTCODES-1 : c+CPLEN); ++i) {
 650       if (asc->ectab[CTCODES+i]) tupd(asc->ectab, CTCODES, MAXCT, 1, i);
 651     }
 652   } else {
 653     tot = asc->ctab[1]+asc->ces;
 654     for (lt = 0, i = CTCODES+c; i; i >>= 1) {
 655       if (i&1) lt += asc->ctab[i-1];
 656       asc->ctab[i] += CTSTEP;
 657     }
 658     if (asc->ctab[1] >= MAXCT) tscale(asc->ctab, CTCODES);
 659     ac_out(&asc->ari, lt, lt+cf, tot);
 660   }
 661   if (asc->ctab[CTCODES+c] == CCUTOFF) asc->ces -= (CTSTEP < asc->ces ? CTSTEP : asc->ces-1);
 662   if (asc->accnt < POSCODES) ++asc->accnt;
 663 }
 664
 665
 666 int libha_pack (libha_t asc) {
 667   volatile int res;
 668   int16_t oc;
 669   uint16_t omlf, obpos;
 670   asc->io.io = &asc->iot;
 671   asc->io.udata = asc->udata;
 672   asc->swd.io = asc->ari.io = &asc->io;
 673   setup_buffers(asc);
 674   res = setjmp(asc->io.errJP);
 675   if (res != 0) return res;
 676   swd_init(&asc->swd);
 677   swd_first_bytes(&asc->swd);
 678   pack_init(asc);
 679   for (swd_findbest(&asc->swd); asc->swd.swd_char >= 0; ) {
 680     if (asc->swd.swd_mlf > MINLEN || (asc->swd.swd_mlf == MINLEN && asc->swd.swd_bpos < MINLENLIM)) {
 681       omlf = asc->swd.swd_mlf;
 682       obpos = asc->swd.swd_bpos;
 683       oc = asc->swd.swd_char;
 684       swd_findbest(&asc->swd);
 685       if (asc->swd.swd_mlf > omlf) {
 686         codechar(asc, oc);
 687       } else {
 688         swd_accept(&asc->swd);
 689         codepair(asc, omlf, obpos);
 690         swd_findbest(&asc->swd);
 691       }
 692     } else {
 693       asc->swd.swd_mlf = MINLEN-1;
 694       codechar(asc, asc->swd.swd_char);
 695       swd_findbest(&asc->swd);
 696     }
 697   }
 698   ac_out(&asc->ari, asc->ttab[asc->ttcon][0]+asc->ttab[asc->ttcon][1], asc->ttab[asc->ttcon][0]+asc->ttab[asc->ttcon][1]+1, asc->ttab[asc->ttcon][0]+asc->ttab[asc->ttcon][1]+1);
 699   ac_end_encode(&asc->ari);
 700   return LIBHA_ERR_OK;
 701 }
 702
 703
 704 #ifndef LIBHA_DISABLE_UNPACKER
 705 int libha_unpack (libha_t asc) {
 706   volatile int res;
 707   uint16_t l, p, tv, i, lt;
 708   asc->io.io = &asc->iot;
 709   asc->io.udata = asc->udata;
 710   asc->swd.io = asc->ari.io = &asc->io;
 711   setup_buffers(asc);
 712   res = setjmp(asc->io.errJP);
 713   if (res != 0) return res;
 714   swd_init(&asc->swd);
 715   unpack_init(asc);
 716   for (;;) {
 717     tv = ac_threshold_val(&asc->ari, asc->ttab[asc->ttcon][0]+asc->ttab[asc->ttcon][1]+1);
 718     i = asc->ttab[asc->ttcon][0]+asc->ttab[asc->ttcon][1];
 719     if (asc->ttab[asc->ttcon][0] > tv) {
 720       ac_in(&asc->ari, 0, asc->ttab[asc->ttcon][0], i+1);
 721       asc->ttab[asc->ttcon][0] += TTSTEP;
 722       if (i >= MAXTT) ttscale(asc, asc->ttcon);
 723       asc->ttcon = (asc->ttcon<<1)&TTOMASK;
 724       tv = ac_threshold_val(&asc->ari, asc->ctab[1]+asc->ces);
 725       if (tv >= asc->ctab[1]) {
 726         ac_in(&asc->ari, asc->ctab[1], asc->ctab[1]+asc->ces, asc->ctab[1]+asc->ces);
 727         tv = ac_threshold_val(&asc->ari, asc->ectab[1]);
 728         for (l = 2, lt = 0;;) {
 729           if (lt+asc->ectab[l] <= tv) {
 730             lt += asc->ectab[l];
 731             ++l;
 732           }
 733           if (l >= CTCODES) {
 734             l -= CTCODES;
 735             break;
 736           }
 737           l <<= 1;
 738         }
 739         ac_in(&asc->ari, lt, lt+asc->ectab[CTCODES+l], asc->ectab[1]);
 740         tzero(asc->ectab, CTCODES, l);
 741         if (asc->ectab[1] != 0) asc->ces += CTSTEP; else asc->ces = 0;
 742         for (i = l < CPLEN ? 0 : l-CPLEN; i < (l+CPLEN >= CTCODES-1 ? CTCODES-1 : l+CPLEN); ++i) {
 743           if (asc->ectab[CTCODES+i]) tupd(asc->ectab, CTCODES, MAXCT, 1, i);
 744         }
 745       } else {
 746         l = 2;
 747         lt = 0;
 748         for (;;) {
 749           if (lt+asc->ctab[l] <= tv) {
 750             lt += asc->ctab[l];
 751             l++;
 752           }
 753           if (l >= CTCODES) {
 754             l -= CTCODES;
 755             break;
 756           }
 757           l <<= 1;
 758         }
 759         ac_in(&asc->ari, lt, lt+asc->ctab[CTCODES+l], asc->ctab[1]+asc->ces);
 760       }
 761       tupd(asc->ctab, CTCODES, MAXCT, CTSTEP, l);
 762       if (asc->ctab[CTCODES+l] == CCUTOFF) asc->ces -= (CTSTEP < asc->ces ? CTSTEP : asc->ces-1);
 763       swd_dchar(&asc->swd, l);
 764       if (asc->accnt < POSCODES) ++asc->accnt;
 765     } else if (i > tv) {
 766       ac_in(&asc->ari, asc->ttab[asc->ttcon][0], i, i+1);
 767       asc->ttab[asc->ttcon][1] += TTSTEP;
 768       if (i >= MAXTT) ttscale(asc, asc->ttcon);
 769       asc->ttcon = ((asc->ttcon<<1)|1)&TTOMASK;
 770       while (asc->accnt > asc->pmax) {
 771         tupd(asc->ptab, PTCODES, MAXPT, PTSTEP, asc->npt++);
 772         asc->pmax <<= 1;
 773       }
 774       tv = ac_threshold_val(&asc->ari, asc->ptab[1]);
 775       for (p = 2, lt = 0;;) {
 776         if (lt+asc->ptab[p] <= tv) {
 777           lt += asc->ptab[p];
 778           p++;
 779         }
 780         if (p >= PTCODES) {
 781           p -= PTCODES;
 782           break;
 783         }
 784         p <<= 1;
 785       }
 786       ac_in(&asc->ari, lt, lt+asc->ptab[PTCODES+p], asc->ptab[1]);
 787       tupd(asc->ptab, PTCODES, MAXPT, PTSTEP, p);
 788       if (p > 1) {
 789         for (i = 1; p; i <<= 1, --p) ;
 790         i >>= 1;
 791         if (i == (asc->pmax>>1)) l = asc->accnt-(asc->pmax>>1); else l = i;
 792         p = ac_threshold_val(&asc->ari, l);
 793         ac_in(&asc->ari, p, p+1, l);
 794         p += i;
 795       }
 796       tv = ac_threshold_val(&asc->ari, asc->ltab[1]+asc->les);
 797       if (tv >= asc->ltab[1]) {
 798         ac_in(&asc->ari, asc->ltab[1], asc->ltab[1]+asc->les, asc->ltab[1]+asc->les);
 799         tv = ac_threshold_val(&asc->ari, asc->eltab[1]);
 800         for (l = 2, lt = 0;;) {
 801           if (lt+asc->eltab[l] <= tv) {
 802             lt += asc->eltab[l];
 803             ++l;
 804           }
 805           if (l >= LTCODES) {
 806             l -= LTCODES;
 807             break;
 808           }
 809           l <<= 1;
 810         }
 811         ac_in(&asc->ari, lt, lt+asc->eltab[LTCODES+l], asc->eltab[1]);
 812         tzero(asc->eltab, LTCODES, l);
 813         if (asc->eltab[1] != 0) asc->les += LTSTEP; else asc->les = 0;
 814         for (i = l < LPLEN ? 0 : l-LPLEN; i < (l+LPLEN >= LTCODES-1 ? LTCODES-1 : l+LPLEN); ++i) {
 815           if (asc->eltab[LTCODES+i]) tupd(asc->eltab, LTCODES, MAXLT, 1, i);
 816         }
 817       } else {
 818         for (l = 2, lt = 0;;) {
 819           if (lt+asc->ltab[l] <= tv) {
 820             lt += asc->ltab[l];
 821             ++l;
 822           }
 823           if (l >= LTCODES) {
 824             l -= LTCODES;
 825             break;
 826           }
 827           l <<= 1;
 828         }
 829         ac_in(&asc->ari, lt, lt+asc->ltab[LTCODES+l], asc->ltab[1]+asc->les);
 830       }
 831       tupd(asc->ltab, LTCODES, MAXLT, LTSTEP, l);
 832       if (asc->ltab[LTCODES+l] == LCUTOFF) asc->les -= (LTSTEP < asc->les ? LTSTEP : asc->les-1);
 833       if (l == SLCODES-1) l = LENCODES-1;
 834       else if (l >= SLCODES) {
 835         i = ac_threshold_val(&asc->ari, LLLEN);
 836         ac_in(&asc->ari, i, i+1, LLLEN);
 837         l = ((l-SLCODES)<<LLBITS)+i+SLCODES-1;
 838       }
 839       l += 3;
 840       if (asc->accnt < POSCODES) {
 841         asc->accnt += l;
 842         if (asc->accnt > POSCODES) asc->accnt = POSCODES;
 843       }
 844       swd_dpair(&asc->swd, l, p);
 845     } else {
 846       /*ac_in(&asc->ari, i, i+1, i+1);*/
 847       flush(&asc->io);
 848       return LIBHA_ERR_OK;
 849     }
 850   }
 851   return LIBHA_ERR_OK;
 852 }
 853 #endif
 854
 855
 856 /******************************************************************************/
 857 /* poly: 0xedb88320L: ISO 3309, ITU-T V.42 */
 858 #ifndef LIBHA_DISABLE_CRC
 859 static const uint32_t crctab[16] = {
 860   0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac,
 861   0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,
 862   0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c,
 863   0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c,
 864 };
 865
 866
 867 unsigned int libha_crc32 (const void *src, int len) {
 868   uint32_t crc = 0xffffffffUL;
 869   if (src != NULL && len > 0) {
 870     const uint8_t *buf = (const uint8_t *)src;
 871     while (len--) {
 872       crc ^= *buf++;
 873       crc = crctab[crc&0x0f]^(crc>>4);
 874       crc = crctab[crc&0x0f]^(crc>>4);
 875     }
 876   }
 877   return crc^0xffffffffUL;
 878 }
 879
 880
 881 unsigned int libha_crc32_begin (void) {
 882   return 0xffffffffUL;
 883 }
 884
 885
 886 unsigned int libha_crc32_end (unsigned int crc) {
 887   return crc^0xffffffffUL;
 888 }
 889
 890
 891 unsigned int libha_crc32_part (unsigned int crc, const void *src, int len) {
 892   if (src != NULL && len > 0) {
 893     const uint8_t *buf = (const uint8_t *)src;
 894     while (len--) {
 895       crc ^= *buf++;
 896       crc = crctab[crc&0x0f]^(crc>>4);
 897       crc = crctab[crc&0x0f]^(crc>>4);
 898     }
 899   }
 900   return crc;
 901 }
 902 #endif