Issue #22483 has been updated by matz (Yukihiro Matsumoto). The region forms of `bit_get` are accepted as proposed. Regarding the write counterpart, I am fine with `bit_put`. I understand @mame's point that get/set is the usual pair in Ruby. But in bit manipulation, "set" already means turning a bit on, and `bit_set`, `bit_clear`, `bit_flip`, and `bit_set?` follow that vocabulary. I don't want to change the meaning of `bit_set` or make it depend on the number of arguments, so the value-writing method needs a different name. @hasumikin, could you propose `bit_put` in a separate ticket, including the behavior when the value does not fit in the region? I'd like to settle it before the release. Matz. ---------------------------------------- Feature #22483: Region forms of String#bit_get https://bugs.ruby-lang.org/issues/22483#change-119922 * Author: hasumikin (hitoshi hasumi) * Status: Open ---------------------------------------- PR: https://github.com/ruby/ruby/pull/19749 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/