tiny.reducer.bytes.capacity

1//! The layout and the memory bound of the *workspace* (the one byte allocation2//! `Storage` makes up front and reuses for every run) are derived for byte3//! reduction.4//!5//! The caller supplies one sizing number, the longest input it will submit, as6//! its *limits*, which the formulas write $N$. Shortening a sequence of length7//! $N$ needs two regions of memory at the same time:8//! 1. The *witness lane* holds the *current sequence* (the shortest sequence9//!    the oracle has accepted so far, which the search deletes from next) and10//!    needs $N$ bytes.11//! 2. The *scratch lane* is where each *candidate* (one shorter byte sequence12//!    built by deleting a run of bytes from the current sequence and handed to13//!    the oracle) is assembled and needs $N - 1$ bytes.14//!15//! Every candidate is strictly shorter than the current sequence, so the16//! scratch lane needs at most $\max(N - 1, 0)$ bytes. The total is:17//!18//! $$\text{storage\_bytes} = N + \max(N - 1, 0)$$19//!20//! At $N = 0$ both lanes need 0 bytes, so the total is 0 bytes. A workspace of21//! zero length asks the allocator for a zero-byte slice while initializing, and22//! that request need not reach the heap.23//!24//! `Capacity.derive()` works out this layout in arithmetic and allocates25//! nothing. The arithmetic overflows when26//! $N + \max(N - 1, 0) > \text{maxInt}(\text{usize})$. For example, on a 64-bit27//! target the largest input limit that can be represented is28//! $\lfloor \text{maxInt}(\text{usize}) / 2 \rfloor + 1 = 2^{63}$, and the29//! storage it derives is $\text{maxInt}(\text{usize}) = 2^{64} - 1$ bytes. A30//! limit above that returns `DeriveError.CapacityOverflow`, which reports that31//! the bound exceeds what `usize` can hold and stands apart from an allocator32//! failure.3334const std = @import("std");3536/// Sizing constraint the caller supplies for the byte reduction workspace.37pub const Limits = struct {38    /// Ceiling on the length in bytes of any initial input handed to39    /// `reduce()`. An input longer than this is refused at acquisition with40    /// `Exhaustion.InputCapacityExceeded`.41    max_input_bytes: usize,42};4344/// Errors raised while computing the storage requirement from `Limits`.45pub const DeriveError = error{46    /// The requested `max_input_bytes` cannot be represented in `usize` once47    /// the scratch lane is added to it, which is the condition48    /// $N + \max(N - 1, 0) > \text{maxInt}(\text{usize})$. The bound exceeds49    /// what the arithmetic can represent, so it stands apart from the50    /// allocator's own `OutOfMemory`.51    CapacityOverflow,52};5354/// Workspace layout derived from the caller's limits, sized so that a run in55/// steady state needs no further allocation.56pub const Capacity = struct {57    /// Caller's limits that this capacity was derived from.58    limits: Limits,59    /// Byte offset in the backing allocation where the scratch lane starts. It60    /// equals `limits.max_input_bytes` exactly.61    candidate_offset: usize,62    /// Greatest length in bytes any candidate takes, which is $\max(N - 1, 0)$.63    candidate_bytes: usize,64    /// Total the combined allocation needs, which is65    /// $\text{candidate\_offset} + \text{candidate\_bytes}$.66    storage_bytes: usize,6768    /// Works out the memory a workspace needs to reduce inputs up to69    /// `limits.max_input_bytes`. It computes $N + \max(N - 1, 0)$, taking the70    /// scratch lane's length with saturating subtraction and the total with71    /// checked addition. It produces the arithmetic layout alone and calls no72    /// allocator.73    ///74    /// ## Errors75    /// It returns `DeriveError.CapacityOverflow` when the combined requirement76    /// exceeds `std.math.maxInt(usize)`.77    pub fn derive(limits: Limits) DeriveError!Capacity {78        const candidate_bytes = limits.max_input_bytes -| 1;79        const capacity = Capacity{80            .limits = limits,81            .candidate_offset = limits.max_input_bytes,82            .candidate_bytes = candidate_bytes,83            .storage_bytes = std.math.add(84                usize,85                limits.max_input_bytes,86                candidate_bytes,87            ) catch return error.CapacityOverflow,88        };89        std.debug.assert(capacity.candidate_offset == limits.max_input_bytes);90        std.debug.assert(capacity.candidate_bytes <= limits.max_input_bytes);91        std.debug.assert(capacity.storage_bytes >= limits.max_input_bytes);92        std.debug.assert(93            capacity.candidate_offset + capacity.candidate_bytes == capacity.storage_bytes,94        );95        return capacity;96    }97};9899fn modelCapacity(limits: Limits) DeriveError!Capacity {100    const input_bytes: u128 = limits.max_input_bytes;101    const candidate_bytes = if (input_bytes == 0) 0 else input_bytes - 1;102    const storage_bytes = input_bytes + candidate_bytes;103    if (storage_bytes > std.math.maxInt(usize)) return error.CapacityOverflow;104    return .{105        .limits = limits,106        .candidate_offset = limits.max_input_bytes,107        .candidate_bytes = @intCast(candidate_bytes),108        .storage_bytes = @intCast(storage_bytes),109    };110}111112test "byte storage capacity matches an independent byte model" {113    comptime {114        @stardustClaim(115            @import("alloc_phase").capacity.witness(@import("./root.zig").Storage, "reducer_byte_capacity"),116            null,117            null,118            null,119            null,120            null,121            null,122        );123    }124125    const limits = Limits{ .max_input_bytes = 9 };126    try std.testing.expectEqual(try modelCapacity(limits), try Capacity.derive(limits));127    try std.testing.expectEqual(@as(usize, 17), (try Capacity.derive(limits)).storage_bytes);128    try std.testing.expectEqual(129        @as(usize, 0),130        (try Capacity.derive(.{ .max_input_bytes = 0 })).storage_bytes,131    );132}133134test "byte storage capacity accepts its largest representable input limit" {135    const max_input_bytes = std.math.maxInt(usize) / 2 + 1;136    const capacity = try Capacity.derive(.{ .max_input_bytes = max_input_bytes });137    try std.testing.expectEqual(std.math.maxInt(usize), capacity.storage_bytes);138    try std.testing.expectError(139        error.CapacityOverflow,140        Capacity.derive(.{ .max_input_bytes = max_input_bytes + 1 }),141    );142}

1/// Module holding the capacity derivation and the limits type.2pub const capacity = @import("capacity.zig");