#include <stddef.h>
#include <stdint.h>

/*
 * ONIONCRC_POLY
 *
 *	A degree-16 polynomial that detects all 3-bit errors in up to
 *	2048-bit words and all 4-bit errors up to 108-bit words, from
 *	Koopman & Chakravarty, `Cyclic Redundancy Code (CRC) Polynomial
 *	Selection For Embedded Networks', International Conference on
 *	Dependable Systems and Networks, 2004.
 *	http://repository.cmu.edu/cgi/viewcontent.cgi?article=1672&context=isr
 *
 *	x^16 + x^14 + x^13 + x^12 + x^10 + x^8 + x^6 + x^4 + x^3 + x^1 + 1
 *
 *	The paper describes this as 0xbaad, but uses a quirky
 *	representation with explicit high-degree term and implicit
 *	constant term taken to be 1.
 *
 *	Of course, for prop224 onion names, we have exactly 262-bit
 *	words (256-bit public key + 8-bit version), so performance on
 *	2048-bit words is irrelevant.  There may be a better choice for
 *	exactly 262-bit words, but it requires some calculation to
 *	choose.
 */
#define	ONIONCRC_POLY	UINT16_C(0x755b)

/*
 * onioncrc_compute_step(crc, o)
 *
 *	Given crc = m_0 x^k (mod g) and o = m_1 of degree 7, compute
 *	and return
 *
 *		crc' = (m_0 x^8 + m_1) x^k (mod g)
 *
 *	using bit-by-bit operations.
 */
static uint16_t
onioncrc_compute_step(uint16_t crc, uint8_t o)
{
	unsigned i;

	crc ^= o << 8;
	for (i = 0; i < 8; i++)
		crc = ((crc << 1) & UINT16_C(0xffff)) ^
		    (ONIONCRC_POLY & -(crc >> 15));

	return crc;
}

/*
 * onioncrc_table[o]
 *
 *	Precomputed table of batch CRC reduction steps for octet o.
 */
static uint16_t onioncrc_table[0x100];

/*
 * onioncrc_init()
 *
 *	Initialize onioncrc_table.
 */
void
onioncrc_init(void)
{
	uint8_t o = 0;

	do {
		onioncrc_table[o] = onioncrc_compute_step(0, o);
	} while (++o != 0);
}

/*
 * onioncrc_step(crc, o)
 *
 *	Given crc = m_0 x^k (mod g) and o = m_1 of degree 7, compute
 *	and return
 *
 *		crc' = (m_0 x^8 + m_1) x^k (mod g)
 *
 *	using table lookup.
 */
uint16_t
onioncrc_step(uint16_t crc, uint8_t o)
{

	return (crc << 8) ^ onioncrc_table[(crc >> 8) ^ o];
}

/*
 * onioncrc_buf(crc, p, n)
 *
 *	Given crc = m_0 x^k (mod g) and the degree-(8*n - 1) polynomial
 *	m_1 = p[0], p[1], ..., p[n - 1], compute and return
 *
 *		crc' = (m_0 x^(8*n) + m_1) x^k (mod g)
 *
 *	using table lookup.
 */
uint16_t
onioncrc_buf(uint16_t crc, const void *buf, size_t len)
{
	const uint8_t *p = buf;
	size_t n = len;

	while (n --> 0)
		crc = onioncrc_step(crc, *p++);

	return crc;
}

#include <err.h>
#include <signal.h>
#include <stdio.h>
#include <unistd.h>

unsigned char buf[BUFSIZ];

int
main(int argc, char **argv)
{
	ssize_t nread;
	uint16_t crc = 0;

	(void)argc;
	(void)argv;

	if (signal(SIGPIPE, SIG_IGN) == SIG_ERR)
		err(1, "signal");

	onioncrc_init();

	while ((nread = read(STDIN_FILENO, buf, sizeof buf)) != 0) {
		if (nread == -1)
			err(1, "read");
		crc = onioncrc_buf(crc, buf, (size_t)nread);
	}

	if (printf("%04hx\n", crc) < 0)
		err(1, "printf");

	return 0;
}