Topic — Bits and wide integers

Needs: Lesson 2 — Values, control flow and functions.

Hashes, ciphers and integer random-number generators work on bit patterns: they shift, rotate, mask and add with a carry. Tungsten's integers are 16 and 32 bits wide, and its shifts and operator precedence differ from C in ways that change such code silently. This topic runs two algorithms of this kind on one PE: the Keccak-f[400] permutation, on 16-bit lanes, and the xorshift128+ generator, on 64-bit words held in 16-bit pieces. A few extra statements show, in the program's own output, each rule that differs from C.

What you will be able to do

• Write logical and arithmetic shifts and rotations of 16-bit values, and know when a shift the compiler folds gives a different answer from the same shift at run time.
• Parenthesize mixed &, | and ^ expressions correctly.
• Hold a 64-bit value in four 16-bit limbs, and shift and add it with a carry.
• Widen a 16-bit value to 32 bits without sign extension.

The program

One PE, no colors. bits.w imports two modules and runs three parts in order:

          ┌──────────────────────────── one PE ─────────────────────────────┐
 A[25] ──>│ 20 rounds of keccak_round(A, RC[i])          ──> A[25]          │
          │ STEPS steps of xorshift128p(x0, x1, out)     ──> x0, x1, out    │
          │ shifts, precedence and casts on v[4]         ──> tr[7], w[2]    │
          └─────────────────────────────────────────────────────────────────┘

A comes from the image: init.py pads a short message to one 36-byte block and writes the 25 words of the state that absorbing it gives. check.py compares A after 20 rounds with a Python Keccak-f[400], the generator's state and last output with a Python xorshift128+ on 64-bit integers, and tr and w with the values written in the script.

Keccak-f[400] belongs to the same family as the Keccak-f[1600] permutation of SHA-3, but its lanes are 16 bits wide instead of 64, so one lane fits one xp. This program computes the permutation only; it is not a SHA-3 hash.

The code

Shifts and rotations

B[10] <- (A[1] << 1)  | (A[1] >> 15);
B[20] <- (A[2] << 14) | (A[2] >> 2);

Tungsten's >> is a logical shift: it fills with zeros, even on the signed xp. That is what a rotation needs. (x << r) | (x >> (16 - r)) moves the bits that leave the top back in at the bottom. Each rotation is two shift instructions and an or:

	sll16 R7 = R6, 0x000e;  //@../keccak.w:37[keccak_round] < @../bits.w:20
	slr16 R8 = R6, 0x0002;  //@../keccak.w:37[keccak_round] < @../bits.w:20
	or16 R9 = R7, R8;  //@../keccak.w:37[keccak_round] < @../bits.w:20

C's arithmetic shift of a signed value, which copies the sign bit, is x>> in Tungsten. The last part of bits.w shows both, and three more rules:

xp v[n=4] = {-8, 1, 16, 3};

tr[0] = v[0] >> 1;
tr[1] = v[0] x>> 1;
tr[2] = -8 >> 1;
tr[3] = v[1] << v[2];
tr[4] = 1 << 16;
tr[5] = v[1] | v[3] & 0;
tr[6] = v[1] | (v[3] & 0);

Element	Expression	Result	C gives	Why
tr[0]	v[0] >> 1, v[0] = -8	32764	-4	>> is logical
tr[1]	v[0] x>> 1	-4	-4	x>> is arithmetic
tr[2]	-8 >> 1	-4	-4	the compiler folds a shift of literals, and gets -4
tr[3]	v[1] << v[2], a count of 16	1	0	a run-time count uses its low 4 bits: 16 acts as 0
tr[4]	1 << 16	0	0	the folded shift of literals is exact
tr[5]	v[1] | v[3] & 0	0	1	&, | and ^ share one level, left to right
tr[6]	v[1] | (v[3] & 0)	1	1	parentheses give C's grouping

tr[0] and tr[2] are the same shift of the same value, and they differ. A shift whose operands are all literals or kernel parameters (xp param) is computed by the compiler, and its result does not follow the run-time rule. A variable, even one set from a literal, follows the run-time rule. The listing shows the two run-time shifts and the folded constant:

	slr16 R1 = R3, 0x0001;  //@../bits.w:29
	sar16 R1 = R3, 0x0001;  //@../bits.w:30
	imov16 R2 = 0xfffc;  //@../bits.w:31

Rotations by a constant are safe: their counts are 1 to 15. A rotation by a run-time count r would compute x >> (16 - r), which for r = 0 is x >> 16, that is x >> 0. That still gives x, but only by luck: write shifts by run-time counts so the count stays in 0 to 15.

The operator precedence puts &, | and ^ on one level. Keccak's χ step is A ^ (~B & C); written without the parentheses, it would be (A ^ ~B) & C. keccak.w parenthesizes every mix.

One Keccak-f[400] round

keccak.w holds the round as a function, keccak_round(xp A[25], xp rc), and the 20 round constants as an array RC. Arrays are passed by reference (lesson 2), so the round updates A in place. Each round has five steps on the 5 × 5 state A[y*5+x]:

Step	What it does	Operators
θ	XORs each lane with the parities of two neighbouring columns	^, a rotation by 1
ρ	rotates each lane by a fixed amount	rotations
π	moves each lane to a new position	assignment
χ	mixes each row non-linearly	^, ~, &
ι	XORs the round constant into lane 0	^

ρ and π are written out in full, with constant rotation counts and positions. The kernel runs the rounds in a loop:

i in [0, 20) {
    keccak_round(A, RC[i]);
}

