//#include "fz_buffer.h"
#include <stdint.h>
#include <stdlib.h>

/*
	fz_buffer is a wrapper around a dynamically allocated array of bytes.

	Buffers have a capacity (the number of bytes storage immediately
	available) and a current size.
*/
typedef struct fz_buffer_s
{
	unsigned char *data;
	unsigned int cap, len;
	//int unused_bits;
} fz_buffer;

fz_buffer *
fz_new_buffer(unsigned int size)
{
	fz_buffer *b = malloc(sizeof(fz_buffer));
	size = size >= 4096 ? size : 4096;
	b->data = malloc(size);
	b->cap = size;
	b->len = 0;
	return b;
}

void
fz_free_buffer(fz_buffer *buf)
{
	if (!buf)
		return;
    free(buf->data);
    free(buf);
}

static inline unsigned int nearest_power(unsigned int x) {
    unsigned int ret = 2;
    __asm__ volatile("or $1, %1 \n\t"
             "bsr %1, %%ecx \n\t"
             "movl $2, %0 \n\t"
             "shl %%cl, %0 \n\t"
             :"=a"(ret) : "D"(x) : "%rcx");
    return ret;
}

void
fz_ensure_buffer(fz_buffer *buf, unsigned int min)
{
	unsigned int newsize = ((min > buf->cap) ? min : buf->cap);
    if (buf->cap > min) return;
    newsize = nearest_power(2*newsize);
	buf->data = realloc(buf->data, newsize);
	buf->cap = newsize;
}

/* Fax G3/G4 tables */

typedef struct
{
	unsigned short code;
	unsigned short nbits;
} cfe_code;

typedef struct {
	cfe_code termination[64];
	cfe_code makeup[41];
} cf_runs;

/* Define the end-of-line code. */
static const cfe_code cf_run_eol = {1, 12};

/* Define the 2-D run codes. */
static const cfe_code cf2_run_pass = {0x1, 4};
static const cfe_code cf2_run_vertical[7] =
{
	{0x3, 7},
	{0x3, 6},
	{0x3, 3},
	{0x1, 1},
	{0x2, 3},
	{0x2, 6},
	{0x2, 7}
};
static const cfe_code cf2_run_horizontal = {1, 3};

/* White run codes. */
static const cf_runs cf_white_runs =
{
	/* Termination codes */
	{
		{0x35, 8}, {0x7, 6}, {0x7, 4}, {0x8, 4},
		{0xb, 4}, {0xc, 4}, {0xe, 4}, {0xf, 4},
		{0x13, 5}, {0x14, 5}, {0x7, 5}, {0x8, 5},
		{0x8, 6}, {0x3, 6}, {0x34, 6}, {0x35, 6},
		{0x2a, 6}, {0x2b, 6}, {0x27, 7}, {0xc, 7},
		{0x8, 7}, {0x17, 7}, {0x3, 7}, {0x4, 7},
		{0x28, 7}, {0x2b, 7}, {0x13, 7}, {0x24, 7},
		{0x18, 7}, {0x2, 8}, {0x3, 8}, {0x1a, 8},
		{0x1b, 8}, {0x12, 8}, {0x13, 8}, {0x14, 8},
		{0x15, 8}, {0x16, 8}, {0x17, 8}, {0x28, 8},
		{0x29, 8}, {0x2a, 8}, {0x2b, 8}, {0x2c, 8},
		{0x2d, 8}, {0x4, 8}, {0x5, 8}, {0xa, 8},
		{0xb, 8}, {0x52, 8}, {0x53, 8}, {0x54, 8},
		{0x55, 8}, {0x24, 8}, {0x25, 8}, {0x58, 8},
		{0x59, 8}, {0x5a, 8}, {0x5b, 8}, {0x4a, 8},
		{0x4b, 8}, {0x32, 8}, {0x33, 8}, {0x34, 8}
	},

	/* Make-up codes */
	{
		{0, 0} /* dummy */ , {0x1b, 5}, {0x12, 5}, {0x17, 6},
		{0x37, 7}, {0x36, 8}, {0x37, 8}, {0x64, 8},
		{0x65, 8}, {0x68, 8}, {0x67, 8}, {0xcc, 9},
		{0xcd, 9}, {0xd2, 9}, {0xd3, 9}, {0xd4, 9},
		{0xd5, 9}, {0xd6, 9}, {0xd7, 9}, {0xd8, 9},
		{0xd9, 9}, {0xda, 9}, {0xdb, 9}, {0x98, 9},
		{0x99, 9}, {0x9a, 9}, {0x18, 6}, {0x9b, 9},
		{0x8, 11}, {0xc, 11}, {0xd, 11}, {0x12, 12},
		{0x13, 12}, {0x14, 12}, {0x15, 12}, {0x16, 12},
		{0x17, 12}, {0x1c, 12}, {0x1d, 12}, {0x1e, 12},
		{0x1f, 12}
	}
};

