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 <rspangler@chromium.org>
Reviewed-on: https://chromium-review.googlesource.com/544177
Reviewed-by: Vadim Bendebury <vbendeb@chromium.org>
(cherry picked from commit 2e3b42610b1239e8643d58396b7471b73e3989f6)
Reviewed-on: https://chromium-review.googlesource.com/571641
Tested-by: Vadim Bendebury <vbendeb@chromium.org>
Commit-Queue: Vadim Bendebury <vbendeb@chromium.org>
(cherry picked from commit 72d9f23db3a89c2c40837a8a9fe8bdc8eb6a4894)
Reviewed-on: https://chromium-review.googlesource.com/828410

8 files changed, 477 insertions, 1 deletions

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 <stdio.h>
+#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