Feature #22405: Run-Length Methods for String Bit Operations

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

[hasumikin (hitoshi hasumi)]

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.

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.

  # 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.

  # 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.

  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.

  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.

  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.

Benchmark scriptBenchmark script

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.