Mřížky halftone JBIG2 v PDFlibPas: HSKIP a záporné offsety

PDFlibPas opravil dvě nezávislé závady ve svém nativním dekodéru halftone regionů JBIG2: ve v3.539.37 se maska HSKIP indexuje jako HSKIP[ng, mg], tak jak ji definuje ITU-T T.88 §6.6.5.1, a ve v3.539.38 se mřížky, které dosáhnou záporných souřadnic, ať záporným HGX nebo HGY, anebo rotací, umisťují se skutečným floor posunem. Před těmi vydáními vyšly postižené halftone regiony zmatené nebo posunuté, aniž se ozvala žádná chyba. Oba bugy se skryly za testovacími daty, která náhodou byla symetrická nebo nezáporná, a ten druhý otevírá vlastnost Delphi a Free Pascalu, která kouše daleko mimo JBIG2: shr nad znaménkovým integerem je logický posun, ne aritmetické >>, které standard předpokládá

Halftone regiony jsou nejvzácnější typ JBIG2 regionu, takže dekodér může zpracovat tisíce naskenovaných dokumentů, než potká rastrované foto zakódované jako jeden. Když se to stane, selhání je odporné: soubor se naparsuje, délky segmentů sedí, stránka má správnou velikost a region je smetí

Co halftone region JBIG2 doopravdy dekóduje?

Halftone region JBIG2 je mřížka malých bitmap vybraných z pattern slovníku a skutečná práce dekodéru je spočítat index pro každou buňku mřížky a pixelovou pozici, kam ta buňka dopadne. Pattern slovník drží HNUMPATS patternů o HPW × HPH pixelech. Segment halftone regionu pak popisuje mřížku HGW sloupců krát HGH řádků a obrázek ve stupních šedi stejné velikosti, zakódovaný jako Grayem kódované bitplanes. Každý bitplane se dekóduje generickou region procedurou nad bitmapou HGW × HGH, nejvýznamnější plane první, a plany dohromady dávají každé buňce její pattern index

Umisťování buněk používá pevnou řádovou čárku s 8bitovým zlomkem. Počátek mřížky HGX, HGY je pár 32bitových hodnot a vektor mřížky HRX, HRY popisuje krok mezi sousedními buňkami, což umožňuje otočenou mřížku. Pro řádek mřížky mg a sloupec mřížky ng počítá T.88 §6.6.5 pixelovou pozici takto:

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

Maska skip vstupuje přes volitelný příznak HENABLESKIP. Když je příznak nastavený, §6.6.5.1 postaví bitmapu HSKIP o HGW × HGH a nastaví HSKIP[ng, mg] na 1 pro každou buňku, jejíž pattern leží celý mimo region: x + HPW <= 0, x >= HBW, y + HPH <= 0 nebo y >= HBH. Bitplanes ve stupních šedi se pak dekódují s tou maskou jako skip bitmapou generického regionu, takže aritmetický dekodér pro přeskočenou buňku ani nečte, neaktualizuje kontext. Dekodér a kodér musí souhlasit v každém bitu HSKIP, jinak se oba aritmetické kodéry rozejdou

Proč přehozená maska HSKIP rozbila jen nečtvercové mřížky?

Maska skip se zapisovala s přehozenými souřadnicemi a odhalila ji jen nečtvercová mřížka, protože čtvercová mřížka drží každou přehozenou souřadnici uvnitř masky. PDFlibPas ukládá bitmapy s pixelovým přístupem (column, row) a kód, který masku stavěl, předával (mg, ng), řádek první. Dekodér bitplanes ve stupních šedi čte masku správně jako (ng, mg). Smyčka umisťující patterny ji četla zpátky v přehozeném pořadí stavitele, takže obě strany si rozuměly a samotná revize umisťovací logiky by ji pustila. Past v názvech to ještě zvýraznila: v umisťovací smyčce proměnná zvaná col iteruje řádky mřížky a Row iteruje sloupce mřížky

