JBIG2 Huffman таблици по избор в чист Pascal PDF декодер

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

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

Какво всъщност съдържа JBIG2 сегментът Tables?

Сегментът Tables е компактно описание на една Huffman таблица: един flags байт, две знакови 32-битови граници и после серия от двойки (prefix length, range length), които разделят интервала между границите, както е разписано в T.88 §7.4.13 и Annex B.2. Бит 0 на flags байта е HTOOB и казва дали таблицата има out-of-band код. Битове 1 до 3 плюс едно дават HTPS — броя битове, с които се записва всяка дължина на префикс; битове 4 до 6 плюс едно дават HTRS — ширината на всяко поле с range length. Бит 7 е резервиран, и PDFlibPas отхвърля сегмента, ако е вдигнат, вместо да гадае какво е имал предвид бъдеща ревизия на стандарта. HTLOW и HTHIGH идват като знакови 32-битови цели, и това е първото място, където декодер може да се обърка: прочитани като unsigned, таблица с отрицателна долна граница — съвсем нормална за delta-кодирани ширини на символи — изглежда сякаш започва от четири милиарда. Всяко поле минава през локалния helper ReadField, който проверява заявката спрямо бит-позицията, на която свършват данните на сегмента, преди да пипне четеца, защото таблица, чела зад сегмента си, би поглъщала header-а на следващия сегмент като дължини на префикси

// 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: долният range ред тръгва от HTLOW минус едно и брои надолу, горният range ред тръгва от HTHIGH с фиксиран 32-битов range, а незадължителният OOB ред няма стойност изобщо. PDFlibPas ги маркира със sentinel range дължините jbig2HuffmanLOW ($FFFFFFFD) и jbig2HuffmanOOB ($FFFFFFFE) — същата конвенция, която ползват петнайсетте му вградени стандартни таблици — така че декодиращият цикъл не се интересува дали таблицата идва от спецификацията или от файла

Защо prefix кодовете трябва да се разпределят в подредбата на редовете на таблицата?

Защото енкодерът никога не записва кодовете. JBIG2 сегментът Tables носи само дължини на префикси, а и двете страни възстановяват реалните бит-модели с каноничната процедура в Annex B.3: преброй колко реда имат всяка дължина, раздай първо кодове с дължина едно, после измести наляво и продължи, а в рамките на една дължина раздавай кодовете в подредбата, в която се появяват редовете. Всяко отклонение от тази подредба тихо дава друга таблица. Декодерът няма да забележи, защото всеки бит-модел, който генерира, пак е валиден prefix код — просто не този, който енкодерът е ползвал — а изходът е правдоподобно изглеждащ битмап, сглобен от грешните символи

// 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 е counting sort, а не comparison sort, по една причина: counting пасът върху Counts, Starts и Positions е стабилен по конструкция, така че редовете с равна дължина на префикса попадат в резултата в подредбата, в която са декларирани — точно подредбата, по която Annex B.3 раздава кодовете. Редовете с нулева дължина на префикса отпадат преди разпределянето на кодовете, защото B.3 ги дефинира като неизползвани, а не като еднобитови кодове. Два guard-а седят в същия цикъл. Проверката за oversubscription хваща таблица, чиито дължини искат повече кодове, отколкото prefix код с тази дълбочина може да побере — това е неравенството на Kraft, изразено като сравнение на цели числа; без нея враждебна таблица дава код, който пасва на два реда, и декодерът избира който и да прегледа пръв. Таванът от 32 бита съществува, защото prefix е Cardinal, а matcher-ът в decodeInt трупа битове в един такъв. T.88 позволява по-дълги префикси на хартия, PDFlibPas ги отхвърля по име, и реален енкодер, излъчвал такъв, не е виждан. Стойностната аритметика иска същата грижа като кодовата: THuffmanTable.val е Int64, а долният range ред се декодира като val - readBits(32) — 32-битов unsigned offset, изваден от HTLOW минус едно. С Integer междинни стойности това изваждане се превърта, а превъртената стойност после минава за ширина на символ. 64-битовият път смята истинската стойност, проверява я спрямо знаковия 32-битов диапазон и вдига грешка, ако не се побира, което превръща тихата развала в изричен отказ

Защо таблиците по избор не се включваха никога преди 3.539.22?

