PDFlibPas JBIG2 poltonske mreže: HSKIP in negativni odmiki

PDFlibPas je popravil dve neodvisni napaki v svojem izvornem dekodirniku poltonskih regij JBIG2: v v3.539.37 je maska preskoka HSKIP indeksirana kot HSKIP[ng, mg], kakor to definira ITU-T T.88 §6.6.5.1, v v3.539.38 pa so mreže, ki dosežejo negativne koordinate — skozi negativen HGX ali HGY ali skozi zasuk — postavljene s pravim floor pomikom. Pred temi izdajami so prizadete poltonske regije prišle ven pomešane ali premaknjene, brez javljene napake. Oba hrošča sta se skrivala za testnimi podatki, ki so bili po naključju simetrični ali nepredznačeni, drugega pa prižiga lastnost Delphija in Free Pascala, ki grize daleč izven JBIG2: shr nad predznačenim celim številom je logični premik, ne aritmetični >>, ki ga standard predpostavlja

Poltonske regije so najredkejši tip regij JBIG2, zato lahko dekodirnik obdela na tisoče skeniranih dokumentov, preden naleti na rastrirano fotografijo, kodirano kot takšno. Ko se to zgodi, je odpoved grda: datoteka se razčleni, dolžine segmentov se seštejejo, stran ima pravo velikost, regija pa je smeti

Kaj sploh dekodira poltonska regija JBIG2?

Poltonska regija JBIG2 je mreža majhnih bitnih zemljevidov, izbranih iz slovarja vzorcev, pravo delo dekodirnika pa je računanje indeksa za vsako celico mreže in slikovnega položaja, kamor ta celica pristane. Slovar vzorcev drži HNUMPATS vzorcev velikosti HPW × HPH pikslov. Segment poltonske regije nato opisuje mrežo HGW stolpcev krat HGH vrstic in sivinsko sliko iste velikosti, kodirano kot Gray-kodirane bitne ravnine. Vsaka bitna ravnina se dekodira s splošnim postopkom regije nad bitnim zemljevidom HGW × HGH, najprej najvišja ravnina, skupaj pa ravnine dajejo vsaki celici njen indeks vzorca

Postavitev celic uporablja fiksno-pično aritmetiko z 8-bitnim ulomkom. Izvor mreže HGX, HGY je par 32-bitnih vrednosti, vektor mreže HRX, HRY pa opisuje korak med sosednjimi celicami, kar dopušča zasukano mrežo. Za vrstico mreže mg in stolpec mreže ng izračuna T.88 §6.6.5 slikovni položaj kot:

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

Maska preskoka vstopi skozi neobvezen zastavični bit HENABLESKIP. Ko je zastavica nastavljena, zgradi §6.6.5.1 bitni zemljevid HGW × HGH z imenom HSKIP in nastavi HSKIP[ng, mg] na 1 za vsako celico, katere vzorec leži povsem izven regije: x + HPW <= 0, x >= HBW, y + HPH <= 0 ali y >= HBH. Sivinske bitne ravnine se nato dekodirajo s to masko kot preskočnim bitnim zemljevidom splošne regije, tako da aritmetični kodirnik ne bere in ne posodablja konteksta za preskočeno celico. Dekodirnik in kodirnik se morata ujemati v vsakem bitu HSKIP, sicer pa dva aritmetična kodirnika izstopita iz koraka

Zakaj je transponirana maska HSKIP pokvarila samo nekvadratne mreže?

Maska preskoka je bila zapisana z zamenjanimi koordinatami, razkrila pa jo je samo nekvadratna mreža, ker kvadratna mreža obdrži vsako zamenjano koordinato znotraj maske. PDFlibPas shranjuje bitne zemljevide s slikovnim dostopovalnikom (column, row), koda, ki je zgradila masko, pa je podala (mg, ng), najprej vrstico. Dekodirnik sivinskih bitnih ravnin bere masko pravilno kot (ng, mg). Zanka postavitve vzorcev jo je brala nazaj v zamenjanem vrstnem redu graditelja, tako da sta se strinjala, in pregled same logike postavitve bi jo uspešno prešel. Past poimenovanja je to še poglobila: v zanki postavitve spremenljivka z imenom col prehaja vrstice mreže, Row pa stolpce mreže

