/*
 *	Universal Terminal Interface -- Screen Refresh
 *
 *	(c) 1997--1999 Martin Mares, <mj@ericsson.cz>
 */

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

#include "termint.h"

/* Put single character and update physical cursor position */

static void
put_single_char(byte c, int pos)
{
  send_char(c);
  cold[pos] = c;
  kold[pos] = set_color;
  aold[pos] = set_attrs;
  if (set_c != win_c1)
    set_c++;
  else
    {
#ifdef DEBUG
      if (set_c > win_c1)
	fatal_error("Write past right margin");
#endif
      switch (auto_margins)
	{
	case AM_DUMB:
	case AM_NO_CORNER:
	  set_c = 0;
	  set_r++;
#ifdef DEBUG
	  if (set_r >= rows)
	    fatal_error("Cursor out of screen and scrolling");
#endif
	  break;
	case AM_GOTO:
	  set_c++;
	  break;
	}
    }
}

/* Calculate cost of linear refresh */

#define CHANGED(pos) (cnew[pos] != cold[pos] || knew[pos] != kold[pos] || anew[pos] != aold[pos])
#define XCHANGED(pos) (CHANGED(pos) && (knew[pos] == kf && anew[pos] == af) != neg)

/* mode = 0		Refresh only changed fragments
 * mode = 1		Refresh changed fragments of given color
 * mode = 2		Refresh changed fragments with exception of given color
 */

#ifdef SOPHISTICATED_REFRESH

static int
linear_refresh_cost(int row, int pos0, int c0, int c1, int fa, int mode)
{
  int cost = 0;
  byte a0 = set_attrs;
  byte k0 = set_color;
  byte a1, k1;
  byte af = mode ? (fa >> 8) : 0xff;	/* 0xff cannot happen! */
  byte kf = fa & 0xff;
  int cc;
  int pos;
  int owr = (mode == 1);
  int neg = (mode != 1);

  if (c0 > c1)
    return 0;

  pos = pos0 + c0;
  while (c0 <= c1)
    {
      if (XCHANGED(pos))
	{
	  if (row >= 0)
	    {
	      cost += goto_cost(row, c0, NULL, NULL);
	      row = -1;
	    }
	  cost += attr_change_cost(a0, anew[pos], k0, knew[pos], NULL);
	  a0 = anew[pos];
	  k0 = knew[pos];
	  if (!cold[pos])		/* Need SP/BS because of overstriking */
	    cost += 2;
	  cost++;
	}
      else
	{
	  cc = c0;
	  while (c0 <= c1 && !XCHANGED(pos))
	    c0++, pos++;
	  if (a0 && !BOOL(CAN_MOVE_WITH_ATTR))
	    {
	      a0 = 0;
	      cost += cost_attr_reset_all;
	    }
	  if (row < 0)
	    {
	      a1 = set_attrs; k1 = set_color;
	      set_attrs = a0; set_color = k0;
	      cost += refresh_move_right_cost(cc, c0-cc, pos0, owr, NULL);
	      set_attrs = a1; set_color = k1;
	    }
	}
      pos++;
      c0++;
    }
  return cost;
}

#endif

/* Calculate cost of linear redraw after clear */

#define NONCLEAR(pos) (cnew[pos] != ' ' || knew[pos] != clr_color || anew[pos] != clr_attr)

static int
linear_redraw_cost(int pos0, int c0, int c1, byte clr_color, byte clr_attr)
{
  int cost = 0;
  byte a0 = clr_attr;
  byte k0 = clr_color;
  byte a1, k1;
  int cc;
  int pos;

  if (c0 > c1)
    return 0;

  pos = pos0 + c0;
  while (c0 <= c1)
    {
      if (NONCLEAR(pos))
	{
	  cost += attr_change_cost(a0, anew[pos], k0, knew[pos], NULL);
	  a0 = anew[pos];
	  k0 = knew[pos];
	  cost++;
	}
      else
	{
	  cc = c0;
	  while (c0 <= c1 && !NONCLEAR(pos))
	    c0++, pos++;
	  if (a0 && !BOOL(CAN_MOVE_WITH_ATTR))
	    {
	      a0 = 0;
	      cost += cost_attr_reset_all;
	    }
	  a1 = set_attrs; k1 = set_color;
	  set_attrs = a0; set_color = k0;
	  cost += refresh_move_right_cost(cc, c0-cc, pos0, 0, NULL);
	  set_attrs = a1; set_color = k1;
	}
      pos++;
      c0++;
    }

  return cost;
}

