miniz_oxide accepts invalid literal/length trees

[fintelia]

This test runs fine against flate2's zlib backend but fails with the miniz_oxide backend:

let corrupt_input = &[
    120, 1, 237, 224, 144, 1, 36, 73, 146, 36, 73, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 122, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
];

flate2::Decompress::new(true)
    .decompress_vec(corrupt_input, &mut Vec::new(), flate2::FlushDecompress::Finish)
    .unwrap_err();

It is caused by an overly lax check in miniz_oxide of whether the set of symbol lengths are valid:

let mut used_symbols = 0;
let mut total = 0;
for i in 1..16 {
    used_symbols += total_symbols[i];
    total += total_symbols[i];
    total <<= 1;
    next_code[i + 1] = total;
}

if total != 65_536 && used_symbols > 1 {
    return Action::Jump(BadTotalSymbols);
}

By contrast, this is the check in the zlib library:

/* check for an over-subscribed or incomplete set of lengths */
left = 1;
for (len = 1; len <= MAXBITS; len++) {
    left <<= 1;
    left -= count[len];
    if (left < 0) return -1;        /* over-subscribed */
}
if (left > 0 && (type == CODES || max != 1))
    return -1;                      /* incomplete set */

The difference is that zlib only allows incomplete huffman trees for distance symbols, and only if the single element has length=1.

[oyvindln]

Hm, might be a carryover from the original miniz c code, will have to look into it.