/Dests name tree'sinde iki çocuklu bir kök taşıyan bir PDF kurun. İlk çocuk /Limits [(a) (z)] beyan eder ve /Kids dizisi doğrudan köke geri işaret eder. İkinci çocuk (chapter7)'nin gerçek girdisini taşır ama sınırları terstir: [(z) (a)]. chapter7 için ders kitabı usulü bir name tree araması isteyin; ya stack bitene dek özyinelenir ya da bir görüntüleyicinin atlayabileceği bir hedef için "bulunamadı" döner. Dosyanın tamamı yaklaşık iki kilobayta sığar ve içindeki her object temiz ayrışır
O dosya üç ayrı tuzağı tek yapıya paketler: bir /Kids döngüsü, tutmadığı bir anahtarı iddia eden bir aralık ve hiçbir şeyle eşleşemeyecek bir aralık. Dördüncü tuzak çok daha büyük bir dosya ister. Tek bir yaprak 32.768'den fazla ad/değer çifti taşıdığında, "hangi yaprak" ile "hangi girdi"yi tek bir 32 bitlik tamsayıya sıkıştıran her kod yanlış çifti işaret etmeye başlar. Bu yazının devamı her tuzağı, bir okuyucunun ne yapması gerektiğini ve Delphi çağrılarının bu şekilde kurulan dosyalarda nasıl davrandığını gezer
Name tree'ler ve number tree'ler üzerinde oturan dört PDF özelliği
Name tree'ler ile number tree'ler, büyük bir anahtar kümesini object'lere eşleyen her PDF özelliğinin altını doldurur ve losLab PDF Library for Delphi olan PDFlibPas, içlerinden dördünü halka açık TPDFlib metodlarıyla açar. ISO 32000-1 §7.9.6 name tree'yi (string anahtarlar, Table 36), §7.9.7 number tree'yi (tamsayı anahtarlar, Table 37) tanımlar. Kök ile ara düğümler /Kids taşır; yapraklar sıralı anahtar/değer çiftlerini /Names ya da /Nums içinde taşır; kök olmayan her düğüm, altındaki en küçük ve en büyük anahtarı tutan iki elemanlı bir /Limits dizisi taşımalıdır
| Tree | Nerede durur | Belirtim | PDFlibPas okuma API'si |
|---|---|---|---|
| Named destination'lar | Name sözlüğünde /Dests | §12.3.2.3 | GetNamedDestination, ardından GetDestPage / GetDestType |
| Page label'lar | Katalogda /PageLabels (number tree) | §12.4.2 | GetPageLabel |
| Ekler | Name sözlüğünde /EmbeddedFiles | §7.7.4, §7.11.4 | EmbeddedFileCount, GetEmbeddedFileStrProperty |
| Belge düzeyi JavaScript | Name sözlüğünde /JavaScript | §7.7.4 | GlobalJavaScriptCount, GlobalJavaScriptPackageName |
İki satır bir kıvrım saklar. Adlandırılmış hedefler daha eski bir PDF 1.1 biçiminde de vardır: katalogda isim object'leriyle anahtarlanmış düz bir /Dests sözlüğü. GetNamedDestination önce o sözlüğe bakar ve ancak sonra PDF 1.2 name tree'sine iner. JavaScript satırının başka bir şey okuyan neredeyse aynı adlı bir akrabası vardır: GetDocJavaScript, katalog /AA sözlüğündeki belge tetikleyicilerine bağlı script'leri döndürür (WS, DS, WP, DP, DC); belge açıldığında koşan adlandırılmış paketler ise /JavaScript name tree'sinde yaşar ve GlobalJavaScriptPackageName listeler
Bu yapıların tamamı dosyadan gelir. Belirtim bir yazara ne üretmesi gerektiğini söyler; okuyucu ise yazanın, bozuk bir artımlı kaydın ya da bir fuzzer'ın gerçekten oraya koyduğunu alır. Pascal PDF ayrıştırıcısını kötücül dosyalara karşı sağlamlaştırmayla aynı derstir, tampon uzunlukları yerine ağaç biçimine uygulanmış
Döngülü bir /Kids dizisi özyinelemeli tree gezginini neden çökertir?
Özyinelemeli bir gezgin, döngülü bir /Kids dizisi üzerinde çöker; çünkü özyinelemede hangi düğümlere girildiğini hatırlayan bir şey yoktur ve bir ata düğüme tek bir çocuk referansı, sonlu bir dosyayı bitmeyen bir inişe çevirir. Meşru bir ağaç hiçbir döngüsüz aynı hasarı verebilir: tek çocuklu düğümlerden 4.096 kademeli bir zincir, özyinelemeli bir okuyucuya 4.096 stack çerçevesi masrafı olan geçerli sözdizimidir
Daha yumuşak varyant hiç çökmez. İki /Kids girdisi aynı yaprağa referans verdiğinde saf bir sayım onu iki kez ziyaret eder; ek sayısı belgedeki dosya sayısından yüksek gelir ve script listesi aynı paketi iki kez gösterir
PDFlibPas her iki ağaç türünü de heap üzerinde açık bir son giren ilk çıkar stack'iyle, sözlük kimliğiyle anahtarlanmış bir visited kümesiyle gezer. Bir düğüm pop edildiğinde işaretlenir. Döngülü bir referans bir an stack'te oturabilir, ama yukarı çıkar çıkmaz atılır ve her farklı düğüm çocuklarını tam bir kez genişletir. Toplam iş, farklı sözlüklerin sayısıyla /Kids dizilerinin birleşik uzunluğuyla sınırlıdır; 4.096 kademeli zincir, 4.096 döngü turu ve 4.096 hash-set girdisi olur
Sıralama, insanların özyinelemeyi döngüye çevirirken yanlış yaptığı kısımdır. Stack, beslediğinizi tersine çevirir; çocuklar son indeksten ilkine doğru itilmelidir, böylece en soldaki çocuk önce pop olur ve yapraklar üreticinin yazdığı soldan sağa sırada çıkar. Pop'ta işaretlemenin push'ta işaretlemeye üstünlüğü aynı nedenledir. Push'ta işaretlemeyle sağdan sola itmelerde, 0 ile 2 konumlarının paylaştığı bir yaprak 2 tarafından sahiplenir ve girdileri, dosyanın söylediğinden sonra görünür. Sayfa etiketleri o sıraya bel bağlar; son bölüm gösteriyor
Kendi tree kodunuzu başka bir object modeline karşı yazacaksanız, önerdiğimiz biçim budur. Aşağıdaki düğüm tipi bilerek soyuttur ve iki fonksiyon da okuyucu tarafı kodudur, kütüphane çağrısı değil
uses
System.Generics.Collections;
type
TTreeNode = class
public
Kids: TArray<TTreeNode>; // yaprakta boş
Keys: TArray<string>; // yaprak anahtarları, düzgün üreticide sıralı
Values: TArray<Integer>; // Keys'e paralel
HasLimits: Boolean;
LoKey, HiKey: string;
end;
// Kendi yardımcınız: /Limits yalnızca sağlam, sıralı bir çift olduğunda buda olabilir
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;
// Kendi aramanız: açık stack, visited kümesi, pop'ta işaretle
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; // döngü ya da paylaşılan çocuk: çoktan görüldü
Visited.Add(Node, 0);
if Length(Node.Kids) > 0 then
begin
// En soldaki çocuk önce pop olsun diye sağdan sola it
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;
// Bu yaprakta ıskalama: kardeşleri pop etmeye devam et
end;
finally
Visited.Free;
Pending.Free;
end;
end;
Tek bir daldaki ıskalama ağaç hakkında hiçbir şey söylemez
En yaygın arama kısayolu, /Limits'i anahtarı kapsayan ilk çocuğu seçip ona iner ve bir kardeşe bir daha bakmaz. Temiz bir ağaçta bu doğru ve hızlıdır. Açılış paragrafındaki dosyada başarısızdır: ilk çocuk chapter7'yi iddia eder, köke geri götürür ve arama, girdiyi tutan sıradaki kardeş varken boş el döner
PDFlibPas ilk inandırıcı daldaki durmaz. GetNamedDestination'un arkasındaki anahtarlı arama, aralığı anahtarı dışlamayan her çocuğu iter ve bir eşleşme bulana ya da stack boşalana dek pop etmeye devam eder. Sınırları ayrık, sağlam bir ağaçta her düzeyde en fazla bir çocuk aralık kontrolünü yaşar; ek maliyet sıfırdır. Hasarlı bir ağaçta bir avuç ekstra düğüm ziyaretidir ve cevap doğru döner
Yapraklar aynı muameleyi görür. ISO 32000-1, bir /Names dizisindeki anahtarların bayt değerine göre sıralı olmasını ister; kütüphane önce bir ikili arama dener. Iskaladığında çiftlerin üzerinde doğrusal bir taramaya döner; yoksa sıra dışı bir yaprak, var olan bir anahtarı görünmez kılardı. Her gerçek ıskalamada doğrusal tarama bedelini ödemeyi kabul ediyoruz: gerçekten bulunmayan adların araması seyrektir ve çalışan bir bağlantıdaki yanlış "bulunamadı", bir yaprağa ekstra bir geçişten çok daha pahalıdır
Tek bir yapısal çelişki red ile ele alınır. Table 36 bir düğümün /Kids ya da /Names taşımasına izin verir, ikisini birden asla. Anahtarlı arama ikisini de taşıyan bir düğümü hatalı sayar ve üreticinin hangi yarıyı kastettiğini tahmin etmek yerine onu atlar. Number tree sayımı — GetPageLabel'in arkasındaki gezinti gibi — daha affedilicidir ve ikisi de mevcutken /Kids izler; bütün bir aralığı düşürmek, ondan sonraki her sayfayı yanlış etiketlerdi
Bir okuyucu /Limits'e ne için güvenebilir?
Bir okuyucu /Limits'e iş atlamak için güvenebilir ve yalnızca çift sağlam olduğunda; girdiyi bir anahtarın bulunmadığı sonucuna varmak için asla kullanamaz. Table 36, ara ve yaprak düğümlerin onu taşıması gerektiğini söyler; oysa pratikte girdi elle düzenlemelerden sonra kaybolur, name tree içinde sayılar tutar ya da sınırları tersten gelir. PDFlibPas bu hâllerin her birini aynı yolla, çocuğu aranabilir tutarak çözer
- Eksik
/Limits: böyle bir çocuğu atlayan bir aralık kontrolü, üretici girdiyi unuttuğu her an onun bütün alt ağacını ulaşılmaz kılar; çocuk aranır - Yanlış tip ya da yanlış uzunluk, name tree'de sayılar ya da tek elemanlı dizi gibi: tam olarak eksik girdi gibi ele alınır
[(Z) (A)]ya da[9 0]gibi ters sınırlar:Lo > Hiolduğunda hiçbir anahtarLo <= Key <= Hi'yi sağlamaz; çifte güvenmek dalı her aramada dışlardı. Bir aralık, yalnızca alt sınırı üst sınırını aşmadığında buda olur- Sağlam ve sıralı: dalı atlamak için kullanılır; girdi zaten bunun için var
Çağıranın tarafında ayrıştırılması gereken iki sıfır var. GetNamedDestination, ad gerçekten yoksa 0 döndürür, değilse bir hedef ID'si döndürür. Geçerli bir ID için GetDestPage'in 0 döndürmesi, adın var olduğu ama hedefinin bu belgede bir sayfaya çözülmediği demektir; farklı bir hata raporudur. GetDestType görünümü bildirir: XYZ için 1, Fit için 2 ve FitBV için 8'e dek böyle gider
uses
PDFlibrary;
procedure LookUpDestination(const FileName, DestName: string);
var
Lib: TPDFlib;
DestID, Page: Integer;
begin
Lib := TPDFlib.Create;
try
if Lib.LoadFromFile(FileName, '') <> 1 then
begin
WriteLn('Load failed, error ', Lib.LastErrorCode);
Exit;
end;
// Önce katalog /Dests (PDF 1.1), sonra /Dests name tree'si
DestID := Lib.GetNamedDestination(DestName);
if DestID = 0 then
begin
WriteLn('No destination named ', DestName);
Exit;
end;
Page := Lib.GetDestPage(DestID);
if Page = 0 then
WriteLn(DestName, ' exists but does not resolve to a page')
else
WriteLn(DestName, ' -> page ', Page,
', view type ', Lib.GetDestType(DestID)); // 1 = XYZ, 2 = Fit ...
finally
Lib.Free;
end;
end;
Bu, kompakt bir regresyon kontrolü kurar. Açılış paragrafındaki iki çocuklu dosyayı kurun, gerçek chapter7 girdisini /Fit görünümüyle 2. sayfaya yöneltin; prosedür 2. sayfayı ve 2 görünüm tipini yazmalı. İlk eşleşme araması "No destination" yazar; çünkü döngülü çocuk yarışı kazanır. Ters sınırlara güvenen bir arama aynı şeyi ters nedenle yazar. Hedefler çözülmeye başladıktan sonra onlara işaret eden outline girdileri Delphi'de PDF yer imi ve annotation action'larını okumada kapsanır
32.768 girdiyi aşan yapraklar ve paketlenmiş indeks tuzağı
Kod "M yaprağındaki N girdisi" için tek bir tamsayı handle istediğinde, kolay yol yaprak konumunu bir Integer'in yüksek 16 bitine, o yaprağın /Names dizisindeki ofseti de düşük 16 bitine paketler. Her çift iki dizi yuvası tutar. 32.768 çift indeksi — 32.769uncu çift — bu yüzden 65.536 ofsetinde, yani $10000'de başlar. O bit yüksek yarıya taşar ve decoder onu sıradaki yaprağın 0 ofseti olarak geri okur
Belirtiler ağaç biçimine göre değişir. Tek yaprakla sıradaki yaprak yoktur; çözülen handle, yaprak listesinin sonuna taşar. Birkaç yaprakla bulma ya da silme, sıradaki yaprağın ilk çiftine düşer; düz bir anahtar taraması ise istenen anahtarı hâlâ var olarak raporlar. Bu boyutta dosyalar egzotik değildir. Sembol başına bir adlandırılmış hedef taşıyan üretilmiş bir API referansı, hızla 32.768 girdiyi geçer ve bazı üreticiler ağacı dengelemek yerine hepsini tek bir düz yaprağa yazar
PDFlibPas yaprak konumu ile girdi ofsetini iki tam genişlikte tamsayıda tutar; hiçbir yaprak boyutunda biri ötekine taşamaz. Aynı okuyucu yalnızca gerçek string anahtarlarını sayar. [(Valid) 42 123 456] gibi bir yaprakta EmbeddedFileCount 1 bildirir; 123 sayısal anahtarı hiçbir zaman boş bir ad sanılmaz ve 0 ya da altı bir indeks, GetEmbeddedFileStrProperty'den arkasında tesadüfen ne varsa onun yerine boş string döndürür. O fonksiyonun 1 etiketi dosya adıdır, 2 etiketi MIME alt tipidir
procedure AuditTrees(const FileName: string);
var
Lib: TPDFlib;
I: Integer;
begin
Lib := TPDFlib.Create;
try
if Lib.LoadFromFile(FileName, '') <> 1 then
Exit;
// /PageLabels number tree'si; olmayan dosyalar düz sayfa numarası döndürür
for I := 1 to Lib.PageCount do
WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
// /EmbeddedFiles name tree'si; indeksler 1 tabanlı, string olmayan anahtarlar atlanır
for I := 1 to Lib.EmbeddedFileCount do
WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')'); // ad, MIME alt tipi
// /JavaScript name tree'si: paket adlarını listele, hiçbirini koşturma
for I := 1 to Lib.GlobalJavaScriptCount do
WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
finally
Lib.Free;
end;
end;
İki sayfalık bir test dosyası beklenen çıktıyı iyi gösterir. /PageLabels köküne bir yaprağı iki kez listeleyen ve kökün kendisine de referans veren bir /Kids dizisi verin; 1. sayfadan küçük harfli roma ve 2. sayfadan A- önekli onluk aralıklarıyla. Denetim i ile A-1 yazmalı, her aralık bir kez uygulanmış. Sayfa etiketlerini böyle bir ağaca yazmanın kendi kıvrımları vardır; /Kids number tree'lerinde saklanan PDF sayfa etiketlerini düzeltmede kapsanır. AddPageLabels, eklemeden önce /Kids kökünü tek bir /Nums yaprağına düzleştirir, aynı döngü güvenli sayımıyla
Gezinim sınırlarını nereye çizer?
Gezinim, gerçek anahtarları sağlam olan her ağaç için sonlanma, kararlı sıra ve doğru cevap garantiler. Hasarlı bir ağacı yazıldığı gibi okur ve yazarın kastettiklerini yeniden kurmaya çalışmaz; o seçimden beş sonuç izler
- Bir düğümü kimlik tanımlar, içerik değil. Aynı girdileri taşıyan iki farklı sözlük iki düğümdür; bir yaprağı referans vermek yerine kopyalayan bir üretici o girdileri iki kez alır
- Sağlam, sıralı bir
/Limitsçifti yanlış olduğunda bile buda olur. İnandırıcı yalan söyleyen bir aralık —(q)'yu da tutan bir yaprak üzerinde[(a) (m)]gibi —q'yu gizler. Tek savunma/Limits'i her yerde yok sayıp her yaprağı taramak olurdu; on binlerce girdili bir hedef ağacında bu, girdinin varlık nedenini çöpe atar. Budamaya devam ediyoruz - Sayım dosya sırasını korur.
GetPageLabelsayılan her aralığı gezer ve başlangıç indeksi sayfaya eşit ya da onun altında olan sonuncuyu uygular; aralıkları sıra dışı yazan bir üretici dosya sırası semantiği alır ve gezintiyi ters çevirmek, 200. sayfaya ön materyal stilini verirdi - Bellek, farklı düğümlerle girdilerle büyür. Gezinim, ayrıştırılmış object'lerin üstüne bir liste ve bir hash set ekler
- Tek yapraktaki yinelenen anahtarlar belirleyici çözülür: ikili arama hangi uyan çifte önce düşerse onu döndürür, doğrusal yedek taramadaki son uyanı tutar
Preflight araçları, arşivciler ve belge görüntüleyiciler bu ağaçları tek bir sayfa render edilmeden okur; bu, onları yükleme kuyruğuna gelen her neyse ilk karşılayan çizere koyar. Burada anlatılan tree okuyucuları, hem Delphi hem Free Pascal ile derlenen PDFlibPas, the PDF Library for Delphi ile gelir