/* Calculate clearing color */

static byte
clearing_color(int pos, int width)
{
  byte bc[16], fc[16];
  int i;
  byte b, f, bb, ff;

  if (!BOOL(ERASES_WITH_BACK_COLOR))
    return default_color;

  bzero(bc, sizeof(bc));
  bzero(fc, sizeof(fc));
  while (width--)
    {
      bc[ BACK(knew[pos]) ]++;
      fc[ FORE(knew[pos]) ]++;
      pos++;
    }

  b = bb = f = ff = 0;
  for(i=0; i<16; i++)
    {
      if (bc[i] > bb)
	bb = bc[i], b = i;
      if (fc[i] > ff)
	ff = fc[i], f = i;
    }

  return COLOR(b,f);
}

/* Look at the left for more chars to clear */

static int
clear_left_extend(int pos0, int c, int lim, byte color, int penalty)
{
  int bestpen = penalty + 2;
  int bestc = c;
  int q, pos;

  TR("\tclear_left_extend(%d,%d,%d,%d)", c, lim, color, penalty);

  pos = pos0 + c;
  lim++;
  for(;;)
    {
      while (c >= lim && (cnew[pos-1] == ' ' || !anew[pos-1]) && knew[pos-1] == color)
	c--, pos--, penalty--;
      if (penalty < bestpen && penalty <= 0)
	bestpen = penalty, bestc = c;
      if (c < lim)
	break;
      q = c;
      while (c >= lim && (cnew[pos-1] != ' ' && anew[pos-1] || knew[pos-1] != color))
	c--, pos--;
      penalty += 3 + linear_redraw_cost(pos0, c, q-1, color, 0);
      if (penalty < bestpen && penalty <= 0)
	bestpen = penalty, bestc = c;
      if (c < lim)
	break;
    }

  TR(" -> %d@%d\n", bestpen, bestc);

  return bestc;
}

/* Look at the right for more chars to clear */

static int
clear_right_extend(int pos0, int c, int lim, byte color)
{
  int penalty = 0;
  int bestpen = 2;
  int bestc = c;
  int q, pos;

  TR("\tclear_right_extend(%d,%d,%d)", c, lim, color);

  c++;
  pos = pos0 + c;
  for(;;)
    {
      while (c <= lim && (cnew[pos] == ' ' || !anew[pos]) && knew[pos] == color)
	c++, pos++, penalty--;
      if (penalty < bestpen)
	bestpen = penalty, bestc = c-1;
      if (c > lim)
	break;
      q = c;
      while (c <= lim && (cnew[pos] != ' ' && anew[pos] || knew[pos] != color))
	c++, pos++;
      penalty += 3 + linear_redraw_cost(pos0, q, c-1, color, 0);
      if (penalty < bestpen)
	bestpen = penalty, bestc = c-1;
      if (c > lim)
	break;
    }

  TR(" -> %d@%d\n", bestpen, bestc);

  return bestc;
}

/* Perform clearing if needed */

