מיזוג PDF מהיר ב-Delphi: הזזת הפניות עקיפות ברמת הבייט

שרשור קובצי PDF נשמע כאילו אמור להיות זול. תוכן העמוד כבר מונח, הגופנים כבר מוטמעים, התמונות כבר דחוסות. עקרונית, מיזוג הוא רק ניהול רישומים: ממספרים מחדש את האובייקטים כדי שמרחבי המספור של שני קבצים לא יתנגשו, מחברים את עצי הדפים, מתקנים את טבלת ה-cross-reference, וכותבים. בפועל, רוב קוד המיזוג זורק את הזולות הזו לפח. עבור כל אובייקט בכל קובץ קלט הוא מבצע ניתוח מלא לעץ אובייקטים מטוקננים, משנה כמה הפניות עקיפות, ואז מסיריאל מחדש את העץ לבייטים. הניתוח והסריאליזציה מחדש הם החלקים היקרים, ולרוב המוחלט של האובייקטים הם מייצרים רצף בייטים שכמעט זהה למה שנכנס

PDFlibPas הוא מנוע PDF מקורי ב-Object Pascal עבור Delphi ו-C++Builder, ומסלול המיזוג המהיר שלו קיים כדי לדלג על הנסיעה הלוך ושוב הזו בכל מקום שבו אפשר להוכיח שזה בטוח. הרעיון ממוקד, אבל התועלת שלו מורגשת על פני קבוצות מסמכים שלמות: עבור אובייקט שאינו משתנה ואינו stream, לוקחים את בייטי המקור המקוריים כפי שהם ומבצעים שכתוב יחיד ברמת הבייט של ההפניות העקיפות שבתוכם, כך שכל N G R הופך ל-(N+Offset) G R. בלי tokenizer, בלי עץ אובייקטים, בלי serializer. המאמר הזה עובר על המקומות שבהם קיצור הדרך הזה חוקי, על מכונת המצבים של המנתח שמבצעת את שכתוב הבייטים בלי לפגוע בשום דבר, על הסיבה לכך שמיזוג סימניות נזקק למנגנון אחר לגמרי, ועל האופן שבו מסלול המיזוג הרגיל נבנה מחדש ממסלול ריבועי לליניארי באותו זמן

למה מספור מחדש של אובייקטים הוא העלות האמיתית של מיזוג

לכל PDF יש מרחב מספור אובייקטים משלו. לקובץ A יש אובייקט 1, אובייקט 2 וכן הלאה, ולקובץ B יש את אובייקט 1, אובייקט 2 וכן הלאה. אי אפשר להכניס את האובייקטים של B לתוך קובץ A בלי שינוי, כי המספרים יתנגשו וכל הפניה עקיפה בתוך B תצביע פתאום על אובייקט שגוי. הפתרון הוא היסט: אם A מסתיים בכמות אובייקטים Offset, אז האובייקט N של B הופך ל-N+Offset בפלט, וכל הפניה N G R שמופיעה אי שם בתוך האובייקטים של B חייבת לזוז ל-(N+Offset) G R כדי להתאים

ההזזה הזו היא כל העבודה הסמנטית של מיזוג גוף המסמך. התיקונים של עץ הדפים ומיזוג AcroForm הם עריכות קטנות ומוגבלות על קומץ אובייקטים. עיקר העבודה הוא שכתוב הפניות לאורך אלפי אובייקטים, והדרך הנאיבית לעשות זאת היא לנתח כל אובייקט כדי למצוא את ההפניות בצורה מבנית. MergeFileListFast של PDFlibPas בוחר מבט הפוך: אפשר לאתר את ההפניות גם בבייטים הגולמיים, אם נזהרים מההקשרים שבהם רצף של ספרה-רווח-ספרה-רווח-R הוא לא הפניה. מדלגים על הניתוח, מזיזים במקום, והעלות לכל אובייקט קורסת לסריקה ליניארית יחידה של הבייטים שבכל מקרה עמדתם להעתיק

