JBIG2 полутонови решетки в PDFlibPas: HSKIP и отмествания

PDFlibPas оправи две независими повреди в native JBIG2 декодера на полутонови региони: в v3.539.37 маската за прескачане HSKIP се индексира като HSKIP[ng, mg], както я дефинира ITU-T T.88 §6.6.5.1, а в v3.539.38 решетки, стигащи отрицателни координати — чрез отрицателен HGX или HGY или чрез ротация — се поставят с истински floor shift. Преди тези версии засегнатите полутонови региони излизахе размазани или изместени, без да се вдига грешка. И двата бъга се криеха зад тестови данни, случайно симетрични или неотрицателни, а вторият включва едно свойство на Delphi и Free Pascal, което хапе далеч извън JBIG2: shr върху знаково цяло число е логически shift, а не аритметичният >>, който стандартът предполага

Полутоновите региони са най-рядката разновидност JBIG2 регион, така че декодер може да обработи хиляди сканирани документи, преди да се срещне с растеризирана снимка, кодирана като такъв. Когато това стане, повредата е неприятна: файлът се парсва, дължините на сегментите се събират, страницата е с правилния размер, а регионът е боклук

Какво всъщност декодира JBIG2 полутоновият регион?

JBIG2 полутонов регион е решетка от малки bitmap-и, избрани от речник с шаблони, а истинската работа на декодера е да пресметне индекс за всяка клетка на решетката и пикселната позиция, където тази клетка попада. Речникът с шаблони държи HNUMPATS шаблона с размер HPW × HPH пиксела. Сегментът на полутоновия регион после описва решетка от HGW колони на HGH реда и изображение в сиво със същия размер, кодирано като Gray-кодирани битови равнини. Всяка битова равнина се декодира с generic региона процедура върху bitmap HGW × HGH, най-значимата равнина пръв, а равнините заедно дават на всяка клетка нейния индекс на шаблон

Поставянето на клетки ползва аритметика с фиксирана точка и 8-битов дял. Началото на решетката HGX, HGY е двойка 32-битови стойности, а векторът на решетката HRX, HRY описва стъпката между съседни клетки, което позволява ротитирана решетка. За ред на решетката mg и колона ng T.88 §6.6.5 смята пикселната позиция така:

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

Маската за прескачане влиза чрез опционалния флаг HENABLESKIP. Когато флагът е включен, §6.6.5.1 строи bitmap HGW × HGH с име HSKIP и задава HSKIP[ng, mg] на 1 за всяка клетка, чийто шаблон лежи изцяло извън региона: x + HPW <= 0, x >= HBW, y + HPH <= 0 или y >= HBH. Сивите битови равнини после се декодират с тази маска като skip bitmap на generic региона, така че аритметичният декодер нито чете, нито обновява контекст за прескачана клетка. Декодер и енкодер трябва да съвпадат по всеки бит на HSKIP, иначе двата аритметични кодера излизат от ритъм

Защо транспонираната HSKIP маска чупеше само не-квадратни решетки?

Маската за прескачане се записваше с разменени координати, а само не-квадратна решетка я изваждаше наяве, защото квадратна решетка пази всяка разменена координата вътре в маската. PDFlibPas пази bitmap-ите с пикселен достъп (column, row), а кодът, строящ маската, подаваше (mg, ng) — редът пръв. Декодерът на сивите битови равнини чете маската коректно като (ng, mg). Цикълът за поставяне на шаблони я четеше обратно в разменения ред на строящия, така че двата съвпадаха, и ревю само на логиката за поставяне щеше да я мине. Капан в имената го влоши: в цикъла за поставяне променливата, казваща се col, обхожда редовете на решетката, а Row обхожда колоните

Вземете решетката 5 × 3 от шаблони 4 × 4 върху регион 16 × 8, която v3.539.37 ползва като регресионен случай. С HRX = 1024 и HRY = 0 колона 4 на решетката попада на x = 16, а ред 2 — на y = 8, и двете извън региона. Коректната маска маркира седем клетки: цялата колона 4 и целият ред 2. Разменените записвания опитваха да зададат пиксели на редови индекси 3 и 4 в маска, висока само три реда, а задавачът на bitmap тихо игнорираше тези извън-диапазонни записвания. Оцелеше колона 2, редове 0 до 2. Декодерът затова прескачаше две клетки, кодирани от енкодера, и декодираше шест клетки, прескачани от енкодера

Аритметичният декодер не се проваля, когато това стане. Той декодира излишни пиксели от битове, принадлежащи на по-късни клетки, контекстите му четат грешни съседи, а всеки индекс на шаблон след първото разминаване е шум — затова симптомът беше размазан регион, а не няколко изместени клетки. На квадратна решетка същият бъг често е невидим: никоя разменена координата не излиза от маската, а когато извън-регионните клетки са симетрични спрямо диагонала — решетка, надвисваща еднакво вдясно и отдолу, например — транспонираната маска е бит по бит коректната. HENABLESKIP е и опционален, трябва да е 0, когато сивото изображение е MMR-кодирано, и рядко се задава от енкодери, така че бъгът имаше много малко начини да излезе наяве. От v3.539.37 строящият записва HSKIP[ng, mg], а цикълът за поставяне чете същия ред

