bits vs bytes: a complete specification of the memory model

[andrewrk]

This proposal makes a distinction between the in-memory storage of a value and the storage of a value according to information theory.

In some cases, these are the same thing, such as with a u8 type. In other cases they can be different for various reasons, such as endianness or aggregate padding.

The idea here is that these two operations would both be well-defined, but would produce different results; they would not be defined in terms of each other:

byte casting:

fn byteCast(a: u32) f32 {
    return @ptrCast(*f32, &a).*;
}

bit casting:

fn bitCast(a: u32) f32 {
    return @bitCast(f32, a);
}

Byte casting is done via pointer reinterpretation, or via extern union field aliasing. Bit casting is done via the @bitCast language primitive. They are both well defined but distinct:

• byte casting - reinterprets memory that is stored in contiguous bytes from one type to another. This is affected by padding and endianness.
• bit casting - reinterprets bits according to information theory. Regardless of padding, alignment, or endianness, if the number of bits it takes to represent a type matches another, the value can be bitcasted from one to the other.

Byte casting is easy to understand; you can almost implement it by accident. Here we focus on bit casting and what it means. First, some prerequisites:

• @bitSizeOf vs @sizeOf - sizeof corresponds to bytes. It takes into account padding. As an example, @sizeOf(u24) == 4. Meanwhile, @bitSizeOf corresponds to information theory. In this example, @bitSizeOf(u24) == 24. bit size ignores padding. The bit size of a struct, regardless of whether it is packed or extern or not, is the sum of @bitSizeOf for each field.
• @bitOffsetOf vs @byteOffsetOf - for bytes it points to the difference in memory address between a field and the base pointer. For bits it tells the number of lower bits that precede the field in a hypothetical integer with bits equal to the @bitSizeOf the aggregate.

With this proposal, each type, regardless of whether it has a well-defined memory layout or not (which applies to bytes), it has a hypothetical integer with a number of bits equal to the @bitSizeOf that type. We call this integer the type's fundamental int. @bitCast is defined as follows:

1. convert from the source type to the its fundamental int.
2. convert from the fundamental int to the destination type.

Attempting to @bitCast between two types that have differing @bitSizeOf values is a compile error. Note that one can obtain the fundamental int for a type by bit casting the value to an unsigned integer.

The motivation for this proposal is:

• To complete the specification of how these bit related functions work.
• To make composing packed structs useful and making align(0) useful in general.
• To make it possible to optimize things such as ??u8, whose fundamental integer would be a u10.
• To have the protection of a type system but also allow Data-Oriented-Design tricks, storing information in compact ways.

With this proposal, one would be able to convert between structs, even though they have no well-defined byte representation, like this:

const std = @import("std");
const expect = std.testing.expect;

const S = struct {
    name: []const u8,
    ok: ?bool,
};

const Other = struct {
    name_ptr: [*]const u8,
    name_len: usize,
    ok_present: u1,
    ok_flag: u1,
};

test "example" {
    var s = S{
        .name = "hello",
        .ok = true,
    };
    var other = @bitCast(Other, s);

    try expect(std.mem.eql(u8, other.name_ptr[0..other.name_len], "hello"));
    try expect(other.ok_present == 1);
    try expect(other.ok_flag == 1);
}

[Hejsil]

So even if the in memory layout is not defined, the fundamental int "layout" for that type is and the "layout" for that fundamental int depends on the field order it seems, which is why S -> Other works.

[Hejsil]

Also, then builtin types (such as slices and optionals) need to have their fundamental int layout be defined even if its memory layout is not.

[Hejsil]

Just writing down what @bitCast would do to convert S -> Other just to validate that I understand:

// Assuming 64bit platform
var s: S = ...;
const Int = meta.Int(@bitSizeOf(S), .unsigned);
var int: Int = 0;
int |= @as(Int, @bitCast(u128, s.name)) << @bitOffsetOf(S, "name");
int |= @as(Int, @bitCast(u2, s.ok)) << @bitOffsetOf(S, "ok");

var o: Other = undefined;
o.name_ptr = @bitCast([*]const u8, @truncate(u64, int >> @bitOffsetOf(Other, "name_ptr")));
o.name_len = @bitCast(usize, @truncate(u64, int >> @bitOffsetOf(Other, "name_len")));
o.ok_present = @bitCast(u1, @truncate(u1, int >> @bitOffsetOf(Other, "ok_present")));
o.ok_flag = @bitCast(u1, @truncate(u1, int >> @bitOffsetOf(Other, "ok_flag")));

