Własne tabele Huffmana JBIG2 w dekoderze PDF w Pascalu

PDFlibPas w wersji 3.539.22 dekoduje własne tabele Huffmana JBIG2 natywnie: czysty pascalowy dekoder w PDFlibJBIG2.pas parsuje segment Tables (typ 53), nadaje kanoniczne kody prefiksowe w kolejności wierszy tabeli, tak jak wymaga tego ITU-T T.88 Annex B.3, pobiera odwołania do własnych tabel w kolejności selektorów dla słowników symboli i regionów tekstowych, a każdy odczyt ogranicza zadeklarowaną długością segmentu, a nie tym, jakie bajty akurat następują

Plik, który wymusił tę pracę, był na pierwszy rzut oka zupełnie zwyczajny. Zeskanowana umowa, skompresowana JBIG2 z kodowaniem Huffmana symboli zamiast znacznie częstszego kodowania arytmetycznego, a koder wysyłał własne tabele kodów zamiast standardowych tabel od B.1 do B.15. Dwa niezależne dekodery nie zgadzały się co do pikseli refinement, a ówczesny dekoder PDFlibPas produkował tekst wyglądający, jakby przeszedł przez niszczarkę: fragmenty glifów przesunięte o kilka pikseli, brakująca jedna kolumna w każdym znaku. Nic nie zgłaszało błędu. To właśnie ten rodzaj błędu, który przeżywa lata, bo dekoder odrzucający plik dostaje zgłoszenie do supportu, a dekoder renderujący go trochę źle dostaje klienta, który zakłada, że skan był zły

Co właściwie zawiera segment Tables w JBIG2?

Segment Tables to zwięzły opis jednej tabeli Huffmana: bajt flag, dwie 32-bitowe granice ze znakiem, a potem ciąg par (długość prefiksu, długość zakresu) dzielących przedział między tymi granicami, zgodnie z układem z T.88 §7.4.13 i Annex B.2. Bit 0 bajtu flag to HTOOB i mówi, czy tabela ma kod poza zakresem. Bity od 1 do 3 plus jeden dają HTPS, czyli liczbę bitów używanych do zapisania każdej długości prefiksu; bity od 4 do 6 plus jeden dają HTRS, czyli szerokość pola każdej długości zakresu. Bit 7 jest zarezerwowany i PDFlibPas odrzuca segment, gdy jest ustawiony, zamiast zgadywać, co przyszła wersja specyfikacji miała przez niego na myśli. Dalej idą HTLOW i HTHIGH jako 32-bitowe liczby całkowite ze znakiem i tu dekoder może się potknąć po raz pierwszy: odczytanie ich jako wartości bez znaku sprawia, że tabela, której dolna granica jest ujemna, co dla kodowanych różnicowo szerokości symboli jest całkowicie normalne, wygląda, jakby zaczynała się od czterech miliardów. Każde pole przechodzi przez lokalny helper ReadField, który przed sięgnięciem do czytnika sprawdza żądanie względem pozycji bitu, na której kończą się dane segmentu, bo tabela czytająca poza swój segment pobierałaby nagłówek następnego segmentu jako długości prefiksów

// TCodeTableSegment.readSegment, PDFlibJBIG2.pas
EndBit := (Int64(decoder.reader.bytePointer) +
  segmentHeader.getSegmentDataLength) * 8;
Flags := ReadField(8);
if (Flags and $80) <> 0 then
  raise EJBIG2DecodeError.Create('reserved custom Huffman table flag');
PrefixBits := ((Flags shr 1) and 7) + 1;   // HTPS
RangeBits  := ((Flags shr 4) and 7) + 1;   // HTRS
LowValue   := Integer(ReadField(32));      // HTLOW ze znakiem
HighValue  := Integer(ReadField(32));      // HTHIGH ze znakiem
if LowValue >= HighValue then
  raise EJBIG2DecodeError.Create('invalid custom Huffman range bounds');
CurrentValue := LowValue;
while CurrentValue < HighValue do
begin
  PrefixLength := ReadField(PrefixBits);
  RangeLength  := ReadField(RangeBits);
  if RangeLength > 32 then
    raise EJBIG2DecodeError.Create('invalid custom Huffman range length');
  AddLine(CurrentValue, PrefixLength, RangeLength);
  Inc(CurrentValue, Int64(1) shl RangeLength);
end;
AddLine(LowValue - 1, ReadField(PrefixBits), jbig2HuffmanLOW);
AddLine(HighValue,   ReadField(PrefixBits), 32);
if (Flags and 1) <> 0 then
  AddLine(0, ReadField(PrefixBits), jbig2HuffmanOOB);

