PDFlibPas: halftone mriežky JBIG2, HSKIP a záporné offsety

PDFlibPas opravil dve nezávislé chyby vo svojom natívnom JBIG2 halftone dekodéri regiónov: vo v3.539.37 sa skip maska HSKIP indexuje ako HSKIP[ng, mg], ako to definuje ITU-T T.88 §6.6.5.1, a vo v3.539.38 sa mriežky, ktoré siahajú do záporných súradníc, či už cez záporné HGX alebo HGY, alebo cez rotáciu, umiestňujú skutočným floor posunom. Pred tými verziami vychádzali postihnuté halftone regióny pomiatané alebo posunuté, bez vyhodenia chyby. Obidve bugy sa schovali za testovacie dáta, ktoré boli náhodou symetrické alebo nezáporné, a ten druhý zapína vlastnosť Delphi a Free Pascal, ktorá hryzie ďaleko mimo JBIG2: shr nad znamienkovým celým číslom je logický posun, nie aritmetické >>, ktoré štandard predpokladá

Halftone regióny sú najmenej častý typ JBIG2 regiónu, takže dekodér môže spracovať tisíce naskenovaných dokumentov, kým sa stretne s rastrizovanou fotografiou kódovanou ako jeden. Keď sa to stane, zlyhanie je nepríjemné: súbor sa parsnie, dĺžky segmentov sčítajú, strana má správnu veľkosť a región je smetie

Čo vlastne dekóduje halftone región JBIG2?

Halftone región JBIG2 je mriežka malých bitmap vybratých z pattern dictionary a skutočná práca dekodéra je počítať index pre každú bunku mriežky a pixelovú pozíciu, kam tá bunka pristane. Pattern dictionary drží HNUMPATS patternov HPW × HPH pixelov. Segment halftone regiónu potom popisuje mriežku HGW stĺpcov krát HGH riadkov a sivú škálu rovnakej veľkosti, kódovanú ako Gray-coded bitplaney. Každý bitplane sa dekóduje generic region procedúrou nad bitmapou HGW × HGH, najvýznamnejšia rovina prvá, a roviny spolu dajú každej bunke jej pattern index

Umiestňovanie buniek používa fixed-point aritmetiku s 8-bitovou zlomkovou časťou. Pôvod mriežky HGX, HGY je pár 32-bitových hodnôt a vektor mriežky HRX, HRY popisuje krok medzi susednými bunkami, čo umožňuje otočenú mriežku. Pre riadok mriežky mg a stĺpec ng počíta T.88 §6.6.5 pixelovú pozíciu ako:

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

Do hry vstupuje skip maska cez voliteľný príznak HENABLESKIP. Keď je príznak nastavený, §6.6.5.1 stavia bitmapu HGW × HGH HSKIP a nastaví HSKIP[ng, mg] na 1 pre každú bunku, ktorej pattern leží úplne mimo regiónu: x + HPW <= 0, x >= HBW, y + HPH <= 0 alebo y >= HBH. Sivá škála bitplanov sa potom dekóduje s touto maskou ako skip bitmapa generic regiónu, takže aritmetický dekodér ani nečíta, neaktualizuje kontext pre preskočenú bunku. Dekodér aj enkodér sa musia zhodnúť na každom bite HSKIP, inak sa obidva aritmetické kodéry rozbehnú z kroku

Prečo transponovaná maska HSKIP pokazila len neštvorcové mriežky?

Skip maska sa zapisovala s vymenenými súradnicami a odhalila ju len neštvorcová mriežka, lebo štvorcová mriežka drží každú vymenenú súradnicu vnútri masky. PDFlibPas ukladá bitmapy s pixelovým prístupom (column, row) a kód, ktorý stavbal masku, podával (mg, ng), riadok najprv. Dekodér sivých bitplanov číta masku korektne ako (ng, mg). Umiestňovacia slučka patternov ju čítala späť v vymenenom poradí stavbu, takže sa obaja zhodli a samostatná kontrola umiestňovacej logiky by prešla. Menová pasť to ešte prihustila: v umiestňovacej slučke premenná menovaná col iteruje riadky mriežky a Row iteruje stĺpce mriežky

