util: Add function to convert binary first base3 number

Add an util function to convert a ternary bit array (each element is
either 0, 1, or 2) to a non-standard ternary number system where the
first 2^n natural numbers are represented as they would be in a
binary system (without any Z digits) and the following 3^n-2^n numbers
use the remaining ternary representations in the normal ternary system
order (skipping the values that were already used up).

This function is useful for converting BOARd ID, which is initially
used a binary and later decided to switch to tri-state after some
revisions have already been built.

BRANCH=Trogdor
BUG=b:190250108
TEST=make runhosttests

Change-Id: I853a04f3b28eb54c61855251dc5232c7e6994fef
Signed-off-by: Wai-Hong Tam <waihong@google.com>
Reviewed-on: https://chromium-review.googlesource.com/c/chromiumos/platform/ec/+/2964389
Reviewed-by: Julius Werner <jwerner@chromium.org>

3 files changed, 109 insertions, 0 deletions

diff --git a/common/util.c b/common/util.c
index d60fcd95d5..8e965273a5 100644
--- a/common/util.c
+++ b/common/util.c
@@ -699,3 +699,56 @@ void wait_for_ready(volatile uint32_t *reg, uint32_t enable, uint32_t ready)
 	while (!(*reg & ready))
 		;
 }
+
+int binary_first_base3_from_bits(int *bits, int nbits)
+{
+	int binary_below = 0;
+	int has_z = 0;
+	int base3 = 0;
+	int i;
+
+	/* Loop through every ternary digit, from MSB to LSB. */
+	for (i = nbits - 1; i >= 0; i--) {
+		/*
+		 * We keep track of the normal ternary result and whether
+		 * we found any bit that was a Z. We also determine the
+		 * amount of numbers that can be represented with only binary
+		 * digits (no Z) whose value in the normal ternary system
+		 * is lower than the one we are parsing. Counting from the left,
+		 * we add 2^i for any '1' digit to account for the binary
+		 * numbers whose values would be below it if all following
+		 * digits we parsed would be '0'. As soon as we find a '2' digit
+		 * we can total the remaining binary numbers below as 2^(i+1)
+		 * because we know that all binary representations counting only
+		 * this and following digits must have values below our number
+		 * (since 1xxx is always smaller than 2xxx).
+		 *
+		 * Example: 1 0 2 1 (counting from the left / most significant)
+		 * '1' at 3^3: Add 2^3 = 8 to account for binaries 0000-0111
+		 * '0' at 3^2: Ignore (not all binaries 1000-1100 are below us)
+		 * '2' at 3^1: Add 2^(1+1) = 4 to account for binaries 1000-1011
+		 * Stop adding for lower digits (3^0), all already accounted
+		 * now. We know that there can be no binary numbers 1020-102X.
+		 */
+		base3 = (base3 * 3) + bits[i];
+
+		if (!has_z) {
+			switch (bits[i]) {
+			case 0: /* Ignore '0' digits. */
+				break;
+			case 1:	/* Account for binaries 0 to 2^i - 1. */
+				binary_below += 1 << i;
+				break;
+			case 2:	/* Account for binaries 0 to 2^(i+1) - 1. */
+				binary_below += 1 << (i + 1);
+				has_z = 1;
+			}
+		}
+	}
+
+	if (has_z)
+		return base3 + (1 << nbits) - binary_below;
+
+	/* binary_below is normal binary system value if !has_z. */
+	return binary_below;
+}
diff --git a/include/util.h b/include/util.h
index a25bbbd77a..21603484bb 100644
--- a/include/util.h
+++ b/include/util.h
@@ -328,6 +328,37 @@ static inline uint64_t mulaa32(uint32_t a, uint32_t b, uint32_t c, uint32_t d)
  */
 void wait_for_ready(volatile uint32_t *reg, uint32_t enable, uint32_t ready);
 
+/**
+ * Convert the ternary bit array (each element is either 0, 1, or 2) to a
+ * non-standard ternary number system where the first 2^n natural numbers are
+ * represented as they would be in a binary system (without any Z digits) and
+ * the following 3^n-2^n numbers use the remaining ternary representations in
+ * the normal ternary system order (skipping the values that were already used
+ * up).
+ *
+ * This function is useful for converting BOARd ID, which is initially used a
+ * binary and later decided to switch to tri-state after some revisions have
+ * already been built.
+ *
+ * Example: For nbits = 2 we get the following representation:
+ *
+ *   Number      X1     X0
+ *     0          0      0
+ *     1          0      1
+ *     2          1      0
+ *     3          1      1	// Start counting ternaries back at 0 after this
+ *     4          0      2	// Skipping 00 and 01 which are already used up
+ *     5          1      2	// Skipping 10 and 11 which are already used up
+ *     6          2      0
+ *     7          2      1
+ *     8          2      2
+ *
+ * @param bits		Array of ternary bits (LSB first).
+ * @param nbits		Total number of bits.
+ * @return Number in the binary-first ternary number system.
+ */
+int binary_first_base3_from_bits(int *bits, int nbits);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/test/utils.c b/test/utils.c
index 82316a53cc..9402e92740 100644
--- a/test/utils.c
+++ b/test/utils.c
@@ -481,6 +481,30 @@ test_static int test_alignment_log2(void)
 	return EC_SUCCESS;
 }
 
+test_static int test_binary_first_base3_from_bits(void)
+{
+	int n0[] = {0, 0, 0};  /* LSB first */
+	int n7[] = {1, 1, 1};
+	int n8[] = {2, 0, 0};
+	int n9[] = {2, 1, 0};
+	int n10[] = {0, 2, 0};
+	int n11[] = {1, 2, 0};
+	int n18[] = {0, 0, 2};
+	int n26[] = {2, 2, 2};
+	int n38[] = {1, 2, 0, 1};
+
+	TEST_EQ(binary_first_base3_from_bits(n0, ARRAY_SIZE(n0)), 0, "%d");
+	TEST_EQ(binary_first_base3_from_bits(n7, ARRAY_SIZE(n7)), 7, "%d");
+	TEST_EQ(binary_first_base3_from_bits(n8, ARRAY_SIZE(n8)), 8, "%d");
+	TEST_EQ(binary_first_base3_from_bits(n9, ARRAY_SIZE(n9)), 9, "%d");
+	TEST_EQ(binary_first_base3_from_bits(n10, ARRAY_SIZE(n10)), 10, "%d");
+	TEST_EQ(binary_first_base3_from_bits(n11, ARRAY_SIZE(n11)), 11, "%d");
+	TEST_EQ(binary_first_base3_from_bits(n18, ARRAY_SIZE(n18)), 18, "%d");
+	TEST_EQ(binary_first_base3_from_bits(n26, ARRAY_SIZE(n26)), 26, "%d");
+	TEST_EQ(binary_first_base3_from_bits(n38, ARRAY_SIZE(n38)), 38, "%d");
+	return EC_SUCCESS;
+}
+
 void run_test(int argc, char **argv)
 {
 	test_reset();
@@ -502,6 +526,7 @@ void run_test(int argc, char **argv)
 	RUN_TEST(test_is_aligned);
 	RUN_TEST(test_safe_memcmp);
 	RUN_TEST(test_alignment_log2);
+	RUN_TEST(test_binary_first_base3_from_bits);
 
 	test_print_result();
 }