Кастомні таблиці Huffman у чистому Pascal-декодері PDF

PDFlibPas версії 3.539.22 декодує кастомні таблиці Huffman у JBIG2 нативно: чистий Pascal-декодер у PDFlibJBIG2.pas розбирає сегмент Tables (тип 53), призначає канонічні префіксні коди в порядку рядків таблиці, як вимагає ITU-T T.88 Annex B.3, споживає посилання на кастомні таблиці в порядку селекторів для symbol dictionaries і text regions, і обмежує кожне читання оголошеною довжиною сегмента, а не тими байтами, які випадково йдуть далі

Файл, який змусив узятися за цю роботу, зовні нічим не вирізнявся. Відсканований контракт, стиснутий JBIG2 з Huffman-кодуванням символів, а не з набагато поширенішим арифметичним кодуванням, і енкодер, що віз із собою власні кодові таблиці замість стандартних B.1–B.15. Два незалежні декодери розходилися на його refinement-пікселях, а тодішній декодер PDFlibPas видавав текст, схожий на пропущений через шредер: фрагменти гліфів зсунуті на кілька пікселів, у кожного символу бракує одного стовпця. Жодної помилки не піднімалося. Це саме той тип бага, що живе роками, бо декодер, який відкидає файл, отримує support ticket, а декодер, який рендерить його трохи неправильно, отримує клієнта, який вирішує, що скан був поганий

Що насправді містить сегмент JBIG2 Tables?

Сегмент Tables — це компактний опис однієї таблиці Huffman: один байт flags, два знакові 32-бітні межі, а далі серія пар (довжина префікса, довжина діапазону), які розбивають інтервал між межами, як описано в T.88 §7.4.13 і Annex B.2. Біт 0 байта flags — це HTOOB, він каже, чи має таблиця out-of-band код. Біти з 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);

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

Чому префіксні коди треба призначати в порядку рядків таблиці?

Бо енкодер ніколи не записує самі коди. Сегмент JBIG2 Tables несе лише довжини префіксів, і обидві сторони відновлюють справжні бітові шаблони канонічною процедурою з 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 присвоював неініціалізоване поле саме собі, і кожен селектор читався як нуль, а це гнало text regions, які просили кастомні таблиці, через стандартні таблиці F, H і K. Другий дефект означав, що виправлення лише першого все одно давало б зіпсовані символи. Коли Huffman symbol dictionary зберігає свої символи як нестиснуту collective bitmap, останній байт кожного рядка частковий, і старий цикл копіювання трактував padding, у якому лежить кількість валідних бітів, як позицію наймолодшого валідного біта; рядок шириною 63 пікселі копіював зі свого останнього байта один біт замість семи. Виправлений цикл виконує for bitPointer := 7 downto ((8 - padding) and 7), а синтетичні фікстури на 7 і 9 біт фіксують обидва боки межі байта. Коли селектори читаються правильно, таблиці роздаються в тому порядку, у якому їх перелічує специфікація: T.88 §7.4.3.1.2 фіксує для text regions порядок FS, DS, DT, RDW, RDH, RDX, RDY і RSIZE, а §7.4.2.1.1 для symbol dictionaries — DH, DW, BMSIZE і AGGINST. Кожен двобітовий селектор означає стандартну таблицю 0 або 1, значення 2 зарезервоване на полях лише з двома стандартними таблицями, а 3 означає кастомну, і кожен кастомний вибір споживає наступний сегмент Tables серед зазначених сегментів у порядку посилань. NextCustomHuffmanTable робить саме цей обхід і піднімає missing custom Huffman table reference, коли регіон посилається на менше таблиць, ніж вимагають його селектори. До того самого виправлення належить ще один рядок: Huffman symbol dictionary, у якого вхідні й нові символи дають у сумі одиницю, обчислює довжину коду символу як нуль за формулою log2, тоді як Huffman-варіант формату пише кожен symbol ID щонайменше одним бітом, тож if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 у TSymbolDictionarySegment не дає шляху refinement і aggregate читати нуль бітів на кожен symbol 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 refinement бере розмір растру?

До старту арифметичного декодера і з поля, яке існує лише в Huffman-режимі. Коли екземпляр text region несе refinement (RI не нульовий) і встановлено SBHUFF, T.88 §6.4.11 велить декодеру прочитати RDW, RDH, RDX і RDY їхніми вибраними таблицями, потім BMSIZE таблицею RSIZE, потім вирівнятися на межу байта і лише тоді виконати загальне декодування refinement рівно над BMSIZE байтами. У text regions арифметичного режиму такого поля немає, і декодер, який ділить один шлях коду на обидва режими, його пропустить, запустить арифметичний декодер на два чи більше байтів раніше й уточнить кожен символ по сміттю. Шлях symbol dictionary із REFAGG і єдиним екземпляром refinement, описаний у §6.5.8.2.2, має те саме поле BMSIZE з тими самими наслідками. У PDFlibPas верхня межа цього розміру — це TStreamReader.SegmentEnd, кінець поточного сегмента, встановлений readSegments, а не кінець усього потоку, бо BMSIZE, який можна задовольнити лише позичивши байти з наступного сегмента, є некоректним, і перевірка його проти довжини потоку дозволила б арифметичному декодеру читати в наступний заголовок. Нижня межа в два байти відбиває початкову пару байтів, яку арифметичний декодер споживає завжди, а після refinement читач стрибає на RefinementEnd незалежно від того, як далеко вперед забіг арифметичний декодер, бо його фінальна позиція — не позиція наступного поля з Huffman-кодуванням

// Декодування text region у TJBIG2Bitmap, шлях Huffman refinement
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 refinement — тепер декодується в растр із нулем відмінних пікселів проти незалежного декодера, а синтетичні фікстури collective bitmap на 7 і 9 біт дають очікувані рядки на обох. Два незалежні декодери, які розходилися на оригінальному зразку, досі розходяться між собою; PDFlibPas збігається з одним із них, і чесне формулювання таке: нативний вивід збігається з однією незалежною реалізацією і зі специфікацією, як її прочитано, а не з тим, що всі декодери світу згодні між собою. Некорректну частину набору покривають:

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

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