Issue #22399 has been reported by hasumikin (hitoshi hasumi). ---------------------------------------- Feature #22399: Iterator Methods for String Bit Operations https://bugs.ruby-lang.org/issues/22399 * Author: hasumikin (hitoshi hasumi) * Status: Open ---------------------------------------- PR URL: https://github.com/ruby/ruby/pull/XXXXX [TBD] ### 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. ```ruby 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. ```ruby 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. ```ruby 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. ```ruby 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. ```ruby 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. -- https://bugs.ruby-lang.org/