The cross-reference says where every object is. In PDF 1.5 to 2.0 it can take two forms, a text table or a binary stream, and objects can live in two places, standing alone in the file or packed in an object stream. A reader must handle both forms, files that mix them, and the chain of sections that incremental updates leave behind.
The cross-reference table
The table form starts with the keyword xref on its own line and is
followed by the trailer. It can only describe objects that
stand alone in the file.
Subsections
The table is one or more subsections. Each starts with a line of two integers: the first object number and the number of entries. Then come the entries, one for each object in the run:
xref
0 1
0000000000 65535 f
3 2
0000025325 00000 n
0000025518 00002 n
23 1
0000025635 00000 n A new file usually has one subsection, 0 Size. Updates usually have
several, one for each run of changed objects.
Entries
Every entry is exactly 20 bytes, so a reader can find the entry for any object by arithmetic:
| Bytes | Content |
|---|---|
| 0–9 | Ten decimal digits: for an in-use entry the byte offset of the object, for a free entry the next free object number |
| 10 | A space |
| 11–15 | Five decimal digits: the generation number |
| 16 | A space |
| 17 | n in use, or f free |
| 18–19 | A two-byte line end: space CR, space LF, or CR LF |
The offset counts from the start of the file to the first digit of the object’s
n g obj line. Some writers end entries with a single byte; readers
that read the table line by line cope with that, readers that do the arithmetic
do not.
The free list
Free entries form a linked list. Object 0 is always free, with generation
65535, and heads the list: its offset field holds the number of the first free
object, whose own entry holds the next, and so on back to 0. A free entry’s
generation is the one to use if its number is used again. An entry with generation
65535 is never reused. Many writers give every free entry 0000000000
65535 f without linking them, and readers accept this.
The trailer
With a table, trailer and a dictionary follow it. With a
cross-reference stream the same keys are in the stream’s dictionary.
| Key | Type | Since | Meaning |
|---|---|---|---|
Size | integer | 1.0 | Required. One more than the highest object number in the file, across every section |
Prev | integer | 1.0 | The byte offset of the previous cross-reference section; present only when there is one |
Root | reference | 1.0 | Required. The catalog |
Encrypt | dictionary | 1.1 | Required in an encrypted file: the encryption dictionary, usually as a reference |
Info | reference | 1.0 | The document information dictionary. Required when the catalog has PieceInfo; in PDF 2.0 only its dates are still current |
ID | array | 1.1 | Two byte strings, each usually 16 bytes: a permanent identifier set when the file was first written, and one that changes with each save. Required when Encrypt is present, and in every PDF 2.0 file. Must be direct when the file is encrypted |
XRefStm | integer | 1.5 | Only in the trailer of a table in a hybrid file: the offset of a cross-reference stream |
Readers take Root, Encrypt, Info and
ID from the newest trailer, the one found first.
startxref
The last lines of the file are startxref, a byte offset and
%%EOF. The offset points at the newest cross-reference section: the
x of xref for a table, or the start of n g obj
for a cross-reference stream. In a linearized
file there is also a startxref near the start, which readers ignore
unless they read the file as linearized.
Cross-reference streams
From PDF 1.5 a cross-reference section can be a stream. It does the work of both the table and the trailer, is compressed like any stream, and can point at objects inside object streams. It is an ordinary indirect object, with a number of its own, and its own entry should be in it.
| Key | Type | Since | Meaning |
|---|---|---|---|
Type | name | 1.5 | Required. XRef |
Size | integer | 1.5 | Required. One more than the highest object number in this section and all earlier ones, as in a trailer |
Index | array | 1.5 | Pairs of integers, the first object number and the count of each subsection, in ascending order. Default [0 Size] |
Prev | integer | 1.5 | The offset of the previous cross-reference section |
W | array | 1.5 | Required. Three integers, the width in bytes of each field of an entry |
Root, Info, ID, Encrypt | 1.5 | As in the trailer | |
Length, Filter, DecodeParms, DL | 1.5 | As in any stream; the filters must be general ones, not Crypt | |
F, FFilter, FDecodeParms | 1.5 | Not to be used: the data may not be external. PDF 2.0 deprecates them here |
Every value in the dictionary must be direct, since a reader must understand it before it can find any other object, and the stream is never encrypted, even in an encrypted file.
Entries
The decoded data is a run of entries, all the same size, in the order given by
Index. Each entry has three fields of the widths in W,
each a big-endian unsigned integer:
| Field 1, type | Field 2 | Field 3 | Meaning |
|---|---|---|---|
| 0 | The number of the next free object | The generation to use if this number is used again | A free object, as f in a table |
| 1 | The byte offset of the object in the file | The generation number | An object that stands alone, as n in a table |
| 2 | The object number of the object stream that holds it (its generation is 0) | The index of the object in that object stream | An object in an object stream |
A width of 0 means the field is not stored and takes its default: a missing type
is 1, and a missing generation 0. Other type values are reserved; a reader should
treat an entry of an unknown type as a reference to the null object. A writer
picks widths big enough for the largest value, so a file under 64 KB can use
W [1 2 1], and a big one W [1 4 2] or
[1 3 1].
An example
The last object of a small PDF 1.7 file of 3,527 bytes:
16 0 obj
<</Filter/FlateDecode/Type/XRef/W[1 2 2]/Size 17/Root 14 0 R/Info 11 0 R
/ID[<57A984D8D8017E7021C18DB41CC7EE07><57A984D8D8017E7021C18DB41CC7EE07>]
/DecodeParms<</Columns 5/Predictor 12>>/Length 87 >>
stream
…
endstream
endobj
startxref
3180
%%EOFTo read it:
- There is no
Index, so it covers objects 0 to 16, 17 entries. W [1 2 2]: each entry is 1 + 2 + 2 = 5 bytes, so the decoded data is 17 × 5 = 85 bytes.- Inflate the 87 stored bytes. The predictor is PNG (12) with
Columns 5, so the inflated data is 17 rows of 6 bytes, a filter-type byte and 5 data bytes, 102 bytes in all. Undo the predictor row by row. - Read each 5-byte entry: one byte of type, two of field 2, two of field 3.
Entry 0 is type 0. Object 3 starts at offset 15 in this file, so its entry is
01 00 0F 00 00: type 1, offset 0x000F, generation 0. An entry02 00 0A 00 03would be type 2: the fourth object (index 3) in object stream 10.
The file’s own object 10 is an object stream with /N 5, so five of
the 17 entries are type 2 entries that point into it.
Object streams
An object stream, from PDF 1.5, holds several indirect objects in one stream, so they are compressed together. Its dictionary has:
| Key | Type | Since | Meaning |
|---|---|---|---|
Type | name | 1.5 | Required. ObjStm |
N | integer | 1.5 | Required. The number of objects in the stream |
First | integer | 1.5 | Required. The offset in the decoded data of the first object, after the header |
Extends | reference | 1.5 | Another object stream that this one continues, forming a collection |
Length, Filter, DecodeParms … | 1.5 | As in any stream; may be encrypted like other streams |
The decoded data begins with a header of N pairs of integers, written
as text: an object number and the offset of that object, counted from
First. The objects follow from First, written bare, without
obj and endobj:
11 0 12 48 13 62
<</Type/Font/Subtype/Type1/BaseFont/Helvetica>>
[0 0 612 792]
<</Type/ExtGState/CA 0.5>>/N 3 and /First 17: objects 11, 12 and 13 at offsets 0, 48 and 62 after the 17-byte headerA type 2 cross-reference entry gives the object stream and the index of the object in it, here 0, 1 or 2. The header’s object numbers should match. The objects are in the order of the header.
What an object stream may not hold:
- streams, since a stream must be an indirect object of its own;
- objects whose generation is not 0;
- the encryption dictionary, which a reader needs before it can decrypt the object stream;
- the object holding the object stream’s own
Length; - in a linearized file, the linearization dictionary, the document catalog and the page objects.
An object stream may not hold another object stream, and a cross-reference stream is never in one. An object in an object stream may still be replaced in an incremental update by a normal object of the same number. Strings inside an object stream are not encrypted separately; the whole stream is encrypted.
Hybrid-reference files
A hybrid file can be read both by readers that know only tables and by readers of
PDF 1.5 and later. Its newest section is a table with a trailer, and the trailer has
XRefStm, the offset of a cross-reference stream.
- The table lists the objects that stand alone. The objects that are in object streams appear in it as free, or not at all.
- The stream at
XRefStmlists the objects in object streams, as type 2 entries. It may also list other objects. - The chain of older sections goes through the table’s trailer and its
Prev.
A reader of PDF 1.5 or later reads a section like this:
- Read the table at the
startxrefoffset. - Read the stream at
XRefStmand use its entries for the object numbers it covers, which the table does not give. - Then follow the trailer’s
Prevto older sections.
An older reader ignores XRefStm and the object streams, so it never sees
the objects in them. The file must be written so that the document still works without
them: those objects should be things an older reader would ignore anyway.
Sections from several updates
Each incremental update adds a section, and Prev links them, newest
first. A reader reads them all, newest first, and keeps the first entry it finds for
each object number. A free entry in a newer section hides an older in-use entry of
the same number. When Size differs between sections, the newest
counts.
A Prev that points at itself or at a section already read would make a
naive reader loop for ever; careful readers keep a list of the offsets they have
read.