![[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 [PGP] / pgp / src|
Return to lzh.c CVS log | Up to [PGP] / pgp / src |
1.1 root 1: /*--------------------------------------------------------------------------*/
2: /* lzh.c - file compression subroutines for lzss + Huffman encoding */
3: /* */
4: /* Source code history: */
5: /* */
6: /* The original lzhuf.c source was written by Haruyasu Yoshizaki on */
7: /* 11/20/1988 with some minor changes 4/6/1989. Comments were */
8: /* translated by Haruhiko Okumura on 4/7/1989. */
9: /* */
10: /* The original lzss compression was written by Haruhiko Okumura, */
11: /* 12-2-404 Green Heights, 580 Nagasawa, Yokosuka 239, Japan. The */
12: /* Adaptive Huffman algorithm was added by Yoshizaki to increase */
13: /* speed and compression and developed it into the LHarc archiver. */
14: /* */
15: /* Modifications were made by Allan Hoeltje P.O. Box 18045 Boulder, */
16: /* Colorado, USA 80308-8045, during the month of June 1989. These */
17: /* modifications include: More comments; better file error handling; */
18: /* run-length encoding input and output to increase the compression */
19: /* ratio. Note: the run length encoding gives you about 2 to 5 per */
20: /* cent better compression but more importantly it speeds up the */
21: /* compression process on text files by about 60 per cent. */
22: /* */
23: /* Additional modifications made on February 17, 1991 to make the */
24: /* routines more usable as subroutines for a parent application. */
25: /* The two routines, lzhEncode and lzhDecode are the main entry */
26: /* points. Everything else is static. */
27: /* */
28: /* It is my understanding that the lzHuff algorithm and source code */
29: /* is in the public domain and it's use is free and unrestricted. */
30: /*--------------------------------------------------------------------------*/
31:
32: #include <stdio.h>
33: #include <stdlib.h>
34: #include <string.h>
35: #include <ctype.h>
36: #include "rsalib.h"
37: #include "rsaio.h"
38:
39: /*
40: ** Convert to or from external byte order.
41: ** Note that hilo_swap does nothing if this is a LSB-first CPU.
42: */
43:
44: #define convert2(x,lx) hilo_swap( (byteptr)&(x), (lx) )
45: #define convert(x) convert2( (x), sizeof(x) )
46:
47:
48: #define EXIT_FAILURE 1
49: #define EXIT_SUCCESS 0
50: typedef unsigned char uchar;
51:
52: static FILE *inFile; /* clear text input */
53: static FILE *outFile; /* compressed output */
54:
55: static unsigned long int codesize = 0;
56: static unsigned long int inCount = 0;
57: static unsigned long int outCount = 0;
58:
59: void Error( char *message )
60: {
61: printf( "\n%s\n", message );
62: exit( EXIT_FAILURE );
63: }
64:
65: /*--------------------------------------------------------------------------*/
66: /* Run length encoded getc and putc routines. */
67: /*--------------------------------------------------------------------------*/
68:
69: /* getCHR
70: This does a simple getc and count.
71: */
72: static int getCHR( FILE *f )
73: {
74: int c;
75: if ((c = getc( f )) != EOF)
76: inCount++;
77: return( c );
78: }
79:
80:
81: /* putCHR
82: This does a simple putc and count with a write error check.
83: */
84: void putCHR( int c, FILE *f )
85: {
86: if (putc( c, f ) == EOF)
87: {
88: Error( "lzh putCHR: can't write output file!" );
89: }
90: outCount++;
91: }
92:
93:
94: #define NOHIST 0 /* don't consider previous input */
95: #define INREP 1 /* sending a repeated value */
96: #define SENTCHAR 1 /* lastchar set, no lookahead yet */
97: #define SENDNEWC 2 /* run over, send new char next */
98: #define SENDCNT 3 /* newchar set, send count next */
99: #define DLE 0x90 /* repeat sequence marker */
100:
101: static unsigned char state = NOHIST; /* current packing state */
102:
103: /*--------------------------------------------------------------------------*/
104: /* getRLC */
105: /* Non-repeat compression - text is read from file "f" and passed */
106: /* through normally except that a run of more than two characters is */
107: /* encoded as: <char> <DLE> <count>. Special case: a count of zero */
108: /* indicates that the DLE is really a DLE, not a repeat marker. */
109: /*--------------------------------------------------------------------------*/
110:
111: static int
112: getRLC( FILE *f )
113: {
114: static int lastc; /* value returned on last call */
115: static int repcnt; /* repetition counter */
116: static int c; /* latest value seen */
117: static char *badstate = "lzh getRLC: Bad packing state!";
118:
119: switch (state) /* depends on our state */
120: {
121: case NOHIST: /* no relevant history */
122: state = SENTCHAR;
123: return (lastc = getCHR(f)); /* remember the value next time */
124: break;
125: case SENTCHAR: /* char was sent. look ahead */
126: switch (lastc) /* action depends on char */
127: {
128: case DLE: /* if we sent a real DLE */
129: state = NOHIST; /* then start over again */
130: return (0); /* but note that the DLE was real */
131: break;
132: case EOF: /* EOF is always a special case */
133: return (EOF);
134: break;
135: default: /* else test for a repeat */
136: for (repcnt = 1 ;
137: ((c = getCHR(f)) == lastc) && (repcnt < 255) ;
138: repcnt++); /* find end of run */
139:
140: switch(repcnt) /* action depends on run size */
141: {
142: case 1: /* not a repeat */
143: return (lastc = c); /* but remember value next time */
144: break;
145: case 2: /* a repeat, but too short */
146: state = SENDNEWC; /* send the second one next time */
147: return (lastc);
148: break;
149: default: /* a run - compress it */
150: state = SENDCNT; /* send repeat count next time */
151: return (DLE); /* send repeat marker this time */
152: break;
153: }
154: }
155: case SENDNEWC: /* send second char of short run */
156: state = SENTCHAR;
157: return (lastc = c);
158: break;
159: case SENDCNT: /* sent DLE, now send count */
160: state = SENDNEWC;
161: return (repcnt);
162: break;
163: default:
164: {
165: Error( badstate );
166: }
167: }
168: }
169:
170:
171: /*--------------------------------------------------------------------------*/
172: /* putRLC */
173: /* This routine is used to decode non-repeat compression bytes and */
174: /* write them to file "t". Bytes are passed one at a time in coded */
175: /* format, and are written out uncoded. The data is stored normally, */
176: /* except that runs of more than two characters are represented as: */
177: /* */
178: /* <char> <DLE> <count> */
179: /* with a special case that a count of zero indicates a DLE as data, */
180: /* not as a repeat marker. */
181: /*--------------------------------------------------------------------------*/
182:
183: static int
184: putRLC( int c, FILE *t )
185: {
186: static int lastc; /* last character seen */
187: static char *badstate = "lzh putRLC: Bad unpacking state!";
188:
189: switch (state) /* action depends on our state */
190: {
191: case NOHIST: /* no previous history */
192: if (c == DLE) /* if starting a series */
193: state = INREP; /* then remember it next time */
194: else
195: putCHR( (lastc = c), t ); /* else nothing unusual */
196: break;
197: case INREP: /* in a repeat */
198: if (c) /* if count is nonzero */
199: while(--c) /* then repeatedly ... */
200: putCHR( lastc, t ); /* ... output the byte */
201: else
202: putCHR( DLE, t ); /* else output DLE as data */
203: state = NOHIST; /* back to no history */
204: break;
205: default:
206: {
207: Error( badstate );
208: }
209: }
210: return(0);
211: }
212:
213:
214: /*--------------------------------------------------------------------------*/
215: /* LZSS Compression */
216: /*--------------------------------------------------------------------------*/
217:
218: #define buffSize 2048 /* size of ring buffer */
219: #define lookSize 60 /* lookahead buffer size */
220: #define THRESHOLD 2 /* if matchLen is greater than Threshold */
221: /* then code string into position & length */
222: #define treeRoot buffSize /* index for root of binary search tree */
223:
224: /*
225: ring buffer with extra bytes to facilitate string comparison of
226: longest match. This is set by the InsertNode() procedure.
227: */
228:
229: static unsigned char textBuf[ buffSize + lookSize - 1 ];
230: static int matchPos, matchLen;
231: static int lson[ buffSize + 1 ];
232: static int rson[ buffSize + 257 ];
233: static int dad [ buffSize + 1 ];
234:
235:
236: /*--------------------------------------------------------------------------*/
237: /* InitTree */
238: /* Initialize the LZSS trees. */
239: /*--------------------------------------------------------------------------*/
240:
241: static void InitTree( void )
242: {
243: register int i;
244:
245: /*
246: For i = 0 to buffSize, rson[i] and lson[i] will be the right and
247: left children of node i. These nodes need not be initialized. Also,
248: dad[i] is the parent of node i. These are initialized to "treeRoot"
249: which means 'not used.'
250:
251: For i = buffSize+1 to buffSize+256, rson[i] is the root of the tree
252: for strings that begin with character i. These are initialized
253: to "treeRoot". Note there are 256 trees.
254: */
255:
256: for (i = buffSize + 1 ; i <= (buffSize + 256) ; i++)
257: rson[i] = treeRoot; /* root */
258: for (i = 0 ; i < buffSize ; i++)
259: dad[i] = treeRoot; /* node */
260: }
261:
262:
263: /*--------------------------------------------------------------------------*/
264: /* InsertNode */
265: /* Inserts string of length lookSize, textBuf[r..r+lookSize-1], into */
266: /* one of the trees (textBuf[r]'th tree) and returns the longest-match */
267: /* position and length via the global variables matchPos and matchLen. */
268: /* If matchLen = lookSize, then remove the old node in favor of the new */
269: /* one, because the old one will be deleted sooner. Note r plays double */
270: /* role, as tree node and position in buffer. */
271: /*--------------------------------------------------------------------------*/
272:
273: static void InsertNode(int r)
274: {
275: int i, p, cmp;
276: unsigned char *key;
277: unsigned c;
278:
279: cmp = 1;
280: key = &textBuf[r];
281: p = buffSize + 1 + key[0];
282: rson[r] = lson[r] = treeRoot;
283: matchLen = 0;
284: for ( ; ; )
285: {
286: if (cmp >= 0)
287: {
288: if (rson[p] != treeRoot)
289: p = rson[p];
290: else
291: {
292: rson[p] = r;
293: dad [r] = p;
294: return;
295: }
296: }
297: else
298: {
299: if (lson[p] != treeRoot)
300: p = lson[p];
301: else
302: {
303: lson[p] = r;
304: dad [r] = p;
305: return;
306: }
307: }
308: for (i = 1; i < lookSize; i++)
309: if ((cmp = key[i] - textBuf[p + i]) != 0)
310: break;
311: if (i > THRESHOLD)
312: {
313: if (i > matchLen)
314: {
315: matchPos = ((r - p) & (buffSize - 1)) - 1;
316: if ((matchLen = i) >= lookSize)
317: break;
318: }
319: if (i == matchLen)
320: {
321: if ((c = ((r - p) & (buffSize - 1)) - 1) < matchPos)
322: {
323: matchPos = c;
324: }
325: }
326: }
327: }
328: dad[r] = dad[p];
329: lson[r] = lson[p];
330: rson[r] = rson[p];
331: dad[lson[p]] = r;
332: dad[rson[p]] = r;
333: if (rson[dad[p]] == p)
334: rson[dad[p]] = r;
335: else
336: lson[dad[p]] = r;
337: dad[p] = treeRoot; /* remove p */
338: }
339:
340:
341: /*--------------------------------------------------------------------------*/
342: /* DeleteNode */
343: /* Delete node p from the tree. */
344: /*--------------------------------------------------------------------------*/
345:
346: static void DeleteNode( register int p )
347: {
348: register int q;
349:
350: if (dad[p] == treeRoot)
351: return; /* not registered */
352: if (rson[p] == treeRoot)
353: q = lson[p];
354: else
355: if (lson[p] == treeRoot)
356: q = rson[p];
357: else
358: {
359: q = lson[p];
360: if (rson[q] != treeRoot)
361: {
362: do {
363: q = rson[q];
364: }
365: while (rson[q] != treeRoot);
366:
367: rson[dad[q]] = lson[q];
368: dad[lson[q]] = dad[q];
369: lson[q] = lson[p];
370: dad[lson[p]] = q;
371: }
372: rson[q] = rson[p];
373: dad[rson[p]] = q;
374: }
375: dad[q] = dad[p];
376:
377: if (rson[dad[p]] == p)
378: rson[dad[p]] = q;
379: else
380: lson[dad[p]] = q;
381: dad[p] = treeRoot;
382: }
383:
384: /*--------------------------------------------------------------------------*/
385: /* Huffman Coding */
386: /*--------------------------------------------------------------------------*/
387:
388: /* kinds of characters (character code = 0..N_CHAR-1) */
389: #define N_CHAR (256 - THRESHOLD + lookSize)
390: #define tableSize (N_CHAR * 2 - 1) /* size of table */
391: #define rootSize (tableSize - 1) /* position of root */
392: #define MAX_FREQ 0x8000 /* update the tree when the root */
393: /* frequency comes to this value. */
394:
395: /*--------------------------------------------------------------------------*/
396: /* Tables for encoding the upper 6 bits of position */
397: /*--------------------------------------------------------------------------*/
398:
399: static uchar p_len[64] =
400: {
401: 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
402: 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
403: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
404: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
405: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
406: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
407: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
408: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
409: };
410:
411: static uchar p_code[64] =
412: {
413: 0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
414: 0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
415: 0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
416: 0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
417: 0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
418: 0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
419: 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
420: 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
421: };
422:
423: /*--------------------------------------------------------------------------*/
424: /* Tables for decoding the upper 6 bits of position */
425: /*--------------------------------------------------------------------------*/
426:
427: static uchar d_code[256] =
428: {
429: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
430: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
431: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
432: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
433: 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
434: 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
435: 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
436: 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
437: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
438: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
439: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
440: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
441: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
442: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
443: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
444: 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
445: 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
446: 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
447: 0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
448: 0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
449: 0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
450: 0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
451: 0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
452: 0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
453: 0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
454: 0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
455: 0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
456: 0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
457: 0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
458: 0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
459: 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
460: 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
461: };
462:
463: static uchar d_len[256] =
464: {
465: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
466: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
467: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
468: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
469: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
470: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
471: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
472: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
473: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
474: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
475: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
476: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
477: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
478: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
479: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
480: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
481: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
482: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
483: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
484: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
485: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
486: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
487: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
488: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
489: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
490: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
491: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
492: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
493: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
494: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
495: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
496: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
497: };
498:
499: static unsigned freq[tableSize + 1]; /* frequency table */
500:
501: static int prnt[ tableSize + N_CHAR ];
502: /* pointers to parent nodes, except for the elements */
503: /* [tableSize..tableSize + N_CHAR - 1] which are used */
504: /* to get the positions of leaves corresponding to the */
505: /* codes. */
506:
507: static int son[ tableSize ]; /* pointers to child nodes (son[], son[] + 1) */
508:
509: static unsigned getbuf = 0;
510: static uchar getlen = 0;
511:
512:
513: /*--------------------------------------------------------------------------*/
514: /* GetBit */
515: /* Get one bit. */
516: /*--------------------------------------------------------------------------*/
517:
518: static int GetBit( void )
519: {
520: int i;
521:
522: while (getlen <= 8)
523: {
524: if ((i = getc( inFile )) < 0)
525: i = 0;
526: getbuf |= i << (8 - getlen);
527: getlen += 8;
528: }
529: i = getbuf;
530: getbuf <<= 1;
531: getlen--;
532: return (i < 0);
533: }
534:
535:
536: /*--------------------------------------------------------------------------*/
537: /* GetByte */
538: /* Get one byte. */
539: /*--------------------------------------------------------------------------*/
540:
541: static int GetByte( void )
542: {
543: unsigned i;
544:
545: while (getlen <= 8)
546: {
547: if ((i = getc( inFile )) < 0)
548: i = 0;
549: getbuf |= i << (8 - getlen);
550: getlen += 8;
551: }
552: i = getbuf;
553: getbuf <<= 8;
554: getlen -= 8;
555: return i >> 8;
556: }
557:
558:
559: /*--------------------------------------------------------------------------*/
560: /* Putcode */
561: /* Write c bits of code. */
562: /*--------------------------------------------------------------------------*/
563:
564: static unsigned putbuf = 0;
565: static uchar putlen = 0;
566:
567: static void Putcode(int l, unsigned c)
568: {
569: static char *werr = "lzh Putcode: can't write output file!";
570:
571: putbuf |= (c >> putlen);
572: if ((putlen += l) >= 8)
573: {
574: if (putc( putbuf >> 8, outFile ) == EOF)
575: {
576: Error( werr );
577: }
578: if ((putlen -= 8) >= 8)
579: {
580: if (putc( putbuf, outFile ) == EOF)
581: {
582: Error( werr );
583: }
584: codesize += 2;
585: putlen -= 8;
586: putbuf = c << (l - putlen);
587: }
588: else
589: {
590: putbuf <<= 8;
591: codesize++;
592: }
593: }
594: }
595:
596:
597: /*--------------------------------------------------------------------------*/
598: /* StartHuff */
599: /* initialize the Huffman trees. */
600: /*--------------------------------------------------------------------------*/
601:
602: static void StartHuff( void )
603: {
604: register int i, j;
605:
606: for (i = 0; i < N_CHAR; i++)
607: {
608: freq[i] = 1;
609: son[i] = i + tableSize;
610: prnt[i + tableSize] = i;
611: }
612: i = 0;
613: j = N_CHAR;
614:
615: while (j <= rootSize)
616: {
617: freq[j] = freq[i] + freq[i + 1];
618: son[j] = i;
619: prnt[i] = prnt[i + 1] = j;
620: i += 2;
621: j++;
622: }
623: freq[tableSize] = 0xffff;
624: prnt[rootSize] = 0;
625: }
626:
627:
628: /*--------------------------------------------------------------------------*/
629: /* reconst */
630: /* Reconstruction of tree. */
631: /*--------------------------------------------------------------------------*/
632:
633: static void reconst( void )
634: {
635: register int i, j, k;
636: unsigned int f, l;
637:
638: /* Collect leaf nodes in the first half of the table and replace the */
639: /* freq by (freq + 1) / 2. */
640:
641: j = 0;
642: for (i = 0; i < tableSize; i++)
643: {
644: if (son[i] >= tableSize)
645: {
646: freq[j] = (freq[i] + 1) / 2;
647: son[j] = son[i];
648: j++;
649: }
650: }
651:
652: /* begin constructing tree by connecting sons */
653:
654: for (i = 0, j = N_CHAR; j < tableSize; i += 2, j++)
655: {
656: k = i + 1;
657: f = freq[j] = freq[i] + freq[k];
658:
659: for (k = j - 1; f < freq[k]; k--);
660:
661: k++;
662: l = (j - k) * 2;
663: memmove( &freq[k + 1], &freq[k], l );
664: freq[k] = f;
665: memmove( &son[k + 1], &son[k], l );
666: son[k] = i;
667: }
668:
669: /* connect prnt */
670:
671: for (i = 0; i < tableSize; i++)
672: if ((k = son[i]) >= tableSize)
673: prnt[k] = i;
674: else
675: prnt[k] = prnt[k + 1] = i;
676: }
677:
678:
679: /*--------------------------------------------------------------------------*/
680: /* update */
681: /* Increment frequency of given code by one, and update tree. */
682: /*--------------------------------------------------------------------------*/
683:
684: static void update(int c)
685: {
686: int i, j, k, l;
687:
688: if (freq[rootSize] == MAX_FREQ)
689: reconst();
690:
691: c = prnt[c + tableSize];
692: do {
693: k = ++freq[c];
694:
695: /* if the order is disturbed, exchange nodes */
696: if (k > freq[l = c + 1])
697: {
698: while (k > freq[++l]);
699: l--;
700: freq[c] = freq[l];
701: freq[l] = k;
702:
703: i = son[c];
704: prnt[i] = l;
705: if (i < tableSize)
706: prnt[i + 1] = l;
707:
708: j = son[l];
709: son[l] = i;
710:
711: prnt[j] = c;
712: if (j < tableSize)
713: prnt[j + 1] = c;
714: son[c] = j;
715:
716: c = l;
717: }
718: }
719: while ((c = prnt[c]) != 0); /* repeat up to root */
720: }
721:
722:
723: /*--------------------------------------------------------------------------*/
724: /* EncodeChar */
725: /*--------------------------------------------------------------------------*/
726:
727: static void EncodeChar(unsigned c)
728: {
729: unsigned i;
730: int j, k;
731:
732: i = j = 0;
733: k = prnt[c + tableSize];
734:
735: /* travel from leaf to root */
736: do {
737: i >>= 1;
738:
739: /* if node's address is odd-numbered, choose bigger brother node */
740: if (k & 1) i += 0x8000;
741:
742: j++;
743: }
744: while ((k = prnt[k]) != rootSize);
745:
746: Putcode(j, i);
747: update(c);
748: }
749:
750:
751: /*--------------------------------------------------------------------------*/
752: /* EncodePosition */
753: /*--------------------------------------------------------------------------*/
754:
755: static void EncodePosition(unsigned c)
756: {
757: unsigned i;
758:
759: /* output upper 6 bits by table lookup */
760:
761: i = c >> 6;
762: Putcode( p_len[i], (unsigned)p_code[i] << 8 );
763:
764: /* output lower 6 bits verbatim */
765: Putcode( 6, (c & 0x3f) << 10 );
766: }
767:
768:
769: /*--------------------------------------------------------------------------*/
770: /* EncodeEnd */
771: /*--------------------------------------------------------------------------*/
772:
773: static void EncodeEnd( void )
774: {
775: static char *werr = "lzh EncodeEnd: can't write output file!";
776:
777: if (putlen)
778: {
779: if (putc(putbuf >> 8, outFile) == EOF)
780: Error( werr );
781: codesize++;
782: }
783: }
784:
785:
786: /*--------------------------------------------------------------------------*/
787: /* DecodeChar */
788: /*--------------------------------------------------------------------------*/
789:
790: static int DecodeChar( void )
791: {
792: register unsigned c;
793:
794: /* Travel from root to leaf choosing the smaller child node (son[]) if */
795: /* the read bit is 0, the bigger (son[]+1} if 1. */
796:
797: c = son[rootSize];
798: while (c < tableSize)
799: {
800: c += GetBit();
801: c = son[c];
802: }
803: c -= tableSize;
804: update(c);
805: return c;
806: }
807:
808:
809: /*--------------------------------------------------------------------------*/
810: /* DecodePosition */
811: /*--------------------------------------------------------------------------*/
812:
813: static int DecodePosition( void )
814: {
815: register unsigned i, j, c;
816:
817: /* recover upper 6 bits from table */
818: i = GetByte();
819: c = (unsigned)d_code[i] << 6;
820: j = d_len[i];
821:
822: /* read lower 6 bits verbatim */
823: j -= 2;
824: while (j--)
825: i = (i << 1) + GetBit();
826: return (c | (i & 0x3f));
827: }
828:
829:
830: /* lzhEncode
831: Compress the input file and write to the output file.
832: Return the ratio of output to input size.
833: */
834: int lzhEncode( FILE *in, FILE *out )
835: {
836: int i, c, len, r, s, last_matchLen;
837: unsigned long int textsize, beginByte;
838: static char *werr = "lzhEncode: can't write output file!";
839:
840: inFile = in; /* set the global file pointers */
841: outFile = out;
842:
843: /* Skip to the end of file and get the byte length. Write the length
844: as the first word in the compressed output file.
845: */
846: beginByte = ftell( inFile ); /* just in case we were prepositioned */
847: fseek( inFile, 0L, SEEK_END );
848: textsize = ftell( inFile ) - beginByte;
849: fseek( inFile, beginByte, SEEK_SET ); /* go back to the beginning of the file */
850:
851: if (textsize == 0)
852: return( -1 ); /* empty files are easy - signal an error */
853:
854: convert( textsize ); /* convert to little endian if necessary */
855:
856: if (fwrite( &textsize, sizeof textsize, 1, outFile ) < 1)
857: Error( werr );
858:
859: StartHuff(); /* init the Huffman trees */
860: InitTree(); /* init the LZSS trees */
861: inCount = 0; /* init the input character count */
862: s = 0;
863: r = buffSize - lookSize;
864: for (i = 0; i < r; i++)
865: textBuf[i] = ' ';
866:
867: /* fill the look ahead buffer */
868:
869: for (len = 0; (len < lookSize) && ((c = getRLC( inFile )) != EOF); len++)
870: textBuf[r + len] = c;
871: for (i = 1; i <= lookSize; i++)
872: InsertNode( r - i );
873: InsertNode( r );
874: do {
875: if (matchLen > len)
876: matchLen = len;
877: if (matchLen <= THRESHOLD)
878: {
879: matchLen = 1;
880: EncodeChar( textBuf[r] );
881: }
882: else
883: {
884: EncodeChar( 255 - THRESHOLD + matchLen );
885: EncodePosition( matchPos );
886: }
887: last_matchLen = matchLen;
888: for (i = 0; (i < last_matchLen) && ((c = getRLC( inFile )) != EOF); i++)
889: {
890: DeleteNode( s );
891: textBuf[s] = c;
892: if (s < lookSize - 1)
893: textBuf[s + buffSize] = c;
894: s = (s + 1) & (buffSize - 1);
895: r = (r + 1) & (buffSize - 1);
896: InsertNode( r );
897: }
898:
899: while (i++ < last_matchLen)
900: {
901: DeleteNode( s );
902: s = (s + 1) & (buffSize - 1);
903: r = (r + 1) & (buffSize - 1);
904: if (--len)
905: InsertNode( r );
906: }
907: }
908: while (len > 0);
909:
910: EncodeEnd();
911:
912: return( (int)((codesize * 10) / inCount ));
913: }
914:
915:
916: /*--------------------------------------------------------------------------*/
917: /* lzhDecode */
918: /*--------------------------------------------------------------------------*/
919:
920: void lzhDecode( FILE *in, FILE *out )
921: {
922: int i, j, k, r, c;
923: unsigned long int textsize;
924: static char *werr = "lzhDecode: can't write output file!";
925:
926: inFile = in; /* set the global file pointers */
927: outFile = out;
928:
929: /* get the size of the input file in the first word */
930:
931: if (fread( &textsize, sizeof textsize, 1, inFile ) < 1)
932: Error( "lzhDecode: Can't read the input file" );
933:
934: convert( textsize ); /* convert to little endian if necessary */
935: if (textsize == 0)
936: return; /* nothing to decode, empty file */
937:
938: StartHuff();
939: for (i = 0; i < (buffSize - lookSize); i++)
940: textBuf[i] = ' ';
941: r = buffSize - lookSize;
942:
943: outCount = 0; /* init the output character count */
944: while (outCount < textsize )
945: {
946: c = DecodeChar();
947: if (c < 256)
948: {
949: if (putRLC( c, outFile ) == EOF)
950: Error( werr );
951:
952: textBuf[r++] = c;
953: r &= (buffSize - 1);
954: }
955: else
956: {
957: i = (r - DecodePosition() - 1) & (buffSize - 1);
958: j = c - 255 + THRESHOLD;
959: for (k = 0; k < j; k++)
960: {
961: c = textBuf[(i + k) & (buffSize - 1)];
962: if (putRLC( c, outFile ) == EOF)
963: Error( werr );
964: textBuf[r++] = c;
965: r &= (buffSize - 1);
966: }
967: }
968: }
969: }
970:
971: /* ---- end of lzh.c */
972:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.