static void
refresh_clearing(int row, int c0, int c1, int pos)
{
  int clr0 = c1 + 1;
  int clr1 = c0 - 1;
  int k, p;
  byte clr_color;

  if (BOOL(ONLY_CLR_RESETS_ATTR))	/* Need to reset attributes? */
    {
      p = pos + c0;
      for(k=c0; k<=c1; k++, p++)
	if (CHANGED(p) && aold[p] != anew[p])
	  {
	    if (k < clr0)
	      clr0 = k;
	    if (k > clr1)
	      clr1 = k;
	  }
      if (clr0 <= clr1)
	TR("\tClear enforced by attributes: %d..%d\n", clr0, clr1);
    }

  if (overstriking)			/* Need to process overstriking? */
    {
      int o0 = clr0;
      int o1 = clr1;

      p = pos + c0;
      for(k=c0; k<=c1; k++, p++)
	if (CHANGED(p) && cnew[p] != ' ' && cold[p] != ' ')
	  {
	    cold[p] = 0;		/* Special markup */
	    if (k < o0)
	      o0 = k;
	    if (k > o1)
	      o1 = k;
	  }

      if (o0 <= o1)
	{
	  if (overstriking == OS_CLEAR || !STR(LEFT) || (o1 == win_c1 && auto_margins))
	    {
	      clr0 = o0, clr1 = o1;
	      TR("\tConverting overstrike %d..%d to clear\n", o0, o1);
	    }
	  else
	    TR("\tOverstriking in region %d..%d\n", o0, o1);
	}
    }

  if (clr0 <= clr1 && !STR(CLEAR_N_CHARS)) /* Only clr-to-eol? */
    {
      if (!STR(CLEAR_TO_EOL))
	fatal_error("Must clear, but don't know how");
      clr1 = win_c1;
    }

  clr_color = clearing_color(pos+c0, c1-c0+1);
  if (clr0 <= clr1)			/* Try to extend the current clearing region */
    {
      clr0 = clear_left_extend(pos, clr0, c0, clr_color, 0);
      clr1 = clear_right_extend(pos, clr1, c1, clr_color);
      TR("\tExtending clear region to %d..%d\n", clr0, clr1);
    }
  else if (STR(CLEAR_N_CHARS) || STR(CLEAR_TO_EOL)) /* Try to gain some points by clearing */
    {
      clr0 = clear_left_extend(pos, c1+1, c0, clr_color, STR(CLEAR_N_CHARS) ? 0 :
			       linear_redraw_cost(pos, c1+1, win_c1, clr_color, 0));
      if (clr0 > c1)
	return;
      clr1 = c1;
      TR("\tLots of spaces, clearing %d..%d\n", clr0, clr1);
    }
  else
    return;

  cgoto(row, clr0);
  send_attrs(0, clr_color);
  if (STR(CLEAR_N_CHARS) && clr1 < win_c1)
    {
      TR("\tClearing %d chars from %d.%d\n", clr1-clr0+1, row, clr0);
      sendp(STR(CLEAR_N_CHARS), clr1 - clr0 + 1);
    }
  else
    {
      TR("\tClearing from %d.%d to EOL\n", row, clr0);
      send(STR(CLEAR_TO_EOL));
    }
  pos += clr0;
  while (clr0 <= clr1)
    {
      cold[pos] = ' ';
      aold[pos] = 0;
      kold[pos] = clr_color;
      pos++;
      clr0++;
    }
}

/* Find dominant attribute/color pair */

#ifdef SOPHISTICATED_REFRESH

#define ZIL 0xffff

static int
find_dominant_attr(int pos, int count)	/* Very tricky */
{
  word val[2*count], cn[2*count], nx[2*count];
  int fex = count;
  int r = count;
  word q, h;

  memset(val, 0xff, count);
  while (r--)
    {
      q = (anew[pos] << 8) | knew[pos];
      h = q % count;
      if (val[h] == ZIL)
	{
	  val[h] = q;
	  nx[h] = ZIL;
	  cn[h] = 1;
	}
      else
	{
	  while (val[h] != q && nx[h] != ZIL)
	    h = nx[h];
	  if (val[h] != q)
	    {
	      nx[h] = fex;
	      h = fex++;
	      val[h] = q;
	      nx[h] = ZIL;
	      cn[h] = 1;
	    }
	  else
	    cn[h]++;
	}
      pos++;
    }

  q = cn[0];
  h = 0;
  for(pos=1; pos<fex; pos++)
    if (val[pos] != ZIL && cn[pos] > q)
      q = cn[pos], h = val[pos];

  return h;
}

/* Estimate cost of refreshing fragment from right to left */