/* Black run codes. */
static const cf_runs cf_black_runs =
{
	/* Termination codes */
	{
		{0x37, 10}, {0x2, 3}, {0x3, 2}, {0x2, 2},
		{0x3, 3}, {0x3, 4}, {0x2, 4}, {0x3, 5},
		{0x5, 6}, {0x4, 6}, {0x4, 7}, {0x5, 7},
		{0x7, 7}, {0x4, 8}, {0x7, 8}, {0x18, 9},
		{0x17, 10}, {0x18, 10}, {0x8, 10}, {0x67, 11},
		{0x68, 11}, {0x6c, 11}, {0x37, 11}, {0x28, 11},
		{0x17, 11}, {0x18, 11}, {0xca, 12}, {0xcb, 12},
		{0xcc, 12}, {0xcd, 12}, {0x68, 12}, {0x69, 12},
		{0x6a, 12}, {0x6b, 12}, {0xd2, 12}, {0xd3, 12},
		{0xd4, 12}, {0xd5, 12}, {0xd6, 12}, {0xd7, 12},
		{0x6c, 12}, {0x6d, 12}, {0xda, 12}, {0xdb, 12},
		{0x54, 12}, {0x55, 12}, {0x56, 12}, {0x57, 12},
		{0x64, 12}, {0x65, 12}, {0x52, 12}, {0x53, 12},
		{0x24, 12}, {0x37, 12}, {0x38, 12}, {0x27, 12},
		{0x28, 12}, {0x58, 12}, {0x59, 12}, {0x2b, 12},
		{0x2c, 12}, {0x5a, 12}, {0x66, 12}, {0x67, 12}
	},

	/* Make-up codes. */
	{
		{0, 0} /* dummy */ , {0xf, 10}, {0xc8, 12}, {0xc9, 12},
		{0x5b, 12}, {0x33, 12}, {0x34, 12}, {0x35, 12},
		{0x6c, 13}, {0x6d, 13}, {0x4a, 13}, {0x4b, 13},
		{0x4c, 13}, {0x4d, 13}, {0x72, 13}, {0x73, 13},
		{0x74, 13}, {0x75, 13}, {0x76, 13}, {0x77, 13},
		{0x52, 13}, {0x53, 13}, {0x54, 13}, {0x55, 13},
		{0x5a, 13}, {0x5b, 13}, {0x64, 13}, {0x65, 13},
		{0x8, 11}, {0xc, 11}, {0xd, 11}, {0x12, 12},
		{0x13, 12}, {0x14, 12}, {0x15, 12}, {0x16, 12},
		{0x17, 12}, {0x1c, 12}, {0x1d, 12}, {0x1e, 12},
		{0x1f, 12}
	}
};

static inline int
getbit(const unsigned char *buf, int x)
{
	/* Invert bit to handle BlackIs1=false */
	return ( ( buf[x >> 3] >> ( 7 - (x & 7) ) ) & 1 ) ^ 1;
}

static inline int
find_changing(const unsigned char *line, int x, int w)
{
	int a, b;

	if (!line || x >= w)
		return w;

	if (x == -1)
	{
		a = 0;
		x = 0;
	}
	else
	{
		a = getbit(line, x);
		x++;
	}
	while (x < w)
	{
		b = getbit(line, x);
		if (a != b)
			break;
		x++;
	}

	return x;
}

static inline int
find_changing_color(const unsigned char *line, int x, int w, int color)
{
	if (!line || x >= w)
		return w;
	x = find_changing(line, x, w);
	if (x < w && getbit(line, x) != color)
		x = find_changing(line, x, w);
	return x;
}

static inline int
getrun(const unsigned char *line, int x, int w, int c)
{
	int z = x;
	while (z < w)
	{
		int b = getbit(line, z);
		if (c != b)
			break;
		++z;
	}
	return z - x;
}

