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