Vzemimo mrežo 5 × 3 vzorcev 4 × 4 na regiji 16 × 8, ki jo v3.539.37 uporablja kot regresijski primer. S HRX = 1024 in HRY = 0 stolpec mreže 4 pristane pri x = 16 in vrstica mreže 2 pri y = 8, oboje izven regije. Pravilna maska označi sedem celic: celoten stolpec 4 in celotno vrstico 2. Zamenjani zapisi so poskušali nastaviti piksle pri vrstičnih indeksih 3 in 4 v maski, visoki le tri vrstice, nastavljalec bitnega zemljevida pa je te izven-obsežne zapise tiho ignoriral. Kar je preživelo, je bil stolpec 2, vrstice 0 do 2. Dekodirnik je zato preskočil dve celici, ki jih je kodirnik kodiral, in dekodiral šest celic, ki jih je kodirnik preskočil

Aritmetični dekodirnik ne odpove, ko se to zgodi. Dekodira dodatne piksle iz bitov, ki pripadajo kasnejšim celicam, njegovi konteksti berejo napačne sosede, vsak indeks vzorca za prvim nesoglasjem pa je šum — zato je bil simptom pomešana regija namesto nekaj premaknjenih celic. Na kvadratni mreži je isti hrošč pogosto neviden: nobena zamenjana koordinata ne zapusti maske, kadar so celice izven regije simetrične glede na diagonalo, na primer kadar mreža prevesi desni in spodnji rob za isto število celic, je transponirana maska bit za bit pravilna. HENABLESKIP je poleg tega neobvezen, mora biti 0, ko je sivinska slika kodirana z MMR, kodirniki pa ga redko nastavijo, tako da je imel hrošč zelo malo načinov, da pride na plan. Od v3.539.37 graditelj zapiše HSKIP[ng, mg] in zanka postavitve bere isti vrstni red

Zakaj negativni odmiki poltonske mreže odpovejo v treh plasteh?

Poltonska mreža, ki se začne levo od ali nad svojo regijo, je pokvarila PDFlibPas na treh ločenih mestih, vsaka napaka pa je skrila naslednjo. T.88 to geometrijo namenoma dopušča. Kodirnik, ki svoje rastriranje poravna na stran namesto na regijo, ali uporablja zasukano mrežo, naravno izdela negativne kote celic, ki jih regija obreže. v3.539.38 je popravil vse tri plaste skupaj, ker bi popravek katere koli same spremenil samo simptom

Plast 1: predznačeno polje, brano kot nepredznačeno

T.88 §7.4.5.1.2 definira HGX in HGY kot predznačene 32-bitne vrednosti, dekodirnik pa jih je bral z istim 32-bitnim pomočnikom, ki ga je uporabljal za nepredznačena polja, ta pomočnik pa je vsak negativen rezultat stisnil na 0. Mreža, namenjena začetku pri HGX = -900, je bila tiho premaknjena na izvor regije. V regresijskem primeru v3.539.38 je cela slika prišla ven dve vrstici prenizko. Stiskanje pojasnjuje tudi, zakaj sta se drugi dve napaki tako dolgo obdržali: s prisiljeno nepredznačenim izvorom se je lahko negativna koordinata pokazala samo skozi zasukano mrežo z HRY > 0, kjer y = HGY + mg × HRX − ng × HRY pade pod nič za kasnejšimi stolpci mreže

Plast 2: shr ni >> 8

T.88 zapiše >> 8 in misli aritmetični premik, ki zaokrožuje proti minus neskončnosti. Dekodirnik ga je prevedel kot shr 8. V Delphiju in Free Pascalu je shr nad predznačenim celim številom logični premik: predznačni bit je premaknen noter kot nič. Za Integer, ki drži -512, shr 8 da 16777214 namesto -2. Vzorec, ki bi bil narisan pri y = -2 in obrezan na spodnjo polovico, je bil poslan 16 milijonov vrstic navzdol in izpuščen kot izven-regijski. Nič se ni sesulo; zgornja vrstica poltona je preprosto izginila

Plast 3: primerjanje fiksnega pika namesto pikslov

