Project

General

Profile

Feature #22483

Updated by hasumikin (hitoshi hasumi) 17 days ago

PR: https://github.com/ruby/ruby/pull/19749 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. 

Back