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 __FBSDID("$FreeBSD$"); 28 29#include "osdep.h" 30#include "cudbg.h" 31#include "cudbg_lib_common.h" 32#include "fastlz.h" 33 34 static unsigned char sixpack_magic[8] = {137, '6', 'P', 'K', 13, 10, 26, 10}; 35 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*/ 39 40 /* for Adler-32 checksum algorithm, see RFC 1950 Section 8.2 */ 41 42#define ADLER32_BASE 65521 43 44 static inline unsigned long update_adler32(unsigned long checksum, 45 const void *buf, int len) 46{ 47 const unsigned char *ptr = (const unsigned char *)buf; 48 unsigned long s1 = checksum & 0xffff; 49 unsigned long s2 = (checksum >> 16) & 0xffff; 50 51 while (len > 0) { 52 unsigned k = len < 5552 ? len : 5552; 53 len -= k; 54 55 while (k >= 8) { 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; 64 k -= 8; 65 } 66 67 while (k-- > 0) { 68 s1 += *ptr++; s2 += s1; 69 } 70 s1 = s1 % ADLER32_BASE; 71 s2 = s2 % ADLER32_BASE; 72 } 73 return (s2 << 16) + s1; 74} 75 76 int write_magic(struct cudbg_buffer *_out_buff) 77{ 78 int rc; 79 80 rc = write_to_buf(_out_buff->data, _out_buff->size, &_out_buff->offset, 81 sixpack_magic, 8); 82 83 return rc; 84} 85 86 int write_to_buf(void *out_buf, u32 out_buf_size, u32 *offset, void *in_buf, 87 u32 in_buf_size) 88{ 89 int rc = 0; 90 91 if (*offset >= out_buf_size) { 92 rc = CUDBG_STATUS_OUTBUFF_OVERFLOW; 93 goto err; 94 } 95 96 memcpy((char *)out_buf + *offset, in_buf, in_buf_size); 97 *offset = *offset + in_buf_size; 98 99 err: 100 return rc; 101} 102 103 int read_from_buf(void *in_buf, u32 in_buf_size, u32 *offset, void *out_buf, 104 u32 out_buf_size) 105{ 106 if (in_buf_size - *offset < out_buf_size) 107 return 0; 108 109 memcpy((char *)out_buf, (char *)in_buf + *offset, out_buf_size); 110 *offset = *offset + out_buf_size; 111 return out_buf_size; 112} 113 114 int write_chunk_header(struct cudbg_buffer *_outbuf, int id, int options, 115 unsigned long size, unsigned long checksum, 116 unsigned long extra) 117{ 118 unsigned char buffer[CUDBG_CHUNK_BUF_LEN]; 119 int rc = 0; 120 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; 137 138 rc = write_to_buf(_outbuf->data, _outbuf->size, &_outbuf->offset, 139 buffer, 16); 140 141 return rc; 142} 143 144 int write_compression_hdr(struct cudbg_buffer *pin_buff, 145 struct cudbg_buffer *pout_buff) 146{ 147 struct cudbg_buffer tmp_buffer; 148 unsigned long fsize = pin_buff->size; 149 unsigned char *buffer; 150 unsigned long checksum; 151 int rc; 152 char *shown_name = "abc"; 153 154 /* Always release inner scratch buffer, before releasing outer. */ 155 rc = get_scratch_buff(pout_buff, 10, &tmp_buffer); 156 157 if (rc) 158 goto err; 159 160 buffer = (unsigned char *)tmp_buffer.data; 161 162 rc = write_magic(pout_buff); 163 164 if (rc) 165 goto err1; 166 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; 172 buffer[4] = 0; 173 buffer[5] = 0; 174 buffer[6] = 0; 175 buffer[7] = 0; 176 buffer[8] = (strlen(shown_name)+1) & 255; 177 buffer[9] = (unsigned char)((strlen(shown_name)+1) >> 8); 178 checksum = 1L; 179 checksum = update_adler32(checksum, buffer, 10); 180 checksum = update_adler32(checksum, shown_name, 181 (int)strlen(shown_name)+1); 182 183 rc = write_chunk_header(pout_buff, 1, 0, 184 10+(unsigned long)strlen(shown_name)+1, 185 checksum, 0); 186 187 if (rc) 188 goto err1; 189 190 rc = write_to_buf(pout_buff->data, pout_buff->size, 191 &(pout_buff->offset), buffer, 10); 192 193 if (rc) 194 goto err1; 195 196 rc = write_to_buf(pout_buff->data, pout_buff->size, 197 &(pout_buff->offset), shown_name, 198 (u32)strlen(shown_name)+1); 199 200 if (rc) 201 goto err1; 202 203 err1: 204 release_scratch_buff(&tmp_buffer, pout_buff); 205 err: 206 return rc; 207} 208 209 int compress_buff(struct cudbg_buffer *pin_buff, struct cudbg_buffer *pout_buff) 210{ 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; 218 219 bytes_read = pin_buff->size; 220 rc = get_scratch_buff(pout_buff, CUDBG_BLOCK_SIZE, &tmp_buffer); 221 222 if (rc) 223 goto err; 224 225 result = (unsigned char *)tmp_buffer.data; 226 227 if (bytes_read < 32) 228 compress_method = 0; 229 230 cudbg_hdr = (struct cudbg_hdr *) pout_buff->data; 231 232 switch (compress_method) { 233 case 1: 234 chunk_size = fastlz_compress_level(level, pin_buff->data, 235 bytes_read, result); 236 237 checksum = update_adler32(1L, result, chunk_size); 238 239 if ((chunk_size > 62000) && (cudbg_hdr->reserved[7] < (u32) 240 chunk_size)) /* 64512 */ 241 cudbg_hdr->reserved[7] = (u32) chunk_size; 242 243 rc = write_chunk_header(pout_buff, 17, 1, chunk_size, checksum, 244 bytes_read); 245 246 if (rc) 247 goto err_put_buff; 248 249 rc = write_to_buf(pout_buff->data, pout_buff->size, 250 &pout_buff->offset, result, chunk_size); 251 252 if (rc) 253 goto err_put_buff; 254 255 break; 256 257 /* uncompressed, also fallback method */ 258 case 0: 259 default: 260 checksum = update_adler32(1L, pin_buff->data, bytes_read); 261 262 rc = write_chunk_header(pout_buff, 17, 0, bytes_read, checksum, 263 bytes_read); 264 265 if (rc) 266 goto err_put_buff; 267 268 rc = write_to_buf(pout_buff->data, pout_buff->size, 269 &pout_buff->offset, pin_buff->data, 270 bytes_read); 271 if (rc) 272 goto err_put_buff; 273 274 break; 275 } 276 277 err_put_buff: 278 release_scratch_buff(&tmp_buffer, pout_buff); 279 err: 280 return rc; 281} 282 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) 286{ 287 unsigned char buffer[8]; 288 size_t bytes_read; 289 int c; 290 291 bytes_read = read_from_buf(_c_buff->data, _c_buff->size, 292 &_c_buff->offset, buffer, 8); 293 294 if (bytes_read < 8) 295 return 0; 296 297 for (c = 0; c < 8; c++) 298 if (buffer[c] != sixpack_magic[c]) 299 return 0; 300 301 return -1; 302} 303 304 static inline unsigned long readU16(const unsigned char *ptr) 305{ 306 return ptr[0]+(ptr[1]<<8); 307} 308 309 static inline unsigned long readU32(const unsigned char *ptr) 310{ 311 return ptr[0]+(ptr[1]<<8)+(ptr[2]<<16)+(ptr[3]<<24); 312} 313 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) 317{ 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); 321 if (byte_r == 0) 322 return 0; 323 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; 329 return 0; 330} 331 332 int validate_buffer(struct cudbg_buffer *compressed_buffer) 333{ 334 if (!detect_magic(compressed_buffer)) 335 return CUDBG_STATUS_INVALID_BUFF; 336 337 return 0; 338} 339 340 int decompress_buffer(struct cudbg_buffer *pc_buff, 341 struct cudbg_buffer *pd_buff) 342{ 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; 353 unsigned long r; 354 unsigned long remaining; 355 unsigned long bytes_read; 356 u32 decompressed_size = 0; 357 int chunk_id, chunk_options, rc; 358 359 if (pd_buff->size < 2 * CUDBG_BLOCK_SIZE) 360 return CUDBG_STATUS_SMALL_BUFF; 361 362 rc = get_scratch_buff(pd_buff, CUDBG_BLOCK_SIZE, 363 &tmp_compressed_buffer); 364 365 if (rc) 366 goto err_cbuff; 367 368 rc = get_scratch_buff(pd_buff, CUDBG_BLOCK_SIZE, 369 &tmp_decompressed_buffer); 370 if (rc) 371 goto err_dcbuff; 372 373 compressed_buffer = (unsigned char *)tmp_compressed_buffer.data; 374 decompressed_buffer = (unsigned char *)tmp_decompressed_buffer.data; 375 376 /* main loop */ 377 378 for (;;) { 379 if (pc_buff->offset > pc_buff->size) 380 break; 381 382 rc = read_chunk_header(pc_buff, &chunk_id, &chunk_options, 383 &chunk_size, &chunk_checksum, 384 &chunk_extra); 385 if (rc != 0) 386 break; 387 388 /* skip 8+16 */ 389 if ((chunk_id == 1) && (chunk_size > 10) && 390 (chunk_size < CUDBG_BLOCK_SIZE)) { 391 392 bytes_read = read_from_buf(pc_buff->data, pc_buff->size, 393 &pc_buff->offset, buffer, 394 chunk_size); 395 396 if (bytes_read == 0) 397 return 0; 398 399 checksum = update_adler32(1L, buffer, chunk_size); 400 if (checksum != chunk_checksum) 401 return CUDBG_STATUS_CHKSUM_MISSMATCH; 402 403 decompressed_size = (u32)readU32(buffer); 404 405 if (pd_buff->size < decompressed_size) { 406 407 pd_buff->size = 2 * CUDBG_BLOCK_SIZE + 408 decompressed_size; 409 pc_buff->offset -= chunk_size + 16; 410 return CUDBG_STATUS_SMALL_BUFF; 411 } 412 total_extracted = 0; 413 414 } 415 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); 420 421 /* allocate new memory with chunk_size size */ 422 rc = get_scratch_buff(pd_buff, chunk_size, 423 &tmp_compressed_buffer); 424 if (rc) 425 goto err_cbuff; 426 427 rc = get_scratch_buff(pd_buff, chunk_size, 428 &tmp_decompressed_buffer); 429 if (rc) 430 goto err_dcbuff; 431 432 compressed_buffer = (unsigned char *)tmp_compressed_buffer.data; 433 decompressed_buffer = (unsigned char *)tmp_decompressed_buffer.data; 434 } 435 436 if ((chunk_id == 17) && decompressed_size) { 437 /* uncompressed */ 438 switch (chunk_options) { 439 /* stored, simply copy to output */ 440 case 0: 441 total_extracted += chunk_size; 442 remaining = chunk_size; 443 checksum = 1L; 444 for (;;) { 445 /* Write a funtion for this */ 446 r = (CUDBG_BLOCK_SIZE < remaining) ? 447 CUDBG_BLOCK_SIZE : remaining; 448 bytes_read = 449 read_from_buf(pc_buff->data, 450 pc_buff->size, 451 &pc_buff->offset, buffer, 452 r); 453 454 if (bytes_read == 0) 455 return 0; 456 457 write_to_buf(pd_buff->data, 458 pd_buff->size, 459 &pd_buff->offset, buffer, 460 bytes_read); 461 checksum = update_adler32(checksum, 462 buffer, 463 bytes_read); 464 remaining -= bytes_read; 465 466 /* verify everything is written 467 * correctly */ 468 if (checksum != chunk_checksum) 469 return 470 CUDBG_STATUS_CHKSUM_MISSMATCH; 471 } 472 473 break; 474 475 /* compressed using FastLZ */ 476 case 1: 477 bytes_read = read_from_buf(pc_buff->data, 478 pc_buff->size, 479 &pc_buff->offset, 480 compressed_buffer, 481 chunk_size); 482 483 if (bytes_read == 0) 484 return 0; 485 486 checksum = update_adler32(1L, compressed_buffer, 487 chunk_size); 488 total_extracted += chunk_extra; 489 490 /* verify that the chunk data is correct */ 491 if (checksum != chunk_checksum) { 492 return CUDBG_STATUS_CHKSUM_MISSMATCH; 493 } else { 494 /* decompress and verify */ 495 remaining = 496 fastlz_decompress(compressed_buffer, 497 chunk_size, 498 decompressed_buffer, 499 chunk_extra); 500 501 if (remaining != chunk_extra) { 502 rc = 503 CUDBG_STATUS_DECOMPRESS_FAIL; 504 goto err; 505 } else { 506 write_to_buf(pd_buff->data, 507 pd_buff->size, 508 &pd_buff->offset, 509 decompressed_buffer, 510 chunk_extra); 511 } 512 } 513 break; 514 515 default: 516 break; 517 } 518 519 } 520 521 } 522 523 err: 524 release_scratch_buff(&tmp_decompressed_buffer, pd_buff); 525 err_dcbuff: 526 release_scratch_buff(&tmp_compressed_buffer, pd_buff); 527 528 err_cbuff: 529 return rc; 530} 531 532