Vezměte mřížku 5 × 3 patternů 4 × 4 na regionu 16 × 8, kterou v3.539.37 používá jako svůj regresní případ. S HRX = 1024 a HRY = 0 dopadne sloupec mřížky 4 na x = 16 a řádek mřížky 2 na y = 8, oboje mimo region. Správná maska označí sedm buněk: celý sloupec 4 a celý řádek 2. Přehozené zápisy se snažily nastavit pixely na řádkových indexech 3 a 4 v masce vysoké jen tři řádky a bitmapový setter je potichu ignoroval jako mimo rozsah. Co přežilo, byl sloupec 2, řádky 0 až 2. Dekodér proto přeskočil dvě buňky, které kodér zakódoval, a dekódoval šest buněk, které kodér přeskočil

Aritmetický dekodér v tomhle okamžiku nespadne. Dekóduje navíc pixely z bitů, které patří pozdějším buňkám, jeho kontexty čtou špatné sousedy a každý pattern index po první neshodě je šum — proto symptomem byl zmatený region a ne pár špatně umístěných buněk. Na čtvercové mřížce je tentýž bug často neviditelný: žádná přehozená souřadnice neopustí masku a když jsou buňky mimo region symetrické kolem diagonály, třeba mřížka přečnívající pravý a dolní hranu o stejný počet buněk, je přehozená maska bit od bitu tou správnou. HENABLESKIP je navíc volitelný, musí být 0, když je obrázek ve stupních šedi MMR-kódovaný, a kodéry ho nastavují zřídka, takže bug měl velmi málo cest na povrch. Od v3.539.37 stavitel zapisuje HSKIP[ng, mg] a umisťovací smyčka čte totéž pořadí

Proč záporné offsety halftone mřížky selžou ve třech vrstvách?

Halftone mřížka začínající vlevo od nebo nad svým regionem rozbila PDFlibPas na třech oddělených místech a každá závada skrývala tu další. T.88 tahle geometrie dovoluje záměrně. Kodér, který zarovná svůj rastr na stránku místo na region, nebo použije otočenou mřížku, přirozeně vyrobí záporné rohy buněk, které region ořízne. v3.539.38 opravil všechny tři vrstvy naráz, protože opravit jakoukoli jednu samotnou znamenalo jen vyměnit symptom

Vrstva 1: znaménkové pole čtené jako bezznaménkové

T.88 §7.4.5.1.2 definuje HGX a HGY jako znaménkové 32bitové hodnoty, ale dekodér je čtl stejným 32bitovým pomocníkem, jaký používal pro bezznaménková pole, a ten pomocník seřízl každý záporný výsledek na 0. Mřížka určená začít na HGX = -900 se potichu přesunula na počátek regionu. V regresním případě v3.539.38 vyšel celý obrázek dva řádky níž, než měl. Ten zářez zároveň vysvětluje, proč ostatní dvě závady přežily tak dlouho: s počátkem vynuceně nezáporným mohla záporná souřadnice vzniknout jen otočenou mřížkou s HRY > 0, kde y = HGY + mg × HRX − ng × HRY klesá pod nulu u pozdějších sloupců mřížky

Vrstva 2: shr není >> 8

T.88 píše >> 8 a myslí tím aritmetický posun, který zaokrouhluje k mínus nekonečnu. Dekodér to přeložil jako shr 8. V Delphi a Free Pascalu je shr nad znaménkovým integerem logický posun: znaménkový bit se posouvá dovnitř jako nula. Pro Integer držící -512 dá shr 8 16777214 místo -2. Pattern, který se měl kreslit na y = -2 a oříznout na spodní polovinu, se poslal 16 milionů řádků dolů a upustil se jako mimo region. Nic nespadlo; horní řádek halftonu prostě zmizel

Vrstva 3: porovnávání pevné řádové čárky místo pixelů

