Recent

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

Ten_Mile_Hike

  • Jr. Member
  • **
  • Posts: 87
[Solved ]Binary String to Integer (can this be improved)?
« on: November 05, 2024, 05:22:06 pm »
Code: Text  [Select][+][-]
  1. The following works perfectly for me. I was just wondering if any
  2. of you gurus have any examples of a more efficient code (even assembly)
  3. Thanks
Code: Pascal  [Select][+][-]
  1. Uses Math
  2. var
  3.   S:String;
  4.   x:Integer;
  5.   tot:Integer=0;
  6. Begin
  7.   S:='10101101';
  8.   For x:=1 to 8 Do Tot := Tot+ Strtoint( S[x] ) * ( 2**(8-x) );
« Last Edit: November 06, 2024, 11:35:10 pm by Ten_Mile_Hike »
When any government, or any church for that matter, undertakes to say to its subjects, This you may not read, this you
must not see, this you are forbidden to know, the end result is tyranny and oppression no matter how holy the motives.

Robert A. Heinlein

Fibonacci

  • Hero Member
  • *****
  • Posts: 612
  • Internal Error Hunter
Re: Binary String to Integer (can this be improved)?
« Reply #1 on: November 05, 2024, 05:28:03 pm »
Code: Text  [Select][+][-]
  1. The following works perfectly for me. I was just wondering if any
  2. of you gurus have any examples of a more efficient code (even assembly)
  3. Thanks
Code: Pascal  [Select][+][-]
  1. Uses Math
  2. var
  3.   S:String;
  4.   x:Integer;
  5.   tot:Integer=0;
  6. Begin
  7.   S:='10101101';
  8.   For x:=1 to 8 Do Tot := Tot+ Strtoint( S[x] ) * ( 2**(8-x) );

Code: Pascal  [Select][+][-]
  1. StrToInt('%10101101')

Code: Pascal  [Select][+][-]
  1. Val('%10101101', tot, err);
« Last Edit: November 05, 2024, 05:29:43 pm by Fibonacci »

Warfley

  • Hero Member
  • *****
  • Posts: 1762
Re: Binary String to Integer (can this be improved)?
« Reply #2 on: November 05, 2024, 05:35:48 pm »
If you don't need error handling you can simply do the following:
Code: Pascal  [Select][+][-]
  1. result:=0;
  2. for c in s do
  3.   result:=ord(c)-ord('0')+(result shl 1);
If you need error handling:
Code: Pascal  [Select][+][-]
  1. for c in s do
  2. begin
  3.   if not (c in ['0', '1']) then
  4.     // Error
  5.   result:=ord(c)-ord('0')+(result shl 1);
  6. 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][+][-]
  1. p:=pchar(s);
  2. while p^ in ['0','1'] do
  3. begin
  4.   result:=ord(p^)-ord('0')+(result shl 1);
  5.   inc(p);
  6. end;
  7. if Boolean(p^) then
  8.   // Error
« Last Edit: November 05, 2024, 05:39:09 pm by Warfley »

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Binary String to Integer (can this be improved)?
« Reply #3 on: November 05, 2024, 07:34:14 pm »
Under the assumption that the string is 8 characters and pre-checked I can offer

Code: Pascal  [Select][+][-]
  1. function Str8ToIntBin(
  2.   Str: UInt64; // string of 8 ASCII8 char as single UInt64
  3. ):UInt8;       // converted value as UInt8
  4.  
  5. var
  6.   Mask1: UInt64; // SWAR conversion constant
  7.   Mask2: UInt64; // SWAR conversion constant
  8.  
  9. begin
  10.   Mask1 := UInt64( $0101010101010101 );
  11. {$ifdef ENDIAN_BIG}
  12.   Mask2 := UInt64( $0102040810204080 );
  13. {$else}
  14.   Mask2 := UInt64( $8040201008040201 );
  15. {$endif}
  16.  
  17. {$push}{$R-}{$Q-}  
  18.   Result := ( ( Str and Mask1 ) * Mask2 ) shr 56;
  19. {$pop}
  20. end;
  21.  

You can retrieve an 8 char stub as a UInt64 from an arbitrary string like

Code: Pascal  [Select][+][-]
  1.       Val := Unaligned( pUInt64( Str )^ );
  2.  
« Last Edit: November 05, 2024, 08:24:03 pm by MathMan »

Ten_Mile_Hike

  • Jr. Member
  • **
  • Posts: 87
Re: Binary String to Integer (can this be improved)?
« Reply #4 on: November 05, 2024, 08:21:09 pm »
These examples are all great. Thank you all so much!!!
Now; can an Assembly master show me how they do
this with inline Assembly?
When any government, or any church for that matter, undertakes to say to its subjects, This you may not read, this you
must not see, this you are forbidden to know, the end result is tyranny and oppression no matter how holy the motives.

Robert A. Heinlein

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Binary String to Integer (can this be improved)?
« Reply #5 on: November 05, 2024, 08:27:00 pm »
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.
« Last Edit: November 05, 2024, 08:43:31 pm by MathMan »

Thaddy

  • Hero Member
  • *****
  • Posts: 16193
  • Censorship about opinions does not belong here.
Re: Binary String to Integer (can this be improved)?
« Reply #6 on: November 06, 2024, 08:05:53 am »
@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.
« Last Edit: November 06, 2024, 08:09:39 am by Thaddy »
If I smell bad code it usually is bad code and that includes my own code.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11944
  • FPC developer.