[Hejsil]

Also, seems @bitCast can no longer return an L value with these semantics. And if that is the case, why not just implement this in the standard library instead of the compiler?

Edit: And to implement this in the standard library, all you really need is @bitSizeOf. Everything else can be implemented from this.

Edit edit: Actually, no. This is not so easy to do in standard library when untagged unions with safety checks are a thing.

[Hejsil]

One thing. How would this work with untagged unions?

const U = union{
    a: u8,
    b: u16,
};

var u = U{.a= 0};
// There are some memory in this union which was not "set" and is probably `undefined`.
// Doing the bitcast here, we now have multiple integer representations that represents the same U{.a = 0}
// information.
var i = @bitCast(u16, u); // i is 0b00000000????????

[ifreund]

One thing. How would this work with untagged unions?

Related:

zig/src/Module.zig

Lines 2600 to 2606 in d66c97d

	// TODO This is taking advantage of matching stage1 debug union layout.
	// We need a better language feature for initializing a union with
	// a runtime known tag.
	const Stage1DataLayout = extern struct {
	data: [8]u8 align(@alignOf(Zir.Inst.Data)),
	safety_tag: u8,
	};

I feel like a solution to one of these questions may solve the other as well. At the very least having both in mind while thinking about solutions would likely be useful.

In particular, what are the semantics of this:

const U = union {
    a: u3,
    b: u5,
};

// What is the debug safety tag of u set to?
// Should we have an "unknown" safety tag which disables safety checks until the union
// is assigned in a way that the compiler knows the intended tag?
var u = @bitCast(U, 0b11111);
// e.g. we could now set the safety tag to `a` here:
u = .{ .a = 0b111 };

[SpexGuy]

I really don't like this. It seems like a fairly complex transformation (no new programmer would ever guess that this is what bitcast does), and I don't see motivating use cases for that complexity. Let's examine the motivations in the issue:

• To complete the specification of how these bit related functions work.

That's good motivation but doesn't explain the complexity

• To make composing packed structs useful and making align(0) useful in general.

The proposal doesn't really talk about composing at all, I'm finding it very difficult to see how this is relevant. Since we're not defining anything related to memory layout (this proposal only specifies a transformation done by bitcast, despite claiming to have something to do with a memory model), it's not really related to align(0) or the representation of nested packed structs. I'd like to see some real use cases for the proposed transformation, because I'm having difficulty coming up with any that would be a good idea in real code.

• To make it possible to optimize things such as ??u8, whose fundamental integer would be a u10.

This proposal does nothing to make this possible. You can still take the address of the inner ?u8 or u8 and this proposal did not redefine the meaning of padding in pointer reads/writes. So even if bitcast does this crazy set of steps, we can't make this optimization.

• To have the protection of a type system but also allow Data-Oriented-Design tricks, storing information in compact ways.

The proposed transform is quite inefficient on most hardware. It can't undergo a SIMD transformation. It's true that computers are faster at doing math / unpacking operations than loading memory, but the more operations they spend unpacking the fewer they can spend doing math. I really need to see more use cases but I'm currently unconvinced that the benefits of this are worth the cost in complexity.

[andrewrk]

Closed in order to simplify the language. @bitCast is to be defined in terms of @ptrCast:

fn bitCast(Dest: type, x: anytype) Dest {
    return @ptrCast(*Dest, &x).*;
}

@bitSizeOf - defined like this:

fn bitSizeOf(T: type) comptime_int {
    const P = packed struct { t: T };
    return @TypeInfo(@structToInt(P)).Int.bits;
}

Most types are not allowed in packed structs. Only ones allowed are integer-like types:

• integers
• enums
• bool
• packed structs

Anything other than these gives a compile error if used with @bitSizeOf.

@bitOffsetOf - only works for packed structs. Counts starting from 0 as the least significant bit. Counts the number of bits from the base pointer of the packed struct.

---

Answers to some specific questions:

• what is the @sizeOf(u24) ?
  • probably 4 but target specific. always >= 3.
    • On an 8-bit CPU it would be size 3, align 1.
    • On a 16-bit CPU it would be size 4, align 2.
    • On 32-bit CPUs and higher, it would be size 4, align 4.
  • in general size of integers is increasing powers of 2 bytes until we hit max integer alignment, then it goes up in increments of alignment bytes.
  • max integer alignment is given by the alignment desired for the largest mov instruction that supports moving integers. Note that on x86_64 movaps supports 16 byte integers, so max int align for x86_64 is 16.
