/* This is a simple program which encodes a stream of valid HTTP/1.1 requests
 * into a binary stream specified in draft-tarreau-httpbis-network-friendly.
 *
 * Input stream is passed on stdin as a series of consecutive HTTP requests
 * possibly reassembled from a TCP stream. The converted binary stream is
 * emitted on stdout.
 *
 * It's some experimental code, error handling is barely existent. The parser
 * will stop as soon as it doesn't understand something.
 */

/* for strptime() */
#define _XOPEN_SOURCE 500

#include <arpa/inet.h>
#include <stdarg.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#include <time.h>
#include <unistd.h>

#define LINE_LEN 16384
#define OUT_LEN 16384

static char line[LINE_LEN];

/* stats */
static int input_lines;
static int input_bytes;
static int output_bytes;
static int full_headers;
static int delta_headers;
static int delta_headers_savings;
static int removed_headers;
static int delta_uri;
static int delta_uri_savings;
static int cached_headers;
static int cached_headers_savings;
static int compressed_dates;
static int compressed_dates_savings;

static unsigned char block[OUT_LEN];

/* names for known methods, IDs 16..31 */
const struct known_meth {
	int l;            /* method length */
	const char m[8];  /* method name   */
} known_meth[] = {
	{ 7, "OPTIONS" },
	{ 3, "GET"     },
	{ 4, "HEAD"    },
	{ 4, "POST"    },
	{ 3, "PUT"     },
	{ 6, "DELETE"  },
	{ 5, "TRACE"   },
	{ 7, "CONNECT" },
	{ 0, "" }, /* end */
};

/* common headers sorted by frequency as found in ~100k req/rep messages */
const struct known_hdr {
	int l;            /* field name length */
	const char *n;    /* field name   */
} known_hdr[] = {
	{ 10, "connection" },
	{  4, "date" },
	{  6, "server" },
	{ 12, "content-type" },
	{ 14, "content-length" },
	{ 13, "last-modified" },
	{  4, "etag" },
	{ 13, "accept-ranges" },
	{ 15, "x-forwarded-for" },
	{ 10, "user-agent" },
	{  6, "accept" },
	{ 15, "accept-language" },
	{ 15, "accept-encoding" },
	{  7, "referer" },
	{ 13, "cache-control" },
	{  6, "cookie" },
	{  7, "expires" },
	{  6, "pragma" },
	{  3, "p3p" },
	{ 10, "set-cookie" },
	{  4, "vary" },
	{ 14, "accept-charset" },
	{ 16, "content-encoding" },
	{  5, "x-pad" },
	{  6, "ua-cpu" },
	{ 10, "keep-alive" },
	{  6, "credit" },
	{  3, "via" },
	{ 17, "if-modified-since" },
	{ 13, "if-none-match" },
	{ 17, "transfer-encoding" },
	{  8, "location" },
	{ 18, "x-forwarded-server" },
	{ 16, "x-forwarded-host" },
	{  7, "cookie2" },
	{  5, "allow" },
	{  2, "te" },
	{ 10, "x-pageview" },
	{  4, "from" },
	{ 13, "x-wap-profile" },
	{  8, "disallow" },
	{ 20, "x-authenticated-user" },
	{ 11, "x-client-ip" },
	{ 13, "content-range" },
	{  9, "client-ip" },
	{  0, "" }, /* end */
};

struct hdr {
	int nlen;         /* field name length if <128, or number if >=128 */
	char *name;       /* field name if length < 128, lowercase */
	int vlen;         /* field value length */
	char *val;        /* field value */
	struct hdr *next;
};

struct req {
	int e;            /* 0:no entity follows; 1:entity follows */
	int meth;         /* meth len-1 if <= 15; meth ID otherwise */
	char *meth_name;  /* method name (plain text, if meth <= 15) */
	int origuri_len;  /* original URI length (as requested) */
	char *origuri;    /* original URI prefixed */
	int ver;          /* 0=1.0, 1=1.1, 2=2.0, 3=other */
	int uri_len;      /* URI length */
	char *uri;        /* URI prefixed with "http://" and Host field value */
	struct hdr *hdr_list;
};

