Re: Byte Addressability And Beyond

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]
   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
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"