Kero van Gelder
9/18/2006 9:25:00 PM
>> Now I'll have to figure out something very simple: when is the new
>> deadline
>> of this quiz :P
>
><laughs> I will release the summary Thursday morning, which means
> you need to have it in before I start writing sometime Wednesday if
> you want me to look it over.
OK, here we go :)
Somehow, I dug into the tests and missed test_rle and test_unrle above the
TEST_VECTORS. A pity, because they *do* get your mind set onto those
trailing false's. Plus, especially test_unrle is trivial to implement.
Run like `ruby test_00111_gizmo.rb -n test_unrle` :)
Then on with test_basic_en/decoding. Encoder#<< shows directly why the extra
false is required for a finite bitstream: the code doesn't do a bloody thing
when appending 'true's. In order to get finite bitstrings (36 out of 37
which end with 'true') across the wire, you have to append a 'false'. For
consistency *always* append a 'false' when you close the string. and that is
precisely what Encoder#finish does.
This way, Encoder#<< works for infinite bitstreams, too.
And then you need some padding (with ones! so the decoder won't be able to
decode them!) for those "practical" bytes.
The decoder has a statemachine to see whether its reading bits for the
multiplier (:div) or the remainder (:rem, which is a binary encoded number
as we all know for these powers-of-two codes; this is not the case for the
general Golomb codes, you'd need an extra offset and sometimes one bit
less). I had to add a state for the exponent (:exp) in the beginning and
move some code around, instead of just reading the exponent in initialize,
because at that time the (string)io can still be empty.
Note how Decoder#read returns as much as can be processed from the
bitstream, up until what is received (dealing with byte boundaries;
additional (fewer than eight) bits could be in the bitstream, but not yet
available for the decoder; see how "practical" bytes are?)
The Gizmo::encode and Gizmo::decode look amazingly like the test_encoder and
test_decoder tests. Sorry :)
By this time I was still messing with the trailing false, which I had to
append to some tests. Apart from that, test_decode_partial and
test_round_trip_probabilistic came almost for free. When I finally saw the
light, I could remove the trailing 'false' in Gizmo::decode, put the tests
back to what they were supposed to be, and immediately after that, Q's
00111.rb ran as it was supposed to.
Thanks for the Quiz, taught me Golomb codes and Ruby's StringIO.
Oh, and I realize now that test_decoder tests the infinite streams.
And then, the code!
-----
# Author: Kero van Gelder
# Copyright: Kero van Gelder, can be distributed under LGPL
require 'stringio'
module SecretAgent00111CommunicationGizmo
class UndefinedRLE < RuntimeError
end
def self.unrle(ary)
ary.inject([]) {|un, val|
un.concat([true] * val)
un << false
}
end
def self.rle(ary)
result = []
while not ary.empty?
nr = 0
while not ary.empty? and ary[0]
nr += 1
ary.shift
end
raise UndefinedRLE if ary.empty?
ary.shift
result << nr
end
raise UndefinedRLE if result.empty?
result
end
Log2 = Math.log(2)
def self.encode(ary, exponent)
io = StringIO.new
encoder = Encoder.new(exponent, io)
ary.each{|result| encoder << result}
encoder.finish
io.string
end
def self.decode(bitstring)
ary = Decoder.new(StringIO.new(bitstring)).read
ary.pop
ary
end
class Encoder
attr_reader :exponent, :io
def initialize(exponent, io)
@exponent, @io = exponent, io
io.print [exponent].pack("c")
@ones = 0
@buf = ""
# @finished = false
end
def << bool
finished? and raise "Channel closed"
if bool
@ones += 1
else
m = 2**exponent
div, rem = @ones.divmod m
@buf << ("1" * div)
@buf << (("%0#{exponent+1}s" % (rem).to_s(2)).gsub(/ /, "0"))
if (blen = @buf.length) >= 8
#p [exponent, div, rem, @buf, blen]
bytes = blen / 8
io.print([@buf.slice!(0, bytes * 8)].pack("B*"))
end
#p io.string
@ones = 0
end
end
def finish
self << false
@finished = true
@buf << ("1" * (8 - @buf.length % 8)) if @buf.length % 8 > 0
io.print([@buf].pack("B*"))
end
def finished?
@finished
end
end
class Decoder
attr_reader :io
def initialize(io)
@io = io
@state = :exp
@buf = ""
@div = 0
@rem = ""
end
def exponent
if @state == :exp # and io.ready?
@exponent = io.read(1).unpack("c")[0]
@state = :div
end
@exponent
end
def read
if @state == :exp # and io.ready?
@exponent = io.read(1).unpack("c")[0]
@state = :div
end
result = []
@buf << io.read.unpack("B*")[0]
while not @buf.empty?
#p [@buf, @state, @exponent, @div, @rem]
if @state == :div
while not @buf.empty? and @buf[0] == ?1
@buf.slice!(0, 1)
@div += 1
end
@state = :rem unless @buf.empty?
end
#p [@buf, @state, @div, @rem]
if @state == :rem
req = exponent + 1 - @rem.length
if @buf.length < req
@rem << @buf.slice!(0..-1)
else
@rem << @buf.slice!(0, req)
result.concat([true] * (@div * 2**exponent + @rem.to_i(2)))
result << false
@div = 0
@rem = ""
@state = :div
end
end
end
result
end
end
end