LZW EarlyChange in Delphi: Encoder Leads the Decoder

An LZW encoder dictionary is always one entry ahead of the decoder that will read its output, so the two sides cannot share a single code width threshold. PDFlibPas gives TPLLZWEncoder and TPDFLZWDecompressor separate thresholds derived from the same EarlyChange flag, and that one-entry lead is the whole reason the flag exists at all

Almost every hand-rolled LZW implementation gets this wrong in the same place. You write the decoder first, because that is what you need in order to open files. It works. Then you write the encoder, mirror the decoder logic line for line because LZW is symmetric, run a round-trip test, and it passes. You ship. Six months later a customer opens your output in a viewer that is not yours, and it is garbage from somewhere in the middle of the stream onward. The mirror was the bug: the two halves of LZW are not symmetric, and pretending they are produces streams that only your own code can read

Why does the encoder need a different threshold than the decoder?

Because the encoder learns each dictionary entry one step before the decoder can. That is not a design choice in PDFlibPas; it is inherent to how LZW works, and every correct implementation has to compensate for it somewhere. Walk the loop and you can see where the lead comes from. The encoder accumulates a match, finds that the next byte breaks it, emits the code for the match, and immediately adds match-plus-byte to its dictionary. The decoder receives that same code and expands it, but it cannot add the corresponding entry yet, because the new entry needs the first byte of the next string, which arrives only with the next code. So at any instant while codes are flowing, the encoder table holds one more entry than the decoder table. If both sides widen the code from 9 to 10 bits when their own FNextCode hits the same number, they widen one code apart and the bit reader on the far side desynchronizes permanently. In TPDFLZWDecompressor.ResetDictionary the decoder threshold is computed once and stored in FChangeCode:

// TPDFLZWDecompressor.ResetDictionary: the decoder side of the threshold
FCodeSize := FInitialCodeSize;                 // 9 for PDF LZWDecode
FBitMask  := (Cardinal(1) shl FCodeSize) - 1;  // 511
if FEarlyChange then
  FChangeCode := FBitMask                      // widen when FNextCode reaches 511
else
  FChangeCode := FBitMask + 1;                 // widen when FNextCode reaches 512
FClearCode := 1 shl (FCodeSize - 1);           // 256
FEOICode   := FClearCode + 1;                  // 257
FNextCode  := FClearCode + 2;                  // 258

The decode loop widens right after it appends an entry, testing (FNextCode = FChangeCode) and (FCodeSize < 12) and recomputing both FBitMask and FChangeCode for the new width. Nine bits trip at 511 or 512, ten bits at 1023 or 1024, eleven bits at 2047 or 2048, and twelve bits is the ceiling where the dictionary has to be flushed with a ClearCode instead of grown. The encoder cannot reuse any of those numbers. Its GrowCodeSize adds one to compensate for the lead, so with EarlyChange set it widens at 512 while the decoder widens at 511:

procedure GrowCodeSize(FinalDataCode: Boolean);
var
  ChangeCode: Cardinal;
begin
  if FCodeSize >= 12 then
    Exit;
  if FEarlyChange then
    ChangeCode := Cardinal(1) shl FCodeSize          // 512 while at 9 bits
  else
    ChangeCode := (Cardinal(1) shl FCodeSize) + 1;   // 513 while at 9 bits
  // The decoder adds its last pending entry before it reads EOI.
  if FinalDataCode then
    Dec(ChangeCode);
  if FNextCode = ChangeCode then
    Inc(FCodeSize);
end;

The last data code is where the two sides finally meet

The end of the stream is the one place where the encoder has to stop leading and think like the decoder, which is what the FinalDataCode parameter on GrowCodeSize is for. Emit the EOI code at the wrong width and everything before it is still perfectly valid, so the defect hides behind thousands of correct bytes. The sequence goes like this. The encoder emits its final data code and, unlike every earlier iteration, adds nothing to its own dictionary afterward, because there is no following byte left to extend the match with. The decoder does the opposite: it receives that final code, and only now can it complete the entry it has been holding since the previous one. On the last step the decoder catches up, the lead collapses to zero, and the width it will use to read EOI is decided by an entry the encoder never made. Dec(ChangeCode) is the encoder pretending, for exactly one call, that it is the decoder:

// TPLLZWEncoder.Compress, the tail of the stream
EmitCode(CurCode);      // final data code, at whatever width is current
GrowCodeSize(True);     // may widen using the decremented threshold
EmitCode(FEOICode);     // EOI at the width the decoder will actually read
FlushBits;
FlushOutput;

The window in which this matters is narrow, which is what makes it dangerous. It bites only when the data happens to run out within one dictionary entry of a width boundary, so a corpus of a hundred test files can miss it entirely while one customer file hits it every time. Boundary cases in Compress have to be driven deliberately: craft inputs whose dictionary lands at 510, 511, and 512 entries, then read the emitted EOI bit width out of the stream by hand rather than inferring it from a successful decode

