1/*	$NetBSD: shuffle.c,v 1.20 2009/04/13 07:31:36 lukem Exp $	*/
2
3/*
4 * Copyright (c) 1998
5 * 	Perry E. Metzger.  All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 *    must display the following acknowledgment:
17 *	This product includes software developed for the NetBSD Project
18 *	by Perry E. Metzger.
19 * 4. The name of the author may not be used to endorse or promote products
20 *    derived from this software without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34#include <sys/cdefs.h>
35#ifndef lint
36__RCSID("$NetBSD: shuffle.c,v 1.20 2009/04/13 07:31:36 lukem Exp $");
37#endif /* not lint */
38
39#include <sys/time.h>
40
41#include <err.h>
42#include <errno.h>
43#include <limits.h>
44#include <stdio.h>
45#include <stdlib.h>
46#include <string.h>
47#include <unistd.h>
48#include <util.h>
49
50static size_t *get_shuffle(size_t);
51__dead static void usage(void);
52static void get_lines(const char *, char ***, size_t *);
53static size_t get_number(const char *, int);
54
55/*
56 * get_shuffle --
57 *	Construct a random shuffle array of t elements
58 */
59static size_t *
60get_shuffle(size_t t)
61{
62	size_t *shuffle;
63	size_t i, j, k, temp;
64
65	shuffle = emalloc(t * sizeof(size_t));
66
67	for (i = 0; i < t; i++)
68		shuffle[i] = i;
69
70	/*
71	 * This algorithm taken from Knuth, Seminumerical Algorithms,
72	 * 2nd Ed., page 139.
73	 */
74
75	for (j = t - 1; j > 0; j--) {
76		k = arc4random() % (j + 1);
77		temp = shuffle[j];
78		shuffle[j] = shuffle[k];
79		shuffle[k] = temp;
80	}
81
82	return shuffle;
83}
84
85/*
86 * usage --
87 *	Print a usage message and exit
88 */
89static void
90usage(void)
91{
92
93	(void) fprintf(stderr,
94    "usage: %s [-0] [-f <filename>] [-n <number>] [-p <number>] [<arg> ...]\n",
95		getprogname());
96	exit(1);
97}
98
99
100/*
101 * get_lines --
102 *	Return an array of lines read from input
103 */
104static void
105get_lines(const char *fname, char ***linesp, size_t *nlinesp)
106{
107	FILE *fp;
108	char *line;
109	size_t size, nlines = 0, maxlines = 128;
110	char **lines = emalloc(sizeof(char *) * maxlines);
111
112	if (strcmp(fname, "-") == 0)
113		fp = stdin;
114	else
115		if ((fp = fopen(fname, "r")) == NULL)
116			err(1, "Cannot open `%s'", fname);
117
118	while ((line = fgetln(fp, &size)) != NULL) {
119		if (size > 0 && line[size - 1] == '\n')
120			size--;
121		lines[nlines] = emalloc(size + 1);
122		(void)memcpy(lines[nlines], line, size);
123		lines[nlines++][size] = '\0';
124		if (nlines >= maxlines) {
125			maxlines *= 2;
126			lines = erealloc(lines, (sizeof(char *) * maxlines));
127		}
128	}
129	lines[nlines] = NULL;
130
131	*linesp = lines;
132	*nlinesp = nlines;
133	if (strcmp(fname, "-") != 0)
134		(void)fclose(fp);
135}
136
137/*
138 * get_number --
139 *	Return a number or exit on error
140 */
141static size_t
142get_number(const char *str, int ch)
143{
144	char *estr;
145	long number;
146
147	errno = 0;
148	number = strtol(str, &estr, 0);
149	if ((number == LONG_MIN || number == LONG_MAX) && errno == ERANGE)
150		err(1, "bad -%c argument `%s'", ch, str);
151	if (*estr)
152		errx(1, "non numeric -%c argument `%s'", ch, str);
153	if (number < 0)
154		errx(1, "negative -%c argument `%s'", ch, str);
155	return (size_t) number;
156}
157
158int
159main(int argc, char *argv[])
160{
161	int nflag = 0, pflag = 0, ch;
162	char *fname = NULL;
163	size_t *shuffle = NULL;
164	char **lines = NULL;
165	size_t nlines = 0, pick = 0, i;
166	char sep = '\n';
167
168	while ((ch = getopt(argc, argv, "0f:n:p:")) != -1) {
169		switch(ch) {
170		case '0':
171			sep = '\0';
172			break;
173		case 'f':
174			fname = optarg;
175			break;
176		case 'n':
177			nlines = get_number(optarg, ch);
178			nflag = 1;
179			break;
180		case 'p':
181			pick = get_number(optarg, ch);
182			pflag = 1;
183			break;
184		case '?':
185		default:
186			usage();
187		}
188	}
189	argc -= optind;
190	argv += optind;
191
192	if ((fname && nflag) || (nflag && (argc > 0)))
193		usage();
194
195	if (fname != NULL)
196		get_lines(fname, &lines, &nlines);
197	else if (nflag == 0) {
198		lines = argv;
199		nlines = argc;
200	}
201
202	if (nlines > 0)
203		shuffle = get_shuffle(nlines);
204
205	if (pflag) {
206		if (pick > nlines)
207			errx(1, "-p specified more components than exist.");
208		nlines = pick;
209	}
210
211	for (i = 0; i < nlines; i++) {
212		if (nflag)
213			printf("%ld", (long)shuffle[i]);
214		else
215			printf("%s", lines[shuffle[i]]);
216		putc(sep, stdout);
217	}
218
219	return 0;
220}
221