PDFlibPas vardų medžiai: ciklai, ribos ir dideli lapai

PDFlibPas, losLab PDF Library for Delphi, PDF vardų medžius ir skaičių medžius apeina su aiškiu steku ir aplankytųjų aibe nuo v3.539.45, tad cikliniai /Kids, bendri vaikai ir tūkstančius lygių gilūs medžiai daugiau neišsenka kreipinių steko ir nedubliuoja įrašų. Nuo v3.539.51 dingusi, sugadinta ar apversta /Limits pora niekada neslepia šakos, laikančios raktą. Pavadinti tikslai, puslapių etiketės, priedai ir dokumento lygio JavaScript visi skaitomi pro šiuos du kodo kelus, o tai juos padeda bet kokio ne paties pagaminto PDF atakos paviršiaus dalimi

Trigeris retai kada egzotiškas. Fuzzeris, priešiškas įkėlimas ar brokuota inkrementinė pakuotė užrašo /Kids įrašą, rodantį atgal į protėvį, ir rekursyvus apėjimas žūsta su stack overflow ant dviejų kilobaitų failo. Tylesnis gedimas – paieška, kuri pasitiki sugadintu /Limits masyvu ir praneša „nerasta“ apie tikslą, kuris aiškiai ten yra

Kur PDF viduje atsiranda vardų medžiai ir skaičių medžiai?

Vardų medžiai ir skaičių medžiai atsiranda visur, kur PDF didelę raktų aibę susieja su objektais, o PDFlibPas bent keturis iš jų skaito per viešąsias API. ISO 32000-1 §7.9.6 apibrėžia vardų medį (eilutės raktai, 36 lentelė), o §7.9.7 – skaičių medį (sveikųjų skaičių raktai, 37 lentelė). Abu yra maždaug subalansuoti medžiai, kurių šaknis ir tarpiniai mazgai neša /Kids, kurių lapai neša surūšiuotas rakto/reikšmės poras /Names ar /Nums, o kurių ne šakniniai mazgai neša dvejų elementų /Limits masyvą su mažiausiu ir didžiausiu raktu žemiau jų

Medis	Kur gyvena	Specifikacija	PDFlibPas skaitymo API
Pavadinti tikslai	/Dests vardų žodyne	§12.3.2.3	GetNamedDestination, tada GetDestPage / GetDestType
Puslapių etiketės	/PageLabels kataloge (skaičių medis)	§12.4.2	GetPageLabel
Priedai	/EmbeddedFiles vardų žodyne	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Dokumento lygio JavaScript	/JavaScript vardų žodyne	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dvi tos lentelės detalės lengva praleisti. Pavadinti tikslai dar turi senesnę PDF 1.1 formą – paprastą /Dests žodyną kataloge, indeksuotą vardų objektais, – ir GetNamedDestination pirmiausia patikrina tą žodyną, o tik paskui leidžiasi į PDF 1.2 vardų medį. O GetDocJavaScript iš viso nėra vardų medžio skaitytuvas: jis grąžina prie dokumento trigerių prikabintus scenarijus iš katalogo /AA žodyno (WS, DS, WP, DP, DC), o pavadintieji scenarijų paketai, paleidžiami atsidarius dokumentą, gyvena /JavaScript vardų medyje

Kiekvienas tų struktūrų baitas ateina iš failo. Specifikacija sako, ką rašytojas privalo pagaminti; ji negali sutrukdyti skaitytuvui gauti ką nors kita – tai ta pati pamoka, slepianti Pascal PDF analizatoriaus sukietinimą prieš kenkėjiškus failus, čia pritaikyta medžio formai, o ne buferių dydžiams

Kodėl ciklinis /Kids masyvas sugriauna rekursyvų medžio apėjimą?

Ciklinis /Kids masyvas sugriauna rekursyvų apėjimą todėl, kad niekas rekursijoje nepastebi, jog mazgas matytas anksčiau, tad vaikas, nurodantis į savąjį protėvį, baigtinį failą paverčia begaliniu besileidimu. Iki v3.539.45 NameTreeLookup, NumTreeLookup, EnumNumTree ir vidinis TPDFNameTree.ProcessNode visi kviesdavo save po kartą kiekvienam vaikui. Viena savęs nuoroda užtekdavo užbaigti procesą, o teisėtas, bet labai gilus medis galėdavo tą patį be jokio ciklo

