Feature #22483: Region forms of String#bit_get

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

[hasumikin (hitoshi hasumi)]

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.

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.

  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.

  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.

Benchmark scriptBenchmark script

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.

Benchmark script for PicoRubyBenchmark script for PicoRuby

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

[hasumikin (hitoshi hasumi)]

• Backport deleted (3.3: UNKNOWN, 3.4: UNKNOWN, 4.0: UNKNOWN)
• Tracker changed from Bug to Feature