Кастомные таблицы Huffman JBIG2 в Pascal-декодере PDFlibPas

PDFlibPas версии 3.539.22 декодирует кастомные таблицы Huffman в JBIG2 нативно: декодер на чистом Pascal в PDFlibJBIG2.pas разбирает сегмент Tables (тип 53), присваивает канонические префиксные коды в порядке строк таблицы, как того требует ITU-T T.88 Annex B.3, потребляет ссылки на кастомные таблицы в порядке селекторов для словарей символов и текстовых областей и ограничивает каждое чтение объявленной длиной сегмента, а не теми байтами, что случайно оказались следом

Файл, который заставил взяться за эту работу, с виду был ничем не примечателен. Сканированный контракт, сжатый JBIG2 с Huffman-кодированием символов вместо куда более распространённого арифметического, причём кодировщик вёз собственные таблицы кодов вместо стандартных B.1–B.15. Два независимых декодера расходились на его пикселях уточнения, а тогдашний декодер PDFlibPas выдавал текст, будто прошедший через шредер: фрагменты глифов, сдвинутые на несколько пикселей, у каждого символа не хватает столбца. Ничего не сообщало об ошибке. Именно так и выглядят баги, которые живут годами: декодер, отклоняющий файл, получает обращение в поддержку, а декодер, отрисовывающий его слегка неправильно, получает заказчика, который решит, что плохой был скан

Что на самом деле содержит сегмент Tables в JBIG2?

Сегмент Tables — это компактное описание одной таблицы Huffman: байт флагов, две знаковые 32-битные границы, а дальше набор пар «длина префикса, длина диапазона», разбивающих интервал между границами, как это изложено в T.88 §7.4.13 и Annex B.2. Бит 0 байта флагов — это HTOOB, он говорит, есть ли в таблице код вне диапазона. Биты с 1 по 3 плюс единица дают HTPS — сколько бит используется на запись каждой длины префикса; биты с 4 по 6 плюс единица дают HTRS — ширину поля каждой длины диапазона. Бит 7 зарезервирован, и PDFlibPas отклоняет сегмент, если тот выставлен, вместо того чтобы угадывать, что имела в виду будущая ревизия. Дальше идут HTLOW и HTHIGH как знаковые 32-битные целые, и это первое место, где декодер может ошибиться: чтение их как беззнаковых превращает таблицу, у которой нижняя граница отрицательна — а это совершенно нормально для ширин символов с дельта-кодированием, — в таблицу, начинающуюся с четырёх миллиардов. Каждое поле проходит через локальный хелпер ReadField, который сверяет запрос с позицией бита, где заканчиваются данные сегмента, ещё до обращения к читателю, потому что таблица, читающая за своим сегментом, проглотила бы заголовок следующего сегмента как длины префиксов

// TCodeTableSegment.readSegment, PDFlibJBIG2.pas
EndBit := (Int64(decoder.reader.bytePointer) +
  segmentHeader.getSegmentDataLength) * 8;
Flags := ReadField(8);
if (Flags and $80) <> 0 then
  raise EJBIG2DecodeError.Create('reserved custom Huffman table flag');
PrefixBits := ((Flags shr 1) and 7) + 1;   // HTPS
RangeBits  := ((Flags shr 4) and 7) + 1;   // HTRS
LowValue   := Integer(ReadField(32));      // знаковый HTLOW
HighValue  := Integer(ReadField(32));      // знаковый HTHIGH
if LowValue >= HighValue then
  raise EJBIG2DecodeError.Create('invalid custom Huffman range bounds');
CurrentValue := LowValue;
while CurrentValue < HighValue do
begin
  PrefixLength := ReadField(PrefixBits);
  RangeLength  := ReadField(RangeBits);
  if RangeLength > 32 then
    raise EJBIG2DecodeError.Create('invalid custom Huffman range length');
  AddLine(CurrentValue, PrefixLength, RangeLength);
  Inc(CurrentValue, Int64(1) shl RangeLength);