Švelnesnė atmaina sugadina rezultatus vietoj griūvės. Kai du /Kids įrašai nurodo į tą patį lapą, naivus išvardijimas jį aplanko dukart, ir priedų skaičius ar scenarijų paketų sąrašas praneša įrašus, kurie neegzistuoja

Taisymas rekursiją pakeičia aiškiu paskutinis-įėjęs-pirmas-išeinantis steku kravoje ir aplankytųjų aibe, kurios raktas – žodyno tapatumas. Mazgas pažymimas tada, kai išimamas, o ne kai įdedamas, tad ciklinė nuoroda gali trumpai pasėdėti steku, bet numetama akimirksniu, kai vėl iškyla. Kiekvienas atskiras mazgas savo vaikus išskleidžia lygiai kartą, tad visas darbas ribojamas atskirų žodynų skaičiumi plius bendru jų /Kids masyvų ilgiu. Gilumas nustoja svarbęs: 4 096 lygių grandinė – vos 4 096 ciklo apėjimai ir 4 096 hash aibės įrašai

Bet tvarka vis dar svarbi, ir steką reikia maitinti atvirkščiai, kad ji išliktų. Vaikai dedami nuo paskutinio indekso žemyn iki pirmojo, tad kairiausias vaikas išimamas pirmiausia, o lapai išeina ta pačia iš kairės į dešinę tvarka, kokia rašė gamintojas. GetPageLabel nuo to priklauso: jis apeina kiekvieną išvardytą intervalą ir pritaiko paskutinįjį, kurio pradinis indeksas ne aukščiau puslapio, tad apvertus išvardijimą 200 puslapis tylioje gautų priešakyminio turinio stilių. Skeletas žemiau parodo raštą ant abstraktaus mazgo tipo, nepriklausomo nuo jokio PDF objektų modelio

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // tuščias lape
    Keys: TArray<string>;      // lapo raktai, surūšiuoti dorai besielgiančio gamintojo
    Values: TArray<Integer>;   // lygiagreti Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits yra užuomina: tik gerai suformuota, surikiuota pora gali nukirpti šaką
function LimitsExclude(Node: TTreeNode; const Key: string): Boolean;
begin
  Result := Node.HasLimits and (Node.LoKey <= Node.HiKey) and
    ((Key < Node.LoKey) or (Key > Node.HiKey));
end;

function FindValue(Root: TTreeNode; const Key: string;
  out Value: Integer): Boolean;
var
  Pending: TList<TTreeNode>;
  Visited: TDictionary<TTreeNode, Byte>;
  Node: TTreeNode;
  I: Integer;
begin
  Result := False;
  Value := 0;
  if Root = nil then
    Exit;
  Pending := TList<TTreeNode>.Create;
  Visited := TDictionary<TTreeNode, Byte>.Create;
  try
    Pending.Add(Root);
    while Pending.Count > 0 do
    begin
      Node := Pending[Pending.Count - 1];
      Pending.Delete(Pending.Count - 1);
      if Visited.ContainsKey(Node) then
        Continue;                      // ciklas ar bendras vaikas: matėme
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Dėkite iš dešinės į kairę, kad kairiausias vaikas būtų išimtas pirmiausia
        for I := High(Node.Kids) downto 0 do
          if (Node.Kids[I] <> nil) and not LimitsExclude(Node.Kids[I], Key) then
            Pending.Add(Node.Kids[I]);
      end
      else
        for I := 0 to High(Node.Keys) do
          if (Node.Keys[I] = Key) and (I <= High(Node.Values)) then
          begin
            Value := Node.Values[I];
            Exit(True);
          end;
      // Nepataikymas šiame lape nėra verdiktas: toliau išiminėkite seseris
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Kodėl paieška negali sustoti ties pirmaja atitinkančia šaka?

