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

2 files changed, 13 insertions, 10 deletions

diff --git a/common/rollback.c b/common/rollback.c
index 4654b21b64..e62e4a09fd 100644
--- a/common/rollback.c
+++ b/common/rollback.c
@@ -180,23 +180,14 @@ test_mockable int rollback_get_secret(uint8_t *secret)
 {
 	int ret = EC_ERROR_UNKNOWN;
 	struct rollback_data data;
-	uint8_t first;
-	int i = 0;
 
 	if (get_latest_rollback(&data) < 0)
 		goto failed;
 
 	/* Check that secret is not full of 0x00 or 0xff */
-	first = data.secret[0];
-	if (first == 0x00 || first == 0xff) {
-		for (i = 1; i < sizeof(data.secret); i++) {
-			if (data.secret[i] != first)
-				goto good;
-		}
+	if (bytes_are_trivial(data.secret, sizeof(data.secret)))
 		goto failed;
-	}
 
-good:
 	memcpy(secret, data.secret, sizeof(data.secret));
 	ret = EC_SUCCESS;
 failed:
diff --git a/common/util.c b/common/util.c
index b9f11aad27..8d12dc59f4 100644
--- a/common/util.c
+++ b/common/util.c
@@ -539,6 +539,18 @@ int get_next_bit(uint32_t *mask)
 	return bit;
 }
 
+bool bytes_are_trivial(const uint8_t *buffer, size_t size)
+{
+	size_t i;
+	uint8_t result0 = 0;
+	uint8_t result1 = 0;
+
+	for (i = 0; i < size; i++) {
+		result0 |= buffer[i] ^ 0x00;
+		result1 |= buffer[i] ^ 0xff;
+	}
+	return (result0 == 0) || (result1 == 0);
+}
 
 /****************************************************************************/
 /* stateful conditional stuff */