/* PGP quine, inspired by Russ Cox: <http://research.swtch.com/zip>.  */

#include <assert.h>
#include <err.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <zlib.h>

/* State is badly factored, sorry.  */

struct {
	uint32_t bits;
	unsigned int n;
	bool final;
} state;

static void
bytes(const uint8_t *const buffer, const size_t size)
{

	if (buffer == NULL)
		assert(size == 0);
	else if (fwrite(buffer, 1, size, stdout) < size)
		err(1, "fwrite");
}

static void
byte(const uint8_t b)
{

	bytes(&b, 1);
}

static void
flush(void)
{

	if (state.n > 0) {
		byte(state.bits & 0xff);
		assert(state.n <= 8);
		state.bits = 0;
		state.n = 0;
	}
}

static uint32_t
reverse(const unsigned int n, const uint32_t b)
{
	uint32_t d = 0;
	unsigned int i;

	for (i = 0; (i < n); i++)
		d |= (((b & (1 << i)) >> i) << (n - 1 - i));

	return (d);
}

static void
bits(const unsigned int n, const uint32_t b)
{

	state.bits |= (b << state.n);
	state.n += n;

	while (state.n >= 8) {
		byte(state.bits & 0xff);
		state.bits >>= 8;
		state.n -= 8;
	}
}

static void
bits_rev(const unsigned int n, const uint32_t b)
{

	bits(n, reverse(n, b));
}

static void
literal(const unsigned int n)
{
	const uint8_t b1 = (n & 0xff);
	const uint8_t b2 = ((n >> 8) & 0xff);

	assert((n >> 16) == 0);

	bits(1, state.final);
	bits(2, 0);
	flush();
	byte(b1);
	byte(b2);
	byte(~b1);
	byte(~b2);
}

static void
repeat(const unsigned int n)
{
	unsigned int steal = 0;

	bits(1, state.final);
	bits(2, 1);

	/*
	 * XXX Hurk -- is there a conciser way to express this?
	 */

	if ((9 <= n) && (n <= 12)) {
		bits_rev(7, ((254 + (n/2)) - 256));
		bits_rev(5, 6);
		bits(2, (n - 8 - 1));

		bits_rev(7, ((254 + n - (n/2)) - 256));
		bits_rev(5, 6);
		bits(2, (n - 8 - 1));

	} else if ((13 <= n) && (n <= 16)) {
		bits_rev(7, ((254 + (n/2)) - 256));
		bits_rev(5, 7);
		bits(2, (n - 12 - 1));

		bits_rev(7, ((254 + n - (n/2)) - 256));
		bits_rev(5, 7);
		bits(2, (n - 12 - 1));

	} else if ((17 <= n) && (n <= 20)) {
		bits_rev(7, ((254 + (n/2)) - 256));
		bits_rev(5, 8);
		bits(3, (n - 16 - 1));

		bits_rev(7, ((254 + n - (n/2)) - 256));
		bits_rev(5, 8);
		bits(3, (n - 16 - 1));

	} else if (n == 21) {
		bits_rev(7, ((254 + 10) - 256));
		bits_rev(5, 8);
		bits(3, (n - 16 - 1));

		bits_rev(7, (265 - 256));
		bits_rev(1, 0);
		bits_rev(5, 8);
		bits(3, (n - 16 - 1));

		steal = 1;

	} else if ((22 <= n) && (n <= 24)) {
		bits_rev(7, ((265 + (((n/2) - 11) >> 1)) - 256));
		bits(1, (((n/2) - 11) & 1));
		bits_rev(5, 8);
		bits((n - 16 - 1), 3);

		bits_rev(7, ((265 + ((n - (n/2) - 11) >> 1)) - 256));
		bits(1, ((n - (n/2) - 11) & 1));
		bits_rev(5, 8);
		bits(3, (n - 16 - 1));

		steal = 2;

	} else if ((25 <= n) && (n <= 32)) {
		bits_rev(7, ((265 + (((n/2) - 11) >> 1)) - 256));
		bits(1, (((n/2) - 11) & 1));
		bits_rev(5, 9);
		bits(3, (n - 24 - 1));

		bits_rev(7, ((265 + ((n - (n/2) - 11) >> 1)) - 256));
		bits(1, (n - (n/2) - 11));
		bits_rev(5, 9);
		bits(3, (n - 24 - 1));

		steal = 2;

	} else if ((33 <= n) && (n <= 36)) {
		bits_rev(7, ((265 + (((n/2) - 11) >> 1)) - 256));
		bits(1, (((n/2) - 11) & 1));
		bits_rev(5, 10);
		bits(4, (n - 32 - 1));

		bits_rev(7, ((265 + ((n - (n/2) - 11) >> 1)) - 256));
		bits(1, ((n - (n/2) - 11) >> 1));
		bits_rev(5, 10);
		bits(4, (n - 32 - 1));

		steal = 4;

	} else if ((37 <= n) && (n <= 48)) {
		bits_rev(7, ((265 + ((18 - 11) >> 1)) - 256));
		bits(1, ((18 - 11) & 1));
		bits_rev(5, 10);
		bits(4, (n - 32 - 1));

		bits_rev(7, ((269 + ((n - 18 - 19) >> 2)) - 256));
		bits(2, ((n - 18 - 19) & 2));
		bits_rev(5, 10);
		bits(4, (n - 32 - 1));

		steal = 5;

	} else if ((49 <= n) && (n <= 64)) {
		bits_rev(7, ((254 + 10) - 256));
		bits_rev(5, 11);
		bits(7, ((273 + ((n - 10 - 35) >> 3)) - 256));

		bits_rev(7, ((273 + ((n - 10 - 35) >> 3)) - 256));
		bits(3, ((n - 10 - 35) & 7));

		bits_rev(5, 11);
		bits(4, (n - 48 - 1));

		steal = 5;

	} else {
		errx(1, "%u too large for repeat", n);
	}

	bits_rev((7 - steal), 0);
}

