1 /*
2 FastLZ - lightning-fast lossless compression library
3
4 Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
5 Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
6 Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
7
8 Permission is hereby granted, free of charge, to any person obtaining a copy
9 of this software and associated documentation files (the "Software"), to deal
10 in the Software without restriction, including without limitation the rights
11 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 copies of the Software, and to permit persons to whom the Software is
13 furnished to do so, subject to the following conditions:
14
15 The above copyright notice and this permission notice shall be included in
16 all copies or substantial portions of the Software.
17
18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24 THE SOFTWARE.
25 */
26 #include <sys/cdefs.h>
27 #include "osdep.h"
28 #include "cudbg.h"
29 #include "cudbg_lib_common.h"
30 #include "fastlz.h"
31
32 static unsigned char sixpack_magic[8] = {137, '6', 'P', 'K', 13, 10, 26, 10};
33
34 #define CUDBG_BLOCK_SIZE (63*1024)
35 #define CUDBG_CHUNK_BUF_LEN 16
36 #define CUDBG_MIN_COMPR_LEN 32 /*min data length for applying compression*/
37
38 /* for Adler-32 checksum algorithm, see RFC 1950 Section 8.2 */
39
40 #define ADLER32_BASE 65521
41
update_adler32(unsigned long checksum,const void * buf,int len)42 static inline unsigned long update_adler32(unsigned long checksum,
43 const void *buf, int len)
44 {
45 const unsigned char *ptr = (const unsigned char *)buf;
46 unsigned long s1 = checksum & 0xffff;
47 unsigned long s2 = (checksum >> 16) & 0xffff;
48
49 while (len > 0) {
50 unsigned k = len < 5552 ? len : 5552;
51 len -= k;
52
53 while (k >= 8) {
54 s1 += *ptr++; s2 += s1;
55 s1 += *ptr++; s2 += s1;
56 s1 += *ptr++; s2 += s1;
57 s1 += *ptr++; s2 += s1;
58 s1 += *ptr++; s2 += s1;
59 s1 += *ptr++; s2 += s1;
60 s1 += *ptr++; s2 += s1;
61 s1 += *ptr++; s2 += s1;
62 k -= 8;
63 }
64
65 while (k-- > 0) {
66 s1 += *ptr++; s2 += s1;
67 }
68 s1 = s1 % ADLER32_BASE;
69 s2 = s2 % ADLER32_BASE;
70 }
71 return (s2 << 16) + s1;
72 }
73
write_magic(struct cudbg_buffer * _out_buff)74 int write_magic(struct cudbg_buffer *_out_buff)
75 {
76 int rc;
77
78 rc = write_to_buf(_out_buff->data, _out_buff->size, &_out_buff->offset,
79 sixpack_magic, 8);
80
81 return rc;
82 }
83
write_to_buf(void * out_buf,u32 out_buf_size,u32 * offset,void * in_buf,u32 in_buf_size)84 int write_to_buf(void *out_buf, u32 out_buf_size, u32 *offset, void *in_buf,
85 u32 in_buf_size)
86 {
87 int rc = 0;
88
89 if (*offset >= out_buf_size) {
90 rc = CUDBG_STATUS_OUTBUFF_OVERFLOW;
91 goto err;
92 }
93
94 memcpy((char *)out_buf + *offset, in_buf, in_buf_size);
95 *offset = *offset + in_buf_size;
96
97 err:
98 return rc;
99 }
100
read_from_buf(void * in_buf,u32 in_buf_size,u32 * offset,void * out_buf,u32 out_buf_size)101 int read_from_buf(void *in_buf, u32 in_buf_size, u32 *offset, void *out_buf,
102 u32 out_buf_size)
103 {
104 if (in_buf_size - *offset < out_buf_size)
105 return 0;
106
107 memcpy((char *)out_buf, (char *)in_buf + *offset, out_buf_size);
108 *offset = *offset + out_buf_size;
109 return out_buf_size;
110 }
111
write_chunk_header(struct cudbg_buffer * _outbuf,int id,int options,unsigned long size,unsigned long checksum,unsigned long extra)112 int write_chunk_header(struct cudbg_buffer *_outbuf, int id, int options,
113 unsigned long size, unsigned long checksum,
114 unsigned long extra)
115 {
116 unsigned char buffer[CUDBG_CHUNK_BUF_LEN];
117 int rc = 0;
118
119 buffer[0] = id & 255;
120 buffer[1] = (unsigned char)(id >> 8);
121 buffer[2] = options & 255;
122 buffer[3] = (unsigned char)(options >> 8);
123 buffer[4] = size & 255;
124 buffer[5] = (size >> 8) & 255;
125 buffer[6] = (size >> 16) & 255;
126 buffer[7] = (size >> 24) & 255;
127 buffer[8] = checksum & 255;
128 buffer[9] = (checksum >> 8) & 255;
129 buffer[10] = (checksum >> 16) & 255;
130 buffer[11] = (checksum >> 24) & 255;
131 buffer[12] = extra & 255;
132 buffer[13] = (extra >> 8) & 255;
133 buffer[14] = (extra >> 16) & 255;
134 buffer[15] = (extra >> 24) & 255;
135
136 rc = write_to_buf(_outbuf->data, _outbuf->size, &_outbuf->offset,
137 buffer, 16);
138
139 return rc;
140 }
141
write_compression_hdr(struct cudbg_buffer * pin_buff,struct cudbg_buffer * pout_buff)142 int write_compression_hdr(struct cudbg_buffer *pin_buff,
143 struct cudbg_buffer *pout_buff)
144 {
145 struct cudbg_buffer tmp_buffer;
146 unsigned long fsize = pin_buff->size;
147 unsigned char *buffer;
148 unsigned long checksum;
149 int rc;
150 char *shown_name = "abc";
151
152 /* Always release inner scratch buffer, before releasing outer. */
153 rc = get_scratch_buff(pout_buff, 10, &tmp_buffer);
154
155 if (rc)
156 goto err;
157
158 buffer = (unsigned char *)tmp_buffer.data;
159
160 rc = write_magic(pout_buff);
161
162 if (rc)
163 goto err1;
164
165 /* chunk for File Entry */
166 buffer[0] = fsize & 255;
167 buffer[1] = (fsize >> 8) & 255;
168 buffer[2] = (fsize >> 16) & 255;
169 buffer[3] = (fsize >> 24) & 255;
170 buffer[4] = 0;
171 buffer[5] = 0;
172 buffer[6] = 0;
173 buffer[7] = 0;
174 buffer[8] = (strlen(shown_name)+1) & 255;
175 buffer[9] = (unsigned char)((strlen(shown_name)+1) >> 8);
176 checksum = 1L;
177 checksum = update_adler32(checksum, buffer, 10);
178 checksum = update_adler32(checksum, shown_name,
179 (int)strlen(shown_name)+1);
180
181 rc = write_chunk_header(pout_buff, 1, 0,
182 10+(unsigned long)strlen(shown_name)+1,
183 checksum, 0);
184
185 if (rc)
186 goto err1;
187
188 rc = write_to_buf(pout_buff->data, pout_buff->size,
189 &(pout_buff->offset), buffer, 10);
190
191 if (rc)
192 goto err1;
193
194 rc = write_to_buf(pout_buff->data, pout_buff->size,
195 &(pout_buff->offset), shown_name,
196 (u32)strlen(shown_name)+1);
197
198 if (rc)
199 goto err1;
200
201 err1:
202 release_scratch_buff(&tmp_buffer, pout_buff);
203 err:
204 return rc;
205 }
206
compress_buff(struct cudbg_buffer * pin_buff,struct cudbg_buffer * pout_buff)207 int compress_buff(struct cudbg_buffer *pin_buff, struct cudbg_buffer *pout_buff)
208 {
209 struct cudbg_buffer tmp_buffer;
210 struct cudbg_hdr *cudbg_hdr;
211 unsigned long checksum;
212 unsigned char *result;
213 unsigned int bytes_read;
214 int chunk_size, level = 2, rc = 0;
215 int compress_method = 1;
216
217 bytes_read = pin_buff->size;
218 rc = get_scratch_buff(pout_buff, CUDBG_BLOCK_SIZE, &tmp_buffer);
219
220 if (rc)
221 goto err;
222
223 result = (unsigned char *)tmp_buffer.data;
224
225 if (bytes_read < 32)
226 compress_method = 0;
227
228 cudbg_hdr = (struct cudbg_hdr *) pout_buff->data;
229
230 switch (compress_method) {
231 case 1:
232 chunk_size = fastlz_compress_level(level, pin_buff->data,
233 bytes_read, result);
234
235 checksum = update_adler32(1L, result, chunk_size);
236
237 if ((chunk_size > 62000) && (cudbg_hdr->reserved[7] < (u32)
238 chunk_size)) /* 64512 */
239 cudbg_hdr->reserved[7] = (u32) chunk_size;
240
241 rc = write_chunk_header(pout_buff, 17, 1, chunk_size, checksum,
242 bytes_read);
243
244 if (rc)
245 goto err_put_buff;
246
247 rc = write_to_buf(pout_buff->data, pout_buff->size,
248 &pout_buff->offset, result, chunk_size);
249
250 if (rc)
251 goto err_put_buff;
252
253 break;
254
255 /* uncompressed, also fallback method */
256 case 0:
257 default:
258 checksum = update_adler32(1L, pin_buff->data, bytes_read);
259
260 rc = write_chunk_header(pout_buff, 17, 0, bytes_read, checksum,
261 bytes_read);
262
263 if (rc)
264 goto err_put_buff;
265
266 rc = write_to_buf(pout_buff->data, pout_buff->size,
267 &pout_buff->offset, pin_buff->data,
268 bytes_read);
269 if (rc)
270 goto err_put_buff;
271
272 break;
273 }
274
275 err_put_buff:
276 release_scratch_buff(&tmp_buffer, pout_buff);
277 err:
278 return rc;
279 }
280
281 /* return non-zero if magic sequence is detected */
282 /* warning: reset the read pointer to the beginning of the file */
detect_magic(struct cudbg_buffer * _c_buff)283 int detect_magic(struct cudbg_buffer *_c_buff)
284 {
285 unsigned char buffer[8];
286 size_t bytes_read;
287 int c;
288
289 bytes_read = read_from_buf(_c_buff->data, _c_buff->size,
290 &_c_buff->offset, buffer, 8);
291
292 if (bytes_read < 8)
293 return 0;
294
295 for (c = 0; c < 8; c++)
296 if (buffer[c] != sixpack_magic[c])
297 return 0;
298
299 return -1;
300 }
301
readU16(const unsigned char * ptr)302 static inline unsigned long readU16(const unsigned char *ptr)
303 {
304 return ptr[0]+(ptr[1]<<8);
305 }
306
readU32(const unsigned char * ptr)307 static inline unsigned long readU32(const unsigned char *ptr)
308 {
309 return ptr[0]+(ptr[1]<<8)+(ptr[2]<<16)+(ptr[3]<<24);
310 }
311
read_chunk_header(struct cudbg_buffer * pc_buff,int * pid,int * poptions,unsigned long * psize,unsigned long * pchecksum,unsigned long * pextra)312 int read_chunk_header(struct cudbg_buffer *pc_buff, int *pid, int *poptions,
313 unsigned long *psize, unsigned long *pchecksum,
314 unsigned long *pextra)
315 {
316 unsigned char buffer[CUDBG_CHUNK_BUF_LEN];
317 int byte_r = read_from_buf(pc_buff->data, pc_buff->size,
318 &pc_buff->offset, buffer, 16);
319 if (byte_r == 0)
320 return 0;
321
322 *pid = readU16(buffer) & 0xffff;
323 *poptions = readU16(buffer+2) & 0xffff;
324 *psize = readU32(buffer+4) & 0xffffffff;
325 *pchecksum = readU32(buffer+8) & 0xffffffff;
326 *pextra = readU32(buffer+12) & 0xffffffff;
327 return 0;
328 }
329
validate_buffer(struct cudbg_buffer * compressed_buffer)330 int validate_buffer(struct cudbg_buffer *compressed_buffer)
331 {
332 if (!detect_magic(compressed_buffer))
333 return CUDBG_STATUS_INVALID_BUFF;
334
335 return 0;
336 }
337
decompress_buffer(struct cudbg_buffer * pc_buff,struct cudbg_buffer * pd_buff)338 int decompress_buffer(struct cudbg_buffer *pc_buff,
339 struct cudbg_buffer *pd_buff)
340 {
341 struct cudbg_buffer tmp_compressed_buffer;
342 struct cudbg_buffer tmp_decompressed_buffer;
343 unsigned char *compressed_buffer;
344 unsigned char *decompressed_buffer;
345 unsigned char buffer[CUDBG_MIN_COMPR_LEN];
346 unsigned long chunk_size;
347 unsigned long chunk_checksum;
348 unsigned long chunk_extra;
349 unsigned long checksum;
350 unsigned long r;
351 unsigned long remaining;
352 unsigned long bytes_read;
353 u32 decompressed_size = 0;
354 int chunk_id, chunk_options, rc;
355
356 if (pd_buff->size < 2 * CUDBG_BLOCK_SIZE)
357 return CUDBG_STATUS_SMALL_BUFF;
358
359 rc = get_scratch_buff(pd_buff, CUDBG_BLOCK_SIZE,
360 &tmp_compressed_buffer);
361
362 if (rc)
363 goto err_cbuff;
364
365 rc = get_scratch_buff(pd_buff, CUDBG_BLOCK_SIZE,
366 &tmp_decompressed_buffer);
367 if (rc)
368 goto err_dcbuff;
369
370 compressed_buffer = (unsigned char *)tmp_compressed_buffer.data;
371 decompressed_buffer = (unsigned char *)tmp_decompressed_buffer.data;
372
373 /* main loop */
374
375 for (;;) {
376 if (pc_buff->offset > pc_buff->size)
377 break;
378
379 rc = read_chunk_header(pc_buff, &chunk_id, &chunk_options,
380 &chunk_size, &chunk_checksum,
381 &chunk_extra);
382 if (rc != 0)
383 break;
384
385 /* skip 8+16 */
386 if ((chunk_id == 1) && (chunk_size > 10) &&
387 (chunk_size < CUDBG_BLOCK_SIZE)) {
388
389 bytes_read = read_from_buf(pc_buff->data, pc_buff->size,
390 &pc_buff->offset, buffer,
391 chunk_size);
392
393 if (bytes_read == 0)
394 return 0;
395
396 checksum = update_adler32(1L, buffer, chunk_size);
397 if (checksum != chunk_checksum)
398 return CUDBG_STATUS_CHKSUM_MISSMATCH;
399
400 decompressed_size = (u32)readU32(buffer);
401
402 if (pd_buff->size < decompressed_size) {
403
404 pd_buff->size = 2 * CUDBG_BLOCK_SIZE +
405 decompressed_size;
406 pc_buff->offset -= chunk_size + 16;
407 return CUDBG_STATUS_SMALL_BUFF;
408 }
409 }
410
411 if (chunk_size > CUDBG_BLOCK_SIZE) {
412 /* Release old allocated memory */
413 release_scratch_buff(&tmp_decompressed_buffer, pd_buff);
414 release_scratch_buff(&tmp_compressed_buffer, pd_buff);
415
416 /* allocate new memory with chunk_size size */
417 rc = get_scratch_buff(pd_buff, chunk_size,
418 &tmp_compressed_buffer);
419 if (rc)
420 goto err_cbuff;
421
422 rc = get_scratch_buff(pd_buff, chunk_size,
423 &tmp_decompressed_buffer);
424 if (rc)
425 goto err_dcbuff;
426
427 compressed_buffer = (unsigned char *)tmp_compressed_buffer.data;
428 decompressed_buffer = (unsigned char *)tmp_decompressed_buffer.data;
429 }
430
431 if ((chunk_id == 17) && decompressed_size) {
432 /* uncompressed */
433 switch (chunk_options) {
434 /* stored, simply copy to output */
435 case 0:
436 remaining = chunk_size;
437 checksum = 1L;
438 for (;;) {
439 /* Write a function for this */
440 r = (CUDBG_BLOCK_SIZE < remaining) ?
441 CUDBG_BLOCK_SIZE : remaining;
442 bytes_read =
443 read_from_buf(pc_buff->data,
444 pc_buff->size,
445 &pc_buff->offset, buffer,
446 r);
447
448 if (bytes_read == 0)
449 return 0;
450
451 write_to_buf(pd_buff->data,
452 pd_buff->size,
453 &pd_buff->offset, buffer,
454 bytes_read);
455 checksum = update_adler32(checksum,
456 buffer,
457 bytes_read);
458 remaining -= bytes_read;
459
460 /* verify everything is written
461 * correctly */
462 if (checksum != chunk_checksum)
463 return
464 CUDBG_STATUS_CHKSUM_MISSMATCH;
465 }
466
467 break;
468
469 /* compressed using FastLZ */
470 case 1:
471 bytes_read = read_from_buf(pc_buff->data,
472 pc_buff->size,
473 &pc_buff->offset,
474 compressed_buffer,
475 chunk_size);
476
477 if (bytes_read == 0)
478 return 0;
479
480 checksum = update_adler32(1L, compressed_buffer,
481 chunk_size);
482
483 /* verify that the chunk data is correct */
484 if (checksum != chunk_checksum) {
485 return CUDBG_STATUS_CHKSUM_MISSMATCH;
486 } else {
487 /* decompress and verify */
488 remaining =
489 fastlz_decompress(compressed_buffer,
490 chunk_size,
491 decompressed_buffer,
492 chunk_extra);
493
494 if (remaining != chunk_extra) {
495 rc =
496 CUDBG_STATUS_DECOMPRESS_FAIL;
497 goto err;
498 } else {
499 write_to_buf(pd_buff->data,
500 pd_buff->size,
501 &pd_buff->offset,
502 decompressed_buffer,
503 chunk_extra);
504 }
505 }
506 break;
507
508 default:
509 break;
510 }
511
512 }
513
514 }
515
516 err:
517 release_scratch_buff(&tmp_decompressed_buffer, pd_buff);
518 err_dcbuff:
519 release_scratch_buff(&tmp_compressed_buffer, pd_buff);
520
521 err_cbuff:
522 return rc;
523 }
524
525