Skip to content

DECISION NEEDED: ternary packing layout is arithmetically impossible (blocks 343 of 906 corpus files) #3873

Description

@gHashTag

specs/base/types.t27 declares a packing layout that does not fit the type it
packs into. Every spec that imports it inherits the defect, and no acceptance
criterion has ever caught it because nothing in the pipeline executes the
generated code.

Evidence

pub const PACKED_BITS_PER_TRIT : u8 = 2;
pub const TRITS_PER_BYTE       : u8 = 8;
pub const PackedTrit           = u8;

8 trits x 2 bits = 16 bits, stored into a u8.

pack_trit guards with if (position >= TRITS_PER_BYTE) return 0xFF;, so
positions 4..7 pass the guard and then compute bit_pos = position * 2 = 8..14
and shift a u8 by that amount:

  position 0 -> bits 0..1   ok
  position 1 -> bits 2..3   ok
  position 2 -> bits 4..5   ok
  position 3 -> bits 6..7   ok
  position 4 -> bits 8..9   OUT OF RANGE for u8
  position 5 -> bits 10..11 OUT OF RANGE for u8
  position 6 -> bits 12..13 OUT OF RANGE for u8
  position 7 -> bits 14..15 OUT OF RANGE for u8

In Zig a shift at or beyond the operand width is illegal behaviour, so half the
address space of pack_trit/unpack_trit is unreachable-or-corrupting rather
than merely wrong.

The word sizing disagrees with itself as well:

pub const WORD_BYTES : u8 = 5;   // ceil(27/8) = 5 bytes for 27 trits

ceil(27/8) is 4, not 5 — and at 2 bits per trit, 27 trits need ceil(27/4) = 7
bytes. The comment reasons at 1 bit per trit while the code packs at 2.

Why this matters more than its size

343 of the 361 corpus files that fail to compile fail inside this one file,
because they import it. It is 38% of the whole corpus blocked on one spec.

This needs a human decision, not a bee

Three mutually exclusive resolutions, each changing the on-memory layout of
every ternary value in the project:

  1. TRITS_PER_BYTE = 4, WORD_BYTES = 7 — keep the 2-bit encoding, fix the
    capacity. Densest correct form of the current encoding.
  2. PackedTrit = u16, TRITS_PER_BYTE = 8 — keep the constant, widen the cell.
    Wastes no trits but doubles every ternary value's footprint.
  3. 5 trits/byte via base-3 arithmetic (3^5 = 243 < 256) instead of bit fields —
    denser than either, but pack_trit/unpack_trit become mul/div, not
    shift/mask, and every consumer changes.

I have deliberately not picked one. Reply with the number and I will implement it
across the corpus and re-run the oracle.

Found by

The correctness oracle added in this cycle: every spec is generated to Zig into
a mirrored tree and run under zig test. First full run: 329 pass, 575 fail to
compile, 2 fail their own tests, out of 906.

Boundary

  • specs/base/types.t27

No activity

Activity on this issue will appear here.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    needs-boundaryNo '## Boundary' section, so the Queen can reserve nothing for it and no bee can take it

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions