#include <sys/ioctl.h>

#include <stdlib.h>
#include <stdbit.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <assert.h>

#include <unistd.h>
#include <termios.h>
#include <signal.h>
#include <poll.h>
#include <time.h>

#include "wrmr.h"
#include "vui.h"

#define CSI "\x1b["

#define VUI_LOG_OUTPUT 0
#define VUI_LOG_OUTPUT_FILE "out_log.txt"

/* terminal control */

static void vui_getwinsz(unsigned *w, unsigned *h);
static void vui_clrspan(VuiBuffer *buf, unsigned x0, unsigned x1, unsigned y);
static void vui_clrtoeol(VuiBuffer *buf, unsigned x0, unsigned y);

static void attr_chg(VuiAttr *ptr, VuiAttr to);
static inline void curs_move(unsigned *restrict ptr_x, unsigned *restrict ptr_y, unsigned dst_x, unsigned dst_y);

static void on_resized(int _);
static void adjust_win_size(void);
static void resize_win(unsigned nw, unsigned nh);

/* buffer handling */

static void clear_buf(VuiBuffer *buf);
static void resize_buf(VuiBuffer *buf, unsigned nw, unsigned nh);
static void free_buf(VuiBuffer *buf);

static inline int bchr_equiv(VuiBuffer *a, VuiBuffer *b, unsigned i);

/* input */

static unsigned getk(void);
static unsigned getk_utf8(uint8_t start);
static VuiKey bad_key(void);
static VuiKey meta_key(u32 c);
static VuiKey esc_key(u32 c);

/* output */

static void vui_out_fit(size_t n);
static void vui_outf(const char *fmt, ...);
static inline void vui_outc(char c);
static inline void vui_outvc(VuiChar c);
static inline void vui_outvcn(VuiChar *c, size_t n);
static inline void vui_outsn(const char *s, unsigned n);
static inline void vui_outs(const char *s);
static inline void vui_out_flush(void);

/* unicode */

static u32 utf8_decode_len(const char *src, u32 n);
static u32 utf8_encode_len(const u32 *src, u32 n);
static void utf8_decode(u32 *dst, u32 n, const char *src);
static void utf8_encode(char *dst, const u32 *src, u32 n);

/* globals */

static struct termios vui_init_stdin_tos, vui_init_stdout_tos, vui_raw_stdin_tos, vui_raw_stdout_tos;

static char *vui_out = NULL;
static size_t vui_outn = 0;
static size_t vui_out_cap = 0;

static VuiWindow win = {
	.front = &win.buf1,
	.back = &win.buf2,
};

/* TODO
 *
 * - clean up keyboard input
 * - separate out library interface
 * - maybe some custom colors
 */

void vui_redraw_fn(void (*fn)(void *ctx)) {
	win.redraw_fn = fn;
}

void vui_redraw_ctx(void *ctx) {
	win.redraw_ctx = ctx;
}

VuiWindow *vui_win(void) {
	return &win;
}

static void vui_getwinsz(unsigned *w, unsigned *h) {
	struct winsize wsz;
	ioctl(STDOUT_FILENO, TIOCGWINSZ, &wsz);
	*w = wsz.ws_col;
	*h = wsz.ws_row;
}

static void vui_clrspan(VuiBuffer *buf, unsigned x0, unsigned x1, unsigned y) {
	for (unsigned x = x0; x < x1; x++) {
		BCHR(buf, x, y) = ' ';
	}
	for (unsigned x = x0; x < x1; x++) {
		BATTR(buf, x, y) = ATTR_DEFAULT;
	}
}

static void vui_clrtoeol(VuiBuffer *buf, unsigned x0, unsigned y) {
	vui_clrspan(buf, x0, buf->width, y);
}

static void clear_buf(VuiBuffer *buf) {
	for (unsigned y = 0; y < buf->height; y++) {
		vui_clrtoeol(buf, 0, y);
	}
}

void vui_clear(void) {
	clear_buf(win.front);
}

void vui_fill_rect(VuiChar c, VuiAttr a, int x0, int y0, int width, int height) {
	if (x0 < 0) { width += x0; x0 = 0; }
	if (y0 < 0) { height += y0; y0 = 0; }
	if (x0 + width >= (int)COLS) width = (COLS - 1) - x0;
	if (y0 + height >= (int)LINES) height = (LINES - 1) - y0;
	if (width < 1 || height < 1) return;
	for (int y = y0; y < y0 + height; y++) {
		for (int x = x0; x < x0 + width; x++) {
			CHR(x, y) = c;
			ATTR(x, y) = a;
		}
	}
}

void vui_fill(VuiChar c, VuiAttr a) {
	vui_fill_rect(c, a, 0, 0, COLS, LINES);
}

static void resize_buf(VuiBuffer *buf, unsigned nw, unsigned nh) {
	VuiChar *nchr  = calloc(nw * nh, sizeof(*buf->chr));
	uint16_t *nattr = calloc(nw * nh, sizeof(*buf->attr));
	assert(nchr);
	assert(nattr);

	unsigned oldw = buf->width;
	unsigned oldh = buf->height;
	unsigned minw = nw < oldw ? nw : oldw;
	unsigned minh = nh < oldh ? nh : oldh;
	for (unsigned y = 0; y < minh; y++) {
		memcpy(nchr  + y*nw, buf->chr  + y*oldw, minw * sizeof(*buf->chr));
		memcpy(nattr + y*nw, buf->attr + y*oldw, minw * sizeof(*buf->attr));
	}

	free(buf->chr);
	free(buf->attr);
	buf->chr = nchr;
	buf->attr = nattr;
	buf->width = nw;
	buf->height = nh;
	for (unsigned y = 0; y < minh; y++) vui_clrtoeol(buf, minw, y);
	for (unsigned y = minh; y < buf->height; y++) vui_clrtoeol(buf, 0, y);
}

static void resize_win(unsigned nw, unsigned nh) {
	resize_buf(&win.buf1, nw, nh);
	resize_buf(&win.buf2, nw, nh);
	win.width  = nw;
	win.height = nh;
}

static void adjust_win_size(void) {
	unsigned w, h;
	vui_getwinsz(&w, &h);
	if (w != COLS || h != LINES) {
		resize_win(w, h);
		win.redraw_all = 1;
	}
}

void vui_curs_vis(int vis) {
	win.curs_vis = vis;
	if (vis) {
		fputs(CSI "?25h", stdout);
		fflush(stdout);
	} else {
		fputs(CSI "?25l", stdout);
		fflush(stdout);
	}
}

void vui_curs_pos(int x, int y) {
	win.curs_x = x;
	win.curs_y = y;
}

/* TODO: use something better than signal() */
/* does sigaction allow for a context pointer? */
static void on_resized(int _) {
	adjust_win_size();
	if (win.redraw_fn) {
		win.redraw_fn(win.redraw_ctx);
	}
	vui_blit();
}

void vui_init(void) {
	tcgetattr(STDIN_FILENO, &vui_init_stdin_tos);
	vui_raw_stdin_tos = vui_init_stdin_tos;
	/*
	vui_raw_stdin_tos.c_lflag &= ~(ECHO | ECHONL | ICANON | IEXTEN | ISIG);
	vui_raw_stdin_tos.c_lflag |= IGNBRK;
	*/

	vui_raw_stdin_tos.c_iflag &= ~(IGNBRK | BRKINT | PARMRK | ISTRIP | INLCR | IGNCR | ICRNL | IXON);
	vui_raw_stdin_tos.c_oflag &= ~OPOST;
	vui_raw_stdin_tos.c_lflag &= ~(ECHO | ECHONL | ICANON | ISIG | IEXTEN);
	vui_raw_stdin_tos.c_cflag &= ~(CSIZE | PARENB);
	vui_raw_stdin_tos.c_cflag |= CS8;

	tcsetattr(STDIN_FILENO, TCSANOW, &vui_raw_stdin_tos);

	tcgetattr(STDOUT_FILENO, &vui_init_stdout_tos);
	vui_raw_stdout_tos = vui_init_stdout_tos;
	vui_raw_stdout_tos.c_oflag &= ~OPOST;
	tcsetattr(STDOUT_FILENO, TCSANOW, &vui_raw_stdout_tos);

	/* set white:black to default */
	printf(CSI "40;37m" CSI "8]");
	vui_curs_vis(0);
	win.redraw_all = 1;

	adjust_win_size();
	signal(SIGWINCH, on_resized);
}


