טבלאות Huffman מותאמות של JBIG2 במפענח PDF טהור ב-Pascal

גרסה 3.539.22 של PDFlibPas מפענחת טבלאות Huffman מותאמות של JBIG2 באופן ילידי: המפענח הטהור ב-Pascal שב-PDFlibJBIG2.pas מפרסר את מקטע ה-Tables (סוג 53), מקצה קודי prefix קנוניים לפי סדר שורות הטבלה כפי ש-ITU-T T.88 נספח B.3 דורש, צורך הפניות לטבלאות מותאמות לפי סדר ה-selectors עבור מילוני סמלים ואזורי טקסט, ותוחם כל קריאה באורך המקטע המוצהר ולא בבתים שבמקרה מגיעים אחריו

הקובץ שאילץ את העבודה הזו לא היה מיוחד על פני השטח. חוזה סרוק, דחוס ב-JBIG2 עם קידוד סמלים ב-Huffman ולא עם הקידוד האריתמטי הנפוץ בהרבה, ושה-encoder שלו שלח טבלאות קוד משלו במקום את הטבלאות התקניות B.1 עד B.15. שני מפענחים בלתי תלויים לא הסכימו על פיקסלי ה-refinement שלו, והמפענח של PDFlibPas מאותה תקופה הפיק טקסט שנראה כאילו עבר במגרסה: שברי glyphs שהוזזו בכמה פיקסלים, עמודה אחת חסרה בכל תו. שום דבר לא העלה שגיאה. זו הצורה של באג ששורד שנים, כי מפענח שדוחה קובץ מקבל פנייה לתמיכה, בעוד מפענח שמצייר אותו קצת לא נכון מקבל לקוח שמניח שהסריקה הייתה גרועה

מה מכיל בעצם מקטע Tables של JBIG2?

מקטע Tables הוא תיאור קומפקטי של טבלת Huffman אחת: בית flags אחד, שני גבולות signed של 32 סיביות, ואחריהם רצף של זוגות (אורך prefix, אורך טווח) שמחלקים את הקטע שבין הגבולות, כפי שמוגדר ב-T.88 §7.4.13 ובנספח B.2. סיבית 0 בבית ה-flags היא HTOOB והיא אומרת אם לטבלה יש קוד out-of-band. סיביות 1 עד 3 ועוד אחת נותנות את HTPS, מספר הסיביות שנכתבות בכל אורך prefix; סיביות 4 עד 6 ועוד אחת נותנות את HTRS, הרוחב של כל שדה אורך טווח. סיבית 7 שמורה, ו-PDFlibPas דוחה את המקטע אם היא דלוקה במקום לנחש מה מהדורה עתידית התכוונה בו. HTLOW ו-HTHIGH מגיעים אחר כך כמספרים שלמים signed של 32 סיביות, וזה המקום הראשון שבו מפענח יכול לטעות: קריאה שלהם כ-unsigned גורמת לטבלה שהגבול התחתון שלה שלילי — מה שהגיוני לגמרי לרוחבי סמלים בקידוד delta — להיראות כאילו היא מתחילה בארבעה מיליארד. כל שדה עובר דרך helper מקומי ReadField שבודק את הבקשה מול מיקום הסיבית שבו נגמרים נתוני המקטע לפני שהוא נוגע בקורא, כי טבלה שקוראת מעבר למקטע שלה הייתה צורכת את כותרת המקטע הבא בתור אורכי 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 מנספח B.2: שורת הטווח התחתון מתחילה ב-HTLOW פחות אחד וסופרת כלפי מטה, שורת הטווח העליון מתחילה ב-HTHIGH עם טווח קבוע של 32 סיביות, ולשורת ה-OOB האופציונלית אין ערך בכלל. PDFlibPas מסמנת אותן באורכי הטווח המיוחדים jbig2HuffmanLOW ($FFFFFFFD) ו-jbig2HuffmanOOB ($FFFFFFFE), אותה מוסכמה שחמש עשרה הטבלאות התקניות המובנות שלה משתמשות בה, כך שלולאת הפענוח לא אכפת אם טבלה באה מהמפרט או מהקובץ

למה קודי prefix חייבים להיות מוקצים לפי סדר שורות הטבלה?

