#define _GNU_SOURCE	/* asprintf */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <ctype.h>
#include <getopt.h>
#include <iconv.h>
#include <errno.h>
#include <inttypes.h>
#include <sys/types.h>
#include <sys/stat.h>

#include <ft2build.h>
#include FT_FREETYPE_H
#include <freetype/ftsynth.h>


#define MAGIC 0xd2828e06

// 4 bits seem to be enough
#define GRAY_BITS 4
// 3 gave smallest file for about 16x16 pixel fonts, but it doesn't really matter much
#define GRAY_BIT_COUNT 3

#define MAX_GRAY ((1 << GRAY_BITS) - 3)
#define REP_BLACK (MAX_GRAY + 1)
#define REP_WHITE (MAX_GRAY + 2)

struct option options[] =
{
	{"add"			, 1, NULL, 'a'},
	{"add-charset"	, 1, NULL, 'c'},
	{"font"			, 1, NULL, 'f'},
	{"line-height"	, 1, NULL, 'l'},
	{"font-path"	, 1, NULL, 'p'},
	{"show"			, 0, NULL, 's'},
	{"add-text"		, 1, NULL, 't'},
	{"verbose"		, 0, NULL, 'v'},
	{"test"			, 0, NULL, 999}, 
	{}
};


typedef struct list_any_s
{
	struct list_any_s *next;
} list_any_t;

typedef struct
{
	void *start;
	void *end;
} list_t;

typedef struct n_set_s
{
	struct n_set_s *next;
	int first, last;
} n_set_t;

typedef struct
{
	unsigned size;
	unsigned char *data;
	unsigned real_size;
} file_data_t;

typedef struct __attribute((packed))
{
	uint32_t magic;
	uint32_t entries;
	int8_t height;
	int8_t baseline;
	int8_t line_height;
} font_header_t;

typedef struct font_s
{
	struct font_s *next;
	char *name;
	char *file_name;
	FT_Face face;
	int size;
	int prop;
	int space_width;
	int dy;
	list_t chars; /* n_set_t */
	unsigned used: 1; /* font is actually used */
	unsigned ok: 1;
	unsigned bold: 1;
	unsigned nobitmap: 1;
	unsigned autohint: 2; /* 0: auto, 1: off, 2: on */
} font_t;

typedef struct char_data_s
{
	struct char_data_s *next;
	unsigned ok: 1; /* char exists */
	int c; /* char (utf32) */
	font_t *font; /* pointer to font */
	int x_advance;
	int x_ofs; /* where to draw lower left bitmap corner */
	int y_ofs;
	unsigned char *bitmap; /* char bitmap, width x height */
	int bitmap_width;
	int bitmap_height;
	unsigned char *data;
	int data_len;
} char_data_t;

list_t font_list; /* font_t */
list_t char_list; /* char_data_t */
list_t chars_missing; /* n_set_t */

int font_height;
int font_y_ofs;

struct
{
	int verbose;
	int test;
	int line_height;
	char *font_path;
	list_t chars; /* n_set_t */
	char *file;
	unsigned show: 1;
} opt;


file_data_t *read_file(char *name);
void dump_char(char_data_t *cd);
void add_data(file_data_t *d, void *buffer, unsigned size);
void write_data(file_data_t *d, char *name);
int intersect(int first0, int last0, int first1, int last1);
void insert_int_list(list_t *list, int first, int last);
void *add_list(list_t *list, void *entry);
void *new_mem(size_t size);
char *new_str(char *str);
int parse_int_list(list_t *list, char *str);
char *search_font(char *font_path, char *name);
void render_char(char_data_t *cd);
int empty_row(char_data_t *cd, int row);
int empty_column(char_data_t *cd, int column);
void add_bbox(char_data_t *cd);
void make_prop(char_data_t *cd);
char *utf32_to_utf8(int u8);
void add_bits(unsigned char *buf, int *buf_ptr, int bits, unsigned data);
unsigned read_unsigned_bits(unsigned char *buf, int *buf_ptr, int bits);
int read_signed_bits(unsigned char *buf, int *buf_ptr, int bits);
int signed_bits(int num);
int unsigned_bits(unsigned num);
void encode_char(char_data_t *cd);
int show_font(char *name);
/*
 * Get next token from string *stringp, where tokens are possibly-empty
 * strings separated by characters from delim.
 *
 * Writes NULs into the string at *stringp to end tokens.
 * delim need not remain constant from call to call.
 * On return, *stringp points past the last NUL written (if there might
 * be further tokens), or is NULL (if there are definitely no more tokens).
 *
 * If *stringp is NULL, strsep returns NULL.
 */
char *strsep(stringp, delim)register char **stringp;
register const char *delim;
{
	register char *s;
	register const char *spanp;
	register int c, sc;
	char *tok;

	if ((s =  *stringp) == NULL)
		return (NULL);
	for (tok = s;;)
	{
		c =  *s++;
		spanp = delim;
		do
		{
			if ((sc =  *spanp++) == c)
			{
				if (c == 0)
					s = NULL;
				else
					s[ - 1] = 0;
				*stringp = s;
				return (tok);
			}
		}
		while (sc != 0);
	}
	/* NOTREACHED */
}