static void free_buf(VuiBuffer *buf) {
	free(buf->chr);
	free(buf->attr);
	buf->chr = NULL;
	buf->attr = NULL;
	buf->width = 0;
	buf->height = 0;
}

static inline int bchr_equiv(VuiBuffer *a, VuiBuffer *b, unsigned i) {
	return a->chr[i] == b->chr[i] && a->attr[i] == b->attr[i];
}

void vui_fini(void) {
	vui_curs_vis(1);
	free_buf(&win.buf1);
	free_buf(&win.buf2);
	free(vui_out);
	vui_out = NULL;
	vui_out_cap = 0;
	printf(CSI "0m" CSI "H" CSI "2J");
	tcsetattr(STDIN_FILENO,  TCSANOW, &vui_init_stdin_tos);
	tcsetattr(STDOUT_FILENO, TCSANOW, &vui_init_stdout_tos);
}

static void vui_out_fit(size_t n) {
	size_t c = stdc_bit_ceil(n);
	if (c > vui_out_cap) {
		char *p = realloc(vui_out, c);
		if (!p) {
			vui_fini();
			fprintf(stderr, "failed to reallocate vui output buffer\n");
			exit(1);
		}
		vui_out = p;
		vui_out_cap = c;
	}
}

static void vui_outf(const char *fmt, ...) {
	va_list ap;
	va_start(ap, fmt);
	int n = vsnprintf(NULL, 0, fmt, ap);
	va_end(ap);
	va_start(ap, fmt);
	vui_out_fit(vui_outn + n);
	vsprintf(&vui_out[vui_outn], fmt, ap);
	vui_outn += n;
	va_end(ap);
}


/* lookup table from utf-8 codepoint to byte length:
 *      { 6,6,6,6,6,6,5,5,5,5,5,4,4,4,4,4,3,3,3,3,3,2,2,2,2,1,1,1,1,1,1,1,1, }
 *      len(cp) = tbl[32 - clz(cp)].
 *
 * how could we possibly reduce this?
 *      6 sixes, 5 fives, 5 fours, 5 threes, four twos, and eight ones.
 *      no obvious pattern.
 *
 * no utf8 elements above 0x10FFFF, so never more than 4 bytes:
 *      4444433333222211111111
 *
 * subtract one from each, so they fit in 3 bytes:
 *      3333322222111100000000
 *
 * pack into a u64:
 *      0b11111111111010101010010101010000000000000000
 *
 * convert to hex, and now:
 *      len(cp) = 1 + (0xFFEAA550000 >> (2 * (32 - clz(cp)))) & 3
 */

#define UTF8_CP_LEN_BITS   ((uint64_t)0xFFEAA550000)
#define UTF8_CP_SHIFT(cp)  ((32 - stdc_leading_zeros((uint32_t)(cp))) << 1)
#define UTF8_CP_LEN(cp)    (1 + ((UTF8_CP_LEN_BITS >> UTF8_CP_SHIFT(cp)) & 3))

static inline void vui_outc(char c) {
	vui_out_fit(vui_outn + 1);
	vui_out[vui_outn++] = c;
}

/* don't pass a NUL to this */
/* it doesn't make sense to do so, and assuming non-zero lets us dodge a branch
 * in stdc_leading_zeros() */
static inline void vui_outvc(VuiChar c) {
	vui_outvcn(&c, 1);
}

static inline void vui_outvcn(VuiChar *c, size_t n) {
	u32 len = utf8_encode_len(c, n);
	vui_out_fit(vui_outn + len);
	utf8_encode(&vui_out[vui_outn], c, n);
	vui_outn += len;
}

