1 /***********************************************************
2 encode.c -- sliding dictionary with percolating update
3 ***********************************************************/
6 #include <string.h> /* memmove() */
10 #define USE_LH6_METHOD 1
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
19 #define HASH(p, c) ((p) + 2 * DICSIZ + ((c) << (DICBIT - 9)))
20 #define MAX_HASH_VAL HASH(DICSIZ + UCHAR_MAX, UCHAR_MAX)
22 #if USE_LH6_METHOD /* dicbit > 14 */
23 typedef uint32_t node; /* need (dicbit+2) bits */
28 static uchar *text, *childcount;
29 static node pos, avail, *position, *parent, *prev, *next = NULL;
32 #if MAXMATCH <= (UCHAR_MAX + 1)
38 extern struct lha_opts opts;
50 text = malloc(DICSIZ * 2 + MAXMATCH);
51 level = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
52 childcount = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
54 position = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
56 position = malloc(DICSIZ * sizeof(*position));
58 parent = malloc(DICSIZ * 2 * sizeof(*parent));
59 prev = malloc(DICSIZ * 2 * sizeof(*prev));
60 next = malloc((MAX_HASH_VAL + 1) * sizeof(*next));
62 error("Out of memory.");
70 for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
73 position[i] = NIL; /* sentinel */
76 for (i = DICSIZ; i < DICSIZ * 2; i++)
79 for (i = 1; i < DICSIZ - 1; i++)
81 next[DICSIZ - 1] = NIL;
82 for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++)
87 child(node q, uchar c)
88 /* q's child for character c (NIL if not found) */
93 parent[NIL] = q; /* sentinel */
94 while (parent[r] != q)
100 makechild(node q, uchar c, node r)
101 /* Let r be q's child for character c. */
133 replace_node(node old, node new)
137 /* replace old into new */
146 parent[new] = parent[old];
150 split(struct match_t *match, node old)
158 replace_node(old, new);
160 level[new] = match->len;
163 /* new child -> old */
164 makechild(new, text[match->pos + match->len], old);
167 makechild(new, text[pos + match->len], pos);
171 insert_node(struct match_t *match)
176 if (match->len >= 4) {
178 r = (match->pos + 1) | DICSIZ;
179 while ((q = parent[r]) == NIL)
181 while (level[q] >= match->len) {
187 while (position[t] < 0) {
192 position[t] = pos | PERC_FLAG;
202 q = text[pos] + DICSIZ;
204 if ((r = child(q, c)) == NIL) {
205 makechild(q, c, pos);
212 /* found match->len */
213 /* scan match->pos candidate r */
221 match->pos = position[r] & ~PERC_FLAG; /* 0x8000U */
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) {
236 if (match->len >= MAXMATCH)
240 if ((r = child(q, *t1)) == NIL) {
241 makechild(q, *t1, pos);
246 /* replace r into pos */
247 replace_node(r, pos);
250 next[r] = pos; /* special use of next[] */
254 delete_node_1(node s)
273 if (parent[pos] == NIL)
281 if (r >= DICSIZ || --childcount[r] > 1)
284 t = position[r] & ~PERC_FLAG;
293 while ((u = position[q]) & PERC_FLAG) {
299 position[q] = (s | DICSIZ);
307 position[q] = s | DICSIZ | PERC_FLAG;
310 s = child(r, text[t + level[r]]);
322 get_next_match(struct lzh_ostream *wp, FILE *rfp, struct match_t *match)
327 if (++pos == DICSIZ * 2) {
328 memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
329 n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, rfp, &wp->crc);
333 if (wp->fp != stdout && opts.quiet < 1) {
342 encode(struct lzh_ostream *wp, FILE *rfp)
344 struct match_t match, lastmatch;
348 huf_encode_start(wp, opts.method);
349 remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, rfp, &wp->crc);
350 wp->origsize += remainder;
352 if (wp->fp != stdout && opts.quiet < 1) {
358 if (match.len > remainder)
359 match.len = remainder;
360 while (remainder > 0 && !wp->unpackable) {
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);
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;