/************************************************************************\
* Portable pixmap to C64 FLI converter 26-Sep-92                         *
* By Pasi 'Albert' Ojala (c) 1991-1998                                   *
*    albert@cs.tut.fi  albert@cc.tut.fi                                  *
*                                                                        *
* 26-Sep-92 Changed the palette a bit                                    *
* 02-Jan-92 Color error propagation to next line also (when dithering)   *
* 08-Jan-94 Now takes the maxval into account                            *
* 05-Sep-94 New palette, 'pure' ANSI-C                                   *
* 22-Jan-95 De-tabified to TAB setting 8                                 *
* 01-Feb-95 Now also reads from stdin                                    *
* 18-Jul-96 Faster color selection (precalculation of rgb->color mapping)*
* 12-Jan-98 Added contrast and brightness controls                       *
* 24-Apr-98 Reduced the memory consumption by reading one line at a time *
*           Added FLI color sorting for better (potential) compression   *
*                                                                        *
\************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define FAST_COL


typedef unsigned char UBYTE;

#ifndef MAXINT
#define MAXINT 0x7FFFFFFF
#endif

char *vers="\0$VER: ppmtofli 1.7 (27.7.98)\n";

UBYTE	pic[200][160];	/* here we store the C64 color values */

/* Just some very quick & grude formulas */
#define Y(r,g,b) ((30*r+59*g+11*b)/100)
#define U(y,b)   (3*493*(b-y)/4096+128)
#define V(y,r)   (3*877*(r-y)/4096+128)

#define ERROR(y,y1,u,u1,v,v1) (abs(y-y1)+3*abs(u-u1)+3*abs(v-v1))


const UBYTE col[16][6] = {
/*    R   G   B     Y   U   V */
    {  0,  0,  0,    0,128,128},
    {240,240,240,  240,128,128},
    {240,  0,  0,   72,103,235},
    {  0,240,240,  168,153, 21},
    {240,  0,240,   98,179,219},
    {  0,240,  0,  141, 78, 38},
    {  0,  0,240,   26,205,112},
    {240,240,  0,  213, 52,145},
    {240, 96,  0,  128, 82,199},
    {160, 64,  0,   85, 98,176},
    {240,112,112,  150,115,185},
    { 80, 80, 80,   80,128,128},
    {128,128,128,  128,128,128},
    {144,240,144,  200,108, 93},
    {144,144,240,  154,159,122},
    {176,176,176,  176,128,128}
};


const UBYTE merge[16] = {	/* 01 -> 10 */
    0x00,	/* 0000 -> 0000 */
    0x02,	/* 0001 -> 0010 */
    0x02,	/* 0010 -> 0010 */
    0x03,	/* 0011 -> 0011 */
    0x08,	/* 0100 -> 1000 */
    0x0a,	/* 0101 -> 1010 */
    0x0a,	/* 0110 -> 1010 */
    0x0b,	/* 0111 -> 1011 */
    0x08,	/* 1000 -> 1000 */
    0x0a,	/* 1001 -> 1010 */
    0x0a,	/* 1010 -> 1010 */
    0x0b,	/* 1011 -> 1011 */
    0x0c,	/* 1100 -> 1100 */
    0x0e,	/* 1101 -> 1110 */
    0x0e,	/* 1110 -> 1110 */
    0x0f	/* 1111 -> 1111 */
};

const UBYTE swap[16] = {	/* 01 <-> 10 */
    0x00,	/* 0000 -> 0000 */
    0x02,	/* 0001 -> 0010 */
    0x01,	/* 0010 -> 0001 */
    0x03,	/* 0011 -> 0011 */
    0x08,	/* 0100 -> 1000 */
    0x0a,	/* 0101 -> 1010 */
    0x09,	/* 0110 -> 1001 */
    0x0b,	/* 0111 -> 1011 */
    0x04,	/* 1000 -> 0100 */
    0x06,	/* 1001 -> 0110 */
    0x05,	/* 1010 -> 0101 */
    0x07,	/* 1011 -> 0111 */
    0x0c,	/* 1100 -> 1100 */
    0x0e,	/* 1101 -> 1110 */
    0x0d,	/* 1110 -> 1101 */
    0x0f	/* 1111 -> 1111 */
};

