Lazarus

Free Pascal => FPC development => Topic started by: meteoricshipyards on January 12, 2016, 11:29:59 pm

Title: What happened to the built in CARD() function?
Post by: meteoricshipyards on January 12, 2016, 11:29:59 pm
Way back in the late 70's and early 80's I worked with Pascal on a CDC NOS machine.  This past Summer I recently found a listing of an Adventure game that I played way back then.  I researched, found Lazarus and Free Pascal, and started typing it in.  One thing that didn't work was the CARD() function.  For those of you who don't know it, it returns the number of items in a set variable.  (For really obscure trivia, it was implemented as a single instruction on the CDC 60 bit architecture). 

As I only had one type of set that I needed the function for, I coded up my own.  But I was wondering when and why it disappeared, and if I should be aware of other items that may have gone away.

Tom A.
Planning on "publishing" the game on an Interactive Fiction site in within a month.
Title: Re: What happened to the built in CARD() function?
Post by: molly on January 13, 2016, 03:25:58 am
One thing that didn't work was the CARD() function.
Perhaps you might find this thread (http://forum.lazarus.freepascal.org/index.php?topic=27629.0) interesting.
Title: Re: What happened to the built in CARD() function?
Post by: marcov on January 13, 2016, 09:17:01 am
It never was in Turbo Pascal, so if it was standard, it already fell off before.

It is also possible it was just some intrinsic for a CDC instruction and not standard.  As Molly correctly pointed out, FPC has popcount, but it is only for integers, so only works for sets the size of a register.
Title: Re: What happened to the built in CARD() function?
Post by: Thaddy on January 13, 2016, 12:21:48 pm
@Marco: You yourself suggested PopCnt sometime ago.... ;)
http://stackoverflow.com/questions/12934017/knowing-how-many-elements-a-set-have

If that is correct and there are already compiler iintrinsics, it shouldn't be too hard to massage the compiler into having a card().
Title: Re: What happened to the built in CARD() function?
Post by: marcov on January 13, 2016, 12:46:37 pm
My point is mainly that if an ancient compiler had it, it is not necessarily standard.

But I guess nothing stops you from submitting a patch if it is easy.
Title: Re: What happened to the built in CARD() function?
Post by: meteoricshipyards on January 13, 2016, 08:01:14 pm
It was in the User Manual and Report at the time, and was the first or second implementation of Pascal, so it was pretty standard :-)

But it is not a function that is used often, or needs to be part of the standard, as far as I'm concerned.  Other functions that are gone (and were definitely implementation specific) are the eos(file) (end of segment) and linelimit(text) functions.

But I'm just glad I found this.  I consider Pascal my native language (even though I learned BASIC and FORTRAN before it).

Tom A.
Now to figure out objects in Pascal....
Title: Re: What happened to the built in CARD() function?
Post by: ArtLogi on January 17, 2016, 02:18:33 am
Well it seems to be in the ISO/IEC 10206:1 Page X, under "Set Extensions"
Quote
The function card yields the number of members in a set.

http://pascal-central.com/docs/iso10206.pdf
http://pascal-central.com/standards.html 
8)

Interesting I had an image that there were only one standard along the years considering pascal language. 1982 and no further updates and standardization work.
Title: Re: What happened to the built in CARD() function?
Post by: marcov on January 17, 2016, 04:55:39 pm
Don't get me wrong, CARD() would be fine, as would other work on sets

- like lifting the upper limit of 256 elements. (this makes using enums and sets difficult since it bounds itsscaling)

- respecting the lower limit (too often, elements are allocated starting with 0, even if the lower bound is not 0 or close to it)

- not even talking of the sparse sets in some Pascal dialects etc.
Title: Re: What happened to the built in CARD() function?
Post by: Bart on January 17, 2016, 05:09:06 pm
Extending Length() to handle sets would, with regard to the name of the function, make more sense to me.

Bart
Title: Re: What happened to the built in CARD() function?
Post by: Thaddy on February 10, 2018, 09:36:45 am
Old thread but not much has happened.
Summary:
For small sets (max 32 members) you can use PopCnt
For large sets (max 256 members you can also use PopCnt, but over an array.
I dreamed up this today because I only needed it now.
Code: Pascal  [Select][+][-]
  1. function Card(const s;SmallSet:boolean =true):word;inline;
  2. var
  3.   t:packed array [0..3] of qword absolute s;
  4. begin
  5.   if SmallSet then
  6.     Result := PopCnt(Dword(s))
  7.   else
  8.     Result := PopCnt(T[0])+PopCnt(T[1])+PopCnt(T[2])+PopCnt(T[3]);
  9. end;

Now if somebody knows a nifty trick to obtain the set size from an untyped const, I can get rid of the second parameter.
In extended ISO Pascal this is solved by an any_set intrinsic 

Title: Re: What happened to the built in CARD() function?
Post by: taazz on February 10, 2018, 10:19:04 am
Now if somebody knows a nifty trick to obtain the set size from an untyped const, I can get rid of the second parameter.
how about making the second parameter the size of the set instead of a boolean.
Title: Re: What happened to the built in CARD() function?
Post by: Thaddy on February 10, 2018, 11:11:43 am
how about making the second parameter the size of the set instead of a boolean.
That's what I had first but I want to get rid of the parameter altogether. Another option was two separate functions. (Can't overload them). I tried rtti but that fails on tkUnKnown/$formal
Title: Re: What happened to the built in CARD() function?
Post by: marcov on February 10, 2018, 02:07:03 pm
Now if somebody knows a nifty trick to obtain the set size from an untyped const, I can get rid of the second parameter.

