+/*
+ * This is a decompressor for the LZMS compression format used by Microsoft.
+ * This format is not documented, but it is one of the formats supported by the
+ * compression API available in Windows 8, and as of Windows 8 it is one of the
+ * formats that can be used in WIM files.
+ *
+ * This decompressor only implements "raw" decompression, which decompresses a
+ * single LZMS-compressed block. This behavior is the same as that of
+ * Decompress() in the Windows 8 compression API when using a compression handle
+ * created with CreateDecompressor() with the Algorithm parameter specified as
+ * COMPRESS_ALGORITHM_LZMS | COMPRESS_RAW. Presumably, non-raw LZMS data
+ * is a container format from which the locations and sizes (both compressed and
+ * uncompressed) of the constituent blocks can be determined.
+ *
+ * An LZMS-compressed block must be read in 16-bit little endian units from both
+ * directions. One logical bitstream starts at the front of the block and
+ * proceeds forwards. Another logical bitstream starts at the end of the block
+ * and proceeds backwards. Bits read from the forwards bitstream constitute
+ * range-encoded data, whereas bits read from the backwards bitstream constitute
+ * Huffman-encoded symbols or verbatim bits. For both bitstreams, the ordering
+ * of the bits within the 16-bit coding units is such that the first bit is the
+ * high-order bit and the last bit is the low-order bit.
+ *
+ * From these two logical bitstreams, an LZMS decompressor can reconstitute the
+ * series of items that make up the LZMS data representation. Each such item
+ * may be a literal byte or a match. Matches may be either traditional LZ77
+ * matches or "delta" matches, either of which can have its offset encoded
+ * explicitly or encoded via a reference to a recently used (repeat) offset.
+ *
+ * A traditional LZ match consists of a length and offset; it asserts that the
+ * sequence of bytes beginning at the current position and extending for the
+ * length is exactly equal to the equal-length sequence of bytes at the offset
+ * back in the window. On the other hand, a delta match consists of a length,
+ * raw offset, and power. It asserts that the sequence of bytes beginning at
+ * the current position and extending for the length is equal to the bytewise
+ * sum of the two equal-length sequences of bytes (2**power) and (raw_offset *
+ * 2**power) bytes before the current position, minus bytewise the sequence of
+ * bytes beginning at (2**power + raw_offset * 2**power) bytes before the
+ * current position. Although not generally as useful as traditional LZ
+ * matches, delta matches can be helpful on some types of data. Both LZ and
+ * delta matches may overlap with the current position; in fact, the minimum
+ * offset is 1, regardless of match length.
+ *
+ * For LZ matches, up to 3 repeat offsets are allowed, similar to some other
+ * LZ-based formats such as LZX and LZMA. They must updated in an LRU fashion,
+ * except for a quirk: updates to the queue must be delayed by one LZMS item,
+ * except for the removal of a repeat match. As a result, 4 entries are
+ * actually needed in the queue, even though it is only possible to decode
+ * references to the first 3 at any given time. The queue must be initialized
+ * to the offsets {1, 2, 3, 4}.
+ *
+ * Repeat delta matches are handled similarly, but for them there are two queues
+ * updated in lock-step: one for powers and one for raw offsets. The power
+ * queue must be initialized to {0, 0, 0, 0}, and the raw offset queue must be
+ * initialized to {1, 2, 3, 4}.
+ *
+ * Bits from the range decoder must be used to disambiguate item types. The
+ * range decoder must hold two state variables: the range, which must initially
+ * be set to 0xffffffff, and the current code, which must initially be set to
+ * the first 32 bits read from the forwards bitstream. The range must be
+ * maintained above 0xffff; when it falls below 0xffff, both the range and code
+ * must be left-shifted by 16 bits and the low 16 bits of the code must be
+ * filled in with the next 16 bits from the forwards bitstream.
+ *
+ * To decode each bit, the range decoder requires a probability that is
+ * logically a real number between 0 and 1. Multiplying this probability by the
+ * current range and taking the floor gives the bound between the 0-bit region
+ * of the range and the 1-bit region of the range. However, in LZMS,
+ * probabilities are restricted to values of n/64 where n is an integer is
+ * between 1 and 63 inclusively, so the implementation may use integer
+ * operations instead. Following calculation of the bound, if the current code
+ * is in the 0-bit region, the new range becomes the current code and the
+ * decoded bit is 0; otherwise, the bound must be subtracted from both the range
+ * and the code, and the decoded bit is 1. More information about range coding
+ * can be found at https://en.wikipedia.org/wiki/Range_encoding. Furthermore,
+ * note that the LZMA format also uses range coding and has public domain code
+ * available for it.
+ *
+ * The probability used to range-decode each bit must be taken from a table, of
+ * which one instance must exist for each distinct context in which a
+ * range-decoded bit is needed. At each call of the range decoder, the
+ * appropriate probability must be obtained by indexing the appropriate
+ * probability table with the last 4 (in the context disambiguating literals
+ * from matches), 5 (in the context disambiguating LZ matches from delta
+ * matches), or 6 (in all other contexts) bits recently range-decoded in that
+ * context, ordered such that the most recently decoded bit is the low-order bit
+ * of the index.
+ *
+ * Furthermore, each probability entry itself is variable, as its value must be
+ * maintained as n/64 where n is the number of 0 bits in the most recently
+ * decoded 64 bits with that same entry. This allows the compressed
+ * representation to adapt to the input and use fewer bits to represent the most
+ * likely data; note that LZMA uses a similar scheme. Initially, the most
+ * recently 64 decoded bits for each probability entry are assumed to be
+ * 0x0000000055555555 (high order to low order); therefore, all probabilities
+ * are initially 48/64. During the course of decoding, each probability may be
+ * updated to as low as 0/64 (as a result of reading many consecutive 1 bits
+ * with that entry) or as high as 64/64 (as a result of reading many consecutive
+ * 0 bits with that entry); however, probabilities of 0/64 and 64/64 cannot be
+ * used as-is but rather must be adjusted to 1/64 and 63/64, respectively,
+ * before being used for range decoding.
+ *
+ * Representations of the LZMS items themselves must be read from the backwards
+ * bitstream. For this, there are 5 different Huffman codes used:
+ *
+ * - The literal code, used for decoding literal bytes. Each of the 256
+ * symbols represents a literal byte. This code must be rebuilt whenever
+ * 1024 symbols have been decoded with it.
+ *
+ * - The LZ offset code, used for decoding the offsets of standard LZ77
+ * matches. Each symbol represents a position slot, which corresponds to a
+ * base value and some number of extra bits which must be read and added to
+ * the base value to reconstitute the full offset. The number of symbols in
+ * this code is the number of position slots needed to represent all possible
+ * offsets in the uncompressed block. This code must be rebuilt whenever
+ * 1024 symbols have been decoded with it.
+ *
+ * - The length code, used for decoding length symbols. Each of the 54 symbols
+ * represents a length slot, which corresponds to a base value and some
+ * number of extra bits which must be read and added to the base value to
+ * reconstitute the full length. This code must be rebuilt whenever 512
+ * symbols have been decoded with it.
+ *
+ * - The delta offset code, used for decoding the offsets of delta matches.
+ * Each symbol corresponds to a position slot, which corresponds to a base
+ * value and some number of extra bits which must be read and added to the
+ * base value to reconstitute the full offset. The number of symbols in this
+ * code is equal to the number of symbols in the LZ offset code. This code
+ * must be rebuilt whenever 1024 symbols have been decoded with it.
+ *
+ * - The delta power code, used for decoding the powers of delta matches. Each
+ * of the 8 symbols corresponds to a power. This code must be rebuilt
+ * whenever 512 symbols have been decoded with it.
+ *
+ * All the LZMS Huffman codes must be built adaptively based on symbol
+ * frequencies. Initially, each code must be built assuming that all symbols
+ * have equal frequency. Following that, each code must be rebuilt whenever a
+ * certain number of symbols has been decoded with it.
+ *
+ * In general, multiple valid Huffman codes can be constructed from a set of
+ * symbol frequencies. Like other compression formats such as XPRESS, LZX, and
+ * DEFLATE, the LZMS format solves this ambiguity by requiring that all Huffman
+ * codes be constructed in canonical form. This form requires that same-length
+ * codewords be lexicographically ordered the same way as the corresponding
+ * symbols and that all shorter codewords lexicographically precede longer
+ * codewords.
+ *
+ * Codewords in all the LZMS Huffman codes are limited to 15 bits. If the
+ * canonical code for a given set of symbol frequencies has any codewords longer
+ * than 15 bits, then all frequencies must be divided by 2, rounding up, and the
+ * code construction must be attempted again.
+ *
+ * An LZMS-compressed block seemingly cannot have a compressed size greater than
+ * or equal to the uncompressed size. In such cases the block must be stored
+ * uncompressed.
+ *
+ * After all LZMS items have been decoded, the data must be postprocessed to
+ * translate absolute address encoded in x86 instructions into their original
+ * relative addresses.
+ *
+ * Details omitted above can be found in the code. Note that in the absence of
+ * an official specification there is no guarantee that this decompressor
+ * handles all possible cases.
+ */
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "wimlib.h"
+#include "wimlib/compress_common.h"
+#include "wimlib/decompressor_ops.h"
+#include "wimlib/decompress_common.h"