Re: [Buildroot] [PATCH v3] package/urandom-scripts: actually credit seed files via seedrng

[David Laight <David.Laight@ACULAB.COM>]

From: Arnout Vandecappelle
> Sent: 02 April 2022 18:09
...
> > Busybox tends to care about code size.
> 
>   Yes, but if it's not overly bloated, it's not going to be blocker for initial
> inclusion.
> 
> > You really want to roll-up the unrolled loop in blakes2.
> > Performance really doesn't matter here.
> 
>   AFAIU (but neither the commit message nor the seedrng about page explain it)
> the Blake2 algorithm was simply chosen because it's small. Any hash function
> should be fine. There's sha1, sha2 and sha3 in libbb, so I guess one of them
> should have all the desired properties.

The unrolled blakes2 is typically 5kb of object code.
The unrolled code is better for large buffers,
but just fetching the code to the I-cache will
significantly affect performance for small buffers.
I really ought to sit and measure the cutoff.

The code is:
+#define G(r, i, a, b, c, d) do { \
+	a += b + m[blake2s_sigma[r][2 * i + 0]]; \
+	d = ror32(d ^ a, 16); \
+	c += d; \
+	b = ror32(b ^ c, 12); \
+	a += b + m[blake2s_sigma[r][2 * i + 1]]; \
+	d = ror32(d ^ a, 8); \
+	c += d; \
+	b = ror32(b ^ c, 7); \
+} while (0)
+
+#define ROUND(r) do { \
+	G(r, 0, v[0], v[ 4], v[ 8], v[12]); \
+	G(r, 1, v[1], v[ 5], v[ 9], v[13]); \
+	G(r, 2, v[2], v[ 6], v[10], v[14]); \
+	G(r, 3, v[3], v[ 7], v[11], v[15]); \
+	G(r, 4, v[0], v[ 5], v[10], v[15]); \
+	G(r, 5, v[1], v[ 6], v[11], v[12]); \
+	G(r, 6, v[2], v[ 7], v[ 8], v[13]); \
+	G(r, 7, v[3], v[ 4], v[ 9], v[14]); \
+} while (0)
+		ROUND(0);
+		ROUND(1);
+		ROUND(2);
+		ROUND(3);
+		ROUND(4);
+		ROUND(5);
+		ROUND(6);
+		ROUND(7);
+		ROUND(8);
+		ROUND(9);
+
+#undef G
+#undef ROUND

Now G() is a 14 instruction register dependency chain.
But since each batch of 4 G() is independent the compiler can
interleave them - significant on modern cpu.

OTOH the 10 ROUND() just advance through blake2s_sigma[].
Unrolling these that is probably not that significant.
Especially if the compiler manages to increment the pointer.
While modern gcc manage to optimise the array away completely
the code isn't constrained by memory accesses so loading
from an actual array won't make much difference.
On some architectures the constants either take multiple
instructions to load, or load from memory anyway.
But these bloat that code block by a factor of 10.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
_______________________________________________
buildroot mailing list
buildroot@buildroot.org
https://lists.buildroot.org/mailman/listinfo/buildroot