end;
AddLine(LowValue - 1, ReadField(PrefixBits), jbig2HuffmanLOW);
AddLine(HighValue,   ReadField(PrefixBits), 32);
if (Flags and 1) <> 0 then
  AddLine(0, ReadField(PrefixBits), jbig2HuffmanOOB);

Две строки, добавленные после цикла, — это эскейп-строки из Annex B.2: строка нижнего диапазона начинается с HTLOW минус один и считает вниз, строка верхнего диапазона начинается с HTHIGH с фиксированным 32-битным диапазоном, а необязательная строка OOB не имеет значения вообще. PDFlibPas помечает их служебными длинами диапазона jbig2HuffmanLOW ($FFFFFFFD) и jbig2HuffmanOOB ($FFFFFFFE) — той же договорённостью, что и его пятнадцать встроенных стандартных таблиц, так что циклу декодирования всё равно, пришла таблица из спецификации или из файла

Почему префиксные коды нужно присваивать в порядке строк таблицы?

Потому что кодировщик сами коды не пишет. Сегмент Tables в JBIG2 несёт только длины префиксов, а обе стороны восстанавливают фактические битовые шаблоны по канонической процедуре из Annex B.3: посчитать, сколько строк имеет каждую длину, раздать сначала коды длиной один, затем сдвинуть влево и продолжать, а внутри одной длины выдавать коды в том порядке, в каком строки объявлены. Любое отклонение от этого порядка молча даёт другую таблицу. Декодер этого не заметит, потому что каждый сгенерированный им битовый шаблон всё ещё валидный префиксный код — просто не тот, которым пользовался кодировщик, и на выходе получается правдоподобная на вид растровая карта, собранная из неверных символов

// THuffmanDecoder.buildTable, PDFlibJBIG2.pas
FillChar(Counts, SizeOf(Counts), 0);
for I := 0 to length - 1 do
begin
  if table[I].prefixLen > 32 then
    raise EJBIG2DecodeError.Create(
      'Huffman prefixes longer than 32 bits are not supported');
  Inc(Counts[table[I].prefixLen]);
end;
Active := 0;
Code := 0;
for Bits := 1 to 32 do
begin
  Starts[Bits]    := Active;
  Positions[Bits] := Active;
  Inc(Active, Counts[Bits]);
  if Code + UInt64(Counts[Bits]) > (UInt64(1) shl Bits) then
    raise EJBIG2DecodeError.Create('oversubscribed Huffman prefix codes');
  Code := (Code + UInt64(Counts[Bits])) shl 1;
end;
SetLength(Result, Active + 1);
for I := 0 to length - 1 do            // устойчивая: исходный порядок сохранён
  if table[I].prefixLen > 0 then       // внутри каждой длины префикса
  begin
    Result[Positions[table[I].prefixLen]] := table[I];
    Inc(Positions[table[I].prefixLen]);
  end;
Code := 0;
for Bits := 1 to 32 do
begin
  for I := Starts[Bits] to Positions[Bits] - 1 do
  begin
    Result[I].prefix := Cardinal(Code);
    Inc(Code);
  end;
  Code := Code shl 1;
end;
Result[Active].rangeLen := jbig2HuffmanEOT;

