PDFlibPas JBIG2 halftone-grids: HSKIP og negative offsetter

PDFlibPas fikset to uavhengige feil i sin native JBIG2 halftone-region-dekoder: i v3.539.37 indekseres HSKIP-skip-masken som HSKIP[ng, mg], slik ITU-T T.88 §6.6.5.1 definerer den, og i v3.539.38 plasseres grids som når negative koordinater, gjennom en negativ HGX eller HGY eller gjennom rotasjon, med et ekte floor-skift. Før de utgivelsene kom berørte halftone-regioner ut garvet eller forskjøvet, uten noen feilmelding. Begge bugene gjemte seg bak testdata som tilfeldigvis var symmetriske eller ikke-negative, og den andre vender på en egenskap ved Delphi og Free Pascal som biter langt utenfor JBIG2: shr på en signed integer er et logisk skift, ikke det aritmetiske >> standarden antar

Halftone-regioner er den mest uvanlige JBIG2-regiontypen, så en dekoder kan prosessere tusenvis av skannede dokumenter før den treffer et rasterisert fotografi kodet som én. Når det skjer, er feilen ubehagelig: filen parser, segmentlengdene går opp, siden har riktig størrelse, og regionen er søppel

Hva dekoder en JBIG2 halftone-region egentlig?

En JBIG2 halftone-region er et grid av små bitmapser plukket fra en pattern dictionary, og dekoderens egentlige jobb er å beregne en indeks for hver grid-celle og pikselposisjonen der cellen lander. Pattern dictionary-en holder HNUMPATS mønstre på HPW × HPH piksler. Halftone-region-segmentet beskriver så et grid på HGW kolonner ganger HGH rader og et gråtonebilde av samme størrelse, kodet som Gray-kodete bitplan. Hvert bitplan dekodes med generic region-prosedyren over en HGW × HGH-bitmap, mest signifikante plan først, og planene gir til sammen hver celle sitt mønsterindeks

Celleplassering bruker fixed-point-aritmetikk med en 8-bits brøkdel. Grid-origo HGX, HGY er et par 32-bits verdier, og grid-vektoren HRX, HRY beskriver steget mellom naboceller, noe som tillater et rotert grid. For grid-rad mg og grid-kolonne ng beregner T.88 §6.6.5 pikselposisjonen som:

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

Skip-masken kommer inn gjennom det valgfrie HENABLESKIP-flagget. Når flagget er satt, bygger §6.6.5.1 en HGW × HGH-bitmap HSKIP og setter HSKIP[ng, mg] til 1 for hver celle hvis mønster ligger helt utenfor regionen: x + HPW <= 0, x >= HBW, y + HPH <= 0 eller y >= HBH. Gråtone-bitplanene dekodes så med den masken som generic region skip-bitmap, så den aritmetiske dekoderen verken leser eller oppdaterer kontekst for en hoppet-over-celle. Dekoder og enkoder må være enige om hver eneste bit i HSKIP, ellers går de to aritmetiske koderne ut av takt

Hvorfor ødela en transponert HSKIP-maske bare ikke-kvadratiske grids?

Skip-masken ble skrevet med koordinatene byttet, og bare et ikke-kvadratisk grid avdekket det, for et kvadratisk grid holder hver byttet koordinat inne i masken. PDFlibPas lagrer bitmapser med en (column, row)-pikselaksessor, og koden som bygde masken, sendte (mg, ng), rad først. Gråtone-bitplan-dekoderen leser masken korrekt som (ng, mg). Mønsterplasserings-løkken leste den tilbake i byggerens byttede rekkefølge, så de to var enige, og en gjennomgang av bare plasseringslogikken ville godkjent den. En navnefelle gjorde det verre: i plasseringsløkken itererer variabelen kalt col over grid-rader og Row over grid-kolonner

Ta 5 × 3-gridet av 4 × 4-mønstre på en 16 × 8-region som v3.539.37 bruker som regresjonstilfelle. Med HRX = 1024 og HRY = 0 lander grid-kolonne 4 ved x = 16 og grid-rad 2 ved y = 8, begge utenfor regionen. Den korrekte masken markerer syv celler: hele kolonne 4 og hele rad 2. De byttede skrivene forsøkte å sette piksler ved radindeksene 3 og 4 i en maske bare tre rader høy, og bitmap-setteren ignorerte i stillhet de utenfor-rekkevidde-skrivene. Det som overlevde, var kolonne 2, radene 0 til 2. Dekoderen hoppet dermed over to celler enkoderen hadde kodet, og dekodet seks celler enkoderen hadde hoppet over

Den aritmetiske dekoderen feiler ikke når det skjer. Den dekoder ekstra piksler ut av biter som tilhører senere celler, kontekstene leser feil naboer, og hvert mønsterindeks etter den første uenigheten er støy, og det er derfor symptomet var en garvet region i stedet for noen feilplasserte celler. På et kvadratisk grid er samme bug ofte usynlig: ingen byttet koordinat forlater masken, og når cellene utenfor regionen er symmetriske om diagonalen, et grid som henger over høyre og bunnkant med like mange celler for eksempel, er den transponerte masken bit for bit den korrekte. HENABLESKIP er også valgfri, må være 0 når gråtonebildet er MMR-kodet, og settes sjelden av enkodere, så bugen hadde svært få måter å komme til syne på. Siden v3.539.37 skriver byggeren HSKIP[ng, mg] og plasseringsløkken leser samme rekkefølge