כי ה-encoder אף פעם לא כותב את הקודים. מקטע Tables של JBIG2 נושא רק אורכי prefix, ושני הצדדים בונים מחדש את תבניות הסיביות עצמן לפי ההליך הקנוני בנספח B.3: ספרו כמה שורות יש בכל אורך, הקצו תחילה קודים באורך אחד, אחר כך הזיזו שמאלה והמשיכו, ובתוך אורך אחד חלקו קודים לפי סדר הופעת השורות. כל סטייה מהסדר הזה מייצרת בשקט טבלה אחרת. המפענח לא ישים לב, כי כל תבנית סיביות שהוא מייצר היא עדיין קוד prefix תקין, רק לא זה שבו השתמש ה-encoder, והפלט הוא bitmap שנראה סביר אך מורכב מהסמלים הלא נכונים

// 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 היא מיון מנייה ולא מיון השוואה מסיבה אחת: מעבר מנייה על Counts, Starts ו-Positions הוא יציב מעצם בנייתו, כך ששורות באותו אורך prefix נוחתות בתוצאה לפי סדר ההצהרה שלהן, וזה בדיוק הסדר שלפיו נספח B.3 מקצה קודים. שורות שאורך ה-prefix שלהן אפס נזרקות לפני הקצאת הקודים, כי B.3 מגדיר אותן כלא בשימוש ולא כקודים של סיבית אחת. שני שומרים יושבים באותה לולאה. בדיקת ה-oversubscription תופסת טבלה שאורכיה תובעים יותר קודים ממה שקוד prefix בעומק כזה יכול להכיל, וזה אי-שוויון Kraft מנוסח כהשוואת מספרים שלמים; בלעדיה, טבלה עוינת מייצרת קוד שמתאים לשתי שורות והמפענח בוחר את זו שהוא סורק ראשונה. תקרת 32 הסיביות קיימת כי prefix הוא Cardinal והמתאים ב-decodeInt צובר סיביות לתוכו. ‏T.88 מתיר prefixes ארוכים יותר על הנייר, PDFlibPas דוחה אותם בשמם, ולא נראה encoder אמיתי שפולט כזה. חשבון הערכים צריך את אותה זהירות כמו חשבון הקודים: THuffmanTable.val הוא Int64, ושורת הטווח התחתון מפוענחת בתור val - readBits(32), היסט unsigned של 32 סיביות שנגרע מ-HTLOW פחות אחד. עם משתני ביניים מסוג Integer החיסור הזה גולש, והערך הגולש מתקבל אחר כך בתור רוחב סמל. המסלול של 64 סיביות מחשב את הערך האמיתי, בודק אותו מול הטווח ה-signed של 32 סיביות, ומעלה חריגה אם הוא לא נכנס בו, וכך הופך השחתה שקטה לסירוב מפורש

למה טבלאות מותאמות אף פעם לא הופעלו לפני 3.539.22?

שני פגמים הסתירו זה את זה. הראשון היה באג של שורה אחת ב-setter: TTextRegionHuffmanFlags.setFlags קיבל את הארגומנט שלו תחת אותו שם כמו השדה שאליו הוא מאחסן, כך ש-Self.flagsAsInt := flagsAsInt השמה את השדה הלא מאותחל לעצמו וכל selector נקרא חזרה כאפס, מה ששלח אזורי טקסט שביקשו טבלאות מותאמות דרך הטבלאות התקניות F, H ו-K במקום. הפגם השני הבטיח שתיקון הראשון לבדו היה עדיין מייצר סמלים פגומים. כשמילון סמלים ב-Huffman מאחסן את הסמלים שלו כ-collective bitmap לא דחוס, הבית האחרון בכל שורה הוא חלקי, ולולאת ההעתקה הישנה התייחסה ל-padding, שמחזיק את מספר הסיביות התקינות, כאל מיקום הסיבית התקינה הנמוכה; שורה ברוחב 63 פיקסלים העתיקה סיבית אחת מהבית האחרון שלה במקום שבע. הלולאה המתוקנת רצה for bitPointer := 7 downto ((8 - padding) and 7), וקובצי בדיקה סינתטיים ברוחב 7 ו-9 סיביות מקבעים את שני צדי גבול הבית. כשה-selectors נקראים נכון, הטבלאות מחולקות לפי הסדר שבו המפרט מפרט אותן, ש-T.88 §7.4.3.1.2 קובע לאזורי טקסט כ-FS, DS, DT, RDW, RDH, RDX, RDY ו-RSIZE ו-§7.4.2.1.1 קובע למילוני סמלים כ-DH, DW, BMSIZE ו-AGGINST. כל selector בן שתי סיביות משמעו טבלה תקנית 0 או 1, reserved עבור 2 בשדות שיש להם רק שתי טבלאות תקניות, ו-custom עבור 3, וכל בחירה מותאמת צורכת את מקטע ה-Tables הבא מבין המקטעים המופנים לפי סדר ההפניה. NextCustomHuffmanTable עושה בדיוק את המעבר הזה ומעלה missing custom Huffman table reference כשאזור מפנה לפחות טבלאות ממה שה-selectors שלו דורשים. עוד שורה אחת שייכת לאותו תיקון: מילון סמלים ב-Huffman שסמלי הקלט והחדשים שלו מסתכמים לאחד מחשב אורך קוד סמל של אפס מנוסחת ה-log2, בעוד הגרסה של הפורמט עם Huffman כותבת כל מזהה סמל עם סיבית אחת לפחות, ולכן if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 ב-TSymbolDictionarySegment מונע מנתיב ה-refinement וה-aggregate לקרוא אפס סיביות לכל מזהה סמל