THuffmanDecoder.buildTable — это сортировка подсчётом, а не сравнением, ровно по одной причине: проход с подсчётом по Counts, Starts и Positions устойчив по построению, так что строки одинаковой длины префикса попадают в результат в порядке объявления — а именно по этому порядку Annex B.3 и присваивает коды. Строки с нулевой длиной префикса отбрасываются до присваивания кодов, потому что B.3 определяет их как неиспользуемые, а не как однобитные коды. В том же цикле стоят две защиты. Проверка переполнения ловит таблицу, длины которой заявляют больше кодов, чем может вместить префиксный код такой глубины, — это неравенство Крафта, выраженное целочисленным сравнением; без неё враждебная таблица даёт код, совпадающий с двумя строками, и декодер берёт ту, до которой дойдёт первым. Потолок в 32 бита существует потому, что prefix — это Cardinal, и сопоставитель в decodeInt накапливает биты в одно значение. T.88 на бумаге допускает и более длинные префиксы, PDFlibPas отклоняет их по имени, и ни один реальный кодировщик таких пока не выдавал. Арифметика значений требует той же аккуратности, что и арифметика кодов: THuffmanTable.val — это Int64, и строка нижнего диапазона декодируется как val - readBits(32), то есть 32-битное беззнаковое смещение, вычитаемое из HTLOW минус один. С промежуточными значениями типа Integer это вычитание переполняется, и переполненное значение затем принимается как ширина символа. 64-битный путь считает истинное значение, сверяет его со знаковым 32-битным диапазоном и возбуждает исключение, если оно не влезает, — так тихая порча превращается в явный отказ

Почему кастомные таблицы не срабатывали до 3.539.22?

Два дефекта прятали друг друга. Первый был однострочным багом сеттера: TTextRegionHuffmanFlags.setFlags получал свой аргумент под тем же именем, что и поле, в которое писал, поэтому Self.flagsAsInt := flagsAsInt присваивал неинициализированное поле само себе, и каждый селектор читался как ноль — это отправляло текстовые области, запрашивавшие кастомные таблицы, через стандартные F, H и K. Второй дефект означал, что исправление одного первого всё равно дало бы испорченные символы. Когда словарь символов Huffman хранит символы как несжатую коллективную растровую карту, последний байт каждой строки неполный, и старый цикл копирования принимал padding, где лежит число валидных бит, за позицию младшего валидного бита; строка шириной 63 пикселя копировала из своего последнего байта один бит вместо семи. Исправленный цикл идёт for bitPointer := 7 downto ((8 - padding) and 7), а синтетические фикстуры шириной 7 и 9 бит закрепляют обе стороны байтовой границы. Когда селекторы читаются правильно, таблицы выдаются в том порядке, в каком их перечисляет спецификация: T.88 §7.4.3.1.2 фиксирует для текстовых областей порядок FS, DS, DT, RDW, RDH, RDX, RDY и RSIZE, а §7.4.2.1.1 — для словарей символов DH, DW, BMSIZE и AGGINST. Каждый двухбитный селектор означает стандартную таблицу 0 или 1, значение 2 зарезервировано на полях, где стандартных таблиц всего две, а 3 означает кастомную, и каждый выбор кастомной потребляет следующий сегмент Tables среди упомянутых сегментов в порядке упоминания. NextCustomHuffmanTable делает ровно этот обход и возбуждает missing custom Huffman table reference, когда область ссылается на меньше таблиц, чем требуют её селекторы. К тому же исправлению относится ещё одна строка: у словаря символов Huffman, где входные и новые символы в сумме дают единицу, формула через log2 даёт длину кода символа ноль, тогда как Huffman-вариант формата пишет каждый ID символа минимум одним битом, поэтому if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 в TSymbolDictionarySegment не даёт пути уточнения и агрегирования прочитать по нулю бит на ID символа

Что гарантирует граница сегмента?

PDFlibPas относится к длине данных сегмента в каждом заголовке как к контракту, который обязаны соблюдать обе стороны: сегмент не может читать за своим объявленным концом и не может закончиться раньше, оставив следующий заголовок на непредсказуемом смещении. Правила, которые из этого контракта следуют, по отдельности невелики. Длина данных с выставленным битом 31 — это маркер неизвестной длины из T.88 §7.2.7, и handleSegmentDataLength отображает её в отрицательное значение, которое readSegments отвергает сразу, вместо того чтобы сканировать вперёд в поисках терминатора. Каждый номер упомянутого сегмента должен быть меньше номера текущего и уже существовать, так что ссылка вперёд или в никуда падает ещё до того, как какая-либо область попробует её разрешить. END_OF_PAGE и END_OF_FILE должны объявлять ноль байт данных. Сегмент Profiles (тип 52) несёт 32-битный счётчик, за которым идёт столько же 32-битных идентификаторов и ни одного пикселя, поэтому его проверяют как 4 плюс 4 умножить на счётчик против объявленной длины, пропускают и оставляют в списке сегментов только затем, чтобы более поздние сегменты могли сослаться на него по номеру. Неизвестный идентификатор профиля — это не неизвестное кодирование, и обращение с ним как с таковым отклонило бы файлы, которые декодируются совершенно нормально

