Least significant set bit in a set

[LemonParty]

Hello.

Is there an intrinsic to find least significant element that included in a set? Analog of BSFDWord function.

[marcov]

bsrdword() ?

[LemonParty]

BsfDWord can only handle 32 bits. What if I have more?

[Thaddy]

Doesn't help much if the set is the full 32 byte 
Then you need to revert to something analogous to what we did for popcnt for sets.
I am not aware of an instruction that does a bsr/bsf on 256 bits at once. Not even in avx-512

[LemonParty]

I ended up with this code:

Code: Pascal  [Select][+][-]

1. resourcestring
2.   rsSetTooLarge = 'Set too large';
3.   rsNotaSet = 'Not a set';
4.   rsEmptySet = 'Empty set';
5.  
6. {...}
7.  
8. function FirstInSet<T{:set}>(aSet: T): SizeUInt; inline;
9. type
10.   HWord = record a,b,c,d: QWord; end; PHWord = ^HWord;
11. var
12.   pTail: PByte;
13. begin
14.   if GetTypeKind(T) = tkSet then begin
15.     Result:= 255;
16.     case SizeOf(T) div 8 of
17.     1: Result:= BsfQWord(PHWord(@aSet)^.a);
18.     2: begin
19.       Result:= BsfQWord(PHWord(@aSet)^.a);
20.       if Result = 255 then begin
21.         Result:= BsfQWord(PHWord(@aSet)^.b);
22.         if Result <> 255 then
23.           inc(Result, 64);
24.       end;
25.       end;
26.     3: begin
27.       Result:= BsfQWord(PHWord(@aSet)^.a);
28.       if Result = 255 then begin
29.         Result:= BsfQWord(PHWord(@aSet)^.b);
30.         if Result = 255 then begin
31.           Result:= BsfQWord(PHWord(@aSet)^.c);
32.           if Result <> 255 then
33.             inc(Result, 128);
34.         end else inc(Result, 64);
35.       end;
36.       end;
37.     4: begin
38.       Result:= BsfQWord(PHWord(@aSet)^.a);
39.       if Result = 255 then begin
40.         Result:= BsfQWord(PHWord(@aSet)^.b);
41.         if Result = 255 then begin
42.           Result:= BsfQWord(PHWord(@aSet)^.c);
43.           if Result = 255 then begin
44.             Result:= BsfQWord(PHWord(@aSet)^.d);
45.             if Result = 255
46.               then raise ESetException.Create(rsEmptySet)
47.               else Exit(Result + 192);
48.             end else inc(Result, 128);
49.           end else inc(Result, 64);
50.         end;
51.       end;
52.     end;
53.  
54.     if Result = 255 then begin
55.       pTail:= @aSet + (SizeOf(T) and -8);
56.       case SizeOf(T) mod 8 of
57.       1: Result:= BsfByte(PByte(pTail)^);
58.       2: Result:= BsfWord(PWord(pTail)^);
59.       3: Result:= BsfDWord(PWord(pTail)^ + PByte(pTail + 2)^ shl 16);
60.       4: Result:= BsfDWord(PDWord(pTail)^);
61.       5: Result:= BsfQWord(PDWord(pTail)^ + QWord(PByte(pTail + 4)^) shl 32);
62.       6: Result:= BsfQWord(PDWord(pTail)^ + QWord(PWord(pTail + 4)^) shl 32);
63.       7: Result:= BsfQWord(PDWord(pTail)^ + QWord(PWord(pTail + 4)^) shl 32 + QWord(PByte(pTail + 6)^) shl 48);
64.       end;
65.  
66.       if Result = 255
67.         then raise ESetException.Create(rsEmptySet)
68.         else inc(Result, 64 * (SizeOf(T) div 8));
69.     end;
70.   end else raise ESetException.Create(rsNotaSet);
71. end;
72.  

Update: found and fixed few mistakes.

[avk]

...

 But in any case, the short amount of code I just presented isn't that bad .

Jamie

Yeah, it can even do something like

Code: Pascal  [Select][+][-]

1. procedure TestMyBSFVariable;
2. var
3.   I: Integer;
4. begin
5.   I := 42;
6.   WriteLn(MyBSFVariable<shortstring>(I));
7. end;
8.  

And the compiler won't object.

Why not just

Code: Pascal  [Select][+][-]

1. function LeastSetBit<TSet>(const s: TSet): Integer;
2. var
3.   I: Integer;
4. begin
5.   if GetTypeKind(TSet) <> tkSet then
6.     raise Exception.Create('Set expected');
7.   for I := 0 to SizeOf(s) - 1 do
8.     if PByte(@s)[I] <> 0 then
9.       exit(I*8 + Integer(BsfByte(PByte(@s)[I])));
10.   Result := -1;
11. end;
12.  

[avk]

Did you look at the help on BSFbyte? It states it returns 255 as a byte, not a sign integer. this is why I casted with a short integer to ensure the compiler would convert it to a sign. your example may not be doing this, it could be returning 255 instead for empty sets.

Jamie

