lib/tldr/src/formats/elf/merge/start.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const elf = @import("../root.zig");
  3 
  4 const Allocator = std.mem.Allocator;
  5 const ObjectFile = elf.parser.ObjectFile;
  6 const SectionHeader = elf.format.SectionHeader;
  7 
  8 pub fn count(bytes: []const u8) usize {
  9     var piece_count: usize = 0;
 10     for (bytes) |byte| {
 11         if (byte == 0) piece_count += 1;
 12     }
 13     return piece_count;
 14 }
 15 
 16 pub const Index = struct {
 17     built: bool = false,
 18     sections: []SectionStarts = &.{},
 19 
 20     pub fn deinit(self: *Index, allocator: Allocator) void {
 21         for (self.sections) |section| allocator.free(section.starts);
 22         allocator.free(self.sections);
 23         self.* = .{};
 24     }
 25 
 26     pub fn forSection(
 27         self: *Index,
 28         allocator: Allocator,
 29         object: ObjectFile,
 30         section_index: usize,
 31     ) Allocator.Error![]const u64 {
 32         if (!self.built) try self.build(allocator, object);
 33         for (self.sections) |section| {
 34             if (section.section_index == section_index) return section.starts;
 35         }
 36         return &.{};
 37     }
 38 
 39     fn build(self: *Index, allocator: Allocator, object: ObjectFile) Allocator.Error!void {
 40         var builders = std.ArrayListUnmanaged(SectionBuilder).empty;
 41         defer builders.deinit(allocator);
 42         errdefer deinitBuilders(allocator, builders.items);
 43 
 44         for (object.symbols) |symbol| {
 45             if (symbol.section_index >= object.sections.len) continue;
 46             const section_index: usize = symbol.section_index;
 47             const section = object.sections[section_index];
 48             if (!mergeStringSectionWithoutRelocations(object, section, section_index)) continue;
 49             if (!symbol.isGlobalDefinition()) continue;
 50             const starts = try builderForSection(allocator, &builders, section_index);
 51             try starts.append(allocator, symbol.value);
 52         }
 53 
 54         const sections = try allocator.alloc(SectionStarts, builders.items.len);
 55         var initialized_sections: usize = 0;
 56         errdefer {
 57             for (sections[0..initialized_sections]) |section| allocator.free(section.starts);
 58             allocator.free(sections);
 59         }
 60         for (builders.items, sections) |*builder, *section| {
 61             std.mem.sort(u64, builder.starts.items, {}, std.sort.asc(u64));
 62             section.* = .{
 63                 .section_index = builder.section_index,
 64                 .starts = try builder.starts.toOwnedSlice(allocator),
 65             };
 66             initialized_sections += 1;
 67         }
 68         self.sections = sections;
 69         self.built = true;
 70     }
 71 };
 72 
 73 pub fn shouldIndex(object: ObjectFile) bool {
 74     var section_count: usize = 0;
 75     for (object.sections, 0..) |section, section_index| {
 76         if (!mergeStringSectionWithoutRelocations(object, section, section_index)) continue;
 77         section_count += 1;
 78         if (section_count > 1) return true;
 79     }
 80     return false;
 81 }
 82 
 83 pub fn collect(
 84     allocator: Allocator,
 85     object: ObjectFile,
 86     section_index: usize,
 87 ) Allocator.Error![]u64 {
 88     var starts = std.ArrayListUnmanaged(u64).empty;
 89     errdefer starts.deinit(allocator);
 90     for (object.symbols) |symbol| {
 91         if (symbol.section_index != section_index) continue;
 92         if (!symbol.isGlobalDefinition()) continue;
 93         try starts.append(allocator, symbol.value);
 94     }
 95     if (starts.items.len == 0) return &.{};
 96     std.mem.sort(u64, starts.items, {}, std.sort.asc(u64));
 97     return try starts.toOwnedSlice(allocator);
 98 }
 99 
100 const SectionStarts = struct {
101     section_index: usize,
102     starts: []const u64,
103 };
104 
105 const SectionBuilder = struct {
106     section_index: usize,
107     starts: std.ArrayListUnmanaged(u64) = .empty,
108 };
109 
110 fn deinitBuilders(allocator: Allocator, builders: []SectionBuilder) void {
111     for (builders) |*builder| builder.starts.deinit(allocator);
112 }
113 
114 fn builderForSection(
115     allocator: Allocator,
116     builders: *std.ArrayListUnmanaged(SectionBuilder),
117     section_index: usize,
118 ) Allocator.Error!*std.ArrayListUnmanaged(u64) {
119     for (builders.items) |*builder| {
120         if (builder.section_index == section_index) return &builder.starts;
121     }
122     try builders.append(allocator, .{ .section_index = section_index });
123     return &builders.items[builders.items.len - 1].starts;
124 }
125 
126 fn mergeStringSectionWithoutRelocations(object: ObjectFile, section: SectionHeader, section_index: usize) bool {
127     if ((section.flags & std.elf.SHF_ALLOC) == 0) return false;
128     if ((section.flags & std.elf.SHF_MERGE) == 0) return false;
129     if ((section.flags & std.elf.SHF_STRINGS) == 0) return false;
130     if (section.section_type != std.elf.SHT_PROGBITS) return false;
131     if (section.entry_size > 1) return false;
132     if (section.alignment > 1) return false;
133     return object.relocationsForSection(section_index).len == 0;
134 }
135 
136 pub fn has(external_starts: []const u64, cursor: *usize, input_offset: usize) bool {
137     const offset: u64 = @intCast(input_offset);
138     while (cursor.* < external_starts.len and external_starts[cursor.*] < offset) cursor.* += 1;
139     return cursor.* < external_starts.len and external_starts[cursor.*] == offset;
140 }