מה מבטיח גבול המקטע?

PDFlibPas מתייחסת לאורך נתוני המקטע בכל כותרת כאל חוזה ששני הכיוונים חייבים לכבד: מקטע לא רשאי לקרוא מעבר לסוף המוצהר שלו, והוא לא רשאי להסתיים קצר ולהשאיר את הכותרת הבאה במיקום בלתי צפוי. הכללים שנובעים מהחוזה הזה קטנים כל אחד בנפרד. אורך נתונים שסיבית 31 דלוקה בו הוא סמן האורך הלא ידוע של T.88 §7.2.7, ו-handleSegmentDataLength ממפה אותו לערך שלילי ש-readSegments דוחה אותו כליל במקום לסרוק קדימה אחרי terminator. כל מספר מקטע מופנה חייב להיות קטן ממספר המקטע הנוכחי וחייב כבר להתקיים, כך שהפניה קדימה או תלויה נכשלת לפני שמישהו מנסה לפענח אותה. 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 יודע שהוא סיים כשהפיקסל האחרון של השורה האחרונה נוצר, וזה יכול לקרות לפני שהוא צרך את ה-terminator EOFB ש-T.88 §6.2.5.7 מציב בסוף הנתונים. הקוד הישן הניח שהקורא עומד בכותרת הבאה, כך שבתי ה-terminator שנותרו פוענחו כמספר מקטע והזרם נכשל כמה בתים אחר כך עם שגיאה מטעה. כעת הסוף המוצהר מנצח: קריאה מעבר לו היא שגיאה, עצירה לפניו היא נורמלית, והקורא מועבר ל-DataEnd עם איפוס מצביע הסיביות כך שהכותרת הבאה נקראת מהמקום שהקובץ אמר שהיא תהיה בו. אותה משמעת מופיעה בכל מקום שבו PDFlibPas מפרסרת מבני PDF לא מהימנים: האורך המוצהר הוא הגבול, והמפענח לא יוצא לחפש גבול נוח יותר

מהיכן קורא ה-refinement ב-Huffman את גודל ה-bitmap שלו?

לפני שהמפענח האריתמטי מתחיל, ומשדה שקיים רק במצב Huffman. כשמופע של אזור טקסט נושא refinement (‏RI אינו אפס) ו-SBHUFF דלוק, T.88 §6.4.11 קובע שהמפענח יקרא את RDW, RDH, RDX ו-RDY עם הטבלאות הנבחרות שלהם, אחר כך את BMSIZE עם טבלת RSIZE, אחר כך יתיישר לגבול בית, ורק אז יריץ את פענוח ה-refinement הגנרי על בדיוק BMSIZE בתים. לאזורי טקסט במצב אריתמטי אין שדה כזה, ומפענח שחולק נתיב קוד אחד לשני המצבים ידלג עליו, יתחיל את המפענח האריתמטי שני בתים או יותר מוקדם, ויבצע refinement לכל סמל מול זבל. לנתיב מילון הסמלים עם REFAGG ומופע refinement בודד, המתואר ב-§6.5.8.2.2, יש את אותו שדה BMSIZE עם אותן השלכות. ב-PDFlibPas הגבול העליון של הגודל הזה הוא TStreamReader.SegmentEnd, סוף המקטע הנוכחי כפי שנקבע ב-readSegments, ולא סוף הזרם כולו, כי BMSIZE שאפשר לספק רק על ידי שאילת בתים מהמקטע הבא הוא פגום, ואימות שלו מול אורך הזרם היה מאפשר למפענח האריתמטי לקרוא לתוך הכותרת הבאה. הגבול התחתון של שני בתים משקף את זוג הבתים הראשוני שהמפענח האריתמטי תמיד צורך, ואחרי ה-refinement הקורא קופץ ל-RefinementEnd בלי קשר לכמה רחוק קרא המפענח האריתמטי קדימה, כי המיקום הסופי שלו אינו המיקום של השדה הבא המקודד ב-Huffman

