scores.c revision 1.21 
1/*	$NetBSD: scores.c,v 1.21 2013/10/19 17:23:08 christos 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	ssize_t result;
387
388#ifdef ALLOW_SCORE_UPDATES
389	if (fdp != NULL) {
390		mint = O_RDWR | O_CREAT;
391		human = "read/write";
392		lck = LOCK_EX;
393	} else
394#endif
395	{
396		mint = O_RDONLY;
397		human = "reading";
398		lck = LOCK_SH;
399	}
400	setegid(egid);
401	mask = umask(S_IWOTH);
402	sd = open(_PATH_SCOREFILE, mint, 0666);
403	(void)umask(mask);
404	setegid(gid);
405	if (sd < 0) {
406		/*
407		 * If the file simply isn't there because nobody's
408		 * played yet, and we aren't going to be trying to
409		 * update it, don't warn. Even if we are going to be
410		 * trying to write it, don't fail -- we can still show
411		 * the player the score they got.
412		 */
413		if (fdp != NULL || errno != ENOENT) {
414			warn("Cannot open %s for %s", _PATH_SCOREFILE, human);
415		}
416		goto fail;
417	}
418
419	/*
420	 * Grab a lock.
421	 * XXX: failure here should probably be more fatal than this.
422	 */
423	if (flock(sd, lck))
424		warn("warning: score file %s cannot be locked",
425		    _PATH_SCOREFILE);
426
427	/*
428	 * The current format (since -current of 20090525) is
429	 *
430	 *    struct highscore_header
431	 *    up to MAXHIGHSCORES x struct highscore_ondisk
432	 *
433	 * Before this, there is no header, and the contents
434	 * might be any of three formats:
435	 *
436	 *    highscore_ondisk       (64-bit machines with 64-bit time_t)
437	 *    highscore_ondisk_599   (32-bit machines with 64-bit time_t)
438	 *    highscore_ondisk_50    (32-bit machines with 32-bit time_t)
439	 *
440	 * The first two appear in 5.99 between the time_t change and
441	 * 20090525, depending on whether the compiler inserts
442	 * structure padding before an unaligned 64-bit time_t. The
443	 * last appears in 5.0 and earlier.
444	 *
445	 * Any or all of these might also appear on other OSes where
446	 * this code has been ported.
447	 *
448	 * Since the old file has no header, we will have to guess
449	 * which of these formats it has.
450	 */
451
452	/*
453	 * First, look for a header.
454	 */
455	result = read(sd, &header, sizeof(header));
456	if (result < 0) {
457		warn("Score file %s: read", _PATH_SCOREFILE);
458		goto sdfail;
459	}
460	if (result != 0 && (size_t)result != sizeof(header)) {
461		warnx("Score file %s: read: unexpected EOF", _PATH_SCOREFILE);
462		/*
463		 * File is hopelessly corrupt, might as well truncate it
464		 * and start over with empty scores.
465		 */
466		if (lseek(sd, 0, SEEK_SET) < 0) {
467			/* ? */
468			warn("Score file %s: lseek", _PATH_SCOREFILE);
469			goto sdfail;
470		}
471		if (ftruncate(sd, 0) == 0) {
472			result = 0;
473		} else {
474			goto sdfail;
475		}
476	}
477
478	if (result == 0) {
479		/* Empty file; that just means there are no scores. */
480		nscores = 0;
481	} else {
482		/*
483		 * Is what we read a header, or the first 16 bytes of
484		 * a score entry? hsh_magic_val is chosen to be
485		 * something that is extremely unlikely to appear in
486		 * hs_name[].
487		 */
488		if (!memcmp(header.hsh_magic, hsh_magic_val, HSH_MAGIC_SIZE)) {
489			/* Yes, we have a header. */
490
491			if (header.hsh_endiantag == HSH_ENDIAN_NATIVE) {
492				/* native endian */
493				doflip = 0;
494			} else if (header.hsh_endiantag == HSH_ENDIAN_OPP) {
495				doflip = 1;
496			} else {
497				warnx("Score file %s: Unknown endian tag %u",
498					_PATH_SCOREFILE, header.hsh_endiantag);
499				goto sdfail;
500			}
501
502			if (header.hsh_version != HSH_VERSION) {
503				warnx("Score file %s: Unknown version code %u",
504					_PATH_SCOREFILE, header.hsh_version);
505				goto sdfail;
506			}
507
508			if (readscores(sd, doflip) < 0) {
509				goto sdfail;
510			}
511		} else {
512			/*
513			 * Ok, it wasn't a header. Try to figure out what
514			 * size records we have.
515			 */
516			result = scorefile_probe(sd);
517			if (lseek(sd, 0, SEEK_SET) < 0) {
518				warn("Score file %s: lseek", _PATH_SCOREFILE);
519				goto sdfail;
520			}
521			switch (result) {
522			case SCOREFILE_CURRENT:
523				result = readscores(sd, 0 /* don't flip */);
524				break;
525			case SCOREFILE_CURRENT_OPP:
526				result = readscores(sd, 1 /* do flip */);
527				break;
528			case SCOREFILE_599:
529				result = readscores599(sd, 0 /* don't flip */);
530				break;
531			case SCOREFILE_599_OPP:
532				result = readscores599(sd, 1 /* do flip */);
533				break;
534			case SCOREFILE_50:
535				result = readscores50(sd, 0 /* don't flip */);
536				break;
537			case SCOREFILE_50_OPP:
538				result = readscores50(sd, 1 /* do flip */);
539				break;
540			default:
541				goto sdfail;
542			}
543			if (result < 0) {
544				goto sdfail;
545			}
546		}
547	}
548
549
550	if (fdp)
551		*fdp = sd;
552	else
553		close(sd);
554
555	return;
556
557sdfail:
558	close(sd);
559 fail:
560	if (fdp != NULL) {
561		*fdp = -1;
562	}
563	nscores = 0;
564}
565
566#ifdef ALLOW_SCORE_UPDATES
567/*
568 * Paranoid write wrapper; unlike fwrite() it preserves errno.
569 */
570static int
571dowrite(int sd, const void *vbuf, size_t len)
572{
573	const char *buf = vbuf;
574	ssize_t result;
575	size_t done = 0;
576
577	while (done < len) {
578		result = write(sd, buf+done, len-done);
579		if (result < 0) {
580			if (errno == EINTR) {
581				continue;
582			}
583			return -1;
584		}
585		done += result;
586	}
587	return 0;
588}
589#endif /* ALLOW_SCORE_UPDATES */
590
591/*
592 * Write the score file out.
593 */
594static void
595putscores(int sd)
596{
597#ifdef ALLOW_SCORE_UPDATES
598	struct highscore_header header;
599	struct highscore_ondisk buf[MAXHISCORES];
600	int i;
601
602	if (sd == -1) {
603		return;
604	}
605
606	memcpy(header.hsh_magic, hsh_magic_val, HSH_MAGIC_SIZE);
607	header.hsh_endiantag = HSH_ENDIAN_NATIVE;
608	header.hsh_version = HSH_VERSION;
609
610	for (i=0; i<nscores; i++) {
611		strncpy(buf[i].hso_name, scores[i].hs_name,
612			sizeof(buf[i].hso_name));
613		buf[i].hso_score = scores[i].hs_score;
614		buf[i].hso_level = scores[i].hs_level;
615		buf[i].hso_pad = 0xbaadf00d;
616		buf[i].hso_time = scores[i].hs_time;
617	}
618
619	if (lseek(sd, 0, SEEK_SET) < 0) {
620		warn("Score file %s: lseek", _PATH_SCOREFILE);
621		goto fail;
622	}
623	if (dowrite(sd, &header, sizeof(header)) < 0 ||
624	    dowrite(sd, buf, sizeof(buf[0]) * nscores) < 0) {
625		warn("Score file %s: write", _PATH_SCOREFILE);
626		goto fail;
627	}
628	return;
629 fail:
630	warnx("high scores may be damaged");
631#else
632	(void)sd;
633#endif /* ALLOW_SCORE_UPDATES */
634}
635
636/*
637 * Close the score file.
638 */
639static void
640closescores(int sd)
641{
642	flock(sd, LOCK_UN);
643	close(sd);
644}
645
646/*
647 * Read and update the scores file with the current reults.
648 */
649void
650savescore(int level)
651{
652	struct highscore *sp;
653	int i;
654	int change;
655	int sd;
656	const char *me;
657
658	getscores(&sd);
659	gotscores = 1;
660	(void)time(&now);
661
662	/*
663	 * Allow at most one score per person per level -- see if we
664	 * can replace an existing score, or (easiest) do nothing.
665	 * Otherwise add new score at end (there is always room).
666	 */
667	change = 0;
668	me = thisuser();
669	for (i = 0, sp = &scores[0]; i < nscores; i++, sp++) {
670		if (sp->hs_level != level || strcmp(sp->hs_name, me) != 0)
671			continue;
672		if (score > sp->hs_score) {
673			(void)printf("%s bettered %s %d score of %d!\n",
674			    "\nYou", "your old level", level,
675			    sp->hs_score * sp->hs_level);
676			sp->hs_score = score;	/* new score */
677			sp->hs_time = now;	/* and time */
678			change = 1;
679		} else if (score == sp->hs_score) {
680			(void)printf("%s tied %s %d high score.\n",
681			    "\nYou", "your old level", level);
682			sp->hs_time = now;	/* renew it */
683			change = 1;		/* gotta rewrite, sigh */
684		} /* else new score < old score: do nothing */
685		break;
686	}
687	if (i >= nscores) {
688		strcpy(sp->hs_name, me);
689		sp->hs_level = level;
690		sp->hs_score = score;
691		sp->hs_time = now;
692		nscores++;
693		change = 1;
694	}
695
696	if (change) {
697		/*
698		 * Sort & clean the scores, then rewrite.
699		 */
700		nscores = checkscores(scores, nscores);
701		putscores(sd);
702	}
703	closescores(sd);
704}
705
706/*
707 * Get login name, or if that fails, get something suitable.
708 * The result is always trimmed to fit in a score.
709 */
710static char *
711thisuser(void)
712{
713	const char *p;
714	struct passwd *pw;
715	size_t l;
716	static char u[sizeof(scores[0].hs_name)];
717
718	if (u[0])
719		return (u);
720	p = getlogin();
721	if (p == NULL || *p == '\0') {
722		pw = getpwuid(getuid());
723		if (pw != NULL)
724			p = pw->pw_name;
725		else
726			p = "  ???";
727	}
728	l = strlen(p);
729	if (l >= sizeof(u))
730		l = sizeof(u) - 1;
731	memcpy(u, p, l);
732	u[l] = '\0';
733	return (u);
734}
735
736/*
737 * Score comparison function for qsort.
738 *
739 * If two scores are equal, the person who had the score first is
740 * listed first in the highscore file.
741 */
742static int
743cmpscores(const void *x, const void *y)
744{
745	const struct highscore *a, *b;
746	long l;
747
748	a = x;
749	b = y;
750	l = (long)b->hs_level * b->hs_score - (long)a->hs_level * a->hs_score;
751	if (l < 0)
752		return (-1);
753	if (l > 0)
754		return (1);
755	if (a->hs_time < b->hs_time)
756		return (-1);
757	if (a->hs_time > b->hs_time)
758		return (1);
759	return (0);
760}
761
762/*
763 * If we've added a score to the file, we need to check the file and ensure
764 * that this player has only a few entries.  The number of entries is
765 * controlled by MAXSCORES, and is to ensure that the highscore file is not
766 * monopolised by just a few people.  People who no longer have accounts are
767 * only allowed the highest score.  Scores older than EXPIRATION seconds are
768 * removed, unless they are someone's personal best.
769 * Caveat:  the highest score on each level is always kept.
770 */
771static int
772checkscores(struct highscore *hs, int num)
773{
774	struct highscore *sp;
775	int i, j, k, numnames;
776	int levelfound[NLEVELS];
777	struct peruser {
778		char *name;
779		int times;
780	} count[NUMSPOTS];
781	struct peruser *pu;
782
783	/*
784	 * Sort so that highest totals come first.
785	 *
786	 * levelfound[i] becomes set when the first high score for that
787	 * level is encountered.  By definition this is the highest score.
788	 */
789	qsort((void *)hs, nscores, sizeof(*hs), cmpscores);
790	for (i = MINLEVEL; i < NLEVELS; i++)
791		levelfound[i] = 0;
792	numnames = 0;
793	for (i = 0, sp = hs; i < num;) {
794		/*
795		 * This is O(n^2), but do you think we care?
796		 */
797		for (j = 0, pu = count; j < numnames; j++, pu++)
798			if (strcmp(sp->hs_name, pu->name) == 0)
799				break;
800		if (j == numnames) {
801			/*
802			 * Add new user, set per-user count to 1.
803			 */
804			pu->name = sp->hs_name;
805			pu->times = 1;
806			numnames++;
807		} else {
808			/*
809			 * Two ways to keep this score:
810			 * - Not too many (per user), still has acct, &
811			 *	score not dated; or
812			 * - High score on this level.
813			 */
814			if ((pu->times < MAXSCORES &&
815			     getpwnam(sp->hs_name) != NULL &&
816			     sp->hs_time + EXPIRATION >= now) ||
817			    levelfound[sp->hs_level] == 0)
818				pu->times++;
819			else {
820				/*
821				 * Delete this score, do not count it,
822				 * do not pass go, do not collect $200.
823				 */
824				num--;
825				for (k = i; k < num; k++)
826					hs[k] = hs[k + 1];
827				continue;
828			}
829		}
830        if (sp->hs_level < NLEVELS && sp->hs_level >= 0)
831    		levelfound[sp->hs_level] = 1;
832		i++, sp++;
833	}
834	return (num > MAXHISCORES ? MAXHISCORES : num);
835}
836
837/*
838 * Show current scores.  This must be called after savescore, if
839 * savescore is called at all, for two reasons:
840 * - Showscores munches the time field.
841 * - Even if that were not the case, a new score must be recorded
842 *   before it can be shown anyway.
843 */
844void
845showscores(int level)
846{
847	struct highscore *sp;
848	int i, n, c;
849	const char *me;
850	int levelfound[NLEVELS];
851
852	if (!gotscores)
853		getscores(NULL);
854	(void)printf("\n\t\t\t    Tetris High Scores\n");
855
856	/*
857	 * If level == 0, the person has not played a game but just asked for
858	 * the high scores; we do not need to check for printing in highlight
859	 * mode.  If SOstr is null, we can't do highlighting anyway.
860	 */
861	me = level && enter_standout_mode ? thisuser() : NULL;
862
863	/*
864	 * Set times to 0 except for high score on each level.
865	 */
866	for (i = MINLEVEL; i < NLEVELS; i++)
867		levelfound[i] = 0;
868	for (i = 0, sp = scores; i < nscores; i++, sp++) {
869        if (sp->hs_level < NLEVELS && sp->hs_level >= 0) {
870    		if (levelfound[sp->hs_level])
871	    		sp->hs_time = 0;
872		    else {
873			    sp->hs_time = 1;
874		    	levelfound[sp->hs_level] = 1;
875		    }
876        }
877	}
878
879	/*
880	 * Page each screenful of scores.
881	 */
882	for (i = 0, sp = scores; i < nscores; sp += n) {
883		n = 40;
884		if (i + n > nscores)
885			n = nscores - i;
886		printem(level, i + 1, sp, n, me);
887		if ((i += n) < nscores) {
888			(void)printf("\nHit RETURN to continue.");
889			(void)fflush(stdout);
890			while ((c = getchar()) != '\n')
891				if (c == EOF)
892					break;
893			(void)printf("\n");
894		}
895	}
896}
897
898static void
899printem(int level, int offset, struct highscore *hs, int n, const char *me)
900{
901	struct highscore *sp;
902	int nrows, row, col, item, i, highlight;
903	char buf[100];
904#define	TITLE "Rank  Score   Name     (points/level)"
905
906	/*
907	 * This makes a nice two-column sort with headers, but it's a bit
908	 * convoluted...
909	 */
910	printf("%s   %s\n", TITLE, n > 1 ? TITLE : "");
911
912	highlight = 0;
913	nrows = (n + 1) / 2;
914
915	for (row = 0; row < nrows; row++) {
916		for (col = 0; col < 2; col++) {
917			item = col * nrows + row;
918			if (item >= n) {
919				/*
920				 * Can only occur on trailing columns.
921				 */
922				(void)putchar('\n');
923				continue;
924			}
925			sp = &hs[item];
926			(void)snprintf(buf, sizeof(buf),
927			    "%3d%c %6d  %-11s (%6d on %d)",
928			    item + offset, sp->hs_time ? '*' : ' ',
929			    sp->hs_score * sp->hs_level,
930			    sp->hs_name, sp->hs_score, sp->hs_level);
931			/*
932			 * Highlight if appropriate.  This works because
933			 * we only get one score per level.
934			 */
935			if (me != NULL &&
936			    sp->hs_level == level &&
937			    sp->hs_score == score &&
938			    strcmp(sp->hs_name, me) == 0) {
939				putpad(enter_standout_mode);
940				highlight = 1;
941			}
942			(void)printf("%s", buf);
943			if (highlight) {
944				putpad(exit_standout_mode);
945				highlight = 0;
946			}
947
948			/* fill in spaces so column 1 lines up */
949			if (col == 0)
950				for (i = 40 - strlen(buf); --i >= 0;)
951					(void)putchar(' ');
952			else /* col == 1 */
953				(void)putchar('\n');
954		}
955	}
956}
957