LZW EarlyChange i Delphi: kodaren leder avkodaren

En LZW-kodares dictionary ligger alltid en post före den avkodare som ska läsa dess utdata, så de två sidorna kan inte dela en enda kodbreddströskel. PDFlibPas ger TPLLZWEncoder och TPDFLZWDecompressor separata trösklar som härleds ur samma EarlyChange-flagga, och det en-post-försprånget är hela anledningen till att flaggan existerar över huvud taget

Nästan varje handrullad LZW-implementation får detta fel på samma ställe. Du skriver avkodaren först, för det är den du behöver för att öppna filer. Den fungerar. Sedan skriver du kodaren, speglar avkodalogiken rad för rad eftersom LZW är symmetriskt, kör ett round-trip-test, och det går igenom. Du släpper. Sex månader senare öppnar en kund din utdata i en viewer som inte är din, och det är skräp från någonstans i mitten av strömmen och framåt. Speglingen var buggen: de två halvorna av LZW är inte symmetriska, och att låtsas att de är det producerar strömmar som bara din egen kod kan läsa

Varför behöver kodaren en annan tröskel än avkodaren?

Därför att kodaren lär sig varje dictionary-post ett steg före avkodaren. Det är inget designval i PDFlibPas; det ligger i hur LZW fungerar, och varje korrekt implementation måste kompensera för det någonstans. Gå igenom loopen så ser du var försprånget kommer ifrån. Kodaren ackumulerar en match, upptäcker att nästa byte bryter den, sänder ut koden för matchen och lägger omedelbart till match-plus-byte i sin dictionary. Avkodaren tar emot samma kod och expanderar den, men den kan inte lägga till motsvarande post ännu, för den nya posten behöver den första byten i nästa sträng, som anländer först med nästa kod. Så vid varje ögonblick medan koder flödar håller kodarens tabell en post mer än avkodarens tabell. Om båda sidor breddar koden från 9 till 10 bitar när deras eget FNextCode når samma tal, breddar de en kod ifrån varandra och bitläsaren på andra sidan desynkroniseras permanent. I TPDFLZWDecompressor.ResetDictionary beräknas avkodartröskeln en gång och lagras i FChangeCode:

// TPDFLZWDecompressor.ResetDictionary: avkodarsidan av tröskeln
FCodeSize := FInitialCodeSize;                 // 9 för PDF LZWDecode
FBitMask  := (Cardinal(1) shl FCodeSize) - 1;  // 511
if FEarlyChange then
  FChangeCode := FBitMask                      // bredda när FNextCode når 511
else
  FChangeCode := FBitMask + 1;                 // bredda när FNextCode når 512
FClearCode := 1 shl (FCodeSize - 1);           // 256
FEOICode   := FClearCode + 1;                  // 257
FNextCode  := FClearCode + 2;                  // 258

Avkodningsloopen breddar direkt efter att den lägger till en post, testar (FNextCode = FChangeCode) and (FCodeSize < 12) och räknar om både FBitMask och FChangeCode för den nya bredden. Nio bitar löser ut vid 511 eller 512, tio bitar vid 1023 eller 1024, elva bitar vid 2047 eller 2048, och tolv bitar är taket där dictionaryn måste spolas med en ClearCode i stället för att växa. Kodaren kan inte återanvända något av dessa tal. Dess GrowCodeSize lägger till ett för att kompensera försprånget, så med EarlyChange satt breddar den vid 512 medan avkodaren breddar vid 511:

procedure GrowCodeSize(FinalDataCode: Boolean);
var
  ChangeCode: Cardinal;
begin
  if FCodeSize >= 12 then
    Exit;
  if FEarlyChange then
    ChangeCode := Cardinal(1) shl FCodeSize          // 512 vid 9 bitar
  else
    ChangeCode := (Cardinal(1) shl FCodeSize) + 1;   // 513 vid 9 bitar
  // Avkodaren lägger till sin sista väntande post innan den läser EOI.
  if FinalDataCode then
    Dec(ChangeCode);
  if FNextCode = ChangeCode then
    Inc(FCodeSize);
  end;

