lib/tldr/src/archive.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const model = @import("model.zig");
3
4 const Allocator = std.mem.Allocator;
5
6 pub const magic = "!<arch>\n";
7 const header_size = 60;
8
9 pub const Member = struct {
10 name: []const u8,
11 bytes: []const u8,
12 header_offset: u64,
13 };
14
15 pub const SymbolIndexEntry = struct {
16 name: []const u8,
17 member_offset: u64,
18 };
19
20 pub const BuildMember = struct {
21 name: []const u8,
22 bytes: []const u8,
23 symbols: []const []const u8 = &.{},
24 };
25
26 pub const ParsedArchive = struct {
27 members: []Member,
28 symbol_index: []SymbolIndexEntry,
29 has_symbol_index: bool,
30
31 pub fn deinit(self: *ParsedArchive, allocator: Allocator) void {
32 allocator.free(self.members);
33 allocator.free(self.symbol_index);
34 self.* = undefined;
35 }
36 };
37
38 pub fn isArchive(bytes: []const u8) bool {
39 return bytes.len >= magic.len and std.mem.eql(u8, bytes[0..magic.len], magic);
40 }
41
42 pub fn build(allocator: Allocator, members: []const BuildMember) Allocator.Error![]u8 {
43 var out = std.ArrayListUnmanaged(u8).empty;
44 errdefer out.deinit(allocator);
45
46 try out.appendSlice(allocator, magic);
47 var member_offsets: []usize = &.{};
48 var symbol_count: usize = 0;
49 var symbol_name_bytes: usize = 0;
50 for (members) |member| {
51 symbol_count += member.symbols.len;
52 for (member.symbols) |symbol| symbol_name_bytes += symbol.len + 1;
53 }
54 if (symbol_count != 0) {
55 member_offsets = try allocator.alloc(usize, members.len);
56 defer allocator.free(member_offsets);
57
58 const symbol_index_size = 4 + symbol_count * 4 + symbol_name_bytes;
59 var next_member_offset = magic.len + header_size + symbol_index_size + (symbol_index_size & 1);
60 for (members, 0..) |member, index| {
61 member_offsets[index] = next_member_offset;
62 const payload_size = encodedMemberPayloadSize(member);
63 next_member_offset += header_size + payload_size + (payload_size & 1);
64 }
65
66 try appendHeaderWithNameField(&out, allocator, "/", symbol_index_size);
67 try appendU32Big(&out, allocator, @intCast(symbol_count));
68 for (members, 0..) |member, member_index| {
69 for (member.symbols) |_| try appendU32Big(&out, allocator, @intCast(member_offsets[member_index]));
70 }
71 for (members) |member| {
72 for (member.symbols) |symbol| {
73 try out.appendSlice(allocator, symbol);
74 try out.append(allocator, 0);
75 }
76 }
77 if ((symbol_index_size & 1) != 0) try out.append(allocator, '\n');
78 }
79
80 for (members) |member| {
81 const payload_size = encodedMemberPayloadSize(member);
82 try appendHeader(&out, allocator, member.name, payload_size);
83 if (!usesShortMemberName(member.name)) try out.appendSlice(allocator, member.name);
84 try out.appendSlice(allocator, member.bytes);
85 if ((payload_size & 1) != 0) try out.append(allocator, '\n');
86 }
87 return try out.toOwnedSlice(allocator);
88 }
89
90 pub fn parse(allocator: Allocator, input: model.Input) model.Error![]Member {
91 const parsed = try parseDetailed(allocator, input);
92 allocator.free(parsed.symbol_index);
93 return parsed.members;
94 }
95
96 pub fn parseDetailed(allocator: Allocator, input: model.Input) model.Error!ParsedArchive {
97 const bytes = input.bytes;
98 if (!isArchive(bytes)) return error.InvalidArchive;
99
100 var long_names: []const u8 = &.{};
101 var members = std.ArrayListUnmanaged(Member).empty;
102 var symbol_index = std.ArrayListUnmanaged(SymbolIndexEntry).empty;
103 var has_symbol_index = false;
104 errdefer {
105 members.deinit(allocator);
106 symbol_index.deinit(allocator);
107 }
108
109 var offset: usize = magic.len;
110 while (offset < bytes.len) {
111 if (offset + header_size > bytes.len) return error.InvalidArchive;
112 const header_offset = offset;
113 const header = bytes[offset .. offset + header_size];
114 if (header[58] != '`' or header[59] != '\n') return error.InvalidArchive;
115 offset += header_size;
116
117 const size = try parseDecimal(header[48..58]);
118 if (size > bytes.len - offset) return error.InvalidArchive;
119 const raw_payload = bytes[offset .. offset + size];
120 offset += size;
121 if ((offset & 1) != 0) {
122 if (offset >= bytes.len) return error.InvalidArchive;
123 offset += 1;
124 }
125
126 const raw_name = trimField(header[0..16]);
127 if (std.mem.eql(u8, raw_name, "/")) {
128 has_symbol_index = true;
129 try parseSymbolIndex(allocator, raw_payload, &symbol_index);
130 continue;
131 }
132 if (std.mem.eql(u8, raw_name, "//")) {
133 long_names = raw_payload;
134 continue;
135 }
136
137 const decoded = try decodeMemberName(raw_name, raw_payload, long_names);
138 try members.append(allocator, .{
139 .name = decoded.name,
140 .bytes = decoded.payload,
141 .header_offset = @intCast(header_offset),
142 });
143 }
144
145 if (offset != bytes.len) return error.InvalidArchive;
146 const member_slice = try members.toOwnedSlice(allocator);
147 errdefer allocator.free(member_slice);
148 const symbol_index_slice = try symbol_index.toOwnedSlice(allocator);
149 return .{
150 .members = member_slice,
151 .symbol_index = symbol_index_slice,
152 .has_symbol_index = has_symbol_index,
153 };
154 }
155
156 pub fn memberIndexByOffsetWithCursor(members: []const Member, offset: u64, cursor: *usize) ?usize {
157 if (cursor.* < members.len) {
158 const current_offset = members[cursor.*].header_offset;
159 if (current_offset == offset) return cursor.*;
160 if (current_offset < offset) {
161 var index = cursor.* + 1;
162 while (index < members.len) : (index += 1) {
163 const member_offset = members[index].header_offset;
164 if (member_offset == offset) {
165 cursor.* = index;
166 return index;
167 }
168 if (member_offset > offset) return null;
169 }
170 return null;
171 }
172 }
173 const index = memberIndexByOffset(members, offset) orelse return null;
174 cursor.* = index;
175 return index;
176 }
177
178 pub fn memberIndexByOffset(members: []const Member, offset: u64) ?usize {
179 var low: usize = 0;
180 var high: usize = members.len;
181 while (low < high) {
182 const middle = low + (high - low) / 2;
183 const member_offset = members[middle].header_offset;
184 if (member_offset == offset) return middle;
185 if (offset < member_offset) {
186 high = middle;
187 } else {
188 low = middle + 1;
189 }
190 }
191 return null;
192 }
193
194 test "member offset cursor handles ordered and fallback lookups" {
195 const members = [_]Member{
196 .{ .name = "a.o", .bytes = &.{}, .header_offset = 8 },
197 .{ .name = "b.o", .bytes = &.{}, .header_offset = 24 },
198 .{ .name = "c.o", .bytes = &.{}, .header_offset = 40 },
199 };
200
201 var cursor: usize = 0;
202 try std.testing.expectEqual(@as(?usize, 0), memberIndexByOffsetWithCursor(&members, 8, &cursor));
203 try std.testing.expectEqual(@as(usize, 0), cursor);
204 try std.testing.expectEqual(@as(?usize, 2), memberIndexByOffsetWithCursor(&members, 40, &cursor));
205 try std.testing.expectEqual(@as(usize, 2), cursor);
206 try std.testing.expectEqual(@as(?usize, 1), memberIndexByOffsetWithCursor(&members, 24, &cursor));
207 try std.testing.expectEqual(@as(usize, 1), cursor);
208 try std.testing.expectEqual(@as(?usize, null), memberIndexByOffsetWithCursor(&members, 32, &cursor));
209 }
210
211 fn parseSymbolIndex(
212 allocator: Allocator,
213 payload: []const u8,
214 symbol_index: *std.ArrayListUnmanaged(SymbolIndexEntry),
215 ) model.Error!void {
216 if (payload.len < 4) return error.InvalidArchive;
217 const symbol_count = readU32Big(payload, 0);
218 const offset_table_size = std.math.mul(usize, symbol_count, 4) catch return error.InvalidArchive;
219 const string_table_start = 4 + offset_table_size;
220 if (string_table_start > payload.len) return error.InvalidArchive;
221
222 try symbol_index.ensureUnusedCapacity(allocator, symbol_count);
223 var name_offset = string_table_start;
224 var index: usize = 0;
225 while (index < symbol_count) : (index += 1) {
226 const end = std.mem.indexOfScalarPos(u8, payload, name_offset, 0) orelse return error.InvalidArchive;
227 try symbol_index.append(allocator, .{
228 .name = payload[name_offset..end],
229 .member_offset = readU32Big(payload, 4 + index * 4),
230 });
231 name_offset = end + 1;
232 }
233 }
234
235 const DecodedMember = struct {
236 name: []const u8,
237 payload: []const u8,
238 };
239
240 fn decodeMemberName(
241 raw_name: []const u8,
242 raw_payload: []const u8,
243 long_names: []const u8,
244 ) model.Error!DecodedMember {
245 if (std.mem.startsWith(u8, raw_name, "#1/")) {
246 const name_len = try parseDecimal(raw_name[3..]);
247 if (name_len > raw_payload.len) return error.InvalidArchive;
248 return .{
249 .name = raw_payload[0..name_len],
250 .payload = raw_payload[name_len..],
251 };
252 }
253
254 if (raw_name.len >= 2 and raw_name[0] == '/' and std.ascii.isDigit(raw_name[1])) {
255 const name_offset = try parseDecimal(raw_name[1..]);
256 if (name_offset >= long_names.len) return error.InvalidArchive;
257 const start: usize = @intCast(name_offset);
258 const line_end = std.mem.indexOfScalarPos(u8, long_names, start, '\n') orelse long_names.len;
259 const name_end = if (line_end > start and long_names[line_end - 1] == '/')
260 line_end - 1
261 else
262 line_end;
263 return .{ .name = long_names[start..name_end], .payload = raw_payload };
264 }
265
266 return .{ .name = trimShortName(raw_name), .payload = raw_payload };
267 }
268
269 fn parseDecimal(field: []const u8) model.Error!usize {
270 const trimmed = trimField(field);
271 if (trimmed.len == 0) return error.InvalidArchive;
272 var value: usize = 0;
273 for (trimmed) |byte| {
274 if (!std.ascii.isDigit(byte)) return error.InvalidArchive;
275 value = std.math.mul(usize, value, 10) catch return error.InvalidArchive;
276 value = std.math.add(usize, value, byte - '0') catch return error.InvalidArchive;
277 }
278 return value;
279 }
280
281 fn readU32Big(bytes: []const u8, offset: usize) u32 {
282 return std.mem.readInt(u32, bytes[offset..][0..4], .big);
283 }
284
285 fn usesShortMemberName(name: []const u8) bool {
286 return name.len != 0 and
287 name.len + 1 <= 16 and
288 std.mem.indexOfScalar(u8, name, '/') == null;
289 }
290
291 fn encodedMemberPayloadSize(member: BuildMember) usize {
292 return member.bytes.len + if (usesShortMemberName(member.name)) @as(usize, 0) else member.name.len;
293 }
294
295 fn appendHeader(
296 out: *std.ArrayListUnmanaged(u8),
297 allocator: Allocator,
298 name: []const u8,
299 payload_size: usize,
300 ) Allocator.Error!void {
301 if (usesShortMemberName(name)) {
302 var name_buf: [17]u8 = undefined;
303 const archive_name = std.fmt.bufPrint(&name_buf, "{s}/", .{name}) catch unreachable;
304 try appendHeaderWithNameField(out, allocator, archive_name, payload_size);
305 return;
306 }
307 var name_buf: [17]u8 = undefined;
308 const archive_name = std.fmt.bufPrint(&name_buf, "#1/{d}", .{name.len}) catch unreachable;
309 try appendHeaderWithNameField(out, allocator, archive_name, payload_size);
310 }
311
312 fn appendHeaderWithNameField(
313 out: *std.ArrayListUnmanaged(u8),
314 allocator: Allocator,
315 name: []const u8,
316 size: usize,
317 ) Allocator.Error!void {
318 try appendField(out, allocator, 16, name);
319 try appendField(out, allocator, 12, "0");
320 try appendField(out, allocator, 6, "0");
321 try appendField(out, allocator, 6, "0");
322 try appendField(out, allocator, 8, "100644");
323
324 var size_buf: [20]u8 = undefined;
325 const size_text = std.fmt.bufPrint(&size_buf, "{d}", .{size}) catch unreachable;
326 try appendField(out, allocator, 10, size_text);
327 try out.appendSlice(allocator, "`\n");
328 }
329
330 fn appendU32Big(
331 out: *std.ArrayListUnmanaged(u8),
332 allocator: Allocator,
333 value: u32,
334 ) Allocator.Error!void {
335 var bytes: [4]u8 = undefined;
336 std.mem.writeInt(u32, &bytes, value, .big);
337 try out.appendSlice(allocator, &bytes);
338 }
339
340 fn appendField(
341 out: *std.ArrayListUnmanaged(u8),
342 allocator: Allocator,
343 width: usize,
344 value: []const u8,
345 ) Allocator.Error!void {
346 std.debug.assert(value.len <= width);
347 try out.appendSlice(allocator, value);
348 try out.appendNTimes(allocator, ' ', width - value.len);
349 }
350
351 fn trimField(field: []const u8) []const u8 {
352 return std.mem.trimEnd(u8, field, " ");
353 }
354
355 fn trimShortName(raw_name: []const u8) []const u8 {
356 const slash_index = std.mem.indexOfScalar(u8, raw_name, '/') orelse raw_name.len;
357 return raw_name[0..slash_index];
358 }
359
360 test "archive parser reads short and BSD extended member names" {
361 const bytes =
362 magic ++
363 "short.o/ 0 0 0 100644 3 `\nabc\n" ++
364 "#1/16 0 0 0 100644 20 `\nvery-long-name.o!\nxy";
365 const members = try parse(std.testing.allocator, .{ .name = "libx.a", .bytes = bytes });
366 defer std.testing.allocator.free(members);
367
368 try std.testing.expectEqual(@as(usize, 2), members.len);
369 try std.testing.expectEqualStrings("short.o", members[0].name);
370 try std.testing.expectEqualSlices(u8, "abc", members[0].bytes);
371 try std.testing.expectEqualStrings("very-long-name.o", members[1].name);
372 try std.testing.expectEqualSlices(u8, "!\nxy", members[1].bytes);
373 }
374
375 test "archive parser reads GNU long-name tables" {
376 const bytes =
377 magic ++
378 "// 0 0 0 100644 20 `\nlong-member-name.o/\n" ++
379 "/0 0 0 0 100644 2 `\nxy";
380 const members = try parse(std.testing.allocator, .{ .name = "libx.a", .bytes = bytes });
381 defer std.testing.allocator.free(members);
382
383 try std.testing.expectEqual(@as(usize, 1), members.len);
384 try std.testing.expectEqualStrings("long-member-name.o", members[0].name);
385 try std.testing.expectEqualSlices(u8, "xy", members[0].bytes);
386 }
387
388 test "archive parser keeps slashes inside GNU long member names" {
389 const bytes =
390 magic ++
391 "// 0 0 0 100644 63 `\n" ++
392 ".zig-cache/o/57afe1b693277004bcc2a09b815ff3f8/libtinyrt_zcu.o/\n\n" ++
393 "/0 0 0 0 100644 2 `\nxy";
394 const members = try parse(std.testing.allocator, .{ .name = "libtinyrt.a", .bytes = bytes });
395 defer std.testing.allocator.free(members);
396
397 try std.testing.expectEqual(@as(usize, 1), members.len);
398 try std.testing.expectEqualStrings(
399 ".zig-cache/o/57afe1b693277004bcc2a09b815ff3f8/libtinyrt_zcu.o",
400 members[0].name,
401 );
402 try std.testing.expectEqualSlices(u8, "xy", members[0].bytes);
403 }
404
405 test "archive parser reads GNU symbol indexes" {
406 const bytes =
407 magic ++
408 "/ 0 0 0 100644 12 `\n" ++
409 "\x00\x00\x00\x01\x00\x00\x00\x50sym\x00" ++
410 "target.o/ 0 0 0 100644 2 `\nxy";
411 var parsed = try parseDetailed(std.testing.allocator, .{ .name = "libx.a", .bytes = bytes });
412 defer parsed.deinit(std.testing.allocator);
413
414 try std.testing.expectEqual(@as(usize, 1), parsed.members.len);
415 try std.testing.expectEqual(@as(usize, 1), parsed.symbol_index.len);
416 try std.testing.expect(parsed.has_symbol_index);
417 try std.testing.expectEqualStrings("target.o", parsed.members[0].name);
418 try std.testing.expectEqual(@as(u64, 80), parsed.members[0].header_offset);
419 try std.testing.expectEqualStrings("sym", parsed.symbol_index[0].name);
420 try std.testing.expectEqual(@as(u64, 80), parsed.symbol_index[0].member_offset);
421 }
422
423 test "archive builder writes member symbol index" {
424 const bytes = try build(std.testing.allocator, &.{
425 .{ .name = "target.o", .bytes = "xy", .symbols = &.{"sym"} },
426 });
427 defer std.testing.allocator.free(bytes);
428
429 var parsed = try parseDetailed(std.testing.allocator, .{ .name = "libx.a", .bytes = bytes });
430 defer parsed.deinit(std.testing.allocator);
431
432 try std.testing.expect(parsed.has_symbol_index);
433 try std.testing.expectEqual(@as(usize, 1), parsed.members.len);
434 try std.testing.expectEqual(@as(usize, 1), parsed.symbol_index.len);
435 try std.testing.expectEqualStrings("target.o", parsed.members[0].name);
436 try std.testing.expectEqualStrings("sym", parsed.symbol_index[0].name);
437 try std.testing.expectEqual(parsed.members[0].header_offset, parsed.symbol_index[0].member_offset);
438 }