int main(int argc, char **argv)
{
	int i, j, k, err, ofs;
	char *str,  *str1,  *t,  *s,  *s1,  *font_spec;
	iconv_t ic = (iconv_t) - 1, ic2;
	char obuf[4], ibuf[6];
	char obuf2[4 *0x100], ibuf2[0x100];
	char *obuf_ptr,  *ibuf_ptr;
	size_t obuf_left, ibuf_left;
	FILE *f;
	font_t *font;
	n_set_t *n;
	char_data_t *cd;
	FT_Library ft_lib;
	font_header_t fh;
	file_data_t font_file = {};
	unsigned char char_ofs[5];

	opt.font_path = (char*)malloc(sizeof(char)*(strlen(getenv("WINDIR")) + 7));
	strcpy(opt.font_path, getenv("WINDIR"));
	opt.font_path = strcat(opt.font_path, "\\FONTS");

	opterr = 0;

	while ((i = getopt_long(argc, argv, "a:c:f:l:p:st:v", options, NULL)) !=  - 1)
	{
		switch (i)
		{
			case 'a':
				err = parse_int_list(&opt.chars, optarg);
				if (err)
				{
					fprintf(stderr, "%s: invalid char range spec\n", optarg);
					return 1;
				}
				break;

			case 'c':
				ic2 = iconv_open("UTF-32LE", optarg);
				if (ic2 == (iconv_t) - 1)
				{
					fprintf(stderr, "don't know char set %s\ntry 'iconv --list'\n", optarg);
					return 1;
				}
				ibuf_ptr = ibuf2;
				ibuf_left = sizeof ibuf2;
				obuf_ptr = obuf2;
				obuf_left = sizeof obuf2;
				for (j = 0; j < sizeof ibuf2; j++)
					ibuf2[j] = j;
				iconv(ic2, &ibuf_ptr, &ibuf_left, &obuf_ptr, &obuf_left);
				for (str = obuf2; str < obuf_ptr; str += 4)
				{
					i = *(int*)str;
					if (i >= 0x20)
						insert_int_list(&opt.chars, i, i);
				}
				iconv_close(ic2);
				break;

			case 'f':
				font = add_list(&font_list, new_mem(sizeof *font));
				font_spec = new_str(optarg);

				if ((s = strchr(font_spec, ':')))
				{
					font->name = new_mem(s - font_spec + 1);
					memcpy(font->name, font_spec, s - font_spec);
					t = s + 1;
					err = 0;
					while (!err && (str = strsep(&t, ":")))
					{
						if ((s = strchr(str, '=')))
						{
							*s++ = 0;
							if (!strcmp(str, "size"))
							{
								font->size = strtol(s, &s1, 0);
								if (*s1)
									err = 1;
							}
							else if (!strcmp(str, "prop"))
							{
								font->prop = strtol(s, &s1, 0);
								if (*s1)
									err = 1;
							}
							else if (!strcmp(str, "space_width"))
							{
								font->space_width = strtol(s, &s1, 0);
								if (*s1)
									err = 1;
							}
							else if (!strcmp(str, "dy"))
							{
								font->dy = strtol(s, &s1, 0);
								if (*s1)
									err = 1;
							}
							else if (!strcmp(str, "bold"))
							{
								font->bold = strtol(s, &s1, 0);
								if (*s1)
									err = 1;
							}
							else if (!strcmp(str, "nobitmap"))
							{
								font->nobitmap = strtol(s, &s1, 0);
								if (*s1)
									err = 1;
							}
							else if (!strcmp(str, "autohint"))
							{
								font->autohint = strtol(s, &s1, 0) + 1;
								if (*s1)
									err = 1;
							}
							else if (!strcmp(str, "c"))
							{
								err = parse_int_list(&font->chars, s);
							}
							else
							{
								err = 1;
							}
						}
						else
						{
							if (*str)
								err = 1;
						}
					}
					free(font_spec);
					if (err)
					{
						fprintf(stderr, "%s: invalid font spec\n", optarg);
						return 1;
					}
				}
				else
				{
					font->name = font_spec;
				}
				break;

			case 'l':
				str = optarg;
				i = strtol(str, &str1, 0);
				if (*str1 || i < 0)
				{
					fprintf(stderr, "%s: invalid line height\n", str);
					return 1;
				}
				opt.line_height = i;
				break;

			case 'p':
				opt.font_path = optarg;
				break;

			case 's':
				opt.show = 1;
				break;

			case 't':
				if (ic == (iconv_t) - 1)
				{
					ic = iconv_open("UTF-32LE", "UTF-8");
					if (ic == (iconv_t) - 1)
					{
						fprintf(stderr, "can't convert utf8 data\n");
						return 1;
					}
				}
				if ((f = fopen(optarg, "r")))
				{
					int ok;

					ibuf_left = 0;
					while ((i = fread(ibuf + ibuf_left, 1, sizeof ibuf - ibuf_left, f)) > 0)
					{
						// fprintf(stderr, "ibuf_left = %d, fread = %d\n", ibuf_left, i);
						ibuf_ptr = ibuf;
						ibuf_left += i;
						do
						{
							obuf_ptr = obuf;
							obuf_left = sizeof obuf;
							k = iconv(ic, &ibuf_ptr, &ibuf_left, &obuf_ptr, &obuf_left);
							// fprintf(stderr, "k = %d, errno = %d, ibuf_left = %d, obuf_left = %d\n", k, k ? errno : 0, ibuf_left, obuf_left);
							if (k >= 0 || (k ==  - 1 && !obuf_left))
							{
								ok = 1;
								if (!obuf_left)
								{
									i = *(int*)obuf;
									if (i >= 0x20)
									{
										insert_int_list(&opt.chars, i, i);
									}
								}
							}
							else
							{
								ok = 0;
							}
						}
						while (ok && ibuf_left);
						if (k ==  - 1 && errno == EILSEQ)
						{
							perror("iconv");
							return 1;
						}
						if (ibuf_left)
						{
							memcpy(ibuf, ibuf + sizeof ibuf - ibuf_left, ibuf_left);
						}
					}
					fclose(f);
				}
				else
				{
					perror(optarg);
					return 1;
				}
				break;

			case 'v':
				opt.verbose++;
				break;

			case 999:
				opt.test++;
				break;
		}
	}

	if (ic != (iconv_t) - 1)
		iconv_close(ic);

	// use default char list
	if (!opt.chars.start)
		insert_int_list(&opt.chars, 0x20, 0x7f);

	argc -= optind;
	argv += optind;

	// FreeSans[size=16 prop=2 space_width=4 dy=16 c=0x1200,0x1000-0x2000]
	if (argc != 1)
	{
		fprintf(stderr, "Usage: mkblfont [options] fontfile\n""Build font for boot loader.\n""  -a, --add=first[-last]\n\tAdd chars from this range.\n""  -c, --add-charset=charset\n\tAdd all chars from this charset.\n""  -f, --font=font_spec\n\tUse this font. Spec format is fontname[option1 option2 ...]\n""  -h, --help\n\tShow this help text.\n""  -l, --line-height=n\n\tSet line height (default: font height).\n""  -p, --font-path=font path\n\tFont path, elements separated by ':'.\n""  -s, --show\n\tShow font info.\n""  -t, --add-text=samplefile\n\tAdd all chars used in this file. File must be UTF-8 encoded.\n""  -v, --verbose\n\tDump font info.\n");
		return 1;
	}

	opt.file = argv[0];

	if (opt.show)
		return show_font(opt.file);

	if ((err = FT_Init_FreeType(&ft_lib)))
	{
		fprintf(stderr, "FreeType init failed (err = %d)\n", err);
		return 3;
	}

	// open all fonts
	for (font = font_list.start; font; font = font->next)
	{
		font->file_name = search_font(opt.font_path, font->name);
		if (font->file_name)
		{
			err = FT_New_Face(ft_lib, font->file_name, 0, &font->face);
			if (!err)
			{
				if (!font->size)
				{
					if (font->face->num_fixed_sizes > 0)
					{
						font->size = font->face->available_sizes[0].height;
					}
				}
				if (font->size && !FT_Set_Pixel_Sizes(font->face, font->size, 0))
					font->ok = 1;
			}
		}
	}

	// print some info
	if (opt.verbose)
	{
		printf("Font List\n");
		for (font = font_list.start; font; font = font->next)
		{
			printf("  %s (%s)\n", font->name, font->ok ? "ok" : "not used");
			printf("    File %s\n", font->file_name);
			printf("    Size %d", font->size);
			if (font->dy)
				printf(", dY %d", font->dy);
			if (font->prop)
				printf(", Prop %d", font->prop);
			if (font->space_width)
				printf(", SpaceWidth %d", font->space_width);
			printf("\n");
			if (font->chars.start)
			{
				for (n = font->chars.start; n; n = n->next)
				{
					printf("    c 0x%04x", n->first);
					if (n->last != n->first)
						printf("-0x%04x", n->last);
					printf("\n");
				}
			}
		}
		printf("\n");
	}

	// print even more info
	if (opt.verbose >= 2)
	{
		printf("Requested Char List\n");
		for (n = opt.chars.start; n; n = n->next)
		{
			printf("  0x%04x", n->first);
			if (n->last != n->first)
				printf("-0x%04x", n->last);
			printf("\n");
		}
		printf("\n");
	}

	// build char list
	for (n = opt.chars.start; n; n = n->next)
	{
		for (i = n->first; i <= n->last; i++)
		{
			cd = add_list(&char_list, new_mem(sizeof *cd));
			cd->c = i;
		}
	}

	// just check the list is really sorted
	for (i =  - 1, cd = char_list.start; cd; cd = cd->next)
	{
		if (cd->c <= i)
		{
			fprintf(stderr, "internal error: char list not sorted\n");
			return 4;
		}
		i = cd->c;
	}

	// render all chars
	for (cd = char_list.start; cd; cd = cd->next)
	{
		render_char(cd);
	}

	FT_Done_FreeType(ft_lib);

	// fix vertical glyph positions
	for (cd = char_list.start; cd; cd = cd->next)
	{
		if (cd->ok)
			cd->y_ofs += cd->font->dy;
	}

	// get font dimensions
	font_height = font_y_ofs = 0;
	for (cd = char_list.start; cd; cd = cd->next)
	{
		if (cd->y_ofs < font_y_ofs)
			font_y_ofs = cd->y_ofs;
		i = cd->bitmap_height + cd->y_ofs;
		if (i > font_height)
			font_height = i;
	}

	font_height -= font_y_ofs;

	if (!opt.test)
		for (cd = char_list.start; cd; cd = cd->next)
			add_bbox(cd);

	for (cd = char_list.start; cd; cd = cd->next)
		make_prop(cd);

	for (i = j = 0, cd = char_list.start; cd; cd = cd->next)
	{
		if (!cd->ok)
			insert_int_list(&chars_missing, cd->c, cd->c);
	}

	for (cd = char_list.start; cd; cd = cd->next)
		encode_char(cd);

	memset(&fh, 0, sizeof fh);

	fh.magic = MAGIC;
	fh.height = font_height;
	fh.baseline =  - font_y_ofs;
	fh.line_height = opt.line_height ? : fh.height + 2;
	fh.entries = 0;

	for (cd = char_list.start; cd; cd = cd->next)
		if (cd->ok)
			fh.entries++;

	if (opt.verbose)
	{
		if (chars_missing.start)
		{
			printf("Missing Chars\n");
			for (n = chars_missing.start; n; n = n->next)
			{
				printf("  0x%04x", n->first);
				if (n->last != n->first)
					printf("-0x%04x", n->last);
				printf("\n");
			}
			printf("\n");
		}

		printf("Font Size\n  Height: %d\n  Baseline: %d\n  Line Height: %d\n\n", font_height,  - font_y_ofs, fh.line_height);

		for (cd = char_list.start; cd; cd = cd->next)
			dump_char(cd);
	}

	//  font_file.size=5;
	add_data(&font_file, &fh, sizeof fh);

	ofs = font_file.size + fh.entries * sizeof char_ofs;

	for (cd = char_list.start; cd; cd = cd->next)
	{
		if (!cd->ok)
			continue;
		i = 0;
		char_ofs[0] =  cd->c &0xff;
		char_ofs[1] = (cd->c >> 8) &0x000000ff;
		char_ofs[2] = (ofs &0x07) << 5;
		char_ofs[3] = (ofs >> 3) &0x000000ff;
		char_ofs[4] = (ofs >> 11) &0x000000ff;
		if (cd->c == 0x3f)
		{
			printf("0x%x\n", cd->data_len);
		}
		add_data(&font_file, char_ofs, sizeof char_ofs);
		ofs += cd->data_len;
	}

	for (cd = char_list.start; cd; cd = cd->next)
	{
		if (!cd->ok)
			continue;
		add_data(&font_file, cd->data, cd->data_len);
	}

	write_data(&font_file, opt.file);

	return 0;
}