static int
backward_fragment_refresh_cost(int row, int pos0, int c0, int c1, int fa)
{
  int cost = 0;
  byte a0 = set_attrs;
  byte k0 = set_color;
  byte a1, k1;
  byte af = fa >> 8;
  byte kf = fa & 0xff;
  int cc;
  int pos;
  int neg = 0;
  int oc = -1;

  if (c0 > c1)
    return 0;

  pos = pos0 + c1;
  while (c1 >= c0)
    {
      if (XCHANGED(pos))
	{
	  cc = c1 + 1;
	  while (c1 >= c0 && XCHANGED(pos))
	    {
	      if (!cold[pos])		/* Need SP/BS because of overstriking */
		cost += 2;
	      cost++;
	      c1--, pos--;
	    }
	  a1 = set_attrs; k1 = set_color;
	  set_attrs = a0; set_color = k0;
	  if (oc >= 0)
	    cost += refresh_move_left_cost(oc, oc-c1, pos0, 1, NULL);
	  else
	    cost += goto_cost(row, c1, NULL, NULL);
	  set_attrs = a1; set_color = k1;
	  if (a0 && !BOOL(CAN_MOVE_WITH_ATTR))
	    {
	      a0 = 0;
	      cost += cost_attr_reset_all;
	    }
	  cost += attr_change_cost(a0, af, k0, kf);
	  a0 = af, k0 = kf;
	  oc = c1;
	  if (oc >= win_c1)
	    {
	      if (auto_margins == AM_DUMB || auto_margins == AM_CORNER)
		return 10000;
	      if (!auto_margins)
		oc--;
	    }
	}
      else
	pos--, c1--l
	  }
  return cost;
}

#endif

/* Perform sequence refresh */

static void
sequence_refresh(int pos, int pos0, int count)
{
  int k, pp, z, y, alg;

  TR("\tRfsh sequence %d,%d,%d (a=%02x, c=%02x)\n", pos, pos0, count, anew[pos], knew[pos]);

  send_attrs(anew[pos], knew[pos]);

  while (count)
    {
      if (!cold[pos])
	{
	  int c0 = set_c;
	  put_single_char(' ', pos);
	  if (set_c != c0)		/* Beware of auto-margins */
	    {
	      send(STR(LEFT));
	      set_c--;
	    }
	}
      if (count == 1 || cnew[pos] != cnew[pos+1])
	{
	  put_single_char(cnew[pos], pos);
	  pos++;
	  count--;
	  continue;
	}
      pp = pos;
      while (count > 0 && cnew[pos] == cnew[pp] && cold[pos])
	count--, pos++;
      k = pos - pp;
      if (cnew[pp] == ' ')		/* There are extra algorithms for multiple spaces */
	{
	  if (k > cost_clear_n + 3 && (BOOL(ERASES_WITH_BACK_COLOR) || (!set_attr && set_color == default_color)))
	    {
	      sendp(STR(CLEAR_N_CHARS), k);
	      while (pp < pos)
		{
		  cold[pp] = ' ';
		  kold[pp] = knew[pp];
		  aold[pp] = anew[pp];
		  pp++;
		}
	      if (count)
		{
		  refresh_move_right_cost(set_c, k, pos0, 0, &alg);
		  refresh_do_move_right(set_c, k, pos0, 0, alg);
		}
	      continue;
	    }
	  z = set_c + k;
	  while (NEXT_TAB_STOP(set_c) <= z && use_tabs == TABS_DESTRUCT)
	    {
	      y = NEXT_TAB_STOP(set_c);
	      if (y == set_c + 1)
		put_single_char(' ', pp++);
	      else
		{
		  sendpad(STR(TAB), INT(PAD_TAB));
		  while (set_c < y)
		    {
		      set_c++;
		      cold[pp] = ' ';
		      kold[pp] = knew[pp];
		      aold[pp] = anew[pp];
		      pp++;
		    }
		}
	    }
	}
      if (pos - pp > cost_repeat_char + 3)
	{
	  sendp(STR(REPEAT), cnew[pp], pos - pp);
	  while (pp < pos)
	    {
	      cold[pp] = cnew[pp];
	      kold[pp] = knew[pp];
	      aold[pp] = anew[pp];
	      pp++;
	    }
	  continue;
	}
      while (pp < pos)
	{
	  put_single_char(cnew[pp], pp);
	  pp++;
	}
    }
}