// פענוח אזור טקסט ב-TJBIG2Bitmap, נתיב ה-refinement ב-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 פיקסלים עם טבלאות מותאמות ו-refinement ב-Huffman, מפוענחת כעת ל-bitmap עם אפס פיקסלים שונים מול מפענח בלתי תלוי, וקובצי הבדיקה הסינתטיים של collective bitmap ברוחב 7 ו-9 סיביות מפיקים את השורות הצפויות בשניהם. שני המפענחים הבלתי תלויים שלא הסכימו על הדוגמה המקורית עדיין לא מסכימים זה עם זה; PDFlibPas תואמת לאחד מהם, והאמירה הכנה היא שהפלט הילידי תואם למימוש בלתי תלוי אחד ולמפרט כפי שנקרא, ולא שכל מפענח בעולם מסכים. הצד הפגום של מערך הבדיקות מכסה:

• סיבית flags שמורה או ערך selector שמור
• טבלה שנחתכה באמצע שורה
• אורכי prefix עם oversubscription ו-prefixes ארוכים מ-32 סיביות
• אזור שה-selectors שלו מבקשים יותר טבלאות מותאמות ממה שהוא מפנה אליהן
• אימות שפלט מיושן מנוקה אחרי פענוח שנכשל ולא נשאר במקום כדי שהקורא יחשוב בטעות שזו תוצאה

שלוש מגבלות נשארות מכוונות. ארגון זרם בגישה אקראית, שבו כל כותרות המקטעים קודמות לכל נתוני המקטעים, מעלה JBIG2 random-access organisation is not supported ברגע שקוראים את דגלי כותרת הקובץ, כי אין דוגמה מייצגת לאמת מולה ומסלול חצי-מיושם גרוע מסירוב בשם מפורש. טבלאות מותאמות מוגבלות ל-65,536 שורות ול-prefixes של 32 סיביות. ונקודת הכניסה הציבורית לפענוח, TPLJBIG2Decoder.LoadFromByteArray, מחזירה את ה-bitmap של העמוד הראשון לפי סדר הזרם דרך getPageAsJBIG2Bitmap(0), מקטע מידע העמוד הראשון שנפגש, ולא מחפשת את שיוך העמוד אפס; זרמי PDF מוטמעים ממספרים את העמוד היחיד שלהם כ-1 כדבר שבשגרה, ובקשה לעמוד 0 לפי שיוך לא תמצא דבר. טקסט הכשל נוחת ב-TPLJBIG2Decoder.LastError, האבחון הפנימי של המפענח שנושא את מספר המקטע, סוגו והיסט הבתים של התקלה, ואינו אותו דבר כמו TPDFlib.LastErrorCode ברמת הספרייה. שום דבר מזה לא נוגע בצד הקידוד, שמכוסה בהערות על ה-backends של ה-encoder של JBIG2 ואיך הם מקושרים; נתיב הקריאה חייב לקבל כל מה שה-encoder של מישהו אחר החליט לפלוט, והוא חולק את הכללים שלו עם שאר מחסנית התמונות, כולל מפענח ה-TIFF המובנה והסירובים שלו ל-BigTIFF ולפריסת אריחים: לסרב בשם מפורש, לא לשאול בתים מעבר לגבול מוצהר, ולשמור על רוחב אריתמטי מספיק כדי שערך ביניים שגלש לא יעבור בתור תשובה תקינה. אם אתם בוחנים נתיב קריאה ילידי ל-JBIG2 עבור Delphi או C++Builder, המפענח ושאר הטיפול בתמונות מתועדים בעמוד PDF Library for Delphi