Vezmime mriežku 5 × 3 patternov 4 × 4 na regióne 16 × 8, ktorú v3.539.37 používa ako regresný prípad. S HRX = 1024 a HRY = 0 pristáva stĺpec mriežky 4 na x = 16 a riadok mriežky 2 na y = 8, oboje mimo regiónu. Korektná maska označí sedem buniek: celý stĺpec 4 a celý riadok 2. Vymenené zápisy sa snažili nastaviť pixely v riadkoch 3 a 4 maske vysokej len tri riadky a bitmapový setter tie mimo-rozsahové zápisy potichu ignoroval. Čo prežilo, bol stĺpec 2, riadky 0 až 2. Dekodér preto preskočil dve bunky, ktoré enkodér zakódoval, a dekódoval šesť buniek, ktoré enkodér preskočil

Aritmetický dekodér pri tom nezlyhá. Dekóduje navyše pixely z bitov patriacich neskorším bunkám, jeho kontexty čítajú zlých susedov a každý pattern index po prvej neshode je šum, prečo príznakom bol pomiataný región namiesto niekoľkých posunutých buniek. Na štvorcovej mriežke je ten istý bug často neviditeľný: žiadna vymenená súradnica masku neopustí a keď sú mimo-regionové bunky symetrické podľa diagonály, napríklad mriežka presahujúca pravú aj spodnú hranu o rovnaký počet buniek, transponovaná maska je bit za bitom tou korektnou. HENABLESKIP je navyše voliteľný, pri MMR-kódovanom sivom obraze musí byť 0 a enkodéry ho nastavujú zriedka, takže bug mal veľmi málo ciest na povrch. Od v3.539.37 staviteľ masky zapisuje HSKIP[ng, mg] a umiestňovacia slučka číta to isté poradie

Prečo zlyhajú záporné offsety halftone mriežky v troch vrstvách?

Halftone mriežka, ktorá štartuje vľavo od alebo nad svojím regiónom, rozbila PDFlibPas na troch oddelených miestach a každá chyba schovala ďalšiu. T.88 dovoľuje túto geometriu zámerne. Enkodér, ktorý zarovnáva svoj raster na stranu namiesto na región, alebo používa otočenú mriežku, prirodzene vyrobí záporné rohy buniek, ktoré región oreže. v3.539.38 opravil všetky tri vrstvy naraz, lebo oprava ktorejkoľvek samej by zmenila len príznak

Vrstva 1: znamienkové pole čítané ako bez-znamienkové

T.88 §7.4.5.1.2 definuje HGX a HGY ako znamienkové 32-bitové hodnoty, ale dekodér ich čítal tým istým 32-bitovým pomocníkom, ktorého používal pre bez-znamienkové polia, a ten pomocník zastrapal každý záporný výsledok na 0. Mriežka mieniaca štartovať na HGX = -900 sa potichu presunula na pôvod regiónu. V regresnom prípade v3.539.38 vyšiel celý obrázok dva riadky príliš nízko. Zástrapa tiež vysvetľuje, prečo ostatné dve chyby prežili tak dlho: s pôvodom násilne nezáporným mohla záporná súradnica vzniknúť len cez otočenú mriežku s HRY > 0, kde y = HGY + mg × HRX − ng × HRY klesá pod nulu pre neskoršie stĺpce mriežky

Vrstva 2: shr nie je >> 8

T.88 píše >> 8 a myslí tým aritmetický posun, ktorý zaokrúhľuje k mínus nekonečnu. Dekodér to preložil ako shr 8. V Delphi a Free Pascal je shr nad znamienkovým celým číslom logický posun: znamienkový bit sa posúva ako nula. Pre Integer držiaci -512 dá shr 8 16777214 namiesto -2. Pattern, ktorý sa mal nakresliť na y = -2 a orezať na spodnú polovicu, bol poslaný 16 miliónov riadkov nadol a zahodený ako mimo-regiónový. Nič nespadlo; horný riadok halftonu jednoducho zmizol

Vrstva 3: porovnávanie fixed-point namiesto pixelov