file_data_t *read_file(char *name)
{
	file_data_t *fd;
	FILE *f;

	fd = new_mem(sizeof *fd);

	if (!name)
		return fd;

	f = fopen(name, "r");

	if (!f)
	{
		perror(name);
		return fd;
	}

	if (fseek(f, 0, SEEK_END))
	{
		perror(name);
		exit(30);
	}

	fd->size = fd->real_size = ftell(f);

	if (fseek(f, 0, SEEK_SET))
	{
		perror(name);
		exit(30);
	}

	if (fd->size)
	{
		fd->data = new_mem(fd->size);
		if (!fd->data)
		{
			fprintf(stderr, "malloc failed\n");
			exit(30);
		}
	}

	if (fread(fd->data, 1, fd->size, f) != fd->size)
	{
		perror(name);
		exit(30);
	}

	fclose(f);

	return fd;
}


void dump_char(char_data_t *cd)
{
	int i, j, y0, y1, y2, x0, x1, x2, width;
	unsigned char *p;
	char c;

	if (!cd || !cd->ok)
		return ;

	printf("Char 0x%04x '%s'\n", cd->c, utf32_to_utf8(cd->c));

	if (cd->font)
		printf("  Font: %s (%d)\n", cd->font->name, cd->font->size);

	printf("  Bitmap: %d x %d\n  Advance: %d\n  Offset: %d x %d\n", cd->bitmap_width, cd->bitmap_height, cd->x_advance, cd->x_ofs, cd->y_ofs);

	if (opt.verbose >= 2 && cd->data)
	{
		printf("  Data[%d]:", cd->data_len);
		for (i = 0; i < cd->data_len; i++)
		{
			if (!(i &7))
			{
				printf("\n   ");
			}
			printf(" %02x", cd->data[i]);
		}
		printf("\n");
	}

	if (cd->bitmap)
	{
		p = cd->bitmap;

		y0 = font_height + font_y_ofs;
		y1 = y0 - cd->bitmap_height - cd->y_ofs;
		y2 = y1 + cd->bitmap_height;

		x1 = cd->bitmap_width + cd->x_ofs;
		if (cd->x_advance > x1)
			x1 = cd->x_advance;

		if (cd->x_ofs < 0)
		{
			width = x1 - cd->x_ofs;
			x1 = 0;
			x0 =  - cd->x_ofs;
		}
		else
		{
			width = x1;
			x1 = cd->x_ofs;
			x0 = 0;
		}

		x2 = x1 + cd->bitmap_width;

		// printf("y0 = %d, y1 = %d, y2 = %d\n", y0, y1, y2);
		// printf("x0 = %d, x1 = %d, x2 = %d, width = %d\n", x0, x1, x2, width);

		printf("     ");
		c = ' ';
		for (i = 0; i < cd->x_advance + x0; i++)
		{
			if (i == x0)
				c = '_';
			printf("%c", c);
		}
		printf("\n");

		for (j = 0; j < font_height; j++)
		{
			printf("  %s", j == y0 - 1 ? "->|" : "  |");
			if (j < y1 || j >= y2)
			{
				for (i = 0; i < width; i++)
					printf(".");
			}
			else
			{
				for (i = 0; i < width; i++)
				{
					if (i < x1 || i >= x2)
					{
						printf(".");
					}
					else
					{
						c = p[(j - y1) *cd->bitmap_width + i - x1];
						if (c == 0)
						{
							c = ' ';
						}
						else if (c >= MAX_GRAY)
						{
							c = '#';
						}
						else
						{
							c += '0';
							if (c > '9')
								c += 'a' - '9' - 1;
						}
						printf("%c", c);
					}
				}
			}
			printf("|%s\n", j == y0 - 1 ? "<-" : "");
		}

		printf("     ");
		c = ' ';
		for (i = 0; i < cd->x_advance + x0; i++)
		{
			if (i == x0)
				c = '-';
			printf("%c", c);
		}
		printf("\n");
	}

	printf("\n");
}


