Feature #22399: Iterator Methods for String Bit Operations

• Status: Open
• Assignee: -
• Target version: -

[hasumikin (hitoshi hasumi)]

PR URL: https://github.com/ruby/ruby/pull/19161

What this adds

The original proposal (#22082) listed this iterator group. Matz asked for a minimal subset in #22082#note-13, and the proposal deferred the group in #22082#note-14. The methods build on the single-bit methods of #22118 and on the region arguments of #22279:

String#each_bit(lsb_first: true) {|bit| ... }                 -> self
String#each_bit(offset, length, lsb_first: true) {|bit| ... } -> self
String#each_bit(range, lsb_first: true) {|bit| ... }          -> self
String#each_bit(lsb_first: true)                              -> Enumerator
String#each_bit(offset, length, lsb_first: true)              -> Enumerator
String#each_bit(range, lsb_first: true)                       -> Enumerator

String#bits(lsb_first: true)                                  -> Array
String#bits(offset, length, lsb_first: true)                  -> Array
String#bits(range, lsb_first: true)                           -> Array
String#bits(lsb_first: true) {|bit| ... }                     -> self
String#bits(offset, length, lsb_first: true) {|bit| ... }     -> self
String#bits(range, lsb_first: true) {|bit| ... }              -> self

String#each_bit_offset(bit, lsb_first: true) {|offset| ... }                 -> self
String#each_bit_offset(bit, offset, length, lsb_first: true) {|offset| ... } -> self
String#each_bit_offset(bit, range, lsb_first: true) {|offset| ... }          -> self
String#each_bit_offset(bit, lsb_first: true)                                 -> Enumerator
String#each_bit_offset(bit, offset, length, lsb_first: true)                 -> Enumerator
String#each_bit_offset(bit, range, lsb_first: true)                          -> Enumerator

String#bit_offsets(bit, lsb_first: true)                                 -> Array
String#bit_offsets(bit, offset, length, lsb_first: true)                 -> Array
String#bit_offsets(bit, range, lsb_first: true)                          -> Array
String#bit_offsets(bit, lsb_first: true) {|offset| ... }                 -> self
String#bit_offsets(bit, offset, length, lsb_first: true) {|offset| ... } -> self
String#bit_offsets(bit, range, lsb_first: true) {|offset| ... }          -> self

each_bit and bits visit every bit of the region. They give each bit as 0 or 1. each_bit_offset and bit_offsets visit the offsets of the bits that are equal to bit. The bit argument is 0, 1, true or false. The offsets come in increasing order.

data = "\xAA\xCC".b
data.bits(8, 4)                        # => [0, 0, 1, 1]
data.bit_offsets(1)                    # => [1, 3, 5, 7, 10, 11, 14, 15]
data.bit_offsets(0, 8..)               # => [8, 9, 12, 13]
data.bit_offsets(1, lsb_first: false)  # => [0, 2, 4, 6, 8, 9, 12, 13]
data.each_bit_offset(1).size           # => 8

The pairing follows each_byte / bytes. The each_* form returns self with a block. Without a block, it returns an Enumerator. The Array form returns an Array. Like bytes, the Array form also accepts a block. With a block, it behaves like the each_* form.

Use cases

Columnar data (LSB-first)

Apache Arrow stores validity bitmaps and boolean columns as LSB-first packed bitmaps. Arrow pads a bitmap buffer to a multiple of 64 bytes. The padding bits have no defined value, so a read must stop at the column length. The region forms express this limit directly. The typical read patterns are:

• Null positions: bit_offsets(0, 0, length) gives the indexes of the null elements of a column. A Ruby loop over bit_set? is not necessary. Without the region, the result includes the padding bits as nulls.

  validity = "\xFD\x03".b         # 10 elements, element 1 is null, bits 10..15 are padding
  validity.bit_offsets(0)         # => [1, 10, 11, 12, 13, 14, 15]
  validity.bit_offsets(0, 0, 10)  # => [1]
  

• Boolean columns: bits(0, length) converts a packed column into an Array of 0 and 1 values.

• Slices: The region forms scan only the chunk of a bitmap that a batch covers. The offsets stay absolute. Thus they work with bit_set? and the mutation methods without adjustment.

Microcontrollers and wire formats

The each_* forms walk a buffer and do not allocate an Array. The region forms (with offset.. or (offset, length)) continue from any bit offset. They do not unpack the whole buffer. On CRuby this matters for large buffers. bits on a 1 MiB buffer builds an Array of 8 million elements. each_bit with a block allocates nothing in the method itself.

The same property helps implementations for microcontrollers (mruby, PicoRuby). These implementations take the core API as their specification. On such devices, a String is often the only buffer a program has.

• Protocol headers: RFC protocol diagrams number bits MSB-first. bits(offset, length, lsb_first: false) returns a header field in wire order. A decoder can follow the diagram directly and does not reverse bits.

  hdr = "\x12\x34\x81\x80".b                 # DNS header: ID, then the 16 flag bits
  flags = hdr.bits(16, 16, lsb_first: false)
  qr, rd, ra = flags[0], flags[7], flags[8]  # => 1, 1, 1
  

• Huffman and other prefix codes: A decoder reads a code stream one bit at a time and descends a tree. each_bit with a region reads the packed codes in the order the encoder wrote them. The decoder allocates nothing per bit. Bit-serial formats differ in packing order. JPEG entropy-coded segments and CCITT fax pack MSB-first, so they need lsb_first: false. DEFLATE packs LSB-first and reads with the default.

  tree = ["a", ["b", ["c", "d"]]]  # 0 => a, 10 => b, 110 => c, 111 => d
  stream = "\x5B\x80".b            # 0 10 110 111 = "abcd", 9 bits
  node = tree
  out = +""
  stream.each_bit(0, 9, lsb_first: false) do |bit|
    node = node[bit]
    if node.is_a?(String)
      out << node
      node = tree
    end
  end
  out # => "abcd"
  

• Bit-banged buses: A shift-register chain receives a multi-byte frame MSB-first. each_bit(lsb_first: false) over the frame gives one GPIO write per bit. The program does not split the frame into Integers first.

• 1 bpp frame buffers: A display such as the SSD1306 stores a page as one byte per column. Bit 0 is the top pixel. With the bitwise methods of #22118, bit_offsets(1) turns a pixel test into a coordinate list. bitwise_and of a sprite and the background keeps only the overlapping pixels. bit_offsets(1) yields their positions. i / 8 is the column and i % 8 is the row within the page.

  sprite     = "\x00\x3C\x3C\x00".b
  background = "\x00\x00\x30\xFF".b
  hits = sprite.bitwise_and(background)
  hits.bit_offsets(1).map { |i| [i / 8, i % 8] } # => [[2, 4], [2, 5]]
  

Why not String#unpack?

unpack1("b*") and unpack1("B*") already give the bits as a "0"/"1" String. That form has four limits:

• It allocates a String eight times the size of the receiver.
• It moves only by whole bytes with @.
• It cannot list the offsets of the set or cleared bits.
• It returns characters, where bit_get returns Integers.

The iterators read in place. They take bit regions. They list offsets directly. Their results compose with the rest of the bit API.

API Contracts

1. Region arguments are the same as for bit_count: no argument (the whole string), (offset, length), or a Range, plus lsb_first:. A lone offset raises ArgumentError, as for bit_count.
2. Reads clamp. The methods cut a region that extends past the end of the string down to the bits that exist. A region that begins at or beyond the end yields nothing. An empty or inverted region yields nothing. bit_count, the other read-only region method, has the same behavior.
3. Offsets are absolute. each_bit_offset and bit_offsets yield offsets relative to the start of the string, in the numbering that lsb_first: selects. Thus data.bit_set?(i, lsb_first: x) is true for every i that data.each_bit_offset(1, lsb_first: x) yields.
4. The bit argument accepts 0, 1, true or false. The method converts any other object with to_int, as for an index, with the same exceptions. An Integer other than 0 or 1 raises ArgumentError. An object without to_int raises TypeError.
5. Errors are raised without a block. The method validates the arguments before it creates the Enumerator. Thus "".each_bit(-1, 4) raises IndexError immediately, not on the first each. The Enumerator validates the arguments again when it iterates or computes its size. Thus to_int conversions can run more than once.
6. Enumerator#size is the number of bits in the region for each_bit. For each_bit_offset, it is the number of matching bits. The Enumerator computes the size on demand from the current contents of the receiver.
7. The block can modify the receiver. The iteration reads the string again for every bit. It stops at the current end of the string. A longer receiver does not extend the iteration beyond the original region.
8. Out-of-range arguments follow #22279. A negative offset raises IndexError. A negative length raises ArgumentError. A position or length beyond 2**64 - 1 raises ArgumentError.
9. Frozen receivers work, because all four methods only read.
10. Encoding has no effect. The methods treat the receiver as a byte sequence, as in #22118.
11. lsb_first changes only the bit numbering within each byte. The byte order does not change, as in #22118 and #22279. The value must be true or false. Any other value raises ArgumentError, as in #22118.

Performance

each_bit_offset and bit_offsets mask each byte against the region. They skip the bytes with no matching bit. Thus they scan a sparse bitmap byte by byte, not bit by bit.

The measurements use an AMD Ryzen 5 5600X, a 1 MiB buffer, and ruby 4.1.0dev with YJIT off. YJIT changes the loop times by less than 15%, because the C method calls dominate the loops. Each alternative produces the same result as the new method. Thus its time includes the conversion of the unpack1("b*") bit String to Integers or offsets. The sparse buffer has 1,000 set bits. The dense buffer is "\xAA" * 1 MiB.

Operation	bit_get / bit_set? loop	unpack1("b*") based	New method
Offsets of the set bits, sparse buffer	0.56 s	0.0125 s	bit_offsets(1): 0.0015 s
Offsets of the set bits, dense buffer	0.61 s	0.29 s	bit_offsets(1): 0.052 s
All bits as an Integer Array, dense buffer	0.63 s	0.43 s	bits: 0.072 s
All bits yielded to a block, dense buffer	0.35 s	0.51 s	each_bit { }: 0.27 s

The block forms gain little speed over a bit_get loop, because the block call dominates. Their benefit is that the method itself allocates nothing.

[hasumikin (hitoshi hasumi)]

• Description updated (diff)