[Solved ]Binary String to Integer (can this be improved)? lazarus / 21-General ---------------------------------------------------------------------- Ten_Mile_Hike · 2024-11-05 16:22 Code: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i The following works perfectly for me. I was just wondering if anyof you gurus have any examples of a more efficient code (even assembly) ThanksCode: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Uses Mathvar  S:String;  x:Integer;  tot:Integer=0;Begin  S:='10101101';  For x:=1 to 8 Do Tot := Tot+ Strtoint( S[x] ) * ( 2**(8-x) ); ---------------------------------------------------------------------- Fibonacci · 2024-11-05 16:28 Quote from: Ten_Mile_Hike on November 05, 2024, 05:22:06 pmCode: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i The following works perfectly for me. I was just wondering if anyof you gurus have any examples of a more efficient code (even assembly) ThanksCode: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Uses Mathvar  S:String;  x:Integer;  tot:Integer=0;Begin  S:='10101101';  For x:=1 to 8 Do Tot := Tot+ Strtoint( S[x] ) * ( 2**(8-x) ); Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i StrToInt('%10101101') Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Val('%10101101', tot, err); ---------------------------------------------------------------------- Warfley · 2024-11-05 16:35 If you don't need error handling you can simply do the following: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i result:=0;for c in s do  result:=ord(c)-ord('0')+(result shl 1);If you need error handling: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i for c in s dobegin  if not (c in ['0', '1']) then    // Error  result:=ord(c)-ord('0')+(result shl 1);end;Or alternatively, probably a bit more efficient on longer strings (because pchar conversion is expensive, might be less efficient on shorter strings): Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i p:=pchar(s);while p^ in ['0','1'] dobegin  result:=ord(p^)-ord('0')+(result shl 1);  inc(p);end;if Boolean(p^) then  // Error ---------------------------------------------------------------------- MathMan · 2024-11-05 18:34 Under the assumption that the string is 8 characters and pre-checked I can offer Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function Str8ToIntBin(  Str: UInt64; // string of 8 ASCII8 char as single UInt64):UInt8;       // converted value as UInt8 var  Mask1: UInt64; // SWAR conversion constant  Mask2: UInt64; // SWAR conversion constant begin  Mask1 := UInt64( $0101010101010101 );{$ifdef ENDIAN_BIG}  Mask2 := UInt64( $0102040810204080 );{$else}  Mask2 := UInt64( $8040201008040201 );{$endif} {$push}{$R-}{$Q-}    Result := ( ( Str and Mask1 ) * Mask2 ) shr 56;{$pop}end;  You can retrieve an 8 char stub as a UInt64 from an arbitrary string like Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i       Val := Unaligned( pUInt64( Str )^ ); ---------------------------------------------------------------------- Ten_Mile_Hike · 2024-11-05 19:21 These examples are all great. Thank you all so much!!! Now; can an Assembly master show me how they do this with inline Assembly? ---------------------------------------------------------------------- MathMan · 2024-11-05 19:27 If you look at the asm generated by the compiler for the function I gave (using O3 / O4) you'll see that there is not much to improve upon. PS - at least if you have a 64 bit CPU target. For a 32 bit target you can modify the Pascal source to handle only 4 chars at a time. Then again the compiler output for that would already be close to optimal. PPS - I am an avid asm fan, really. But in this case I'd stick with the Pascal source and leave the burden to the compiler. Unless you'd have a very specific use case in mind - but then, pls elaborate. ---------------------------------------------------------------------- Thaddy · 2024-11-06 07:05 @MathMan Your notation in your last example: you should use % instead of $. That will make your point more obvious. I mean, if you see the real binary representation, you do not need to mentally translate between hex and binary and makes the point on sight. ---------------------------------------------------------------------- marcov · 2024-11-06 18:21 Quote from: Ten_Mile_Hike on November 05, 2024, 08:21:09 pmThese examples are all great. Thank you all so much!!! Now; can an Assembly master show me how they do this with inline Assembly? I tried, but the quick method delivers the bits reversed.  Changing that would slow down. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure binstringtoint(const s:shortstring;var x :word);assembler;// s must contain 16 characters either 1 or 0// works, but result is bit reversedasm  mov rax,[rcx+1]  mov r9,[rcx+9]  mov r10,$0101010101010101  pext rax,rax,r10  pext r9,r9,r10  shl  r9,8  add  rax,r9  mov [rdx],axend; var s,s2 :shortstring;   i : integer;   x : word;d : dword; pd : pdword;begin  s:='1101001000101101'; // $D22D         binstringtoint(s,x);   writeln(inttohex(x,4),' ',inttobin(x,16));   // reference.  x :=$D22D;  writeln(inttohex(x,4),' ',inttobin(x,16)); end. ---------------------------------------------------------------------- Thaddy · 2024-11-06 18:32 How would a negation slow down by much? ---------------------------------------------------------------------- MathMan · 2024-11-06 19:26 Quote from: Thaddy on November 06, 2024, 07:32:07 pmHow would a negation slow down by much? marcov does not mean reversed value of bits, but reversed bit sequence. @Marcov: consider 'bswap' or 'movbe'  <= latter only avail with Haswell ongoing iirc But you are anyway on Haswell ongoing, as you use 'pext', which only came with the BMI2 extensions. ---------------------------------------------------------------------- marcov · 2024-11-06 20:33 Quote from: MathMan on November 06, 2024, 08:26:16 pm@Marcov: consider 'bswap' or 'movbe'  <= latter only avail with Haswell ongoing iirc Hmm. That wouldn't fix the bitfields that come out, but maybe it would work on the input to pext. Yup, that works! Code: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure binstringtoint(const s:shortstring;var x :word);assembler;// s must contain 16 characters either 1 or 0// works, but result is bit reversedasm  mov rax,[rcx+1]  mov r9,[rcx+9]  mov r10,$0101010101010101  bswap r9  bswap rax  pext rax,rax,r10  pext r9,r9,r10  shl  rax,8  add  rax,r9  mov [rdx],axend; var s,s2 :shortstring;   i : integer;   x : word;d : dword; pd : pdword;begin  s:='1101001000101101'; // $D22D         binstringtoint(s,x);   writeln(inttohex(x,4),' ',inttobin(x,16));  x :=$D22D;  writeln(inttohex(x,4),' ',inttobin(x,16));  end.  Generalizing this should be easy, and left as an exercise to the reader. QuoteBut you are anyway on Haswell ongoing, as you use 'pext', which only came with the BMI2 extensions. This is all fairly new for me, since I used Ivy Bridge till september 2023. I did have a Kaveri (AMD 7850K) though which also has BMI2. As for the purpose, that is a bit doubtful, but most of my (recent) assembler knowledge comes from writing SSE routines for image manipulation. And there it matters :-) ---------------------------------------------------------------------- MathMan · 2024-11-06 21:03 Quote from: marcov on November 06, 2024, 09:33:17 pmQuote from: MathMan on November 06, 2024, 08:26:16 pm@Marcov: consider 'bswap' or 'movbe'  <= latter only avail with Haswell ongoing iirc Hmm. That wouldn't fix the bitfields that come out, but maybe it would work on the input to pext. Yup, that works! Code: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure binstringtoint(const s:shortstring;var x :word);assembler;// s must contain 16 characters either 1 or 0// works, but result is bit reversedasm  mov rax,[rcx+1]  mov r9,[rcx+9]  mov r10,$0101010101010101  bswap r9  bswap rax  pext rax,rax,r10  pext r9,r9,r10  shl  rax,8  add  rax,r9  mov [rdx],axend; var s,s2 :shortstring;   i : integer;   x : word;d : dword; pd : pdword;begin  s:='1101001000101101'; // $D22D         binstringtoint(s,x);   writeln(inttohex(x,4),' ',inttobin(x,16));  x :=$D22D;  writeln(inttohex(x,4),' ',inttobin(x,16));  end.  Generalizing this should be easy, and left as an exercise to the reader. QuoteBut you are anyway on Haswell ongoing, as you use 'pext', which only came with the BMI2 extensions. This is all fairly new for me, since I used Ivy Bridge till september 2023. I did have a Kaveri (AMD 7850K) though which also has BMI2. As for the purpose, that is a bit doubtful, but most of my (recent) assembler knowledge comes from writing SSE routines for image manipulation. And there it matters :-) You're nearly there - I had this implemented as Code: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure binstringtoint(const s:shortstring;var x :word);assembler;// s must contain 16 characters either 1 or 0// works, but result is bit reversedasm  movbe rax,[rcx+1]  movbe r9,[rcx+9]  mov r10,$0101010101010101  pext rax,rax,r10  pext r9,r9,r10  shl  rax,8  add  rax,r9  mov [rdx],axend; ...  This allows slightly better scheduling to the four execution units - at least it measured slightly faster on Skylake. Of course the mantra can be extended to AVX2 or even AVX512, which would give another boost - but requires a larger string. Regarding the purpose - I totally agree with you. And that is why I proposed to use the Pascal version provided and leave the burden of adapting that to different CPUs / OSs to the compiler. ---------------------------------------------------------------------- marcov · 2024-11-06 21:27 (movbe) Quote from: MathMan on November 06, 2024, 10:03:10 pmThis allows slightly better scheduling to the four execution units - at least it measured slightly faster on Skylake. I've programmed a couple of thousand lines of ASM in recent years, but all vectorized. But in general I don't bother since with simple operations, the memory bottleneck always wins out. QuoteOf course the mantra can be extended to AVX2 or even AVX512, which would give another boost - but requires a larger string. The mirroring can be done with pshufb, but what instruction would you use for packing the bytes to bits ? The scatter/gather instructions maybe can do something similar, but looked complex and operated on memory rather than registers, which risks alignment problems. ---------------------------------------------------------------------- Ten_Mile_Hike · 2024-11-06 22:36 Thank you all. I always learn something interesting here. I appreciate it very much ---------------------------------------------------------------------- MathMan · 2024-11-06 22:47 Quote from: marcov on November 06, 2024, 10:27:02 pm (movbe) Quote from: MathMan on November 06, 2024, 10:03:10 pmThis allows slightly better scheduling to the four execution units - at least it measured slightly faster on Skylake. I've programmed a couple of thousand lines of ASM in recent years, but all vectorized. But in general I don't bother since with simple operations, the memory bottleneck always wins out. QuoteOf course the mantra can be extended to AVX2 or even AVX512, which would give another boost - but requires a larger string. The mirroring can be done with pshufb, but what instruction would you use for packing the bytes to bits ? The scatter/gather instructions maybe can do something similar, but looked complex and operated on memory rather than registers, which risks alignment problems. You got me  I thought I had seen that one implemented by Wojciech Muła, Daniel Lemire or Nathan Kurz - but can't find it easily at the moment. There definitely is no direct instruction for that in AVX/2/512. Top of my head I see two approaches - one via intial PADDUSB/PADDUSW and several follow up instructions, or it might be possible to use PCLMULQDQ with a special multiplier. Would need to work on that a bit ... Don't know if you are aware of the works of Wojciech Muła - might be interesting for you. See here - http://0x80.pl <= no https unfortunately ---------------------------------------------------------------------- MathMan · 2024-11-07 06:43 @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 · 2024-11-07 15:13 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure binstringtointmathman(const s:shortstring;var x :dword; var s2:shortstring);assembler;// s must contain 16 characters either 1 or 0// works, but result is bit reversedasm  mov  r10d,$01020102  vmovq xmm0,r10  vpbroadcastd xmm1,xmm0  mov      r11,$0101010101010101  vmovq    xmm0,r11  vpbroadcastq xmm4,xmm0  mov      r11,$0001000400010004  vmovq    xmm0,r11  vpbroadcastq xmm5,xmm0  mov      r11,$0001001000010010  vmovq    xmm0,r11  vpbroadcastq xmm6,xmm0   movdqu xmm2,[rcx+1]  pand xmm2,xmm4  pmaddubsw xmm2,xmm1  pmaddwd xmm2,xmm5  packusdw xmm2,xmm2  pmaddwd xmm2,xmm6   movdqu [rcx+1],xmm2  mov eax,[rcx+1]  mov r10d,[rcx+5]  shl rax,8  add rax,r10  mov [rdx],rax  end; ---------------------------------------------------------------------- MathMan · 2024-11-07 18:46 Nice! QuoteThe 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 · 2024-11-07 20:12 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 · 2024-11-08 13:29 Before commiting in my private test repo, I did process some suggestions and cleaned up a bit Code: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure binstringtointmathman(const s:shortstring;var x :dword);assembler;// s must contain 16 characters either 1 or 0// suggested by Mathman, url: http://0x80.pl/notesen/2014-10-15-parsing-decimal-numbers- part-2-sse.htmlasm  // setup constants, not optimized  mov  r10d,$01020102  vmovq   xmm0,r10  vpbroadcastd xmm1,xmm0  mov      r11,$0101010101010101  vmovq    xmm0,r11  vpbroadcastq xmm4,xmm0  mov      r11,$0001000400010004  vmovq    xmm0,r11  vpbroadcastq xmm5,xmm0  mov      r11,$0001001000010010  vmovq    xmm0,r11  vpbroadcastq xmm3,xmm0 // the real packing  vmovdqu xmm2,[rcx+1]  vpand xmm2,xmm2,xmm4                  // and 1 -> lose the 48  vpmaddubsw xmm2,xmm2,xmm1             // for every two bytes mul * (1,2) then sum.  vpmaddwd xmm2,xmm2,xmm5               // simularly for two two bit codes (1,4) to form four bit code.  vpackusdw xmm2,xmm2,xmm2            // convert to vector of words.  vpmaddwd xmm2,xmm2,xmm3             // merge two 4 bit codes with (1,16)   vmovd eax,xmm2                      // read two dwords back  vpextrd r10d,xmm2,1  shl rax,8                           // shift and add  add rax,r10  mov [rdx],eax                       // storeend;[/pascal] ---------------------------------------------------------------------- MathMan · 2024-11-08 17:40 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 · 2024-11-08 18:09 Fixed