אינדקס אובייקטים דליל ועצל ב־PDF ב־Delphi עם PDFiumPas

אתם רוצים מילון אחד מתוך PDF של 2 GB והכלי קודם מרחיב את כל טבלת ההפניות הצולבות למערך בגודל שנקבע לפי ה־/Size של ה־trailer. PDFiumPas מחליף את הצעד הזה באינדקס אובייקטים דליל ועצל: הוא שומר רק את מתארי מקטעי ה־xref, פותר מספר אובייקט בודד לפי דרישה דרך חלונות חסומים, ומטמין רק את הרשומות שבאמת נגעתם בהן

הצורה הישנה של הקוד הזה ב־FPdfCompress הייתה ישרה אבל יקרה. ApplyDefaultOpenAction קרא את הקובץ המלא לתוך TBytes אחד, ואז הקצה מערך TPdfActiveXrefEntries צפוף עם משבצת אחת לכל מספר אובייקט עד /Size. שני דברים השתבשו בקנה מידה גדול. עלות הקריאה צמחה ליניארית עם גודל המסמך גם כשהמתקשר רצה ארבעה מילונים, והמערך הצפוף התנגש עם תקציב המנתח: TPdfParserResourceBudget.Default קובע את MaxObjects ל־4,000,000, ולכן קובץ תקף לחלוטין שמספר האובייקט הגבוה ביותר שלו יושב מעל התקרה הזאת נדחה על טיעון של זיכרון ולא של נכונות

למה ה־API הציבורי של PDFium לא עונה על השאלה הזאת?

כי המידע קיים בתוך PDFium אבל לעולם לא חוצה את גבול ה־C. CPDF_Parser מתחזק בפנים את טבלת ההפניות הצולבות, את החברות בזרמי האובייקטים ואת קדימות התיקונים, אך הכותרות המפורסמות לא חושפות נקודת כניסה שמקבלת מספר אובייקט ומחזירה את היסט הבתים הגולמי שלו, את הדור שלו, איזה תיקון ניצח, או באיזה ObjStm הוא חי. צד השמירה סגור באותה מידה: FPDF_SaveAsCopy ו־FPDF_SaveWithVersion נותנים לכם רק callback של כתיבה סדרתית. לכן כל תיקון ברמת בתים לקטלוג אחרי שמירה טבעית חייב להיבנה בשכבת ה־Pascal, וזו הסיבה ש־PDFiumPas מנתח את המבנים האלה בעצמו במקום לעשות שימוש חוזר ב־DLL

מה האינדקס הדליל באמת מחזיק בזיכרון?

מתארים, לא רשומות. לטבלה קלאסית (ISO 32000-1 §7.5.4) TPdfSparseXrefSubsection מאחסן את מספר האובייקט הראשון, את מספר האובייקטים, את היסט הבתים שבו מתחילות שורות הרשומות ואת רוחב הרשומה הנמדד. הרשומות עצמן נשארות בקובץ. הרוחב נמדד מהשורה הראשונה במקום להניח שהוא 20 בתים, כי המפיקים חלוקים לגבי סימני סוף שורה; PDFiumPas מקבל 18 עד 64 ודוחה כל דבר מחוץ לטווח הזה, וכן כל תת־מקטע שהמספר המוכרז שלו ירוץ מעבר לסוף הזרם. לזרם הפניות צולבות (§7.5.8) המקטע מחזיק את שלושת רוחבי השדות של ה־/W, כל אחד מוגבל ל־0 עד 8, את זוגות ה־/Index השטוחים, ואת בתי הרשומות המפוענחים, שאורכם הצפוי מחושב מתוך /W ו־/Index לפני שבית בודד מנופח

כל האינדקס נבנה על ידי Initialize מחלון זנב של 1 MiB לכל היותר, שבו נמצא ה־startxref, וכל קריאת אובייקט שאחריו משתמשת בחלון אובייקטים של 1 MiB. התקרה של זרם גולמי היא 64 MiB ושורת xref בודדת לא תעלה על 1024 בתים. אם קראתם את ההערה שלנו על אימות זרמי אובייקטים והפניות צולבות עם PDFiumPas, אותו משמעת של רוחבי שדות חלה כאן, רק שעכשיו היא משמשת למיעון רשומה אחת במקום לביקורת של טבלה שלמה

