#include <u.h>
#include <libc.h>
#include <bio.h>
#include <ttf.h>
#include "impl.h"

typedef struct Scan Scan;
typedef struct TTLine TTLine;

enum {
	LINEBLOCK = 32,
	PTBLOCK = 64,
};

struct TTLine {
	int x0, y0;
	int x1, y1;
	int link;
	u8int dir;
};

struct Scan {
	enum {
		DROPOUTS = 1,
		STUBDET = 2,
		SMART = 4,
	} flags;

	TTGlyph *g;
	
	TTLine *lines;
	int nlines;
	
	int *hpts, *vpts;
	int nhpts, nvpts;
	int *hscanl, *vscanl;
	
	u8int *bit;
	int width, height;
	int stride;
};

static void
dobezier(Scan *s, TTPoint p, TTPoint q, TTPoint r)
{
	vlong m, n;
	TTLine *l;

	m = (vlong)(q.x - p.x) * (r.y - p.y) - (vlong)(q.y - p.y) * (r.x - p.x);
	n = (vlong)(r.x - p.x) * (r.x - p.x) + (vlong)(r.y - p.y) * (r.y - p.y);
	if(m * m > 4 * n){
		dobezier(s, p, (TTPoint){(p.x+q.x+1)/2, (p.y+q.y+1)/2, 0}, (TTPoint){(p.x+2*q.x+r.x+2)/4, (p.y+2*q.y+r.y+2)/4, 0});
		dobezier(s, (TTPoint){(p.x+2*q.x+r.x+2)/4, (p.y+2*q.y+r.y+2)/4, 0}, (TTPoint){(r.x+q.x+1)/2, (r.y+q.y+1)/2, 0}, r);
		return;
	}
	if((s->nlines & LINEBLOCK - 1) == 0)
		s->lines = realloc(s->lines, sizeof(TTLine) * (s->nlines + LINEBLOCK));
	l = &s->lines[s->nlines++];
	if(p.y < r.y){
		l->x0 = p.x;
		l->y0 = p.y;
		l->x1 = r.x;
		l->y1 = r.y;
		l->dir = 0;
	}else{
		l->x0 = r.x;
		l->y0 = r.y;
		l->x1 = p.x;
		l->y1 = p.y;
		l->dir = 1;
	}
	l->link = -1;
}

static int
hlinecmp(void *va, void *vb)
{
	TTLine *a, *b;
	
	a = va;
	b = vb;
	if(a->y0 < b->y0) return -1;
	if(a->y0 > b->y0) return 1;
	return 0;
}

static int
vlinecmp(void *va, void *vb)
{
	TTLine *a, *b;
	
	a = va;
	b = vb;
	if(a->x0 < b->x0) return -1;
	if(a->x0 > b->x0) return 1;
	return 0;
}

static int
intcmp(void *va, void *vb)
{
	int a, b;
	
	a = *(int*)va;
	b = *(int*)vb;
	return (a>b) - (a<b);
}

static void
hprep(Scan *s)
{
	int i, j, x, y;
	TTLine *l;
	int watch, act, *p;

	qsort(s->lines, s->nlines, sizeof(TTLine), hlinecmp);
	s->hscanl = calloc(sizeof(int), (s->height + 1));
	act = -1;
	watch = 0;
	p = &act;
	for(i = 0; i < s->height; i++){
		y = 64 * i + 32;
		for(; watch < s->nlines && s->lines[watch].y0 <= y; watch++){
			if(s->lines[watch].y1 <= y || s->lines[watch].y0 == s->lines[watch].y1)
				continue;
			s->lines[watch].link = -1;
			*p = watch;
			p = &s->lines[watch].link;
		}
		s->hscanl[i] = s->nhpts;
		p = &act;
		while(j = *p, j >= 0){
			l = &s->lines[j];
			if(l->y1 <= y){
				j = l->link;
				l->link = -1;
				*p = j;
				continue;
			}
			x = l->x0 + ttfvrounddiv((vlong)(y - l->y0)*(l->x1 - l->x0), l->y1 - l->y0);
			if((s->nhpts & PTBLOCK - 1) == 0)
				s->hpts = realloc(s->hpts, (s->nhpts + PTBLOCK) * sizeof(int));
			s->hpts[s->nhpts++] = x << 1 | l->dir;
			p = &l->link;
		}
		qsort(s->hpts + s->hscanl[i], s->nhpts - s->hscanl[i], sizeof(int), intcmp);
	}
	s->hscanl[i] = s->nhpts;
}

static int
iswhite(Scan *s, int x, int y)
{
	return (s->bit[(s->height - 1 - y) * s->stride + (x>>3)] >> 7-(x&7) & 1)==0;
}

static void
pixel(Scan *s, int x, int y)
{
	assert(x >= 0 && x < s->width && y >= 0 && y < s->height);
	s->bit[(s->height - 1 - y) * s->stride + (x>>3)] |= (1<<7-(x&7));
}