• what is the size and alignment of packed struct {a: u8, b: u8, c: u8}?
  • always size 3, align 1. inferred backing integer is u24 but without being explicitly specified it has alignment 1, no padding, as if it were [3]u8 rather than an integer.
  • if we make it packed(u24) struct {a: u8, b: u8, c: u8} then it becomes exactly the same align and size as u24

[igor84]

I found this issue after already giving this a lot of thought so I decided to share my view on it.

The way I see it alignment of some type is not defined by that type but by its container. If we take u24 as an example I expect @sizeOf(24) to always be 3. If I define a local variable (on stack) it may take 4 or 8 bytes of space as I expect stack has some default alignment requirement. If I want to allocate one on the heap I expect it to take 3 bytes (arrays are covered later). If I put it in a struct it can take as much additional bytes as it needs to fulfill the alignment requirements of that struct. So if I put it in packed struct (which I understand as struct which requires alignment on 1 byte) I expect it to take 3 bytes and if I put it in struct with align(8) I expect it to take up 8 bytes.

Zig is currently not consistent on this front:

const T1 = packed struct { f1: u24 }; // @sizeOf(T1) == 4
const T2 = packed struct {f1: u24, f2: u8}; // @sizeOf(T2) == 4

This means that u24 field in T1 took 4 bytes but in T2 struct didn't. Also I would expect T2 to work like that while I wouldn't expect T1 to be 4 bytes.

Next problem are arrays. To keep this logic, they as containers also now need to define alignment so we can have "normal" u24 arrays that actually add padding of 1 byte and packed arrays that actually store u24s right next to each other. There is even practical example where this is useful since some image formats store colors as RGBRGBRGB...

I would really like to understand this problem fully now that I am so deeply in it so I am eager to here what am I missing. Why can't we have this?

[SpexGuy]

The critical problem is that sizeof is, by definition, array stride. If we didn't include padding in sizeof, we would need a separate built-in for array stride. Additionally, since alignment is an attribute of the container, not the type, alignment cannot affect layout (and therefore cannot affect size).

[igor84]

I just don't see how can we support u24, packed structs that make sense and not have built-in for array stride and alignment for arrays as well. For example currently the following is true:
@sizeOf(packed struct { f1: u24, f2: u8 }) == 4 while
@sizeOf(packed struct { f1: u8, f2: u24 }) == 5.
How can we make std.io.reader.readStruct() work correctly with both and not cause error.EndOfStream in second case?

If I understand your logic the above is not considered a bug and will remain so in the future (also the test at test/behavior/struct.zig on line 431 confirms it is valid expectation).

[SpexGuy]

The current (stage 1) implementation of packed on which you are basing your arguments is not the correct behavior. packed struct { u8, u24 } will be four bytes align(1) and packed struct { u24 } will be 3 align(1). However packed (u24) struct { ... } will be the size and alignment of u24, probably size 4 align(4). In general alignment only takes sense when talking about whole values. Fields of packed structs do not have a meaningful alignment, and their size in the packed struct is determined by @bitSizeOf, not @sizeOf.

[igor84]

So if someone (like me :) ) would manage to fix packed structs in stage1 they would be right to change the test/behavior/struct.zig like it is done here: https://github.com/ziglang/zig/pull/3745/files#diff-2543d9651c81667654ce214fd04ab490787f15ed52623cfe29339c98cc482426L256 ?

[SpexGuy]

Yep, that would be needed. Though those tests are run by both stage 1 and stage 2, so you would need to either split the tests or fix both. The current implementation in stage 2 rounds up to a multiple of a machine word size, instead of taking the minimum number of bytes needed.

[igor84]

That test starts with these lines so I guess it should be fine to also just add .stage2_llvm, .stage2_x86 and stage2_riscv64.

if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest;
if (builtin.zig_backend == .stage2_wasm) return error.SkipZigTest; // TODO
if (builtin.zig_backend == .stage2_c) return error.SkipZigTest; // TODO
if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest; // TODO
if (builtin.zig_backend == .stage2_x86_64) return error.SkipZigTest; // TODO
if (builtin.cpu.arch == .wasm32) return error.SkipZigTest; // TODO

[SpexGuy]

Probably best to keep the current tests for stage 2 targets that work, since there are no other packed struct tests for stage 2.