/* Perform left-to-right fragment refresh */

static void
forward_fragment_refresh(int row, int pos0, int c0, int c1, int fa)
{
  byte af = fa >> 8;
  byte kf = fa & 0xff;
  int pos, alg, pp;
  int oc = -1;

  TR("\tRefreshing forward fragment: %d..%d (color %04x)\n", c0, c1, fa);

  pos = pos0 + c0;
  while (c0 <= c1)
    if (CHANGED(pos) && ((fa < 0) ? 1 : (knew[pos] == kf && anew[pos] == af)))
      {
	if (oc < 0)
	  cgoto(row, c0);
	else
	  {
	    refresh_move_right_cost(oc, c0-oc, pos0, 1, &alg);
	    refresh_do_move_right(oc, c0-oc, pos0, 1, alg);
	  }
	pp = pos;
      rest:
	while (c0 <= c1 && CHANGED(pos) && anew[pos] == anew[pp] && knew[pos] == knew[pp])
	  pos++, c0++;
	if (c0 < c1 && cnew[pos] == cnew[pos-1] && anew[pos] == anew[pp] && knew[pos] == knew[pp] &&
	    cnew[pos+1] == cnew[pos] && CHANGED(pos+1) && anew[pos+1] == anew[pp] && knew[pos+1] == knew[pp])
	  {
	    pos++, c0++;		/* Holes of size 1 are allowed */
	    goto rest;
	  }
	sequence_refresh(pp, pos0, pos-pp);
	oc = set_c;
      }
    else
      pos++, c0++;
}

/* Perform right-to-left fragment refresh */

#ifdef SOPHISTICATED_REFRESH

static void
backward_fragment_refresh(int row, int pos0, int c0, int c1, int fa)
{
  byte af = fa >> 8;
  byte kf = fa & 0xff;
  int pos, alg;
  int oc = -1;

  pos = pos0 + c1;
  while (c0 <= c1)
    {
#error  ??? HIC SUNT LEONES ???
	}
}

#endif

/* Process simple cases of refreshing */

static inline int
try_simple_case(int row, int c0, int c1, int pos)
{
  int z, poz, p0;

  if (c1 >= columns - 1)		/* Beware the Jabberwock, my son! */
    return 0;

  p0 = pos;
  pos += c0;
  poz = pos;
  for(z=c0; z <= c1; z++, poz++)
    if ((overstriking && cold[poz] != ' ') ||
	anew[poz] != anew[pos] ||
	knew[poz] != knew[pos] ||
	(aold[poz] && BOOL(ONLY_CLR_RESETS_ATTR)))
      return 0;

  TR("\tSimple case, OK\n");

  forward_fragment_refresh(row, p0, c0, c1, -1);
  return 1;
}

/* Main multi-pass refresh of a line */

static inline void
refresh_main(int row, int pos, int c0, int c1)
{

#ifdef SOPHISTICATED_REFRESH

  while (c0 <= c1)
    {
      cost0 = linear_refresh_cost(row, pos, c0, c1, 0, 0);
      fa = find_dominant_attr(pos+c0, c1-c0+1);
      cost1 = cost2 = linear_refresh_cost(row, pos, c0, c1, fa, 1);
      cost1 += linear_refresh_cost(row, pos, c0, c1, fa, 2);
      cost2 += backward_fragment_refresh_cost(row, pos, c0, c1, fa);
      TR(("\tDominant attr=%04x, lcost=%d, fcost=%d, bcost=%d\n",
	  fa, cost0, cost1, cost2));

      if (cost1 < cost0 && cost1 <= cost2)
	forward_fragment_refresh(row, pos, c0, c1, fa);
      else if (cost2 < cost0)
	backward_fragment_refresh(row, pos, c0, c1, fa);
      else
	forward_fragment_refresh(row, pos, c0, c1, -1);

#error ??? and what about refreshing the whole region backwards ???

	      while (!CHANGED(pos + c0) && c0 <= c1)
		c0++;
	while (!CHANGED(pos + c1) && c0 <= c1)
	  c1--;
    }

#else

  forward_fragment_refresh(row, pos, c0, c1, -1);

#endif
}

