simplification for the easiest case
[shellsnippets/shellsnippets.git] / mksh / teckids / shuffle
1 # -*- mode: sh -*-
2 #-
3 # Copyright © 2017
4 #       mirabilos <thorsten.glaser@teckids.org>
5 #
6 # Provided that these terms and disclaimer and all copyright notices
7 # are retained or reproduced in an accompanying document, permission
8 # is granted to deal in this work without restriction, including un‐
9 # limited rights to use, publicly perform, distribute, sell, modify,
10 # merge, give away, or sublicence.
11 #
12 # This work is provided “AS IS” and WITHOUT WARRANTY of any kind, to
13 # the utmost extent permitted by applicable law, neither express nor
14 # implied; without malicious intent or gross negligence. In no event
15 # may a licensor, author or contributor be held liable for indirect,
16 # direct, other damage, loss, or other issues arising in any way out
17 # of dealing in the work, even if advised of the possibility of such
18 # damage or existence of a defect, except proven that it results out
19 # of said person’s immediate fault when using the work as intended.
20
21 # arc4random(3) in Pure mksh™
22 set -A seedbuf -- $(dd if=/dev/urandom bs=257 count=1 2>&- | \
23     hexdump -ve '1/1 "0x%02X "')
24 set -A rs_S
25 typeset -i rs_S rs_i=-1 rs_j=0 n
26 while (( ++rs_i < 256 )); do
27         (( rs_S[rs_i] = rs_i ))
28 done
29 rs_i=-1
30 while (( ++rs_i < 256 )); do
31         (( n = rs_S[rs_i] ))
32         (( rs_j = (rs_j + n + seedbuf[rs_i]) & 0xFF ))
33         (( rs_S[rs_i] = rs_S[rs_j] ))
34         (( rs_S[rs_j] = n ))
35 done
36 rs_i=0
37 rs_j=0
38 typeset -i rs_out
39 function arcfour_byte {
40         typeset -i si sj
41
42         (( rs_i = (rs_i + 1) & 0xFF ))
43         (( si = rs_S[rs_i] ))
44         (( rs_j = (rs_j + si) & 0xFF ))
45         (( sj = rs_S[rs_j] ))
46         (( rs_S[rs_i] = sj ))
47         (( rs_S[rs_j] = si ))
48         (( rs_out = rs_S[(si + sj) & 0xFF] ))
49 }
50 (( n = 256 * 12 + seedbuf[256] + (RANDOM & 0xFF) ))
51 while (( n-- )); do
52         arcfour_byte
53 done
54 (( n = rs_out ))
55 while (( n-- )); do
56         arcfour_byte
57 done
58
59 typeset -Uui16 -Z11 arc4random_rv
60 function arc4random {
61         # apply uncertainty
62         arcfour_byte
63         (( rs_out & 1 )) && arcfour_byte
64         # read four octets into result dword
65         arcfour_byte
66         (( arc4random_rv = rs_out ))
67         arcfour_byte
68         (( arc4random_rv |= rs_out << 8 ))
69         arcfour_byte
70         (( arc4random_rv |= rs_out << 16 ))
71         arcfour_byte
72         (( arc4random_rv |= rs_out << 24 ))
73 }
74
75 # arc4random_uniform(3) in Pure mksh™
76 function arc4random_uniform {
77         # Derived from code written by Damien Miller <djm@openbsd.org>
78         # published under the ISC licence, with simplifications by
79         # Jinmei Tatuya. Written in mksh by Thorsten Glaser.
80         #-
81         # Calculate a uniformly distributed random number less than
82         # upper_bound avoiding “modulo bias”.
83         # Uniformity is achieved by generating new random numbers
84         # until the one returned is outside the range
85         # [0, 2^32 % upper_bound[. This guarantees the selected
86         # random number will be inside the range
87         # [2^32 % upper_bound, 2^32[ which maps back to
88         # [0, upper_bound[ after reduction modulo upper_bound.
89         #-
90         typeset -Ui upper_bound=$1 min
91
92         if (( upper_bound < 2 )); then
93                 arc4random_rv=0
94                 return
95         fi
96
97         # calculate (2^32 % upper_bound) avoiding 64-bit math
98         # if upper_bound > 2^31: 2^32 - upper_bound (only one
99         # “value area”); otherwise (x <= 2^31) use the fact
100         # that ((2^32 - x) % x) == (2^32 % x)
101         ((# min = upper_bound > 0x80000000 ? 1 + ~upper_bound :
102             (0xFFFFFFFF - upper_bound + 1) % upper_bound ))
103
104         # This could theoretically loop forever but each retry has
105         # p > 0.5 (worst case, usually far better) of selecting a
106         # number inside the range we need, so it should rarely need
107         # to re-roll (at all).
108         while :; do
109                 arc4random
110                 ((# arc4random_rv >= min )) && break
111         done
112
113         ((# arc4random_rv %= upper_bound ))
114 }
115
116
117 set -A names
118 nnames=0
119 while IFS= read -r; do
120         names[nnames++]=$REPLY
121 done
122 while (( ${#names[@]} )); do
123         arc4random_uniform ${#names[@]}
124         user_dn=${names[arc4random_rv]}
125         unset names[arc4random_rv]
126         set -A names -- "${names[@]}"
127
128         print -r -- "$user_dn"
129 done