**diff options**

author | Simon Tatham <anakin@pobox.com> | 2017-09-29 14:04:42 +0100 |
---|---|---|

committer | Simon Tatham <anakin@pobox.com> | 2017-09-29 14:06:29 +0100 |

commit | 12107a73eff6b6f6a861ba156e94e13d9bcdbe56 (patch) | |

tree | 16e9f5015dff0efb66d62c768a4193986e8bc015 | |

parent | 7ed66467ffe6dde9f4ca4975845d129772e4a851 (diff) | |

download | halibut-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.c | 15 |

1 files changed, 13 insertions, 2 deletions

@@ -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; /* |