summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSimon Tatham <anakin@pobox.com>2017-09-29 14:04:42 +0100
committerSimon Tatham <anakin@pobox.com>2017-09-29 14:06:29 +0100
commit12107a73eff6b6f6a861ba156e94e13d9bcdbe56 (patch)
tree16e9f5015dff0efb66d62c768a4193986e8bc015
parent7ed66467ffe6dde9f4ca4975845d129772e4a851 (diff)
downloadhalibut-12107a73eff6b6f6a861ba156e94e13d9bcdbe56.zip
halibut-12107a73eff6b6f6a861ba156e94e13d9bcdbe56.tar.gz
halibut-12107a73eff6b6f6a861ba156e94e13d9bcdbe56.tar.bz2
halibut-12107a73eff6b6f6a861ba156e94e13d9bcdbe56.tar.xz
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.
-rw-r--r--huffman.c15
1 files changed, 13 insertions, 2 deletions
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;
/*