Fusión rápida de PDF en Delphi: referencias por bytes

Fusionar PDFs suena como si debiera ser barato. El contenido de la página ya está armado, las fuentes ya están incrustadas, las imágenes ya están comprimidas. En principio, una fusión es solo contabilidad, renumerar los objetos para que los espacios de numeración de dos archivos dejen de chocar, unir los árboles de páginas, corregir la tabla de referencias cruzadas y escribir. En la práctica, la mayoría del código de fusión desperdicia esa ventaja. Para cada objeto en cada archivo de entrada hace un análisis completo hasta un árbol de objetos tokenizados, modifica un par de referencias indirectas y luego serializa el árbol de vuelta a bytes. El análisis y la reserialización son las partes caras, y para la gran mayoría de los objetos producen una secuencia de bytes casi idéntica a la que entró

PDFlibPas es un motor PDF nativo en Object Pascal para Delphi y C++Builder, y su ruta de fusión rápida existe para omitir ese ciclo de ida y vuelta siempre que sea demostrablemente seguro. La idea es acotada, pero rinde en conjuntos completos de documentos: para un objeto sin modificar que no sea de tipo stream, tome los bytes fuente originales tal cual y haga una sola reescritura a nivel de bytes de las referencias indirectas que contiene, convirtiendo cada N G R en (N+Offset) G R. Sin tokenizador, sin árbol de objetos, sin serializador. Este artículo recorre dónde es legal ese atajo, la máquina de estados del analizador que hace la reescritura sin corromper nada, por qué la fusión de marcadores necesitó un mecanismo completamente distinto y cómo, al mismo tiempo, se reconstruyó la ruta de fusión ordinaria de cuadrática a lineal

Por qué la renumeración de objetos es el verdadero costo de una fusión

Cada PDF lleva su propio espacio de numeración de objetos. El archivo A tiene objeto 1, objeto 2, y así sucesivamente; el archivo B tiene su propio objeto 1, objeto 2, y así sucesivamente. No puede colocar los objetos de B en el archivo A sin cambios, porque los números chocarían y toda referencia indirecta dentro de B resolvería ahora al objeto equivocado. La solución es un desplazamiento: si A termina con un conteo de objetos Offset, entonces el objeto N de B pasa a ser el objeto N+Offset en la salida, y toda referencia N G R que aparezca en cualquier parte de los objetos de B debe desplazarse a (N+Offset) G R para coincidir

Ese desplazamiento es todo el trabajo semántico de fusionar el cuerpo. Las correcciones del árbol de páginas y la fusión de AcroForm son ediciones pequeñas y acotadas sobre un puñado de objetos. El trabajo grande es reescribir referencias a través de miles de objetos, y la forma ingenua de hacerlo es analizar cada objeto para encontrar las referencias estructuralmente. MergeFileListFast de PDFlibPas toma la visión opuesta: las referencias también se pueden encontrar en los bytes crudos, si se tiene cuidado con los contextos donde una secuencia dígito-espacio-dígito-espacio-R no es una referencia. Omitir el análisis, desplazar en el lugar, y el costo por objeto colapsa a un solo recorrido lineal de bytes que de todos modos se iban a copiar

Cuándo es seguro reutilizar bytes de origen

La ruta de bytes solo se toma cuando las tres condiciones se cumplen para el objeto que se copia desde un documento posterior. Si falla cualquiera de ellas, el objeto vuelve por la ruta completa de decodificación y reserialización, así que la corrección siempre gana sobre la velocidad:

Doc2.IsChangedObject(X) es False. Si el motor de fusión ya modificó el objeto en memoria, por ejemplo un objeto de página cuyo /Parent fue redirigido, el árbol en memoria es la fuente de verdad y los bytes originales están desactualizados. Solo califican los objetos intactos
Los bytes de origen no contienen la palabra clave stream. El cuerpo de un objeto stream es binario opaco enmarcado por stream/endstream, y un análisis ingenuo de referencias sobre datos comprimidos o cifrados encontraría con gusto y dañaría patrones de bytes que parecen referencias. Los objetos stream conservan la ruta original consciente de streams
Los bytes de origen no contienen ni /StructTreeRoot ni /StructElem. En el perfil rápido, el árbol de estructura del PDF etiquetado se descarta en lugar de fusionarse, así que esos objetos deben pasar por la ruta de decodificación, donde el motor puede anularlos de forma deliberada

La decisión vive en el bucle de copia por objeto. Cuando las tres comprobaciones pasan, los bytes del objeto van directos a ShiftIndRefsInSource y luego al escritor; de lo contrario, los bytes se descartan y el objeto se reconstruye con GetObject, se desplaza con ShiftIndRef y se serializa. Vale la pena ver la estructura de esa rama, porque el orden de las comprobaciones es lo que la mantiene segura:

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;

