randomize_fd.c revision 256281
1219820Sjeff/* 2219820Sjeff * Copyright (C) 2003 Sean Chittenden <seanc@FreeBSD.org> 3219820Sjeff * All rights reserved. 4219820Sjeff * 5219820Sjeff * Redistribution and use in source and binary forms, with or without 6219820Sjeff * modification, are permitted provided that the following conditions 7219820Sjeff * are met: 8219820Sjeff * 1. Redistributions of source code must retain the above copyright 9219820Sjeff * notice, this list of conditions and the following disclaimer. 10219820Sjeff * 2. Redistributions in binary form must reproduce the above copyright 11219820Sjeff * notice, this list of conditions and the following disclaimer in the 12219820Sjeff * documentation and/or other materials provided with the distribution. 13219820Sjeff * 14219820Sjeff * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND 15219820Sjeff * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16219820Sjeff * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17219820Sjeff * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE 18219820Sjeff * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19219820Sjeff * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20219820Sjeff * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21219820Sjeff * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22219820Sjeff * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23219820Sjeff * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24219820Sjeff * SUCH DAMAGE. 25219820Sjeff */ 26219820Sjeff 27219820Sjeff#include <sys/cdefs.h> 28219820Sjeff__FBSDID("$FreeBSD: stable/10/games/random/randomize_fd.c 241847 2012-10-22 03:06:59Z eadler $"); 29219820Sjeff 30219820Sjeff#include <sys/types.h> 31219820Sjeff#include <sys/param.h> 32219820Sjeff 33219820Sjeff#include <ctype.h> 34219820Sjeff#include <err.h> 35219820Sjeff#include <errno.h> 36219820Sjeff#include <stdlib.h> 37219820Sjeff#include <stdio.h> 38219820Sjeff#include <string.h> 39219820Sjeff#include <unistd.h> 40219820Sjeff 41219820Sjeff#include "randomize_fd.h" 42219820Sjeff 43219820Sjeffstatic struct rand_node *rand_root; 44219820Sjeffstatic struct rand_node *rand_tail; 45219820Sjeff 46219820Sjeffstatic struct rand_node * 47219820Sjeffrand_node_allocate(void) 48219820Sjeff{ 49219820Sjeff struct rand_node *n; 50219820Sjeff 51219820Sjeff n = (struct rand_node *)malloc(sizeof(struct rand_node)); 52219820Sjeff if (n == NULL) 53219820Sjeff err(1, "malloc"); 54219820Sjeff 55219820Sjeff n->len = 0; 56219820Sjeff n->cp = NULL; 57219820Sjeff n->next = NULL; 58219820Sjeff return(n); 59219820Sjeff} 60219820Sjeff 61219820Sjeffstatic void 62219820Sjeffrand_node_free(struct rand_node *n) 63219820Sjeff{ 64219820Sjeff if (n != NULL) { 65219820Sjeff if (n->cp != NULL) 66219820Sjeff free(n->cp); 67219820Sjeff 68219820Sjeff free(n); 69219820Sjeff } 70219820Sjeff} 71219820Sjeff 72219820Sjeffstatic void 73219820Sjeffrand_node_free_rec(struct rand_node *n) 74219820Sjeff{ 75219820Sjeff if (n != NULL) { 76219820Sjeff if (n->next != NULL) 77219820Sjeff rand_node_free_rec(n->next); 78219820Sjeff 79219820Sjeff rand_node_free(n); 80219820Sjeff } 81219820Sjeff} 82219820Sjeff 83219820Sjeffstatic void 84219820Sjeffrand_node_append(struct rand_node *n) 85219820Sjeff{ 86219820Sjeff if (rand_root == NULL) 87219820Sjeff rand_root = rand_tail = n; 88219820Sjeff else { 89219820Sjeff rand_tail->next = n; 90219820Sjeff rand_tail = n; 91219820Sjeff } 92219820Sjeff} 93219820Sjeff 94219820Sjeffint 95219820Sjeffrandomize_fd(int fd, int type, int unique, double denom) 96219820Sjeff{ 97219820Sjeff u_char *buf; 98219820Sjeff u_int slen; 99219820Sjeff u_long i, j, numnode, selected; 100219820Sjeff struct rand_node *n, *prev; 101219820Sjeff int bufleft, eof, fndstr, ret; 102219820Sjeff size_t bufc, buflen; 103219820Sjeff ssize_t len; 104219820Sjeff 105219820Sjeff rand_root = rand_tail = NULL; 106219820Sjeff bufc = i = 0; 107219820Sjeff bufleft = eof = fndstr = numnode = 0; 108219820Sjeff 109219820Sjeff if (type == RANDOM_TYPE_UNSET) 110219820Sjeff type = RANDOM_TYPE_LINES; 111219820Sjeff 112219820Sjeff buflen = sizeof(u_char) * MAXBSIZE; 113219820Sjeff buf = (u_char *)malloc(buflen); 114219820Sjeff if (buf == NULL) 115219820Sjeff err(1, "malloc"); 116219820Sjeff 117219820Sjeff while (!eof) { 118219820Sjeff /* Check to see if we have bits in the buffer */ 119219820Sjeff if (bufleft == 0) { 120219820Sjeff len = read(fd, buf, buflen); 121219820Sjeff if (len == -1) 122219820Sjeff err(1, "read"); 123219820Sjeff else if (len == 0) { 124219820Sjeff eof++; 125219820Sjeff break; 126219820Sjeff } else if ((size_t)len < buflen) 127219820Sjeff buflen = (size_t)len; 128219820Sjeff 129219820Sjeff bufleft = (int)len; 130219820Sjeff } 131219820Sjeff 132219820Sjeff /* Look for a newline */ 133219820Sjeff for (i = bufc; i <= buflen && bufleft >= 0; i++, bufleft--) { 134219820Sjeff if (i == buflen) { 135219820Sjeff if (fndstr) { 136219820Sjeff if (!eof) { 137219820Sjeff memmove(buf, &buf[bufc], i - bufc); 138219820Sjeff i -= bufc; 139219820Sjeff bufc = 0; 140219820Sjeff len = read(fd, &buf[i], buflen - i); 141219820Sjeff if (len == -1) 142219820Sjeff err(1, "read"); 143219820Sjeff else if (len == 0) { 144219820Sjeff eof++; 145219820Sjeff break; 146219820Sjeff } else if (len < (ssize_t)(buflen - i)) 147219820Sjeff buflen = i + (size_t)len; 148219820Sjeff 149219820Sjeff bufleft = (int)len; 150219820Sjeff fndstr = 0; 151219820Sjeff } 152219820Sjeff } else { 153219820Sjeff buflen *= 2; 154219820Sjeff buf = (u_char *)realloc(buf, buflen); 155219820Sjeff if (buf == NULL) 156219820Sjeff err(1, "realloc"); 157219820Sjeff 158219820Sjeff if (!eof) { 159219820Sjeff len = read(fd, &buf[i], buflen - i); 160219820Sjeff if (len == -1) 161219820Sjeff err(1, "read"); 162219820Sjeff else if (len == 0) { 163219820Sjeff eof++; 164219820Sjeff break; 165219820Sjeff } else if (len < (ssize_t)(buflen - i)) 166219820Sjeff buflen = i + (size_t)len; 167219820Sjeff 168219820Sjeff bufleft = (int)len; 169219820Sjeff } 170219820Sjeff 171219820Sjeff } 172219820Sjeff } 173219820Sjeff 174219820Sjeff if ((type == RANDOM_TYPE_LINES && buf[i] == '\n') || 175219820Sjeff (type == RANDOM_TYPE_WORDS && isspace(buf[i])) || 176219820Sjeff (eof && i == buflen - 1)) { 177219820Sjeff make_token: 178219820Sjeff if (numnode == RANDOM_MAX_PLUS1) { 179219820Sjeff errno = EFBIG; 180219820Sjeff err(1, "too many delimiters"); 181219820Sjeff } 182219820Sjeff numnode++; 183219820Sjeff n = rand_node_allocate(); 184219820Sjeff if (-1 != (int)i) { 185219820Sjeff slen = i - (u_long)bufc; 186219820Sjeff n->len = slen + 2; 187219820Sjeff n->cp = (u_char *)malloc(slen + 2); 188219820Sjeff if (n->cp == NULL) 189 err(1, "malloc"); 190 191 memmove(n->cp, &buf[bufc], slen); 192 n->cp[slen] = buf[i]; 193 n->cp[slen + 1] = '\0'; 194 bufc = i + 1; 195 } 196 rand_node_append(n); 197 fndstr = 1; 198 } 199 } 200 } 201 202 (void)close(fd); 203 204 /* Necessary evil to compensate for files that don't end with a newline */ 205 if (bufc != i) { 206 i--; 207 goto make_token; 208 } 209 210 free(buf); 211 212 for (i = numnode; i > 0; i--) { 213 selected = random() % numnode; 214 215 for (j = 0, prev = n = rand_root; n != NULL; j++, prev = n, n = n->next) { 216 if (j == selected) { 217 if (n->cp == NULL) 218 break; 219 220 if ((int)(denom * random() / 221 RANDOM_MAX_PLUS1) == 0) { 222 ret = printf("%.*s", 223 (int)n->len - 1, n->cp); 224 if (ret < 0) 225 err(1, "printf"); 226 } 227 if (unique) { 228 if (n == rand_root) 229 rand_root = n->next; 230 if (n == rand_tail) 231 rand_tail = prev; 232 233 prev->next = n->next; 234 rand_node_free(n); 235 numnode--; 236 } 237 break; 238 } 239 } 240 } 241 242 fflush(stdout); 243 244 if (!unique) 245 rand_node_free_rec(rand_root); 246 247 return(0); 248} 249