Rzadki leniwy indeks obiektów PDF w Delphi z PDFiumPas

Chcesz wyciągnąć jeden słownik z dwugigabajtowego PDF, a narzędzie najpierw rozwija całą tabelę odwołań krzyżowych do tablicy wymiarowanej wartością /Size z traileru. PDFiumPas zastępuje ten krok rzadkim leniwym indeksem obiektów: przechowuje wyłącznie deskryptory sekcji xref, rozwiązuje pojedynczy numer obiektu na żądanie przez ograniczone okna i buforuje tylko te wpisy, których faktycznie użyłeś

Stara postać tego kodu w FPdfCompress była uczciwa, ale droga. ApplyDefaultOpenAction wczytywała cały plik do jednego TBytes, a następnie alokowała gęstą tablicę TPdfActiveXrefEntries z jednym slotem na numer obiektu aż do /Size. Przy skali zawodziły dwie rzeczy. Koszt odczytu rósł liniowo z rozmiarem dokumentu, nawet gdy wywołujący chciał cztery słowniki, a gęsta tablica kolidowała z budżetem parsera: TPdfParserResourceBudget.Default ustawia MaxObjects na 4 000 000, więc całkowicie poprawny plik, którego najwyższy numer obiektu leży powyżej tego limitu, był odrzucany z powodów pamięciowych, a nie poprawnościowych

Dlaczego publiczne API biblioteki PDFium nie odpowiada na to pytanie?

Bo te informacje istnieją wewnątrz PDFium, ale nigdy nie przekraczają granicy C. CPDF_Parser utrzymuje wewnętrznie tabelę odwołań krzyżowych, przynależność do strumieni obiektów i pierwszeństwo rewizji, a opublikowane nagłówki nie wystawiają żadnego punktu wejścia, który przyjąłby numer obiektu i zwrócił jego surowy offset, generację, rewizję, która wygrała, albo ObjStm, w którym obiekt żyje. Strona zapisu jest równie zamknięta: FPDF_SaveAsCopy i FPDF_SaveWithVersion dają ci wyłącznie sekwencyjne wywołanie zwrotne zapisu. Każda poprawka katalogu na poziomie bajtów po natywnym zapisie musi więc powstać w warstwie Pascal, dlatego PDFiumPas parsuje te struktury samodzielnie, zamiast korzystać z biblioteki DLL

Co rzadki indeks faktycznie przechowuje w pamięci?

Deskryptory, nie wpisy. Dla klasycznej tabeli (ISO 32000-1 §7.5.4) TPdfSparseXrefSubsection przechowuje pierwszy numer obiektu, liczbę obiektów, offset bajtowy, od którego zaczynają się wiersze wpisów, i zmierzoną szerokość wpisu. Same wpisy zostają w pliku. Szerokość jest mierzona z pierwszego wiersza, a nie zakładana jako 20 bajtów, bo producenci nie są zgodni co do końców linii; PDFiumPas akceptuje od 18 do 64 i odrzuca wszystko poza tym przedziałem, wraz z każdą podsekcją, której zadeklarowany licznik wybiegłby poza koniec strumienia. Dla strumienia odwołań krzyżowych (§7.5.8) sekcja przechowuje trzy szerokości pól /W, każde ograniczone do zakresu od 0 do 8, spłaszczone pary /Index oraz zdekodowane bajty wpisów, których oczekiwana długość jest wyliczana z /W i /Index, zanim choć jeden bajt zostanie rozpakowany

Cały indeks buduje Initialize z końcowego okna o rozmiarze co najwyżej 1 MiB, w którym odnajdywany jest startxref, a każdy kolejny odczyt obiektu używa okna obiektu o wielkości 1 MiB. Sufit surowego strumienia wynosi 64 MiB, a pojedyncza linia xref nie może przekraczać 1024 bajtów. Jeśli czytałeś naszą notkę o walidacji strumieni obiektów i odwołań krzyżowych w PDFiumPas, ta sama dyscyplina szerokości pól obowiązuje i tutaj, tylko że teraz służy zaadresowaniu jednego wpisu zamiast audytu całej tabeli