Well, there is also a problem that you need to mask out unused bits. They are probably zero, but I don't know how reliable that is. And sets are multiples of bytes, not qwords.
Title: Re: What happened to the built in CARD() function?
Post by: Thaddy on February 10, 2018, 03:33:53 pm
@marcov
The unused bits in sets < 33 bits are predictably zero, as are the unused bytes in a large up-to-32 byte set (this is also documented)
I can not use, however, just the function body for large sets for any set because that fails on stack-allocated space. And I tested that that will fail. (of course, but I tested it)
The use of qwords is an internal and legal for any bit set > 32 bits. It merely uses the most efficient available PopCnt overload.
Title: Re: What happened to the built in CARD() function?
Post by: howardpc on February 10, 2018, 04:16:17 pm
Now if somebody knows a nifty trick to obtain the set size from an untyped const, I can get rid of the second parameter.

An untyped const parameter has no type information (SizeOf() = 0, TTypeKind = tkUnknown), which is logical since it is untyped.
You can, however, determine the size predicated on the unused bits being zero. Where is this documented?
The following routine may not be very efficient, but it expresses the cardinality of any set passed as an untyped parameter to the Card() function.

Code: Pascal  [Select][+][-]
  1. program Cardinality;
  2.  
  3. {$Mode objfpc}{$H+}
  4.  
  5. type
  6.   T4ByteRange      = Byte(0)..Byte(3);
  7.   T32ByteRange     = Byte(0)..Byte(31);
  8.   TMediumSetQWords = array[T4ByteRange] of QWord;
  9.  
  10. function Card(const aSet): Integer;
  11. var
  12.   msqw: TMediumSetQWords absolute aSet;
  13.   w: Word = 0;
  14.   b: Byte;
  15. begin
  16.   for b := Low(T4ByteRange) to High(T4ByteRange) do
  17.     Inc(w, PopCnt(msqw[b]));
  18.   if (w = 0) then
  19.     Exit(0);
  20.   Result := 0;
  21.   for b:= 1 to High(T4ByteRange) do
  22.     Inc(Result);
  23.   if (Result = 0) then
  24.     Exit(PopCnt(DWord(aSet)))
  25.   else Exit(w);
  26. end;
  27.  
  28. var
  29.   smallSet:  set of T32ByteRange;
  30.   mediumSet: set of Char;
  31.   c:         Char;
  32.   b:         T32ByteRange;
  33.  
  34. begin
  35.   smallSet := [];
  36.     WriteLn('smallSet: Card([]) = ', Card(smallSet));
  37.   smallSet := [31];
  38.     WriteLn('smallSet: Card([31]) = ', Card(smallSet));
  39.   smallSet := [1,3,5,7,31];
  40.     WriteLn('smallSet: Card([1,3,5,7,31]) = ', Card(smallSet));
  41.   for b := Low(T32ByteRange) to High(T32ByteRange) do
  42.     Include(smallSet, b);
  43.     WriteLn('smallSet: Card([full small set]) = ', Card(smallSet));
  44.   WriteLn;
  45.  
  46.   mediumSet := [];
  47.     WriteLn('mediumSet: Card([]) = ',Card(mediumSet));
  48.   mediumSet := ['?'];
  49.     WriteLn('mediumSet: Card([''?'']) = ',Card(mediumSet));
  50.   mediumSet := ['!','f','%','D'];
  51.     WriteLn('mediumSet: Card([''!'',''f'',''%'',''D'']) = ',Card(mediumSet));
  52.   Exclude(mediumSet, 'f');
  53.     WriteLn('mediumSet: after Exclude(mediumSet,''f''), Card(mediumSet) = ',Card(mediumSet));
  54.   for c in Char do
  55.     Include(mediumSet, c);
  56.   WriteLn('Card([full medium set]) = ',Card(mediumSet));
  57.  
  58.   ReadLn;
  59. end.    
