split

func NewAllocator ¶

func NewAllocator[W any](mapping descriptor.RegisterMap[W]) Allocator[W]

NewAllocator converts a mapping into a full allocator simply by wrapping the two fields.

func Addition ¶

func Addition[W word.Word[W]](mapping LimbsMap[W], alloc Allocator[W], insn *bytecode.Arith[W],
) []Bytecode[W]

Addition splits an add instruction into one (or more) add instructions, potentially introducing one (or more) carry lines at the same time. For example, consider splitting this instruction (where both x and y are u16):

> x = y + 1

Suppose now that x (resp. y) is split into two u8 registers, x1 and x0 (resp. y1 and y0). Then, we end up with the following instructions:

> c::x0 = y0 + 1 > x1 = y1 + c

Where c is a newly introduced (u1) carry line.

func Bitwise ¶

func Bitwise[W word.Word[W]](mapping descriptor.LimbsMap[W], alloc Allocator[W], insn *bytecode.Bitwise[W],
) []Bytecode[W]

Bitwise splits a bitwise AND, OR or XOR instruction into one (or more) bitwise instructions of the same kind. Unlike for e.g. addition, this does not require adding any carry lines. For example, consider splitting this instruction (where all registers are u16):

> x = y & z

Suppose now that x, y and z are split into u8 registers (i.e. x=x1::x0, etc). Then, we end up with the following instructions:

> x0 = y0 & z0 > x1 = y1 & z1

The same limb-wise decomposition applies to OR and XOR. Thus, we can see that splitting bitwise operations is relatively straightforward.

func Concat ¶

func Concat[W word.Word[W]](mapping descriptor.LimbsMap[W], alloc Allocator[W],
	insn *bytecode.Cat[W]) []Bytecode[W]

Concat splits a concatenation instruction into one (or more) instructions, potentially introducing one (or more) carry lines at the same time. For example, consider splitting this function:

fn (y,z:u16) -> (x:32) {
  x = y::z
}

Splitting into (max) u8 registers gives the following (assuming a bandwidth of u16):

fn (y1,y0,z1,z0:u8) -> (x3,x2,x1,x0:u8) {
  x1::x0 = z1::z0
  x3::x2 = y1::y0
}

In this case, no carry lines were required. But, now consider the follwing (more complex) example:

fn (y:u12,z:u20) -> (x:32) {
  x = y::z
}

Again, splitting into (max) u8 registers gives the following (again, assuming a bandwidth of u16):

fn (y1:u4,y0:u8, z2:u4,z1,z0:u8) -> (x3,x2,x1,x0:u8) {
  var c0,c1:u4
  c0::x0 = y1::y0
  c1::x1 = z0::c0
  x3::x2 = z1::c1
}

Here, we can see that two carry registers, c0 and c1 have been introduced.

func DivRem ¶

func DivRem[W word.Word[W]](mapping descriptor.LimbsMap[W], insn *bytecode.DivRem[W]) []Bytecode[W]

DivRem splits a DIV or REM instruction into a single WIDE_DIV / WIDE_REM intrinsic operating over the limb vectors of its operands. Like a shift (see Shift), a division cannot be decomposed into independent per-limb operations because carries and borrows cross limb boundaries. Instead the (possibly multi-limb) dividend, divisor and result are handed to the corresponding wide intrinsic, whose executor reconstructs each value via big.Int arithmetic (see loadIntrinsicOperand / storeIntrinsicResult). For example, splitting

> x = y / z (all u16)

into u8 limbs (x=x1::x0, etc.) yields

> x1;x0 = wide_div(y1;y0, z1;z0)

where each operand is the limb vector of the original register (ordered most-significant limb first, matching ApplyLimbsMap).

func Multiplication ¶

func Multiplication[W word.Word[W]](mapping descriptor.LimbsMap[W], alloc Allocator[W], insn *bytecode.Arith[W],
) []Bytecode[W]

Multiplication splits a multiplication instruction "target = k · s0 · … · sn" into a sequence of narrow multiply/add instructions which are field-agnostic (every register is at most RegisterWidth bits) and bandwidth-safe (every emitted multiply and addition fits within the field bandwidth on its own). It does NOT rely on any downstream constraint-level splitting.

