PDFlibPas JBIG2-halftone-gitter: HSKIP og negative offsets

PDFlibPas rettede to uafhængige fejl i sin native JBIG2-halftone-region-dekoder: i v3.539.37 indekseres HSKIP-skip-masken som HSKIP[ng, mg], som ITU-T T.88 §6.6.5.1 definerer den, og i v3.539.38 placeres gittere, der når negative koordinater — gennem en negativ HGX eller HGY eller gennem rotation — med en ægte floor-shift. Før de releases kom berørte halftone-regioner ud garblerede eller forskudte, uden nogen fejl rejst. Begge bugs gemte sig bag testdata, der tilfældigvis var symmetriske eller ikke-negative, og den anden bunder i en egenskab ved Delphi og Free Pascal, der bider langt uden for JBIG2: shr på et signeret integer er en logisk shift, ikke den aritmetiske >>, standarden antager

Halftone-regioner er den sjældneste JBIG2-regiontype, så en dekoder kan behandle tusinder af scannede dokumenter, før den møder et rastergengivet fotografi kodet som én. Når det sker, er fejlen ubehagelig: filen parser fint, segmentlængderne lægger op, siden har den rigtige størrelse, og regionen er skrald

Hvad dekoder en JBIG2-halftone-region egentlig?

En JBIG2-halftone-region er et gitter af små bitmaps, valgt fra et pattern dictionary, og dekoderens egentlige arbejde er at beregne et indeks for hver gittercelle og den pixelposition, cellen lander på. Pattern dictionary holder HNUMPATS mønstre på HPW × HPH pixels. Halftone-region-segmentet beskriver derefter et gitter på HGW kolonner gange HGH rækker og et gråtonebillede af samme størrelse, kodet som Gray-kodede bitplaner. Hvert bitplan dekodes med generic region-proceduren over en HGW × HGH-bitmap, mest betydende plan først, og planerne giver tilsammen hver celle sit mønsterindeks

Celleplacering bruger fixed-point-aritmetik med en 8-bit brøkdel. Gitterorigo HGX, HGY er et par af 32-bit værdier, og gittervektoren HRX, HRY beskriver trinnet mellem naboceller, hvilket tillader et roteret gitter. For gitterrække mg og gitterkolonne ng beregner T.88 §6.6.5 pixelpositionen som:

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

Skip-masken kommer ind gennem det valgfrie HENABLESKIP-flag. Er flaget sat, bygger §6.6.5.1 en HGW × HGH-bitmap HSKIP og sætter HSKIP[ng, mg] til 1 for hver celle, hvis mønster ligger helt uden for regionen: x + HPW <= 0, x >= HBW, y + HPH <= 0 eller y >= HBH. Gråtone-bitplanerne dekodes derefter med den maske som generic region skip-bitmap, så den aritmetiske dekoder hverken læser eller opdaterer kontekst for en skipped celle. Dekoder og enkoder skal være enige om hver eneste bit i HSKIP, ellers falder de to aritmetiske kodere ud af trit

Hvorfor brød en transponeret HSKIP-maske kun ikke-kvadratiske gittere?

Skip-masken blev skrevet med sine koordinater byttet om, og kun et ikke-kvadratisk gitter afslørede det, for et kvadratisk gitter holder hver byttet koordinat inde i masken. PDFlibPas gemmer bitmaps med en (column, row)-pixelaccessor, og koden, der byggede masken, gav (mg, ng) videre, række først. Gråtone-bitplan-dekoderen læser masken korrekt som (ng, mg). Mønsterplaceringsløkken læste den tilbage i byggerens byttede rækkefølge, så de to var enige, og en gennemgang af placeringslogikken alene ville godkende den. En navnefælde gjorde det værre: i placeringsløkken itererer variablen kaldet col over gitterrækker, og Row itererer over gitterkolonner

Tag gitteret på 5 × 3 med 4 × 4-mønstre på en 16 × 8-region, som v3.539.37 bruger som regressionstilfælde. Med HRX = 1024 og HRY = 0 lander gitterkolonne 4 på x = 16 og gitterrække 2 på y = 8, begge uden for regionen. Den korrekte maske markerer syv celler: hele kolonne 4 og hele række 2. De byttede skrivninger forsøgte at sætte pixels på rækkeindeks 3 og 4 i en maske kun tre rækker høj, og bitmap-sætteren ignorerede stille de uden for interval- skrivninger. Det, der overlevede, var kolonne 2, rækker 0 til 2. Dekoderen skippede derfor to celler, enkoderen havde kodet, og dekodede seks celler, enkoderen havde skippet

Den aritmetiske dekoder fejler ikke, når det sker. Den dekoder ekstra pixels ud af bits, der tilhører senere celler, dens kontekster læser forkerte naboer, og hvert mønsterindeks efter den første uenighed er støj, hvilket er hvorfor symptomet var en garbled region i stedet for et par forskudte celler. På et kvadratisk gitter er samme bug ofte usynlig: ingen byttet koordinat forlader masken, og når cellerne uden for regionen er symmetriske om diagonalen — et gitter, der rager ud over højre og nederste kant med samme antal celler, for eksempel — er den transponerede maske bit for bit den korrekte. HENABLESKIP er desuden valgfri, skal være 0, når gråtonebilledet er MMR-kodet, og sættes sjældent af enkodere, så buggen havde meget få måder at vise sig på. Siden v3.539.37 skriver byggeren HSKIP[ng, mg], og placeringsløkken læser samme rækkefølge