Test skip porovnával hodnoty pevné řádové čárky, ne pixelové pozice, a jakmile je zlomek nenulový, nejsou ty dvě věci ekvivalentní. Původní kód logický posun obešel tím, že testoval xx + HPW × 256 <= 0 na neposunuté hodnotě — domnělý ekvivalent testu z T.88. S HGX = -900 a 4pixelovým patternem to dá -900 + 1024 = 124, což je kladné, takže buňka se nepřeskočí. Standard posouvá nejdřív: floor(-900 / 256) = -4 a -4 + 4 = 0 splňuje x + HPW <= 0, takže buňka leží celá vně a musí se přeskočit. Kodér ji přeskočil, dekodér ji dekódoval a obrázek ve stupních šedi se rozjel úplně stejně jako v případě přehozené masky

Regresní případ z v3.539.38 používá mřížku 4 × 3 patternů 4 × 4 na HGX = -900, HGY = -512, HRX = 1024 na regionu 12 × 10. Sloupce mřížky dopadnou na x = -4, 0, 4 a 8, takže sloupec 0 je celý venku a patří do HSKIP; řádky mřížky dopadnou na y = -2, 2 a 6, takže řádek 0 se musí oříznout na spodní dva pixelové řádky, ne upustit. Oprava vrstev jedna po druhé reprodukuje tenhle stack:

Opravené závady	Dekódovaný region
Žádná (před v3.539.38)	Mřížka přitahaná na počátek, celý obrázek dva řádky níž
Jen čtení znaménkových HGX / HGY	První řádek mřížky chybí, zbytek zmatený rozjezdem skip testu
Znaménkové čtení, floor posun a skip test v pixelovém prostoru	Identický, pixel za pixel, se stránkou spočítanou z T.88 §6.6.5 a se dvěma nezávislými referenčními dekodéry

Oprava je jeden pomocník, HalftoneGridPixel, sdílený stavitelem masky skip a umisťovací smyčkou. Souřadnici akumuluje v Int64, takže velký součin mg × HRX nemůže přetéct, dělí 256 s zaokrouhlením k mínus nekonečnu a seřezává na ±MaxInt div 2, takže poškozená mřížka nemůže později přetéct bitmapovou aritmetiku. Test skip teď porovnává tyhle pixelové hodnoty proti HPW, HPH, HBW a HBH, přesně jak to staví §6.6.5.1

Jak v Delphi napíšete aritmetický posun doprava?

Delphi nemá operátor aritmetického posunu, takže správný znaménkový posun doprava se musí napsat jako dělení floor a obyčejné div tímto dělením není. div zaokrouhluje k nule. Pro nezáporné hodnoty se zaokrouhlování k nule a floor shodují a shodují se i pro záporné hodnoty, které jsou přesnými násobky dělitele — proto -512 div 256 = -2 v rychlém testu vypadá dobře. Všude jinde se rozcházejí: -900 div 256 je -3, zatímco floor je -4, a -1 div 256 je 0, zatímco floor je -1. Souřadnice JBIG2 s nenulovým zlomkem je přesně ten případ, kdy div dá špatný pixel

Na kompilátorech Delphi Win32 a Win64 dá proměnná Integer držící -512 posunutá doprava o 8 hodnotu 16777214 a Int64 držící -512 dá 72057594037927934. Free Pascal definuje shr také jako logický posun a dodává SarLongint a SarInt64 ve své unitě System pro aritmetickou verzi, ale ty funkce v Delphi neexistují, takže kód sdílený mezi oběma kompilátory potřebuje vlastního pomocníka:

// Dělení floor: zaokrouhluje k mínus nekonečnu pro jakékoli znaménko A a B.
// B nesmí být 0 a FloorDiv(Low(Integer), -1) přetéká stejně jako 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;

// Aritmetický posun doprava (">>" z C a T.88 nad znaménkovými hodnotami).
// Pro záporné Value je not Value = -Value - 1 nezáporné, takže tam je
// logický shr bezpečný a vnější not vrátí výsledek zpátky
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 s not nikdy neposouvá záporné číslo, takže nezávisí na tom, jak kompilátor zachází se znaménkovým bitem, a nikdy nepřeteče, včetně Low(Integer). Oba pomocníci se shodovali s Int64 floor referencí přes několik milionů hodnot, každý posun od 0 do 31 a hrany Low(Integer) a High(Integer) na Delphi Win32, Delphi Win64 a Free Pascal x86_64. Sanity check, který stojí za to držet v každém unit testu, který sahá na souřadnice:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logický posun, ten starý bug
  Writeln(V div 256);         // -3        zaokrouhlení k nule
  Writeln(FloorDiv(V, 256));  // -4        to, co T.88 myslí >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) vrátí také -4, ale její výlet přes Double ztrácí přesnost pro hodnoty Int64 nad 2⁵³, takže celočíselná geometrie by měla zůstat v celých číslech