static inline void vui_outsn(const char *s, unsigned n) {
	vui_out_fit(vui_outn + n);
	memcpy(&vui_out[vui_outn], s, n);
	vui_outn += n;
}

static inline void vui_outs(const char *s) {
	vui_outsn(s, strlen(s));
}

static inline void vui_out_flush(void) {
	/*fwrite(vui_out, 1, vui_outn, stdout);
	fflush(stdout);*/

	write(STDOUT_FILENO, vui_out, vui_outn);

#if VUI_LOG_OUTPUT
	static unsigned out_frame = 0;
	FILE *f = fopen(VUI_LOG_OUTPUT_FILE, "a");
	assert(f);
	fprintf(f, "\n\n:: OUTPUT FRAME %u ::\n", ++out_frame);
	fwrite(vui_out, 1, vui_outn, f);
	fclose(f);
#endif

	vui_outn = 0;
}

static inline void curs_move(unsigned *restrict ptr_x, unsigned *restrict ptr_y, unsigned dst_x, unsigned dst_y) {
	unsigned src_x = *ptr_x;
	unsigned src_y = *ptr_y;
	if (src_x != dst_x && src_y != dst_y) {
		if (dst_x == src_x - 1) {
			vui_outf(CSI "\b%ud", dst_y + 1);
		} else if (dst_x > 0) {
			vui_outf(CSI "%u;%uH", dst_y + 1, dst_x + 1);
		} else if (dst_y > 0) {
			vui_outf(CSI "%uH", dst_y + 1);
		} else {
			vui_outs(CSI "H");
		}
	} else if (src_x != dst_x) {
		if (dst_x == 0) {
			vui_outc('\r');
		} else if (dst_x == src_x - 1) {
			vui_outc('\b');
		} else {
			vui_outf(CSI "%uG", dst_x + 1);
		}
	} else if (src_y != dst_y) {
		if (dst_y == src_y - 1 && dst_x == src_x + 1) {
			vui_outs("\x1b" "M");
			abort();
		} else if (dst_y == src_y + 1 && dst_x == src_x + 1) {
			vui_outs("\x1b" "D");
			abort();
		} else if (dst_y > 0) {
			vui_outf(CSI "%ud", dst_y + 1);
		} else if (dst_y == src_y - 1) {
			vui_outs(CSI "A");
		} else if (dst_y == src_y -+1) {
			vui_outs(CSI "B");
		} else {
			vui_outs(CSI "d");
		}
	}
	*ptr_x = dst_x;
	*ptr_y = dst_y;
}

#define M(s) do {\
	if (sep) vui_outc(';');\
	vui_outs(s);\
	sep = 1;\
} while(0)

