  Text compression schemes and compact data structures usually combine
sophisticated probability models with basic coding methods whose average
codeword length closely match the entropy of known distributions. In the
frequent case where basic coding represents run-lengths of outcomes that have
probability $p$, i.e. the geometric distribution $\Pr(i)=p^i(1-p)$, a
\emph{Golomb code} is an optimal instantaneous code, which has the additional
advantage that codewords can be computed using only an integer parameter
calculated from $p$, without need for a large or sophisticated data structure.
Golomb coding does not, however, gracefully handle the case where run-lengths
are bounded by a known integer~$n$. In this case, codewords allocated for the
case $i>n$ are wasted. While negligible for large $n$, this makes Golomb coding
unattractive in situations where $n$ is recurrently small, e.g., when
representing many short lists of integers drawn from limited ranges, or when
the range of $n$ is narrowed down by a recursive algorithm. We address the
problem of choosing a code for this case, considering efficiency from both
information-theoretic and computational perspectives, and arrive at a simple
code that allows computing a codeword using only $O(1)$ simple computer
operations and $O(1)$ machine words. We demonstrate experimentally that the
resulting representation length is very close (equal in a majority of tested
cases) to the optimal Huffman code, to the extent that the expected difference
is practically negligible. We describe efficient branch-free implementation of
encoding and decoding.
