+ is->bitbuf = 0;
+ is->num_filled_bits = 0;
+ is->in = in + in_limit;
+ is->num_le16_remaining = in_limit;
+}
+
+/* Ensures that @num_bits bits are buffered in the input bitstream. */
+static int
+lzms_input_bitstream_ensure_bits(struct lzms_input_bitstream *is,
+ unsigned num_bits)
+{
+ while (is->num_filled_bits < num_bits) {
+ u64 next;
+
+ LZMS_ASSERT(is->num_filled_bits + 16 <= sizeof(is->bitbuf) * 8);
+
+ if (unlikely(is->num_le16_remaining == 0))
+ return -1;
+
+ next = get_unaligned_u16_le(--is->in);
+ is->num_le16_remaining--;
+
+ is->bitbuf |= next << (sizeof(is->bitbuf) * 8 - is->num_filled_bits - 16);
+ is->num_filled_bits += 16;
+ }
+ return 0;
+
+}
+
+/* Returns the next @num_bits bits that are buffered in the input bitstream. */
+static u32
+lzms_input_bitstream_peek_bits(struct lzms_input_bitstream *is,
+ unsigned num_bits)
+{
+ LZMS_ASSERT(is->num_filled_bits >= num_bits);
+ return is->bitbuf >> (sizeof(is->bitbuf) * 8 - num_bits);
+}
+
+/* Removes the next @num_bits bits that are buffered in the input bitstream. */
+static void
+lzms_input_bitstream_remove_bits(struct lzms_input_bitstream *is,
+ unsigned num_bits)
+{
+ LZMS_ASSERT(is->num_filled_bits >= num_bits);
+ is->bitbuf <<= num_bits;
+ is->num_filled_bits -= num_bits;
+}
+
+/* Removes and returns the next @num_bits bits that are buffered in the input
+ * bitstream. */
+static u32
+lzms_input_bitstream_pop_bits(struct lzms_input_bitstream *is,
+ unsigned num_bits)
+{
+ u32 bits = lzms_input_bitstream_peek_bits(is, num_bits);
+ lzms_input_bitstream_remove_bits(is, num_bits);
+ return bits;
+}
+
+/* Reads the next @num_bits from the input bitstream. */
+static u32
+lzms_input_bitstream_read_bits(struct lzms_input_bitstream *is,
+ unsigned num_bits)
+{
+ if (unlikely(lzms_input_bitstream_ensure_bits(is, num_bits)))
+ return 0;
+ return lzms_input_bitstream_pop_bits(is, num_bits);
+}
+
+/* Initialize the range decoder @rd to read forwards from the specified
+ * compressed data buffer @in that is @in_limit 16-bit integers long. */
+static void
+lzms_range_decoder_raw_init(struct lzms_range_decoder_raw *rd,
+ const le16 *in, size_t in_limit)
+{
+ rd->range = 0xffffffff;
+ rd->code = ((u32)get_unaligned_u16_le(&in[0]) << 16) |
+ ((u32)get_unaligned_u16_le(&in[1]) << 0);
+ rd->in = in + 2;
+ rd->num_le16_remaining = in_limit - 2;
+}
+
+/* Ensures the current range of the range decoder has at least 16 bits of
+ * precision. */
+static int
+lzms_range_decoder_raw_normalize(struct lzms_range_decoder_raw *rd)
+{
+ if (rd->range <= 0xffff) {
+ rd->range <<= 16;
+ if (unlikely(rd->num_le16_remaining == 0))
+ return -1;
+ rd->code = (rd->code << 16) | get_unaligned_u16_le(rd->in++);
+ rd->num_le16_remaining--;
+ }
+ return 0;
+}
+
+/* Decode and return the next bit from the range decoder (raw version).
+ *
+ * @prob is the chance out of LZMS_PROBABILITY_MAX that the next bit is 0.
+ */
+static int
+lzms_range_decoder_raw_decode_bit(struct lzms_range_decoder_raw *rd, u32 prob)
+{
+ u32 bound;
+
+ /* Ensure the range has at least 16 bits of precision. */
+ lzms_range_decoder_raw_normalize(rd);
+
+ /* Based on the probability, calculate the bound between the 0-bit
+ * region and the 1-bit region of the range. */
+ bound = (rd->range >> LZMS_PROBABILITY_BITS) * prob;
+
+ if (rd->code < bound) {
+ /* Current code is in the 0-bit region of the range. */
+ rd->range = bound;
+ return 0;
+ } else {
+ /* Current code is in the 1-bit region of the range. */
+ rd->range -= bound;
+ rd->code -= bound;
+ return 1;
+ }
+}
+
+/* Decode and return the next bit from the range decoder. This wraps around
+ * lzms_range_decoder_raw_decode_bit() to handle using and updating the
+ * appropriate probability table. */
+static int
+lzms_range_decode_bit(struct lzms_range_decoder *dec)
+{
+ struct lzms_probability_entry *prob_entry;
+ u32 prob;
+ int bit;
+
+ /* Load the probability entry corresponding to the current state. */
+ prob_entry = &dec->prob_entries[dec->state];
+
+ /* Get the probability that the next bit is 0. */
+ prob = lzms_get_probability(prob_entry);
+
+ /* Decode the next bit. */
+ bit = lzms_range_decoder_raw_decode_bit(dec->rd, prob);
+
+ /* Update the state and probability entry based on the decoded bit. */
+ dec->state = (((dec->state << 1) | bit) & dec->mask);
+ lzms_update_probability_entry(prob_entry, bit);
+
+ /* Return the decoded bit. */
+ return bit;
+}
+
+
+/* Build the decoding table for a new adaptive Huffman code using the alphabet
+ * used in the specified Huffman decoder, with the symbol frequencies
+ * dec->sym_freqs. */
+static void
+lzms_rebuild_adaptive_huffman_code(struct lzms_huffman_decoder *dec)
+{
+
+ /* XXX: This implementation makes use of code already implemented for
+ * the XPRESS and LZX compression formats. However, since for the
+ * adaptive codes used in LZMS we don't actually need the explicit codes
+ * themselves, only the decode tables, it may be possible to optimize
+ * this by somehow directly building or updating the Huffman decode
+ * table. This may be a worthwhile optimization because the adaptive
+ * codes change many times throughout a decompression run. */
+ LZMS_DEBUG("Rebuilding adaptive Huffman code (num_syms=%u)",
+ dec->num_syms);
+ make_canonical_huffman_code(dec->num_syms, LZMS_MAX_CODEWORD_LEN,
+ dec->sym_freqs, dec->lens, dec->codewords);
+#if defined(ENABLE_LZMS_DEBUG)
+ int ret =
+#endif
+ make_huffman_decode_table(dec->decode_table, dec->num_syms,
+ LZMS_DECODE_TABLE_BITS, dec->lens,
+ LZMS_MAX_CODEWORD_LEN);
+ LZMS_ASSERT(ret == 0);
+}
+
+/* Decode and return the next Huffman-encoded symbol from the LZMS-compressed
+ * block using the specified Huffman decoder. */
+static u32
+lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec)
+{
+ const u16 *decode_table = dec->decode_table;
+ struct lzms_input_bitstream *is = dec->is;
+ u16 entry;
+ u16 key_bits;
+ u16 sym;
+
+ /* The Huffman codes used in LZMS are adaptive and must be rebuilt
+ * whenever a certain number of symbols have been read. Each such
+ * rebuild uses the current symbol frequencies, but the format also
+ * requires that the symbol frequencies be halved after each code
+ * rebuild. This diminishes the effect of old symbols on the current
+ * Huffman codes, thereby causing the Huffman codes to be more locally
+ * adaptable. */
+ if (dec->num_syms_read == dec->rebuild_freq) {
+ lzms_rebuild_adaptive_huffman_code(dec);
+ for (unsigned i = 0; i < dec->num_syms; i++) {
+ dec->sym_freqs[i] >>= 1;
+ dec->sym_freqs[i] += 1;