جدول‌های Huffman سفارشی JBIG2 در decoder پاسکالی PDF

نسخهٔ 3.539.22 از PDFlibPas جدول‌های Huffman سفارشی JBIG2 را به‌صورت بومی decode می‌کند: decoder خالص پاسکالی در PDFlibJBIG2.pas سگمنت Tables (نوع 53) را parse می‌کند، کدهای canonical prefix را به همان ترتیبی که خطوط جدول آمده‌اند و مطابق ITU-T T.88 Annex B.3 تخصیص می‌دهد، ارجاع‌های جدول سفارشی را برای symbol dictionaryها و نواحی متنی به ترتیب selector مصرف می‌کند، و هر خواندن را با طول اعلام‌شدهٔ سگمنت کرانمند می‌کند، نه با هر byte ای که تصادفاً بعدش آمده باشد

فایلی که این کار را اجباری کرد، در ظاهر هیچ چیز خاصی نداشت. یک قرارداد اسکن‌شده، فشرده‌شده با JBIG2 و با symbol coding هافمن — نه با arithmetic coding که خیلی رایج‌تر است — و با encoderی که جدول‌های کد خودش را می‌فرستاد، نه جدول‌های استاندارد B.1 تا B.15. دو decoder مستقل روی پیکسل‌های refinement اش با هم اختلاف داشتند و decoder آن زمان PDFlibPas متنی تولید می‌کرد که انگار از دستگاه رنده رد شده: قطعه‌های glyph چند پیکسل جابه‌جا، و یک ستون از هر کاراکتر غایب. هیچ‌چیز خطا نمی‌داد. این همان شکلی از باگ است که سال‌ها زنده می‌ماند، چون decoderی که فایل را رد می‌کند یک تیکت پشتیبانی می‌گیرد، در حالی که decoderی که آن را کمی غلط رندر می‌کند مشتری‌ای می‌گیرد که فکر می‌کند اسکن بد بوده

یک سگمنت Tables در JBIG2 واقعاً چه چیزی در خود دارد؟

یک سگمنت Tables توصیف فشردهٔ یک جدول Huffman است: یک byte پرچم، دو کران 32-bit علامت‌دار، و بعد رشته‌ای از جفت‌های (طول prefix، طول range) که بازهٔ میان دو کران را افراز می‌کنند، همان‌طور که در T.88 §7.4.13 و Annex B.2 چیده شده. بیت 0 از byte پرچم همان HTOOB است و می‌گوید جدول کد out-of-band دارد یا نه. بیت‌های 1 تا 3 به‌علاوهٔ یک می‌دهند HTPS، یعنی تعداد بیت‌هایی که هر طول prefix با آن‌ها نوشته می‌شود؛ بیت‌های 4 تا 6 به‌علاوهٔ یک می‌دهند HTRS، یعنی عرض هر فیلد طول range. بیت 7 رزرو است و PDFlibPas اگر ست شده باشد سگمنت را رد می‌کند، به‌جای اینکه حدس بزند یک بازنگری آینده منظورش چه بوده. بعد HTLOW و HTHIGH به صورت اعداد صحیح 32-bit علامت‌دار می‌آیند، که همان اولین جایی است که decoder می‌تواند خطا کند: خواندنشان به‌عنوان بی‌علامت باعث می‌شود جدولی که کران پایینش منفی است — که برای عرض‌های symbol با کدگذاری delta کاملاً عادی است — به نظر برسد از چهار میلیارد شروع می‌شود. هر فیلد از یک هلپر محلی ReadField می‌گذرد که پیش از دست زدن به reader، درخواست را با موقعیت بیتی پایان دادهٔ سگمنت می‌سنجد، چون جدولی که از سگمنت خودش رد شود، هدر سگمنت بعدی را به‌جای طول‌های prefix مصرف می‌کند

