common: Substitute modified CRC8 with CRC-5-USB

The modified CRC8 implementation didn't detect some errors. For
example, using the modified CRC8: CC5QQLALU and DC5QQLALU calculates
to the same value.

BUG=b:37952913
BRANCH=none
TEST=make buildall
Used online CRC-5-USB calculator to test several values against
this implementation.
Signed-off-by: Sam Hurst <shurst@chromium.org>

Change-Id: I5a17941e25691872a25b41525f65f36e2ed1d4fa
Reviewed-on: https://chromium-review.googlesource.com/660812
Commit-Ready: Sam Hurst <shurst@google.com>
Tested-by: Sam Hurst <shurst@google.com>
Reviewed-by: Randall Spangler <rspangler@chromium.org>
Reviewed-by: Michael Tang <ntang@chromium.org>

3 files changed, 34 insertions, 25 deletions

diff --git a/common/base32.c b/common/base32.c
index 476873bc5e..8a33d7685c 100644
--- a/common/base32.c
+++ b/common/base32.c
@@ -9,22 +9,20 @@
 #include "base32.h"
 #include "util.h"
 
-uint8_t crc5_sym(int sym, uint8_t previous_crc)
-{
-	unsigned crc = previous_crc << 8;
-	int i;
+static const unsigned char crc5_table1[] = {
+	0x00, 0x0E, 0x1C, 0x12, 0x11, 0x1F, 0x0D, 0x03,
+	0x0B, 0x05, 0x17, 0x19, 0x1A, 0x14, 0x06, 0x08
+};
 
-	/*
-	 * This is a modified CRC-8 which only folds in a 5-bit
-	 * symbol, and it only keeps the bottom 5 bits of the CRC.
-	 */
-	crc ^= (sym << 11);
-	for (i = 5; i; i--) {
-		if (crc & 0x8000)
-			crc ^= (0x1070 << 3);
-		crc <<= 1;
-	}
-	return (uint8_t)((crc >> 8) & 0x1f);
+static const unsigned char crc5_table0[] = {
+	0x00, 0x16, 0x05, 0x13, 0x0A, 0x1C, 0x0F, 0x19,
+	0x14, 0x02, 0x11, 0x07, 0x1E, 0x08, 0x1B, 0x0D
+};
+
+uint8_t crc5_sym(uint8_t sym, uint8_t previous_crc)
+{
+	uint8_t tmp = sym ^ previous_crc;
+	return crc5_table1[tmp & 0x0F] ^ crc5_table0[(tmp >> 4) & 0x0F];
 }
 
 /* A-Z0-9 with I,O,0,1 removed */
diff --git a/include/base32.h b/include/base32.h
index e519034732..ac04ce9c70 100644
--- a/include/base32.h
+++ b/include/base32.h
@@ -12,13 +12,14 @@
 extern const char base32_map[33];
 
 /**
- * 5-bit CRC
+ * CRC-5-USB Initially created for USB Token Packets. It uses
+ * the generator polynomial X^5 + X^2 + X^0 and is 5-bits.
  *
  * @param sym		New symbol to update CRC with
  * @param previous_crc	Existing CRC value
  * @return The updated CRC.
  */
-uint8_t crc5_sym(int sym, uint8_t previous_crc);
+uint8_t crc5_sym(uint8_t sym, uint8_t previous_crc);
 
 /**
  * base32-encode data into a null-terminated string
diff --git a/test/base32.c b/test/base32.c
index f49b28dd11..6fd574bb73 100644
--- a/test/base32.c
+++ b/test/base32.c
@@ -28,6 +28,17 @@ static int test_crc5(void)
 		TEST_ASSERT(seen == 0xffffffff);
 	}
 
+	/*
+	 * Do the same in the opposite order, to make sure a subsequent
+	 * character doesn't obscure a previous typo.
+	 */
+	for (i = 0; i < 32; i++) {
+		seen = 0;
+		for (j = 0; j < 32; j++)
+			seen |= 1 << crc5_sym(i, j);
+		TEST_ASSERT(seen == 0xffffffff);
+	}
+
 	/* Transposing different symbols generates distinct CRCs */
 	for (c = 0; c < 32; c++) {
 		for (i = 0; i < 32; i++) {
@@ -91,13 +102,13 @@ static int test_encode(void)
 	ENCTEST("\xff\x00\xff\x00\xff", 40, 0, "96AR8AH9");
 
 	/* CRC requires exact multiple of symbol count */
-	ENCTEST("\xff\x00\xff\x00\xff", 40, 4, "96ARL8AH9V");
-	ENCTEST("\xff\x00\xff\x00\xff", 40, 8, "96AR8AH9V");
+	ENCTEST("\xff\x00\xff\x00\xff", 40, 4, "96ARU8AH9D");
+	ENCTEST("\xff\x00\xff\x00\xff", 40, 8, "96AR8AH9L");
 	TEST_ASSERT(
 	    base32_encode(enc, 16, (uint8_t *)"\xff\x00\xff\x00\xff", 40, 6)
 	    == EC_ERROR_INVAL);
 	/* But what matters is symbol count, not bit count */
-	ENCTEST("\xff\x00\xff\x00\xfe", 39, 4, "96ARL8AH8W");
+	ENCTEST("\xff\x00\xff\x00\xfe", 39, 4, "96ARU8AH8P");
 
 	return EC_SUCCESS;
 }
@@ -148,7 +159,7 @@ static int test_decode(void)
 	DECTEST("\xff", 8, 0, "96");
 	DECTEST("\x08\x87", 16, 0, "BCDS");
 	DECTEST("\xff\x00\xff\x00\xff", 40, 0, "96AR8AH9");
-	DECTEST("\xff\x00\xff\x00\xfe", 39, 4, "96ARL8AH8W");
+	DECTEST("\xff\x00\xff\x00\xfe", 39, 4, "96ARU8AH8P");
 
 	/* Decode ignores whitespace and dashes */
 	DECTEST("\xff\x00\xff\x00\xff", 40, 0, " 96\tA-R\r8A H9\n");
@@ -171,14 +182,13 @@ static int test_decode(void)
 	DECTEST("\xff\xff\xff\xff\xff", 0, 0, "99999999");
 
 	/* Good CRCs */
-	DECTEST("\xff\x00\xff\x00\xff", 40, 4, "96ARL8AH9V");
-	DECTEST("\xff\x00\xff\x00\xff", 40, 8, "96AR8AH9V");
-	/* Detect errors in data, CRC, and transposition */
+	DECTEST("\xff\x00\xff\x00\xff", 40, 4, "96ARU8AH9D");
+	DECTEST("\xff\x00\xff\x00\xff", 40, 8, "96AR8AH9L");
 
 	/* CRC requires exact multiple of symbol count */
 	TEST_ASSERT(base32_decode(dec, 40, "96ARL8AH9", 4) == -1);
 	/* But what matters is symbol count, not bit count */
-	DECTEST("\xff\x00\xff\x00\xfe", 39, 4, "96ARL8AH8W");
+	DECTEST("\xff\x00\xff\x00\xfe", 39, 4, "96ARU8AH8P");
 
 	/* Detect errors in data, CRC, and transposition */
 	TEST_ASSERT(base32_decode(dec, 40, "96AQL", 4) == -1);