void add_data(file_data_t *d, void *buffer, unsigned size)
{
	if (!size || !d || !buffer)
		return ;

	if (d->size + size > d->real_size)
	{
		d->real_size = d->size + size + 0x1000;
		d->data = realloc(d->data, d->real_size);
		if (!d->data)
			d->real_size = 0;
	}

	if (d->size + size <= d->real_size)
	{
		memcpy(d->data + d->size, buffer, size);
		d->size += size;
	}
	else
	{
		fprintf(stderr, "Oops, out of memory? Aborted.\n");
		exit(10);
	}
}


void write_data(file_data_t *d, char *name)
{
	FILE *f;

	f = strcmp(name, "-") ? fopen(name, "wb"): stdout;

	if (!f)
	{
		perror(name);
		return ;
	}

	if (fwrite(d->data, d->size, 1, f) != 1)
	{
		perror(name);
		exit(3);
	}

	fclose(f);
}


int intersect(int first0, int last0, int first1, int last1)
{
	return (first1 >= first0 && first1 <= last0 + 1) || (last1 >= first0 - 1 && last1 <= last0) || (first1 < first0 && last1 > last0);
}


void insert_int_list(list_t *list, int first, int last)
{
	n_set_t *n,  *p,  *next;

	for (n = list->start; n; n = n->next)
	{
		if (intersect(n->first, n->last, first, last))
		{
			if (first < n->first)
				n->first = first;
			if (last > n->last)
				n->last = last;
			break;
		}
	}

	if (!n)
	{
		 /* not joined */
		if (!(n = list->start) || first < n->first)
		{
			list->start = p = new_mem(sizeof *p);
			p->next = n;
			p->first = first;
			p->last = last;
		}
		else
		{
			for (n = list->start; n; n = n->next)
			{
				if (!n->next || first < n->next->first)
				{
					p = new_mem(sizeof *p);
					p->next = n->next;
					p->first = first;
					p->last = last;
					n->next = p;
					if (!p->next)
						list->end = p;
					break;
				}
			}
		}
	}

	for (n = list->start; n; n = next)
	{
		if (!(next = n->next))
			break;

		if (intersect(n->first, n->last, next->first, next->last))
		{
			if (next->first < n->first)
				n->first = next->first;
			if (next->last > n->last)
				n->last = next->last;
			n->next = next->next;
			if (!n->next)
				list->end = n;
			free(next);
			next = n;
		}
	}
}


