Recent

Author Topic: [CLOSED] TBits implementation  (Read 1184 times)

julkas

  • Sr. Member
  • ****
  • Posts: 382
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
[CLOSED] TBits implementation
« on: June 18, 2019, 09:01:33 pm »
Why TBits functions FindFirstBit, FindNextBit, FindPrevBit implementation doesn't use Bsf, Bsr family?
« Last Edit: June 20, 2019, 03:16:34 pm by julkas »
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

howardpc

  • Hero Member
  • *****
  • Posts: 3148
Re: TBits implementation
« Reply #1 on: June 18, 2019, 09:23:58 pm »
Perhaps TBits was implemented before those intrinsics were available?

julkas

  • Sr. Member
  • ****
  • Posts: 382
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: TBits implementation
« Reply #2 on: June 19, 2019, 09:45:30 am »
Count() function - total number TRUE or FALSE values is missing. Why?
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

Thaddy

  • Hero Member
  • *****
  • Posts: 8901
« Last Edit: June 19, 2019, 10:12:41 am by Thaddy »
Most people that want to use threading should learn to patch their jeans first: use a needle.

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 7434
Re: TBits implementation
« Reply #4 on: June 19, 2019, 10:43:44 am »
Sometimes intrinsics might require allignment, or the wordsize of tbits' array and the intrinsic might not match on all architectures.

julkas

  • Sr. Member
  • ****
  • Posts: 382
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: TBits implementation
« Reply #5 on: June 19, 2019, 01:58:23 pm »
TBits is great data structure (when properly implemented), but
1. Free Pascal implementation lacks very basic Count() function.
C++ std::bitset::count
Quote
Returns the number of bits in the bitset that are set (i.e., that have a value of one).
2. I cant subclass TBits and implement my own Count() function - underlaying array is declared as private (FPC 3.0.4) and I don't want hacks.
3. Find family must be optimized.
4. I am lazy and I want simple answers for simple questions.

Please advice.

P. S. Can I open issue on TBits implementation?

« Last Edit: June 19, 2019, 02:41:07 pm by julkas »
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

julkas

  • Sr. Member
  • ****
  • Posts: 382
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: TBits implementation
« Reply #6 on: June 19, 2019, 06:05:23 pm »
It would be great also - something like SetRange(from, to). What you think about?
Thanks.
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

lucamar

  • Hero Member
  • *****
  • Posts: 2017
Re: TBits implementation
« Reply #7 on: June 19, 2019, 06:33:48 pm »
2. I cant subclass TBits and implement my own Count() function - underlaying array is declared as private (FPC 3.0.4) and I don't want hacks.

Instead of subclassing you can build a helper for the class. I'm not completely sure but IIRC you can access private fields that way. It also allows you to keep using TBits as-is but with the helper's add-ons (and replacements).

Note that all this is just theory; I haven's used helpers for more than the basic tasks, like adding TStrings-like functionality to normal arrays of strings and such.
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 2.0.2/2.0.4  - FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

Thaddy

  • Hero Member
  • *****
  • Posts: 8901
Re: TBits implementation
« Reply #8 on: June 19, 2019, 07:30:33 pm »
I agree. A helper class is a good solution.
BTW Tbits is often misused.
Most people that want to use threading should learn to patch their jeans first: use a needle.

Zoran

  • Hero Member
  • *****
  • Posts: 1459
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: TBits implementation
« Reply #9 on: June 19, 2019, 07:52:29 pm »
I think that Count() intrinsic for Pascal sets would be useful.
I mean, there is no way to count members of a set, apart from making a specialized Count() function for particular set type.

julkas

  • Sr. Member
  • ****
  • Posts: 382
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: TBits implementation
« Reply #10 on: June 20, 2019, 10:05:30 am »
Thanks @lucamar, but helper has access only to protected fields.
Here my test (FPC 3.0.4). Removing comments gives compilation error -
Code: Text  [Select]
  1. Compile Project, Target: zz.exe: Exit code 1, Errors: 1
  2. zz.lpr(13,15) Error: Identifier not found "FPriv"