Která volání PDFlibPas pustí halftone dekodér?

Halftone dekodér JBIG2 běží, když PDFlibPas renderuje stránku vestavěným rendererem, protože renderování potřebuje pixely. RenderPageToFile i RenderPageToStream se k němu dostanou přes JBIG2Decode obrazové streamy stránky, takže přerenderování halftone stránky je přímá cesta, jak potvrdit, že v3.539.38 mění váš výstup. Tentýž dekodér obsluhuje i ostatní typy JBIG2 regionů, pokryté v custom Huffman tabulkách JBIG2 v čistě Pascal dekodéru a dekódování random-access JBIG2 souborů v Delphi a vyrenderovaná bitmapa živí konverze jako renderování PDF stránek do 1bitové monochromie

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
      // Renderování dekóduje každý JBIG2 region, halftony nevyjímaje
      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.

Extrakce obrázků normálně jde jinou cestou. GetPageImageList vrací JBIG2 obrázky v nativní podobě a SaveImageListItemDataToFile nebo GetImageListItemDataToString vám podá samostatný JBIG2 soubor poskládaný z bajtů streamu: hlavičku souboru, data JBIG2Globals a end-of-file segment kolem dat stránky. Vlastnost 400 na GetImageListItemIntProperty hlásí u takové položky 6. Na téhle cestě se nic nedekóduje, takže extrahovaný .jb2, který vypadal v jiném prohlížeči správně, zatímco vyrenderovaná stránka ukazovala šum, byl typickým znakem těchto dvou halftone bugů:

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;

Když masky nebo konverze barev vynutí renderovanou zálohu, vrátí se položka jako dekódovaná bitmapa a halftone dekodér skutečně běží. Více o image seznamech v extrakci textu, obrázků a písem z PDF v Delphi

Rychlá reference: pravidla halftone mřížky JBIG2

• Indexujte masku skip jako HSKIP[ng, mg], sloupec mřížky první, a čtěte ji zpátky ve stejném pořadí všude, kde se umisťují buňky (T.88 §6.6.5.1, opraveno v PDFlibPas v3.539.37)
• Testujte jakýkoli halftone nebo mřížkový kód s nečtvercovou mřížkou a asymetrickou sadou buněk mimo region, protože čtvercová mřížka dokáže přehozený index skrýt úplně
• Čtěte HGX a HGY jako znaménkové 32bitové hodnoty (T.88 §7.4.5.1.2), nikdy přes bezznaménkového pomocníka, který záporné seřezává
• Překládejte >> 8 ze standardu jako dělení floor 256, ne jako shr 8 a ne jako div 256
• Pouštějte test skip na posunutých pixelových pozicích; forma v pevné řádové čárce se liší, kdykoli je zlomek nenulový, jak ukazuje HGX = -900 s 4pixelovým patternem
• Akumulujte souřadnice mřížky v Int64 a seřezávejte je, než je předáte bitmapovému kódu, takže poškozená mřížka nemůže přetéct
• Přejděte na v3.539.38 a novější, pokud vaše dokumenty obsahují halftone regiony s HENABLESKIP, zápornými počátky mřížky nebo otočenými mřížkami

PDFlibPas renderuje, extrahuje a upravuje PDF dokumenty z Delphi a C++Builderu s nativním Pascal JBIG2 dekodérem, který teď zvládá masky skip halftonu, záporné počátky mřížky a otočené mřížky tak, jak specifikuje T.88. Funkce, edice a trial ke stažení na PDFlibPas Delphi PDF library