PDFlibPas JBIG2-halftoneraster: HSKIP och negativa offset

PDFlibPas fixade två oberoende fel i sin nativa JBIG2-halftone-regionavkodare: i v3.539.37 indexeras HSKIP-hoppmasken som HSKIP[ng, mg] som ITU-T T.88 §6.6.5.1 definierar den, och i v3.539.38 placeras raster som når negativa koordinater, via negativ HGX eller HGY eller via rotation, med ett genuint floor-skift. Före de releaserna kom drabbade halftone-regioner ut förstörda eller förskjutna, utan något fel. Båda buggarna gömde sig bakom testdata som råkade vara symmetrisk eller icke-negativ, och den andra vilar på en egenskap hos Delphi och Free Pascal som biter långt utanför JBIG2: shr på ett signerat heltal är ett logiskt skift, inte den aritmetiska >> standarden förutsätter

Halftone-regioner är den ovanligaste JBIG2-regiontypen, så en avkodare kan processa tusentals inskannade dokument innan den stöter på ett rasteriserat fotografi kodat som en. När det händer är felet otäckt: filen tolkas, segmentlängderna summerar, sidan har rätt storlek, och regionen är skräp

Vad avkodar en JBIG2-halftoneregion egentligen?

En JBIG2-halftoneregion är ett raster av små bitmappar plockade från en pattern dictionary, och avkodarens verkliga arbete är att beräkna ett index för varje rastercell och pixelpositionen där cellen landar. Pattern dictionary:n håller HNUMPATS mönster om HPW × HPH pixlar. Halftoneregionsegmentet beskriver sedan ett raster om HGW kolumner gånger HGH rader och en gråskalebild av samma storlek, kodad som Gray-kodade bitplan. Varje bitplan avkodas med den generiska regionproceduren över en HGW × HGH-bitmapp, mest signifikant plan först, och planen ger tillsammans varje cell dess mönsterindex

Cellplacering använder fixed-point-aritmetik med en 8-bitarsbråkdel. Rasterorigo HGX, HGY är ett par 32-bitarsvärden, och rastervektorn HRX, HRY beskriver steget mellan närliggande celler, vilket tillåter ett roterat raster. För rasterrad mg och rasterkolumn ng beräknar T.88 §6.6.5 pixelpositionen som:

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

Hoppmasken kommer in via den valfria HENABLESKIP-flaggan. Är flaggan satt bygger §6.6.5.1 en HGW × HGH-bitmapp HSKIP och sätter HSKIP[ng, mg] till 1 för varje cell vars mönster ligger helt utanför regionen: x + HPW <= 0, x >= HBW, y + HPH <= 0 eller y >= HBH. Gråskalebitplanen avkodas sedan med den masken som den generiska regionens skip-bitmapp, så den aritmetiska avkodaren varken läser eller uppdaterar kontext för en hoppad cell. Avkodare och kodare måste enas om varje bit i HSKIP, annars hamnar de två aritmetiska kodarna ur fas

Varför slog en transponerad HSKIP-mask bara sönder icke-kvadratiska raster?

Hoppmasken skrevs med sina koordinater ombytta, och bara ett icke-kvadratiskt raster avslöjade det, för ett kvadratiskt raster håller varje ombytt koordinat inne i masken. PDFlibPas lagrar bitmappar med en (column, row)-pixelaccessor, och koden som byggde masken skickade (mg, ng), rad först. Gråskalebitplansavkodaren läser masken korrekt som (ng, mg). Mönsterplaceringsloopen läste den tillbaka i byggarens ombytta ordning, så de två var överens, och en granskning av enbart placeringslogiken skulle godkänna den. En namnfälla gjorde det värre: i placeringsloopen itererar variabeln kallad col raster-rader och Row raster-kolumner

Ta rastret 5 × 3 av mönster 4 × 4 på en region 16 × 8 som v3.539.37 använder som sitt regressionsfall. Med HRX = 1024 och HRY = 0 landar rasterkolumn 4 på x = 16 och rasterrad 2 på y = 8, båda utanför regionen. Den korrekta masken markerar sju celler: hela kolumn 4 och hela rad 2. De ombytta skrivningarna försökte sätta pixlar på radindex 3 och 4 i en mask bara tre rader hög, och bitmappssettern ignorerade tyst de skrivningarna utanför räckhåll. Det som överlevde var kolumn 2, rader 0 till 2. Avkodaren hoppade därför över två celler kodaren kodat, och avkodade sex celler kodaren hoppat över

Den aritmetiska avkodaren misslyckas inte när det händer. Den avkodar extra pixlar ur bitar som tillhör senare celler, dess kontexter läser fel grannar, och varje mönsterindex efter den första oenigheten är brus, vilket är varför symtomet var en förstörd region i stället för några felplacerade celler. På ett kvadratiskt raster är samma bugg ofta osynlig: ingen ombytt koordinat lämnar masken, och när cellerna utanför regionen är symmetriska kring diagonalen, ett raster som skjuter ut över höger och undre kant med samma antal celler till exempel, är den transponerade masken bit för bit den korrekta. HENABLESKIP är dessutom valfri, måste vara 0 när gråskalebilden är MMR-kodad, och sätts sällan av kodare, så buggen hade mycket få sätt att visa sig. Sedan v3.539.37 skriver byggaren HSKIP[ng, mg] och placeringsloopen läser samma ordning