Code: Pascal  [Select]
  1. unit priv;
  2. {$mode delphi}
  3. interface
  4.  
  5. uses
  6.   Classes, SysUtils;
  7.  
  8. type
  9.   TBase = class
  10.     private
  11.       FPriv: LongInt;
  12.     protected
  13.       FProt: LongInt;
  14.   end;
  15.  
  16. implementation
  17. end.

Code: Pascal  [Select]
  1. program zz;
  2. {$mode delphi}
  3. uses Classes, priv;
  4.  
  5. type
  6.   THelp = class helper for TBase
  7.      //function CntPriv(): LongInt;
  8.      function CntProt(): LongInt;
  9.   end;
  10. (*
  11.   function THelp.CntPriv(): LongInt;
  12.   begin
  13.     Result := FPriv;
  14.   end;
  15. *)
  16.   function THelp.CntProt(): LongInt;
  17.   begin
  18.     Result := FProt;
  19.   end;
  20.  
  21. var
  22.   obj: TBase;
  23.  
  24. begin
  25.   obj := TBase.Create;
  26.   WriteLn('CntProt - ', obj.CntProt());
  27.   obj.Destroy;
  28. end.

Please advice.
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

lucamar

  • Hero Member
  • *****
  • Posts: 2017
Re: TBits implementation
« Reply #11 on: June 20, 2019, 10:34:28 am »
Well, I said I wasn't completely sure and your test proves rather conclusively that it isn't so.

Since sub-classing won't work and neither do helpers your only option then seems to be patching TBits to add whatever you need.

Or, of course, creating your own TNicerBits class. :)

Or if all you want is a Count() function that can be done easily (in a helper): e.g. using TBits.FindFirstBit() and TBits.FindNextBit(), or walking through Bits[] and checking. Not, perhaps, the best way to do it, but it should work.
« Last Edit: June 20, 2019, 10:37:06 am by lucamar »
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 2.0.2/2.0.4  - FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

julkas

  • Sr. Member
  • ****
  • Posts: 382
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: TBits implementation
« Reply #12 on: June 20, 2019, 10:59:38 am »
Or if all you want is a Count() function that can be done easily (in a helper): e.g. using TBits.FindFirstBit() and TBits.FindNextBit(), or walking through Bits[] and checking. Not, perhaps, the best way to do it, but it should work.
Yes, it should work, but with poor performance.
The Count() function must be implemented with PopCnt().
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

ASerge

  • Hero Member
  • *****
  • Posts: 1406
Re: TBits implementation
« Reply #13 on: June 20, 2019, 06:20:49 pm »
Yes, it should work, but with poor performance.
The Count() function must be implemented with PopCnt().
No problem:
Code: Pascal  [Select]
  1. {$MODE OBJFPC}
  2. {$APPTYPE CONSOLE}
  3.  
  4. uses Classes;
  5.  
  6. type
  7.   TExBits = class(TBits)
  8.   strict private
  9.     type PBitArray = ^Classes.TBitArray;
  10.   protected
  11.     function GetFBits: PBitArray;
  12.   public
  13.     function Count(State: Boolean = True): Integer;
  14.   end;
  15.  
  16. function TExBits.Count(State: Boolean): Integer;
  17. var
  18.   P: PBitArray;
  19.   i: Integer;
  20. begin
  21.   P := GetFBits;
  22.   Result := 0;
  23.   for i := 0 to GetFSize - 1 do
  24.     Inc(Result, PopCnt(P^[i]));
  25.   if not State then
  26.     Result := Size - Result;
  27. end;
  28.  
  29. {$ASMMODE INTEL}
  30. function TExBits.GetFBits: PBitArray; assembler; nostackframe;
  31. asm
  32.    mov  @Result, Self.TBits.FBits
  33. end;
  34.  
  35. var
  36.   ExBits: TExBits;
  37. begin
  38.   ExBits := TExBits.Create(40);
  39.   try
  40.     ExBits[1] := True;
  41.     ExBits[36] := True;
  42.     Writeln(ExBits.Count);
  43.     Writeln(ExBits.Count(False));
  44.   finally
  45.     ExBits.Free;
  46.   end;
  47.   Readln;
  48. end.

julkas

  • Sr. Member
  • ****
  • Posts: 382
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: [CLOSED] TBits implementation
« Reply #14 on: June 20, 2019, 09:27:33 pm »
@ASerge Das ist sehr gut!
And without ASM?
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;