static int
intersectsh(Scan *s, int x, int y)
{
	int a, b, c, vc, v;
	
	a = s->hscanl[y];
	b = s->hscanl[y+1]-1;
	v = x * 64 + 32;
	if(a > b || s->hpts[a]>>1 > v + 64 || s->hpts[b]>>1 < v) return 0;
	while(a <= b){
		c = (a + b) / 2;
		vc = s->hpts[c]>>1;
		if(vc < v)
			a = c + 1;
		else if(vc > v + 64)
			b = c - 1;
		else
			return 1;
	}
	return 0;
}

static int
intersectsv(Scan *s, int x, int y)
{
	int a, b, c, vc, v;
	
	a = s->vscanl[x];
	b = s->vscanl[x+1]-1;
	v = y * 64 + 32;
	if(a > b || s->vpts[a]>>1 > v + 64 || s->vpts[b]>>1 < v) return 0;
	while(a <= b){
		c = (a + b) / 2;
		vc = s->vpts[c]>>1;
		if(vc < v)
			a = c + 1;
		else if(vc > v + 64)
			b = c - 1;
		else
			return 1;
	}
	return 0;
}

static void
hscan(Scan *s)
{
	int i, j, k, e;
	int wind, match, seen, x;
	
	for(i = 0; i < s->height; i++){
		e = s->hscanl[i+1];
		k = s->hscanl[i];
		if(k == e) continue;
		wind = 0;
		for(j = 0; j < s->width; j++){
			x = 64 * j + 32;
			match = 0;
			seen = 0;
			while(k < e && (s->hpts[k] >> 1) <= x){
				wind += (s->hpts[k] & 1) * 2 - 1;
				seen |= 1<<(s->hpts[k] & 1);
				if((s->hpts[k] >> 1) == x)
					match++;
				k++;
			}
			if(match || wind)
				pixel(s, j, i);
			else if((s->flags & DROPOUTS) != 0 && seen == 3 && j > 0 && iswhite(s, j-1, i)){
				if((s->flags & STUBDET) == 0){
					pixel(s, j-1, i);
					continue;
				}
				if(i <= 0 || i > s->height - 1 || j <= 0 || j > s->width - 1)
					continue;
				if(!intersectsv(s, j-1, i-1) && !intersectsh(s, j-1, i-1) && !intersectsv(s, j, i-1) || !intersectsv(s, j-1, i) && !intersectsh(s, j-1, i+1) && !intersectsv(s, j, i))
					continue;
				pixel(s, j-1, i);
			}
		}
	}
}

static void
vprep(Scan *s)
{
	int i, j, x, y;
	TTLine *l;
	int watch, act, *p;

	for(i = 0; i < s->nlines; i++){
		l = &s->lines[i];
		if(l->x0 > l->x1){
			x = l->x0, l->x0 = l->x1, l->x1 = x;
			x = l->y0, l->y0 = l->y1, l->y1 = x;
			l->dir ^= 1;
		}
	}
	qsort(s->lines, s->nlines, sizeof(TTLine), vlinecmp);
	s->vscanl = calloc(sizeof(int), (s->width + 1));
	act = -1;
	watch = 0;
	p = &act;
	for(i = 0; i < s->width; i++){
		x = 64 * i + 32;
		for(; watch < s->nlines && s->lines[watch].x0 <= x; watch++){
			if(s->lines[watch].x1 <= x || s->lines[watch].x0 == s->lines[watch].x1)
				continue;
			s->lines[watch].link = -1;
			*p = watch;
			p = &s->lines[watch].link;
		}
		s->vscanl[i] = s->nvpts;
		p = &act;
		while(j = *p, j >= 0){
			l = &s->lines[j];
			if(l->x1 <= x){
				j = l->link;
				l->link = -1;
				*p = j;
				continue;
			}
			y = l->y0 + ttfvrounddiv((vlong)(x - l->x0) * (l->y1 - l->y0), l->x1 - l->x0);
			if((s->nvpts & PTBLOCK - 1) == 0)
				s->vpts = realloc(s->vpts, (s->nvpts + PTBLOCK) * sizeof(int));
			s->vpts[s->nvpts++] = y << 1 | l->dir;
			p = &l->link;
		}
		qsort(s->vpts + s->vscanl[i], s->nvpts - s->vscanl[i], sizeof(int), intcmp);
	}
	s->vscanl[i] = s->nvpts;

}

static void
vscan(Scan *s)
{
	int i, j, k, e;
	int seen, y;
	
	for(i = 0; i < s->width; i++){
		e = s->vscanl[i+1];
		k = s->vscanl[i];
		if(k == e) continue;
		for(j = 0; j < s->height; j++){
			y = 64 * j + 32;
			seen = 0;
			while(k < e && (s->vpts[k] >> 1) <= y){
				seen |= 1<<(s->vpts[k] & 1);
				k++;
			}
			if(seen == 3 && j > 0 && iswhite(s, i, j-1) && iswhite(s, i, j)){
				if((s->flags & STUBDET) == 0){
					pixel(s, i, j-1);
					continue;
				}
				if(i <= 0 || i > s->width - 1 || j <= 0 || j > s->height - 1)
					continue;
				if(!intersectsv(s, i-1, j-1) & !intersectsh(s, i-1, j-1) & !intersectsh(s, i-1, j) | !intersectsv(s, i+1, j-1) & !intersectsh(s, i, j-1) & !intersectsh(s, i, j))
					continue;
				pixel(s, i, j-1);
			}
		}
	}
}
	
