Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4680 | right-hear | 1 | #include "fitz.h" |
2 | |||
3 | /* TODO: error checking */ |
||
4 | |||
5 | enum |
||
6 | { |
||
7 | MIN_BITS = 9, |
||
8 | MAX_BITS = 12, |
||
9 | NUM_CODES = (1 << MAX_BITS), |
||
10 | LZW_CLEAR = 256, |
||
11 | LZW_EOD = 257, |
||
12 | LZW_FIRST = 258, |
||
13 | MAX_LENGTH = 4097 |
||
14 | }; |
||
15 | |||
16 | typedef struct lzw_code_s lzw_code; |
||
17 | |||
18 | struct lzw_code_s |
||
19 | { |
||
20 | int prev; /* prev code (in string) */ |
||
21 | unsigned short length; /* string len, including this token */ |
||
22 | unsigned char value; /* data value */ |
||
23 | unsigned char first_char; /* first token of string */ |
||
24 | }; |
||
25 | |||
26 | typedef struct fz_lzwd_s fz_lzwd; |
||
27 | |||
28 | struct fz_lzwd_s |
||
29 | { |
||
30 | fz_stream *chain; |
||
31 | int eod; |
||
32 | |||
33 | int early_change; |
||
34 | |||
35 | int code_bits; /* num bits/code */ |
||
36 | int code; /* current code */ |
||
37 | int old_code; /* previously recognized code */ |
||
38 | int next_code; /* next free entry */ |
||
39 | |||
40 | lzw_code table[NUM_CODES]; |
||
41 | |||
42 | unsigned char bp[MAX_LENGTH]; |
||
43 | unsigned char *rp, *wp; |
||
44 | }; |
||
45 | |||
46 | static int |
||
47 | read_lzwd(fz_stream *stm, unsigned char *buf, int len) |
||
48 | { |
||
49 | fz_lzwd *lzw = stm->state; |
||
50 | lzw_code *table = lzw->table; |
||
51 | unsigned char *p = buf; |
||
52 | unsigned char *ep = buf + len; |
||
53 | unsigned char *s; |
||
54 | int codelen; |
||
55 | |||
56 | int code_bits = lzw->code_bits; |
||
57 | int code = lzw->code; |
||
58 | int old_code = lzw->old_code; |
||
59 | int next_code = lzw->next_code; |
||
60 | |||
61 | while (lzw->rp < lzw->wp && p < ep) |
||
62 | *p++ = *lzw->rp++; |
||
63 | |||
64 | while (p < ep) |
||
65 | { |
||
66 | if (lzw->eod) |
||
67 | return 0; |
||
68 | |||
69 | code = fz_read_bits(lzw->chain, code_bits); |
||
70 | |||
71 | if (fz_is_eof_bits(lzw->chain)) |
||
72 | { |
||
73 | lzw->eod = 1; |
||
74 | break; |
||
75 | } |
||
76 | |||
77 | if (code == LZW_EOD) |
||
78 | { |
||
79 | lzw->eod = 1; |
||
80 | break; |
||
81 | } |
||
82 | |||
83 | if (code == LZW_CLEAR) |
||
84 | { |
||
85 | code_bits = MIN_BITS; |
||
86 | next_code = LZW_FIRST; |
||
87 | old_code = -1; |
||
88 | continue; |
||
89 | } |
||
90 | |||
91 | /* if stream starts without a clear code, old_code is undefined... */ |
||
92 | if (old_code == -1) |
||
93 | { |
||
94 | old_code = code; |
||
95 | } |
||
96 | else |
||
97 | { |
||
98 | /* add new entry to the code table */ |
||
99 | table[next_code].prev = old_code; |
||
100 | table[next_code].first_char = table[old_code].first_char; |
||
101 | table[next_code].length = table[old_code].length + 1; |
||
102 | if (code < next_code) |
||
103 | table[next_code].value = table[code].first_char; |
||
104 | else if (code == next_code) |
||
105 | table[next_code].value = table[next_code].first_char; |
||
106 | else |
||
107 | fz_warn("out of range code encountered in lzw decode"); |
||
108 | |||
109 | next_code ++; |
||
110 | |||
111 | if (next_code > (1 << code_bits) - lzw->early_change - 1) |
||
112 | { |
||
113 | code_bits ++; |
||
114 | if (code_bits > MAX_BITS) |
||
115 | code_bits = MAX_BITS; /* FIXME */ |
||
116 | } |
||
117 | |||
118 | old_code = code; |
||
119 | } |
||
120 | |||
121 | /* code maps to a string, copy to output (in reverse...) */ |
||
122 | if (code > 255) |
||
123 | { |
||
124 | codelen = table[code].length; |
||
125 | lzw->rp = lzw->bp; |
||
126 | lzw->wp = lzw->bp + codelen; |
||
127 | |||
128 | assert(codelen < MAX_LENGTH); |
||
129 | |||
130 | s = lzw->wp; |
||
131 | do { |
||
132 | *(--s) = table[code].value; |
||
133 | code = table[code].prev; |
||
134 | } while (code >= 0 && s > lzw->bp); |
||
135 | } |
||
136 | |||
137 | /* ... or just a single character */ |
||
138 | else |
||
139 | { |
||
140 | lzw->bp[0] = code; |
||
141 | lzw->rp = lzw->bp; |
||
142 | lzw->wp = lzw->bp + 1; |
||
143 | } |
||
144 | |||
145 | /* copy to output */ |
||
146 | while (lzw->rp < lzw->wp && p < ep) |
||
147 | *p++ = *lzw->rp++; |
||
148 | } |
||
149 | |||
150 | lzw->code_bits = code_bits; |
||
151 | lzw->code = code; |
||
152 | lzw->old_code = old_code; |
||
153 | lzw->next_code = next_code; |
||
154 | |||
155 | return p - buf; |
||
156 | } |
||
157 | |||
158 | static void |
||
159 | close_lzwd(fz_stream *stm) |
||
160 | { |
||
161 | fz_lzwd *lzw = stm->state; |
||
162 | fz_close(lzw->chain); |
||
163 | fz_free(lzw); |
||
164 | } |
||
165 | |||
166 | fz_stream * |
||
167 | fz_open_lzwd(fz_stream *chain, fz_obj *params) |
||
168 | { |
||
169 | fz_lzwd *lzw; |
||
170 | fz_obj *obj; |
||
171 | int i; |
||
172 | |||
173 | lzw = fz_malloc(sizeof(fz_lzwd)); |
||
174 | lzw->chain = chain; |
||
175 | lzw->eod = 0; |
||
176 | lzw->early_change = 1; |
||
177 | |||
178 | obj = fz_dict_gets(params, "EarlyChange"); |
||
179 | if (obj) |
||
180 | lzw->early_change = !!fz_to_int(obj); |
||
181 | |||
182 | for (i = 0; i < 256; i++) |
||
183 | { |
||
184 | lzw->table[i].value = i; |
||
185 | lzw->table[i].first_char = i; |
||
186 | lzw->table[i].length = 1; |
||
187 | lzw->table[i].prev = -1; |
||
188 | } |
||
189 | |||
190 | for (i = 256; i < NUM_CODES; i++) |
||
191 | { |
||
192 | lzw->table[i].value = 0; |
||
193 | lzw->table[i].first_char = 0; |
||
194 | lzw->table[i].length = 0; |
||
195 | lzw->table[i].prev = -1; |
||
196 | } |
||
197 | |||
198 | lzw->code_bits = MIN_BITS; |
||
199 | lzw->code = -1; |
||
200 | lzw->next_code = LZW_FIRST; |
||
201 | lzw->old_code = -1; |
||
202 | lzw->rp = lzw->bp; |
||
203 | lzw->wp = lzw->bp; |
||
204 | |||
205 | return fz_new_stream(lzw, read_lzwd, close_lzwd); |
||
206 | }>>>>>><>>>>>><> |