static void attr_chg(VuiAttr *ptr, VuiAttr to) {
	VuiAttr from = *ptr;
	if (from == to) return;

	int attr_chg_count = stdc_count_ones(ATTR_A(from) ^ ATTR_A(to));
	int chg_attr = (attr_chg_count != 0);
	if (!chg_attr) goto chg_colors;

	/* deduct color changes */
	attr_chg_count -= (ATTR_FG(to) == ATTR_FG(from)) && (ATTR_FG(to) != ATTR_DEFAULT);
	attr_chg_count -= (ATTR_BG(to) == ATTR_BG(from)) && (ATTR_BG(to) != ATTR_DEFAULT);

	int should_rebuild = (attr_chg_count > 1) || to == ATTR_DEFAULT;

	if (should_rebuild) {
		vui_outs(CSI "0");
		if (to & A_BOLD) vui_outs(";1");
		if (to & A_DIM) vui_outs(";2");
		if (to & A_ITALIC) vui_outs(";3");
		if (to & A_UNDERSCORE) vui_outs(";4");
		if (to & A_BLINK) vui_outs(";5");
		if (to & A_REVERSE) vui_outs(";7");
		from = ATTR_DEFAULT;
		assert(ATTR_FG(from) == FG_WHITE);
		assert(ATTR_BG(from) == BG_BLACK);
	} else {
		int sep = 0;
		vui_outs(CSI);
		if ((to ^ from) & A_BOLD) {
			if (to & A_BOLD) M("1");
			else {
				M("22");
				from &= (~A_BOLD & ~A_DIM);
			}
		}
		if ((to ^ from) & A_DIM) {
			if (to & A_BOLD) M("2");
			else {
				M("22");
				from &= (~A_BOLD & ~A_DIM);
			}
		}
		if ((to ^ from) & A_ITALIC)     M((to & A_ITALIC)     ? "3" : "23");
		if ((to ^ from) & A_UNDERSCORE) M((to & A_UNDERSCORE) ? "4" : "24");
		if ((to ^ from) & A_BLINK)      M((to & A_BLINK)      ? "5" : "25");
		if ((to ^ from) & A_REVERSE)    M((to & A_REVERSE)    ? "7" : "27");
	}

chg_colors:;

	int f_fg = ATTR_FG(from);
	int f_bg = ATTR_BG(from);
	int t_fg = ATTR_FG(to);
	int t_bg = ATTR_BG(to);

	int chg_fg = (t_fg != f_fg);
	int chg_bg = (t_bg != f_bg);
	if (chg_fg || chg_bg) {
		if (chg_attr) vui_outc(';');
		else vui_outs(CSI);
		if (chg_fg) {
			vui_outc(t_fg > 7 ? '9' : '3');
			vui_outc((t_fg & 7) + '0');
		}
		if (chg_bg) {
			if (chg_fg) vui_outc(';');
			if (t_bg > 7) {
				vui_outs("10");
			} else {
				vui_outc('4');
			}
			vui_outc((t_bg & 7) + '0');
		}
	}

	if (chg_fg || chg_bg || chg_attr) vui_outc('m');
	*ptr = to;
}

void vui_scroll_buf(VuiBuffer *b, int dx, int dy);

static VuiAttr attr_last = ATTR_DEFAULT;
static unsigned cur_x = 0;
static unsigned cur_y = 0;

static void emit_scroll_x(u32 y) {
	if (win.scroll_x < 0) {
		/* delete chars at start of line */
		attr_chg(&attr_last, ATTR_DEFAULT);
		curs_move(&cur_x, &cur_y, 0, y);
		vui_outf(CSI "%dP", -win.scroll_x);
	} else if (win.scroll_x > 0) {
		/* insert spaces at start of line */
		attr_chg(&attr_last, ATTR_DEFAULT);
		curs_move(&cur_x, &cur_y, 0, y);
		vui_outf(CSI "%d@", win.scroll_x);
	}
}

static void emit_scroll_y(void) {
	/* xterm has \x1b[S and \x1b[T to scroll directly */
	/* but these don't work in linux vtty */
	if (win.scroll_y < 0) {
		/* delete lines at top */
		curs_move(&cur_x, &cur_y, 0, 0);
		attr_chg(&attr_last, ATTR_DEFAULT);
		if (win.scroll_y == -1) vui_outs(CSI "M");
		else vui_outf(CSI "%dM", -win.scroll_y);
	} else if (win.scroll_y > 0) {
		/* insert blank lines at top */
		curs_move(&cur_x, &cur_y, 0, 0);
		attr_chg(&attr_last, ATTR_DEFAULT);
		if (win.scroll_y == 1) vui_outs(CSI "L");
		else vui_outf(CSI "%dL", win.scroll_y);
	}
}