// TJBIG2StreamDecoder.readSegments, PDFlibJBIG2.pas
DataLength := segmentHeader.getSegmentDataLength;
if DataLength < 0 then
  raise EJBIG2DecodeError.Create(Context +
    'unknown or oversized segment length is not supported');
if DataLength > Length(reader.Data) - reader.bytePointer then
  raise EJBIG2DecodeError.Create(Context + 'truncated segment data');
DataEnd := reader.bytePointer + DataLength;
for I := 0 to noOfReferredToSegments - 1 do
  if (referredToSegments[I] >= segmentHeader.getSegmentNumber) or
     (findSegment(referredToSegments[I]) = nil) then
    raise EJBIG2DecodeError.Create(Context + 'invalid segment reference');
// ... создаём объект сегмента для этого типа ...
reader.SegmentEnd := DataEnd;
segment.readSegment;
if reader.bytePointer > DataEnd then
  raise EJBIG2DecodeError.Create(Context +
    'decoded data exceeds declared segment length');
if reader.bytePointer < DataEnd then
begin
  reader.bytePointer := DataEnd;   // MMR может оставить EOFB непрочитанным
  reader.bitPointer := 7;
end;

Именно на хвосте этого цикла прежняя версия декодера ошибалась на областях с кодированием MMR. Декодер MMR знает, что закончил, когда получен последний пиксель последней строки, а это может случиться до того, как он потребил терминатор EOFB, который T.88 §6.2.5.7 ставит в конец данных. Старый код предполагал, что читатель стоит на следующем заголовке, поэтому оставшиеся байты терминатора разбирались как номер сегмента, и поток падал несколькими байтами позже с вводящей в заблуждение ошибкой. Теперь побеждает объявленный конец: читать за ним — ошибка, остановиться раньше — нормально, а читатель переставляется на DataEnd со сброшенным указателем бита, чтобы следующий заголовок читался оттуда, где файл сказал, что он будет. Та же дисциплина видна везде, где PDFlibPas разбирает недоверенные структуры PDF: объявленная длина — это граница, и декодер не идёт искать границу поудобнее

Откуда уточнение по Huffman берёт размер своей растровой карты?

До запуска арифметического декодера и из поля, которое существует только в режиме Huffman. Когда экземпляр текстовой области несёт уточнение (RI не равен нулю) и выставлен SBHUFF, T.88 §6.4.11 предписывает декодеру прочитать RDW, RDH, RDX и RDY их выбранными таблицами, затем BMSIZE таблицей RSIZE, затем выровняться на байтовую границу и только после этого выполнить общее декодирование уточнения ровно по BMSIZE байтам. У текстовых областей в арифметическом режиме такого поля нет, и декодер с одним общим путём для обоих режимов его пропустит, запустит арифметический декодер на два или больше байт раньше и уточнит каждый символ по мусору. Путь словаря символов с REFAGG и единственным экземпляром уточнения, описанный в §6.5.8.2.2, имеет то же поле BMSIZE с теми же последствиями. В PDFlibPas верхняя граница этого размера — это TStreamReader.SegmentEnd, конец текущего сегмента, выставленный readSegments, а не конец всего потока, потому что BMSIZE, который можно удовлетворить только заняв байты у следующего сегмента, — это порча, и сверка его с длиной потока дала бы арифметическому декодеру читать в следующий заголовок. Нижняя граница в два байта отражает начальную пару байт, которую арифметический декодер потребляет всегда, а после уточнения читатель перескакивает на RefinementEnd независимо от того, насколько вперёд забежал арифметический декодер, поскольку его конечная позиция — не позиция следующего поля с Huffman-кодированием

