lib/pdf/src/xref.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const filter = @import("filter/root.zig");
4 const object = @import("object.zig");
5
6 const XrefFormatError = error{
7 MissingStartxref,
8 MissingXrefTable,
9 MissingTrailerRoot,
10 BadXrefEntry,
11 BadXrefStream,
12 };
13
14 pub const XrefError = XrefFormatError || object.ParseError || filter.Error;
15
16 pub const Compressed = struct {
17 container: u32,
18 index: u32,
19 };
20
21 pub const Location = union(enum) {
22 offset: usize,
23 compressed: Compressed,
24 };
25
26 pub const Table = struct {
27 locations: std.AutoHashMapUnmanaged(u32, Location) = .empty,
28 root: object.Reference,
29
30 pub fn deinit(self: *Table, allocator: std.mem.Allocator) void {
31 self.locations.deinit(allocator);
32 }
33 };
34
35 pub fn parse(
36 allocator: std.mem.Allocator,
37 arena: std.mem.Allocator,
38 filter_storage: *filter.Storage,
39 bytes: []const u8,
40 ) XrefError!Table {
41 var table = Table{ .root = .{ .number = 0, .generation = 0 } };
42 errdefer table.deinit(allocator);
43 var root: ?object.Reference = null;
44 var offset: ?usize = try startxref(bytes);
45 var guard: usize = 0;
46 while (offset) |section_offset| {
47 guard += 1;
48 if (guard > 64) break;
49 offset = try parseSection(
50 allocator,
51 arena,
52 filter_storage,
53 bytes,
54 section_offset,
55 &table,
56 &root,
57 );
58 }
59 table.root = root orelse return error.MissingTrailerRoot;
60 return table;
61 }
62
63 fn startxref(bytes: []const u8) XrefError!usize {
64 const window_start = bytes.len -| 256;
65 const window = bytes[window_start..];
66 const found = std.mem.lastIndexOf(u8, window, "startxref") orelse return error.MissingStartxref;
67 var parser = object.Parser.init(bytes, window_start + found + "startxref".len);
68 return parser.parseUnsigned(usize) catch error.MissingStartxref;
69 }
70
71 fn parseSection(
72 allocator: std.mem.Allocator,
73 arena: std.mem.Allocator,
74 filter_storage: *filter.Storage,
75 bytes: []const u8,
76 section_offset: usize,
77 table: *Table,
78 root: *?object.Reference,
79 ) XrefError!?usize {
80 if (section_offset >= bytes.len) return error.MissingXrefTable;
81 var parser = object.Parser.init(bytes, section_offset);
82 if (parser.atKeyword("xref")) {
83 return parseTableSection(
84 allocator,
85 arena,
86 filter_storage,
87 bytes,
88 &parser,
89 table,
90 root,
91 );
92 }
93 return parseStreamSection(
94 allocator,
95 arena,
96 filter_storage,
97 bytes,
98 section_offset,
99 table,
100 root,
101 );
102 }
103
104 fn register(allocator: std.mem.Allocator, table: *Table, number: u32, location: Location) XrefError!void {
105 const slot = table.locations.getOrPut(allocator, number) catch return error.OutOfMemory;
106 if (!slot.found_existing) slot.value_ptr.* = location;
107 }
108
109 const TableEntry = struct {
110 number: u32,
111 offset: usize,
112 };
113
114 fn parseTableSection(
115 allocator: std.mem.Allocator,
116 arena: std.mem.Allocator,
117 filter_storage: *filter.Storage,
118 bytes: []const u8,
119 parser: *object.Parser,
120 table: *Table,
121 root: *?object.Reference,
122 ) XrefError!?usize {
123 try parser.expectKeyword("xref");
124 var scratch: std.ArrayList(TableEntry) = .empty;
125 defer scratch.deinit(allocator);
126 for (bytes[parser.pos..]) |_| {
127 if (parser.atKeyword("trailer")) break;
128 const first = try parser.parseUnsigned(u32);
129 const count = try parser.parseUnsigned(u32);
130 parser.skipWhitespace();
131 var index: u32 = 0;
132 while (index < count) : (index += 1) {
133 if (parser.pos + 18 > bytes.len) return error.BadXrefEntry;
134 const entry = bytes[parser.pos .. parser.pos + 18];
135 const entry_offset = std.fmt.parseUnsigned(usize, entry[0..10], 10) catch return error.BadXrefEntry;
136 const kind = entry[17];
137 const number = std.math.add(u32, first, index) catch return error.BadXrefEntry;
138 if (kind == 'n') scratch.append(allocator, .{ .number = number, .offset = entry_offset }) catch return error.OutOfMemory;
139 parser.pos += 18;
140 while (parser.pos < bytes.len and object.whitespace(bytes[parser.pos])) parser.pos += 1;
141 }
142 }
143 if (!parser.atKeyword("trailer")) return error.BadNumber;
144 try parser.expectKeyword("trailer");
145 const trailer = switch (try parser.parseValue(arena)) {
146 .dict => |dict| dict,
147 else => return error.MissingXrefTable,
148 };
149 if (trailer.get("XRefStm")) |value| {
150 switch (value) {
151 .integer => |stream_offset| if (stream_offset >= 0) {
152 _ = try parseStreamSection(
153 allocator,
154 arena,
155 filter_storage,
156 bytes,
157 @intCast(stream_offset),
158 table,
159 root,
160 );
161 },
162 else => {},
163 }
164 }
165 for (scratch.items) |entry| try register(allocator, table, entry.number, .{ .offset = entry.offset });
166 applyRoot(trailer, root);
167 return previousOffset(trailer);
168 }
169
170 fn parseStreamSection(
171 allocator: std.mem.Allocator,
172 arena: std.mem.Allocator,
173 filter_storage: *filter.Storage,
174 bytes: []const u8,
175 section_offset: usize,
176 table: *Table,
177 root: *?object.Reference,
178 ) XrefError!?usize {
179 if (section_offset >= bytes.len) return error.MissingXrefTable;
180 var parser = object.Parser.init(bytes, section_offset);
181 _ = parser.parseUnsigned(u32) catch return error.BadXrefStream;
182 _ = parser.parseUnsigned(u16) catch return error.BadXrefStream;
183 parser.expectKeyword("obj") catch return error.BadXrefStream;
184 const dict = switch (try parser.parseValue(arena)) {
185 .dict => |dict| dict,
186 else => return error.BadXrefStream,
187 };
188 const type_value = dict.get("Type") orelse return error.BadXrefStream;
189 switch (type_value) {
190 .name => |name| if (!std.mem.eql(u8, name, "XRef")) return error.BadXrefStream,
191 else => return error.BadXrefStream,
192 }
193 const length = directUnsigned(dict, "Length") orelse return error.BadXrefStream;
194 const data_start = parser.streamStart() catch return error.BadXrefStream;
195 if (data_start + length > bytes.len) return error.BadXrefStream;
196 const filter_name = try filter.nameOf(try filter.single(dict.get("Filter") orelse .null));
197 const params = try filter.paramsOf(try filter.single(dict.get("DecodeParms") orelse .null));
198 const decoded = try filter.bytesFromStream(
199 filter_storage,
200 filter_name,
201 params,
202 bytes[data_start .. data_start + length],
203 );
204 defer filter_storage.reset();
205 const widths = try fieldWidths(dict);
206 const size = directUnsigned(dict, "Size") orelse return error.BadXrefStream;
207 var cursor: usize = 0;
208 if (dict.get("Index")) |index_value| {
209 const items = switch (index_value) {
210 .array => |array| array,
211 else => return error.BadXrefStream,
212 };
213 if (items.len % 2 != 0) return error.BadXrefStream;
214 var pair: usize = 0;
215 while (pair < items.len) : (pair += 2) {
216 const first = valueUnsigned(items[pair]) orelse return error.BadXrefStream;
217 const count = valueUnsigned(items[pair + 1]) orelse return error.BadXrefStream;
218 try decodeEntries(allocator, table, decoded, &cursor, widths, first, count);
219 }
220 } else {
221 try decodeEntries(allocator, table, decoded, &cursor, widths, 0, size);
222 }
223 applyRoot(dict, root);
224 return previousOffset(dict);
225 }
226
227 fn fieldWidths(dict: object.Dict) XrefError![3]usize {
228 const value = dict.get("W") orelse return error.BadXrefStream;
229 const items = switch (value) {
230 .array => |array| array,
231 else => return error.BadXrefStream,
232 };
233 if (items.len != 3) return error.BadXrefStream;
234 var widths: [3]usize = undefined;
235 for (items, 0..) |item, index| {
236 widths[index] = switch (item) {
237 .integer => |raw| if (raw >= 0 and raw <= 8) @intCast(raw) else return error.BadXrefStream,
238 else => return error.BadXrefStream,
239 };
240 }
241 if (widths[0] + widths[1] + widths[2] == 0) return error.BadXrefStream;
242 return widths;
243 }
244
245 fn decodeEntries(allocator: std.mem.Allocator, table: *Table, decoded: []const u8, cursor: *usize, widths: [3]usize, first: usize, count: usize) XrefError!void {
246 const row_len = widths[0] + widths[1] + widths[2];
247 var index: usize = 0;
248 while (index < count) : (index += 1) {
249 if (cursor.* + row_len > decoded.len) return error.BadXrefStream;
250 const row = decoded[cursor.* .. cursor.* + row_len];
251 cursor.* += row_len;
252 const kind: u64 = if (widths[0] == 0) 1 else readBigEndian(row[0..widths[0]]);
253 const second = readBigEndian(row[widths[0] .. widths[0] + widths[1]]);
254 const third = readBigEndian(row[widths[0] + widths[1] ..]);
255 const number = std.math.cast(u32, first + index) orelse return error.BadXrefStream;
256 switch (kind) {
257 0 => {},
258 1 => try register(allocator, table, number, .{
259 .offset = std.math.cast(usize, second) orelse return error.BadXrefStream,
260 }),
261 2 => try register(allocator, table, number, .{ .compressed = .{
262 .container = std.math.cast(u32, second) orelse return error.BadXrefStream,
263 .index = std.math.cast(u32, third) orelse return error.BadXrefStream,
264 } }),
265 else => {},
266 }
267 }
268 }
269
270 fn readBigEndian(bytes: []const u8) u64 {
271 var value: u64 = 0;
272 for (bytes) |byte| value = (value << 8) | byte;
273 return value;
274 }
275
276 fn directUnsigned(dict: object.Dict, key: []const u8) ?usize {
277 return valueUnsigned(dict.get(key) orelse return null);
278 }
279
280 fn valueUnsigned(value: object.Value) ?usize {
281 return switch (value) {
282 .integer => |raw| if (raw >= 0) std.math.cast(usize, raw) else null,
283 else => null,
284 };
285 }
286
287 fn applyRoot(trailer: object.Dict, root: *?object.Reference) void {
288 if (root.* != null) return;
289 const value = trailer.get("Root") orelse return;
290 switch (value) {
291 .reference => |reference| root.* = reference,
292 else => {},
293 }
294 }
295
296 fn previousOffset(trailer: object.Dict) ?usize {
297 const value = trailer.get("Prev") orelse return null;
298 return valueUnsigned(value);
299 }
300
301 fn parseTest(
302 allocator: std.mem.Allocator,
303 arena: std.mem.Allocator,
304 bytes: []const u8,
305 ) !Table {
306 var storage = try filter.Storage.init(allocator, .{ .bounds = .{
307 .input_bytes = bytes.len,
308 .decoded_bytes = bytes.len,
309 } });
310 defer storage.deinit(allocator);
311 storage.activate();
312 return parse(allocator, arena, &storage, bytes);
313 }
314
315 test "xref parses table entries trailer root and prev chains" {
316 const body =
317 "%PDF-1.4\n" ++
318 "xref\n0 3\n" ++
319 "0000000000 65535 f \n" ++
320 "0000000009 00000 n \n" ++
321 "0000000100 00000 n \n" ++
322 "trailer\n<< /Size 3 /Root 1 0 R >>\n" ++
323 "startxref\n9\n%%EOF";
324 var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator);
325 defer arena_state.deinit();
326 var table = try parseTest(std.testing.allocator, arena_state.allocator(), body);
327 defer table.deinit(std.testing.allocator);
328 try std.testing.expectEqual(@as(u32, 1), table.root.number);
329 try std.testing.expectEqual(@as(usize, 9), table.locations.get(1).?.offset);
330 try std.testing.expectEqual(@as(usize, 100), table.locations.get(2).?.offset);
331 try std.testing.expect(table.locations.get(0) == null);
332 const missing_trailer = "%PDF-1.4\nxref\n0 0\nstartxref\n9\n%%EOF";
333 try std.testing.expectError(
334 error.BadNumber,
335 parseTest(std.testing.allocator, arena_state.allocator(), missing_trailer),
336 );
337 }
338
339 fn xrefStreamBodyAlloc(allocator: std.mem.Allocator, dict_fragment: []const u8, rows: []const u8) ![]u8 {
340 var out = std.ArrayList(u8).empty;
341 errdefer out.deinit(allocator);
342 const head = try std.fmt.allocPrint(allocator, "9 0 obj\n<< /Type /XRef /Length {d} {s} >>\nstream\n", .{ rows.len, dict_fragment });
343 defer allocator.free(head);
344 try out.appendSlice(allocator, head);
345 try out.appendSlice(allocator, rows);
346 try out.appendSlice(allocator, "\nendstream\nendobj\n");
347 return out.toOwnedSlice(allocator);
348 }
349
350 test "xref stream decodes typed entries with explicit index" {
351 const rows = [_]u8{
352 1, 0, 64, 0,
353 2, 0, 7, 3,
354 0, 0, 0, 0,
355 1, 0, 200, 1,
356 };
357 const section = try xrefStreamBodyAlloc(
358 std.testing.allocator,
359 "/Size 12 /W [1 2 1] /Index [4 2 10 2] /Root 4 0 R",
360 &rows,
361 );
362 defer std.testing.allocator.free(section);
363 const body = try std.mem.concat(std.testing.allocator, u8, &.{ "%PDF-1.5\n", section, "startxref\n9\n%%EOF" });
364 defer std.testing.allocator.free(body);
365 var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator);
366 defer arena_state.deinit();
367 var table = try parseTest(std.testing.allocator, arena_state.allocator(), body);
368 defer table.deinit(std.testing.allocator);
369 try std.testing.expectEqual(@as(u32, 4), table.root.number);
370 try std.testing.expectEqual(@as(usize, 64), table.locations.get(4).?.offset);
371 try std.testing.expectEqual(@as(u32, 7), table.locations.get(5).?.compressed.container);
372 try std.testing.expectEqual(@as(u32, 3), table.locations.get(5).?.compressed.index);
373 try std.testing.expect(table.locations.get(10) == null);
374 try std.testing.expectEqual(@as(usize, 200), table.locations.get(11).?.offset);
375 }
376
377 test "xref stream defaults index to whole size and honors zero width types" {
378 const rows = [_]u8{
379 0, 0,
380 30, 0,
381 60, 2,
382 };
383 const section = try xrefStreamBodyAlloc(
384 std.testing.allocator,
385 "/Size 3 /W [0 1 1] /Root 1 0 R",
386 &rows,
387 );
388 defer std.testing.allocator.free(section);
389 const body = try std.mem.concat(std.testing.allocator, u8, &.{ "%PDF-1.5\n", section, "startxref\n9\n%%EOF" });
390 defer std.testing.allocator.free(body);
391 var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator);
392 defer arena_state.deinit();
393 var table = try parseTest(std.testing.allocator, arena_state.allocator(), body);
394 defer table.deinit(std.testing.allocator);
395 try std.testing.expectEqual(@as(usize, 0), table.locations.get(0).?.offset);
396 try std.testing.expectEqual(@as(usize, 30), table.locations.get(1).?.offset);
397 try std.testing.expectEqual(@as(usize, 60), table.locations.get(2).?.offset);
398 }
399
400 test "hybrid tables read the xref stream before their own entries" {
401 var body = std.ArrayList(u8).empty;
402 defer body.deinit(std.testing.allocator);
403 try body.appendSlice(std.testing.allocator, "%PDF-1.4\n");
404 const stream_offset = body.items.len;
405 const rows = [_]u8{ 2, 0, 9, 0 };
406 const stream_body = try xrefStreamBodyAlloc(
407 std.testing.allocator,
408 "/Size 6 /W [1 2 1] /Index [5 1] /Root 2 0 R",
409 &rows,
410 );
411 defer std.testing.allocator.free(stream_body);
412 try body.appendSlice(std.testing.allocator, stream_body);
413 const table_offset = body.items.len;
414 const classic = try std.fmt.allocPrint(
415 std.testing.allocator,
416 "xref\n5 1\n0000000777 00000 n \n" ++
417 "trailer\n<< /Size 6 /Root 2 0 R /XRefStm {d} >>\nstartxref\n{d}\n%%EOF",
418 .{ stream_offset, table_offset },
419 );
420 defer std.testing.allocator.free(classic);
421 try body.appendSlice(std.testing.allocator, classic);
422 var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator);
423 defer arena_state.deinit();
424 var table = try parseTest(std.testing.allocator, arena_state.allocator(), body.items);
425 defer table.deinit(std.testing.allocator);
426 try std.testing.expectEqual(@as(u32, 9), table.locations.get(5).?.compressed.container);
427 }
428
429 test "malformed xref streams fail typed" {
430 const missing_w = "%PDF-1.5\n9 0 obj\n<< /Type /XRef /Size 2 /Length 0 /Root 1 0 R >>\nstream\n\nendstream\nendobj\nstartxref\n9\n%%EOF";
431 var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator);
432 defer arena_state.deinit();
433 try std.testing.expectError(
434 error.BadXrefStream,
435 parseTest(std.testing.allocator, arena_state.allocator(), missing_w),
436 );
437 const not_xref = "%PDF-1.5\n9 0 obj\n<< /Type /Font >>\nendobj\nstartxref\n9\n%%EOF";
438 try std.testing.expectError(
439 error.BadXrefStream,
440 parseTest(std.testing.allocator, arena_state.allocator(), not_xref),
441 );
442 }