/* returns the number of bytes common between the two strings starting from
 * the left.
 */
int strcom(const char *s1, const char *s2)
{
	long l = -1;
	do { l++; } while (s1[l] == s2[l] && s1[l]);
	return l;
}

/* returns the number of bytes common between the two memory areas,
 * starting from the left.
 */
int memcom(const char *s1, const char *s2, int len)
{
	long l = -1;
	do { l++; } while (s1[l] == s2[l] && l < len);
	return l;
}

/* reads one line, strips the trailing CR/LF and returns the remaining length,
 * 0 if the line is empty, or -1 if the end was reached.
 */
static int get_line(FILE *stream)
{
	char *ret;

	if (!(ret = fgets(line, LINE_LEN, stream)))
		return -1;
	input_lines++;

	while (ret < line + LINE_LEN && *ret) {
		if (*ret == '\r' || *ret == '\n') {
			*ret = '\0';
			break;
		}
		ret++;
	}
	input_bytes += ret - line + 2;
	return ret - line;
}

char *memprintf(char **out, const char *format, ...)
{
	va_list args;
	char *ret = NULL;
	int allocated = 0;
	int needed = 0;

	do {
		/* vsnprintf() will return the required length even when the
		 * target buffer is NULL. We do this in a loop just in case
		 * intermediate evaluations get wrong.
		 */
		va_start(args, format);
		needed = vsnprintf(ret, allocated, format, args) + 1;
		va_end(args);

		if (needed <= allocated)
			break;

		allocated = needed;
		ret = realloc(ret, allocated);
	} while (ret);

	if (needed < 0) {
		/* an error was encountered */
		free(ret);
		ret = NULL;
	}

	if (out) {
		free(*out);
		*out = ret;
	}

	return ret;
}

/* given a valid request line, it returns pointers to meth, uri, ver. All
 * will be zero-terminated at the end. Returns the number of non-empty
 * elements found.
 */
static int parse_req_line(char *ptr, char **meth, char **uri, char **ver)
{
	int ret = 0;

	/* meth */
	for (*meth = ptr; *ptr && *ptr != ' '; ptr++);
	if (!*ptr || ptr == *meth)
		return ret;
	*ptr++ = '\0';
	ret++;

	/* uri */
	for (*uri = ptr; *ptr && *ptr != ' '; ptr++);
	if (!*ptr || ptr == *uri)
		return ret;
	*ptr++ = '\0';
	ret++;

	/* ver */
	for (*ver = ptr; *ptr && *ptr != ' '; ptr++);
	if (ptr == *ver)
		return ret;
	*ptr = '\0';
	ret++;

	return ret;
}

/* given a valid header field line, it returns a pointer to its name, the name
 * length, a pointer to the value and the value length. Folding is not supported.
 * Returns non-zero unless a parsing error is encountered (eg: space caused by
 * traffic reassembly consecutive to a broken capture).
 */
static int parse_hdr_line(char *ptr, char **name, int *nlen, char **val, int *vlen)
{
	int ret = 0;

	/* field name */
	for (*name = ptr; *ptr != ':'; ptr++)
		if (*ptr == ' ' || !*ptr)
			return ret; /* corrupted entry */
	*nlen = ptr - *name;
	*ptr++ = '\0';
	ret++;

	while (*ptr == ' ') ptr++;

	/* field value */
	for (*val = ptr; *ptr; ptr++);
	*vlen = ptr - *val;
	*ptr++ = '\0';
	ret++;

	return ret;
}

int find_meth_id(int len, const char *meth)
{
	int id;

	for (id = 0; known_meth[id].l; id++) {
		if (known_meth[id].l != len)
			continue;
		if (strcmp(known_meth[id].m, meth) == 0)
			return id + 16;
	}
	return 0;
}