Dwie linie dopisywane po pętli to linie ucieczki z Annex B.2: dolna linia zakresu startuje od HTLOW minus jeden i liczy w dół, górna startuje od HTHIGH ze stałym 32-bitowym zakresem, a opcjonalna linia OOB nie ma żadnej wartości. PDFlibPas oznacza je wartownikowymi długościami zakresu jbig2HuffmanLOW ($FFFFFFFD) i jbig2HuffmanOOB ($FFFFFFFE), czyli tą samą konwencją, której używa jego piętnaście wbudowanych tabel standardowych, więc pętla dekodująca nie dba o to, czy tabela przyszła ze specyfikacji, czy z pliku

Dlaczego kody prefiksowe trzeba nadawać w kolejności wierszy tabeli?

Bo koder nigdy nie zapisuje samych kodów. Segment Tables w JBIG2 niesie wyłącznie długości prefiksów, a obie strony odtwarzają właściwe wzorce bitów kanoniczną procedurą z Annex B.3: policz, ile linii ma każdą długość, nadaj najpierw kody długości jeden, potem przesuwaj w lewo i kontynuuj, a w obrębie jednej długości rozdawaj kody w kolejności, w jakiej pojawiają się linie. Każde odejście od tej kolejności po cichu daje inną tabelę. Dekoder tego nie zauważy, bo każdy wzorzec bitów, jaki wygeneruje, wciąż jest poprawnym kodem prefiksowym, tylko nie tym, którego użył koder, a wynikiem jest wyglądająca wiarygodnie bitmapa złożona z niewłaściwych symboli

// THuffmanDecoder.buildTable, PDFlibJBIG2.pas
FillChar(Counts, SizeOf(Counts), 0);
for I := 0 to length - 1 do
begin
  if table[I].prefixLen > 32 then
    raise EJBIG2DecodeError.Create(
      'Huffman prefixes longer than 32 bits are not supported');
  Inc(Counts[table[I].prefixLen]);
end;
Active := 0;
Code := 0;
for Bits := 1 to 32 do
begin
  Starts[Bits]    := Active;
  Positions[Bits] := Active;
  Inc(Active, Counts[Bits]);
  if Code + UInt64(Counts[Bits]) > (UInt64(1) shl Bits) then
    raise EJBIG2DecodeError.Create('oversubscribed Huffman prefix codes');
  Code := (Code + UInt64(Counts[Bits])) shl 1;
end;
SetLength(Result, Active + 1);
for I := 0 to length - 1 do            // stabilnie: zachowana pierwotna kolejność
  if table[I].prefixLen > 0 then       // w obrębie każdej długości prefiksu
  begin
    Result[Positions[table[I].prefixLen]] := table[I];
    Inc(Positions[table[I].prefixLen]);
  end;
Code := 0;
for Bits := 1 to 32 do
begin
  for I := Starts[Bits] to Positions[Bits] - 1 do
  begin
    Result[I].prefix := Cardinal(Code);
    Inc(Code);
  end;
  Code := Code shl 1;
end;
Result[Active].rangeLen := jbig2HuffmanEOT;

THuffmanDecoder.buildTable jest sortowaniem przez zliczanie, a nie przez porównywanie, z jednego powodu: przebieg zliczający po Counts, Starts i Positions jest z konstrukcji stabilny, więc linie o równej długości prefiksu trafiają do wyniku w kolejności, w jakiej je zadeklarowano, a dokładnie według tej kolejności Annex B.3 nadaje kody. Linie o zerowej długości prefiksu są odrzucane przed nadawaniem kodów, bo B.3 definiuje je jako nieużywane, a nie jako kody jednobitowe. W tej samej pętli siedzą dwa zabezpieczenia. Sprawdzenie przekroczenia pojemności łapie tabelę, której długości żądają więcej kodów, niż może pomieścić kod prefiksowy o takiej głębokości, czyli nierówność Krafta wyrażoną jako porównanie liczb całkowitych; bez niego wroga tabela tworzy kod pasujący do dwóch linii, a dekoder wybiera tę, którą zeskanuje pierwszą. Pułap 32 bitów istnieje, bo prefix jest typu Cardinal, a matcher w decodeInt akumuluje bity do jednego takiego. T.88 dopuszcza dłuższe prefiksy na papierze, PDFlibPas odrzuca je z nazwy, a żaden prawdziwy koder nie został przyłapany na wysyłaniu takiego. Arytmetyka wartości wymaga takiej samej staranności jak arytmetyka kodów: THuffmanTable.val jest typu Int64, a dolna linia zakresu dekodowana jest jako val - readBits(32), czyli 32-bitowe przesunięcie bez znaku odejmowane od HTLOW minus jeden. Przy Integer jako typie pośrednim to odejmowanie się zawija, a zawinięta wartość jest potem przyjmowana jako szerokość symbolu. Ścieżka 64-bitowa liczy prawdziwą wartość, sprawdza ją względem 32-bitowego zakresu ze znakiem i rzuca wyjątek, gdy się nie mieści, co zamienia ciche uszkodzenie w jawne odrzucenie