uses
  FPdfCompress;

var
  Source: TFileStream;
  Revision: TPdfSparseRevisionInfo;
begin
  Source := TFileStream.Create(FileName, fmOpenRead or fmShareDenyWrite);
  try
    { przechodzi tylko po startxref, łańcuchu /Prev i katalogu }
    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;

Jak jedno wyszukanie dochodzi do jednego obiektu?

Arytmetyką, w obu układach. Klasyczna podsekcja ma wiersze o stałej szerokości, więc adres wpisu to początek podsekcji plus offset obiektu razy zmierzona szerokość; PDFiumPas wczytuje wtedy tę jedną linię, parsuje dziesięciocyfrowy offset i pięciocyfrową generację, sprawdza generację względem sufitu 65535 z §7.5.4 i klasyfikuje końcowe słowo kluczowe jako axkDirect albo axkFree. Strumień odwołań krzyżowych potrzebuje jednego kroku więcej, bo podsekcje /Index są sklejone w zdekodowanym przebiegu bajtów, więc indeks sumuje liczniki poprzednich podsekcji, zanim pomnoży przez zsumowaną szerokość /W. Typ 1 daje offset, typ 2 daje numer strumienia obiektów i indeks członka, a wszystko inne staje się axkUnknown zamiast zgadywanki

{ klasyczna tabela, ISO 32000-1 sekcja 7.5.4 }
EntryOffset := Subsection.EntryOffset +
  Int64(ObjectNumber - Subsection.FirstObject) * Subsection.EntryWidth;

{ strumień odwołań krzyżowych, ISO 32000-1 sekcja 7.5.8 }
EntryWidth := Section.Widths[0] + Section.Widths[1] + Section.Widths[2];
EntryPosition := Integer((PriorCount + ObjectNumber -
  Section.IndexValues[I]) * EntryWidth);

Nic w żadnej ze ścieżek nie jest proporcjonalne do /Size. W tym cały sens przepisania: wartość rozmiaru z traileru jest niesiona dalej jako metadane i używana przy zapisie rewizji przyrostowej, ale nigdy nie napędza alokacji. Zestaw regresyjny przypina to zestawem danych testowych, którego drzewo stron mieszka przy obiektach 1 000 000 000 i 1 000 000 001 pod trailerem deklarującym /Size 1000000002. Stara gęsta implementacja odmawiała przyjęcia takiego pliku; rzadki indeks rozwiązuje oba odwołania i zachowuje zadeklarowany rozmiar w trailerze wyjściowym

Rewizje hybrydowe, łańcuchy /Prev i straż wokół nich

Pierwszeństwo rewizji to miejsce, w którym naiwny leniwy indeks się gubi. PDFiumPas przechodzi łańcuch od startxref w kolejności od najnowszych i zatrzymuje wyszukanie na pierwszej sekcji, która odpowie, co odtwarza regułę pierwszeństwa bez materializowania scalonej tabeli. Pliki hybrydowe (§7.5.8.4) są obsłużone wewnątrz gałęzi klasycznej: gdy trailer zawiera /XRefStm, sekcja strumienia uzupełniającego jest rejestrowana przed klasyczną sekcją, która się na nią powołała, więc skompresowane obiekty niewidoczne dla zwykłej tabeli są nadal odnajdywane, a wpisy klasyczne zachowują swoje znaczenie. Starsze rewizje są potem śledzone przez /Prev