const char *colornames[] = {
    "black",
    "white",
    "red",
    "cyan",
    "purple",
    "green",
    "blue",
    "yellow",
    "orange",
    "brown",
    "light red",
    "dark gray",
    "gray",
    "light green",
    "light blue",
    "light gray"
};

#define MODE_USEBGCOLOR		1 /* will use bgcolor */
#define MODE_USEWHOLESCREEN	2 /* will convert the leftmost 12 pixels too */
#define MODE_MERGE		4 /* will merge FLI colors, if it means less error */
#define MODE_VERBOSE		8

#define STAT_ERROR		32
#define STAT_USAGE		64

int Convert(char *name, int mode, int lumratio);


int main(int argc, char *argv[]) {
    UBYTE *a, *buffer, color, apu[100], *b, ty, tv, tu;
    int i, x, y, error, temp, width, height, w, h;
    int brightness=0, contrast=0, dither=0, lumratio=7;
    int status=0, shift=0, maxval;
    FILE *inFp;
    char *inFile = NULL, *outFile = NULL;
#ifdef FAST_COL
    static UBYTE closest[16][16][16];
#endif

    for (i=1; i<argc; i++) {
	if (argv[i][0]=='-') {
	    x = 1;
	    while (argv[i][x]) {
		switch (argv[i][x]) {
		case 'b':
		    brightness = atoi(argv[i]+x+1);
		    if (brightness<-255 || brightness>255) {
			fprintf(stderr, "Brightness should be -255..255!\n");
			brightness = 0;
			status |= STAT_ERROR;
		    }
		    x = strlen(argv[i])-1;
		    break;
		case 'c':
		    contrast = atoi(argv[i]+x+1);
		    if (contrast<-100 || contrast>100) {
			fprintf(stderr, "Contrast should be -100..100!\n");
			contrast = 0;
			status |= STAT_ERROR;
		    }
		    x = strlen(argv[i])-1;
		    break;
		/* dither -d<value> , default value is 5 */
		case 'd':
		    if (!(dither = atoi(argv[i]+x+1)))
			dither = 5;
		    x = strlen(argv[i])-1;
		    break;
		case 'l':
		    lumratio = atoi(argv[i]+x+1);
		    if (lumratio<0 || lumratio>20) {
			fprintf(stderr,"Luminance ration should be 0..20!\n");
			status |= STAT_ERROR;
		    }
		    x = strlen(argv[i])-1;
		    break;
		/* use the whole screen */
		case 'w':
		    status |= MODE_USEWHOLESCREEN;
		    break;
		/* use the background color */
		case 'a':
		    status |= MODE_USEBGCOLOR;
		    break;
		/* use merge mode */
		case 'm':
		    status |= MODE_MERGE;
		    break;
		/* shift the picture */
		case 's':
		    shift = 12;
		    break;
		case 'v':
		    status |= MODE_VERBOSE;
		    break;
		default:
		    status |= STAT_ERROR;
		    break;
		}
		x++;
	    }
	    if ((status & STAT_ERROR)) {
		fprintf(stderr, "Error in the options!\n");
		break;
	    }
	} else if (!inFile) {
	    inFile = argv[i];
	} else if(!outFile) {
	    outFile = argv[i];
	} else {
	    status |= STAT_ERROR;
	    fprintf(stderr, "Too many filenames!\n");
	    break;
	}
    }

    if ((status & STAT_ERROR)) {
	fprintf(stderr, "%s\n",vers+7);
	fprintf(stderr, "Usage: %s [-vmbswd<val> -l<val>] [ppmfile] [flifile]\n",argv[0]);
	fprintf(stderr, "       d = do a simple dither in the color conversion\n");
	fprintf(stderr, "       l = the importance of luminance in color conversion (0..20), default 7\n");
	fprintf(stderr, "       b = brighten or darken the picture (-255..255), default 0\n");
	fprintf(stderr, "       c = increase the contrast (-100..100 [0%%..200%%), default 0\n");
	fprintf(stderr, "       w = use the 12 leftmost pixels too (will use approximation)\n");
	fprintf(stderr, "       s = shift the picture before converting\n");
	fprintf(stderr, "       a = use the background colors in the conversion\n");
	fprintf(stderr, "       m = merge FLI colors if it means less errors\n");
	fprintf(stderr, "       v = verbose, output extra information about the process\n");
	exit(5);
    }
    if (!outFile)
	fprintf(stderr, "No output filename - outputting to stdout\n");

    if (!inFile) {
	fprintf(stderr, "Reading from stdin\n");
	inFp = stdin;
    } else {
	if (!(inFp = fopen(inFile, "rb"))) {
	    fprintf(stderr, "Could not open %s for reading\n", inFile);
	    return EXIT_FAILURE;
	}
    }

    fgets((char *)apu, 100, inFp);
    if (strncmp((char *)apu, "P6", 2)) {
	if (inFp != stdin)
	    fclose(inFp);
	fprintf(stderr, "Don't know how to handle this type of ppm ..(%s)\n", apu);
	return EXIT_FAILURE;
    }
    fgets((char *)apu, 100, inFp);
    width = atoi((char *)apu);
    i = 0;
    while (apu[i]!=' ' && apu[i]!='\t' && apu[i])
	i++;
    height = atoi((char *)apu+i);
    fprintf(stderr, "Input file seems to be %d x %d\n", width, height);
    fgets((char *)apu, 100, inFp);	/* just get the maxval..*/
    maxval = atoi((char *)apu)+1;
    if (maxval<1 || maxval>256)
	maxval = 256;

    /*
	Reduced the memory consumption to 2* 3*width bytes.
	The first line has the line color data.
	The second line has the old 'residual'.
     */

    if (!(buffer = (UBYTE *)calloc(3*width * 2, 1))) {
	if (inFp != stdin)
	    fclose(inFp);
	fprintf(stderr, "Memory allocation error (%d bytes)\n", 2* 3*width);
	return EXIT_FAILURE;
    }
    if (width>160-shift || height>200)
	fprintf(stderr, "Output picture will be sized %d x 200\n", 160-shift);

    w = width;
    h = height;
    if (w<=149)
	shift = 12;
    if (w>160-shift)
	w = 160-shift;
    if (h>200)
	h = 200;

#ifdef FAST_COL
    fflush(stderr);
    for (x=0; x<255; x+=16) {
	for (y=0; y<255; y+=16) {
	    int z;

	    for (z=0; z<255; z+=16) {
		/* Target YUV */
		ty = Y(x,y,z);
		tu = U(ty,z);
		tv = V(ty,x);

		error = MAXINT;
		color = 0;
		for (i=0; i<16; i++) {
		    temp = ERROR(lumratio*ty, lumratio*col[i][3],
				 tu, col[i][4],
				 tv, col[i][5]);
		    if (temp<error) {
			color = i;
			error = temp;
		    }
		}
		closest[x/16][y/16][z/16] = color;
	    }
	}
    }
#endif

    if (brightness || contrast) {
	if (brightness>0)
	    fprintf(stderr, "Brightening the picture by %d\n", brightness);
	if (brightness<0)
	    fprintf(stderr, "Darkening the picture by %d\n", -brightness);
	if (contrast)
	    fprintf(stderr, "Adjusting the contrast to %3d%%\n", 100+contrast);
    }

    fprintf(stderr, "Converting colors");
#ifndef FAST_COL
    fprintf(stderr, "\n");
#endif
    fflush(stderr);
    for (y=0; y<h; y++) {
	if (!fread((char *)buffer, 3*width, 1, inFp))
	    fprintf(stderr, "Short file! Result may be quite original.. \n");

	if (maxval != 256 || brightness || contrast) {
	    for (i=3*width-1;i>=0;i--) {
		temp = 256*buffer[i]/maxval;
		temp = ((temp + brightness)-128)*(100+contrast)/100 + 128;
		if (temp<0)
		    temp = 0;
		else if (temp>255)
		    temp = 255;
		buffer[i] = temp;
	    }
	}
	a = buffer;		/* Current line */
	for (x=0; x<w; x++) {
	    int cr, cg, cb;

	    b = a + 3*width;	/* Residual line */
	    cr = *a + *(signed char *)b;
	    cg = *(a+1) + *(signed char *)(b+1);
	    cb = *(a+2) + *(signed char *)(b+2);

	    /* Saturate */
	    if (cr>255)
		cr = 255;
	    else if(cr<0)
		cr = 0;
	    if (cg>255)
		cg = 255;
	    else if(cg<0)
		cg = 0;
	    if (cb>255)
		cb = 255;
	    else if (cb<0)
		cb = 0;
#ifdef FAST_COL
	    color = closest[cr/16][cg/16][cb/16];
#else
	    /* Target YUV */
	    ty = Y(cr,cg,cb);
	    tu = U(ty,cb);
	    tv = V(ty,cr);

	    error = MAXINT;
	    for (i=0;i<16;i++) {
		temp = ERROR(lumratio*ty,lumratio*col[i][3],
			     tu,col[i][4],
			     tv,col[i][5]);
		if (temp < error) {
		    color = i;
		    error = temp;
		    if (error<8)	/* we are very satisfied if the error is less than .. */
			break;
		}
	    }
#endif
	    pic[y][x+shift] = color;

	    if (dither && x < w-1) {
		/* First propagate forwards */
		b = a+3;
		temp = (cr - col[color][0])/dither/2 + *b;
		if (temp>=0 && temp<256)
		    *b = temp;
		b++;
		temp = (cg - col[color][1])/dither/2 + *b;
		if (temp>=0 && temp<256)
		    *b = temp;
		b++;
		temp = (cb - col[color][2])/dither/2 + *b;
		if (temp>=0 && temp<256)
		    *b = temp;
#if 1
		b = a + 3*width;
		/* Then propagate to next line */
		*(b+0) = (cr - col[color][0])/dither/2;
		*(b+1) = (cg - col[color][1])/dither/2;
		*(b+2) = (cb - col[color][2])/dither/2;
#endif
	    }
	    a += 3;
	}
#ifdef FAST_COL
	if ((y&7)==7)
	    fprintf(stderr, ".");
#else
	fprintf(stderr, "\rLine %d", y);
#endif
	fflush(stderr);
    }
    if (inFp != stdin)
	fclose(inFp);

    fprintf(stderr,"\n");
    free(buffer);

    if (shift)
	fprintf(stderr, "Shifting the picture by %d pixels\n", shift);

    return Convert(outFile, status, lumratio);
}