Hvorfor feiler negative halftone grid-offsets i tre lag?

Et halftone-grid som starter til venstre for eller over regionen sin, knuste PDFlibPas på tre separate steder, og hver feil skjulte den neste. T.88 tillater denne geometrien med vilje. En enkoder som justerer rasteret sitt mot siden i stedet for mot regionen, eller bruker et rotert grid, produserer naturlig negative cellehjørner som regionen beskjærer. v3.539.38 fikset alle tre lagene sammen, for å fikse én alene endret bare symptomet

Lag 1: et signed felt lest som unsigned

T.88 §7.4.5.1.2 definerer HGX og HGY som signed 32-bits verdier, men dekoderen leste dem med samme 32-bits hjelper den brukte til unsigned felt, og den hjelperen klemte hvert negativt resultat til 0. Et grid ment å starte ved HGX = -900 ble i stillhet flyttet til region-origo. I v3.539.38-regresjonstilfellet kom hele bildet ut to rader for lavt. Klemmen forklarer også hvorfor de to andre feilene overlevde så lenge: med origo tvunget til ikke-negativ kunne et negativt koordinat bare dukke opp gjennom et rotert grid med HRY > 0, der y = HGY + mg × HRX − ng × HRY faller under null for senere grid-kolonner

Lag 2: shr er ikke >> 8

T.88 skriver >> 8 og mener et aritmetisk skift, som runder mot minus uendelig. Dekoderen oversatte det som shr 8. I Delphi og Free Pascal er shr på en signed integer et logisk skift: fortegnsbiten skiftes inn som en null. For en Integer som holder -512 gir shr 8 16777214 i stedet for -2. Et mønster som skulle vært tegnet ved y = -2 og beskåret til sin nedre halvdel, ble sendt 16 millioner rader ned og droppet som utenfor regionen. Ingenting krasjet; øverste rad i halftonen forsvant bare

Lag 3: å sammenligne fixed point i stedet for piksler

Skip-testen sammenlignet fixed-point-verdier, ikke pikselposisjoner, og de to er ikke ekvivalente når brøkdelen er ulik null. Den opprinnelige koden unnvekk det logiske skiftet ved å teste xx + HPW × 256 <= 0 på den uskiftede verdien, en angivelig ekvivalent av T.88-testen. Med HGX = -900 og et 4-pikslers mønster gir det -900 + 1024 = 124, som er positivt, så cellen hoppes ikke over. Standarden skifter først: floor(-900 / 256) = -4, og -4 + 4 = 0 oppfyller x + HPW <= 0, så cellen ligger helt utenfor og må hoppes over. Enkoderen hoppet over den, dekoderen dekodet den, og gråtonebildet drev nøyaktig som i tilfellet med transponert maske

Regresjonstilfellet fra v3.539.38 bruker et 4 × 3-grid av 4 × 4-mønstre ved HGX = -900, HGY = -512, HRX = 1024 på en 12 × 10-region. Grid-kolonner lander ved x = -4, 0, 4 og 8, så kolonne 0 er helt utenfor og hører hjemme i HSKIP; grid-rader lander ved y = -2, 2 og 6, så rad 0 må beskjæres til sine to nederste pikselrader i stedet for å droppes. Å fikse lagene én om gangen reproduserer stakken:

Feil fikset	Dekodet region
Ingen (før v3.539.38)	Grid dratt til origo, hele bildet to rader for lavt
Bare signed lesing av HGX / HGY	Første grid-rad mangler, resten garvet av skip-test-driften
Signed lesing, floor-skift og skip-test i pikselrom	Identisk, piksel for piksel, med siden beregnet fra T.88 §6.6.5 og med to uavhengige referansedekodere

Fiksen er én hjelper, HalftoneGridPixel, delt av skip-maske-byggeren og plasseringsløkken. Den akkumulerer koordinaten i Int64 slik at et stort mg × HRX-produkt ikke kan wrappe, deler på 256 med avrunding mot minus uendelig, og klemmer til ±MaxInt div 2 slik at et korrupt grid ikke kan overflyte senere bitmap-aritmetikk. Skip-testen sammenligner nå de pikselverdiene mot HPW, HPH, HBW og HBH, nøyaktig slik §6.6.5.1 sier det

Hvordan skriver du et aritmetisk høyreskift i Delphi?

Delphi har ingen aritmetisk skiftoperator, så et korrekt signed høyreskift må skrives som en floor-divisjon, og vanlig div er ikke den divisjonen. div kutter mot null. For ikke-negative verdier er avkutting og floor enige, og de er også enige for negative verdier som er eksakte multipler av divisoren, og det er derfor -512 div 256 = -2 ser fint ut i en rask test. De er uenige ellers: -900 div 256 er -3, mens floor er -4, og -1 div 256 er 0, mens floor er -1. En JBIG2-koordinat med en ulik-null-brøkdel er nøyaktig tilfellet der div gir feil piksel