Den sista datakoden är där de två sidorna äntligen möts

Slutet på strömmen är det enda stället där kodaren måste sluta leda och tänka som avkodaren, vilket är vad parametern FinalDataCode på GrowCodeSize är till för. Sänd ut EOI-koden i fel bredd och allt före den är fortfarande fullt giltigt, så defekten gömmer sig bakom tusentals korrekta byte. Sekvensen går så här. Kodaren sänder ut sin sista datakod och, till skillnad från varje tidigare iteration, lägger den ingenting i sin egen dictionary efteråt, för det finns ingen efterföljande byte kvar att utöka matchen med. Avkodaren gör tvärtom: den tar emot den sista koden och först nu kan den fullborda posten den hållit på sedan den föregående. På sista steget hinner avkodaren ifatt, försprånget kollapsar till noll, och bredden den kommer att använda för att läsa EOI avgörs av en post som kodaren aldrig gjorde. Dec(ChangeCode) är kodaren som låtsas, för exakt ett anrop, att den är avkodaren:

// TPLLZWEncoder.Compress, svansen av strömmen
EmitCode(CurCode);      // sista datakoden, i den bredd som är aktuell
GrowCodeSize(True);     // kan bredda med den dekrementerade tröskeln
EmitCode(FEOICode);     // EOI i den bredd avkodaren faktiskt kommer att läsa
FlushBits;
FlushOutput;

Fönstret där detta spelar roll är smalt, vilket är vad som gör det farligt. Det biter bara när data råkar ta slut inom en dictionary-post från en breddgräns, så en korpus på hundra testfiler kan missa det helt medan en kundfil träffar på det varje gång. Gränsfallen i Compress måste drivas medvetet: konstruera indata vars dictionary hamnar på 510, 511 och 512 poster, läs sedan den emitterade EOI-bitbredden ur strömmen för hand i stället för att härleda den från en lyckad avkodning

Varför kan ett godkänt round-trip-test fortfarande dölja en trasig ström?

Därför att två implementationer som gör samma misstag håller med varandra. Om din kodare och din avkodare båda breddar en kod för tidigt, eller båda en kod för sent, förblir de i låssteg, round-trippen återger indata byte för byte, och sviten är grön medan strömmen du producerade är oläslig för allt annat. Det är det enskilt mest värdefulla att ta med sig från hela övningen: för LZW är självkonsistens värdelös som bevis. Så själv-round-tripping kan inte vara primärtestet, och PDFlibPas validerar LZW-vägen på tre andra sätt i stället. Handbyggda kodströmmar där det förväntade bitmönstret skrivits för hand, så att påståendet handlar om byten snarare än om resultatet av att avkoda dem. Dubbelriktad interoperabilitet mot oberoende implementationer, där strömmar som denna kodare producerat avkodas på annat håll och strömmar producerade på annat håll avkodas av TPDFLZWDecompressor. Och differentialavkodning, att läsa samma byte två gånger med EarlyChange satt åt båda håll, så att en ström som avkodas rent under fel inställning talar om för dig att breddgränserna aldrig rördes över huvud taget:

Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := True;
  A := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := False;   // medvetet fel regel för PDF
  B := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
// A måste matcha källan; B får INTE matcha den. Om B också matchar,
// var indatan för kort för att korsa en kodbreddsgräns.

Externa indata är vad som faktiskt ger denna täckning. Det aktuella testmaterialet korsar 9-, 10-, 11- och 12-bitars bredder och tvingar 34 dictionary-återställningar i en enda ström, vilket är det enda realistiska sättet att bevisa att ClearCode-vägen vid 4095-taket fungerar över huvud taget. Om dina fixtures aldrig överstiger några kilobyte har ingen av den koden någonsin kört. Och när en fix ändrar vad din kodare producerar, behandla den gamla utdatan som trasig snarare än som en kompatibilitetsbaslinje värd att bevara; en ström som blandar kodbredder felaktigt är inte ett legacy-format, det är en bugg som råkat skrivas till disk

PDF säger 1, TIFF säger att det beror på

