zlib.c (13876B)
1 #include "zlib.h" 2 #include "compression.h" /* Use existing adler32 and crc32 functions */ 3 #include "deflate_impl.h" /* Use existing deflate compression */ 4 #include <string.h> 5 #include <stdlib.h> 6 7 /* Use existing implementations from compression.c */ 8 /* adler32 is already defined in compression.c */ 9 /* crc32_calc is defined in compression.c, we'll alias it */ 10 11 uint32_t crc32(uint32_t crc, const uint8_t *buf, uint32_t len) { 12 return crc32_calc(crc, buf, len); 13 } 14 15 /* Huffman decoding structures */ 16 typedef struct { 17 uint16_t *table; 18 uint16_t count[16]; /* Number of codes of each length */ 19 int maxbits; 20 } huffman_t; 21 22 typedef struct { 23 const uint8_t *in; 24 uint32_t inlen; 25 uint32_t inpos; 26 uint32_t bitbuf; 27 int bitcnt; 28 29 uint8_t *out; 30 uint32_t outlen; 31 uint32_t outpos; 32 33 huffman_t lencode; 34 huffman_t distcode; 35 } inflate_state; 36 37 /* Bit manipulation */ 38 static int bits(inflate_state *s, int need) { 39 int val = s->bitbuf; 40 41 while (s->bitcnt < need) { 42 if (s->inpos >= s->inlen) return -1; 43 val |= (int)(s->in[s->inpos++]) << s->bitcnt; 44 s->bitcnt += 8; 45 } 46 47 s->bitbuf = val >> need; 48 s->bitcnt -= need; 49 50 return val & ((1 << need) - 1); 51 } 52 53 /* Build Huffman decoding tables */ 54 static int build_huffman(huffman_t *h, const uint16_t *length, int n) { 55 uint16_t offs[16]; 56 57 /* Count number of codes of each length */ 58 for (int i = 0; i < 16; i++) h->count[i] = 0; 59 60 for (int i = 0; i < n; i++) { 61 if (length[i] > 15) return -1; 62 h->count[length[i]]++; 63 } 64 65 if (h->count[0] == n) return 0; 66 67 /* Check for valid set of lengths */ 68 int left = 1; 69 for (int len = 1; len <= 15; len++) { 70 left <<= 1; 71 left -= h->count[len]; 72 if (left < 0) return -1; 73 } 74 75 /* Generate offsets into symbol table */ 76 offs[1] = 0; 77 for (int len = 1; len < 15; len++) 78 offs[len + 1] = offs[len] + h->count[len]; 79 80 /* Generate decoding tables */ 81 for (int symbol = 0; symbol < n; symbol++) { 82 if (length[symbol] != 0) { 83 int idx = offs[length[symbol]]++; 84 h->table[idx] = symbol; 85 } 86 } 87 88 return 0; 89 } 90 91 /* Decode a symbol from stream using Huffman tree */ 92 static int decode(inflate_state *s, huffman_t *h) { 93 int code = 0; 94 int first = 0; 95 int index = 0; 96 97 for (int len = 1; len <= h->maxbits; len++) { 98 int bit = bits(s, 1); 99 if (bit < 0) return -1; 100 101 code |= bit; 102 103 /* Search for code in table */ 104 for (int i = index; i < index + h->count[len]; i++) { 105 if (h->table[i] != 0xFFFF) { 106 if (code == first) { 107 return h->table[i]; 108 } 109 first++; 110 } 111 } 112 113 index += h->count[len]; 114 first <<= 1; 115 code <<= 1; 116 } 117 118 return -1; 119 } 120 121 /* Fixed Huffman tables */ 122 static int build_fixed(inflate_state *s) { 123 static int virgin = 1; 124 static uint16_t lencnt[16], lensym[288]; 125 static uint16_t distcnt[16], distsym[32]; 126 127 if (virgin) { 128 int symbol; 129 uint16_t lengths[288]; 130 131 /* Literal/length table */ 132 for (symbol = 0; symbol < 144; symbol++) 133 lengths[symbol] = 8; 134 for (; symbol < 256; symbol++) 135 lengths[symbol] = 9; 136 for (; symbol < 280; symbol++) 137 lengths[symbol] = 7; 138 for (; symbol < 288; symbol++) 139 lengths[symbol] = 8; 140 141 s->lencode.table = lensym; 142 s->lencode.maxbits = 9; 143 build_huffman(&s->lencode, lengths, 288); 144 145 /* Distance table */ 146 for (symbol = 0; symbol < 32; symbol++) 147 lengths[symbol] = 5; 148 149 s->distcode.table = distsym; 150 s->distcode.maxbits = 5; 151 build_huffman(&s->distcode, lengths, 32); 152 153 virgin = 0; 154 } 155 156 return 0; 157 } 158 159 /* Decode literal/length and distance codes */ 160 static int decode_codes(inflate_state *s, huffman_t *lencode, huffman_t *distcode) { 161 static const uint16_t lens[29] = { 162 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 163 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 164 }; 165 static const uint16_t lext[29] = { 166 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 167 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 168 }; 169 static const uint16_t dists[30] = { 170 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 171 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 172 8193, 12289, 16385, 24577 173 }; 174 static const uint16_t dext[30] = { 175 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 176 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 177 12, 12, 13, 13 178 }; 179 180 int symbol; 181 182 do { 183 symbol = decode(s, lencode); 184 if (symbol < 0) return symbol; 185 186 if (symbol < 256) { 187 /* Literal */ 188 if (s->outpos >= s->outlen) return -1; 189 s->out[s->outpos++] = symbol; 190 } else if (symbol > 256) { 191 /* Length/distance pair */ 192 symbol -= 257; 193 if (symbol >= 29) return -1; 194 195 int len = lens[symbol] + bits(s, lext[symbol]); 196 if (len < 0) return -1; 197 198 symbol = decode(s, distcode); 199 if (symbol < 0) return symbol; 200 201 int dist = dists[symbol] + bits(s, dext[symbol]); 202 if (dist < 0) return -1; 203 204 if (s->outpos < (uint32_t)dist) return -1; 205 if (s->outpos + len > s->outlen) return -1; 206 207 /* Copy match */ 208 uint8_t *from = s->out + s->outpos - dist; 209 uint8_t *to = s->out + s->outpos; 210 s->outpos += len; 211 212 while (len--) *to++ = *from++; 213 } 214 } while (symbol != 256); 215 216 return 0; 217 } 218 219 /* Inflate implementation */ 220 static int puff(uint8_t *dest, uint32_t *destlen, const uint8_t *source, uint32_t sourcelen) { 221 inflate_state s; 222 int last, type; 223 int err; 224 225 s.in = source; 226 s.inlen = sourcelen; 227 s.inpos = 0; 228 s.bitbuf = 0; 229 s.bitcnt = 0; 230 231 s.out = dest; 232 s.outlen = *destlen; 233 s.outpos = 0; 234 235 do { 236 last = bits(&s, 1); 237 if (last < 0) return Z_DATA_ERROR; 238 239 type = bits(&s, 2); 240 if (type < 0) return Z_DATA_ERROR; 241 242 switch (type) { 243 case 0: /* Uncompressed */ 244 /* Skip to byte boundary */ 245 s.bitbuf = 0; 246 s.bitcnt = 0; 247 248 /* Get length */ 249 if (s.inpos + 4 > s.inlen) return Z_DATA_ERROR; 250 251 uint16_t len = s.in[s.inpos] | (s.in[s.inpos + 1] << 8); 252 uint16_t nlen = s.in[s.inpos + 2] | (s.in[s.inpos + 3] << 8); 253 s.inpos += 4; 254 255 if (len != (~nlen & 0xffff)) return Z_DATA_ERROR; 256 257 if (s.inpos + len > s.inlen) return Z_DATA_ERROR; 258 if (s.outpos + len > s.outlen) return Z_BUF_ERROR; 259 260 memcpy(s.out + s.outpos, s.in + s.inpos, len); 261 s.inpos += len; 262 s.outpos += len; 263 break; 264 265 case 1: /* Fixed Huffman */ 266 err = build_fixed(&s); 267 if (err) return err; 268 269 err = decode_codes(&s, &s.lencode, &s.distcode); 270 if (err) return err; 271 break; 272 273 case 2: /* Dynamic Huffman */ 274 { 275 /* Read dynamic Huffman table specification */ 276 int nlen = bits(&s, 5) + 257; /* Number of literal/length codes */ 277 int ndist = bits(&s, 5) + 1; /* Number of distance codes */ 278 int ncode = bits(&s, 4) + 4; /* Number of code length codes */ 279 280 if (nlen < 0 || ndist < 0 || ncode < 0) return Z_DATA_ERROR; 281 if (nlen > 286 || ndist > 30) return Z_DATA_ERROR; 282 283 /* Read code length code lengths (yes, really) */ 284 static const uint8_t order[19] = { 285 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 286 }; 287 288 uint16_t lengths[19] = {0}; 289 for (int i = 0; i < ncode; i++) { 290 int len = bits(&s, 3); 291 if (len < 0) return Z_DATA_ERROR; 292 lengths[order[i]] = len; 293 } 294 295 /* Build code length tree */ 296 static uint16_t lencode_table[19]; 297 huffman_t lencode = { lencode_table, {0}, 7 }; 298 err = build_huffman(&lencode, lengths, 19); 299 if (err) return err; 300 301 /* Read literal/length and distance code lengths */ 302 uint16_t lenlens[286 + 30]; 303 int index = 0; 304 while (index < nlen + ndist) { 305 int symbol = decode(&s, &lencode); 306 if (symbol < 0) return symbol; 307 308 if (symbol < 16) { 309 /* Literal length */ 310 lenlens[index++] = symbol; 311 } else { 312 /* Repeat previous length or zeros */ 313 int len = 0; 314 int repeat = 0; 315 316 if (symbol == 16) { 317 if (index == 0) return Z_DATA_ERROR; 318 len = lenlens[index - 1]; 319 repeat = bits(&s, 2) + 3; 320 } else if (symbol == 17) { 321 repeat = bits(&s, 3) + 3; 322 } else { /* symbol == 18 */ 323 repeat = bits(&s, 7) + 11; 324 } 325 326 if (repeat < 0) return Z_DATA_ERROR; 327 if (index + repeat > nlen + ndist) return Z_DATA_ERROR; 328 329 while (repeat--) 330 lenlens[index++] = len; 331 } 332 } 333 334 /* Build literal/length tree */ 335 static uint16_t litlen_table[286]; 336 s.lencode.table = litlen_table; 337 s.lencode.maxbits = 15; 338 err = build_huffman(&s.lencode, lenlens, nlen); 339 if (err) return err; 340 341 /* Build distance tree */ 342 static uint16_t dist_table[30]; 343 s.distcode.table = dist_table; 344 s.distcode.maxbits = 15; 345 err = build_huffman(&s.distcode, lenlens + nlen, ndist); 346 if (err) return err; 347 348 /* Decode data */ 349 err = decode_codes(&s, &s.lencode, &s.distcode); 350 if (err) return err; 351 } 352 break; 353 354 default: 355 return Z_DATA_ERROR; 356 } 357 } while (!last); 358 359 *destlen = s.outpos; 360 return Z_OK; 361 } 362 363 /* Uncompress - simple interface */ 364 int uncompress(uint8_t *dest, uint32_t *destLen, const uint8_t *source, uint32_t sourceLen) { 365 /* Check zlib header */ 366 if (sourceLen < 2) return Z_DATA_ERROR; 367 368 uint8_t cmf = source[0]; 369 uint8_t flg = source[1]; 370 371 /* Check compression method */ 372 if ((cmf & 0x0f) != Z_DEFLATED) return Z_DATA_ERROR; 373 374 /* Check header checksum */ 375 if (((cmf << 8) + flg) % 31 != 0) return Z_DATA_ERROR; 376 377 /* Skip header */ 378 const uint8_t *data = source + 2; 379 uint32_t datalen = sourceLen - 6; /* -2 header, -4 adler32 */ 380 381 /* Decompress */ 382 int err = puff(dest, destLen, data, datalen); 383 if (err != Z_OK) return err; 384 385 /* Verify Adler-32 checksum */ 386 uint32_t check = (source[sourceLen-4] << 24) | 387 (source[sourceLen-3] << 16) | 388 (source[sourceLen-2] << 8) | 389 source[sourceLen-1]; 390 391 uint32_t sum = adler32(1, dest, *destLen); 392 if (check != sum) return Z_DATA_ERROR; 393 394 return Z_OK; 395 } 396 397 /* Compress using existing deflate implementation */ 398 int compress(uint8_t *dest, uint32_t *destLen, const uint8_t *source, uint32_t sourceLen) { 399 if (*destLen < 6) return Z_BUF_ERROR; /* Need room for header + trailer */ 400 401 /* Compress using deflate_compress_full from deflate_impl.c */ 402 uint8_t *deflate_data = NULL; 403 uint32_t deflate_size = 0; 404 405 if (deflate_compress_full(source, sourceLen, &deflate_data, &deflate_size, 6) != 0) { 406 return Z_STREAM_ERROR; 407 } 408 409 /* Check if output fits */ 410 if (2 + deflate_size + 4 > *destLen) { 411 free(deflate_data); 412 return Z_BUF_ERROR; 413 } 414 415 /* Write zlib header */ 416 dest[0] = 0x78; /* CMF: deflate, 32K window */ 417 dest[1] = 0x9C; /* FLG: default compression */ 418 419 /* Copy deflate data */ 420 memcpy(dest + 2, deflate_data, deflate_size); 421 free(deflate_data); 422 423 /* Write Adler-32 checksum (big-endian) */ 424 uint32_t checksum = adler32(1, source, sourceLen); 425 dest[2 + deflate_size + 0] = (checksum >> 24) & 0xFF; 426 dest[2 + deflate_size + 1] = (checksum >> 16) & 0xFF; 427 dest[2 + deflate_size + 2] = (checksum >> 8) & 0xFF; 428 dest[2 + deflate_size + 3] = checksum & 0xFF; 429 430 *destLen = 2 + deflate_size + 4; 431 return Z_OK; 432 } 433 434 /* Stream interface stubs */ 435 int inflateInit(z_streamp strm) { 436 (void)strm; 437 return Z_STREAM_ERROR; /* Use uncompress() for simple decompression */ 438 } 439 440 int inflate(z_streamp strm, int flush) { 441 (void)strm; 442 (void)flush; 443 return Z_STREAM_ERROR; 444 } 445 446 int inflateEnd(z_streamp strm) { 447 (void)strm; 448 return Z_OK; 449 } 450 451 int deflateInit(z_streamp strm, int level) { 452 (void)strm; 453 (void)level; 454 return Z_STREAM_ERROR; 455 } 456 457 int deflate(z_streamp strm, int flush) { 458 (void)strm; 459 (void)flush; 460 return Z_STREAM_ERROR; 461 } 462 463 int deflateEnd(z_streamp strm) { 464 (void)strm; 465 return Z_OK; 466 }