[Solved ]Binary String to Integer (can this be improved)?

[Ten_Mile_Hike]

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) );

[Fibonacci]

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);

[Warfley]

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

[MathMan]

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.  

[Ten_Mile_Hike]

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]

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]

@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]

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]

How would a negation slow down by much?

[MathMan]

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.

[marcov]

@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.

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]

@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.

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]

 (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.

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]

Thank you all. I always learn something interesting
here. I appreciate it very much

[MathMan]

(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.

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