1 /*
2 * Copyright (C) 2013-2022 Cisco Systems, Inc. and/or its affiliates. All rights reserved.
3 * Copyright (C) 2008-2013 Sourcefire, Inc.
4 *
5 * Authors: Alberto Wu
6 *
7 * Acknowledgements: Written from scratch based on specs from PKWARE:
8 * http://www.pkware.com/documents/casestudies/APPNOTE.TXT
9 *
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License version 2 as
12 * published by the Free Software Foundation.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
22 * MA 02110-1301, USA.
23 */
24
25 /*
26 * Written from scratch based on specs from PKWARE:
27 * see www.pkware.com/documents/casestudies/APPNOTE.TXT
28 *
29 * To the best of my knowledge, it's patent free:
30 * http://www.unisys.com/about__unisys/lzw
31 */
32
33 /* To Cami and Dario, the only lawyers I can stand */
34
35 #if HAVE_CONFIG_H
36 #include "clamav-config.h"
37 #endif
38
39 #if HAVE_STRING_H
40 #include <string.h>
41 #endif
42
43 #include "clamav.h"
44 #include "explode.h"
45 #include "others.h"
46
47 /* NOTE: sorting algo must be stable! */
bs(uint8_t * k,uint8_t * v,unsigned int elements)48 static void bs(uint8_t *k, uint8_t *v, unsigned int elements)
49 {
50 uint8_t tmp;
51 unsigned int i = 0, l = 0, stop = 0, r = elements;
52
53 while (!stop) {
54 stop = 1;
55 for (; i < r; i++) {
56 if (v[k[i]] > v[k[i + 1]]) {
57 tmp = k[i];
58 k[i] = k[i + 1];
59 k[i + 1] = tmp;
60 stop = 0;
61 }
62 }
63 if (stop) break;
64 r--;
65 i--;
66 for (; i > l; i--) {
67 if (v[k[i]] < v[k[i - 1]]) {
68 tmp = k[i];
69 k[i] = k[i - 1];
70 k[i - 1] = tmp;
71 stop = 0;
72 }
73 }
74 l++;
75 i++;
76 }
77 }
78
unpack_tree(struct xplstate * X,uint32_t * tree,unsigned int expected)79 static int unpack_tree(struct xplstate *X, uint32_t *tree, unsigned int expected)
80 {
81 uint8_t temptree[256], order[256], *ttree = temptree;
82 uint8_t *cur = X->window;
83 uint8_t packsz;
84 unsigned int i;
85 uint16_t code = 0, codeinc = 0, lastlen = 0;
86
87 packsz = *cur++;
88
89 for (i = 0; i < expected; i++) order[i] = i;
90
91 i = expected;
92
93 do {
94 uint8_t values, len;
95 values = *cur++;
96 len = (values & 15) + 1;
97 values = (values >> 4) + 1;
98 if (values > i) return 1;
99 i -= values;
100 while (values--)
101 *ttree++ = len;
102 } while (packsz--);
103
104 if (i) return 1;
105
106 bs(order, temptree, expected - 1);
107
108 i = expected - 1;
109 do {
110 code = code + codeinc;
111 if (temptree[order[i]] != lastlen) {
112 lastlen = temptree[order[i]];
113 codeinc = 1 << (16 - lastlen);
114 }
115 tree[order[i]] = code | ((uint32_t)lastlen << 16);
116 } while (i--);
117
118 return 0;
119 }
120
121 /* bit lame of a lookup, but prolly not worth optimizing */
lookup_tree(uint32_t * tree,unsigned int size,uint16_t code,uint8_t len)122 static int lookup_tree(uint32_t *tree, unsigned int size, uint16_t code, uint8_t len)
123 {
124 uint32_t lookup = ((uint32_t)(len + 1)) << 16 | code;
125 unsigned int i;
126 for (i = 0; i < size; i++)
127 if (tree[i] == lookup) return i;
128 return -1;
129 }
130
explode_init(struct xplstate * X,uint16_t flags)131 int explode_init(struct xplstate *X, uint16_t flags)
132 {
133 X->bits = X->cur = 0;
134 if (flags & 2) {
135 X->largewin = 1;
136 X->mask = 0x1fff;
137 } else {
138 X->largewin = 0;
139 X->mask = 0xfff;
140 }
141 if (flags & 4) {
142 X->state = GRABLITS;
143 X->litcodes = 1;
144 X->minlen = 3;
145 } else {
146 X->state = GRABLENS;
147 X->litcodes = 0;
148 X->minlen = 2;
149 }
150 X->got = 0;
151 return EXPLODE_OK;
152 }
153
154 #define GETBIT \
155 if (X->bits) { \
156 X->bits--; \
157 val = X->bitmap & 1; \
158 X->bitmap >>= 1; \
159 } else { \
160 if (!X->avail_in) return EXPLODE_EBUFF; \
161 if (X->avail_in >= 4) { \
162 X->bitmap = cli_readint32(X->next_in); \
163 X->bits = 31; \
164 X->next_in += 4; \
165 X->avail_in -= 4; \
166 } else { \
167 X->bitmap = *X->next_in; \
168 X->bits = 7; \
169 X->next_in++; \
170 X->avail_in--; \
171 } \
172 val = X->bitmap & 1; \
173 X->bitmap >>= 1; \
174 }
175
176 #define GETBITS(NUM) \
177 if (X->bits >= (NUM)) { \
178 val = X->bitmap & ((1 << (NUM)) - 1); \
179 X->bitmap >>= (NUM); \
180 X->bits -= (NUM); \
181 } else { \
182 if (X->avail_in * 8 + X->bits < (NUM)) return EXPLODE_EBUFF; \
183 val = X->bitmap; \
184 if (X->avail_in >= 4) { \
185 X->bitmap = cli_readint32(X->next_in); \
186 X->next_in += 4; \
187 X->avail_in -= 4; \
188 val |= (X->bitmap & ((1 << ((NUM)-X->bits)) - 1)) << X->bits; \
189 X->bitmap >>= (NUM)-X->bits; \
190 X->bits = 32 - ((NUM)-X->bits); \
191 } else { \
192 X->bitmap = *X->next_in; \
193 X->next_in++; \
194 X->avail_in--; \
195 val |= (X->bitmap & ((1 << ((NUM)-X->bits)) - 1)) << X->bits; \
196 X->bitmap >>= (NUM)-X->bits; \
197 X->bits = 8 - ((NUM)-X->bits); \
198 } \
199 }
200
201 #define GETCODES(CASE, WHICH, HOWMANY) \
202 case CASE: { \
203 if (!X->avail_in) return EXPLODE_EBUFF; \
204 if (!X->got) \
205 need = *X->next_in; \
206 else \
207 need = X->window[0]; \
208 if (need > HOWMANY - 1) return EXPLODE_ESTREAM; /* too many codes */ \
209 need = need + 2 - X->got; /* bytes remaining */ \
210 if (need > X->avail_in) { /* if not enuff */ \
211 /* just copy what's avail... */ \
212 memcpy(&X->window[X->got], X->next_in, X->avail_in); \
213 X->got += X->avail_in; \
214 X->next_in += X->avail_in; \
215 X->avail_in = 0; \
216 return EXPLODE_EBUFF; /* ...and beg for more */ \
217 } \
218 /* else fetch what's needed */ \
219 memcpy(&X->window[X->got], X->next_in, need); \
220 X->avail_in -= need; \
221 X->next_in += need; \
222 if (unpack_tree(X, X->WHICH, HOWMANY)) return EXPLODE_ESTREAM; \
223 /* and move on */ \
224 X->got = 0; \
225 X->state++; \
226 }
227
228 #define SETCASE(CASE) \
229 X->state = (CASE); \
230 case (CASE): { /* FAKE */ \
231 }
232
explode(struct xplstate * X)233 int explode(struct xplstate *X)
234 {
235 unsigned int val, need;
236 int temp = -1;
237
238 switch (X->state) {
239 /* grab compressed coded literals, if present */
240 GETCODES(GRABLITS, lit_tree, 256);
241 /* grab compressed coded lens */
242 GETCODES(GRABLENS, len_tree, 64);
243 /* grab compressed coded dists */
244 GETCODES(GRABDISTS, dist_tree, 64);
245
246 case EXPLODE:
247 while (X->avail_in || X->bits) {
248 GETBIT; /* can't fail */
249 if (val) {
250 if (X->litcodes) {
251 X->backsize = 0;
252 X->state = EXPLODE_LITCODES;
253 for (X->got = 0; X->got <= 15; X->got++) {
254 case EXPLODE_LITCODES:
255 GETBIT;
256 X->backsize |= val << (15 - X->got);
257 if ((temp = lookup_tree(X->lit_tree, 256, X->backsize, X->got)) != -1) break;
258 }
259 if (temp == -1) return EXPLODE_ESTREAM;
260 X->got = temp;
261 } else {
262 SETCASE(EXPLODE_LITS);
263 GETBITS(8);
264 X->got = val;
265 }
266 SETCASE(EXPLODE_WBYTE);
267 if (!X->avail_out) return EXPLODE_EBUFF;
268 X->avail_out--;
269 *X->next_out = X->window[X->cur & X->mask] = X->got;
270 X->cur++;
271 X->next_out++;
272 } else {
273 SETCASE(EXPLODE_BASEDIST);
274 GETBITS(6u + X->largewin);
275 X->backbytes = val;
276 X->backsize = 0;
277 X->state = EXPLODE_DECODEDISTS;
278 for (X->got = 0; X->got <= 15; X->got++) {
279 case EXPLODE_DECODEDISTS:
280 GETBIT;
281 X->backsize |= val << (15 - X->got);
282 if ((temp = lookup_tree(X->dist_tree, 64, X->backsize, X->got)) != -1) break;
283 }
284 if (temp == -1) return EXPLODE_ESTREAM;
285 X->backbytes |= temp << (6 + X->largewin);
286 X->backbytes++;
287 X->backsize = 0;
288 X->state = EXPLODE_DECODELENS;
289 for (X->got = 0; X->got <= 15; X->got++) {
290 case EXPLODE_DECODELENS:
291 GETBIT;
292 X->backsize |= val << (15 - X->got);
293 if ((temp = lookup_tree(X->len_tree, 64, X->backsize, X->got)) != -1) break;
294 }
295 if (temp == -1) return EXPLODE_ESTREAM;
296
297 if (temp == 63) {
298 SETCASE(EXPLODE_DECODEEXTRA);
299 GETBITS(8);
300 temp = 63 + val;
301 }
302 X->backsize = temp + X->minlen;
303 X->state = EXPLODE_BACKCOPY;
304 while (X->backsize--) {
305 case EXPLODE_BACKCOPY:
306 if (!X->avail_out) return EXPLODE_EBUFF;
307 X->avail_out--;
308 if (X->cur >= X->backbytes)
309 *X->next_out = X->window[X->cur & X->mask] = X->window[(X->cur - X->backbytes) & X->mask];
310 else
311 *X->next_out = X->window[X->cur & X->mask] = 0;
312 X->cur++;
313 X->next_out++;
314 }
315 }
316 X->state = EXPLODE;
317 }
318 }
319 return EXPLODE_EBUFF;
320 }
321
explode_shutdown(void)322 void explode_shutdown(void) {}
323