Delphi'de LZW EarlyChange: Kodlayıcı Çözücünün Önündedir

Bir LZW kodlayıcı sözlüğü, çıktısını okuyacak çözücüden her zaman bir girdi öndedir; bu yüzden iki taraf tek bir kod genişliği eşiğini paylaşamaz. PDFlibPas, TPLLZWEncoder ve TPDFLZWDecompressor'a aynı EarlyChange bayrağından türetilen ayrı eşikler verir ve bu bir girdilik öndelik, bayrağın var olmasının tüm nedenidir

Hemen hemen her el yazması LZW uygulaması bunu aynı yerde yanlış yapar. Önce çözücüyü yazarsınız, çünkü dosyaları açmak için ihtiyacınız olan şey odur. Çalışır. Sonra kodlayıcıyı yazarsınız, LZW simetrik olduğu için çözücü mantığını satır satır aynalarsınız, bir round-trip testi çalıştırırsınız ve geçer. Yayınlarsınız. Altı ay sonra bir müşteri çıktınızı sizinkine benzemeyen bir görüntüleyicide açar ve akışın ortasından itibaren her şey çöptür. Aynalama hataydı: LZW'nin iki yarısı simetrik değildir ve öyle olduklarını varsaymak yalnızca kendi kodunuzun okuyabildiği akışlar üretir

Kodlayıcı neden çözücüden farklı bir eşik gerektirir?

Çünkü kodlayıcı her sözlük girdisini çözücüden bir adım önce öğrenir. Bu, PDFlibPas'ta bir tasarım tercihi değildir; LZW'nin nasıl çalıştığının doğasında vardır ve her doğru uygulama bir yerde bunu telafi etmek zorundadır. Döngüyü yürüyün, öndeliğin nereden geldiğini görürsünüz. Kodlayıcı bir eşleşme biriktirir, sonraki baytın onu bozduğunu bulur, eşleşmenin kodunu yayar ve eşleşme-artı-baytı hemen sözlüğüne ekler. Çözücü aynı kodu alır ve açar, ama karşılık gelen girdiyi henüz ekleyemez, çünkü yeni girdi sonraki dizenin ilk baytını gerektirir ve o bayt yalnızca sonraki kodla gelir. Yani kodlar akarken herhangi bir anda kodlayıcı tablosu çözücü tablosundan bir girdi fazla tutar. İki taraf da kendi FNextCode'u aynı sayıya ulaştığında kodu 9 bitten 10 bit'e genişletirse, bir kod arayla genişletirler ve uzak taraftaki bit okuyucu kalıcı olarak senkronizasyonu kaybeder. TPDFLZWDecompressor.ResetDictionary içinde çözücü eşiği bir kez hesaplanır ve FChangeCode'da saklanır:

// TPDFLZWDecompressor.ResetDictionary: eşiğin çözücü tarafı
FCodeSize := FInitialCodeSize;                 // PDF LZWDecode için 9
FBitMask  := (Cardinal(1) shl FCodeSize) - 1;  // 511
if FEarlyChange then
  FChangeCode := FBitMask                      // FNextCode 511'e ulaştığında genişlet
else
  FChangeCode := FBitMask + 1;                 // FNextCode 512'ye ulaştığında genişlet
FClearCode := 1 shl (FCodeSize - 1);           // 256
FEOICode   := FClearCode + 1;                  // 257
FNextCode  := FClearCode + 2;                  // 258

Çözme döngüsü, bir girdi ekledikten hemen sonra genişletir, (FNextCode = FChangeCode) and (FCodeSize < 12)'yi test eder ve yeni genişlik için hem FBitMask hem FChangeCode'u yeniden hesaplar. Dokuz bit 511 veya 512'de tetiklenir, on bit 1023 veya 1024'te, on bir bit 2047 veya 2048'de ve on iki bit, sözlüğün büyütmek yerine bir ClearCode ile temizlenmesi gereken tavandır. Kodlayıcı bu sayıların hiçbirini yeniden kullanamaz. Onun GrowCodeSize'u öndeliği telafi etmek için bir ekler; böylece EarlyChange set edildiğinde çözücü 511'de genişletirken o 512'de genişletir:

procedure GrowCodeSize(FinalDataCode: Boolean);
var
  ChangeCode: Cardinal;
begin
  if FCodeSize >= 12 then
    Exit;
  if FEarlyChange then
    ChangeCode := Cardinal(1) shl FCodeSize          // 9 bitteyken 512
  else
    ChangeCode := (Cardinal(1) shl FCodeSize) + 1;   // 9 bitteyken 513
  // Çözücü, EOI'yi okumadan önce bekleyen son girdisini ekler.
  if FinalDataCode then
    Dec(ChangeCode);
  if FNextCode = ChangeCode then
    Inc(FCodeSize);
  end;

Son veri kodu, iki tarafın nihayet buluştuğu yerdir