uses
  FPdfCompress;

var
  Source: TFileStream;
  Revision: TPdfSparseRevisionInfo;
begin
  Source := TFileStream.Create(FileName, fmOpenRead or fmShareDenyWrite);
  try
    { עובר על startxref, שרשרת ה־/Prev והקטלוג בלבד }
    if ReadPdfSparseRevisionInfo(Source, Revision) then
    begin
      Writeln('root      ', Revision.RootObjectNumber, ' ',
        Revision.RootGeneration);
      Writeln('max obj   ', Revision.MaximumObjectNumber);
      Writeln('xref str  ', Revision.UsesXrefStream);
      Writeln('encrypted ', Revision.HasEncrypt);
      Writeln(string(Revision.CatalogDictionary));
    end;
  finally
    Source.Free;
  end;
end;

איך חיפוש אחד מגיע לאובייקט אחד?

באריתמטיקה, בשני הפריסות. לתת־מקטע קלאסי יש שורות ברוחב קבוע, ולכן כתובת רשומה היא תחילת תת־המקטע ועוד היסט האובייקט כפול הרוחב הנמדד; PDFiumPas קורא אז את השורה האחת הזאת, מפענח את ההיסט בן עשר הספרות ואת הדור בן חמש הספרות, בודק את הדור מול תקרת 65535 מתוך §7.5.4, ומסווג את מילת המפתח הסוגרת כ־axkDirect או axkFree. זרם הפניות צולבות זקוק לצעד נוסף אחר שתתי־המקטעים של /Index משורשרים ברצף הבתים המפוענח, ולכן האינדקס מצבר את ספירות תתי־המקטעים שקדמו לפני הכפלה ברוחב ה־/W המסוכם. סוג 1 מניב היסט, סוג 2 מניב מספר זרם אובייקטים ואינדקס חבר, וכל דבר אחר הופך ל־axkUnknown במקום ניחוש

{ טבלה קלאסית, ISO 32000-1 סעיף 7.5.4 }
EntryOffset := Subsection.EntryOffset +
  Int64(ObjectNumber - Subsection.FirstObject) * Subsection.EntryWidth;

{ זרם הפניות צולבות, ISO 32000-1 סעיף 7.5.8 }
EntryWidth := Section.Widths[0] + Section.Widths[1] + Section.Widths[2];
EntryPosition := Integer((PriorCount + ObjectNumber -
  Section.IndexValues[I]) * EntryWidth);

שום דבר באף אחד מהנתיבים אינו פרופורציונלי ל־/Size. זו כל המטרה של הכתיבה מחדש: ערך גודל ה־trailer מועבר הלאה כמטא־דאטה ומשמש בכתיבת התיקון המצטבר, אבל הוא לעולם לא מניע הקצאה. ערכת הרגרסיה מקובעת על זה באמצעות מבחן שעץ העמודים שלו יושב באובייקטים 1,000,000,000 ו־1,000,000,001 תחת trailer שמכריז על /Size 1000000002. המימוש הצפוף הישן דחה את הקובץ הזה; האינדקס הדליל פותר את שתי ההפניות ושומר על הגודל המוכרז ב־trailer של הפלט

תיקונים היברידיים, שרשרות /Prev והשומרים סביבם

קדימות התיקונים היא המקום שבו אינדקס עצל נאיבי טועה. PDFiumPas הולך על השרשרת מ־startxref בסדר חדש־ביותר תחילה ועוצר חיפוש במקטע הראשון שעונה, מה שמשחזר את כלל הקדימות בלי להגשים טבלה ממוזגת. קבצי הפניה היברידיים (§7.5.8.4) מטופלים בתוך הענף הקלאסי: כשה־trailer נושא /XRefStm, מקטע הזרם המשלים נרשם לפני המקטע הקלאסי שהפנה אליו, כך שאובייקטים דחוסים בלתי־נראים לטבלה הפשוטה עדיין נמצאים בזמן שהרשומות הקלאסיות שומרות על מעמדן. תיקונים ישנים יותר נעקבים אחר כך דרך /Prev