void vui_blit(void) {
	VuiBuffer *front = win.front;
	VuiBuffer *back = win.back;

	if (win.redraw_all) {
		vui_outs(CSI "H" CSI "2J" CSI "0m");
		attr_last = ATTR_DEFAULT;
		unsigned max = COLS * LINES;
		for (unsigned i = 0; i < max; i++) {
			attr_chg(&attr_last, front->attr[i]);
			vui_outvc(front->chr[i]);
		}
		vui_outs(CSI "H");
		cur_x = 0;
		cur_y = 0;
		win.redraw_all = 0;
		win.scroll_x = 0;
		win.scroll_y = 0;
		goto end;
	}

	emit_scroll_y();
	vui_scroll_buf(back, win.scroll_x, win.scroll_y);
	for (unsigned y = 0; y < LINES; y++) {
		unsigned x = 0;
		emit_scroll_x(y);
		while (x < COLS) {
			while (x < COLS && bchr_equiv(back, front, (y * COLS) + x)) x++;
			if (x >= COLS) break;
			unsigned x0 = x;
			VuiAttr a = ATTR(x0, y);
			while (x < COLS && !bchr_equiv(back, front, (y * COLS) + x) && BATTR(front, x, y) == a) x++;
			if (x0 != x) {
				curs_move(&cur_x, &cur_y, x0, y);
				attr_chg(&attr_last, a);
				vui_outvcn(&CHR(x0, y), x - x0);
				cur_x = x;
			}
		}
	}

end:
	win.scroll_x = 0;
	win.scroll_y = 0;

	if (win.curs_vis) {
		curs_move(&cur_x, &cur_y, win.curs_x, win.curs_y);
	}

	vui_out_flush();
	memcpy(back->chr,  front->chr,  sizeof(*back->chr)  * (back->width * back->height));
	memcpy(back->attr, front->attr, sizeof(*back->attr) * (back->width * back->height));
	win.front = back;
	win.back = front;
}

void vui_chra(int x, int y, VuiChar c, VuiAttr a) {
	if (x >= 0 && x < (int)COLS && y >= 0 && y < (int)LINES) {
		CHR(x, y) = c;
		ATTR(x, y) = a;
	}
}

void vui_chr(int x, int y, VuiChar c) {
	vui_chra(x, y, c, ATTR_DEFAULT);
}

static void truncate_span(int *x, unsigned *nptr) {
	int n = (int)*nptr;
	if (*x < 0) {
		n += *x;
		*x = 0;
	}
	if (*x >= (int)COLS) {
		*nptr = 0;
		return;
	}
	if (*x + n >= (int)COLS) {
		n = COLS - *x - 1;
	}
	if (n < 0) n = 0;
	assert(n >= 0);
	assert(*x + n < (int)COLS);
	*nptr = n;
}

void vui_putsna(int x, int y, const char *s, unsigned srcn, VuiAttr a) {
	u32 n = utf8_decode_len(s, srcn);
	truncate_span(&x, &n);
	if (n < 1 || y < 0 || y >= (int)LINES) return;
	utf8_decode(&CHR(x, y), n, s);
	for (uint16_t *pa = &ATTR(x, y); n--;) *pa++ = a;
}

void vui_putsn(int x, int y, const char *s, unsigned n) {
	vui_putsna(x, y, s, n, ATTR_DEFAULT);
}

void vui_putsa(int x, int y, const char *s, VuiAttr a) {
	vui_putsna(x, y, s, strlen(s), a);
}

void vui_puts(int x, int y, const char *s) {
	vui_putsn(x, y, s, strlen(s));
}

int vui_avprintf(int x, int y, VuiAttr a, const char *fmt, va_list ap) {
	va_list ap2;
	va_copy(ap2, ap);
	int n = vsnprintf(NULL, 0, fmt, ap);
	if (x < 0) x = COLS + x - (n - 1);
	if (y < 0) y = LINES + y;
	if (x + n > (int)COLS) n = COLS - x;
	if (x < (int)COLS && y < (int)LINES && n > 0) {
		char buf[n + 1];
		vsnprintf(buf, n + 1, fmt, ap2);
		vui_putsna(x, y, buf, n, a);
	}
	va_end(ap2);
	return n;
}

int vui_aprintf(int x, int y, VuiAttr a, const char *fmt, ...) {
	va_list ap;
	va_start(ap, fmt);
	int r = vui_avprintf(x, y, a, fmt, ap);
	va_end(ap);
	return r;
}

int vui_printf(int x, int y, const char *fmt, ...) {
	va_list ap;
	va_start(ap, fmt);
	int r = vui_avprintf(x, y, ATTR_DEFAULT, fmt, ap);
	va_end(ap);
	return r;
}