int Convert(char *name,int mode,int lumratio) {
    int x, y, memind, ind, pos, bits;
    int d[4], e, error, g[4], approx[256], appr=0, start=12;
    UBYTE *BASE,a,b,c;
    UBYTE *colmemhist[16];	/* [16][1024]*/
    UBYTE *linehist[16];	/* [16][256] */
    UBYTE *gfxmem;		/* [8192]    */
    UBYTE *chrmems;		/* [8192]    */
    UBYTE *colmem;		/* [1024]    */
    UBYTE *bgcol;		/* [256]     */
    FILE *handle;
    static const UBYTE bitmask[4]  = {0x3f, 0xcf, 0xf3, 0xfc};
    static const UBYTE bitshift[4] = {0x40, 0x10, 0x04, 0x01};

    if ((mode & MODE_USEWHOLESCREEN))
	start = 0;

#define ALLOC_SIZE	(37*1024+256)		/* size of the allocation */

    if ((BASE = (UBYTE *)calloc(ALLOC_SIZE, 1))) {
	/* initialize the pointers */
	for (x=0;x<16;x++)
	    colmemhist[x] = BASE+x*1024;
	for (x=0;x<16;x++)
	    linehist[x] = BASE+16*1024+x*256;
	gfxmem = BASE+16*1024+16*256;
	chrmems = gfxmem+8192;
	colmem = chrmems+8192;
	bgcol = colmem+1024;

	for (y=0; y<256; y++)
	    approx[y] = 0;

	fprintf(stderr, "Making histogram (matrix)\n");
	for (y=0; y<200; y++) {
	    for (x=0; x<40; x++) {
		int cnt = 1;
		a = pic[y][4*x+0];
		b = pic[y][4*x+1];
		c = pic[y][4*x+2];
		e = pic[y][4*x+3];

		if (b!=a)
		    cnt++;
		if (c!=a && c!=b)
		    cnt++;
		if (e!=a && e!=b && e!=c)
		    cnt++;
		/* if there is 3 or 4 colors in the line, count them. */
		/* if there is 0..2 colors, we can use the FLI colors */
		/* and there is no need to use color memory ! */
		if (cnt>2) {
		    ind = x + (y/8)*40;
		    colmemhist[a][ind] += 1;
		    colmemhist[b][ind] += 1;
		    colmemhist[c][ind] += 1;
		    colmemhist[e][ind] += 1;
		}
	    }
	}

	fprintf(stderr, "Selecting colors for color memory.\n");
	for (y=0; y<1000; y++) {
	    if (y%40 < 3) {
		/* FLI has a 'feature' in the first three char columns (12 pixels) */
		/* bitpair 11 will be brown, 01 and 10 will be light gray          */
		/* here we select those colors - conversion will try to use them   */
		colmem[y] = 0x09;
		chrmems[y] = chrmems[y+1024] = chrmems[y+2048] = 0xff;
		chrmems[y+3072] = chrmems[y+4096] = chrmems[y+5120] = 0xff;
		chrmems[y+6144] = chrmems[y+7168] = 0xff;
	    } else {
		a = b = 0;
		for (x=1; x<16; x++) {
		    /* we take the color that is used mostly as the third color  */
		    /* or the best possible in that respect, 0=black don't count */

		    /*	TODO: select the color that is used in most *lines*
			      in the 4x8 pixel area
			TODO2: select the color that is used in most lines
			       over the whole width, then remove those cells
			       that don't have that color. ??
		     */
		    if (colmemhist[x][y] > a) {
			a = colmemhist[x][y];
			b = x;
		    }
		}
		colmem[y] = b;
		chrmems[y] = chrmems[y+1024] = chrmems[y+2048] = 17*b;
		chrmems[y+3072] = chrmems[y+4096] = chrmems[y+5120] = 17*b;
		chrmems[y+6144] = chrmems[y+7168] = 17*b;
	    }
	}

	if ((mode & MODE_USEBGCOLOR)) {
	    fprintf(stderr, "Making histograph (line)\n");
	    for (y=0; y<200; y++) {
		/* if the color is not in color memory, count it to line history */
		/* Even if it is black */
		for (x=0; x<160/4; x++) {
		    int a0 = pic[y][4*x],
			a1 = pic[y][4*x+1],
			a2 = pic[y][4*x+2],
			a3 = pic[y][4*x+3];

		    if (colmem[x/4+(y/8)*40] != a0)
			linehist[a0][y]++;
		    if (a1 != a0 && colmem[x/4+(y/8)*40] != a1)
			linehist[a0][y]++;
		    if (a2 != a1 && a2 != a0 && colmem[x/4+(y/8)*40] != a2)
			linehist[a0][y]++;
		    if (a3 != a2 && a3 != a1 && a3 != a0 && colmem[x/4+(y/8)*40] != a3)
			linehist[a0][y]++;
		}
	    }
	    fprintf(stderr, "Selecting background colors\n");
	    for (y=0; y<200; y++) {
		a = b = 0;
		/* we pick the most used color in the line */
		for (x=0; x<16; x++) {
		    if (linehist[x][y]>a) {
			a = linehist[x][y];
			b = x;
		    }
		}
		bgcol[y+6] = b;
	    }
	}
	fprintf(stderr, "Creating FLI-picture\n");
	for (y=0; y<200; y++) {
	    for (x=start; x<160; x++) {
		ind = x/4+(y/8)*40;	/* color memory index */
		pos = y%8+ind*8;	/* grafix memory byte */
		bits = (x%4);		/* bit numbers */
		memind = (y%8)*1024+ind;
		a = chrmems[memind];

		c = pic[y][x];
		if (c == bgcol[y+6]) {
		    b = 0;
		} else if (c == colmem[ind]) {
		    /* MUST BE here, not after b=1 and 2 !!! */
		    b = 3;
		} else if (c == (a&15)) {
		    b = 2;
		} else if (c == (a/16)) {
		    b = 1;
		} else {
		    if ((a&15) == colmem[ind]) {
			b = 2;
			chrmems[memind] = (a & 0xf0) | c;
		    } else if ((a/16) == colmem[ind] /*|| (a/16)==(a&15)*/) {
			b = 1;
			chrmems[memind] = (a & 0x0f) | (16*c);
		    } else {
			g[0] = e = bgcol[y+6];
			d[0] = ERROR(lumratio*col[e][3], lumratio*col[c][3],
				     col[e][4], col[c][4],
				     col[e][5], col[c][5]);
			g[1] = e = a/16;
			d[1] = ERROR(lumratio*col[e][3], lumratio*col[c][3],
				     col[e][4], col[c][4],
				     col[e][5], col[c][5]);
			g[2] = e = a&15;
			d[2] = ERROR(lumratio*col[e][3], lumratio*col[c][3],
				     col[e][4], col[c][4],
				     col[e][5], col[c][5]);
			g[3] = e = colmem[ind];
			d[3] = ERROR(lumratio*col[e][3], lumratio*col[c][3],
				     col[e][4], col[c][4],
				     col[e][5], col[c][5]);
			error = d[0] + d[1] + d[2] + d[3];
			b = 0;
			for (e=0; e<4; e++) {
			    if (d[e]<error) {
				b = e;
				error = d[e];
			    }
			}
			if (x>12 && (mode & MODE_MERGE)) {
			    /* check if FLI color merge will cause less error */
			    e = ERROR(lumratio*col[a/16][3], lumratio*col[a&15][3],
				     col[a/16][4], col[a&15][4],
				     col[a/16][5], col[a&15][5]);
			    if (e<error) {
				gfxmem[pos] = (merge[gfxmem[pos]>>4]<<4)+merge[gfxmem[pos]&15];
				b = 1;
				chrmems[memind] = (a & 15) | (16*c);
				if ((mode & MODE_VERBOSE))
				    fprintf(stderr, "Merged %s -> %s\n", colornames[a/16], colornames[a&15]);
			    } else {
				appr = -1;
				++approx[c*16+g[b]];
			    }
			} else {
			    appr = -1;
			    ++approx[c*16+g[b]];
			}
		    }
		}
		gfxmem[pos] = (gfxmem[pos] & bitmask[bits]) | (bitshift[bits] * b);
#if 1
		if ((chrmems[memind]>>4) > (chrmems[memind] & 15)) {
		    /* Sort the FLI colors for better compressibility */
		    chrmems[memind] = (chrmems[memind]>>4) | ((chrmems[memind] & 15)<<4);
		    gfxmem[pos] = (swap[gfxmem[pos]>>4]<<4)+swap[gfxmem[pos]&15];
		}
#endif
	    }
	}

	if ((mode & MODE_VERBOSE) && appr) {
	    int tot = 0;

	    fprintf(stderr, "Approximations:\n");
	    for (e=0; e<256; e++) {
		if (approx[e])
		    fprintf(stderr, "%4d %s -> %s\n", approx[e], colornames[e/16], colornames[e%16]);
		tot += approx[e];
	    }
	    fprintf(stderr, "%4d approximations total\n", tot);
	}
	if (name) {
	    fprintf(stderr, "Saving %s\n", name);
	    if ((handle = fopen(name, "wb"))) {
		fwrite("\000\073", 2, 1, handle); /* load address $3b00 */
		fwrite(bgcol, 256, 1, handle);
		fwrite(colmem, 1024, 1, handle);
		fwrite(chrmems, 8192, 1, handle);
		fwrite(gfxmem, 8000, 1, handle);
		fclose(handle);
		free(BASE);
		return 0;
	    }
	    fprintf(stderr, "Write failed!\n");
	    free(BASE);
	    return EXIT_FAILURE;
	}
	/* output to stdout */
	fwrite("\000\073", 2, sizeof(char), stdout); /* load address $3b00 */
	fwrite(bgcol, 256, sizeof(UBYTE), stdout);
	fwrite(colmem, 1024, sizeof(UBYTE), stdout);
	fwrite(chrmems, 8192, sizeof(UBYTE), stdout);
	fwrite(gfxmem, 8000, sizeof(UBYTE), stdout);
	free(BASE);
	return 0;
    }
    fprintf(stderr, "Memory allocation failed! (%d bytes)\n", ALLOC_SIZE);
    return EXIT_FAILURE;
}