// 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 با یک range ثابت 32-bit شروع می‌شود، و خط OOB اختیاری اصلاً مقداری ندارد. PDFlibPas آن‌ها را با طول‌های range نشانه‌دار jbig2HuffmanLOW ($FFFFFFFD) و jbig2HuffmanOOB ($FFFFFFFE) علامت می‌زند؛ همان قراردادی که پانزده جدول استاندارد داخلی‌اش هم به کار می‌برند، پس حلقهٔ decode اهمیتی نمی‌دهد که جدول از spec آمده یا از فایل

چرا کدهای prefix باید به ترتیب خطوط جدول تخصیص داده شوند؟

چون encoder هرگز خود کدها را نمی‌نویسد. یک سگمنت Tables در JBIG2 فقط طول‌های prefix را حمل می‌کند و هر دو طرف الگوهای بیتی واقعی را با رویهٔ canonical در Annex B.3 بازمی‌سازند: بشمار هر طول چند خط دارد، اول کدهای با طول یک را بده، بعد shift به چپ بزن و ادامه بده، و درون یک طول، کدها را به همان ترتیبی که خطوط ظاهر می‌شوند پخش کن. هر انحرافی از این ترتیب بی‌صدا یک جدول متفاوت می‌سازد. decoder متوجه نمی‌شود، چون هر الگوی بیتی که تولید می‌کند هنوز یک prefix code معتبر است، فقط همانی نیست که encoder استفاده کرده، و خروجی یک bitmap ظاهراً معقول است که از symbolهای اشتباه سرهم شده

// 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       // درون هر طول prefix
  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: یک پاس شمارشی روی Counts و Starts و Positions بنا به ساختارش پایدار است، پس خطوطی با طول prefix برابر به همان ترتیبی که اعلان شده بودند در نتیجه می‌نشینند، که دقیقاً همان ترتیبی است که Annex B.3 بر مبنایش کد تخصیص می‌دهد. خطوط با طول prefix صفر پیش از تخصیص کد حذف می‌شوند، چون B.3 آن‌ها را استفاده‌نشده تعریف می‌کند، نه کد یک-بیتی. دو نگهبان در همان حلقه نشسته‌اند. بررسی اشباع‌شدگی جدولی را می‌گیرد که طول‌هایش بیشتر از ظرفیت یک prefix code با آن عمق ادعای کد می‌کنند، که همان نامساوی Kraft است در قالب یک مقایسهٔ عدد صحیح؛ بدون آن، یک جدول خصمانه کدی تولید می‌کند که با دو خط می‌خواند و decoder هرکدام را که اول اسکن کند برمی‌دارد. سقف 32 بیت وجود دارد چون prefix یک Cardinal است و matcher در decodeInt بیت‌ها را در یکی جمع می‌کند. T.88 روی کاغذ prefixهای بلندتر را مجاز می‌داند، PDFlibPas آن‌ها را به اسم رد می‌کند، و هیچ encoder واقعی دیده نشده که یکی از آن‌ها را بفرستد. حساب مقدارها همان‌قدر دقت لازم دارد که حساب کدها: THuffmanTable.val یک Int64 است و خط range پایینی به‌صورت val - readBits(32) decode می‌شود، یعنی یک offset بی‌علامت 32-bit که از HTLOW منهای یک کم می‌شود. با متغیرهای میانی از نوع Integer آن تفریق wrap می‌خورد و مقدار wrap شده بعد به‌عنوان عرض یک symbol پذیرفته می‌شود. مسیر 64-bit مقدار واقعی را حساب می‌کند، با بازهٔ 32-bit علامت‌دار می‌سنجدش و اگر جا نشود raise می‌کند؛ و همین یک خرابی بی‌صدا را به یک رد صریح تبدیل می‌کند

چرا جدول‌های سفارشی پیش از 3.539.22 هرگز عمل نمی‌کردند؟

