-
Notifications
You must be signed in to change notification settings - Fork 1
/
lzd.c
224 lines (191 loc) · 5.86 KB
/
lzd.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
/*
Lempel-Ziv decompression. Mostly based on Tom Pfau's assembly language
code.
This file is public domain.
-- Rahul Dhesi 1991/07/07
*/
#include "booz.h"
#include <stdio.h>
/* must fit in MEM_BLOCK_SIZE */
#define OUT_BUF_SIZE 4096
#define IN_BUF_SIZE 4096
#define STACKSIZE 2000
#define INBUFSIZ (IN_BUF_SIZE - SPARE)
#define OUTBUFSIZ (OUT_BUF_SIZE - SPARE)
#define MEMERR 2
#define IOERR 1
#define MAXBITS 13
#define CLEAR 256 /* clear code */
#define Z_EOF 257 /* end of file marker */
#define FIRST_FREE 258 /* first free code */
#define MAXMAX 8192 /* max code + 1 */
#define SPARE 4
char out_buf_adr[MEM_BLOCK_SIZE];
#define in_buf_adr (&out_buf_adr[OUT_BUF_SIZE])
struct tabentry {
unsigned next;
char z_ch;
};
static struct tabentry *table;
static int gotmem = 0;
static int init_dtab();
static unsigned rd_dcode();
static int wr_dchar();
static int ad_dcode();
static unsigned lzd_sp = 0;
static unsigned lzd_stack[STACKSIZE + SPARE];
static int push(ch)
int ch;
{
lzd_stack[lzd_sp++] = ch;
if (lzd_sp >= STACKSIZE)
prterror ('f', "Stack overflow in lzd()\n", (char *) 0, (char *) 0);
}
#define pop() (lzd_stack[--lzd_sp])
unsigned cur_code;
unsigned old_code;
unsigned in_code;
unsigned free_code;
int nbits;
unsigned max_code;
char fin_char;
char k;
unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
unsigned bit_offset;
unsigned output_offset;
static FILE *in_file;
static FILE *out_file;
int lzd(input_file, output_file)
FILE *input_file, *output_file; /* input & output file handles */
{
in_file = input_file; /* make it avail to other fns */
out_file = output_file; /* ditto */
nbits = 9;
max_code = 512;
free_code = FIRST_FREE;
lzd_sp = 0;
bit_offset = 0;
output_offset = 0;
if (gotmem == 0) {
table = (struct tabentry *)
malloc (MAXMAX * sizeof (struct tabentry) + SPARE);
gotmem++;
}
if (table == (struct tabentry *) 0)
memerr();
fread(in_buf_adr, 1, INBUFSIZ, in_file);
if (ferror(in_file))
return(IOERR);
init_dtab(); /* initialize table */
loop:
cur_code = rd_dcode();
if (cur_code == Z_EOF) {
if (output_offset != 0) {
if (out_file != NULL) {
if (fwrite(out_buf_adr, 1, output_offset, out_file) != output_offset)
prterror ('f', "Output error in lzd()\n",
(char *) 0, (char *) 0);
}
addbfcrc(out_buf_adr, output_offset);
}
return (0);
}
if (cur_code == CLEAR) {
init_dtab();
fin_char = k = old_code = cur_code = rd_dcode();
wr_dchar((int) k);
goto loop;
}
in_code = cur_code;
if (cur_code >= free_code) { /* if code not in table (k<w>k<w>k) */
cur_code = old_code; /* previous code becomes current */
push(fin_char);
}
while (cur_code > 255) { /* if code, not character */
push(table[cur_code].z_ch); /* push suffix char */
cur_code = table[cur_code].next; /* <w> := <w>.code */
}
k = fin_char = cur_code;
push(k);
while (lzd_sp != 0) {
wr_dchar((int) pop());
}
ad_dcode();
old_code = in_code;
goto loop;
} /* lzd() */
/* rd_dcode() reads a code from the input (compressed) file and returns
its value. */
static unsigned rd_dcode()
{
register char *ptra, *ptrb; /* miscellaneous pointers */
unsigned word; /* first 16 bits in buffer */
unsigned byte_offset;
char nextch; /* next 8 bits in buffer */
unsigned ofs_inbyte; /* offset within byte */
ofs_inbyte = bit_offset % 8;
byte_offset = bit_offset / 8;
bit_offset = bit_offset + nbits;
if (byte_offset >= INBUFSIZ - 5) {
int space_left;
bit_offset = ofs_inbyte + nbits;
space_left = INBUFSIZ - byte_offset;
ptrb = byte_offset + in_buf_adr; /* point to char */
ptra = in_buf_adr;
/* we now move the remaining characters down buffer beginning */
while (space_left > 0) {
*ptra++ = *ptrb++;
space_left--;
}
fread(ptra, 1, byte_offset, in_file);
if (ferror(in_file))
prterror ('f', "Input error in lzd:rd_dcode\n",
(char *) 0, (char *) 0);
byte_offset = 0;
}
ptra = byte_offset + in_buf_adr;
/* NOTE: "word = *((int *) ptra)" would not be independent of byte order. */
word = (unsigned char) *ptra; ptra++;
word = word | ((unsigned char) *ptra) << 8; ptra++;
nextch = *ptra;
if (ofs_inbyte != 0) {
/* shift nextch right by ofs_inbyte bits */
/* and shift those bits right into word; */
word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
}
return (word & masks[nbits]);
} /* rd_dcode() */
static int init_dtab()
{
nbits = 9;
max_code = 512;
free_code = FIRST_FREE;
}
static int wr_dchar (ch)
int ch;
{
if (output_offset >= OUTBUFSIZ) { /* if buffer full */
if (out_file != NULL) {
if (fwrite(out_buf_adr, 1, output_offset, out_file) != output_offset)
prterror ('f', "Write error in lzd:wr_dchar\n",
(char *) 0, (char *) 0);
}
addbfcrc(out_buf_adr, output_offset); /* update CRC */
output_offset = 0; /* restore empty buffer */
}
out_buf_adr[output_offset++] = ch; /* store character */
} /* wr_dchar() */
/* adds a code to table */
static int ad_dcode()
{
table[free_code].z_ch = k; /* save suffix char */
table[free_code].next = old_code; /* save prefix code */
free_code++;
if (free_code >= max_code) {
if (nbits < MAXBITS) {
nbits++;
max_code = max_code << 1; /* double max_code */
}
}
}