מתי בטוח מבחינה פורמלית להשתמש מחדש בבייטי המקור

מסלול הבייטים נבחר רק כאשר שלושה תנאים מתקיימים יחד עבור האובייקט שמועתק מתוך מסמך עוקב. אם אחד מהם נכשל, האובייקט חוזר למסלול המלא של פענוח וסריאליזציה מחדש, כך שהדיוק תמיד גובר על המהירות

• Doc2.IsChangedObject(X) מחזיר False. אם מנוע המיזוג כבר שינה את האובייקט בזיכרון, למשל אובייקט עמוד שה-/Parent שלו הופנה מחדש, עץ הזיכרון הוא מקור האמת והבייטים המקוריים כבר לא עדכניים. רק אובייקטים שלא נגעו בהם כשירים
• בבייטי המקור אין מילה stream. הגוף של אובייקט stream הוא בינארי אטום שממוסגר על ידי stream/endstream, וסריקה נאיבית של נתוני stream דחוסים או מוצפנים היתה "מוצאת" בשמחה דפוסי בייטים שנראים כמו הפניות ומקלקלת אותם. אובייקטי stream נשארים במסלול המקורי שמודע ל-stream
• בבייטי המקור אין לא /StructTreeRoot ולא /StructElem. בפרופיל המהיר עץ המבנה של tagged-PDF נזרק במקום להיות ממוזג, ולכן האובייקטים האלה חייבים לעבור דרך מסלול הפענוח, שם המנוע יכול לאפס אותם במכוון

ההחלטה חיה בלולאת ההעתקה לכל אובייקט. כאשר כל שלוש הבדיקות עוברות, הבייטים של האובייקט עוברים ישר ל-ShiftIndRefsInSource ומשם לכותב; אחרת הבייטים נזרקים והאובייקט נבנה מחדש עם GetObject, מוזז עם ShiftIndRef, ונכתב מחדש. המבנה של הענף הזה שווה לראות, כי סדר הבדיקות הוא מה ששומר עליו בטוח

ObjectData := '';
if not Doc2.IsChangedObject(X) then
begin
  ObjectData := FastMergeObjectSource(Reader2, X);
  if (PLPos('stream', ObjectData) > 0) or
     ((not PreserveStructTree) and (PLPos('/StructTreeRoot', ObjectData) > 0)) or
     ((not PreserveStructTree) and (PLPos('/StructElem', ObjectData) > 0)) then
    ObjectData := ''                                  // fall back to decode
  else
    ObjectData := ShiftIndRefsInSource(ObjectData, Offset);
end;

if ObjectData <> '' then
  Writer.AddObject(X + Offset, Doc2.GetGenNum(X), ObjectData)
else
begin
  Obj := Doc2.GetObject(X, TempStruct);              // full parse path
  // ... null out struct-tree objects, ShiftIndRef, Obj.Output ...
end;

ריק ObjectData הוא האות שמסלול הבייטים דחה את האובייקט. הסמן היחיד הזה שומר על כך שהמסלולים המהיר והאיטי לא יסטו זה מזה: יש בדיוק מקום אחד שמחליט, ובדיוק מסלול גיבוי אחד

מכונת המצבים להזזת הפניות והמקרים הקיצוניים שלה

שכתוב בייטים של הפניות עקיפות הוא דבר שקל באופן מטעה לעשות בו טעות, כי R ורצפים של ספרות מופיעים בכל רחבי אובייקט PDF בהקשרים שאינם הפניות. ShiftIndRefsInSource הוא סורק קטן שנכתב ביד, שסורק את הבייטים פעם אחת ומזיז מספר רק כשהוא מלווה, עם רווחי PDF בין הטוקנים, במספר נוסף ואז בתוחם R. היציאות הזולות מגיעות קודם: אם ה-offset הוא אפס או שהמקור ריק, הבייטים מוחזרים ללא שינוי בלי להיכנס לסורק בכלל

