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