Paieška negali sustoti ties pirmąja šaka, kurios intervalas atitinka, nes /Limits intervalai tikrame faile gali persidengti ar meluoti, o šaka, teigianti turinti raktą, nebūtinai yra šaka, jį laikanti. Iki v3.539.45 paieškos pirmajam vaikui, kurio /Limits dengė raktą, nustatydavo Found vėliavą, leisdavosi į jį ir daugiau nežiūrėdavo į kitas seseris. Jei tas vaikas pasirodydavo tuščias, pasenęs arba kilpa atgal į šaknį, atsakymas būdavo nil, net kai pati kita sesuo laikydavo raktą

Perrašytasis FindTreeValue, kuris dabar remia ir NameTreeLookup, ir NumTreeLookup, deda kiekvieną vaiką, kurio intervalas neatskiria rakto, ir toliau išiminėja, kol randa atitikmenį arba ištuština steką. Nepataikymas viename lape – tiesiog nepataikymas viename lape. Gerai suformuotame medyje tai nekainuoja nieko papildomai; sugadintame kainuoja keletą papildomų mazgų apsilankymų ir grąžina teisingą atsakymą

Lapo paieška laikosi tos pačios filosofijos. ISO 32000-1 reikalauja, kad /Names masyvo raktai būtų surūšiuoti pagal baito reikšmę, tad lapas pirmiausia perieškomas dvejetaine paieška. Nesuveikus, PDFlibPas grįžta prie tiesinio porų perėjimo, nes netvarkingas lapas kitu atveju padarytų esantį raktą nematomu. Rūšiavimas – greitasis kelias, ne filtras

Paieška dar atsisako spėlioti viename struktūriniame prieštare. 36 lentelė leidžia mazgui nešti arba /Kids, arba /Names – niekada abu, – o paieškos kelias mazgą, nešantį abu, traktuoja kaip sugadintą ir praleidžia, vietoj to, kad išsirinktų vieną interpretaciją. Išvardijimo keliai, kaip EnumNumTree, atlaidūs ir seka /Kids, kai abu yra

Kuo skaitytuvas gali pasitikėti /Limits?

Skaitytuvas /Limits gali pasitikėti tik darbo praleidimui, niekada – spręsdamas, kad rakto nėra, ir tik kai pora gerai suformuota. 36 lentelė sako, kad tarpiniai ir lapiniai mazgai privalo nešti /Limits kaip dvejų elementų mažiausio ir didžiausio raktų masyvą, bet praktikoje tas įrašas dingsta po rankinių redagavimų, laiko skaičius vardų medyje arba atkeliauja su apsuktomis ribomis. PDFlibPas v3.539.45 ir v3.539.51 kiekvieną atvejį sprendžia taip pat: jei intervalo nepavyksta perskaityti kaip teisingo tipo surikiuotos poros, vaikas lieka ieškomas

• Dingusios /Limits: senoji intervalo patikra grąžindavo False ir vaikas praleisdavas visai, tad gamintojas, pamiršęs įrašą, padarydavo nepasiekiamą visą savo pomedį. Nuo v3.539.45 vaikas ieškomas
• Netinkamas tipas ar ilgis, kaip skaičiai vardų medyje arba vieno elemento masyvas: traktuojama lygiai kaip dingęs įrašas nuo v3.539.45
• Apversta ribos, kaip [(Z) (A)] arba [9 0]: v3.539.45 jų vis dar laikydavosi, o joks raktas negali tenkinti Lo <= Key <= Hi, kai Lo > Hi, tad šaka būdavo atmetama kiekvienai paieškai. Nuo v3.539.51 intervalas kirpimui naudojamas tik tada, kai jo apatinė riba neviršija viršutinės
• Gerai suformuota, surikiuota ir teisinga: naudojama šakos praleidimui – tai visos įrašo prasmė

Tikri raktai sprendžia baigtį kiekvienu atveju. Priešiškas /Limits gali priversti PDFlibPas aplankyti daugiau mazgų, nei būtina, bet sugadintas daugiau negali padaryti, kad esamas tikslas dingtų. Iš kvietėjo pusės niekas nekeičiasi: GetNamedDestination grąžina 0, kai vardo tikrai nėra, o kitu atveju – tikslų ID, ir tikslų funkcijos toliau jau pačios