int vui_wait_for_input(int ms) {
	return poll(&(struct pollfd) { .fd = STDIN_FILENO, .events = POLLIN }, 1, ms);
}

int vui_has_input(void) {
	return vui_wait_for_input(0);
}

void vui_scroll_buf(VuiBuffer *b, int dx, int dy) {
	if ((unsigned)abs(dx) >= b->width || (unsigned)abs(dy) >= b->height) {
		clear_buf(b);
		return;
	}
	if (dy > 0) {
		memmove(b->chr  + (b->width * dy), b->chr,  sizeof(*b->chr)  * b->width * (b->height - dy));
		memmove(b->attr + (b->width * dy), b->attr, sizeof(*b->attr) * b->width * (b->height - dy));
		for (int y = 0; y < dy; y++) vui_clrtoeol(b, 0, y);
	} else if (dy < 0) {
		memmove(b->chr,  b->chr  + (b->width * -dy), sizeof(*b->chr)  * b->width * (b->height + dy));
		memmove(b->attr, b->attr + (b->width * -dy), sizeof(*b->attr) * b->width * (b->height + dy));
		for (int y = b->height - 1; y > (int)b->height + dy - 1; y--) vui_clrtoeol(b, 0, y);
	}
	if (dx > 0) {
		for (unsigned i = 0; i < b->height; i++) {
			memmove(b->chr  + (i * b->width) + dx, b->chr + (i * b->width),  sizeof(*b->chr) * (b->width - dx));
			memmove(b->attr + (i * b->width) + dx, b->attr + (i * b->width), sizeof(*b->attr) * (b->width - dx));
			vui_clrspan(b, 0, dx, i);
		}
	} else if (dx < 0) {
		for (unsigned i = 0; i < b->height; i++) {
			memmove(b->chr + (i * b->width), b->chr + (i * b->width) - dx, sizeof(*b->chr) * (b->width + dx));
			memmove(b->attr + (i * b->width), b->attr + (i * b->width) - dx, sizeof(*b->attr) * (b->width + dx));
			vui_clrspan(b, b->width + dx - 1, b->width, i);
		}

	}
}

void vui_scroll(int dx, int dy) {
	vui_scroll_buf(win.front, dx, dy);
	win.scroll_x += dx;
	win.scroll_y += dy;
}

static unsigned getk(void) {
	char c;
	int r;
	do {
		r = read(STDIN_FILENO, &c, 1);
	} while (r == -1 && errno == EINTR);
	if (r == -1) return KEY_EOF;
	return c;
}

static unsigned getk_utf8(uint8_t start) {
	unsigned n = stdc_leading_ones(start);
	if (n > 4) return KEY_INVALID;
	static const uint8_t cpmask[4] = { 0x7f, 0x3f, 0x1f, 0xf };
	uint32_t ch = start & cpmask[n - 1];
	while (--n) {
		uint8_t k = getk();
		if ((k & 0xc0) != 0x80) return KEY_INVALID;
		ch = (ch << 6) | (k & 0x3f);
	}
	return ch;
}

static VuiKey bad_key(void) {
	/* yell */
	putchar('\a');
	fflush(stdout);
	return KEY_INVALID;
}