הדיוק של הסורק נשען על זיהוי ההקשרים שבהם רצף שנראה כמו הפניה חייב להישאר במקומו. אלה הגבולות שהכי קל לפספס, וכל אחד מהם מטופל במפורש

• מחרוזות ליטרליות שמוגדרות בין ( ל-) מועתקות כפי שהן, תוך מעקב אחרי עומק קינון ותוך כיבוד רצף ההברחה עם backslash, כך שסוגר מבריח לא יטלטל את מונה העומק. מחרוזת כמו (see object 3 0 R for details) מכילה דפוס הפניה קלאסי, אבל בפועל זו רק פרוזה, והיא חייבת להישמר בייט לבייט
• מחרוזות הקסדצימליות שמוגדרות בין < ל-> עוברות ללא פרשנות. הבייטים 52 בתוך מחרוזת hex הם קוד ASCII של R, וסורק שהיה מתייחס לנתוני hex כטקסט היה יכול להמציא הפניה רפאים. הפתיחה << של מילון מזוהה קודם, כדי שמילון לא יתבלבל עם מחרוזת hex
• אובייקטי שם שמתחילים ב-/ נצרכים בשלמותם, מהסלאש ועד לרווח או לתוחם הבא. בלי זה, שם כמו /R (מפתח משאב נפוץ) היה יכול להיקרא כ-R של הפניה
• הערות שמתחילות ב-% רצות עד סוף השורה ונקראות כטקסט אטום
• הבדיקה של מספר ואז R היא קשיחה. הפניה מוכרת רק כ-N רווח G רווח R, כשה-R מסתיים ברווח, בתוחם או בסוף הקלט. אם מספר הדור חסר, או שאחרי R מגיע אות, הספרות נפלטות ללא שינוי. זה מה שמגן על המספר ב-/Length 1234 ועל ארבעת המספרים של MediaBox מפני הגדלה שקטה

לב הבדיקה הקשיחה הזו כמעט זהה למשפט המפרט את המנגנון

if (P <= N) and (Source[P] = 'R') and
   ((P = N) or PLIsPdfWhite(Source[P + 1]) or PLIsPdfDelimiter(Source[P + 1])) then
  Obj1 := PLStrToIntDef(PLCopy(Source, I, E1 - I), -1);

if Obj1 >= 0 then
begin
  AppendStr(PLIntToStr(Obj1 + Offset));   // shifted object number
  AppendBytes(E1, P - E1);                 // original whitespace + generation
  AppendBytes(P, 1);                       // the 'R'
end;

רק מספר האובייקט נכתב מחדש, מספר הדור והרווחים המדויקים שהיו בין הטוקנים מועתקים כפי שהם, כך שהפלט זהה לבייטים של הקלט למעט אותו מספר בודד שהיה חייב להשתנות. הדיוק הזה הוא כל העניין, והוא מה שהופך שימוש חוזר בבייטי המקור לשקול לסריאליזציה מחדש מלאה, ולא רק לקירוב. ההתנהגות מכוסה על ידי סט ממוקד של בדיקות יחידה שמפעיל הפניות גולמיות, הפניות בתוך מערכים, מספרים שאינם הפניות, מחרוזות ליטרליות, מחרוזות hex, ומספרי דור שאינם אפס עם היסט מוחל

למה סימניות לא יכלו להשתמש שוב ב-AppendOutline

מיזוג סימניות של כמה מסמכים לעץ outline אחד נראה כמו עבודה עבור העוזר הקיים AppendOutline, שכבר יודע לחבר סימניות ברמת-העל של מסמך אחד אל מסמך אחר. אבל זה הכלי הלא נכון כאן, והסיבה היא אי-התאמה עדינה בין שכבות. AppendOutline מאתר את סימנית-העל האחרונה הנוכחית על ידי מעבר של הקורא על בייטי הקובץ המקוריים. אבל מסלול המיזוג המהיר מבצע את העריכות שלו בתוך מאגר של אובייקטים חדשים דרך ChangeObject, והקורא לעולם לא רואה את העריכות האלה. מחברים שלושה מסמכים או יותר, וכל הוספה כזו מפנה מחדש את הסימנית האחרונה המקורית של המסמך הראשון אל המסמך החדש ביותר, כך שכל הסימניות של המסמכים שבאמצע נושרות מהשרשרת, ורק /Count המצטבר נשאר נכון, מה שהופך את הבאג לקל להחמיץ עד שמישהו פותח את חלונית הסימניות

