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[@]}"