Hvorfor fejler negative halftone-gitter-offsets i tre lag?

Et halftone-gitter, der starter venstre for eller over sin region, brød PDFlibPas tre separate steder, og hver fejl skjulte den næste. T.88 tillader denne geometri bevidst. En enkoder, der justerer sit raster efter siden frem for regionen, eller bruger et roteret gitter, producerer naturligt negative cellesider, som regionen beskærer. v3.539.38 rettede alle tre lag sammen, for at rette ét alene kun ændrede symptomet

Lag 1: et signeret felt læst som unsigned

T.88 §7.4.5.1.2 definerer HGX og HGY som signerede 32-bit værdier, men dekoderen læste dem med samme 32-bit-hjælper, den brugte til unsigned-felter, og den hjælper klemte ethvert negativt resultat til 0. Et gitter, der skulle starte ved HGX = -900, blev stille flyttet hen på regionorigo. I v3.539.38's regressionstilfælde kom hele billedet ud to rækker for lavt. Klemmen forklarer også, hvorfor de to andre fejl overlevede så længe: med origo tvunget til at være ikke-negativ kunne en negativ koordinat kun optræde gennem et roteret gitter med HRY > 0, hvor y = HGY + mg × HRX − ng × HRY falder under nul for senere gitterkolonner

Lag 2: shr er ikke >> 8

T.88 skriver >> 8 og mener en aritmetisk shift, som runder mod minus uendelig. Dekoderen oversatte det til shr 8. I Delphi og Free Pascal er shr på et signeret integer en logisk shift: fortegnsbiten skiftes ind som en nul. For en Integer med -512 giver shr 8 16777214 i stedet for -2. Et mønster, der skulle være tegnet ved y = -2 og beskåret til sin nedre halvdel, blev sendt 16 millioner rækker ned og droppet som uden for regionen. Intet crashede; halftonens øverste række forsvandt bare

Lag 3: sammenligning af fixed point i stedet for pixels

Skip-testen sammenlignede fixed-point-værdier, ikke pixelpositioner, og de to er ikke ækvivalente, så snart brøkdelen er forskellig fra nul. Den oprindelige kode undve den logiske shift ved at teste xx + HPW × 256 <= 0 på den ushiftede værdi, en formodet ækvivalent til T.88-testen. Med HGX = -900 og et 4-pixel-mønster giver det -900 + 1024 = 124, hvilket er positivt, så cellen skippes ikke. Standarden shifter først: floor(-900 / 256) = -4, og -4 + 4 = 0 opfylder x + HPW <= 0, så cellen ligger helt uden for og skal skippes. Enkoderen skippede den, dekoderen dekodede den, og gråtonebilledet drev præcis som i tilfældet med den transponerede maske

Regressionstilfældet fra v3.539.38 bruger et gitter på 4 × 3 med 4 × 4-mønstre ved HGX = -900, HGY = -512, HRX = 1024 på en 12 × 10-region. Gitterkolonner lander ved x = -4, 0, 4 og 8, så kolonne 0 ligger helt uden for og hører hjemme i HSKIP; gitterrækker lander ved y = -2, 2 og 6, så række 0 skal beskæres til sine to nederste pixelrækker frem for at blive droppet. At rette lagene ét ad gangen reproducerer stakken:

Fejl rettet	Dekoderet region
Ingen (før v3.539.38)	Gitter trukket hen til origo, hele billedet to rækker for lavt
Kun signeret HGX / HGY-læsning	Første gitterrække mangler, resten garbleret af skip-test-driften
Signeret læsning, floor-shift og skip-test i pixelrum	Identisk, pixel for pixel, med siden beregnet ud fra T.88 §6.6.5 og med to uafhængige reference-dekodere

Fixet er én hjælper, HalftoneGridPixel, delt af skip-maske-byggeren og placeringsløkken. Den akkumulerer koordinaten i Int64, så et stort mg × HRX-produkt ikke kan rende rundt, dividerer med 256 med afrunding mod minus uendelig og klemmer til ±MaxInt div 2, så et korrupt gitter ikke kan få senere bitmap-aritmetik til at løbe over. Skip-testen sammenligner nu de pixelværdier med HPW, HPH, HBW og HBH, præcis som §6.6.5.1 angiver det

Hvordan skriver man en aritmetisk right shift i Delphi?

Delphi har ingen aritmetisk shift-operator, så en korrekt signeret right shift må skrives som en floor-division, og almindelig div er ikke dén division. div trunkerer mod nul. For ikke-negative værdier er trunkering og floor enige, og de er også enige for negative værdier, der er præcise multipla af divisoren, hvilket er hvorfor -512 div 256 = -2 ser fin ud i en hurtig test. De er uenige alle andre steder: -900 div 256 er -3, mens floor er -4, og -1 div 256 er 0, mens floor er -1. En JBIG2-koordinat med en brøkdel forskellig fra nul er præcis det tilfælde, hvor div giver den forkerte pixel