Preskus preskoka je primerjal vrednosti fiksne pike, ne slikovnih položajev, in ti dve nista enakovredna, takoj ko je ulomek neničelen. Izvirna koda se je logičnega premika izognila s preskusom xx + HPW × 256 <= 0 na nepremaknjeni vrednosti, domnevni enakovrednosti preskusa T.88. Z HGX = -900 in vzorcem 4 pikslov to da -900 + 1024 = 124, kar je pozitivno, zato celica ni preskočena. Standard premakne najprej: floor(-900 / 256) = -4 in -4 + 4 = 0 izpolnjuje x + HPW <= 0, tako da celica leži povsem izven in mora biti preskočena. Kodirnik jo je preskočil, dekodirnik jo je dekodiral, sivinska slika pa je zdrsnila točno kot v primeru transponirane maske

Regresijski primer iz v3.539.38 uporablja mrežo 4 × 3 vzorcev 4 × 4 pri HGX = -900, HGY = -512, HRX = 1024 na regiji 12 × 10. Stolpci mreže pristanejo pri x = -4, 0, 4 in 8, tako da je stolpec 0 povsem izven in pripada v HSKIP; vrstice mreže pristanejo pri y = -2, 2 in 6, zato mora biti vrstica 0 obrezana na spodnji dve pikslovni vrstici namesto izpuščena. Popravljanje plasti eno po eno ponovi sklad:

Popravljene napake	Dekodirana regija
Nobena (pred v3.539.38)	Mreža potegnjena na izvor, cela slika dve vrstici prenizko
Samo branje predznačenih HGX / HGY	Prva vrstica mreže manjka, preostanek pomešan zaradi zdrsa preskusa preskoka
Predznačeno branje, floor premik in preskus preskoka v pikslovnem prostoru	Identično, piksel za pikslom, strani, izračunani iz T.88 §6.6.5, in dvema neodvisnima referenčnima dekodirnikoma

Popravek je en sam pomočnik, HalftoneGridPixel, ki ga si delita graditelj maske preskoka in zanka postavitve. Koordinato nabira v Int64, tako da velik zmnožek mg × HRX ne more prevrniti, deli s 256 z zaokroževanjem proti minus neskončnosti in stiska na ±MaxInt div 2, tako da pokvarjena mreža ne more preliti kasnejše bitno-zemljevidne aritmetike. Preskus preskoka zdaj primerja te pikslovne vrednosti z HPW, HPH, HBW in HBH, točno kakor to navaja §6.6.5.1

Kako v Delphiju zapišete aritmetični premik desno?

Delphi nima operatorja aritmetičnega premika, zato je treba pravilen predznačen premik desno zapisati kot floor deljenje, navadni div pa to deljenje ni. div truncira proti ničli. Za nepredznačene vrednosti se trunciranje in floor strinjata, strinjata se tudi za negativne vrednosti, ki so točni mnogokratniki delitelja — zato je -512 div 256 = -2 videti v redu v hitrem preizkusu. Razhajata povsod drugje: -900 div 256 je -3, floor pa je -4, -1 div 256 je 0, floor pa -1. Koordinata JBIG2 z neničelnim ulomkom je točno primer, kjer div da napačen piksel

Na prevajalnikih Delphi Win32 in Win64 da spremenljivka Integer, ki drži -512, premaknjena desno za 8, vrednost 16777214, Int64, ki drži -512, pa 72057594037927934. Free Pascal prav tako definira shr kot logični premik in pošilja SarLongint in SarInt64 v svoji enoti System za aritmetično različico, te funkcije pa v Delphiju ne obstajajo, zato koda, deljena med tema dvema prevajalnikoma, potrebuje svojega pomočnika:

// Floor deljenje: zaokrožuje proti minus neskončnosti za vsak predznak A in B.
// B ne sme biti 0, FloorDiv(Low(Integer), -1) pa se prelije točno kot 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;

// Aritmetični premik desno (C in T.88 ">>" nad predznačenimi vrednostmi).
// Za negativno Value je not Value = -Value - 1 nepredznačeno, zato je
// logični shr tam varen, zunanji not pa preslika rezultat nazaj
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 not nikoli ne premakne negativnega števila, zato ni odvisen od tega, kako prevajalnik ravna s predznačnim bitom, in se nikoli ne prelije, vključno za Low(Integer). Oba pomočnika sta se ujemala z Int64 floor referenco čez nekaj milijonov vrednosti, vsak premik od 0 do 31 ter robova Low(Integer) in High(Integer) na Delphi Win32, Delphi Win64 in Free Pascal x86_64. Preizkus zdrave pameti, vreden hrambe v vsakem testu enote, ki se dotika koordinat:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logični premik, stari hrošč
  Writeln(V div 256);         // -3        trunciranje proti ničli
  Writeln(FloorDiv(V, 256));  // -4        to pomeni T.88 z >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) vrne tudi -4, a njen obvoz skozi Double izgubi natančnost za vrednosti Int64 nad 2⁵³, zato naj celoštevilčna geometrija ostane v celih številih