שני שומרים תוחמים את ההליכה הזאת, ושניהם חשובים בקבצים פגומים. כל היסט שנבקר נרשם, כך ש־/Prev שמצביע בחזרה לתוך השרשרת מסתיים במקום להסתחרר, ועומק המעבר מוגבל על ידי MaxRecursionDepth, שברירת המחדל שלו 1024. דגל ההצפנה מצטבר על פני השרשרת כולה במקום להיקרא מה־trailer החדש בלבד, כי מסמך שה־trailer האחרון שלו משמיט /Encrypt עדיין יכול להיות מוצפן בהמשך אחורה; מתקשרים שמצרפים תיקונים מסתמכים על הדגל הזה כדי לסרב לכתוב אובייקטי טקסט רגיל לקובץ מוצפן

רשומות סוג 2: למה זרם האובייקטים ממתין

רשומת סוג 2 מציינת זרם אובייקטים, ו־PDFiumPas לא נוגע בזרם הזה עד שמתקשר מבקש חבר מתוכו. כשזה קורה סוף סוף, /Type /ObjStm נבדק, /N נבדק מול תקציב האובייקטים ו־/First מול תקרת הבתים המפוענחים, ו־/N עובר בדיקת היגיון מול /First כי לכל זוג כותרת דרושים לפחות ארבעה בתים. רק אז הזרם מתנפח, וסריקת הכותרת נעצרת בחבר המבוקש ובעוקב שלו במקום לבנות טבלת חברים מלאה. זרם אובייקטים מפוענח אחד נשמר בכל רגע, וזו התמורה הנכונה כשענף של עץ עמודים מתקבץ ל־ObjStm יחיד; הסקירה שלנו על פענוח זרמי אובייקטים ומנבאים ב־Delphi מכסה מה קורה בתוך צעד הניפוח הזה (§7.5.7)

var
  Reader: TPdfSparseDictionaryReader;
  Generation: Integer;
  Dict: AnsiString;
begin
  { אינדקס שמור אחד, קריאות מודעות־דור רבות }
  Reader := TPdfSparseDictionaryReader.Create(Source);
  try
    if Reader.Valid and
       Reader.ReadLatestDictionary(PageObjectNumber, Generation, Dict) then
      HandlePage(PageObjectNumber, Generation, Dict);
  finally
    Reader.Free;  { המקור נשאר שלכם }
  end;
end;

היכן המטמון מפסיק להבטיח

האינדקס הוא תמונת מצב, ושווה להיות בלתי מתפשרים לגבי זה. המקטעים מנותחים פעם אחת ב־Initialize; אם הזרם הבסיסי מוסב אחר כך, כל רשומה מטמונית מתיישנת והמחלקה לא תשים לב. TPdfSparseDictionaryReader מחזיק את האינדקס לכל אורך חיי המקור שבבעלות המתקשר, וזה בדיוק מה שהליכה רקורסיבית על עץ עמודים רוצה ובדיוק מה שאסור לעשות דרך כתיבה מחדש. מטמון הרשומות הוא מערך שטוח שנסרק ליניארית והוא מאחסן גם תוצאות שליליות, כך שכמה מאות חיפושים זולים וכמה מאות אלפים לא. ReadDictionary דורש התאמת דור מדויקת בזמן ש־ReadLatestDictionary פותר את הפעיל, וההבדל מכוון: פתרון הפניות זקוק לראשון, בדיקת קטלוג זקוקה לשני. היכן שאין אפשרות לקיים את התחומים האלה, היחידות הסובבות חוזרות למנתח הקובץ המלא המורשת במקום לצמצם את מערך הקבצים שעדיין עובדים, תבנית שאנו משתמשים בה גם עבור הזרמת PDFs גדולים לפי דרישה

רגרסיות חוצות־מהדר מכסות את אותה התנהגות בשלוש שרשרות הכלים כולן, כולל טענה שמקור של 2 MiB לעולם לא רואה קריאה בודדת גדולה מ־1 MiB. אם אתם מתחזקים קוד Delphi, C++Builder או Lazarus שנוגע ישירות במבנה PDF ונמאס לכם לשלם עלויות ניתוח של קובץ מלא עבור ארבעה מילונים, האינדקס הדליל והתפר הציבורי סביבו מגיעים בתוך רכיב PDFiumPas ל־Delphi