Dlaczego własne tabele nigdy się nie włączały przed 3.539.22?

Dwa defekty wzajemnie się ukrywały. Pierwszy to jednolinijkowy błąd settera: TTextRegionHuffmanFlags.setFlags dostawał argument pod tą samą nazwą co pole, do którego go zapisywał, więc Self.flagsAsInt := flagsAsInt przypisywało niezainicjowane pole samo do siebie i każdy selektor odczytywał się jako zero, co kierowało regiony tekstowe proszące o własne tabele przez tabele standardowe F, H i K. Drugi defekt sprawiał, że naprawa samego pierwszego wciąż dawałaby uszkodzone symbole. Kiedy słownik symboli Huffmana zapisuje symbole jako nieskompresowaną bitmapę zbiorczą, ostatni bajt każdego wiersza jest częściowy, a stara pętla kopiująca traktowała padding, w którym siedzi liczba poprawnych bitów, jako pozycję najniższego poprawnego bitu; wiersz o szerokości 63 pikseli kopiował jeden bit z ostatniego bajtu zamiast siedmiu. Poprawiona pętla biegnie for bitPointer := 7 downto ((8 - padding) and 7), a syntetyczne fixture'y o szerokościach 7 i 9 bitów przypinają obie strony granicy bajtu. Gdy selektory czytają się poprawnie, tabele są rozdawane w kolejności, w jakiej wymienia je specyfikacja, co T.88 §7.4.3.1.2 ustala dla regionów tekstowych jako FS, DS, DT, RDW, RDH, RDX, RDY i RSIZE, a §7.4.2.1.1 dla słowników symboli jako DH, DW, BMSIZE i AGGINST. Każdy dwubitowy selektor oznacza tabelę standardową 0 albo 1, wartość 2 zarezerwowaną na polach z tylko dwiema tabelami standardowymi, a 3 własną, i każde wybranie własnej tabeli zużywa następny segment Tables spośród segmentów, do których się odwołano, w kolejności odwołań. NextCustomHuffmanTable robi dokładnie taki przebieg i rzuca missing custom Huffman table reference, gdy region odwołuje się do mniejszej liczby tabel, niż żądają jego selektory. Do tej samej poprawki należy jeszcze jedna linia: słownik symboli Huffmana, którego symbole wejściowe i nowe sumują się do jednego, wylicza ze wzoru na log2 zerową długość kodu symbolu, a wariant Huffmana tego formatu zapisuje każdy identyfikator symbolu co najmniej jednym bitem, więc if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 w TSymbolDictionarySegment powstrzymuje ścieżkę refinement i agregacji przed czytaniem zera bitów na identyfikator symbolu

Co gwarantuje granica segmentu?

PDFlibPas traktuje długość danych segmentu w każdym nagłówku jako kontrakt, który obie strony muszą dotrzymać: segment nie może czytać poza swój zadeklarowany koniec i nie może skończyć się za wcześnie, zostawiając następny nagłówek pod nieprzewidywalnym przesunięciem. Reguły, które z tego kontraktu wynikają, są pojedynczo niewielkie. Długość danych z ustawionym bitem 31 to znacznik nieznanej długości z T.88 §7.2.7, a handleSegmentDataLength mapuje ją na wartość ujemną, którą readSegments odrzuca od razu, zamiast skanować dalej w poszukiwaniu terminatora. Każdy numer segmentu, do którego się odwołano, musi być mniejszy od numeru bieżącego segmentu i musi już istnieć, więc odwołanie w przód albo do nieistniejącego segmentu pada, zanim jakikolwiek region spróbuje je rozwiązać. END_OF_PAGE i END_OF_FILE muszą deklarować zero bajtów danych. Segment Profiles (typ 52) niesie 32-bitowy licznik, po nim tyle 32-bitowych identyfikatorów i ani jednego piksela, więc jest sprawdzany jako 4 plus 4 razy licznik względem zadeklarowanej długości, pomijany i trzymany na liście segmentów tylko po to, żeby późniejsze segmenty mogły się do niego odwołać po numerze. Nieznany identyfikator profilu to nie to samo co nieznane kodowanie, a potraktowanie go jak nieznanego kodowania odrzucałoby pliki, które dekodują się bez najmniejszego problemu

