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

[Carlo Hamalainen]

On 04/11/13 06:51, Ian Munsie wrote:
>
> Of course, I would do the whole thing in Python, but then I'm strange
> like that :-p

I take your strange and raise you a Haskell ;-)

https://gist.github.com/carlohamalainen/7300879

-- Extract the 2-bit pairs from a word.
pairs :: Word8 -> [Word8]
pairs x = reverse [3 .&. shiftR x (2*i) | i <- [0..3]]

-- Corrector keeps the first bit of each bit pair
-- that is not 0b00 or 0b11.
correctPair 1 = [0]
correctPair 2 = [1]
correctPair _ = []

-- Attempt to assemble a byte from 8 bits.
assembleByte :: [Word8] -> Maybe Word8
assembleByte bits = if length bits == 8
                        then Just $ foldl (.|.) 0 [shiftL x n | (x, n)
<- zip (take 8 bits) [7,6..0]]
                        else Nothing

-- Assemble as many bytes as possible from a list of bits.
assembleBytes :: [Word8] -> [Word8]
assembleBytes bits = mapMaybe assembleByte (chunksOf 8 bits)

-- Remove bias in a sequence of words.
extractor :: [Word8] -> [Word8]
extractor = assembleBytes . concatMap correctPair . concatMap pairs

main = do
    c <- BSL.getContents
    BSL.putStr $ BSL.pack $ extractor $ runGet listOfWord8 c


> I've used generators ("yield" keyword) below to avoid reading the
> entire input at any stage, so you can run this over input that never
> ends like /dev/urandom (something in your shell pipeline is blocking
> that possibility).

Since Haskell is a lazily evaluated language, you can imagine that the
code that I wrote has implicit 'yield' statements everywhere. This means
that you can compose the extractor function with other things, and apply
it to an infinite data structure (similar to /dev/urandom):

Define an infinite list of 'a' in Word8 format:

(have loaded my program already)
*Main BS> import qualified Data.ByteString.Internal as BS (c2w, w2c)
*Main BS> let infinity = repeat (BS.c2w 'a') :: [Word8] -- infinite list
of 'a'

Grab the first 5 elements from the infinite list:

*Main BS> take 5 infinity
[97,97,97,97,97]

Take the first 5 result of extractor *directly* applied to the infinite
list:

*Main BS> take 5 (extractor infinity)
[73,36,146,73,36]

Compose "chunksOf 2" (takes a list and gives you its elements as lists
of length 2, e.g. [1, 2, 3, 4] -> [[1, 2], [3, 4]]) with the extractor
function, apply that to the infinite list, and then take the first 5
results of that:

*Main BS> take 5 ((chunksOf 2 . extractor) infinity)
[[73,36],[146,73],[36,146],[73,36],[146,73]]

This is similar to Unix shell pipes which act in a lazy manner, and this
lets you join together arbitrary sequences of commands (grep, sed, awk,
etc) for fun and profit.

For those who are interested, here's a paper about gluing programs
together using functional composition and lazy evaluation:

http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf

It's taken me a while to have this sink in; hat tip to Leighton B for
telling me about it a few months ago. I've spent a long time writing
C/Python/Fortran code with explicit loops and yield-type interfaces and
it ended up feeling like the only way to do things. Not so :-)

-- 
Carlo Hamalainen
http://carlo-hamalainen.net