המסלול המהיר פותר את זה עם הזרקה דו-שלבית מבוססת-מטא-דאטה, שלא חוזרת לעולם על מעבר בקורא. מעבר ראשון על כל הקלטים אוסף, לכל מסמך, את אובייקט ה-root של ה-outline ואת מספרי הדור, את מספרי הסימניות הראשונה והאחרונה ברמת-העל, ואת /Count של ה-root. מתוך הסיכום הזה הקוד מחשב את מספרי האובייקט הגלובליים של כל קישור שהוא צריך ליצור, /Parent ברמת-העל של כל מסמך אל ה-root המשותף, /Prev של הסימנית הראשונה אל האחרונה של המסמך הקודם, /Next של הסימנית האחרונה אל הראשונה של המסמך הבא, הכל באמצעות אריתמטיקה של מספרי אובייקט בלבד. מאחורי זה מסתתר אילוץ סדר כתיבה: האובייקטים של המסמך הראשון נכתבים לפני שאפילו נפתח המסמך הבא, ולכן כל עריכות ה-outline של המסמך הראשון, /Count ו-/Last של ה-root, ו-/Next של הסימנית האחרונה הישנה, חייבות להיות ניתנות לביטוי כאריתמטיקה שלא צריכה את המסמך הבא בהישג יד. העריכות של כל מסמך עוקב מיושמות במקומן אחרי פתיחתו אבל לפני הכתיבה, כך שהן עוברות דרך אותו מסלול change-object

אינווריאנט יישור ה-Offset שמחבר הכול

גם הזזת ההפניות וגם ההזרקה של הסימניות תלויות באינווריאנט אריתמטי אחד, וזה ההנחה השברירית ביותר בכל התכנון. הפניה שמוזרקת למסמך עוקב נכתבת כ-מספר האובייקט הגלובלי היעד פחות ה-Offset של אותו מסמך, כך שכאשר האובייקט מוזז מאוחר יותר על ידי ShiftIndRef(Offset) הערך נוחת על המספר הגלובלי הרצוי. המסמך הראשון מקבל Offset = 0 ומשתמש במספרים גלובליים ישירות. כדי שהחיסור הזה יהיה נכון, רצף ה-offset-ים שרץ בזמן ההזרקה חייב להתאים לרצף ה-offset-ים שבשימוש כאשר האובייקטים נכתבים בסוף

וזה אכן קורה, בגלל אופן העבודה של מיזוגי העמודים והטפסים: AddPages, AddFields ו-AddFieldFonts משנות רק אובייקטים קיימים של המסמך הראשון, והן לעולם לא מוסיפות אובייקטים חדשים. לכן ספירת האובייקטים של המסמך הראשון נשארת ללא שינוי לאורך שלב מיזוג העמודים, וה-offset של כל מסמך עוקב, סכום כל ספירות האובייקטים של המסמכים שלפניו, נשאר יציב מרגע ההזרקה ועד הכתיבה. שוברים את זה, למשל מוסיפים שלב שיוצר אובייקט חדש באמצע המיזוג, וכל הפניה לעמוד או לסימניה בהמשך תהיה שגויה בדיוק במספר האובייקטים שהוספתם. האינווריאנט שקט, אבל הוא נושא עומס

שלוש נקודות כניסה מעל מנוע אחד