int find_hdr_id(int len, const char *name)
{
	int id;

	for (id = 0; known_hdr[id].l; id++) {
		if (known_hdr[id].l != len)
			continue;
		if (strcasecmp(known_hdr[id].n, name) == 0)
			return id + 128;
	}
	return 0;
}

struct req *prepare_req(const char *meth, const char *uri, const char *ver)
{
	struct req *req;
	int len;

	req = calloc(1, sizeof(*req));

	/* retrieve version */
	while (*ver && *ver != '/')
		ver++;

	/* we have /1.1 here now */
	len = strlen(ver);
	if (len != 4 || ver[2] != '.')
		goto fail;

	req->ver = 2 * (ver[1] - '0' - 1) + (ver[3] - '0');
	if (req->ver < 0 || req->ver > 2)
		goto fail;

	/* retrieve meth */
	len = strlen(meth);
	if (len > 16)
		goto fail;

	if (!(req->meth = find_meth_id(len, meth))) {
		req->meth = len - 1;
		req->meth_name = strdup(meth);
	}

	/* retrieve URI */
	len = strlen(uri);
	req->origuri_len = len;
	req->origuri = strdup(uri);
	return req;

 fail:
	free(req);
	return NULL;
}

struct hdr *append_hdr(struct req *req, const char *name, int nlen, const char *val, int vlen)
{
	struct hdr **head = &req->hdr_list;
	struct hdr *hdr;
	char *p;

	if (nlen > 128)
		return NULL;

	while (*head)
		head = &(*head)->next;

	hdr = calloc(1, sizeof(*hdr));

	if (!(hdr->nlen = find_hdr_id(nlen, name))) {
		/* unknown header, store it in plain text and lower case */
		hdr->nlen = nlen;
		hdr->name = strdup(name);
		for (p = hdr->name; *p; p++)
			*p = tolower(*p);
	}

	hdr->vlen = vlen;
	hdr->val = strdup(val);
	*head = hdr;
	return hdr;
}

void destroy_req(struct req *req)
{
	struct hdr *hdr, *hdr_next;

	if (!req)
		return;

	//fprintf(stderr, "meth_name=%d (%s)\n", req->meth, req->meth_name);
	free(req->meth_name);
	//fprintf(stderr, "origuri=%s\n", req->origuri);
	free(req->origuri);
	//fprintf(stderr, "uri=%s\n", req->uri);
	free(req->uri);

	for (hdr = req->hdr_list; hdr; hdr = hdr_next) {
		//fprintf(stderr, "hdr_name=%d (%s)\n", hdr->nlen, hdr->name);
		free(hdr->name);
		//fprintf(stderr, "hdr_val=%d (%s)\n", hdr->vlen, hdr->val);
		free(hdr->val);
		hdr_next = hdr->next;
		free(hdr);
	}
	free(req);
}

/* emit the variable length and return the pointer to the next byte */
static unsigned char *emit_length(unsigned char *p, int l)
{
	if (l < 128)
		*p++ = l;
	else {
		*p++ = 0x80 + (l >> 8);
		*p++ = l & 255;
	}
	return p;
}

/* Encoding of header list.
 *
 * header-list    = *( header-field ) end-of-hdr
 * header-field   = field-name field-value
 * field-name     = common-hdr / rare-hdr / rsvd-hdr
 * field-value    = common-length length-prefix *( octet )
 * rare-hdr       = hdr-len token  ; token is [hdr-len] octets
 * hdr-len        = %x01-7F        ; header names may be up to 127 bytes long
 * common-hdr     = %x80-FE        ; 127 possible header names
 * rsvd-hdr       = %xFF           ; for future extensions if needed.
 * end-of-hdr     = %x00           ; this was the last header.
 *
 */

