blob: 9f61f2f7de3d10ac54b98a0dd4d698b094b407f8
1 | /* vi: set sw=4 ts=4: */ |
2 | /* |
3 | * shuf: Write a random permutation of the input lines to standard output. |
4 | * |
5 | * Copyright (C) 2014 by Bartosz Golaszewski <bartekgola@gmail.com> |
6 | * |
7 | * Licensed under GPLv2 or later, see file LICENSE in this source tree. |
8 | */ |
9 | |
10 | //config:config SHUF |
11 | //config: bool "shuf" |
12 | //config: default y |
13 | //config: help |
14 | //config: Generate random permutations |
15 | |
16 | //kbuild:lib-$(CONFIG_SHUF) += shuf.o |
17 | //applet:IF_SHUF(APPLET_NOEXEC(shuf, shuf, BB_DIR_USR_BIN, BB_SUID_DROP, shuf)) |
18 | |
19 | //usage:#define shuf_trivial_usage |
20 | //usage: "[-e|-i L-H] [-n NUM] [-o FILE] [-z] [FILE|ARG...]" |
21 | //usage:#define shuf_full_usage "\n\n" |
22 | //usage: "Randomly permute lines\n" |
23 | //usage: "\n -e Treat ARGs as lines" |
24 | //usage: "\n -i L-H Treat numbers L-H as lines" |
25 | //usage: "\n -n NUM Output at most NUM lines" |
26 | //usage: "\n -o FILE Write to FILE, not standard output" |
27 | //usage: "\n -z End lines with zero byte, not newline" |
28 | |
29 | #include "libbb.h" |
30 | |
31 | /* This is a NOEXEC applet. Be very careful! */ |
32 | |
33 | #define OPT_e (1 << 0) |
34 | #define OPT_i (1 << 1) |
35 | #define OPT_n (1 << 2) |
36 | #define OPT_o (1 << 3) |
37 | #define OPT_z (1 << 4) |
38 | #define OPT_STR "ei:n:o:z" |
39 | |
40 | /* |
41 | * Use the Fisher-Yates shuffle algorithm on an array of lines. |
42 | */ |
43 | static void shuffle_lines(char **lines, unsigned numlines) |
44 | { |
45 | unsigned i; |
46 | unsigned r; |
47 | char *tmp; |
48 | |
49 | srand(monotonic_us()); |
50 | |
51 | for (i = numlines-1; i > 0; i--) { |
52 | r = rand(); |
53 | /* RAND_MAX can be as small as 32767 */ |
54 | if (i > RAND_MAX) |
55 | r ^= rand() << 15; |
56 | r %= i; |
57 | tmp = lines[i]; |
58 | lines[i] = lines[r]; |
59 | lines[r] = tmp; |
60 | } |
61 | } |
62 | |
63 | int shuf_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; |
64 | int shuf_main(int argc, char **argv) |
65 | { |
66 | unsigned opts; |
67 | char *opt_i_str, *opt_n_str, *opt_o_str; |
68 | unsigned i; |
69 | char **lines; |
70 | unsigned numlines; |
71 | char eol; |
72 | |
73 | opt_complementary = "e--i:i--e"; /* mutually exclusive */ |
74 | opts = getopt32(argv, OPT_STR, &opt_i_str, &opt_n_str, &opt_o_str); |
75 | |
76 | argc -= optind; |
77 | argv += optind; |
78 | |
79 | /* Prepare lines for shuffling - either: */ |
80 | if (opts & OPT_e) { |
81 | /* make lines from command-line arguments */ |
82 | numlines = argc; |
83 | lines = argv; |
84 | } else |
85 | if (opts & OPT_i) { |
86 | /* create a range of numbers */ |
87 | char *dash; |
88 | unsigned lo, hi; |
89 | |
90 | dash = strchr(opt_i_str, '-'); |
91 | if (!dash) { |
92 | bb_error_msg_and_die("bad range '%s'", opt_i_str); |
93 | } |
94 | *dash = '\0'; |
95 | lo = xatou(opt_i_str); |
96 | hi = xatou(dash + 1); |
97 | *dash = '-'; |
98 | if (hi < lo) { |
99 | bb_error_msg_and_die("bad range '%s'", opt_i_str); |
100 | } |
101 | |
102 | numlines = (hi+1) - lo; |
103 | lines = xmalloc(numlines * sizeof(lines[0])); |
104 | for (i = 0; i < numlines; i++) { |
105 | lines[i] = (char*)(uintptr_t)lo; |
106 | lo++; |
107 | } |
108 | } else { |
109 | /* default - read lines from stdin or the input file */ |
110 | FILE *fp; |
111 | |
112 | if (argc > 1) |
113 | bb_show_usage(); |
114 | |
115 | fp = xfopen_stdin(argv[0] ? argv[0] : "-"); |
116 | lines = NULL; |
117 | numlines = 0; |
118 | for (;;) { |
119 | char *line = xmalloc_fgetline(fp); |
120 | if (!line) |
121 | break; |
122 | lines = xrealloc_vector(lines, 6, numlines); |
123 | lines[numlines++] = line; |
124 | } |
125 | fclose_if_not_stdin(fp); |
126 | } |
127 | |
128 | if (numlines != 0) |
129 | shuffle_lines(lines, numlines); |
130 | |
131 | if (opts & OPT_o) |
132 | xmove_fd(xopen(opt_o_str, O_WRONLY|O_CREAT|O_TRUNC), STDOUT_FILENO); |
133 | |
134 | if (opts & OPT_n) { |
135 | unsigned maxlines; |
136 | maxlines = xatou(opt_n_str); |
137 | if (numlines > maxlines) |
138 | numlines = maxlines; |
139 | } |
140 | |
141 | eol = '\n'; |
142 | if (opts & OPT_z) |
143 | eol = '\0'; |
144 | |
145 | for (i = 0; i < numlines; i++) { |
146 | if (opts & OPT_i) |
147 | printf("%u%c", (unsigned)(uintptr_t)lines[i], eol); |
148 | else |
149 | printf("%s%c", lines[i], eol); |
150 | } |
151 | |
152 | fflush_stdout_and_exit(EXIT_SUCCESS); |
153 | } |
154 |