ruby-dev

Download

ruby-dev@ml.ruby-lang.org

October 2026

1 participants
2 discussions

[ruby-dev:52247] [Ruby Feature#22405] Run-Length Methods for String Bit Operations
by hasumikin (hitoshi hasumi) 07 Oct '26

07 Oct '26

Issue #22405 has been reported by hasumikin (hitoshi hasumi). ---------------------------------------- Feature #22405: Run-Length Methods for String Bit Operations https://bugs.ruby-lang.org/issues/22405 * Author: hasumikin (hitoshi hasumi) * Status: Open ---------------------------------------- PR: (WIP) ### What this adds This ticket adds the run-length methods of the String bit operation API. A run is a maximal sequence of consecutive bits with the same value. The methods build on the region arguments of #22279 and on the iterator conventions of #22399: ``` String#bit_run_length(bit, offset, lsb_first: true) -> Integer | nil String#each_bit_run(lsb_first: true) {|bit, offset, length| ... } -> self String#each_bit_run(offset, length, lsb_first: true) {|bit, offset, length| ... } -> self String#each_bit_run(range, lsb_first: true) {|bit, offset, length| ... } -> self String#each_bit_run(lsb_first: true) -> Enumerator String#each_bit_run(offset, length, lsb_first: true) -> Enumerator String#each_bit_run(range, lsb_first: true) -> Enumerator String#bit_runs(lsb_first: true) -> Array String#bit_runs(offset, length, lsb_first: true) -> Array String#bit_runs(range, lsb_first: true) -> Array String#bit_runs(lsb_first: true) {|bit, offset, length| ... } -> self String#bit_runs(offset, length, lsb_first: true) {|bit, offset, length| ... } -> self String#bit_runs(range, lsb_first: true) {|bit, offset, length| ... } -> self ``` `each_bit_run` and `bit_runs` visit every run of the region as `[bit, offset, length]`. The runs come in increasing order of offset. `bit_run_length` returns the length of the run of `bit` that begins at `offset`. ```ruby data = "\x0F\x01".b data.bit_runs # => [[1, 0, 4], [0, 4, 4], [1, 8, 1], [0, 9, 7]] data.bit_runs(8..) # => [[1, 8, 1], [0, 9, 7]] data.bit_run_length(1, 0) # => 4 data.bit_run_length(0, 0) # => 0 data.bit_run_length(1, 16) # => nil data.each_bit_run.size # => 4 ``` The pairing follows `each_bit` / `bits`. The `each_*` form returns `self` with a block. Without a block, it returns an Enumerator. The Array form returns an Array. With a block, it behaves like the `each_*` form. ### Use cases #### Bitstream parsing (MSB-first) - **Rice codes for sensor logs.** A battery device logs the differences between consecutive samples. Small differences are frequent, so a Rice code stores each value as a unary quotient followed by `k` remainder bits. The unary part is a run of set bits, so `bit_run_length(1, pos, lsb_first: false)` reads it in one call. The region form of `bits` then reads the remainder from the position where the run ended. ```ruby # Rice code, MSB-first. A value n is stored as: # q = n >> k set bits, one cleared bit, then the k low bits of n # bs is the bitstream (a binary String) and pos is a bit offset in it. # Returns the value and the bit offset of the next code. def read_rice(bs, pos, k) q = bs.bit_run_length(1, pos, lsb_first: false) # count the set bits pos += q + 1 # skip them and the cleared bit # Read k bits and build an Integer from them, MSB first r = bs.bits(pos, k, lsb_first: false).inject(0) {|acc, b| acc * 2 + b } [(q << k) | r, pos + k] end # "\x79\x14" = 0111 1001 0001 0100, decoded with k = 2: # pos unary q remainder value # 0 0 0 11 0 << 2 | 3 = 3 # 3 110 2 01 2 << 2 | 1 = 9 # 8 0 0 00 0 << 2 | 0 = 0 # 11 10 1 10 1 << 2 | 2 = 6 # (bit 15 is padding) bs = "\x79\x14".b pos = 0 values = [] 4.times do value, pos = read_rice(bs, pos, 2) # pass the returned offset to the next call values << value end values # => [3, 9, 0, 6] pos # => 15 ``` #### 1 bpp frame buffers - **E-paper partial refresh.** An e-paper panel refreshes a small window much faster than the full screen, and each refresh costs power. A driver keeps the previous frame and sends only the pixels that changed. `bitwise_xor` of the previous row and the new row marks the changed pixels. `bit_runs` of the result gives the changed spans. Most panel controllers accept a window only at byte boundaries. Thus the driver widens each span to a multiple of 8 and refreshes one window per span. The same pattern applies to a monochrome LCD with a page or row buffer. ```ruby # 32 pixels, MSB-first (the high bit of each byte is the left pixel), 1 = black old_row = "\xFF\x00\xF0\x0F".b new_row = "\xFF\x3C\xF0\x00".b # XOR sets a bit only where the pixel changed: # pixel: 0 8 16 24 # old_row: 1111 1111 0000 0000 1111 0000 0000 1111 # new_row: 1111 1111 0011 1100 1111 0000 0000 0000 # changed: 0000 0000 0011 1100 0000 0000 0000 1111 # ^^^^ ^^^^ # 10..13 28..31 changed = old_row.bitwise_xor(new_row) # bit_runs gives [bit, offset, length] for each run: # [[0, 0, 10], [1, 10, 4], [0, 14, 14], [1, 28, 4]] # Keep the runs of 1 (the changed spans) and convert them to Ranges. spans = changed.bit_runs(lsb_first: false).select {|bit, _, _| bit == 1 } .map {|_, x, width| x...(x + width) } spans # => [10...14, 28...32] # Widen each span to byte boundaries for the panel controller: # round the begin down and the end up to a multiple of 8. # 10...14 -> (10 / 8 * 8)...((14 + 7) / 8 * 8) = 8...16 # 28...32 -> (28 / 8 * 8)...((32 + 7) / 8 * 8) = 24...32 spans.map {|r| (r.begin / 8 * 8)...((r.end + 7) / 8 * 8) } # => [8...16, 24...32] ``` #### Columnar data (LSB-first) - **Bulk copies over valid ranges.** An Apache Arrow validity bitmap marks the null elements. Where the valid elements form long runs, a kernel copies each run as one slice and does not test every element. `bit_runs(0, length)` gives the runs within the column length. `bit_run_length(1, i)` tells how many valid elements start at `i`, for a loop that advances by run. ```ruby validity = "\xFC\x0F".b # 12 elements, elements 0 and 1 are null validity.bit_runs(0, 12).select {|bit, _, _| bit == 1 } .map {|_, off, len| off...(off + len) } # => [2...12] ``` #### Microcontrollers - **Block allocators.** A memory allocator or a page map keeps a bitmap of the used blocks. A first-fit allocation for `n` blocks is the first run of cleared bits with a sufficient length. Such an allocator is written in Ruby in two settings. One is a program assuming Spinel compiles AOT to native code, where a bitmap walk in Ruby becomes a plain loop. The other is a microcontroller program that manages a pool of slots. In both cases `each_bit_run` walks the bitmap and allocates nothing. ```ruby bitmap = "\xFF\x0F\xC0\x00".b # 32 blocks, 1 = in use def first_fit(bitmap, n) bitmap.each_bit_run do |bit, off, len| return off if bit.zero? && len >= n end nil end first_fit(bitmap, 8) # => 12 first_fit(bitmap, 20) # => nil ``` - **Pulse widths from a sampled input.** A program samples a GPIO pin at a fixed rate into a bitmap. This turns a signal into runs. `bit_runs` converts the capture into level and width pairs. These pairs are the input of an IR remote decoder (NEC and similar protocols distinguish bits by pulse width) or of a logic analyzer view. ```ruby capture = "\x01\x00\xFF\x0F".b # one sample per bit, LSB-first capture.bit_runs.map {|level, _, width| [level, width] } # => [[1, 1], [0, 15], [1, 12], [0, 4]] ``` ### API Contracts The three methods follow the rules of the earlier tickets. `each_bit_run` and `bit_runs` take the region arguments of #22279 and share every contract of `each_bit` in #22399. In particular, reads clamp, offsets are absolute, errors are raised without a block, the Enumerator validates again on use, and frozen receivers work. `bit_run_length` takes a lone `offset` like `bit_get` in #22118 and a `bit` argument like `each_bit_offset` in #22399. Encoding, `lsb_first:` and the out-of-range errors are as in #22118 and #22279. The contracts below are the ones specific to runs. 1. **Runs are cut at the region boundaries.** The first run starts at the region start, even if the same bit continues before it. The last run ends at the region end. 2. **Each run is one Array** `[bit, offset, length]`, with `bit` as `0` or `1`. A block with three parameters receives the three values. A block with one parameter, or a lambda, receives the Array, as with `Hash#each`. `to_a` and `bit_runs` collect the Arrays. 3. **`bit_run_length` returns `nil`, `0` or a count.** It returns `nil` when `offset` is at or beyond the end of the string. It returns `0` when the bit at `offset` differs from `bit`. Otherwise it counts up to the first differing bit or the end of the string. 4. **Enumerator#size** is the number of runs in the region, computed on demand from the current contents of the receiver. 5. **The block can modify the receiver.** The iteration reads each run from the current contents of the string when it visits the run. It clamps the length of the run to the current end and stops there. A longer receiver does not extend the iteration beyond the original region. ### Performance The script below gives the times. Each time is the median of 5 calls on a 1 MiB buffer. The machine is an AMD Ryzen 5 5600X with Ruby 4.1.0dev (master at 2db3072cfb) and this patch, gcc 13.3.0 `-O3`, YJIT off. {{collapse(Benchmark script) ```ruby few = ("\xFF".b * 4096 + "\x00".b * 4096) * 128 # 1 MiB, 256 runs many = "\xAA".b * (1 << 20) # 1 MiB, 8 Mi runs # The alternatives build the same [bit, offset, length] Arrays as bit_runs. def by_chunk_while(s) off = 0 s.bits.chunk_while {|a, b| a == b }.map {|c| [c[0], off, c.size].tap { off += c.size } } end def by_scan(s) off = 0 s.unpack1("b*").scan(/0+|1+/).map {|m| [m.ord - 48, off, m.size].tap { off += m.size } } end def median(n = 5) Array.new(n) { t = Process.clock_gettime(Process::CLOCK_MONOTONIC) yield Process.clock_gettime(Process::CLOCK_MONOTONIC) - t }.sort[n / 2] end { few:, many: }.each do |name, s| raise unless by_chunk_while(s) == s.bit_runs && by_scan(s) == s.bit_runs printf "%-4s chunk_while %.4f\n", name, median { by_chunk_while(s) } printf "%-4s scan %.4f\n", name, median { by_scan(s) } printf "%-4s bit_runs %.4f\n", name, median { s.bit_runs } printf "%-4s size %.4f\n", name, median { s.each_bit_run.size } end printf "index %.6f\n", median { few.unpack1("b*").index("0") } printf "bit_run_length %.6f\n", median { few.bit_run_length(1, 0) } ``` }} | | Few runs | Many runs | |--------------------------|---------:|----------:| | `bits` + `chunk_while` | 700 ms | 2,210 ms | | `unpack1("b*")` + `scan` | 36 ms | 2,440 ms | | `bit_runs` | 1.1 ms | 260 ms | | `each_bit_run.size` | 1.1 ms | 26 ms | | | Few runs | |----------------------------|---------:| | `unpack1("b*").index("0")` | 8.4 ms | | `bit_run_length(1, 0)` | 4 us | The methods skip a byte of all `0` or all `1` bits in one step. In the many-runs case, the Array for each run bounds the time. `each_bit_run.size` makes no Array, so it is 10 times faster there. -- https://bugs.ruby-lang.org/

2 1

[ruby-dev:52246] [Ruby Feature#22399] Iterator Methods for String Bit Operations
by hasumikin (hitoshi hasumi) 07 Oct '26

07 Oct '26

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/

2 1