void *add_list(list_t *list, void *entry)
{
	if (list->end)
	{
		((list_any_t*)list->end)->next = entry;
	}
	list->end = entry;

	if (!list->start)
	{
		list->start = entry;
	}

	return entry;
}


void *new_mem(size_t size)
{
	return calloc(size, 1);
}


char *new_str(char *str)
{
	return str ? strdup(str): str;
}


int parse_int_list(list_t *list, char *str)
{
	int err = 0, i, j, k;
	char *s,  *s1,  *t;

	list->start = list->end = NULL;

	if (!str)
		return 0;

	while (isspace(*str))
		str++;

	if (! *str)
		return 0;

	t = str = new_str(str);

	while ((s = strsep(&t, ",")))
	{
		if (sscanf(s, "%i - %i%n", &i, &j, &k) == 2 && k == strlen(s))
		{
			insert_int_list(list, i, j);
		}
		else
		{
			i = strtol(s, &s1, 0);
			if (*s1)
			{
				err = 1;
				break;
			}
			insert_int_list(list, i, i);
		}
	}

	free(str);

	return err;
}


char *search_font(char *font_path, char *name)
{
	int i, j;
	char *font_name = NULL;
	char *cur_path,  *sep,  *p;
	struct stat sbuf;
	static char *suffix[] =
	{
		"", ".ttc", ".ttf", ".pfa", ".pfb", ".pcf.gz"
	};

	if (!font_path || !name)
		return NULL;

	while (*font_path)
	{
		cur_path = strdup(font_path);

		if ((sep = strchr(cur_path, ';')))
			 *sep = 0;

		for (i = 0; i < sizeof suffix / sizeof * suffix; i++)
		{
			//      #asprintf(&font_name, "%s/%s%s", cur_path, name, suffix[i]);
			font_name = (char*)malloc(sizeof(char)*(strlen(cur_path) + strlen(name) + strlen(suffix[i]) + 2));
			if (font_name != NULL)
			{
				j = 0;
				p = cur_path;
				while (*p)	font_name[j++] =  *p++;
				font_name[j++] = 0x5c;
				p = name;
				while (*p)	font_name[j++] =  *p++;
				p = suffix[i];
				while (*p)	font_name[j++] =  *p++;
				font_name[j] = 0;
			}
			if (!stat(font_name, &sbuf) && S_ISREG(sbuf.st_mode)) break;
			free(font_name);
			font_name = NULL;
		}

		if (i < sizeof suffix / sizeof * suffix)
		{
			free(cur_path);
			break;
		}

		if (sep)
		{
			font_path += sep - cur_path + 1;
		}
		else
		{
			font_path = "";
		}

		free(cur_path);
	}

	return font_name;
}


