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