Un ObjectData vacío es la señal de que la ruta de bytes rechazó el objeto. Ese sentinela único mantiene las rutas rápida y lenta sin desviarse: hay exactamente un lugar que decide y exactamente una ruta de retroceso

La máquina de estados para desplazar referencias y sus casos límite

Una reescritura a bytes de referencias indirectas es engañosamente fácil de hacer mal, porque R y secuencias de dígitos aparecen por todo un objeto PDF en contextos que no son referencias. ShiftIndRefsInSource es un pequeño analizador escrito a mano que recorre los bytes una sola vez y solo reescribe un número cuando va seguido, con espacio en blanco PDF entre los tokens, por otro número y luego por un delimitador R. Los atajos baratos van primero: si el desplazamiento es cero o el origen está vacío, los bytes se devuelven intactos sin entrar al analizador

La corrección del analizador depende de reconocer los contextos en los que una secuencia con forma de referencia debe dejarse en paz. Estos son los límites más fáciles de pasar por alto, y cada uno se maneja de forma explícita:

Cadenas literales delimitadas por ( y ) se copian de forma literal, siguiendo la profundidad de anidación y respetando el escape con barra invertida para que un paréntesis escapado no desajuste el conteo de profundidad. Una cadena como (see object 3 0 R for details) contiene un patrón clásico de referencia que en realidad solo es prosa, y debe sobrevivir byte por byte
Cadenas hexadecimales delimitadas por < y > se pasan sin interpretación. Los bytes 52 dentro de una cadena hexagonal son el código ASCII de R, y un analizador que tratara la carga útil hexagonal como texto podría fabricar una referencia fantasma. La apertura << de un diccionario se detecta primero para que no se confunda un diccionario con una cadena hexadecimal
Objetos nombre que empiezan con / se consumen completos, desde la barra hasta el siguiente espacio en blanco o delimitador. Sin esto, un nombre como /R, una clave de recurso común, podría leerse como la R de una referencia
Comentarios introducidos por % corren hasta el final de la línea y se omiten como texto opaco
La prueba número-luego-R es estricta. Una referencia solo se reconoce como N espacio en blanco G espacio en blanco R, con la R terminada por espacio en blanco, un delimitador o el final de la entrada. Si falta el número de generación, o si una R va seguida por una letra, los dígitos se emiten sin cambios. Eso protege al entero de /Length 1234 y a los cuatro números de un MediaBox para que no se incrementen en silencio

El núcleo de esa prueba estricta se lee casi exactamente como lo dice la oración de la especificación:

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;

Solo se reescribe el número de objeto; el número de generación y el espacio en blanco exacto original entre tokens se copian tal cual, así que la salida es idéntica a la entrada a nivel de bytes salvo por el entero que realmente debía cambiar. Esa precisión es todo el punto, es lo que hace que reutilizar bytes de origen sea equivalente a una reserialización completa, no solo parecido. El comportamiento está cubierto por un conjunto acotado de pruebas unitarias que ejercitan referencias sueltas, referencias dentro de arreglos, números que no son referencias, cadenas literales, cadenas hexadecimales y números de generación no cero con un desplazamiento aplicado

Por qué los marcadores no pudieron reutilizar AppendOutline

Fusionar los marcadores de varios documentos en un solo árbol de esquema parece un trabajo para el ayudante existente AppendOutline, que ya sabe cómo injertar los marcadores de nivel superior de un documento sobre otro. Aquí es la herramienta equivocada, y la razón es un desajuste sutil de capas. AppendOutline ubica el último marcador de nivel superior actual recorriendo el lector sobre los bytes originales del archivo. Pero la ruta rápida de fusión organiza sus ediciones en un búfer de nuevos objetos mediante ChangeObject; el lector nunca ve esas ediciones. Encadene tres documentos o más y cada inserción vuelve a apuntar el último marcador original del primer documento al documento más nuevo, así que los marcadores de todos los documentos intermedios quedan fuera de la cadena, solo el /Count acumulado sigue correcto, lo que hace que el error sea fácil de pasar por alto hasta que alguien abre el panel de marcadores

La ruta rápida lo resuelve con una inyección en dos fases, basada en metadatos, que nunca vuelve a recorrer el lector. Una primera pasada sobre todas las entradas recopila, por documento, el objeto raíz del esquema y sus números de generación, los números del primer y último marcador de nivel superior, y el /Count de la raíz. A partir de ese resumen, el código calcula los números globales de objeto de cada enlace que necesita forjar, cada /Parent de nivel superior de documento hacia la raíz compartida, el /Prev del primer marcador hacia el último del documento anterior, el /Next del último marcador hacia el primero del siguiente, usando pura aritmética de números de objeto. Detrás de esto hay una restricción de orden de escritura: los objetos del primer documento se escriben antes de que siquiera se abra cualquier documento siguiente, así que todas las ediciones de esquema del primer documento, el /Count y /Last de la raíz y el /Next del antiguo último marcador, tienen que poder expresarse como aritmética que no necesita tener a mano ningún documento posterior. Las ediciones de cada documento siguiente se aplican en el lugar después de abrirlo pero antes de escribirlo, así que pasan por la misma ruta de cambio de objeto

