Flash 325 lines
// mem — slice and memory primitives, in pure Flash.
//
// The verbs mirror Zig's `std.mem` spellings — callers pass the element
// type first — so a facade can re-route between the two implementations
// without touching a call site. `sort` is a stable insertion sort by
// design: the compiler sorts small slices where stability is worth more
// than asymptotics, and equal keys must never reorder across a swap of
// the implementation. The integer codecs (`readInt` / `writeInt`) take
// the byte order explicitly as a `mem.Endian` — there is no native-endian
// shortcut, so every call site states the wire format it speaks.
use "base"
// Element-wise slice equality. Lengths must match exactly.
pub fn eql(comptime T type, a []T, b []T) bool {
if a.len != b.len {
return false
}
for x, i in a {
if x != b[i] {
return false
}
}
return true
}
// First index of `value` in `haystack`, or null.
pub fn indexOfScalar(comptime T type, haystack []T, value T) ?usize {
for x, i in haystack {
if x == value {
return i
}
}
return null
}
// First index where `needle` occurs as a sub-slice of `haystack`, or null.
// An empty needle matches at index 0.
pub fn indexOf(comptime T type, haystack []T, needle []T) ?usize {
if needle.len > haystack.len {
return null
}
for i in 0..haystack.len - needle.len + 1 {
if eql(T, haystack[i .. i + needle.len], needle) {
return i
}
}
return null
}
// Copy `source` into the front of `dest`. `dest.len` must be at least
// `source.len`; the slices must not overlap.
pub fn copy(comptime T type, dest []mut T, source []T) void {
for x, i in source {
dest[i] = x
}
}
// Set every element of `dest` to `value`.
pub fn set(comptime T type, dest []mut T, value T) void {
for i in 0..dest.len {
dest[i] = value
}
}
// Lexicographic less-than over two slices: the first differing element
// decides; a strict prefix orders before its extension.
pub fn lessThan(comptime T type, lhs []T, rhs []T) bool {
var n usize = lhs.len
if rhs.len < n {
n = rhs.len
}
for i in 0..n {
if lhs[i] < rhs[i] {
return true
}
if rhs[i] < lhs[i] {
return false
}
}
return lhs.len < rhs.len
}
// Stable insertion sort. `lessThanFn(context, a, b)` reports a < b; equal
// elements keep their input order. Small-N workloads only — the point is
// stability and simplicity, not asymptotics.
pub fn sort(comptime T type, items []mut T, context anytype, lessThanFn anytype) void {
var i usize = 1
while i < items.len {
x := items[i]
var j usize = i
while j > 0 && lessThanFn(context, x, items[j - 1]) {
items[j] = items[j - 1]
j -= 1
}
items[j] = x
i += 1
}
}
// Byte order for the explicit-endian integer codecs below. Spelled like
// Zig's `std.builtin.Endian` so call sites pass the same `.little` /
// `.big` literals.
pub const Endian = enum {
little,
big,
}
// Read an unsigned integer `T` from the first `#sizeOf(T)` bytes of
// `buffer`, in the given byte order. `T` is at most 64 bits wide.
pub fn readInt(comptime T type, buffer []u8, endian Endian) T {
n := #sizeOf(T)
var acc u64 = 0
if endian == .little {
var i usize = n
while i > 0 {
i -= 1
acc = (acc << 8) | buffer[i]
}
} else {
for i in 0..n {
acc = (acc << 8) | buffer[i]
}
}
return #truncate(acc)
}
// Write `value` into the first `#sizeOf(T)` bytes of `buffer`, in the
// given byte order. `T` is an unsigned integer at most 64 bits wide.
pub fn writeInt(comptime T type, buffer []mut u8, value T, endian Endian) void {
n := #sizeOf(T)
var v u64 = value
if endian == .little {
for i in 0..n {
buffer[i] = #truncate(v)
v >>= 8
}
} else {
var i usize = n
while i > 0 {
i -= 1
buffer[i] = #truncate(v)
v >>= 8
}
}
}
// View the memory of `ptr`'s pointee as a read-only byte slice of length
// `#sizeOf(T)`. The writable counterpart is `asBytesMut` — Flash spells
// pointee mutability in the type, so the two views are separate verbs.
pub fn asBytes(comptime T type, ptr *T) []u8 {
const p [*]u8 = #ptrCast(ptr)
return p[0..#sizeOf(T)]
}
// View the memory of `ptr`'s pointee as a writable byte slice of length
// `#sizeOf(T)`.
pub fn asBytesMut(comptime T type, ptr *mut T) []mut u8 {
const p [*]mut u8 = #ptrCast(ptr)
return p[0..#sizeOf(T)]
}
// The prefix of `slice` up to (excluding) the first element equal to
// `end`, or all of `slice` if no element matches.
pub fn sliceTo(comptime T type, slice []T, end T) []T {
for x, i in slice {
if x == end {
return slice[0..i]
}
}
return slice
}
// Count a 0-terminated many-item pointer into a slice of the elements up
// to (excluding) the sentinel.
pub fn span(comptime T type, ptr [*:0]T) []T {
var n usize = 0
while ptr[n] != 0 {
n += 1
}
return ptr[0..n]
}
// Round `addr` up to the next multiple of `alignment`, which must be a
// power of two. Aligned addresses are returned unchanged.
pub fn alignForward(comptime T type, addr T, alignment T) T {
return (addr + alignment - 1) & ~(alignment - 1)
}
fn ascending(ctx i32, a i32, b i32) bool {
_ = ctx
return a < b
}
const Pair = struct {
key i32,
tag u8,
}
fn lessKey(ctx i32, a Pair, b Pair) bool {
_ = ctx
return a.key < b.key
}
test "eql compares element-wise" {
try base.expect(eql(u8, "flash", "flash"))
try base.expect(!eql(u8, "flash", "flasc"))
try base.expect(!eql(u8, "flash", "flas"))
try base.expect(eql(u8, "", ""))
const xs [3]u32 = .{ 1, 2, 3 }
const ys [3]u32 = .{ 1, 2, 3 }
try base.expect(eql(u32, xs[0..], ys[0..]))
}
test "indexOfScalar finds the first hit or null" {
try base.expectEqual(1, indexOfScalar(u8, "abcb", 'b'))
try base.expectEqual(null, indexOfScalar(u8, "abc", 'z'))
try base.expectEqual(null, indexOfScalar(u8, "", 'a'))
}
test "indexOf finds a sub-slice" {
try base.expectEqual(2, indexOf(u8, "hello", "ll"))
try base.expectEqual(0, indexOf(u8, "hello", "he"))
try base.expectEqual(null, indexOf(u8, "hello", "lo!"))
try base.expectEqual(null, indexOf(u8, "hi", "hello"))
try base.expectEqual(0, indexOf(u8, "hello", ""))
try base.expectEqual(0, indexOf(u8, "", ""))
}
test "copy moves elements, set fills" {
var buf [4]u8 = .{ 0, 0, 0, 0 }
copy(u8, buf[0..], "ab")
try base.expectEqual('a', buf[0])
try base.expectEqual('b', buf[1])
try base.expectEqual(0, buf[2])
set(u8, buf[0..], 7)
try base.expectEqual(7, buf[0])
try base.expectEqual(7, buf[3])
}
test "lessThan orders lexicographically" {
try base.expect(lessThan(u8, "abc", "abd"))
try base.expect(!lessThan(u8, "abd", "abc"))
try base.expect(lessThan(u8, "ab", "abc"))
try base.expect(!lessThan(u8, "abc", "ab"))
try base.expect(!lessThan(u8, "abc", "abc"))
try base.expect(lessThan(u8, "", "a"))
}
test "sort orders a slice" {
var xs [5]i32 = .{ 3, 1, 2, 1, 0 }
const ctx i32 = 0
sort(i32, xs[0..], ctx, ascending)
try base.expectEqual(0, xs[0])
try base.expectEqual(1, xs[1])
try base.expectEqual(1, xs[2])
try base.expectEqual(2, xs[3])
try base.expectEqual(3, xs[4])
}
test "sort is stable on equal keys" {
var ps [4]Pair = .{ .{ .key = 1, .tag = 'a' }, .{ .key = 0, .tag = 'x' }, .{ .key = 1, .tag = 'b' }, .{ .key = 0, .tag = 'y' } }
const ctx i32 = 0
sort(Pair, ps[0..], ctx, lessKey)
try base.expectEqual('x', ps[0].tag)
try base.expectEqual('y', ps[1].tag)
try base.expectEqual('a', ps[2].tag)
try base.expectEqual('b', ps[3].tag)
}
test "readInt and writeInt round-trip both byte orders" {
var buf [8]u8 = .{ 0, 0, 0, 0, 0, 0, 0, 0 }
writeInt(u32, buf[0..4], 0x12345678, .little)
try base.expectEqual(0x78, buf[0])
try base.expectEqual(0x12, buf[3])
try base.expectEqual(0x12345678, readInt(u32, buf[0..4], .little))
writeInt(u32, buf[0..4], 0x12345678, .big)
try base.expectEqual(0x12, buf[0])
try base.expectEqual(0x78, buf[3])
try base.expectEqual(0x12345678, readInt(u32, buf[0..4], .big))
writeInt(u16, buf[0..2], 0xBEEF, .little)
try base.expectEqual(0xBEEF, readInt(u16, buf[0..2], .little))
writeInt(u8, buf[0..1], 0xA5, .big)
try base.expectEqual(0xA5, readInt(u8, buf[0..1], .big))
writeInt(u64, buf[0..8], 0xDEADBEEFCAFEF00D, .little)
try base.expectEqual(0xDEADBEEFCAFEF00D, readInt(u64, buf[0..8], .little))
}
test "asBytes views memory in place" {
var arr [4]u8 = .{ 1, 2, 3, 4 }
bytes := asBytes([4]u8, &arr)
try base.expectEqual(4, bytes.len)
try base.expectEqual(1, bytes[0])
try base.expectEqual(4, bytes[3])
mut_bytes := asBytesMut([4]u8, &arr)
mut_bytes[0] = 9
try base.expectEqual(9, arr[0])
var word u32 = 0
writeInt(u32, asBytesMut(u32, &word), 0x01020304, .little)
try base.expectEqual(0x01020304, readInt(u32, asBytes(u32, &word), .little))
}
test "sliceTo cuts at the first match" {
const xs [5]u8 = .{ 'a', 'b', 0, 'c', 0 }
try base.expect(eql(u8, "ab", sliceTo(u8, xs[0..], 0)))
try base.expect(eql(u8, "abc", sliceTo(u8, "abc", 0)))
try base.expectEqual(0, sliceTo(u8, "", 0).len)
}
test "span counts to the sentinel" {
const s [*:0]u8 = "flash"
try base.expect(eql(u8, "flash", span(u8, s)))
const e [*:0]u8 = ""
try base.expectEqual(0, span(u8, e).len)
}
test "alignForward rounds up to a power of two" {
try base.expectEqual(0, alignForward(usize, 0, 8))
try base.expectEqual(8, alignForward(usize, 1, 8))
try base.expectEqual(8, alignForward(usize, 8, 8))
try base.expectEqual(16, alignForward(usize, 9, 8))
try base.expectEqual(4096, alignForward(u32, 1, 4096))
try base.expectEqual(7, alignForward(u8, 7, 1))
}