relicence under MirOS Licence, granted by private deal with the CTO
[shellsnippets/shellsnippets.git] / mksh / shuffle
1 #!/usr/bin/env mksh
2 # $MirOS: contrib/code/Snippets/shuffle,v 1.7+urandom 2012/10/19 18:59:39 tg Exp $
3 #-
4 # Copyright © 2006, 2010, 2011, 2012
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 usage() {
26         print -u2 "Syntax: $0 [-v] program [args ...] -- file ... [-- args ...]"
27         print -u2 "Prepend another hyphen-minus to escape multi-dash first-args"
28         exit ${1:-1}
29 }
30
31 [[ -z $1 || $1 = -[hH?] ]] && usage ${1:+0}
32
33 if [[ $1 = -v ]]; then
34         verbose=1
35         shift
36 else
37         verbose=0
38 fi
39
40 set -A cmdline
41 set -A files
42 set -A postfix
43
44 integer ncmdline=0
45 integer nfiles=0
46 integer npostfix=0
47 integer state=0
48
49 # Read in command line arguments
50 for arg in "$@"; do
51         case $state {
52         (0)     if [[ $arg = -- ]]; then
53                         let state++
54                 elif [[ $arg = --+(-) ]]; then
55                         cmdline[ncmdline++]=${arg#-}
56                 else
57                         cmdline[ncmdline++]=$arg
58                 fi
59                 ;;
60         (1)     if [[ $arg = -- ]]; then
61                         let state++
62                 else
63                         files[nfiles++]=$arg
64                 fi
65                 ;;
66         (2)     postfix[npostfix++]=$arg
67                 ;;
68         }
69 done
70
71 (( ncmdline < 1 || nfiles < 1 )) && usage
72
73
74 # arc4random(3) in Pure mksh™
75 set -A seedbuf -- $(dd if=/dev/urandom bs=257 count=1 2>&- | \
76     hexdump -ve '1/1 "0x%02X "')
77 set -A rs_S
78 typeset -i rs_S rs_i=-1 rs_j=0 n
79 while (( ++rs_i < 256 )); do
80         (( rs_S[rs_i] = rs_i ))
81 done
82 rs_i=-1
83 while (( ++rs_i < 256 )); do
84         (( n = rs_S[rs_i] ))
85         (( rs_j = (rs_j + n + seedbuf[rs_i]) & 0xFF ))
86         (( rs_S[rs_i] = rs_S[rs_j] ))
87         (( rs_S[rs_j] = n ))
88 done
89 rs_i=0
90 rs_j=0
91 typeset -i rs_out
92 function arcfour_byte {
93         typeset -i si sj
94
95         (( rs_i = (rs_i + 1) & 0xFF ))
96         (( si = rs_S[rs_i] ))
97         (( rs_j = (rs_j + si) & 0xFF ))
98         (( sj = rs_S[rs_j] ))
99         (( rs_S[rs_i] = sj ))
100         (( rs_S[rs_j] = si ))
101         (( rs_out = rs_S[(si + sj) & 0xFF] ))
102 }
103 (( n = 256 * 12 + seedbuf[256] + (RANDOM & 0xFF) ))
104 while (( n-- )); do
105         arcfour_byte
106 done
107 (( n = rs_out ))
108 while (( n-- )); do
109         arcfour_byte
110 done
111
112 typeset -Uui16 -Z11 arc4random_rv
113 function arc4random {
114         # apply uncertainty
115         arcfour_byte
116         (( rs_out & 1 )) && arcfour_byte
117         # read four octets into result dword
118         arcfour_byte
119         (( arc4random_rv = rs_out ))
120         arcfour_byte
121         (( arc4random_rv |= rs_out << 8 ))
122         arcfour_byte
123         (( arc4random_rv |= rs_out << 16 ))
124         arcfour_byte
125         (( arc4random_rv |= rs_out << 24 ))
126 }
127
128 # arc4random_uniform(3) in Pure mksh™
129 function arc4random_uniform {
130         # Derived from code written by Damien Miller <djm@openbsd.org>
131         # published under the ISC licence, with simplifications by
132         # Jinmei Tatuya. Written in mksh by Thorsten Glaser.
133         #-
134         # Calculate a uniformly distributed random number less than
135         # upper_bound avoiding “modulo bias”.
136         # Uniformity is achieved by generating new random numbers
137         # until the one returned is outside the range
138         # [0, 2^32 % upper_bound[. This guarantees the selected
139         # random number will be inside the range
140         # [2^32 % upper_bound, 2^32[ which maps back to
141         # [0, upper_bound[ after reduction modulo upper_bound.
142         #-
143         typeset -Ui upper_bound=$1 min
144
145         if (( upper_bound < 2 )); then
146                 arc4random_rv=0
147                 return
148         fi
149
150         # calculate (2^32 % upper_bound) avoiding 64-bit math
151         # if upper_bound > 2^31: 2^32 - upper_bound (only one
152         # “value area”); otherwise (x <= 2^31) use the fact
153         # that ((2^32 - x) % x) == (2^32 % x)
154         ((# min = upper_bound > 0x80000000 ? 1 + ~upper_bound :
155             (0xFFFFFFFF - upper_bound + 1) % upper_bound ))
156
157         # This could theoretically loop forever but each retry has
158         # p > 0.5 (worst case, usually far better) of selecting a
159         # number inside the range we need, so it should rarely need
160         # to re-roll (at all).
161         while :; do
162                 arc4random
163                 ((# arc4random_rv >= min )) && break
164         done
165
166         ((# arc4random_rv %= upper_bound ))
167 }
168
169
170 # Append shuffled list of files
171 (( ++nfiles ))
172 while (( --nfiles )); do
173         arc4random_uniform $nfiles
174         arg=${files[arc4random_rv]}
175         if [[ -e $arg ]]; then
176                 cmdline[ncmdline++]=$arg
177         else
178                 print -u2 "Warning: non-existent '$arg' skipped"
179         fi
180         unset files[arc4random_rv]
181         set -A files -- "${files[@]}"
182 done
183
184 # Append post-command arguments, if any
185 for arg in "${postfix[@]}"; do
186         cmdline[ncmdline++]=$arg
187 done
188
189 # Run the command
190 if (( verbose )); then
191         C_QUOTE=$'[]\t\n "#$&'\''()*;<=>?[\\`|]'
192         for i in "${cmdline[@]}"; do
193                 if [[ $i = *${C_QUOTE}* ]]; then
194                         print -nr " '${i//\'/\'\\\'\'}'"
195                 else
196                         print -nr " $i"
197                 fi
198         done
199         print
200 fi
201 exec "${cmdline[@]}"