/* Refresh single line */

static void
refresh_line(int row, int pos, int c0, int c1)
{
restart:
  while (!CHANGED(pos+c0) && c0 <= c1)	/* Correct bounds */
    c0++;
  while (!CHANGED(pos+c1) && c0 <= c1)
    c1--;
  if (c0 > c1)				/* Nothing to do */
    return;

  TR("Refreshing line %d, %d..%d\n", row, c0, c1);

  if (row == rows - 1 && c1 == win_c1)	/* Auto-margins can be a problem */
    {
      switch (auto_margins)
	{
	case AM_NO_CORNER:
	  {
	    int poz = pos + c1;
	    cnew[poz] = cold[poz];
	    knew[poz] = kold[poz];
	    anew[poz] = aold[poz];
	    TR("\tauto_margins: killing last position\n");
	    goto restart;
	  }
	case AM_DUMB:
	  {
	    int poz = pos + --c1;
	    byte c1 = cnew[poz];
	    byte k1 = knew[poz];
	    byte a1 = anew[poz];
	    cnew[poz] = cnew[poz+1];
	    knew[poz] = knew[poz+1];
	    anew[poz] = anew[poz+1];
	    TR("\tauto_margins: using insert trick\n");
	    refresh_line(row, pos, c0, c1);
	    TR("\tauto_margins: inserting last character of the screen\n");
	    cgoto(row, c1);
	    set_ins_mode(IM_INSERT);
	    send_attrs(a1, k1);
	    if (STR(INSERT_CHAR)[0])
	      sendp(STR(INSERT_CHAR), c1);
	    else
	      {
		send_char(c1);
		send(STR(POSTINSERT_CHAR));
	      }
	    return;
	  }
	}
    }

  if (row < win_r0 || row > win_r1 || c0 < win_c0 || c1 > win_c1)
    reset_window();
  if (ins_mode)
    set_ins_mode(0);

  if (try_simple_case(row, c0, c1, pos)) /* Simple cases first */
    return;

  refresh_clearing(row, c0, c1, pos);

  refresh_main(row, pos, c0, c1);
}

/* Refresh */

static void
tc_refresh(void)
{
  int pos = ltop * columns;

  byte *first = lfirst + ltop;
  byte *last = llast + ltop;

  while (ltop <= lbot)
    {
      if (*first <= *last)
	refresh_line(ltop, pos, *first, *last);
      *first++ = 0xff;
      *last++ = 0;
      ltop++;
      pos += columns;
    }
}

void
Trefresh(void)
{
  if (set_cm != current_cm)
    set_cursor_shape();

  TR("Trefresh called for %d..%d\n", ltop, lbot);

  if (use_vcsa)
    vcsa_refresh();
  else
    tc_refresh();

  ltop = 0xff;
  lbot = 0;

  switch (current_cm & CM_FOLLOWMASK)
    {
    case CM_FOLLOW:
      cgoto((write_r >= rows) ? (rows - 1) : write_r,
	    (write_c >= columns) ? (columns - 1) : write_c);
      break;
    case CM_FIXED:
      cgoto(lastc_r, lastc_c);
      break;
    }

  FLUSH;
}

/* Redraw */

void
Tredraw(void)
{
  TR("Complete redraw requested\n");
  set_r = set_c = -1;			/* Avoid cursor movement optimizations */
  cgoto(0, 0);
  light(0, 0, rows, columns);
  force_attrs(cls_attrs, cls_color);
  if (!try_cls())
    force_redraw();
  else
    light(0, 0, rows, columns);
  Trefresh();
}

void
force_redraw(void)
{
  bzero(cold, rows * columns);
  memset(kold, default_color, rows * columns);
  memset(aold, 0xff, rows * columns);
  light(0, 0, rows, columns);
}