På Delphi Win32- og Win64-kompilerne giver en Integer-variabel med -512 shifted right med 8 resultatet 16777214, og en Int64 med -512 giver 72057594037927934. Free Pascal definerer også shr som en logisk shift og leverer SarLongint og SarInt64 i sin System-unit til den aritmetiske version, men de funktioner findes ikke i Delphi, så kode delt mellem de to kompilere behøver sin egen hjælper:

// Floor-division: runder mod minus uendelig for ethvert fortegn af A og B.
// B må ikke være 0, og FloorDiv(Low(Integer), -1) overløber præcis som 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;

// Aritmetisk right shift (C's og T.88's ">>" på signerede værdier).
// For negativ Value er not Value = -Value - 1 ikke-negativ, så der
// er logisk shr sikkert, og det ydre not kortlægger resultatet tilbage
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;

not-tricket shifter aldrig et negativt tal, så det afhænger ikke af, hvordan en kompiler behandler fortegnsbiten, og det løber aldrig over, også for Low(Integer). Begge hjælpere matchede en Int64-floor-reference over flere millioner værdier, hver shift fra 0 til 31 og Low(Integer)- og High(Integer)-kanterne på Delphi Win32, Delphi Win64 og Free Pascal x86_64. En sanity check, der er værd at beholde i enhver unit test, der rører koordinater:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logisk shift, den gamle bug
  Writeln(V div 256);         // -3        trunkering mod nul
  Writeln(FloorDiv(V, 256));  // -4        det, T.88 mener med >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) returnerer også -4, men dens omvej gennem Double mister præcision for Int64-værdier over 2⁵³, så integer-geometri bør blive i integers

Hvilke PDFlibPas-kald kører halftone-dekoderen?

JBIG2-halftone-dekoderen kører, når PDFlibPas renderer en side med den indbyggede renderer, for rendering behøver pixels. RenderPageToFile og RenderPageToStream når begge frem til den gennem sidens JBIG2Decode-imagestreams, så at re-renderere en halftone-side er den direkte måde at bekræfte, at v3.539.38 ændrer dit output. Samme dekoder håndterer de andre JBIG2-regiontyper, dækket i JBIG2 custom Huffman-tabeller i den rene Pascal-dekoder og dekodning af random-access JBIG2-filer i Delphi, og den renderede bitmap fodrer konverteringer som rendering af PDF-sider til 1-bit monokrom

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
      // Rendering dekoder hver JBIG2-region, halftones inkluderet
      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.

Billed-ekstraktion tager normalt en anden vej. GetPageImageList returnerer JBIG2-billeder i native form, og SaveImageListItemDataToFile eller GetImageListItemDataToString giver dig en selvstændig JBIG2-fil bygget ud fra stream-bytes: filheaderen, JBIG2Globals-dataene og et end-of-file-segment omkring sidedataene. Egenskab 400 hos GetImageListItemIntProperty rapporterer 6 for sådan et item. Intet dekodes på den vej, så en ekstraheret .jb2, der ser korrekt ud i en anden viewer, mens den renderede side viser støj, var et typisk tegn på disse to halftone-bugs:

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;

Når masker eller farvekonvertering tvinger en renderet fallback frem, kommer itemet tilbage som en dekodet bitmap, og halftone-dekoderen kører da. Mere om image lists i Delphi PDF-tekst-, billed- og font-ekstraktion

Hurtig reference: JBIG2-halftone-gitter-regler

• Indeksér skip-masken som HSKIP[ng, mg], gitterkolonne først, og læs den tilbage i samme rækkefølge, hvor som helst celler placeres (T.88 §6.6.5.1, rettet i PDFlibPas v3.539.37)
• Test enhver halftone- eller gitterkode med et ikke-kvadratisk gitter og et asymmetrisk sæt celler uden for regionen, for et kvadratisk gitter kan skjule et transponeret indeks fuldstændigt
• Læs HGX og HGY som signerede 32-bit værdier (T.88 §7.4.5.1.2), aldrig gennem en unsigned-hjælper, der klemmer negative
• Oversæt standardens >> 8 som en floor-division med 256, ikke som shr 8 og ikke som div 256
• Kør skip-testen på shiftede pixelpositioner; fixed-point-formen afviger, når brøkdelen er forskellig fra nul, som HGX = -900 med et 4-pixel-mønster viser
• Akkumulér gitterkoordinater i Int64 og klem, inden de gives videre til bitmap-kode, så et korrupt gitter ikke kan få noget til at løbe over
• Opgradér til v3.539.38 eller senere, hvis dine dokumenter indeholder halftone-regioner med HENABLESKIP, negative gitterorigoer eller roterede gittere

PDFlibPas renderer, ekstraherer og redigerer PDF-dokumenter fra Delphi og C++Builder med en native Pascal-JBIG2-dekoder, der nu håndterer halftone-skip-masker, negative gitterorigoer og roterede gittere, som T.88 specificerer. Se PDFlibPas Delphi PDF library for features, udgaver og en trial-download