Ten spacer ograniczają dwie straże i obie mają znaczenie przy uszkodzonych plikach. Każdy odwiedzony offset jest zapisywany, więc /Prev wskazujący z powrotem w łańcuch się kończy, zamiast kręcić się w kółko, a głębokość przechodzenia ogranicza MaxRecursionDepth, domyślnie 1024. Flaga szyfrowania jest akumulowana wzdłuż całego łańcucha, a nie odczytywana wyłącznie z najnowszego traileru, bo dokument, którego ostatni trailer pomija /Encrypt, może być nadal zaszyfrowany gdzieś dalej w tyle; wywołujący dopisujący rewizje polegają na tej fladze, by odmówić zapisu obiektów w czystym tekście do zaszyfrowanego pliku

Wpisy typu 2: dlaczego strumień obiektów czeka

Wpis typu 2 wskazuje strumień obiektów, a PDFiumPas nie dotyka tego strumienia, dopóki wywołujący nie poprosi o jednego z jego członków. Gdy w końcu to następuje, weryfikowane jest /Type /ObjStm, /N jest sprawdzane względem budżetu obiektów, a /First względem sufitu zdekodowanych bajtów, przy czym /N jest dodatkowo rachowane z /First, bo każda para nagłówka potrzebuje co najmniej czterech bajtów. Dopiero wtedy strumień jest rozpakowywany, a skan nagłówka zatrzymuje się na żądanym członku i jego następcy, zamiast budować pełną tabelę członków. Jednocześnie przetrzymywany jest jeden zdekodowany strumień obiektów, co jest właściwym kompromisem, gdy gałąź drzewa stron grupuje się w pojedynczy ObjStm; nasz tekst o dekodowaniu strumieni obiektów i predyktorów w Delphi opisuje, co dzieje się w środku tego kroku rozpakowywania (§7.5.7)

var
  Reader: TPdfSparseDictionaryReader;
  Generation: Integer;
  Dict: AnsiString;
begin
  { jeden przetrzymywany indeks, wiele odczytów świadomych generacji }
  Reader := TPdfSparseDictionaryReader.Create(Source);
  try
    if Reader.Valid and
       Reader.ReadLatestDictionary(PageObjectNumber, Generation, Dict) then
      HandlePage(PageObjectNumber, Generation, Dict);
  finally
    Reader.Free;  { Source pozostaje twój }
  end;
end;

Gdzie cache przestaje składać obietnice

Ten indeks jest migawką i warto to powiedzieć wprost. Sekcje są parsowane raz, w Initialize; jeśli strumień źródłowy zostanie potem zmodyfikowany, każdy zbuforowany wpis jest nieaktualny, a klasa tego nie zauważy. TPdfSparseDictionaryReader trzyma indeks przez należący do wywołującego czas życia źródła, co jest dokładnie tym, czego chce rekurencyjny spacer po drzewie stron, i dokładnie tym, czego nie wolno robić w poprzek przepisania pliku. Cache wpisów to płaska tablica przeszukiwana liniowo, która przechowuje też wyniki negatywne, więc kilkaset wyszukań jest tanich, a kilkaset tysięcy już nie. ReadDictionary wymaga dokładnego dopasowania generacji, podczas gdy ReadLatestDictionary rozwiązuje aktywną, i ta różnica jest zamierzona: rozwiązywanie odwołań potrzebuje pierwszej, inspekcja katalogu — drugiej. Tam, gdzie tych granic nie da się dotrzymać, otaczające moduły wracają do starszego parsera całego pliku zamiast zawężać zbiór plików, które wciąż działają, to samo podejście stosujemy przy strumieniowaniu dużych PDF na żądanie

Regresje międzykompilatorowe pokrywają to samo zachowanie na wszystkich trzech toolchainach, w tym asercję, że źródło o rozmiarze 2 MiB nigdy nie zobaczy pojedynczego odczytu większego niż 1 MiB. Jeśli utrzymujesz kod Delphi, C++Builder albo Lazarus, który bezpośrednio dotyka struktury PDF, i masz dość płacenia kosztów parsowania całego pliku za cztery słowniki, rzadki indeks i publiczny szew wokół niego znajdziesz w komponencie PDFiumPas Delphi PDFium