BsfByte() can return 255 only for the zero argument.
It is cheaper to check the current byte for a zero value than to check the return of BsfByte().
That's exactly what LeastSetBit() does.

[avk]

Bsrbyte returns 0 for the first bit, so how does that work?

So you want me to help you check?

[LemonParty]

BsfByte is not optimal compare to BsfQWord. And also loops are not going to be inlined.

[avk]

BsfByte is not optimal compare to BsfQWord...

May be

Code: Pascal  [Select][+][-]

1. function LeastSetBit<TSet>(const s: TSet): Integer;
2. var
3.   p, pEnd: PByte;
4. begin
5.   if GetTypeKind(TSet) <> tkSet then
6.     raise Exception.Create('Set expected');
7.   p := @s;
8.   pEnd := p + SizeOf(s);
9.   while p < pEnd - 7 do begin
10.     if PQWord(p)^ <> 0 then exit((p - PByte(@s))*8 + Integer(BsfQWord(PQWord(p)^)));
11.     Inc(p, 8);
12.   end;
13.   if p < pEnd - 3 then begin
14.     if PDWord(p)^ <> 0 then exit((p - PByte(@s))*8 + Integer(BsfDWord(PDWord(p)^)));
15.     Inc(p, 4);
16.   end;
17.   while p < pEnd do begin
18.     if p^ <> 0 then exit((p - PByte(@s))*8 + Integer(BsfByte(p^)));
19.     Inc(p);
20.   end;
21.   Result := -1;
22. end;
23.  

[creaothceann]

Code: Pascal  [Select][+][-]

1. function LeastSetBit<TSet>(const s : TSet) : integer;
2. var
3.         p, pEnd : PByte;
4. begin
5.         if (GetTypeKind(TSet) <> tkSet) then raise Exception.Create('set expected');
6.         p    := @s;
7.         pEnd := p + SizeOf(s);
8.         while (p < (pEnd - 7)) do   begin  if (PQWord(p)^ <> 0) then exit(p - (PByte(@s) * 8) + integer(BsfQWord(PQWord(p)^)));  Inc(p, 8);  end;
9.         if    (p < (pEnd - 3)) then begin  if (PDWord(p)^ <> 0) then exit(p - (PByte(@s) * 8) + integer(BsfDWord(PDWord(p)^)));  Inc(p, 4);  end;
10.         while (p < (pEnd    )) do   begin  if (      (p)^ <> 0) then exit(p - (PByte(@s) * 8) + integer(BsfByte (      (p)^)));  Inc(p   );  end;
11.         Result := -1;
12. end;
13.  

[Thaddy]

And also loops are not going to be inlined.

What makes you think that? Sets are a prime target for {$optimization loopunroll} and that is what inline will do in at least -O3 and -O4.

[LemonParty]

What makes you think that? Sets are a prime target for {$optimization loopunroll} and that is what inline will do in at least -O3 and -O4.

I remember that in documentation told that functions and procedures with loops are not inlined. But maybe loop with fixed counter is a different case.

[Thaddy]

@LemonParty

Take this demo:

Code: Pascal  [Select][+][-]

1. program inlineloops;
2. {$ifdef fpc}{$mode objfpc}{$endif}
3. {$optimization level3}{$I-}
4. function doloop:integer;inline;
5. var i:integer;
6. begin
7.   for i := 0 to 3 do
8.     writeln(i);
9.     result := 3;
10. end;
11. begin
12.   doloop;
13. end.

This renders:

Code: ASM  [Select][+][-]

1. # [8] writeln(i);
2.         call    fpc_get_output
3.         movq    %rax,%rbx
4.         movq    %rax,%rdx
5.         xorl    %r8d,%r8d
6.         xorl    %ecx,%ecx
7.         call    fpc_write_text_sint
8.         movq    %rbx,%rcx
9.         call    fpc_writeln_end
10.         call    fpc_get_output
11.         movq    %rax,%rbx
12.         movq    %rax,%rdx
13.         movl    $1,%r8d
14.         xorl    %ecx,%ecx
15.         call    fpc_write_text_sint
16.         movq    %rbx,%rcx
17.         call    fpc_writeln_end
18.         call    fpc_get_output
19.         movq    %rax,%rbx
20.         movq    %rax,%rdx
21.         movl    $2,%r8d
22.         xorl    %ecx,%ecx
23.         call    fpc_write_text_sint
24.         movq    %rbx,%rcx
25.         call    fpc_writeln_end
26.         call    fpc_get_output
27.         movq    %rax,%rbx
28.         movq    %rax,%rdx
29.         movl    $3,%r8d
30.         xorl    %ecx,%ecx
31.         call    fpc_write_text_sint
32.         movq    %rbx,%rcx
33.         call    fpc_writeln_end
34. # Var $result located in register eax
35. # [9] result := 3;
36.         movl    $3,%eax
37. # [10] end;

Fully unrolled.
So yes, it is a different case.

[marcov]

(I'm not 100% sure, but afaik sets are mostly only dword aligned. And only if it is a multiple.  Random typecasting to pdword,pqword might bring trouble with older versions of architectures that care about alignment )