Comment by mahmud | Hacker News Reader

Comment by mahmud | Hacker News Reader

Here is a fun challenge for language snobs: implement bit-streams for your favorite language. Here is a simple signature:

  bitvec read_nbits (unsigned int count, bitstream input);

  bool write_nbits (unsigned int count,bitvec bits,
                   bitstream output);

Then add a multirecord I/O. That is, read a record of bitvecs, each N bits wide, where the length is not given but encoded in the bitstream in this manner: read a bitvec record of N bits, if the high-bit is set (take it in whatever endian you like), read another record and repeat, if the high bit is not set, return whatever you read thus far.

Then add the ability to return the bitvec records as single integers (bignums even) both signed and unsigned, taking them in this manner. If the bitvecs are unsigned, each record contributes its 7 least significant bits, and the high bit is dropped. Taking the bit on either end of the first record as the most signficant, iterate over the rest and shift and OR according to your endian needs to construct an integer from the sum of all the bits.

When I first did this exercise, I was very close to gouging my own eye-balls out, but after I did it, I started to think of bits as something very natural, and not to be feared.

  let nthbit (bitContainer:'T) nth : bool = (bitContainer &&& ((1 :> 'T) <<<nth))

  let bitstream (bitContainerSeq:seq<'T>) : seq<bool> =
   let sz = sizeof<'T>
   bitContainerSeq 
   |> Seq.map (fun b -> [0..sz] 
                        |> nthbit b 
                        |> Seq.ofArray )
   |> Seq.concat

I think that should do it unfortunatley I'm away from an F# compiler

This looks magical :-)

Are you sure you're decoding bits from an octet stream (normal 8-bit bytes) and not using logical booleans? I ask this because I don't see any bit-manipulation operators, except maybe for "1 :> 'T" which looks like the SML module type casting, but I could be wrong.

Yes very sure. nthbit will extract the nth bit from an integer type. The bitwise logic is the &&& and <<< in F# you use triples for bitwise. But there is a bug in there, i forgot to times sz by 8 http://msdn.microsoft.com/en-us/library/dd469495.aspx

bitstream turns a sequence of integer types into a sequence of bits.

So if you wanted to turn a stream into bits you'd do something like the following.

  new System.IO.FileStream('foo.txt')
  |> Seq.unfold (fun s -> (s , match s.read with
                               | -1 -> None
                               | x -> Some(x)))
  |> bitstream

I just realized that the bitstream function is unnecessary and you could instead write

  let bits (bitContainer:'T) : seq<bool> = 
     [0..(sizeof<'T>*8)]
     |> Seq.ofArray
     |> Seq.map (fun nth -> (bitContainer &&& ((1 :> 'T) <<<nth))

And change the above code to:

  new System.IO.FileStream('foo.txt')
  |> Seq.unfold (fun s -> (s , match s.read with
                               | -1 -> None
                               | x -> Some(x)))
  |> Seq.map bits
  |> Seq.concat

Just for fun here's the reverse to turn a sequence of booleans into a sequence of integer types (byte,int,long,etc). Note that the length of sequence s must be a multiple of sizeof<'T> times 8

  let bitsToBitContainer (s:seq<bool>) : seq<'T> =
    let sz = sizeof<'T>*8
    s
    |> Seq.scan (fun (i,n) x -> (i++,(n<<<1)|||(x&&&1)) (0,0)
    |> Seq.filter (fun (i,n) -> i = sz)
    |> Seq.map (fun (i,n) -> n)

I am liking this F# thing. Thanks! :-)

You wouldn't happen to still have your code? This sounds like an interesting exercise. Maybe you could blog about your implementation and we can compare notes.

The source is in my old thinkpad, but would love to redo it in my new favorite language, AliceML :-)

http://www.ps.uni-saarland.de/alice/

Reply on news.ycombinator.com