util: Add function to check whether a buffer is trivial (all 0x00 or all 0xff)

This function's execution time depends only on the buffer length but not on
the specific bytes in the buffer.

BRANCH=nocturne
BUG=chromium:927095
TEST=make -j buildall
TEST=timed the execution of bytes_are_trivial() on a long array with
the following contents:
Array 1: 0x01, 0x00, 0x00, 0x00, ..., 0x00, 0x00 (first byte nontrivial)
Array 2: 0x00, 0x00, 0x00, 0x00, ..., 0x00, 0x02 (last byte nontrivial)
Array 3: 0x00, 0x00, ... , 0x00, 0x03, 0x00, ..., (middle byte nontrivial)
Array 4: 0x00, 0x00 , ... (trivial)
(These 4 arrays have the same length.)
Verified that execution on these arrays take similar amount of time,
proportional to the length of the array, specifically:
For 256k bytes, takes 21~40 microseconds
For 128k bytes, takes 10~17 microseconds
For 64k bytes, takes 5~9 microseconds
For 32k bytes, takes 2~5 microseconds
Because the host timer inaccuracy and potential process scheduling
variations, the execution time for arrays 1-4 are sometimes not exactly
the same. To avoid test flakiness, this timing test is not written to
unit tests. But it should prove that bytes_are_trivial() is a constant
time algorithm.

Change-Id: I131748e1a4ee3a3e19a105dba5dc443bb2371d30
Signed-off-by: Yicheng Li <yichengli@chromium.org>
Reviewed-on: https://chromium-review.googlesource.com/c/chromiumos/platform/ec/+/1787870

1 files changed, 20 insertions, 0 deletions

diff --git a/test/utils.c b/test/utils.c
index c1cc1c301e..cd05aa9f3e 100644
--- a/test/utils.c
+++ b/test/utils.c
@@ -405,6 +405,25 @@ static int test_swap(void)
 	return EC_SUCCESS;
 }
 
+static int test_bytes_are_trivial(void)
+{
+	static const uint8_t all0x00[] = { 0x00, 0x00, 0x00 };
+	static const uint8_t all0xff[] = { 0xff, 0xff, 0xff, 0xff };
+	static const uint8_t nontrivial1[] = { 0x00, 0x01, 0x02 };
+	static const uint8_t nontrivial2[] = { 0xdd, 0xee, 0xff };
+	static const uint8_t nontrivial3[] = { 0x00, 0x00, 0x00, 0xff };
+	static const uint8_t nontrivial4[] = { 0xff, 0x00, 0x00, 0x00 };
+
+	TEST_ASSERT(bytes_are_trivial(all0x00, sizeof(all0x00)));
+	TEST_ASSERT(bytes_are_trivial(all0xff, sizeof(all0xff)));
+	TEST_ASSERT(!bytes_are_trivial(nontrivial1, sizeof(nontrivial1)));
+	TEST_ASSERT(!bytes_are_trivial(nontrivial2, sizeof(nontrivial2)));
+	TEST_ASSERT(!bytes_are_trivial(nontrivial3, sizeof(nontrivial3)));
+	TEST_ASSERT(!bytes_are_trivial(nontrivial4, sizeof(nontrivial4)));
+
+	return EC_SUCCESS;
+}
+
 void run_test(void)
 {
 	test_reset();
@@ -422,6 +441,7 @@ void run_test(void)
 	RUN_TEST(test_cond_t);
 	RUN_TEST(test_mula32);
 	RUN_TEST(test_swap);
+	RUN_TEST(test_bytes_are_trivial);
 
 	test_print_result();
 }