void render_char(char_data_t *cd)
{
	font_t *font;
	n_set_t *n;
	int err, glyph_index;
	FT_GlyphSlot glyph;
	int i, j;
	unsigned char uc;

	for (font = font_list.start; font; font = font->next)
	{
		if (!font->ok)
			continue;
		if (font->chars.start)
		{
			for (n = font->chars.start; n; n = n->next)
			{
				if (cd->c >= n->first && cd->c <= n->last)
					break;
			}
			if (!n)
				continue;
		}
		glyph_index = FT_Get_Char_Index(font->face, cd->c);
		if (!glyph_index)
			continue;

		err = FT_Load_Char(font->face, cd->c, FT_LOAD_RENDER | (font->nobitmap ? FT_LOAD_NO_BITMAP : 0) | (font->autohint ? font->autohint == 1 ? FT_LOAD_NO_AUTOHINT : FT_LOAD_FORCE_AUTOHINT: 0));
		if (err)
			continue;

		cd->ok = 1;

		cd->font = font;

		glyph = font->face->glyph;
		if (cd->font->bold)
			FT_GlyphSlot_Embolden(glyph);

		cd->bitmap_width = glyph->bitmap.width;
		cd->bitmap_height = glyph->bitmap.rows;
		cd->bitmap = new_mem(cd->bitmap_width *cd->bitmap_height);

		cd->x_advance = glyph->advance.x / 64.;
		cd->x_ofs = glyph->bitmap_left;
		cd->y_ofs = glyph->bitmap_top - glyph->bitmap.rows;

		for (j = 0; j < cd->bitmap_height; j++)
		{
			for (i = 0; i < cd->bitmap_width; i++)
			{
				switch (glyph->bitmap.pixel_mode)
				{
					case FT_PIXEL_MODE_MONO:
						uc = ((glyph->bitmap.buffer[i / 8+j * glyph->bitmap.pitch] >> (7-(i &7))) &1) *MAX_GRAY;
						break;

					case FT_PIXEL_MODE_GRAY:
						uc = (glyph->bitmap.buffer[i + j * glyph->bitmap.pitch]*(MAX_GRAY + 1)) / (255+1);
						break;

					default:
						uc = 0;
				}
				cd->bitmap[i + j * cd->bitmap_width] = uc;
			}
		}

		#if 0
			printf("bitmap: mode %d, %d x %d, + %d x %d, advance %f x %f\n", glyph->bitmap.pixel_mode, glyph->bitmap.width, glyph->bitmap.rows, glyph->bitmap_left, glyph->bitmap_top, glyph->advance.x / 64., glyph->advance.y / 64.);

			printf("metrics:\n  size %f x %f\n  bearing %f x %f, advance %f\n", glyph->metrics.width / 64., glyph->metrics.height / 64., glyph->metrics.horiBearingX / 64., glyph->metrics.horiBearingY / 64., glyph->metrics.horiAdvance / 64.);
		#endif

		break;
	}
}


int empty_row(char_data_t *cd, int row)
{
	unsigned char *p1,  *p2;

	p2 = (p1 = cd->bitmap + row * cd->bitmap_width) + cd->bitmap_width;
	while (p1 < p2)
		if (*p1++)
			return 0;

	return 1;
}


int empty_column(char_data_t *cd, int col)
{
	int i;
	unsigned char *p;

	for (p = cd->bitmap + col, i = 0; i < cd->bitmap_height; i++, p += cd->bitmap_width)
	{
		if (*p)
			return 0;
	}

	return 1;
}


void add_bbox(char_data_t *cd)
{
	int i;
	unsigned char *bitmap;
	int width, height, dx, dy;

	if (!cd->ok)
		return ;

	width = cd->bitmap_width;
	height = cd->bitmap_height;
	dx = dy = 0;

	while (height && empty_row(cd, height - 1))
		height--;
	while (width && empty_column(cd, width - 1))
		width--;

	for (dx = 0; dx < width && empty_column(cd, dx); dx++)
		;
	for (dy = 0; dy < height && empty_row(cd, dy); dy++)
		;

	width -= dx;
	height -= dy;

	if (width != cd->bitmap_width || height != cd->bitmap_height)
	{
		bitmap = new_mem(width *height);

		for (i = 0; i < height; i++)
		{
			memcpy(bitmap + i * width, cd->bitmap + dx + (i + dy) *cd->bitmap_width, width);
		}

		free(cd->bitmap);
		cd->bitmap = bitmap;

		cd->x_ofs += dx;
		cd->y_ofs += cd->bitmap_height - height - dy;

		cd->bitmap_width = width;
		cd->bitmap_height = height;
	}
}


/*
 * Fake proprtionally spaced font from fixed size font.
 */
void make_prop(char_data_t *cd)
{
	int width;

	if (!cd->ok || !cd->font->prop)
		return ;

	width = cd->bitmap_width ? cd->bitmap_width + cd->font->prop: cd->font->space_width;
	cd->x_ofs = cd->font->prop;
	cd->x_advance = width;
}


