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