uses
  PDFlibrary;

procedure LookUpDestination(const FileName, DestName: string);
var
  Lib: TPDFlib;
  DestID: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
    begin
      WriteLn('Load failed, error ', Lib.LastErrorCode);
      Exit;
    end;
    // Pirmiausia katalogo /Dests (PDF 1.1), tada /Dests vardų medis
    DestID := Lib.GetNamedDestination(DestName);
    if DestID = 0 then
      WriteLn('No destination named ', DestName)
    else if Lib.GetDestPage(DestID) = 0 then
      WriteLn(DestName, ' exists but does not resolve to a page')
    else
      WriteLn(DestName, ' -> page ', Lib.GetDestPage(DestID),
        ', view type ', Lib.GetDestType(DestID));  // 1 = XYZ, 2 = Fit ...
  finally
    Lib.Free;
  end;
end;

Paleista prieš rankomis sudėtą failą, kurio /Dests šaknis turi vieną vaiką, kilpą darantį atgal į šaknį po [(a) (z)] intervalu, ir antrą vaiką, laikantį tikrąjį įrašą po apverstomis [(z) (a)] ribomis, ši procedūra tikslą išspręndžia į 2 puslapį su 2 rodinio tipu (Fit). Iki v3.539.45 ta pati paieška grąžindavo 0, nes kilpą darantis vaikas reikalaudavo rakto pirmiausia, o paieška sesers niekada nepasiekdavo; vienas v3.539.45 vis dar grąžindavo 0, nes apverstas intervalas atmetė tikrąjį lapą. Jeigu paskui skaitote turinius, rodančius į šiuos tikslus, giminaičio straipsnis apie PDF žymių ir anotacijų veiksmų skaitymą Delphi dengia veiksmų pusę

Kaip lapas su 32 769 vardais sulaužė TPDFNameTree?

Lapas su 32 769 vardo/reikšmės poromis sulaužė TPDFNameTree, nes jo vidinis FindIndex supakavo du skaičius į vieną 32 bitų Integer: lapo vietą vidiniame masyvų sąraše aukštuosiuose 16 bitų ir įrašo poslinkį to lapo /Names masyve žemuosiuose 16 bitų. Kiekviena pora užima du masyvo langus, tad 32 769-oji pora, poros indeksas 32 768, prasideda poslinkyje 65 536 – tai $10000. Ta reikšmė perneša į aukštąją pusę, ir dekoduotojas ją skaitydavo atgal kaip poslinkį 0 kitame lape

TPDFNameTree – klasė, slypinti už priedų, globalių JavaScript paketų ir pavadintų tikslų rašymo, o tai padaro pasekmes konkrečiomis. Vieno lapo medyje kito lapo nėra, tad FindKey ir DeleteKey indeksuodavo už lapų sąrašo galo; kelių lapų medyje jie grąžindavo arba ištrindavo pirmąją sekančio lapo porą vietoj prašytosios. Tuo metu HasKey vesdavo savą peržiūrą ir pranešdavo raktą esant, tad klasė prieštaraudavo pati sau. Sugeneruotas atskaitinis vadovas su vienu pavadintu tikslu kiekvienam API simboliui peržengia 32 768 įrašus be jokių pastangų, o kai kurie gamintojai visus juos rašo į vieną plokščią lapą

