encode.c

   1 /***********************************************************
   2         encode.c -- sliding dictionary with percolating update
   3 ***********************************************************/
   4 #include "ar.h"
   5 #include <stdlib.h>
   6 #include <string.h>             /* memmove() */
   7
   8 #define PERCOLATE  0
   9 #define NIL        0
  10 #define USE_LH6_METHOD 1
  11
  12 #undef DICBIT
  13 #undef DICSIZ
  14 #define DICBIT (opts.method->dicbit)
  15 #define DICSIZ (2 << (DICBIT-1))
  16 /* #define PERC_FLAG ((unsigned)2 << (DICBIT+1)) ??? */
  17 #define PERC_FLAG 0x8000U
  18
  19 #define HASH(p, c) ((p) + 2 * DICSIZ + ((c) << (DICBIT - 9)))
  20 #define MAX_HASH_VAL HASH(DICSIZ + UCHAR_MAX, UCHAR_MAX)
  21
  22 #if USE_LH6_METHOD /* dicbit > 14 */
  23 typedef uint32_t node;          /* need (dicbit+2) bits */
  24 #else
  25 typedef short node;
  26 #endif
  27
  28 static uchar *text, *childcount;
  29 static node pos, avail, *position, *parent, *prev, *next = NULL;
  30 static int remainder;
  31
  32 #if MAXMATCH <= (UCHAR_MAX + 1)
  33 static uchar *level;
  34 #else
  35 static ushort *level;
  36 #endif
  37
  38 extern struct lha_opts opts;
  39
  40 struct match_t {
  41     node pos;
  42     int len;
  43 };
  44
  45 static void
  46 allocate_memory(void)
  47 {
  48     if (next != NULL)
  49         return;
  50     text = malloc(DICSIZ * 2 + MAXMATCH);
  51     level = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
  52     childcount = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
  53 #if PERCOLATE
  54     position = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
  55 #else
  56     position = malloc(DICSIZ * sizeof(*position));
  57 #endif
  58     parent = malloc(DICSIZ * 2 * sizeof(*parent));
  59     prev = malloc(DICSIZ * 2 * sizeof(*prev));
  60     next = malloc((MAX_HASH_VAL + 1) * sizeof(*next));
  61     if (next == NULL)
  62         error("Out of memory.");
  63 }
  64
  65 static void
  66 init_slide(void)
  67 {
  68     node i;
  69
  70     for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
  71         level[i] = 1;
  72 #if PERCOLATE
  73         position[i] = NIL;      /* sentinel */
  74 #endif
  75     }
  76     for (i = DICSIZ; i < DICSIZ * 2; i++)
  77         parent[i] = NIL;
  78     avail = 1;
  79     for (i = 1; i < DICSIZ - 1; i++)
  80         next[i] = i + 1;
  81     next[DICSIZ - 1] = NIL;
  82     for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++)
  83         next[i] = NIL;
  84 }
  85
  86 static node
  87 child(node q, uchar c)
  88         /* q's child for character c (NIL if not found) */
  89 {
  90     node r;
  91
  92     r = next[HASH(q, c)];
  93     parent[NIL] = q;            /* sentinel */
  94     while (parent[r] != q)
  95         r = next[r];
  96     return r;
  97 }
  98
  99 static void
 100 makechild(node q, uchar c, node r)
 101         /* Let r be q's child for character c. */
 102 {
 103     node h, t;
 104
 105     h = HASH(q, c);
 106
 107     /*
 108       insert r after h.
 109
 110       h next -> t
 111
 112       h next -> r
 113                 r next -> t
 114     */
 115     t = next[h];
 116     next[h] = r;
 117     next[r] = t;
 118
 119     /*
 120       h <- prev t
 121
 122       h <- prev r
 123                 r <- prev t
 124     */
 125     prev[t] = r;
 126     prev[r] = h;
 127
 128     parent[r] = q;
 129     childcount[q]++;
 130 }
 131
 132 static void
 133 replace_node(node old, node new)
 134 {
 135     node t;
 136
 137     /* replace old into new */
 138     t = prev[old];
 139     prev[new] = t;
 140     next[t] = new;
 141
 142     t = next[old];
 143     next[new] = t;
 144     prev[t] = new;
 145
 146     parent[new] = parent[old];
 147 }
 148
 149 static void
 150 split(struct match_t *match, node old)
 151 {
 152     node new;
 153
 154     new = avail;
 155     avail = next[new];
 156     childcount[new] = 0;
 157
 158     replace_node(old, new);
 159
 160     level[new] = match->len;
 161     position[new] = pos;
 162
 163     /* new child -> old */
 164     makechild(new, text[match->pos + match->len], old);
 165     /* new child -> pos
 166                     pos child -> old */
 167     makechild(new, text[pos + match->len], pos);
 168 }
 169
 170 static void
 171 insert_node(struct match_t *match)
 172 {
 173     node q, r, j, t;
 174     uchar c, *t1, *t2;
 175
 176     if (match->len >= 4) {
 177         match->len--;
 178         r = (match->pos + 1) | DICSIZ;
 179         while ((q = parent[r]) == NIL)
 180             r = next[r];
 181         while (level[q] >= match->len) {
 182             r = q;
 183             q = parent[q];
 184         }
 185 #if PERCOLATE
 186         t = q;
 187         while (position[t] < 0) {
 188             position[t] = pos;
 189             t = parent[t];
 190         }
 191         if (t < DICSIZ)
 192             position[t] = pos | PERC_FLAG;
 193 #else
 194         t = q;
 195         while (t < DICSIZ) {
 196             position[t] = pos;
 197             t = parent[t];
 198         }
 199 #endif
 200     }
 201     else {
 202         q = text[pos] + DICSIZ;
 203         c = text[pos + 1];
 204         if ((r = child(q, c)) == NIL) {
 205             makechild(q, c, pos);
 206             match->len = 1;
 207             return;
 208         }
 209         match->len = 2;
 210     }
 211
 212     /* found match->len */
 213     /* scan match->pos candidate r */
 214     for (;;) {
 215         if (r >= DICSIZ) {
 216             j = MAXMATCH;
 217             match->pos = r;
 218         }
 219         else {
 220             j = level[r];
 221             match->pos = position[r] & ~PERC_FLAG; /* 0x8000U */
 222         }
 223         if (match->pos >= pos)
 224             match->pos -= DICSIZ;
 225         t1 = &text[pos + match->len];
 226         t2 = &text[match->pos + match->len];
 227         while (match->len < j) {
 228             if (*t1 != *t2) {
 229                 split(match, r);
 230                 return;
 231             }
 232             match->len++;
 233             t1++;
 234             t2++;
 235         }
 236         if (match->len >= MAXMATCH)
 237             break;
 238         position[r] = pos;
 239         q = r;
 240         if ((r = child(q, *t1)) == NIL) {
 241             makechild(q, *t1, pos);
 242             return;
 243         }
 244         match->len++;
 245     }
 246     /* replace r into pos */
 247     replace_node(r, pos);
 248
 249     parent[r] = NIL;
 250     next[r] = pos;              /* special use of next[] */
 251 }
 252
 253 static void
 254 delete_node_1(node s)
 255 {
 256     node t, u;
 257
 258     t = prev[s];
 259     u = next[s];
 260     next[t] = u;
 261     prev[u] = t;
 262 }
 263
 264 static void
 265 delete_node(void)
 266 {
 267 #if PERCOLATE
 268     node q, r, s, t, u;
 269 #else
 270     node r, s, t;
 271 #endif
 272
 273     if (parent[pos] == NIL)
 274         return;
 275
 276     delete_node_1(pos);
 277
 278     r = parent[pos];
 279     parent[pos] = NIL;
 280
 281     if (r >= DICSIZ || --childcount[r] > 1)
 282         return;
 283 #if PERCOLATE
 284     t = position[r] & ~PERC_FLAG;
 285 #else
 286     t = position[r];
 287 #endif
 288     if (t >= pos)
 289         t -= DICSIZ;
 290 #if PERCOLATE
 291     s = t;
 292     q = parent[r];
 293     while ((u = position[q]) & PERC_FLAG) {
 294         u &= ~PERC_FLAG;
 295         if (u >= pos)
 296             u -= DICSIZ;
 297         if (u > s)
 298             s = u;
 299         position[q] = (s | DICSIZ);
 300         q = parent[q];
 301     }
 302     if (q < DICSIZ) {
 303         if (u >= pos)
 304             u -= DICSIZ;
 305         if (u > s)
 306             s = u;
 307         position[q] = s | DICSIZ | PERC_FLAG;
 308     }
 309 #endif
 310     s = child(r, text[t + level[r]]);
 311
 312     delete_node_1(s);
 313     replace_node(r, s);
 314
 315     /* free r */
 316     parent[r] = NIL;
 317     next[r] = avail;
 318     avail = r;
 319 }
 320
 321 static void
 322 get_next_match(struct lzh_ostream *wp, FILE *rfp, struct match_t *match)
 323 {
 324     int n;
 325
 326     remainder--;
 327     if (++pos == DICSIZ * 2) {
 328         memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
 329         n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, rfp);
 330         wp->origsize += n;
 331         remainder += n;
 332         pos = DICSIZ;
 333         if (wp->fp != stdout && opts.quiet < 1) {
 334             putc('.', stdout);
 335         }
 336     }
 337     delete_node();
 338     insert_node(match);
 339 }
 340
 341 void
 342 encode(struct lzh_ostream *wp, FILE *rfp)
 343 {
 344     struct match_t match, lastmatch;
 345
 346     allocate_memory();
 347     init_slide();
 348     huf_encode_start(wp, opts.method);
 349     remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, rfp);
 350     wp->origsize += remainder;
 351
 352     if (wp->fp != stdout && opts.quiet < 1) {
 353         putc('.', stdout);
 354     }
 355     match.len = 0;
 356     pos = DICSIZ;
 357     insert_node(&match);
 358     if (match.len > remainder)
 359         match.len = remainder;
 360     while (remainder > 0 && !wp->unpackable) {
 361         lastmatch = match;
 362         get_next_match(wp, rfp, &match);
 363         if (match.len > remainder)
 364             match.len = remainder;
 365         if (match.len > lastmatch.len || lastmatch.len < THRESHOLD)
 366             output(wp, text[pos - 1], 0);
 367         else {
 368             output(wp, lastmatch.len + (UCHAR_MAX + 1 - THRESHOLD),
 369                    (pos - lastmatch.pos - 2) & (DICSIZ - 1));
 370             while (--lastmatch.len > 0)
 371                 get_next_match(wp, rfp, &match);
 372             if (match.len > remainder)
 373                 match.len = remainder;
 374         }
 375     }
 376     huf_encode_end(wp);
 377 }