![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lzh.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Synchronet] / sbbs / sbbs2 / fido|
Return to lzh.c CVS log | Up to [Synchronet] / sbbs / sbbs2 / fido |
1.1 root 1: /* LZH.C */
2:
3: /* Digital Dynamics conversion of 1988 LZH (LHarc) encoding functions */
4: /* Based on Japanese version 29-NOV-1988 */
5: /* LZSS coded by Haruhiko Okumura */
6: /* Adaptive Huffman Coding coded by Haruyasu Yoshizaki */
7:
8:
9: #include <stdio.h>
10: #include <stdlib.h>
11: #include <string.h>
12: #include <ctype.h>
13: #ifndef __WATCOMC__
14: #include <alloc.h>
15: #endif
16:
17: /****************************************************************************/
18: /* Memory allocation macros for various compilers and environments */
19: /* MALLOC is used for allocations of 64k or less */
20: /* FREE is used to free buffers allocated with MALLOC */
21: /* LMALLOC is used for allocations of possibly larger than 64k */
22: /* LFREE is used to free buffers allocated with LMALLOC */
23: /* REALLOC is used to re-size a previously MALLOCed or LMALLOCed buffer */
24: /****************************************************************************/
25: #if defined(__COMPACT__) || defined(__LARGE__) || defined(__HUGE__)
26: #if defined(__TURBOC__)
27: #define REALLOC(x,y) farrealloc(x,y)
28: #define LMALLOC(x) farmalloc(x)
29: #define MALLOC(x) farmalloc(x)
30: #define LFREE(x) farfree(x)
31: #define FREE(x) farfree(x)
32: #elif defined(__WATCOMC__)
33: #define REALLOC realloc
34: #define LMALLOC(x) halloc(x,1) /* far heap, but slow */
35: #define MALLOC malloc /* far heap, but 64k max */
36: #define LFREE hfree
37: #define FREE free
38: #else /* Other 16-bit Compiler */
39: #define REALLOC realloc
40: #define LMALLOC malloc
41: #define MALLOC malloc
42: #define LFREE free
43: #define FREE free
44: #endif
45: #else /* 32-bit Compiler or Small Memory Model */
46: #define REALLOC realloc
47: #define LMALLOC malloc
48: #define MALLOC malloc
49: #define LFREE free
50: #define FREE free
51: #endif
52:
53:
54:
55: typedef unsigned char uchar;
56:
57: /* LZSS Parameters */
58:
59: #define LZH_N 4096 /* Size of string buffer */
60: #define LZH_F 60 /* Size of look-ahead buffer */
61: #define LZH_THRESHOLD 2
62: #define LZH_NIL LZH_N /* End of tree's node */
63:
64: #ifdef LZH_DYNAMIC_BUF
65:
66: unsigned char *lzh_text_buf;
67: short int lzh_match_position, lzh_match_length,
68: *lzh_lson, *lzh_rson, *lzh_dad;
69:
70: #else
71:
72: unsigned char lzh_text_buf[LZH_N + LZH_F - 1];
73: short int lzh_match_position, lzh_match_length,
74: lzh_lson[LZH_N + 1], lzh_rson[LZH_N + 257], lzh_dad[LZH_N + 1];
75:
76: #endif
77:
78:
79: void lzh_init_tree(void) /* Initializing tree */
80: {
81: short int i;
82:
83: for (i = LZH_N + 1; i <= LZH_N + 256; i++)
84: lzh_rson[i] = LZH_NIL; /* root */
85: for (i = 0; i < LZH_N; i++)
86: lzh_dad[i] = LZH_NIL; /* node */
87: }
88:
89: /******************************/
90: /* Inserting node to the tree */
91: /* Only used during encoding */
92: /******************************/
93: void lzh_insert_node(short int r)
94: {
95: short int i, p, cmp;
96: unsigned char *key;
97: unsigned c;
98:
99: cmp = 1;
100: key = lzh_text_buf+r;
101: p = LZH_N + 1 + key[0];
102: lzh_rson[r] = lzh_lson[r] = LZH_NIL;
103: lzh_match_length = 0;
104: for ( ; ; ) {
105: if (cmp >= 0) {
106: if (lzh_rson[p] != LZH_NIL)
107: p = lzh_rson[p];
108: else {
109: lzh_rson[p] = r;
110: lzh_dad[r] = p;
111: return;
112: }
113: } else {
114: if (lzh_lson[p] != LZH_NIL)
115: p = lzh_lson[p];
116: else {
117: lzh_lson[p] = r;
118: lzh_dad[r] = p;
119: return;
120: }
121: }
122: for (i = 1; i < LZH_F; i++)
123: if ((cmp = key[i] - lzh_text_buf[p + i]) != 0)
124: break;
125: if (i > LZH_THRESHOLD) {
126: if (i > lzh_match_length) {
127: lzh_match_position = ((r - p) & (LZH_N - 1)) - 1;
128: if ((lzh_match_length = i) >= LZH_F)
129: break;
130: }
131: if (i == lzh_match_length) {
132: if ((c = ((r - p) & (LZH_N - 1)) - 1) < lzh_match_position) {
133: lzh_match_position = c;
134: }
135: }
136: }
137: }
138: lzh_dad[r] = lzh_dad[p];
139: lzh_lson[r] = lzh_lson[p];
140: lzh_rson[r] = lzh_rson[p];
141: lzh_dad[lzh_lson[p]] = r;
142: lzh_dad[lzh_rson[p]] = r;
143: if (lzh_rson[lzh_dad[p]] == p)
144: lzh_rson[lzh_dad[p]] = r;
145: else
146: lzh_lson[lzh_dad[p]] = r;
147: lzh_dad[p] = LZH_NIL; /* remove p */
148: }
149:
150: void lzh_delete_node(short int p) /* Deleting node from the tree */
151: {
152: short int q;
153:
154: if (lzh_dad[p] == LZH_NIL)
155: return; /* unregistered */
156: if (lzh_rson[p] == LZH_NIL)
157: q = lzh_lson[p];
158: else
159: if (lzh_lson[p] == LZH_NIL)
160: q = lzh_rson[p];
161: else {
162: q = lzh_lson[p];
163: if (lzh_rson[q] != LZH_NIL) {
164: do {
165: q = lzh_rson[q];
166: } while (lzh_rson[q] != LZH_NIL);
167: lzh_rson[lzh_dad[q]] = lzh_lson[q];
168: lzh_dad[lzh_lson[q]] = lzh_dad[q];
169: lzh_lson[q] = lzh_lson[p];
170: lzh_dad[lzh_lson[p]] = q;
171: }
172: lzh_rson[q] = lzh_rson[p];
173: lzh_dad[lzh_rson[p]] = q;
174: }
175: lzh_dad[q] = lzh_dad[p];
176: if (lzh_rson[lzh_dad[p]] == p)
177: lzh_rson[lzh_dad[p]] = q;
178: else
179: lzh_lson[lzh_dad[p]] = q;
180: lzh_dad[p] = LZH_NIL;
181: }
182:
183: /* Huffman coding parameters */
184:
185: #define LZH_N_CHAR (256 - LZH_THRESHOLD + LZH_F)
186: /* character code (= 0..LZH_N_CHAR-1) */
187: #define LZH_T (LZH_N_CHAR * 2 - 1) /* Size of table */
188: #define LZH_R (LZH_T - 1) /* root position */
189: #define MAX_FREQ 0x8000
190: /* update when cumulative frequency */
191: /* reaches to this value */
192:
193: /*
194: * Tables for encoding/decoding upper 6 bits of
195: * sliding dictionary pointer
196: */
197: /* encoder table */
198: uchar lzh_p_len[64] = {
199: 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
200: 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
201: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
202: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
203: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
204: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
205: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
206: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
207: };
208:
209: uchar lzh_p_code[64] = {
210: 0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
211: 0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
212: 0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
213: 0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
214: 0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
215: 0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
216: 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
217: 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
218: };
219:
220: /* decoder table */
221: uchar lzh_d_code[256] = {
222: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
223: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
224: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
225: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
226: 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
227: 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
228: 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
229: 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
230: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
231: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
232: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
233: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
234: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
235: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
236: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
237: 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
238: 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
239: 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
240: 0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
241: 0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
242: 0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
243: 0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
244: 0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
245: 0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
246: 0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
247: 0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
248: 0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
249: 0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
250: 0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
251: 0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
252: 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
253: 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
254: };
255:
256: uchar lzh_d_len[256] = {
257: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
258: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
259: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
260: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
261: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
262: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
263: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
264: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
265: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
266: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
267: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
268: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
269: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
270: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
271: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
272: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
273: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
274: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
275: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
276: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
277: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
278: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
279: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
280: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
281: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
282: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
283: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
284: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
285: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
286: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
287: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
288: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
289: };
290:
291: #ifdef LZH_DYNAMIC_BUF
292:
293: unsigned short *lzh_freq=NULL; /* cumulative freq table */
294:
295: /*
296: * pointing parent nodes.
297: * area [LZH_T..(LZH_T + LZH_N_CHAR - 1)] are pointers for leaves
298: */
299: short int *lzh_prnt=NULL;
300:
301: /* pointing children nodes (son[], son[] + 1)*/
302: short int *lzh_son=NULL;
303:
304: #else /* STATIC */
305:
306: unsigned short lzh_freq[LZH_T + 1]; /* cumulative freq table */
307: short int lzh_prnt[LZH_T + LZH_N_CHAR];
308: short int lzh_son[LZH_T + 1]; /* bug fixed by Digital Dynamics */
309:
310: #endif
311:
312:
313: unsigned short lzh_getbuf = 0; /* Was just "unsigned" fixed 04/12/95 */
314: uchar lzh_getlen = 0;
315:
316: int lzh_getbit(uchar *inbuf, long *incnt, long inlen) /* get one bit */
317: {
318: short int i;
319:
320: while (lzh_getlen <= 8) {
321: if((*incnt)>=inlen)
322: i=0;
323: else
324: i=inbuf[(*incnt)++];
325: lzh_getbuf |= i << (8 - lzh_getlen);
326: lzh_getlen += 8;
327: }
328: i = lzh_getbuf;
329: lzh_getbuf <<= 1;
330: lzh_getlen--;
331: return (i < 0);
332: }
333:
334: short int lzh_getbyte(uchar *inbuf, long *incnt, long inlen) /* get a byte */
335: {
336: unsigned short i;
337:
338: while (lzh_getlen <= 8) {
339: if((*incnt)>=inlen)
340: i=0;
341: else
342: i=inbuf[(*incnt)++];
343: lzh_getbuf |= i << (8 - lzh_getlen);
344: lzh_getlen += 8;
345: }
346: i = lzh_getbuf;
347: lzh_getbuf <<= 8;
348: lzh_getlen -= 8;
349: return i >> 8;
350: }
351:
352: unsigned lzh_putbuf = 0;
353: uchar lzh_putlen = 0;
354:
355: /* output c bits */
356: void lzh_putcode(short int l, unsigned short c, uchar *outbuf, long *outlen)
357: {
358: lzh_putbuf |= c >> lzh_putlen;
359: if ((lzh_putlen += l) >= 8) {
360: outbuf[(*outlen)++]=(lzh_putbuf >> 8);
361: if ((lzh_putlen -= 8) >= 8) {
362: outbuf[(*outlen)++]=lzh_putbuf;
363: lzh_putlen -= 8;
364: lzh_putbuf = c << (l - lzh_putlen);
365: } else {
366: lzh_putbuf <<= 8;
367: }
368: }
369: }
370:
371:
372: /* initialize freq tree */
373:
374: void lzh_start_huff()
375: {
376: short int i, j;
377:
378: lzh_getbuf = 0; /* Added by Digital Dynamics for repeating operations */
379: lzh_getlen = 0;
380: lzh_putbuf = 0;
381: lzh_putlen = 0;
382:
383: for (i = 0; i < LZH_N_CHAR; i++) {
384: lzh_freq[i] = 1;
385: lzh_son[i] = i + LZH_T;
386: lzh_prnt[i + LZH_T] = i;
387: }
388: i = 0; j = LZH_N_CHAR;
389: while (j <= LZH_R) {
390: lzh_freq[j] = lzh_freq[i] + lzh_freq[i + 1];
391: lzh_son[j] = i;
392: lzh_prnt[i] = lzh_prnt[i + 1] = j;
393: i += 2; j++;
394: }
395: lzh_freq[LZH_T] = 0xffff;
396: lzh_prnt[LZH_R] = 0;
397: }
398:
399:
400: /* reconstruct freq tree */
401:
402: void lzh_reconst()
403: {
404: short int i, j, k;
405: unsigned short f, l;
406:
407: /* halven cumulative freq for leaf nodes */
408: j = 0;
409: for (i = 0; i < LZH_T; i++) {
410: if (lzh_son[i] >= LZH_T) {
411: lzh_freq[j] = (lzh_freq[i] + 1) / 2;
412: lzh_son[j] = lzh_son[i];
413: j++;
414: }
415: }
416: /* make a tree : first, connect children nodes */
417: for (i = 0, j = LZH_N_CHAR; j < LZH_T; i += 2, j++) {
418: k = i + 1;
419: f = lzh_freq[j] = lzh_freq[i] + lzh_freq[k];
420: for (k = j - 1; f < lzh_freq[k]; k--);
421: k++;
422: l = (j - k) * 2;
423:
424: /* movmem() is Turbo-C dependent
425: rewritten to memmove() by Kenji */
426:
427: /* movmem(&lzh_freq[k], &lzh_freq[k + 1], l); */
428: (void)memmove(lzh_freq+k+1,lzh_freq+k, l);
429: lzh_freq[k] = f;
430: /* movmem(&lzh_son[k], &lzh_son[k + 1], l); */
431: (void)memmove(lzh_son+k+1,lzh_son+k, l);
432: lzh_son[k] = i;
433: }
434: /* connect parent nodes */
435: for (i = 0; i < LZH_T; i++) {
436: if ((k = lzh_son[i]) >= LZH_T) {
437: lzh_prnt[k] = i;
438: } else {
439: lzh_prnt[k] = lzh_prnt[k + 1] = i;
440: }
441: }
442: }
443:
444: /* update freq tree */
445:
446: void lzh_update(short int c)
447: {
448: short int i, j, k, l;
449:
450: if (lzh_freq[LZH_R] == MAX_FREQ) {
451: lzh_reconst();
452: }
453: c = lzh_prnt[c + LZH_T];
454: do {
455: k = ++lzh_freq[c];
456:
457: /* swap nodes to keep the tree freq-ordered */
458: if (k > lzh_freq[l = c + 1]) {
459: while (k > lzh_freq[++l]);
460: l--;
461: lzh_freq[c] = lzh_freq[l];
462: lzh_freq[l] = k;
463:
464: i = lzh_son[c];
465: lzh_prnt[i] = l;
466: if (i < LZH_T) lzh_prnt[i + 1] = l;
467:
468: j = lzh_son[l];
469: lzh_son[l] = i;
470:
471: lzh_prnt[j] = c;
472: if (j < LZH_T) lzh_prnt[j + 1] = c;
473: lzh_son[c] = j;
474:
475: c = l;
476: }
477: } while ((c = lzh_prnt[c]) != 0); /* do it until reaching the root */
478: }
479:
480: unsigned short lzh_code, lzh_len;
481:
482: void lzh_encode_char(unsigned short c, uchar *outbuf, long *outlen)
483: {
484: unsigned short i;
485: short int j, k;
486:
487: i = 0;
488: j = 0;
489: k = lzh_prnt[c + LZH_T];
490:
491: /* search connections from leaf node to the root */
492: do {
493: i >>= 1;
494:
495: /*
496: if node's address is odd, output 1
497: else output 0
498: */
499: if (k & 1) i += 0x8000;
500:
501: j++;
502: } while ((k = lzh_prnt[k]) != LZH_R);
503: lzh_putcode(j, i, outbuf, outlen);
504: lzh_code = i;
505: lzh_len = j;
506: lzh_update(c);
507: }
508:
509: void lzh_encode_position(unsigned short c, uchar *outbuf, long *outlen)
510: {
511: unsigned short i;
512:
513: /* output upper 6 bits with encoding */
514: i = c >> 6;
515: lzh_putcode(lzh_p_len[i], (unsigned)lzh_p_code[i] << 8, outbuf, outlen);
516:
517: /* output lower 6 bits directly */
518: lzh_putcode(6, (c & 0x3f) << 10, outbuf, outlen);
519: }
520:
521: void lzh_encode_end(uchar *outbuf, long *outlen)
522: {
523: if (lzh_putlen) {
524: outbuf[(*outlen)++]=(lzh_putbuf >> 8);
525: }
526: }
527:
528: short int lzh_decode_char(uchar *inbuf, long *incnt, long inlen)
529: {
530: unsigned short c;
531:
532: c = lzh_son[LZH_R];
533:
534: /*
535: * start searching tree from the root to leaves.
536: * choose node #(lzh_son[]) if input bit == 0
537: * else choose #(lzh_son[]+1) (input bit == 1)
538: */
539: while (c < LZH_T) {
540: c += lzh_getbit(inbuf,incnt,inlen);
541: c = lzh_son[c];
542: }
543: c -= LZH_T;
544: lzh_update(c);
545: return c;
546: }
547:
548: short int lzh_decode_position(uchar *inbuf, long *incnt, long inlen)
549: {
550: unsigned short i, j, c;
551:
552: /* decode upper 6 bits from given table */
553: i = lzh_getbyte(inbuf,incnt,inlen);
554: c = (unsigned)lzh_d_code[i] << 6;
555: j = lzh_d_len[i];
556:
557: /* input lower 6 bits directly */
558: j -= 2;
559: while (j--) {
560: i = (i << 1) + lzh_getbit(inbuf,incnt,inlen);
561: }
562: return c | i & 0x3f;
563: }
564:
565: /* Compression */
566:
567: /* Encoding/Compressing */
568: /* Returns length of outbuf */
569: long lzh_encode(uchar *inbuf, long inlen, uchar *outbuf)
570: {
571: short int i, c, len, r, s, last_match_length;
572: long incnt,outlen; /* textsize=0; */
573:
574: #ifdef LZH_DYNAMIC_BUF
575:
576: if((lzh_text_buf=(uchar *)MALLOC(LZH_N + LZH_F - 1))==NULL)
577: return(-1);
578: if((lzh_freq=(unsigned short*)MALLOC((LZH_T + 1)*sizeof(unsigned short)))==NULL) {
579: FREE(lzh_text_buf);
580: return(-1); }
581: if((lzh_prnt=(short *)MALLOC((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) {
582: FREE(lzh_text_buf);
583: FREE(lzh_freq);
584: return(-1); }
585: if((lzh_son=(short *)MALLOC((LZH_T + 1) * sizeof(short)))==NULL) {
586: FREE(lzh_text_buf);
587: FREE(lzh_prnt);
588: FREE(lzh_freq);
589: return(-1); }
590: if((lzh_lson=(short *)MALLOC((LZH_N + 1)*sizeof(short)))==NULL) {
591: FREE(lzh_text_buf);
592: FREE(lzh_prnt);
593: FREE(lzh_freq);
594: FREE(lzh_son);
595: return(-1); }
596: if((lzh_rson=(short *)MALLOC((LZH_N + 257)*sizeof(short)))==NULL) {
597: FREE(lzh_text_buf);
598: FREE(lzh_prnt);
599: FREE(lzh_freq);
600: FREE(lzh_son);
601: FREE(lzh_lson);
602: return(-1); }
603: if((lzh_dad=(short *)MALLOC((LZH_N + 1)*sizeof(short)))==NULL) {
604: FREE(lzh_text_buf);
605: FREE(lzh_prnt);
606: FREE(lzh_freq);
607: FREE(lzh_son);
608: FREE(lzh_lson);
609: FREE(lzh_rson);
610: return(-1); }
611: #endif
612:
613: incnt=0;
614: memcpy(outbuf,&inlen,sizeof(inlen));
615: outlen=sizeof(inlen);
616: if(!inlen) {
617: #ifdef LZH_DYNAMIC_BUF
618: FREE(lzh_text_buf);
619: FREE(lzh_prnt);
620: FREE(lzh_freq);
621: FREE(lzh_son);
622: FREE(lzh_lson);
623: FREE(lzh_rson);
624: FREE(lzh_dad);
625: #endif
626: return(outlen); }
627: lzh_start_huff();
628: lzh_init_tree();
629: s = 0;
630: r = LZH_N - LZH_F;
631: for (i = s; i < r; i++)
632: lzh_text_buf[i] = ' ';
633: for (len = 0; len < LZH_F && incnt<inlen; len++)
634: lzh_text_buf[r + len] = inbuf[incnt++];
635: /* textsize = len; */
636: for (i = 1; i <= LZH_F; i++)
637: lzh_insert_node(r - i);
638: lzh_insert_node(r);
639: do {
640: if (lzh_match_length > len)
641: lzh_match_length = len;
642: if (lzh_match_length <= LZH_THRESHOLD) {
643: lzh_match_length = 1;
644: lzh_encode_char(lzh_text_buf[r],outbuf,&outlen);
645: } else {
646: lzh_encode_char(255 - LZH_THRESHOLD + lzh_match_length
647: ,outbuf,&outlen);
648: lzh_encode_position(lzh_match_position
649: ,outbuf,&outlen);
650: }
651: last_match_length = lzh_match_length;
652: for (i = 0; i < last_match_length && incnt<inlen; i++) {
653: lzh_delete_node(s);
654: c=inbuf[incnt++];
655: lzh_text_buf[s] = c;
656: if (s < LZH_F - 1)
657: lzh_text_buf[s + LZH_N] = c;
658: s = (s + 1) & (LZH_N - 1);
659: r = (r + 1) & (LZH_N - 1);
660: lzh_insert_node(r);
661: }
662: /***
663: if ((textsize += i) > printcount) {
664: printf("%12ld\r", textsize);
665: printcount += 1024;
666: }
667: ***/
668: while (i++ < last_match_length) {
669: lzh_delete_node(s);
670: s = (s + 1) & (LZH_N - 1);
671: r = (r + 1) & (LZH_N - 1);
672: if (--len) lzh_insert_node(r);
673: }
674: } while (len > 0);
675: lzh_encode_end(outbuf,&outlen);
676: /*
677: printf("input: %ld (%ld) bytes\n", inlen,textsize);
678: printf("output: %ld bytes\n", outlen);
679: printf("output/input: %.3f\n", (double)outlen / inlen);
680: */
681:
682: #ifdef LZH_DYNAMIC_BUF
683: FREE(lzh_text_buf);
684: FREE(lzh_prnt);
685: FREE(lzh_freq);
686: FREE(lzh_son);
687: FREE(lzh_lson);
688: FREE(lzh_rson);
689: FREE(lzh_dad);
690: #endif
691:
692: return(outlen);
693: }
694:
695: /* Decoding/Uncompressing */
696: /* Returns length of outbuf */
697: long lzh_decode(uchar *inbuf, long inlen, uchar *outbuf)
698: {
699: short int i, j, k, r, c;
700: unsigned long int count;
701: long incnt,textsize;
702:
703: #ifdef LZH_DYNAMIC_BUF
704:
705: if((lzh_text_buf=(uchar *)MALLOC((LZH_N + LZH_F - 1)*2))==NULL)
706: return(-1);
707: if((lzh_freq=(unsigned short *)MALLOC((LZH_T + 1)*sizeof(unsigned short)))
708: ==NULL) {
709: FREE(lzh_text_buf);
710: return(-1); }
711: if((lzh_prnt=(short *)MALLOC((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) {
712: FREE(lzh_text_buf);
713: FREE(lzh_freq);
714: return(-1); }
715: if((lzh_son=(short *)MALLOC((LZH_T + 1) * sizeof(short)))==NULL) {
716: FREE(lzh_text_buf);
717: FREE(lzh_prnt);
718: FREE(lzh_freq);
719: return(-1); }
720:
721: #endif
722:
723: incnt=0;
724: memcpy(&textsize,inbuf,sizeof(textsize));
725: incnt+=sizeof(textsize);
726: if (textsize == 0) {
727: #ifdef LZH_DYNAMIC_BUF
728: FREE(lzh_text_buf);
729: FREE(lzh_prnt);
730: FREE(lzh_freq);
731: FREE(lzh_son);
732: #endif
733: return(textsize); }
734: lzh_start_huff();
735: for (i = 0; i < LZH_N - LZH_F; i++)
736: *(lzh_text_buf+i) = ' ';
737: r = LZH_N - LZH_F;
738: for (count = 0; count < textsize; ) {
739: c = lzh_decode_char(inbuf,&incnt,inlen);
740: if (c < 256) {
741: outbuf[count]=c;
742: #if 0
743: if(r>(LZH_N + LZH_F - 1) || r<0) {
744: printf("Overflow! (%d)\n",r);
745: getch();
746: exit(-1); }
747: #endif
748: *(lzh_text_buf+r) = c;
749: r++;
750: r &= (LZH_N - 1);
751: count++;
752: } else {
753: i = (r - lzh_decode_position(inbuf,&incnt,inlen) - 1)
754: & (LZH_N - 1);
755: j = c - 255 + LZH_THRESHOLD;
756: for (k = 0; k < j && count<textsize; k++) {
757: c = lzh_text_buf[(i + k) & (LZH_N - 1)];
758: outbuf[count]=c;
759: #if 0
760: if(r>(LZH_N + LZH_F - 1) || r<0) {
761: printf("Overflow! (%d)\n",r);
762: exit(-1); }
763: #endif
764: *(lzh_text_buf+r) = c;
765: r++;
766: r &= (LZH_N - 1);
767: count++;
768: }
769: }
770: }
771: /***
772: printf("%12ld\n", count);
773: ***/
774:
775: #ifdef LZH_DYNAMIC_BUF
776: FREE(lzh_text_buf);
777: FREE(lzh_prnt);
778: FREE(lzh_freq);
779: FREE(lzh_son);
780: #endif
781:
782: return(count);
783: }
784:
785:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.