test/entropy: Add host test and compute entropy

Check that added entropy is at least somewhat acceptable.

BRANCH=none
BUG=b:38486828
TEST=make BOARD=hammer -j tests
     ./util/flash_ec --board=hammer --image=build/hammer/test-entropy.bin
     EC console: runtest, get around 4000/1000 (=4) bits of entropy, value
     matches (roughly) the value obtained using the awk script.
TEST=make run-entropy

Change-Id: I88d0e9ec0e38ab3ec70d3e8163b8ac1556df978d
Reviewed-on: https://chromium-review.googlesource.com/523482
Commit-Ready: Nicolas Boichat <drinkcat@chromium.org>
Tested-by: Nicolas Boichat <drinkcat@chromium.org>
Reviewed-by: Vincent Palatin <vpalatin@chromium.org>

1 files changed, 40 insertions, 8 deletions

diff --git a/test/entropy.c b/test/entropy.c
index f01a3dd0a0..7498d4edf9 100644
--- a/test/entropy.c
+++ b/test/entropy.c
@@ -15,6 +15,20 @@
 
 static int buckets[256];
 
+static const int log2_mult = 2;
+
+/*
+ * log2 (multiplied by 2). For non-power of 2, this rounds to the closest
+ * half-integer, otherwise the value is exact.
+ */
+uint32_t log2(int32_t val)
+{
+	int val1 = 31 - __builtin_clz(val);
+	int val2 = 32 - __builtin_clz(val - 1);
+
+	return log2_mult * (val1 + val2)/2;
+}
+
 void run_test(void)
 {
 	const int loopcount = 512;
@@ -22,6 +36,9 @@ void run_test(void)
 	uint8_t buffer[32];
 	timestamp_t t0, t1;
 	int i, j;
+	uint32_t entropy;
+	const int totalcount = loopcount * sizeof(buffer);
+	const int log2totalcount = log2(totalcount);
 
 	memset(buckets, 0, sizeof(buckets));
 
@@ -43,18 +60,33 @@ void run_test(void)
 		watchdog_reload();
 	}
 
-	ccprintf("Total count: %d\n", loopcount * sizeof(buffer));
+	ccprintf("Total count: %d\n", totalcount);
 	ccprintf("Buckets: ");
+	entropy = 0;
 	for (j = 0; j < 256; j++) {
+		/*
+		 * Shannon entropy (base 2) is sum of -p[j] * log_2(p[j]).
+		 * p[j] = buckets[j]/totalcount
+		 * -p[j] * log_2(p[j])
+		 *  = -(buckets[j]/totalcount) * log_2(buckets[j]/totalcount)
+		 *  = buckets[j] * (log_2(totalcount) - log_2(buckets[j]))
+		 *                                               / totalcount
+		 * Our log2() function is scaled by log2_mult, and we defer the
+		 * division by totalcount until we get the total sum, so we need
+		 * to divide by (log2_mult * totalcount) at the end.
+		 */
+		entropy += buckets[j] * (log2totalcount - log2(buckets[j]));
 		ccprintf("%d;", buckets[j]);
 		cflush();
 	}
 	ccprintf("\n");
-	/*
-	 * From the data above, entropy can be obtained with this command:
-	 * tr ';' '\n' | awk 'BEGIN { e = 0; tot=16384.0 }
-		{ p = $1/tot; if (p > 0) { e -= p*log(p)/log(2) } }
-		END { print e }'
-	 */
-	test_pass();
+
+	ccprintf("Entropy: %u/1000 bits\n",
+		entropy * 1000 / (log2_mult * totalcount));
+
+	/* We want at least 2 bits of entropy (out of a maximum of 8) */
+	if ((entropy / (log2_mult * totalcount)) >= 2)
+		test_pass();
+	else
+		test_fail();
 }