המסלול המהיר אינו פיצול של קוד המיזוג. באותו מהלך עבודה, מנוע רמת-הבייט פורק לשגרה פנימית אחת, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), וממשקי ה-API הציבוריים הפכו לעטיפות דקות שבוחרות שני דגלים:

• MergeFileListFast קוראת למנוע בלי שמירה על עץ המבנה, המסלול הרזה ביותר, שמפיל את עץ ה-tagged-PDF כדי שמסלול הבייטים יחול על מספר האובייקטים הגדול ביותר
• MergeFileList קוראת לו עם שמירה פעילה, כך שעץ המבנה שורד והתוצאה נשארת tagged PDF שמיש. המסלול הרגיל הזה גם יורש את מיזוג הסימניות והטפסים הרב-מסמכיים
• MergeFileListStrict מפעילה מצב strict: המעבר המטא-דאטה הראשון נעצר בקלט הראשון שלא מדווח על מיזוג נקי, כך שרק המסמכים שנאספו לפני הקובץ הבעייתי נכללים, במקום לדלג על הקובץ הבעייתי ולהמשיך

האיחוד של המסלולים גם איפשר לבנות מחדש את המיזוג הרגיל מלולאה זוגית ב-O(N²), מיזוג קובץ אחד ושניים, ואז מיזוג התוצאה עם השלישי וכן הלאה, תוך ניתוח מחדש של האגרגטור הגדל בכל שלב, אל מעבר ליניארי יחיד שפותח כל קלט פעם אחת. שתי נקודות הכניסה הוותיקות של שני קבצים ושני streams, MergeFiles ו-MergeStreams, נשארו ללא שינוי וזמינות למי שבאמת רוצה מיזוג זוגי

הערה כנה אחת על התנהגות עץ המבנה, כי היא עקצה את סט הבדיקות. ההסרה של המסלול המהיר אינה מוחלטת: היא מסירה את ההפניה של הקטלוג של המסמך הראשון ל-/StructTreeRoot, אבל אובייקט עץ המבנה עצמו עדיין נכתב החוצה כ-orphan. לכן הבייטים של הפלט המהיר עדיין מכילים את המחרוזת /StructTreeRoot, ואי אפשר להבחין בין פלט מהיר לפלט רגיל רק על ידי חיפוש המחרוזת הזו, ההבדל האמיתי הוא האם הקטלוג עדיין מגיע אל עץ המבנה, וזה מה שקובע אם הקובץ עדיין הוא PDF מתויג שניתן לנווט בו

מתי לבחור בכל מסלול

מסלול הבייטים הוא אופטימיזציית תפוקה להרכבת הרבה מסמכים כשלא צריך לשמר את עץ ה-tagged-PDF, למשל איגוד דוחות, ריצות דוחות, ושרשור אצווה. במדידות על מיזוגים חוזרים של סטים בינוניים עד גדולים, שימוש חוזר בבייטים קיצץ בערך ארבעה עד שלושה עשר אחוז מזמן הריצה, תלוי בתמהיל האובייקטים, בלי כשלונות חדשים בקלטים קטנים או פגומים, כי כל אובייקט שהסורק לא יכול להוכיח שהוא בטוח חוזר לניתוח המלא. אם כן צריך את עץ המבנה שלם לצורכי נגישות, השתמשו במסלול המיזוג הרגיל של PDF מתויג, ששומר עליו; ואם אתם עובדים עם קובצי ענק בודדים ולא עם הרבה קלטים, טכניקות העתקת הבייטים שמתוארות במאמר המלווה על מיזוג ופיצול של PDF גדול עם גישה ישירה לקובץ מיישמות את אותה תפיסה של "להעתיק בייטים, להימנע מעץ האובייקטים המלא" בקנה מידה של קובץ

שגרות המיזוג והווריאנטים המהירים והמחמירים שלהן הן חלק מ-ספריית ה-PDF ל-Delphi של PDFlibPas, שהמדריך שלה כולל את המפרט המלא של ה-API לרשימת קבצים ושל אפשרויות המיזוג המתוארות כאן