Siatki halftone JBIG2 w PDFlibPas: HSKIP i ujemne offsety

PDFlibPas naprawił dwie niezależne usterki we własnym dekoderze regionów halftone JBIG2: w v3.539.37 maska skip HSKIP jest indeksowana jako HSKIP[ng, mg], tak jak definiuje to ITU-T T.88 §6.6.5.1, a w v3.539.38 siatki docierające do ujemnych współrzędnych, przez ujemne HGX albo HGY albo przez obrót, są rozmieszczane prawdziwym przesunięciem floor. Przed tymi wydaniami dotknięte regiony halftone wychodziły popsute albo przesunięte, bez zgłoszenia błędu. Oba błędy kryły się za danymi testowymi, które akurat były symetryczne albo nieujemne, a drugi włącza się na właściwości Delphi i Free Pascal, która kąsa daleko poza JBIG2: shr na liczbie ze znakiem to przesunięcie logiczne, a nie arytmetyczne >>, które zakłada standard

Regiony halftone to najrzadszy typ regionu JBIG2, więc dekoder potrafi przerobić tysiące zeskanowanych dokumentów, zanim spotka zrastryzowane zdjęcie zakodowane jako jeden z nich. A gdy już spotka, awaria jest paskudna: plik się parsuje, długości segmentów się sumują, strona ma właściwy rozmiar, a region to śmieci

Co właściwie dekoduje region halftone JBIG2?

Region halftone JBIG2 to siatka małych bitmap wybranych ze słownika wzorców, a prawdziwa praca dekodera to policzenie indeksu dla każdej komórki siatki i pozycji pikselowej, w której ta komórka wyląduje. Słownik wzorców trzyma HNUMPATS wzorców o rozmiarze HPW × HPH pikseli. Segment regionu halftone opisuje potem siatkę HGW kolumn na HGH wierszy i obraz w skali szarości tego samego rozmiaru, zakodowany jako bitplane'y kodowane Greya. Każdy bitplane jest dekodowany procedurą regionu generycznego na bitmapie HGW × HGH, najbardziej znacząca płaszczyzna pierwsza, a płaszczyzny razem dają każdej komórce jej indeks wzorca

Rozmieszczanie komórek używa arytmetyki stałoprzecinkowej z 8-bitową częścią ułamkową. Początek siatki HGX, HGY to para wartości 32-bitowych, a wektor siatki HRX, HRY opisuje krok między sąsiednimi komórkami, co pozwala na obróconą siatkę. Dla wiersza siatki mg i kolumny siatki ng T.88 §6.6.5 liczy pozycję pikselową tak:

• x = (HGX + mg × HRY + ng × HRX) >> 8
• y = (HGY + mg × HRX − ng × HRY) >> 8

Maska skip wchodzi przez opcjonalną flagę HENABLESKIP. Gdy flaga jest ustawiona, §6.6.5.1 buduje bitmapę HSKIP o rozmiarze HGW × HGH i ustawia HSKIP[ng, mg] na 1 dla każdej komórki, której wzorzec leży w całości poza regionem: x + HPW <= 0, x >= HBW, y + HPH <= 0 albo y >= HBH. Bitplane'y w skali szarości są potem dekodowane z tą maską jako skip bitmapa regionu generycznego, więc dekoder arytmetyczny ani nie czyta, ani nie aktualizuje kontekstu dla komórki pominiętej. Dekoder i enkoder muszą zgadzać się co do każdego bitu HSKIP, bo inaczej oba koder arytmetyczne tracą z sobą krok

Dlaczego transponowana maska HSKIP psuła tylko siatki niekwadratowe?

Maska skip była zapisywana z zamienionymi współrzędnymi, a obnażała ją tylko siatka niekwadratowa, bo siatka kwadratowa trzyma każdą zamienioną współrzędną wewnątrz maski. PDFlibPas trzyma bitmapy z akcesorem pikselowym (column, row), a kod budujący maskę przekazywał (mg, ng), wiersz pierwszy. Dekoder bitplane'ów w skali szarości czyta maskę poprawnie jako (ng, mg). Pętla rozmieszczania wzorców czytała ją z powrotem w zamienionej kolejności budowniczego, więc oboje się zgadzali, i sama przegląd logiki rozmieszczania by to przepuściła. Pułapka nazewnicza pogorszyła sprawę: w pętli rozmieszczania zmienna zwana col iteruje wiersze siatki, a Row iteruje kolumny siatki