دو نقص یکدیگر را پنهان می‌کردند. اولی یک باگ یک-خطی در setter بود: TTextRegionHuffmanFlags.setFlags آرگومانش را با همان نامی می‌گرفت که فیلد مقصد داشت، پس Self.flagsAsInt := flagsAsInt فیلد مقداردهی‌نشده را به خودش نسبت می‌داد و هر selector صفر برمی‌گشت؛ همین نواحی متنی‌ای که جدول سفارشی می‌خواستند را به‌جایش به سراغ جدول‌های استاندارد F و H و K می‌فرستاد. نقص دوم یعنی تلاش برای fix کردن فقط اولی هم باز symbolهای خراب تولید می‌کرد. وقتی یک symbol dictionary هافمنی symbolهایش را به صورت یک collective bitmap فشردنشده ذخیره می‌کند، آخرین byte هر سطر ناقص است و حلقهٔ کپی قدیمی padding را — که تعداد بیت‌های معتبر را نگه می‌دارد — موقعیت پایین‌ترین بیت معتبر می‌گرفت؛ یک سطر 63-پیکسلی از byte آخرش یک بیت کپی می‌کرد، نه هفت بیت. حلقهٔ اصلاح‌شده به شکل for bitPointer := 7 downto ((8 - padding) and 7) اجرا می‌شود و fixtureهای مصنوعی در عرض‌های 7 و 9 بیتی هر دو طرف مرز byte را پین می‌کنند. با درست خوانده شدن selectorها، جدول‌ها به همان ترتیبی که spec فهرستشان می‌کند پخش می‌شوند؛ ترتیبی که T.88 §7.4.3.1.2 برای نواحی متنی به صورت FS و DS و DT و RDW و RDH و RDX و RDY و RSIZE و §7.4.2.1.1 برای symbol dictionaryها به صورت DH و DW و BMSIZE و AGGINST تعیین می‌کند. هر selector دو-بیتی یعنی جدول استاندارد 0 یا 1، مقدار 2 روی فیلدهایی که فقط دو جدول استاندارد دارند رزرو است، و 3 یعنی سفارشی؛ و هر انتخاب سفارشی، سگمنت Tables بعدی را به ترتیب ارجاع از میان سگمنت‌های ارجاع‌شده مصرف می‌کند. NextCustomHuffmanTable دقیقاً همین راه رفتن را انجام می‌دهد و وقتی ناحیه‌ای به تعداد کمتر از نیاز selectorهایش جدول ارجاع داده باشد missing custom Huffman table reference را raise می‌کند. یک خط دیگر هم به همین fix تعلق دارد: یک symbol dictionary هافمنی که symbolهای ورودی و جدیدش روی هم یک می‌شوند، از فرمول log2 طول کد symbol را صفر حساب می‌کند، در حالی که نسخهٔ هافمنی این فرمت هر شناسهٔ symbol را با حداقل یک بیت می‌نویسد؛ پس if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 در TSymbolDictionarySegment نمی‌گذارد مسیر refinement و aggregate صفر بیت به ازای هر شناسهٔ symbol بخواند

مرز سگمنت چه چیزی را تضمین می‌کند؟

PDFlibPas طول دادهٔ سگمنت در هر هدر را یک قرارداد می‌بیند که هر دو جهت باید رعایتش کنند: سگمنت نباید از انتهای اعلام‌شدهٔ خودش رد شود و نباید کوتاه تمام شود و هدر بعدی را روی یک offset پیش‌بینی‌ناپذیر رها کند. قواعدی که از این قرارداد بیرون می‌آیند هر یک به‌تنهایی کوچک‌اند. طول داده‌ای که بیت 31 اش ست باشد همان نشانگر طول-نامعلوم T.88 §7.2.7 است و handleSegmentDataLength آن را به یک مقدار منفی نگاشت می‌کند که readSegments همان‌جا ردش می‌کند، نه اینکه به دنبال یک terminator جلوتر را اسکن کند. هر شمارهٔ سگمنت ارجاع‌شده باید کوچک‌تر از شمارهٔ سگمنت جاری باشد و از قبل وجود داشته باشد، پس یک ارجاع رو-به-جلو یا آویزان پیش از آنکه ناحیه‌ای بخواهد resolve‌اش کند شکست می‌خورد. END_OF_PAGE و END_OF_FILE باید صفر byte داده اعلام کنند. یک سگمنت Profiles (نوع 52) یک شمارندهٔ 32-bit و بعد از آن همان تعداد شناسهٔ 32-bit و اصلاً هیچ پیکسلی حمل می‌کند، پس به‌صورت 4 به‌علاوهٔ 4 ضرب در شمارنده با طول اعلام‌شده سنجیده می‌شود، رد می‌شود، و فقط به این دلیل در فهرست سگمنت‌ها می‌ماند که سگمنت‌های بعدی هنوز بتوانند با شماره به آن ارجاع بدهند. یک شناسهٔ profile ناشناخته یک encoding ناشناخته نیست و برخورد کردن با آن به‌عنوان چنین چیزی، فایل‌هایی را رد می‌کند که کاملاً بی‌عیب decode می‌شوند

