From: Daniel Martin <martin@...>
Date: 2006-09-12T02:43:29+09:00
Subject: [QUIZ][SOLUTION] Secret Agent 00111 (#94)

Q:

Got your memo about needing help with the encoding.  The code is
below; I've taken a fairly straightforward approach here, since the
handheld device you described has more than enough computational power
to encode what it needs to quickly enough to get the message through.

By the way, one of your unit tests - with the two StringIO objects -
gave me an inordinate amount of trouble.  I suggest that in the future
you take advantage of IO.pipe when faced with a similar situation.

Let me know what's up with those retirement plans, and look me up if
you ever find yourself on this side of the pond.

Your Friend,
Marshall Flinkman

#! /usr/bin/env ruby
require 'io/nonblock'

# The SecretAgent00111CommunicationGizmo class implements a way to
# send a series of true/false values through a binary channel using
# only a relatively small number of bytes.  It does this by assuming
# that true values are much more likely than false values, and
# that therefore one can do a simple run length encoding on the
# original series of true/false values and end up with a sequence
# of numbers amenable to being compressed by a Rice code. (i.e. by
# a Golomb code with the parameter a power of 2)
#
# The format of a compressed message of integers is:
#
# * One byte of _exponent_.  Our code will use a parameter value of 
#   b = 2 ** _exponent_
# * For each number _n_ that's encoded:
#   * _d_ '1' bits
#   * a '0' bit
#   * _exponent_ bits that as a binary number form the value _r_
#   The number _n_ then has the value <tt> n == d * (2 ** exponent) + r </tt>
# * Whatever number of '1' bits are necessary to pad the whole
#   transmission to an even byte boundary
#
# Bits within a byte are ordered as by _pack("B*")_ -- that is, MSB first.
class SecretAgent00111CommunicationGizmo
  class UndefinedRLE < Exception; end
end

# We're going to define a bunch of class methods now,
# and SecretAgent00111CommunicationGizmo is just too
# long to write out over and over again, and I don't
# like the look of putting "self." in front of each
# method name as I define it, so...
class << SecretAgent00111CommunicationGizmo

  # Run length encode an input array of true/false values.
  # Note that this array *must* end in a "false" value, or an
  # exception (SecretAgent00111CommunicationGizmo::UndefinedRLE)
  # will be thrown.
  def rle(tfarr)
    raise self::UndefinedRLE unless false == tfarr.last
    ans = []
    tfarr.inject(0) {|a,tf|
      if tf
        a + 1
      else
        ans<<a; 0
      end
    }
    ans
  end

  # Undo the operation of +rle+.  Expands a given array of numbers
  # into an array of true/false values.
  def unrle(inarr)
    inarr.map{|x| [[true]*x,false]}.flatten
  end

  # This method does the internal work of encoding a
  # given number by our Rice code into a string of '0' and '1'.
  # Not really for client use.
  def bits_for_encoding(x, exponent)
    a, b = x.divmod(1<<exponent)
    ['1' * a, sprintf('0%0*b', exponent, b)].join
  end

  # Encode a true/false array by first adding a "false" to the end
  # and then encoding the resulting string of numbers via our Rice
  # code.
  def encode(array,exponent)
    msg = rle(array+[false]).map{|x|
      bits_for_encoding(x,exponent)
    }.join
    msg += '1' * ((- msg.length) % 8)
    exponent.chr + [msg].pack("B*")
  end

  # This method does the internal work to decode a
  # message in '1' and '0' bits into an array of
  # integers.  Note that the string in msg is changed
  # by this method, and shortened to whatever sequence
  # at the end couldn't be decoded.
  def decode_bits(msg,exponent)
    ans = []
    trim_from = 0
    msg.scan(/(1*)0([01]{#{exponent}})/) {|a,b|
      ans << a.length*(1<<exponent) + b.to_i(2)
      trim_from = $~.end(0)
    }
    msg.slice!(0,trim_from)
    ans
  end

  # Undo the result of +encode+
  def decode(bitstring)
    # It's not polite to mangle someone else's bitstring
    # so don't use slice! here
    # Seriously, the sample program stops working if you
    # mangle bitstring because then it doesn't give the right
    # input to Decoder.new(StringIO.new(s))
    exponent = bitstring.slice(0,1)[0]
    msg = bitstring[1..-1].unpack("B*")[0]
    unrle(decode_bits(msg,exponent))[0..-2]
  end
end

class SecretAgent00111CommunicationGizmo
  # Lets subclasses call class methods as their own
  def method_missing(meth, *args)
    self.class.send(meth,*args)
  end

  # This class is meant for on-the-fly compression to a given
  # IO channel.
  class Encoder < SecretAgent00111CommunicationGizmo
    def initialize(exponent, output)
      output << exponent.chr
      @exponent = exponent
      @output = output
      @current_byte = ''
      @current_run = 0
    end
    def <<(tf)
      if tf
        @current_run += 1
      else
        send_number(@current_run)
        @current_run=0
      end
      self
    end
    def finish
      self << false
      @current_byte += '1' * ((-@current_byte.length)%8)
      output_maybe
    end

    private
    def output_maybe
      if @current_byte.length >= 8
        out_bits = @current_byte.slice!(0,(@current_byte.length/8)*8)
        @output << [out_bits].pack("B*")
      end
    end
    def send_number(x)
      @current_byte += bits_for_encoding(x,@exponent)
      output_maybe
    end
  end

  # This class is meant for on-the-fly decompression to a given
  # IO channel.
  class Decoder < SecretAgent00111CommunicationGizmo
    attr_reader :exponent
    def initialize(io)
      # StringIO isn't really an IO object, so doesn't know about
      # nonblock.
      io.nonblock = true if io.respond_to?(:nonblock=)
      @io = io
      @initialized = false
      @remaining = ''
    end
    def exponent
      if not @initialized
        @exponent = @io.readchar
        @initialized = true
      end
      @exponent
    end
    def read
      exp = exponent
      ans = []
      # Use read with no arguments since read with an integer
      # argument messes up the bizarre way StringIO is used in
      # the unit test.  Does Q not know about IO.pipe ?
      buff = @io.read rescue buff = nil
      while buff and buff.length > 0
        @remaining += buff.unpack("B*")[0]
        ans.concat unrle(decode_bits(@remaining, exp))
        buff = @io.read rescue buff = nil
      end
      ans
    end
  end
end

__END__

-- 
s=%q(  Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1]       )
       puts "s=%q(#{s})",s.map{|i|i}[1]