From bc1e26fb89f2271aec0f2e7373fa342d8770d53e Mon Sep 17 00:00:00 2001 From: Randall Spangler Date: Wed, 21 Jun 2017 14:40:23 -0700 Subject: common: Add base32 encoding Base32 encoding is used to turn the RMA reset binary challenge/response into less-typo-prone text, at 5 bits per character. BUG=b:37952913 BRANCH=none TEST=make runtests Change-Id: I474750a20204ba353cea1e91982aa03e8071c0c2 Signed-off-by: Randall Spangler Reviewed-on: https://chromium-review.googlesource.com/544177 Reviewed-by: Vadim Bendebury (cherry picked from commit 2e3b42610b1239e8643d58396b7471b73e3989f6) Reviewed-on: https://chromium-review.googlesource.com/571641 Tested-by: Vadim Bendebury Commit-Queue: Vadim Bendebury (cherry picked from commit 72d9f23db3a89c2c40837a8a9fe8bdc8eb6a4894) Reviewed-on: https://chromium-review.googlesource.com/828410 --- common/base32.c | 177 +++++++++++++++++++++++++++++++++++++++++++++ common/build.mk | 1 + include/base32.h | 72 +++++++++++++++++++ include/config.h | 3 + test/base32.c | 200 +++++++++++++++++++++++++++++++++++++++++++++++++++ test/base32.tasklist | 17 +++++ test/build.mk | 4 +- test/test_config.h | 4 ++ 8 files changed, 477 insertions(+), 1 deletion(-) create mode 100644 common/base32.c create mode 100644 include/base32.h create mode 100644 test/base32.c create mode 100644 test/base32.tasklist diff --git a/common/base32.c b/common/base32.c new file mode 100644 index 0000000000..476873bc5e --- /dev/null +++ b/common/base32.c @@ -0,0 +1,177 @@ +/* Copyright 2017 The Chromium OS Authors. All rights reserved. + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +/* Base-32 encoding/decoding */ + +#include "common.h" +#include "base32.h" +#include "util.h" + +uint8_t crc5_sym(int sym, uint8_t previous_crc) +{ + unsigned crc = previous_crc << 8; + int i; + + /* + * 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); +} + +/* A-Z0-9 with I,O,0,1 removed */ +const char base32_map[33] = "ABCDEFGHJKLMNPQRSTUVWXYZ23456789"; + +/** + * Decode a base32 symbol. + * + * @param sym Input symbol + * @return The symbol value or -1 if error. + */ +static int decode_sym(int sym) +{ + int i = 0; + + for (i = 0; i < 32; i++) { + if (sym == base32_map[i]) + return i; + } + + return -1; +} + +int base32_encode(char *dest, int destlen_chars, + const void *srcbits, int srclen_bits, + int add_crc_every) +{ + const uint8_t *src = srcbits; + int destlen_needed; + int crc = 0, crc_count = 0; + int didx = 0; + int i; + + *dest = 0; + + /* Make sure destination is big enough */ + destlen_needed = (srclen_bits + 4) / 5; /* Symbols before adding CRC */ + if (add_crc_every) { + /* Must be an exact number of groups to add CRC */ + if (destlen_needed % add_crc_every) + return EC_ERROR_INVAL; + destlen_needed += destlen_needed / add_crc_every; + } + destlen_needed++; /* For terminating null */ + if (destlen_chars < destlen_needed) + return EC_ERROR_INVAL; + + for (i = 0; i < srclen_bits; i += 5) { + int sym; + int sidx = i / 8; + int bit_offs = i % 8; + + if (bit_offs <= 3) { + /* Entire symbol fits in that byte */ + sym = src[sidx] >> (3 - bit_offs); + } else { + /* Use the bits we have left */ + sym = src[sidx] << (bit_offs - 3); + + /* Use the bits from the next byte, if any */ + if (i + 1 < srclen_bits) + sym |= src[sidx + 1] >> (11 - bit_offs); + } + + sym &= 0x1f; + + /* Pad incomplete symbol with 0 bits */ + if (srclen_bits - i < 5) + sym &= 0x1f << (5 + i - srclen_bits); + + dest[didx++] = base32_map[sym]; + + /* Add CRC if needed */ + if (add_crc_every) { + crc = crc5_sym(sym, crc); + if (++crc_count == add_crc_every) { + dest[didx++] = base32_map[crc]; + crc_count = crc = 0; + } + } + } + + /* Terminate string and return */ + dest[didx] = 0; + return EC_SUCCESS; +} + +int base32_decode(uint8_t *dest, int destlen_bits, const char *src, + int crc_after_every) +{ + int crc = 0, crc_count = 0; + int out_bits = 0; + + for (; *src; src++) { + int sym, sbits, dbits, b; + + if (isspace(*src) || *src == '-') + continue; + + sym = decode_sym(*src); + if (sym < 0) + return -1; /* Bad input symbol */ + + /* Check CRC if needed */ + if (crc_after_every) { + if (crc_count == crc_after_every) { + if (crc != sym) + return -1; + crc_count = crc = 0; + continue; + } else { + crc = crc5_sym(sym, crc); + crc_count++; + } + } + + /* + * Stop if we're out of space. Have to do this after checking + * the CRC, or we might not check the last CRC. + */ + if (out_bits >= destlen_bits) + break; + + /* See how many bits we get to use from this symbol */ + sbits = MIN(5, destlen_bits - out_bits); + if (sbits < 5) + sym >>= (5 - sbits); + + /* Fill up the rest of the current byte */ + dbits = 8 - (out_bits & 7); + b = MIN(dbits, sbits); + if (dbits == 8) + dest[out_bits / 8] = 0; /* Starting a new byte */ + dest[out_bits / 8] |= (sym << (dbits - b)) >> (sbits - b); + out_bits += b; + sbits -= b; + + /* Start the next byte if there's space */ + if (sbits > 0) { + dest[out_bits / 8] = sym << (8 - sbits); + out_bits += sbits; + } + } + + /* If we have CRCs, should have a full group */ + if (crc_after_every && crc_count) + return -1; + + return out_bits; +} diff --git a/common/build.mk b/common/build.mk index 93ec3fad97..ef41886133 100644 --- a/common/build.mk +++ b/common/build.mk @@ -20,6 +20,7 @@ common-$(CONFIG_ADC)+=adc.o common-$(HAS_TASK_ALS)+=als.o common-$(CONFIG_AP_HANG_DETECT)+=ap_hang_detect.o common-$(CONFIG_BACKLIGHT_LID)+=backlight_lid.o +common-$(CONFIG_BASE32)+=base32.o # TODO(crosbug.com/p/23821): Why do these include battery_common but # the other batteries don't? Perhaps should use CONFIG_CMD_BATTERY # instead, since all that's in battery.c is the battery console diff --git a/include/base32.h b/include/base32.h new file mode 100644 index 0000000000..e519034732 --- /dev/null +++ b/include/base32.h @@ -0,0 +1,72 @@ +/* Copyright 2017 The Chromium OS Authors. All rights reserved. + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +/* Base-32 encoding/decoding, designed for manual operator entry. */ + +#ifndef __CROS_EC_BASE32_H +#define __CROS_EC_BASE32_H + +/* Symbol map for base32 encoding */ +extern const char base32_map[33]; + +/** + * 5-bit CRC + * + * @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); + +/** + * base32-encode data into a null-terminated string + * + * Uses A-Z0-9 encoding, skipping I,O,0,1 since they're easy to get mixed up. + * + * @param dest Destination buffer; set to empty string on + * error + * @param destlen_chars Length of destination buffer in characters + * @param src Source binary data + * @param srclen_bits Length of source *in bits*. If this is not a + * multiple of 8, the *most significant* bits of + * the last byte will be used. If this is not a + * multiple of 5, the least significant bits of + * the last symbol will be padded with 0 bits. + * @param add_crc_every If non-zero, add a CRC symbol after each group + * of this many symbols. There must be an exact + * number of groups; that is, ceil(srclen_bits/5) + * must be a multiple of add_crc_every. + * @return EC_SUCCESS, or non-zero error code. + */ +int base32_encode(char *dest, int destlen_chars, + const void *srcbits, int srclen_bits, + int add_crc_every); + +/** + * base32-decode data from a null-terminated string + * + * Ignores whitespace and '-' dashes in the source string. + * + * If the destination is smaller than the decoded bitstream, only that many + * bits will be decoded. This is useful for decoding the first part of a + * bitstream to look for a struct version. + * + * If the destination is larger than the decoded bitstream, check the return + * value to determine how many bits were decoded from the source. Note that if + * padding was added by base32_encode (that is, the input length was not a + * multiple of 5 bits), the padding will be included in the count. + * + * @param dest Destination; must be at least + * ceil(destlen_bits/8) bytes. + * @param destlen_bits Length of destination *in bits*. + * @param src Source string (null-terminated) + * @param crc_after_every If non-zero, expect CRC symbol after every + * group of this many symbols. + * @return Number of decoded *bits*, or -1 if error. + */ +int base32_decode(uint8_t *dest, int destlen_bits, const char *src, + int crc_after_every); + +#endif diff --git a/include/config.h b/include/config.h index e13a3c2aa5..7206555113 100644 --- a/include/config.h +++ b/include/config.h @@ -188,6 +188,9 @@ */ #undef CONFIG_BACKLIGHT_REQ_GPIO +/* Support base32 text encoding */ +#undef CONFIG_BASE32 + /*****************************************************************************/ /* Battery config */ diff --git a/test/base32.c b/test/base32.c new file mode 100644 index 0000000000..f49b28dd11 --- /dev/null +++ b/test/base32.c @@ -0,0 +1,200 @@ +/* Copyright 2017 The Chromium OS Authors. All rights reserved. + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + * + * Test Base-32 encoding/decoding + */ + +#include +#include "common.h" +#include "base32.h" +#include "test_util.h" +#include "util.h" + +static int test_crc5(void) +{ + uint32_t seen; + int i, j, c; + int errors = 0; + + /* + * For every current CRC value and symbol, new CRC value is unique. + * This guarantees a single-character typo will be detected. + */ + for (i = 0; i < 32; i++) { + seen = 0; + for (j = 0; j < 32; j++) + seen |= 1 << crc5_sym(j, i); + TEST_ASSERT(seen == 0xffffffff); + } + + /* Transposing different symbols generates distinct CRCs */ + for (c = 0; c < 32; c++) { + for (i = 0; i < 32; i++) { + for (j = i + 1; j < 32; j++) { + if (crc5_sym(j, crc5_sym(i, c)) == + crc5_sym(i, crc5_sym(j, c))) + errors++; + } + } + } + TEST_ASSERT(errors == 0); + + return EC_SUCCESS; +} + +static int enctest(const void *src, int srcbits, int crc_every, + const char *enc) +{ + char dest[32]; + + if (base32_encode(dest, sizeof(dest), src, srcbits, crc_every)) + return -1; + if (strlen(dest) != strlen(enc) || strncmp(dest, enc, strlen(dest))) { + fprintf(stderr, "expected encode: \"%s\"\n", enc); + fprintf(stderr, "got encode: \"%s\"\n", dest); + return -2; + } + return 0; +} + +#define ENCTEST(a, b, c, d) TEST_ASSERT(enctest(a, b, c, d) == 0) + +static int test_encode(void) +{ + const uint8_t src1[5] = {0xff, 0x00, 0xff, 0x00, 0xff}; + char enc[32]; + + /* Test for enough space; error produces null string */ + *enc = 1; + TEST_ASSERT(base32_encode(enc, 3, src1, 15, 0) == EC_ERROR_INVAL); + TEST_ASSERT(*enc == 0); + + /* Empty source */ + ENCTEST("\x00", 0, 0, ""); + + /* Single symbol uses top 5 bits */ + ENCTEST("\x07", 5, 0, "A"); + ENCTEST("\xb8", 5, 0, "Z"); + ENCTEST("\xc0", 5, 0, "2"); + ENCTEST("\xf8", 5, 0, "9"); + + /* Multiples of 5 bits use top bits */ + ENCTEST("\x08\x86", 10, 0, "BC"); + ENCTEST("\x08\x86", 15, 0, "BCD"); + + /* Multiples of 8 bits pad with 0 bits */ + ENCTEST("\xff", 8, 0, "96"); + ENCTEST("\x08\x87", 16, 0, "BCDS"); + + /* Multiples of 40 bits use all the bits */ + 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"); + 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"); + + return EC_SUCCESS; +} + +static int cmpbytes(const uint8_t *expect, const uint8_t *got, int len, + const char *desc) +{ + int i; + + if (!memcmp(expect, got, len)) + return 0; + + fprintf(stderr, "expected %s:", desc); + for (i = 0; i < len; i++) + fprintf(stderr, " %02x", expect[i]); + fprintf(stderr, "\ngot %s: ", desc); + for (i = 0; i < len; i++) + fprintf(stderr, " %02x", got[i]); + fprintf(stderr, "\n"); + + return -2; +} + +static int dectest(const void *dec, int decbits, int crc_every, const char *enc) +{ + uint8_t dest[32]; + int destbits = decbits > 0 ? decbits : sizeof(dest) * 8; + int wantbits = decbits > 0 ? decbits : 5 * strlen(enc); + int gotbits = base32_decode(dest, destbits, enc, crc_every); + + TEST_ASSERT(gotbits == wantbits); + if (gotbits != wantbits) + return -1; + return cmpbytes(dec, dest, (decbits + 7) / 8, "decode"); +} + +#define DECTEST(a, b, c, d) TEST_ASSERT(dectest(a, b, c, d) == 0) + +static int test_decode(void) +{ + uint8_t dec[32]; + + /* Decode tests, dest-limited */ + DECTEST("\xf8", 5, 0, "97"); + DECTEST("\x08", 5, 0, "BCDS"); + DECTEST("\x08\x80", 10, 0, "BCDS"); + DECTEST("\x08\x86", 15, 0, "BCDS"); + 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"); + + /* Decode ignores whitespace and dashes */ + DECTEST("\xff\x00\xff\x00\xff", 40, 0, " 96\tA-R\r8A H9\n"); + + /* Invalid symbol fails */ + TEST_ASSERT(base32_decode(dec, 16, "AI", 0) == -1); + + /* If dest buffer is big, use all the source bits */ + DECTEST("", 0, 0, ""); + DECTEST("\xf8", 0, 0, "9"); + DECTEST("\x07\xc0", 0, 0, "A9"); + DECTEST("\x00\x3e", 0, 0, "AA9"); + DECTEST("\x00\x01\xf0", 0, 0, "AAA9"); + DECTEST("\xff\x00\xff\x00\xff", 0, 0, "96AR8AH9"); + + /* Decode always overwrites destination */ + memset(dec, 0xff, sizeof(dec)); + DECTEST("\x00\x00\x00\x00\x00", 0, 0, "AAAAAAAA"); + memset(dec, 0x00, sizeof(dec)); + 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 */ + + /* 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"); + + /* Detect errors in data, CRC, and transposition */ + TEST_ASSERT(base32_decode(dec, 40, "96AQL", 4) == -1); + TEST_ASSERT(base32_decode(dec, 40, "96ARM", 4) == -1); + TEST_ASSERT(base32_decode(dec, 40, "96RAL", 4) == -1); + + return EC_SUCCESS; +} + +void run_test(void) +{ + test_reset(); + + RUN_TEST(test_crc5); + RUN_TEST(test_encode); + RUN_TEST(test_decode); + + test_print_result(); +} diff --git a/test/base32.tasklist b/test/base32.tasklist new file mode 100644 index 0000000000..e241aab4bb --- /dev/null +++ b/test/base32.tasklist @@ -0,0 +1,17 @@ +/* Copyright 2017 The Chromium OS Authors. All rights reserved. + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +/** + * List of enabled tasks in the priority order + * + * The first one has the lowest priority. + * + * For each task, use the macro TASK_TEST(n, r, d, s) where : + * 'n' in the name of the task + * 'r' in the main routine of the task + * 'd' in an opaque parameter passed to the routine at startup + * 's' is the stack size in bytes; must be a multiple of 8 + */ +#define CONFIG_TEST_TASK_LIST /* No test task */ diff --git a/test/build.mk b/test/build.mk index a90dfc410f..e3a781a87a 100644 --- a/test/build.mk +++ b/test/build.mk @@ -31,7 +31,8 @@ test-list-$(BOARD_SAMUS_PD)= ifneq ($(TEST_LIST_HOST),) test-list-host=$(TEST_LIST_HOST) else -test-list-host = battery_get_params_smart +test-list-host = base32 +test-list-host += battery_get_params_smart test-list-host += bklight_lid test-list-host += bklight_passthru test-list-host += button @@ -71,6 +72,7 @@ test-list-host += usb_pd_giveback test-list-host += utils endif +base32-y=base32.o battery_get_params_smart-y=battery_get_params_smart.o bklight_lid-y=bklight_lid.o bklight_passthru-y=bklight_passthru.o diff --git a/test/test_config.h b/test/test_config.h index 357f06beb9..ef0cbf10ee 100644 --- a/test/test_config.h +++ b/test/test_config.h @@ -18,6 +18,10 @@ #undef CONFIG_VBOOT_HASH #undef CONFIG_USB_PD_LOGGING +#ifdef TEST_BASE32 +#define CONFIG_BASE32 +#endif + #ifdef TEST_BKLIGHT_LID #define CONFIG_BACKLIGHT_LID #endif -- cgit v1.2.1