Recent

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

julkas

  • Guest
[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 »

howardpc

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

julkas

  • Guest
Re: TBits implementation
« Reply #2 on: June 19, 2019, 09:45:30 am »
Count() function - total number TRUE or FALSE values is missing. Why?

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
« Last Edit: June 19, 2019, 10:12:41 am by Thaddy »
Specialize a type, not a var.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
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

  • Guest
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 »

julkas

  • Guest
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.

lucamar

  • Hero Member
  • *****
  • Posts: 4219
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/FPC 2.0.8/3.0.4 & 2.0.12/3.2.0 - 32/64 bits on:
(K|L|X)Ubuntu 12..18, Windows XP, 7, 10 and various DOSes.

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
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.
Specialize a type, not a var.

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • 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

  • Guest
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.

lucamar

  • Hero Member
  • *****
  • Posts: 4219
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/FPC 2.0.8/3.0.4 & 2.0.12/3.2.0 - 32/64 bits on:
(K|L|X)Ubuntu 12..18, Windows XP, 7, 10 and various DOSes.

julkas

  • Guest
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().

ASerge

  • Hero Member
  • *****
  • Posts: 2222
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

  • Guest
Re: [CLOSED] TBits implementation
« Reply #14 on: June 20, 2019, 09:27:33 pm »
@ASerge Das ist sehr gut!
And without ASM?

 

TinyPortal © 2005-2018