void
ttfscan(TTGlyph *g)
{
	int i, j, c;
	TTPoint p, q, r;
	Scan s;

	memset(&s, 0, sizeof(s));
	s.g = g;
	s.flags = 0;
	c = g->font->scanctrl;
	if((c & 1<<8) != 0 && g->font->ppem <= (c & 0xff))
		s.flags |= DROPOUTS;
	if((c & 1<<11) != 0 && g->font->ppem > (c & 0xff))
		s.flags &= ~DROPOUTS;
	if((c & 3<<12) != 0)
		s.flags &= ~DROPOUTS;
	if((s.flags & DROPOUTS) != 0)
		switch(g->font->scantype){
		case 0: break;
		case 1: s.flags |= STUBDET; break;
		case 2: case 3: case 6: case 7: s.flags &= ~DROPOUTS; break;
		case 4: s.flags |= SMART; break;
		case 5: s.flags |= SMART | STUBDET; break;
		}
	
//	s.width = (g->pt[g->npt - 1].x + 63) / 64;
//	s.height = g->font->ascentpx + g->font->descentpx;
	s.width = -g->xminpx + g->xmaxpx;
	s.height = -g->yminpx + g->ymaxpx;
	s.stride = s.width + 7 >> 3;
	s.bit = mallocz(s.height * s.stride, 1);
	assert(s.bit != nil);
	for(i = 0; i < g->npt; i++){
		g->pt[i].x -= g->xminpx * 64;
		g->pt[i].y -= g->yminpx * 64;
//		g->pt[i].y += g->font->descentpx * 64;
	}
	for(i = 0; i < g->ncon; i++){
		if(g->confst[i] + 1 >= g->confst[i+1]) continue;
		p = g->pt[g->confst[i]];
		assert((p.flags & 1) != 0);
		for(j = g->confst[i]; j++ < g->confst[i+1]; ){
			if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0)
				q = g->pt[j++];
			else
				q = p;
			if(j >= g->confst[i+1])
				r = g->pt[g->confst[i]];
			else{
				r = g->pt[j];
				if((g->pt[j].flags & 1) == 0){
					r.x = (r.x + q.x) / 2;
					r.y = (r.y + q.y) / 2;
				}
			}
			dobezier(&s, p, q, r);
			p = r;
			if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0)
				j--;
		}
	}
	hprep(&s);
	if((s.flags & DROPOUTS) != 0)
		vprep(&s);
	hscan(&s);
	if((s.flags & DROPOUTS) != 0)
		vscan(&s);
	free(s.hpts);
	free(s.vpts);
	free(s.hscanl);
	free(s.vscanl);
	free(s.lines);
	g->bit = s.bit;
	g->width = s.width;
	g->height = s.height;
	g->stride = s.stride;
}

int
ttfgetcontour(TTGlyph *g, int i, float **fp, int *np)
{
	float offx, offy, scale;
	float *nf;
	int n, j;
	TTPoint p, q, r;

	if((uint)i >= g->ncon)
		return 0;
	if(g->confst[i]+1 >= g->confst[i+1]){
		if(np != nil)
			*np = 0;
		if(fp != nil)
			*fp = malloc(0);
		return g->ncon - i;
	}
	if(g->bit != nil){
		scale = 1.0f / 64;
		offx = g->xminpx;
		offy = g->yminpx;
	}else{
		scale = 1.0f * g->font->ppem / g->font->u->emsize;
		offx = 0;
		offy = 0;
	}
	p = g->pt[g->confst[i]];
	n = 1;
	if(fp != nil){
		*fp = malloc(2 * sizeof(float));
		if(*fp == nil) return -1;
		(*fp)[0] = p.x * scale;
		(*fp)[1] = p.y * scale + offy;
	}
	assert((p.flags & 1) != 0);
	for(j = g->confst[i]; j++ < g->confst[i+1]; ){
		if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0)
			q = g->pt[j++];
		else
			q = p;
		if(j >= g->confst[i+1])
			r = g->pt[g->confst[i]];
		else{
			r = g->pt[j];
			if((g->pt[j].flags & 1) == 0){
				r.x = (r.x + q.x) / 2;
				r.y = (r.y + q.y) / 2;
			}
		}
		if(fp != nil){
			nf = realloc(*fp, sizeof(float) * 2 * (n + 2));
			if(nf == nil){
				free(*fp);
				return -1;
			}
			*fp = nf;
			nf[2*n] = q.x * scale;
			nf[2*n+1] = q.y * scale + offy;
			nf[2*n+2] = r.x * scale;
			nf[2*n+3] = r.y * scale + offy;
		}
		p = r;
		n += 2;
		if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0)
			j--;
	}
	if(np != nil)
		*np = n;
	return g->ncon - i;
}