static unsigned char *dump_hdr(unsigned char *p, struct hdr *hdr)
{
	/* common-hdr or hdr-len */
	*p = hdr->nlen;
	if (hdr->nlen < 128) {
		/* rare-hdr */
		memcpy(p, hdr->name, hdr->nlen);
		p += hdr->nlen;
	}

	p = emit_length(p, 0); /* no common part */
	p = emit_length(p, hdr->vlen);
	if (hdr->vlen) {
		memcpy(p, hdr->val, hdr->vlen);
		p += hdr->vlen;
	}
	full_headers++;
	return p;
}

static unsigned char *dump_hdr_delta(unsigned char *p, struct hdr *hdr, int com)
{
	/* common-hdr or hdr-len */
	*p = hdr->nlen;
	if (hdr->nlen < 128) {
		/* rare-hdr */
		memcpy(p, hdr->name, hdr->nlen);
		p += hdr->nlen;
	}

	p = emit_length(p, com); /* emit common part */
	p = emit_length(p, hdr->vlen - com);
	if (hdr->vlen != com) {
		memcpy(p, hdr->val + com, hdr->vlen - com);
		p += hdr->vlen - com;
	}
	delta_headers++;
	delta_headers_savings += com;
	return p;
}

static unsigned char *dump_removed_hdr(unsigned char *p, struct hdr *hdr)
{
	/* common-hdr or hdr-len */
	*p = hdr->nlen;
	if (hdr->nlen < 128) {
		/* rare-hdr */
		memcpy(p, hdr->name, hdr->nlen);
		p += hdr->nlen;
	}

	p = emit_length(p, 0);
	p = emit_length(p, 0);
	removed_headers++;
	return p;
}

/* Encoding of request frame
 *
 *        0 1 2 3 4 5 6 7
 *       +---+------------+
 *       | V | frame-type |
 *       +---+------------+
 *
 *   V stands for the HTTP version.  Possible values for these 2 bits are:
 *      - 00: HTTP/1.0
 *      - 01: HTTP/1.1
 *      - 10: HTTP/2.0
 *      - 11: other version
 *
 *   This is followed by the following frame length encoded on 3 bytes.
 *
 *        0 1 2 3 4 5 6 7
 *       +-+-+---+-------+
 *       |E|M|R 0| METH  |  R=relative URI to previous one
 *       +-+-+---+-------+
 *       | optional-meth |
 *       |     (0-16)    |
 *       +---------------+
 *       | length-prefix |
 *       |     (1-2)     |
 *       +---------------+
 *       | URI (1-32767) |
 *       +---------------+
 *       |  header-list  |
 *       |   (variable)  |
 *       +---------------+
 */
static unsigned char *dump_whole_req(unsigned char *p, struct req *req)
{
	struct hdr *hdr;
	unsigned char *p_init = p;

	*p++ = (req->ver << 6) | 0x02; /* frame-type = req */
	/* p[1..3] = frame size, filled at the end */
	p += 3;
	*p++ = ((req->meth & 0x10) << 2) | (req->meth & 0xF); /* E/M/00/METH */
	if (req->meth < 16) { /* need to store plain text meth name */
		memcpy(p, req->meth_name, req->meth + 1);
		p += req->meth + 1;
	}
	/* uri prefixed by length */
	p = emit_length(p, req->uri_len);
	memcpy(p, req->uri, req->uri_len);
	p += req->uri_len;

	/* headers */
	for (hdr = req->hdr_list; hdr; hdr = hdr->next)
		p = dump_hdr(p, hdr);
	*p++ = 0; /* end of header list */

	/* message size */
	p_init[1] = (p - p_init - 4) >> 16;
	p_init[2] = (p - p_init - 4) >> 8;
	p_init[3] = (p - p_init - 4) >> 0;

	return p;
}