64-bit words in 16-bit limbs

xorshift128+ keeps two 64-bit words, x0 and x1. One step is:

t = x0; s = x1; x0 = s
t ^= t << 23
t ^= t >> 18
t ^= s ^ (s >> 5)
x1 = t
output = t + s  (mod 2**64)

The shifts 23, 18 and 5 are one of the published sets for xorshift128+. A generator with another set gives a different sequence, so compare the shifts before you compare outputs with another implementation. bits.w starts x0 and x1 from fixed values, and at least one of the two words must be nonzero: an all-zero state stays zero, and every output is 0. xorshift128p does not check its state.

xorshift.w holds each word as four xp limbs, low limb first. A shift by 23 is a shift by one whole limb (16 bits) and then by 7 bits; each new limb takes bits from two old ones:

// r = t << 23: one whole limb, then 7 bits
function shl23(xp t[4], xp r[4]) {
    r[0] = 0;
    r[1] = t[0] << 7;
    r[2] = (t[1] << 7) | (t[0] >> 9);
    r[3] = (t[2] << 7) | (t[1] >> 9);
}

The shifts right by 18 and by 5 follow the same pattern. They rely on >> being logical: an arithmetic shift would fill the top bits of a limb with copies of its sign bit, and the | with the next limb's bits would keep those ones.

The 64-bit add carries from one limb into the next:

// s = a + b modulo 2**64
function add_limbs(xp a[4], xp b[4], xp s[4]) {
    u32 c = 0;
    ∀j in [0, 4) {
        u32 w = (u32)(u16)a[j] + (u32)(u16)b[j] + c;
        s[j] = (xp)w;
        c = w >> 16;
    }
}

Each limb sum is formed in 32 bits, so the carry lands in bit 16. (xp)w keeps the low 16 bits, and w >> 16 is the carry. The body runs once per j, in order, so c reaches the next limb.

The (u16) step matters. (u32) of an xp sign-extends: a limb with its top bit set becomes 0xffff in the upper half. (u16) first makes the value unsigned, and (u32) of a u16 fills with zeros. The program shows both:

w[0] = ((u32)v[1] << 16) | (u32)v[0];
w[1] = ((u32)(u16)v[1] << 16) | (u32)(u16)v[0];

With v[1] = 1 and v[0] = -8, w[0] is 0xfffffff8, and w[1] is the intended 0x0001fff8.

What the hardware does

• The PE's shift instructions work on 16-bit values: sll16 shifts left, slr16 shifts right filling zeros, and sar16 shifts right copying the sign bit. A shift count in a register uses only its low 4 bits, so it is taken modulo 16.
• and, or, xor and add exist at 16 and 32 bits. The 32-bit add is what add_limbs uses for each limb, add32.
• The PE has no 64-bit integer arithmetic. A wider value is a set of 16-bit or 32-bit pieces that the program combines itself.

The 20 rounds of Keccak-f[400] take about 7,900 cycles, about 395 per round, and one xorshift128+ step about 160 cycles.

The test

Row	Message	Steps of xorshift128+
tutorial	"abc"	1
empty	the empty message	17
keccak	"Keccak"	200

ref.py computes Keccak-f[400] with Python integers, and derives the round constants from the Keccak LFSR instead of copying the RC table. Its xorshift128+ works on whole 64-bit integers, so it checks the limb arithmetic independently.

Run it

In your copy of the tutorial (see Lesson 1):

cd tutorial/ext-numerics/bits-and-wide-integers
make TEST=tutorial
make TEST='*'

A passing row prints a line ending in PASS tutorial [ SEED=1 STEPS=1 CYCLES=20000 ARCH=sdr ], and test-tutorial/make-log contains:

A      ok
x0     ok
x1     ok
out    ok
tr     ok
w      ok
Ok!

A failing check prints MISMATCH with the device's and the model's values, and the log ends with FAIL.

After you edit a source file, run make clean before the next test.

Pitfalls

• >> on a signed value is not C's >>. At run time it shifts in zeros, even for a negative xp. For a negative value use x>>, or / by a power of two: at run time both round toward minus infinity, so v[0] x>> 1 and v[0] / 2 are both -4.
• A folded shift and a run-time shift can disagree. -8 >> 1 is -4, but the same shift of a variable that holds -8 is 32764. A count of 16 or more at run time is taken modulo 16.
• a | b & c is (a | b) & c. Parenthesize every mix of &, | and ^.
• (u32) of a negative xp fills the upper half with ones. Write (u32)(u16)x.
• Comparisons are not 0 or 1. A comparison stored as a value is -1 when true (lesson 2), so carry = (s < a) gives -1. Compute a carry in a wider type, as add_limbs does.

Exercises

1. Remove the parentheses around ~T[1] & T[2] in the first χ line of keccak.w, then run make clean and the test. A no longer matches, while x0, x1 and out still do.
2. In add_limbs, replace (u32)(u16)a[j] with (u32)a[j] and run the empty row. x0 and x1 still match, because the state update does no addition, but out does not: its third limb is off by one. A limb with its top bit set now adds 0xffff0000 to w, and the carry is wrong.
3. After lesson 8, lay the permutation out as a pipeline: one PE per round, the state passed from PE to PE along a row, as lesson 8's wavefront passes its data.

Next

Topic — Hardware random numbers seeds the PE's hardware random-number generators and checks every draw against a host model.

References

• Bitwise operators
• Operator precedence
• Casts
• Function parameters
• The Keccak team's reference