Title: Re: What happened to the built in CARD() function?
Post by: marcov on February 11, 2018, 01:09:55 pm
The use of qwords is an internal and legal for any bit set > 32 bits. It merely uses the most efficient available PopCnt overload.

Code: Pascal  [Select][+][-]
  1. {$mode delphi}
  2.  
  3. type  txxx = set of 0..247;
  4.  
  5. begin
  6.   writeln(sizeof(txxx));
  7. end.

Prints 31.
Title: Re: What happened to the built in CARD() function?
Post by: Thaddy on February 11, 2018, 01:43:13 pm
Prints 31.
https://www.freepascal.org/docs-html/ref/refsu16.html#x40-580003.3.3
" The compiler stores small sets (less than 32 elements) in a Longint, if the type range allows it. This allows for faster processing and decreases program size. Otherwise, sets are stored in 32 bytes."
The docs are wrong anyway since it should read less than 33 bits since set of 0..31 is size 4.

Maybe file a bug report against documentation?
Title: Re: What happened to the built in CARD() function?
Post by: marcov on February 11, 2018, 01:49:27 pm
https://www.freepascal.org/docs-html/ref/refsu16.html#x40-580003.3.3
" The compiler stores small sets (less than 32 elements) in a Longint, if the type range allows it. This allows for faster processing and decreases program size. Otherwise, sets are stored in 32 bytes."

True for mode objfpc, but not for delphi.  IIRC before the bytewise growing, Delphi mode already had a while that sets were multiples of 4 (might still be on non x86). That might go back as far as 2.2