static unsigned char *dump_second_req(unsigned char *p, struct req *req, struct req *prev)
{
	struct hdr *hdr, *hdr0;
	unsigned char *p_init = p;
	int com;

	*p++ = (req->ver << 6) | 0x02; /* frame-type = req */
	/* p[1..3] = frame size, filled at the end */
	p += 3;
	*p++ = ((req->meth & 0x10) << 2) | (req->meth & 0xF); /* E/M/00/METH */
	if (req->meth < 16) { /* need to store plain text meth name */
		memcpy(p, req->meth_name, req->meth + 1);
		p += req->meth + 1;
	}
	/* uri prefixed by length and possibly common length */
	com = strcom(req->uri, prev->uri);
	if (com > 2) {
		*p_init |= 0x20;
		p = emit_length(p, com); /* emit common part length */
		p = emit_length(p, req->uri_len - com); /* and replaced part */
		if (com < req->uri_len)
			memcpy(p, req->uri + com, req->uri_len - com); /* emit only changes */
		p += req->uri_len - com;
		delta_uri++;
		delta_uri_savings += com;
	}
	else {
		p = emit_length(p, req->uri_len);
		memcpy(p, req->uri, req->uri_len);
		p += req->uri_len;
	}

	/* added headers */
	for (hdr = req->hdr_list; hdr; hdr = hdr->next) {
		for (hdr0 = prev->hdr_list; hdr0; hdr0 = hdr0->next) {
			if (hdr->nlen != hdr0->nlen)
				continue;
			if (hdr->nlen < 128 && strcmp(hdr->name, hdr0->name) != 0)
				continue;
			/* we found the same field name */
#if 0
			if (hdr->vlen != hdr0->vlen)
				continue;
			if (memcmp(hdr->val, hdr0->val, hdr->vlen) != 0)
				continue;
			/* OK we have the same value too */
#endif
			break;
		}
		if (!hdr0) /* only dump when different */
			p = dump_hdr(p, hdr);
		else if (hdr->vlen != hdr0->vlen || memcmp(hdr->val, hdr0->val, hdr->vlen) != 0) {
			com = memcom(hdr->val, hdr0->val, hdr->vlen);
			p = dump_hdr_delta(p, hdr, com);
		}
		else {
			cached_headers++;
			cached_headers_savings += hdr->vlen + 2; /* at least name + length */
		}
	}
	/* removed headers */
	for (hdr0 = req->hdr_list; hdr0; hdr0 = hdr0->next) {
		for (hdr = prev->hdr_list; hdr; hdr = hdr->next) {
			if (hdr->nlen != hdr0->nlen)
				continue;
			if (hdr->nlen < 128 && memcmp(hdr->name, hdr0->name, hdr->vlen) != 0)
				continue;
			/* we found the same field name */
			break;
		}
		if (!hdr) /* previous header was removed */
			p = dump_removed_hdr(p, hdr0);
	}
	*p++ = 0; /* end of header list */

	/* message size */
	p_init[1] = (p - p_init - 4) >> 16;
	p_init[2] = (p - p_init - 4) >> 8;
	p_init[3] = (p - p_init - 4) >> 0;

	return p;
}

