[clug] command to reverse 'xxd -b'??

[steve jenkin]

I'm trying to understand the von Neumann 'extractor', also called
'corrector'. It removes 'bias' (more 0's or 1's in a bit-stream) from a
Random Number Generator output.

It looks at pair of bits, discarding '00' and '11' (bits same).
For '01', '10', it emits the first bit and discards the second.

<https://en.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor>

So I wrote a shell script... Nothing like reusing existing wheels.

Only I hit a speed bump, reversing the output of 'xxd -b'.
[the man page says "No, we dont do this."]

'xxd -r -p' will happily reverse hex values into binary.
[v. neat, learned that today]

'xxd -b' dumps file in binary, strings of ascii '0' and '1'.
But I couldn't find a command that would nicely rewrite binary back into
hex...

I ended up using 'awk' :(

Questions:

 - anyone got a way to just use commands to do this?
   [I could've used 'sed' to convert '0000' .. '1111' to hex.]
   [was going to be long & tedious]
   Any other ideas?

 - PERL can probably do this trivially... example welcome!

 - Python may or may not be good for bit-banging like this.
   example welcome, if it's simple :)

Thanks In Advance
steve


============= sh/bash Script, commented ===========

Pass input file(s) as command line parameters,
script writes binary output to STDOUT

call as:
 script input-file >new-bin-file


xxd -b -g0 "$@"|\	# convert input to binary, with line nrs
			# & ascii dump. '-p' doesn't work with '-b'

 sed -e 's/^[0-9a-f][0-9a-f]*: //' -e 's/  .*//' -e 's/../&|/g'|\
 tr '|' '\n'|grep -v -e '^$' |\	# remove line nrs & ascii dump
			# break binary into two bits per line

 grep -v -e '^00' -e '^11'|sed -e 's/.$//'|\
			# von Neumann corrector

(tr -d '\n';echo) |\	# join output back into one long line

 sed -e 's/......../&|/g'|tr '|' '\n' |\
			# reformat into 8-bits per line

 awk '{s = $1; n=0;
   for (i=1; i <= length(s); i++)
     { n=n*2; n += index("01", substr(s, i, 1))-1;}
    printf("%02X\n", n);
   }' |\		# not fancy. rewrite as Hex

 (tr -d '\n';echo)|\	# back to one long line
 sed -e 's/..../&|/g'|tr '|' '\n'|\	# 4hex (2bytes) per line for xxd

 xxd -r -p			# use xxd to reverse hexdump

================================================


============= sh/bash Script, usable [watch for line-breaks] ===========

xxd -b -g0 "$@"|\
 sed -e 's/^[0-9a-f][0-9a-f]*: //' -e 's/  .*//' -e 's/../&|/g'|tr '|'
'\n'|grep -v -e '^$' |\
 grep -v -e '^00' -e '^11'|sed -e 's/.$//'|(tr -d '\n';echo) |\
 sed -e 's/......../&|/g'|tr '|' '\n' |\
 awk '{s = $1; n=0;
   for (i=1; i <= length(s); i++) { n=n*2; n += index("01", substr(s, i,
1))-1;}
    printf("%02X\n", n);}' |\
 (tr -d '\n';echo)|sed -e 's/..../&|/g'|tr '|' '\n'|\
 xxd -r -p

================================================


-- 
Steve Jenkin, Info Tech, Systems and Design Specialist.
0412 786 915 (+61 412 786 915)
PO Box 48, Kippax ACT 2615, AUSTRALIA

sjenkin at canb.auug.org.au http://members.tip.net.au/~sjenkin