På Delphi Win32- og Win64-kompilatorene gir en Integer-variabel som holder -512, skiftet høyre med 8, 16777214, og en Int64 som holder -512, gir 72057594037927934. Free Pascal definerer også shr som et logisk skift og følger med SarLongint og SarInt64 i System-uniten for den aritmetiske versjonen, men de funksjonene finnes ikke i Delphi, så kode delt mellom de to kompilatorene trenger sin egen hjelper:

// Floor-divisjon: runder mot minus uendelig for ethvert fortegn på A og B.
// B må ikke være 0, og FloorDiv(Low(Integer), -1) overflyter akkurat 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 høyreskift (C- og T.88 «>>» på signed verdier).
// For negativ Value er not Value = -Value - 1 ikke-negativ, så det
// logiske shr er trygt der, og den ytre not mapper resultatet tilbake
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-trikset skifter aldri et negativt tall, så det er ikke avhengig av hvordan en kompilator behandler fortegnsbiten, og det overflyter aldri, inkludert for Low(Integer). Begge hjelperne matchet en Int64-floor-referanse over flere millioner verdier, hvert skift fra 0 til 31 og Low(Integer)- og High(Integer)-kantene på Delphi Win32, Delphi Win64 og Free Pascal x86_64. En fornuftssjekk verdt å beholde i enhver unit-test som rører koordinater:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logisk skift, den gamle bugen
  Writeln(V div 256);         // -3        avkutting mot null
  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 omveien gjennom Double mister presisjon for Int64-verdier over 2⁵³, så heltallsgeometri bør holde seg i heltall

Hvilke PDFlibPas-kall kjører halftone-dekoderen?

JBIG2 halftone-dekoderen kjører når PDFlibPas rendrer en side med den innebygde rendereren, for rendering trenger piksler. RenderPageToFile og RenderPageToStream når den begge gjennom sidens JBIG2Decode-bildestrømmer, så å rendere en halftone-side på nytt er den direkte måten å bekrefte at v3.539.38 endrer output-en din på. Samme dekoder håndterer de andre JBIG2-regiontypene, dekket i JBIG2 custom Huffman-tabeller i den rene Pascal-dekoderen og dekoding av random-access JBIG2-filer i Delphi, og den renderte bitmapen mater konverteringer som å rendere 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 inkludert
      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.

Bildeekstraksjon tar normalt en annen sti. GetPageImageList returnerer JBIG2-bilder i native form, og SaveImageListItemDataToFile eller GetImageListItemDataToString gir deg en frittstående JBIG2-fil bygget fra strømbytene: filheaderen, JBIG2Globals-dataene og et end-of-file-segment rundt sidedataene. Egenskap 400 hos GetImageListItemIntProperty rapporterer 6 for en slik post. Ingenting dekodes på den stien, så en ekstrahert .jb2 som ser korrekt ut i en annen viewer mens den renderte siden viser støy, var et typisk tegn på disse to halftone-bugene:

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 fargekonvertering tvinger frem en rendret fallback, kommer posten tilbake som en dekodet bitmap, og halftone-dekoderen kjører faktisk. Mer om bildelister i Delphi PDF tekst-, bilde- og font-ekstraksjon

Hurtigreferanse: JBIG2 halftone grid-regler

• Indekser skip-masken som HSKIP[ng, mg], grid-kolonne først, og les den tilbake i samme rekkefølge uansett hvor celler plasseres (T.88 §6.6.5.1, fikset i PDFlibPas v3.539.37)
• Test all halftone- eller grid-kode med et ikke-kvadratisk grid og et asymmetrisk sett med celler utenfor regionen, for et kvadratisk grid kan skjule en transponert indeks fullstendig
• Les HGX og HGY som signed 32-bits verdier (T.88 §7.4.5.1.2), aldri gjennom en unsigned-hjelper som klemmer negativer
• Oversett standardens >> 8 som en floor-divisjon på 256, ikke som shr 8 og ikke som div 256
• Kjør skip-testen på skiftede pikselposisjoner; fixed-point-formen avviker når som helst brøkdelen er ulik null, som HGX = -900 med et 4-pikslers mønster viser
• Akkumuler grid-koordinater i Int64 og klem før du gir dem til bitmap-kode, slik at et korrupt grid ikke kan overflyte
• Oppgrader til v3.539.38 eller senere hvis dokumentene dine inneholder halftone-regioner med HENABLESKIP, negative grid-origoer eller roterte grids

PDFlibPas rendrer, ekstraherer og redigerer PDF-dokumenter fra Delphi og C++Builder med en native Pascal JBIG2-dekoder som nå håndterer halftone-skip-masker, negative grid-origoer og roterte grids slik T.88 spesifiserer. Se PDFlibPas Delphi PDF library for funksjoner, utgaver og en prøvenedlasting