Recent

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

julkas

  • Sr. Member
  • ****
  • Posts: 416
  • 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: 3182
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: 416
  • 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: 9189
« Last Edit: June 19, 2019, 10:12:41 am by Thaddy »
also related to equus asinus.

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 7507
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: 416
  • 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: 416
  • 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: 2084
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: 9189
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.
also related to equus asinus.

Zoran

  • Hero Member
  • *****
  • Posts: 1464
    • 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: 416
  • 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: 2084
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: 416
  • 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: 1412
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: 416
  • 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;