bfd8f92c29c733c944170310d901b60ab744dc14
[shellsnippets/shellsnippets.git] / mksh / shuffle
1 #!/usr/bin/env mksh
2 # $MirOS: contrib/code/Snippets/shuffle,v 1.6 2011/09/07 19:54:51 tg Exp $
3 #-
4 # Copyright © 2006, 2010, 2011
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) and arc4random_uniform(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 = 1024 + 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 function arc4random_uniform {
129         # Derived from code written by Damien Miller <djm@openbsd.org>
130         # published under the ISC licence, with simplifications by
131         # Jinmei Tatuya. Written in mksh by Thorsten Glaser.
132         #-
133         # Calculate a uniformly distributed random number less than
134         # upper_bound avoiding “modulo bias”.
135         # Uniformity is achieved by generating new random numbers
136         # until the one returned is outside the range
137         # [0, 2^32 % upper_bound[. This guarantees the selected
138         # random number will be inside the range
139         # [2^32 % upper_bound, 2^32[ which maps back to
140         # [0, upper_bound[ after reduction modulo upper_bound.
141         #-
142         typeset -Ui upper_bound=$1 min
143
144         if (( upper_bound < 2 )); then
145                 arc4random_rv=0
146                 return
147         fi
148
149         # calculate (2^32 % upper_bound) avoiding 64-bit math
150         # if upper_bound > 2^31: 2^32 - upper_bound (only one
151         # “value area”); otherwise (x <= 2^31) use the fact
152         # that ((2^32 - x) % x) == (2^32 % x)
153         ((# min = upper_bound > 0x80000000 ? 1 + ~upper_bound :
154             (0xFFFFFFFF - upper_bound + 1) % upper_bound ))
155
156         # This could theoretically loop forever but each retry has
157         # p > 0.5 (worst case, usually far better) of selecting a
158         # number inside the range we need, so it should rarely need
159         # to re-roll (at all).
160         while :; do
161                 arc4random
162                 ((# arc4random_rv >= min )) && break
163         done
164
165         ((# arc4random_rv %= upper_bound ))
166 }
167
168
169 # Append shuffled list of files
170 (( ++nfiles ))
171 while (( --nfiles )); do
172         arc4random_uniform $nfiles
173         arg=${files[arc4random_rv]}
174         if [[ -e $arg ]]; then
175                 cmdline[ncmdline++]=$arg
176         else
177                 print -u2 "Warning: non-existent '$arg' skipped"
178         fi
179         unset files[arc4random_rv]
180         set -A files -- "${files[@]}"
181 done
182
183 # Append post-command arguments, if any
184 for arg in "${postfix[@]}"; do
185         cmdline[ncmdline++]=$arg
186 done
187
188 # Run the command
189 if (( verbose )); then
190         C_QUOTE=$'[]\t\n "#$&'\''()*;<=>?[\\`|]'
191         for i in "${cmdline[@]}"; do
192                 if [[ $i = *${C_QUOTE}* ]]; then
193                         print -nr " '${i//\'/\'\\\'\'}'"
194                 else
195                         print -nr " $i"
196                 fi
197         done
198         print
199 fi
200 exec "${cmdline[@]}"