Akışın sonu, kodlayıcının önde gitmeyi bırakıp çözücü gibi düşünmesi gereken tek yerdir; GrowCodeSize üzerindeki FinalDataCode parametresinin amacı budur. EOI kodunu yanlış genişlikte yayın ve öncesindeki her şey hâlâ tamamen geçerlidir; bu yüzden kusur binlerce doğru baytın arkasına saklanır. Sıra şöyle işler. Kodlayıcı son veri kodunu yayar ve önceki her yinelemenin aksine ardından kendi sözlüğüne hiçbir şey eklemez, çünkü eşleşmeyi genişletecek takip eden bir bayt kalmamıştır. Çözücü tersini yapar: o son kodu alır ve ancak şimdi önceki koddan beri tuttuğu girdiyi tamamlayabilir. Son adımda çözücü yakalar, öndelik sıfıra çöker ve EOI'yi okumak için kullanacağı genişlik, kodlayıcının hiç yapmadığı bir girdi tarafından belirlenir. Dec(ChangeCode), kodlayıcının tam olarak bir çağrı için çözücü gibi davranmasıdır:

// TPLLZWEncoder.Compress, akışın kuyruğu
EmitCode(CurCode);      // geçerli genişlikteki son veri kodu
GrowCodeSize(True);     // eksiltilmiş eşiği kullanarak genişletebilir
EmitCode(FEOICode);     // EOI, çözücünün gerçekten okuyacağı genişlikte
FlushBits;
FlushOutput;

Bunun önemli olduğu pencere dardır ve bu onu tehlikeli yapan şeydir. Yalnızca veri, bir genişlik sınırına bir sözlük girdisi mesafesinde tükendiğinde ısırır; bu yüzden yüz test dosyalık bir derlem kusuru tamamen ıskalayabilirken tek bir müşteri dosyası her seferinde yakalar. Compress içindeki sınır durumları bilinçli olarak sürülmelidir: sözlüğü 510, 511 ve 512 girdide bırakan girdiler üretin, ardından yayılan EOI bit genişliğini başarılı bir çözmeden çıkarım yapmak yerine elle akıştan okuyun

Geçen bir round-trip testi neden yine de bozuk bir akışı gizleyebilir?

Çünkü aynı hatayı yapan iki uygulama birbiriyle anlaşır. Kodlayıcınız ve çözücünüz ikisi de kodu bir kod erken genişletiyorsa ya da ikisi de bir kod geç genişletiyorsa, kilit adımda kalırlar, round trip girdiyi bayt bayt yeniden üretir ve siz ürettiğiniz akış başka hiçbir şey tarafından okunamazken suite yeşildir. Tüm bu alıştırmadan çıkarılacak en değerli tek şey budur: LZW için öz tutarlılık, kanıt olarak hiçbir şey değmez. Bu yüzden kendi kendine round-trip birincil test olamaz ve PDFlibPas LZW yolunu üç başka şekilde doğrular. Beklenen bit deseni elle yazılan, elle kurulmuş kod akışları; böylece iddia baytlar hakkındadır, onları çözmenin sonucu hakkında değil. Bağımsız uygulamalara karşı çift yönlü birlikte çalışabilirlik; bu kodlayıcının ürettiği akışlar başka yerde çözülür ve başka yerde üretilen akışlar TPDFLZWDecompressor tarafından çözülür. Ve diferansiyel çözme: EarlyChange iki yönde de set edilerek aynı baytları iki kez okumak; böylece yanlış ayar altında temiz çözülen bir akış, genişlik sınırlarının hiç çalıştırılmadığını söyler:

Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := True;
  A := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := False;   // bilerek PDF için yanlış kural
  B := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
// A kaynakla eşleşmelidir; B ise eşleşmemelidir. B de eşleşirse,
// girdi bir kod genişliği sınırını aşamayacak kadar kısaydı.

Gerçek kapsamı veren şey harici girdilerdir. Mevcut test materyali 9, 10, 11 ve 12 bit genişliklerini geçer ve tek bir akışta 34 sözlük sıfırlaması zorlar; 4095 tavanındaki ClearCode yolunun hiç çalıştığını kanıtlamanın tek gerçekçi yolu budur. Sabitleriniz birkaç kilobaytı asla aşmıyorsa, o kodun hiçbiri hiç çalışmamıştır. Ve bir düzeltme kodlayıcınızın ürettiğini değiştirdiğinde, eski çıktıya korumaya değer bir uyumluluk tabanı olarak değil bozuk olarak davranın; kod genişliklerini yanlış karıştıran bir akış eski bir biçim değil, şansa diske yazılmış bir hatadır

PDF 1 der, TIFF duruma göre değişir

