Recent

Author Topic: [Solved ]Binary String to Integer (can this be improved)?  (Read 1361 times)

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: [Solved ]Binary String to Integer (can this be improved)?
« Reply #15 on: November 07, 2024, 07:43:32 am »
@marcov

Can not let it stand like this. I knew I had seen it - though not directly. It can be done as a variant of the decimal string to value conversion described by Mula here - http://0x80.pl/notesen/2014-10-15-parsing-decimal-numbers-part-2-sse.html.

The multiplier constants must be tailored to binary of course and the final aggregation could then be done by first shifting up of qwords according to their positional weight and a horizontal add. One doesn't even need the initial pshufb here.

Cheers,
MathMan

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11947
  • FPC developer.
Re: [Solved ]Binary String to Integer (can this be improved)?
« Reply #16 on: November 07, 2024, 04:13:07 pm »
Yes, neither can I, so I made it to work  :)

Note that I didn't bother optimizing (or changing requirements) for loading constants, since any place where that is critical has to have a loop keeping the constants in registers.

There is also a s2 shortstring parameter, which is redundant and only a buffer for testing. 

The requirement for storing the SIMD register and retrieving is a bit convoluted, I now simply dumped it over the original string, but for a real solution you will probably read first dword, vppermd and then move the another.

Code: Text  [Select][+][-]
  1. procedure binstringtointmathman(const s:shortstring;var x :dword; var s2:shortstring);assembler;
  2. // s must contain 16 characters either 1 or 0
  3. // works, but result is bit reversed
  4. asm
  5.   mov  r10d,$01020102
  6.   vmovq   xmm0,r10
  7.   vpbroadcastd xmm1,xmm0
  8.   mov      r11,$0101010101010101
  9.   vmovq    xmm0,r11
  10.   vpbroadcastq xmm4,xmm0
  11.   mov      r11,$0001000400010004
  12.   vmovq    xmm0,r11
  13.   vpbroadcastq xmm5,xmm0
  14.   mov      r11,$0001001000010010
  15.   vmovq    xmm0,r11
  16.   vpbroadcastq xmm6,xmm0
  17.  
  18.   movdqu xmm2,[rcx+1]
  19.   pand xmm2,xmm4
  20.   pmaddubsw xmm2,xmm1
  21.   pmaddwd xmm2,xmm5
  22.   packusdw xmm2,xmm2
  23.   pmaddwd xmm2,xmm6
  24.  
  25.   movdqu [rcx+1],xmm2
  26.   mov eax,[rcx+1]
  27.   mov r10d,[rcx+5]
  28.   shl rax,8
  29.   add rax,r10
  30.   mov [rdx],rax  
  31. end;
  32.  
« Last Edit: November 07, 2024, 04:15:38 pm by marcov »

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: [Solved ]Binary String to Integer (can this be improved)?
« Reply #17 on: November 07, 2024, 07:46:05 pm »
Nice!

Quote
The requirement for storing the SIMD register and retrieving is a bit convoluted, I now simply dumped it over the original string, but for a real solution you will probably read first dword, vppermd and then move the another.

That can be done easier with 'vpextrd rax,xmm2,0' / 'vpextrd rdx,xmm2,1' - no need to store out and read back.

Beside that better use VEX encoding throughout - on some architectures there is a hefty penalty when executing mixed VEX / non-VEX encoded instructions.

But there is one thing bothering me - you use xmm6. Iirc the Win64 ABI only has xmm0-xmm5 as 'scratch' registers available? Can be easily changed to use xmm0 instead of xmm6 though.


marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11947
  • FPC developer.
Re: [Solved ]Binary String to Integer (can this be improved)?
« Reply #18 on: November 07, 2024, 09:12:52 pm »
Probably only vpextrd for the second one. The first can be done with a MOV afaik.

As for Vex throughout, I don't care for that. That is most older architectures and the more high performance applications typically get their own new hardware anyway.

I didn't check register allocation, so yeah, that (xmm6) could be the case. IN Delphi you can easily save registers by just saying .saveenv xmm6, but FPC doesn't grok that.


marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11947
  • FPC developer.
Re: [Solved ]Binary String to Integer (can this be improved)?
« Reply #19 on: November 08, 2024, 02:29:43 pm »
Before commiting in my private test repo, I did process some suggestions and cleaned up a bit

Code: Text  [Select][+][-]
  1. procedure binstringtointmathman(const s:shortstring;var x :dword);assembler;
  2. // s must contain 16 characters either 1 or 0
  3. // suggested by Mathman, url: http://0x80.pl/notesen/2014-10-15-parsing-decimal-numbers-part-2-sse.html
  4. asm
  5.   // setup constants, not optimized
  6.   mov  r10d,$01020102
  7.   vmovq   xmm0,r10
  8.   vpbroadcastd xmm1,xmm0
  9.   mov      r11,$0101010101010101
  10.   vmovq    xmm0,r11
  11.   vpbroadcastq xmm4,xmm0
  12.   mov      r11,$0001000400010004
  13.   vmovq    xmm0,r11
  14.   vpbroadcastq xmm5,xmm0
  15.   mov      r11,$0001001000010010
  16.   vmovq    xmm0,r11
  17.   vpbroadcastq xmm3,xmm0
  18.  
  19. // the real packing
  20.   vmovdqu xmm2,[rcx+1]
  21.   vpand xmm2,xmm2,xmm4                  // and 1 -> lose the 48
  22.   vpmaddubsw xmm2,xmm2,xmm1             // for every two bytes mul * (1,2) then sum.
  23.   vpmaddwd xmm2,xmm2,xmm5               // simularly for two two bit codes (1,4) to form four bit code.
  24.   vpackusdw xmm2,xmm2,xmm2              // convert to vector of words.
  25.   vpmaddwd xmm2,xmm2,xmm3               // merge two 4 bit codes with (1,16)
  26.  
  27.   vmovd eax,xmm2                        // read two dwords back
  28.   vpextrd r10d,xmm2,1
  29.   shl rax,8                             // shift and add
  30.   add rax,r10
  31.   mov [rdx],eax                         // store
  32. end;
  33. [/pascal]
« Last Edit: November 08, 2024, 07:09:04 pm by marcov »

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: [Solved ]Binary String to Integer (can this be improved)?
« Reply #20 on: November 08, 2024, 06:40:44 pm »
Looks ok at first glance, except for the last line.

You defined X: dword, but store out a qword to @X - that may go bonkers.

Cheers,
MathMan

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11947
  • FPC developer.
Re: [Solved ]Binary String to Integer (can this be improved)?
« Reply #21 on: November 08, 2024, 07:09:10 pm »
Fixed

 

TinyPortal © 2005-2018