Meg's Mirrors

zig

1	const mem = @This();
2
3	const builtin = @import("builtin");
4	const native_endian = builtin.cpu.arch.endian();
5
6	const std = @import("std.zig");
7	const debug = std.debug;
8	const assert = debug.assert;
9	const math = std.math;
10	const testing = std.testing;
11	const Endian = std.lang.Endian;
12	const AbsorbSentinel = std.meta.AbsorbSentinel;
13
14	/// The standard library currently thoroughly depends on byte size
15	/// being 8 bits. (see the use of u8 throughout allocation code as
16	/// the "byte" type.) Code which depends on this can reference this
17	/// declaration. If we ever try to port the standard library to a
18	/// non-8-bit-byte platform, this will allow us to search for things
19	/// which need to be updated.
20	pub const byte_size_in_bits = 8;
21
22	pub const Allocator = @import("mem/Allocator.zig");
23
24	/// Stored as a power-of-two.
25	pub const Alignment = enum(math.Log2Int(usize)) {
26	@"1" = 0,
27	@"2" = 1,
28	@"4" = 2,
29	@"8" = 3,
30	@"16" = 4,
31	@"32" = 5,
32	@"64" = 6,
33	_,
34
35	pub fn toByteUnits(a: Alignment) usize {
36	return @as(usize, 1) << @backingInt(a);
37	}
38
39	pub fn fromByteUnits(n: usize) Alignment {
40	assert(std.math.isPowerOfTwo(n));
41	return @fromBackingInt(@intCast(@ctz(n)));
42	}
43
44	pub fn fromByteUnitsOptional(maybe_n: ?usize) ?Alignment {
45	return if (maybe_n) |n| .fromByteUnits(n) else null;
46	}
47
48	pub inline fn of(comptime T: type) Alignment {
49	return comptime fromByteUnits(@alignOf(T));
50	}
51
52	pub fn order(lhs: Alignment, rhs: Alignment) std.math.Order {
53	return std.math.order(@backingInt(lhs), @backingInt(rhs));
54	}
55
56	pub fn compare(lhs: Alignment, op: std.math.CompareOperator, rhs: Alignment) bool {
57	return std.math.compare(@backingInt(lhs), op, @backingInt(rhs));
58	}
59
60	pub fn max(lhs: Alignment, rhs: Alignment) Alignment {
61	return @fromBackingInt(@intCast(@max(@backingInt(lhs), @backingInt(rhs))));
62	}
63
64	pub fn min(lhs: Alignment, rhs: Alignment) Alignment {
65	return @fromBackingInt(@intCast(@min(@backingInt(lhs), @backingInt(rhs))));
66	}
67
68	/// Return next address with this alignment.
69	pub fn forward(a: Alignment, address: usize) usize {
70	const x = (@as(usize, 1) << @backingInt(a)) - 1;
71	return (address + x) & ~x;
72	}
73
74	/// Return previous address with this alignment.
75	pub fn backward(a: Alignment, address: usize) usize {
76	const x = (@as(usize, 1) << @backingInt(a)) - 1;
77	return address & ~x;
78	}
79
80	/// Return whether address is aligned to this amount.
81	pub fn check(a: Alignment, address: usize) bool {
82	return @ctz(address) >= @backingInt(a);
83	}
84	};
85
86	/// Detects and asserts if the std.mem.Allocator interface is violated by the caller
87	/// or the allocator.
88	pub fn ValidationAllocator(comptime T: type) type {
89	return struct {
90	const Self = @This();
91
92	underlying_allocator: T,
93
94	pub fn init(underlying_allocator: T) @This() {
95	return .{
96	.underlying_allocator = underlying_allocator,
97	};
98	}
99
100	pub fn allocator(self: *Self) Allocator {
101	return .{
102	.ptr = self,
103	.vtable = &.{
104	.alloc = alloc,
105	.resize = resize,
106	.remap = remap,
107	.free = free,
108	},
109	};
110	}
111
112	fn getUnderlyingAllocatorPtr(self: *Self) Allocator {
113	if (T == Allocator) return self.underlying_allocator;
114	return self.underlying_allocator.allocator();
115	}
116
117	pub fn alloc(
118	ctx: *anyopaque,
119	n: usize,
120	alignment: mem.Alignment,
121	ret_addr: usize,
122	) ?[*]u8 {
123	assert(n > 0);
124	const self: *Self = @ptrCast(@alignCast(ctx));
125	const underlying = self.getUnderlyingAllocatorPtr();
126	const result = underlying.rawAlloc(n, alignment, ret_addr) orelse
127	return null;
128	assert(alignment.check(@intFromPtr(result)));
129	return result;
130	}
131
132	pub fn resize(
133	ctx: *anyopaque,
134	buf: []u8,
135	alignment: Alignment,
136	new_len: usize,
137	ret_addr: usize,
138	) bool {
139	const self: *Self = @ptrCast(@alignCast(ctx));
140	assert(buf.len > 0);
141	const underlying = self.getUnderlyingAllocatorPtr();
142	return underlying.rawResize(buf, alignment, new_len, ret_addr);
143	}
144
145	pub fn remap(
146	ctx: *anyopaque,
147	buf: []u8,
148	alignment: Alignment,
149	new_len: usize,
150	ret_addr: usize,
151	) ?[*]u8 {
152	const self: *Self = @ptrCast(@alignCast(ctx));
153	assert(buf.len > 0);
154	const underlying = self.getUnderlyingAllocatorPtr();
155	return underlying.rawRemap(buf, alignment, new_len, ret_addr);
156	}
157
158	pub fn free(
159	ctx: *anyopaque,
160	buf: []u8,
161	alignment: Alignment,
162	ret_addr: usize,
163	) void {
164	const self: *Self = @ptrCast(@alignCast(ctx));
165	assert(buf.len > 0);
166	const underlying = self.getUnderlyingAllocatorPtr();
167	underlying.rawFree(buf, alignment, ret_addr);
168	}
169
170	pub fn reset(self: *Self) void {
171	self.underlying_allocator.reset();
172	}
173	};
174	}
175
176	/// Wraps an allocator with basic validation checks.
177	/// Asserts that allocation sizes are greater than zero and returned pointers have correct alignment.
178	pub fn validationWrap(allocator: anytype) ValidationAllocator(@TypeOf(allocator)) {
179	return ValidationAllocator(@TypeOf(allocator)).init(allocator);
180	}
181
182	test "Allocator basics" {
183	try testing.expectError(error.OutOfMemory, testing.failing_allocator.alloc(u8, 1));
184	try testing.expectError(error.OutOfMemory, testing.failing_allocator.allocSentinel(u8, 1, 0));
185	}
186
187	test "Allocator.resize" {
188	const primitiveIntTypes = .{
189	i8,
190	u8,
191	i16,
192	u16,
193	i32,
194	u32,
195	i64,
196	u64,
197	i128,
198	u128,
199	isize,
200	usize,
201	};
202	inline for (primitiveIntTypes) |T| {
203	var values = try testing.allocator.alloc(T, 100);
204	defer testing.allocator.free(values);
205
206	for (values, 0..) |*v, i| v.* = @as(T, @intCast(i));
207	if (testing.allocator.resize(values, values.len + 10)) {
208	values = values.ptr[0 .. values.len + 10];
209	try testing.expect(values.len == 110);
210	} else {
211	// `resize` is not guaranteed to succeed even if there is sufficient memory.
212	}
213	}
214
215	const primitiveFloatTypes = .{
216	f16,
217	f32,
218	f64,
219	f128,
220	};
221	inline for (primitiveFloatTypes) |T| {
222	var values = try testing.allocator.alloc(T, 100);
223	defer testing.allocator.free(values);
224
225	for (values, 0..) |*v, i| v.* = @as(T, @floatFromInt(i));
226	if (testing.allocator.resize(values, values.len + 10)) {
227	values = values.ptr[0 .. values.len + 10];
228	try testing.expect(values.len == 110);
229	} else {
230	// `resize` is not guaranteed to succeed even if there is sufficient memory.
231	}
232	}
233	}
234
235	test "Allocator alloc and remap with zero-bit type" {
236	var values = try testing.allocator.alloc(void, 10);
237	defer testing.allocator.free(values);
238
239	try testing.expectEqual(10, values.len);
240	const remaped = testing.allocator.remap(values, 200);
241	try testing.expect(remaped != null);
242
243	values = remaped.?;
244	try testing.expectEqual(200, values.len);
245	}
246
247	/// Copy all of source into dest at position 0.
248	/// dest.len must be >= source.len.
249	/// If the slices overlap, dest.ptr must be <= src.ptr.
250	/// This function is deprecated; use @memmove instead.
251	pub fn copyForwards(comptime T: type, dest: []T, source: []const T) void {
252	for (dest[0..source.len], source) |*d, s| d.* = s;
253	}
254
255	/// Copy all of source into dest at position 0.
256	/// dest.len must be >= source.len.
257	/// If the slices overlap, dest.ptr must be >= src.ptr.
258	/// This function is deprecated; use @memmove instead.
259	pub fn copyBackwards(comptime T: type, dest: []T, source: []const T) void {
260	// TODO instead of manually doing this check for the whole array
261	// and turning off runtime safety, the compiler should detect loops like
262	// this and automatically omit safety checks for loops
263	@setRuntimeSafety(false);
264	assert(dest.len >= source.len);
265	var i = source.len;
266	while (i > 0) {
267	i -= 1;
268	dest[i] = source[i];
269	}
270	}
271
272	/// Generally, Zig users are encouraged to explicitly initialize all fields of a struct explicitly rather than using this function.
273	/// However, it is recognized that there are sometimes use cases for initializing all fields to a "zero" value. For example, when
274	/// interfacing with a C API where this practice is more common and relied upon. If you are performing code review and see this
275	/// function used, examine closely - it may be a code smell.
276	/// Zero initializes the type.
277	/// This can be used to zero-initialize any type for which it makes sense. Structs will be initialized recursively.
278	pub fn zeroes(comptime T: type) T {
279	switch (@typeInfo(T)) {
280	.comptime_int, .int, .comptime_float, .float => {
281	return @as(T, 0);
282	},
283	.@"enum" => {
284	return @as(T, @fromBackingInt(@intCast(0)));
285	},
286	.void => {
287	return {};
288	},
289	.bool => {
290	return false;
291	},
292	.optional, .null => {
293	return null;
294	},
295	.@"struct" => |struct_info| {
296	if (@sizeOf(T) == 0) return undefined;
297	if (struct_info.layout == .@"extern") {
298	var item: T = undefined;
299	@memset(asBytes(&item), 0);
300	return item;
301	} else {
302	var structure: T = undefined;
303	inline for (
304	struct_info.field_names,
305	struct_info.field_types,
306	struct_info.field_attrs,
307	) |field_name, field_type, field_attrs| {
308	if (!field_attrs.@"comptime") {
309	@field(structure, field_name) = zeroes(field_type);
310	}
311	}
312	return structure;
313	}
314	},
315	.pointer => |ptr_info| {
316	switch (ptr_info.size) {
317	.slice => {
318	if (ptr_info.sentinel()) |sentinel| {
319	if (ptr_info.child == u8 and sentinel == 0) {
320	return ""; // A special case for the most common use-case: null-terminated strings.
321	}
322	@compileError("Can't set a sentinel slice to zero. This would require allocating memory.");
323	} else {
324	return &[_]ptr_info.child{};
325	}
326	},
327	.c => {
328	return null;
329	},
330	.one, .many => {
331	if (ptr_info.attrs.@"allowzero") return @ptrFromInt(0);
332	@compileError("Only nullable and allowzero pointers can be set to zero.");
333	},
334	}
335	},
336	.array => |info| {
337	return @splat(zeroes(info.child));
338	},
339	.vector => |info| {
340	return @splat(zeroes(info.child));
341	},
342	.@"union" => |info| {
343	if (info.layout == .@"extern") {
344	var item: T = undefined;
345	@memset(asBytes(&item), 0);
346	return item;
347	}
348	@compileError("Can't set a " ++ @typeName(T) ++ " to zero.");
349	},
350	.enum_literal,
351	.error_union,
352	.error_set,
353	.@"fn",
354	.type,
355	.noreturn,
356	.undefined,
357	.@"opaque",
358	.spirv,
359	.frame,
360	.@"anyframe",
361	=> {
362	@compileError("Can't set a " ++ @typeName(T) ++ " to zero.");
363	},
364	}
365	}
366
367	test zeroes {
368	const C_struct = extern struct {
369	x: u32,
370	y: u32 align(128),
371	};
372
373	var a = zeroes(C_struct);
374
375	// Extern structs should have padding zeroed out.
376	{
377	const num_bytes = @sizeOf(@TypeOf(a));
378	try testing.expectEqualSlices(u8, &@as([num_bytes]u8, @splat(0)), @ptrCast(&a));
379	}
380
381	a.y += 10;
382
383	try testing.expect(a.x == 0);
384	try testing.expect(a.y == 10);
385
386	const ZigStruct = struct {
387	comptime comptime_field: u8 = 5,
388
389	integral_types: struct {
390	integer_8: i8,
391	integer_16: i16,
392	integer_32: i32,
393	integer_64: i64,
394	integer_128: i128,
395	unsigned_0: u0,
396	unsigned_8: u8,
397	unsigned_16: u16,
398	unsigned_32: u32,
399	unsigned_64: u64,
400	unsigned_128: u128,
401
402	float_32: f32,
403	float_64: f64,
404	},
405
406	pointers: struct {
407	optional: ?*u8,
408	c_pointer: [*c]u8,
409	slice: []u8,
410	nullTerminatedString: [:0]const u8,
411	},
412
413	array: [2]u32,
414	vector_u32: @Vector(2, u32),
415	vector_f32: @Vector(2, f32),
416	vector_bool: @Vector(2, bool),
417	optional_int: ?u8,
418	empty: void,
419	sentinel: [3:0]u8,
420	};
421
422	const b = zeroes(ZigStruct);
423	try testing.expectEqual(@as(u8, 5), b.comptime_field);
424	try testing.expectEqual(@as(i8, 0), b.integral_types.integer_8);
425	try testing.expectEqual(@as(i16, 0), b.integral_types.integer_16);
426	try testing.expectEqual(@as(i32, 0), b.integral_types.integer_32);
427	try testing.expectEqual(@as(i64, 0), b.integral_types.integer_64);
428	try testing.expectEqual(@as(i128, 0), b.integral_types.integer_128);
429	try testing.expectEqual(@as(u8, 0), b.integral_types.unsigned_0);
430	try testing.expectEqual(@as(u8, 0), b.integral_types.unsigned_8);
431	try testing.expectEqual(@as(u16, 0), b.integral_types.unsigned_16);
432	try testing.expectEqual(@as(u32, 0), b.integral_types.unsigned_32);
433	try testing.expectEqual(@as(u64, 0), b.integral_types.unsigned_64);
434	try testing.expectEqual(@as(u128, 0), b.integral_types.unsigned_128);
435	try testing.expectEqual(@as(f32, 0), b.integral_types.float_32);
436	try testing.expectEqual(@as(f64, 0), b.integral_types.float_64);
437	try testing.expectEqual(@as(?*u8, null), b.pointers.optional);
438	try testing.expectEqual(@as([*c]u8, null), b.pointers.c_pointer);
439	try testing.expectEqual(@as([]u8, &[_]u8{}), b.pointers.slice);
440	try testing.expectEqual(@as([:0]const u8, ""), b.pointers.nullTerminatedString);
441	for (b.array) |e| {
442	try testing.expectEqual(@as(u32, 0), e);
443	}
444	try testing.expectEqual(@as(@TypeOf(b.vector_u32), @splat(0)), b.vector_u32);
445	try testing.expectEqual(@as(@TypeOf(b.vector_f32), @splat(0.0)), b.vector_f32);
446	if (!(builtin.zig_backend == .stage2_llvm and builtin.cpu.arch == .hexagon)) {
447	try testing.expectEqual(@as(@TypeOf(b.vector_bool), @splat(false)), b.vector_bool);
448	}
449	try testing.expectEqual(@as(?u8, null), b.optional_int);
450	for (b.sentinel) |e| {
451	try testing.expectEqual(@as(u8, 0), e);
452	}
453
454	const C_union = extern union {
455	a: u8,
456	b: u32,
457	};
458
459	const c = zeroes(C_union);
460	try testing.expectEqual(@as(u8, 0), c.a);
461	try testing.expectEqual(@as(u32, 0), c.b);
462
463	const comptime_union = comptime zeroes(C_union);
464	try testing.expectEqual(@as(u8, 0), comptime_union.a);
465	try testing.expectEqual(@as(u32, 0), comptime_union.b);
466
467	// Ensure zero sized struct with fields is initialized correctly.
468	_ = zeroes(struct { handle: void });
469	}
470
471	/// Initializes all fields of the struct with their default value, or zero values if no default value is present.
472	/// If the field is present in the provided initial values, it will have that value instead.
473	/// Structs are initialized recursively.
474	pub fn zeroInit(comptime T: type, init: anytype) T {
475	const Init = @TypeOf(init);
476
477	switch (@typeInfo(T)) {
478	.@"struct" => |struct_info| {
479	switch (@typeInfo(Init)) {
480	.@"struct" => |init_info| {
481	if (init_info.is_tuple) {
482	if (init_info.field_names.len > struct_info.field_names.len) {
483	@compileError("Tuple initializer has more elements than there are fields in `" ++ @typeName(T) ++ "`");
484	}
485	} else {
486	inline for (init_info.field_names) |field_name| {
487	if (!@hasField(T, field_name)) {
488	@compileError("Encountered an initializer for `" ++ field_name ++ "`, but it is not a field of " ++ @typeName(T));
489	}
490	}
491	}
492
493	var value: T = if (struct_info.layout == .@"extern") zeroes(T) else undefined;
494
495	inline for (
496	struct_info.field_names,
497	struct_info.field_types,
498	struct_info.field_attrs,
499	0..,
500	) |f_name, f_type, f_attr, i| {
501	if (f_attr.@"comptime") {
502	continue;
503	}
504
505	if (init_info.is_tuple and init_info.field_names.len > i) {
506	@field(value, f_name) = @field(init, init_info.field_names[i]);
507	} else if (@hasField(@TypeOf(init), f_name)) {
508	switch (@typeInfo(f_type)) {
509	.@"struct" => {
510	@field(value, f_name) = zeroInit(f_type, @field(init, f_name));
511	},
512	else => {
513	@field(value, f_name) = @field(init, f_name);
514	},
515	}
516	} else if (f_attr.defaultValue(f_type)) |val| {
517	@field(value, f_name) = val;
518	} else {
519	switch (@typeInfo(f_type)) {
520	.@"struct" => {
521	@field(value, f_name) = std.mem.zeroInit(f_type, .{});
522	},
523	else => {
524	@field(value, f_name) = std.mem.zeroes(@TypeOf(@field(value, f_name)));
525	},
526	}
527	}
528	}
529
530	return value;
531	},
532	else => {
533	@compileError("The initializer must be a struct");
534	},
535	}
536	},
537	else => {
538	@compileError("Can't default init a " ++ @typeName(T));
539	},
540	}
541	}
542
543	test zeroInit {
544	const I = struct {
545	d: f64,
546	};
547
548	const S = struct {
549	a: u32,
550	b: ?bool,
551	c: I,
552	e: [3]u8,
553	f: i64 = -1,
554	};
555
556	const s = zeroInit(S, .{
557	.a = 42,
558	});
559
560	try testing.expectEqual(S{
561	.a = 42,
562	.b = null,
563	.c = .{
564	.d = 0,
565	},
566	.e = [3]u8{ 0, 0, 0 },
567	.f = -1,
568	}, s);
569
570	const Color = struct {
571	r: u8,
572	g: u8,
573	b: u8,
574	a: u8,
575	};
576
577	const c = zeroInit(Color, .{ 255, 255 });
578	try testing.expectEqual(Color{
579	.r = 255,
580	.g = 255,
581	.b = 0,
582	.a = 0,
583	}, c);
584
585	const Foo = struct {
586	foo: u8 = 69,
587	bar: u8,
588	};
589
590	const f = zeroInit(Foo, .{});
591	try testing.expectEqual(Foo{
592	.foo = 69,
593	.bar = 0,
594	}, f);
595
596	const Bar = struct {
597	foo: u32 = 666,
598	bar: u32 = 420,
599	};
600
601	const b = zeroInit(Bar, .{69});
602	try testing.expectEqual(Bar{
603	.foo = 69,
604	.bar = 420,
605	}, b);
606
607	const Baz = struct {
608	foo: [:0]const u8 = "bar",
609	};
610
611	const baz1 = zeroInit(Baz, .{});
612	try testing.expectEqual(Baz{}, baz1);
613
614	const baz2 = zeroInit(Baz, .{ .foo = "zab" });
615	try testing.expectEqualSlices(u8, "zab", baz2.foo);
616
617	const NestedBaz = struct {
618	bbb: Baz,
619	};
620	const nested_baz = zeroInit(NestedBaz, .{});
621	try testing.expectEqual(NestedBaz{
622	.bbb = Baz{},
623	}, nested_baz);
624	}
625
626	/// Sorts a slice in-place using a stable algorithm (maintains relative order of equal elements).
627	/// Average time complexity: O(n log n), worst case: O(n log n)
628	/// Space complexity: O(log n) for recursive calls
629	///
630	/// For slice of primitives with default ordering, consider using `std.sort.block` directly.
631	/// For unstable but potentially faster sorting, see `sortUnstable`.
632	pub fn sort(
633	comptime T: type,
634	items: []T,
635	context: anytype,
636	comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
637	) void {
638	std.sort.block(T, items, context, lessThanFn);
639	}
640
641	/// Sorts a slice in-place using an unstable algorithm (does not preserve relative order of equal elements).
642	/// Time complexity: O(n) best case, O(n log n) worst case and average case.
643	/// Generally faster than stable sort but order of equal elements is undefined.
644	///
645	/// Uses pattern-defeating quicksort (PDQ) algorithm which performs well on many data patterns.
646	/// For stable sorting that preserves equal element order, use `sort`.
647	pub fn sortUnstable(
648	comptime T: type,
649	items: []T,
650	context: anytype,
651	comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
652	) void {
653	std.sort.pdq(T, items, context, lessThanFn);
654	}
655
656	/// TODO: currently this just calls `insertionSortContext`. The block sort implementation
657	/// in this file needs to be adapted to use the sort context.
658	pub fn sortContext(a: usize, b: usize, context: anytype) void {
659	std.sort.insertionContext(a, b, context);
660	}
661
662	/// Sorts a range [a, b) using an unstable algorithm with custom context.
663	/// This is a lower-level interface for sorting that works with indices instead of slices.
664	/// Does not preserve relative order of equal elements.
665	///
666	/// The context must provide lessThan(a_idx, b_idx) and swap(a_idx, b_idx) methods.
667	/// Uses pattern-defeating quicksort (PDQ) algorithm.
668	pub fn sortUnstableContext(a: usize, b: usize, context: anytype) void {
669	std.sort.pdqContext(a, b, context);
670	}
671
672	/// Compares two slices of numbers lexicographically. O(n).
673	pub fn order(comptime T: type, lhs: []const T, rhs: []const T) math.Order {
674	if (lhs.ptr != rhs.ptr) {
675	const n = @min(lhs.len, rhs.len);
676	for (lhs[0..n], rhs[0..n]) |lhs_elem, rhs_elem| {
677	switch (math.order(lhs_elem, rhs_elem)) {
678	.eq => continue,
679	.lt => return .lt,
680	.gt => return .gt,
681	}
682	}
683	}
684	return math.order(lhs.len, rhs.len);
685	}
686
687	/// Compares two many-item pointers with NUL-termination lexicographically.
688	pub fn orderZ(comptime T: type, lhs: [*:0]const T, rhs: [*:0]const T) math.Order {
689	return boundedOrderZ(T, lhs, rhs, std.math.maxInt(usize));
690	}
691
692	/// Compares two many-item pointers with NUL-termination lexicographically until some specified bound.
693	pub fn boundedOrderZ(comptime T: type, lhs: [*:0]const T, rhs: [*:0]const T, bound: usize) math.Order {
694	if (lhs == rhs) return .eq;
695	var i: usize = 0;
696	while (lhs[i] == rhs[i] and lhs[i] != 0 and i < bound) : (i += 1) {}
697	return if (i < bound) math.order(lhs[i], rhs[i]) else .eq;
698	}
699
700	test order {
701	try testing.expect(order(u8, "abcd", "bee") == .lt);
702	try testing.expect(order(u8, "abc", "abc") == .eq);
703	try testing.expect(order(u8, "abc", "abc0") == .lt);
704	try testing.expect(order(u8, "", "") == .eq);
705	try testing.expect(order(u8, "", "a") == .lt);
706
707	const s: []const u8 = "abc";
708	try testing.expect(order(u8, s, s) == .eq);
709	try testing.expect(order(u8, s[0..2], s) == .lt);
710	}
711
712	test orderZ {
713	try testing.expect(orderZ(u8, "abcd", "bee") == .lt);
714	try testing.expect(orderZ(u8, "abc", "abc") == .eq);
715	try testing.expect(orderZ(u8, "abc", "abc0") == .lt);
716	try testing.expect(orderZ(u8, "", "") == .eq);
717	try testing.expect(orderZ(u8, "", "a") == .lt);
718
719	const s: [*:0]const u8 = "abc";
720	try testing.expect(orderZ(u8, s, s) == .eq);
721	}
722
723	/// Returns true if lhs < rhs, false otherwise
724	pub fn lessThan(comptime T: type, lhs: []const T, rhs: []const T) bool {
725	return order(T, lhs, rhs) == .lt;
726	}
727
728	test lessThan {
729	try testing.expect(lessThan(u8, "abcd", "bee"));
730	try testing.expect(!lessThan(u8, "abc", "abc"));
731	try testing.expect(lessThan(u8, "abc", "abc0"));
732	try testing.expect(!lessThan(u8, "", ""));
733	try testing.expect(lessThan(u8, "", "a"));
734	}
735
736	const use_vectors = switch (builtin.zig_backend) {
737	// These backends don't support vectors yet.
738	.stage2_aarch64,
739	.stage2_loongarch,
740	.stage2_powerpc,
741	.stage2_riscv64,
742	=> false,
743	// The SPIR-V backend does not support the optimized path yet.
744	.stage2_spirv => false,
745	else => true,
746	};
747
748	// The naive memory comparison implementation is more useful for fuzzers to find interesting inputs.
749	const use_vectors_for_comparison = use_vectors and !builtin.fuzz;
750
751	/// Returns true if and only if the slices have the same length and all elements
752	/// compare true using equality operator.
753	pub fn eql(comptime T: type, a: []const T, b: []const T) bool {
754	if (!@inComptime() and @sizeOf(T) != 0 and std.meta.hasUniqueRepresentation(T) and
755	use_vectors_for_comparison)
756	{
757	return eqlBytes(sliceAsBytes(a), sliceAsBytes(b));
758	}
759
760	if (a.len != b.len) return false;
761	if (a.len == 0) return true;
762	if (@typeInfo(T) != .float and a.ptr == b.ptr) return true;
763
764	for (a, b) |a_elem, b_elem| {
765	if (a_elem != b_elem) return false;
766	}
767	return true;
768	}
769
770	test eql {
771	try testing.expect(eql(u8, "abcd", "abcd"));
772	try testing.expect(!eql(u8, "abcdef", "abZdef"));
773	try testing.expect(!eql(u8, "abcdefg", "abcdef"));
774
775	comptime {
776	try testing.expect(eql(type, &.{ bool, f32 }, &.{ bool, f32 }));
777	try testing.expect(!eql(type, &.{ bool, f32 }, &.{ f32, bool }));
778	try testing.expect(!eql(type, &.{ bool, f32 }, &.{bool}));
779
780	try testing.expect(eql(comptime_int, &.{ 1, 2, 3 }, &.{ 1, 2, 3 }));
781	try testing.expect(!eql(comptime_int, &.{ 1, 2, 3 }, &.{ 3, 2, 1 }));
782	try testing.expect(!eql(comptime_int, &.{1}, &.{ 1, 2 }));
783	}
784
785	try testing.expect(eql(void, &.{ {}, {} }, &.{ {}, {} }));
786	try testing.expect(!eql(void, &.{{}}, &.{ {}, {} }));
787
788	const x: [3]f64 = .{ 42.0, math.nan(f64), 3.1415 };
789	try testing.expect(!eql(f64, &x, &x));
790	}
791
792	/// std.mem.eql heavily optimized for slices of bytes.
793	fn eqlBytes(a: []const u8, b: []const u8) bool {
794	comptime assert(use_vectors_for_comparison);
795
796	if (a.len != b.len) return false;
797	if (a.len == 0 or a.ptr == b.ptr) return true;
798
799	if (a.len <= 16) {
800	if (a.len < 4) {
801	const x = (a[0] ^ b[0]) | (a[a.len - 1] ^ b[a.len - 1]) | (a[a.len / 2] ^ b[a.len / 2]);
802	return x == 0;
803	}
804	var x: u32 = 0;
805	for ([_]usize{ 0, a.len - 4, (a.len / 8) * 4, a.len - 4 - ((a.len / 8) * 4) }) |n| {
806	x |= @as(u32, @bitCast(a[n..][0..4].*)) ^ @as(u32, @bitCast(b[n..][0..4].*));
807	}
808	return x == 0;
809	}
810
811	// Figure out the fastest way to scan through the input in chunks.
812	// Uses vectors when supported and falls back to usize/words when not.
813	const Scan = if (std.simd.suggestVectorLength(u8)) |vec_size|
814	struct {
815	pub const size = vec_size;
816	pub const Chunk = @Vector(size, u8);
817	pub inline fn isNotEqual(chunk_a: Chunk, chunk_b: Chunk) bool {
818	return @reduce(.Or, chunk_a != chunk_b);
819	}
820	}
821	else
822	struct {
823	pub const size = @sizeOf(usize);
824	pub const Chunk = usize;
825	pub inline fn isNotEqual(chunk_a: Chunk, chunk_b: Chunk) bool {
826	return chunk_a != chunk_b;
827	}
828	};
829
830	inline for (1..6) |s| {
831	const n = 16 << s;
832	if (n <= Scan.size and a.len <= n) {
833	const V = @Vector(n / 2, u8);
834	var x = @as(V, a[0 .. n / 2].*) ^ @as(V, b[0 .. n / 2].*);
835	x |= @as(V, a[a.len - n / 2 ..][0 .. n / 2].*) ^ @as(V, b[a.len - n / 2 ..][0 .. n / 2].*);
836	const zero: V = @splat(0);
837	return !@reduce(.Or, x != zero);
838	}
839	}
840	// Compare inputs in chunks at a time (excluding the last chunk).
841	for (0..(a.len - 1) / Scan.size) |i| {
842	const a_chunk: Scan.Chunk = @bitCast(a[i * Scan.size ..][0..Scan.size].*);
843	const b_chunk: Scan.Chunk = @bitCast(b[i * Scan.size ..][0..Scan.size].*);
844	if (Scan.isNotEqual(a_chunk, b_chunk)) return false;
845	}
846
847	// Compare the last chunk using an overlapping read (similar to the previous size strategies).
848	const last_a_chunk: Scan.Chunk = @bitCast(a[a.len - Scan.size ..][0..Scan.size].*);
849	const last_b_chunk: Scan.Chunk = @bitCast(b[a.len - Scan.size ..][0..Scan.size].*);
850	return !Scan.isNotEqual(last_a_chunk, last_b_chunk);
851	}
852
853	/// Deprecated in favor of `findDiff`.
854	pub const indexOfDiff = findDiff;
855
856	/// Compares two slices and returns the index of the first inequality.
857	/// Returns null if the slices are equal.
858	pub fn findDiff(comptime T: type, a: []const T, b: []const T) ?usize {
859	const shorter = @min(a.len, b.len);
860	if (@typeInfo(T) != .float and a.ptr == b.ptr) {
861	return if (a.len == b.len) null else shorter;
862	}
863	for (a[0..shorter], b[0..shorter], 0..) |a_elem, b_elem, i| {
864	if (a_elem != b_elem) return i;
865	}
866	return if (a.len == b.len) null else shorter;
867	}
868
869	test findDiff {
870	try testing.expectEqual(null, findDiff(u8, "one", "one"));
871	try testing.expectEqual(3, findDiff(u8, "one two", "one"));
872	try testing.expectEqual(3, findDiff(u8, "one", "one two"));
873	try testing.expectEqual(6, findDiff(u8, "one twx", "one two"));
874	try testing.expectEqual(0, findDiff(u8, "xne", "one"));
875
876	const x: [3]f64 = .{ 42.0, math.nan(f64), 3.1415 };
877	try testing.expectEqual(1, findDiff(f64, &x, &x));
878	}
879
880	/// Takes a sentinel-terminated pointer and returns a slice preserving pointer attributes.
881	/// `[*c]` pointers are assumed to be 0-terminated and assumed to not be allowzero.
882	fn Span(comptime T: type) type {
883	switch (@typeInfo(T)) {
884	.optional => |optional_info| {
885	return ?Span(optional_info.child);
886	},
887	.pointer => |ptr_info| {
888	const new_sentinel: ?ptr_info.child = switch (ptr_info.size) {
889	.one, .slice => @compileError("invalid type given to std.mem.span: " ++ @typeName(T)),
890	.many => ptr_info.sentinel() orelse @compileError("invalid type given to std.mem.span: " ++ @typeName(T)),
891	.c => 0,
892	};
893	var attrs = ptr_info.attrs;
894	attrs.@"allowzero" = attrs.@"allowzero" and ptr_info.size != .c;
895	return @Pointer(.slice, attrs, ptr_info.child, new_sentinel);
896	},
897	else => {},
898	}
899	@compileError("invalid type given to std.mem.span: " ++ @typeName(T));
900	}
901
902	test Span {
903	try testing.expect(Span([*:1]u16) == [:1]u16);
904	try testing.expect(Span(?[*:1]u16) == ?[:1]u16);
905	try testing.expect(Span([*:1]const u8) == [:1]const u8);
906	try testing.expect(Span(?[*:1]const u8) == ?[:1]const u8);
907	try testing.expect(Span([*c]u16) == [:0]u16);
908	try testing.expect(Span(?[*c]u16) == ?[:0]u16);
909	try testing.expect(Span([*c]const u8) == [:0]const u8);
910	try testing.expect(Span(?[*c]const u8) == ?[:0]const u8);
911	}
912
913	/// Takes a sentinel-terminated pointer and returns a slice, iterating over the
914	/// memory to find the sentinel and determine the length.
915	/// Pointer attributes such as const are preserved.
916	/// `[*c]` pointers are assumed to be non-null and 0-terminated.
917	pub fn span(ptr: anytype) Span(@TypeOf(ptr)) {
918	if (@typeInfo(@TypeOf(ptr)) == .optional) {
919	if (ptr) |non_null| {
920	return span(non_null);
921	} else {
922	return null;
923	}
924	}
925	const Result = Span(@TypeOf(ptr));
926	const l = len(ptr);
927	const ptr_info = @typeInfo(Result).pointer;
928	if (ptr_info.sentinel()) |s| {
929	return ptr[0..l :s];
930	} else {
931	return ptr[0..l];
932	}
933	}
934
935	test span {
936	var array: [5]u16 = [_]u16{ 1, 2, 3, 4, 5 };
937	const ptr = @as([*:3]u16, array[0..2 :3]);
938	try testing.expect(eql(u16, span(ptr), &[_]u16{ 1, 2 }));
939	try testing.expectEqual(@as(?[:0]u16, null), span(@as(?[*:0]u16, null)));
940	}
941
942	/// Helper for the return type of sliceTo()
943	fn SliceTo(comptime T: type, comptime end: std.meta.Elem(T)) type {
944	switch (@typeInfo(T)) {
945	.optional => |optional_info| {
946	return ?SliceTo(optional_info.child, end);
947	},
948	.pointer => |ptr_info| {
949	const Elem = std.meta.Elem(T);
950	const have_sentinel: bool = switch (ptr_info.size) {
951	.one, .slice => if (std.meta.sentinel(T)) |s| s == end else false,
952	.many => if (std.meta.sentinel(T)) |s| s == end else true,
953	.c => true,
954	};
955	var attrs = ptr_info.attrs;
956	attrs.@"allowzero" = attrs.@"allowzero" and ptr_info.size != .c;
957	return @Pointer(.slice, attrs, Elem, if (have_sentinel) end else null);
958	},
959	else => {},
960	}
961	@compileError("invalid type given to std.mem.sliceTo: " ++ @typeName(T));
962	}
963
964	/// Takes a pointer to an array, a many-item pointer, or a slice, and returns a
965	/// slice of the items up to the first occurrence of `end`.
966	/// If `end` is not found, the resulting slice will include all items up to the
967	/// input's length or sentinel.
968	/// If the pointer type is unbounded (no length or sentinel), `end` will be the
969	/// sentinel for the resulting slice.
970	/// If the pointer type is sentinel-terminated by `end`, the resulting slice
971	/// will also be sentinel-terminated by `end`.
972	/// Pointer properties such as mutability and alignment are preserved.
973	/// C pointers are assumed to be non-null.
974	pub fn sliceTo(ptr: anytype, comptime end: std.meta.Elem(@TypeOf(ptr))) SliceTo(@TypeOf(ptr), end) {
975	if (@typeInfo(@TypeOf(ptr)) == .optional) {
976	const non_null = ptr orelse return null;
977	return sliceTo(non_null, end);
978	}
979	const Result = SliceTo(@TypeOf(ptr), end);
980	const length = lenSliceTo(ptr, end);
981	const ptr_info = @typeInfo(Result).pointer;
982	if (ptr_info.sentinel()) |s| {
983	return ptr[0..length :s];
984	} else {
985	return ptr[0..length];
986	}
987	}
988
989	test sliceTo {
990	try testing.expectEqualSlices(u8, "aoeu", sliceTo("aoeu", 0));
991
992	{
993	var array: [5]u16 = [_]u16{ 1, 2, 3, 4, 5 };
994	try testing.expectEqualSlices(u16, &array, sliceTo(&array, 0));
995	try testing.expectEqualSlices(u16, array[0..3], sliceTo(array[0..3], 0));
996	try testing.expectEqualSlices(u16, array[0..2], sliceTo(&array, 3));
997	try testing.expectEqualSlices(u16, array[0..2], sliceTo(array[0..3], 3));
998
999	const many_ptr: [*]u16 = &array;
1000	try testing.expectEqualSlices(u16, array[0..2], sliceTo(many_ptr, 3));
1001	try testing.expectEqual([:3]u16, @TypeOf(sliceTo(many_ptr, 3)));
1002
1003	const sentinel_ptr = @as([*:5]u16, @ptrCast(&array));
1004	try testing.expectEqualSlices(u16, array[0..2], sliceTo(sentinel_ptr, 3));
1005	try testing.expectEqual([]u16, @TypeOf(sliceTo(sentinel_ptr, 3)));
1006	try testing.expectEqualSlices(u16, array[0..4], sliceTo(sentinel_ptr, 5));
1007	try testing.expectEqual([:5]u16, @TypeOf(sliceTo(sentinel_ptr, 5)));
1008	try testing.expectEqualSlices(u16, array[0..4], sliceTo(sentinel_ptr, 99));
1009
1010	const optional_sentinel_ptr = @as(?[*:5]u16, @ptrCast(&array));
1011	try testing.expectEqualSlices(u16, array[0..2], sliceTo(optional_sentinel_ptr, 3).?);
1012	try testing.expectEqualSlices(u16, array[0..4], sliceTo(optional_sentinel_ptr, 99).?);
1013
1014	const c_ptr = @as([*c]u16, &array);
1015	try testing.expectEqualSlices(u16, array[0..2], sliceTo(c_ptr, 3));
1016	try testing.expectEqual([:3]u16, @TypeOf(sliceTo(c_ptr, 3)));
1017
1018	const slice: []u16 = &array;
1019	try testing.expectEqualSlices(u16, array[0..2], sliceTo(slice, 3));
1020	try testing.expectEqualSlices(u16, &array, sliceTo(slice, 99));
1021
1022	const sentinel_slice: [:5]u16 = array[0..4 :5];
1023	try testing.expectEqualSlices(u16, array[0..2], sliceTo(sentinel_slice, 3));
1024	try testing.expectEqualSlices(u16, array[0..4], sliceTo(sentinel_slice, 99));
1025	}
1026	{
1027	var sentinel_array: [5:0]u16 = [_:0]u16{ 1, 2, 3, 4, 5 };
1028	try testing.expectEqualSlices(u16, sentinel_array[0..2], sliceTo(&sentinel_array, 3));
1029	try testing.expectEqualSlices(u16, &sentinel_array, sliceTo(&sentinel_array, 0));
1030	try testing.expectEqualSlices(u16, &sentinel_array, sliceTo(&sentinel_array, 99));
1031	}
1032
1033	try testing.expectEqual(@as(?[]u8, null), sliceTo(@as(?[]u8, null), 0));
1034	}
1035
1036	/// Private helper for sliceTo(). If you want the length, use sliceTo(foo, x).len
1037	fn lenSliceTo(ptr: anytype, comptime end: std.meta.Elem(@TypeOf(ptr))) usize {
1038	switch (@typeInfo(@TypeOf(ptr))) {
1039	.pointer => |ptr_info| switch (ptr_info.size) {
1040	.one => switch (@typeInfo(ptr_info.child)) {
1041	.array => |array_info| {
1042	if (array_info.sentinel()) |s| {
1043	if (s == end) {
1044	return findSentinel(array_info.child, end, ptr);
1045	}
1046	}
1047	return findScalar(array_info.child, ptr, end) orelse array_info.len;
1048	},
1049	else => {},
1050	},
1051	.many => if (ptr_info.sentinel()) |s| {
1052	if (s == end) {
1053	return findSentinel(ptr_info.child, end, ptr);
1054	}
1055	// We're looking for something other than the sentinel,
1056	// but iterating past the sentinel would be a bug so we need
1057	// to check for both.
1058	var i: usize = 0;
1059	while (ptr[i] != end and ptr[i] != s) i += 1;
1060	return i;
1061	} else {
1062	return findSentinel(ptr_info.child, end, @ptrCast(ptr));
1063	},
1064	.c => {
1065	assert(ptr != null);
1066	return findSentinel(ptr_info.child, end, ptr);
1067	},
1068	.slice => {
1069	if (ptr_info.sentinel()) |s| {
1070	if (s == end) {
1071	return findSentinel(ptr_info.child, s, ptr);
1072	}
1073	}
1074	return findScalar(ptr_info.child, ptr, end) orelse ptr.len;
1075	},
1076	},
1077	else => {},
1078	}
1079	@compileError("invalid type given to std.mem.sliceTo: " ++ @typeName(@TypeOf(ptr)));
1080	}
1081
1082	test lenSliceTo {
1083	try testing.expect(lenSliceTo("aoeu", 0) == 4);
1084
1085	{
1086	var array: [5]u16 = [_]u16{ 1, 2, 3, 4, 5 };
1087	try testing.expectEqual(@as(usize, 5), lenSliceTo(&array, 0));
1088	try testing.expectEqual(@as(usize, 3), lenSliceTo(array[0..3], 0));
1089	try testing.expectEqual(@as(usize, 2), lenSliceTo(&array, 3));
1090	try testing.expectEqual(@as(usize, 2), lenSliceTo(array[0..3], 3));
1091
1092	const sentinel_ptr = @as([*:5]u16, @ptrCast(&array));
1093	try testing.expectEqual(@as(usize, 2), lenSliceTo(sentinel_ptr, 3));
1094	try testing.expectEqual(@as(usize, 4), lenSliceTo(sentinel_ptr, 99));
1095
1096	const c_ptr = @as([*c]u16, &array);
1097	try testing.expectEqual(@as(usize, 2), lenSliceTo(c_ptr, 3));
1098
1099	const slice: []u16 = &array;
1100	try testing.expectEqual(@as(usize, 2), lenSliceTo(slice, 3));
1101	try testing.expectEqual(@as(usize, 5), lenSliceTo(slice, 99));
1102
1103	const sentinel_slice: [:5]u16 = array[0..4 :5];
1104	try testing.expectEqual(@as(usize, 2), lenSliceTo(sentinel_slice, 3));
1105	try testing.expectEqual(@as(usize, 4), lenSliceTo(sentinel_slice, 99));
1106	}
1107	{
1108	var sentinel_array: [5:0]u16 = [_:0]u16{ 1, 2, 3, 4, 5 };
1109	try testing.expectEqual(@as(usize, 2), lenSliceTo(&sentinel_array, 3));
1110	try testing.expectEqual(@as(usize, 5), lenSliceTo(&sentinel_array, 0));
1111	try testing.expectEqual(@as(usize, 5), lenSliceTo(&sentinel_array, 99));
1112	}
1113	}
1114
1115	/// Takes a sentinel-terminated pointer and iterates over the memory to find the
1116	/// sentinel and determine the length.
1117	/// `[*c]` pointers are assumed to be non-null and 0-terminated.
1118	pub fn len(value: anytype) usize {
1119	switch (@typeInfo(@TypeOf(value))) {
1120	.pointer => |info| switch (info.size) {
1121	.many => {
1122	const sentinel = info.sentinel() orelse
1123	@compileError("invalid type given to std.mem.len: " ++ @typeName(@TypeOf(value)));
1124	return findSentinel(info.child, sentinel, value);
1125	},
1126	.c => {
1127	assert(value != null);
1128	return findSentinel(info.child, 0, value);
1129	},
1130	else => @compileError("invalid type given to std.mem.len: " ++ @typeName(@TypeOf(value))),
1131	},
1132	else => @compileError("invalid type given to std.mem.len: " ++ @typeName(@TypeOf(value))),
1133	}
1134	}
1135
1136	test len {
1137	var array: [5]u16 = [_]u16{ 1, 2, 0, 4, 5 };
1138	const ptr = @as([*:4]u16, array[0..3 :4]);
1139	try testing.expect(len(ptr) == 3);
1140	const c_ptr = @as([*c]u16, ptr);
1141	try testing.expect(len(c_ptr) == 2);
1142	}
1143
1144	/// Deprecated in favor of `findSentinel`.
1145	pub const indexOfSentinel = findSentinel;
1146
1147	/// Returns the index of the sentinel value in a sentinel-terminated pointer.
1148	/// Linear search through memory until the sentinel is found.
1149	pub fn findSentinel(comptime T: type, comptime sentinel: T, p: [*:sentinel]const T) usize {
1150	var i: usize = 0;
1151	while (p[i] != sentinel) {
1152	i += 1;
1153	}
1154	return i;
1155	}
1156
1157	test "findSentinel vector paths" {
1158	const Types = [_]type{ u8, u16, u32, u64 };
1159	const allocator = std.testing.allocator;
1160	const page_size = std.heap.page_size_min;
1161
1162	inline for (Types) |T| {
1163	const block_len = std.simd.suggestVectorLength(T) orelse continue;
1164
1165	// Allocate three pages so we guarantee a page-crossing address with a full page after
1166	const memory = try allocator.alloc(T, 3 * page_size / @sizeOf(T));
1167	defer allocator.free(memory);
1168	@memset(memory, 0xaa);
1169
1170	// Find starting page-alignment = 0
1171	var start: usize = 0;
1172	const start_addr = @intFromPtr(&memory);
1173	start += (std.mem.alignForward(usize, start_addr, page_size) - start_addr) / @sizeOf(T);
1174	try testing.expect(start < page_size / @sizeOf(T));
1175
1176	// Validate all sub-block alignments
1177	const search_len = page_size / @sizeOf(T);
1178	memory[start + search_len] = 0;
1179	for (0..block_len) |offset| {
1180	try testing.expectEqual(search_len - offset, findSentinel(T, 0, @ptrCast(&memory[start + offset])));
1181	}
1182	memory[start + search_len] = 0xaa;
1183
1184	// Validate page boundary crossing
1185	const start_page_boundary = start + (page_size / @sizeOf(T));
1186	memory[start_page_boundary + block_len] = 0;
1187	for (0..block_len) |offset| {
1188	try testing.expectEqual(2 * block_len - offset, findSentinel(T, 0, @ptrCast(&memory[start_page_boundary - block_len + offset])));
1189	}
1190	}
1191	}
1192
1193	/// Returns true if all elements in a slice are equal to the scalar value provided
1194	pub fn allEqual(comptime T: type, slice: []const T, scalar: T) bool {
1195	for (slice) |item| {
1196	if (item != scalar) return false;
1197	}
1198	return true;
1199	}
1200
1201	/// Remove a set of values from the beginning of a slice.
1202	pub fn trimStart(comptime T: type, slice: []const T, values_to_strip: []const T) []const T {
1203	var begin: usize = 0;
1204	while (begin < slice.len and findScalar(T, values_to_strip, slice[begin]) != null) : (begin += 1) {}
1205	return slice[begin..];
1206	}
1207
1208	test trimStart {
1209	try testing.expectEqualSlices(u8, "foo\n ", trimStart(u8, " foo\n ", " \n"));
1210	}
1211
1212	/// Remove a set of values from the end of a slice.
1213	pub fn trimEnd(comptime T: type, slice: []const T, values_to_strip: []const T) []const T {
1214	var end: usize = slice.len;
1215	while (end > 0 and findScalar(T, values_to_strip, slice[end - 1]) != null) : (end -= 1) {}
1216	return slice[0..end];
1217	}
1218
1219	test trimEnd {
1220	try testing.expectEqualSlices(u8, " foo", trimEnd(u8, " foo\n ", " \n"));
1221	}
1222
1223	/// Remove a set of values from the beginning and end of a slice.
1224	pub fn trim(comptime T: type, slice: []const T, values_to_strip: []const T) []const T {
1225	var begin: usize = 0;
1226	var end: usize = slice.len;
1227	while (begin < end and findScalar(T, values_to_strip, slice[begin]) != null) : (begin += 1) {}
1228	while (end > begin and findScalar(T, values_to_strip, slice[end - 1]) != null) : (end -= 1) {}
1229	return slice[begin..end];
1230	}
1231
1232	test trim {
1233	try testing.expectEqualSlices(u8, "foo", trim(u8, " foo\n ", " \n"));
1234	try testing.expectEqualSlices(u8, "foo", trim(u8, "foo", " \n"));
1235	}
1236
1237	/// Deprecated in favor of `findScalar`.
1238	pub const indexOfScalar = findScalar;
1239
1240	/// Linear search for the index of a scalar value inside a slice.
1241	pub fn findScalar(comptime T: type, slice: []const T, value: T) ?usize {
1242	return findScalarPos(T, slice, 0, value);
1243	}
1244
1245	/// Deprecated in favor of `findScalarLast`.
1246	pub const lastIndexOfScalar = findScalarLast;
1247
1248	/// Linear search for the last index of a scalar value inside a slice.
1249	pub fn findScalarLast(comptime T: type, slice: []const T, value: T) ?usize {
1250	var i: usize = slice.len;
1251	while (i != 0) {
1252	i -= 1;
1253	if (slice[i] == value) return i;
1254	}
1255	return null;
1256	}
1257
1258	/// Deprecated in favor of `findScalarPos`.
1259	pub const indexOfScalarPos = findScalarPos;
1260
1261	/// Linear search for the index of a scalar value inside a slice, starting from a given position.
1262	/// Returns null if the value is not found.
1263	pub fn findScalarPos(comptime T: type, slice: []const T, start_index: usize, value: T) ?usize {
1264	if (start_index >= slice.len) return null;
1265
1266	var i: usize = start_index;
1267	if (use_vectors_for_comparison and
1268	!std.debug.inValgrind() and // https://github.com/ziglang/zig/issues/17717
1269	!@inComptime() and
1270	(@typeInfo(T) == .int or @typeInfo(T) == .float) and std.math.isPowerOfTwo(@bitSizeOf(T)))
1271	{
1272	if (std.simd.suggestVectorLength(T)) |block_len| {
1273	// For Intel Nehalem (2009) and AMD Bulldozer (2012) or later, unaligned loads on aligned data result
1274	// in the same execution as aligned loads. We ignore older arch's here and don't bother pre-aligning.
1275	//
1276	// Use `std.simd.suggestVectorLength(T)` to get the same alignment as used in this function
1277	// however this usually isn't necessary unless your arch has a performance penalty due to this.
1278	//
1279	// This may differ for other arch's. Arm for example costs a cycle when loading across a cache
1280	// line so explicit alignment prologues may be worth exploration.
1281
1282	// Unrolling here is ~10% improvement. We can then do one bounds check every 2 blocks
1283	// instead of one which adds up.
1284	const Block = @Vector(block_len, T);
1285	if (i + 2 * block_len < slice.len) {
1286	const mask: Block = @splat(value);
1287	while (true) {
1288	inline for (0..2) |_| {
1289	const block: Block = slice[i..][0..block_len].*;
1290	const matches = block == mask;
1291	if (@reduce(.Or, matches)) {
1292	return i + std.simd.firstTrue(matches).?;
1293	}
1294	i += block_len;
1295	}
1296	if (i + 2 * block_len >= slice.len) break;
1297	}
1298	}
1299
1300	// {block_len, block_len / 2} check
1301	inline for (0..2) |j| {
1302	const block_x_len = block_len / (1 << j);
1303	comptime if (block_x_len < 4) break;
1304
1305	const BlockX = @Vector(block_x_len, T);
1306	if (i + block_x_len < slice.len) {
1307	const mask: BlockX = @splat(value);
1308	const block: BlockX = slice[i..][0..block_x_len].*;
1309	const matches = block == mask;
1310	if (@reduce(.Or, matches)) {
1311	return i + std.simd.firstTrue(matches).?;
1312	}
1313	i += block_x_len;
1314	}
1315	}
1316	}
1317	}
1318
1319	for (slice[i..], i..) |c, j| {
1320	if (c == value) return j;
1321	}
1322	return null;
1323	}
1324
1325	test findScalarPos {
1326	const Types = [_]type{ u8, u16, u32, u64 };
1327
1328	inline for (Types) |T| {
1329	var memory: [64 / @sizeOf(T)]T = undefined;
1330	@memset(&memory, 0xaa);
1331	memory[memory.len - 1] = 0;
1332
1333	for (0..memory.len) |i| {
1334	try testing.expectEqual(memory.len - i - 1, findScalarPos(T, memory[i..], 0, 0).?);
1335	}
1336	}
1337	}
1338
1339	/// Deprecated in favor of `findAny`.
1340	pub const indexOfAny = findAny;
1341
1342	/// Linear search for the index of any value in the provided list inside a slice.
1343	/// Returns null if no values are found.
1344	pub fn findAny(comptime T: type, slice: []const T, values: []const T) ?usize {
1345	return findAnyPos(T, slice, 0, values);
1346	}
1347
1348	/// Deprecated in favor of `findLastAny`.
1349	pub const lastIndexOfAny = findLastAny;
1350
1351	/// Linear search for the last index of any value in the provided list inside a slice.
1352	/// Returns null if no values are found.
1353	pub fn findLastAny(comptime T: type, slice: []const T, values: []const T) ?usize {
1354	var i: usize = slice.len;
1355	while (i != 0) {
1356	i -= 1;
1357	for (values) |value| {
1358	if (slice[i] == value) return i;
1359	}
1360	}
1361	return null;
1362	}
1363
1364	/// Deprecated in favor of `findAnyPos`.
1365	pub const indexOfAnyPos = findAnyPos;
1366
1367	/// Linear search for the index of any value in the provided list inside a slice, starting from a given position.
1368	/// Returns null if no values are found.
1369	pub fn findAnyPos(comptime T: type, slice: []const T, start_index: usize, values: []const T) ?usize {
1370	if (start_index >= slice.len) return null;
1371	for (slice[start_index..], start_index..) |c, i| {
1372	for (values) |value| {
1373	if (c == value) return i;
1374	}
1375	}
1376	return null;
1377	}
1378
1379	/// Deprecated in favor of `findNone`.
1380	pub const indexOfNone = findNone;
1381
1382	/// Find the first item in `slice` which is not contained in `values`.
1383	///
1384	/// Comparable to `strspn` in the C standard library.
1385	pub fn findNone(comptime T: type, slice: []const T, values: []const T) ?usize {
1386	return findNonePos(T, slice, 0, values);
1387	}
1388
1389	test findNone {
1390	try testing.expect(findNone(u8, "abc123", "123").? == 0);
1391	try testing.expect(findLastNone(u8, "abc123", "123").? == 2);
1392	try testing.expect(findNone(u8, "123abc", "123").? == 3);
1393	try testing.expect(findLastNone(u8, "123abc", "123").? == 5);
1394	try testing.expect(findNone(u8, "123123", "123") == null);
1395	try testing.expect(findNone(u8, "333333", "123") == null);
1396
1397	try testing.expect(findNonePos(u8, "abc123", 3, "321") == null);
1398	}
1399
1400	/// Deprecated in favor of `findLastNone`.
1401	pub const lastIndexOfNone = findLastNone;
1402
1403	/// Find the last item in `slice` which is not contained in `values`.
1404	///
1405	/// Like `strspn` in the C standard library, but searches from the end.
1406	pub fn findLastNone(comptime T: type, slice: []const T, values: []const T) ?usize {
1407	var i: usize = slice.len;
1408	outer: while (i != 0) {
1409	i -= 1;
1410	for (values) |value| {
1411	if (slice[i] == value) continue :outer;
1412	}
1413	return i;
1414	}
1415	return null;
1416	}
1417
1418	pub const indexOfNonePos = findNonePos;
1419
1420	/// Find the first item in `slice[start_index..]` which is not contained in `values`.
1421	/// The returned index will be relative to the start of `slice`, and never less than `start_index`.
1422	///
1423	/// Comparable to `strspn` in the C standard library.
1424	pub fn findNonePos(comptime T: type, slice: []const T, start_index: usize, values: []const T) ?usize {
1425	if (start_index >= slice.len) return null;
1426	outer: for (slice[start_index..], start_index..) |c, i| {
1427	for (values) |value| {
1428	if (c == value) continue :outer;
1429	}
1430	return i;
1431	}
1432	return null;
1433	}
1434
1435	/// Deprecated in favor of `find`.
1436	pub const indexOf = find;
1437
1438	/// Search for needle in haystack and return the index of the first occurrence.
1439	/// Uses Boyer-Moore-Horspool algorithm on large inputs; linear search on small inputs.
1440	/// Returns null if needle is not found.
1441	pub fn find(comptime T: type, haystack: []const T, needle: []const T) ?usize {
1442	return findPos(T, haystack, 0, needle);
1443	}
1444
1445	/// Deprecated in favor of `findLastLinear`.
1446	pub const lastIndexOfLinear = findLastLinear;
1447
1448	/// Find the index in a slice of a sub-slice, searching from the end backwards.
1449	/// To start looking at a different index, slice the haystack first.
1450	/// Consider using `lastIndexOf` instead of this, which will automatically use a
1451	/// more sophisticated algorithm on larger inputs.
1452	pub fn findLastLinear(comptime T: type, haystack: []const T, needle: []const T) ?usize {
1453	if (needle.len > haystack.len) return null;
1454	var i: usize = haystack.len - needle.len;
1455	while (true) : (i -= 1) {
1456	if (mem.eql(T, haystack[i..][0..needle.len], needle)) return i;
1457	if (i == 0) return null;
1458	}
1459	}
1460
1461	pub const indexOfPosLinear = findPosLinear;
1462
1463	/// Consider using `findPos` instead of this, which will automatically use a
1464	/// more sophisticated algorithm on larger inputs.
1465	pub fn findPosLinear(comptime T: type, haystack: []const T, start_index: usize, needle: []const T) ?usize {
1466	if (needle.len > haystack.len) return null;
1467	var i: usize = start_index;
1468	const end = haystack.len - needle.len;
1469	while (i <= end) : (i += 1) {
1470	if (eql(T, haystack[i..][0..needle.len], needle)) return i;
1471	}
1472	return null;
1473	}
1474
1475	test findPosLinear {
1476	try testing.expectEqual(0, findPosLinear(u8, "", 0, ""));
1477	try testing.expectEqual(0, findPosLinear(u8, "123", 0, ""));
1478
1479	try testing.expectEqual(null, findPosLinear(u8, "", 0, "1"));
1480	try testing.expectEqual(0, findPosLinear(u8, "1", 0, "1"));
1481	try testing.expectEqual(null, findPosLinear(u8, "2", 0, "1"));
1482	try testing.expectEqual(1, findPosLinear(u8, "21", 0, "1"));
1483	try testing.expectEqual(null, findPosLinear(u8, "222", 0, "1"));
1484
1485	try testing.expectEqual(null, findPosLinear(u8, "", 0, "12"));
1486	try testing.expectEqual(null, findPosLinear(u8, "1", 0, "12"));
1487	try testing.expectEqual(null, findPosLinear(u8, "2", 0, "12"));
1488	try testing.expectEqual(0, findPosLinear(u8, "12", 0, "12"));
1489	try testing.expectEqual(null, findPosLinear(u8, "21", 0, "12"));
1490	try testing.expectEqual(1, findPosLinear(u8, "212", 0, "12"));
1491	try testing.expectEqual(0, findPosLinear(u8, "122", 0, "12"));
1492	try testing.expectEqual(1, findPosLinear(u8, "212112", 0, "12"));
1493	}
1494
1495	fn boyerMooreHorspoolPreprocessReverse(pattern: []const u8, table: *[256]usize) void {
1496	for (table) |*c| {
1497	c.* = pattern.len;
1498	}
1499
1500	var i: usize = pattern.len - 1;
1501	// The first item is intentionally ignored and the skip size will be pattern.len.
1502	// This is the standard way Boyer-Moore-Horspool is implemented.
1503	while (i > 0) : (i -= 1) {
1504	table[pattern[i]] = i;
1505	}
1506	}
1507
1508	fn boyerMooreHorspoolPreprocess(pattern: []const u8, table: *[256]usize) void {
1509	for (table) |*c| {
1510	c.* = pattern.len;
1511	}
1512
1513	var i: usize = 0;
1514	// The last item is intentionally ignored and the skip size will be pattern.len.
1515	// This is the standard way Boyer-Moore-Horspool is implemented.
1516	while (i < pattern.len - 1) : (i += 1) {
1517	table[pattern[i]] = pattern.len - 1 - i;
1518	}
1519	}
1520
1521	/// Deprecated in favor of `find`.
1522	pub const lastIndexOf = findLast;
1523
1524	/// Find the index in a slice of a sub-slice, searching from the end backwards.
1525	/// To start looking at a different index, slice the haystack first.
1526	/// Uses the Reverse Boyer-Moore-Horspool algorithm on large inputs;
1527	/// `lastIndexOfLinear` on small inputs.
1528	pub fn findLast(comptime T: type, haystack: []const T, needle: []const T) ?usize {
1529	if (needle.len > haystack.len) return null;
1530	if (needle.len == 0) return haystack.len;
1531
1532	if (!std.meta.hasUniqueRepresentation(T) or haystack.len < 52 or needle.len <= 4)
1533	return findLastLinear(T, haystack, needle);
1534
1535	const haystack_bytes = sliceAsBytes(haystack);
1536	const needle_bytes = sliceAsBytes(needle);
1537
1538	var skip_table: [256]usize = undefined;
1539	boyerMooreHorspoolPreprocessReverse(needle_bytes, skip_table[0..]);
1540
1541	var i: usize = haystack_bytes.len - needle_bytes.len;
1542	while (true) {
1543	if (i % @sizeOf(T) == 0 and mem.eql(u8, haystack_bytes[i .. i + needle_bytes.len], needle_bytes)) {
1544	return @divExact(i, @sizeOf(T));
1545	}
1546	const skip = skip_table[haystack_bytes[i]];
1547	if (skip > i) break;
1548	i -= skip;
1549	}
1550
1551	return null;
1552	}
1553
1554	/// Deprecated in favor of `findPos`.
1555	pub const indexOfPos = findPos;
1556
1557	/// Uses Boyer-Moore-Horspool algorithm on large inputs; `findPosLinear` on small inputs.
1558	pub fn findPos(comptime T: type, haystack: []const T, start_index: usize, needle: []const T) ?usize {
1559	if (needle.len > haystack.len) return null;
1560	if (needle.len < 2) {
1561	if (needle.len == 0) return start_index;
1562	// findScalarPos is significantly faster than findPosLinear
1563	return findScalarPos(T, haystack, start_index, needle[0]);
1564	}
1565
1566	if (!std.meta.hasUniqueRepresentation(T) or haystack.len < 52 or needle.len <= 4)
1567	return findPosLinear(T, haystack, start_index, needle);
1568
1569	const haystack_bytes = sliceAsBytes(haystack);
1570	const needle_bytes = sliceAsBytes(needle);
1571
1572	var skip_table: [256]usize = undefined;
1573	boyerMooreHorspoolPreprocess(needle_bytes, skip_table[0..]);
1574
1575	var i: usize = start_index * @sizeOf(T);
1576	while (i <= haystack_bytes.len - needle_bytes.len) {
1577	if (i % @sizeOf(T) == 0 and mem.eql(u8, haystack_bytes[i .. i + needle_bytes.len], needle_bytes)) {
1578	return @divExact(i, @sizeOf(T));
1579	}
1580	i += skip_table[haystack_bytes[i + needle_bytes.len - 1]];
1581	}
1582
1583	return null;
1584	}
1585
1586	test find {
1587	try testing.expect(find(u8, "one two three four five six seven eight nine ten eleven", "three four").? == 8);
1588	try testing.expect(findLast(u8, "one two three four five six seven eight nine ten eleven", "three four").? == 8);
1589	try testing.expect(find(u8, "one two three four five six seven eight nine ten eleven", "two two") == null);
1590	try testing.expect(findLast(u8, "one two three four five six seven eight nine ten eleven", "two two") == null);
1591
1592	try testing.expect(find(u8, "one two three four five six seven eight nine ten", "").? == 0);
1593	try testing.expect(findLast(u8, "one two three four five six seven eight nine ten", "").? == 48);
1594
1595	try testing.expect(find(u8, "one two three four", "four").? == 14);
1596	try testing.expect(findLast(u8, "one two three two four", "two").? == 14);
1597	try testing.expect(find(u8, "one two three four", "gour") == null);
1598	try testing.expect(findLast(u8, "one two three four", "gour") == null);
1599	try testing.expect(find(u8, "foo", "foo").? == 0);
1600	try testing.expect(findLast(u8, "foo", "foo").? == 0);
1601	try testing.expect(find(u8, "foo", "fool") == null);
1602	try testing.expect(findLast(u8, "foo", "lfoo") == null);
1603	try testing.expect(findLast(u8, "foo", "fool") == null);
1604
1605	try testing.expect(find(u8, "foo foo", "foo").? == 0);
1606	try testing.expect(findLast(u8, "foo foo", "foo").? == 4);
1607	try testing.expect(findLastAny(u8, "boo, cat", "abo").? == 6);
1608	try testing.expect(findScalarLast(u8, "boo", 'o').? == 2);
1609	}
1610
1611	test "find multibyte" {
1612	{
1613	// make haystack and needle long enough to trigger Boyer-Moore-Horspool algorithm
1614	const haystack = @as([100]u16, @splat(0)) ++ [_]u16{ 0xbbaa, 0xccbb, 0xddcc, 0xeedd, 0xffee, 0x00ff };
1615	const needle = [_]u16{ 0xbbaa, 0xccbb, 0xddcc, 0xeedd, 0xffee };
1616	try testing.expectEqual(findPos(u16, &haystack, 0, &needle), 100);
1617
1618	// check for misaligned false positives (little and big endian)
1619	const needleLE = [_]u16{ 0xbbbb, 0xcccc, 0xdddd, 0xeeee, 0xffff };
1620	try testing.expectEqual(findPos(u16, &haystack, 0, &needleLE), null);
1621	const needleBE = [_]u16{ 0xaacc, 0xbbdd, 0xccee, 0xddff, 0xee00 };
1622	try testing.expectEqual(findPos(u16, &haystack, 0, &needleBE), null);
1623	}
1624
1625	{
1626	// make haystack and needle long enough to trigger Boyer-Moore-Horspool algorithm
1627	const haystack = [_]u16{ 0xbbaa, 0xccbb, 0xddcc, 0xeedd, 0xffee, 0x00ff } ++ @as([100]u16, @splat(0));
1628	const needle = [_]u16{ 0xbbaa, 0xccbb, 0xddcc, 0xeedd, 0xffee };
1629	try testing.expectEqual(findLast(u16, &haystack, &needle), 0);
1630
1631	// check for misaligned false positives (little and big endian)
1632	const needleLE = [_]u16{ 0xbbbb, 0xcccc, 0xdddd, 0xeeee, 0xffff };
1633	try testing.expectEqual(findLast(u16, &haystack, &needleLE), null);
1634	const needleBE = [_]u16{ 0xaacc, 0xbbdd, 0xccee, 0xddff, 0xee00 };
1635	try testing.expectEqual(findLast(u16, &haystack, &needleBE), null);
1636	}
1637	}
1638
1639	test "findPos empty needle" {
1640	try testing.expectEqual(findPos(u8, "abracadabra", 5, ""), 5);
1641	}
1642
1643	/// Returns the number of needles inside the haystack
1644	/// needle.len must be > 0
1645	/// does not count overlapping needles
1646	pub fn count(comptime T: type, haystack: []const T, needle: []const T) usize {
1647	if (needle.len == 1) return countScalar(T, haystack, needle[0]);
1648	assert(needle.len > 0);
1649	var i: usize = 0;
1650	var found: usize = 0;
1651
1652	while (findPos(T, haystack, i, needle)) |idx| {
1653	i = idx + needle.len;
1654	found += 1;
1655	}
1656
1657	return found;
1658	}
1659
1660	test count {
1661	try testing.expect(count(u8, "", "h") == 0);
1662	try testing.expect(count(u8, "h", "h") == 1);
1663	try testing.expect(count(u8, "hh", "h") == 2);
1664	try testing.expect(count(u8, "world!", "hello") == 0);
1665	try testing.expect(count(u8, "hello world!", "hello") == 1);
1666	try testing.expect(count(u8, " abcabc abc", "abc") == 3);
1667	try testing.expect(count(u8, "udexdcbvbruhasdrw", "bruh") == 1);
1668	try testing.expect(count(u8, "foo bar", "o bar") == 1);
1669	try testing.expect(count(u8, "foofoofoo", "foo") == 3);
1670	try testing.expect(count(u8, "fffffff", "ff") == 3);
1671	try testing.expect(count(u8, "owowowu", "owowu") == 1);
1672	}
1673
1674	/// Returns the number of times `element` appears in a slice of memory.
1675	pub fn countScalar(comptime T: type, list: []const T, element: T) usize {
1676	const n = list.len;
1677	var i: usize = 0;
1678	var found: usize = 0;
1679
1680	if (use_vectors_for_comparison and
1681	(@typeInfo(T) == .int or @typeInfo(T) == .float) and std.math.isPowerOfTwo(@bitSizeOf(T)))
1682	{
1683	if (std.simd.suggestVectorLength(T)) |block_size| {
1684	const Block = @Vector(block_size, T);
1685
1686	const letter_mask: Block = @splat(element);
1687	while (n - i >= block_size) : (i += block_size) {
1688	const haystack_block: Block = list[i..][0..block_size].*;
1689	found += std.simd.countTrues(letter_mask == haystack_block);
1690	}
1691	}
1692	}
1693
1694	for (list[i..n]) |item| {
1695	found += @intFromBool(item == element);
1696	}
1697
1698	return found;
1699	}
1700
1701	test countScalar {
1702	try testing.expectEqual(0, countScalar(u8, "", 'h'));
1703	try testing.expectEqual(1, countScalar(u8, "h", 'h'));
1704	try testing.expectEqual(2, countScalar(u8, "hh", 'h'));
1705	try testing.expectEqual(2, countScalar(u8, "ahhb", 'h'));
1706	try testing.expectEqual(3, countScalar(u8, " abcabc abc", 'b'));
1707	}
1708
1709	/// Returns true if the haystack contains expected_count or more needles
1710	/// needle.len must be > 0
1711	/// does not count overlapping needles
1712	//
1713	/// See also: `containsAtLeastScalar`
1714	pub fn containsAtLeast(comptime T: type, haystack: []const T, expected_count: usize, needle: []const T) bool {
1715	if (needle.len == 1) return containsAtLeastScalar(T, haystack, needle[0], expected_count);
1716	assert(needle.len > 0);
1717	if (expected_count == 0) return true;
1718
1719	var i: usize = 0;
1720	var found: usize = 0;
1721
1722	while (findPos(T, haystack, i, needle)) |idx| {
1723	i = idx + needle.len;
1724	found += 1;
1725	if (found == expected_count) return true;
1726	}
1727	return false;
1728	}
1729
1730	test containsAtLeast {
1731	try testing.expect(containsAtLeast(u8, "aa", 0, "a"));
1732	try testing.expect(containsAtLeast(u8, "aa", 1, "a"));
1733	try testing.expect(containsAtLeast(u8, "aa", 2, "a"));
1734	try testing.expect(!containsAtLeast(u8, "aa", 3, "a"));
1735
1736	try testing.expect(containsAtLeast(u8, "radaradar", 1, "radar"));
1737	try testing.expect(!containsAtLeast(u8, "radaradar", 2, "radar"));
1738
1739	try testing.expect(containsAtLeast(u8, "radarradaradarradar", 3, "radar"));
1740	try testing.expect(!containsAtLeast(u8, "radarradaradarradar", 4, "radar"));
1741
1742	try testing.expect(containsAtLeast(u8, " radar radar ", 2, "radar"));
1743	try testing.expect(!containsAtLeast(u8, " radar radar ", 3, "radar"));
1744	}
1745
1746	/// Returns true if `element` appears at least `minimum` number of times in `list`.
1747	//
1748	/// Related:
1749	/// * `containsAtLeast`
1750	/// * `countScalar`
1751	pub fn containsAtLeastScalar(comptime T: type, list: []const T, element: T, minimum: usize) bool {
1752	const n = list.len;
1753	var i: usize = 0;
1754	var found: usize = 0;
1755
1756	if (use_vectors_for_comparison and
1757	(@typeInfo(T) == .int or @typeInfo(T) == .float) and std.math.isPowerOfTwo(@bitSizeOf(T)))
1758	{
1759	if (std.simd.suggestVectorLength(T)) |block_size| {
1760	const Block = @Vector(block_size, T);
1761
1762	const letter_mask: Block = @splat(element);
1763	while (n - i >= block_size) : (i += block_size) {
1764	const haystack_block: Block = list[i..][0..block_size].*;
1765	found += std.simd.countTrues(letter_mask == haystack_block);
1766	if (found >= minimum) return true;
1767	}
1768	}
1769	}
1770
1771	for (list[i..n]) |item| {
1772	found += @intFromBool(item == element);
1773	if (found >= minimum) return true;
1774	}
1775
1776	return false;
1777	}
1778
1779	test containsAtLeastScalar {
1780	try testing.expect(containsAtLeastScalar(u8, "aa", 'a', 0));
1781	try testing.expect(containsAtLeastScalar(u8, "aa", 'a', 1));
1782	try testing.expect(containsAtLeastScalar(u8, "aa", 'a', 2));
1783	try testing.expect(!containsAtLeastScalar(u8, "aa", 'a', 3));
1784
1785	try testing.expect(containsAtLeastScalar(u8, "adadda", 'd', 3));
1786	try testing.expect(!containsAtLeastScalar(u8, "adadda", 'd', 4));
1787	}
1788
1789	/// Reads an integer from memory with size equal to bytes.len.
1790	/// ReturnType specifies the return type, which must be large enough to store
1791	/// the result.
1792	pub fn readVarInt(comptime ReturnType: type, bytes: []const u8, endian: Endian) ReturnType {
1793	assert(@typeInfo(ReturnType).int.bits >= bytes.len * 8);
1794	const bits = @typeInfo(ReturnType).int.bits;
1795	const signedness = @typeInfo(ReturnType).int.signedness;
1796	const WorkType = @Int(signedness, @max(16, bits));
1797	var result: WorkType = 0;
1798	switch (endian) {
1799	.big => {
1800	for (bytes) |b| {
1801	result = (result << 8) | b;
1802	}
1803	},
1804	.little => {
1805	const ShiftType = math.Log2Int(WorkType);
1806	for (bytes, 0..) |b, index| {
1807	result = result | (@as(WorkType, b) << @as(ShiftType, @intCast(index * 8)));
1808	}
1809	},
1810	}
1811	return @truncate(result);
1812	}
1813
1814	test readVarInt {
1815	try testing.expect(readVarInt(u0, &[_]u8{}, .big) == 0x0);
1816	try testing.expect(readVarInt(u0, &[_]u8{}, .little) == 0x0);
1817	try testing.expect(readVarInt(u8, &[_]u8{0x12}, .big) == 0x12);
1818	try testing.expect(readVarInt(u8, &[_]u8{0xde}, .little) == 0xde);
1819	try testing.expect(readVarInt(u16, &[_]u8{ 0x12, 0x34 }, .big) == 0x1234);
1820	try testing.expect(readVarInt(u16, &[_]u8{ 0x12, 0x34 }, .little) == 0x3412);
1821
1822	try testing.expect(readVarInt(i8, &[_]u8{0xff}, .big) == -1);
1823	try testing.expect(readVarInt(i8, &[_]u8{0xfe}, .little) == -2);
1824	try testing.expect(readVarInt(i16, &[_]u8{ 0xff, 0xfd }, .big) == -3);
1825	try testing.expect(readVarInt(i16, &[_]u8{ 0xfc, 0xff }, .little) == -4);
1826
1827	// Return type can be oversized (bytes.len * 8 < @typeInfo(ReturnType).int.bits)
1828	try testing.expect(readVarInt(u9, &[_]u8{0x12}, .little) == 0x12);
1829	try testing.expect(readVarInt(u9, &[_]u8{0xde}, .big) == 0xde);
1830	try testing.expect(readVarInt(u80, &[_]u8{ 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0, 0x24 }, .big) == 0x123456789abcdef024);
1831	try testing.expect(readVarInt(u80, &[_]u8{ 0xec, 0x10, 0x32, 0x54, 0x76, 0x98, 0xba, 0xdc, 0xfe }, .little) == 0xfedcba9876543210ec);
1832
1833	try testing.expect(readVarInt(i9, &[_]u8{0xff}, .big) == 0xff);
1834	try testing.expect(readVarInt(i9, &[_]u8{0xfe}, .little) == 0xfe);
1835	}
1836
1837	/// Loads an integer from packed memory with provided bit_count, bit_offset, and signedness.
1838	/// Asserts that T is large enough to store the read value.
1839	pub fn readVarPackedInt(
1840	comptime T: type,
1841	bytes: []const u8,
1842	bit_offset: usize,
1843	bit_count: usize,
1844	endian: std.builtin.Endian,
1845	signedness: std.builtin.Signedness,
1846	) T {
1847	const uN = @Int(.unsigned, @bitSizeOf(T));
1848	const iN = @Int(.signed, @bitSizeOf(T));
1849	const Log2N = std.math.Log2Int(T);
1850
1851	const read_size = (bit_count + (bit_offset % 8) + 7) / 8;
1852	const bit_shift = @as(u3, @intCast(bit_offset % 8));
1853	const pad = @as(Log2N, @intCast(@bitSizeOf(T) - bit_count));
1854
1855	const lowest_byte = switch (endian) {
1856	.big => bytes.len - (bit_offset / 8) - read_size,
1857	.little => bit_offset / 8,
1858	};
1859	const read_bytes = bytes[lowest_byte..][0..read_size];
1860
1861	if (@bitSizeOf(T) <= 8) {
1862	// These are the same shifts/masks we perform below, but adds `@truncate`/`@intCast`
1863	// where needed since int is smaller than a byte.
1864	const value: uN = if (read_size == 1) b: {
1865	break :b @truncate(read_bytes[0] >> bit_shift);
1866	} else b: {
1867	const i: u1 = @intFromBool(endian == .big);
1868	const head: uN = @truncate(read_bytes[i] >> bit_shift);
1869	const tail_shift: Log2N = @intCast(@as(u4, 8) - bit_shift);
1870	const tail: uN = @truncate(read_bytes[1 - i]);
1871	break :b (tail << tail_shift) | head;
1872	};
1873	switch (signedness) {
1874	.signed => return @intCast((@as(iN, @bitCast(value)) << pad) >> pad),
1875	.unsigned => return @intCast((value << pad) >> pad),
1876	}
1877	}
1878
1879	// Copy the value out (respecting endianness), accounting for bit_shift
1880	var int: uN = 0;
1881	switch (endian) {
1882	.big => {
1883	for (read_bytes[0 .. read_size - 1]) |elem| {
1884	int = elem | (int << 8);
1885	}
1886	int = (read_bytes[read_size - 1] >> bit_shift) | (int << (@as(u4, 8) - bit_shift));
1887	},
1888	.little => {
1889	int = read_bytes[0] >> bit_shift;
1890	for (read_bytes[1..], 0..) |elem, i| {
1891	int |= (@as(uN, elem) << @as(Log2N, @intCast((8 * (i + 1) - bit_shift))));
1892	}
1893	},
1894	}
1895	switch (signedness) {
1896	.signed => return @intCast((@as(iN, @bitCast(int)) << pad) >> pad),
1897	.unsigned => return @intCast((int << pad) >> pad),
1898	}
1899	}
1900
1901	test readVarPackedInt {
1902	const T = packed struct(u16) { a: u3, b: u7, c: u6 };
1903	var st = T{ .a = 1, .b = 2, .c = 4 };
1904	const b_field = readVarPackedInt(u64, std.mem.asBytes(&st), @bitOffsetOf(T, "b"), 7, builtin.cpu.arch.endian(), .unsigned);
1905	try std.testing.expectEqual(st.b, b_field);
1906	}
1907
1908	/// Reads an integer from memory with bit count specified by T.
1909	/// The bit count of T must be evenly divisible by 8.
1910	/// This function cannot fail and cannot cause undefined behavior.
1911	pub inline fn readInt(comptime T: type, buffer: *const [@divExact(@typeInfo(T).int.bits, 8)]u8, endian: Endian) T {
1912	// Zig's logical bit order aligns with a little-endian byte array, so when reading in big-endian
1913	// we must `@byteSwap` the int after we `@bitCast` to it.
1914	const little_val: T = @bitCast(buffer.*);
1915	return switch (endian) {
1916	.little => little_val,
1917	.big => @byteSwap(little_val),
1918	};
1919	}
1920
1921	test readInt {
1922	try testing.expect(readInt(u0, &[_]u8{}, .big) == 0x0);
1923	try testing.expect(readInt(u0, &[_]u8{}, .little) == 0x0);
1924
1925	try testing.expect(readInt(u8, &[_]u8{0x32}, .big) == 0x32);
1926	try testing.expect(readInt(u8, &[_]u8{0x12}, .little) == 0x12);
1927
1928	try testing.expect(readInt(u16, &[_]u8{ 0x12, 0x34 }, .big) == 0x1234);
1929	try testing.expect(readInt(u16, &[_]u8{ 0x12, 0x34 }, .little) == 0x3412);
1930
1931	try testing.expect(readInt(u72, &[_]u8{ 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0, 0x24 }, .big) == 0x123456789abcdef024);
1932	try testing.expect(readInt(u72, &[_]u8{ 0xec, 0x10, 0x32, 0x54, 0x76, 0x98, 0xba, 0xdc, 0xfe }, .little) == 0xfedcba9876543210ec);
1933
1934	try testing.expect(readInt(i8, &[_]u8{0xff}, .big) == -1);
1935	try testing.expect(readInt(i8, &[_]u8{0xfe}, .little) == -2);
1936
1937	try testing.expect(readInt(i16, &[_]u8{ 0xff, 0xfd }, .big) == -3);
1938	try testing.expect(readInt(i16, &[_]u8{ 0xfc, 0xff }, .little) == -4);
1939
1940	try moreReadIntTests();
1941	try comptime moreReadIntTests();
1942	}
1943
1944	fn readPackedIntLittle(comptime T: type, bytes: []const u8, bit_offset: usize) T {
1945	const uN = @Int(.unsigned, @bitSizeOf(T));
1946	const Log2N = std.math.Log2Int(T);
1947
1948	const bit_count = @as(usize, @bitSizeOf(T));
1949	const bit_shift = @as(u3, @intCast(bit_offset % 8));
1950
1951	const load_size = @divCeil(bit_count, 8);
1952	const load_tail_bits = @as(u3, @intCast((load_size * 8) - bit_count));
1953	const LoadInt = @Int(.unsigned, load_size * 8);
1954
1955	if (bit_count == 0)
1956	return 0;
1957
1958	// Read by loading a LoadInt, and then follow it up with a 1-byte read
1959	// of the tail if bit_offset pushed us over a byte boundary.
1960	const read_bytes = bytes[bit_offset / 8 ..];
1961	const val: uN = @truncate(readInt(LoadInt, read_bytes[0..load_size], .little) >> bit_shift);
1962	if (bit_shift > load_tail_bits) {
1963	const tail_bits = @as(Log2N, @intCast(bit_shift - load_tail_bits));
1964	const tail_byte = read_bytes[load_size];
1965	const tail_truncated = if (bit_count < 8) @as(uN, @truncate(tail_byte)) else @as(uN, tail_byte);
1966	return @bitCast(val | (tail_truncated << (@as(Log2N, @truncate(bit_count)) -% tail_bits)));
1967	} else {
1968	return @bitCast(val);
1969	}
1970	}
1971
1972	fn readPackedIntBig(comptime T: type, bytes: []const u8, bit_offset: usize) T {
1973	const uN = @Int(.unsigned, @bitSizeOf(T));
1974	const Log2N = std.math.Log2Int(T);
1975
1976	const bit_count = @as(usize, @bitSizeOf(T));
1977	const bit_shift = @as(u3, @intCast(bit_offset % 8));
1978	const byte_count = @divCeil(@as(usize, bit_shift) + bit_count, 8);
1979
1980	const load_size = @divCeil(bit_count, 8);
1981	const load_tail_bits = @as(u3, @intCast((load_size * 8) - bit_count));
1982	const LoadInt = @Int(.unsigned, load_size * 8);
1983
1984	if (bit_count == 0)
1985	return 0;
1986
1987	// Read by loading a LoadInt, and then follow it up with a 1-byte read
1988	// of the tail if bit_offset pushed us over a byte boundary.
1989	const end = bytes.len - (bit_offset / 8);
1990	const read_bytes = bytes[(end - byte_count)..end];
1991	const val = @as(uN, @truncate(readInt(LoadInt, bytes[(end - load_size)..end][0..load_size], .big) >> bit_shift));
1992	if (bit_shift > load_tail_bits) {
1993	const tail_bits = @as(Log2N, @intCast(bit_shift - load_tail_bits));
1994	const tail_byte = if (bit_count < 8) @as(uN, @truncate(read_bytes[0])) else @as(uN, read_bytes[0]);
1995	return @bitCast(val | (tail_byte << (@as(Log2N, @truncate(bit_count)) -% tail_bits)));
1996	} else {
1997	return @bitCast(val);
1998	}
1999	}
2000
2001	/// Loads an integer from packed memory.
2002	/// Asserts that buffer contains at least bit_offset + @bitSizeOf(T) bits.
2003	pub fn readPackedInt(comptime T: type, bytes: []const u8, bit_offset: usize, endian: Endian) T {
2004	switch (endian) {
2005	.little => return readPackedIntLittle(T, bytes, bit_offset),
2006	.big => return readPackedIntBig(T, bytes, bit_offset),
2007	}
2008	}
2009
2010	test readPackedInt {
2011	const T = packed struct(u16) { a: u3, b: u7, c: u6 };
2012	var st = T{ .a = 1, .b = 2, .c = 4 };
2013	const b_field = readPackedInt(u7, std.mem.asBytes(&st), @bitOffsetOf(T, "b"), builtin.cpu.arch.endian());
2014	try std.testing.expectEqual(st.b, b_field);
2015	}
2016
2017	test "comptime read/write int" {
2018	comptime {
2019	var bytes: [2]u8 = undefined;
2020	writeInt(u16, &bytes, 0x1234, .little);
2021	const result = readInt(u16, &bytes, .big);
2022	try testing.expect(result == 0x3412);
2023	}
2024	comptime {
2025	var bytes: [2]u8 = undefined;
2026	writeInt(u16, &bytes, 0x1234, .big);
2027	const result = readInt(u16, &bytes, .little);
2028	try testing.expect(result == 0x3412);
2029	}
2030	}
2031
2032	/// Writes an integer to memory, storing it in twos-complement.
2033	/// This function always succeeds, has defined behavior for all inputs, but
2034	/// the integer bit width must be divisible by 8.
2035	pub inline fn writeInt(comptime T: type, buffer: *[@divExact(@typeInfo(T).int.bits, 8)]u8, value: T, endian: Endian) void {
2036	// Zig's logical bit order aligns with a little-endian byte array, so when writing in big-endian
2037	// we must `@byteSwap` the int before we `@bitCast` to an array.
2038	buffer.* = switch (endian) {
2039	.little => @bitCast(value),
2040	.big => @bitCast(@byteSwap(value)),
2041	};
2042	}
2043
2044	test writeInt {
2045	var buf0: [0]u8 = undefined;
2046	var buf1: [1]u8 = undefined;
2047	var buf2: [2]u8 = undefined;
2048	var buf9: [9]u8 = undefined;
2049
2050	writeInt(u0, &buf0, 0x0, .big);
2051	try testing.expect(eql(u8, buf0[0..], &[_]u8{}));
2052	writeInt(u0, &buf0, 0x0, .little);
2053	try testing.expect(eql(u8, buf0[0..], &[_]u8{}));
2054
2055	writeInt(u8, &buf1, 0x12, .big);
2056	try testing.expect(eql(u8, buf1[0..], &[_]u8{0x12}));
2057	writeInt(u8, &buf1, 0x34, .little);
2058	try testing.expect(eql(u8, buf1[0..], &[_]u8{0x34}));
2059
2060	writeInt(u16, &buf2, 0x1234, .big);
2061	try testing.expect(eql(u8, buf2[0..], &[_]u8{ 0x12, 0x34 }));
2062	writeInt(u16, &buf2, 0x5678, .little);
2063	try testing.expect(eql(u8, buf2[0..], &[_]u8{ 0x78, 0x56 }));
2064
2065	writeInt(u72, &buf9, 0x123456789abcdef024, .big);
2066	try testing.expect(eql(u8, buf9[0..], &[_]u8{ 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0, 0x24 }));
2067	writeInt(u72, &buf9, 0xfedcba9876543210ec, .little);
2068	try testing.expect(eql(u8, buf9[0..], &[_]u8{ 0xec, 0x10, 0x32, 0x54, 0x76, 0x98, 0xba, 0xdc, 0xfe }));
2069
2070	writeInt(i8, &buf1, -1, .big);
2071	try testing.expect(eql(u8, buf1[0..], &[_]u8{0xff}));
2072	writeInt(i8, &buf1, -2, .little);
2073	try testing.expect(eql(u8, buf1[0..], &[_]u8{0xfe}));
2074
2075	writeInt(i16, &buf2, -3, .big);
2076	try testing.expect(eql(u8, buf2[0..], &[_]u8{ 0xff, 0xfd }));
2077	writeInt(i16, &buf2, -4, .little);
2078	try testing.expect(eql(u8, buf2[0..], &[_]u8{ 0xfc, 0xff }));
2079	}
2080
2081	fn writePackedIntLittle(comptime T: type, bytes: []u8, bit_offset: usize, value: T) void {
2082	const uN = @Int(.unsigned, @bitSizeOf(T));
2083	const Log2N = std.math.Log2Int(T);
2084
2085	const bit_count = @as(usize, @bitSizeOf(T));
2086	const bit_shift = @as(u3, @intCast(bit_offset % 8));
2087
2088	const store_size = (@bitSizeOf(T) + 7) / 8;
2089	const store_tail_bits = @as(u3, @intCast((store_size * 8) - bit_count));
2090	const StoreInt = @Int(.unsigned, store_size * 8);
2091
2092	if (bit_count == 0)
2093	return;
2094
2095	// Write by storing a StoreInt, and then follow it up with a 1-byte tail
2096	// if bit_offset pushed us over a byte boundary.
2097	const write_bytes = bytes[bit_offset / 8 ..];
2098	const head = write_bytes[0] & ((@as(u8, 1) << bit_shift) - 1);
2099
2100	var write_value = (@as(StoreInt, @as(uN, @bitCast(value))) << bit_shift) | @as(StoreInt, @intCast(head));
2101	if (bit_shift > store_tail_bits) {
2102	const tail_len = @as(Log2N, @intCast(bit_shift - store_tail_bits));
2103	write_bytes[store_size] &= ~((@as(u8, 1) << @as(u3, @intCast(tail_len))) - 1);
2104	write_bytes[store_size] |= @as(u8, @intCast((@as(uN, @bitCast(value)) >> (@as(Log2N, @truncate(bit_count)) -% tail_len))));
2105	} else if (bit_shift < store_tail_bits) {
2106	const tail_len = store_tail_bits - bit_shift;
2107	const tail = write_bytes[store_size - 1] & (@as(u8, 0xfe) << (7 - tail_len));
2108	write_value |= @as(StoreInt, tail) << (8 * (store_size - 1));
2109	}
2110
2111	writeInt(StoreInt, write_bytes[0..store_size], write_value, .little);
2112	}
2113
2114	fn writePackedIntBig(comptime T: type, bytes: []u8, bit_offset: usize, value: T) void {
2115	const uN = @Int(.unsigned, @bitSizeOf(T));
2116	const Log2N = std.math.Log2Int(T);
2117
2118	const bit_count = @as(usize, @bitSizeOf(T));
2119	const bit_shift = @as(u3, @intCast(bit_offset % 8));
2120	const byte_count = (bit_shift + bit_count + 7) / 8;
2121
2122	const store_size = (@bitSizeOf(T) + 7) / 8;
2123	const store_tail_bits = @as(u3, @intCast((store_size * 8) - bit_count));
2124	const StoreInt = @Int(.unsigned, store_size * 8);
2125
2126	if (bit_count == 0)
2127	return;
2128
2129	// Write by storing a StoreInt, and then follow it up with a 1-byte tail
2130	// if bit_offset pushed us over a byte boundary.
2131	const end = bytes.len - (bit_offset / 8);
2132	const write_bytes = bytes[(end - byte_count)..end];
2133	const head = write_bytes[byte_count - 1] & ((@as(u8, 1) << bit_shift) - 1);
2134
2135	var write_value = (@as(StoreInt, @as(uN, @bitCast(value))) << bit_shift) | @as(StoreInt, @intCast(head));
2136	if (bit_shift > store_tail_bits) {
2137	const tail_len = @as(Log2N, @intCast(bit_shift - store_tail_bits));
2138	write_bytes[0] &= ~((@as(u8, 1) << @as(u3, @intCast(tail_len))) - 1);
2139	write_bytes[0] |= @as(u8, @intCast((@as(uN, @bitCast(value)) >> (@as(Log2N, @truncate(bit_count)) -% tail_len))));
2140	} else if (bit_shift < store_tail_bits) {
2141	const tail_len = store_tail_bits - bit_shift;
2142	const tail = write_bytes[0] & (@as(u8, 0xfe) << (7 - tail_len));
2143	write_value |= @as(StoreInt, tail) << (8 * (store_size - 1));
2144	}
2145
2146	writeInt(StoreInt, write_bytes[(byte_count - store_size)..][0..store_size], write_value, .big);
2147	}
2148
2149	/// Stores an integer to packed memory.
2150	/// Asserts that buffer contains at least bit_offset + @bitSizeOf(T) bits.
2151	pub fn writePackedInt(comptime T: type, bytes: []u8, bit_offset: usize, value: T, endian: Endian) void {
2152	switch (endian) {
2153	.little => writePackedIntLittle(T, bytes, bit_offset, value),
2154	.big => writePackedIntBig(T, bytes, bit_offset, value),
2155	}
2156	}
2157
2158	test writePackedInt {
2159	const T = packed struct(u16) { a: u3, b: u7, c: u6 };
2160	var st = T{ .a = 1, .b = 2, .c = 4 };
2161	writePackedInt(u7, std.mem.asBytes(&st), @bitOffsetOf(T, "b"), 0x7f, builtin.cpu.arch.endian());
2162	try std.testing.expectEqual(T{ .a = 1, .b = 0x7f, .c = 4 }, st);
2163	}
2164
2165	/// Stores an integer to packed memory with provided bit_offset, bit_count, and signedness.
2166	/// If negative, the written value is sign-extended.
2167	pub fn writeVarPackedInt(bytes: []u8, bit_offset: usize, bit_count: usize, value: anytype, endian: std.builtin.Endian) void {
2168	const T = @TypeOf(value);
2169	const uN = @Int(.unsigned, @bitSizeOf(T));
2170
2171	const bit_shift = @as(u3, @intCast(bit_offset % 8));
2172	const write_size = (bit_count + bit_shift + 7) / 8;
2173	const lowest_byte = switch (endian) {
2174	.big => bytes.len - (bit_offset / 8) - write_size,
2175	.little => bit_offset / 8,
2176	};
2177	const write_bytes = bytes[lowest_byte..][0..write_size];
2178
2179	if (write_size == 0) {
2180	return;
2181	} else if (write_size == 1) {
2182	// Single byte writes are handled specially, since we need to mask bits
2183	// on both ends of the byte.
2184	const mask = (@as(u8, 0xff) >> @as(u3, @intCast(8 - bit_count)));
2185	const new_bits = @as(u8, @intCast(@as(uN, @bitCast(value)) & mask)) << bit_shift;
2186	write_bytes[0] = (write_bytes[0] & ~(mask << bit_shift)) | new_bits;
2187	return;
2188	}
2189
2190	var remaining: T = value;
2191
2192	// Iterate bytes forward for Little-endian, backward for Big-endian
2193	const delta: i2 = if (endian == .big) -1 else 1;
2194	const start = if (endian == .big) @as(isize, @intCast(write_bytes.len - 1)) else 0;
2195
2196	var i: isize = start; // isize for signed index arithmetic
2197
2198	// Write first byte, using a mask to protects bits preceding bit_offset
2199	const head_mask = @as(u8, 0xff) >> bit_shift;
2200	write_bytes[@intCast(i)] &= ~(head_mask << bit_shift);
2201	write_bytes[@intCast(i)] |= @as(u8, @intCast(@as(uN, @bitCast(remaining)) & head_mask)) << bit_shift;
2202	remaining = math.shr(T, remaining, @as(u4, 8) - bit_shift);
2203	i += delta;
2204
2205	// Write bytes[1..bytes.len - 1]
2206	if (@bitSizeOf(T) > 8) {
2207	const loop_end = start + delta * (@as(isize, @intCast(write_size)) - 1);
2208	while (i != loop_end) : (i += delta) {
2209	write_bytes[@as(usize, @intCast(i))] = @as(u8, @truncate(@as(uN, @bitCast(remaining))));
2210	remaining >>= 8;
2211	}
2212	}
2213
2214	// Write last byte, using a mask to protect bits following bit_offset + bit_count
2215	const following_bits = -%@as(u3, @truncate(bit_shift + bit_count));
2216	const tail_mask = (@as(u8, 0xff) << following_bits) >> following_bits;
2217	write_bytes[@as(usize, @intCast(i))] &= ~tail_mask;
2218	write_bytes[@as(usize, @intCast(i))] |= @as(u8, @intCast(@as(uN, @bitCast(remaining)) & tail_mask));
2219	}
2220
2221	test writeVarPackedInt {
2222	const T = packed struct(u16) { a: u3, b: u7, c: u6 };
2223	var st = T{ .a = 1, .b = 2, .c = 4 };
2224	const value: u64 = 0x7f;
2225	writeVarPackedInt(std.mem.asBytes(&st), @bitOffsetOf(T, "b"), 7, value, builtin.cpu.arch.endian());
2226	try testing.expectEqual(T{ .a = 1, .b = value, .c = 4 }, st);
2227	}
2228
2229	/// Deprecated: use `byteSwap` instead.
2230	pub const byteSwapAllFields = byteSwap;
2231
2232	/// Deprecated: use `byteSwapAligned` instead.
2233	pub const byteSwapAllFieldsAligned = byteSwapAligned;
2234
2235	/// Reverses the byte order.
2236	/// Handles structs, unions, arrays, enums, floats, and integers recursively.
2237	/// The order of extern struct fields and array elements remains unchanged and
2238	/// will be byte swapped recursively.
2239	/// Useful for converting between little-endian and big-endian representations.
2240	pub fn byteSwap(comptime S: type, ptr: *S) void {
2241	byteSwapAligned(S, .of(S), ptr);
2242	}
2243
2244	/// Reverses the byte order.
2245	/// Handles structs, unions, arrays, enums, floats, and integers recursively.
2246	/// The order of extern struct fields and array elements remains unchanged and
2247	/// will be byte swapped recursively.
2248	/// Useful for converting between little-endian and big-endian representations.
2249	pub fn byteSwapAligned(
2250	comptime S: type,
2251	comptime a: Alignment,
2252	ptr: *align(a.toByteUnits()) S,
2253	) void {
2254	switch (@typeInfo(S)) {
2255	.@"struct" => |@"struct"| {
2256	if (@"struct".backing_integer) |Int| {
2257	ptr.* = @bitCast(@byteSwap(@as(Int, @bitCast(ptr.*))));
2258	} else {
2259	if (@"struct".layout != .@"extern") {
2260	@compileError("byteSwapAligned expects a packed or extern struct");
2261	}
2262	inline for (@"struct".field_types, @"struct".field_names, @"struct".field_attrs) |f_type, f_name, f_attr| {
2263	switch (@typeInfo(f_type)) {
2264	.@"struct" => byteSwapAligned(f_type, .fromByteUnits(f_attr.@"align" orelse @alignOf(f_type)), &@field(ptr, f_name)),
2265	.@"union", .array => byteSwapAligned(f_type, .fromByteUnits(f_attr.@"align" orelse @alignOf(f_type)), &@field(ptr, f_name)),
2266	.@"enum" => {
2267	@field(ptr, f_name) = @fromBackingInt(@byteSwap(@backingInt(@field(ptr, f_name))));
2268	},
2269	.bool => {},
2270	.float => |float| {
2271	@field(ptr, f_name) = @bitCast(@byteSwap(@as(@Int(.unsigned, float.bits), @bitCast(@field(ptr, f_name)))));
2272	},
2273	else => {
2274	@field(ptr, f_name) = @byteSwap(@field(ptr, f_name));
2275	},
2276	}
2277	}
2278	}
2279	},
2280	.@"union" => |@"union"| if (@"union".backing_integer) |Int| {
2281	ptr.* = @bitCast(@byteSwap(@as(Int, @bitCast(ptr.*))));
2282	} else {
2283	if (@"union".layout != .@"extern") {
2284	@compileError("byteSwapAligned expects a packed or extern union");
2285	}
2286
2287	const first_size = @bitSizeOf(@"union".field_types[0]);
2288	inline for (@"union".field_types) |field_type| {
2289	if (@bitSizeOf(field_type) != first_size) {
2290	@compileError("Unable to byte-swap unions with varying field sizes");
2291	}
2292	}
2293
2294	const FieldInt = @Int(.unsigned, first_size);
2295	const field_ptr = &@field(ptr, @"union".field_names[0]);
2296	field_ptr.* = @bitCast(@byteSwap(@as(FieldInt, @bitCast(field_ptr.*))));
2297	},
2298	.array => |array| {
2299	byteSwapAllElements(array.child, ptr);
2300	},
2301	.@"enum" => {
2302	ptr.* = @fromBackingInt(@byteSwap(@backingInt(ptr.*)));
2303	},
2304	.bool => {},
2305	.float => |float| {
2306	const int_repr: @Int(.unsigned, float.bits) = @bitCast(ptr.*);
2307	ptr.* = @bitCast(@byteSwap(int_repr));
2308	},
2309	else => {
2310	ptr.* = @byteSwap(ptr.*);
2311	},
2312	}
2313	}
2314
2315	test byteSwap {
2316	const T = extern struct {
2317	f0: u8,
2318	f1: u16,
2319	f2: u32,
2320	f3: [1]u8,
2321	f4: bool,
2322	f5: f32,
2323	f6: extern union { f0: u16, f1: u16 },
2324	};
2325	const K = extern struct {
2326	f0: u8,
2327	f1: T,
2328	f2: u16,
2329	f3: [1]u8,
2330	f4: bool,
2331	f5: f32,
2332	};
2333	const P = packed struct(u32) {
2334	f0: u1,
2335	f1: u7,
2336	f2: u4,
2337	f3: u4,
2338	f4: u16,
2339	};
2340	const A = extern struct {
2341	f0: u32,
2342	f1: extern struct {
2343	f0: u64,
2344	} align(4),
2345	f2: u32,
2346	};
2347	const E = enum(u32) {
2348	_,
2349	};
2350	var s = T{
2351	.f0 = 0x12,
2352	.f1 = 0x1234,
2353	.f2 = 0x12345678,
2354	.f3 = .{0x12},
2355	.f4 = true,
2356	.f5 = @bitCast(@as(u32, 0x4640e400)),
2357	.f6 = .{ .f0 = 0x1234 },
2358	};
2359	var k = K{
2360	.f0 = 0x12,
2361	.f1 = s,
2362	.f2 = 0x1234,
2363	.f3 = .{0x12},
2364	.f4 = false,
2365	.f5 = @bitCast(@as(u32, 0x45d42800)),
2366	};
2367	var p: P = @bitCast(@as(u32, 0x01234567));
2368	var a: A = A{
2369	.f0 = 0x12345678,
2370	.f1 = .{ .f0 = 0x123456789ABCDEF0 },
2371	.f2 = 0x87654321,
2372	};
2373	var e: E = @fromBackingInt(0x12345678);
2374	var f: f32 = @bitCast(@as(u32, 0x4640e400));
2375	byteSwap(T, &s);
2376	byteSwap(K, &k);
2377	byteSwap(P, &p);
2378	byteSwap(A, &a);
2379	byteSwap(E, &e);
2380	byteSwap(f32, &f);
2381	try std.testing.expectEqual(T{
2382	.f0 = 0x12,
2383	.f1 = 0x3412,
2384	.f2 = 0x78563412,
2385	.f3 = .{0x12},
2386	.f4 = true,
2387	.f5 = @bitCast(@as(u32, 0x00e44046)),
2388	.f6 = .{ .f0 = 0x3412 },
2389	}, s);
2390	try std.testing.expectEqual(K{
2391	.f0 = 0x12,
2392	.f1 = s,
2393	.f2 = 0x3412,
2394	.f3 = .{0x12},
2395	.f4 = false,
2396	.f5 = @bitCast(@as(u32, 0x0028d445)),
2397	}, k);
2398	try std.testing.expectEqual(@as(P, @bitCast(@as(u32, 0x67452301))), p);
2399	try std.testing.expectEqual(A{
2400	.f0 = 0x78563412,
2401	.f1 = .{ .f0 = 0xF0DEBC9A78563412 },
2402	.f2 = 0x21436587,
2403	}, a);
2404	try std.testing.expectEqual(@as(E, @fromBackingInt(0x78563412)), e);
2405	try std.testing.expectEqual(@as(f32, @bitCast(@as(u32, 0x00e44046))), f);
2406	}
2407
2408	/// Reverses the byte order of all elements in a slice.
2409	/// Handles structs, unions, arrays, enums, floats, and integers recursively.
2410	/// Useful for converting between little-endian and big-endian representations.
2411	pub fn byteSwapAllElements(comptime Elem: type, slice: []Elem) void {
2412	for (slice) |*elem| byteSwap(Elem, elem);
2413	}
2414
2415	/// Returns an iterator that iterates over the slices of `buffer` that are not
2416	/// any of the items in `delimiters`.
2417	///
2418	/// `tokenizeAny(u8, " abc|def || ghi ", " |")` will return slices
2419	/// for "abc", "def", "ghi", null, in that order.
2420	///
2421	/// If `buffer` is empty, the iterator will return null.
2422	/// If none of `delimiters` exist in buffer,
2423	/// the iterator will return `buffer`, null, in that order.
2424	///
2425	/// See also: `tokenizeSequence`, `tokenizeScalar`,
2426	/// `splitSequence`,`splitAny`, `splitScalar`,
2427	/// `splitBackwardsSequence`, `splitBackwardsAny`, and `splitBackwardsScalar`
2428	pub fn tokenizeAny(comptime T: type, buffer: []const T, delimiters: []const T) TokenIterator(T, .any) {
2429	return .{
2430	.index = 0,
2431	.buffer = buffer,
2432	.delimiter = delimiters,
2433	};
2434	}
2435
2436	/// Returns an iterator that iterates over the slices of `buffer` that are not
2437	/// the sequence in `delimiter`.
2438	///
2439	/// `tokenizeSequence(u8, "<>abc><def<><>ghi", "<>")` will return slices
2440	/// for "abc><def", "ghi", null, in that order.
2441	///
2442	/// If `buffer` is empty, the iterator will return null.
2443	/// If `delimiter` does not exist in buffer,
2444	/// the iterator will return `buffer`, null, in that order.
2445	/// The delimiter length must not be zero.
2446	///
2447	/// See also: `tokenizeAny`, `tokenizeScalar`,
2448	/// `splitSequence`,`splitAny`, and `splitScalar`
2449	/// `splitBackwardsSequence`, `splitBackwardsAny`, and `splitBackwardsScalar`
2450	pub fn tokenizeSequence(comptime T: type, buffer: []const T, delimiter: []const T) TokenIterator(T, .sequence) {
2451	assert(delimiter.len != 0);
2452	return .{
2453	.index = 0,
2454	.buffer = buffer,
2455	.delimiter = delimiter,
2456	};
2457	}
2458
2459	/// Returns an iterator that iterates over the slices of `buffer` that are not
2460	/// `delimiter`.
2461	///
2462	/// `tokenizeScalar(u8, " abc def ghi ", ' ')` will return slices
2463	/// for "abc", "def", "ghi", null, in that order.
2464	///
2465	/// If `buffer` is empty, the iterator will return null.
2466	/// If `delimiter` does not exist in buffer,
2467	/// the iterator will return `buffer`, null, in that order.
2468	///
2469	/// See also: `tokenizeAny`, `tokenizeSequence`,
2470	/// `splitSequence`,`splitAny`, and `splitScalar`
2471	/// `splitBackwardsSequence`, `splitBackwardsAny`, and `splitBackwardsScalar`
2472	pub fn tokenizeScalar(comptime T: type, buffer: []const T, delimiter: T) TokenIterator(T, .scalar) {
2473	return .{
2474	.index = 0,
2475	.buffer = buffer,
2476	.delimiter = delimiter,
2477	};
2478	}
2479
2480	test tokenizeScalar {
2481	var it = tokenizeScalar(u8, " abc def ghi ", ' ');
2482	try testing.expect(eql(u8, it.next().?, "abc"));
2483	try testing.expect(eql(u8, it.peek().?, "def"));
2484	try testing.expect(eql(u8, it.next().?, "def"));
2485	try testing.expect(eql(u8, it.next().?, "ghi"));
2486	try testing.expect(it.next() == null);
2487
2488	it = tokenizeScalar(u8, "..\\bob", '\\');
2489	try testing.expect(eql(u8, it.next().?, ".."));
2490	try testing.expect(eql(u8, "..", "..\\bob"[0..it.index]));
2491	try testing.expect(eql(u8, it.next().?, "bob"));
2492	try testing.expect(it.next() == null);
2493
2494	it = tokenizeScalar(u8, "//a/b", '/');
2495	try testing.expect(eql(u8, it.next().?, "a"));
2496	try testing.expect(eql(u8, it.next().?, "b"));
2497	try testing.expect(eql(u8, "//a/b", "//a/b"[0..it.index]));
2498	try testing.expect(it.next() == null);
2499
2500	it = tokenizeScalar(u8, "|", '|');
2501	try testing.expect(it.next() == null);
2502	try testing.expect(it.peek() == null);
2503
2504	it = tokenizeScalar(u8, "", '|');
2505	try testing.expect(it.next() == null);
2506	try testing.expect(it.peek() == null);
2507
2508	it = tokenizeScalar(u8, "hello", ' ');
2509	try testing.expect(eql(u8, it.next().?, "hello"));
2510	try testing.expect(it.next() == null);
2511
2512	var it16 = tokenizeScalar(
2513	u16,
2514	std.unicode.utf8ToUtf16LeStringLiteral("hello"),
2515	' ',
2516	);
2517	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("hello")));
2518	try testing.expect(it16.next() == null);
2519	}
2520
2521	test tokenizeAny {
2522	var it = tokenizeAny(u8, "a|b,c/d e", " /,|");
2523	try testing.expect(eql(u8, it.next().?, "a"));
2524	try testing.expect(eql(u8, it.peek().?, "b"));
2525	try testing.expect(eql(u8, it.next().?, "b"));
2526	try testing.expect(eql(u8, it.next().?, "c"));
2527	try testing.expect(eql(u8, it.next().?, "d"));
2528	try testing.expect(eql(u8, it.next().?, "e"));
2529	try testing.expect(it.next() == null);
2530	try testing.expect(it.peek() == null);
2531
2532	it = tokenizeAny(u8, "hello", "");
2533	try testing.expect(eql(u8, it.next().?, "hello"));
2534	try testing.expect(it.next() == null);
2535
2536	var it16 = tokenizeAny(
2537	u16,
2538	std.unicode.utf8ToUtf16LeStringLiteral("a|b,c/d e"),
2539	std.unicode.utf8ToUtf16LeStringLiteral(" /,|"),
2540	);
2541	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("a")));
2542	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("b")));
2543	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("c")));
2544	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("d")));
2545	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("e")));
2546	try testing.expect(it16.next() == null);
2547	}
2548
2549	test tokenizeSequence {
2550	var it = tokenizeSequence(u8, "a<>b<><>c><>d><", "<>");
2551	try testing.expectEqualStrings("a", it.next().?);
2552	try testing.expectEqualStrings("b", it.peek().?);
2553	try testing.expectEqualStrings("b", it.next().?);
2554	try testing.expectEqualStrings("c>", it.next().?);
2555	try testing.expectEqualStrings("d><", it.next().?);
2556	try testing.expect(it.next() == null);
2557	try testing.expect(it.peek() == null);
2558
2559	var it16 = tokenizeSequence(
2560	u16,
2561	std.unicode.utf8ToUtf16LeStringLiteral("a<>b<><>c><>d><"),
2562	std.unicode.utf8ToUtf16LeStringLiteral("<>"),
2563	);
2564	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("a")));
2565	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("b")));
2566	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("c>")));
2567	try testing.expect(eql(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("d><")));
2568	try testing.expect(it16.next() == null);
2569	}
2570
2571	test "tokenize (reset)" {
2572	{
2573	var it = tokenizeAny(u8, " abc def ghi ", " ");
2574	try testing.expect(eql(u8, it.next().?, "abc"));
2575	try testing.expect(eql(u8, it.next().?, "def"));
2576	try testing.expect(eql(u8, it.next().?, "ghi"));
2577
2578	it.reset();
2579
2580	try testing.expect(eql(u8, it.next().?, "abc"));
2581	try testing.expect(eql(u8, it.next().?, "def"));
2582	try testing.expect(eql(u8, it.next().?, "ghi"));
2583	try testing.expect(it.next() == null);
2584	}
2585	{
2586	var it = tokenizeSequence(u8, "<><>abc<>def<><>ghi<>", "<>");
2587	try testing.expect(eql(u8, it.next().?, "abc"));
2588	try testing.expect(eql(u8, it.next().?, "def"));
2589	try testing.expect(eql(u8, it.next().?, "ghi"));
2590
2591	it.reset();
2592
2593	try testing.expect(eql(u8, it.next().?, "abc"));
2594	try testing.expect(eql(u8, it.next().?, "def"));
2595	try testing.expect(eql(u8, it.next().?, "ghi"));
2596	try testing.expect(it.next() == null);
2597	}
2598	{
2599	var it = tokenizeScalar(u8, " abc def ghi ", ' ');
2600	try testing.expect(eql(u8, it.next().?, "abc"));
2601	try testing.expect(eql(u8, it.next().?, "def"));
2602	try testing.expect(eql(u8, it.next().?, "ghi"));
2603
2604	it.reset();
2605
2606	try testing.expect(eql(u8, it.next().?, "abc"));
2607	try testing.expect(eql(u8, it.next().?, "def"));
2608	try testing.expect(eql(u8, it.next().?, "ghi"));
2609	try testing.expect(it.next() == null);
2610	}
2611	}
2612
2613	/// Returns an iterator that iterates over the slices of `buffer` that
2614	/// are separated by the byte sequence in `delimiter`.
2615	///
2616	/// `splitSequence(u8, "abc||def||||ghi", "||")` will return slices
2617	/// for "abc", "def", "", "ghi", null, in that order.
2618	///
2619	/// If `delimiter` does not exist in buffer,
2620	/// the iterator will return `buffer`, null, in that order.
2621	/// The delimiter length must not be zero.
2622	///
2623	/// See also: `splitAny`, `splitScalar`, `splitBackwardsSequence`,
2624	/// `splitBackwardsAny`,`splitBackwardsScalar`,
2625	/// `tokenizeAny`, `tokenizeSequence`, and `tokenizeScalar`.
2626	pub fn splitSequence(comptime T: type, buffer: []const T, delimiter: []const T) SplitIterator(T, .sequence) {
2627	assert(delimiter.len != 0);
2628	return .{
2629	.index = 0,
2630	.buffer = buffer,
2631	.delimiter = delimiter,
2632	};
2633	}
2634
2635	/// Returns an iterator that iterates over the slices of `buffer` that
2636	/// are separated by any item in `delimiters`.
2637	///
2638	/// `splitAny(u8, "abc,def||ghi", "|,")` will return slices
2639	/// for "abc", "def", "", "ghi", null, in that order.
2640	///
2641	/// If none of `delimiters` exist in buffer,
2642	/// the iterator will return `buffer`, null, in that order.
2643	///
2644	/// See also: `splitSequence`, `splitScalar`, `splitBackwardsSequence`,
2645	/// `splitBackwardsAny`,`splitBackwardsScalar`,
2646	/// `tokenizeAny`, `tokenizeSequence`, and `tokenizeScalar`.
2647	pub fn splitAny(comptime T: type, buffer: []const T, delimiters: []const T) SplitIterator(T, .any) {
2648	return .{
2649	.index = 0,
2650	.buffer = buffer,
2651	.delimiter = delimiters,
2652	};
2653	}
2654
2655	/// Returns an iterator that iterates over the slices of `buffer` that
2656	/// are separated by `delimiter`.
2657	///
2658	/// `splitScalar(u8, "abc|def||ghi", '|')` will return slices
2659	/// for "abc", "def", "", "ghi", null, in that order.
2660	///
2661	/// If `delimiter` does not exist in buffer,
2662	/// the iterator will return `buffer`, null, in that order.
2663	///
2664	/// See also: `splitSequence`, `splitAny`, `splitBackwardsSequence`,
2665	/// `splitBackwardsAny`,`splitBackwardsScalar`,
2666	/// `tokenizeAny`, `tokenizeSequence`, and `tokenizeScalar`.
2667	pub fn splitScalar(comptime T: type, buffer: []const T, delimiter: T) SplitIterator(T, .scalar) {
2668	return .{
2669	.index = 0,
2670	.buffer = buffer,
2671	.delimiter = delimiter,
2672	};
2673	}
2674
2675	test splitScalar {
2676	var it = splitScalar(u8, "abc|def||ghi", '|');
2677	try testing.expectEqualSlices(u8, it.rest(), "abc|def||ghi");
2678	try testing.expectEqualSlices(u8, it.first(), "abc");
2679
2680	try testing.expectEqualSlices(u8, it.rest(), "def||ghi");
2681	try testing.expectEqualSlices(u8, it.peek().?, "def");
2682	try testing.expectEqualSlices(u8, it.next().?, "def");
2683
2684	try testing.expectEqualSlices(u8, it.rest(), "|ghi");
2685	try testing.expectEqualSlices(u8, it.next().?, "");
2686
2687	try testing.expectEqualSlices(u8, it.rest(), "ghi");
2688	try testing.expectEqualSlices(u8, it.peek().?, "ghi");
2689	try testing.expectEqualSlices(u8, it.next().?, "ghi");
2690
2691	try testing.expectEqualSlices(u8, it.rest(), "");
2692	try testing.expect(it.peek() == null);
2693	try testing.expect(it.next() == null);
2694
2695	it = splitScalar(u8, "", '|');
2696	try testing.expectEqualSlices(u8, it.first(), "");
2697	try testing.expect(it.next() == null);
2698
2699	it = splitScalar(u8, "|", '|');
2700	try testing.expectEqualSlices(u8, it.first(), "");
2701	try testing.expectEqualSlices(u8, it.next().?, "");
2702	try testing.expect(it.peek() == null);
2703	try testing.expect(it.next() == null);
2704
2705	it = splitScalar(u8, "hello", ' ');
2706	try testing.expectEqualSlices(u8, it.first(), "hello");
2707	try testing.expect(it.next() == null);
2708
2709	var it16 = splitScalar(
2710	u16,
2711	std.unicode.utf8ToUtf16LeStringLiteral("hello"),
2712	' ',
2713	);
2714	try testing.expectEqualSlices(u16, it16.first(), std.unicode.utf8ToUtf16LeStringLiteral("hello"));
2715	try testing.expect(it16.next() == null);
2716	}
2717
2718	test splitSequence {
2719	var it = splitSequence(u8, "a, b ,, c, d, e", ", ");
2720	try testing.expectEqualSlices(u8, it.first(), "a");
2721	try testing.expectEqualSlices(u8, it.rest(), "b ,, c, d, e");
2722	try testing.expectEqualSlices(u8, it.next().?, "b ,");
2723	try testing.expectEqualSlices(u8, it.next().?, "c");
2724	try testing.expectEqualSlices(u8, it.next().?, "d");
2725	try testing.expectEqualSlices(u8, it.next().?, "e");
2726	try testing.expect(it.next() == null);
2727
2728	var it16 = splitSequence(
2729	u16,
2730	std.unicode.utf8ToUtf16LeStringLiteral("a, b ,, c, d, e"),
2731	std.unicode.utf8ToUtf16LeStringLiteral(", "),
2732	);
2733	try testing.expectEqualSlices(u16, it16.first(), std.unicode.utf8ToUtf16LeStringLiteral("a"));
2734	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("b ,"));
2735	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("c"));
2736	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("d"));
2737	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("e"));
2738	try testing.expect(it16.next() == null);
2739	}
2740
2741	test splitAny {
2742	var it = splitAny(u8, "a,b, c d e", ", ");
2743	try testing.expectEqualSlices(u8, it.first(), "a");
2744	try testing.expectEqualSlices(u8, it.rest(), "b, c d e");
2745	try testing.expectEqualSlices(u8, it.next().?, "b");
2746	try testing.expectEqualSlices(u8, it.next().?, "");
2747	try testing.expectEqualSlices(u8, it.next().?, "c");
2748	try testing.expectEqualSlices(u8, it.next().?, "d");
2749	try testing.expectEqualSlices(u8, it.next().?, "e");
2750	try testing.expect(it.next() == null);
2751
2752	it = splitAny(u8, "hello", "");
2753	try testing.expect(eql(u8, it.next().?, "hello"));
2754	try testing.expect(it.next() == null);
2755
2756	var it16 = splitAny(
2757	u16,
2758	std.unicode.utf8ToUtf16LeStringLiteral("a,b, c d e"),
2759	std.unicode.utf8ToUtf16LeStringLiteral(", "),
2760	);
2761	try testing.expectEqualSlices(u16, it16.first(), std.unicode.utf8ToUtf16LeStringLiteral("a"));
2762	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("b"));
2763	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral(""));
2764	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("c"));
2765	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("d"));
2766	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("e"));
2767	try testing.expect(it16.next() == null);
2768	}
2769
2770	test "split (reset)" {
2771	{
2772	var it = splitSequence(u8, "abc def ghi", " ");
2773	try testing.expect(eql(u8, it.first(), "abc"));
2774	try testing.expect(eql(u8, it.next().?, "def"));
2775	try testing.expect(eql(u8, it.next().?, "ghi"));
2776
2777	it.reset();
2778
2779	try testing.expect(eql(u8, it.first(), "abc"));
2780	try testing.expect(eql(u8, it.next().?, "def"));
2781	try testing.expect(eql(u8, it.next().?, "ghi"));
2782	try testing.expect(it.next() == null);
2783	}
2784	{
2785	var it = splitAny(u8, "abc def,ghi", " ,");
2786	try testing.expect(eql(u8, it.first(), "abc"));
2787	try testing.expect(eql(u8, it.next().?, "def"));
2788	try testing.expect(eql(u8, it.next().?, "ghi"));
2789
2790	it.reset();
2791
2792	try testing.expect(eql(u8, it.first(), "abc"));
2793	try testing.expect(eql(u8, it.next().?, "def"));
2794	try testing.expect(eql(u8, it.next().?, "ghi"));
2795	try testing.expect(it.next() == null);
2796	}
2797	{
2798	var it = splitScalar(u8, "abc def ghi", ' ');
2799	try testing.expect(eql(u8, it.first(), "abc"));
2800	try testing.expect(eql(u8, it.next().?, "def"));
2801	try testing.expect(eql(u8, it.next().?, "ghi"));
2802
2803	it.reset();
2804
2805	try testing.expect(eql(u8, it.first(), "abc"));
2806	try testing.expect(eql(u8, it.next().?, "def"));
2807	try testing.expect(eql(u8, it.next().?, "ghi"));
2808	try testing.expect(it.next() == null);
2809	}
2810	}
2811
2812	/// Returns an iterator that iterates backwards over the slices of `buffer` that
2813	/// are separated by the sequence in `delimiter`.
2814	///
2815	/// `splitBackwardsSequence(u8, "abc||def||||ghi", "||")` will return slices
2816	/// for "ghi", "", "def", "abc", null, in that order.
2817	///
2818	/// If `delimiter` does not exist in buffer,
2819	/// the iterator will return `buffer`, null, in that order.
2820	/// The delimiter length must not be zero.
2821	///
2822	/// See also: `splitBackwardsAny`, `splitBackwardsScalar`,
2823	/// `splitSequence`, `splitAny`,`splitScalar`,
2824	/// `tokenizeAny`, `tokenizeSequence`, and `tokenizeScalar`.
2825	pub fn splitBackwardsSequence(comptime T: type, buffer: []const T, delimiter: []const T) SplitBackwardsIterator(T, .sequence) {
2826	assert(delimiter.len != 0);
2827	return .{
2828	.index = buffer.len,
2829	.buffer = buffer,
2830	.delimiter = delimiter,
2831	};
2832	}
2833
2834	/// Returns an iterator that iterates backwards over the slices of `buffer` that
2835	/// are separated by any item in `delimiters`.
2836	///
2837	/// `splitBackwardsAny(u8, "abc,def||ghi", "|,")` will return slices
2838	/// for "ghi", "", "def", "abc", null, in that order.
2839	///
2840	/// If none of `delimiters` exist in buffer,
2841	/// the iterator will return `buffer`, null, in that order.
2842	///
2843	/// See also: `splitBackwardsSequence`, `splitBackwardsScalar`,
2844	/// `splitSequence`, `splitAny`,`splitScalar`,
2845	/// `tokenizeAny`, `tokenizeSequence`, and `tokenizeScalar`.
2846	pub fn splitBackwardsAny(comptime T: type, buffer: []const T, delimiters: []const T) SplitBackwardsIterator(T, .any) {
2847	return .{
2848	.index = buffer.len,
2849	.buffer = buffer,
2850	.delimiter = delimiters,
2851	};
2852	}
2853
2854	/// Returns an iterator that iterates backwards over the slices of `buffer` that
2855	/// are separated by `delimiter`.
2856	///
2857	/// `splitBackwardsScalar(u8, "abc|def||ghi", '|')` will return slices
2858	/// for "ghi", "", "def", "abc", null, in that order.
2859	///
2860	/// If `delimiter` does not exist in buffer,
2861	/// the iterator will return `buffer`, null, in that order.
2862	///
2863	/// See also: `splitBackwardsSequence`, `splitBackwardsAny`,
2864	/// `splitSequence`, `splitAny`,`splitScalar`,
2865	/// `tokenizeAny`, `tokenizeSequence`, and `tokenizeScalar`.
2866	pub fn splitBackwardsScalar(comptime T: type, buffer: []const T, delimiter: T) SplitBackwardsIterator(T, .scalar) {
2867	return .{
2868	.index = buffer.len,
2869	.buffer = buffer,
2870	.delimiter = delimiter,
2871	};
2872	}
2873
2874	test splitBackwardsScalar {
2875	var it = splitBackwardsScalar(u8, "abc|def||ghi", '|');
2876	try testing.expectEqualSlices(u8, it.rest(), "abc|def||ghi");
2877	try testing.expectEqualSlices(u8, it.first(), "ghi");
2878
2879	try testing.expectEqualSlices(u8, it.rest(), "abc|def|");
2880	try testing.expectEqualSlices(u8, it.next().?, "");
2881
2882	try testing.expectEqualSlices(u8, it.rest(), "abc|def");
2883	try testing.expectEqualSlices(u8, it.next().?, "def");
2884
2885	try testing.expectEqualSlices(u8, it.rest(), "abc");
2886	try testing.expectEqualSlices(u8, it.next().?, "abc");
2887
2888	try testing.expectEqualSlices(u8, it.rest(), "");
2889	try testing.expect(it.next() == null);
2890
2891	it = splitBackwardsScalar(u8, "", '|');
2892	try testing.expectEqualSlices(u8, it.first(), "");
2893	try testing.expect(it.next() == null);
2894
2895	it = splitBackwardsScalar(u8, "|", '|');
2896	try testing.expectEqualSlices(u8, it.first(), "");
2897	try testing.expectEqualSlices(u8, it.next().?, "");
2898	try testing.expect(it.next() == null);
2899
2900	it = splitBackwardsScalar(u8, "hello", ' ');
2901	try testing.expectEqualSlices(u8, it.first(), "hello");
2902	try testing.expect(it.next() == null);
2903
2904	var it16 = splitBackwardsScalar(
2905	u16,
2906	std.unicode.utf8ToUtf16LeStringLiteral("hello"),
2907	' ',
2908	);
2909	try testing.expectEqualSlices(u16, it16.first(), std.unicode.utf8ToUtf16LeStringLiteral("hello"));
2910	try testing.expect(it16.next() == null);
2911	}
2912
2913	test splitBackwardsSequence {
2914	var it = splitBackwardsSequence(u8, "a, b ,, c, d, e", ", ");
2915	try testing.expectEqualSlices(u8, it.rest(), "a, b ,, c, d, e");
2916	try testing.expectEqualSlices(u8, it.first(), "e");
2917
2918	try testing.expectEqualSlices(u8, it.rest(), "a, b ,, c, d");
2919	try testing.expectEqualSlices(u8, it.next().?, "d");
2920
2921	try testing.expectEqualSlices(u8, it.rest(), "a, b ,, c");
2922	try testing.expectEqualSlices(u8, it.next().?, "c");
2923
2924	try testing.expectEqualSlices(u8, it.rest(), "a, b ,");
2925	try testing.expectEqualSlices(u8, it.next().?, "b ,");
2926
2927	try testing.expectEqualSlices(u8, it.rest(), "a");
2928	try testing.expectEqualSlices(u8, it.next().?, "a");
2929
2930	try testing.expectEqualSlices(u8, it.rest(), "");
2931	try testing.expect(it.next() == null);
2932
2933	var it16 = splitBackwardsSequence(
2934	u16,
2935	std.unicode.utf8ToUtf16LeStringLiteral("a, b ,, c, d, e"),
2936	std.unicode.utf8ToUtf16LeStringLiteral(", "),
2937	);
2938	try testing.expectEqualSlices(u16, it16.first(), std.unicode.utf8ToUtf16LeStringLiteral("e"));
2939	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("d"));
2940	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("c"));
2941	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("b ,"));
2942	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("a"));
2943	try testing.expect(it16.next() == null);
2944	}
2945
2946	test splitBackwardsAny {
2947	var it = splitBackwardsAny(u8, "a,b, c d e", ", ");
2948	try testing.expectEqualSlices(u8, it.rest(), "a,b, c d e");
2949	try testing.expectEqualSlices(u8, it.first(), "e");
2950
2951	try testing.expectEqualSlices(u8, it.rest(), "a,b, c d");
2952	try testing.expectEqualSlices(u8, it.next().?, "d");
2953
2954	try testing.expectEqualSlices(u8, it.rest(), "a,b, c");
2955	try testing.expectEqualSlices(u8, it.next().?, "c");
2956
2957	try testing.expectEqualSlices(u8, it.rest(), "a,b,");
2958	try testing.expectEqualSlices(u8, it.next().?, "");
2959
2960	try testing.expectEqualSlices(u8, it.rest(), "a,b");
2961	try testing.expectEqualSlices(u8, it.next().?, "b");
2962
2963	try testing.expectEqualSlices(u8, it.rest(), "a");
2964	try testing.expectEqualSlices(u8, it.next().?, "a");
2965
2966	try testing.expectEqualSlices(u8, it.rest(), "");
2967	try testing.expect(it.next() == null);
2968
2969	var it16 = splitBackwardsAny(
2970	u16,
2971	std.unicode.utf8ToUtf16LeStringLiteral("a,b, c d e"),
2972	std.unicode.utf8ToUtf16LeStringLiteral(", "),
2973	);
2974	try testing.expectEqualSlices(u16, it16.first(), std.unicode.utf8ToUtf16LeStringLiteral("e"));
2975	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("d"));
2976	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("c"));
2977	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral(""));
2978	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("b"));
2979	try testing.expectEqualSlices(u16, it16.next().?, std.unicode.utf8ToUtf16LeStringLiteral("a"));
2980	try testing.expect(it16.next() == null);
2981	}
2982
2983	test "splitBackwards (reset)" {
2984	{
2985	var it = splitBackwardsSequence(u8, "abc def ghi", " ");
2986	try testing.expect(eql(u8, it.first(), "ghi"));
2987	try testing.expect(eql(u8, it.next().?, "def"));
2988	try testing.expect(eql(u8, it.next().?, "abc"));
2989
2990	it.reset();
2991
2992	try testing.expect(eql(u8, it.first(), "ghi"));
2993	try testing.expect(eql(u8, it.next().?, "def"));
2994	try testing.expect(eql(u8, it.next().?, "abc"));
2995	try testing.expect(it.next() == null);
2996	}
2997	{
2998	var it = splitBackwardsAny(u8, "abc def,ghi", " ,");
2999	try testing.expect(eql(u8, it.first(), "ghi"));
3000	try testing.expect(eql(u8, it.next().?, "def"));
3001	try testing.expect(eql(u8, it.next().?, "abc"));
3002
3003	it.reset();
3004
3005	try testing.expect(eql(u8, it.first(), "ghi"));
3006	try testing.expect(eql(u8, it.next().?, "def"));
3007	try testing.expect(eql(u8, it.next().?, "abc"));
3008	try testing.expect(it.next() == null);
3009	}
3010	{
3011	var it = splitBackwardsScalar(u8, "abc def ghi", ' ');
3012	try testing.expect(eql(u8, it.first(), "ghi"));
3013	try testing.expect(eql(u8, it.next().?, "def"));
3014	try testing.expect(eql(u8, it.next().?, "abc"));
3015
3016	it.reset();
3017
3018	try testing.expect(eql(u8, it.first(), "ghi"));
3019	try testing.expect(eql(u8, it.next().?, "def"));
3020	try testing.expect(eql(u8, it.next().?, "abc"));
3021	try testing.expect(it.next() == null);
3022	}
3023	}
3024
3025	/// Returns an iterator with a sliding window of slices for `buffer`.
3026	/// The sliding window has length `size` and on every iteration moves
3027	/// forward by `advance`.
3028	///
3029	/// Extract data for moving average with:
3030	/// `window(u8, "abcdefg", 3, 1)` will return slices
3031	/// "abc", "bcd", "cde", "def", "efg", null, in that order.
3032	///
3033	/// Chunk or split every N items with:
3034	/// `window(u8, "abcdefg", 3, 3)` will return slices
3035	/// "abc", "def", "g", null, in that order.
3036	///
3037	/// Pick every even index with:
3038	/// `window(u8, "abcdefg", 1, 2)` will return slices
3039	/// "a", "c", "e", "g" null, in that order.
3040	///
3041	/// The `size` and `advance` must be not be zero.
3042	pub fn window(comptime T: type, buffer: []const T, size: usize, advance: usize) WindowIterator(T) {
3043	assert(size != 0);
3044	assert(advance != 0);
3045	return .{
3046	.index = if (buffer.len > 0) 0 else null,
3047	.buffer = buffer,
3048	.size = size,
3049	.advance = advance,
3050	};
3051	}
3052
3053	test window {
3054	{
3055	// moving average size 3
3056	var it = window(u8, "abcdefg", 3, 1);
3057	try testing.expectEqualSlices(u8, "abc", it.next().?);
3058	try testing.expectEqualSlices(u8, "bcd", it.next().?);
3059	try testing.expectEqualSlices(u8, "cde", it.next().?);
3060	try testing.expectEqualSlices(u8, "def", it.next().?);
3061	try testing.expectEqualSlices(u8, "efg", it.next().?);
3062	try testing.expectEqual(null, it.next());
3063
3064	// multibyte
3065	var it16 = window(u16, std.unicode.utf8ToUtf16LeStringLiteral("abcdefg"), 3, 1);
3066	try testing.expectEqualSlices(u16, std.unicode.utf8ToUtf16LeStringLiteral("abc"), it16.next().?);
3067	try testing.expectEqualSlices(u16, std.unicode.utf8ToUtf16LeStringLiteral("bcd"), it16.next().?);
3068	try testing.expectEqualSlices(u16, std.unicode.utf8ToUtf16LeStringLiteral("cde"), it16.next().?);
3069	try testing.expectEqualSlices(u16, std.unicode.utf8ToUtf16LeStringLiteral("def"), it16.next().?);
3070	try testing.expectEqualSlices(u16, std.unicode.utf8ToUtf16LeStringLiteral("efg"), it16.next().?);
3071	try testing.expectEqual(it16.next(), null);
3072	}
3073
3074	{
3075	// chunk/split every 3
3076	var it = window(u8, "abcdefg", 3, 3);
3077	try testing.expectEqualSlices(u8, "abc", it.next().?);
3078	try testing.expectEqualSlices(u8, "def", it.next().?);
3079	try testing.expectEqualSlices(u8, "g", it.next().?);
3080	try testing.expectEqual(null, it.next());
3081	}
3082
3083	{
3084	// pick even
3085	var it = window(u8, "abcdefg", 1, 2);
3086	try testing.expectEqualSlices(u8, "a", it.next().?);
3087	try testing.expectEqualSlices(u8, "c", it.next().?);
3088	try testing.expectEqualSlices(u8, "e", it.next().?);
3089	try testing.expectEqualSlices(u8, "g", it.next().?);
3090	try testing.expectEqual(null, it.next());
3091
3092	it = window(u8, "abcdefgh", 1, 2);
3093	try testing.expectEqualSlices(u8, "a", it.next().?);
3094	try testing.expectEqualSlices(u8, "c", it.next().?);
3095	try testing.expectEqualSlices(u8, "e", it.next().?);
3096	try testing.expectEqualSlices(u8, "g", it.next().?);
3097	try testing.expectEqual(null, it.next());
3098	}
3099
3100	{
3101	// empty
3102	var it = window(u8, "", 1, 1);
3103	try testing.expectEqual(null, it.next());
3104
3105	it = window(u8, "", 10, 1);
3106	try testing.expectEqual(null, it.next());
3107
3108	it = window(u8, "", 1, 10);
3109	try testing.expectEqual(null, it.next());
3110
3111	it = window(u8, "", 10, 10);
3112	try testing.expectEqual(null, it.next());
3113	}
3114
3115	{
3116	// first
3117	var it = window(u8, "abcdefg", 3, 3);
3118	try testing.expectEqualSlices(u8, "abc", it.next().?);
3119	it.reset();
3120	try testing.expectEqualSlices(u8, "abc", it.next().?);
3121	}
3122
3123	{
3124	// reset
3125	var it = window(u8, "abcdefg", 3, 3);
3126	try testing.expectEqualSlices(u8, "abc", it.next().?);
3127	try testing.expectEqualSlices(u8, "def", it.next().?);
3128	try testing.expectEqualSlices(u8, "g", it.next().?);
3129	try testing.expectEqual(null, it.next());
3130
3131	it.reset();
3132	try testing.expectEqualSlices(u8, "abc", it.next().?);
3133	try testing.expectEqualSlices(u8, "def", it.next().?);
3134	try testing.expectEqualSlices(u8, "g", it.next().?);
3135	try testing.expectEqual(null, it.next());
3136	}
3137
3138	{
3139	// size > buffer.len
3140	var it = window(u8, "abcdefg", 100, 1);
3141	try testing.expectEqualSlices(u8, "abcdefg", it.next().?);
3142	try testing.expectEqual(null, it.next());
3143	}
3144
3145	{
3146	// advance >= buffer.len
3147	var it = window(u8, "abcdefg", 1, 7);
3148	try testing.expectEqualSlices(u8, "a", it.next().?);
3149	try testing.expectEqual(null, it.next());
3150	}
3151
3152	{
3153	// advance == 1 and size == 1
3154	var it = window(u8, "abcdefg", 1, 1);
3155	try testing.expectEqualSlices(u8, "a", it.next().?);
3156	try testing.expectEqualSlices(u8, "b", it.next().?);
3157	try testing.expectEqualSlices(u8, "c", it.next().?);
3158	try testing.expectEqualSlices(u8, "d", it.next().?);
3159	try testing.expectEqualSlices(u8, "e", it.next().?);
3160	try testing.expectEqualSlices(u8, "f", it.next().?);
3161	try testing.expectEqualSlices(u8, "g", it.next().?);
3162	try testing.expectEqual(null, it.next());
3163	}
3164
3165	{
3166	// advance > size
3167	var it = window(u8, "abcdefg", 2, 3);
3168	try testing.expectEqualSlices(u8, "ab", it.next().?);
3169	try testing.expectEqualSlices(u8, "de", it.next().?);
3170	try testing.expectEqualSlices(u8, "g", it.next().?);
3171	try testing.expectEqual(null, it.next());
3172	}
3173	}
3174
3175	/// Iterator type returned by the `window` function for sliding window operations.
3176	pub fn WindowIterator(comptime T: type) type {
3177	return struct {
3178	buffer: []const T,
3179	index: ?usize,
3180	size: usize,
3181	advance: usize,
3182
3183	const Self = @This();
3184
3185	/// Returns a slice of the next window, or null if window is at end.
3186	pub fn next(self: *Self) ?[]const T {
3187	const start = self.index orelse return null;
3188	const next_index = start + self.advance;
3189	const end = if (start + self.size < self.buffer.len) blk: {
3190	self.index = if (next_index < self.buffer.len) next_index else null;
3191	break :blk start + self.size;
3192	} else blk: {
3193	self.index = null;
3194	break :blk self.buffer.len;
3195	};
3196	return self.buffer[start..end];
3197	}
3198
3199	/// Resets the iterator to the initial window.
3200	pub fn reset(self: *Self) void {
3201	self.index = 0;
3202	}
3203	};
3204	}
3205
3206	/// Returns true if haystack starts with needle.
3207	/// Time complexity: O(needle.len)
3208	pub fn startsWith(comptime T: type, haystack: []const T, needle: []const T) bool {
3209	return if (needle.len > haystack.len) false else eql(T, haystack[0..needle.len], needle);
3210	}
3211
3212	test startsWith {
3213	try testing.expect(startsWith(u8, "Bob", "Bo"));
3214	try testing.expect(!startsWith(u8, "Needle in haystack", "haystack"));
3215	}
3216
3217	/// Returns true if haystack ends with needle.
3218	/// Time complexity: O(needle.len)
3219	pub fn endsWith(comptime T: type, haystack: []const T, needle: []const T) bool {
3220	return if (needle.len > haystack.len) false else eql(T, haystack[haystack.len - needle.len ..], needle);
3221	}
3222
3223	test endsWith {
3224	try testing.expect(endsWith(u8, "Needle in haystack", "haystack"));
3225	try testing.expect(!endsWith(u8, "Bob", "Bo"));
3226	}
3227
3228	/// If `slice` starts with `prefix`, returns the rest of `slice` starting at `prefix.len`.
3229	pub fn cutPrefix(comptime T: type, slice: []const T, prefix: []const T) ?[]const T {
3230	return if (startsWith(T, slice, prefix)) slice[prefix.len..] else null;
3231	}
3232
3233	test cutPrefix {
3234	try testing.expectEqualStrings("foo", cutPrefix(u8, "--example=foo", "--example=").?);
3235	try testing.expectEqual(null, cutPrefix(u8, "--example=foo", "-example="));
3236	}
3237
3238	/// If `slice` ends with `suffix`, returns `slice` from beginning to start of `suffix`.
3239	pub fn cutSuffix(comptime T: type, slice: []const T, suffix: []const T) ?[]const T {
3240	return if (endsWith(T, slice, suffix)) slice[0 .. slice.len - suffix.len] else null;
3241	}
3242
3243	test cutSuffix {
3244	try testing.expectEqualStrings("foo", cutSuffix(u8, "foobar", "bar").?);
3245	try testing.expectEqual(null, cutSuffix(u8, "foobar", "baz"));
3246	}
3247
3248	/// Returns slice of `haystack` before and after first occurrence of `needle`,
3249	/// or `null` if not found.
3250	///
3251	/// See also:
3252	/// * `cutScalar`
3253	/// * `split`
3254	/// * `tokenizeAny`
3255	pub fn cut(comptime T: type, haystack: []const T, needle: []const T) ?struct { []const T, []const T } {
3256	const index = find(T, haystack, needle) orelse return null;
3257	return .{ haystack[0..index], haystack[index + needle.len ..] };
3258	}
3259
3260	test cut {
3261	try testing.expectEqual(null, cut(u8, "a b c", "B"));
3262	const before, const after = cut(u8, "a be c", "be") orelse return error.TestFailed;
3263	try testing.expectEqualStrings("a ", before);
3264	try testing.expectEqualStrings(" c", after);
3265	}
3266
3267	/// Returns slice of `haystack` before and after last occurrence of `needle`,
3268	/// or `null` if not found.
3269	///
3270	/// See also:
3271	/// * `cut`
3272	/// * `cutScalarLast`
3273	pub fn cutLast(comptime T: type, haystack: []const T, needle: []const T) ?struct { []const T, []const T } {
3274	const index = findLast(T, haystack, needle) orelse return null;
3275	return .{ haystack[0..index], haystack[index + needle.len ..] };
3276	}
3277
3278	test cutLast {
3279	try testing.expectEqual(null, cutLast(u8, "a b c", "B"));
3280	const before, const after = cutLast(u8, "a be c be d", "be") orelse return error.TestFailed;
3281	try testing.expectEqualStrings("a be c ", before);
3282	try testing.expectEqualStrings(" d", after);
3283	}
3284
3285	/// Returns slice of `haystack` before and after first occurrence `needle`, or
3286	/// `null` if not found.
3287	///
3288	/// See also:
3289	/// * `cut`
3290	/// * `splitScalar`
3291	/// * `tokenizeScalar`
3292	pub fn cutScalar(comptime T: type, haystack: []const T, needle: T) ?struct { []const T, []const T } {
3293	const index = findScalar(T, haystack, needle) orelse return null;
3294	return .{ haystack[0..index], haystack[index + 1 ..] };
3295	}
3296
3297	test cutScalar {
3298	try testing.expectEqual(null, cutScalar(u8, "a b c", 'B'));
3299	const before, const after = cutScalar(u8, "a b c", 'b') orelse return error.TestFailed;
3300	try testing.expectEqualStrings("a ", before);
3301	try testing.expectEqualStrings(" c", after);
3302	}
3303
3304	/// Returns slice of `haystack` before and after last occurrence of `needle`,
3305	/// or `null` if not found.
3306	///
3307	/// See also:
3308	/// * `cut`
3309	/// * `splitScalar`
3310	/// * `tokenizeScalar`
3311	pub fn cutScalarLast(comptime T: type, haystack: []const T, needle: T) ?struct { []const T, []const T } {
3312	const index = findScalarLast(T, haystack, needle) orelse return null;
3313	return .{ haystack[0..index], haystack[index + 1 ..] };
3314	}
3315
3316	test cutScalarLast {
3317	try testing.expectEqual(null, cutScalarLast(u8, "a b c", 'B'));
3318	const before, const after = cutScalarLast(u8, "a b c b d", 'b') orelse return error.TestFailed;
3319	try testing.expectEqualStrings("a b c ", before);
3320	try testing.expectEqualStrings(" d", after);
3321	}
3322
3323	/// Delimiter type for tokenization and splitting operations.
3324	pub const DelimiterType = enum { sequence, any, scalar };
3325
3326	/// Iterator type for tokenization operations, skipping empty sequences and delimiter sequences.
3327	pub fn TokenIterator(comptime T: type, comptime delimiter_type: DelimiterType) type {
3328	return struct {
3329	buffer: []const T,
3330	delimiter: switch (delimiter_type) {
3331	.sequence, .any => []const T,
3332	.scalar => T,
3333	},
3334	index: usize,
3335
3336	const Self = @This();
3337
3338	/// Returns a slice of the current token, or null if tokenization is
3339	/// complete, and advances to the next token.
3340	pub fn next(self: *Self) ?[]const T {
3341	const result = self.peek() orelse return null;
3342	self.index += result.len;
3343	return result;
3344	}
3345
3346	/// Returns a slice of the current token, or null if tokenization is
3347	/// complete. Does not advance to the next token.
3348	pub fn peek(self: *Self) ?[]const T {
3349	// move to beginning of token
3350	while (self.index < self.buffer.len and self.isDelimiter(self.index)) : (self.index += switch (delimiter_type) {
3351	.sequence => self.delimiter.len,
3352	.any, .scalar => 1,
3353	}) {}
3354	const start = self.index;
3355	if (start == self.buffer.len) {
3356	return null;
3357	}
3358
3359	// move to end of token
3360	var end = start;
3361	while (end < self.buffer.len and !self.isDelimiter(end)) : (end += 1) {}
3362
3363	return self.buffer[start..end];
3364	}
3365
3366	/// Returns a slice of the remaining bytes. Does not affect iterator state.
3367	pub fn rest(self: Self) []const T {
3368	// move to beginning of token
3369	var index: usize = self.index;
3370	while (index < self.buffer.len and self.isDelimiter(index)) : (index += switch (delimiter_type) {
3371	.sequence => self.delimiter.len,
3372	.any, .scalar => 1,
3373	}) {}
3374	return self.buffer[index..];
3375	}
3376
3377	/// Resets the iterator to the initial token.
3378	pub fn reset(self: *Self) void {
3379	self.index = 0;
3380	}
3381
3382	fn isDelimiter(self: Self, index: usize) bool {
3383	switch (delimiter_type) {
3384	.sequence => return startsWith(T, self.buffer[index..], self.delimiter),
3385	.any => {
3386	const item = self.buffer[index];
3387	for (self.delimiter) |delimiter_item| {
3388	if (item == delimiter_item) {
3389	return true;
3390	}
3391	}
3392	return false;
3393	},
3394	.scalar => return self.buffer[index] == self.delimiter,
3395	}
3396	}
3397	};
3398	}
3399
3400	/// Iterator type for splitting operations, including empty sequences between delimiters.
3401	pub fn SplitIterator(comptime T: type, comptime delimiter_type: DelimiterType) type {
3402	return struct {
3403	buffer: []const T,
3404	index: ?usize,
3405	delimiter: switch (delimiter_type) {
3406	.sequence, .any => []const T,
3407	.scalar => T,
3408	},
3409
3410	const Self = @This();
3411
3412	/// Returns a slice of the first field.
3413	/// Call this only to get the first field and then use `next` to get all subsequent fields.
3414	/// Asserts that iteration has not begun.
3415	pub fn first(self: *Self) []const T {
3416	assert(self.index.? == 0);
3417	return self.next().?;
3418	}
3419
3420	/// Returns a slice of the next field, or null if splitting is complete.
3421	pub fn next(self: *Self) ?[]const T {
3422	const start = self.index orelse return null;
3423	const end = if (switch (delimiter_type) {
3424	.sequence => findPos(T, self.buffer, start, self.delimiter),
3425	.any => findAnyPos(T, self.buffer, start, self.delimiter),
3426	.scalar => findScalarPos(T, self.buffer, start, self.delimiter),
3427	}) |delim_start| blk: {
3428	self.index = delim_start + switch (delimiter_type) {
3429	.sequence => self.delimiter.len,
3430	.any, .scalar => 1,
3431	};
3432	break :blk delim_start;
3433	} else blk: {
3434	self.index = null;
3435	break :blk self.buffer.len;
3436	};
3437	return self.buffer[start..end];
3438	}
3439
3440	/// Returns a slice of the next field, or null if splitting is complete.
3441	/// This method does not alter self.index.
3442	pub fn peek(self: *const Self) ?[]const T {
3443	const start = self.index orelse return null;
3444	const end = if (switch (delimiter_type) {
3445	.sequence => findPos(T, self.buffer, start, self.delimiter),
3446	.any => findAnyPos(T, self.buffer, start, self.delimiter),
3447	.scalar => findScalarPos(T, self.buffer, start, self.delimiter),
3448	}) |delim_start| delim_start else self.buffer.len;
3449	return self.buffer[start..end];
3450	}
3451
3452	/// Returns a slice of the remaining bytes. Does not affect iterator state.
3453	pub fn rest(self: Self) []const T {
3454	const end = self.buffer.len;
3455	const start = self.index orelse end;
3456	return self.buffer[start..end];
3457	}
3458
3459	/// Resets the iterator to the initial slice.
3460	pub fn reset(self: *Self) void {
3461	self.index = 0;
3462	}
3463	};
3464	}
3465
3466	/// Iterator type for splitting operations from the end backwards, including empty sequences.
3467	pub fn SplitBackwardsIterator(comptime T: type, comptime delimiter_type: DelimiterType) type {
3468	return struct {
3469	buffer: []const T,
3470	index: ?usize,
3471	delimiter: switch (delimiter_type) {
3472	.sequence, .any => []const T,
3473	.scalar => T,
3474	},
3475
3476	const Self = @This();
3477
3478	/// Returns a slice of the first field.
3479	/// Call this only to get the first field and then use `next` to get all subsequent fields.
3480	/// Asserts that iteration has not begun.
3481	pub fn first(self: *Self) []const T {
3482	assert(self.index.? == self.buffer.len);
3483	return self.next().?;
3484	}
3485
3486	/// Returns a slice of the next field, or null if splitting is complete.
3487	pub fn next(self: *Self) ?[]const T {
3488	const end = self.index orelse return null;
3489	const start = if (switch (delimiter_type) {
3490	.sequence => findLast(T, self.buffer[0..end], self.delimiter),
3491	.any => findLastAny(T, self.buffer[0..end], self.delimiter),
3492	.scalar => findScalarLast(T, self.buffer[0..end], self.delimiter),
3493	}) |delim_start| blk: {
3494	self.index = delim_start;
3495	break :blk delim_start + switch (delimiter_type) {
3496	.sequence => self.delimiter.len,
3497	.any, .scalar => 1,
3498	};
3499	} else blk: {
3500	self.index = null;
3501	break :blk 0;
3502	};
3503	return self.buffer[start..end];
3504	}
3505
3506	/// Returns a slice of the remaining bytes. Does not affect iterator state.
3507	pub fn rest(self: Self) []const T {
3508	const end = self.index orelse 0;
3509	return self.buffer[0..end];
3510	}
3511
3512	/// Resets the iterator to the initial slice.
3513	pub fn reset(self: *Self) void {
3514	self.index = self.buffer.len;
3515	}
3516	};
3517	}
3518
3519	/// Naively combines a series of slices with a separator.
3520	/// Allocates memory for the result, which must be freed by the caller.
3521	pub fn join(allocator: Allocator, separator: []const u8, slices: []const []const u8) Allocator.Error![]u8 {
3522	return joinMaybeZ(allocator, separator, slices, false);
3523	}
3524
3525	/// Naively combines a series of slices with a separator and null terminator.
3526	/// Allocates memory for the result, which must be freed by the caller.
3527	pub fn joinZ(allocator: Allocator, separator: []const u8, slices: []const []const u8) Allocator.Error![:0]u8 {
3528	const out = try joinMaybeZ(allocator, separator, slices, true);
3529	return out[0 .. out.len - 1 :0];
3530	}
3531
3532	fn joinMaybeZ(allocator: Allocator, separator: []const u8, slices: []const []const u8, zero: bool) Allocator.Error![]u8 {
3533	if (slices.len == 0) return if (zero) try allocator.dupe(u8, &[1]u8{0}) else &[0]u8{};
3534
3535	const total_len = blk: {
3536	var sum: usize = separator.len * (slices.len - 1);
3537	for (slices) |slice| sum += slice.len;
3538	if (zero) sum += 1;
3539	break :blk sum;
3540	};
3541
3542	const buf = try allocator.alloc(u8, total_len);
3543	errdefer allocator.free(buf);
3544
3545	@memcpy(buf[0..slices[0].len], slices[0]);
3546	var buf_index: usize = slices[0].len;
3547	for (slices[1..]) |slice| {
3548	@memcpy(buf[buf_index .. buf_index + separator.len], separator);
3549	buf_index += separator.len;
3550	@memcpy(buf[buf_index .. buf_index + slice.len], slice);
3551	buf_index += slice.len;
3552	}
3553
3554	if (zero) buf[buf.len - 1] = 0;
3555
3556	// No need for shrink since buf is exactly the correct size.
3557	return buf;
3558	}
3559
3560	test join {
3561	{
3562	const str = try join(testing.allocator, ",", &[_][]const u8{});
3563	defer testing.allocator.free(str);
3564	try testing.expect(eql(u8, str, ""));
3565	}
3566	{
3567	const str = try join(testing.allocator, ",", &[_][]const u8{ "a", "b", "c" });
3568	defer testing.allocator.free(str);
3569	try testing.expect(eql(u8, str, "a,b,c"));
3570	}
3571	{
3572	const str = try join(testing.allocator, ",", &[_][]const u8{"a"});
3573	defer testing.allocator.free(str);
3574	try testing.expect(eql(u8, str, "a"));
3575	}
3576	{
3577	const str = try join(testing.allocator, ",", &[_][]const u8{ "a", "", "b", "", "c" });
3578	defer testing.allocator.free(str);
3579	try testing.expect(eql(u8, str, "a,,b,,c"));
3580	}
3581	}
3582
3583	test joinZ {
3584	{
3585	const str = try joinZ(testing.allocator, ",", &[_][]const u8{});
3586	defer testing.allocator.free(str);
3587	try testing.expect(eql(u8, str, ""));
3588	try testing.expectEqual(str[str.len], 0);
3589	}
3590	{
3591	const str = try joinZ(testing.allocator, ",", &[_][]const u8{ "a", "b", "c" });
3592	defer testing.allocator.free(str);
3593	try testing.expect(eql(u8, str, "a,b,c"));
3594	try testing.expectEqual(str[str.len], 0);
3595	}
3596	{
3597	const str = try joinZ(testing.allocator, ",", &[_][]const u8{"a"});
3598	defer testing.allocator.free(str);
3599	try testing.expect(eql(u8, str, "a"));
3600	try testing.expectEqual(str[str.len], 0);
3601	}
3602	{
3603	const str = try joinZ(testing.allocator, ",", &[_][]const u8{ "a", "", "b", "", "c" });
3604	defer testing.allocator.free(str);
3605	try testing.expect(eql(u8, str, "a,,b,,c"));
3606	try testing.expectEqual(str[str.len], 0);
3607	}
3608	}
3609
3610	/// Copies each T from slices into a new slice that exactly holds all the elements.
3611	pub fn concat(allocator: Allocator, comptime T: type, slices: []const []const T) Allocator.Error![]T {
3612	return concatMaybeSentinel(allocator, T, slices, null);
3613	}
3614
3615	/// Copies each T from slices into a new slice that exactly holds all the elements.
3616	pub fn concatWithSentinel(allocator: Allocator, comptime T: type, slices: []const []const T, comptime s: T) Allocator.Error![:s]T {
3617	const ret = try concatMaybeSentinel(allocator, T, slices, s);
3618	return ret[0 .. ret.len - 1 :s];
3619	}
3620
3621	/// Copies each T from slices into a new slice that exactly holds all the elements as well as the sentinel.
3622	pub fn concatMaybeSentinel(allocator: Allocator, comptime T: type, slices: []const []const T, comptime s: ?T) Allocator.Error![]T {
3623	if (slices.len == 0) return if (s) |sentinel| try allocator.dupe(T, &[1]T{sentinel}) else &[0]T{};
3624
3625	const total_len = blk: {
3626	var sum: usize = 0;
3627	for (slices) |slice| {
3628	sum += slice.len;
3629	}
3630
3631	if (s) |_| {
3632	sum += 1;
3633	}
3634
3635	break :blk sum;
3636	};
3637
3638	const buf = try allocator.alloc(T, total_len);
3639	errdefer allocator.free(buf);
3640
3641	var buf_index: usize = 0;
3642	for (slices) |slice| {
3643	@memcpy(buf[buf_index .. buf_index + slice.len], slice);
3644	buf_index += slice.len;
3645	}
3646
3647	if (s) |sentinel| {
3648	buf[buf.len - 1] = sentinel;
3649	}
3650
3651	// No need for shrink since buf is exactly the correct size.
3652	return buf;
3653	}
3654
3655	test concat {
3656	{
3657	const str = try concat(testing.allocator, u8, &[_][]const u8{ "abc", "def", "ghi" });
3658	defer testing.allocator.free(str);
3659	try testing.expect(eql(u8, str, "abcdefghi"));
3660	}
3661	{
3662	const str = try concat(testing.allocator, u32, &[_][]const u32{
3663	&[_]u32{ 0, 1 },
3664	&[_]u32{ 2, 3, 4 },
3665	&[_]u32{},
3666	&[_]u32{5},
3667	});
3668	defer testing.allocator.free(str);
3669	try testing.expect(eql(u32, str, &[_]u32{ 0, 1, 2, 3, 4, 5 }));
3670	}
3671	{
3672	const str = try concatWithSentinel(testing.allocator, u8, &[_][]const u8{ "abc", "def", "ghi" }, 0);
3673	defer testing.allocator.free(str);
3674	try testing.expectEqualSentinel(u8, 0, str, "abcdefghi");
3675	}
3676	{
3677	const slice = try concatWithSentinel(testing.allocator, u8, &[_][]const u8{}, 0);
3678	defer testing.allocator.free(slice);
3679	try testing.expectEqualSentinel(u8, 0, slice, &[_:0]u8{});
3680	}
3681	{
3682	const slice = try concatWithSentinel(testing.allocator, u32, &[_][]const u32{
3683	&[_]u32{ 0, 1 },
3684	&[_]u32{ 2, 3, 4 },
3685	&[_]u32{},
3686	&[_]u32{5},
3687	}, 2);
3688	defer testing.allocator.free(slice);
3689	try testing.expectEqualSentinel(u32, 2, slice, &[_:2]u32{ 0, 1, 2, 3, 4, 5 });
3690	}
3691	}
3692
3693	fn moreReadIntTests() !void {
3694	{
3695	const bytes = [_]u8{
3696	0x12,
3697	0x34,
3698	0x56,
3699	0x78,
3700	};
3701	try testing.expect(readInt(u32, &bytes, .big) == 0x12345678);
3702	try testing.expect(readInt(u32, &bytes, .big) == 0x12345678);
3703	try testing.expect(readInt(i32, &bytes, .big) == 0x12345678);
3704	try testing.expect(readInt(u32, &bytes, .little) == 0x78563412);
3705	try testing.expect(readInt(u32, &bytes, .little) == 0x78563412);
3706	try testing.expect(readInt(i32, &bytes, .little) == 0x78563412);
3707	}
3708	{
3709	const buf = [_]u8{
3710	0x00,
3711	0x00,
3712	0x12,
3713	0x34,
3714	};
3715	const answer = readInt(u32, &buf, .big);
3716	try testing.expect(answer == 0x00001234);
3717	}
3718	{
3719	const buf = [_]u8{
3720	0x12,
3721	0x34,
3722	0x00,
3723	0x00,
3724	};
3725	const answer = readInt(u32, &buf, .little);
3726	try testing.expect(answer == 0x00003412);
3727	}
3728	{
3729	const bytes = [_]u8{
3730	0xff,
3731	0xfe,
3732	};
3733	try testing.expect(readInt(u16, &bytes, .big) == 0xfffe);
3734	try testing.expect(readInt(i16, &bytes, .big) == -0x0002);
3735	try testing.expect(readInt(u16, &bytes, .little) == 0xfeff);
3736	try testing.expect(readInt(i16, &bytes, .little) == -0x0101);
3737	}
3738	}
3739
3740	/// Returns the smallest number in a slice. O(n).
3741	/// `slice` must not be empty.
3742	pub fn min(comptime T: type, slice: []const T) T {
3743	assert(slice.len > 0);
3744	var best = slice[0];
3745	for (slice[1..]) |item| {
3746	best = @min(best, item);
3747	}
3748	return best;
3749	}
3750
3751	test min {
3752	try testing.expectEqual(min(u8, "abcdefg"), 'a');
3753	try testing.expectEqual(min(u8, "bcdefga"), 'a');
3754	try testing.expectEqual(min(u8, "a"), 'a');
3755	}
3756
3757	/// Returns the largest number in a slice. O(n).
3758	/// `slice` must not be empty.
3759	pub fn max(comptime T: type, slice: []const T) T {
3760	assert(slice.len > 0);
3761	var best = slice[0];
3762	for (slice[1..]) |item| {
3763	best = @max(best, item);
3764	}
3765	return best;
3766	}
3767
3768	test max {
3769	try testing.expectEqual(max(u8, "abcdefg"), 'g');
3770	try testing.expectEqual(max(u8, "gabcdef"), 'g');
3771	try testing.expectEqual(max(u8, "g"), 'g');
3772	}
3773
3774	/// Finds the smallest and largest number in a slice. O(n).
3775	/// Returns an anonymous struct with the fields `min` and `max`.
3776	/// `slice` must not be empty.
3777	pub fn minMax(comptime T: type, slice: []const T) struct { T, T } {
3778	assert(slice.len > 0);
3779	var running_minimum = slice[0];
3780	var running_maximum = slice[0];
3781	for (slice[1..]) |item| {
3782	running_minimum = @min(running_minimum, item);
3783	running_maximum = @max(running_maximum, item);
3784	}
3785	return .{ running_minimum, running_maximum };
3786	}
3787
3788	test minMax {
3789	{
3790	const actual_min, const actual_max = minMax(u8, "abcdefg");
3791	try testing.expectEqual(@as(u8, 'a'), actual_min);
3792	try testing.expectEqual(@as(u8, 'g'), actual_max);
3793	}
3794	{
3795	const actual_min, const actual_max = minMax(u8, "bcdefga");
3796	try testing.expectEqual(@as(u8, 'a'), actual_min);
3797	try testing.expectEqual(@as(u8, 'g'), actual_max);
3798	}
3799	{
3800	const actual_min, const actual_max = minMax(u8, "a");
3801	try testing.expectEqual(@as(u8, 'a'), actual_min);
3802	try testing.expectEqual(@as(u8, 'a'), actual_max);
3803	}
3804	}
3805
3806	/// Deprecated in favor of `findMin`.
3807	pub const indexOfMin = findMin;
3808
3809	/// Returns the index of the smallest number in a slice. O(n).
3810	/// `slice` must not be empty.
3811	pub fn findMin(comptime T: type, slice: []const T) usize {
3812	assert(slice.len > 0);
3813	var best = slice[0];
3814	var index: usize = 0;
3815	for (slice[1..], 0..) |item, i| {
3816	if (item < best) {
3817	best = item;
3818	index = i + 1;
3819	}
3820	}
3821	return index;
3822	}
3823
3824	test findMin {
3825	try testing.expectEqual(findMin(u8, "abcdefg"), 0);
3826	try testing.expectEqual(findMin(u8, "bcdefga"), 6);
3827	try testing.expectEqual(findMin(u8, "a"), 0);
3828	}
3829
3830	pub const indexOfMax = findMax;
3831
3832	/// Returns the index of the largest number in a slice. O(n).
3833	/// `slice` must not be empty.
3834	pub fn findMax(comptime T: type, slice: []const T) usize {
3835	assert(slice.len > 0);
3836	var best = slice[0];
3837	var index: usize = 0;
3838	for (slice[1..], 0..) |item, i| {
3839	if (item > best) {
3840	best = item;
3841	index = i + 1;
3842	}
3843	}
3844	return index;
3845	}
3846
3847	test findMax {
3848	try testing.expectEqual(findMax(u8, "abcdefg"), 6);
3849	try testing.expectEqual(findMax(u8, "gabcdef"), 0);
3850	try testing.expectEqual(findMax(u8, "a"), 0);
3851	}
3852
3853	/// Deprecated in favor of `findMinMax`.
3854	pub const indexOfMinMax = findMinMax;
3855
3856	/// Finds the indices of the smallest and largest number in a slice. O(n).
3857	/// Returns the indices of the smallest and largest numbers in that order.
3858	/// `slice` must not be empty.
3859	pub fn findMinMax(comptime T: type, slice: []const T) struct { usize, usize } {
3860	assert(slice.len > 0);
3861	var minVal = slice[0];
3862	var maxVal = slice[0];
3863	var minIdx: usize = 0;
3864	var maxIdx: usize = 0;
3865	for (slice[1..], 0..) |item, i| {
3866	if (item < minVal) {
3867	minVal = item;
3868	minIdx = i + 1;
3869	}
3870	if (item > maxVal) {
3871	maxVal = item;
3872	maxIdx = i + 1;
3873	}
3874	}
3875	return .{ minIdx, maxIdx };
3876	}
3877
3878	test findMinMax {
3879	try testing.expectEqual(.{ 0, 6 }, findMinMax(u8, "abcdefg"));
3880	try testing.expectEqual(.{ 1, 0 }, findMinMax(u8, "gabcdef"));
3881	try testing.expectEqual(.{ 0, 0 }, findMinMax(u8, "a"));
3882	}
3883
3884	/// Exchanges contents of two memory locations.
3885	pub fn swap(comptime T: type, noalias a: *T, noalias b: *T) void {
3886	if (@inComptime()) {
3887	// In comptime, accessing bytes of values with no defined layout is a compile error.
3888	const tmp = a.*;
3889	a.* = b.*;
3890	b.* = tmp;
3891	} else {
3892	// Swapping in streaming nature from start to end instead of swapping
3893	// everything in one step allows easier optimizations and less stack usage.
3894	const a_bytes: []align(@alignOf(T)) u8 = @ptrCast(a);
3895	const b_bytes: []align(@alignOf(T)) u8 = @ptrCast(b);
3896	for (a_bytes, b_bytes) |*ab, *bb| {
3897	const tmp = ab.*;
3898	ab.* = bb.*;
3899	bb.* = tmp;
3900	}
3901	}
3902	}
3903
3904	test "swap works at comptime with types with no defined layout" {
3905	comptime {
3906	const T = struct { val: u64 };
3907	var a: T = .{ .val = 0 };
3908	var b: T = .{ .val = 1 };
3909	swap(T, &a, &b);
3910	try testing.expectEqual(T{ .val = 1 }, a);
3911	try testing.expectEqual(T{ .val = 0 }, b);
3912	}
3913	}
3914
3915	inline fn reverseVector(comptime N: usize, comptime T: type, a: []T) [N]T {
3916	var res: [N]T = undefined;
3917	inline for (0..N) |i| {
3918	res[i] = a[N - i - 1];
3919	}
3920	return res;
3921	}
3922
3923	/// In-place order reversal of a slice
3924	pub fn reverse(comptime T: type, items: []T) void {
3925	var i: usize = 0;
3926	const end = items.len / 2;
3927
3928	vec: {
3929	if (!use_vectors) break :vec;
3930	if (@inComptime()) break :vec;
3931	switch (@typeInfo(T)) {
3932	.int, .float => {},
3933	.pointer => |pointer| if (pointer.size == .slice) break :vec,
3934	else => break :vec,
3935	}
3936	if (@bitSizeOf(T) == 0 or !comptime std.math.isPowerOfTwo(@bitSizeOf(T))) break :vec;
3937	const simd_size = std.simd.suggestVectorLength(T) orelse break :vec;
3938	if (simd_size > end) break :vec;
3939
3940	const simd_end = end - (simd_size - 1);
3941	while (i < simd_end) : (i += simd_size) {
3942	const left_slice = items[i .. i + simd_size];
3943	const right_slice = items[items.len - i - simd_size .. items.len - i];
3944
3945	const left_shuffled: [simd_size]T = reverseVector(simd_size, T, left_slice);
3946	const right_shuffled: [simd_size]T = reverseVector(simd_size, T, right_slice);
3947
3948	@memcpy(right_slice, &left_shuffled);
3949	@memcpy(left_slice, &right_shuffled);
3950	}
3951	}
3952
3953	while (i < end) : (i += 1) {
3954	swap(T, &items[i], &items[items.len - i - 1]);
3955	}
3956	}
3957
3958	test reverse {
3959	{
3960	var arr = [_]i32{ 5, 3, 1, 2, 4 };
3961	reverse(i32, arr[0..]);
3962	try testing.expectEqualSlices(i32, &arr, &.{ 4, 2, 1, 3, 5 });
3963	}
3964	{
3965	var arr = [_]u0{};
3966	reverse(u0, arr[0..]);
3967	try testing.expectEqualSlices(u0, &arr, &.{});
3968	}
3969	{
3970	var arr = [_]i64{ 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18 };
3971	reverse(i64, arr[0..]);
3972	try testing.expectEqualSlices(i64, &arr, &.{ 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 });
3973	}
3974	{
3975	var arr = [_][]const u8{ "a", "b", "c", "d" };
3976	reverse([]const u8, arr[0..]);
3977	try testing.expectEqualSlices([]const u8, &arr, &.{ "d", "c", "b", "a" });
3978	}
3979	{
3980	const MyType = union(enum) {
3981	a: [3]u8,
3982	b: u24,
3983	c,
3984	};
3985	var arr = [_]MyType{ .{ .a = .{ 0, 0, 0 } }, .{ .b = 0 }, .c };
3986	reverse(MyType, arr[0..]);
3987	try testing.expectEqualSlices(MyType, &arr, &([_]MyType{ .c, .{ .b = 0 }, .{ .a = .{ 0, 0, 0 } } }));
3988	}
3989	}
3990
3991	/// Returned by `reverseIterator`.
3992	pub fn ReverseIterator(comptime T: type) type {
3993	const ptr = switch (@typeInfo(T)) {
3994	.pointer => |ptr| ptr,
3995	else => @compileError("expected slice or pointer to array, found '" ++ @typeName(T) ++ "'"),
3996	};
3997	switch (ptr.size) {
3998	.slice => {},
3999	.one => if (@typeInfo(ptr.child) != .array) @compileError("expected slice or pointer to array, found '" ++ @typeName(T) ++ "'"),
4000	.many, .c => @compileError("expected slice or pointer to array, found '" ++ @typeName(T) ++ "'"),
4001	}
4002	const Element = std.meta.Elem(T);
4003	const Pointer = @Pointer(.many, ptr.attrs, Element, std.meta.sentinel(T));
4004	const ElementPointer = @Pointer(.one, ptr.attrs, Element, null);
4005	return struct {
4006	ptr: Pointer,
4007	index: usize,
4008	pub fn next(self: *@This()) ?Element {
4009	if (self.index == 0) return null;
4010	self.index -= 1;
4011	return self.ptr[self.index];
4012	}
4013	pub fn nextPtr(self: *@This()) ?ElementPointer {
4014	if (self.index == 0) return null;
4015	self.index -= 1;
4016	return &self.ptr[self.index];
4017	}
4018	};
4019	}
4020
4021	/// Iterates over a slice in reverse.
4022	pub fn reverseIterator(slice: anytype) ReverseIterator(@TypeOf(slice)) {
4023	return .{ .ptr = slice.ptr, .index = slice.len };
4024	}
4025
4026	test reverseIterator {
4027	{
4028	var it = reverseIterator("abc");
4029	try testing.expectEqual(@as(?u8, 'c'), it.next());
4030	try testing.expectEqual(@as(?u8, 'b'), it.next());
4031	try testing.expectEqual(@as(?u8, 'a'), it.next());
4032	try testing.expectEqual(@as(?u8, null), it.next());
4033	}
4034	{
4035	var array = [2]i32{ 3, 7 };
4036	const slice: []const i32 = &array;
4037	var it = reverseIterator(slice);
4038	try testing.expectEqual(@as(?i32, 7), it.next());
4039	try testing.expectEqual(@as(?i32, 3), it.next());
4040	try testing.expectEqual(@as(?i32, null), it.next());
4041
4042	it = reverseIterator(slice);
4043	try testing.expect(*const i32 == @TypeOf(it.nextPtr().?));
4044	try testing.expectEqual(@as(?i32, 7), it.nextPtr().?.*);
4045	try testing.expectEqual(@as(?i32, 3), it.nextPtr().?.*);
4046	try testing.expectEqual(@as(?*const i32, null), it.nextPtr());
4047
4048	const mut_slice: []i32 = &array;
4049	var mut_it = reverseIterator(mut_slice);
4050	mut_it.nextPtr().?.* += 1;
4051	mut_it.nextPtr().?.* += 2;
4052	try testing.expectEqual([2]i32{ 5, 8 }, array);
4053	}
4054	{
4055	var array = [2]i32{ 3, 7 };
4056	const ptr_to_array: *const [2]i32 = &array;
4057	var it = reverseIterator(ptr_to_array);
4058	try testing.expectEqual(@as(?i32, 7), it.next());
4059	try testing.expectEqual(@as(?i32, 3), it.next());
4060	try testing.expectEqual(@as(?i32, null), it.next());
4061
4062	it = reverseIterator(ptr_to_array);
4063	try testing.expect(*const i32 == @TypeOf(it.nextPtr().?));
4064	try testing.expectEqual(@as(?i32, 7), it.nextPtr().?.*);
4065	try testing.expectEqual(@as(?i32, 3), it.nextPtr().?.*);
4066	try testing.expectEqual(@as(?*const i32, null), it.nextPtr());
4067
4068	const mut_ptr_to_array: *[2]i32 = &array;
4069	var mut_it = reverseIterator(mut_ptr_to_array);
4070	mut_it.nextPtr().?.* += 1;
4071	mut_it.nextPtr().?.* += 2;
4072	try testing.expectEqual([2]i32{ 5, 8 }, array);
4073	}
4074	}
4075
4076	/// In-place rotation of the values in an array ([0 1 2 3] becomes [1 2 3 0] if we rotate by 1)
4077	/// Assumes 0 <= amount <= items.len
4078	pub fn rotate(comptime T: type, items: []T, amount: usize) void {
4079	reverse(T, items[0..amount]);
4080	reverse(T, items[amount..]);
4081	reverse(T, items);
4082	}
4083
4084	test rotate {
4085	var arr = [_]i32{ 5, 3, 1, 2, 4 };
4086	rotate(i32, arr[0..], 2);
4087
4088	try testing.expect(eql(i32, &arr, &[_]i32{ 1, 2, 4, 5, 3 }));
4089	}
4090
4091	/// Replace needle with replacement as many times as possible, writing to an output buffer which is assumed to be of
4092	/// appropriate size. Use replacementSize to calculate an appropriate buffer size.
4093	/// The `input` and `output` slices must not overlap.
4094	/// The needle must not be empty.
4095	/// Returns the number of replacements made.
4096	pub fn replace(comptime T: type, input: []const T, needle: []const T, replacement: []const T, output: []T) usize {
4097	// Empty needle will loop until output buffer overflows.
4098	assert(needle.len > 0);
4099
4100	var i: usize = 0;
4101	var slide: usize = 0;
4102	var replacements: usize = 0;
4103	while (slide < input.len) {
4104	if (mem.startsWith(T, input[slide..], needle)) {
4105	@memcpy(output[i..][0..replacement.len], replacement);
4106	i += replacement.len;
4107	slide += needle.len;
4108	replacements += 1;
4109	} else {
4110	output[i] = input[slide];
4111	i += 1;
4112	slide += 1;
4113	}
4114	}
4115
4116	return replacements;
4117	}
4118
4119	test replace {
4120	var output: [29]u8 = undefined;
4121	var replacements = replace(u8, "All your base are belong to us", "base", "Zig", output[0..]);
4122	var expected: []const u8 = "All your Zig are belong to us";
4123	try testing.expect(replacements == 1);
4124	try testing.expectEqualStrings(expected, output[0..expected.len]);
4125
4126	replacements = replace(u8, "Favor reading code over writing code.", "code", "", output[0..]);
4127	expected = "Favor reading over writing .";
4128	try testing.expect(replacements == 2);
4129	try testing.expectEqualStrings(expected, output[0..expected.len]);
4130
4131	// Empty needle is not allowed but input may be empty.
4132	replacements = replace(u8, "", "x", "y", output[0..0]);
4133	expected = "";
4134	try testing.expect(replacements == 0);
4135	try testing.expectEqualStrings(expected, output[0..expected.len]);
4136
4137	// Adjacent replacements.
4138
4139	replacements = replace(u8, "\\n\\n", "\\n", "\n", output[0..]);
4140	expected = "\n\n";
4141	try testing.expect(replacements == 2);
4142	try testing.expectEqualStrings(expected, output[0..expected.len]);
4143
4144	replacements = replace(u8, "abbba", "b", "cd", output[0..]);
4145	expected = "acdcdcda";
4146	try testing.expect(replacements == 3);
4147	try testing.expectEqualStrings(expected, output[0..expected.len]);
4148	}
4149
4150	/// Replace all occurrences of `match` with `replacement`.
4151	pub fn replaceScalar(comptime T: type, slice: []T, match: T, replacement: T) void {
4152	for (slice) |*e| {
4153	if (e.* == match)
4154	e.* = replacement;
4155	}
4156	}
4157
4158	/// Collapse consecutive duplicate elements into one entry.
4159	pub fn collapseRepeatsLen(comptime T: type, slice: []T, elem: T) usize {
4160	if (slice.len == 0) return 0;
4161	var write_idx: usize = 1;
4162	var read_idx: usize = 1;
4163	while (read_idx < slice.len) : (read_idx += 1) {
4164	if (slice[read_idx - 1] != elem or slice[read_idx] != elem) {
4165	slice[write_idx] = slice[read_idx];
4166	write_idx += 1;
4167	}
4168	}
4169	return write_idx;
4170	}
4171
4172	/// Collapse consecutive duplicate elements into one entry.
4173	pub fn collapseRepeats(comptime T: type, slice: []T, elem: T) []T {
4174	return slice[0..collapseRepeatsLen(T, slice, elem)];
4175	}
4176
4177	fn testCollapseRepeats(str: []const u8, elem: u8, expected: []const u8) !void {
4178	const mutable = try std.testing.allocator.dupe(u8, str);
4179	defer std.testing.allocator.free(mutable);
4180	try testing.expect(std.mem.eql(u8, collapseRepeats(u8, mutable, elem), expected));
4181	}
4182	test collapseRepeats {
4183	try testCollapseRepeats("", '/', "");
4184	try testCollapseRepeats("a", '/', "a");
4185	try testCollapseRepeats("/", '/', "/");
4186	try testCollapseRepeats("//", '/', "/");
4187	try testCollapseRepeats("/a", '/', "/a");
4188	try testCollapseRepeats("//a", '/', "/a");
4189	try testCollapseRepeats("a/", '/', "a/");
4190	try testCollapseRepeats("a//", '/', "a/");
4191	try testCollapseRepeats("a/a", '/', "a/a");
4192	try testCollapseRepeats("a//a", '/', "a/a");
4193	try testCollapseRepeats("//a///a////", '/', "/a/a/");
4194	}
4195
4196	/// Calculate the size needed in an output buffer to perform a replacement.
4197	/// The needle must not be empty.
4198	pub fn replacementSize(comptime T: type, input: []const T, needle: []const T, replacement: []const T) usize {
4199	// Empty needle will loop forever.
4200	assert(needle.len > 0);
4201
4202	var i: usize = 0;
4203	var size: usize = input.len;
4204	while (i < input.len) {
4205	if (mem.startsWith(T, input[i..], needle)) {
4206	size = size - needle.len + replacement.len;
4207	i += needle.len;
4208	} else {
4209	i += 1;
4210	}
4211	}
4212
4213	return size;
4214	}
4215
4216	test replacementSize {
4217	try testing.expect(replacementSize(u8, "All your base are belong to us", "base", "Zig") == 29);
4218	try testing.expect(replacementSize(u8, "Favor reading code over writing code.", "code", "") == 29);
4219	try testing.expect(replacementSize(u8, "Only one obvious way to do things.", "things.", "things in Zig.") == 41);
4220
4221	// Empty needle is not allowed but input may be empty.
4222	try testing.expect(replacementSize(u8, "", "x", "y") == 0);
4223
4224	// Adjacent replacements.
4225	try testing.expect(replacementSize(u8, "\\n\\n", "\\n", "\n") == 2);
4226	try testing.expect(replacementSize(u8, "abbba", "b", "cd") == 8);
4227	}
4228
4229	/// Perform a replacement on an allocated buffer of pre-determined size. Caller must free returned memory.
4230	pub fn replaceOwned(comptime T: type, allocator: Allocator, input: []const T, needle: []const T, replacement: []const T) Allocator.Error![]T {
4231	const output = try allocator.alloc(T, replacementSize(T, input, needle, replacement));
4232	_ = replace(T, input, needle, replacement, output);
4233	return output;
4234	}
4235
4236	test replaceOwned {
4237	const gpa = std.testing.allocator;
4238
4239	const base_replace = replaceOwned(u8, gpa, "All your base are belong to us", "base", "Zig") catch @panic("out of memory");
4240	defer gpa.free(base_replace);
4241	try testing.expect(eql(u8, base_replace, "All your Zig are belong to us"));
4242
4243	const zen_replace = replaceOwned(u8, gpa, "Favor reading code over writing code.", " code", "") catch @panic("out of memory");
4244	defer gpa.free(zen_replace);
4245	try testing.expect(eql(u8, zen_replace, "Favor reading over writing."));
4246	}
4247
4248	/// Converts a little-endian integer to host endianness.
4249	pub fn littleToNative(comptime T: type, x: T) T {
4250	return switch (native_endian) {
4251	.little => x,
4252	.big => @byteSwap(x),
4253	};
4254	}
4255
4256	/// Converts a big-endian integer to host endianness.
4257	pub fn bigToNative(comptime T: type, x: T) T {
4258	return switch (native_endian) {
4259	.little => @byteSwap(x),
4260	.big => x,
4261	};
4262	}
4263
4264	/// Converts an integer from specified endianness to host endianness.
4265	pub fn toNative(comptime T: type, x: T, endianness_of_x: Endian) T {
4266	return switch (endianness_of_x) {
4267	.little => littleToNative(T, x),
4268	.big => bigToNative(T, x),
4269	};
4270	}
4271
4272	/// Converts an integer which has host endianness to the desired endianness.
4273	pub fn nativeTo(comptime T: type, x: T, desired_endianness: Endian) T {
4274	return switch (desired_endianness) {
4275	.little => nativeToLittle(T, x),
4276	.big => nativeToBig(T, x),
4277	};
4278	}
4279
4280	/// Converts an integer which has host endianness to little endian.
4281	pub fn nativeToLittle(comptime T: type, x: T) T {
4282	return switch (native_endian) {
4283	.little => x,
4284	.big => @byteSwap(x),
4285	};
4286	}
4287
4288	/// Converts an integer which has host endianness to big endian.
4289	pub fn nativeToBig(comptime T: type, x: T) T {
4290	return switch (native_endian) {
4291	.little => @byteSwap(x),
4292	.big => x,
4293	};
4294	}
4295
4296	/// Returns the number of elements that, if added to the given pointer, align it
4297	/// to a multiple of the given quantity, or `null` if one of the following
4298	/// conditions is met:
4299	/// - The aligned pointer would not fit the address space,
4300	/// - The delta required to align the pointer is not a multiple of the pointee's
4301	/// type.
4302	pub fn alignPointerOffset(ptr: anytype, align_to: usize) ?usize {
4303	assert(isValidAlign(align_to));
4304
4305	const T = @TypeOf(ptr);
4306	const info = @typeInfo(T);
4307	if (info != .pointer or info.pointer.size != .many)
4308	@compileError("expected many item pointer, got " ++ @typeName(T));
4309
4310	// Do nothing if the pointer is already well-aligned.
4311	if (align_to <= info.pointer.attrs.@"align" orelse @alignOf(info.pointer.child))
4312	return 0;
4313
4314	// Calculate the aligned base address with an eye out for overflow.
4315	const addr = @intFromPtr(ptr);
4316	var ov = @addWithOverflow(addr, align_to - 1);
4317	if (ov[1] != 0) return null;
4318	ov[0] &= ~@as(usize, align_to - 1);
4319
4320	// The delta is expressed in terms of bytes, turn it into a number of child
4321	// type elements.
4322	const delta = ov[0] - addr;
4323	const pointee_size = @sizeOf(info.pointer.child);
4324	if (delta % pointee_size != 0) return null;
4325	return delta / pointee_size;
4326	}
4327
4328	/// Aligns a given pointer value to a specified alignment factor.
4329	/// Returns an aligned pointer or null if one of the following conditions is
4330	/// met:
4331	/// - The aligned pointer would not fit the address space,
4332	/// - The delta required to align the pointer is not a multiple of the pointee's
4333	/// type.
4334	pub fn alignPointer(ptr: anytype, align_to: usize) ?@TypeOf(ptr) {
4335	const adjust_off = alignPointerOffset(ptr, align_to) orelse return null;
4336	// Avoid the use of ptrFromInt to avoid losing the pointer provenance info.
4337	return @alignCast(ptr + adjust_off);
4338	}
4339
4340	test alignPointer {
4341	const S = struct {
4342	fn checkAlign(comptime T: type, base: usize, align_to: usize, expected: usize) !void {
4343	const ptr: T = @ptrFromInt(base);
4344	const aligned = alignPointer(ptr, align_to);
4345	try testing.expectEqual(expected, @intFromPtr(aligned));
4346	}
4347	};
4348
4349	try S.checkAlign([*]u8, 0x123, 0x200, 0x200);
4350	try S.checkAlign([*]align(4) u8, 0x10, 2, 0x10);
4351	try S.checkAlign([*]u32, 0x10, 2, 0x10);
4352	try S.checkAlign([*]u32, 0x4, 16, 0x10);
4353	// Misaligned.
4354	try S.checkAlign([*]align(1) u32, 0x3, 2, 0);
4355	// Overflow.
4356	try S.checkAlign([*]u32, math.maxInt(usize) - 3, 8, 0);
4357	}
4358
4359	fn CopyPtrAttrs(
4360	comptime source: type,
4361	comptime size: std.builtin.Type.Pointer.Size,
4362	comptime child: type,
4363	) type {
4364	const ptr = @typeInfo(source).pointer;
4365	var attrs = ptr.attrs;
4366	if (attrs.@"align" == null) {
4367	const want = @alignOf(ptr.child);
4368	if (@alignOf(child) != want) {
4369	attrs.@"align" = want;
4370	}
4371	}
4372	return @Pointer(size, attrs, child, null);
4373	}
4374
4375	fn AsBytesReturnType(comptime P: type) type {
4376	const pointer = @typeInfo(P).pointer;
4377	assert(pointer.size == .one);
4378	const size = @sizeOf(pointer.child);
4379	return CopyPtrAttrs(P, .one, [size]u8);
4380	}
4381
4382	/// Given a pointer to a single item, returns a slice of the underlying bytes, preserving pointer attributes.
4383	pub fn asBytes(ptr: anytype) AsBytesReturnType(@TypeOf(ptr)) {
4384	return @ptrCast(@alignCast(ptr));
4385	}
4386
4387	test asBytes {
4388	const deadbeef = @as(u32, 0xDEADBEEF);
4389	const deadbeef_bytes = switch (native_endian) {
4390	.big => "\xDE\xAD\xBE\xEF",
4391	.little => "\xEF\xBE\xAD\xDE",
4392	};
4393
4394	try testing.expect(eql(u8, asBytes(&deadbeef), deadbeef_bytes));
4395
4396	var codeface = @as(u32, 0xC0DEFACE);
4397	for (asBytes(&codeface)) |*b|
4398	b.* = 0;
4399	try testing.expect(codeface == 0);
4400
4401	const S = packed struct {
4402	a: u8,
4403	b: u8,
4404	c: u8,
4405	d: u8,
4406	};
4407
4408	const inst = S{
4409	.a = 0xBE,
4410	.b = 0xEF,
4411	.c = 0xDE,
4412	.d = 0xA1,
4413	};
4414	switch (native_endian) {
4415	.little => {
4416	try testing.expect(eql(u8, asBytes(&inst), "\xBE\xEF\xDE\xA1"));
4417	},
4418	.big => {
4419	try testing.expect(eql(u8, asBytes(&inst), "\xA1\xDE\xEF\xBE"));
4420	},
4421	}
4422
4423	const ZST = struct {};
4424	const zero = ZST{};
4425	try testing.expect(eql(u8, asBytes(&zero), ""));
4426	}
4427
4428	test "asBytes preserves pointer attributes" {
4429	const inArr: u32 align(16) = 0xDEADBEEF;
4430	const inPtr = @as(*align(16) const volatile u32, @ptrCast(&inArr));
4431	const outSlice = asBytes(inPtr);
4432
4433	const in = @typeInfo(@TypeOf(inPtr)).pointer;
4434	const out = @typeInfo(@TypeOf(outSlice)).pointer;
4435
4436	const in_attrs = in.attrs;
4437	const out_attrs = out.attrs;
4438
4439	try testing.expectEqual(in_attrs.@"const", out_attrs.@"const");
4440	try testing.expectEqual(in_attrs.@"volatile", out_attrs.@"volatile");
4441	try testing.expectEqual(in_attrs.@"allowzero", out_attrs.@"allowzero");
4442	try testing.expectEqual(in_attrs.@"align", out_attrs.@"align");
4443	}
4444
4445	/// Given any value, returns a copy of its bytes in an array.
4446	pub fn toBytes(value: anytype) [@sizeOf(@TypeOf(value))]u8 {
4447	return asBytes(&value).*;
4448	}
4449
4450	test toBytes {
4451	var my_bytes = toBytes(@as(u32, 0x12345678));
4452	switch (native_endian) {
4453	.big => try testing.expect(eql(u8, &my_bytes, "\x12\x34\x56\x78")),
4454	.little => try testing.expect(eql(u8, &my_bytes, "\x78\x56\x34\x12")),
4455	}
4456
4457	my_bytes[0] = '\x99';
4458	switch (native_endian) {
4459	.big => try testing.expect(eql(u8, &my_bytes, "\x99\x34\x56\x78")),
4460	.little => try testing.expect(eql(u8, &my_bytes, "\x99\x56\x34\x12")),
4461	}
4462	}
4463
4464	fn BytesAsValueReturnType(comptime T: type, comptime B: type) type {
4465	return CopyPtrAttrs(B, .one, T);
4466	}
4467
4468	/// Given a pointer to an array of bytes, returns a pointer to a value of the specified type
4469	/// backed by those bytes, preserving pointer attributes.
4470	pub fn bytesAsValue(comptime T: type, bytes: anytype) BytesAsValueReturnType(T, @TypeOf(bytes)) {
4471	return @ptrCast(bytes);
4472	}
4473
4474	test bytesAsValue {
4475	const deadbeef = @as(u32, 0xDEADBEEF);
4476	const deadbeef_bytes = switch (native_endian) {
4477	.big => "\xDE\xAD\xBE\xEF",
4478	.little => "\xEF\xBE\xAD\xDE",
4479	};
4480
4481	try testing.expect(deadbeef == bytesAsValue(u32, deadbeef_bytes).*);
4482
4483	var codeface_bytes: [4]u8 = switch (native_endian) {
4484	.big => "\xC0\xDE\xFA\xCE",
4485	.little => "\xCE\xFA\xDE\xC0",
4486	}.*;
4487	const codeface = bytesAsValue(u32, &codeface_bytes);
4488	try testing.expect(codeface.* == 0xC0DEFACE);
4489	codeface.* = 0;
4490	for (codeface_bytes) |b|
4491	try testing.expect(b == 0);
4492
4493	const S = packed struct {
4494	a: u8,
4495	b: u8,
4496	c: u8,
4497	d: u8,
4498	};
4499
4500	const inst = S{
4501	.a = 0xBE,
4502	.b = 0xEF,
4503	.c = 0xDE,
4504	.d = 0xA1,
4505	};
4506	const inst_bytes = switch (native_endian) {
4507	.little => "\xBE\xEF\xDE\xA1",
4508	.big => "\xA1\xDE\xEF\xBE",
4509	};
4510	const inst2 = bytesAsValue(S, inst_bytes);
4511	try testing.expect(std.meta.eql(inst, inst2.*));
4512	}
4513
4514	test "bytesAsValue preserves pointer attributes" {
4515	const inArr align(16) = [4]u8{ 0xDE, 0xAD, 0xBE, 0xEF };
4516	const inSlice = @as(*align(16) const volatile [4]u8, @ptrCast(&inArr))[0..];
4517	const outPtr = bytesAsValue(u32, inSlice);
4518
4519	const in_attrs = @typeInfo(@TypeOf(inSlice)).pointer.attrs;
4520	const out_attrs = @typeInfo(@TypeOf(outPtr)).pointer.attrs;
4521
4522	try testing.expectEqual(in_attrs.@"const", out_attrs.@"const");
4523	try testing.expectEqual(in_attrs.@"volatile", out_attrs.@"volatile");
4524	try testing.expectEqual(in_attrs.@"allowzero", out_attrs.@"allowzero");
4525	try testing.expectEqual(in_attrs.@"align", out_attrs.@"align");
4526	}
4527
4528	/// Given a pointer to an array of bytes, returns a value of the specified type backed by a
4529	/// copy of those bytes.
4530	pub fn bytesToValue(comptime T: type, bytes: anytype) T {
4531	return bytesAsValue(T, bytes).*;
4532	}
4533	test bytesToValue {
4534	const deadbeef_bytes = switch (native_endian) {
4535	.big => "\xDE\xAD\xBE\xEF",
4536	.little => "\xEF\xBE\xAD\xDE",
4537	};
4538
4539	const deadbeef = bytesToValue(u32, deadbeef_bytes);
4540	try testing.expect(deadbeef == @as(u32, 0xDEADBEEF));
4541	}
4542
4543	fn BytesAsSliceReturnType(comptime T: type, comptime bytesType: type) type {
4544	return CopyPtrAttrs(bytesType, .slice, T);
4545	}
4546
4547	/// Given a slice of bytes, returns a slice of the specified type
4548	/// backed by those bytes, preserving pointer attributes.
4549	/// If `T` is zero-bytes sized, the returned slice has a len of zero.
4550	pub fn bytesAsSlice(comptime T: type, bytes: anytype) BytesAsSliceReturnType(T, @TypeOf(bytes)) {
4551	// let's not give an undefined pointer to @ptrCast
4552	// it may be equal to zero and fail a null check
4553	if (bytes.len == 0 or @sizeOf(T) == 0) {
4554	return &[0]T{};
4555	}
4556
4557	const cast_target = CopyPtrAttrs(@TypeOf(bytes), .many, T);
4558
4559	return @as(cast_target, @ptrCast(bytes))[0..@divExact(bytes.len, @sizeOf(T))];
4560	}
4561
4562	test bytesAsSlice {
4563	{
4564	const bytes = [_]u8{ 0xDE, 0xAD, 0xBE, 0xEF };
4565	const slice = bytesAsSlice(u16, bytes[0..]);
4566	try testing.expect(slice.len == 2);
4567	try testing.expect(bigToNative(u16, slice[0]) == 0xDEAD);
4568	try testing.expect(bigToNative(u16, slice[1]) == 0xBEEF);
4569	}
4570	{
4571	const bytes = [_]u8{ 0xDE, 0xAD, 0xBE, 0xEF };
4572	var runtime_zero: usize = 0;
4573	_ = &runtime_zero;
4574	const slice = bytesAsSlice(u16, bytes[runtime_zero..]);
4575	try testing.expect(slice.len == 2);
4576	try testing.expect(bigToNative(u16, slice[0]) == 0xDEAD);
4577	try testing.expect(bigToNative(u16, slice[1]) == 0xBEEF);
4578	}
4579	}
4580
4581	test "bytesAsSlice keeps pointer alignment" {
4582	{
4583	var bytes = [_]u8{ 0x01, 0x02, 0x03, 0x04 };
4584	const numbers = bytesAsSlice(u32, bytes[0..]);
4585	try comptime testing.expect(@TypeOf(numbers) == []align(@alignOf(@TypeOf(bytes))) u32);
4586	}
4587	{
4588	var bytes = [_]u8{ 0x01, 0x02, 0x03, 0x04 };
4589	var runtime_zero: usize = 0;
4590	_ = &runtime_zero;
4591	const numbers = bytesAsSlice(u32, bytes[runtime_zero..]);
4592	try comptime testing.expect(@TypeOf(numbers) == []align(@alignOf(@TypeOf(bytes))) u32);
4593	}
4594	}
4595
4596	test "bytesAsSlice on a packed struct" {
4597	const F = packed struct {
4598	a: u8,
4599	};
4600
4601	const b: [1]u8 = .{9};
4602	const f = bytesAsSlice(F, &b);
4603	try testing.expect(f[0].a == 9);
4604	}
4605
4606	test "bytesAsSlice with specified alignment" {
4607	var bytes align(4) = [_]u8{
4608	0x33,
4609	0x33,
4610	0x33,
4611	0x33,
4612	};
4613	const slice: []u32 = std.mem.bytesAsSlice(u32, bytes[0..]);
4614	try testing.expect(slice[0] == 0x33333333);
4615	}
4616
4617	test "bytesAsSlice preserves pointer attributes" {
4618	const inArr align(16) = [4]u8{ 0xDE, 0xAD, 0xBE, 0xEF };
4619	const inSlice = @as(*align(16) const volatile [4]u8, @ptrCast(&inArr))[0..];
4620	const outSlice = bytesAsSlice(u16, inSlice);
4621
4622	const in_attrs = @typeInfo(@TypeOf(inSlice)).pointer.attrs;
4623	const out_attrs = @typeInfo(@TypeOf(outSlice)).pointer.attrs;
4624
4625	try testing.expectEqual(in_attrs.@"const", out_attrs.@"const");
4626	try testing.expectEqual(in_attrs.@"volatile", out_attrs.@"volatile");
4627	try testing.expectEqual(in_attrs.@"allowzero", out_attrs.@"allowzero");
4628	try testing.expectEqual(in_attrs.@"align", out_attrs.@"align");
4629	}
4630
4631	test "bytesAsSlice with zero-bit element type" {
4632	{
4633	const bytes = [_]u8{};
4634	const slice = bytesAsSlice(void, &bytes);
4635	try testing.expectEqual(0, slice.len);
4636	}
4637	{
4638	const bytes = [_]u8{ 0x01, 0x02, 0x03, 0x04 };
4639	const slice = bytesAsSlice(u0, &bytes);
4640	try testing.expectEqual(0, slice.len);
4641	}
4642	}
4643
4644	fn SliceAsBytesReturnType(comptime Slice: type) type {
4645	return CopyPtrAttrs(Slice, .slice, u8);
4646	}
4647
4648	/// Given a slice, returns a slice of the underlying bytes, preserving pointer attributes.
4649	pub fn sliceAsBytes(slice: anytype) SliceAsBytesReturnType(@TypeOf(slice)) {
4650	const Slice = @TypeOf(slice);
4651
4652	// a slice of zero-bit values always occupies zero bytes
4653	if (@sizeOf(std.meta.Elem(Slice)) == 0) return &[0]u8{};
4654
4655	// let's not give an undefined pointer to @ptrCast
4656	// it may be equal to zero and fail a null check
4657	if (slice.len == 0 and std.meta.sentinel(Slice) == null) return &[0]u8{};
4658
4659	const cast_target = CopyPtrAttrs(Slice, .many, u8);
4660
4661	return @as(cast_target, @ptrCast(slice))[0 .. slice.len * @sizeOf(std.meta.Elem(Slice))];
4662	}
4663
4664	test sliceAsBytes {
4665	const bytes = [_]u16{ 0xDEAD, 0xBEEF };
4666	const slice = sliceAsBytes(bytes[0..]);
4667	try testing.expect(slice.len == 4);
4668	try testing.expect(eql(u8, slice, switch (native_endian) {
4669	.big => "\xDE\xAD\xBE\xEF",
4670	.little => "\xAD\xDE\xEF\xBE",
4671	}));
4672	}
4673
4674	test "sliceAsBytes with sentinel slice" {
4675	const empty_string: [:0]const u8 = "";
4676	const bytes = sliceAsBytes(empty_string);
4677	try testing.expect(bytes.len == 0);
4678	}
4679
4680	test "sliceAsBytes with zero-bit element type" {
4681	const lots_of_nothing: [10_000]void = @splat({});
4682	const bytes = sliceAsBytes(&lots_of_nothing);
4683	try testing.expect(bytes.len == 0);
4684	}
4685
4686	test "sliceAsBytes packed struct at runtime and comptime" {
4687	const Foo = packed struct {
4688	a: u4,
4689	b: u4,
4690	};
4691	const S = struct {
4692	fn doTheTest() !void {
4693	var foo: Foo = undefined;
4694	var slice = sliceAsBytes(@as(*[1]Foo, &foo)[0..1]);
4695	slice[0] = 0x13;
4696	try testing.expect(foo.a == 0x3);
4697	try testing.expect(foo.b == 0x1);
4698	}
4699	};
4700	try S.doTheTest();
4701	try comptime S.doTheTest();
4702	}
4703
4704	test "sliceAsBytes and bytesAsSlice back" {
4705	try testing.expect(@sizeOf(i32) == 4);
4706
4707	var big_thing_array = [_]i32{ 1, 2, 3, 4 };
4708	const big_thing_slice: []i32 = big_thing_array[0..];
4709
4710	const bytes = sliceAsBytes(big_thing_slice);
4711	try testing.expect(bytes.len == 4 * 4);
4712
4713	bytes[4] = 0;
4714	bytes[5] = 0;
4715	bytes[6] = 0;
4716	bytes[7] = 0;
4717	try testing.expect(big_thing_slice[1] == 0);
4718
4719	const big_thing_again = bytesAsSlice(i32, bytes);
4720	try testing.expect(big_thing_again[2] == 3);
4721
4722	big_thing_again[2] = -1;
4723	try testing.expect(bytes[8] == math.maxInt(u8));
4724	try testing.expect(bytes[9] == math.maxInt(u8));
4725	try testing.expect(bytes[10] == math.maxInt(u8));
4726	try testing.expect(bytes[11] == math.maxInt(u8));
4727	}
4728
4729	test "sliceAsBytes preserves pointer attributes" {
4730	const inArr align(16) = [2]u16{ 0xDEAD, 0xBEEF };
4731	const inSlice = @as(*align(16) const volatile [2]u16, @ptrCast(&inArr))[0..];
4732	const outSlice = sliceAsBytes(inSlice);
4733
4734	const in_attrs = @typeInfo(@TypeOf(inSlice)).pointer.attrs;
4735	const out_attrs = @typeInfo(@TypeOf(outSlice)).pointer.attrs;
4736
4737	try testing.expectEqual(in_attrs.@"const", out_attrs.@"const");
4738	try testing.expectEqual(in_attrs.@"volatile", out_attrs.@"volatile");
4739	try testing.expectEqual(in_attrs.@"allowzero", out_attrs.@"allowzero");
4740	try testing.expectEqual(in_attrs.@"align", out_attrs.@"align");
4741	}
4742
4743	/// If the provided slice is not sentinel terminated, do nothing and return that slice.
4744	/// If it is sentinel-terminated, return a non-sentinel-terminated slice with the
4745	/// length increased by one to include the absorbed sentinel element.
4746	pub fn absorbSentinel(slice: anytype) AbsorbSentinel(@TypeOf(slice)) {
4747	const info = @typeInfo(@TypeOf(slice)).pointer;
4748	switch (info.size) {
4749	.slice => {
4750	if (info.sentinel_ptr == null) {
4751	return slice;
4752	} else {
4753	return slice.ptr[0 .. slice.len + 1];
4754	}
4755	},
4756	.one => {
4757	const child_info = @typeInfo(info.child).array;
4758	if (child_info.sentinel_ptr == null) {
4759	return slice;
4760	} else {
4761	return slice[0 .. child_info.len + 1];
4762	}
4763	},
4764	else => unreachable,
4765	}
4766	}
4767
4768	test absorbSentinel {
4769	{
4770	var buffer: [3:0]u8 = .{ 1, 2, 3 };
4771	const foo: [:0]const u8 = &buffer;
4772	const bar: []const u8 = &buffer;
4773	const baz: *const [3:0]u8 = &buffer;
4774	try testing.expectEqual([]const u8, @TypeOf(absorbSentinel(foo)));
4775	try testing.expectEqual([]const u8, @TypeOf(absorbSentinel(bar)));
4776	try testing.expectEqual(*const [4]u8, @TypeOf(absorbSentinel(baz)));
4777	try testing.expectEqualSlices(u8, &.{ 1, 2, 3, 0 }, absorbSentinel(foo));
4778	try testing.expectEqualSlices(u8, &.{ 1, 2, 3 }, absorbSentinel(bar));
4779	try testing.expectEqualSlices(u8, &.{ 1, 2, 3, 0 }, absorbSentinel(baz));
4780	}
4781	{
4782	var buffer: [3:0]u8 = .{ 1, 2, 3 };
4783	const foo: [:0]u8 = &buffer;
4784	const bar: []u8 = &buffer;
4785	const baz: *[3:0]u8 = &buffer;
4786	try testing.expectEqual([]u8, @TypeOf(absorbSentinel(foo)));
4787	try testing.expectEqual([]u8, @TypeOf(absorbSentinel(bar)));
4788	try testing.expectEqual(*[4]u8, @TypeOf(absorbSentinel(baz)));
4789	var expected_foo = [_]u8{ 1, 2, 3, 0 };
4790	try testing.expectEqualSlices(u8, &expected_foo, absorbSentinel(foo));
4791	var expected_bar = [_]u8{ 1, 2, 3 };
4792	try testing.expectEqualSlices(u8, &expected_bar, absorbSentinel(bar));
4793	var expected_baz = [_]u8{ 1, 2, 3, 0 };
4794	try testing.expectEqualSlices(u8, &expected_baz, absorbSentinel(baz));
4795	}
4796	}
4797
4798	/// Round an address down to the next (or current) aligned address.
4799	/// Unlike `alignForward`, `alignment` can be any positive number, not just a power of 2.
4800	pub fn alignForwardAnyAlign(comptime T: type, addr: T, alignment: T) T {
4801	if (isValidAlignGeneric(T, alignment))
4802	return alignForward(T, addr, alignment);
4803	assert(alignment != 0);
4804	return alignBackwardAnyAlign(T, addr + (alignment - 1), alignment);
4805	}
4806
4807	/// Round an address up to the next (or current) aligned address.
4808	/// The alignment must be a power of 2 and greater than 0.
4809	/// Asserts that rounding up the address does not cause integer overflow.
4810	pub fn alignForward(comptime T: type, addr: T, alignment: T) T {
4811	assert(isValidAlignGeneric(T, alignment));
4812	return alignBackward(T, addr + (alignment - 1), alignment);
4813	}
4814
4815	/// Rounds an address up to the next alignment boundary using log2 representation.
4816	/// Equivalent to alignForward with alignment = 1 << log2_alignment.
4817	/// More efficient when alignment is known to be a power of 2.
4818	pub fn alignForwardLog2(addr: usize, log2_alignment: u8) usize {
4819	const alignment = @as(usize, 1) << @as(math.Log2Int(usize), @intCast(log2_alignment));
4820	return alignForward(usize, addr, alignment);
4821	}
4822
4823	/// Force an evaluation of the expression; this tries to prevent
4824	/// the compiler from optimizing the computation away even if the
4825	/// result eventually gets discarded.
4826	// TODO: use @declareSideEffect() when it is available - https://github.com/ziglang/zig/issues/6168
4827	pub fn doNotOptimizeAway(val: anytype) void {
4828	if (@inComptime()) return;
4829
4830	if (builtin.zig_backend == .stage2_c and builtin.abi == .msvc) {
4831	_ = @atomicRmw(*const anyopaque, @as(*volatile *const anyopaque, &struct {
4832	var escape: *const anyopaque = undefined;
4833	}.escape), .Xchg, &val, .acq_rel); // TODO: syncscope("singlethreaded")
4834	return;
4835	}
4836
4837	switch (@typeInfo(@TypeOf(val))) {
4838	.void, .null, .comptime_int, .comptime_float => return,
4839	.@"enum" => doNotOptimizeAway(@backingInt(val)),
4840	.bool => doNotOptimizeAway(@intFromBool(val)),
4841	.int => |int| {
4842	// SPIR-V targets do not have registers per se, they have values
4843	// tied to IDs that can be passed to valid instructions. Some
4844	// SPIR-V targets do not define c_long, so we just allow any sized
4845	// integer on these targets
4846	const val_fits_in_gp_register = builtin.target.cpu.arch.isSpirV() or fits: {
4847	const max_gp_register_bits = @bitSizeOf(c_long);
4848	break :fits int.bits <= max_gp_register_bits;
4849	};
4850	if (val_fits_in_gp_register) {
4851	const val2 = @as(
4852	@Int(int.signedness, @max(8, std.math.ceilPowerOfTwoAssert(u16, int.bits))),
4853	val,
4854	);
4855	asm volatile (""
4856	:
4857	: [_] "r" (val2),
4858	);
4859	} else {
4860	doNotOptimizeAway(&val);
4861	}
4862	},
4863	.float => |float| switch (float.bits) {
4864	else => comptime unreachable,
4865	16, 80, 128 => doNotOptimizeAway(&val),
4866	32, 64 => asm volatile (""
4867	:
4868	: [_] "rm" (val),
4869	),
4870	},
4871	.pointer => asm volatile (""
4872	:
4873	: [_] "m" (val),
4874	: .{ .memory = true }),
4875	.array => |array| if (array.len * @sizeOf(array.child) <= 64) {
4876	for (val) |v| doNotOptimizeAway(v);
4877	} else doNotOptimizeAway(&val),
4878	else => doNotOptimizeAway(&val),
4879	}
4880	}
4881
4882	test doNotOptimizeAway {
4883	comptime doNotOptimizeAway("test");
4884
4885	doNotOptimizeAway(null);
4886	doNotOptimizeAway(true);
4887	doNotOptimizeAway(0);
4888	doNotOptimizeAway(0.0);
4889	doNotOptimizeAway(@as(u1, 0));
4890	doNotOptimizeAway(@as(u3, 0));
4891	doNotOptimizeAway(@as(u8, 0));
4892	doNotOptimizeAway(@as(u16, 0));
4893	doNotOptimizeAway(@as(u32, 0));
4894	doNotOptimizeAway(@as(u64, 0));
4895	doNotOptimizeAway(@as(u128, 0));
4896	doNotOptimizeAway(@as(u13, 0));
4897	doNotOptimizeAway(@as(u37, 0));
4898	doNotOptimizeAway(@as(u96, 0));
4899	doNotOptimizeAway(@as(u200, 0));
4900	doNotOptimizeAway(@as(f32, 0.0));
4901	doNotOptimizeAway(@as(f64, 0.0));
4902	doNotOptimizeAway(@as([4]u8, @splat(0)));
4903	doNotOptimizeAway(@as([100]u8, @splat(0)));
4904	doNotOptimizeAway(@as(std.builtin.Endian, .little));
4905	}
4906
4907	test alignForward {
4908	try testing.expect(alignForward(usize, 1, 1) == 1);
4909	try testing.expect(alignForward(usize, 2, 1) == 2);
4910	try testing.expect(alignForward(usize, 1, 2) == 2);
4911	try testing.expect(alignForward(usize, 2, 2) == 2);
4912	try testing.expect(alignForward(usize, 3, 2) == 4);
4913	try testing.expect(alignForward(usize, 4, 2) == 4);
4914	try testing.expect(alignForward(usize, 7, 8) == 8);
4915	try testing.expect(alignForward(usize, 8, 8) == 8);
4916	try testing.expect(alignForward(usize, 9, 8) == 16);
4917	try testing.expect(alignForward(usize, 15, 8) == 16);
4918	try testing.expect(alignForward(usize, 16, 8) == 16);
4919	try testing.expect(alignForward(usize, 17, 8) == 24);
4920	}
4921
4922	/// Round an address down to the previous (or current) aligned address.
4923	/// Unlike `alignBackward`, `alignment` can be any positive number, not just a power of 2.
4924	pub fn alignBackwardAnyAlign(comptime T: type, addr: T, alignment: T) T {
4925	if (isValidAlignGeneric(T, alignment))
4926	return alignBackward(T, addr, alignment);
4927	assert(alignment != 0);
4928	return addr - @mod(addr, alignment);
4929	}
4930
4931	/// Round an address down to the previous (or current) aligned address.
4932	/// The alignment must be a power of 2 and greater than 0.
4933	pub fn alignBackward(comptime T: type, addr: T, alignment: T) T {
4934	assert(isValidAlignGeneric(T, alignment));
4935	// 000010000 // example alignment
4936	// 000001111 // subtract 1
4937	// 111110000 // binary not
4938	return addr & ~(alignment - 1);
4939	}
4940
4941	/// Returns whether `alignment` is a valid alignment, meaning it is
4942	/// a positive power of 2.
4943	pub fn isValidAlign(alignment: usize) bool {
4944	return isValidAlignGeneric(usize, alignment);
4945	}
4946
4947	/// Returns whether `alignment` is a valid alignment, meaning it is
4948	/// a positive power of 2.
4949	pub fn isValidAlignGeneric(comptime T: type, alignment: T) bool {
4950	return alignment > 0 and std.math.isPowerOfTwo(alignment);
4951	}
4952
4953	/// Returns true if i is aligned to the given alignment.
4954	/// Works with any positive alignment value, not just powers of 2.
4955	/// For power-of-2 alignments, `isAligned` is more efficient.
4956	pub fn isAlignedAnyAlign(i: usize, alignment: usize) bool {
4957	if (isValidAlign(alignment))
4958	return isAligned(i, alignment);
4959	assert(alignment != 0);
4960	return 0 == @mod(i, alignment);
4961	}
4962
4963	/// Returns true if addr is aligned to 2^log2_alignment.
4964	/// More efficient than `isAligned` when alignment is known to be a power of 2.
4965	/// log2_alignment must be < @bitSizeOf(usize).
4966	pub fn isAlignedLog2(addr: usize, log2_alignment: u8) bool {
4967	return @ctz(addr) >= log2_alignment;
4968	}
4969
4970	/// Given an address and an alignment, return true if the address is a multiple of the alignment
4971	/// The alignment must be a power of 2 and greater than 0.
4972	pub fn isAligned(addr: usize, alignment: usize) bool {
4973	return isAlignedGeneric(u64, addr, alignment);
4974	}
4975
4976	/// Generic version of `isAligned` that works with any integer type.
4977	/// Returns true if addr is aligned to the given alignment.
4978	/// Alignment must be a power of 2 and greater than 0.
4979	pub fn isAlignedGeneric(comptime T: type, addr: T, alignment: T) bool {
4980	return alignBackward(T, addr, alignment) == addr;
4981	}
4982
4983	test isAligned {
4984	try testing.expect(isAligned(0, 4));
4985	try testing.expect(isAligned(1, 1));
4986	try testing.expect(isAligned(2, 1));
4987	try testing.expect(isAligned(2, 2));
4988	try testing.expect(!isAligned(2, 4));
4989	try testing.expect(isAligned(3, 1));
4990	try testing.expect(!isAligned(3, 2));
4991	try testing.expect(!isAligned(3, 4));
4992	try testing.expect(isAligned(4, 4));
4993	try testing.expect(isAligned(4, 2));
4994	try testing.expect(isAligned(4, 1));
4995	try testing.expect(!isAligned(4, 8));
4996	try testing.expect(!isAligned(4, 16));
4997	}
4998
4999	test "freeing empty string with null-terminated sentinel" {
5000	const empty_string = try testing.allocator.dupeSentinel(u8, "", 0);
5001	testing.allocator.free(empty_string);
5002	}
5003
5004	/// Returns a slice with the given new alignment,
5005	/// all other pointer attributes copied from `AttributeSource`.
5006	fn AlignedSlice(comptime AttributeSource: type, comptime new_alignment: usize) type {
5007	const ptr = @typeInfo(AttributeSource).pointer;
5008	var attrs = ptr.attrs;
5009	attrs.@"align" = new_alignment;
5010	return @Pointer(.slice, attrs, ptr.child, null);
5011	}
5012
5013	/// Returns the largest slice in the given bytes that conforms to the new alignment,
5014	/// or `null` if the given bytes contain no conforming address.
5015	pub fn alignInBytes(bytes: []u8, comptime new_alignment: usize) ?[]align(new_alignment) u8 {
5016	const begin_address = @intFromPtr(bytes.ptr);
5017	const end_address = begin_address + bytes.len;
5018
5019	const begin_address_aligned = mem.alignForward(usize, begin_address, new_alignment);
5020	const new_length = std.math.sub(usize, end_address, begin_address_aligned) catch |e| switch (e) {
5021	error.Overflow => return null,
5022	};
5023	const alignment_offset = begin_address_aligned - begin_address;
5024	return @alignCast(bytes[alignment_offset .. alignment_offset + new_length]);
5025	}
5026
5027	/// Returns the largest sub-slice within the given slice that conforms to the new alignment,
5028	/// or `null` if the given slice contains no conforming address.
5029	pub fn alignInSlice(slice: anytype, comptime new_alignment: usize) ?AlignedSlice(@TypeOf(slice), new_alignment) {
5030	const bytes = sliceAsBytes(slice);
5031	const aligned_bytes = alignInBytes(bytes, new_alignment) orelse return null;
5032
5033	const Element = @TypeOf(slice[0]);
5034	const slice_length_bytes = aligned_bytes.len - (aligned_bytes.len % @sizeOf(Element));
5035	const aligned_slice = bytesAsSlice(Element, aligned_bytes[0..slice_length_bytes]);
5036	return @alignCast(aligned_slice);
5037	}
5038
5039	test "read/write(Var)PackedInt" {
5040	// This test generates too much code to execute on WASI.
5041	// LLVM backend fails with "too many locals: locals exceed maximum"
5042	if (builtin.cpu.arch.isWasm()) return error.SkipZigTest;
5043
5044	const foreign_endian: Endian = if (native_endian == .big) .little else .big;
5045	const expect = std.testing.expect;
5046	var prng = std.Random.DefaultPrng.init(1234);
5047	const random = prng.random();
5048
5049	@setEvalBranchQuota(10_000);
5050	inline for ([_]type{ u8, u16, u32, u128 }) |BackingType| {
5051	for ([_]BackingType{
5052	@as(BackingType, 0), // all zeros
5053	-%@as(BackingType, 1), // all ones
5054	random.int(BackingType), // random
5055	random.int(BackingType), // random
5056	random.int(BackingType), // random
5057	}) |init_value| {
5058	const uTs = [_]type{ u1, u3, u7, u8, u9, u10, u15, u16, u86 };
5059	const iTs = [_]type{ i1, i3, i7, i8, i9, i10, i15, i16, i86 };
5060	inline for (uTs ++ iTs) |PackedType| {
5061	if (@bitSizeOf(PackedType) > @bitSizeOf(BackingType))
5062	continue;
5063
5064	const iPackedType = @Int(.signed, @bitSizeOf(PackedType));
5065	const uPackedType = @Int(.unsigned, @bitSizeOf(PackedType));
5066	const Log2T = std.math.Log2Int(BackingType);
5067
5068	const offset_at_end = @bitSizeOf(BackingType) - @bitSizeOf(PackedType);
5069	for ([_]usize{ 0, 1, 7, 8, 9, 10, 15, 16, 86, offset_at_end }) |offset| {
5070	if (offset > offset_at_end or offset == @bitSizeOf(BackingType))
5071	continue;
5072
5073	for ([_]PackedType{
5074	~@as(PackedType, 0), // all ones: -1 iN / maxInt uN
5075	@as(PackedType, 0), // all zeros: 0 iN / 0 uN
5076	@bitCast(@as(iPackedType, math.maxInt(iPackedType))), // maxInt iN
5077	@bitCast(@as(iPackedType, math.minInt(iPackedType))), // maxInt iN
5078	random.int(PackedType), // random
5079	random.int(PackedType), // random
5080	}) |write_value| {
5081	{ // Fixed-size Read/Write (Native-endian)
5082
5083	// Initialize Value
5084	var value: BackingType = init_value;
5085
5086	// Read
5087	const read_value1 = readPackedInt(PackedType, asBytes(&value), offset, native_endian);
5088	try expect(read_value1 == @as(PackedType, @bitCast(@as(uPackedType, @truncate(value >> @as(Log2T, @intCast(offset)))))));
5089
5090	// Write
5091	writePackedInt(PackedType, asBytes(&value), offset, write_value, native_endian);
5092	try expect(write_value == @as(PackedType, @bitCast(@as(uPackedType, @truncate(value >> @as(Log2T, @intCast(offset)))))));
5093
5094	// Read again
5095	const read_value2 = readPackedInt(PackedType, asBytes(&value), offset, native_endian);
5096	try expect(read_value2 == write_value);
5097
5098	// Verify bits outside of the target integer are unmodified
5099	const diff_bits = init_value ^ value;
5100	if (offset != offset_at_end)
5101	try expect(diff_bits >> @as(Log2T, @intCast(offset + @bitSizeOf(PackedType))) == 0);
5102	if (offset != 0)
5103	try expect(diff_bits << @as(Log2T, @intCast(@bitSizeOf(BackingType) - offset)) == 0);
5104	}
5105
5106	{ // Fixed-size Read/Write (Foreign-endian)
5107
5108	// Initialize Value
5109	var value: BackingType = @byteSwap(init_value);
5110
5111	// Read
5112	const read_value1 = readPackedInt(PackedType, asBytes(&value), offset, foreign_endian);
5113	try expect(read_value1 == @as(PackedType, @bitCast(@as(uPackedType, @truncate(@byteSwap(value) >> @as(Log2T, @intCast(offset)))))));
5114
5115	// Write
5116	writePackedInt(PackedType, asBytes(&value), offset, write_value, foreign_endian);
5117	try expect(write_value == @as(PackedType, @bitCast(@as(uPackedType, @truncate(@byteSwap(value) >> @as(Log2T, @intCast(offset)))))));
5118
5119	// Read again
5120	const read_value2 = readPackedInt(PackedType, asBytes(&value), offset, foreign_endian);
5121	try expect(read_value2 == write_value);
5122
5123	// Verify bits outside of the target integer are unmodified
5124	const diff_bits = init_value ^ @byteSwap(value);
5125	if (offset != offset_at_end)
5126	try expect(diff_bits >> @as(Log2T, @intCast(offset + @bitSizeOf(PackedType))) == 0);
5127	if (offset != 0)
5128	try expect(diff_bits << @as(Log2T, @intCast(@bitSizeOf(BackingType) - offset)) == 0);
5129	}
5130
5131	const signedness = @typeInfo(PackedType).int.signedness;
5132	const NextPowerOfTwoInt = @Int(signedness, try std.math.ceilPowerOfTwo(u16, @bitSizeOf(PackedType)));
5133	const ui64 = @Int(signedness, 64);
5134	inline for ([_]type{ PackedType, NextPowerOfTwoInt, ui64 }) |U| {
5135	{ // Variable-size Read/Write (Native-endian)
5136
5137	if (@bitSizeOf(U) < @bitSizeOf(PackedType))
5138	continue;
5139
5140	// Initialize Value
5141	var value: BackingType = init_value;
5142
5143	// Read
5144	const read_value1 = readVarPackedInt(U, asBytes(&value), offset, @bitSizeOf(PackedType), native_endian, signedness);
5145	try expect(read_value1 == @as(PackedType, @bitCast(@as(uPackedType, @truncate(value >> @as(Log2T, @intCast(offset)))))));
5146
5147	// Write
5148	writeVarPackedInt(asBytes(&value), offset, @bitSizeOf(PackedType), @as(U, write_value), native_endian);
5149	try expect(write_value == @as(PackedType, @bitCast(@as(uPackedType, @truncate(value >> @as(Log2T, @intCast(offset)))))));
5150
5151	// Read again
5152	const read_value2 = readVarPackedInt(U, asBytes(&value), offset, @bitSizeOf(PackedType), native_endian, signedness);
5153	try expect(read_value2 == write_value);
5154
5155	// Verify bits outside of the target integer are unmodified
5156	const diff_bits = init_value ^ value;
5157	if (offset != offset_at_end)
5158	try expect(diff_bits >> @as(Log2T, @intCast(offset + @bitSizeOf(PackedType))) == 0);
5159	if (offset != 0)
5160	try expect(diff_bits << @as(Log2T, @intCast(@bitSizeOf(BackingType) - offset)) == 0);
5161	}
5162
5163	{ // Variable-size Read/Write (Foreign-endian)
5164
5165	if (@bitSizeOf(U) < @bitSizeOf(PackedType))
5166	continue;
5167
5168	// Initialize Value
5169	var value: BackingType = @byteSwap(init_value);
5170
5171	// Read
5172	const read_value1 = readVarPackedInt(U, asBytes(&value), offset, @bitSizeOf(PackedType), foreign_endian, signedness);
5173	try expect(read_value1 == @as(PackedType, @bitCast(@as(uPackedType, @truncate(@byteSwap(value) >> @as(Log2T, @intCast(offset)))))));
5174
5175	// Write
5176	writeVarPackedInt(asBytes(&value), offset, @bitSizeOf(PackedType), @as(U, write_value), foreign_endian);
5177	try expect(write_value == @as(PackedType, @bitCast(@as(uPackedType, @truncate(@byteSwap(value) >> @as(Log2T, @intCast(offset)))))));
5178
5179	// Read again
5180	const read_value2 = readVarPackedInt(U, asBytes(&value), offset, @bitSizeOf(PackedType), foreign_endian, signedness);
5181	try expect(read_value2 == write_value);
5182
5183	// Verify bits outside of the target integer are unmodified
5184	const diff_bits = init_value ^ @byteSwap(value);
5185	if (offset != offset_at_end)
5186	try expect(diff_bits >> @as(Log2T, @intCast(offset + @bitSizeOf(PackedType))) == 0);
5187	if (offset != 0)
5188	try expect(diff_bits << @as(Log2T, @intCast(@bitSizeOf(BackingType) - offset)) == 0);
5189	}
5190	}
5191	}
5192	}
5193	}
5194	}
5195	}
5196	}
5197
5198	pub const PrintError = error{
5199	/// As much as possible was written to the buffer, but it was too small to
5200	/// fit all the printed bytes.
5201	NoSpaceLeft,
5202	};
5203
5204	/// Render a formatted string into `buffer`. Returns a slice of `buffer`
5205	/// starting at index 0 containing the result, or `error.NoSpaceLeft` if one or
5206	/// more bytes were truncated.
5207	///
5208	/// See `std.Io.Writer.print`.
5209	pub fn print(buffer: []u8, comptime format: []const u8, args: anytype) PrintError![]u8 {
5210	var w: std.Io.Writer = .fixed(buffer);
5211	w.print(format, args) catch |err| switch (err) {
5212	error.WriteFailed => return error.NoSpaceLeft,
5213	};
5214	return w.buffered();
5215	}
5216
5217	test print {
5218	const x: i32 = -1;
5219	const y: []const u8 = "hi";
5220	var buffer: [64]u8 = undefined;
5221	const s = try print(&buffer, "{d}={s}", .{ x, y });
5222	try testing.expectEqualStrings("-1=hi", s);
5223	}
5224
5225	/// Like `print` but returned slice has the provided sentinel.
5226	pub fn printSentinel(
5227	buffer: []u8,
5228	comptime format: []const u8,
5229	args: anytype,
5230	comptime sentinel: u8,
5231	) PrintError![:sentinel]u8 {
5232	const result = try print(buffer, format ++ [1]u8{sentinel}, args);
5233	return result[0 .. result.len - 1 :sentinel];
5234	}
5235
5236	test printSentinel {
5237	const x: i32 = -1;
5238	const y: []const u8 = "hi";
5239	var buffer: [64]u8 = undefined;
5240	const s = try printSentinel(&buffer, "{d}={s}", .{ x, y }, 0);
5241	try testing.expectEqualStrings("-1=hi", s);
5242	try testing.expectEqual(0, s[s.len]);
5243	}