// 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;

انتهای همان حلقه جایی است که نسخهٔ قدیمی‌تر decoder روی نواحی کدشده با MMR خطا کرد. یک decoder MMR می‌داند وقتی آخرین پیکسل آخرین سطر تولید شد کارش تمام است، و این می‌تواند پیش از مصرف شدن terminator یعنی EOFB رخ بدهد که T.88 §6.2.5.7 آن را در انتهای داده می‌گذارد. کد قدیمی فرض می‌کرد reader روی هدر بعدی نشسته، پس byteهای باقی‌ماندهٔ terminator به‌عنوان شمارهٔ سگمنت parse می‌شدند و stream چند byte بعدتر با یک خطای گمراه‌کننده شکست می‌خورد. حالا انتهای اعلام‌شده برنده است: خواندن از آن رد شدن خطاست، زودتر تمام کردن عادی است، و reader با ریست شدن اشاره‌گر بیت به DataEnd منتقل می‌شود تا هدر بعدی از همان جایی خوانده شود که فایل گفته بود. همین انضباط هر جایی که PDFlibPas ساختارهای PDF غیرقابل‌اعتماد را parse می‌کند دیده می‌شود: طول اعلام‌شده همان مرز است و decoder به دنبال مرز مهربان‌تری نمی‌رود

refinement هافمن اندازهٔ bitmap خود را از کجا می‌خواند؟

پیش از آنکه arithmetic decoder شروع کند، و از فیلدی که فقط در حالت Huffman وجود دارد. وقتی یک نمونهٔ ناحیهٔ متنی refinement حمل می‌کند (یعنی RI ناصفر است) و SBHUFF ست شده باشد، T.88 §6.4.11 از decoder می‌خواهد RDW و RDH و RDX و RDY را با جدول‌های انتخاب‌شده بخواند، بعد BMSIZE را با جدول RSIZE، بعد به مرز byte تراز کند، و تنها پس از آن decode عمومی refinement را روی دقیقاً BMSIZE byte اجرا کند. نواحی متنی در حالت arithmetic چنین فیلدی ندارند و decoderی که برای هر دو حالت یک مسیر کد مشترک دارد آن را جا می‌اندازد، arithmetic decoder را دو byte یا بیشتر زودتر شروع می‌کند و هر symbol را روی garbage refine می‌کند. مسیر symbol dictionary با REFAGG و یک نمونهٔ refinement واحد، که در §6.5.8.2.2 توصیف شده، همان فیلد BMSIZE را با همان پیامدها دارد. در PDFlibPas کران بالای آن اندازه TStreamReader.SegmentEnd است، یعنی انتهای سگمنت جاری به همان صورتی که readSegments تنظیمش کرده، نه انتهای کل stream؛ چون یک BMSIZE که تنها با قرض گرفتن byte از سگمنت بعدی برآورده می‌شود بدشکل است و سنجیدنش با طول stream اجازه می‌دهد arithmetic decoder به هدر بعدی بخزد. کران پایین دو byte بازتاب همان جفت byte اولیه‌ای است که arithmetic decoder همیشه مصرف می‌کند، و بعد از refinement، reader بدون توجه به اینکه arithmetic decoder چقدر جلوتر خوانده باشد به RefinementEnd می‌پرد، چون موقعیت نهایی‌اش همان موقعیت فیلد Huffman بعدی نیست