Защо отрицателните отмествания на полутоновата решетка се провалят на три пласта?

Полутонова решетка, започваща вляво от или над своя регион, чупеше PDFlibPas на три отделни места, а всяка повреда криеше следващата. T.88 позволява тази геометрия нарочно. Енкодер, подравняващ растера си към страницата, а не към региона, или ползващ ротитирана решетка, естествено произвежда отрицателни ъгли на клетки, които регионът отрязва. v3.539.38 оправи и трите пласта заедно, защото оправянето само на един само сменяше симптома

Пласт 1: знаково поле, четено като беззнаково

T.88 §7.4.5.1.2 дефинира HGX и HGY като знакови 32-битови стойности, но декодерът ги четеше със същия 32-битов помощник, ползван за беззнаковите полета, а този помощник притискаше всеки отрицателен резултат към 0. Решетка, трябвало да започне от HGX = -900, тихо се местеше върху началото на региона. В регресионния случай на v3.539.38 цялата картина излизаше два реда по-надолу. Притискането обяснява и защо другите две повреди оцеляха толкова дълго: с начало, насилвано да е неотрицателно, отрицателна координата можеше да се появи само чрез ротитирана решетка с HRY > 0, където y = HGY + mg × HRX − ng × HRY пада под нула за по-късните колони на решетката

Пласт 2: shr не е >> 8

T.88 пише >> 8 и значи аритметичен shift, който закръгля към минус безкрайност. Декодерът го преведе като shr 8. В Delphi и Free Pascal shr върху знаково цяло число е логически shift: знаковият бит се вкарва като нула. За Integer, държащ -512, shr 8 дава 16777214 вместо -2. Шаблон, който трябваше да бъде нарисуван на y = -2 и отрязан до долната си половина, беше изпращан 16 милиона реда надолу и пропускан като извън-регионен. Нищо не се срина; горният ред на полутоновия просто изчезваше

Пласт 3: сравняване на фиксирана точка вместо пиксели

Тестът за прескачане сравняваше стойности с фиксирана точка, а не пикселни позиции, а двете не са еквивалентни, щом дялът е ненулев. Оригиналният код заобикаляше логическия shift, като тестваше xx + HPW × 256 <= 0 върху не-изместваната стойност — предполагаем еквивалент на теста на T.88. С HGX = -900 и шаблон от 4 пиксела това дава -900 + 1024 = 124, което е положително, така че клетката не се прескача. Стандартът първо измества: floor(-900 / 256) = -4, а -4 + 4 = 0 отговаря на x + HPW <= 0, така че клетката лежи изцяло извън и трябва да се прескача. Енкодерът я прескачаше, декодерът я декодираше, а сивото изображение се изместваше точно като в случая с транспонираната маска

Регресионният случай от v3.539.38 ползва решетка 4 × 3 от шаблони 4 × 4 при HGX = -900, HGY = -512, HRX = 1024 върху регион 12 × 10. Колоните на решетката попадат на x = -4, 0, 4 и 8, така че колона 0 е изцяло извън и си личи място в HSKIP; редовете на решетката попадат на y = -2, 2 и 6, така че ред 0 трябва да бъде отрязан до долните си два пикселни реда, а не пропуснат. Оправянето на пластовете един по един възпроизвежда стълбицата:

Оправени повреди	Декодиран регион
Нито една (преди v3.539.38)	Решетката дръпната към началото, цялата картина два реда по-надолу
Само знаково четене на HGX / HGY	Първият ред на решетката липсва, останалото размазано от изместването на skip теста
Знаково четене, floor shift и skip тест в пикселно пространство	Идентичен, пиксел по пиксел, на страницата, сметната от T.88 §6.6.5, и на два независими референтни декодера

Поправката е един помощник, HalftoneGridPixel, споделен от строящия маската за прескачане и цикъла за поставяне. Той акумулира координатата в Int64, така че голям продукт mg × HRX не може да препълни, дели на 256 с закръгляне към минус безкрайност и притиска към ±MaxInt div 2, така че повредена решетка не може да препълни по-късната bitmap аритметика. Тестът за прескачане вече сравнява тези пикселни стойности с HPW, HPH, HBW и HBH, точно както го формулира §6.6.5.1

Как се пише аритметичен сдясно shift в Delphi?

Delphi няма оператор за аритметичен shift, затова коректен знаков сдясно shift трябва да се напише като floor деление, а обикновеното div не е това деление. div отрязва към нулата. За неотрицателни стойности отрязването и floor съвпадат, а съвпадат и при отрицателни стойности, точни кратноности на делителя — затова -512 div 256 = -2 изглежда наред в бърз тест. Разминават се навсякъде другаде: -900 div 256 е -3, а floor е -4, и -1 div 256 е 0, а floor е -1. JBIG2 координата с ненулев дял е точно случай, в който div дава грешния пиксел