Nuo v3.539.45 FindIndex grąžina masyvo indeksą per atskirą out parametrą, o pilną įrašo poslinkį – kaip savo rezultatą, tad jokia reikšmė nenukerpama. Tas pats leidimas sugriežtino du kaimynus. KeyName dabar skaičiuoja ir grąžina tik tikrus eilutės raktus, o indeksui 0 ar žemesniam grąžina tuščią eilutę – anksčiau jis castindavo bet kokį objektą, einantį po netinkamo rakto. HasKey daugiau netraktuoja skaitinio ar kitaip netinkamo rakto kaip tuščio vardo. Lape, tokiam kaip [(Valid) 42 123 456], HasKey('') dabar False, o KeyName(2) grąžina tuščią eilutę

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // /PageLabels skaičių medis; failai be jo grąžina paprastus puslapių numerius
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles vardų medis; indeksai nuo 1, ne eilutės raktai praleidžiami
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // pavadinimas, MIME tipas
    // /JavaScript vardų medis: išvardinkite paketų pavadinimus, nieko nevykdykite
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Ant to paties rankomis sudėto failo, kurio /PageLabels šaknis vieną lapą išvardija dukart ir nurodo į save, ši auditas atspausdina i ir A-1 abiem puslapiams, kiekvieną intervalą po kartą, ir vienintelį scenarijų paketą iš /JavaScript medžio, kuris irgi rodo atgal į savą šaknį. Puslapių etikečių rašymo pusė turi savą istoriją su /Kids šaknimis, aprašytą PDF puslapių etikečių, saugomų /Kids skaičių medžiuose, taisyme; AddPageLabels tokią šaknį išlygina prieš įterpdama ir remiasi tuo pačiu čia aprašytu EnumNumTree išvardijimu

Ko šis sukietinimas vis dar negarantuoja?

Sukietinimas garantuoja baigtinumą, stabilią tvarką ir teisingus rezultatus medžiams, kurių tikri raktai sveiki; jis nepadaro sugadinto medžio reiškiančiu tai, ką ketino jo autorius. Kelios ribos vertos žinios, prieš statant ant jų

• Aplankytųjų aibė dirba pagal objektų tapatumą. Du atskiri žodynai su identišku turiniu yra du mazgai, tad gamintojas, nukopijavęs lapą vietoj nuorodos į jį, vis tiek pagimdo dubliuotus įrašus
• Gerai suformuota, surikiuota, bet neteisinga /Limits vis tiek kirpsta. Skaitytuvas, naudojantis intervalus kaip optimizaciją, negali turėti imuniteto intervalui, kuris meluoja tikimai; vienintelė alternatyva – visai ignoruoti /Limits ir peržiūrėti kiekvieną lapą
• Išvardijimas išlaiko failo tvarką, bet nerūšiuoja. GetPageLabel pritaiko paskutinį išvardytą intervalą ne aukščiau puslapio, tad gamintojas, rašantis intervalus netvarkingai, gauna failo tvarkos semantiką
• Atmintis auga su atskirų mazgų ir įrašų skaičiumi. Apėjimas prideda sąrašą ir hash aibę – nieko daugiau, bet 100 MB vardų medis po analizės tebėra 100 MB vardų medis
• Dubliuoti raktai vieno lapo viduje nepranešami. Dvejetainė paieška grąžina tą atitinkančią porą, kurią pasiekia pirmiausia; tiesinis atsarginis kelias pasilieka paskutinę peržiūrėtą atitiktį

Trumpa atmintinė: PDF medžių skaitymas iš nepatikimų failų

• Atnaujinkite iki v3.539.45 ar vėlesnės, kad vardų ir skaičių medžių apėjimas būtų saugus ciklams ir stekui, o iki v3.539.51 ar vėlesnės – kad apverastos /Limits daugiau neslėptų raktų
• 0 grąžinantį GetNamedDestination traktuokite kaip „nėra“, o 0 grąžinantį GetDestPage – kaip „yra, bet netinkamas naudoti“
• /JavaScript vardų medžiui naudokite GlobalJavaScriptCount ir GlobalJavaScriptPackageName; GetDocJavaScript vietoj to skaito katalogo /AA trigerius
• Priedus ir scenarijų paketus indeksuokite nuo 1 iki skaičiaus, kurį praneša biblioteka; netinkami raktai nesiskaito
• Savo medžio kode žymėkite mazgus aplankytais išimant, dėkite vaikus atvirkščiai ir leiskite /Limits kirpti tik tada, kai tai gerai suformuota, surikiuota pora

Išankstinės patikros įrankiai, archyvatoriai ir peržiūros programos šiuos medžius skaito dar prieš atvaizduojant bet kurį puslapį, tad jie turi išgyventi bet ką, kas atkeliauja į įkėlimo eilę. Aukščiau aprašyti medžių skaitytuvai keliauja su PDFlibPas, PDF Library for Delphi, kuriuo kompiliuojasi ir Delphi, ir Free Pascal