// Декодирование текстовой области TJBIG2Bitmap, путь уточнения по Huffman
RefinementSize := huffmanDecoder.decodeInt(huffmanRSizeTable).intResult;
huffmanDecoder.consumeRemainingBits;
if (RefinementSize < 2) or
   (RefinementSize > huffmanDecoder.reader.SegmentEnd -
                     huffmanDecoder.reader.bytePointer) then
  raise EJBIG2DecodeError.Create('invalid refinement bitmap size');
RefinementEnd := huffmanDecoder.reader.bytePointer + RefinementSize;
arithmeticDecoder.start;
// ... readGenericRefinementRegion ...
if huffmanDecoder.reader.bytePointer > RefinementEnd then
  raise EJBIG2DecodeError.Create('refinement data exceeds declared size');
huffmanDecoder.reader.bytePointer := RefinementEnd;
huffmanDecoder.reader.bitPointer := 7;

Что было проверено, и что по-прежнему отклоняется

Образец, с которого всё началось, — изображение JBIG2 размером 500 на 473 пикселя с кастомными таблицами и уточнением по Huffman — теперь декодируется в растровую карту с нулём различающихся пикселей против независимого декодера, а синтетические фикстуры коллективной растровой карты шириной 7 и 9 бит дают ожидаемые строки на обеих. Два независимых декодера, расходившихся на исходном образце, по-прежнему расходятся друг с другом; PDFlibPas совпадает с одним из них, и честная формулировка такова: нативный вывод совпадает с одной независимой реализацией и с прочитанной спецификацией, а не такова, что все декодеры мира согласны. Сторона набора тестов, отвечающая за порчу, покрывает:

• зарезервированный бит флагов или зарезервированное значение селектора
• таблицу, обрезанную посреди строки
• переполненные длины префиксов и префиксы длиннее 32 бит
• область, чьи селекторы запрашивают больше кастомных таблиц, чем она упоминает
• подтверждение, что устаревший вывод очищается после неудачного декодирования, а не остаётся на месте, чтобы вызывающий принял его за результат

Три ограничения остаются намеренными. Организация потока с произвольным доступом, когда все заголовки сегментов идут перед всеми данными сегментов, возбуждает JBIG2 random-access organisation is not supported сразу после чтения флагов заголовка файла, потому что нет представительного образца, на котором это можно проверить, а наполовину реализованный путь хуже отказа по имени. Кастомные таблицы ограничены 65 536 строками и 32-битными префиксами. А публичная точка входа декодирования, TPLJBIG2Decoder.LoadFromByteArray, возвращает растровую карту первой страницы в порядке потока через getPageAsJBIG2Bitmap(0) — первый встреченный сегмент информации о странице, — а не ищет ассоциацию страницы с номером ноль; встроенные потоки PDF регулярно нумеруют свою единственную страницу единицей, и запрос страницы 0 по ассоциации не нашёл бы ничего. Текст отказа попадает в TPLJBIG2Decoder.LastError — внутреннюю диагностику декодера, несущую номер сегмента, тип и байтовое смещение сбоя, и это не то же самое, что библиотечный TPDFlib.LastErrorCode. Ничего из этого не касается стороны кодирования, которая разобрана в заметках про бэкенды кодировщика JBIG2 и то, как они линкуются; путь чтения обязан принимать то, что решил выдать чужой кодировщик, и делит свои правила с остальной частью стека работы с изображениями, включая встроенный декодер TIFF и его отказы для BigTIFF и тайловой раскладки: отказывать по имени, никогда не занимать байты через объявленную границу и держать арифметику настолько широкой, чтобы переполненное промежуточное значение не могло сойти за верный ответ. Если вы оцениваете нативный путь чтения JBIG2 для Delphi или C++Builder, декодер и остальная работа с изображениями описаны на странице PDF Library for Delphi