On Tue, Oct 12, 2010 at 6:35 AM, Jason Larsen <jason.larsen / gmail.com> wrote:
> I'm trying to write a pure Ruby implementation of SHA1. In order to do
> so, I need to be able to directly manipulate bits. I know about the
> bitwise operators in Ruby, but I'm having issues with the way that
> Ruby wraps things up in classes. Basically I've run into two problems.
>
> PROBLEM 1: I need to pad the message by appending a 1-bit, and then a
> certain number of 0s. When appending numbers (e.g. 0b1) to the end of
> by string, Ruby wraps each number in its Fixnum class making it 1 byte
> long: So basically adding 0b1 appends 0b0000_0001, which is 7 zeros
> that shouldn't be there. The fix I've found is I to tack 0x80 on the
> end, which concats 0b1000_0000. The downside is that I have to keep
> track of my zeros in batches of bytes (which at this point my
> implementation handles alright), but I'd like to know how to do it bit
> by bit if possible.
>
> I've seen the String.unpack and Array.pack used for binary data.
> However, I can only get the bits out in one glob str.unpack("B*"), or
> str.unpack("B8"*string.length), which still just gives me a bunch of
> stringified 8bit binary values. Seems like there should be a better
> way.
>
> PROBLEM 2: After adding a one-bit and k zeros, I need to append a 64-
> bit long integer representing the length of the message being hashed.
> It seem like Fixnum is 8 bytes long on my machine, so the question is
> how do I add a 64bit binary representation of this number to the end
> of a string?
>
> Any help would be greatly appreciated. Thanks in advance.

I would create a class which is a thin wrapper around a String
instance and probably a length in bits.  Then add methods that perform
bit manipulations that you need and use that in your implementation.

# untested
class BitStream
  NULL = "\000".force_encoding "BINARY"

  def initialize(s = "", l = 0)
     @s = s
     @l = l
     @s.force_encoding "BINARY"
  end

  def bit_length; @l; end

  def add_bit(b)
    b = case b
      when false, 0, nil
        0
      else
        1
    end

    self[@l] = b
  end

  def [](index)
    raise "Index error" if index < 0 || index >= @l
    byte, off = index.divmod 8
    @s[byte].ord & (1 << off) == 0 ? 0 : 1
  end

  def []=(index, bit)
    raise "Index error" if index < 0
    byte, off = index.divmod 8

    while @s.bytesize < byte
      @s << NULL
    end

    x = @s[byte].ord

    @s[byte] = (if bit == 1
      x | (1 << off)
    else
      x & (0xFF ^ (1 << off))
    end).chr
  end
end

Kind regards

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/