// TJBIG2StreamDecoder.readSegments, PDFlibJBIG2.pas
DataLength := segmentHeader.getSegmentDataLength;
if DataLength < 0 then
  raise EJBIG2DecodeError.Create(Context +
    'unknown or oversized segment length is not supported');
if DataLength > Length(reader.Data) - reader.bytePointer then
  raise EJBIG2DecodeError.Create(Context + 'truncated segment data');
DataEnd := reader.bytePointer + DataLength;
for I := 0 to noOfReferredToSegments - 1 do
  if (referredToSegments[I] >= segmentHeader.getSegmentNumber) or
     (findSegment(referredToSegments[I]) = nil) then
    raise EJBIG2DecodeError.Create(Context + 'invalid segment reference');
// ... utwórz obiekt segmentu dla tego typu ...
reader.SegmentEnd := DataEnd;
segment.readSegment;
if reader.bytePointer > DataEnd then
  raise EJBIG2DecodeError.Create(Context +
    'decoded data exceeds declared segment length');
if reader.bytePointer < DataEnd then
begin
  reader.bytePointer := DataEnd;   // MMR może zostawić EOFB nieodczytany
  reader.bitPointer := 7;
end;

Ogon tej pętli to miejsce, w którym wcześniejsza wersja dekodera myliła się na regionach kodowanych MMR. Dekoder MMR wie, że skończył, gdy powstanie ostatni piksel ostatniego wiersza, co może się zdarzyć, zanim pochłonie terminator EOFB, który T.88 §6.2.5.7 umieszcza na końcu danych. Stary kod zakładał, że czytnik stoi już na następnym nagłówku, więc resztkowe bajty terminatora były parsowane jako numer segmentu, a strumień padał kilka bajtów dalej z mylącym komunikatem. Teraz wygrywa zadeklarowany koniec: czytanie poza niego jest błędem, zatrzymanie się przed nim jest normalne, a czytnik przesuwa się na DataEnd z wyzerowanym wskaźnikiem bitu, żeby następny nagłówek był czytany stamtąd, gdzie plik zapowiedział. Ta sama dyscyplina obowiązuje wszędzie, gdzie PDFlibPas parsuje niezaufane struktury PDF: zadeklarowana długość jest granicą i dekoder nie rozgląda się za życzliwszą

Skąd refinement w trybie Huffmana czyta rozmiar swojej bitmapy?

Zanim startuje dekoder arytmetyczny i z pola, które istnieje tylko w trybie Huffmana. Kiedy instancja regionu tekstowego niesie refinement (RI jest niezerowe) i ustawione jest SBHUFF, T.88 §6.4.11 każe dekoderowi odczytać RDW, RDH, RDX i RDY wybranymi dla nich tabelami, potem BMSIZE tabelą RSIZE, potem wyrównać do granicy bajtu i dopiero wtedy przeprowadzić ogólne dekodowanie refinement na dokładnie BMSIZE bajtach. Regiony tekstowe w trybie arytmetycznym takiego pola nie mają, a dekoder dzielący jedną ścieżkę kodu dla obu trybów je pominie, uruchomi dekoder arytmetyczny dwa albo więcej bajtów za wcześnie i przeprowadzi refinement każdego symbolu względem śmieci. Ścieżka słownika symboli z REFAGG i pojedynczą instancją refinement, opisana w §6.5.8.2.2, ma to samo pole BMSIZE z tymi samymi konsekwencjami. W PDFlibPas górną granicą tego rozmiaru jest TStreamReader.SegmentEnd, czyli koniec bieżącego segmentu ustawiony przez readSegments, a nie koniec całego strumienia, bo BMSIZE, którego nie da się zaspokoić inaczej niż pożyczając bajty z następnego segmentu, jest wadliwy, a walidowanie go względem długości strumienia pozwoliłoby dekoderowi arytmetycznemu czytać w następny nagłówek. Dolna granica dwóch bajtów odpowiada początkowej parze bajtów, którą dekoder arytmetyczny zawsze zjada, a po refinement czytnik przeskakuje na RefinementEnd niezależnie od tego, jak daleko dekoder arytmetyczny wybiegł do przodu, bo jego końcowa pozycja nie jest pozycją następnego pola kodowanego Huffmanem