Skip test porovnával fixed-point hodnoty, nie pixelové pozície, a tie dve nie sú ekvivalentné, akonáhle zlomková časť nie je nulová. Pôvodný kód obišiel logický posun testovaním xx + HPW × 256 <= 0 na neposunutých hodnotách, údajný ekvivalent T.88 testu. S HGX = -900 a 4-pixelovým patternom to dáva -900 + 1024 = 124, čo je kladné, takže bunka sa nepreskočí. Štandard posúva najprv: floor(-900 / 256) = -4 a -4 + 4 = 0 splňuje x + HPW <= 0, takže bunka leží úplne vonku a musí sa preskočiť. Enkodér ju preskočil, dekodér ju dekódoval a sivý obraz sa potiahol presne ako v prípade transponovanej masky

Regresný prípad z v3.539.38 používa mriežku 4 × 3 patternov 4 × 4 na HGX = -900, HGY = -512, HRX = 1024 na regióne 12 × 10. Stĺpce mriežky pristávajú na x = -4, 0, 4 a 8, takže stĺpec 0 je úplne vonku a patrí do HSKIP; riadky mriežky pristávajú na y = -2, 2 a 6, takže riadok 0 sa musí orezať na spodné dva pixelové riadky namiesto zahodenia. Oprava vrstiev jedna po druhej reprodukuje túto kaskádu:

Opravené chyby	Dekódovaný región
Žiadna (pred v3.539.38)	Mriežka pritiahnutá k pôvodu, celý obrázok dva riadky príliš nízko
Iba čítanie znamienkového HGX / HGY	Prvý riadok mriežky chýba, zvyšok pomiataný driftom skip testu
Znamienkové čítanie, floor posun a skip test v pixelovom priestore	Identický, pixel za pixelom, s stranou počítanou z T.88 §6.6.5 a s dvomi nezávislými referenčnými dekodérmi

Opravou je jeden pomocník, HalftoneGridPixel, zdieľaný staviateľom skip masky aj umiestňovacou slučkou. Sčítava súradnicu v Int64, takže veľký súčin mg × HRX sa nemôže pretočiť, delí 256 s zaokrúhľovaním k mínus nekonečnu a zastrapáva na ±MaxInt div 2, aby pokazená mriežka nemohla neskôr spôsobiť pretečenie bitmapovej aritmetiky. Skip test teraz porovnáva tie pixelové hodnoty proti HPW, HPH, HBW a HBH, presne ako to uvádza §6.6.5.1

Ako sa v Delphi píše aritmetický posun doprava?

Delphi nemá aritmetický posunový operátor, takže korektný znamienkový posun doprava sa musí napísať ako floor delenie a obyčajné div nie je to delenie. div zaokrúhľuje smerom k nule. Pre nezáporné hodnoty sa zaokrúhľovanie smerom k nule a floor zhodujú a zhodujú sa aj pre záporné hodnoty, ktoré sú presnými násobkami deliteľa, prečo -512 div 256 = -2 vyzerá v rýchlom teste v poriadku. Inde sa rozchádzajú: -900 div 256 je -3, kým floor je -4, a -1 div 256 je 0, kým floor je -1. JBIG2 súradnica s nenulovou zlomkovou časťou je presne prípad, kde div dá nesprávny pixel

Na kompilátoroch Delphi Win32 a Win64 dá Integer premenná držiaca -512 posunutá doprava o 8 hodnotu 16777214 a Int64 držiaci -512 dáva 72057594037927934. Free Pascal tiež definuje shr ako logický posun a dodáva SarLongint a SarInt64 vo svojej jednotke System pre aritmetickú verziu, ale tie funkcie v Delphi neexistujú, takže kód zdieľaný medzi oboma kompilátormi potrebuje vlastného pomocníka:

// Floor delenie: zaokrúhľuje k mínus nekonečnu pre ľubovoľné znamienká A a B.
// B nesmie byť 0 a FloorDiv(Low(Integer), -1) pretečie rovnako ako 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 (C aj T.88 ">>" nad znamienkovými hodnotami).
// Pre záporné Value nie je Value = -Value - 1 nezáporné, takže tam je
// logický shr bezpečný a vonkajšie not vráti výsledok naspäť
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 neposúva záporné číslo, takže nezávisí od toho, ako kompilátor zaobchádza so znamienkovým bitom, a nikdy nepretečie, vrátane Low(Integer). Obidva pomocníky sa zhodli s Int64 floor referenciou na niekoľkých miliónoch hodnôt, každý posun od 0 do 31 a okraje Low(Integer) a High(Integer) na Delphi Win32, Delphi Win64 a Free Pascal x86_64. Sanity kontrola, ktorá stojí za udržanie v každom jednotkovom teste, ktorý sa dotýka súradníc:

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

