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 r; 353 unsigned long remaining; 354 unsigned long bytes_read; 355 u32 decompressed_size = 0; 356 int chunk_id, chunk_options, rc; 357 358 if (pd_buff->size < 2 * CUDBG_BLOCK_SIZE) 359 return CUDBG_STATUS_SMALL_BUFF; 360 361 rc = get_scratch_buff(pd_buff, CUDBG_BLOCK_SIZE, 362 &tmp_compressed_buffer); 363 364 if (rc) 365 goto err_cbuff; 366 367 rc = get_scratch_buff(pd_buff, CUDBG_BLOCK_SIZE, 368 &tmp_decompressed_buffer); 369 if (rc) 370 goto err_dcbuff; 371 372 compressed_buffer = (unsigned char *)tmp_compressed_buffer.data; 373 decompressed_buffer = (unsigned char *)tmp_decompressed_buffer.data; 374 375 /* main loop */ 376 377 for (;;) { 378 if (pc_buff->offset > pc_buff->size) 379 break; 380 381 rc = read_chunk_header(pc_buff, &chunk_id, &chunk_options, 382 &chunk_size, &chunk_checksum, 383 &chunk_extra); 384 if (rc != 0) 385 break; 386 387 /* skip 8+16 */ 388 if ((chunk_id == 1) && (chunk_size > 10) && 389 (chunk_size < CUDBG_BLOCK_SIZE)) { 390 391 bytes_read = read_from_buf(pc_buff->data, pc_buff->size, 392 &pc_buff->offset, buffer, 393 chunk_size); 394 395 if (bytes_read == 0) 396 return 0; 397 398 checksum = update_adler32(1L, buffer, chunk_size); 399 if (checksum != chunk_checksum) 400 return CUDBG_STATUS_CHKSUM_MISSMATCH; 401 402 decompressed_size = (u32)readU32(buffer); 403 404 if (pd_buff->size < decompressed_size) { 405 406 pd_buff->size = 2 * CUDBG_BLOCK_SIZE + 407 decompressed_size; 408 pc_buff->offset -= chunk_size + 16; 409 return CUDBG_STATUS_SMALL_BUFF; 410 } 411 } 412 413 if (chunk_size > CUDBG_BLOCK_SIZE) { 414 /* Release old allocated memory */ 415 release_scratch_buff(&tmp_decompressed_buffer, pd_buff); 416 release_scratch_buff(&tmp_compressed_buffer, pd_buff); 417 418 /* allocate new memory with chunk_size size */ 419 rc = get_scratch_buff(pd_buff, chunk_size, 420 &tmp_compressed_buffer); 421 if (rc) 422 goto err_cbuff; 423 424 rc = get_scratch_buff(pd_buff, chunk_size, 425 &tmp_decompressed_buffer); 426 if (rc) 427 goto err_dcbuff; 428 429 compressed_buffer = (unsigned char *)tmp_compressed_buffer.data; 430 decompressed_buffer = (unsigned char *)tmp_decompressed_buffer.data; 431 } 432 433 if ((chunk_id == 17) && decompressed_size) { 434 /* uncompressed */ 435 switch (chunk_options) { 436 /* stored, simply copy to output */ 437 case 0: 438 remaining = chunk_size; 439 checksum = 1L; 440 for (;;) { 441 /* Write a function for this */ 442 r = (CUDBG_BLOCK_SIZE < remaining) ? 443 CUDBG_BLOCK_SIZE : remaining; 444 bytes_read = 445 read_from_buf(pc_buff->data, 446 pc_buff->size, 447 &pc_buff->offset, buffer, 448 r); 449 450 if (bytes_read == 0) 451 return 0; 452 453 write_to_buf(pd_buff->data, 454 pd_buff->size, 455 &pd_buff->offset, buffer, 456 bytes_read); 457 checksum = update_adler32(checksum, 458 buffer, 459 bytes_read); 460 remaining -= bytes_read; 461 462 /* verify everything is written 463 * correctly */ 464 if (checksum != chunk_checksum) 465 return 466 CUDBG_STATUS_CHKSUM_MISSMATCH; 467 } 468 469 break; 470 471 /* compressed using FastLZ */ 472 case 1: 473 bytes_read = read_from_buf(pc_buff->data, 474 pc_buff->size, 475 &pc_buff->offset, 476 compressed_buffer, 477 chunk_size); 478 479 if (bytes_read == 0) 480 return 0; 481 482 checksum = update_adler32(1L, compressed_buffer, 483 chunk_size); 484 485 /* verify that the chunk data is correct */ 486 if (checksum != chunk_checksum) { 487 return CUDBG_STATUS_CHKSUM_MISSMATCH; 488 } else { 489 /* decompress and verify */ 490 remaining = 491 fastlz_decompress(compressed_buffer, 492 chunk_size, 493 decompressed_buffer, 494 chunk_extra); 495 496 if (remaining != chunk_extra) { 497 rc = 498 CUDBG_STATUS_DECOMPRESS_FAIL; 499 goto err; 500 } else { 501 write_to_buf(pd_buff->data, 502 pd_buff->size, 503 &pd_buff->offset, 504 decompressed_buffer, 505 chunk_extra); 506 } 507 } 508 break; 509 510 default: 511 break; 512 } 513 514 } 515 516 } 517 518 err: 519 release_scratch_buff(&tmp_decompressed_buffer, pd_buff); 520 err_dcbuff: 521 release_scratch_buff(&tmp_compressed_buffer, pd_buff); 522 523 err_cbuff: 524 return rc; 525 } 526 527