При компилаторите Delphi Win32 и Win64 променлива Integer с -512, изместена надясно с 8, дава 16777214, а Int64 с -512 дава 72057594037927934. Free Pascal също дефинира shr като логически shift и доставя SarLongint и SarInt64 в unit-а си System за аритметичната версия, но тези функции ги няма в Delphi, затова код, споделен между двата компилатора, се нуждае от собствен помощник:

// Floor деление: закръгля към минус безкрайност за всеки знак на A и B.
// B не бива да е 0, а FloorDiv(Low(Integer), -1) препълва точно като 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;

// Аритметичен сдясно shift (C-ът и T.88 ">>" върху знакови стойности).
// За отрицателен Value, not Value = -Value - 1 е неотрицателно, така че
// логическият shr е безопасен там, а външният not връща резултата обратно
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 никога не измества отрицателно число, така че не зависи от това как компилаторът третира знаковия бит, и никога не препълва, включително за Low(Integer). И двата помощника съвпаднаха с Int64 floor референция върху няколко милиона стойности, при всяко изместване от 0 до 31 и на ръбовете Low(Integer) и High(Integer) на Delphi Win32, Delphi Win64 и Free Pascal x86_64. Sanity проверка, която си заслужава да остане във всеки unit тест, пипащ координати:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  логически shift, старият бъг
  Writeln(V div 256);         // -3        отрязване към нулата
  Writeln(FloorDiv(V, 256));  // -4        това, което T.88 значи с >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) също връща -4, но околният ѝ път през Double губи прецизност за Int64 стойности над 2⁵³, затова цялочислената геометрия трябва да си остане в цели числа

Кои извиквания на PDFlibPas пускат полутоновия декодер?

Полутоновият декодер на JBIG2 работи, когато PDFlibPas рендира страница с вградения рендерер, защото рендирането се нуждае от пиксели. RenderPageToFile и RenderPageToStream и двете стигат до него чрез JBIG2Decode image потоците на страницата, така че повторното рендиране на полутонова страница е директният начин да се уверите, че v3.539.38 променя изхода ви. Същият декодер обработва и другите разновидности JBIG2 регион, разгледани в персонални Huffman таблици на JBIG2 в чистия Pascal декодер и декодиране на random-access JBIG2 файлове в Delphi, а рендираният bitmap храни конверсии като рендиране на PDF страници в 1-битов monochrome

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
      // Рендирането декодира всеки JBIG2 регион, полутоновите включително
      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.

Извличането на изображения обикновено минава по друг път. GetPageImageList връща JBIG2 изображения в native форма, а SaveImageListItemDataToFile или GetImageListItemDataToString ви подават самостоятелен JBIG2 файл, сглобен от байтовете на потока: file header-ът, данните JBIG2Globals и end-of-file сегмент около данните на страницата. Свойство 400 на GetImageListItemIntProperty докладва 6 за такъв елемент. Нищо не се декодира по този път, така че извлечен .jb2, който изглежда наред в друг преглед, докато рендирираната страница показва шум, беше типичен белег на тези два полутонови бъга:

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;

Когато маски или цветова конверсия наложат рендиран fallback, елементът се връща като декодиран bitmap и полутоновият декодер наистина работи. Повече за image списъците има в извличане на текст, изображения и шрифтове от PDF в Delphi

Бърза справка: правила за JBIG2 полутоновата решетка

• Индексирайте маската за прескачане като HSKIP[ng, mg] — колона на решетката пръв — и я четете обратно в същия ред, където и да се поставят клетки (T.88 §6.6.5.1, оправено в PDFlibPas v3.539.37)
• Тествайте всеки полутонов или решетъчен код с не-квадратна решетка и асиметричен набор извън-регионни клетки, защото квадратна решетка може напълно да скрие транспониран индекс
• Четете HGX и HGY като знакови 32-битови стойности (T.88 §7.4.5.1.2), никога чрез беззнаков помощник, притискащ отрицателните
• Превеждайте >> 8 на стандарта като floor деление на 256, не като shr 8 и не като div 256
• Пускайте skip теста върху изместени пикселни позиции; формата с фиксирана точка се разминава всеки път, когато дялът е ненулев, както показва HGX = -900 с шаблон от 4 пиксела
• Акумулирайте координатите на решетката в Int64 и притискайте, преди да ги подадете на bitmap код, така че повредена решетка да не може да препълни
• Надградете към v3.539.38 или по-нова, ако документите ви съдържат полутонови региони с HENABLESKIP, отрицателни начала на решетка или ротитирани решетки

PDFlibPas рендира, извлича и редактира PDF документи от Delphi и C++Builder с native Pascal JBIG2 декодер, който вече обработва полутонови маски за прескачане, отрицателни начала на решетка и ротитирани решетки, както T.88 го определя. Вижте PDFlibPas Delphi PDF library за функции, издания и trial изтегляне