Re: Binary String to Integer (can this be improved)?
« Reply #7 on: November 06, 2024, 07:21:48 pm »
These 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][+][-]
  1. procedure binstringtoint(const s:shortstring;var x :word);assembler;
  2. // s must contain 16 characters either 1 or 0
  3. // works, but result is bit reversed
  4. asm
  5.   mov rax,[rcx+1]
  6.   mov r9,[rcx+9]
  7.   mov r10,$0101010101010101
  8.   pext rax,rax,r10
  9.   pext r9,r9,r10
  10.   shl  r9,8
  11.   add  rax,r9
  12.   mov [rdx],ax
  13. end;
  14.  
  15. var s,s2 :shortstring;
  16.    i : integer;
  17.    x : word;
  18. d : dword;
  19.  pd : pdword;
  20. begin
  21.   s:='1101001000101101'; // $D22D
  22.        
  23.   binstringtoint(s,x);
  24.  
  25.   writeln(inttohex(x,4),' ',inttobin(x,16));
  26.  
  27.   // reference.
  28.   x :=$D22D;
  29.   writeln(inttohex(x,4),' ',inttobin(x,16));
  30. end.
  31.  

Thaddy

  • Hero Member
  • *****
  • Posts: 16193
  • Censorship about opinions does not belong here.
Re: Binary String to Integer (can this be improved)?
« Reply #8 on: November 06, 2024, 07:32:07 pm »
How would a negation slow down by much?
If I smell bad code it usually is bad code and that includes my own code.

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Binary String to Integer (can this be improved)?
« Reply #9 on: November 06, 2024, 08:26:16 pm »
How 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.
« Last Edit: November 06, 2024, 08:32:06 pm by MathMan »

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11944
  • FPC developer.
Re: Binary String to Integer (can this be improved)?
« Reply #10 on: November 06, 2024, 09:33:17 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][+][-]
  1. procedure binstringtoint(const s:shortstring;var x :word);assembler;
  2. // s must contain 16 characters either 1 or 0
  3. // works, but result is bit reversed
  4. asm
  5.   mov rax,[rcx+1]
  6.   mov r9,[rcx+9]
  7.   mov r10,$0101010101010101
  8.   bswap r9
  9.   bswap rax
  10.   pext rax,rax,r10
  11.   pext r9,r9,r10
  12.   shl  rax,8
  13.   add  rax,r9
  14.   mov [rdx],ax
  15. end;
  16.  
  17. var s,s2 :shortstring;
  18.    i : integer;
  19.    x : word;
  20. d : dword;
  21.  pd : pdword;
  22. begin
  23.   s:='1101001000101101'; // $D22D
  24.        
  25.   binstringtoint(s,x);
  26.  
  27.   writeln(inttohex(x,4),' ',inttobin(x,16));
  28.   x :=$D22D;
  29.   writeln(inttohex(x,4),' ',inttobin(x,16));
  30.  
  31. end.
  32.  

Generalizing this should be easy, and left as an exercise to the reader.


Quote
But 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

  • Sr. Member
  • ****
  • Posts: 405
Re: Binary String to Integer (can this be improved)?
« Reply #11 on: November 06, 2024, 10:03:10 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][+][-]
  1. procedure binstringtoint(const s:shortstring;var x :word);assembler;
  2. // s must contain 16 characters either 1 or 0
  3. // works, but result is bit reversed
  4. asm
  5.   mov rax,[rcx+1]
  6.   mov r9,[rcx+9]
  7.   mov r10,$0101010101010101
  8.   bswap r9
  9.   bswap rax
  10.   pext rax,rax,r10
  11.   pext r9,r9,r10
  12.   shl  rax,8
  13.   add  rax,r9
  14.   mov [rdx],ax
  15. end;
  16.  
  17. var s,s2 :shortstring;
  18.    i : integer;
  19.    x : word;
  20. d : dword;
  21.  pd : pdword;
  22. begin
  23.   s:='1101001000101101'; // $D22D
  24.        
  25.   binstringtoint(s,x);
  26.  
  27.   writeln(inttohex(x,4),' ',inttobin(x,16));
  28.   x :=$D22D;
  29.   writeln(inttohex(x,4),' ',inttobin(x,16));
  30.  
  31. end.
  32.  

Generalizing this should be easy, and left as an exercise to the reader.


Quote
But 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][+][-]
  1. procedure binstringtoint(const s:shortstring;var x :word);assembler;
  2. // s must contain 16 characters either 1 or 0
  3. // works, but result is bit reversed
  4. asm
  5.   movbe rax,[rcx+1]
  6.   movbe r9,[rcx+9]
  7.   mov r10,$0101010101010101
  8.   pext rax,rax,r10
  9.   pext r9,r9,r10
  10.   shl  rax,8
  11.   add  rax,r9
  12.   mov [rdx],ax
  13. end;
  14.  
  15. ...
  16.  

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

  • Administrator
  • Hero Member
  • *
  • Posts: 11944
  • FPC developer.
Re: Binary String to Integer (can this be improved)?
« Reply #12 on: November 06, 2024, 10:27:02 pm »
 (movbe)
This 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.

Quote
Of 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

  • Jr. Member
  • **
  • Posts: 87
Re: [Solved ]Binary String to Integer (can this be improved)?
« Reply #13 on: November 06, 2024, 11:36:41 pm »
Thank you all. I always learn something interesting
here. I appreciate it very much
When any government, or any church for that matter, undertakes to say to its subjects, This you may not read, this you
must not see, this you are forbidden to know, the end result is tyranny and oppression no matter how holy the motives.

Robert A. Heinlein

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Binary String to Integer (can this be improved)?
« Reply #14 on: November 06, 2024, 11:47:34 pm »
(movbe)
This 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.

Quote
Of 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

 

TinyPortal © 2005-2018