char *utf32_to_utf8(int u8)
{
	static char buf[16];
	static iconv_t ic = (iconv_t) - 1;
	char *ibuf,  *obuf;
	size_t obuf_left, ibuf_left;
	int i;

	*buf = 0;

	if (ic == (iconv_t) - 1)
	{
		ic = iconv_open("UTF-8", "UTF-32LE");
		if (ic == (iconv_t) - 1)
		{
			fprintf(stderr, "Error: can't convert utf8 data.\n");
			exit(1);
		}
	}

	ibuf = (char*) &u8;
	obuf = buf;
	ibuf_left = 4;
	obuf_left = sizeof buf - 1;

	i = iconv(ic, &ibuf, &ibuf_left, &obuf, &obuf_left);

	if (i >= 0)
	{
		i = sizeof buf - 1-obuf_left;
		buf[i] = 0;
	}
	else
	{
		fprintf(stderr, "Warning: failed to convert 0x%x to utf8.\n", u8);
	}

	return buf;
}


void add_bits(unsigned char *buf, int *buf_ptr, int bits, unsigned data)
{
	int rem, ptr;

	while (bits > 0)
	{
		ptr =  *buf_ptr >> 3;
		rem = 8-(*buf_ptr &7);
		if (rem > bits)
			rem = bits;
		buf[ptr] = (buf[ptr] &((1 << (*buf_ptr &7)) - 1)) + ((data &((1 << rem) - 1)) << (*buf_ptr &7));
		*buf_ptr += rem;
		bits -= rem;
		data >>= rem;
	}
}


unsigned read_unsigned_bits(unsigned char *buf, int *buf_ptr, int bits)
{
	int rem, ptr;
	unsigned data = 0, dptr = 0;

	while (bits > 0)
	{
		ptr =  *buf_ptr >> 3;
		rem = 8-(*buf_ptr &7);
		if (rem > bits)
			rem = bits;
		data += ((buf[ptr] >> (*buf_ptr &7)) &((1 << rem) - 1)) << dptr;
		dptr += rem;
		*buf_ptr += rem;
		bits -= rem;
	}

	return data;
}


int read_signed_bits(unsigned char *buf, int *buf_ptr, int bits)
{
	int i;

	i = read_unsigned_bits(buf, buf_ptr, bits);

	if (bits == 0)
		return i;

	if ((i &(1 << (bits - 1))))
	{
		i +=  - 1 << bits;
	}

	return i;
}


int signed_bits(int num)
{
	int bits = 32;
	int val = num &(1 << 31);

	if (num == 0)
		return 0;

	while ((num &(1 << 31)) == val)
	{
		bits--;
		num <<= 1;
	}

	return bits + 1;
}


int unsigned_bits(unsigned num)
{
	int bits = 0;

	if (num == 0)
		return 0;

	while (num)
	{
		num >>= 1;
		bits++;
	}

	return bits;
}


void encode_cnt(unsigned char *buf, int *buf_ptr, int lc, int lc_cnt)
{
	if ((lc_cnt - 2) >= (1 << GRAY_BIT_COUNT))
	{
		fprintf(stderr, "cnt %d too large\n", lc_cnt);
		exit(1);
	}

	if (lc_cnt >= 2)
	{
		*buf_ptr -= GRAY_BITS;
		add_bits(buf, buf_ptr, GRAY_BITS, lc == 0 ? REP_BLACK : REP_WHITE);
		// printf("(%d)", lc == 0 ? REP_BLACK : REP_WHITE);
		add_bits(buf, buf_ptr, GRAY_BIT_COUNT, lc_cnt - 2);
		// printf("(%d)", lc_cnt - 2);
	}
	else if (lc_cnt)
	{
		add_bits(buf, buf_ptr, GRAY_BITS, lc);
		// printf("[%d]", lc);
	}
}