Math.Floor(V / 256) tiež vráti -4, ale jeho oklika cez Double stráca presnosť pre Int64 hodnoty nad 2⁵³, takže celočíselná geometria má ostať v celých číslach

Ktoré volania PDFlibPas spúšťajú halftone dekodér?

Halftone dekodér JBIG2 beží, keď PDFlibPas renderuje stranu so vstavaným rendererom, lebo renderovanie potrebuje pixely. RenderPageToFile aj RenderPageToStream sa k nemu dostanú cez JBIG2Decode image streamy strany, takže opätovné vyrenderovanie halftone strany je priama cesta, ako potvrdiť, že v3.539.38 mení váš výstup. Ten istý dekodér obsluhuje aj ostatné typy JBIG2 regiónov, pokryté v vlastných Huffman tabuľkách JBIG2 v čistom Pascal dekodéri a dekódovaní random-access JBIG2 súborov v Delphi, a vyrenderovaná bitmapa kŕmi konverzie ako renderovanie PDF strán do 1-bitovej monochrómie

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
      // Renderovanie dekóduje každý JBIG2 región, halftony vrátane
      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.

Extrahovanie obrázkov bežne berie inú cestu. GetPageImageList vracia JBIG2 obrázky v natívnej podobe a SaveImageListItemDataToFile alebo GetImageListItemDataToString vám podá samostatný JBIG2 súbor postavený zo streamových bajtov: hlavička súboru, dáta JBIG2Globals a end-of-file segment okolo dát strany. Property 400 GetImageListItemIntProperty hlási 6 pre takúto položku. Nič sa na tej ceste nedeóduje, takže extrahovaný .jb2, ktorý vyzerá správne v inom prehliadači, kým vyrenderovaná strana ukazuje šum, bol typickým znakom týchto dvoch halftone bugov:

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;

Keď masky alebo farebná konverzia vynútia renderovanú zálohu, položka sa vráti ako dekódovaná bitmapa a halftone dekodér sa naozaj spustí. Viac o image listoch je v extrakcii textu, obrázkov a fontov PDF v Delphi

Rýchla referencia: pravidlá halftone mriežky JBIG2

• Indexujte skip masku ako HSKIP[ng, mg], stĺpec mriežky najprv, a čítajte ju v tom istom poradí všade, kde sa umiestňujú bunky (T.88 §6.6.5.1, opravené v PDFlibPas v3.539.37)
• Testujte každý halftone alebo grid kód s neštvorcovou mriežkou a asymetrickou sadou mimo-regionových buniek, lebo štvorcová mriežka dokáže transponovaný index úplne skryť
• Čítajte HGX a HGY ako znamienkové 32-bitové hodnoty (T.88 §7.4.5.1.2), nikdy cez bez-znamienkového pomocníka, ktorý zastrapáva záporné
• Prekladajte >> 8 štandardu ako floor delenie 256, nie ako shr 8 ani ako div 256
• Skip test púšťajte na posunutých pixelových pozíciách; fixed-point forma sa rozchádza vždy, keď zlomková časť nie je nulová, ako ukazuje HGX = -900 s 4-pixelovým patternom
• Sčítavajte grid súradnice v Int64 a zastrapajte ich skôr, než ich podáte bitmapovému kódu, aby pokazená mriežka nemohla spôsobiť pretečenie
• Upgradujte na v3.539.38 alebo novšiu, ak vaše dokumenty obsahujú halftone regióny s HENABLESKIP, zápornými pôvodmi mriežky alebo otočenými mriežkami

PDFlibPas renderuje, extrahuje a upravuje PDF dokumenty z Delphi a C++Builder s natívnym JBIG2 dekodérom v Pascali, ktorý teraz obsluhuje halftone skip masky, záporné pôvody mriežky aj otočené mriežky tak, ako ich určuje T.88. Pozrite PDFlibPas Delphi PDF library pre funkcie, edície a skúšobné stiahnutie