void fz_append_bits(fz_buffer *buf, unsigned int *unused, unsigned int val, int bits)
{
    unsigned int unused_bits = *unused;
	int shift;

	/* Throughout this code, the invariant is that we need to write the
	 * bottom 'bits' bits of 'val' into the stream. On entry we assume
	 * that val & ((1<<bits)-1) == val, but we do not rely on this after
	 * having written the first partial byte. */

	if (bits == 0)
		return;

	/* buf->len always covers all the bits in the buffer, including
	 * any unused ones in the last byte, which will always be 0.
	 * buf->unused_bits = the number of unused bits in the last byte.
	 */

	/* Find the amount we need to shift val up by so that it will be in
	 * the correct position to be inserted into any existing data byte. */
	shift = ((int)unused_bits - bits);

	/* Extend the buffer as required before we start; that way we never
	 * fail part way during writing. If shift < 0, then we'll need -shift
	 * more bits. */
	if (shift < 0) {
		int extra = (7-shift)>>3; /* Round up to bytes */
		fz_ensure_buffer(buf, buf->len + extra);
	}

	/* Write any bits that will fit into the existing byte */
	if (unused_bits) {
		buf->data[buf->len-1] |= (shift >= 0 ? (val<<shift) : (val>>-shift));
		if (shift >= 0) {
			/* If we were shifting up, we're done. */
            *unused = unused_bits - bits;
			return;
		}
		/* The number of bits left to write is the number that didn't
		 * fit in this first byte. */
		bits = -shift;
	}

	/* Write any whole bytes */
	while (bits >= 8) {
		bits -= 8;
		buf->data[buf->len++] = val>>bits;
	}

	/* Write trailing bits (with 0's in unused bits) */
	if (bits > 0) {
		bits = 8-bits;
		buf->data[buf->len++] = val<<bits;
	}
	*unused = bits;
}

static inline void
putcode(fz_buffer *out, unsigned int *b, const cfe_code *run)
{
	fz_append_bits(out, b, run->code, run->nbits);
}

static void
putrun(fz_buffer *out, unsigned int *b, int run, int c)
{
	const cf_runs *codetable = c ? &cf_black_runs : &cf_white_runs;
	if (run > 63) {
		int m = run >> 6;
		while (m > 40)
		{
			putcode(out, b, &codetable->makeup[40]);
			m -= 40;
		}
		if (m > 0)
			putcode(out, b, &codetable->makeup[m]);
    }
	putcode(out, b, &codetable->termination[run & 63]);
}

fz_buffer *
fz_compress_ccitt_fax_g4(const unsigned char *src, int columns, int rows)
{
	int stride = (columns + 7) >> 3;
    unsigned int unused_bits = 0;
	fz_buffer *out = fz_new_buffer((stride * rows) >> 3);
	const unsigned char *ref = NULL;

	while (rows-- > 0)
	{
		unsigned int c = 0;
		int a0 = -1;

		while (a0 < columns)
		{
			int a1 = find_changing(src, a0, columns);
			int b1 = find_changing_color(ref, a0, columns, c^1);
			int b2 = find_changing(ref, b1, columns);
			int diff = b1 - a1;
			if (a0 < 0)
				a0 = 0;

			/* pass mode */
			if (b2 < a1) {
				putcode(out, &unused_bits, &cf2_run_pass);
				a0 = b2;
			/* vertical mode */
			} else if (diff >= -3 && diff <= 3) {
				putcode(out, &unused_bits, &cf2_run_vertical[diff + 3]);
				a0 = a1;
				c = c^1;
			/* horizontal mode */
			} else {
				int a2 = find_changing(src, a1, columns);
				putcode(out, &unused_bits, &cf2_run_horizontal);
				putrun(out, &unused_bits, a1 - a0, c);
				putrun(out, &unused_bits, a2 - a1, c^1);
				a0 = a2;
			}
		}
        //if (encoded_byte_align) { fz_append_bits(out, &unused_bits, 0, 8-unused_bits); }

		ref = src;
		src += stride;
	}

	putcode(out, &unused_bits, &cf_run_eol);
	putcode(out, &unused_bits, &cf_run_eol);

	return out;
}

fz_buffer *
fz_compress_ccitt_fax_g3(const unsigned char *src, int columns, int rows)
{
	int i, stride = (columns + 7) >> 3;
    unsigned int unused_bits = 0;
	fz_buffer *out = fz_new_buffer((stride * rows) >> 3);

	while (rows-- > 0)
	{
        unsigned int c = 0;
		int a0 = 0;
		while (a0 < columns)
		{
			int run = getrun(src, a0, columns, c);
			putrun(out, &unused_bits, run, c);
			a0 += run;
			c = c^1;
		}
        fz_append_bits(out, &unused_bits, 0, 8 - unused_bits);
		src += stride;
	}

	for (i = 0; i < 6; ++i)
		putcode(out, &unused_bits, &cf_run_eol);

	return out;
}

#include <unistd.h>
uint8_t *slurp_file(char *path, uint64_t *filesize);

int main(int argc, char **argv)
{
    uint64_t sz;
    uint8_t *infile = slurp_file(argv[1], &sz);
    uint32_t w = strtoul(infile+3, &infile, 10);
    uint32_t h = strtoul(infile, &infile, 10);
    fz_buffer *b = fz_compress_ccitt_fax_g4(infile+1, w, h);
    write(1, b->data, b->len);
    fz_free_buffer(b);
    return 0;
}