Kateri klici PDFlibPas poganjajo dekodirnik poltonov?

Dekodirnik poltonov JBIG2 teče, kadar PDFlibPas izrisuje stran z vgrajenim izrisovalnikom, ker izrisovanje potrebuje piksle. RenderPageToFile in RenderPageToStream do njega prideta skozi slikovne tokove JBIG2Decode strani, tako da je ponovni izris poltonske strani neposreden način, da potrdite, da vam v3.539.38 spremeni izhod. Isti dekodirnik obravnava druge tipe regij JBIG2, pokrite v poljubnih tabelah Huffman JBIG2 v čistem Pascal dekodirniku in dekodiranju naključno-dostopnih datotek JBIG2 v Delphiju, izrisana bitna slika pa napaja pretvorbe, kot je izrisovanje strani PDF v 1-bitno monokromno

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
      // Risanje dekodira vsako regijo JBIG2, vključno s poltoni
      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.

Izvlečenje slik običajno gre po drugi poti. GetPageImageList vrne slike JBIG2 v izvirni obliki, SaveImageListItemDataToFile ali GetImageListItemDataToString pa vam poda samostojno datoteko JBIG2, zgrajeno iz bajtov toka: glavo datoteke, podatke JBIG2Globals in segment konec-datoteke okoli podatkov strani. Lastnost 400 od GetImageListItemIntProperty poroča 6 za takšen predmet. Nič se ne dekodira na tej poti, zato je bil izvlečen .jb2, ki je videti pravilen v drugem pregledovalniku, medtem ko izrisana stran kaže šum, tipičen znak teh dveh poltonskih hroščev:

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;

Kadar maske ali pretvorba barv vsilijo izrisovan kot rezervno pot, se predmet vrne kot dekodirana bitna slika in dekodirnik poltonov res teče. Več o seznamih slik je v izvlečenju besedila, slik in pisav PDF v Delphiju

Hiter pregled: pravila mreže poltonov JBIG2

• Indeksirajte masko preskoka kot HSKIP[ng, mg], najprej stolpec mreže, in jo berite nazaj v istem vrstnem redu, kjer koli se postavljajo celice (T.88 §6.6.5.1, popravljeno v PDFlibPas v3.539.37)
• Preskusite katero koli kodo poltonov ali mrež z nekvadratno mrežo in nesimetrično množico celic izven regije, ker lahko kvadratna mreža popolnoma skrije transponiran indeks
• Berite HGX in HGY kot predznačene 32-bitne vrednosti (T.88 §7.4.5.1.2), nikoli skozi nepredznačenega pomočnika, ki stiska negativne
• Standardov >> 8 prevedite kot floor deljenje s 256, ne kot shr 8 in ne kot div 256
• Poganjajte preskus preskoka na premaknjenih slikovnih položajih; oblika fiksne pike se razlikuje, kadar koli je ulomek neničelen, kakor to pokaže HGX = -900 z vzorcem 4 pikslov
• Nabirajte koordinate mreže v Int64 in jih stisnite, preden jih izročite bitno-zemljevidni kodi, tako da pokvarjena mreža ne more preliti
• Nadgradite na v3.539.38 ali novejši, če vaši dokumenti vsebujejo poltonske regije s HENABLESKIP, negativnimi izvori mreže ali zasukanimi mrežami

PDFlibPas izrisuje, izvlači in ureja dokumente PDF iz Delphija in C++Builderja z izvornim Pascal dekodirnikom JBIG2, ki zdaj obravnava maske preskoka poltonov, negativne izvore mreže in zasukane mreže, kakor to določa T.88. Poglejte PDFlibPas Delphi PDF knjižnico za zmožnosti, izdaje in preskusni prenos