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