PDFlibPas sätter EarlyChange som standard till True på både TPLLZWEncoder och TPDFLZWDecompressor eftersom ISO 32000-1 Table 10 definierar EarlyChange som en LZWDecode-avkodningsparameter med standardvärdet 1, vilket betyder att kodlängden ökar en kod tidigt. Det specificeras i ISO 32000-1 avsnitt 7.4.4.2 tillsammans med prediktorparametrarna, och en PDF som vill ha det andra beteendet måste säga /EarlyChange 0 explicit i sin /DecodeParms-dictionary. TIFF är anledningen till att flaggan är en egenskap snarare än en konstant: TIFF 6.0 avsnitt 13 beskriver LZW-komprimering utan samma entydiga uttalande, och kodare i det vilda har historiskt varit splittrade i frågan, vilket mycket väl är varför PDF-specifikationen kände behov av att namnge parametern över huvud taget. På en TIFF-till-PDF-pipeline är inställningen därför inte något du kan hardcoda i någon ände. Vad TIFF-sidan än visade sig behöva måste föras explicit in i PDF:ens /DecodeParms, annars konverterar du en fil som öppnades fint till en som inte gör det. Samma omsorg gäller FillOrder, där foTop och foBottom väljer vilken ände av byten bitläsaren fyller från, och TIFF Predictor 2:s horisontella differentiering, som TPDFLZWParms bär genom Predictor, Colors, BitsPerComponent och Columns. Våra anteckningar om att hårda den inbyggda TIFF-avkodaren för BigTIFF och tile-layouter täcker resten av den vägen

Två mindre fällor värda att namnge

Båda dessa är lätta att koppla ihop fel när du har kodar- och avkodarobjekten öppna sida vid sida och antar att symmetrin gäller där också:

• InitialCodeSize betyder inte samma sak på de båda klasserna. TPLLZWEncoder.InitialCodeSize är rotsymbolbredden, validerad till 2 till och med 8, där InitDictionary härleder FClearCode som 1 shl FInitialCodeSize och sätter FCodeSize till FInitialCodeSize + 1. TPDFLZWDecompressor.InitialCodeSize är den första kodbredden, validerad till 2 till och med 9, där ResetDictionary härleder FClearCode som 1 shl (FCodeSize - 1). För vanlig 8-bitars PDF-data är standardvärdena 8 respektive 9 och du märker aldrig; sätt dem båda till samma tal för hand så har du byggt ett omatchat par
• Att avkoda icke-pålitlig LZW är ett minnessäkerhetsproblem innan det är ett korrekthetsproblem, eftersom dictionary-indexen kommer direkt ur filen. TPDFLZWDecompressor avvisar alla koder över 4095 eller på eller över FNextCode, vägrar att lägga till poster förbi 4095, kontrollerar återstående indata i bitar före varje GetNextCode och exponerar SawExplicitEOI så att en anropare kan skilja en korrekt avslutad ström från en som bara tog slut på byte. En trunkerad ström är ingen partiell framgång. Den bredare översikten i att hårda en Pascal-PDF-parser mot skadliga filer täcker klassen av defekter dessa skydd stänger

Vad detta lämnar dig med

LZW ser symmetriskt ut och är det inte. Kodarens dictionary leder med en post genom strömmens kropp och försprånget försvinner vid den sista koden, så en korrekt implementation bär två trösklar plus ett specialfall, och flaggan EarlyChange flyttar båda trösklarna tillsammans. Få endera fel med en enda kod och du producerar utdata som är giltig ända tills den inte är det, utan fel och utan undantag någonstans, bara en viewer någonstans som renderar brus. Den ärliga gränsen är att inget av detta kan testas inifrån: ingenting i din egen svit kan skilja en korrekt ström från en konsekvent felaktig, så interoperabilitetskontrollen är inte en valfri extra pass, den är det enda riktiga bevis du någonsin kommer att få. Båda klasserna levereras i PDF Library for Delphi, som också sköter det omgivande strukturarbetet som beskrivs i våra anteckningar om objektströmmar och korsreferensströmmar, för Delphi och C++Builder över de kompilatorversioner biblioteket stödjer