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