Weźmy siatkę 5 × 3 ze wzorców 4 × 4 na regionie 16 × 8, którą v3.539.37 używa jako przypadku regresyjnego. Przy HRX = 1024 i HRY = 0 kolumna siatki 4 ląduje na x = 16, a wiersz siatki 2 na y = 8, oba poza regionem. Poprawna maska zaznacza siedem komórek: całą kolumnę 4 i cały wiersz 2. Zamienione zapisy próbowały ustawić piksele w wierszach o indeksach 3 i 4 w masce mającej tylko trzy wiersze wysokości, a setter bitmapy po cichu ignorował te zapisy poza zakresem. Przeżyła kolumna 2, wiersze od 0 do 2. Dekoder pominął więc dwie komórki zakodowane przez enkoder i zdekodował sześć komórek, które enkoder pominął

Dekoder arytmetyczny nie zawodzi, gdy to się dzieje. Dekoduje dodatkowe piksele z bitów należnych dalszym komórkom, jego konteksty czytają złych sąsiadów, a każdy indeks wzorca po pierwszej niezgodzie to szum — dlatego objawem był popsuty region, a nie kilka źle rozmieszczonych komórek. Na siatce kwadratowej ten sam błąd bywa niewidoczny: żadna zamieniona współrzędna nie wychodzi z maski, a gdy komórki poza regionem są symetryczne względem przekątnej — na przykład siatka wystająca za prawą i dolną krawędź o tę samą liczbę komórek — transponowana maska jest bit w bit poprawną maską. HENABLESKIP jest przy okazji opcjonalny, musi być 0, gdy obraz w skali szarości jest kodowany MMR, i enkodery rzadko go ustawiają, więc błąd miał niewiele dróg na jaw. Od v3.539.37 budowniczy zapisuje HSKIP[ng, mg], a pętla rozmieszczania czyta tę samą kolejność

Dlaczego ujemne offsety siatki halftone zawodzą na trzech warstwach?

Siatka halftone startująca na lewo od regionu albo nad nim wywalała PDFlibPas w trzech osobnych miejscach, a każda usterka kryła następną. T.88 pozwala na taką geometrię celowo. Enkoder, który kalibruje raster do strony zamiast do regionu, albo używa obróconej siatki, naturalnie produkuje ujemne narożniki komórek, które region przycina. v3.539.38 naprawiło wszystkie trzy warstwy naraz, bo naprawa dowolnej z osobna zmieniała tylko objaw

Warstwa 1: pole ze znakiem czytane jako bez znaku

T.88 §7.4.5.1.2 definiuje HGX i HGY jako wartości 32-bitowe ze znakiem, ale dekoder czytał je tym samym helperem 32-bitowym, którego używał dla pól bez znaku, a ten helper dociskał każdy ujemny wynik do 0. Siatka mająca startować na HGX = -900 była po cichu przeciągana na początek regionu. W przypadku regresyjnym v3.539.38 cały obraz wychodził dwa wiersze za nisko. Docisk wyjaśnia też, dlaczego pozostałe dwie usterki przeżyły tak długo: przy początku wymuszonym na nieujemnym ujemna współrzędna mogła się pojawić tylko przez obróconą siatkę z HRY > 0, gdzie y = HGY + mg × HRX − ng × HRY spada poniżej zera dla dalszych kolumn siatki

Warstwa 2: shr to nie >> 8

T.88 pisze >> 8 i ma na myśli przesunięcie arytmetyczne, które zaokrągla w stronę minus nieskończoności. Dekoder przetłumaczył to jako shr 8. W Delphi i Free Pascal shr na liczbie ze znakiem to przesunięcie logiczne: bit znaku jest wsuwany jako zero. Dla Integer trzymającego -512 shr 8 daje 16777214 zamiast -2. Wzorzec, który powinien zostać narysowany na y = -2 i przycięty do dolnej połowy, został wysłany 16 milionów wierszy w dół i upuszczony jako poza regionem. Nic nie wybuchło; górny wiersz halftone po prostu zniknął

Warstwa 3: porównywanie stałoprzecinkowo zamiast w pikselach

Test skip porównywał wartości stałoprzecinkowe, a nie pozycje pikselowe, a te dwie przestają być równoważne, gdy tylko część ułamkowa jest niezerowa. Pierwotny kod omijał przesunięcie logiczne, testując xx + HPW × 256 <= 0 na wartości bez przesunięcia — rzekomy odpowiednik testu z T.88. Przy HGX = -900 i wzorcu 4-pikselowym wychodzi -900 + 1024 = 124, czyli dodatnio, więc komórka nie jest pomijana. Standard przesuwa najpierw: floor(-900 / 256) = -4, a -4 + 4 = 0 spełnia x + HPW <= 0, więc komórka leży w całości na zewnątrz i musi być pominięta. Enkoder ją pominął, dekoder ją zdekodował, a obraz w skali szarości dryfował dokładnie jak w przypadku transponowanej maski