void encode_char(char_data_t *cd)
{
	int i, j, bits, lc_cnt;
	unsigned char *buf;
	int buf_ptr;
	unsigned type;
	unsigned char col[MAX_GRAY + 1];
	int lc;

	if (!cd->ok)
		return ;

	// just large enough
	buf = new_mem(cd->bitmap_width *cd->bitmap_height + 5 * 8+1);
	buf_ptr = 0;

	memset(col, 0, sizeof col);

	for (i = 0; i < cd->bitmap_width *cd->bitmap_height; i++)
	{
		if (cd->bitmap[i] <= MAX_GRAY)
		{
			col[cd->bitmap[i]] = 1;
		}
	}

	type = 0;
	for (i = 1; i < MAX_GRAY; i++)
	{
		if (col[i])
		{
			type = 1;
			break;
		}
	}

	// type 0: mono, 1: grays

	add_bits(buf, &buf_ptr, 2, type);

	bits = unsigned_bits(cd->bitmap_width);
	j = unsigned_bits(cd->bitmap_height);
	if (j > bits)
		bits = j;
	j = signed_bits(cd->x_advance);
	if (j > bits)
		bits = j;
	j = signed_bits(cd->x_ofs);
	if (j > bits)
		bits = j;
	j = signed_bits(cd->y_ofs);
	if (j > bits)
		bits = j;

	if (!bits)
		bits = 1;

	if (bits > 8)
	{
		free(buf);
		cd->ok = 0;

		return ;
	}

	add_bits(buf, &buf_ptr, 3, bits - 1);
	add_bits(buf, &buf_ptr, bits, cd->bitmap_width);
	add_bits(buf, &buf_ptr, bits, cd->bitmap_height);
	add_bits(buf, &buf_ptr, bits, cd->x_ofs);
	add_bits(buf, &buf_ptr, bits, cd->y_ofs);
	add_bits(buf, &buf_ptr, bits, cd->x_advance);

	switch (type)
	{
		case 0:
			for (i = 0; i < cd->bitmap_width *cd->bitmap_height; i++)
			{
				add_bits(buf, &buf_ptr, 1, cd->bitmap[i] ? 1 : 0);
			}
			break;

		case 1:
			lc =  - 1;
			for (i = lc_cnt = 0; i < cd->bitmap_width *cd->bitmap_height; i++)
			{
				if (cd->bitmap[i] == lc && (lc == 0 || lc == MAX_GRAY) && lc_cnt < ((1 << GRAY_BIT_COUNT) + 1))
				{
					lc_cnt++;
				}
				else
				{
					if (lc_cnt)
					{
						encode_cnt(buf, &buf_ptr, lc, lc_cnt);
						lc_cnt = 0;
						lc =  - 1;
					}
					add_bits(buf, &buf_ptr, GRAY_BITS, cd->bitmap[i]);
					// printf("[%d]", cd->bitmap[i]);
				}
				lc = cd->bitmap[i];
			}
			if (lc_cnt)
			{
				encode_cnt(buf, &buf_ptr, lc, lc_cnt);
			}
			break;
	}

	cd->data = new_mem(cd->data_len = ((buf_ptr + 7) >> 3));
	memcpy(cd->data, buf, cd->data_len);

	free(buf);
}


int show_font(char *name)
{
	int i, j, ofs, ofs2, bits, lc, lc_cnt, bitmap_len;
	file_data_t *font_file;
	font_header_t fh;
	unsigned type;
	char_data_t *cd;

	opt.verbose++;

	font_file = read_file(name);

	if (font_file->size < sizeof fh)
		return 0;

	memcpy(&fh, font_file->data, sizeof fh);

	if (fh.magic != MAGIC)
	{
		fprintf(stderr, "%s: wrong file format\n", name);
		return 1;
	}

	if (font_file->size < sizeof fh + fh.entries * 5)
	{
		fprintf(stderr, "%s: file too short\n", name);
		return 2;
	}

	font_height = fh.height;
	font_y_ofs =  - fh.baseline;

	for (i = 0; i < fh.entries; i++)
	{
		cd = add_list(&char_list, new_mem(sizeof *cd));
		j = 0;
		cd->c = read_unsigned_bits(font_file->data + sizeof fh + i * 5, &j, 21);
		ofs = read_unsigned_bits(font_file->data + sizeof fh + i * 5, &j, 19);

		if (i != fh.entries - 1)
		{
			j = 21;
			ofs2 = read_unsigned_bits(font_file->data + sizeof fh + (i + 1) *5, &j, 19);
		}
		else
		{
			ofs2 = font_file->size;
		}

		if (ofs2 < ofs || ofs2 > font_file->size)
		{
			fprintf(stderr, "%s: invalid data for chhar 0x%04x\n", name, cd->c);
			return 3;
		}

		cd->data = new_mem(cd->data_len = ofs2 - ofs);
		memcpy(cd->data, font_file->data + ofs, cd->data_len);
	}

	for (cd = char_list.start; cd; cd = cd->next)
	{
		j = 0;
		type = read_unsigned_bits(cd->data, &j, 2);
		bits = read_unsigned_bits(cd->data, &j, 3) + 1;

		if (type > 1)
		{
			fprintf(stderr, "%s: unknown type %d for char 0x%04x\n", name, type, cd->c);
			return 3;
		}

		cd->bitmap_width = read_unsigned_bits(cd->data, &j, bits);
		cd->bitmap_height = read_unsigned_bits(cd->data, &j, bits);
		cd->x_ofs = read_signed_bits(cd->data, &j, bits);
		cd->y_ofs = read_signed_bits(cd->data, &j, bits);
		cd->x_advance = read_signed_bits(cd->data, &j, bits);

		cd->bitmap = new_mem(bitmap_len = cd->bitmap_width *cd->bitmap_height);

		switch (type)
		{
			case 0:
				for (i = 0; i < bitmap_len; i++)
				{
					cd->bitmap[i] = read_unsigned_bits(cd->data, &j, 1) ? MAX_GRAY : 0;
				}
				break;

			case 1:
				for (i = 0; i < bitmap_len;)
				{
					lc = read_unsigned_bits(cd->data, &j, GRAY_BITS);
					// printf("(%d)", lc);
					if (lc <= MAX_GRAY)
					{
						cd->bitmap[i++] = lc;
						continue;
					}
					lc = lc == REP_BLACK ? 0 : MAX_GRAY;
					lc_cnt = read_unsigned_bits(cd->data, &j, GRAY_BIT_COUNT) + 3;
					// printf("(%d)", lc_cnt);
					while (i < bitmap_len && lc_cnt--)
						cd->bitmap[i++] = lc;
				}
				break;
		}

		cd->ok = 1;
	}

	printf("Font Size\n  Height: %d\n  Baseline: %d\n  Line Height: %d\n\n", font_height,  - font_y_ofs, fh.line_height);

	for (cd = char_list.start; cd; cd = cd->next)
		dump_char(cd);

	return 0;
}