more example scripts from Teckids e.V.
[shellsnippets/shellsnippets.git] / mksh / unsort
1 #!/bin/mksh
2 #-
3 # Copyright © 2006, 2010, 2011, 2012, 2015
4 #       Thorsten “mirabilos” Glaser <tg@mirbsd.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 # Unsort a file ("$@" or stdin as filter, or with -o).
22
23 export LC_ALL=C
24 unset LANGUAGE
25
26 usage() {
27         print -r -- "Syntax: $0 [-o outfile] [infile ...]"
28         cleanup ${1:-1}
29 }
30
31 function cleanup {
32         exit ${1:-1}
33 }
34
35 flag_o=0
36
37 while getopts "ho:" ch; do
38         case $ch {
39         (h)
40                 usage 0
41                 ;;
42         (o)
43                 flag_o=1
44                 outf=$OPTARG
45                 ;;
46         (+o)
47                 flag_o=0
48                 ;;
49         (*)
50                 usage
51                 ;;
52         }
53 done
54 shift $((OPTIND - 1))
55
56 # open output file, if any
57 if (( flag_o )); then
58         if ! tmpf=$(mktemp "$outf.XXXXXXXXXX"); then
59                 print -ru2 -- "E: cannot create temporary file"
60                 cleanup
61         fi
62         function cleanup {
63                 rm -f "$tmpf"
64                 exit ${1:-1}
65         }
66         trap 'cleanup' HUP INT QUIT PIPE TERM
67         exec >"$tmpf"
68 fi
69
70 # arc4random(3) in Pure mksh™ {{{
71 set +U
72 rndev=/dev/urandom
73 [[ -c /dev/arandom ]] && rndev=/dev/arandom
74 if ! read -arN257 seedbuf <"$rndev"; then
75         print -ru2 -- "E: cannot read random seed from $rndev"
76         cleanup
77 fi
78 set -A rs_S
79 typeset -i rs_S rs_i=-1 rs_j=0 n=-1
80 while (( ++n < 256 )); do
81         ((# rs_S[n] = n ))
82 done
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=0
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=0
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 # arc4random(3) in Pure mksh™ }}}
169
170 # read input
171 set -A lines
172 nlines=0
173 if [[ -n $1 ]]; then
174         cat "$@" |&
175         coproc=-p
176 else
177         coproc=
178 fi
179 while IFS= read $coproc -r line; do
180         if (( nlines == 2147483647 )); then
181                 print -ru2 "E: input too big"
182                 exit 1
183         fi
184         lines[nlines++]=$line
185 done
186
187 # write output
188 (( ++nlines ))
189 while (( --nlines )); do
190         arc4random_uniform $nlines
191         print -r -- "${lines[arc4random_rv]}"
192         unset lines[arc4random_rv]
193         set -A lines -- "${lines[@]}"
194 done
195
196 # close output file, if any
197 if (( flag_o )); then
198         exec >&2
199         if ! rename "$tmpf" "$outf"; then
200                 print -ru2 -- "E: cannot move temporary file to output file"
201                 cleanup
202         fi
203         function cleanup {
204                 exit ${1:-1}
205         }
206 fi
207
208 # done
209 exit 0