From 12107a73eff6b6f6a861ba156e94e13d9bcdbe56 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Fri, 29 Sep 2017 14:04:42 +0100 Subject: Fill in a truncated comment in huffman.c. I just happened to run across this clearly unfinished paragraph in build_huffman_tree(), and when I wrote the rest of it, I realised that there was actually an implicit input constraint which I hadn't documented, relating the size of the symbol alphabet to the upper bound on Huffman code length. (Fortunately, Deflate never violates that constraint, because both of those values are constant in every Huffman tree it builds.) So I've also added a pair of assertions, one of which enforces that constraint. --- huffman.c | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'huffman.c') diff --git a/huffman.c b/huffman.c index 3fada10..58fcc60 100644 --- a/huffman.c +++ b/huffman.c @@ -274,11 +274,22 @@ void build_huffman_tree(int *freqs, unsigned char *lengths, * ---------------------------------- * maxprob - nactivesyms * - * rounded up, of course. And we'll only even be trying - * this if + * rounded up, of course. And we'll only even be trying this if + * smallestfreq <= totalfreq / maxprob, which is precisely the + * condition under which the numerator of this fraction is + * positive. + * + * (As for the denominator, that could only be negative if there + * were more than F_{n+2} symbols overall, in which case it + * _wouldn't_ be possible to avoid having a symbol with + * probability at most 1/F_{n+2}. So that is a constraint on the + * input parameters to this function, which we enforce by + * assertion.) */ num = totalfreq - smallestfreq * maxprob; denom = maxprob - nactivesyms; + assert(num > 0); /* this just restates the assert above */ + assert(denom > 0); /* this is a constraint on the function parameters */ adjust = (num + denom - 1) / denom; /* -- cgit v1.1