/* Parses a flow of request messages. Returns the number of messages read. */
static int parse_messages(FILE *stream)
{
	int ret, msg;
	char *meth, *uri, *ver;
	char *name, *val;
	int nlen, vlen;
	struct req *req, *prev_req;
	unsigned char *end;

	req = prev_req = NULL;
	for (msg = 0; ; msg++) {
		/* wait for request line */
		while (!(ret = get_line(stream)));
		if (ret == -1)
			return msg;

		ret = parse_req_line(line, &meth, &uri, &ver);
		if (ret != 3)
			return msg;

		//fprintf(stderr, "meth=<%s> uri=<%s> ver=<%s>\n", meth, uri, ver);
		req = prepare_req(meth, uri, ver);
		if (!req)
			return msg;

		/* loop over header fields */
		while (1) {
			ret = get_line(stream);
			if (ret == -1) /* truncated message */
				return msg;
			if (ret == 0) /* end of header fields */
				break;

			ret = parse_hdr_line(line, &name, &nlen, &val, &vlen);
			if (!ret)
				return msg; /* parse error */
			//fprintf(stderr, "  name=<%s:%d> value=<%s:%d>\n", name, nlen, val, vlen);

			/* special case for the Host header */
			if (nlen == 4 && strcasecmp(name, "Host") == 0) {
				if (req->uri_len)
					return msg; /* duplicate host header */
				memprintf(&req->uri, "http://%s%s", val,
					  *req->origuri == '/' ? req->origuri : "");
				req->uri_len = strlen(req->uri);
			}
			else if (nlen == 17 && strcasecmp(name, "if-modified-since") == 0) {
				/* re-encode as binary */
				struct tm tm;
				time_t t;
				// Note: 64b is overkill, it's 585k years with microsecond resolution.
				//uint64_t t2;
				uint32_t t2;


				memset(&tm, 0, sizeof(tm));
				strptime(val, "%a, %d %b %Y %H:%M:%S %Z", &tm);
				t = mktime(&tm);

				if (sizeof(t2) == sizeof(uint64_t)) {
					t2 = t * 1000000;
					t2 = htonl((t2 >> 16) >> 16) + htonl(t2 & 0xFFFFFFFFU);
				} else {
					t2 = htonl(t);
				}
				if (!append_hdr(req, name, nlen, (char *)&t2, sizeof(t2)))
					return msg;
				compressed_dates++;
				compressed_dates_savings += vlen - sizeof(t2);
			}
			else {
				if (!append_hdr(req, name, nlen, val, vlen))
					return msg;
			}
		}

		if (!prev_req)
			end = dump_whole_req(block, req);
		else
			end = dump_second_req(block, req, prev_req);

		destroy_req(prev_req);
		prev_req = req;
		if (write(1, block, end - block) < 0) /* ignore errors here */;
		output_bytes += end - block;
		//fprintf(stderr, "\n");
	}
	destroy_req(req);
}

int main(int argc, char **argv)
{
	int ret;
	FILE *in = stdin;

	if (argc > 1) {
		in = fopen(argv[1], "r");
		if (!in) {
			perror("fopen");
			exit(1);
		}
	}

	ret = parse_messages(in);

	fprintf(stderr, "Stats:\n");
	fprintf(stderr, "  Messages: %d\n", ret);
	fprintf(stderr, "  Input bytes: %d (%d/msg)\n", input_bytes, (input_bytes+ret/2)/ret);
	fprintf(stderr, "  Output bytes: %d (%d/msg)\n", output_bytes, (output_bytes+ret/2)/ret);
	fprintf(stderr, "  Compression ratio: %2.1f (%2.1f %% saved)\n",
		1.0 * input_bytes / output_bytes,
		100 - 100.0 * output_bytes / input_bytes);
	fprintf(stderr, "  Input lines: %d (%d/msg)\n", input_lines, (input_lines+ret/2)/ret);
	fprintf(stderr, "  Full headers sent: %d\n", full_headers);
	fprintf(stderr, "  Partial headers sent: %d\n", delta_headers);
	fprintf(stderr, "  Partial headers savings: %d bytes\n", delta_headers_savings);
	fprintf(stderr, "  Removed headers sent: %d\n", removed_headers);
	fprintf(stderr, "  Cached headers not sent: %d\n", cached_headers);
	fprintf(stderr, "  Cached headers savings: %d bytes\n", cached_headers_savings);
	fprintf(stderr, "  Partial URIs sent: %d\n", delta_uri);
	fprintf(stderr, "  Partial URIs savings: %d bytes\n", delta_uri_savings);
	fprintf(stderr, "  Compressed date headers: %d\n", compressed_dates);
	fprintf(stderr, "  Compressed dates savings: %d bytes\n", compressed_dates_savings);
	exit(0);
}