2 FastLZ - lightning-fast lossless compression library
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)
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:
15 The above copyright notice and this permission notice shall be included in
16 all copies or substantial portions of the Software.
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
26 #include <sys/cdefs.h>
27 __FBSDID("$FreeBSD$");
31 #include "cudbg_lib_common.h"
34 static unsigned char sixpack_magic[8] = {137, '6', 'P', 'K', 13, 10, 26, 10};
36 #define CUDBG_BLOCK_SIZE (63*1024)
37 #define CUDBG_CHUNK_BUF_LEN 16
38 #define CUDBG_MIN_COMPR_LEN 32 /*min data length for applying compression*/
40 /* for Adler-32 checksum algorithm, see RFC 1950 Section 8.2 */
42 #define ADLER32_BASE 65521
44 static inline unsigned long update_adler32(unsigned long checksum,
45 const void *buf, int len)
47 const unsigned char *ptr = (const unsigned char *)buf;
48 unsigned long s1 = checksum & 0xffff;
49 unsigned long s2 = (checksum >> 16) & 0xffff;
52 unsigned k = len < 5552 ? len : 5552;
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 s1 += *ptr++; s2 += s1;
63 s1 += *ptr++; s2 += s1;
68 s1 += *ptr++; s2 += s1;
70 s1 = s1 % ADLER32_BASE;
71 s2 = s2 % ADLER32_BASE;
73 return (s2 << 16) + s1;
76 int write_magic(struct cudbg_buffer *_out_buff)
80 rc = write_to_buf(_out_buff->data, _out_buff->size, &_out_buff->offset,
86 int write_to_buf(void *out_buf, u32 out_buf_size, u32 *offset, void *in_buf,
91 if (*offset >= out_buf_size) {
92 rc = CUDBG_STATUS_OUTBUFF_OVERFLOW;
96 memcpy((char *)out_buf + *offset, in_buf, in_buf_size);
97 *offset = *offset + in_buf_size;
103 int read_from_buf(void *in_buf, u32 in_buf_size, u32 *offset, void *out_buf,
106 if (in_buf_size - *offset < out_buf_size)
109 memcpy((char *)out_buf, (char *)in_buf + *offset, out_buf_size);
110 *offset = *offset + out_buf_size;
114 int write_chunk_header(struct cudbg_buffer *_outbuf, int id, int options,
115 unsigned long size, unsigned long checksum,
118 unsigned char buffer[CUDBG_CHUNK_BUF_LEN];
121 buffer[0] = id & 255;
122 buffer[1] = (unsigned char)(id >> 8);
123 buffer[2] = options & 255;
124 buffer[3] = (unsigned char)(options >> 8);
125 buffer[4] = size & 255;
126 buffer[5] = (size >> 8) & 255;
127 buffer[6] = (size >> 16) & 255;
128 buffer[7] = (size >> 24) & 255;
129 buffer[8] = checksum & 255;
130 buffer[9] = (checksum >> 8) & 255;
131 buffer[10] = (checksum >> 16) & 255;
132 buffer[11] = (checksum >> 24) & 255;
133 buffer[12] = extra & 255;
134 buffer[13] = (extra >> 8) & 255;
135 buffer[14] = (extra >> 16) & 255;
136 buffer[15] = (extra >> 24) & 255;
138 rc = write_to_buf(_outbuf->data, _outbuf->size, &_outbuf->offset,
144 int write_compression_hdr(struct cudbg_buffer *pin_buff,
145 struct cudbg_buffer *pout_buff)
147 struct cudbg_buffer tmp_buffer;
148 unsigned long fsize = pin_buff->size;
149 unsigned char *buffer;
150 unsigned long checksum;
152 char *shown_name = "abc";
154 /* Always release inner scratch buffer, before releasing outer. */
155 rc = get_scratch_buff(pout_buff, 10, &tmp_buffer);
160 buffer = (unsigned char *)tmp_buffer.data;
162 rc = write_magic(pout_buff);
167 /* chunk for File Entry */
168 buffer[0] = fsize & 255;
169 buffer[1] = (fsize >> 8) & 255;
170 buffer[2] = (fsize >> 16) & 255;
171 buffer[3] = (fsize >> 24) & 255;
176 buffer[8] = (strlen(shown_name)+1) & 255;
177 buffer[9] = (unsigned char)((strlen(shown_name)+1) >> 8);
179 checksum = update_adler32(checksum, buffer, 10);
180 checksum = update_adler32(checksum, shown_name,
181 (int)strlen(shown_name)+1);
183 rc = write_chunk_header(pout_buff, 1, 0,
184 10+(unsigned long)strlen(shown_name)+1,
190 rc = write_to_buf(pout_buff->data, pout_buff->size,
191 &(pout_buff->offset), buffer, 10);
196 rc = write_to_buf(pout_buff->data, pout_buff->size,
197 &(pout_buff->offset), shown_name,
198 (u32)strlen(shown_name)+1);
204 release_scratch_buff(&tmp_buffer, pout_buff);
209 int compress_buff(struct cudbg_buffer *pin_buff, struct cudbg_buffer *pout_buff)
211 struct cudbg_buffer tmp_buffer;
212 struct cudbg_hdr *cudbg_hdr;
213 unsigned long checksum;
214 unsigned char *result;
215 unsigned int bytes_read;
216 int chunk_size, level = 2, rc = 0;
217 int compress_method = 1;
219 bytes_read = pin_buff->size;
220 rc = get_scratch_buff(pout_buff, CUDBG_BLOCK_SIZE, &tmp_buffer);
225 result = (unsigned char *)tmp_buffer.data;
230 cudbg_hdr = (struct cudbg_hdr *) pout_buff->data;
232 switch (compress_method) {
234 chunk_size = fastlz_compress_level(level, pin_buff->data,
237 checksum = update_adler32(1L, result, chunk_size);
239 if ((chunk_size > 62000) && (cudbg_hdr->reserved[7] < (u32)
240 chunk_size)) /* 64512 */
241 cudbg_hdr->reserved[7] = (u32) chunk_size;
243 rc = write_chunk_header(pout_buff, 17, 1, chunk_size, checksum,
249 rc = write_to_buf(pout_buff->data, pout_buff->size,
250 &pout_buff->offset, result, chunk_size);
257 /* uncompressed, also fallback method */
260 checksum = update_adler32(1L, pin_buff->data, bytes_read);
262 rc = write_chunk_header(pout_buff, 17, 0, bytes_read, checksum,
268 rc = write_to_buf(pout_buff->data, pout_buff->size,
269 &pout_buff->offset, pin_buff->data,
278 release_scratch_buff(&tmp_buffer, pout_buff);
283 /* return non-zero if magic sequence is detected */
284 /* warning: reset the read pointer to the beginning of the file */
285 int detect_magic(struct cudbg_buffer *_c_buff)
287 unsigned char buffer[8];
291 bytes_read = read_from_buf(_c_buff->data, _c_buff->size,
292 &_c_buff->offset, buffer, 8);
297 for (c = 0; c < 8; c++)
298 if (buffer[c] != sixpack_magic[c])
304 static inline unsigned long readU16(const unsigned char *ptr)
306 return ptr[0]+(ptr[1]<<8);
309 static inline unsigned long readU32(const unsigned char *ptr)
311 return ptr[0]+(ptr[1]<<8)+(ptr[2]<<16)+(ptr[3]<<24);
314 int read_chunk_header(struct cudbg_buffer *pc_buff, int *pid, int *poptions,
315 unsigned long *psize, unsigned long *pchecksum,
316 unsigned long *pextra)
318 unsigned char buffer[CUDBG_CHUNK_BUF_LEN];
319 int byte_r = read_from_buf(pc_buff->data, pc_buff->size,
320 &pc_buff->offset, buffer, 16);
324 *pid = readU16(buffer) & 0xffff;
325 *poptions = readU16(buffer+2) & 0xffff;
326 *psize = readU32(buffer+4) & 0xffffffff;
327 *pchecksum = readU32(buffer+8) & 0xffffffff;
328 *pextra = readU32(buffer+12) & 0xffffffff;
332 int validate_buffer(struct cudbg_buffer *compressed_buffer)
334 if (!detect_magic(compressed_buffer))
335 return CUDBG_STATUS_INVALID_BUFF;
340 int decompress_buffer(struct cudbg_buffer *pc_buff,
341 struct cudbg_buffer *pd_buff)
343 struct cudbg_buffer tmp_compressed_buffer;
344 struct cudbg_buffer tmp_decompressed_buffer;
345 unsigned char *compressed_buffer;
346 unsigned char *decompressed_buffer;
347 unsigned char buffer[CUDBG_MIN_COMPR_LEN];
348 unsigned long chunk_size;
349 unsigned long chunk_checksum;
350 unsigned long chunk_extra;
351 unsigned long checksum;
352 unsigned long total_extracted = 0;
354 unsigned long remaining;
355 unsigned long bytes_read;
356 u32 decompressed_size = 0;
357 int chunk_id, chunk_options, rc;
359 if (pd_buff->size < 2 * CUDBG_BLOCK_SIZE)
360 return CUDBG_STATUS_SMALL_BUFF;
362 rc = get_scratch_buff(pd_buff, CUDBG_BLOCK_SIZE,
363 &tmp_compressed_buffer);
368 rc = get_scratch_buff(pd_buff, CUDBG_BLOCK_SIZE,
369 &tmp_decompressed_buffer);
373 compressed_buffer = (unsigned char *)tmp_compressed_buffer.data;
374 decompressed_buffer = (unsigned char *)tmp_decompressed_buffer.data;
379 if (pc_buff->offset > pc_buff->size)
382 rc = read_chunk_header(pc_buff, &chunk_id, &chunk_options,
383 &chunk_size, &chunk_checksum,
389 if ((chunk_id == 1) && (chunk_size > 10) &&
390 (chunk_size < CUDBG_BLOCK_SIZE)) {
392 bytes_read = read_from_buf(pc_buff->data, pc_buff->size,
393 &pc_buff->offset, buffer,
399 checksum = update_adler32(1L, buffer, chunk_size);
400 if (checksum != chunk_checksum)
401 return CUDBG_STATUS_CHKSUM_MISSMATCH;
403 decompressed_size = (u32)readU32(buffer);
405 if (pd_buff->size < decompressed_size) {
407 pd_buff->size = 2 * CUDBG_BLOCK_SIZE +
409 pc_buff->offset -= chunk_size + 16;
410 return CUDBG_STATUS_SMALL_BUFF;
416 if (chunk_size > CUDBG_BLOCK_SIZE) {
417 /* Release old allocated memory */
418 release_scratch_buff(&tmp_decompressed_buffer, pd_buff);
419 release_scratch_buff(&tmp_compressed_buffer, pd_buff);
421 /* allocate new memory with chunk_size size */
422 rc = get_scratch_buff(pd_buff, chunk_size,
423 &tmp_compressed_buffer);
427 rc = get_scratch_buff(pd_buff, chunk_size,
428 &tmp_decompressed_buffer);
432 compressed_buffer = (unsigned char *)tmp_compressed_buffer.data;
433 decompressed_buffer = (unsigned char *)tmp_decompressed_buffer.data;
436 if ((chunk_id == 17) && decompressed_size) {
438 switch (chunk_options) {
439 /* stored, simply copy to output */
441 total_extracted += chunk_size;
442 remaining = chunk_size;
445 /* Write a funtion for this */
446 r = (CUDBG_BLOCK_SIZE < remaining) ?
447 CUDBG_BLOCK_SIZE : remaining;
449 read_from_buf(pc_buff->data,
451 &pc_buff->offset, buffer,
457 write_to_buf(pd_buff->data,
459 &pd_buff->offset, buffer,
461 checksum = update_adler32(checksum,
464 remaining -= bytes_read;
466 /* verify everything is written
468 if (checksum != chunk_checksum)
470 CUDBG_STATUS_CHKSUM_MISSMATCH;
475 /* compressed using FastLZ */
477 bytes_read = read_from_buf(pc_buff->data,
486 checksum = update_adler32(1L, compressed_buffer,
488 total_extracted += chunk_extra;
490 /* verify that the chunk data is correct */
491 if (checksum != chunk_checksum) {
492 return CUDBG_STATUS_CHKSUM_MISSMATCH;
494 /* decompress and verify */
496 fastlz_decompress(compressed_buffer,
501 if (remaining != chunk_extra) {
503 CUDBG_STATUS_DECOMPRESS_FAIL;
506 write_to_buf(pd_buff->data,
524 release_scratch_buff(&tmp_decompressed_buffer, pd_buff);
526 release_scratch_buff(&tmp_compressed_buffer, pd_buff);