1 /*	$NetBSD: scores.c,v 1.26 2021/05/02 12:50:46 rillig Exp $	*/
2 
3 /*-
4  * Copyright (c) 1992, 1993
5  *	The Regents of the University of California.  All rights reserved.
6  *
7  * This code is derived from software contributed to Berkeley by
8  * Chris Torek and Darren F. Provine.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 3. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  *
34  *	@(#)scores.c	8.1 (Berkeley) 5/31/93
35  */
36 
37 /*
38  * Score code for Tetris, by Darren Provine (kilroy@gboro.glassboro.edu)
39  * modified 22 January 1992, to limit the number of entries any one
40  * person has.
41  *
42  * Major whacks since then.
43  */
44 #include <err.h>
45 #include <errno.h>
46 #include <fcntl.h>
47 #include <pwd.h>
48 #include <stdio.h>
49 #include <stdlib.h>
50 #include <string.h>
51 #include <sys/stat.h>
52 #include <time.h>
53 #include <term.h>
54 #include <unistd.h>
55 
56 #include "pathnames.h"
57 #include "screen.h"
58 #include "scores.h"
59 #include "tetris.h"
60 
61 /*
62  * Allow updating the high scores unless we're built as part of /rescue.
63  */
64 #ifndef RESCUEDIR
65 #define ALLOW_SCORE_UPDATES
66 #endif
67 
68 /*
69  * Within this code, we can hang onto one extra "high score", leaving
70  * room for our current score (whether or not it is high).
71  *
72  * We also sometimes keep tabs on the "highest" score on each level.
73  * As long as the scores are kept sorted, this is simply the first one at
74  * that level.
75  */
76 #define NUMSPOTS (MAXHISCORES + 1)
77 #define	NLEVELS (MAXLEVEL + 1)
78 
79 static time_t now;
80 static int nscores;
81 static int gotscores;
82 static struct highscore scores[NUMSPOTS];
83 
84 static int checkscores(struct highscore *, int);
85 static int cmpscores(const void *, const void *);
86 static void getscores(int *);
87 static void printem(int, int, struct highscore *, int, const char *);
88 static char *thisuser(void);
89 
90 /* contents chosen to be a highly illegal username */
91 static const char hsh_magic_val[HSH_MAGIC_SIZE] = "//:\0\0://";
92 
93 #define HSH_ENDIAN_NATIVE	0x12345678
94 #define HSH_ENDIAN_OPP		0x78563412
95 
96 /* current file format version */
97 #define HSH_VERSION		1
98 
99 /* codes for scorefile_probe return */
100 #define SCOREFILE_ERROR		(-1)
101 #define SCOREFILE_CURRENT	0	/* 40-byte */
102 #define SCOREFILE_CURRENT_OPP	1	/* 40-byte, opposite-endian */
103 #define SCOREFILE_599		2	/* 36-byte */
104 #define SCOREFILE_599_OPP	3	/* 36-byte, opposite-endian */
105 #define SCOREFILE_50		4	/* 32-byte */
106 #define SCOREFILE_50_OPP	5	/* 32-byte, opposite-endian */
107 
108 /*
109  * Check (or guess) what kind of score file contents we have.
110  */
111 static int
112 scorefile_probe(int sd)
113 {
114 	struct stat st;
115 	int t1, t2, t3, tx;
116 	ssize_t result;
117 	uint32_t numbers[3], offset56, offset60, offset64;
118 
119 	if (fstat(sd, &st) < 0) {
120 		warn("Score file %s: fstat", _PATH_SCOREFILE);
121 		return -1;
122 	}
123 
124 	t1 = st.st_size % sizeof(struct highscore_ondisk) == 0;
125 	t2 = st.st_size % sizeof(struct highscore_ondisk_599) == 0;
126 	t3 = st.st_size % sizeof(struct highscore_ondisk_50) == 0;
127 	tx = t1 + t2 + t3;
128 	if (tx == 1) {
129 		/* Size matches exact number of one kind of records */
130 		if (t1) {
131 			return SCOREFILE_CURRENT;
132 		} else if (t2) {
133 			return SCOREFILE_599;
134 		} else {
135 			return SCOREFILE_50;
136 		}
137 	} else if (tx == 0) {
138 		/* Size matches nothing, pick most likely as default */
139 		goto wildguess;
140 	}
141 
142 	/*
143 	 * File size is multiple of more than one structure size.
144 	 * (For example, 288 bytes could be 9*hso50 or 8*hso599.)
145 	 * Read the file and see if we can figure out what's going
146 	 * on. This is the layout of the first two records:
147 	 *
148 	 *   offset     hso / current   hso_599         hso_50
149 	 *              (40-byte)       (36-byte)       (32-byte)
150 	 *
151 	 *   0          name #0         name #0         name #0
152          *   4            :               :               :
153          *   8            :               :               :
154          *   12           :               :               :
155          *   16           :               :               :
156 	 *   20         score #0        score #0        score #0
157 	 *   24         level #0        level #0        level #0
158 	 *   28          (pad)          time #0         time #0
159 	 *   32         time #0                         name #1
160 	 *   36                         name #1           :
161          *   40         name #1           :               :
162          *   44           :               :               :
163          *   48           :               :               :
164 	 *   52           :               :             score #1
165 	 *   56           :             score #1        level #1
166 	 *   60         score #1        level #1        time #1
167 	 *   64         level #1        time #1         name #2
168 	 *   68          (pad)            :               :
169 	 *   72         time #1         name #2           :
170 	 *   76           :               :               :
171 	 *   80                  --- end ---
172 	 *
173 	 * There are a number of things we could check here, but the
174 	 * most effective test is based on the following restrictions:
175 	 *
176 	 *    - The level must be between 1 and 9 (inclusive)
177 	 *    - All times must be after 1985 and are before 2038,
178 	 *      so the high word must be 0 and the low word may not be
179 	 *      a small value.
180 	 *    - Integer values of 0 or 1-9 cannot be the beginning of
181 	 *      a login name string.
182 	 *    - Values of 1-9 are probably not a score.
183 	 *
184 	 * So we read the three words at offsets 56, 60, and 64, and
185 	 * poke at the values to try to figure things...
186 	 */
187 
188 	if (lseek(sd, 56, SEEK_SET) < 0) {
189 		warn("Score file %s: lseek", _PATH_SCOREFILE);
190 		return -1;
191 	}
192 	result = read(sd, &numbers, sizeof(numbers));
193 	if (result < 0) {
194 		warn("Score file %s: read", _PATH_SCOREFILE);
195 		return -1;
196 	}
197 	if ((size_t)result != sizeof(numbers)) {
198 		/*
199 		 * The smallest file whose size divides by more than
200 		 * one of the sizes is substantially larger than 64,
201 		 * so this should *never* happen.
202 		 */
203 		warnx("Score file %s: Unexpected EOF", _PATH_SCOREFILE);
204 		return -1;
205 	}
206 
207 	offset56 = numbers[0];
208 	offset60 = numbers[1];
209 	offset64 = numbers[2];
210 
211 	if (offset64 >= MINLEVEL && offset64 <= MAXLEVEL) {
212 		/* 40-byte structure */
213 		return SCOREFILE_CURRENT;
214 	} else if (offset60 >= MINLEVEL && offset60 <= MAXLEVEL) {
215 		/* 36-byte structure */
216 		return SCOREFILE_599;
217 	} else if (offset56 >= MINLEVEL && offset56 <= MAXLEVEL) {
218 		/* 32-byte structure */
219 		return SCOREFILE_50;
220 	}
221 
222 	/* None was a valid level; try opposite endian */
223 	offset64 = swap32(offset64);
224 	offset60 = swap32(offset60);
225 	offset56 = swap32(offset56);
226 
227 	if (offset64 >= MINLEVEL && offset64 <= MAXLEVEL) {
228 		/* 40-byte structure */
229 		return SCOREFILE_CURRENT_OPP;
230 	} else if (offset60 >= MINLEVEL && offset60 <= MAXLEVEL) {
231 		/* 36-byte structure */
232 		return SCOREFILE_599_OPP;
233 	} else if (offset56 >= MINLEVEL && offset56 <= MAXLEVEL) {
234 		/* 32-byte structure */
235 		return SCOREFILE_50_OPP;
236 	}
237 
238 	/* That didn't work either, dunno what's going on */
239  wildguess:
240 	warnx("Score file %s is likely corrupt", _PATH_SCOREFILE);
241 	if (sizeof(void *) == 8 && sizeof(time_t) == 8) {
242 		return SCOREFILE_CURRENT;
243 	} else if (sizeof(time_t) == 8) {
244 		return SCOREFILE_599;
245 	} else {
246 		return SCOREFILE_50;
247 	}
248 }
249 
250 /*
251  * Copy a string safely, making sure it's null-terminated.
252  */
253 static void
254 readname(char *to, size_t maxto, const char *from, size_t maxfrom)
255 {
256 	size_t amt;
257 
258 	amt = maxto < maxfrom ? maxto : maxfrom;
259 	memcpy(to, from, amt);
260 	to[maxto-1] = '\0';
261 }
262 
263 /*
264  * Copy integers, byte-swapping if desired.
265  */
266 static int32_t
267 read32(int32_t val, int doflip)
268 {
269 	if (doflip) {
270 		val = swap32(val);
271 	}
272 	return val;
273 }
274 
275 static int64_t
276 read64(int64_t val, int doflip)
277 {
278 	if (doflip) {
279 		val = swap64(val);
280 	}
281 	return val;
282 }
283 
284 /*
285  * Read up to MAXHISCORES scorefile_ondisk entries.
286  */
287 static int
288 readscores(int sd, int doflip)
289 {
290 	struct highscore_ondisk buf[MAXHISCORES];
291 	ssize_t result;
292 	int i;
293 
294 	result = read(sd, buf, sizeof(buf));
295 	if (result < 0) {
296 		warn("Score file %s: read", _PATH_SCOREFILE);
297 		return -1;
298 	}
299 	nscores = result / sizeof(buf[0]);
300 
301 	for (i=0; i<nscores; i++) {
302 		readname(scores[i].hs_name, sizeof(scores[i].hs_name),
303 			 buf[i].hso_name, sizeof(buf[i].hso_name));
304 		scores[i].hs_score = read32(buf[i].hso_score, doflip);
305 		scores[i].hs_level = read32(buf[i].hso_level, doflip);
306 		scores[i].hs_time = read64(buf[i].hso_time, doflip);
307 	}
308 	return 0;
309 }
310 
311 /*
312  * Read up to MAXHISCORES scorefile_ondisk_599 entries.
313  */
314 static int
315 readscores599(int sd, int doflip)
316 {
317 	struct highscore_ondisk_599 buf[MAXHISCORES];
318 	ssize_t result;
319 	int i;
320 
321 	result = read(sd, buf, sizeof(buf));
322 	if (result < 0) {
323 		warn("Score file %s: read", _PATH_SCOREFILE);
324 		return -1;
325 	}
326 	nscores = result / sizeof(buf[0]);
327 
328 	for (i=0; i<nscores; i++) {
329 		readname(scores[i].hs_name, sizeof(scores[i].hs_name),
330 			 buf[i].hso599_name, sizeof(buf[i].hso599_name));
331 		scores[i].hs_score = read32(buf[i].hso599_score, doflip);
332 		scores[i].hs_level = read32(buf[i].hso599_level, doflip);
333 		/*
334 		 * Don't bother pasting the time together into a
335 		 * 64-bit value; just take whichever half is nonzero.
336 		 */
337 		scores[i].hs_time =
338 			read32(buf[i].hso599_time[buf[i].hso599_time[0] == 0],
339 			       doflip);
340 	}
341 	return 0;
342 }
343 
344 /*
345  * Read up to MAXHISCORES scorefile_ondisk_50 entries.
346  */
347 static int
348 readscores50(int sd, int doflip)
349 {
350 	struct highscore_ondisk_50 buf[MAXHISCORES];
351 	ssize_t result;
352 	int i;
353 
354 	result = read(sd, buf, sizeof(buf));
355 	if (result < 0) {
356 		warn("Score file %s: read", _PATH_SCOREFILE);
357 		return -1;
358 	}
359 	nscores = result / sizeof(buf[0]);
360 
361 	for (i=0; i<nscores; i++) {
362 		readname(scores[i].hs_name, sizeof(scores[i].hs_name),
363 			 buf[i].hso50_name, sizeof(buf[i].hso50_name));
364 		scores[i].hs_score = read32(buf[i].hso50_score, doflip);
365 		scores[i].hs_level = read32(buf[i].hso50_level, doflip);
366 		scores[i].hs_time = read32(buf[i].hso50_time, doflip);
367 	}
368 	return 0;
369 }
370 
371 /*
372  * Read the score file.  Can be called from savescore (before showscores)
373  * or showscores (if savescore will not be called).  If the given pointer
374  * is not NULL, sets *fdp to an open file handle that corresponds to a
375  * read/write score file that is locked with LOCK_EX.  Otherwise, the
376  * file is locked with LOCK_SH for the read and closed before return.
377  */
378 static void
379 getscores(int *fdp)
380 {
381 	struct highscore_header header;
382 	int sd, mint, lck;
383 	mode_t mask;
384 	const char *human;
385 	int doflip;
386 	int serrno;
387 	ssize_t result;
388 
389 #ifdef ALLOW_SCORE_UPDATES
390 	if (fdp != NULL) {
391 		mint = O_RDWR | O_CREAT;
392 		human = "read/write";
393 		lck = LOCK_EX;
394 	} else
395 #endif
396 	{
397 		mint = O_RDONLY;
398 		human = "reading";
399 		lck = LOCK_SH;
400 	}
401 	setegid(egid);
402 	mask = umask(S_IWOTH);
403 	sd = open(_PATH_SCOREFILE, mint, 0666);
404 	serrno = errno;
405 	(void)umask(mask);
406 	setegid(gid);
407 	if (sd < 0) {
408 		/*
409 		 * If the file simply isn't there because nobody's
410 		 * played yet, and we aren't going to be trying to
411 		 * update it, don't warn. Even if we are going to be
412 		 * trying to write it, don't fail -- we can still show
413 		 * the player the score they got.
414 		 */
415 		errno = serrno;
416 		if (fdp != NULL || errno != ENOENT) {
417 			warn("Cannot open %s for %s", _PATH_SCOREFILE, human);
418 		}
419 		goto fail;
420 	}
421 
422 	/*
423 	 * Grab a lock.
424 	 * XXX: failure here should probably be more fatal than this.
425 	 */
426 	if (flock(sd, lck))
427 		warn("warning: score file %s cannot be locked",
428 		    _PATH_SCOREFILE);
429 
430 	/*
431 	 * The current format (since -current of 20090525) is
432 	 *
433 	 *    struct highscore_header
434 	 *    up to MAXHIGHSCORES x struct highscore_ondisk
435 	 *
436 	 * Before this, there is no header, and the contents
437 	 * might be any of three formats:
438 	 *
439 	 *    highscore_ondisk       (64-bit machines with 64-bit time_t)
440 	 *    highscore_ondisk_599   (32-bit machines with 64-bit time_t)
441 	 *    highscore_ondisk_50    (32-bit machines with 32-bit time_t)
442 	 *
443 	 * The first two appear in 5.99 between the time_t change and
444 	 * 20090525, depending on whether the compiler inserts
445 	 * structure padding before an unaligned 64-bit time_t. The
446 	 * last appears in 5.0 and earlier.
447 	 *
448 	 * Any or all of these might also appear on other OSes where
449 	 * this code has been ported.
450 	 *
451 	 * Since the old file has no header, we will have to guess
452 	 * which of these formats it has.
453 	 */
454 
455 	/*
456 	 * First, look for a header.
457 	 */
458 	result = read(sd, &header, sizeof(header));
459 	if (result < 0) {
460 		warn("Score file %s: read", _PATH_SCOREFILE);
461 		goto sdfail;
462 	}
463 	if (result != 0 && (size_t)result != sizeof(header)) {
464 		warnx("Score file %s: read: unexpected EOF", _PATH_SCOREFILE);
465 		/*
466 		 * File is hopelessly corrupt, might as well truncate it
467 		 * and start over with empty scores.
468 		 */
469 		if (lseek(sd, 0, SEEK_SET) < 0) {
470 			/* ? */
471 			warn("Score file %s: lseek", _PATH_SCOREFILE);
472 			goto sdfail;
473 		}
474 		if (ftruncate(sd, 0) == 0) {
475 			result = 0;
476 		} else {
477 			goto sdfail;
478 		}
479 	}
480 
481 	if (result == 0) {
482 		/* Empty file; that just means there are no scores. */
483 		nscores = 0;
484 	} else {
485 		/*
486 		 * Is what we read a header, or the first 16 bytes of
487 		 * a score entry? hsh_magic_val is chosen to be
488 		 * something that is extremely unlikely to appear in
489 		 * hs_name[].
490 		 */
491 		if (!memcmp(header.hsh_magic, hsh_magic_val, HSH_MAGIC_SIZE)) {
492 			/* Yes, we have a header. */
493 
494 			if (header.hsh_endiantag == HSH_ENDIAN_NATIVE) {
495 				/* native endian */
496 				doflip = 0;
497 			} else if (header.hsh_endiantag == HSH_ENDIAN_OPP) {
498 				doflip = 1;
499 			} else {
500 				warnx("Score file %s: Unknown endian tag %u",
501 					_PATH_SCOREFILE, header.hsh_endiantag);
502 				goto sdfail;
503 			}
504 
505 			if (header.hsh_version != HSH_VERSION) {
506 				warnx("Score file %s: Unknown version code %u",
507 					_PATH_SCOREFILE, header.hsh_version);
508 				goto sdfail;
509 			}
510 
511 			if (readscores(sd, doflip) < 0) {
512 				goto sdfail;
513 			}
514 		} else {
515 			/*
516 			 * Ok, it wasn't a header. Try to figure out what
517 			 * size records we have.
518 			 */
519 			result = scorefile_probe(sd);
520 			if (lseek(sd, 0, SEEK_SET) < 0) {
521 				warn("Score file %s: lseek", _PATH_SCOREFILE);
522 				goto sdfail;
523 			}
524 			switch (result) {
525 			case SCOREFILE_CURRENT:
526 				result = readscores(sd, 0 /* don't flip */);
527 				break;
528 			case SCOREFILE_CURRENT_OPP:
529 				result = readscores(sd, 1 /* do flip */);
530 				break;
531 			case SCOREFILE_599:
532 				result = readscores599(sd, 0 /* don't flip */);
533 				break;
534 			case SCOREFILE_599_OPP:
535 				result = readscores599(sd, 1 /* do flip */);
536 				break;
537 			case SCOREFILE_50:
538 				result = readscores50(sd, 0 /* don't flip */);
539 				break;
540 			case SCOREFILE_50_OPP:
541 				result = readscores50(sd, 1 /* do flip */);
542 				break;
543 			default:
544 				goto sdfail;
545 			}
546 			if (result < 0) {
547 				goto sdfail;
548 			}
549 		}
550 	}
551 
552 
553 	if (fdp)
554 		*fdp = sd;
555 	else
556 		close(sd);
557 
558 	return;
559 
560 sdfail:
561 	close(sd);
562  fail:
563 	if (fdp != NULL) {
564 		*fdp = -1;
565 	}
566 	nscores = 0;
567 }
568 
569 #ifdef ALLOW_SCORE_UPDATES
570 /*
571  * Paranoid write wrapper; unlike fwrite() it preserves errno.
572  */
573 static int
574 dowrite(int sd, const void *vbuf, size_t len)
575 {
576 	const char *buf = vbuf;
577 	ssize_t result;
578 	size_t done = 0;
579 
580 	while (done < len) {
581 		result = write(sd, buf+done, len-done);
582 		if (result < 0) {
583 			if (errno == EINTR) {
584 				continue;
585 			}
586 			return -1;
587 		}
588 		done += result;
589 	}
590 	return 0;
591 }
592 #endif /* ALLOW_SCORE_UPDATES */
593 
594 /*
595  * Write the score file out.
596  */
597 static void
598 putscores(int sd)
599 {
600 #ifdef ALLOW_SCORE_UPDATES
601 	struct highscore_header header;
602 	struct highscore_ondisk buf[MAXHISCORES] = {0};
603 	int i;
604 
605 	if (sd == -1) {
606 		return;
607 	}
608 
609 	memcpy(header.hsh_magic, hsh_magic_val, HSH_MAGIC_SIZE);
610 	header.hsh_endiantag = HSH_ENDIAN_NATIVE;
611 	header.hsh_version = HSH_VERSION;
612 
613 	for (i=0; i<nscores; i++) {
614 		memcpy(buf[i].hso_name, scores[i].hs_name,
615 			sizeof(buf[i].hso_name));
616 		buf[i].hso_score = scores[i].hs_score;
617 		buf[i].hso_level = scores[i].hs_level;
618 		buf[i].hso_pad = 0xbaadf00d;
619 		buf[i].hso_time = scores[i].hs_time;
620 	}
621 
622 	if (lseek(sd, 0, SEEK_SET) < 0) {
623 		warn("Score file %s: lseek", _PATH_SCOREFILE);
624 		goto fail;
625 	}
626 	if (dowrite(sd, &header, sizeof(header)) < 0 ||
627 	    dowrite(sd, buf, sizeof(buf[0]) * nscores) < 0) {
628 		warn("Score file %s: write", _PATH_SCOREFILE);
629 		goto fail;
630 	}
631 	return;
632  fail:
633 	warnx("high scores may be damaged");
634 #else
635 	(void)sd;
636 #endif /* ALLOW_SCORE_UPDATES */
637 }
638 
639 /*
640  * Close the score file.
641  */
642 static void
643 closescores(int sd)
644 {
645 	flock(sd, LOCK_UN);
646 	close(sd);
647 }
648 
649 /*
650  * Read and update the scores file with the current reults.
651  */
652 void
653 savescore(int level)
654 {
655 	struct highscore *sp;
656 	int i;
657 	int change;
658 	int sd;
659 	const char *me;
660 
661 	getscores(&sd);
662 	gotscores = 1;
663 	(void)time(&now);
664 
665 	/*
666 	 * Allow at most one score per person per level -- see if we
667 	 * can replace an existing score, or (easiest) do nothing.
668 	 * Otherwise add new score at end (there is always room).
669 	 */
670 	change = 0;
671 	me = thisuser();
672 	for (i = 0, sp = &scores[0]; i < nscores; i++, sp++) {
673 		if (sp->hs_level != level || strcmp(sp->hs_name, me) != 0)
674 			continue;
675 		if (score > sp->hs_score) {
676 			(void)printf("%s bettered %s %d score of %d!\n",
677 			    "\nYou", "your old level", level,
678 			    sp->hs_score * sp->hs_level);
679 			sp->hs_score = score;	/* new score */
680 			sp->hs_time = now;	/* and time */
681 			change = 1;
682 		} else if (score == sp->hs_score) {
683 			(void)printf("%s tied %s %d high score.\n",
684 			    "\nYou", "your old level", level);
685 			sp->hs_time = now;	/* renew it */
686 			change = 1;		/* gotta rewrite, sigh */
687 		} /* else new score < old score: do nothing */
688 		break;
689 	}
690 	if (i >= nscores) {
691 		strcpy(sp->hs_name, me);
692 		sp->hs_level = level;
693 		sp->hs_score = score;
694 		sp->hs_time = now;
695 		nscores++;
696 		change = 1;
697 	}
698 
699 	if (change) {
700 		/*
701 		 * Sort & clean the scores, then rewrite.
702 		 */
703 		nscores = checkscores(scores, nscores);
704 		putscores(sd);
705 	}
706 	closescores(sd);
707 }
708 
709 /*
710  * Get login name, or if that fails, get something suitable.
711  * The result is always trimmed to fit in a score.
712  */
713 static char *
714 thisuser(void)
715 {
716 	const char *p;
717 	struct passwd *pw;
718 	size_t l;
719 	static char u[sizeof(scores[0].hs_name)];
720 
721 	if (u[0])
722 		return (u);
723 	p = getlogin();
724 	if (p == NULL || *p == '\0') {
725 		pw = getpwuid(getuid());
726 		if (pw != NULL)
727 			p = pw->pw_name;
728 		else
729 			p = "  ???";
730 	}
731 	l = strlen(p);
732 	if (l >= sizeof(u))
733 		l = sizeof(u) - 1;
734 	memcpy(u, p, l);
735 	u[l] = '\0';
736 	return (u);
737 }
738 
739 /*
740  * Score comparison function for qsort.
741  *
742  * If two scores are equal, the person who had the score first is
743  * listed first in the highscore file.
744  */
745 static int
746 cmpscores(const void *x, const void *y)
747 {
748 	const struct highscore *a, *b;
749 	long l;
750 
751 	a = x;
752 	b = y;
753 	l = (long)b->hs_level * b->hs_score - (long)a->hs_level * a->hs_score;
754 	if (l < 0)
755 		return (-1);
756 	if (l > 0)
757 		return (1);
758 	if (a->hs_time < b->hs_time)
759 		return (-1);
760 	if (a->hs_time > b->hs_time)
761 		return (1);
762 	return (0);
763 }
764 
765 /*
766  * If we've added a score to the file, we need to check the file and ensure
767  * that this player has only a few entries.  The number of entries is
768  * controlled by MAXSCORES, and is to ensure that the highscore file is not
769  * monopolised by just a few people.  People who no longer have accounts are
770  * only allowed the highest score.  Scores older than EXPIRATION seconds are
771  * removed, unless they are someone's personal best.
772  * Caveat:  the highest score on each level is always kept.
773  */
774 static int
775 checkscores(struct highscore *hs, int num)
776 {
777 	struct highscore *sp;
778 	int i, j, k, numnames;
779 	int levelfound[NLEVELS];
780 	struct peruser {
781 		char *name;
782 		int times;
783 	} count[NUMSPOTS];
784 	struct peruser *pu;
785 
786 	/*
787 	 * Sort so that highest totals come first.
788 	 *
789 	 * levelfound[i] becomes set when the first high score for that
790 	 * level is encountered.  By definition this is the highest score.
791 	 */
792 	qsort((void *)hs, nscores, sizeof(*hs), cmpscores);
793 	for (i = MINLEVEL; i < NLEVELS; i++)
794 		levelfound[i] = 0;
795 	numnames = 0;
796 	for (i = 0, sp = hs; i < num;) {
797 		/*
798 		 * This is O(n^2), but do you think we care?
799 		 */
800 		for (j = 0, pu = count; j < numnames; j++, pu++)
801 			if (strcmp(sp->hs_name, pu->name) == 0)
802 				break;
803 		if (j == numnames) {
804 			/*
805 			 * Add new user, set per-user count to 1.
806 			 */
807 			pu->name = sp->hs_name;
808 			pu->times = 1;
809 			numnames++;
810 		} else {
811 			/*
812 			 * Two ways to keep this score:
813 			 * - Not too many (per user), still has acct, &
814 			 *	score not dated; or
815 			 * - High score on this level.
816 			 */
817 			if ((pu->times < MAXSCORES &&
818 			     getpwnam(sp->hs_name) != NULL &&
819 			     sp->hs_time + EXPIRATION >= now) ||
820 			    levelfound[sp->hs_level] == 0)
821 				pu->times++;
822 			else {
823 				/*
824 				 * Delete this score, do not count it,
825 				 * do not pass go, do not collect $200.
826 				 */
827 				num--;
828 				for (k = i; k < num; k++)
829 					hs[k] = hs[k + 1];
830 				continue;
831 			}
832 		}
833 		if (sp->hs_level < NLEVELS && sp->hs_level >= 0)
834 			levelfound[sp->hs_level] = 1;
835 		i++, sp++;
836 	}
837 	return (num > MAXHISCORES ? MAXHISCORES : num);
838 }
839 
840 /*
841  * Show current scores.  This must be called after savescore, if
842  * savescore is called at all, for two reasons:
843  * - Showscores munches the time field.
844  * - Even if that were not the case, a new score must be recorded
845  *   before it can be shown anyway.
846  */
847 void
848 showscores(int level)
849 {
850 	struct highscore *sp;
851 	int i, n, c;
852 	const char *me;
853 	int levelfound[NLEVELS];
854 
855 	if (!gotscores)
856 		getscores(NULL);
857 	(void)printf("\n\t\t\t    Tetris High Scores\n");
858 
859 	/*
860 	 * If level == 0, the person has not played a game but just asked for
861 	 * the high scores; we do not need to check for printing in highlight
862 	 * mode.  If SOstr is null, we can't do highlighting anyway.
863 	 */
864 	me = level && enter_standout_mode ? thisuser() : NULL;
865 
866 	/*
867 	 * Set times to 0 except for high score on each level.
868 	 */
869 	for (i = MINLEVEL; i < NLEVELS; i++)
870 		levelfound[i] = 0;
871 	for (i = 0, sp = scores; i < nscores; i++, sp++) {
872         if (sp->hs_level < NLEVELS && sp->hs_level >= 0) {
873     		if (levelfound[sp->hs_level])
874 	    		sp->hs_time = 0;
875 		    else {
876 			    sp->hs_time = 1;
877 		    	levelfound[sp->hs_level] = 1;
878 		    }
879         }
880 	}
881 
882 	/*
883 	 * Page each screenful of scores.
884 	 */
885 	for (i = 0, sp = scores; i < nscores; sp += n) {
886 		n = 40;
887 		if (i + n > nscores)
888 			n = nscores - i;
889 		printem(level, i + 1, sp, n, me);
890 		if ((i += n) < nscores) {
891 			(void)printf("\nHit RETURN to continue.");
892 			(void)fflush(stdout);
893 			while ((c = getchar()) != '\n')
894 				if (c == EOF)
895 					break;
896 			(void)printf("\n");
897 		}
898 	}
899 }
900 
901 static void
902 printem(int level, int offset, struct highscore *hs, int n, const char *me)
903 {
904 	struct highscore *sp;
905 	int nrows, row, col, item, i, highlight;
906 	char buf[100];
907 #define	TITLE "Rank  Score   Name     (points/level)"
908 
909 	/*
910 	 * This makes a nice two-column sort with headers, but it's a bit
911 	 * convoluted...
912 	 */
913 	printf("%s   %s\n", TITLE, n > 1 ? TITLE : "");
914 
915 	highlight = 0;
916 	nrows = (n + 1) / 2;
917 
918 	for (row = 0; row < nrows; row++) {
919 		for (col = 0; col < 2; col++) {
920 			item = col * nrows + row;
921 			if (item >= n) {
922 				/*
923 				 * Can only occur on trailing columns.
924 				 */
925 				(void)putchar('\n');
926 				continue;
927 			}
928 			sp = &hs[item];
929 			(void)snprintf(buf, sizeof(buf),
930 			    "%3d%c %6d  %-11s (%6d on %d)",
931 			    item + offset, sp->hs_time ? '*' : ' ',
932 			    sp->hs_score * sp->hs_level,
933 			    sp->hs_name, sp->hs_score, sp->hs_level);
934 			/*
935 			 * Highlight if appropriate.  This works because
936 			 * we only get one score per level.
937 			 */
938 			if (me != NULL &&
939 			    sp->hs_level == level &&
940 			    sp->hs_score == score &&
941 			    strcmp(sp->hs_name, me) == 0) {
942 				putpad(enter_standout_mode);
943 				highlight = 1;
944 			}
945 			(void)printf("%s", buf);
946 			if (highlight) {
947 				putpad(exit_standout_mode);
948 				highlight = 0;
949 			}
950 
951 			/* fill in spaces so column 1 lines up */
952 			if (col == 0)
953 				for (i = 40 - strlen(buf); --i >= 0;)
954 					(void)putchar(' ');
955 			else /* col == 1 */
956 				(void)putchar('\n');
957 		}
958 	}
959 }