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
79static time_t now;
80static int nscores;
81static int gotscores;
82static struct highscore scores[NUMSPOTS];
83
84static int checkscores(struct highscore *, int);
85static int cmpscores(const void *, const void *);
86static void getscores(int *);
87static void printem(int, int, struct highscore *, int, const char *);
88static char *thisuser(void);
89
90/* contents chosen to be a highly illegal username */
91static 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 */
111static int
112scorefile_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 = bswap32(offset64);
224	offset60 = bswap32(offset60);
225	offset56 = bswap32(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 */
253static void
254readname(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 */
266static int32_t
267read32(int32_t val, int doflip)
268{
269	if (doflip) {
270		val = bswap32(val);
271	}
272	return val;
273}
274
275static int64_t
276read64(int64_t val, int doflip)
277{
278	if (doflip) {
279		val = bswap64(val);
280	}
281	return val;
282}
283
284/*
285 * Read up to MAXHISCORES scorefile_ondisk entries.
286 */
287static int
288readscores(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 */
314static int
315readscores599(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 */
347static int
348readscores50(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 */
378static void
379getscores(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
560sdfail:
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 */
573static int
574dowrite(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 */
597static void
598putscores(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 */
642static void
643closescores(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 */
652void
653savescore(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 */
713static char *
714thisuser(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 */
745static int
746cmpscores(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 */
774static int
775checkscores(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 */
847void
848showscores(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
901static void
902printem(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}
960