diff options
| -rw-r--r-- | common/util.c | 53 | ||||
| -rw-r--r-- | include/util.h | 31 | ||||
| -rw-r--r-- | test/utils.c | 25 |
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(); } |