use urandom(4), not arandom(4), to be more portable
[shellsnippets/shellsnippets.git] / mksh / shuffle
1 #!/usr/bin/env mksh
2 # $MirOS: contrib/code/Snippets/shuffle,v 1.5 2010/11/06 14:59:20 tg Exp $
3 #-
4 # Copyright © 2006, 2010
5 #       Thorsten “mirabilos” Glaser <tg@mirbsd.org>
6 #
7 # Provided that these terms and disclaimer and all copyright notices
8 # are retained or reproduced in an accompanying document, permission
9 # is granted to deal in this work without restriction, including un‐
10 # limited rights to use, publicly perform, distribute, sell, modify,
11 # merge, give away, or sublicence.
12 #
13 # This work is provided “AS IS” and WITHOUT WARRANTY of any kind, to
14 # the utmost extent permitted by applicable law, neither express nor
15 # implied; without malicious intent or gross negligence. In no event
16 # may a licensor, author or contributor be held liable for indirect,
17 # direct, other damage, loss, or other issues arising in any way out
18 # of dealing in the work, even if advised of the possibility of such
19 # damage or existence of a defect, except proven that it results out
20 # of said person’s immediate fault when using the work as intended.
21 #-
22 # Provide shuffled input to mpg123, mplayer, mppdec, and other tools
23 # that do not properly employ arc4random(3) et al.
24
25 function usage {
26         print -u2 "Syntax: $0 program [args ...] -- file ... [ -- args ... ]"
27         print -u2 "To escape '--' in first args prepend another hyphen-minus"
28         exit 1
29 }
30
31 [[ -z $1 || $1 = -@(h|H|?) ]] && usage
32
33 set -A cmdline
34 set -A files
35 set -A postfix
36
37 integer ncmdline=0
38 integer nfiles=0
39 integer npostfix=0
40 integer state=0
41
42 # Read in command line arguments
43 for arg in "$@"; do
44         case $state {
45         (0)     if [[ $arg = -- ]]; then
46                         let state++
47                 elif [[ $arg = --- ]]; then
48                         cmdline[ncmdline++]=--
49                 else
50                         cmdline[ncmdline++]=$arg
51                 fi
52                 ;;
53         (1)     if [[ $arg = -- ]]; then
54                         let state++
55                 else
56                         files[nfiles++]=$arg
57                 fi
58                 ;;
59         (2)     postfix[npostfix++]=$arg
60                 ;;
61         }
62 done
63
64 (( ncmdline < 1 || nfiles < 1 )) && usage
65
66
67 # arc4random(3) and arc4random_uniform(3) in Pure mksh™
68 set -A seedbuf -- $(dd if=/dev/urandom bs=257 count=1 2>&- | \
69     hexdump -ve '1/1 "0x%02X "')
70 set -A rs_S
71 typeset -i rs_S rs_i=-1 rs_j=0 n
72 while (( ++rs_i < 256 )); do
73         (( rs_S[rs_i] = rs_i ))
74 done
75 rs_i=-1
76 while (( ++rs_i < 256 )); do
77         (( n = rs_S[rs_i] ))
78         (( rs_j = (rs_j + n + seedbuf[rs_i]) & 0xFF ))
79         (( rs_S[rs_i] = rs_S[rs_j] ))
80         (( rs_S[rs_j] = n ))
81 done
82 rs_i=0
83 rs_j=0
84 typeset -i rs_out
85 function arcfour_byte {
86         typeset -i si sj
87
88         (( rs_i = (rs_i + 1) & 0xFF ))
89         (( si = rs_S[rs_i] ))
90         (( rs_j = (rs_j + si) & 0xFF ))
91         (( sj = rs_S[rs_j] ))
92         (( rs_S[rs_i] = sj ))
93         (( rs_S[rs_j] = si ))
94         (( rs_out = rs_S[(si + sj) & 0xFF] ))
95 }
96 (( n = 1024 + seedbuf[256] + (RANDOM & 0xFF) ))
97 while (( n-- )); do
98         arcfour_byte
99 done
100 (( n = rs_out ))
101 while (( n-- )); do
102         arcfour_byte
103 done
104
105 typeset -Uui16 -Z11 arc4random_rv
106 function arc4random {
107         # apply uncertainty
108         arcfour_byte
109         (( rs_out & 1 )) && arcfour_byte
110         # read four octets into result dword
111         arcfour_byte
112         (( arc4random_rv = rs_out ))
113         arcfour_byte
114         (( arc4random_rv |= rs_out << 8 ))
115         arcfour_byte
116         (( arc4random_rv |= rs_out << 16 ))
117         arcfour_byte
118         (( arc4random_rv |= rs_out << 24 ))
119 }
120
121 function arc4random_uniform {
122         # Derived from code written by Damien Miller <djm@openbsd.org>
123         # published under the ISC licence, with simplifications by
124         # Jinmei Tatuya. Written in mksh by Thorsten Glaser.
125         #-
126         # Calculate a uniformly distributed random number less than
127         # upper_bound avoiding “modulo bias”.
128         # Uniformity is achieved by generating new random numbers
129         # until the one returned is outside the range
130         # [0, 2^32 % upper_bound[. This guarantees the selected
131         # random number will be inside the range
132         # [2^32 % upper_bound, 2^32[ which maps back to
133         # [0, upper_bound[ after reduction modulo upper_bound.
134         #-
135         typeset -Ui upper_bound=$1 min
136
137         if (( upper_bound < 2 )); then
138                 arc4random_rv=0
139                 return
140         fi
141
142         # calculate (2^32 % upper_bound) avoiding 64-bit math
143         # if upper_bound > 2^31: 2^32 - upper_bound (only one
144         # “value area”); otherwise (x <= 2^31) use the fact
145         # that ((2^32 - x) % x) == (2^32 % x)
146         ((# min = upper_bound > 0x80000000 ? 1 + ~upper_bound :
147             (0xFFFFFFFF - upper_bound + 1) % upper_bound ))
148
149         # This could theoretically loop forever but each retry has
150         # p > 0.5 (worst case, usually far better) of selecting a
151         # number inside the range we need, so it should rarely need
152         # to re-roll (at all).
153         while :; do
154                 arc4random
155                 ((# arc4random_rv >= min )) && break
156         done
157
158         ((# arc4random_rv %= upper_bound ))
159 }
160
161
162 # Append shuffled list of files
163 (( ++nfiles ))
164 while (( --nfiles )); do
165         arc4random_uniform $nfiles
166         arg=${files[arc4random_rv]}
167         if [[ -e $arg ]]; then
168                 cmdline[ncmdline++]=$arg
169         else
170                 print -u2 "Warning: non-existent '$arg' skipped"
171         fi
172         unset files[arc4random_rv]
173         set -A files -- "${files[@]}"
174 done
175
176 # Append post-command arguments, if any
177 for arg in "${postfix[@]}"; do
178         cmdline[${#cmdline[*]}]=$arg
179 done
180
181 # Run the command
182 exec "${cmdline[@]}"