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 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 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 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 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 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 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 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 */ 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 302 static inline unsigned long readU16(const unsigned char *ptr) 303 { 304 return ptr[0]+(ptr[1]<<8); 305 } 306 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 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 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 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