PDFlibPas, EarlyChange'i hem TPLLZWEncoder hem TPDFLZWDecompressor üzerinde True varsayılan yapar, çünkü ISO 32000-1 Tablo 10, EarlyChange'i varsayılan değeri 1 olan bir LZWDecode çözme parametresi olarak tanımlar; yani kod uzunluğu bir kod erken artar. Bu, ISO 32000-1 bölüm 7.4.4.2'de tahminci parametreleriyle birlikte belirtilir ve diğer davranışı isteyen bir PDF, /DecodeParms sözlüğünde açıkça /EarlyChange 0 demek zorundadır. Bayrağın bir sabit değil bir özellik olmasının nedeni TIFF'tir: TIFF 6.0 bölüm 13, LZW sıkıştırmasını aynı net ifade olmadan tanımlar ve sahadaki kodlayıcılar tarihsel olarak bu konuda bölünmüştür; PDF belirtiminin parametreyi adlandırma ihtiyacı hissetmesinin büyük olasılıkla nedeni budur. Bir TIFF'ten PDF'e hattında bu yüzden ayar, iki uçta da sabit kodlayamayacağınız bir şeydir. TIFF tarafının neye ihtiyaç duyduğu ortaya çıkarsa çıksın, açıkça PDF /DecodeParms'una taşınmak zorundadır; aksi hâlde sorunsuz açılan bir dosyayı açılmayan bir dosyaya dönüştürürsünüz. Aynı özen FillOrder için de geçerlidir; burada foTop ve foBottom, bit okuyucunun baytın hangi ucundan doldurduğunu seçer; ve TPDFLZWParms'ın Predictor, Colors, BitsPerComponent ve Columns üzerinden taşıdığı TIFF Predictor 2 yatay farklama için de. BigTIFF ve tile düzenleri için yerleşik TIFF çözücüyü sıkılaştırma notlarımız o yolun geri kalanını kapsar

Adlandırmaya değer iki küçük tuzak

İkisi de kodlayıcı ve çözücü nesnelerini yan yana açıkken ve simetrinin orada da geçerli olduğunu varsayarken yanlış bağlanması kolay olan şeylerdir:

• InitialCodeSize iki sınıfta da aynı şeyi ifade etmez. TPLLZWEncoder.InitialCodeSize kök sembol genişliğidir, 2 ila 8 arasında doğrulanır ve InitDictionary, FClearCode'u 1 shl FInitialCodeSize olarak türetir ve FCodeSize'u FInitialCodeSize + 1'e ayarlar. TPDFLZWDecompressor.InitialCodeSize ilk kod genişliğidir, 2 ila 9 arasında doğrulanır ve ResetDictionary, FClearCode'u 1 shl (FCodeSize - 1) olarak türetir. Sıradan 8 bit PDF verisi için varsayılanlar sırasıyla 8 ve 9'dur ve asla fark etmezsiniz; ikisini de elle aynı sayıya ayarlayın ve uyumsuz bir çift kurmuş olursunuz
• Güvenilmeyen LZW çözmek, doğruluk sorunu olmadan önce bir bellek güvenliği sorunudur, çünkü sözlük dizinleri doğrudan dosyadan gelir. TPDFLZWDecompressor 4095'in üzerindeki veya FNextCode seviyesinde ve üzerindeki herhangi bir kodu reddeder, 4095'in ötesine girdi eklemeyi reddeder, her GetNextCode'tan önce kalan girdiyi bit olarak kontrol eder ve SawExplicitEOI'yi açığa çıkarır; böylece bir çağıran, düzgün sonlandırılmış bir akışı yalnızca baytları tükenmiş bir akıştan ayırt edebilir. Kesilmiş bir akış kısmi bir başarı değildir. Bir Pascal PDF ayrıştırıcısını kötü niyetli dosyalara karşı sıkılaştırma konulu daha geniş inceleme, bu korumaların kapattığı kusur sınıfını kapsar

Bunun size bıraktığı şey

LZW simetrik görünür ve değildir. Kodlayıcı sözlüğü akışın gövdesi boyunca bir girdi önde gider ve öndelik son kodda kaybolur; bu yüzden doğru bir uygulama iki eşik artı bir özel durum taşır ve EarlyChange bayrağı iki eşiği birlikte kaydırır. İkisinden birini tek bir kod kaydırın ve hiçbir yerde hata veya istisna olmadan, yalnızca bir görüntüleyicinin bir yerlerde gürültü render etmesiyle, olmadığı ana kadar geçerli olan çıktı üretirsiniz. Dürüst sınır şudur: bunların hiçbiri içeriden test edilemez — kendi suite'inizdeki hiçbir şey doğru bir akışı tutarlı biçimde yanlış olandan ayırt edemez; bu yüzden birlikte çalışabilirlik kontrolü isteğe bağlı ek bir geçiş değil, asla elde edemeyeceğiniz tek gerçek kanıttır. İki sınıf da PDF Library for Delphi içinde gelir; bu kütüphane, nesne akışları ve çapraz başvuru akışları notlarımızda anlatılan çevre yapı işini de halleder ve kütüphanenin desteklediği derleyici sürümlerinde Delphi ve C++Builder için çalışır