deflate.c (18222B)
1 #include <stdlib.h> 2 #include <string.h> 3 #include "flate.h" 4 5 enum { 6 CodeBits = 16, /* max number of bits in a code + 1 */ 7 EOB = 256, /* end of block symbol */ 8 Nlit = 256, /* number of lit codes */ 9 Nlen = 29, /* number of len codes */ 10 Nlitlen = Nlit + Nlen + 3, /* litlen codes + block end + 2 unused */ 11 Ndist = 30, /* number of distance codes */ 12 Nclen = 19, /* number of code length codes */ 13 MinMatch = 3, /* min match length */ 14 MaxMatch = 258, /* max match length */ 15 WinSize = 1 << 15, /* sliding window size */ 16 17 MaxChainLen = 256, /* max length of hash chain */ 18 HashBits = 13, 19 HashSize = 1 << HashBits, /* hash table size */ 20 BigDist = 1 << 12, /* max match distance for short match length */ 21 MaxDist = WinSize, 22 BlockSize = 1 << 15, /* TODO */ 23 SrcSize = 2*WinSize + MaxMatch, 24 DstSize = BlockSize + MaxMatch + 6, /* worst case compressed block size */ 25 LzSize = 1 << 13, /* lz buffer size */ 26 LzGuard = LzSize - 2, 27 LzLitFlag = 1 << 15 /* marks literal run length in lz buffer */ 28 }; 29 30 typedef struct { 31 ushort dist; 32 ushort len; 33 } Match; 34 35 typedef struct { 36 ushort n; 37 ushort bits; 38 } LzCode; 39 40 typedef struct { 41 int pos; /* position in input src */ 42 int startpos; /* block start pos in input src */ 43 int endpos; /* end of available bytes in src */ 44 int skip; /* skipped hash chain updates (until next iter) */ 45 Match prevm; /* previous (deferred) match */ 46 int state; /* prev return value */ 47 int eof; /* end of input */ 48 uchar *in; /* input data (not yet in src) */ 49 uchar *inend; 50 uint bits; /* for output */ 51 int nbits; /* for output */ 52 uchar *dst; /* compressed output (position in dstbuf) */ 53 uchar *dstbegin; /* start position of unflushed data in dstbuf */ 54 LzCode *lz; /* current pos in lzbuf */ 55 int nlit; /* literal run length in lzbuf */ 56 ushort head[HashSize]; /* position of hash chain heads */ 57 ushort chain[WinSize]; /* hash chain */ 58 ushort lfreq[Nlitlen]; 59 ushort dfreq[Ndist]; 60 uchar src[SrcSize]; /* input buf */ 61 uchar dstbuf[DstSize]; 62 LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */ 63 } State; 64 65 static uchar fixllen[Nlitlen]; /* fixed lit/len huffman code tree */ 66 static ushort fixlcode[Nlitlen]; 67 static uchar fixdlen[Ndist]; /* fixed distance huffman code tree */ 68 static ushort fixdcode[Ndist]; 69 70 /* base offset and extra bits tables */ 71 static uchar lenbits[Nlen] = { 72 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 73 }; 74 static ushort lenbase[Nlen] = { 75 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 76 }; 77 static uchar distbits[Ndist] = { 78 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 79 }; 80 static ushort distbase[Ndist] = { 81 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 82 }; 83 84 /* ordering of code lengths */ 85 static uchar clenorder[Nclen] = { 86 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 87 }; 88 89 90 static uint revcode(uint c, int n) { 91 int i; 92 uint r = 0; 93 94 for (i = 0; i < n; i++) { 95 r = (r << 1) | (c & 1); 96 c >>= 1; 97 } 98 return r; 99 } 100 101 /* build huffman code tree from code lengths */ 102 static void huffcodes(ushort *codes, const uchar *lens, int n) { 103 int c[CodeBits]; 104 int i, code, count; 105 106 /* count code lengths and calc first code for each length */ 107 for (i = 0; i < CodeBits; i++) 108 c[i] = 0; 109 for (i = 0; i < n; i++) 110 c[lens[i]]++; 111 for (code = 0, i = 1; i < CodeBits; i++) { 112 count = c[i]; 113 c[i] = code; 114 code += count; 115 if (code > (1 << i)) 116 abort(); /* over-subscribed */ 117 code <<= 1; 118 } 119 if (code < (1 << i)) 120 /* incomplete */; 121 122 for (i = 0; i < n; i++) 123 if (lens[i]) 124 codes[i] = revcode(c[lens[i]]++, lens[i]); 125 else 126 codes[i] = 0; 127 } 128 129 static int heapparent(int n) {return (n - 2)/4 * 2;} 130 static int heapchild(int n) {return 2 * n + 2;} 131 132 static int heappush(int *heap, int len, int w, int n) { 133 int p, c, tmp; 134 135 c = len; 136 heap[len++] = n; 137 heap[len++] = w; 138 while (c > 0) { 139 p = heapparent(c); 140 if (heap[c+1] < heap[p+1]) { 141 tmp = heap[c]; heap[c] = heap[p]; heap[p] = tmp; 142 tmp = heap[c+1]; heap[c+1] = heap[p+1]; heap[p+1] = tmp; 143 c = p; 144 } else 145 break; 146 } 147 return len; 148 } 149 150 static int heappop(int *heap, int len, int *w, int *n) { 151 int p, c, tmp; 152 153 *n = heap[0]; 154 *w = heap[1]; 155 heap[1] = heap[--len]; 156 heap[0] = heap[--len]; 157 p = 0; 158 for (;;) { 159 c = heapchild(p); 160 if (c >= len) 161 break; 162 if (c+2 < len && heap[c+3] < heap[c+1]) 163 c += 2; 164 if (heap[p+1] > heap[c+1]) { 165 tmp = heap[p]; heap[p] = heap[c]; heap[c] = tmp; 166 tmp = heap[p+1]; heap[p+1] = heap[c+1]; heap[c+1] = tmp; 167 } else 168 break; 169 p = c; 170 } 171 return len; 172 } 173 174 /* symbol frequencies -> code lengths (limited to 255) */ 175 static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) { 176 /* 2 <= nsym <= Nlitlen, log(nsym) <= limit <= CodeBits-1 */ 177 int parent[2*Nlitlen-1]; 178 int count[CodeBits]; 179 int heap[2*Nlitlen]; 180 int n, len, top, overflow; 181 int i, j; 182 int wi, wj; 183 184 for (n = 0; n < limit+1; n++) 185 count[n] = 0; 186 for (len = n = 0; n < nsym; n++) 187 if (freqs[n] > 0) 188 len = heappush(heap, len, freqs[n], n); 189 else 190 lens[n] = 0; 191 /* deflate: fewer than two symbols: add new */ 192 for (n = 0; len < 4; n++) 193 if (freqs[n] == 0) 194 len = heappush(heap, len, ++freqs[n], n); 195 /* build code tree */ 196 top = len; 197 for (n = nsym; len > 2; n++) { 198 len = heappop(heap, len, &wi, &i); 199 len = heappop(heap, len, &wj, &j); 200 parent[i] = n; 201 parent[j] = n; 202 len = heappush(heap, len, wi + wj, n); 203 /* keep an ordered list of nodes at the end */ 204 heap[len+1] = i; 205 heap[len] = j; 206 } 207 /* calc code lengths (deflate: with limit) */ 208 overflow = 0; 209 parent[--n] = 0; 210 for (i = 2; i < top; i++) { 211 n = heap[i]; 212 if (n >= nsym) { 213 /* overwrite parent index with length */ 214 parent[n] = parent[parent[n]] + 1; 215 if (parent[n] > limit) 216 overflow++; 217 } else { 218 lens[n] = parent[parent[n]] + 1; 219 if (lens[n] > limit) { 220 lens[n] = limit; 221 overflow++; 222 } 223 count[lens[n]]++; 224 } 225 } 226 if (overflow == 0) 227 return; 228 /* modify code tree to fix overflow (from zlib) */ 229 while (overflow > 0) { 230 for (n = limit-1; count[n] == 0; n--); 231 count[n]--; 232 count[n+1] += 2; 233 count[limit]--; 234 overflow -= 2; 235 } 236 for (len = limit; len > 0; len--) 237 for (i = count[len]; i > 0;) { 238 n = heap[--top]; 239 if (n < nsym) { 240 lens[n] = len; 241 i--; 242 } 243 } 244 } 245 246 /* output n (<= 16) bits */ 247 static void putbits(State *s, uint bits, int n) { 248 s->bits |= bits << s->nbits; 249 s->nbits += n; 250 while (s->nbits >= 8) { 251 *s->dst++ = s->bits & 0xff; 252 s->bits >>= 8; 253 s->nbits -= 8; 254 } 255 } 256 257 /* run length encode literal and dist code lengths into codes and extra */ 258 static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *dlen, int ndist) { 259 int i, c, r, rr; 260 int n = 0; 261 262 for (i = 0; i < nlit; i++) 263 codes[i] = llen[i]; 264 for (i = 0; i < ndist; i++) 265 codes[nlit + i] = dlen[i]; 266 for (i = 0; i < nlit + ndist;) { 267 c = codes[i]; 268 for (r = 1; i + r < nlit + ndist && codes[i + r] == c; r++); 269 i += r; 270 if (c == 0) { 271 while (r >= 11) { 272 rr = r > 138 ? 138 : r; 273 codes[n] = 18; 274 extra[n++] = rr - 11; 275 r -= rr; 276 } 277 if (r >= 3) { 278 codes[n] = 17; 279 extra[n++] = r - 3; 280 r = 0; 281 } 282 } 283 while (r--) { 284 codes[n++] = c; 285 while (r >= 3) { 286 rr = r > 6 ? 6 : r; 287 codes[n] = 16; 288 extra[n++] = rr - 3; 289 r -= rr; 290 } 291 } 292 } 293 return n; 294 } 295 296 /* compress block data into s->dstbuf using given codes */ 297 static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar *dlen) { 298 int n; 299 LzCode *lz; 300 uchar *p; 301 302 for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++) 303 if (lz->bits & LzLitFlag) 304 for (n = lz->n; n > 0; n--, p++) 305 putbits(s, lcode[*p], llen[*p]); 306 else { 307 p += lenbase[lz->n] + lz->bits; 308 putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]); 309 putbits(s, lz->bits, lenbits[lz->n]); 310 lz++; 311 putbits(s, dcode[lz->n], dlen[lz->n]); 312 putbits(s, lz->bits, distbits[lz->n]); 313 } 314 putbits(s, lcode[EOB], llen[EOB]); 315 } 316 317 /* build code trees and select dynamic/fixed/uncompressed block compression */ 318 static void deflate_block(State *s) { 319 uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist]; 320 uchar llen[Nlitlen], dlen[Ndist], clen[Nclen]; 321 ushort cfreq[Nclen]; 322 /* freq can be overwritten by code */ 323 ushort *lcode = s->lfreq, *dcode = s->dfreq, *ccode = cfreq; 324 int i, c, n, ncodes; 325 int nlit, ndist, nclen; 326 LzCode *lz; 327 uchar *p; 328 int dynsize, fixsize, uncsize; 329 int blocklen = s->pos - s->startpos; 330 /* int dyntree; */ 331 332 /* calc dynamic codes */ 333 hufflens(llen, s->lfreq, Nlitlen, CodeBits-1); 334 hufflens(dlen, s->dfreq, Ndist, CodeBits-1); 335 huffcodes(lcode, llen, Nlitlen); 336 huffcodes(dcode, dlen, Ndist); 337 for (nlit = Nlitlen; nlit > Nlit && llen[nlit-1] == 0; nlit--); 338 for (ndist = Ndist; ndist > 1 && dlen[ndist-1] == 0; ndist--); 339 ncodes = clencodes(codes, extra, llen, nlit, dlen, ndist); 340 memset(cfreq, 0, sizeof(cfreq)); 341 for (i = 0; i < ncodes; i++) 342 cfreq[codes[i]]++; 343 hufflens(clen, cfreq, Nclen, 7); 344 huffcodes(ccode, clen, Nclen); 345 for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--); 346 347 /* calc compressed size */ 348 uncsize = 3 + 16 + 8 * blocklen + (16 - 3 - s->nbits) % 8; /* byte aligned */ 349 fixsize = 3; 350 dynsize = 3 + 5 + 5 + 4 + 3 * nclen; 351 for (i = 0; i < ncodes; i++) { 352 c = codes[i]; 353 dynsize += clen[c]; 354 if (c == 16) 355 dynsize += 2; 356 if (c == 17) 357 dynsize += 3; 358 if (c == 18) 359 dynsize += 7; 360 } 361 /* dyntree = dynsize - 3; */ 362 for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++) 363 if (lz->bits & LzLitFlag) 364 for (n = lz->n; n > 0; n--, p++) { 365 fixsize += fixllen[*p]; 366 dynsize += llen[*p]; 367 } 368 else { 369 p += lenbase[lz->n] + lz->bits; 370 fixsize += fixllen[Nlit + lz->n + 1]; 371 dynsize += llen[Nlit + lz->n + 1]; 372 fixsize += lenbits[lz->n]; 373 dynsize += lenbits[lz->n]; 374 lz++; 375 fixsize += fixdlen[lz->n]; 376 dynsize += dlen[lz->n]; 377 fixsize += distbits[lz->n]; 378 dynsize += distbits[lz->n]; 379 } 380 fixsize += fixllen[EOB]; 381 dynsize += llen[EOB]; 382 383 /* emit block */ 384 putbits(s, s->eof && s->pos == s->endpos, 1); 385 if (dynsize < fixsize && dynsize < uncsize) { 386 /* dynamic code */ 387 putbits(s, 2, 2); 388 putbits(s, nlit - 257, 5); 389 putbits(s, ndist - 1, 5); 390 putbits(s, nclen - 4, 4); 391 for (i = 0; i < nclen; i++) 392 putbits(s, clen[clenorder[i]], 3); 393 for (i = 0; i < ncodes; i++) { 394 c = codes[i]; 395 putbits(s, ccode[c], clen[c]); 396 if (c == 16) 397 putbits(s, extra[i], 2); 398 if (c == 17) 399 putbits(s, extra[i], 3); 400 if (c == 18) 401 putbits(s, extra[i], 7); 402 } 403 putblock(s, lcode, llen, dcode, dlen); 404 } else if (fixsize < uncsize) { 405 /* fixed code */ 406 putbits(s, 1, 2); 407 putblock(s, fixlcode, fixllen, fixdcode, fixdlen); 408 } else { 409 /* uncompressed */ 410 putbits(s, 0, 2); 411 putbits(s, 0, 7); /* align to byte boundary */ 412 s->nbits = 0; 413 putbits(s, blocklen, 16); 414 putbits(s, ~blocklen & 0xffff, 16); 415 memcpy(s->dst, s->src + s->startpos, blocklen); 416 s->dst += blocklen; 417 } 418 /* 419 fprintf(stderr, "blen:%d [%d,%d] lzlen:%d dynlen:%d (tree:%d rate:%.3f) fixlen:%d (rate:%.3f) unclen:%d (rate:%.3f)\n", 420 blocklen, s->startpos, s->pos, s->lz - s->lzbuf, dynsize, dyntree, dynsize/(float)blocklen, 421 fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen); 422 */ 423 } 424 425 /* find n in base */ 426 static int bisect(ushort *base, int len, int n) { 427 int lo = 0; 428 int hi = len; 429 int k; 430 431 while (lo < hi) { 432 k = (lo + hi) / 2; 433 if (n < base[k]) 434 hi = k; 435 else 436 lo = k + 1; 437 } 438 return lo - 1; 439 } 440 441 /* add literal run length to lzbuf */ 442 static void flushlit(State *s) { 443 if (s->nlit) { 444 s->lz->bits = LzLitFlag; 445 s->lz->n = s->nlit; 446 s->lz++; 447 s->nlit = 0; 448 } 449 } 450 451 /* add match to lzbuf and update freq counts */ 452 static void recordmatch(State *s, Match m) { 453 int n; 454 455 /*fprintf(stderr, "m %d %d\n", m.len, m.dist);*/ 456 flushlit(s); 457 n = bisect(lenbase, Nlen, m.len); 458 s->lz->n = n; 459 s->lz->bits = m.len - lenbase[n]; 460 s->lz++; 461 s->lfreq[Nlit + n + 1]++; 462 n = bisect(distbase, Ndist, m.dist); 463 s->lz->n = n; 464 s->lz->bits = m.dist - distbase[n]; 465 s->lz++; 466 s->dfreq[n]++; 467 } 468 469 /* update literal run length */ 470 static void recordlit(State *s, int c) { 471 /*fprintf(stderr, "l %c\n", c);*/ 472 s->nlit++; 473 s->lfreq[c]++; 474 } 475 476 /* multiplicative hash (using a prime close to golden ratio * 2^32) */ 477 static int gethash(uchar *p) { 478 return (0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits)) % HashSize; 479 } 480 481 /* update hash chain at the current position */ 482 static int updatechain(State *s) { 483 int hash, next = 0, p = s->pos, i; 484 485 if (s->endpos - p < MinMatch) 486 p = s->endpos - MinMatch; 487 for (i = s->pos - s->skip; i <= p; i++) { 488 hash = gethash(s->src + i); 489 next = s->head[hash]; 490 s->head[hash] = i; 491 if (next >= i || i - next >= MaxDist) 492 next = 0; 493 s->chain[i % WinSize] = next; 494 } 495 s->skip = 0; 496 return next; 497 } 498 499 /* find longest match, next position in the hash chain is given */ 500 static Match getmatch(State *s, int next) { 501 Match m = {0, MinMatch-1}; 502 int len; 503 int limit = s->pos - MaxDist; 504 int chainlen = MaxChainLen; 505 uchar *q; 506 uchar *p = s->src + s->pos; 507 uchar *end = p + MaxMatch; 508 509 do { 510 q = s->src + next; 511 /*fprintf(stderr,"match: next:%d pos:%d limit:%d\n", next, s->pos, limit);*/ 512 /* next match should be at least m.len+1 long */ 513 if (q[m.len] != p[m.len] || q[m.len-1] != p[m.len-1] || q[0] != p[0]) 514 continue; 515 while (++p != end && *++q == *p); 516 len = MaxMatch - (end - p); 517 p -= len; 518 /*fprintf(stderr,"match: len:%d dist:%d\n", len, s->pos - next);*/ 519 if (len > m.len) { 520 m.dist = s->pos - next; 521 m.len = len; 522 if (s->pos + len >= s->endpos) { /* TODO: overflow */ 523 m.len = s->endpos - s->pos; 524 return m; 525 } 526 if (len == MaxMatch) 527 return m; 528 } 529 } while ((next = s->chain[next % WinSize]) > limit && --chainlen); 530 if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist)) 531 m.len = 0; 532 return m; 533 } 534 535 static void startblock(State *s) { 536 s->startpos = s->pos; 537 s->dst = s->dstbegin = s->dstbuf; 538 s->lz = s->lzbuf; 539 s->nlit = 0; 540 memset(s->lfreq, 0, sizeof(s->lfreq)); 541 memset(s->dfreq, 0, sizeof(s->dfreq)); 542 s->lfreq[EOB]++; 543 } 544 545 static int shiftwin(State *s) { 546 int n; 547 548 if (s->startpos < WinSize) 549 return 0; 550 memmove(s->src, s->src + WinSize, SrcSize - WinSize); 551 for (n = 0; n < HashSize; n++) 552 s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0; 553 for (n = 0; n < WinSize; n++) 554 s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0; 555 s->pos -= WinSize; 556 s->startpos -= WinSize; 557 s->endpos -= WinSize; 558 return 1; 559 } 560 561 static int endblock(State *s) { 562 if ((s->pos >= 2*WinSize && !shiftwin(s)) || s->pos - s->startpos >= BlockSize || 563 s->lz - s->lzbuf >= LzGuard || (s->eof && s->pos == s->endpos)) { 564 /* deflate block */ 565 flushlit(s); 566 if (s->prevm.len) 567 s->pos--; 568 deflate_block(s); 569 if (s->eof && s->pos == s->endpos) 570 putbits(s, 0, 7); 571 return 1; 572 } 573 return 0; 574 } 575 576 static int fillsrc(State *s) { 577 int n, k; 578 579 if (s->endpos < SrcSize && !s->eof) { 580 n = SrcSize - s->endpos; 581 k = s->inend - s->in; 582 if (n > k) 583 n = k; 584 memcpy(s->src + s->endpos, s->in, n); 585 s->in += n; 586 s->endpos += n; 587 if (s->endpos < SrcSize) 588 return 0; 589 } 590 return 1; 591 } 592 593 static int calcguard(State *s) { 594 int p = s->endpos - MaxMatch; 595 int q = s->startpos + BlockSize; 596 597 return p < q ? p : q; 598 } 599 600 /* deflate compress from s->src into s->dstbuf */ 601 static int deflate_state(State *s) { 602 Match m; 603 int next; 604 int guard; 605 606 if (s->state == FlateIn) 607 s->eof = s->in == s->inend; 608 else if (s->state == FlateOut) { 609 if (s->dstbegin < s->dst) 610 return (s->state = FlateOut); 611 if (s->eof && s->pos == s->endpos) 612 return (s->state = FlateOk); 613 startblock(s); 614 if (s->prevm.len) 615 s->pos++; 616 } else 617 return s->state; 618 619 guard = calcguard(s); 620 for (;;) { 621 if (s->pos >= guard || s->lz - s->lzbuf >= LzGuard) { 622 /*fprintf(stderr,"guard:%d pos:%d len:%d lzlen:%d end:%d start:%d nin:%d eof:%d\n", guard, s->pos, s->pos - s->startpos, s->lz - s->lzbuf, s->endpos, s->startpos, s->inend - s->in, s->eof);*/ 623 if (endblock(s)) 624 return (s->state = FlateOut); 625 if (!fillsrc(s)) 626 return (s->state = FlateIn); 627 guard = calcguard(s); 628 } 629 next = updatechain(s); 630 if (next) 631 m = getmatch(s, next); 632 if (next && m.len > s->prevm.len) { 633 if (s->prevm.len) 634 recordlit(s, s->src[s->pos-1]); 635 s->prevm = m; 636 } else if (s->prevm.len) { 637 recordmatch(s, s->prevm); 638 s->skip = s->prevm.len - 2; 639 s->prevm.len = 0; 640 s->pos += s->skip; 641 } else 642 recordlit(s, s->src[s->pos]); 643 s->pos++; 644 } 645 } 646 647 /* alloc and init state */ 648 static State *alloc_state(void) { 649 State *s = malloc(sizeof(State)); 650 int i; 651 652 if (!s) 653 return s; 654 memset(s->chain, 0, sizeof(s->chain)); 655 memset(s->head, 0, sizeof(s->head)); 656 s->bits = s->nbits = 0; 657 /* TODO: globals */ 658 if (fixllen[0] == 0) { 659 for (i = 0; i < 144; i++) 660 fixllen[i] = 8; 661 for (; i < 256; i++) 662 fixllen[i] = 9; 663 for (; i < 280; i++) 664 fixllen[i] = 7; 665 for (; i < Nlitlen; i++) 666 fixllen[i] = 8; 667 for (i = 0; i < Ndist; i++) 668 fixdlen[i] = 5; 669 huffcodes(fixlcode, fixllen, Nlitlen); 670 huffcodes(fixdcode, fixdlen, Ndist); 671 } 672 s->state = FlateOut; 673 s->in = s->inend = 0; 674 s->dst = s->dstbegin = s->dstbuf; 675 s->pos = s->startpos = s->endpos = WinSize; 676 s->eof = 0; 677 s->skip = 0; 678 s->prevm.len = 0; 679 return s; 680 } 681 682 683 /* extern */ 684 685 int deflate(FlateStream *stream) { 686 State *s = stream->state; 687 int n, k; 688 689 if (stream->err) { 690 free(s); 691 stream->state = 0; 692 return FlateErr; 693 } 694 if (!s) { 695 s = stream->state = alloc_state(); 696 if (!s) 697 return stream->err = "no mem.", FlateErr; 698 } 699 if (stream->nin) { 700 s->in = stream->in; 701 s->inend = s->in + stream->nin; 702 stream->nin = 0; 703 } 704 n = deflate_state(s); 705 if (n == FlateOut) { 706 k = s->dst - s->dstbegin; 707 if (k < stream->nout) 708 stream->nout = k; 709 memcpy(stream->out, s->dstbegin, stream->nout); 710 s->dstbegin += stream->nout; 711 } 712 if (n == FlateOk || n == FlateErr) { 713 free(s); 714 stream->state = 0; 715 } 716 return n; 717 }