JBIG2-полутона в PDFlibPas: HSKIP и отрицательные сдвиги

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

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

Что на самом деле декодирует полутоновая область JBIG2?

Полутоновая область JBIG2 — это сетка маленьких битмапов, выбранных из словаря паттернов, и настоящая работа декодера — вычислить индекс для каждой ячейки сетки и пиксельную позицию, куда эта ячейка приземляется. Словарь паттернов держит HNUMPATS паттернов размером HPW × HPH пикселей. Сегмент полутоновой области затем описывает сетку из HGW столбцов на HGH строк и полутоновое изображение того же размера, кодированное как Gray-битплейны. Каждый битплейн декодируется процедурой generic region над битмапом HGW × HGH, старший план первым, и вместе планы дают каждой ячейке её индекс паттерна

Размещение ячеек использует fixed-point арифметику с 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 строит битмап HGW × HGH с именем HSKIP и ставит 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], и цикл размещения читает тот же порядок

Почему отрицательные смещения полутоновой сетки ломаются в три слоя?

Полутоновая сетка, начинающаяся левее или выше своей области, ломала 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 миллионов строк вниз и отбрасывался как вне области. Ничего не падало; просто верхняя строка полутона исчезала

Слой 3: сравнение fixed-point вместо пикселей

Тест пропуска сравнивал fixed-point значения, а не пиксельные позиции, а после появления ненулевой дробной части это уже не эквивалентно. Исходный код обходил логический сдвиг проверкой 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	Первая строка сетки отсутствует, остальное искажено дрейфом теста пропуска
Знаковое чтение, floor-сдвиг и пиксельный тест пропуска	Идентично пиксель в пиксель странице, вычисленной по T.88 §6.6.5, и двум независимым референс-декодерам

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

Как записать арифметический сдвиг вправо в Delphi?

В Delphi нет оператора арифметического сдвига, поэтому корректный знаковый сдвиг вправо приходится писать как 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 как логический сдвиг и поставляет 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 запускают полутоновый декодер?

Полутоновый декодер JBIG2 запускается, когда PDFlibPas рендерит страницу встроенным рендерером, потому что рендерингу нужны пиксели. RenderPageToFile и RenderPageToStream добираются до него через JBIG2Decode-потоки изображений страницы, так что повторный рендеринг полутоновой страницы — прямой способ убедиться, что v3.539.38 меняет ваш вывод. Тот же декодер обрабатывает прочие типы областей JBIG2, разобранные в статьях о пользовательских таблицах Huffman в чисто Pascal-декодере JBIG2 и декодировании random-access JBIG2-файлов на Delphi, а отрендеренный битмап питает конверсии вроде рендеринга страниц PDF в 1-битный монохром

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-изображения в нативной форме, а SaveImageListItemDataToFile или GetImageListItemDataToString выдают самостоятельный JBIG2-файл, собранный из байтов потока: заголовок файла, данные JBIG2Globals и сегмент конца файла вокруг данных страницы. Свойство 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;

Когда маски или конверсия цвета заставляют рендерный фоллбэк, элемент возвращается декодированным битмапом, и полутоновый декодер действительно запускается. Подробнее о списках изображений — в извлечении текста, изображений и шрифтов из 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
• Прогоняйте тест пропуска на сдвинутых пиксельных позициях; fixed-point форма расходится всякий раз, когда дробная часть ненулевая, как показывает HGX = -900 с паттерном в 4 пикселя
• Накапливайте координаты сетки в Int64 и клампите перед передачей в битмапный код, чтобы битая сетка не могла переполнить
• Обновляйтесь до v3.539.38 или новее, если ваши документы содержат полутоновые области с HENABLESKIP, отрицательными началами сеток или повёрнутыми сетками

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