static void
generate(const uint8_t *const head, const size_t n_head,
    const uint8_t *const tail, const size_t n_tail)
{
	const size_t unit = 5;

	/* Print the head.  */
	literal(n_head);
		bytes(head, n_head);

	/* Print code to print the head followed by its literal command.  */
	literal(unit + n_head + unit);
		literal(n_head);
			bytes(head, n_head);
		literal(unit + n_head + unit);

	/* Repeat what we just printed.  */
	repeat(unit + n_head + unit);

	/* Print the last repeat command.  */
	literal(unit);
		repeat(unit + n_head + unit);

	/* Print the last literal command.  */
	literal(unit);
		literal(unit);

	/* Print the four commands: repeat, literal, literal, print four.  */
	literal(4 * unit);
		repeat(unit + n_head + unit);
		literal(unit);
			literal(unit);
		literal(4 * unit);

	/* Repeat the last four commands.  */
	repeat(4 * unit);

	/* Print the four commands: repeat, literal, repeat, literal.  */
	literal(4 * unit);
		repeat(4 * unit);
		literal(4 * unit);
			repeat(4 * unit);
			literal(4 * unit);

	/* Repeat the last four commands.  */
	repeat(4 * unit);

	/* Print the four commands: repeat, literal, literal, literal.  */
	literal(4 * unit);
		repeat(4 * unit);
		literal(0);
		literal(0);
		literal(unit + unit + n_tail);

	/* Repeat the last four commands.  */
	repeat(4 * unit);

	/* Two no-ops for padding.  */
	literal(0);
	literal(0);

	/* Print code to print the tail.  */
	literal(unit + unit + n_tail);
		repeat(unit + unit + n_tail);
		state.final = true;
		literal(n_tail);
			bytes(tail, n_tail);
		state.final = false;

	/* Repeat the last two commands.  */
	repeat(unit + unit + n_tail);

	/* Print the tail.  */
	state.final = true;
	literal(n_tail);
		bytes(tail, n_tail);
}

int
main(const int argc, char **const argv)
{
	const uint8_t head[] = {
		0xa0,		/* pkt hdr, old fmt, compressed, 1-octet len */
		0xb4,		/* length: 180 octets */
		0x01,		/* compression alg: raw DEFLATE */
	};
	const size_t n_head = sizeof(head);
	const uint8_t tail[] = { 0 };
	const size_t n_tail = sizeof(tail);

	(void)argc;		/* ignore */
	(void)argv;		/* ignore */

	bytes(head, n_head);
	generate(head, n_head, tail, n_tail);
	bytes(tail, n_tail);

	return (0);
}