1 /* $OpenBSD: hashmap.c,v 1.7 2002/06/22 18:13:05 deraadt Exp $ */ 2 3 /**************************************************************************** 4 * Copyright (c) 1998,2000 Free Software Foundation, Inc. * 5 * * 6 * Permission is hereby granted, free of charge, to any person obtaining a * 7 * copy of this software and associated documentation files (the * 8 * "Software"), to deal in the Software without restriction, including * 9 * without limitation the rights to use, copy, modify, merge, publish, * 10 * distribute, distribute with modifications, sublicense, and/or sell * 11 * copies of the Software, and to permit persons to whom the Software is * 12 * furnished to do so, subject to the following conditions: * 13 * * 14 * The above copyright notice and this permission notice shall be included * 15 * in all copies or substantial portions of the Software. * 16 * * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 20 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 21 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 22 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 23 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 24 * * 25 * Except as contained in this notice, the name(s) of the above copyright * 26 * holders shall not be used in advertising or otherwise to promote the * 27 * sale, use or other dealings in this Software without prior written * 28 * authorization. * 29 ****************************************************************************/ 30 31 /**************************************************************************** 32 * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 * 33 * and: Eric S. Raymond <esr@snark.thyrsus.com> * 34 ****************************************************************************/ 35 36 /****************************************************************************** 37 38 NAME 39 hashmap.c -- fill in scramble vector based on text hashes 40 41 SYNOPSIS 42 void _nc_hash_map(void) 43 44 DESCRIPTION: 45 This code attempts to recognize pairs of old and new lines in the physical 46 and virtual screens. When a line pair is recognized, the old line index is 47 placed in the oldindex member of the virtual screen line, to be used by the 48 vertical-motion optimizer portion of the update logic (see hardscroll.c). 49 50 Line pairs are recognized by applying a modified Heckel's algorithm, 51 sped up by hashing. If a line hash is unique in both screens, those 52 lines must be a pair. Then if the lines just before or after the pair 53 are the same or similar, they are a pair too. 54 55 We don't worry about false pairs produced by hash collisions, on the 56 assumption that such cases are rare and will only make the latter stages 57 of update less efficient, not introduce errors. 58 59 HOW TO TEST THIS: 60 61 Use the following production: 62 63 hashmap: hashmap.c 64 $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap 65 66 AUTHOR 67 Eric S. Raymond <esr@snark.thyrsus.com>, May 1996 68 Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997 69 70 *****************************************************************************/ 71 72 #include <curses.priv.h> 73 #include <term.h> /* for back_color_erase */ 74 75 MODULE_ID("$From: hashmap.c,v 1.36 2000/12/10 03:04:30 tom Exp $") 76 77 #ifdef HASHDEBUG 78 79 # define _tracef printf 80 # undef TR 81 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); } 82 # undef screen_lines 83 # define screen_lines MAXLINES 84 # define TEXTWIDTH 1 85 int oldnums[MAXLINES], reallines[MAXLINES]; 86 static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH]; 87 # define OLDNUM(n) oldnums[n] 88 # define OLDTEXT(n) oldtext[n] 89 # define NEWTEXT(m) newtext[m] 90 # define PENDING(n) 1 91 92 #else /* !HASHDEBUG */ 93 94 # define OLDNUM(n) _nc_oldnums[n] 95 # define OLDTEXT(n) curscr->_line[n].text 96 # define NEWTEXT(m) newscr->_line[m].text 97 # define TEXTWIDTH (curscr->_maxx+1) 98 # define PENDING(n) (newscr->_line[n].firstchar != _NOCHANGE) 99 100 #endif /* !HASHDEBUG */ 101 102 #define oldhash (SP->oldhash) 103 #define newhash (SP->newhash) 104 105 static inline unsigned long 106 hash(chtype * text) 107 { 108 int i; 109 chtype ch; 110 unsigned long result = 0; 111 for (i = TEXTWIDTH; i > 0; i--) { 112 ch = *text++; 113 result += (result << 5) + ch; 114 } 115 return result; 116 } 117 118 /* approximate update cost */ 119 static int 120 update_cost(chtype * from, chtype * to) 121 { 122 int cost = 0; 123 int i; 124 125 for (i = TEXTWIDTH; i > 0; i--) 126 if (*from++ != *to++) 127 cost++; 128 129 return cost; 130 } 131 static int 132 update_cost_from_blank(chtype * to) 133 { 134 int cost = 0; 135 int i; 136 chtype blank = BLANK; 137 138 if (back_color_erase) 139 blank |= (stdscr->_bkgd & A_COLOR); 140 141 for (i = TEXTWIDTH; i > 0; i--) 142 if (blank != *to++) 143 cost++; 144 145 return cost; 146 } 147 148 /* 149 * Returns true when moving line 'from' to line 'to' seems to be cost 150 * effective. 'blank' indicates whether the line 'to' would become blank. 151 */ 152 static inline bool 153 cost_effective(const int from, const int to, const bool blank) 154 { 155 int new_from; 156 157 if (from == to) 158 return FALSE; 159 160 new_from = OLDNUM(from); 161 if (new_from == _NEWINDEX) 162 new_from = from; 163 164 /* 165 * On the left side of >= is the cost before moving; 166 * on the right side -- cost after moving. 167 */ 168 return (((blank ? update_cost_from_blank(NEWTEXT(to)) 169 : update_cost(OLDTEXT(to), NEWTEXT(to))) 170 + update_cost(OLDTEXT(new_from), NEWTEXT(from))) 171 >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from)) 172 : update_cost(OLDTEXT(new_from), NEWTEXT(from))) 173 + update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE; 174 } 175 176 typedef struct { 177 unsigned long hashval; 178 int oldcount, newcount; 179 int oldindex, newindex; 180 } sym; 181 182 static sym *hashtab = 0; 183 static int lines_alloc = 0; 184 185 static void 186 grow_hunks(void) 187 { 188 int start, end, shift; 189 int back_limit, forward_limit; /* limits for cells to fill */ 190 int back_ref_limit, forward_ref_limit; /* limits for refrences */ 191 int i; 192 int next_hunk; 193 194 /* 195 * This is tricky part. We have unique pairs to use as anchors. 196 * Use these to deduce the presence of spans of identical lines. 197 */ 198 back_limit = 0; 199 back_ref_limit = 0; 200 201 i = 0; 202 while (i < screen_lines && OLDNUM(i) == _NEWINDEX) 203 i++; 204 for (; i < screen_lines; i = next_hunk) { 205 start = i; 206 shift = OLDNUM(i) - i; 207 208 /* get forward limit */ 209 i = start + 1; 210 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i 211 == shift) 212 i++; 213 end = i; 214 while (i < screen_lines && OLDNUM(i) == _NEWINDEX) 215 i++; 216 next_hunk = i; 217 forward_limit = i; 218 if (i >= screen_lines || OLDNUM(i) >= i) 219 forward_ref_limit = i; 220 else 221 forward_ref_limit = OLDNUM(i); 222 223 i = start - 1; 224 /* grow back */ 225 if (shift < 0) 226 back_limit = back_ref_limit + (-shift); 227 while (i >= back_limit) { 228 if (newhash[i] == oldhash[i + shift] 229 || cost_effective(i + shift, i, shift < 0)) { 230 OLDNUM(i) = i + shift; 231 TR(TRACE_UPDATE | TRACE_MOVE, 232 ("connected new line %d to old line %d (backward continuation)", 233 i, i + shift)); 234 } else { 235 TR(TRACE_UPDATE | TRACE_MOVE, 236 ("not connecting new line %d to old line %d (backward continuation)", 237 i, i + shift)); 238 break; 239 } 240 i--; 241 } 242 243 i = end; 244 /* grow forward */ 245 if (shift > 0) 246 forward_limit = forward_ref_limit - shift; 247 while (i < forward_limit) { 248 if (newhash[i] == oldhash[i + shift] 249 || cost_effective(i + shift, i, shift > 0)) { 250 OLDNUM(i) = i + shift; 251 TR(TRACE_UPDATE | TRACE_MOVE, 252 ("connected new line %d to old line %d (forward continuation)", 253 i, i + shift)); 254 } else { 255 TR(TRACE_UPDATE | TRACE_MOVE, 256 ("not connecting new line %d to old line %d (forward continuation)", 257 i, i + shift)); 258 break; 259 } 260 i++; 261 } 262 263 back_ref_limit = back_limit = i; 264 if (shift > 0) 265 back_ref_limit += shift; 266 } 267 } 268 269 NCURSES_EXPORT(void) 270 _nc_hash_map(void) 271 { 272 sym *sp; 273 register int i; 274 int start, shift, size; 275 276 if (screen_lines > lines_alloc) { 277 if (hashtab) 278 free(hashtab); 279 hashtab = typeMalloc(sym, (screen_lines + 1) * 2); 280 if (!hashtab) { 281 if (oldhash) { 282 FreeAndNull(oldhash); 283 } 284 lines_alloc = 0; 285 return; 286 } 287 lines_alloc = screen_lines; 288 } 289 290 if (oldhash && newhash) { 291 /* re-hash only changed lines */ 292 for (i = 0; i < screen_lines; i++) { 293 if (PENDING(i)) 294 newhash[i] = hash(NEWTEXT(i)); 295 } 296 } else { 297 /* re-hash all */ 298 if (oldhash == 0) 299 oldhash = typeCalloc(unsigned long, screen_lines); 300 if (newhash == 0) 301 newhash = typeCalloc(unsigned long, screen_lines); 302 if (!oldhash || !newhash) 303 return; /* malloc failure */ 304 for (i = 0; i < screen_lines; i++) { 305 newhash[i] = hash(NEWTEXT(i)); 306 oldhash[i] = hash(OLDTEXT(i)); 307 } 308 } 309 310 #ifdef HASH_VERIFY 311 for (i = 0; i < screen_lines; i++) { 312 if (newhash[i] != hash(NEWTEXT(i))) 313 fprintf(stderr, "error in newhash[%d]\n", i); 314 if (oldhash[i] != hash(OLDTEXT(i))) 315 fprintf(stderr, "error in oldhash[%d]\n", i); 316 } 317 #endif 318 319 /* 320 * Set up and count line-hash values. 321 */ 322 memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2); 323 for (i = 0; i < screen_lines; i++) { 324 unsigned long hashval = oldhash[i]; 325 326 for (sp = hashtab; sp->hashval; sp++) 327 if (sp->hashval == hashval) 328 break; 329 sp->hashval = hashval; /* in case this is a new entry */ 330 sp->oldcount++; 331 sp->oldindex = i; 332 } 333 for (i = 0; i < screen_lines; i++) { 334 unsigned long hashval = newhash[i]; 335 336 for (sp = hashtab; sp->hashval; sp++) 337 if (sp->hashval == hashval) 338 break; 339 sp->hashval = hashval; /* in case this is a new entry */ 340 sp->newcount++; 341 sp->newindex = i; 342 343 OLDNUM(i) = _NEWINDEX; /* initialize old indices array */ 344 } 345 346 /* 347 * Mark line pairs corresponding to unique hash pairs. 348 * 349 * We don't mark lines with offset 0, because it can make fail 350 * extending hunks by cost_effective. Otherwise, it does not 351 * have any side effects. 352 */ 353 for (sp = hashtab; sp->hashval; sp++) 354 if (sp->oldcount == 1 && sp->newcount == 1 355 && sp->oldindex != sp->newindex) { 356 TR(TRACE_UPDATE | TRACE_MOVE, 357 ("new line %d is hash-identical to old line %d (unique)", 358 sp->newindex, sp->oldindex)); 359 OLDNUM(sp->newindex) = sp->oldindex; 360 } 361 362 grow_hunks(); 363 364 /* 365 * Eliminate bad or impossible shifts -- this includes removing 366 * those hunks which could not grow because of conflicts, as well 367 * those which are to be moved too far, they are likely to destroy 368 * more than carry. 369 */ 370 for (i = 0; i < screen_lines;) { 371 while (i < screen_lines && OLDNUM(i) == _NEWINDEX) 372 i++; 373 if (i >= screen_lines) 374 break; 375 start = i; 376 shift = OLDNUM(i) - i; 377 i++; 378 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i 379 == shift) 380 i++; 381 size = i - start; 382 if (size < 3 || size + min(size / 8, 2) < abs(shift)) { 383 while (start < i) { 384 OLDNUM(start) = _NEWINDEX; 385 start++; 386 } 387 } 388 } 389 390 /* After clearing invalid hunks, try grow the rest. */ 391 grow_hunks(); 392 393 #if NO_LEAKS 394 FreeAndNull(hashtab); 395 lines_alloc = 0; 396 #endif 397 } 398 399 NCURSES_EXPORT(void) 400 _nc_make_oldhash(int i) 401 { 402 if (oldhash) 403 oldhash[i] = hash(OLDTEXT(i)); 404 } 405 406 NCURSES_EXPORT(void) 407 _nc_scroll_oldhash(int n, int top, int bot) 408 { 409 int size; 410 int i; 411 412 if (!oldhash) 413 return; 414 415 size = sizeof(*oldhash) * (bot - top + 1 - abs(n)); 416 if (n > 0) { 417 memmove(oldhash + top, oldhash + top + n, size); 418 for (i = bot; i > bot - n; i--) 419 oldhash[i] = hash(OLDTEXT(i)); 420 } else { 421 memmove(oldhash + top - n, oldhash + top, size); 422 for (i = top; i < top - n; i++) 423 oldhash[i] = hash(OLDTEXT(i)); 424 } 425 } 426 427 #ifdef HASHDEBUG 428 static void 429 usage(void) 430 { 431 static const char *table[] = 432 { 433 "hashmap test-driver", 434 "", 435 "# comment", 436 "l get initial line number vector", 437 "n use following letters as text of new lines", 438 "o use following letters as text of old lines", 439 "d dump state of test arrays", 440 "h apply hash mapper and see scroll optimization", 441 "? this message" 442 }; 443 size_t n; 444 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++) 445 fprintf(stderr, "%s\n", table[n]); 446 } 447 448 int 449 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) 450 { 451 char line[BUFSIZ], *st, *last; 452 int n; 453 454 SP = typeCalloc(SCREEN, 1); 455 for (n = 0; n < screen_lines; n++) { 456 reallines[n] = n; 457 oldnums[n] = _NEWINDEX; 458 oldtext[n][0] = newtext[n][0] = '.'; 459 } 460 461 if (isatty(fileno(stdin))) 462 usage(); 463 464 #ifdef TRACE 465 _nc_tracing = TRACE_MOVE; 466 #endif 467 for (;;) { 468 /* grab a test command */ 469 if (fgets(line, sizeof(line), stdin) == (char *) NULL) 470 exit(EXIT_SUCCESS); 471 472 switch (line[0]) { 473 case '#': /* comment */ 474 (void) fputs(line, stderr); 475 break; 476 477 case 'l': /* get initial line number vector */ 478 for (n = 0; n < screen_lines; n++) { 479 reallines[n] = n; 480 oldnums[n] = _NEWINDEX; 481 } 482 n = 0; 483 st = strtok_r(line, " ", &last); 484 do { 485 oldnums[n++] = atoi(st); 486 } while 487 ((st = strtok_r((char *) NULL, " "), &last) != 0); 488 break; 489 490 case 'n': /* use following letters as text of new lines */ 491 for (n = 0; n < screen_lines; n++) 492 newtext[n][0] = '.'; 493 for (n = 0; n < screen_lines; n++) 494 if (line[n + 1] == '\n') 495 break; 496 else 497 newtext[n][0] = line[n + 1]; 498 break; 499 500 case 'o': /* use following letters as text of old lines */ 501 for (n = 0; n < screen_lines; n++) 502 oldtext[n][0] = '.'; 503 for (n = 0; n < screen_lines; n++) 504 if (line[n + 1] == '\n') 505 break; 506 else 507 oldtext[n][0] = line[n + 1]; 508 break; 509 510 case 'd': /* dump state of test arrays */ 511 #ifdef TRACE 512 _nc_linedump(); 513 #endif 514 (void) fputs("Old lines: [", stdout); 515 for (n = 0; n < screen_lines; n++) 516 putchar(oldtext[n][0]); 517 putchar(']'); 518 putchar('\n'); 519 (void) fputs("New lines: [", stdout); 520 for (n = 0; n < screen_lines; n++) 521 putchar(newtext[n][0]); 522 putchar(']'); 523 putchar('\n'); 524 break; 525 526 case 'h': /* apply hash mapper and see scroll optimization */ 527 _nc_hash_map(); 528 (void) fputs("Result:\n", stderr); 529 #ifdef TRACE 530 _nc_linedump(); 531 #endif 532 _nc_scroll_optimize(); 533 (void) fputs("Done.\n", stderr); 534 break; 535 case '?': 536 usage(); 537 break; 538 } 539 } 540 return EXIT_SUCCESS; 541 } 542 543 #endif /* HASHDEBUG */ 544 545 /* hashmap.c ends here */ 546