La invariante de alineación del desplazamiento que lo une todo

Tanto el desplazamiento de referencias como la inyección de marcadores dependen de una invariante aritmética, y es la suposición más frágil de todo el diseño. Una referencia inyectada en un documento siguiente se escribe como el número global de objeto objetivo menos el Offset de ese documento, de modo que cuando más tarde el objeto se desplaza con ShiftIndRef(Offset) el valor cae en el número global previsto. El primer documento obtiene Offset = 0 y usa números globales directamente. Para que esa resta sea correcta, la secuencia de desplazamientos en curso usada durante la inyección tiene que coincidir con la secuencia usada cuando los objetos se escriben al final

Sí coincide, por una propiedad de cómo funcionan las fusiones de páginas y formularios: AddPages, AddFields y AddFieldFonts solo modifican los objetos existentes del primer documento, nunca agregan nuevos. Así, el conteo de objetos del primer documento permanece sin cambios durante la etapa de fusión de páginas, y el desplazamiento de cada documento siguiente, la suma de los conteos de objetos de todos los documentos anteriores, se mantiene estable desde la inyección hasta la escritura final. Rompa eso, introduzca una etapa que cree un objeto nuevo a mitad de la fusión, y todas las referencias de páginas y marcadores aguas abajo quedarían desplazadas por la cantidad de objetos que añadió. La invariante es silenciosa, pero sostiene todo

Tres puntos de entrada sobre un solo motor

La ruta rápida no es una bifurcación del código de fusión. En la misma línea de trabajo, el motor a nivel de bytes se factorizó en una sola rutina interna, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), y las API públicas quedaron como envoltorios delgados que eligen dos banderas:

MergeFileListFast llama al motor con la preservación del árbol de estructura desactivada, la ruta más ligera, descartando el árbol del PDF etiquetado para que la ruta de bytes aplique a la mayor cantidad de objetos
MergeFileList lo llama con la preservación activada, de modo que el árbol de estructura sobreviva y el resultado siga siendo un PDF etiquetado utilizable. Esta ruta ordinaria también hereda la fusión de marcadores y formularios de varios documentos
MergeFileListStrict activa el modo estricto: la primera pasada de metadatos se detiene en la primera entrada que no informa una fusión limpia, así que solo se incluyen los documentos reunidos antes del archivo defectuoso, en lugar de omitirlo y continuar

Unificar las rutas también permitió reconstruir la fusión ordinaria a partir de un bucle por pares O(N²), fusionar el archivo uno y dos, fusionar ese resultado con el tres y así sucesivamente, volviendo a analizar el acumulador en crecimiento en cada paso, hacia una única pasada lineal que abre cada entrada una sola vez. Los dos puntos de entrada tradicionales de dos archivos y dos flujos, MergeFiles y MergeStreams, no se tocan y siguen disponibles para quienes realmente quieren una fusión por pares

Una nota honesta sobre el comportamiento del árbol de estructura, porque nos hizo tropezar en la suite de pruebas. El "descartar" de la ruta rápida no es total, elimina la referencia del catálogo del primer documento a /StructTreeRoot, pero el objeto del árbol de estructura todavía se escribe como huérfano. Así que los bytes de la salida rápida todavía contienen la cadena /StructTreeRoot, y no puede distinguir la salida rápida de la ordinaria buscando esa cadena, la diferencia real es si el catálogo todavía llega al árbol de estructura, que es lo que determina si el archivo sigue siendo un PDF etiquetado navegable

Cuándo elegir cada ruta

La ruta de bytes es una optimización de rendimiento para ensamblar muchos documentos cuando no necesita conservar el árbol de estructura del PDF etiquetado, como al agrupar informes, generar estados de cuenta o concatenar por lotes. Medida sobre fusiones repetidas de conjuntos de entrada medianos y grandes, la reutilización de bytes recortó aproximadamente entre cuatro y trece por ciento del tiempo de reloj, según la mezcla de objetos, sin nuevos fallos en entradas pequeñas o malformadas, porque cualquier objeto que el analizador no pueda demostrar seguro vuelve al análisis completo. Si sí necesita intacto el árbol de estructura para accesibilidad, use la ruta ordinaria de fusión de PDF etiquetado, que lo conserva; y si trabaja con archivos únicos muy grandes en lugar de muchas entradas, las técnicas de copia de bytes descritas en la pieza complementaria sobre fusión y división de PDF grandes con acceso directo al archivo aplican la misma filosofía de copiar bytes y evitar el árbol de objetos completo a escala de archivo

Las rutinas de fusión y sus variantes rápida y estricta forman parte de la PDFlibPas Delphi PDF Library, cuya documentación contiene la referencia completa para la API de listas de archivos y las opciones de fusión descritas aquí