aboutsummaryrefslogtreecommitdiff
path: root/trees.c
diff options
context:
space:
mode:
authorMark Adler <madler@alumni.caltech.edu>2018-04-17 22:09:22 -0700
committerMark Adler <madler@alumni.caltech.edu>2018-04-19 19:47:11 -0700
commit5c44459c3b28a9bd3283aaceab7c615f8020c531 (patch)
tree7a5d9e7a3fd8c0438f592de2f3ee89a91d2cd06a /trees.c
parente99813dbfe9a09e33d42e8da9e550a0c4b7ff734 (diff)
downloadzlib-5c44459c3b28a9bd3283aaceab7c615f8020c531.tar.gz
zlib-5c44459c3b28a9bd3283aaceab7c615f8020c531.tar.bz2
zlib-5c44459c3b28a9bd3283aaceab7c615f8020c531.zip
Fix a bug that can crash deflate on some input when using Z_FIXED.
This bug was reported by Danilo Ramos of Eideticom, Inc. It has lain in wait 13 years before being found! The bug was introduced in zlib 1.2.2.2, with the addition of the Z_FIXED option. That option forces the use of fixed Huffman codes. For rare inputs with a large number of distant matches, the pending buffer into which the compressed data is written can overwrite the distance symbol table which it overlays. That results in corrupted output due to invalid distances, and can result in out-of-bound accesses, crashing the application. The fix here combines the distance buffer and literal/length buffers into a single symbol buffer. Now three bytes of pending buffer space are opened up for each literal or length/distance pair consumed, instead of the previous two bytes. This assures that the pending buffer cannot overwrite the symbol table, since the maximum fixed code compressed length/distance is 31 bits, and since there are four bytes of pending space for every three bytes of symbol space.
Diffstat (limited to 'trees.c')
-rw-r--r--trees.c50
1 files changed, 14 insertions, 36 deletions
diff --git a/trees.c b/trees.c
index 4f4a650..decaeb7 100644
--- a/trees.c
+++ b/trees.c
@@ -416,7 +416,7 @@ local void init_block(s)
416 416
417 s->dyn_ltree[END_BLOCK].Freq = 1; 417 s->dyn_ltree[END_BLOCK].Freq = 1;
418 s->opt_len = s->static_len = 0L; 418 s->opt_len = s->static_len = 0L;
419 s->last_lit = s->matches = 0; 419 s->sym_next = s->matches = 0;
420} 420}
421 421
422#define SMALLEST 1 422#define SMALLEST 1
@@ -948,7 +948,7 @@ void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last)
948 948
949 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 949 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
950 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 950 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
951 s->last_lit)); 951 s->sym_next / 3));
952 952
953 if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 953 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
954 954
@@ -1017,8 +1017,9 @@ int ZLIB_INTERNAL _tr_tally (s, dist, lc)
1017 unsigned dist; /* distance of matched string */ 1017 unsigned dist; /* distance of matched string */
1018 unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 1018 unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
1019{ 1019{
1020 s->d_buf[s->last_lit] = (ush)dist; 1020 s->sym_buf[s->sym_next++] = dist;
1021 s->l_buf[s->last_lit++] = (uch)lc; 1021 s->sym_buf[s->sym_next++] = dist >> 8;
1022 s->sym_buf[s->sym_next++] = lc;
1022 if (dist == 0) { 1023 if (dist == 0) {
1023 /* lc is the unmatched char */ 1024 /* lc is the unmatched char */
1024 s->dyn_ltree[lc].Freq++; 1025 s->dyn_ltree[lc].Freq++;
@@ -1033,30 +1034,7 @@ int ZLIB_INTERNAL _tr_tally (s, dist, lc)
1033 s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++; 1034 s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
1034 s->dyn_dtree[d_code(dist)].Freq++; 1035 s->dyn_dtree[d_code(dist)].Freq++;
1035 } 1036 }
1036 1037 return (s->sym_next == s->sym_end);
1037#ifdef TRUNCATE_BLOCK
1038 /* Try to guess if it is profitable to stop the current block here */
1039 if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
1040 /* Compute an upper bound for the compressed length */
1041 ulg out_length = (ulg)s->last_lit*8L;
1042 ulg in_length = (ulg)((long)s->strstart - s->block_start);
1043 int dcode;
1044 for (dcode = 0; dcode < D_CODES; dcode++) {
1045 out_length += (ulg)s->dyn_dtree[dcode].Freq *
1046 (5L+extra_dbits[dcode]);
1047 }
1048 out_length >>= 3;
1049 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1050 s->last_lit, in_length, out_length,
1051 100L - out_length*100L/in_length));
1052 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
1053 }
1054#endif
1055 return (s->last_lit == s->lit_bufsize-1);
1056 /* We avoid equality with lit_bufsize because of wraparound at 64K
1057 * on 16 bit machines and because stored blocks are restricted to
1058 * 64K-1 bytes.
1059 */
1060} 1038}
1061 1039
1062/* =========================================================================== 1040/* ===========================================================================
@@ -1069,13 +1047,14 @@ local void compress_block(s, ltree, dtree)
1069{ 1047{
1070 unsigned dist; /* distance of matched string */ 1048 unsigned dist; /* distance of matched string */
1071 int lc; /* match length or unmatched char (if dist == 0) */ 1049 int lc; /* match length or unmatched char (if dist == 0) */
1072 unsigned lx = 0; /* running index in l_buf */ 1050 unsigned sx = 0; /* running index in sym_buf */
1073 unsigned code; /* the code to send */ 1051 unsigned code; /* the code to send */
1074 int extra; /* number of extra bits to send */ 1052 int extra; /* number of extra bits to send */
1075 1053
1076 if (s->last_lit != 0) do { 1054 if (s->sym_next != 0) do {
1077 dist = s->d_buf[lx]; 1055 dist = s->sym_buf[sx++] & 0xff;
1078 lc = s->l_buf[lx++]; 1056 dist += (unsigned)(s->sym_buf[sx++] & 0xff) << 8;
1057 lc = s->sym_buf[sx++];
1079 if (dist == 0) { 1058 if (dist == 0) {
1080 send_code(s, lc, ltree); /* send a literal byte */ 1059 send_code(s, lc, ltree); /* send a literal byte */
1081 Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 1060 Tracecv(isgraph(lc), (stderr," '%c' ", lc));
@@ -1100,11 +1079,10 @@ local void compress_block(s, ltree, dtree)
1100 } 1079 }
1101 } /* literal or match pair ? */ 1080 } /* literal or match pair ? */
1102 1081
1103 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 1082 /* Check that the overlay between pending_buf and sym_buf is ok: */
1104 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, 1083 Assert(s->pending < s->lit_bufsize + sx, "pendingBuf overflow");
1105 "pendingBuf overflow");
1106 1084
1107 } while (lx < s->last_lit); 1085 } while (sx < s->sym_next);
1108 1086
1109 send_code(s, END_BLOCK, ltree); 1087 send_code(s, END_BLOCK, ltree);
1110} 1088}