tiny.reticulum.packet.hashlist

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const packet = @import("root.zig");45const TableLimits = struct {6    hashes_max: usize,7};89const TableCapacity = struct {10    hashes_max: usize,11    storage_bytes: usize,1213    pub const DeriveError = error{ InvalidLimit, CapacityOverflow };1415    pub fn derive(limits: TableLimits) DeriveError!TableCapacity {16        if (limits.hashes_max == 0) return error.InvalidLimit;17        const hashes_max = limits.hashes_max;18        const storage_bytes = alloc_phase.capacity.mul(19            usize,20            hashes_max,21            @sizeOf(packet.Hash),22        ) catch return error.CapacityOverflow;23        return .{ .hashes_max = hashes_max, .storage_bytes = storage_bytes };24    }25};2627pub const Table = struct {28    phase: alloc_phase.capacity.Phase,29    capacity: Capacity,30    storage: Storage,31    hashes: []packet.Hash,32    start: usize = 0,33    len: usize = 0,34    generation_len: usize = 0,3536    pub const storage_alignment: usize = 8;37    pub const Storage = []align(storage_alignment) u8;38    pub const Limits: type = TableLimits;39    pub const Capacity: type = TableCapacity;40    pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};41    pub const work_limits: alloc_phase.capacity.WorkLimits = .{42        .transition_steps_max = 1_000_001,43        .cleanup_steps_per_call_max = 0,44        .cleanup_calls_at_capacity_max = 0,45    };46    pub const claim: alloc_phase.capacity.Declaration = .{47        .source = .{48            .id = "reticulum.hashlist",49            .kind = .phase_static,50            .limit_source = .caller,51            .storage = .{52                .covered = &.{.{53                    .id = "caller_packet_hash_fifo",54                    .lifetime = .transferred,55                    .detail = "caller storage for a bounded FIFO of packet hashes",56                }},57                .excluded = &.{58                    "borrowed lookup hashes",59                    "encoded packets and wire hash computation",60                },61            },62            .capacity = .{63                .inputs = &.{alloc_phase.capacity.bindInput(64                    Limits,65                    "hashes_max",66                    "hashes_max",67                )},68                .type_selectors = &.{alloc_phase.capacity.bindType(packet.Hash, "hash")},69                .nodes = &.{70                    .{ .input = 0 },71                    .{ .scale = .{72                        .node = 0,73                        .coefficient = .{ .size_of_concrete_type = 0 },74                    } },75                },76                .assertions = &.{.{77                    .scope = .closure_total,78                    .measure = .retained,79                    .relation = .exact,80                    .expression = 1,81                }},82            },83            .overload = .{84                .kind = .not_applicable,85                .detail = "a new hash replaces the oldest hash when the FIFO is full",86            },87            .risks = .{88                .transitive = .{89                    .status = .excluded,90                    .detail = "hash lookup and insertion call no allocating owner",91                },92                .foreign = .{93                    .status = .excluded,94                    .detail = "the hash FIFO crosses no foreign boundary",95                },96            },97            .work = .{ .equation = "lookup scans at most hashes_max entries" },98            .obligations = &.{99                .{ .key = "reticulum_hashlist_capacity", .role = .capacity_model },100                .{ .key = "reticulum_hashlist_replace", .role = .overload },101                .{ .key = "reticulum_hashlist_work", .role = .work_bound },102            },103        },104        .bindings = .{105            .owner = @This(),106            .seal = .{107                .family = alloc_phase.capacity.selector(@This().activate),108                .premise = .{ .class = .checked_semantic_fact, .authority = .checker },109            },110            .teardown = .{111                .family = alloc_phase.capacity.selector(@This().deinit),112                .premise = .{ .class = .checked_semantic_fact, .authority = .checker },113            },114        },115    };116117    pub fn init(storage: Storage, limits: Limits) InitError!Table {118        const capacity = try Capacity.derive(limits);119        if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;120        return .{121            .phase = .initialization,122            .capacity = capacity,123            .storage = storage,124            .hashes = std.mem.bytesAsSlice(packet.Hash, storage),125        };126    }127128    pub fn activate(self: *Table) void {129        std.debug.assert(self.phase == .initialization);130        std.debug.assert(self.len == 0);131        self.phase = .steady;132    }133134    pub fn contains(self: *const Table, hash: packet.Hash) bool {135        std.debug.assert(self.phase == .steady);136        for (0..self.len) |offset| {137            const index = (self.start + offset) % self.capacity.hashes_max;138            if (std.mem.eql(u8, &self.hashes[index], &hash)) return true;139        }140        return false;141    }142143    /// Adds the 32-byte SHA-256 digest that names a packet (*packet hash*) so144    /// the caller recognizes a later copy of the same packet, and returns the145    /// hash it pushed out, or null when it pushed none out. A hash the store146    /// already holds is left where it is and null comes back. Once the store is147    /// full the oldest hash leaves and the new one takes its slot, so the store148    /// keeps the order the hashes arrived in, following Reticulum@1.5.0149    /// RNS/Transport.py:167-168,803-805.150    pub fn insert(self: *Table, hash: packet.Hash) ?packet.Hash {151        std.debug.assert(self.phase == .steady);152        std.debug.assert(self.len <= self.capacity.hashes_max);153        if (self.contains(hash)) return null;154        if (self.len < self.capacity.hashes_max) {155            const index = (self.start + self.len) % self.capacity.hashes_max;156            self.hashes[index] = hash;157            self.len += 1;158            self.generation_len += 1;159            return null;160        }161        const evicted = self.hashes[self.start];162        self.hashes[self.start] = hash;163        self.start = (self.start + 1) % self.capacity.hashes_max;164        if (self.generation_len < self.capacity.hashes_max) self.generation_len += 1;165        return evicted;166    }167168    /// Drops the hashes stored before the last rotation and keeps the ones169    /// added since so the store keeps recent hashes and lets go of old ones on170    /// a timer, following Reticulum@1.5.0 RNS/Transport.py:803-805. The call171    /// returns with the store untouched until more than half its slots hold172    /// hashes added since the last rotation.173    pub fn rotate(self: *Table) void {174        std.debug.assert(self.phase == .steady);175        const threshold = self.capacity.hashes_max / 2;176        if (self.generation_len <= threshold) return;177        std.debug.assert(self.generation_len <= self.len);178        const discarded = self.len - self.generation_len;179        self.start = (self.start + discarded) % self.capacity.hashes_max;180        self.len = self.generation_len;181        self.generation_len = 0;182    }183184    /// Removes a hash added since the last rotation and returns whether it was185    /// there. A copy of that hash from before the last rotation stays. The186    /// reference does this for a data packet of an encrypted session between187    /// two endpoints (*link*) that arrived over a network interface (*carrier*)188    /// the link does not run on, so the packet can be acted on again, following189    /// Reticulum@1.5.0 RNS/Transport.py:2515-2516.190    pub fn removeCurrent(self: *Table, hash: packet.Hash) bool {191        std.debug.assert(self.phase == .steady);192        std.debug.assert(self.generation_len <= self.len);193        const first = self.len - self.generation_len;194        for (first..self.len) |offset| {195            const index = (self.start + offset) % self.capacity.hashes_max;196            if (!std.mem.eql(u8, &self.hashes[index], &hash)) continue;197            for (offset + 1..self.len) |later| {198                const target = (self.start + later - 1) % self.capacity.hashes_max;199                const source = (self.start + later) % self.capacity.hashes_max;200                self.hashes[target] = self.hashes[source];201            }202            self.len -= 1;203            self.generation_len -= 1;204            std.debug.assert(self.generation_len <= self.len);205            return true;206        }207        return false;208    }209210    pub fn count(self: *const Table) usize {211        std.debug.assert(self.phase == .steady);212        return self.len;213    }214215    pub fn deinit(self: *Table) Storage {216        std.debug.assert(self.phase == .steady);217        self.phase = .teardown;218        const storage = self.storage;219        self.* = undefined;220        return storage;221    }222};223224comptime {225    alloc_phase.capacity.requireProvisionedExactOwnerShape(Table);226}227228test "hashlist admits maximum and evicts oldest at maximum plus one" {229    comptime {230        @stardustClaim(alloc_phase.capacity.witness(231            Table,232            "reticulum_hashlist_capacity",233        ), null, null, null, null, null, null);234        @stardustClaim(alloc_phase.capacity.witness(235            Table,236            "reticulum_hashlist_replace",237        ), null, null, null, null, null, null);238        @stardustClaim(alloc_phase.capacity.witness(239            Table,240            "reticulum_hashlist_work",241        ), null, null, null, null, null, null);242    }243    const capacity = comptime TableCapacity.derive(.{ .hashes_max = 3 }) catch unreachable;244    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;245    var table = try Table.init(&bytes, .{ .hashes_max = 3 });246    table.activate();247    defer _ = table.deinit();248    for (1..4) |value| {249        try std.testing.expect(table.insert(@splat(@as(u8, @intCast(value)))) == null);250    }251    try std.testing.expectEqual(@as(usize, 3), table.count());252    try std.testing.expectEqual(@as(packet.Hash, @splat(1)), table.insert(@splat(4)).?);253    try std.testing.expect(!table.contains(@splat(1)));254    try std.testing.expect(table.contains(@splat(4)));255}256257test "Reticulum@1.5.0 RNS/Transport.py:803-805 rotates bounded hash generations" {258    const capacity = comptime TableCapacity.derive(.{ .hashes_max = 4 }) catch unreachable;259    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;260    var table = try Table.init(&bytes, .{ .hashes_max = 4 });261    table.activate();262    defer _ = table.deinit();263    for (1..4) |value| _ = table.insert(@splat(@as(u8, @intCast(value))));264    table.rotate();265    for (4..7) |value| _ = table.insert(@splat(@as(u8, @intCast(value))));266    table.rotate();267    try std.testing.expectEqual(@as(usize, 3), table.count());268    try std.testing.expect(!table.contains(@splat(1)));269    try std.testing.expect(table.contains(@splat(4)));270    try std.testing.expect(table.contains(@splat(6)));271}272273test "Reticulum@1.5.0 RNS/Transport.py:2515-2516 removes a hash from the current generation" {274    const capacity = comptime TableCapacity.derive(.{ .hashes_max = 4 }) catch unreachable;275    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;276    var table = try Table.init(&bytes, .{ .hashes_max = 4 });277    table.activate();278    defer _ = table.deinit();279    for (1..4) |value| _ = table.insert(@splat(@as(u8, @intCast(value))));280    table.rotate();281    _ = table.insert(@splat(4));282    try std.testing.expect(!table.removeCurrent(@splat(2)));283    try std.testing.expect(table.contains(@splat(2)));284    try std.testing.expect(table.removeCurrent(@splat(4)));285    try std.testing.expect(!table.contains(@splat(4)));286    _ = table.insert(@splat(5));287    try std.testing.expectEqual(@as(packet.Hash, @splat(1)), table.insert(@splat(6)).?);288    try std.testing.expect(table.removeCurrent(@splat(5)));289    try std.testing.expectEqual(@as(usize, 3), table.count());290    try std.testing.expect(table.contains(@splat(2)));291    try std.testing.expect(table.contains(@splat(3)));292    try std.testing.expect(table.contains(@splat(6)));293    try std.testing.expect(!table.contains(@splat(5)));294}

1pub const hashlist = @import("hashlist.zig");