diff options
author | Sam Hurst <shurst@google.com> | 2017-09-11 11:39:55 -0700 |
---|---|---|
committer | chrome-bot <chrome-bot@chromium.org> | 2017-09-12 16:17:03 -0700 |
commit | cdcc09096ad5fac8e74903346b09552e3aeb3547 (patch) | |
tree | 20e2e644391a7bc5f9371e98230c779607af41e9 | |
parent | cfe418923d73d610c34a21b020efa823ed0d0898 (diff) | |
download | chrome-ec-cdcc09096ad5fac8e74903346b09552e3aeb3547.tar.gz |
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>
-rw-r--r-- | common/base32.c | 28 | ||||
-rw-r--r-- | include/base32.h | 5 | ||||
-rw-r--r-- | test/base32.c | 26 |
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); |