Разреженный ленивый индекс объектов PDF в Delphi

Вам нужен один словарь из PDF на 2 ГБ, а инструмент сперва разворачивает всю таблицу перекрёстных ссылок в массив размером по трейлерному /Size. PDFiumPas заменяет этот шаг разреженным ленивым индексом объектов: он хранит только дескрипторы секций xref, находит один номер объекта по требованию через ограниченные окна и кэширует лишь те записи, которых вы действительно коснулись

Прежняя форма этого кода в FPdfCompress была честной, но дорогой. ApplyDefaultOpenAction читала весь файл в один TBytes, а затем выделяла плотный массив TPdfActiveXrefEntries со слотом на каждый номер объекта вплоть до /Size. На масштабе ломались две вещи. Стоимость чтения росла линейно с размером документа, даже когда вызывающему были нужны четыре словаря, а плотный массив конфликтовал с бюджетом парсера: TPdfParserResourceBudget.Default задаёт MaxObjects равным 4 000 000, поэтому вполне корректный файл, у которого старший номер объекта выше этого потолка, отклонялся по соображениям памяти, а не корректности

Почему публичный API PDFium не отвечает на этот вопрос?

Потому что информация существует внутри PDFium, но никогда не пересекает границу C. CPDF_Parser хранит таблицу перекрёстных ссылок, членство в потоках объектов и приоритет ревизий внутри себя, но опубликованные заголовки не дают точки входа, которая принимает номер объекта и возвращает его сырое смещение, его поколение, выигравшую ревизию или поток ObjStm, в котором он живёт. Сторона записи столь же закрыта: FPDF_SaveAsCopy и FPDF_SaveWithVersion вручают вам лишь колбэк последовательной записи. Поэтому любой байтовый патч каталога после нативного сохранения приходится строить на слое 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 МиБ — там находится startxref, — а каждое последующее чтение объекта использует объектное окно в 1 МиБ. Потолок сырого потока — 64 МиБ, а одна строка 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. В этом весь смысл переписывания: значение размера трейлера переносится дальше как метаданные и используется при записи инкрементальной ревизии, но оно никогда не управляет выделением памяти. Регрессионный набор фиксирует это фикстурой, у которой дерево страниц живёт в объектах 1 000 000 000 и 1 000 000 001 при трейлере, объявляющем /Size 1000000002. Прежняя плотная реализация отказывала такому файлу; разреженный индекс находит обе ссылки и сохраняет объявленный размер в выходном трейлере

Гибридные ревизии, цепочки /Prev и охраняющие их проверки

Приоритет ревизий — то место, где наивный ленивый индекс ошибается. PDFiumPas проходит цепочку от startxref в порядке от новейшей к старшей и останавливает поиск на первой секции, которая отвечает, что воспроизводит правило приоритета без материализации объединённой таблицы. Файлы гибридных ссылок (§7.5.8.4) обрабатываются внутри классической ветки: когда трейлер несёт /XRefStm, дополнительная секция потока регистрируется перед классической секцией, которая на неё сослалась, поэтому сжатые объекты, невидимые для обычной таблицы, всё равно находятся, а классические записи сохраняют свой статус. Более старые ревизии затем обходятся через /Prev

Этот обход ограничивают две проверки, и обе важны на повреждённых файлах. Каждое посещённое смещение записывается, поэтому /Prev, указывающий обратно в цепочку, завершает обход вместо зацикливания, а глубина обхода ограничена MaxRecursionDepth, по умолчанию равным 1024. Флаг шифрования накапливается по всей цепочке, а не читается только из новейшего трейлера, потому что документ, у которого в свежем трейлере нет /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;  { Source остаётся вашим }
  end;
end;

Где кэш перестаёт давать обещания

Индекс — это снимок, и об этом стоит сказать прямо. Секции разбираются один раз в Initialize; если нижележащий поток изменится после этого, каждая кэшированная запись устареет, и класс этого не заметит. TPdfSparseDictionaryReader держит индекс в течение принадлежащего вызывающему времени жизни источника — именно это нужно рекурсивному обходу дерева страниц и именно этого нельзя делать поверх перезаписи. Кэш записей — плоский массив с линейным поиском, и он хранит также отрицательные результаты, поэтому несколько сотен поисков дёшевы, а несколько сотен тысяч — уже нет. ReadDictionary требует точного совпадения поколения, тогда как ReadLatestDictionary находит активное, и разница намеренная: разрешению ссылок нужно первое, осмотру каталога — второе. Там, где эти границы невозможно соблюсти, окружающие модули откатываются к устаревшему парсеру всего файла вместо того, чтобы сужать набор работающих файлов, — приём, который мы также используем для потоковой передачи больших PDF по требованию

Кросс-компиляторные регрессии покрывают одно и то же поведение на всех трёх тулчейнах, включая утверждение, что источник на 2 МиБ никогда не видит ни одного чтения больше 1 МиБ. Если вы сопровождаете код на Delphi, C++Builder или Lazarus, который напрямую касается структуры PDF, и устали платить за разбор всего файла ради четырёх словарей, разреженный индекс и публичный шов вокруг него поставляются в составе компонента PDFiumPas Delphi PDFium