#include <config.h>
#include "termchar.h"
#include "lisp.h"
#include "dispextern.h"
#include "frame.h"
extern struct display_line **ophys_lines;
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INFINITY 1000000
struct matrix_elt
{
int writecost;
int insertcost;
int deletecost;
unsigned char insertcount;
unsigned char deletecount;
unsigned char writecount;
};
static void
calculate_scrolling (frame, matrix, window_size, lines_below,
draw_cost, old_hash, new_hash,
free_at_end)
FRAME_PTR frame;
struct matrix_elt *matrix;
int window_size;
int *draw_cost;
int *old_hash;
int *new_hash;
int free_at_end;
{
register int i, j;
int frame_height = FRAME_HEIGHT (frame);
register struct matrix_elt *p, *p1;
register int cost, cost1;
int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below);
int *first_insert_cost
= &FRAME_INSERT_COST (frame)[frame_height - 1 - lines_moved];
int *first_delete_cost
= &FRAME_DELETE_COST (frame)[frame_height - 1 - lines_moved];
int *next_insert_cost
= &FRAME_INSERTN_COST (frame)[frame_height - 1 - lines_moved];
int *next_delete_cost
= &FRAME_DELETEN_COST (frame)[frame_height - 1 - lines_moved];
int extra_cost = baud_rate / (10 * 4 * FRAME_HEIGHT (frame));
if (baud_rate <= 0)
extra_cost = 1;
matrix->writecost = 0;
matrix->insertcost = INFINITY;
matrix->deletecost = INFINITY;
matrix->insertcount = 0;
matrix->deletecount = 0;
cost = first_insert_cost[1] - next_insert_cost[1];
for (i = 1; i <= window_size; i++)
{
p = matrix + i * (window_size + 1);
cost += draw_cost[i] + next_insert_cost[i] + extra_cost;
p->insertcost = cost;
p->writecost = INFINITY;
p->deletecost = INFINITY;
p->insertcount = i;
p->deletecount = 0;
}
cost = first_delete_cost[1] - next_delete_cost[1];
for (j = 1; j <= window_size; j++)
{
cost += next_delete_cost[j];
matrix[j].deletecost = cost;
matrix[j].writecost = INFINITY;
matrix[j].insertcost = INFINITY;
matrix[j].deletecount = j;
matrix[j].insertcount = 0;
}
p = matrix + window_size + 2;
for (i = 1; i <= window_size; i++, p++)
for (j = 1; j <= window_size; j++, p++)
{
p1 = p - window_size - 2;
cost = p1->writecost;
if (cost > p1->insertcost)
cost = p1->insertcost;
if (cost > p1->deletecost)
cost = p1->deletecost;
if (old_hash[j] != new_hash[i])
cost += draw_cost[i];
p->writecost = cost;
p1 = p - window_size - 1;
if (free_at_end == i)
{
cost = p1->writecost;
cost1 = p1->insertcost;
}
else
{
cost = p1->writecost + first_insert_cost[i];
if ((int) p1->insertcount > i)
abort ();
cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
}
p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost;
p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
if ((int) p->insertcount > i)
abort ();
p1 = p - 1;
if (free_at_end == i)
{
cost = p1->writecost;
cost1 = p1->deletecost;
}
else
{
cost = p1->writecost + first_delete_cost[i];
cost1 = p1->deletecost + next_delete_cost[i];
}
p->deletecost = min (cost, cost1);
p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
}
}
static void
do_scrolling (frame, matrix, window_size, unchanged_at_top)
FRAME_PTR frame;
struct matrix_elt *matrix;
int window_size;
int unchanged_at_top;
{
register struct matrix_elt *p;
register int i, j;
register struct frame_glyphs *current_frame;
register struct frame_glyphs *temp_frame;
struct queue { int count, pos; } *queue;
int offset = unchanged_at_top;
int qi = 0;
int window = 0;
register int tem;
int next;
queue = (struct queue *) alloca (FRAME_HEIGHT (frame)
* sizeof (struct queue));
current_frame = FRAME_CURRENT_GLYPHS (frame);
temp_frame = FRAME_TEMP_GLYPHS (frame);
bcopy (current_frame->glyphs, temp_frame->glyphs,
current_frame->height * sizeof (GLYPH *));
bcopy (current_frame->charstarts, temp_frame->charstarts,
current_frame->height * sizeof (int *));
bcopy (current_frame->used, temp_frame->used,
current_frame->height * sizeof (int));
bcopy (current_frame->highlight, temp_frame->highlight,
current_frame->height * sizeof (char));
bzero (temp_frame->enable, temp_frame->height * sizeof (char));
bcopy (current_frame->bufp, temp_frame->bufp,
current_frame->height * sizeof (int));
#ifdef HAVE_WINDOW_SYSTEM
if (FRAME_WINDOW_P (frame))
{
bcopy (current_frame->top_left_x, temp_frame->top_left_x,
current_frame->height * sizeof (short));
bcopy (current_frame->top_left_y, temp_frame->top_left_y,
current_frame->height * sizeof (short));
bcopy (current_frame->pix_width, temp_frame->pix_width,
current_frame->height * sizeof (short));
bcopy (current_frame->pix_height, temp_frame->pix_height,
current_frame->height * sizeof (short));
bcopy (current_frame->max_ascent, temp_frame->max_ascent,
current_frame->height * sizeof (short));
}
#endif
i = j = window_size;
while (i > 0 || j > 0)
{
p = matrix + i * (window_size + 1) + j;
tem = p->insertcost;
if (tem < p->writecost && tem < p->deletecost)
{
queue[qi].count = p->insertcount;
i -= p->insertcount;
queue[qi++].pos = i + unchanged_at_top;
}
else if (p->deletecost < p->writecost)
{
j -= p->deletecount;
if (!window)
{
set_terminal_window (window_size + unchanged_at_top);
window = 1;
}
ins_del_lines (j + unchanged_at_top, - p->deletecount);
}
else
{
current_frame->glyphs[i + offset - 1]
= temp_frame->glyphs[j + offset - 1];
current_frame->charstarts[i + offset - 1]
= temp_frame->charstarts[j + offset - 1];
current_frame->used[i + offset - 1]
= temp_frame->used[j + offset - 1];
current_frame->highlight[i + offset - 1]
= temp_frame->highlight[j + offset - 1];
temp_frame->enable[j + offset - 1] = 1;
i--;
j--;
}
}
if (!window && qi)
{
set_terminal_window (window_size + unchanged_at_top);
window = 1;
}
next = unchanged_at_top;
for (i = qi - 1; i >= 0; i--)
{
ins_del_lines (queue[i].pos, queue[i].count);
tem = queue[i].pos;
for (j = tem + queue[i].count - 1; j >= tem; j--)
{
current_frame->enable[j] = 0;
while (temp_frame->enable[next])
next++;
current_frame->glyphs[j] = temp_frame->glyphs[next];
current_frame->charstarts[j] = temp_frame->charstarts[next++];
}
}
if (window)
set_terminal_window (0);
}
static void
calculate_direct_scrolling (frame, matrix, window_size, lines_below,
draw_cost, old_draw_cost, old_hash, new_hash,
free_at_end)
FRAME_PTR frame;
struct matrix_elt *matrix;
int window_size;
int *draw_cost;
int *old_draw_cost;
int *old_hash;
int *new_hash;
int free_at_end;
{
register int i, j;
int frame_height = FRAME_HEIGHT (frame);
register struct matrix_elt *p, *p1;
register int cost, cost1, delta;
int *first_insert_cost
= &FRAME_INSERT_COST (frame)[frame_height - 1];
int *first_delete_cost
= &FRAME_DELETE_COST (frame)[frame_height - 1];
int *next_insert_cost
= &FRAME_INSERTN_COST (frame)[frame_height - 1];
int *next_delete_cost
= &FRAME_DELETEN_COST (frame)[frame_height - 1];
int scroll_overhead;
int extra_cost = baud_rate / (10 * 4 * FRAME_HEIGHT (frame));
if (baud_rate <= 0)
extra_cost = 1;
scroll_overhead = scroll_region_cost + extra_cost;
matrix->writecost = 0;
matrix->insertcost = INFINITY;
matrix->deletecost = INFINITY;
matrix->writecount = 0;
matrix->insertcount = 0;
matrix->deletecount = 0;
cost = 0;
for (i = 1; i <= window_size; i++)
{
p = matrix + i * (window_size + 1);
cost += draw_cost[i];
p->insertcost = cost;
p->writecost = INFINITY;
p->deletecost = INFINITY;
p->insertcount = i;
p->writecount = 0;
p->deletecount = 0;
}
for (j = 1; j <= window_size; j++)
{
matrix[j].deletecost = 0;
matrix[j].writecost = INFINITY;
matrix[j].insertcost = INFINITY;
matrix[j].deletecount = j;
matrix[j].writecount = 0;
matrix[j].insertcount = 0;
}
p = matrix + window_size + 2;
for (i = 1; i <= window_size; i++, p++)
for (j = 1; j <= window_size; j++, p++)
{
p1 = p - window_size - 2;
cost = p1->insertcost;
if (cost > p1->deletecost)
cost = p1->deletecost;
cost1 = p1->writecost;
if (i == j)
{
if (cost > cost1)
{
cost = cost1;
p->writecount = p1->writecount + 1;
}
else
p->writecount = 1;
if (old_hash[j] != new_hash[i])
{
cost += draw_cost[i];
}
}
else
{
if (i > j)
{
delta = i - j;
cost += scroll_overhead + first_insert_cost[-delta] +
(delta-1) * (next_insert_cost[-delta] + extra_cost);
cost1 += first_insert_cost[-j] - first_insert_cost[1-j] +
(delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]);
}
else
{
delta = j - i;
cost += scroll_overhead + first_delete_cost[-delta] +
(delta-1) * (next_delete_cost[-delta] + extra_cost);
cost1 += first_delete_cost[-i] - first_delete_cost[1-i] +
(delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]);
}
if (cost1 < cost)
{
cost = cost1;
p->writecount = p1->writecount + 1;
}
else
p->writecount = 1;
if (old_hash[j] != new_hash[i])
{
cost += draw_cost[i] + old_draw_cost[j];
}
}
p->writecost = cost;
p1 = p - window_size - 1;
cost = p1->writecost;
if (i > j && p1->deletecost < cost)
cost = p1->deletecost;
if (p1->insertcost <= cost)
{
cost = p1->insertcost;
p->insertcount = p1->insertcount + 1;
}
else
p->insertcount = 1;
cost += draw_cost[i];
p->insertcost = cost;
p1 = p - 1;
cost = p1->writecost;
if (i < j && p1->insertcost < cost)
cost = p1->insertcost;
cost1 = p1->deletecost;
if (p1->deletecost <= cost)
{
cost = p1->deletecost;
p->deletecount = p1->deletecount + 1;
}
else
p->deletecount = 1;
p->deletecost = cost;
}
}
static void
do_direct_scrolling (frame, matrix, window_size, unchanged_at_top)
FRAME_PTR frame;
struct matrix_elt *matrix;
int window_size;
int unchanged_at_top;
{
register struct matrix_elt *p;
register int i, j;
register struct frame_glyphs *current_frame;
register struct frame_glyphs *temp_frame;
struct alt_queue { int count, pos, window; } *queue;
int offset = unchanged_at_top;
int qi = 0;
int window = 0;
register int tem;
int next;
int write_follows = 1;
queue = (struct alt_queue *) alloca (FRAME_HEIGHT (frame)
* sizeof (struct alt_queue));
current_frame = FRAME_CURRENT_GLYPHS (frame);
temp_frame = FRAME_TEMP_GLYPHS (frame);
bcopy (current_frame->glyphs, temp_frame->glyphs,
current_frame->height * sizeof (GLYPH *));
bcopy (current_frame->charstarts, temp_frame->charstarts,
current_frame->height * sizeof (GLYPH *));
bcopy (current_frame->used, temp_frame->used,
current_frame->height * sizeof (int));
bcopy (current_frame->highlight, temp_frame->highlight,
current_frame->height * sizeof (char));
bzero (temp_frame->enable, temp_frame->height * sizeof (char));
bcopy (current_frame->bufp, temp_frame->bufp,
current_frame->height * sizeof (int));
#ifdef HAVE_WINDOW_SYSTEM
if (FRAME_WINDOW_P (frame))
{
bcopy (current_frame->top_left_x, temp_frame->top_left_x,
current_frame->height * sizeof (short));
bcopy (current_frame->top_left_y, temp_frame->top_left_y,
current_frame->height * sizeof (short));
bcopy (current_frame->pix_width, temp_frame->pix_width,
current_frame->height * sizeof (short));
bcopy (current_frame->pix_height, temp_frame->pix_height,
current_frame->height * sizeof (short));
bcopy (current_frame->max_ascent, temp_frame->max_ascent,
current_frame->height * sizeof (short));
}
#endif
i = j = window_size;
while (i > 0 || j > 0)
{
p = matrix + i * (window_size + 1) + j;
tem = p->insertcost;
if (tem < p->writecost && tem < p->deletecost
&& (write_follows || i < j))
{
write_follows = 0;
queue[qi].window = i + unchanged_at_top;
queue[qi].count = 0;
i -= p->insertcount;
queue[qi++].pos = i + unchanged_at_top;
}
else if (p->deletecost < p->writecost && (write_follows || i > j))
{
write_follows = 0;
j -= p->deletecount;
}
else
{
write_follows = 1;
tem = p->writecount;
if (i > j)
{
set_terminal_window (i + unchanged_at_top);
window = 1;
ins_del_lines (j - tem + unchanged_at_top, i - j);
}
else if (i < j)
{
queue[qi].pos = i - tem + unchanged_at_top;
queue[qi].window = j + unchanged_at_top;
queue[qi++].count = i - j;
}
while (tem > 0)
{
i--;
j--;
tem--;
current_frame->glyphs[i + offset]
= temp_frame->glyphs[j + offset];
current_frame->charstarts[i + offset]
= temp_frame->charstarts[j + offset];
current_frame->used[i + offset]
= temp_frame->used[j + offset];
current_frame->highlight[i + offset]
= temp_frame->highlight[j + offset];
temp_frame->enable[j + offset] = 1;
}
}
}
next = unchanged_at_top;
for (i = qi - 1; i >= 0; i--)
{
if (queue[i].count)
{
set_terminal_window (queue[i].window);
window = 1;
ins_del_lines (queue[i].pos, queue[i].count);
}
else
{
tem = queue[i].pos;
for (j = queue[i].window - 1; j >= tem; j--)
{
current_frame->enable[j] = 0;
while (temp_frame->enable[next])
next++;
current_frame->glyphs[j] = temp_frame->glyphs[next];
current_frame->charstarts[j] = temp_frame->charstarts[next++];
}
}
}
if (window)
set_terminal_window (0);
}
void
scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
draw_cost, old_draw_cost, old_hash, new_hash, free_at_end)
FRAME_PTR frame;
int window_size, unchanged_at_top, unchanged_at_bottom;
int *draw_cost;
int *old_draw_cost;
int *old_hash;
int *new_hash;
int free_at_end;
{
struct matrix_elt *matrix;
matrix = ((struct matrix_elt *)
alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
if (scroll_region_ok)
{
calculate_direct_scrolling (frame, matrix, window_size,
unchanged_at_bottom,
draw_cost, old_draw_cost,
old_hash, new_hash, free_at_end);
do_direct_scrolling (frame, matrix, window_size, unchanged_at_top);
}
else
{
calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
draw_cost, old_hash, new_hash,
free_at_end);
do_scrolling (frame, matrix, window_size, unchanged_at_top);
}
}
int
scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
int start, end;
int *oldhash, *newhash, *cost;
{
struct { int hash; int count; } lines[01000];
register int i, h;
register int matchcount = 0;
int avg_length = 0;
int threshold;
for (i = start; i < end; i++)
avg_length += cost[i];
avg_length /= end - start;
threshold = avg_length / 4;
bzero (lines, sizeof lines);
for (i = start; i < end; i++)
{
if (cost[i] > threshold)
{
h = newhash[i] & 0777;
lines[h].hash = newhash[i];
lines[h].count++;
}
}
for (i = start; i < end; i++)
{
h = oldhash[i] & 0777;
if (oldhash[i] == lines[h].hash)
{
matchcount++;
if (--lines[h].count == 0)
lines[h].hash = 0;
}
}
return matchcount;
}
int
scroll_cost (frame, from, to, amount)
FRAME_PTR frame;
int from, to, amount;
{
int limit = to;
int offset;
int height = FRAME_HEIGHT (frame);
if (amount == 0)
return 0;
if (! scroll_region_ok)
limit = height;
else if (amount > 0)
limit += amount;
if (amount < 0)
{
int temp = to;
to = from + amount;
from = temp + amount;
amount = - amount;
}
offset = height - limit;
return
(FRAME_INSERT_COST (frame)[offset + from]
+ (amount - 1) * FRAME_INSERTN_COST (frame)[offset + from]
+ FRAME_DELETE_COST (frame)[offset + to]
+ (amount - 1) * FRAME_DELETEN_COST (frame)[offset + to]);
}
static void
line_ins_del (frame, ov1, pf1, ovn, pfn, ov, mf)
FRAME_PTR frame;
int ov1, ovn;
int pf1, pfn;
register int *ov, *mf;
{
register int i;
register int frame_height = FRAME_HEIGHT (frame);
register int insert_overhead = ov1 * 10;
register int next_insert_cost = ovn * 10;
for (i = frame_height-1; i >= 0; i--)
{
mf[i] = next_insert_cost / 10;
next_insert_cost += pfn;
ov[i] = (insert_overhead + next_insert_cost) / 10;
insert_overhead += pf1;
}
}
static void
ins_del_costs (frame,
one_line_string, multi_string,
setup_string, cleanup_string,
costvec, ncostvec, coefficient)
FRAME_PTR frame;
char *one_line_string, *multi_string;
char *setup_string, *cleanup_string;
int *costvec, *ncostvec;
int coefficient;
{
if (multi_string)
line_ins_del (frame,
string_cost (multi_string) * coefficient,
per_line_cost (multi_string) * coefficient,
0, 0, costvec, ncostvec);
else if (one_line_string)
line_ins_del (frame,
string_cost (setup_string) + string_cost (cleanup_string), 0,
string_cost (one_line_string),
per_line_cost (one_line_string),
costvec, ncostvec);
else
line_ins_del (frame,
9999, 0, 9999, 0,
costvec, ncostvec);
}
void
do_line_insertion_deletion_costs (frame,
ins_line_string, multi_ins_string,
del_line_string, multi_del_string,
setup_string, cleanup_string, coefficient)
FRAME_PTR frame;
char *ins_line_string, *multi_ins_string;
char *del_line_string, *multi_del_string;
char *setup_string, *cleanup_string;
int coefficient;
{
if (FRAME_INSERT_COST (frame) != 0)
{
FRAME_INSERT_COST (frame) =
(int *) xrealloc (FRAME_INSERT_COST (frame),
FRAME_HEIGHT (frame) * sizeof (int));
FRAME_DELETEN_COST (frame) =
(int *) xrealloc (FRAME_DELETEN_COST (frame),
FRAME_HEIGHT (frame) * sizeof (int));
FRAME_INSERTN_COST (frame) =
(int *) xrealloc (FRAME_INSERTN_COST (frame),
FRAME_HEIGHT (frame) * sizeof (int));
FRAME_DELETE_COST (frame) =
(int *) xrealloc (FRAME_DELETE_COST (frame),
FRAME_HEIGHT (frame) * sizeof (int));
}
else
{
FRAME_INSERT_COST (frame) =
(int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
FRAME_DELETEN_COST (frame) =
(int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
FRAME_INSERTN_COST (frame) =
(int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
FRAME_DELETE_COST (frame) =
(int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
}
ins_del_costs (frame,
ins_line_string, multi_ins_string,
setup_string, cleanup_string,
FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
coefficient);
ins_del_costs (frame,
del_line_string, multi_del_string,
setup_string, cleanup_string,
FRAME_DELETE_COST (frame), FRAME_DELETEN_COST (frame),
coefficient);
}