// decode ناحیهٔ متنی TJBIG2Bitmap، مسیر 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 پیکسل با جدول‌های سفارشی و refinement هافمنی، حالا در مقایسه با یک decoder مستقل به bitmapی با صفر پیکسل متفاوت decode می‌شود، و fixtureهای مصنوعی collective bitmap در عرض 7 و 9 بیت هر دو همان سطرهای موردانتظار را تولید می‌کنند. همان دو decoder مستقلی که روی نمونهٔ اصلی اختلاف داشتند، حالا هم با هم اختلاف دارند؛ PDFlibPas با یکی از آن‌ها می‌خواند و بیان صادقانه این است که خروجی بومی با یک پیاده‌سازی مستقل و با spec آن‌طور که خوانده شده توافق دارد، نه اینکه هر decoderی در دنیا توافق دارد. سمت بدشکل سویت این‌ها را پوشش می‌دهد:

• یک بیت پرچم رزرو یا یک مقدار selector رزرو
• جدولی که وسط یک خط بریده شده
• طول‌های prefix اشباع‌شده و prefixهای بلندتر از 32 بیت
• ناحیه‌ای که selectorهایش بیشتر از جدول‌هایی که ارجاع داده، جدول سفارشی می‌خواهند
• تأیید اینکه خروجی کهنه پس از یک decode ناکام پاک می‌شود و به‌جایش رها نمی‌شود تا caller آن را اشتباهاً نتیجه بگیرد

سه محدودیت عمداً سر جای خود می‌مانند. سازمان‌دهی stream با دسترسی تصادفی، که در آن همهٔ هدرهای سگمنت پیش از همهٔ داده‌های سگمنت می‌آیند، به‌محض خواندن پرچم‌های هدر فایل JBIG2 random-access organisation is not supported را raise می‌کند، چون نمونهٔ نماینده‌ای برای اعتبارسنجی‌اش وجود ندارد و یک مسیر نیمه‌پیاده‌شده از یک رد نام‌دار بدتر است. جدول‌های سفارشی روی 65,536 خط و prefixهای 32 بیتی سقف دارند. و ورودی عمومی decode، یعنی TPLJBIG2Decoder.LoadFromByteArray، اولین bitmap صفحه به ترتیب stream را از طریق getPageAsJBIG2Bitmap(0) برمی‌گرداند — همان اولین سگمنت page-information که به آن می‌رسد — نه با جستجوی association صفر؛ streamهای جاسازی‌شده در PDF روتین صفحهٔ تک‌شان را 1 می‌شمارند و پرسیدن صفحهٔ 0 با association هیچ چیزی پیدا نمی‌کند. متن شکست در TPLJBIG2Decoder.LastError می‌نشیند، همان عیب‌یاب داخلی decoder که شمارهٔ سگمنت و نوع و byte offset نقص را حمل می‌کند و با TPDFlib.LastErrorCode که سطح کتابخانه است یکی نیست. هیچ‌کدام از این‌ها به سمت encode دست نمی‌زند، که در یادداشت‌های بک‌اندهای encoder مربوط به JBIG2 و نحوهٔ لینک شدنشان پوشش داده شده؛ مسیر خواندن باید هر چیزی را که encoder شخص دیگری انتخاب کرده بپذیرد و قواعدش را با بقیهٔ پشتهٔ تصویر شریک است، از جمله decoder داخلی TIFF و رد کردن‌هایش برای BigTIFF و چیدمان tiled: به اسم رد کن، هرگز از یک مرز اعلام‌شده byte قرض نگیر، و حساب را به‌قدر کافی عریض نگه دار تا یک مقدار میانی wrap‌شده نتواند از یک پاسخ معتبر جا بزند. اگر دارید یک مسیر خواندن بومی JBIG2 را برای Delphi یا C++Builder ارزیابی می‌کنید، decoder و بقیهٔ بخش تصویر روی صفحهٔ PDF Library for Delphi مستند شده است