Два дефекта се криеха един зад друг. Първият беше едноредов бъг в setter: TTextRegionHuffmanFlags.setFlags получаваше аргумента си под същото име, като полето, в което го записваше, така че Self.flagsAsInt := flagsAsInt присвояваше неинициализираното поле само на себе си, всеки селектор се четеше обратно като нула, и текстовите региони, искащи таблици по избор, минаваха през стандартните F, H и K. Вторият дефект значеше, че една-единствена поправка на първия пак би дала развалени символи. Когато Huffman symbol речник съхранява символите си като некомпресиран колективен битмап, последният байт на всеки ред е частичен, а старият копиращ цикъл третираше 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 за symbol речници като DH, DW, BMSIZE и AGGINST. Всеки двубитов селектор значи стандартна таблица 0 или 1, резервирано за 2 по полета с само две стандартни таблици, и таблица по избор за 3, а всяко такова избиране консумира следващия Tables сегмент измежду споменатите сегменти в подредбата на справките. NextCustomHuffmanTable прави точно този обход и вдига missing custom Huffman table reference, когато регион сочи по-малко таблици, отколкото селекторите му искат. Още един ред принадлежи на същата поправка: Huffman symbol речник, чийто входни и нови символи се събират на едно, изчислява нула за дължина на символния код от формулата с log2, докато Huffman вариантът на формата пише всеки symbol ID с поне един бит, така че if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 в TSymbolDictionarySegment пази пътя за refinement и агрегация от четене на нула бита на symbol ID

Каква гаранция дава границата на сегмента?

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

// 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 поставя в края на данните. Старият код приемаше, че четецът стои на следващия header, така че останалите байтове на терминатора се парсваха като номер на сегмент и stream-ът се проваляше няколко байта по-късно с подвеждаща грешка. Сега декларираният край печели: четене зад него е грешка, по-ранен стоп е нормален, а четецът се мести на DataEnd с нулиран бит-указател, така че следващият header се чете оттам, откъдето файлът каза, че ще бъде. Същата дисциплина се показва навсякъде, където PDFlibPas парсва недоверени PDF структури: декларираната дължина е границата, а декодерът не ходи да търси по-удобна

Откъде refinement четенето по Huffman взема размера на битмапа си?

Преди аритметичният декодер да тръгне, и от поле, което съществува само в Huffman режим. Когато инстанция на текстов регион носи refinement (RI е ненулево) и SBHUFF е вдигнат, T.88 §6.4.11 кара декодера да прочете RDW, RDH, RDX и RDY с избраните им таблици, после BMSIZE с таблицата RSIZE, после да подравни на байтова граница, и чак тогава да пусне generic refinement декодиране върху точно BMSIZE байта. Текстовите региони в аритметичен режим нямат такова поле, и декодер, който дели един кодов път за двата режима, ще го прескочи, ще пусне аритметичния декодер два и повече байта по-рано и ще refine-ва всеки символ срещу боклук. Пътят на symbol речника с REFAGG и една refinement инстанция, описан в §6.5.8.2.2, има същото поле BMSIZE със същите последствия. В PDFlibPas горната граница за този размер е TStreamReader.SegmentEnd — краят на текущия сегмент, какъвто го настройва readSegments, не краят на целия stream, защото BMSIZE, задоволим само с вземане на байтове от следващия сегмент, е malformed, а валидирането му спрямо дължината на stream-а би позволило на аритметичния декодер да чете в следващия header. Долната граница от два байта отразява първоначалната байтова двойка, която аритметичният декодер винаги консумира, а след refinement четецът скача на RefinementEnd независимо колко напред е чел аритметичният декодер, понеже финалната му позиция не е позицията на следващото Huffman-кодирано поле

// 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 — сега се декодира до битмап с нула различаващи се пиксела спрямо независим декодер, а синтетичните фикстури с колективен битмап 7 и 9 бита дават очакваните редове и на двете. Двата независими декодера, несъгласуващи се по оригиналната проба, пак не се съгласяват помежду си; PDFlibPas пасва на единия от тях, и честното твърдение е, че нативният изход се съгласява с една независима имплементация и със спецификацията, както я четем, а не че всеки декодер по света се съгласява. Malformed страната на пакета покрива:

• резервиран flag бит или резервирана стойност на селектор
• таблица, отрязана по средата на ред
• oversubscribed дължини на префикси и префикси, по-дълги от 32 бита
• регион, чиито селектори искат повече таблици по избор, отколкото сочи
• потвърждение, че старият изход се изчиства след неуспешен decode, вместо да стои на мястото си и извикващият да го вземе за резултат

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