Przypadek regresyjny z v3.539.38 używa siatki 4 × 3 ze wzorców 4 × 4 przy HGX = -900, HGY = -512, HRX = 1024 na regionie 12 × 10. Kolumny siatki lądują na x = -4, 0, 4 i 8, więc kolumna 0 jest w całości na zewnątrz i należy do HSKIP; wiersze siatki lądują na y = -2, 2 i 6, więc wiersz 0 trzeba przyciąć do jego dolnych dwóch wierszy pikseli, a nie upuszczać. Naprawianie warstw po jednej odtwarza tę drabinę:

Naprawione usterki	Zdekodowany region
Żadna (przed v3.539.38)	Siatka przyciągnięta do początku, cały obraz dwa wiersze za nisko
Tylko odczyt HGX / HGY ze znakiem	Pierwszy wiersz siatki brakuje, reszta popsuta dryfem testu skip
Odczyt ze znakiem, przesunięcie floor i test skip w przestrzeni pikseli	Identyczny, piksel w piksel, ze stroną policzoną z T.88 §6.6.5 i z dwoma niezależnymi dekoderami referencyjnymi

Poprawka to jeden helper, HalftoneGridPixel, wspólny dla budowniczego maski skip i pętli rozmieszczania. Akumuluje współrzędną w Int64, żeby duży iloczyn mg × HRX nie mógł się przepełnić, dzieli przez 256 z zaokrągleniem w stronę minus nieskończoności i dociska do ±MaxInt div 2, żeby popsuta siatka nie przepełniła późniejszej arytmetyki bitmap. Test skip porównuje teraz te wartości pikselowe z HPW, HPH, HBW i HBH, dokładnie tak, jak stanowi §6.6.5.1

Jak napisać arytmetyczne przesunięcie w prawo w Delphi?

Delphi nie ma operatora przesunięcia arytmetycznego, więc poprawne przesunięcie w prawo ze znakiem trzeba zapisać jako dzielenie floor, a gołe div to nie jest to dzielenie. div obcina w stronę zera. Dla wartości nieujemnych obcinanie i floor się zgadzają, a zgadzają się też dla wartości ujemnych będących dokładnymi wielokrotnościami dzielnika, dlatego -512 div 256 = -2 wygląda dobrze w szybkim teście. Rozjeżdżają się wszędzie indziej: -900 div 256 to -3, podczas gdy floor to -4, a -1 div 256 to 0, podczas gdy floor to -1. Współrzędna JBIG2 z niezerową częścią ułamkową to dokładnie ten przypadek, w którym div daje zły piksel

Na kompilatorach Delphi Win32 i Win64 zmienna Integer trzymająca -512 po przesunięciu w prawo o 8 daje 16777214, a Int64 trzymające -512 daje 72057594037927934. Free Pascal też definiuje shr jako przesunięcie logiczne i dostarcza SarLongint i SarInt64 w jednostce System jako wersję arytmetyczną, ale tych funkcji nie ma w Delphi, więc kod wspólny dla obu kompilatorów potrzebuje własnego helpera:

// Dzielenie floor: zaokrągla w stronę minus nieskończoności dla dowolnych znaków A i B.
// B nie może być 0, a FloorDiv(Low(Integer), -1) przepełnia się tak samo jak div
function FloorDiv(A, B: Integer): Integer;
begin
  Result := A div B;
  if (A mod B <> 0) and ((A < 0) <> (B < 0)) then
    Dec(Result);
end;

// Arytmetyczne przesunięcie w prawo (C i T.88 ">>" na wartościach ze znakiem).
// Dla ujemnego Value not Value = -Value - 1 jest nieujemne, więc
// logiczne shr jest tam bezpieczne, a zewnętrzne not odwraca wynik
function SarInt32(Value: Integer; Shift: Integer): Integer;  // Shift 0..31
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

function SarInt64(Value: Int64; Shift: Integer): Int64;      // Shift 0..63
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

Trik z not nigdy nie przesuwa liczby ujemnej, więc nie zależy od tego, jak kompilator obchodzi się z bitem znaku, i nigdy się nie przepełnia, łącznie z Low(Integer). Oba helpery zgodziły się z referencją floor na Int64 na kilku milionach wartości, przy każdym przesunięciu od 0 do 31 oraz na krawędziach Low(Integer) i High(Integer) na Delphi Win32, Delphi Win64 i Free Pascal x86_64. Test przytomności warto trzymać w każdym teście jednostkowym, który dotyka współrzędnych:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  przesunięcie logiczne, stary błąd
  Writeln(V div 256);         // -3        obcinanie w stronę zera
  Writeln(FloorDiv(V, 256));  // -4        to, co T.88 rozumie przez >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) też zwraca -4, ale jej objazd przez Double traci precyzję dla wartości Int64 powyżej 2⁵³, więc geometria na liczbach całkowitych powinna zostać w liczbach całkowitych

