Class: LZW::BitBuf

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/lzw/bitbuf.rb

Overview

Wrap up a String, in binary encoding, for single-bit manipulation and working with variable-size integers. This is necessary because our LZW streams don’t align with byte boundaries beyond the 4th byte, they start writing codes 9 bits at a time (by default) and scale up from that later.

Derived from Gene Hsu’s work at github.com/genehsu/bitarray/blob/master/lib/bitarray/string.rb but it wasn’t worth inheriting from an unaccepted pull to a gem that’s unmaintained. Mostly, masking out is way smarter than something like vec() which is what I’m doing in the Perl version of this right now.

Compared to bitarray: I’m forcing this to default-0 for bits, making a fixed size unnecessary, and supporting both bit orders. And changing the interface, so I shouldn’t subclass anyway.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(field: "\000", msb_first: false) ⇒ BitBuf

Returns a new instance of BitBuf.

Parameters:

  • field (String) (defaults to: "\000") —

    Optional string to wrap with BitBuf. Will be copied with binary encoding.

  • msb_first (Boolean) (defaults to: false) —

    Optionally force bit order used when writing integers to the bitfield. Default false.



55
56
57
58
59
60
61
 
# File 'lib/lzw/bitbuf.rb', line 55

def initialize(
  field: "\000",
  msb_first: false
)
  @field = field.b
  @msb_first = msb_first
end

Instance Attribute Details

#bytesize ⇒ Numeric (readonly)

Returns the current bytesize of the BitBuf

Returns:

  • (Numeric) 


117
118
119
 
# File 'lib/lzw/bitbuf.rb', line 117

def bytesize
  @field.bytesize
end

#field ⇒ String (readonly)

The string, set to binary encoding, wrapped by this BitBuf. This is essentially the “pack”ed form of the bitfield.

Returns:

  • (String) 


49
50
51
 
# File 'lib/lzw/bitbuf.rb', line 49

def field
  @field
end

#msb_first ⇒ Boolean (readonly)

If true, #get_varint and #set_varint work in MSB-first order.

Returns:

  • (Boolean) 


44
45
46
 
# File 'lib/lzw/bitbuf.rb', line 44

def msb_first
  @msb_first
end

Instance Method Details

#[](pos) ⇒ Fixnum

Read a bit at pos. Trying to read a bit beyond the currently defined #bytesize will automatically grow the BitBuf to the next whole byte needed to include that bit.

Parameters:

  • pos (Numeric) —

    0-indexed bit position

Returns:

  • (Fixnum) —

    the bit value at the requested bit position.



96
97
98
99
100
 
# File 'lib/lzw/bitbuf.rb', line 96

def [](pos)
  byte, bit = byte_divmod(pos)

  (@field.getbyte(byte) >> bit) & 1
end

#[]=(pos, val)

Set a specific bit at pos to val. Trying to set a bit beyond the currently defined #bytesize will automatically grow the BitBuf to the next whole byte needed to include that bit.

Parameters:

  • pos (Numeric) —

    0-indexed bit position

  • val (Numeric) —

    0 or 1. 2 isn’t yet allowed for bits.



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/lzw/bitbuf.rb', line 69

def []=(pos, val)
  byte, bit = byte_divmod(pos)

  # puts "p:#{pos} B:#{byte} b:#{bit} = #{val}  (#{self[pos]})"

  case val
  when 0
    @field.setbyte(
      byte,
      @field.getbyte(byte) & AND_BITMASK[bit]
    )
  when 1
    @field.setbyte(
      byte,
      @field.getbyte(byte) | OR_BITMASK[bit]
    )
  else
    fail ArgumentError, "Only 0 and 1 are valid for a bit field"
  end
end

#each

Iterate over the BitBuf bitwise.



103
104
105
106
107
 
# File 'lib/lzw/bitbuf.rb', line 103

def each
  (bytesize * 8).times do |pos|
    yield self[pos]
  end
end

#get_varint(pos, width) ⇒ Numeric?

Fetch an unsigned integer of “width” size from “pos” in the BitBuf. Unlike other methods, if “pos” is beyond the end of the BitBuf, nil is returned.

Returns:

  • (Numeric, nil) 


145
146
147
148
149
150
151
152
153
154
155
 
# File 'lib/lzw/bitbuf.rb', line 145

def get_varint(pos, width)
  return nil if (pos + width) > bytesize * 8

  int = 0
  width.times do |bit_offset|
    int += 2**bit_offset *
      self[pos + (@msb_first ? (width - bit_offset) : bit_offset)]
  end

  int
end

#set_varint(pos, width, val)

Store an unsigned integer in of “bits” length, at “pos” position, and in LSB-first order unless #msb_first is true. This method will grow the BitBuf as necessary, in whole bytes.

Parameters:

  • pos (Numeric) —

    0-indexed bit position to write the first bit

  • width (Numeric) —

    Default 8. The desired size of the supplied integer. There is no overflow check.

  • val (Numeric) —

    The integer value to be stored in the BitBuf.



129
130
131
132
133
134
135
136
137
138
 
# File 'lib/lzw/bitbuf.rb', line 129

def set_varint(pos, width, val)
  fail ArgumentError, "integer overflow for #{width} bits: #{val}" \
    if val > 2**width

  width.times do |bit_offset|
    self[pos + (@msb_first ? (width - bit_offset - 1) : bit_offset)] =
      (val >> bit_offset) & 1
  end
  self
end

#to_s

Returns the BitBuf as a text string of zeroes and ones.



110
111
112
 
# File 'lib/lzw/bitbuf.rb', line 110

def to_s
  @field.unpack1("b*")
end