! our WIM's LZX and LZMS resources are a dialect of our own (#76)

[Hawkynt]

#76 left the WIM container and its XPRESS resources readable by both tools that
own the format. The other two compression types are still ours alone:

$ wimlib-imagex verify ours-lzx.wim
[ERROR] Failed to decompress data!
$ 7z t ours-lzx.wim
ERROR: Cannot open the file as [wim] archive

Same for LZMS. Uncompressed, XPRESS and XPRESS-Huffman containers of the same
eight files pass both readers; only these two fail, and they fail in the
decompressor rather than anywhere in the container, which is now known good.

The cause is the same shape as the XPRESS one that #76 fixed: the encoders
round-trip against their own decoders and against nothing else. For LZX that
is now confirmed from two directions, because our LZX cabinets fail
cabextract as well — see the sibling issue. LzxCompressor serves CAB, CHM
and WIM, so one correct implementation settles all three.

LZMS has no other user here; it is WIM-only.

Both are worth doing with the harness #76 established: wimcapture <dir> out.wim --compress=LZX gives a byte-exact reference for any payload, a single
resource can be grafted into a reference container to test one chunk in
isolation, and the two readers have to be asked separately because each
tolerates something the other rejects.

Until then the writer's default and the archive-creation path use XPRESS,
which both readers accept, so nothing produced by default is unreadable
elsewhere. Asking for LZX or LZMS explicitly still yields a container only we
can read, which is why this is recorded rather than closed.

[Hawkynt]

LZX is fixed in 5c592e9; LZMS is still outstanding, so this stays open.

Four things were wrong at once, and they cancelled in our own round-trip.

The offset bias had the wrong sign. A position slot names a formatted
offset, two more than the distance — which is what leaves slots 0, 1 and 2 free
for the three remembered offsets. We added the two instead of taking it off, in
the encoder and again in the decoder, so read correctly every match we ever
wrote pointed four bytes past its data. wimlib's own stream settles it: it
encodes a distance of 4 as slot 5, whose base is 6, with an empty footer.

That sign also made slot 3 start at distance 5, so the match finder was told to
refuse distances of 2, 3 and 4 — the commonest matches there are. With the sign
right the reference payload went from 298 bytes to 54, against wimlib's 52.

An insurance word. The bit writer appended a zero word past the last real
one. 7-Zip compares the compressed size against what it consumed and rejects
the difference — it rejects wimlib's own chunks if you pad them the same way.

A tree of nothing. A block whose matches are all short uses no length
symbol, and we wrote the length tree as 249 zeros. wimlib refuses that outright.
Same fix as the deflate trees in #85: a second one-bit code.

No E8 filter. A WIM rewrites x86 call targets in every LZX chunk before
compressing, and a reader undoes it whether it was done or not — so a chunk
holding anything that looked like a call came back altered, reported as a hash
mismatch rather than a decoding failure. Now in LzxWimE8Filter.

Verified across eight payload shapes at four sizes each, two of them dense in
call opcodes: 32 of 32 accepted by both wimlib-imagex verify and 7z t, where
none passed before. LZX is now one of the compression types
WimReferenceReaderTests exercises.

Left here: LZMS, which no other format in the tree uses.

[Hawkynt]

Findings on the LZMS codec, and a decision about the writer, in 44c30aa.

From a reference image (wimcapture <dir> out.wim --compress=LZMS):

• The two streams run the opposite way from ours. A chunk carries a
  range-coded stream and a Huffman-coded one; the reference runs the range coder
  forwards from the start and the Huffman bitstream backwards from the
  end. Ours are the other way about. It is visible without decoding anything —
  read a reference chunk's tail backwards and the literal text appears, because
  a fresh literal table gives every byte its own value as an eight-bit code:

  tail read backwards: 54 68 65 20 71 75 69 63 6b 20 62 72 6f 77 6e 20 66 6f 78 20
  as text            : The quick brown fox
  

• The offset slots are ours, not the format's. DecodeOffsetFromSlot
  computes a base from a power-of-two rule; LZMS has a table of slot bases.

• The initial probability is 48, not the 32 in LzmsConstants.

• An LZMS image is version 3584 with 128 KB chunks, not 1.13 with 32 KB — so
  even a correct codec would not produce a valid image without the container
  change:

  version 0x00000E00 flags 0x00080082 chunk=131072
  

That is most of a codec, and the slot table is not derivable from the oracles
here — wimlib will write LZMS for comparison, which is a real advantage over
Quantum, but reconstructing the table needs either the specification or a long
differential probe that itself depends on having the range coder right first.
It has not been attempted.

Meanwhile WimWriter refuses CompressionLzms rather than handing back an
image that opens nowhere, naming the faults in the message. LzmsCompressor
stays for the workbench's own use; it is only the WIM — a claim about somebody
else's format — that is refused.

The reader is wrong in the same ways, so a genuine LZMS image is still one we
cannot read. That half stays open here too.

[Hawkynt]

I started the derivation. Seven mechanisms are now settled by measurement
against wimlib-written chunks, each verified against data rather than assumed.
Recording them here because they are the expensive part and they are not
written down anywhere else in this project.

Method throughout: wimcapture <dir> out.wim --compress=LZMS on a payload whose
LZ factorisation is known in advance, then predict what the stream must contain
and check. Nobody else's source was read; this is analysis of output.

1. The range decoder reads forwards from the start of the chunk, in 16-bit
little-endian units. range = 0xFFFFFFFF; code is the first two units,
most significant first. To decode a bit: range >>= 6, bound = range * prob;
code < bound gives a zero and range = bound, otherwise a one with
code -= bound and range -= bound. Normalise while range <= 0xFFFF by
shifting both left 16 and pulling in the next unit.

2. The probability entry is a 64-bit history of recent bits plus a count of
the zeros in it. Both start from 0x0000000055555555, which has sixteen ones,
so the initial count is 48 — not the 32 in LzmsConstants.InitialProb. The
probability used is that count clamped to [1, 63]. Updating: the bit leaving the
top of the 64-bit window is added to the count and the new bit subtracted.

3. The Huffman bitstream reads backwards from the end of the chunk, also in
16-bit little-endian units, bits taken most significant first from a 64-bit
buffer filled as buf |= word << (48 - bits_held). Ours has these two streams
the other way round, which is the fault that makes every chunk we write
undecodable.

4. The initial literal code is flat eight-bit — symbol equals byte value.
Verified directly: the tail of a reference chunk read backwards is the payload's
opening text in order.

5. A main-state bit of 0 is a literal, 1 a match, with the context index
updated as (state << 1 | bit) & (states - 1). A payload of a 45-byte phrase
repeated decodes to exactly 32 literals then a match, which is where the first
two-byte repeat in that phrase falls.

6. Within a match the offset symbol comes before the length symbol. Fixing
the distance and sweeping the length leaves the leading bits unchanged; fixing
the length and sweeping the distance moves them.

7. Offset slots are one-to-one with distance at least to 1000 — no extra
bits at small offsets — and the codes are canonical, growing by one per
distance. That contradicts NumLzOffsetSlots = 799: the alphabet is larger.

What is left is the bulk: the slot table past the one-to-one region (a boundary
search over a 30-bit space), the Huffman rebuild rule, delta matches, the
repeat-offset states, and the x86 filter — then an encoder, which need not match
wimlib's parse, only the format. The pieces above are what the next attempt
should start from rather than rediscover; each took a payload designed so the
answer was known before the stream was read.