static VuiKey meta_key(u32 c) {
	switch (c) {
	case '2': return esc_key(getk()) | KEY_SHIFT_BIT; break;
	case '3': return esc_key(getk()) | KEY_ALT_BIT; break;
	case '4': return esc_key(getk()) | KEY_ALT_BIT | KEY_SHIFT_BIT; break;
	case '5': return esc_key(getk()) | KEY_CTRL_BIT; break;
	case '6': return esc_key(getk()) | KEY_CTRL_BIT | KEY_SHIFT_BIT; break;
	case '7': return esc_key(getk()) | KEY_CTRL_BIT | KEY_ALT_BIT; break;
	case '8': return esc_key(getk()) | KEY_CTRL_BIT | KEY_SHIFT_BIT | KEY_ALT_BIT; break;
	case '9': return esc_key(getk()) | KEY_META_BIT; break;
	case '1':
		  switch (getk()) {
		  case '0': return esc_key(getk()) | KEY_META_BIT | KEY_SHIFT_BIT; break;
		  case '1': return esc_key(getk()) | KEY_META_BIT | KEY_ALT_BIT; break;
		  case '3': return esc_key(getk()) | KEY_META_BIT | KEY_CTRL_BIT; break;
		  case '4': return esc_key(getk()) | KEY_META_BIT | KEY_SHIFT_BIT | KEY_CTRL_BIT; break;
		  case '5': return esc_key(getk()) | KEY_META_BIT | KEY_ALT_BIT | KEY_CTRL_BIT; break;
		  case '6': return esc_key(getk()) | KEY_META_BIT | KEY_SHIFT_BIT | KEY_ALT_BIT | KEY_CTRL_BIT; break;
		  default: return bad_key();
		  }
	default: return bad_key();
	}
}

static VuiKey esc_key(u32 c) {
	switch (c) {
	case 'P': return KEY_F1; break;
	case 'Q': return KEY_F2; break;
	case 'R': return KEY_F3; break;
	case 'S': return KEY_F4; break;
	case '1':
		switch (getk()) {
		case ';': return meta_key(getk());
		case '5':
		default: return bad_key();
		}
		break;
	case 'A': return KEY_UP;
	case 'B': return KEY_DOWN;
	case 'C': return KEY_RIGHT;
	case 'D': return KEY_LEFT;
	case 'H': return KEY_HOME;
	case 'F': return KEY_END;
	case '5':
		  if (getk() != '~') return bad_key();
		  return KEY_PGUP;
	case '6':
		  if (getk() != '~') return bad_key();
		  return KEY_PGDN;
	default: return bad_key();
	}
}

VuiKey vui_key(void) {
	int c = getk();
	switch (c) {
	case '\n':
		return KEY_RET;
	case '\b': case 0x7f:
		return KEY_BKSP;
	case '\x1b':
		if (vui_has_input()) {
			c = getk();
			switch (c) {
			case 'O':
			   switch (getk()) {
			   case 'P': return KEY_F1; break;
			   case 'Q': return KEY_F2; break;
			   case 'R': return KEY_F3; break;
			   case 'S': return KEY_F4; break;
			   default: return bad_key(); break;
			   }
			case '[': return esc_key(getk());
			default: return bad_key();
			}
		} else {
			return KEY_ESC;
		}
	default:
		return c & 0x80 ? getk_utf8(c) : c;
	}
}

/* utf8 */

static u32 utf8_decode_len(const char *src, u32 n) {
	u32 i = 0;
	u32 len = 0;
	while (i < n) {
		i += stdc_leading_ones((u8)src[i]) + ((~src[i] & 0x80) >> 7);
		len++;
	}
	return len;
}

static void utf8_decode(u32 *dst, u32 n, const char *src) {
	while (n--) {
		u8 c = *src++;
		u32 bits = stdc_leading_ones(c);
		ASSUME(bits < 5);
		u32 cp = c & (0xff >> bits);
		while (bits-- > 1) {
			c = *src++;
			cp = (cp << 6) | (c & 0x3F);
		}
		*dst++ = cp;
	}
}

static u32 utf8_encode_len(const u32 *src, u32 n) {
	u32 len = 0;
	while (n) len += UTF8_CP_LEN(src[--n]);
	return len;
}

static void utf8_encode(char *dst, const u32 *src, u32 n) {
	while (n--) {
		u32 c = *src++;
		ASSUME(c > 0 && c <= 0x110000);

		u32 len = UTF8_CP_LEN(c);
		ASSUME(len > 0 && len < 5);

		if (len > 1) {
			for (u32 i = len; --i;) {
				dst[i] = 0x80 | (c & 0x3f);
				c >>= 6;
			}
			*dst = (0xf0 << (4 - len)) | c;
			dst += len;
		} else {
			*dst++ = c;
		}
	}
}