src/libha.c

   1 /***********************************************************************
   2  * This file is part of HA, a general purpose file archiver.
   3  * Copyright (C) 1995 Harri Hirvola
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  ***********************************************************************/
  19 #include <stdint.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22
  23 #include "libha.h"
  24
  25
  26 /******************************************************************************/
  27 void (*error_mem) (const char *where) = NULL;
  28
  29 int (*getbyte) (void) = NULL;
  30 void (*putbyte) (int c) = NULL;
  31 void (*flush) (void) = NULL;
  32
  33
  34 /******************************************************************************/
  35 /* Minimum possible match lenght for this implementation */
  36 #define MINLEN  (3)
  37
  38 #define HSIZE    (16384)
  39 #define HSHIFT   (3)
  40 #define HASH(p)  ((swd->b[p]^((swd->b[p+1]^(swd->b[p+2]<<HSHIFT))<<HSHIFT))&(HSIZE-1))
  41 #define MAXCNT   (1024)
  42
  43
  44 typedef struct {
  45   uint16_t swd_bpos, swd_mlf;
  46   int16_t swd_char;
  47   uint16_t cblen, binb;
  48   uint16_t bbf, bbl, inptr;
  49   uint16_t *ccnt, *ll, *cr, *best;
  50   unsigned char *b;
  51   uint16_t blen, iblen;
  52 } swd_t;
  53
  54
  55 /* maxl=max len to be found  */
  56 /* bufl=dictionary buffer len */
  57 /* bufl+2*maxl-1<32768 !!! */
  58
  59
  60 static void swd_cleanup (swd_t *swd) {
  61   if (swd->ccnt != NULL) { free(swd->ccnt); swd->ccnt = NULL; }
  62   if (swd->ll != NULL) { free(swd->ll); swd->ll = NULL; }
  63   if (swd->cr != NULL) { free(swd->cr); swd->cr = NULL; }
  64   if (swd->b != NULL) { free(swd->b); swd->b = NULL; }
  65   if (swd->best != NULL) { free(swd->best); swd->best = NULL; }
  66 }
  67
  68
  69 static void swd_init (swd_t *swd, uint16_t maxl, uint16_t bufl) {
  70   int16_t i;
  71   swd->iblen = maxl;
  72   swd->cblen = bufl;
  73   swd->blen = swd->cblen+swd->iblen;
  74   swd->ll = calloc(swd->blen, sizeof(*swd->ll));
  75   swd->best = calloc(swd->blen, sizeof(*swd->best));
  76   swd->ccnt = calloc(HSIZE, sizeof(*swd->ccnt));
  77   swd->cr = calloc(HSIZE, sizeof(*swd->cr));
  78   swd->b = calloc((swd->blen+swd->iblen-1), sizeof(*swd->b));
  79   if (swd->ll == NULL || swd->ccnt == NULL || swd->cr == NULL || swd->b == NULL) {
  80     swd_cleanup(swd);
  81     error_mem("swd_init()");
  82   }
  83   //fprintf(stderr, "swd_init: maxl=%u; bufl=%u\n", maxl, bufl);
  84   for (i = 0; i < HSIZE; ++i) {
  85     swd->ccnt[i] = 0;
  86     swd->cr[i] = 0;
  87   }
  88   swd->binb = swd->bbf = swd->bbl = swd->inptr = 0;
  89   while (swd->bbl < swd->iblen) {
  90     if ((i = getbyte()) < 0) break;
  91     swd->b[swd->inptr++] = i;
  92     ++swd->bbl;
  93   }
  94   swd->swd_mlf = MINLEN-1;
  95 }
  96
  97
  98 static void swd_accept (swd_t *swd) {
  99   int16_t i, j;
 100   j = swd->swd_mlf-2;
 101   /* Relies on non changed swd->swd_mlf !!! */
 102   do {
 103     if (swd->binb == swd->cblen) {
 104       --swd->ccnt[HASH(swd->inptr)];
 105     } else {
 106       ++swd->binb;
 107     }
 108     i = HASH(swd->bbf);
 109     //fprintf(stderr, "i=%d", i);
 110     //fprintf(stderr, "; swd->bbf=%u\n", swd->bbf);
 111     swd->ll[swd->bbf] = swd->cr[i];
 112     swd->cr[i] = swd->bbf;
 113     swd->best[swd->bbf] = 30000;
 114     swd->ccnt[i]++;
 115     if (++swd->bbf == swd->blen) swd->bbf = 0;
 116     if ((i = getbyte()) < 0) {
 117       --swd->bbl;
 118       if (++swd->inptr == swd->blen) swd->inptr = 0;
 119       continue;
 120     }
 121     if (swd->inptr < swd->iblen-1) {
 122       swd->b[swd->inptr+swd->blen] = swd->b[swd->inptr] = i;
 123       ++swd->inptr;
 124     } else {
 125       swd->b[swd->inptr] = i;
 126       if (++swd->inptr == swd->blen) swd->inptr = 0;
 127     }
 128   } while (--j);
 129   swd->swd_mlf = MINLEN-1;
 130 }
 131
 132
 133 static void swd_findbest (swd_t *swd) {
 134   uint16_t i, ref, cnt, ptr, start_len;
 135   int16_t c;
 136   i = HASH(swd->bbf);
 137   cnt = swd->ccnt[i];
 138   ++swd->ccnt[i];
 139   if (cnt > MAXCNT) cnt = MAXCNT;
 140   ptr = swd->ll[swd->bbf] = swd->cr[i];
 141   swd->cr[i] = swd->bbf;
 142   swd->swd_char = swd->b[swd->bbf];
 143   if ((start_len = swd->swd_mlf) >= swd->bbl) {
 144     if (swd->bbl == 0) swd->swd_char = -1;
 145     swd->best[swd->bbf] = 30000;
 146   } else {
 147     for (ref = swd->b[swd->bbf+swd->swd_mlf-1]; cnt--; ptr = swd->ll[ptr]) {
 148       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]) {
 149         {
 150           unsigned char *p1 = swd->b+ptr+3, *p2 = swd->b+swd->bbf+3;
 151           for (i = 3; i < swd->bbl; ++i) if (*p1++ != *p2++) break;
 152         }
 153         if (i <= swd->swd_mlf) continue;
 154         swd->swd_bpos = ptr;
 155         if ((swd->swd_mlf = i) == swd->bbl || swd->best[ptr] < i) break;
 156         ref = swd->b[swd->bbf+swd->swd_mlf-1];
 157       }
 158     }
 159     swd->best[swd->bbf] = swd->swd_mlf;
 160     if (swd->swd_mlf > start_len) {
 161       if (swd->swd_bpos < swd->bbf) {
 162         swd->swd_bpos = swd->bbf-swd->swd_bpos-1;
 163       } else {
 164         swd->swd_bpos = swd->blen-1-swd->swd_bpos+swd->bbf;
 165       }
 166     }
 167   }
 168   if (swd->binb == swd->cblen) {
 169     --swd->ccnt[HASH(swd->inptr)];
 170   } else {
 171     ++swd->binb;
 172   }
 173   if (++swd->bbf == swd->blen) swd->bbf = 0;
 174   if ((c = getbyte()) < 0) {
 175     --swd->bbl;
 176     if (++swd->inptr == swd->blen) swd->inptr = 0;
 177     return;
 178   }
 179   if (swd->inptr < swd->iblen-1) {
 180     swd->b[swd->inptr+swd->blen] = swd->b[swd->inptr] = c;
 181     ++swd->inptr;
 182   } else {
 183     swd->b[swd->inptr] = c;
 184     if (++swd->inptr == swd->blen) swd->inptr = 0;
 185   }
 186 }
 187
 188
 189 static void swd_dinit (swd_t *swd, uint16_t bufl) {
 190   swd->cblen = bufl;
 191   swd->b = malloc(swd->cblen*sizeof(unsigned char));
 192   if (swd->b == NULL) {
 193     swd_cleanup(swd);
 194     error_mem("swd_dinit()");
 195   }
 196   swd->bbf = 0;
 197 }
 198
 199
 200 static void swd_dpair (swd_t *swd, uint16_t l, uint16_t p) {
 201   if (swd->bbf > p) {
 202     p = swd->bbf-1-p;
 203   } else {
 204     p = swd->cblen-1-p+swd->bbf;
 205   }
 206   while (l--) {
 207     swd->b[swd->bbf] = swd->b[p];
 208     putbyte(swd->b[p]);
 209     if (++swd->bbf == swd->cblen) swd->bbf = 0;
 210     if (++p == swd->cblen) p = 0;
 211   }
 212 }
 213
 214
 215 static void swd_dchar (swd_t *swd, int16_t c) {
 216   swd->b[swd->bbf] = c;
 217   putbyte(c);
 218   if (++swd->bbf == swd->cblen) swd->bbf = 0;
 219 }
 220
 221
 222 /******************************************************************************/
 223 static uint16_t h, l, v;
 224 static int16_t s;
 225 static int16_t gpat, ppat;
 226
 227
 228 /***********************************************************************
 229   Bit I/O
 230 ***********************************************************************/
 231 #define putbit(b)  do { \
 232   ppat <<= 1; \
 233   if (b) ppat |= 1; \
 234   if (ppat&0x100) { \
 235     putbyte(ppat&0xff); \
 236     ppat = 1; \
 237   } \
 238 } while (0)
 239
 240
 241 #define getbit(b)  do { \
 242   gpat <<= 1; \
 243   if (!(gpat&0xff)) { \
 244     gpat = getbyte(); \
 245     if (gpat&0x100) { \
 246       gpat = 0x100; \
 247     } else { \
 248       gpat <<= 1; \
 249       gpat |= 1; \
 250     } \
 251   } \
 252   b |= (gpat&0x100)>>8; \
 253 } while (0)
 254
 255
 256 /***********************************************************************
 257   Arithmetic encoding
 258 ***********************************************************************/
 259 static void ac_out (uint16_t low, uint16_t high, uint16_t tot) {
 260   uint32_t r;
 261   r = (uint32_t)(h-l)+1;
 262   h = (uint16_t)(r*high/tot-1)+l;
 263   l += (uint16_t)(r*low/tot);
 264   if (!((h^l)&0x8000)) {
 265     putbit(l&0x8000);
 266     while (s) {
 267       --s;
 268       putbit(~l&0x8000);
 269     }
 270     l <<= 1;
 271     h <<= 1;
 272     h |= 1;
 273     while (!((h^l)&0x8000)) {
 274       putbit(l&0x8000);
 275       l <<= 1;
 276       h <<= 1;
 277       h |= 1;
 278     }
 279   }
 280   while ((l&0x4000) && !(h&0x4000)) {
 281     ++s;
 282     l <<= 1;
 283     l &= 0x7fff;
 284     h <<= 1;
 285     h |= 0x8001;
 286   }
 287 }
 288
 289
 290 static void ac_init_encode (void) {
 291   h = 0xffff;
 292   l = s = 0;
 293   ppat = 1;
 294 }
 295
 296
 297 static void ac_end_encode (void) {
 298   ++s;
 299   putbit(l&0x4000);
 300   while (s--) {
 301     putbit(~l&0x4000);
 302   }
 303   if (ppat == 1) {
 304     flush();
 305     return;
 306   }
 307   while (!(ppat&0x100)) ppat <<= 1;
 308   putbyte(ppat&0xff);
 309   flush();
 310 }
 311
 312
 313 /***********************************************************************
 314   Arithmetic decoding
 315 ***********************************************************************/
 316 static void ac_in (uint16_t low, uint16_t high, uint16_t tot) {
 317   uint32_t r;
 318   r = (uint32_t) (h-l)+1;
 319   h = (uint16_t) (r*high/tot-1)+l;
 320   l += (uint16_t) (r*low/tot);
 321   while (!((h^l)&0x8000)) {
 322     l <<= 1;
 323     h <<= 1;
 324     h |= 1;
 325     v <<= 1;
 326     getbit(v);
 327   }
 328   while ((l&0x4000) && !(h&0x4000)) {
 329     l <<= 1;
 330     l &= 0x7fff;
 331     h <<= 1;
 332     h |= 0x8001;
 333     v <<= 1;
 334     v ^= 0x8000;
 335     getbit(v);
 336   }
 337 }
 338
 339
 340 static uint16_t ac_threshold_val (uint16_t tot) {
 341   uint32_t r = (uint32_t) (h-l)+1;
 342   return (uint16_t)((((uint32_t) (v-l)+1)*tot-1)/r);
 343 }
 344
 345
 346 static void ac_init_decode (void) {
 347   h = 0xffff;
 348   l = 0;
 349   gpat = 0;
 350   v = getbyte()<<8;
 351   v |= 0xff&getbyte();
 352 }
 353
 354
 355 /******************************************************************************/
 356 #define POSCODES   (31200)
 357 #define SLCODES    (16)
 358 #define LLCODES    (48)
 359 #define LLLEN      (16)
 360 #define LLBITS     (4)
 361 #define LLMASK     (LLLEN-1)
 362 #define LENCODES   (SLCODES+LLCODES*LLLEN)
 363 #define LTCODES    (SLCODES+LLCODES)
 364 #define CTCODES    (256)
 365 #define PTCODES    (16)
 366 #define LTSTEP     (8)
 367 #define MAXLT      (750*LTSTEP)
 368 #define CTSTEP     (1)
 369 #define MAXCT      (1000*CTSTEP)
 370 #define PTSTEP     (24)
 371 #define MAXPT      (250*PTSTEP)
 372 #define TTSTEP     (40)
 373 #define MAXTT      (150*TTSTEP)
 374 #define TTORD      (4)
 375 #define TTOMASK    (TTORD-1)
 376 #define LCUTOFF    (3*LTSTEP)
 377 #define CCUTOFF    (3*CTSTEP)
 378 #define CPLEN      (8)
 379 #define LPLEN      (4)
 380 #define MINLENLIM  (4096)
 381
 382
 383 static uint16_t ltab[2*LTCODES];
 384 static uint16_t eltab[2*LTCODES];
 385 static uint16_t ptab[2*PTCODES];
 386 static uint16_t ctab[2*CTCODES];
 387 static uint16_t ectab[2*CTCODES];
 388 static uint16_t ttab[TTORD][2];
 389 static uint16_t accnt, pmax, npt;
 390 static uint16_t ces;
 391 static uint16_t les;
 392 static uint16_t ttcon;
 393 static swd_t swd;
 394
 395 void asc_cleanup (void) {
 396   swd_cleanup(&swd);
 397 }
 398
 399
 400 static void tabinit (uint16_t t[], uint16_t tl, uint16_t ival) {
 401   uint16_t i, j;
 402   for (i = tl; i < 2*tl; ++i) t[i] = ival;
 403   for (i = tl-1, j = (tl<<1)-2; i; --i, j -= 2) t[i] = t[j]+t[j+1];
 404 }
 405
 406
 407 static void tscale (uint16_t t[], uint16_t tl) {
 408   uint16_t i, j;
 409   for (i = (tl<<1)-1; i >= tl; --i) if (t[i] > 1) t[i] >>= 1;
 410   for (i = tl-1, j = (tl<<1)-2; i; --i, j -= 2) t[i] = t[j]+t[j+1];
 411 }
 412
 413
 414 static void tupd (uint16_t t[], uint16_t tl, uint16_t maxt, uint16_t step, uint16_t p) {
 415   int16_t i;
 416   for (i = p+tl; i; i >>= 1) t[i] += step;
 417   if (t[1] >= maxt) tscale(t, tl);
 418 }
 419
 420
 421 static void tzero (uint16_t t[], uint16_t tl, uint16_t p) {
 422   int16_t i, step;
 423   for (i = p+tl, step = t[i]; i; i >>= 1) t[i] -= step;
 424 }
 425
 426
 427 static void model_init (void) {
 428   int16_t i;
 429   ces = CTSTEP;
 430   les = LTSTEP;
 431   accnt = 0;
 432   ttcon = 0;
 433   npt = pmax = 1;
 434   for (i = 0; i < TTORD; ++i) ttab[i][0] = ttab[i][1] = TTSTEP;
 435   tabinit(ltab, LTCODES, 0);
 436   tabinit(eltab, LTCODES, 1);
 437   tabinit(ctab, CTCODES, 0);
 438   tabinit(ectab, CTCODES, 1);
 439   tabinit(ptab, PTCODES, 0);
 440   tupd(ptab, PTCODES, MAXPT, PTSTEP, 0);
 441 }
 442
 443
 444 static void pack_init (void) {
 445   model_init();
 446   ac_init_encode();
 447 }
 448
 449
 450 static void unpack_init (void) {
 451   model_init();
 452   ac_init_decode();
 453 }
 454
 455
 456 static void ttscale (uint16_t con) {
 457   ttab[con][0] >>= 1;
 458   if (ttab[con][0] == 0) ttab[con][0] = 1;
 459   ttab[con][1] >>= 1;
 460   if (ttab[con][1] == 0) ttab[con][1] = 1;
 461 }
 462
 463
 464 static void codepair (int16_t l, int16_t p) {
 465   uint16_t i, j, lt, k, cf, tot;
 466   i = ttab[ttcon][0]+ttab[ttcon][1];
 467   ac_out(ttab[ttcon][0], i, i+1);
 468   ttab[ttcon][1] += TTSTEP;
 469   if (i >= MAXTT) ttscale(ttcon);
 470   ttcon = ((ttcon<<1)|1)&TTOMASK;
 471   while (accnt > pmax) {
 472     tupd(ptab, PTCODES, MAXPT, PTSTEP, npt++);
 473     pmax <<= 1;
 474   }
 475   for (i = p, j = 0; i; ++j, i >>= 1) ;
 476   cf = ptab[PTCODES+j];
 477   tot = ptab[1];
 478   for (lt = 0, i = PTCODES+j; i; i >>= 1) {
 479     if (i&1) lt += ptab[i-1];
 480     ptab[i] += PTSTEP;
 481   }
 482   if (ptab[1] >= MAXPT) tscale(ptab, PTCODES);
 483   ac_out(lt, lt+cf, tot);
 484   if (p > 1) {
 485     for (i = 0x8000U; !(p&i); i >>= 1) ;
 486     j = p&~i;
 487     if (i != (pmax>>1)) {
 488       ac_out(j, j+1, i);
 489     } else {
 490       ac_out(j, j+1, accnt-(pmax>>1));
 491     }
 492   }
 493   i = l-MINLEN;
 494   if (i == LENCODES-1) {
 495     i = SLCODES-1, j = 0xffff;
 496   } else if (i < SLCODES-1) {
 497     j = 0xffff;
 498   } else {
 499     j = (i-SLCODES+1)&LLMASK;
 500     i = ((i-SLCODES+1)>>LLBITS)+SLCODES;
 501   }
 502   if ((cf = ltab[LTCODES+i]) == 0) {
 503     ac_out(ltab[1], ltab[1]+les, ltab[1]+les);
 504     for (lt = 0, k = LTCODES+i; k; k >>= 1) {
 505       if (k&1) lt += eltab[k-1];
 506       ltab[k] += LTSTEP;
 507     }
 508     if (ltab[1] >= MAXLT) tscale(ltab, LTCODES);
 509     ac_out(lt, lt+eltab[LTCODES+i], eltab[1]);
 510     tzero(eltab, LTCODES, i);
 511     if (eltab[1] != 0) les += LTSTEP; else les = 0;
 512     for (k = i <= LPLEN ? 0 : i-LPLEN; k < (i+LPLEN >= LTCODES-1 ? LTCODES-1 : i+LPLEN); ++k) {
 513       if (eltab[LTCODES+k]) tupd(eltab, LTCODES, MAXLT, 1, k);
 514     }
 515   } else {
 516     tot = ltab[1]+les;
 517     for (lt = 0, k = LTCODES+i; k; k >>= 1) {
 518       if (k&1) lt += ltab[k-1];
 519       ltab[k] += LTSTEP;
 520     }
 521     if (ltab[1] >= MAXLT) tscale(ltab, LTCODES);
 522     ac_out(lt, lt+cf, tot);
 523   }
 524   if (ltab[LTCODES+i] == LCUTOFF) les -= (LTSTEP < les ? LTSTEP : les-1);
 525   if (j != 0xffff) ac_out(j, j+1, LLLEN);
 526   if (accnt < POSCODES) {
 527     accnt += l;
 528     if (accnt > POSCODES) accnt = POSCODES;
 529   }
 530 }
 531
 532
 533 static void codechar (int16_t c) {
 534   uint16_t i, lt, tot, cf;
 535   i = ttab[ttcon][0]+ttab[ttcon][1];
 536   ac_out(0, ttab[ttcon][0], i+1);
 537   ttab[ttcon][0] += TTSTEP;
 538   if (i >= MAXTT) ttscale(ttcon);
 539   ttcon = (ttcon<<1)&TTOMASK;
 540   if ((cf = ctab[CTCODES+c]) == 0) {
 541     ac_out(ctab[1], ctab[1]+ces, ctab[1]+ces);
 542     for (lt = 0, i = CTCODES+c; i; i >>= 1) {
 543       if (i&1) lt += ectab[i-1];
 544       ctab[i] += CTSTEP;
 545     }
 546     if (ctab[1] >= MAXCT) tscale(ctab, CTCODES);
 547     ac_out(lt, lt+ectab[CTCODES+c], ectab[1]);
 548     tzero(ectab, CTCODES, c);
 549     if (ectab[1] != 0) ces += CTSTEP; else ces = 0;
 550     for (i = c <= CPLEN ? 0 : c-CPLEN; i < (c+CPLEN >= CTCODES-1 ? CTCODES-1 : c+CPLEN); ++i) {
 551       if (ectab[CTCODES+i]) tupd(ectab, CTCODES, MAXCT, 1, i);
 552     }
 553   } else {
 554     tot = ctab[1]+ces;
 555     for (lt = 0, i = CTCODES+c; i; i >>= 1) {
 556       if (i&1) lt += ctab[i-1];
 557       ctab[i] += CTSTEP;
 558     }
 559     if (ctab[1] >= MAXCT) tscale(ctab, CTCODES);
 560     ac_out(lt, lt+cf, tot);
 561   }
 562   if (ctab[CTCODES+c] == CCUTOFF) ces -= (CTSTEP < ces ? CTSTEP : ces-1);
 563   if (accnt < POSCODES) ++accnt;
 564 }
 565
 566
 567 void asc_pack (void) {
 568   int16_t oc;
 569   uint16_t omlf, obpos;
 570   swd_init(&swd, LENCODES+MINLEN-1, POSCODES);
 571   pack_init();
 572   for (swd_findbest(&swd); swd.swd_char >= 0;) {
 573     if (swd.swd_mlf > MINLEN || (swd.swd_mlf == MINLEN && swd.swd_bpos < MINLENLIM)) {
 574       omlf = swd.swd_mlf;
 575       obpos = swd.swd_bpos;
 576       oc = swd.swd_char;
 577       swd_findbest(&swd);
 578       if (swd.swd_mlf > omlf) {
 579         codechar(oc);
 580       } else {
 581         swd_accept(&swd);
 582         codepair(omlf, obpos);
 583         swd_findbest(&swd);
 584       }
 585     } else {
 586       swd.swd_mlf = MINLEN-1;
 587       codechar(swd.swd_char);
 588       swd_findbest(&swd);
 589     }
 590   }
 591   ac_out(ttab[ttcon][0]+ttab[ttcon][1], ttab[ttcon][0]+ttab[ttcon][1]+1, ttab[ttcon][0]+ttab[ttcon][1]+1);
 592   ac_end_encode();
 593   asc_cleanup();
 594 }
 595
 596
 597 void asc_unpack (void) {
 598   uint16_t l, p, tv, i, lt;
 599   swd_dinit(&swd, POSCODES);
 600   unpack_init();
 601   for (;;) {
 602     tv = ac_threshold_val(ttab[ttcon][0]+ttab[ttcon][1]+1);
 603     i = ttab[ttcon][0]+ttab[ttcon][1];
 604     if (ttab[ttcon][0] > tv) {
 605       ac_in(0, ttab[ttcon][0], i+1);
 606       ttab[ttcon][0] += TTSTEP;
 607       if (i >= MAXTT) ttscale(ttcon);
 608       ttcon = (ttcon<<1)&TTOMASK;
 609       tv = ac_threshold_val(ctab[1]+ces);
 610       if (tv >= ctab[1]) {
 611         ac_in(ctab[1], ctab[1]+ces, ctab[1]+ces);
 612         tv = ac_threshold_val(ectab[1]);
 613         for (l = 2, lt = 0;;) {
 614           if (lt+ectab[l] <= tv) {
 615             lt += ectab[l];
 616             ++l;
 617           }
 618           if (l >= CTCODES) {
 619             l -= CTCODES;
 620             break;
 621           }
 622           l <<= 1;
 623         }
 624         ac_in(lt, lt+ectab[CTCODES+l], ectab[1]);
 625         tzero(ectab, CTCODES, l);
 626         if (ectab[1] != 0) ces += CTSTEP; else ces = 0;
 627         for (i = l < CPLEN ? 0 : l-CPLEN; i < (l+CPLEN >= CTCODES-1 ? CTCODES-1 : l+CPLEN); ++i) {
 628           if (ectab[CTCODES+i]) tupd(ectab, CTCODES, MAXCT, 1, i);
 629         }
 630       } else {
 631         l = 2;
 632         lt = 0;
 633         for (;;) {
 634           if (lt+ctab[l] <= tv) {
 635             lt += ctab[l];
 636             l++;
 637           }
 638           if (l >= CTCODES) {
 639             l -= CTCODES;
 640             break;
 641           }
 642           l <<= 1;
 643         }
 644         ac_in(lt, lt+ctab[CTCODES+l], ctab[1]+ces);
 645       }
 646       tupd(ctab, CTCODES, MAXCT, CTSTEP, l);
 647       if (ctab[CTCODES+l] == CCUTOFF) ces -= (CTSTEP < ces ? CTSTEP : ces-1);
 648       swd_dchar(&swd, l);
 649       if (accnt < POSCODES) ++accnt;
 650     } else if (i > tv) {
 651       ac_in(ttab[ttcon][0], i, i+1);
 652       ttab[ttcon][1] += TTSTEP;
 653       if (i >= MAXTT) ttscale(ttcon);
 654       ttcon = ((ttcon<<1)|1)&TTOMASK;
 655       while (accnt > pmax) {
 656         tupd(ptab, PTCODES, MAXPT, PTSTEP, npt++);
 657         pmax <<= 1;
 658       }
 659       tv = ac_threshold_val(ptab[1]);
 660       for (p = 2, lt = 0;;) {
 661         if (lt+ptab[p] <= tv) {
 662           lt += ptab[p];
 663           p++;
 664         }
 665         if (p >= PTCODES) {
 666           p -= PTCODES;
 667           break;
 668         }
 669         p <<= 1;
 670       }
 671       ac_in(lt, lt+ptab[PTCODES+p], ptab[1]);
 672       tupd(ptab, PTCODES, MAXPT, PTSTEP, p);
 673       if (p > 1) {
 674         for (i = 1; p; i <<= 1, --p) ;
 675         i >>= 1;
 676         if (i == (pmax>>1)) l = accnt-(pmax>>1); else l = i;
 677         p = ac_threshold_val(l);
 678         ac_in(p, p+1, l);
 679         p += i;
 680       }
 681       tv = ac_threshold_val(ltab[1]+les);
 682       if (tv >= ltab[1]) {
 683         ac_in(ltab[1], ltab[1]+les, ltab[1]+les);
 684         tv = ac_threshold_val(eltab[1]);
 685         for (l = 2, lt = 0;;) {
 686           if (lt+eltab[l] <= tv) {
 687             lt += eltab[l];
 688             ++l;
 689           }
 690           if (l >= LTCODES) {
 691             l -= LTCODES;
 692             break;
 693           }
 694           l <<= 1;
 695         }
 696         ac_in(lt, lt+eltab[LTCODES+l], eltab[1]);
 697         tzero(eltab, LTCODES, l);
 698         if (eltab[1] != 0) les += LTSTEP; else les = 0;
 699         for (i = l < LPLEN ? 0 : l-LPLEN; i < (l+LPLEN >= LTCODES-1 ? LTCODES-1 : l+LPLEN); ++i) {
 700           if (eltab[LTCODES+i]) tupd(eltab, LTCODES, MAXLT, 1, i);
 701         }
 702       } else {
 703         for (l = 2, lt = 0;;) {
 704           if (lt+ltab[l] <= tv) {
 705             lt += ltab[l];
 706             ++l;
 707           }
 708           if (l >= LTCODES) {
 709             l -= LTCODES;
 710             break;
 711           }
 712           l <<= 1;
 713         }
 714         ac_in(lt, lt+ltab[LTCODES+l], ltab[1]+les);
 715       }
 716       tupd(ltab, LTCODES, MAXLT, LTSTEP, l);
 717       if (ltab[LTCODES+l] == LCUTOFF) les -= (LTSTEP < les ? LTSTEP : les-1);
 718       if (l == SLCODES-1) l = LENCODES-1;
 719       else if (l >= SLCODES) {
 720         i = ac_threshold_val(LLLEN);
 721         ac_in(i, i+1, LLLEN);
 722         l = ((l-SLCODES)<<LLBITS)+i+SLCODES-1;
 723       }
 724       l += 3;
 725       if (accnt < POSCODES) {
 726         accnt += l;
 727         if (accnt > POSCODES) accnt = POSCODES;
 728       }
 729       swd_dpair(&swd, l, p);
 730     } else {
 731       ac_in(i, i+1, i+1);
 732       flush();
 733       asc_cleanup();
 734       return;
 735     }
 736   }
 737 }