Varför faller negativa halftonerasteroffset ut i tre lager?

Ett halftoneraster som börjar vänster om eller ovanför sin region slogo sönder PDFlibPas på tre separata ställen, och varje fel dolde nästa. T.88 tillåter denna geometri med flit. En kodare som riktar in sitt raster mot sidan i stället för mot regionen, eller använder ett roterat raster, framställer naturligt negativa cellhörn som regionen beskär. v3.539.38 fixade alla tre lager tillsammans, för att fixa vilket ensamt bara ändrade symtomet

Lager 1: ett signerat fält läst som teckenlöst

T.88 §7.4.5.1.2 definierar HGX och HGY som signerade 32-bitarsvärden, men avkodaren läste dem med samma 32-bitars hjälpare den använde för teckenlösa fält, och den hjälparen klamrade varje negativt resultat till 0. Ett raster avsett att börja på HGX = -900 flyttades tyst på regionorigo. I v3.539.38:s regressionsfall kom hela bilden ut två rader för lågt. Klamringen förklarar också varför de andra två felen överlevde så länge: med origot tvingat icke-negativt kunde en negativ koordinat bara dyka upp via ett roterat raster med HRY > 0, där y = HGY + mg × HRX − ng × HRY sjunker under noll för senare rasterkolumner

Lager 2: shr är inte >> 8

T.88 skriver >> 8 och menar ett aritmetiskt skift, som avrundar mot minus oändlighet. Avkodaren översatte det som shr 8. I Delphi och Free Pascal är shr på ett signerat heltal ett logiskt skift: teckenbiten skiftas in som en nolla. För en Integer som håller -512 ger shr 8 16777214 i stället för -2. Ett mönster som skulle ha ritats på y = -2 och beskurits till sin undre halva skickades 16 miljoner rader ner och kastades som utanför regionen. Inget kraschade; halftonens översta rad försvann bara

Lager 3: att jämföra fixed point i stället för pixlar

Skip-testet jämförde fixed-point-värden, inte pixelpositioner, och de två är inte ekvivalenta när bråkdelen väl är skild från noll. Ursprungskoden kringgick det logiska skiftet genom att testa xx + HPW × 256 <= 0 på det oshiftade värdet, en förmodad ekvivalent till T.88-testet. Med HGX = -900 och ett 4-pixlars mönster ger det -900 + 1024 = 124, som är positivt, så cellen hoppas inte. Standarden skiftar först: floor(-900 / 256) = -4, och -4 + 4 = 0 uppfyller x + HPW <= 0, så cellen ligger helt utanför och måste hoppas. Kodaren hoppade den, avkodaren avkodade den, och gråskalebilden drev exakt som i fallet med den transponerade masken

Regressionsfallet från v3.539.38 använder ett raster 4 × 3 av mönster 4 × 4 vid HGX = -900, HGY = -512, HRX = 1024 på en region 12 × 10. Rasterkolumner landar på x = -4, 0, 4 och 8, så kolumn 0 är helt utanför och hör hemma i HSKIP; rasterrader landar på y = -2, 2 och 6, så rad 0 måste beskäras till sina undre två pixlarrader i stället för att kastas. Att fixa lagren en i taget återskapar stacken:

Fixade fel	Avkodad region
Inga (före v3.539.38)	Rastret draget till origo, hela bilden två rader för lågt
Bara signerad läsning av HGX / HGY	Första rasterraden saknas, resten förstörd av skip-testdriften
Signerad läsning, floor-skift och skip-test i pixelytor	Identisk, pixel för pixel, med sidan beräknad från T.88 §6.6.5 och med två oberoende referensavkodare

Fixen är en hjälpare, HalftoneGridPixel, delad av skip-maskbyggaren och placeringsloopen. Den ackumulerar koordinaten i Int64 så att en stor produkt mg × HRX inte kan runna över, dividerar med 256 med avrundning mot minus oändlighet, och klamrar till ±MaxInt div 2 så att ett korrupt raster inte kan svämma över senare bitmappsaritmetik. Skip-testet jämför nu de pixelvärdena mot HPW, HPH, HBW och HBH, exakt som §6.6.5.1 anger

Hur skriver man ett aritmetiskt högerskift i Delphi?

Delphi har ingen aritmetisk skiftoperator, så ett korrekt signerat högerskift måste skrivas som en floor-division, och vanlig div är inte den divisionen. div avkortar mot noll. För icke-negativa värden överensstämmer avkortning och floor, och de överensstämmer också för negativa värden som är exakta multipler av divisorn, vilket är varför -512 div 256 = -2 ser bra ut i ett snabbt test. De är oense överallt annars: -900 div 256 är -3, medan floor är -4, och -1 div 256 är 0, medan floor är -1. En JBIG2-koordinat med en skild-från-noll bråkdel är exakt fallet där div ger fel pixel