Why can a passing round-trip test still hide a broken stream?

Because two implementations that make the same mistake agree with each other. If your encoder and your decoder both widen one code too early, or both one code too late, they stay in lockstep, the round trip reproduces the input byte for byte, and the suite is green while the stream you produced is unreadable by anything else. That is the single most valuable thing to take away from the whole exercise: for LZW, self-consistency is worth nothing as evidence. So self round-tripping cannot be the primary test, and PDFlibPas validates the LZW path three other ways instead. Hand-built code streams with the expected bit pattern written out by hand, so the assertion is about the bytes rather than about the result of decoding them. Bidirectional interoperability against independent implementations, where streams this encoder produced are decoded elsewhere and streams produced elsewhere are decoded by TPDFLZWDecompressor. And differential decoding, reading the same bytes twice with EarlyChange set both ways, so that a stream which decodes cleanly under the wrong setting tells you the width boundaries were never exercised at all:

Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := True;
  A := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := False;   // deliberately the wrong rule for PDF
  B := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
// A must match the source; B must NOT match it. If B also matches,
// the input was too short to cross a code width boundary.

External inputs are what actually give this coverage. The current test material crosses 9, 10, 11, and 12 bit widths and forces 34 dictionary resets in a single stream, which is the only realistic way to prove the ClearCode path at the 4095 ceiling works at all. If your fixtures never exceed a few kilobytes, none of that code has ever run. And when a fix changes what your encoder produces, treat the old output as broken rather than as a compatibility baseline worth preserving; a stream that mixes code widths incorrectly is not a legacy format, it is a bug that happened to get written to disk

PDF says 1, TIFF says it depends

PDFlibPas defaults EarlyChange to True on both TPLLZWEncoder and TPDFLZWDecompressor because ISO 32000-1 Table 10 defines EarlyChange as an LZWDecode decode parameter with a default value of 1, meaning the code length increases one code early. That is specified in ISO 32000-1 section 7.4.4.2 alongside the predictor parameters, and a PDF that wants the other behavior has to say /EarlyChange 0 explicitly in its /DecodeParms dictionary. TIFF is the reason the flag is a property rather than a constant: TIFF 6.0 section 13 describes LZW compression without the same unambiguous statement, and encoders in the wild have historically split on it, which is very likely why the PDF specification felt the need to name the parameter at all. On a TIFF-to-PDF pipeline the setting is therefore not something you can hardcode at either end. Whatever the TIFF side turned out to need has to be carried explicitly into the PDF /DecodeParms, or you convert a file that opened fine into one that does not. The same care applies to FillOrder, where foTop and foBottom select which end of the byte the bit reader fills from, and to TIFF Predictor 2 horizontal differencing, which TPDFLZWParms carries through Predictor, Colors, BitsPerComponent, and Columns. Our notes on hardening the built-in TIFF decoder for BigTIFF and tiled layouts cover the rest of that path

Two smaller traps worth naming

Both of these are easy to wire up wrong when you have the encoder and the decoder objects open side by side and assume the symmetry holds there too:

InitialCodeSize does not mean the same thing on both classes. TPLLZWEncoder.InitialCodeSize is the root symbol width, validated to 2 through 8, with InitDictionary deriving FClearCode as 1 shl FInitialCodeSize and setting FCodeSize to FInitialCodeSize + 1. TPDFLZWDecompressor.InitialCodeSize is the first code width, validated to 2 through 9, with ResetDictionary deriving FClearCode as 1 shl (FCodeSize - 1). For ordinary 8-bit PDF data the defaults are 8 and 9 respectively and you never notice; set them both to the same number by hand and you have built a mismatched pair
Decoding untrusted LZW is a memory safety problem before it is a correctness problem, because the dictionary indices come straight out of the file. TPDFLZWDecompressor rejects any code above 4095 or at or above FNextCode, refuses to add entries past 4095, checks the remaining input in bits before every GetNextCode, and exposes SawExplicitEOI so a caller can tell a properly terminated stream from one that merely ran out of bytes. A truncated stream is not a partial success. The wider survey in hardening a Pascal PDF parser against malicious files covers the class of defect these guards close

What this leaves you with

LZW looks symmetric and is not. The encoder dictionary leads by one entry through the body of the stream and the lead vanishes on the final code, so a correct implementation carries two thresholds plus one special case, and the EarlyChange flag shifts both thresholds together. Get either one off by a single code and you produce output that is valid right up until it is not, with no error and no exception anywhere, just a viewer somewhere rendering noise. The honest boundary is that none of this is testable from the inside: nothing in your own suite can distinguish a correct stream from a consistently wrong one, so the interoperability check is not an optional extra pass, it is the only real evidence you will ever get. Both classes ship in the PDF Library for Delphi, which also handles the surrounding structure work described in our notes on object streams and cross-reference streams, for Delphi and C++Builder across the compiler versions the library supports