documentation bug filed: https://bugs.freepascal.org/view.php?id=33156
Title: Re: What happened to the built in CARD() function?
Post by: ASerge on February 11, 2018, 02:04:05 pm
" The compiler stores small sets (less than 32 elements) in a Longint, if the type range allows it. This allows for faster processing and decreases program size. Otherwise, sets are stored in 32 bytes."
I think the documentation is inaccurate and most likely in FPC, as in Delphi: Max div 8 - Min div 8 + 1 (http://docwiki.embarcadero.com/RADStudio/Tokyo/en/Internal_Data_Formats_(Delphi)#Set_Types).
Title: Re: What happened to the built in CARD() function?
Post by: howardpc on February 11, 2018, 02:11:20 pm
After a bit more thought, a simplified Card() is this:
Code: Pascal  [Select][+][-]
  1. {$Mode objfpc}
  2.  
  3. type
  4.  
  5.   TMediumSetDWords = array[0..7] of DWord;
  6.  
  7. function Card(const aSet): Word;
  8. var
  9.   msdw: TMediumSetDWords absolute aSet;
  10.   b: Byte;
  11. begin
  12.   Result := PopCnt(msdw[0]);
  13.   for b := 1 to 7 do
  14.     Inc(Result, PopCnt(msdw[b]));
  15. end;
Title: Re: What happened to the built in CARD() function?
Post by: Thaddy on February 11, 2018, 02:46:46 pm
After a bit more thought, a simplified Card() is this:
- That code is less efficient on modern processors since PopCnt has a qword option (like I used)
- It will - just like my own code - fail when called on a set that is stack allocated, i.e. from within a procedure or function. Unused bytes are "dirty".
- And as Marco demonstrates it will always fail in {$mode delphi}. The unused bytes are undefined, i.e. also dirty.

Without a means of determining the size of the set inside a function and from an un-typed const it seems impossible to write a typesafe generic card function as it stands using high-level code. For small sets it works though:
Code: Pascal  [Select][+][-]
  1. // card for sets with 32 elements or less.
  2. function card(const s):integer;
  3. begin
  4.   card := PopCnt(Dword(s));
  5. end;

For the compiler it should not be any problem to introduce such a feature since it knows the size of the set at compile time. This looks only solvable with compiler magic. (Just like PopCnt)
Title: Re: What happened to the built in CARD() function?
Post by: PascalDragon on February 17, 2018, 07:32:02 pm
Generic functions to the rescue:

Code: Pascal  [Select][+][-]
  1. program tcard;
  2.  
  3. {$mode objfpc}
  4.  
  5. generic function Card<T>(aSetValue: T): LongInt;
  6. var
  7.   i: LongInt;
  8. begin
  9.   if SizeOf(aSetValue) <= 4 then
  10.     Result := PopCnt(PLongWord(@aSetValue)^)
  11.   else begin
  12.     Result := 0;
  13.     for i := 0 to SizeOf(aSetValue) div SizeOf(LongWord) - 1 do
  14.       Inc(Result, PopCnt(PLongWord(@aSetValue)[i]));
  15.   end;
  16. end;
  17.  
  18. type
  19.   TSet1 = set of 1..3;
  20.   TSet2 = set of 1..40;
  21.  
  22. var
  23.   set1: TSet1;
  24.   set2: TSet2;
  25. begin
  26.   set1 := [2];
  27.   set2 := [4, 9, 23, 40];
  28.  
  29.   Writeln(specialize Card<TSet1>(set1));
  30.   Writeln(specialize Card<TSet2>(set2));
  31. end.
  32.  

Sadly the "Unreachable code" warning can not be suppressed  :'(
Title: Re: What happened to the built in CARD() function?
Post by: ASerge on February 17, 2018, 09:28:58 pm
Sadly the "Unreachable code" warning can not be suppressed  :'(
1. This is compiled only in the development version.
2. With {$mode objfpc} only two set sizes: 4 and 32. Thus, either one or the other part of "if" is an unreachable code.
3. With {$mode delphi} this code, with little modification, is wrong, because, as @Thaddy say "The unused bytes are undefined, i.e. also dirty".
Code: Pascal  [Select][+][-]
  1. program Project1;
  2. {$APPTYPE CONSOLE}
  3.  
  4. {-$mode delphi}
  5. {$mode objfpc}
  6.  
  7. {$IFDEF FPC_OBJFPC}generic{$ENDIF}
  8. function Card<T>(const aSetValue: T): Integer;
  9. var
  10.   i: Integer;
  11. begin
  12.   Result := 0;
  13.   for i := 0 to SizeOf(T) - 1 do
  14.     Inc(Result, PopCnt(PByte(@aSetValue)[i]));
  15. end;
  16.  
  17. type
  18.   TSet1 = set of 0..3;
  19.   TSet2 = set of 0..40;
  20.  
  21. var
  22.   set1: TSet1 = [2];
  23.   set2: TSet2 = [4, 9, 23, 40];
  24. begin
  25.   set1 := [2];
  26.   set2 := [4, 9, 23, 40];
  27.  
  28.   Writeln(SizeOf(TSet1));
  29.   Writeln(SizeOf(TSet2));
  30.   Writeln({$IFDEF FPC_OBJFPC}specialize {$ENDIF}Card<TSet1>(set1));
  31.   Writeln({$IFDEF FPC_OBJFPC}specialize {$ENDIF}Card<TSet2>(set2));
  32.   Readln;
  33. end.
Title: Re: What happened to the built in CARD() function?
Post by: PascalDragon on February 18, 2018, 11:36:32 am
Sadly the "Unreachable code" warning can not be suppressed  :'(
1. This is compiled only in the development version.
So? A potential Card() function or intrinsic would also only be part of trunk.
2. With {$mode objfpc} only two set sizes: 4 and 32. Thus, either one or the other part of "if" is an unreachable code.
Yes, I know, but I'm more complaining about that even with {$warn off 6018} around the generic function the compiler doesn't remember that setting when specializing the function which is quite irritating, cause I thought that this should work. Probably a bug I'll have to look at... *sigh*
3. With {$mode delphi} this code, with little modification, is wrong, because, as @Thaddy say "The unused bytes are undefined, i.e. also dirty".
Code: Pascal  [Select][+][-]
  1. program Project1;
  2. {$APPTYPE CONSOLE}
  3.  
  4. {-$mode delphi}
  5. {$mode objfpc}
  6.  
  7. {$IFDEF FPC_OBJFPC}generic{$ENDIF}
  8. function Card<T>(const aSetValue: T): Integer;
  9. var
  10.   i: Integer;
  11. begin
  12.   Result := 0;
  13.   for i := 0 to SizeOf(T) - 1 do
  14.     Inc(Result, PopCnt(PByte(@aSetValue)[i]));
  15. end;
  16.  
  17. type
  18.   TSet1 = set of 0..3;
  19.   TSet2 = set of 0..40;
  20.  
  21. var
  22.   set1: TSet1 = [2];
  23.   set2: TSet2 = [4, 9, 23, 40];
  24. begin
  25.   set1 := [2];
  26.   set2 := [4, 9, 23, 40];
  27.  
  28.   Writeln(SizeOf(TSet1));
  29.   Writeln(SizeOf(TSet2));
  30.   Writeln({$IFDEF FPC_OBJFPC}specialize {$ENDIF}Card<TSet1>(set1));
  31.   Writeln({$IFDEF FPC_OBJFPC}specialize {$ENDIF}Card<TSet2>(set2));
  32.   Readln;
  33. end.
Yes, that definitely simplifies that affair without any unreachable code warning. I was much too focused on the difference between small and large sets plus I wasn't aware that PopCnt had an overload for Byte as I had no need to use that function before.  :-[

Small additional improvement: Unlike Delphi FPC can also make use of "inline" here as long as the method implementation is encountered before it is first called (e.g. in the case above that works).  :D
TinyPortal © 2005-2018