lib/xkb/src/compose/capacity.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const table = @import("table.zig");
  3 
  4 pub const storage_alignment: usize = @max(@alignOf(table.Node), @alignOf(table.Edge));
  5 
  6 pub const Limits = struct {
  7     sequence_symbols: usize,
  8     text_bytes: usize,
  9 };
 10 
 11 pub const DeriveError = error{
 12     SequenceSymbolLimitExceeded,
 13     TextByteLimitExceeded,
 14     CapacityOverflow,
 15 };
 16 
 17 pub const Capacity = struct {
 18     limits: Limits,
 19     node_count: usize,
 20     node_offset: usize,
 21     node_bytes: usize,
 22     edge_count: usize,
 23     edge_offset: usize,
 24     edge_bytes: usize,
 25     text_offset: usize,
 26     storage_bytes: usize,
 27 
 28     pub fn derive(limits: Limits) DeriveError!Capacity {
 29         if (limits.sequence_symbols >= table.max_nodes) {
 30             return error.SequenceSymbolLimitExceeded;
 31         }
 32         if (limits.text_bytes > std.math.maxInt(u32)) return error.TextByteLimitExceeded;
 33         const node_count = try added(limits.sequence_symbols, 1);
 34         const nodes = try placed(table.Node, 0, node_count);
 35         const edges = try placed(table.Edge, nodes.end, limits.sequence_symbols);
 36         const text_offset = edges.end;
 37         return .{
 38             .limits = limits,
 39             .node_count = node_count,
 40             .node_offset = nodes.start,
 41             .node_bytes = nodes.bytes,
 42             .edge_count = limits.sequence_symbols,
 43             .edge_offset = edges.start,
 44             .edge_bytes = edges.bytes,
 45             .text_offset = text_offset,
 46             .storage_bytes = try added(text_offset, limits.text_bytes),
 47         };
 48     }
 49 };
 50 
 51 const Region = struct {
 52     start: usize,
 53     bytes: usize,
 54     end: usize,
 55 };
 56 
 57 fn added(left: usize, right: usize) DeriveError!usize {
 58     return std.math.add(usize, left, right) catch error.CapacityOverflow;
 59 }
 60 
 61 fn placed(comptime T: type, offset: usize, count: usize) DeriveError!Region {
 62     const mask: usize = @alignOf(T) - 1;
 63     const start = (try added(offset, mask)) & ~mask;
 64     const bytes = std.math.mul(usize, count, @sizeOf(T)) catch
 65         return error.CapacityOverflow;
 66     return .{ .start = start, .bytes = bytes, .end = try added(start, bytes) };
 67 }
 68 
 69 fn modelCapacity(limits: Limits) DeriveError!Capacity {
 70     if (limits.sequence_symbols >= table.max_nodes) {
 71         return error.SequenceSymbolLimitExceeded;
 72     }
 73     if (limits.text_bytes > std.math.maxInt(u32)) return error.TextByteLimitExceeded;
 74     const node_count = @as(u128, limits.sequence_symbols) + 1;
 75     const node_offset: u128 = 0;
 76     const node_bytes = node_count * @sizeOf(table.Node);
 77     const edge_offset = alignForward(node_offset + node_bytes, @alignOf(table.Edge));
 78     const edge_count: u128 = limits.sequence_symbols;
 79     const edge_bytes = edge_count * @sizeOf(table.Edge);
 80     const text_offset = edge_offset + edge_bytes;
 81     const storage_bytes = text_offset + limits.text_bytes;
 82     const values = [_]u128{
 83         node_count,
 84         node_bytes,
 85         edge_offset,
 86         edge_count,
 87         edge_bytes,
 88         text_offset,
 89         storage_bytes,
 90     };
 91     for (values) |value| {
 92         if (value > std.math.maxInt(usize)) return error.CapacityOverflow;
 93     }
 94     return .{
 95         .limits = limits,
 96         .node_count = @intCast(node_count),
 97         .node_offset = @intCast(node_offset),
 98         .node_bytes = @intCast(node_bytes),
 99         .edge_count = @intCast(edge_count),
100         .edge_offset = @intCast(edge_offset),
101         .edge_bytes = @intCast(edge_bytes),
102         .text_offset = @intCast(text_offset),
103         .storage_bytes = @intCast(storage_bytes),
104     };
105 }
106 
107 fn alignForward(value: u128, alignment: u128) u128 {
108     return (value + alignment - 1) & ~(alignment - 1);
109 }
110 
111 test "Compose capacity matches an independent aligned byte model" {
112     comptime {
113         @stardustClaim(
114             @import("alloc_phase").capacity.witness(@import("./root.zig").Storage, "xkb_compose_capacity"),
115             null,
116             null,
117             null,
118             null,
119             null,
120             null,
121         );
122     }
123 
124     const limits = Limits{ .sequence_symbols = 4096, .text_bytes = 16 * 1024 };
125     const capacity = try Capacity.derive(limits);
126     try std.testing.expectEqual(try modelCapacity(limits), capacity);
127     try std.testing.expectEqual(capacity.node_count, capacity.edge_count + 1);
128     try std.testing.expectEqual(
129         capacity.storage_bytes,
130         capacity.text_offset + limits.text_bytes,
131     );
132 }
133 
134 test "Compose capacity rejects index and text representation overflow" {
135     try std.testing.expectError(
136         error.SequenceSymbolLimitExceeded,
137         Capacity.derive(.{ .sequence_symbols = table.max_nodes, .text_bytes = 0 }),
138     );
139     if (comptime @bitSizeOf(usize) > @bitSizeOf(u32)) {
140         try std.testing.expectError(
141             error.TextByteLimitExceeded,
142             Capacity.derive(.{
143                 .sequence_symbols = 0,
144                 .text_bytes = @as(usize, std.math.maxInt(u32)) + 1,
145             }),
146         );
147     }
148 }