Re: Byte Addressability And Beyond

EricP wrote:

Terje Mathisen wrote:

Terje Mathisen wrote:

EricP wrote:

MitchAlsup1 wrote:

BGB wrote:
>

On 5/5/2024 10:31 AM, Scott Lurndal wrote:

Thomas Koenig <tkoenig@netcologne.de> writes:

Scott Lurndal <scott@slp53.sl.home> schrieb:
>

>

Not as of yet in my case, but bitfield extract might happen eventually.
Issue is finding a way to pull it off that is useful and cheaper than shift+mask (and probably adding some mechanism to pattern-match it from the AST or similar).

>
But, but but but:: it IS shift and Mask !!
>

Annoyingly, a good general case instruction could not be encoded in a 32-bit instruction form at this point (could either add a few special cases as 32-bit ops, or use a 64-bit encoding; or do it as a 2RI op rather than 3RI but this is lame...).

>

Then again, say:
   BITEXTR  Imm10, Rn  //Rn=(Rn>>(Imm&63))&((1<<((Imm>>6)&15))-1)
Could potentially still be useful.

>
    SL    Rd,Rc,<width:offset>
>
Is a bit field extract instruction, it is also a smash instruction (smashing a 64-bit value into a 8-bit or 12-bit or 47 bit for whatever
purpose is needed)
>
    SR    Rd,Rc,<width:offset>
>
Positions the value in a register (Rc) such that it fits the alignment of
a field.
>
    INS   Rd,Rc,Rf,<width:offset>
>
Inserts the field from Rf into its position <w:o> in Rc, inserts the field and delivers the new container to Rd.

>
I think my instruction set could accomplish pretty much the same
efficiency for bit field operations as bit addresses but without
requiring direct bit addressing.
>
An issue that comes up is when the in-memory bit field is > 56 bits wide
as it might straddle two 64-bit words. If width is <= 56 bits then
a load from a byte address handles most of the shifting and the
rest can be handled within a single register.
>
But if the in-memory bit field is > 56 bits wide it may or may not straddle
a single 64-bit memory location, and require a pair of registers to loaded.

>
x86 does not have bitfield insert/extract, but it does have SHRD/SHLD so it is fairly easy to handle arbitrary length (<= 64 bits) and alignment:
>
; RSI -> target, RCX = # bits to extract, RBX = 64-field size (0..63)
  mov rax,[rsi]
  mov rdx,[rsi+8]

This is what I wanted to avoid: blindly loading the next word
as that could unnecessarilly read a cache line or worse,
trap on an access violation.

Its not that it is difficult to avoid, it just adds to the fiddlyness
(like conditional branches around one or two instructions).

  shrd rax,rdx,cl    ; bit offset
>
  and rax,bitmask[rbx*8] ; 64 mask entries.
>
The last instruction can also be replaced with
>
   shlx rax,rax,rbx    ; Nr of excess bits (64-field to extract)
   shrx rax,rax,rbx
>
or the entire thing can be replaced with this one which calculates the mask on the fly:
>
  mov rax,[rsi]
  mov rdx,[rsi+8]
  or rdi,-1        ; Generate mask
>
  shrd rax,rdx,cl    ; bit offset
  shrx rdi,rdi,rbx    ; excess bits to mask away
>
  and rax,rdi
>
All seems like about 3 clock cycles when hitting the cache.

 I realized this morning that with arbitrary alignment and both signed and unsigned extract, it is better to always shift up first to get rid of the excess and then shift down to align. The main problem here is that you now need different code for straddling and non-straddling items since shifts (including double-wide shifts) have to be less than 64 bits. :-(
 This is not a problem for constant length and alignment since the compiler can chose the correct pattern, but for codecs and compression it does not work. (Or at least not for those 57..64 field lengths).
   mov rax,[rsi]
  shl rax,cl       ; Excess bits above the field we need
  shrx rax,rax,rbx ; rbx=64-field length
 The last instruction would be
   sarx rax,rax,rbx
 if you wanted a signed bitfield.
 No matter how you do it it will be become a bottleneck in any huffmann token  extractor or similar codes. In my own decoders I've tended to grab a 32 (in the old days) or 64-bit chunk into a register and immediately align it. Then I'll use a lookup table over the first N (typically 6-12) bits of this buffer value and let the table decide how many bits to keep for the token, or in the case of longer tokens, select a second-level table to lookup the remaining bits.
 After decrementing the buffer bits remaining counter I'll branch out to refill it, but only if I have at least 32 or 48 free bits. This keeps the number of refills fairly low.
 Terje

There seem to be two use cases, one for bit-wise load and store to
individual bit fields in compiled structures, the other is dynamic
bit fields in bit streams.

The first is bit sized elements in packed arrays, or packed structs,
or packed arrays of packed structs, or packed structs containing packed
array of bit fields, etc. These are supported by some languages
(Ada85 had optional packed arrays and record structs).
For these the field start bit-offset is dynamic but the field size and
type are compile constants and so offer some potential for optimization
(but that could require inlining some of the access subroutines).

Such fields would tend to be both read and written is semi random order
but with a high probability that nearby fields will also be accessed.

The other is bit fields in bit streams being processed sequentially from
lsb to msb order, e.g for a codec. For these the field size and type are
dynamic but the token start offset can be arranged to be in bit[0].
If you know the bit-wise token always starts in bit[0] you don't need to
deal with field straddles, but must dynamically track where the last valid
in-register bit is and detect when to load the next word and append to the
register bit stream.

Bit stream processing would likely be either write-only encode or read-only
decode, proceeding once serially either low to high or high to low order.

Both would simplify greatly with double-wide shifts of register pairs,
as well as double-wide bit field extract and insert.

If you have the later {double-wide bit field extract and insert} why do you need the former {double-wide shifts of register pairs}
And by double-wide bit field extracts--you mean the container is 2 registers
wide and the extracted result is 64-bits (or less) wide; and that for insert
the value being inserted is 64-bits wide and the container it is being inserted
into is 2 registers wide.