Sujet : Re: Byte Addressability And Beyond
De : terje.mathisen (at) *nospam* tmsw.no (Terje Mathisen)
Groupes : comp.archDate : 07. May 2024, 07:39:18
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <v1ceq6$339t4$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11
User-Agent : Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Firefox/91.0 SeaMonkey/2.53.18.2
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"
Date | Sujet | # | | Auteur |
1 May 24 | Byte Addressability And Beyond | 590 | | Lawrence D'Oliveiro |
1 May 24 | Re: Byte Addressability And Beyond | 431 | | John Levine |
1 May 24 | Re: Byte Addressability And Beyond | 409 | | Lawrence D'Oliveiro |
1 May 24 | Re: Byte Addressability And Beyond | 3 | | John Levine |
1 May 24 | Re: Byte Addressability And Beyond | 1 | | John Levine |
1 May 24 | Re: Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
1 May 24 | Re: Byte Addressability And Beyond | 1 | | Michael S |
1 May 24 | Re: Byte Addressability And Beyond | 404 | | John Levine |
2 May 24 | Re: Byte Addressability And Beyond | 382 | | Lawrence D'Oliveiro |
2 May 24 | Re: Byte Addressability And Beyond | 4 | | John Levine |
2 May 24 | Re: Byte Addressability And Beyond | 3 | | Lawrence D'Oliveiro |
2 May 24 | Re: Byte Addressability And Beyond | 2 | | John Levine |
5 May 24 | Re: Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
2 May 24 | Re: Byte Addressability And Beyond | 367 | | John Savard |
2 May 24 | Re: Byte Addressability And Beyond | 2 | | MitchAlsup1 |
11 May 24 | Re: Byte Addressability And Beyond | 1 | | John Savard |
4 May 24 | Re: Byte Addressability And Beyond | 364 | | Lawrence D'Oliveiro |
8 May 24 | Re: Byte Addressability And Beyond | 363 | | John Savard |
8 May 24 | Re: Byte Addressability And Beyond | 2 | | Lawrence D'Oliveiro |
10 May 24 | Re: Byte Addressability And Beyond | 1 | | David Brown |
8 May 24 | Re: Byte Addressability And Beyond | 360 | | MitchAlsup1 |
8 May 24 | Re: Byte Addressability And Beyond | 359 | | John Levine |
8 May 24 | Re: Byte Addressability And Beyond | 357 | | Lawrence D'Oliveiro |
9 May 24 | Re: Byte Addressability And Beyond | 356 | | John Levine |
10 May 24 | Re: Byte Addressability And Beyond | 354 | | David Brown |
10 May 24 | Re: Byte Addressability And Beyond | 353 | | Anton Ertl |
11 May 24 | Re: Byte Addressability And Beyond | 352 | | David Brown |
11 May 24 | Re: Byte Addressability And Beyond | 351 | | Anton Ertl |
11 May 24 | Re: Byte Addressability And Beyond | 158 | | David Brown |
11 May 24 | Re: Byte Addressability And Beyond | 1 | | Anton Ertl |
27 May 24 | Re: Byte Addressability And Beyond | 156 | | Lawrence D'Oliveiro |
27 May 24 | Re: Byte Addressability And Beyond | 155 | | John Levine |
27 May 24 | Re: Byte Addressability And Beyond | 154 | | Lawrence D'Oliveiro |
27 May 24 | Re: Byte Addressability And Beyond | 153 | | John Levine |
27 May 24 | Re: Byte Addressability And Beyond | 149 | | John Levine |
27 May 24 | Re: Byte Addressability And Beyond | 1 | | MitchAlsup1 |
28 May 24 | Re: Byte Addressability And Beyond | 147 | | Lawrence D'Oliveiro |
28 May 24 | Re: encoding conversion, Byte Addressability And Beyond | 1 | | John Levine |
28 May 24 | Re: Byte Addressability And Beyond | 145 | | Thomas Koenig |
29 May 24 | Re: Byte Addressability And Beyond | 137 | | Lawrence D'Oliveiro |
29 May 24 | Re: Byte Addressability And Beyond | 136 | | Anton Ertl |
29 May 24 | Re: Byte Addressability And Beyond | 12 | | Stefan Monnier |
29 May 24 | Re: Byte Addressability And Beyond | 10 | | Stefan Monnier |
29 May 24 | Re: Byte Addressability And Beyond | 3 | | John Levine |
30 May 24 | Re: Byte Addressability And Beyond | 2 | | George Neuner |
4 Jun 24 | Re: Byte Addressability And Beyond | 1 | | George Neuner |
30 May 24 | Re: Byte Addressability And Beyond | 6 | | Anton Ertl |
4 Jun 24 | Re: Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
4 Jun 24 | Re: Byte Addressability And Beyond | 4 | | Stefan Monnier |
7 Jun 24 | Re: Byte Addressability And Beyond | 1 | | Terje Mathisen |
7 Jun 24 | Re: Character non-equivalence, was Byte Addressability And Beyond | 2 | | John Levine |
9 Jun 24 | Re: Character non-equivalence, was Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
30 May 24 | Re: Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
30 May 24 | Re: Byte Addressability And Beyond | 117 | | Lawrence D'Oliveiro |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 66 | | John Levine |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Stephen Fuld |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 22 | | Anton Ertl |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 21 | | Thomas Koenig |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 8 | | Michael S |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Thomas Koenig |
30 May 24 | Re: IBM architectural goals, Byte Addressability And Beyond | 5 | | John Levine |
30 May 24 | Re: IBM architectural goals, Byte Addressability And Beyond | 2 | | Michael S |
30 May 24 | Re: IBM architectural goals, Byte Addressability And Beyond | 1 | | John Levine |
30 May 24 | Re: IBM architectural goals, Byte Addressability And Beyond | 2 | | Thomas Koenig |
30 May 24 | Re: IBM architectural goals, Byte Addressability And Beyond | 1 | | John Levine |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Anton Ertl |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 3 | | Anton Ertl |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | John Levine |
30 May 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Thomas Koenig |
31 May 24 | Re: architectural goals, Byte Addressability And Beyond | 5 | | Terje Mathisen |
1 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 4 | | Thomas Koenig |
1 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 3 | | Anton Ertl |
2 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 2 | | John Levine |
4 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Stefan Monnier |
4 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 4 | | Lawrence D'Oliveiro |
4 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | MitchAlsup1 |
4 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Lynn Wheeler |
4 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Stefan Monnier |
31 May 24 | Re: architectural goals, Byte Addressability And Beyond | 42 | | John Savard |
31 May 24 | Re: architectural goals, Byte Addressability And Beyond | 41 | | John Levine |
1 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 31 | | John Savard |
1 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 20 | | Thomas Koenig |
2 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 6 | | John Savard |
2 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 5 | | Thomas Koenig |
2 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 3 | | John Levine |
3 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 2 | | OrangeFish |
3 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | John Levine |
4 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
4 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 13 | | Lawrence D'Oliveiro |
5 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 12 | | Lawrence D'Oliveiro |
5 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
6 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 10 | | George Neuner |
6 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 6 | | John Levine |
7 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 4 | | Lawrence D'Oliveiro |
7 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 3 | | Stephen Fuld |
7 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 2 | | Lawrence D'Oliveiro |
7 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Stephen Fuld |
7 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Terje Mathisen |
6 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Lynn Wheeler |
6 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | OrangeFish |
7 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
2 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 10 | | John Dallman |
2 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | Michael S |
2 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 1 | | John Dallman |
4 Jun 24 | Re: architectural goals, Byte Addressability And Beyond | 7 | | Lawrence D'Oliveiro |
30 May 24 | Re: Byte Addressability And Beyond | 49 | | Stephen Fuld |
30 May 24 | Re: Byte Addressability And Beyond | 1 | | Anton Ertl |
30 May 24 | Re: Byte Addressability And Beyond | 2 | | Lawrence D'Oliveiro |
30 May 24 | Re: Byte Addressability And Beyond | 4 | | Terje Mathisen |
30 May 24 | Re: Byte Addressability And Beyond | 7 | | Terje Mathisen |
28 May 24 | Re: Byte Addressability And Beyond | 3 | | Lawrence D'Oliveiro |
12 May 24 | Re: python text, Byte Addressability And Beyond | 14 | | John Levine |
12 May 24 | Re: Byte Addressability And Beyond | 178 | | Thomas Koenig |
27 May 24 | Re: Byte Addressability And Beyond | 1 | | Lawrence D'Oliveiro |
8 May 24 | Re: Byte Addressability And Beyond | 1 | | Michael S |
2 May 24 | Re: Byte Addressability And Beyond | 10 | | MitchAlsup1 |
2 May 24 | Re: Byte Addressability And Beyond | 3 | | Michael S |
2 May 24 | Re: Byte Addressability And Beyond | 18 | | Anton Ertl |
1 May 24 | Byte Order (was: Byte Addressability And Beyond) | 4 | | Anton Ertl |
1 May 24 | Re: Byte Addressability And Beyond | 17 | | Stefan Monnier |
1 May 24 | Re: Byte Addressability And Beyond | 40 | | MitchAlsup1 |
1 May 24 | Re: Byte Addressability And Beyond | 15 | | Thomas Koenig |
1 May 24 | Re: Byte Addressability And Beyond | 3 | | Michael S |
2 May 24 | Re: Byte Addressability And Beyond | 4 | | Lawrence D'Oliveiro |
3 May 24 | Re: Byte Addressability And Beyond | 75 | | Anton Ertl |
5 May 24 | Re: Byte Addressability And Beyond | 20 | | John Savard |
5 May 24 | Re: Byte Addressability And Beyond | 1 | | John Savard |