This is slide-old.c in view mode; [Download] [Up]
/* ------------------------------------------------------------------------ */ /* LHa for UNIX */ /* slice.c -- sliding dictionary with percolating update */ /* */ /* Modified Nobutaka Watazaki */ /* */ /* Ver. 1.14 Source All chagned 1995.01.14 N.Watazaki */ /* ------------------------------------------------------------------------ */ #include "lha.h" /* ------------------------------------------------------------------------ */ static unsigned long encoded_origsize; /* ------------------------------------------------------------------------ */ static struct encode_option encode_define[2] = { #if defined(__STDC__) || defined(AIX) /* lh1 */ {(void (*) ()) output_dyn, (void (*) ()) encode_start_fix, (void (*) ()) encode_end_dyn}, /* lh4, 5 */ {(void (*) ()) output_st1, (void (*) ()) encode_start_st1, (void (*) ()) encode_end_st1} #else /* lh1 */ {(int (*) ()) output_dyn, (int (*) ()) encode_start_fix, (int (*) ()) encode_end_dyn}, /* lh4, 5, 6 */ {(int (*) ()) output_st1, (int (*) ()) encode_start_st1, (int (*) ()) encode_end_st1} #endif }; static struct decode_option decode_define[] = { /* lh1 */ {decode_c_dyn, decode_p_st0, decode_start_fix}, /* lh2 */ {decode_c_dyn, decode_p_dyn, decode_start_dyn}, /* lh3 */ {decode_c_st0, decode_p_st0, decode_start_st0}, /* lh4 */ {decode_c_st1, decode_p_st1, decode_start_st1}, /* lh5 */ {decode_c_st1, decode_p_st1, decode_start_st1}, /* lh6 */ {decode_c_st1, decode_p_st1, decode_start_st1}, /* lzs */ {decode_c_lzs, decode_p_lzs, decode_start_lzs}, /* lz5 */ {decode_c_lz5, decode_p_lz5, decode_start_lz5} }; static struct encode_option encode_set; static struct decode_option decode_set; static node pos, matchpos, avail, *position, *parent, *prev; static int remainder, matchlen; static unsigned char *level, *childcount; static unsigned long /*short*/ dicsiz; /* t.okamoto */ static unsigned short max_hash_val; static unsigned short hash1, hash2; /* ------------------------------------------------------------------------ */ int encode_alloc(method) int method; { if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */ encode_set = encode_define[0]; maxmatch = 60; dicbit = MAX_DICBIT - 3; /* 12 Changed N.Watazaki */ } else { encode_set = encode_define[1]; maxmatch = MAXMATCH; if (method == LZHUFF6_METHOD_NUM) dicbit = MAX_DICBIT; /* 15 Changed N.Watazaki */ else dicbit = MAX_DICBIT - 2; /* 13 Changed N.Watazaki */ } while (1) { dicsiz = 1 << dicbit; max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX; text = (unsigned char *) malloc(dicsiz * 2 + maxmatch); level = (unsigned char *) malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level)); childcount = (unsigned char *) malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount)); #if PERCOLATE position = (node *) malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position)); #else position = (node *) malloc(dicsiz * sizeof(*position)); #endif parent = (node *) malloc(dicsiz * 2 * sizeof(*parent)); prev = (node *) malloc(dicsiz * 2 * sizeof(*prev)); next = (node *) malloc((max_hash_val + 1) * sizeof(*next)); if (next == NULL || method > 1 && alloc_buf() == NULL) { if (next) free(next); if (prev) free(prev); if (parent) free(parent); if (position) free(position); if (childcount) free(childcount); if (level) free(level); if (text) free(text); } else { break; } exit(207); } return method; } /* ------------------------------------------------------------------------ */ static void init_slide( /*void*/ ) { node i; for (i = dicsiz; i <= dicsiz + UCHAR_MAX; i++) { level[i] = 1; #if PERCOLATE position[i] = NIL; /* sentinel */ #endif } for (i = dicsiz; i < dicsiz * 2; i++) parent[i] = NIL; avail = 1; for (i = 1; i < dicsiz - 1; i++) next[i] = i + 1; next[dicsiz - 1] = NIL; for (i = dicsiz * 2; i <= max_hash_val; i++) next[i] = NIL; hash1 = dicbit - 9; hash2 = dicsiz * 2; } #define HASH(p, c) ((p) + ((c) << hash1) + hash2) /* ------------------------------------------------------------------------ */ static /* inline */ node child(q, c) /* q's child for character c (NIL if not found) */ node q; unsigned char c; { node r; r = next[HASH(q, c)]; parent[NIL] = q; /* sentinel */ while (parent[r] != q) r = next[r]; return r; } static /* inline */ void makechild(q, c, r) /* Let r be q's child for character c. */ node q; unsigned char c; node r; { node h, t; h = HASH(q, c); t = next[h]; next[h] = r; next[r] = t; prev[t] = r; prev[r] = h; parent[r] = q; childcount[q]++; } /* ------------------------------------------------------------------------ */ static /* inline */ void split(old) node old; { node new, t; new = avail; avail = next[new]; childcount[new] = 0; t = prev[old]; prev[new] = t; next[t] = new; t = next[old]; next[new] = t; prev[t] = new; parent[new] = parent[old]; level[new] = matchlen; position[new] = pos; makechild(new, text[matchpos + matchlen], old); makechild(new, text[pos + matchlen], pos); } /* ------------------------------------------------------------------------ */ static void insert_node(/*void*/) { node q, r, j, t; unsigned char c, *t1, *t2; if (matchlen >= 4) { matchlen--; r = (matchpos + 1) | dicsiz; while ((q = parent[r]) == NIL) r = next[r]; while (level[q] >= matchlen) { r = q; q = parent[q]; } #if PERCOLATE t = q; while (position[t] < 0) { position[t] = pos; t = parent[t]; } if (t < dicsiz) position[t] = pos | SHRT_MIN; #else t = q; while (t < dicsiz) { position[t] = pos; t = parent[t]; } #endif } else { q = text[pos] + dicsiz; c = text[pos + 1]; if ((r = child(q, c)) == NIL) { makechild(q, c, pos); matchlen = 1; return; } matchlen = 2; } for (;;) { if (r >= dicsiz) { j = maxmatch; matchpos = r; } else { j = level[r]; matchpos = position[r] & SHRT_MAX; } if (matchpos >= pos) matchpos -= dicsiz; t1 = &text[pos + matchlen]; t2 = &text[matchpos + matchlen]; while (matchlen < j) { if (*t1 != *t2) { split(r); return; } matchlen++; t1++; t2++; } if (matchlen == maxmatch) break; position[r] = pos; q = r; if ((r = child(q, *t1)) == NIL) { makechild(q, *t1, pos); return; } matchlen++; } t = prev[r]; prev[pos] = t; next[t] = pos; t = next[r]; next[pos] = t; prev[t] = pos; parent[pos] = q; parent[r] = NIL; next[r] = pos; /* special use of next[] */ } /* ------------------------------------------------------------------------ */ static void delete_node(/*void*/) { #if PERCOLATE node q, r, s, t, u; #else node r, s, t, u; #endif if (parent[pos] == NIL) return; r = prev[pos]; s = next[pos]; next[r] = s; prev[s] = r; r = parent[pos]; parent[pos] = NIL; if (r >= dicsiz || --childcount[r] > 1) return; #if PERCOLATE t = position[r] & SHRT_MAX; #else t = position[r]; #endif if (t >= pos) t -= dicsiz; #if PERCOLATE s = t; q = parent[r]; while ((u = position[q]) < 0) { u &= SHRT_MAX; if (u >= pos) u -= dicsiz; if (u > s) s = u; position[q] = (s | dicsiz); q = parent[q]; } if (q < dicsiz) { if (u >= pos) u -= dicsiz; if (u > s) s = u; position[q] = (s | dicsiz) | SHRT_MIN; } #endif s = child(r, text[t + level[r]]); t = prev[s]; u = next[s]; next[t] = u; prev[u] = t; t = prev[r]; next[t] = s; prev[s] = t; t = next[r]; prev[t] = s; next[s] = t; parent[s] = parent[r]; parent[r] = NIL; next[r] = avail; avail = r; } /* ------------------------------------------------------------------------ */ /* static */ void get_next_match(/*void*/) { int n; remainder--; if (++pos == dicsiz * 2) { bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch); n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile); encoded_origsize += n; remainder += n; pos = dicsiz; } delete_node(); insert_node(); } /* ------------------------------------------------------------------------ */ void encode(interface) struct interfacing *interface; { int lastmatchlen, dicsiz1; node lastmatchpos; infile = interface->infile; outfile = interface->outfile; origsize = interface->original; compsize = count = 0L; crc = unpackable = 0; init_slide(); encode_set.encode_start(); dicsiz1 = dicsiz - 1; pos = dicsiz + maxmatch; memset(&text[pos], ' ', dicsiz); remainder = fread_crc(&text[pos], dicsiz, infile); encoded_origsize = remainder; matchlen = 0; insert_node(); while (remainder > 0 && !unpackable) { lastmatchlen = matchlen; lastmatchpos = matchpos; get_next_match(); if (matchlen > remainder) matchlen = remainder; if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) { encode_set.output(text[pos - 1], 0); count++; } else { encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD), (pos - lastmatchpos - 2) & dicsiz1); while (--lastmatchlen > 0) { get_next_match(); count++; } if (matchlen > remainder) matchlen = remainder; } } encode_set.encode_end(); interface->packed = compsize; interface->original = encoded_origsize; } /* ------------------------------------------------------------------------ */ void decode(interface) struct interfacing *interface; { int i, j, k, c, dicsiz1, offset; infile = interface->infile; outfile = interface->outfile; dicbit = interface->dicbit; origsize = interface->original; compsize = interface->packed; decode_set = decode_define[interface->method - 1]; crc = 0; prev_char = -1; dicsiz = 1 << dicbit; text = (unsigned char *) malloc(dicsiz); if (text == NULL) /* error(MEMOVRERR, NULL); */ exit(errno); memset(text, ' ', dicsiz); decode_set.decode_start(); dicsiz1 = dicsiz - 1; offset = (interface->method == 7) ? 0x100 - 2 : 0x100 - 3; count = 0; loc = 0; while (count < origsize) { c = decode_set.decode_c(); if (c <= UCHAR_MAX) { text[loc++] = c; if (loc == dicsiz) { fwrite_crc(text, dicsiz, outfile); loc = 0; } count++; } else { j = c - offset; i = (loc - decode_set.decode_p() - 1) & dicsiz1; count += j; for (k = 0; k < j; k++) { c = text[(i + k) & dicsiz1]; text[loc++] = c; if (loc == dicsiz) { fwrite_crc(text, dicsiz, outfile); loc = 0; } } } } if (loc != 0) { fwrite_crc(text, loc, outfile); } free(text); }
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.