På Delphi Win32- och Win64-kompilatorerna ger en Integer-variabel som håller -512, shiftrad höger med 8, 16777214, och en Int64 som håller -512 ger 72057594037927934. Free Pascal definierar också shr som ett logiskt skift och levererar SarLongint och SarInt64 i sin System-unit för den aritmetiska varianten, men de funktionerna finns inte i Delphi, så kod som delas mellan de två kompilatorerna behöver sin egen hjälpare:

// Floor-division: avrundar mot minus oändlighet för vilket tecken A och B har.
// B får inte vara 0, och FloorDiv(Low(Integer), -1) svämmar över precis 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;

// Aritmetiskt högerskift (C:ets och T.88:s ">>" på signerade värden).
// För negativt Value är not Value = -Value - 1 icke-negativt, så det
// logiska shr är säkert där, och det yttre not mappar tillbaka resultatet
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 skiftar aldrig ett negativt tal, så det beror inte på hur en kompilator behandlar teckenbiten, och det svämmar aldrig över, inklusive för Low(Integer). Båda hjälparna matchade en Int64-floorreferens över flera miljoner värden, varje skift från 0 till 31 och kanterna Low(Integer) och High(Integer) på Delphi Win32, Delphi Win64 och Free Pascal x86_64. En sundhetskontroll värd att behålla i vilken enhetstest som helst som rör koordinater:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logiskt skift, den gamla buggen
  Writeln(V div 256);         // -3        avkortning mot noll
  Writeln(FloorDiv(V, 256));  // -4        vad T.88 menar med >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) returnerar också -4, men dess omväg via Double förlorar precision för Int64-värden över 2⁵³, så heltalsgeometri bör stanna i heltal

Vilka PDFlibPas-anrop kör halftone-avkodaren?

JBIG2-halftone-avkodaren körs när PDFlibPas renderar en sida med den inbyggda renderaren, för rendering behöver pixlar. RenderPageToFile och RenderPageToStream når den båda via sidans JBIG2Decode-bildströmmar, så att återrendera en halftonesida är den direkta vägen att bekräfta att v3.539.38 ändrar din utdata. Samma avkodare hanterar de andra JBIG2-regiontyperna, tagna upp i JBIG2 custom Huffman-tabeller i den rena Pascal-avkodaren och att avkoda random access JBIG2-filer i Delphi, och den renderade bitmappen matar konverteringar som att rendera PDF-sidor till 1-bitars 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 avkodar varje JBIG2-region, halftoner inkluderade
      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.

Bildextraktion tar normalt en annan väg. GetPageImageList returnerar JBIG2-bilder i nativ form, och SaveImageListItemDataToFile eller GetImageListItemDataToString ger dig en fristående JBIG2-fil byggd ur strömbytena: filheadern, JBIG2Globals-datat och ett end-of-file-segment runt siddatat. Egenskap 400 hos GetImageListItemIntProperty rapporterar 6 för en sådan post. Inget avkodas på den vägen, så en extraherad .jb2 som ser korrekt ut i en annan visare medan den renderade sidan visar brus var ett typiskt tecken på de här två halftone-buggarna:

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  // fristående JBIG2
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

När masker eller färgkonvertering tvingar fram en renderad fallback kommer posten tillbaka som en avkodad bitmapp och halftone-avkodaren körs. Mer om bildlistor finns i Delphi PDF text-, bild- och fontextraktion

Snabbreferens: regler för JBIG2-halftoneraster

• Indexera skip-masken som HSKIP[ng, mg], rasterkolumn först, och läs den tillbaka i samma ordning varhelst celler placeras (T.88 §6.6.5.1, fixat i PDFlibPas v3.539.37)
• Testa all halftone- eller rastarkod med ett icke-kvadratiskt raster och en asymmetrisk mängd celler utanför regionen, för ett kvadratiskt raster kan dölja ett transponerat index helt
• Läs HGX och HGY som signerade 32-bitarsvärden (T.88 §7.4.5.1.2), aldrig genom en teckenlös hjälpare som klamrar negativa
• Översätt standardens >> 8 som en floor-division med 256, inte som shr 8 och inte som div 256
• Kör skip-testet på shiftade pixelpositioner; fixed-point-formen avviker närhelst bråkdelen är skild från noll, som HGX = -900 med ett 4-pixlars mönster visar
• Ackumulera rasterkoordinater i Int64 och klamra innan de lämnas till bitmappskod, så ett korrupt raster inte kan svämma över
• Uppgradera till v3.539.38 eller senare om dina dokument innehåller halftone-regioner med HENABLESKIP, negativ rasterorigo eller roterade raster

PDFlibPas renderar, extraherar och redigerar PDF-dokument från Delphi och C++Builder med en nativ Pascal-JBIG2-avkodare som nu hanterar halftone-hoppmasker, negativ rasterorigo och roterade raster som T.88 specificerar. Se PDFlibPas Delphi PDF library för funktioner, utgåvor och en testnedladdning