The approach is schoolbook long multiplication over "sub-limbs":

1. A multiply granularity g is chosen (see mulGranularity) such that a partial product of two g-bit values fits the field bandwidth. Each operand — and the constant — is decomposed (least-significant first) into g-bit sub-limbs.
2. For a binary product a·b, every partial product aᵢ·bⱼ is materialised into fresh sub-limb registers via a narrow MulVecConst and bucketed against its column weight (i+j, plus the sub-limb offset within the product). The constant k is decomposed into g-bit sub-limbs and folded in via an initial scalar pass; n-ary products are reduced to a left-fold of binary products. Each fold keeps the full product width, since the multiply is overflow-checked rather than truncating.
3. Each column is a multi-operand addition, lowered by reusing the carry machinery of Addition (insertAddCarryLines / addAssignment): a carry from column c always has weight c+1, so it threads into the next column.
4. The full product is finally laid into the target's RegisterWidth limbs. Bits that lie beyond the target width are accumulated into zero-width columns, which forces them to be zero: exactly the overflow check the unsplit multiply performs (a product that does not fit the target makes the constraints unsatisfiable / aborts execution).

func Shift ¶

func Shift[W word.Word[W]](mapping descriptor.LimbsMap[W], insn *bytecode.Bitwise[W]) []Bytecode[W]

Shift splits a bitwise SHL or SHR instruction into a single WIDE_SHL / WIDE_SHR intrinsic operating over the limb vectors of its operands. Unlike AND, OR and XOR — which are bit-position-aligned and therefore split limb-wise (see Bitwise) — a shift moves bits across limb boundaries and so cannot be decomposed into independent per-limb shifts. Instead the (possibly multi-limb) value, shift amount and result are handed to the corresponding wide intrinsic, whose executor reconstructs each value via big.Int arithmetic (see loadIntrinsicOperand / storeIntrinsicResult). For example, splitting

> x = y << z (all u16)

into u8 limbs (x=x1::x0, etc.) yields

> x1;x0 = wide_shl(y1;y0, z1;z0)

where each operand is the limb vector of the original register (ordered most-significant limb first, matching ApplyLimbsMap).

func Subtraction ¶

func Subtraction[W word.Word[W]](mapping descriptor.LimbsMap[W], alloc Allocator[W], insn *bytecode.Arith[W],
) []Bytecode[W]

Subtraction splits a subtraction instruction into one (or more) subtraction instructions, potentially introducing one (or more) borrow lines at the same time. For example, consider splitting this instruction (where both x and y are u16):

> x = y - 1

Suppose now that x (resp. y) is split into two u8 registers, x1 and x0 (resp. y1 and y0). Then, we end up with the following instructions:

> b::x0 = y0 - 1 > x1 = y1 - b

Where b is a newly introduced (u1) borrow line. The mechanism is identical to that of Addition: when a chunk's right-hand side produces more bits than its left-hand side can hold, a borrow register is allocated and spliced into the current chunk's LHS and the next chunk's RHS.

func Switch ¶

func Switch[W word.Word[W]](mapping descriptor.LimbsMap[W], insn *bytecode.Switch[W],
) []Bytecode[W]

Switch splits a switch instruction.

func ApplyLimbsMap ¶

func ApplyLimbsMap[W any](limbsMap descriptor.LimbsMap[W], rids ...RegisterId) []RegisterId

ApplyLimbsMap maps a set of (bytecode) registers onto their corresponding limb registers. Observe that this splits the limbs in "declaration order" (also known as "big endian" ordering). For example, consider this declaration:

> fn f(x:u32, y:u32) -> (r:u32) { ... }

After splitting registers into u16 limbs, we have this:

> fn f(x'1:u16,x'0:u16, y'1:u16,y'0:u16) -> (r'1:u16,r'0:u16) { ... }

Observe that x'1 is the most significant limb of x, etc. Thus, given the array "[x,y,r]", this function returns "[x'1,x'0,y'1,y'0,r'1,r'0]"