ruby-dev
Threads by month
- ----- 2026 -----
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2025 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2024 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2023 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2022 -----
- December
- November
October 2026
- 1 participants
- 6 discussions
[ruby-dev:52250] [Ruby Feature#22482] String#bit_index, a bit search for String bit operations
by hasumikin (hitoshi hasumi) 17 Nov '26
by hasumikin (hitoshi hasumi) 17 Nov '26
17 Nov '26
Issue #22482 has been reported by hasumikin (hitoshi hasumi).
----------------------------------------
Feature #22482: String#bit_index, a bit search for String bit operations
https://bugs.ruby-lang.org/issues/22482
* Author: hasumikin (hitoshi hasumi)
* Status: Open
----------------------------------------
Impl: (WIP)
This is a reply to the comment of Matz in #22399#note-3. It replaces the seven methods of #22399 and #22405 with one search method. The deferred methods can be written on top of it in Ruby, and the last section gives the measurements on PicoRuby that Matz asked for. The region form of `bit_get`, which replaces the Integer fold of `bits`, is proposed separately in #XXXXX.
### What this adds
```
String#bit_index(bit, offset = 0, lsb_first: true) -> Integer | nil
String#bit_index(bit, offset, length, lsb_first: true) -> Integer | nil
String#bit_index(bit, range, lsb_first: true) -> Integer | nil
```
`bit_index` returns the offset of the first bit at or after `offset` that is equal to `bit`, or `nil`. The `bit` argument is `0`, `1`, `true` or `false`. A byte that holds no matching bit is skipped in one step. A `length` or a `range` limits the search to a window, with the region arguments of #22279.
```ruby
data = "\xF0\xAA".b
data.bit_index(1) # => 4
data.bit_index(0, 4) # => 8
data.bit_index(1, lsb_first: false) # => 0
data.bit_index(1, 0...4) # => nil
"\x00".b.bit_index(1) # => nil
```
### The deferred methods, written on top
`bit_offsets`, `bit_runs` and `bit_run_length` can be written on top of a search method in a few lines. This is the case.
```ruby
def bit_offsets(s, bit)
offsets = []
i = -1
offsets << i while (i = s.bit_index(bit, i + 1))
offsets
end
def bit_run_length(s, bit, offset)
current = s.bit_get(offset)
return nil if current.nil?
return 0 if current != bit
(s.bit_index(1 - bit, offset) || s.bytesize * 8) - offset
end
def each_bit_run(s)
i = 0
size = s.bytesize * 8
while i < size
bit = s.bit_get(i)
j = s.bit_index(1 - bit, i) || size
yield bit, i, j - i
i = j
end
end
```
`each_bit` and `bits` are replaced by a `bit_get` loop. Where the examples in #22399 folded the Array into an Integer, the region form of `bit_get` (#XXXXX) reads the Integer directly.
### Use cases
- **Null positions in columnar data (LSB-first).** An Apache Arrow validity bitmap marks the null elements. An Arrow array is a slice over a shared bitmap, so the window is the slice, and the padding bits are never read.
```ruby
validity = "\xFD\x03".b # 10 elements, element 1 is null, bits 10..15 are padding
nulls = []
pos = 0
while (i = validity.bit_index(0, pos...10))
nulls << i
pos = i + 1
end
nulls # => [1]
```
- **Block allocators.** A first-fit allocation for `n` blocks is the first run of cleared bits with a sufficient length. The loop allocates nothing.
```ruby
bitmap = "\xFF\x0F\xC0\x00".b # 32 blocks, 1 = in use
def first_fit(bitmap, n)
size = bitmap.bytesize * 8
i = 0
while (i = bitmap.bit_index(0, i))
j = bitmap.bit_index(1, i) || size
return i if j - i >= n
i = j
end
nil
end
first_fit(bitmap, 8) # => 12
first_fit(bitmap, 20) # => nil
```
- **Variable-length codes (MSB-first).** A Rice code stores a value as a unary run of set bits, a cleared bit, and `k` remainder bits. `bit_index(0, pos, lsb_first: false)` finds the end of the run, and the region form of `bit_get` reads the remainder.
```ruby
def read_rice(bs, pos, k)
stop = bs.bit_index(0, pos, lsb_first: false) # the cleared bit after the run
q = stop - pos
r = bs.bit_get(stop + 1, k, lsb_first: false)
[(q << k) | r, stop + 1 + k]
end
bs = "\x79\x14".b # 0111 1001 0001 0100
pos = 0
values = []
4.times do
value, pos = read_rice(bs, pos, 2)
values << value
end
values # => [3, 9, 0, 6]
```
- **Changed spans of an e-paper frame** are the runs of set bits in `old_row.bitwise_xor(new_row)`, found by the loop of `each_bit_run` above. **A pending interrupt** or **a free block** is found with one call and handled, with no loop at all.
### API Contracts
1. **Arguments** follow #22118 and #22279. A negative `offset` raises `IndexError`. A negative `length` raises `ArgumentError`. A position or length beyond `2**64 - 1` raises `ArgumentError`. The `lsb_first` value must be `true` or `false`. A Range with a `length` raises `ArgumentError`, as in `bit_count`.
2. **The `bit` argument** accepts `0`, `1`, `true` or `false`. Any other object is converted with `to_int`, as for an index. An Integer other than `0` or `1` raises `ArgumentError`.
3. **The result is an absolute offset** in the numbering that `lsb_first:` selects, so `s.bit_set?(i, lsb_first: x)` is true for `i = s.bit_index(1, lsb_first: x)`. An `offset` at or beyond the end returns `nil`, like `bit_get`.
4. **A window clamps.** A `length` or a `range` is a window with the region rules of `bit_count`: a window that extends past the end is clamped to the end of the string, as the search of `String#index` is. A window with no matching bit returns `nil`, and so does an empty window.
5. **Frozen receivers** work. **Encoding** has no effect. The method treats the receiver as a byte sequence, as in #22118.
### Scope: no iterator in this ticket
`bit_index` follows the cursor idiom of `String#index`. The idiom has a known cost: a scan of single bits in dense data runs the loop body once per matching bit in Ruby, and the method call bounds the loop. The measurements below show this. On CRuby the loop is 4 times slower than the `bit_offsets` of #22399 on a dense buffer, and on the Pico 2 W a run of 1 bit gives the search nothing to skip, so the loop is a little slower than a `bit_get` loop there.
This ticket targets the sparse and the run cases, which Matz named, and accepts the dense scan. I measured C iterator prototypes with a block (`each_bit_index`, `each_bit_run`): a block call costs about as much as a method call, so they gain 1.0 to 1.6 times on CRuby and 2 to 3 times on the Pico. If an iterator is wanted later, the use cases point to `each_bit_run {|bit, offset, length| }`, with the window forms of `bit_index`, and it can be added on top of the same C search. `bit_run_length(bit, offset)` was considered as the primitive instead of `bit_index`: the two carry the same information, but `bit_index` is the idiom of `String#index` and the one that `each_bit_run` would build on.
### Performance on CRuby
Each time is the median of 5 calls. 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
sparse = "\x00".b * (1 << 20) # 1 MiB, 1,000 set bits
1000.times { sparse.bit_set(it * 8388) }
dense = "\xAA".b * (1 << 20) # 1 MiB, every other bit set
runs = "".b # 1 MiB, 1,024 runs of 8,192 bits
1024.times { |i| runs << ((i.even? ? "\x00" : "\xFF").b * 1024) }
N = 1 << 23
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
# bit_offsets on top of bit_index, against the alternatives of #22399
def offsets_by_loop(s) = (0...N).select { s.bit_set?(it) }
def offsets_by_unpack(s)
b = s.unpack1("b*")
offsets = []
i = -1
offsets << i while (i = b.index("1", i + 1))
offsets
end
def offsets_by_bit_index(s)
offsets = []
i = -1
offsets << i while (i = s.bit_index(1, i + 1))
offsets
end
# bit_run_length and bit_runs on top of bit_index
def run_length_by_loop(s, offset)
bit = s.bit_get(offset)
i = offset + 1
i += 1 while i < N && s.bit_get(i) == bit
i - offset
end
def run_length_by_bit_index(s, offset)
bit = s.bit_get(offset)
(s.bit_index(1 - bit, offset) || N) - offset
end
def runs_by_loop(s)
result = []
i = 0
while i < N
bit = s.bit_get(i)
j = i + 1
j += 1 while j < N && s.bit_get(j) == bit
result << [bit, j - i]
i = j
end
result
end
def runs_by_bit_index(s)
result = []
i = 0
while i < N
bit = s.bit_get(i)
j = s.bit_index(1 - bit, i) || N
result << [bit, j - i]
i = j
end
result
end
def count_runs_by_loop(s)
count = 0
i = 0
while i < N
bit = s.bit_get(i)
i += 1
i += 1 while i < N && s.bit_get(i) == bit
count += 1
end
count
end
def count_runs_by_bit_index(s)
count = 0
i = 0
while i < N
bit = s.bit_get(i)
i = s.bit_index(1 - bit, i) || N
count += 1
end
count
end
{ sparse:, dense: }.each do |name, s|
raise unless offsets_by_loop(s) == offsets_by_bit_index(s) && offsets_by_unpack(s) == offsets_by_bit_index(s)
printf "%-6s offsets loop %.4f\n", name, median { offsets_by_loop(s) }
printf "%-6s offsets unpack %.4f\n", name, median { offsets_by_unpack(s) }
printf "%-6s offsets bit_index %.4f\n", name, median { offsets_by_bit_index(s) }
end
printf "run_length loop %.4f\n", median { 1000.times { run_length_by_loop(runs, 0) } }
printf "run_length bit_index %.4f\n", median { 1000.times { run_length_by_bit_index(runs, 0) } }
raise unless runs_by_loop(runs) == runs_by_bit_index(runs)
printf "runs loop %.4f\n", median { runs_by_loop(runs) }
printf "runs bit_index %.4f\n", median { runs_by_bit_index(runs) }
raise unless count_runs_by_loop(dense) == N && count_runs_by_bit_index(dense) == N
printf "short runs loop %.4f\n", median { runs_by_loop(dense) }
printf "short runs bit_index %.4f\n", median { runs_by_bit_index(dense) }
printf "short runs loop, count %.4f\n", median { count_runs_by_loop(dense) }
printf "short runs bit_index, count %.4f\n", median { count_runs_by_bit_index(dense) }
```
}}
**Offsets of the set bits of 1 MiB** (`bit_offsets` written on top of `bit_index`):
| | Sparse | Dense |
|------------------------------------------------------------|--------:|-------:|
| `bit_set?` loop | 461 ms | 493 ms |
| `unpack1("b*")` + `index` | 8.9 ms | 351 ms |
| `bit_index` loop | 0.7 ms | 176 ms |
| `bit_offsets` in C, no block (#22399 patch, for reference) | 1.2 ms | 41 ms |
For sparse data, the Ruby loop over `bit_index` is as fast as the C method of #22399. For dense data, the method call per bit bounds the loop, and the C method is 4 times faster. The loop is still faster than `unpack`.
**Runs of 1 MiB with 1,024 runs** (`bit_run_length` and `bit_runs` written on top of `bit_index`):
| | `bit_get` loop | `bit_index` |
|-------------------------------|---------------:|------------:|
| `bit_run_length(1, 0)` x1,000 | 358 ms | 1.0 ms |
| all 1,024 runs | 293 ms | 1.0 ms |
For long runs, `bit_index` gives the same speed as the C methods of #22405 (1.1 ms for the same buffer shape).
**Short runs of 1 MiB with 8 Mi runs of 1 bit** (the dense buffer). This is the data of the memory concern of Matz about `bit_runs`: one Array per run. The first row builds that Array, the second row only counts the runs.
| | `bit_get` loop | `bit_index` loop | C method of #22405, no block (for reference) |
|-----------------------------|---------------:|-----------------:|---------------------------------------------:|
| all runs, one Array per run | 1,224 ms | 942 ms | 256 ms (`bit_runs`) |
| all runs, count only | 646 ms | 543 ms | 25.5 ms (`each_bit_run.size`) |
For short runs, `bit_index` gives no gain over `bit_get`: two method calls per run bound the loop. The Array per run costs about 400 to 600 ms in Ruby and 230 ms in C.
### Performance on PicoRuby
I ported `bit_index` to the mruby VM of PicoRuby (`mruby-string-bitops`, which already has the methods of #22118 and #22279) and ran the same comparisons on a board.
- Board: Raspberry Pi Pico 2 W (RP2350, Cortex-M33 at 150 MHz)
- Firmware: R2P2 4.0.6, PicoRuby master at a90afd12 plus this patch, mruby VM, `MRB_INT64`, release build
- Buffers: 8 KiB (65,536 bits), so that every variant fits in RAM. Each time is the median of 5 runs, measured with `Machine.uptime_us`.
{{collapse(Benchmark script for PicoRuby)
```ruby
# bitbench - benchmark String#bit_index
require 'benchmark'
SIZE = 8 * 1024
BITS = SIZE * 8
REPEAT = 5
sparse = "\x00" * SIZE # 64 set bits
i = 0
while i < 64
sparse.bit_set(i * 1024 + 3)
i += 1
end
dense = "\xAA" * SIZE # every other bit set
runs = "" # 8 runs of 8,192 bits
i = 0
while i < 8
runs << ((i % 2 == 0) ? "\x00" : "\xFF") * 1024
i += 1
end
def offsets_by_loop(s)
sum = 0
i = 0
while i < BITS
sum += i if s.bit_set?(i)
i += 1
end
sum
end
def offsets_by_bit_index(s)
sum = 0
i = -1
while (i = s.bit_index(1, i + 1))
sum += i
end
sum
end
def run_length_by_loop(s, offset)
bit = s.bit_get(offset)
i = offset + 1
i += 1 while i < BITS && s.bit_get(i) == bit
i - offset
end
def run_length_by_bit_index(s, offset)
bit = s.bit_get(offset)
(s.bit_index(1 - bit, offset) || BITS) - offset
end
def runs_by_loop(s)
count = 0
i = 0
while i < BITS
bit = s.bit_get(i)
j = i + 1
j += 1 while j < BITS && s.bit_get(j) == bit
count += 1
i = j
end
count
end
def runs_by_bit_index(s)
count = 0
i = 0
while i < BITS
bit = s.bit_get(i)
j = s.bit_index(1 - bit, i) || BITS
count += 1
i = j
end
count
end
puts "== offsets of the set bits (bit_offsets equivalent) =="
Benchmark.bm(28, repeat: REPEAT) do |x|
x.report("sparse: bit_set? loop") { offsets_by_loop(sparse) }
x.report("sparse: bit_index loop") { offsets_by_bit_index(sparse) }
x.report("dense: bit_set? loop") { offsets_by_loop(dense) }
x.report("dense: bit_index loop") { offsets_by_bit_index(dense) }
end
puts "== run length at offset 0 (bit_run_length equivalent, x10) =="
Benchmark.bm(28, repeat: REPEAT) do |x|
x.report("bit_get loop") { i = 0; while i < 10; run_length_by_loop(runs, 0); i += 1; end }
x.report("bit_index") { i = 0; while i < 10; run_length_by_bit_index(runs, 0); i += 1; end }
end
puts "== all 8 runs (bit_runs equivalent) =="
Benchmark.bm(28, repeat: REPEAT) do |x|
x.report("bit_get loop") { runs_by_loop(runs) }
x.report("bit_index loop") { runs_by_bit_index(runs) }
end
puts "== all #{BITS} runs of 1 bit (bit_runs equivalent, short runs) =="
Benchmark.bm(28, repeat: REPEAT) do |x|
x.report("bit_get loop") { runs_by_loop(dense) }
x.report("bit_index loop") { runs_by_bit_index(dense) }
end
```
}}
**Offsets of the set bits of 8 KiB** (`bit_offsets` written on top of `bit_index`):
| | Sparse | Dense |
|------------------|---------:|---------:|
| `bit_set?` loop | 2,172 ms | 2,222 ms |
| `bit_index` loop | 4.2 ms | 1,195 ms |
**Runs of 8 KiB with 8 runs** (`bit_run_length` and `bit_runs` written on top of `bit_index`):
| | `bit_get` loop | `bit_index` |
|----------------------------|---------------:|------------:|
| `bit_run_length(1, 0)` x10 | 2,841 ms | 3.2 ms |
| all 8 runs | 2,268 ms | 2.6 ms |
**Short runs of 8 KiB with 65,536 runs of 1 bit** (the dense buffer; the rows count the runs and make no Array):
| | `bit_get` loop | `bit_index` loop |
|-----------------|---------------:|-----------------:|
| all 65,536 runs | 4,387 ms | 4,647 ms |
For short runs, the `bit_index` loop is a little slower than the `bit_get` loop on the microcontroller. A run of one bit gives the search in C nothing to skip, and a `bit_index` call costs a little more than the `bit_get` call it replaces.
The ratios are the same as on CRuby, but the absolute times matter more here. A `bit_set?` loop over 8 KiB takes 2.2 seconds on the microcontroller. The `bit_index` loop takes 4.2 ms for sparse data, which is the difference between a usable and an unusable bitmap scan. None of the variants allocates per element, so the heap in use did not change beyond GC noise (within 8 KiB) during any row.
--
https://bugs.ruby-lang.org/
2
3
[ruby-dev:52243] [Ruby Feature#22279] Region (Length / Range) Arguments for String Bit Operations
by hasumikin (hitoshi hasumi) 14 Nov '26
by hasumikin (hitoshi hasumi) 14 Nov '26
14 Nov '26
Issue #22279 has been reported by hasumikin (hitoshi hasumi).
----------------------------------------
Feature #22279: Region (Length / Range) Arguments for String Bit Operations
https://bugs.ruby-lang.org/issues/22279
* Author: hasumikin (hitoshi hasumi)
* Status: Open
----------------------------------------
PR URL:
## What this adds
Region overloads for the methods introduced in #22118, so they act on a contiguous run of bits in a single call:
```
String#bit_set(offset, length, lsb_first: true) -> self
String#bit_set(range, lsb_first: true) -> self
String#bit_clear(offset, length, lsb_first: true) -> self
String#bit_clear(range, lsb_first: true) -> self
String#bit_flip(offset, length, lsb_first: true) -> self
String#bit_flip(range, lsb_first: true) -> self
String#bit_count(offset, length, lsb_first: true) -> Integer
String#bit_count(range, lsb_first: true) -> Integer
```
Existing single-offset forms and the no-argument `bit_count` are unchanged.
## Use cases
Apache Arrow stores validity masks and boolean columns as LSB-first packed bitmaps (the same layout as Ruby's default `lsb_first: true`) and touches them a range at a time.
**Writing a buffer:** mark a contiguous run of elements valid or null in one call (the equivalent of Arrow C++'s `bit_util::SetBitsTo`), or invert a boolean column:
```ruby
validity.bit_set(start, run) # mark [start, start+run) valid
validity.bit_clear(start, run) # mark them null
column.bit_flip(0...n_elements) # boolean NOT
```
**Reading a buffer:** `null_count` is `length - bit_count`, a rank query over the mask. An Arrow array is an O(1) slice with an arbitrary bit offset, so a slice's `null_count` counts a range that starts and ends mid-byte:
```ruby
null_count = slice_length - validity.bit_count(slice_offset, slice_length)
```
## API Contracts
- `(offset, length)` and a Range are equivalent; passing both is an `ArgumentError`. The positional form follows `String#[](start, length)`.
- Endless / beginless ranges work as usual (`0..` = to the last bit). An empty region (`length == 0`, or an empty Range) is a no-op for the mutations and `0` for `bit_count`. For the mutations, even an empty region must begin within `0..bit_size`: `"\x00".bit_set(9, 0)` and `"\x00".bit_set(9...9)` both raise `IndexError`, mirroring how `"abc"[4, 0]` is `nil` while `"abc"[3, 0]` is `""`.
- Mutations require the whole region to be in range and raise `IndexError` on overrun without modifying any bits; `bit_count` clamps to the bits that exist: the same read/write split as #22118.
- `bit_count` returns `0` (not `nil`) for a region that lies entirely beyond the end. It is an aggregate, not a slice or a single-position lookup: the "reads return nil" rule of #22118 exists because `bit_get` has no in-domain value for "no such bit", whereas the count of set bits in an empty intersection is legitimately `0`, and the result is meant to feed arithmetic (`length - bit_count(...)`). This also keeps one rule for clamping: whatever part of the region exists is counted, and an empty part counts as `0`.
- Mutations raise `FrozenError` on a frozen receiver even for an empty region, following `[].freeze.push` and `"".freeze.concat`. An out-of-range region is still detected first (`IndexError`), as in `String#setbyte`.
- Negative offsets and Range endpoints raise `IndexError`, with no count-from-end normalization, as in #22118. A negative `length` raises `ArgumentError`, following the decision in #22881.
- An inverted Range (`5..2`) is treated as empty, like `"abcd"[2..0]` returning `""`.
- Bit positions beyond `2**64 - 1` raise `ArgumentError` even for the clamping `bit_count` (the representable-range rule of #22118 applies before clamping).
- A lone `offset` keeps its #22118 single-bit meaning, so it is valid only for the mutations (`bit_set(offset)` etc.). `bit_count` has no single-bit form: it takes no argument (whole string), `(offset, length)`, or a Range, and `bit_count(offset)` raises `ArgumentError`. A one-bit count would return the same 0/1 as `bit_get(offset)`, and reading it as "from `offset` to the end" would contradict `String#[](index)`; counting to the end is spelled `bit_count(offset..)`.
- An explicit `nil` is an argument, not an omission: `bit_set(0, nil)` and `bit_count(0, nil)` raise `TypeError`, as `"abc"[0, nil]` does.
- `lsb_first` only changes the bit-to-position mapping within a byte.
## Performance
A region call lets the implementation use `memset` / byte-wide `popcount` instead of a Ruby-level per-bit loop. On an AMD Ryzen 5 5600X (x86_64-linux, gcc, `--zjit`), with `buf = "\x00".b * 2**20` (1 MiB), setting 8,388,600 bits at an unaligned offset:
```ruby
buf.bit_set(4, 8388600) # 15 us
8388600.times { buf.bit_set(4 + it) } # 440 ms (~29,000x slower)
```
Most of that gap is the per-call overhead of 8 million Ruby method calls rather than the per-byte work; the point is that a region call removes the loop entirely, not that the single-bit form is slow.
For `bit_count` the point is addressing rather than raw speed: with `data = Random.bytes(4096)`, a region such as `data.bit_count(12347, 1000)` cannot be expressed with `byteslice` at all, because it starts and ends mid-byte. Even for a byte-aligned region the region form avoids the intermediate String: `data.bit_count(12344, 1008)` 90 ns vs `data.byteslice(1543, 126).bit_count` 130 ns.
--
https://bugs.ruby-lang.org/
3
3
[ruby-dev:52251] [Ruby Bug#22483] Region forms of String#bit_get
by hasumikin (hitoshi hasumi) 13 Nov '26
by hasumikin (hitoshi hasumi) 13 Nov '26
13 Nov '26
Issue #22483 has been reported by hasumikin (hitoshi hasumi).
----------------------------------------
Bug #22483: Region forms of String#bit_get
https://bugs.ruby-lang.org/issues/22483
* Author: hasumikin (hitoshi hasumi)
* Status: Open
* Backport: 3.3: UNKNOWN, 3.4: UNKNOWN, 4.0: UNKNOWN
----------------------------------------
Impl: (WIP)
This ticket completes the region arguments of #22279 for `bit_get`. #22279 added the `(offset, length)` and `range` forms to `bit_set`, `bit_clear`, `bit_flip` and `bit_count`, and the commit message of #22118 announced the same extension for `bit_get`. It is also the second half of my reply to the comment of Matz in #22399#note-3: where the examples of #22399 folded the Array of `bits` into an Integer, the region form of `bit_get` reads the Integer directly. The search method is proposed separately in #22482.
### What this adds
```
String#bit_get(offset, length, lsb_first: true) -> Integer | nil
String#bit_get(range, lsb_first: true) -> Integer | nil
```
`bit_get` with a `length` or a `range` reads a bit region as a non-negative Integer, as `Integer#[](i, len)` and `Integer#[](range)` do for the bits of an Integer. The existing one-bit form is the case `length = 1`.
```ruby
data = "\xF0\xAA".b
data.bit_get(4) # => 1
data.bit_get(0, 8) # => 0xF0
data.bit_get(4, 8) # => 0xAF
data.bit_get(8..) # => 0xAA
data.bit_get(0, 16) # => 0xAAF0
hdr = "\x12\x34\x81\x80".b # a DNS header
hdr.bit_get(16, 16, lsb_first: false) # => 0x8180
hdr.bit_get(4, 12, lsb_first: false) # => 0x234
```
### Use cases
- **Protocol headers (MSB-first).** RFC diagrams number bits MSB-first and give each field a width. `bit_get(offset, width, lsb_first: false)` reads a field by the coordinates of the diagram, without a bit reversal and without an Array.
```ruby
hdr = "\x12\x34\x81\x80".b # DNS header: ID, then the 16 flag bits
id = hdr.bit_get(0, 16, lsb_first: false) # => 0x1234
qr = hdr.bit_get(16, lsb_first: false) # => 1
opcode = hdr.bit_get(17, 4, lsb_first: false) # => 0
rcode = hdr.bit_get(28, 4, lsb_first: false) # => 0
```
- **Non-aligned sensor frames on a microcontroller.** A telemetry format packs 12 + 10 + 14 bits into a 36-bit frame, so every second frame starts in the middle of a byte. With `getbyte` the decoder needs two code paths, one per alignment. With `bit_get` it needs one.
```ruby
frames.times do |i|
off = i * 36
temp = data.bit_get(off, 12)
hum = data.bit_get(off + 12, 10)
co2 = data.bit_get(off + 22, 14)
process(temp, hum, co2)
end
```
- **Hardware registers.** A device register packs several fields into one or two bytes. `bit_get(5, 3)` reads a 3-bit mode field as the datasheet writes it.
- **Variable-length codes.** A Rice or Golomb decoder reads the `k` remainder bits after a unary run with `bit_get(pos, k, lsb_first: false)`. With the search method of #22482, the decoder is two calls per value.
### API Contracts
1. **Arguments** follow #22118 and #22279. A negative `offset` raises `IndexError`. A negative `length` raises `ArgumentError`. A position or length beyond `2**64 - 1` raises `ArgumentError`. The `lsb_first` value must be `true` or `false`. A Range with a `length` raises `ArgumentError`, as in `bit_count`.
2. **The region form does not clamp.** `bit_count` clamps a region that extends past the end, because a smaller count is still correct. A truncated value would be wrong, so `bit_get` returns `nil` instead, as the one-bit form does beyond the end and as `unpack1` does on short data. The `nil` has one meaning, so a parser of a truncated packet can test it without a `rescue`. An empty region returns `0`, unless it begins beyond the end: `bit_get(16, 0)` on a 2-byte string returns `0`, and `bit_get(17, 0)` returns `nil`, as `bit_get(17)` does.
3. **The result has no width limit.** A region wider than 64 bits returns a Bignum. In mruby, a build without `mruby-bigint` raises `RangeError` for a region wider than its Integer.
4. **`lsb_first` changes the bit numbering and the significance.** The byte order never changes. With `lsb_first: true`, the first bit of the region is the least significant bit of the result, as in `Integer#[](i, len)`. With `lsb_first: false`, the first bit of the region is the most significant bit of the result, which is the value that an RFC diagram shows for the field.
5. **Frozen receivers** work. **Encoding** has no effect. The method treats the receiver as a byte sequence, as in #22118.
### Why a region form of `bit_get`, not a new method
- `Integer#[]` sets the precedent: `Integer#[](i)` returns one bit, and `Integer#[](i, len)` and `Integer#[](range)` return a bit region as an Integer. The region form of `bit_get` is the same extension for the bits of a String, with the same significance of the first bit under `lsb_first: true`.
- #22279 added the same forms to the other bit methods, and the commit message of #22118 announced it for `bit_get`. This ticket completes it, and `bit_get` stays in line with the other bit methods.
- The `nil` rule carries over without a new rule: a read past the end returns `nil`, whether it is one bit or a region.
- No new name is needed.
A write side of the region form is not part of this ticket, because the use cases above only read. Note that `bit_set(offset, length)` already means "set all bits of the region", so a write of an Integer value into a region would need a name of its own, such as `bit_put(offset, length, value)`.
### Performance on CRuby
Each time is the median of 5 calls. 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
dense = "\xAA".b * (1 << 20) # 1 MiB
N = 1 << 23
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
# the region form of bit_get against a one-bit bit_get fold and against unpack
def field_by_fold(s, off, len, lsb_first)
v = 0
len.times do |i|
bit = s.bit_get(off + i, lsb_first: lsb_first)
v |= bit << (lsb_first ? i : len - 1 - i)
end
v
end
def field_by_unpack(s, off, len, lsb_first)
s.unpack1(lsb_first ? "b*" : "B*")[off, len].send(lsb_first ? :reverse : :itself).to_i(2)
end
def frames_by_fold(s, n)
sum = 0
n.times do |i|
off = i * 36
sum += field_by_fold(s, off, 12, true) + field_by_fold(s, off + 12, 10, true) + field_by_fold(s, off + 22, 14, true)
end
sum
end
def frames_by_getbyte(s, n)
sum = 0
n.times do |i|
b = i * 36 >> 3
if i.even?
temp = s.getbyte(b) | ((s.getbyte(b+1) & 0x0F) << 8)
hum = (s.getbyte(b+1) >> 4) | ((s.getbyte(b+2) & 0x3F) << 4)
co2 = (s.getbyte(b+2) >> 6) | (s.getbyte(b+3) << 2) | ((s.getbyte(b+4) & 0x0F) << 10)
else
temp = (s.getbyte(b) >> 4) | (s.getbyte(b+1) << 4)
hum = s.getbyte(b+2) | ((s.getbyte(b+3) & 0x03) << 8)
co2 = (s.getbyte(b+3) >> 2) | (s.getbyte(b+4) << 6)
end
sum += temp + hum + co2
end
sum
end
def frames_by_bit_get(s, n)
sum = 0
n.times do |i|
off = i * 36
sum += s.bit_get(off, 12) + s.bit_get(off + 12, 10) + s.bit_get(off + 22, 14)
end
sum
end
hdr = "\x12\x34\x81\x80".b
[true, false].each do |order|
raise unless hdr.bit_get(4, 16, lsb_first: order) == field_by_fold(hdr, 4, 16, order)
raise unless hdr.bit_get(4, 16, lsb_first: order) == field_by_unpack(hdr, 4, 16, order)
printf "field %-5s fold %.4f\n", order, median { 100_000.times { field_by_fold(hdr, 4, 16, order) } }
printf "field %-5s unpack %.4f\n", order, median { 100_000.times { field_by_unpack(hdr, 4, 16, order) } }
printf "field %-5s bit_get %.4f\n", order, median { 100_000.times { hdr.bit_get(4, 16, lsb_first: order) } }
end
frames = N / 36
raise unless frames_by_fold(dense, frames) == frames_by_bit_get(dense, frames)
raise unless frames_by_getbyte(dense, frames) == frames_by_bit_get(dense, frames)
printf "frames fold %.4f\n", median { frames_by_fold(dense, frames) }
printf "frames getbyte %.4f\n", median { frames_by_getbyte(dense, frames) }
printf "frames bit_get %.4f\n", median { frames_by_bit_get(dense, frames) }
```
}}
| | `bit_get` fold | `unpack1` + `to_i(2)` | `getbyte` + masks | `bit_get(offset, length)` |
|-----------------------------------------|---------------:|----------------------:|------------------:|--------------------------:|
| 16-bit field at offset 4, x100,000 | 234 ms | 35 ms | - | 16 ms |
| same, `lsb_first: false` | 297 ms | 28 ms | - | 13 ms |
| 233,016 frames of 12 + 10 + 14 bits | 1,219 ms | - | 54 ms | 30 ms |
The region form of `bit_get` is faster than hand-written `getbyte` masks and needs no alignment branch.
### Performance on PicoRuby
I ported the region form to the mruby VM of PicoRuby (`mruby-string-bitops`, which already has the methods of #22118 and #22279) and ran the same comparisons on a board.
- Board: Raspberry Pi Pico 2 W (RP2350, Cortex-M33 at 150 MHz)
- Firmware: R2P2 4.0.6, PicoRuby master at a90afd12 plus this patch, mruby VM, `MRB_INT64`, release build
- Buffer: 8 KiB (65,536 bits), so that every variant fits in RAM. Each time is the median of 5 runs, measured with `Machine.uptime_us`.
{{collapse(Benchmark script for PicoRuby)
```ruby
# bitbench - benchmark the region form of String#bit_get
require 'benchmark'
SIZE = 8 * 1024
BITS = SIZE * 8
REPEAT = 5
dense = "\xAA" * SIZE
def field_by_fold(s, off, len, lsb_first)
v = 0
i = 0
while i < len
bit = s.bit_get(off + i, lsb_first: lsb_first)
v |= bit << (lsb_first ? i : len - 1 - i)
i += 1
end
v
end
def frames_by_fold(s, n)
sum = 0
i = 0
while i < n
off = i * 36
sum += field_by_fold(s, off, 12, true) + field_by_fold(s, off + 12, 10, true) + field_by_fold(s, off + 22, 14, true)
i += 1
end
sum
end
def frames_by_getbyte(s, n)
sum = 0
i = 0
while i < n
b = i * 36 >> 3
if i % 2 == 0
temp = s.getbyte(b) | ((s.getbyte(b+1) & 0x0F) << 8)
hum = (s.getbyte(b+1) >> 4) | ((s.getbyte(b+2) & 0x3F) << 4)
co2 = (s.getbyte(b+2) >> 6) | (s.getbyte(b+3) << 2) | ((s.getbyte(b+4) & 0x0F) << 10)
else
temp = (s.getbyte(b) >> 4) | (s.getbyte(b+1) << 4)
hum = s.getbyte(b+2) | ((s.getbyte(b+3) & 0x03) << 8)
co2 = (s.getbyte(b+3) >> 2) | (s.getbyte(b+4) << 6)
end
sum += temp + hum + co2
i += 1
end
sum
end
def frames_by_bit_get(s, n)
sum = 0
i = 0
while i < n
off = i * 36
sum += s.bit_get(off, 12) + s.bit_get(off + 12, 10) + s.bit_get(off + 22, 14)
i += 1
end
sum
end
puts "== one 16-bit field at bit offset 4 of a 4-byte header (x1000) =="
hdr = "\x12\x34\x81\x80"
[true, false].each do |order|
label = order ? "lsb_first" : "msb_first"
Benchmark.bm(28, repeat: REPEAT) do |x|
x.report("#{label}: bit_get fold") { i = 0; while i < 1000; field_by_fold(hdr, 4, 16, order); i += 1; end }
x.report("#{label}: bit_get region") { i = 0; while i < 1000; hdr.bit_get(4, 16, lsb_first: order); i += 1; end }
end
end
frames = BITS / 36
puts "== unaligned 12/10/14-bit sensor frames (#{frames} frames) =="
Benchmark.bm(28, repeat: REPEAT) do |x|
x.report("bit_get fold loop") { frames_by_fold(dense, frames) }
x.report("getbyte with masks") { frames_by_getbyte(dense, frames) }
x.report("bit_get region") { frames_by_bit_get(dense, frames) }
end
```
}}
| | `bit_get` fold | `getbyte` + masks | `bit_get(offset, length)` |
|-----------------------------------|---------------:|------------------:|--------------------------:|
| 16-bit field at offset 4, x1,000 | 2,445 ms | - | 166 ms |
| same, `lsb_first: false` | 2,682 ms | - | 160 ms |
| 1,820 frames of 12 + 10 + 14 bits | 10,130 ms | 555 ms | 213 ms |
The ratios are the same as on CRuby, but the absolute times matter more here. The region form of `bit_get` is 2.6 times faster than hand-written `getbyte` masks and 48 times faster than a one-bit `bit_get` fold. None of the variants allocates per element, so the heap in use did not change beyond GC noise (within 8 KiB) during any row.
--
https://bugs.ruby-lang.org/
3
5
[ruby-dev:52175] [Ruby Bug#21663] IO#pos will corrupt the file position in specific situation.
by t_nagaya (Tsutomu Nagaya) 09 Nov '26
by t_nagaya (Tsutomu Nagaya) 09 Nov '26
09 Nov '26
Issue #21663 has been reported by t_nagaya (Tsutomu Nagaya).
----------------------------------------
Bug #21663: IO#pos will corrupt the file position in specific situation.
https://bugs.ruby-lang.org/issues/21663
* Author: t_nagaya (Tsutomu Nagaya)
* Status: Open
* ruby -v: ruby 3.2.3 (2024-01-18 revision 52bb2ac0a6) [x64-mingw-ucrt]
* Backport: 3.2: UNKNOWN, 3.3: UNKNOWN, 3.4: UNKNOWN
----------------------------------------
`IO#pos` and `IO#tell` will corrupt the file position in the following situation.
### Situation:
- Running on Windows. (`RUBY_CRLF_ENVIRONMENT` is defined.)
- The filesize is over 0x100000000 bytes.
- The file is opened in text mode.
- There are several `CRLF`s written around 0x100000000.
- Some read operations to fill internal buffer (`rbuf`) has been performed.
- The real file position (associated with the file descriptor) is somewhat greater than 0x100000000.
### Code to reproduce:
```ruby
file = "./test_file"
# Prepare a test file
f = File.open(file, "wb:binary")
f.truncate(0x100000000)
f.pos = f.size - 13
f.puts("0123456789\r\n9876543210\r\n" * 10)
f.close
# Operations to reproduce
f = File.open(file, "r:utf-8")
f.seek(0x100000000 - 13)
puts "%#x" % f.pos
p f.gets
puts "%#x" % f.pos
p f.gets
puts "%#x" % f.pos
f.close
```
### Actual result:
```
0xfffffff3
"0123456789\n"
0x100000012
"789\n"
0x100000017
```
### Expected result:
```
0xfffffff3
"0123456789\n"
0xffffffff
"9876543210\n"
0x10000000b
```
### Notes:
Currently, io.c has the following code.
In the above situation, `extra_max` may be set to 0 or a small integer value by casting it as the type `long` (assumed 4 bytes).
So `newlines` is set lower than the actual count, the file does not seek back correctly.
```c
/*
* IO unread with taking care of removed '\r' in text mode.
*/
static void
io_unread(rb_io_t *fptr, bool discard_rbuf)
{
rb_off_t r, pos;
ssize_t read_size;
long i;
long newlines = 0;
long extra_max;
char *p;
char *buf;
rb_io_check_closed(fptr);
if (fptr->rbuf.len == 0 || fptr->mode & FMODE_DUPLEX) {
return;
}
errno = 0;
if (!rb_w32_fd_is_text(fptr->fd)) {
r = lseek(fptr->fd, -fptr->rbuf.len, SEEK_CUR);
if (r < 0 && errno) {
if (errno == ESPIPE)
fptr->mode |= FMODE_DUPLEX;
if (!discard_rbuf) return;
}
goto end;
}
pos = lseek(fptr->fd, 0, SEEK_CUR);
if (pos < 0 && errno) {
if (errno == ESPIPE)
fptr->mode |= FMODE_DUPLEX;
if (!discard_rbuf) goto end;
}
/* add extra offset for removed '\r' in rbuf */
extra_max = (long)(pos - fptr->rbuf.len);
p = fptr->rbuf.ptr + fptr->rbuf.off;
/* if the end of rbuf is '\r', rbuf doesn't have '\r' within rbuf.len */
if (*(fptr->rbuf.ptr + fptr->rbuf.capa - 1) == '\r') {
newlines++;
}
for (i = 0; i < fptr->rbuf.len; i++) {
if (*p == '\n') newlines++;
if (extra_max == newlines) break;
p++;
}
buf = ALLOC_N(char, fptr->rbuf.len + newlines);
while (newlines >= 0) {
r = lseek(fptr->fd, pos - fptr->rbuf.len - newlines, SEEK_SET);
if (newlines == 0) break;
if (r < 0) {
newlines--;
continue;
}
read_size = _read(fptr->fd, buf, fptr->rbuf.len + newlines);
if (read_size < 0) {
int e = errno;
free(buf);
rb_syserr_fail_path(e, fptr->pathv);
}
if (read_size == fptr->rbuf.len) {
lseek(fptr->fd, r, SEEK_SET);
break;
}
else {
newlines--;
}
}
free(buf);
end:
fptr->rbuf.off = 0;
fptr->rbuf.len = 0;
clear_codeconv(fptr);
return;
}
```
--
https://bugs.ruby-lang.org/
2
1
[ruby-dev:52247] [Ruby Feature#22405] Run-Length Methods for String Bit Operations
by hasumikin (hitoshi hasumi) 07 Oct '26
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
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