Które wywołania PDFlibPas odpalają dekoder halftone?

Dekoder halftone JBIG2 rusza, gdy PDFlibPas renderuje stronę wbudowanym rendererem, bo renderowanie potrzebuje pikseli. RenderPageToFile i RenderPageToStream docierają do niego oba przez strumienie obrazów JBIG2Decode strony, więc przerenderowanie strony z halftone to najprostszy sposób potwierdzenia, że v3.539.38 zmienia twoje wyjście. Ten sam dekoder obsługuje pozostałe typy regionów JBIG2, opisane w własnych tabelach Huffmana JBIG2 w czystym dekoderze Pascal i dekodowaniu plików JBIG2 o dostępie losowym w Delphi, a wyrenderowana bitmapa zasila konwersje takie jak renderowanie stron PDF do 1-bitowej monochromatyki

uses
  SysUtils, PDFlibrary;

var
  Lib: TPDFlib;
  Page: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile('scanned-halftone.pdf', '') <> 1 then
      raise Exception.CreateFmt('Load failed, error %d', [Lib.LastErrorCode]);
    for Page := 1 to Lib.PageCount do
      // Renderowanie dekoduje każdy region JBIG2, halftony wliczone
      if Lib.RenderPageToFile(150, Page, PDF_RENDER_PNG,
        Format('page-%.3d.png', [Page])) <> 1 then
        Writeln('Page ', Page, ' was not rendered');
  finally
    Lib.Free;
  end;
end.

Ekstrakcja obrazów zwykle jedzie inną ścieżką. GetPageImageList zwraca obrazy JBIG2 w formie natywnej, a SaveImageListItemDataToFile albo GetImageListItemDataToString wręcza samodzielny plik JBIG2 złożony z bajtów strumienia: nagłówek pliku, dane JBIG2Globals i segment końca pliku wokół danych strony. Właściwość 400 GetImageListItemIntProperty raportuje 6 dla takiego elementu. Nic nie jest dekodowane na tej ścieżce, więc wyekstrahowany .jb2, który wygląda poprawnie w innej przeglądarce, podczas gdy wyrenderowana strona pokazuje szum, był typowym znakiem tych dwóch błędów halftone:

var
  ListID, I: Integer;
begin
  Lib.SelectPage(1);
  ListID := Lib.GetPageImageList(0);
  if ListID = 0 then
    Exit;
  try
    for I := 1 to Lib.GetImageListCount(ListID) do
      if Lib.GetImageListItemIntProperty(ListID, I, 400) = 6 then  // standalone JBIG2
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

Gdy maski albo konwersja kolorów wymuszą fallback przez renderowanie, element wraca jako zdekodowana bitmapa i dekoder halftone faktycznie rusza. Więcej o listach obrazów w ekstrakcji tekstu, obrazów i fontów z PDF w Delphi

Ściąga: reguły siatki halftone JBIG2

• Indeksuj maskę skip jako HSKIP[ng, mg], kolumna siatki pierwsza, i czytaj ją w tej samej kolejności wszędzie tam, gdzie rozmieszczasz komórki (T.88 §6.6.5.1, naprawione w PDFlibPas v3.539.37)
• Testuj każdy kod halftone albo siatki na siatce niekwadratowej i asymetrycznym zestawie komórek poza regionem, bo siatka kwadratowa potrafi kompletnie ukryć transponowany indeks
• Czytaj HGX i HGY jako wartości 32-bitowe ze znakiem (T.88 §7.4.5.1.2), nigdy przez helper bez znaku, który dociska ujemne
• Przetłumacz >> 8 ze standardu jako dzielenie floor przez 256, nie jako shr 8 i nie jako div 256
• Rób test skip na przesuniętych pozycjach pikselowych; forma stałoprzecinkowa różni się zawsze, gdy część ułamkowa jest niezerowa, jak pokazuje HGX = -900 z 4-pikselowym wzorcem
• Akumuluj współrzędne siatki w Int64 i dociskaj je przed przekazaniem do kodu bitmap, żeby popsuta siatka nie przepełniła arytmetyki
• Zaktualizuj do v3.539.38 lub nowszego, jeśli twoje dokumenty zawierają regiony halftone z HENABLESKIP, ujemnymi początkami siatki albo obróconymi siatkami

PDFlibPas renderuje, ekstrahuje i edytuje dokumenty PDF z Delphi i C++Buildera natywnym dekoderem JBIG2 w Pascalu, który obsługuje teraz maski skip halftone, ujemne początki siatki i obrócone siatki tak, jak określa T.88. Funkcje, wydania i wersję próbną znajdziesz na PDFlibPas Delphi PDF library