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, 13 insertions, 0 deletions

diff --git a/include/util.h b/include/util.h
index 10d9b3661d..a6de67e3d8 100644
--- a/include/util.h
+++ b/include/util.h
@@ -13,6 +13,7 @@
 #include "panic.h"
 
 #include "builtin/assert.h"         /* For ASSERT(). */
+#include <stdbool.h>
 #include <stddef.h>
 
 #ifdef __cplusplus
@@ -163,6 +164,18 @@ int uint64divmod(uint64_t *v, int by);
 int get_next_bit(uint32_t *mask);
 
 /**
+ * Check if |buffer| is full of 0x00 or 0xff.
+ *
+ * This function runs in constant execution time and is not vulnerable to
+ * timing attacks.
+ *
+ * @param buffer the buffer to check.
+ * @param size the number of bytes to check.
+ * @return true if |buffer| is full of 0x00 or 0xff, false otherwise.
+ */
+bool bytes_are_trivial(const uint8_t *buffer, size_t size);
+
+/**
  * Reverse's the byte-order of the provided buffer.
  */
 void reverse(void *dest, size_t len);