add file-line randomiser (with overhauled arc4random in Pure mksh™)
authorThorsten Glaser <t.glaser@tarent.de>
Thu, 11 Jun 2015 12:12:46 +0000 (14:12 +0200)
committerThorsten Glaser <t.glaser@tarent.de>
Thu, 11 Jun 2015 12:12:46 +0000 (14:12 +0200)
mksh/unsort [new file with mode: 0644]

diff --git a/mksh/unsort b/mksh/unsort
new file mode 100644 (file)
index 0000000..e7dff27
--- /dev/null
@@ -0,0 +1,209 @@
+#!/bin/mksh
+#-
+# Copyright © 2006, 2010, 2011, 2012, 2015
+#      Thorsten “mirabilos” Glaser <tg@mirbsd.org>
+#
+# Provided that these terms and disclaimer and all copyright notices
+# are retained or reproduced in an accompanying document, permission
+# is granted to deal in this work without restriction, including un‐
+# limited rights to use, publicly perform, distribute, sell, modify,
+# merge, give away, or sublicence.
+#
+# This work is provided “AS IS” and WITHOUT WARRANTY of any kind, to
+# the utmost extent permitted by applicable law, neither express nor
+# implied; without malicious intent or gross negligence. In no event
+# may a licensor, author or contributor be held liable for indirect,
+# direct, other damage, loss, or other issues arising in any way out
+# of dealing in the work, even if advised of the possibility of such
+# damage or existence of a defect, except proven that it results out
+# of said person’s immediate fault when using the work as intended.
+#-
+# Unsort a file ("$@" or stdin as filter, or with -o).
+
+export LC_ALL=C
+unset LANGUAGE
+
+usage() {
+       print -r -- "Syntax: $0 [-o outfile] [infile ...]"
+       cleanup ${1:-1}
+}
+
+function cleanup {
+       exit ${1:-1}
+}
+
+flag_o=0
+
+while getopts "ho:" ch; do
+       case $ch {
+       (h)
+               usage 0
+               ;;
+       (o)
+               flag_o=1
+               outf=$OPTARG
+               ;;
+       (+o)
+               flag_o=0
+               ;;
+       (*)
+               usage
+               ;;
+       }
+done
+shift $((OPTIND - 1))
+
+# open output file, if any
+if (( flag_o )); then
+       if ! tmpf=$(mktemp "$outf.XXXXXXXXXX"); then
+               print -ru2 -- "E: cannot create temporary file"
+               cleanup
+       fi
+       function cleanup {
+               rm -f "$tmpf"
+               exit ${1:-1}
+       }
+       trap 'cleanup' HUP INT QUIT PIPE TERM
+       exec >"$tmpf"
+fi
+
+# arc4random(3) in Pure mksh™ {{{
+set +U
+rndev=/dev/urandom
+[[ -c /dev/arandom ]] && rndev=/dev/arandom
+if ! read -arN257 seedbuf <"$rndev"; then
+       print -ru2 -- "E: cannot read random seed from $rndev"
+       cleanup
+fi
+set -A rs_S
+typeset -i rs_S rs_i=-1 rs_j=0 n=-1
+while (( ++n < 256 )); do
+       ((# rs_S[n] = n ))
+done
+while (( ++rs_i < 256 )); do
+       ((# n = rs_S[rs_i] ))
+       ((# rs_j = (rs_j + n + seedbuf[rs_i]) & 0xFF ))
+       ((# rs_S[rs_i] = rs_S[rs_j] ))
+       ((# rs_S[rs_j] = n ))
+done
+rs_i=0
+rs_j=0
+typeset -i rs_out=0
+function arcfour_byte {
+       typeset -i si sj
+
+       ((# rs_i = (rs_i + 1) & 0xFF ))
+       ((# si = rs_S[rs_i] ))
+       ((# rs_j = (rs_j + si) & 0xFF ))
+       ((# sj = rs_S[rs_j] ))
+       ((# rs_S[rs_i] = sj ))
+       ((# rs_S[rs_j] = si ))
+       ((# rs_out = rs_S[(si + sj) & 0xFF] ))
+}
+((# n = 256 * 12 + seedbuf[256] + (RANDOM & 0xFF) ))
+while ((# n-- )); do
+       arcfour_byte
+done
+((# n = rs_out ))
+while ((# n-- )); do
+       arcfour_byte
+done
+
+typeset -Uui16 -Z11 arc4random_rv=0
+function arc4random {
+       # apply uncertainty
+       arcfour_byte
+       ((# rs_out & 1 )) && arcfour_byte
+       # read four octets into result dword
+       arcfour_byte
+       ((# arc4random_rv = rs_out ))
+       arcfour_byte
+       ((# arc4random_rv |= rs_out << 8 ))
+       arcfour_byte
+       ((# arc4random_rv |= rs_out << 16 ))
+       arcfour_byte
+       ((# arc4random_rv |= rs_out << 24 ))
+}
+
+# arc4random_uniform(3) in Pure mksh™
+function arc4random_uniform {
+       # Derived from code written by Damien Miller <djm@openbsd.org>
+       # published under the ISC licence, with simplifications by
+       # Jinmei Tatuya. Written in mksh by Thorsten Glaser.
+       #-
+       # Calculate a uniformly distributed random number less than
+       # upper_bound avoiding “modulo bias”.
+       # Uniformity is achieved by generating new random numbers
+       # until the one returned is outside the range
+       # [0, 2^32 % upper_bound[. This guarantees the selected
+       # random number will be inside the range
+       # [2^32 % upper_bound, 2^32[ which maps back to
+       # [0, upper_bound[ after reduction modulo upper_bound.
+       #-
+       typeset -Ui upper_bound=$1 min
+
+       if ((# upper_bound < 2 )); then
+               arc4random_rv=0
+               return
+       fi
+
+       # calculate (2^32 % upper_bound) avoiding 64-bit math
+       # if upper_bound > 2^31: 2^32 - upper_bound (only one
+       # “value area”); otherwise (x <= 2^31) use the fact
+       # that ((2^32 - x) % x) == (2^32 % x)
+       ((# min = upper_bound > 0x80000000 ? 1 + ~upper_bound :
+           (0xFFFFFFFF - upper_bound + 1) % upper_bound ))
+
+       # This could theoretically loop forever but each retry has
+       # p > 0.5 (worst case, usually far better) of selecting a
+       # number inside the range we need, so it should rarely need
+       # to re-roll (at all).
+       while :; do
+               arc4random
+               ((# arc4random_rv >= min )) && break
+       done
+
+       ((# arc4random_rv %= upper_bound ))
+}
+# arc4random(3) in Pure mksh™ }}}
+
+# read input
+set -A lines
+nlines=0
+if [[ -n $1 ]]; then
+       cat "$@" |&
+       coproc=-p
+else
+       coproc=
+fi
+while IFS= read $coproc -r line; do
+       if (( nlines == 2147483647 )); then
+               print -ru2 "E: input too big"
+               exit 1
+       fi
+       lines[nlines++]=$line
+done
+
+# write output
+(( ++nlines ))
+while (( --nlines )); do
+       arc4random_uniform $nlines
+       print -r -- "${lines[arc4random_rv]}"
+       unset lines[arc4random_rv]
+       set -A lines -- "${lines[@]}"
+done
+
+# close output file, if any
+if (( flag_o )); then
+       exec >&2
+       if ! rename "$tmpf" "$outf"; then
+               print -ru2 -- "E: cannot move temporary file to output file"
+               cleanup
+       fi
+       function cleanup {
+               exit ${1:-1}
+       }
+fi
+
+# done
+exit 0