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