// Dekodowanie regionu tekstowego TJBIG2Bitmap, ścieżka refinement w trybie Huffmana
RefinementSize := huffmanDecoder.decodeInt(huffmanRSizeTable).intResult;
huffmanDecoder.consumeRemainingBits;
if (RefinementSize < 2) or
   (RefinementSize > huffmanDecoder.reader.SegmentEnd -
                     huffmanDecoder.reader.bytePointer) then
  raise EJBIG2DecodeError.Create('invalid refinement bitmap size');
RefinementEnd := huffmanDecoder.reader.bytePointer + RefinementSize;
arithmeticDecoder.start;
// ... readGenericRefinementRegion ...
if huffmanDecoder.reader.bytePointer > RefinementEnd then
  raise EJBIG2DecodeError.Create('refinement data exceeds declared size');
huffmanDecoder.reader.bytePointer := RefinementEnd;
huffmanDecoder.reader.bitPointer := 7;

Co zostało zweryfikowane, a co nadal jest odrzucane

Próbka, od której to wszystko się zaczęło, obraz JBIG2 o wymiarach 500 na 473 piksele z własnymi tabelami i refinement w trybie Huffmana, dekoduje się teraz do bitmapy z zerem różniących się pikseli względem niezależnego dekodera, a syntetyczne fixture'y bitmap zbiorczych o szerokościach 7 i 9 bitów dają oczekiwane wiersze w obu przypadkach. Dwa niezależne dekodery, które nie zgadzały się co do oryginalnej próbki, nadal nie zgadzają się ze sobą; PDFlibPas zgadza się z jednym z nich, a uczciwe stwierdzenie brzmi, że natywne wyjście zgadza się z jedną niezależną implementacją i ze specyfikacją tak, jak ją czytamy, a nie że zgadzają się wszystkie dekodery świata. Wadliwa strona zestawu testów obejmuje:

• zarezerwowany bit flagi albo zarezerwowaną wartość selektora
• tabelę uciętą w środku wiersza
• długości prefiksów przekraczające pojemność i prefiksy dłuższe niż 32 bity
• region, którego selektory żądają więcej własnych tabel, niż region ich wymienia
• potwierdzenie, że nieświeże wyjście jest czyszczone po nieudanym dekodowaniu, a nie zostawiane wywołującemu do pomylenia z wynikiem

Trzy ograniczenia pozostają celowe. Organizacja strumienia z dostępem swobodnym, w której wszystkie nagłówki segmentów poprzedzają wszystkie dane segmentów, rzuca JBIG2 random-access organisation is not supported od razu po odczytaniu flag nagłówka pliku, bo nie ma reprezentatywnej próbki, na której dałoby się to zweryfikować, a połowicznie zaimplementowana ścieżka jest gorsza niż nazwane odrzucenie. Własne tabele są ograniczone do 65 536 linii i 32-bitowych prefiksów. A publiczne wejście dekodowania, TPLJBIG2Decoder.LoadFromByteArray, zwraca bitmapę pierwszej strony w kolejności strumienia przez getPageAsJBIG2Bitmap(0), czyli pierwszy napotkany segment informacji o stronie, zamiast szukać skojarzenia ze stroną zero; osadzone strumienie PDF rutynowo numerują swoją jedyną stronę jako 1, a pytanie o stronę 0 po skojarzeniu nie znalazłoby niczego. Tekst błędu ląduje w TPLJBIG2Decoder.LastError, wewnętrznej diagnostyce dekodera niosącej numer segmentu, jego typ i przesunięcie bajtowe miejsca awarii, i to nie jest to samo co biblioteczne TPDFlib.LastErrorCode. Nic z tego nie dotyczy strony kodowania, którą omawiają notatki o backendach kodera JBIG2 i sposobie ich linkowania; ścieżka odczytu musi przyjąć to, co zdecydował się wysłać czyjś koder, i dzieli swoje reguły z resztą stosu obsługi obrazów, w tym z wbudowanym dekoderem TIFF i jego odrzuceniami BigTIFF oraz układu kafelkowego: odmawiaj z nazwy, nigdy nie pożyczaj bajtów przez zadeklarowaną granicę i utrzymuj arytmetykę tak szeroką, żeby zawinięta wartość pośrednia nie mogła ujść za poprawną odpowiedź. Jeśli oceniasz natywną ścieżkę odczytu JBIG2 dla Delphi albo C++Buildera, dekoder i reszta obsługi obrazów są opisane na stronie PDF Library for Delphi