Сітки halftone JBIG2 у PDFlibPas: HSKIP і від'ємні зміщення

PDFlibPas полагодив дві незалежні вади у своєму нативному декодері halftone-регіонів JBIG2: у v3.539.37 маска пропуску HSKIP індексується як HSKIP[ng, mg], як її визначає ITU-T T.88 §6.6.5.1, а в v3.539.38 сітки, що сягають від'ємних координат — через від'ємний HGX чи HGY або через ротацію, — розміщуються зі справжнім floor-зсувом. До тих релізів постраждалі halftone-регіони виходили перемазаними чи зсунутими, без жодної помилки. Обидва баги ховалися за тестовими даними, що випадково були симетричними чи невід'ємними, а другий вмикає властивість Delphi й Free Pascal, яка кусає далеко за межами JBIG2: shr над знаковим цілим — це логічний зсув, а не арифметичний >>, який припускає стандарт

Halftone-регіони — найрідкісніший тип регіонів JBIG2, тож декодер може обробити тисячі відсканованих документів, перш ніж зустріне растрову фотографію, закодовану таким. Коли зустріне — відмова огидна: файл розбирається, довжини сегментів сумуються, сторінка має правильний розмір, а регіон — сміття

Що насправді декодує halftone-регіон JBIG2?

Halftone-регіон JBIG2 — це сітка маленьких бітмапів, узятих зі словника патернів, і справжня робота декодера — обчислити індекс для кожної клітинки сітки та піксельну позицію, куда та клітинка падає. Словник патернів тримає HNUMPATS патернів розміром HPW × HPH пікселів. Сегмент halftone-регіону описує сітку з HGW колонок на HGH рядків і напівтонове зображення того ж розміру, закодоване як бітплощини з кодуванням Gray. Кожна бітплощина декодується процедурою generic region над бітмапом 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 будує бітмап HSKIP розміром HGW × HGH і ставить HSKIP[ng, mg] у 1 для кожної клітинки, чий патерн лежить повністю поза регіоном: x + HPW <= 0, x >= HBW, y + HPH <= 0 чи y >= HBH. Бітплощини напівтонового зображення тоді декодуються з тією маскою як skip-бітмап generic region, тож арифметичний декодер ні читає, ні оновлює контекст для пропущеної клітинки. Декодер і енкодер мусять збігатися в кожному біті HSKIP, інакше два арифметичні кодери розсинхронізуються

Чому транспонована маска HSKIP ламала лише неквадратні сітки?

Маска пропуску записувалася з переплутаними координатами, і лише неквадратна сітка це викривала, бо квадратна сітка тримає кожну переплутану координату всередині маски. PDFlibPas зберігає бітмапи з піксельним доступником (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 маски заввишки лише три рядки, і сеттер бітмапа тихо проігнорував ті записи поза межами. Вижила колонка 2, рядки 0–2. Декодер отже пропустив дві клітинки, які енкодер закодував, і декодував шість клітинок, які енкодер пропустив

Арифметичний декодер не падає, коли таке стається. Він декодує зайві пікселі з бітів, що належать пізнішим клітинкам, його контексти читають неправильних сусідів, і кожен індекс патерну після першої розбіжності — шум, саме тому симптомом була перемазана область, а не кілька зсунутих клітинок. На квадратній сітці той самий баг часто невидимий: жодна переплутана координата не виходить із маски, а коли клітинки поза регіоном симетричні щодо діагоналі — скажімо, сітка нависає над правим і нижнім краями на однакову кількість клітинок, — транспонована маска біт за бітом збігається з коректною. HENABLESKIP ще й необов'язковий, мусить бути 0, коли напівтонове зображення кодоване MMR, і рідко встановлюється енкодерами, тож у бага було дуже мало шляхів виринанути. З v3.539.37 будівник пише HSKIP[ng, mg], а цикл розміщення читає той самий порядок

Чому від'ємні зміщення halftone-сітки ламаються в трьох шарах?

Halftone-сітка, що стартує лівіше чи вище свого регіону, ламала 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 і має на увазі арифметичний зсув, який округлює до мінус нескінченності. Декодер переклав це як shr 8. У Delphi та Free Pascal shr над знаковим цілим — логічний зсув: знаковий біт засувається як нуль. Для Integer, що тримає -512, shr 8 дає 16777214 замість -2. Патерн, який мав бути намальованим на y = -2 і обрізаним до нижньої половини, летів на 16 мільйонів рядків униз і скидався як поза регіоном. Нічого не впало; верхній рядок halftone просто зник

Шар 3: порівняння фіксованої крапки замість пікселів

Тест пропуску порівнював значення фіксованої крапки, а не піксельні позиції, а ці дві речі не еквівалентні, щойно дріб ненульовий. Початковий код обійшов логічний зсув, тестуючи 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-зсув і skip-тест у піксельному просторі	Ідентичний, піксель за пікселем, сторінці, обчисленій з T.88 §6.6.5, і двом незалежним референсним декодерам

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

Як написати арифметичний зсув праворуч у Delphi?

У Delphi немає оператора арифметичного зсуву, тож коректний знаковий зсув праворуч доводиться писати як ділення з округленням донизу, а звичайний 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 як логічний зсув і постачає SarLongint і SarInt64 у своєму юніті 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;

// Арифметичний зсув праворуч (це 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. Санітарна перевірка, варта місця в будь-якому юніт-тесті, що торкається координат:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  логічний зсув, старий баг
  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 запускають halftone-декодер?

Halftone-декодер JBIG2 запускається, коли PDFlibPas рендерить сторінку вбудованим рендерером, бо рендерингу потрібні пікселі. RenderPageToFile і RenderPageToStream обидва доходять до нього через JBIG2Decode-потоки зображень сторінки, тож повторний рендеринг halftone-сторінки — прямий спосіб пересвідчитися, що v3.539.38 змінює ваш вихід. Той самий декодер обслуговує інші типи регіонів JBIG2, описані в власних таблицях Huffman у JBIG2 чистого Pascal-декодера та декодуванні JBIG2-файлів з довільним доступом у Delphi, а відрендерений бітмап живить конверсії, як-от рендеринг 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, включно з halftone
      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-зображення в нативній формі, а SaveImageListItemDataToFile чи GetImageListItemDataToString віддає вам самостійний JBIG2-файл, зібраний із байтів потоку: заголовок файлу, дані JBIG2Globals і сегмент end-of-file навколо даних сторінки. Властивість 400 у GetImageListItemIntProperty звітує 6 для такого елемента. На тому шляху нічого не декодується, тож витягнутий .jb2, що виглядає правильним в іншому переглядачі, тоді як відрендерена сторінка показує шум, був типовою ознакою цих двох halftone-багів:

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;

Коли маски чи конверсія кольору змушують відрендерений фолбек, елемент повертається як декодований бітмап, і halftone-декодер справді запускається. Більше про списки зображень — в екстракції тексту, зображень і шрифтів із PDF у Delphi

Шпаргалка: правила halftone-сітки JBIG2

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

PDFlibPas рендерить, витягує і редагує PDF-документи з Delphi та C++Builder із нативним Pascal-декодером JBIG2, який тепер поводиться з масками пропуску halftone, від'ємними початками сітки і поверненими сітками так, як визначає T.88. Можливості, видання і пробне завантаження — на PDFlibPas Delphi PDF library