Recent

Author Topic: Some fun with bitmanipulations  (Read 6887 times)

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Some fun with bitmanipulations
« on: October 10, 2019, 10:42:44 am »
I have submitted a patch to add bitwise manipulations on any ordinals in trunk (not accepted yet) but since it can also be used in other versions I separated it into a unit. (attached)
I wrote it to manipulate hardware on a Raspberry Pi, but it is also useful for other purposes.
The code is simple, concise, precise and type safe.
Example:
Code: Pascal  [Select][+][-]
  1. {$mode delphi}{$H+}
  2. uses
  3.   ordinalbits;
  4.  
  5. var a:ShortInt = 0;
  6. begin
  7.   writeln(a.ToBinString);
  8.   a.setbit(7);
  9.   writeln(a.ToBinString);
  10.   writeln(a);                    // should be -128
  11.   a.Togglebit(1);                // should be -126      
  12.   writeln(a.ToBinString);
  13.   writeln(a.testbit(1));         // should be true
  14.   writeln(a);
  15.   a.Togglebit(1);          
  16.   writeln(a.ToBinString);
  17.   writeln(a.testbit(1));         // should be false  
  18.   a.togglebit(7);                // should be zero
  19.   writeln(a.ToBinString);
  20.   writeln(a.testbit(7));         // should be false
  21.   writeln(a);
  22.   writeln(High(TQwordBitIndex)); // should be 63
  23. end.
This specific version works from version 3.0.0.
I think this was really missing. I hope you fillet me if there's something to improve..
It supports all ordinal types for which there is already a type helper, except Booleans, which are strictly speaking also ordinals.
I hope you like the simple code ... :D
« Last Edit: October 10, 2019, 10:45:16 am by Thaddy »
Specialize a type, not a var.

howardpc

  • Hero Member
  • *****
  • Posts: 4144
Re: Some fun with bitmanipulations
« Reply #1 on: October 10, 2019, 11:03:06 am »
Thanks Thaddy.
I found I needed to add a {$RangeChecks off}  to ordinalbits.inc to get your test program to succeed.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Some fun with bitmanipulations
« Reply #2 on: October 10, 2019, 12:10:16 pm »
Is this tested on both little- and big-endian systems?

Memories writing Modula-2 code where different compilers ordered the content of a bitset differently.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Re: Some fun with bitmanipulations
« Reply #3 on: October 10, 2019, 12:14:24 pm »
I found I needed to add a {$RangeChecks off}  to ordinalbits.inc to get your test program to succeed.
That should not be the case. (I am sure about the patch nbr 4) Maybe I made a typo during general porting, I will look into it.
[edit]
Can not reproduce it. Can you give me the line where it fails? Everything is checked with {$rangechecks on}, hence I defined the ranges specifically. That's how I caught a rangecheck during testing the patch. Any help would be appreciated.
Note that if there is an impossible - for the ordinal - index value then it should indeed fail with a rangecheck error. That is intentional.
E.g. on a byte the range is 0..7 and 8 will throw a rangecheck error. Similar for the others.
« Last Edit: October 10, 2019, 12:30:11 pm by Thaddy »
Specialize a type, not a var.

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Re: Some fun with bitmanipulations
« Reply #4 on: October 10, 2019, 12:16:25 pm »
Is this tested on both little- and big-endian systems?

Memories writing Modula-2 code where different compilers ordered the content of a bitset differently.

MarkMLl

The code extends the already available helpers. It assumes no specific bitness.
Specialize a type, not a var.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Some fun with bitmanipulations
« Reply #5 on: October 10, 2019, 12:40:32 pm »
Have the helpers been checked recently? :-)

I used to make a point of running up a SPARC-based system every so often to check this sort of thing, but at present it's not as easy for me as it was a year ago.
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Re: Some fun with bitmanipulations
« Reply #6 on: October 10, 2019, 12:56:08 pm »
I used to have a big endian machine (a powerpc) in fact I still have it, but it is a museum piece occupying attic space on display at my personal museum and is just lying beautiful in its case.... It is pretty dead...
But if the helpers were not sound that would have shown up in bug reports. The code I wrote is fully portable.
« Last Edit: October 10, 2019, 01:00:27 pm by Thaddy »
Specialize a type, not a var.

howardpc

  • Hero Member
  • *****
  • Posts: 4144
Re: Some fun with bitmanipulations
« Reply #7 on: October 10, 2019, 12:58:48 pm »
I found I needed to add a {$RangeChecks off}  to ordinalbits.inc to get your test program to succeed.
Can not reproduce it. Can you give me the line where it fails?
The first call fails (  a.setbit(7); )
This is on 64-bit Linux

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Re: Some fun with bitmanipulations
« Reply #8 on: October 10, 2019, 01:17:38 pm »
The first call fails (  a.setbit(7); )
This is on 64-bit Linux
That should not happen, because of:
Code: Pascal  [Select][+][-]
  1.   // make type safe ranges
  2.   // 0..7
  3.   TByteBitIndex = 0..Pred(SizeOf(Byte) * 8);
  4.   TShortIntBitIndex = TByteBitIndex;
Specialize a type, not a var.

howardpc

  • Hero Member
  • *****
  • Posts: 4144
Re: Some fun with bitmanipulations
« Reply #9 on: October 10, 2019, 01:20:26 pm »
Whether or not it "should" I am simply reporting that it does.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Some fun with bitmanipulations
« Reply #10 on: October 10, 2019, 01:32:56 pm »
I used to have a big endian machine (a powerpc) in fact I still have it, but it is a museum piece occupying attic space on display at my personal museum and is just lying beautiful in its case.... It is pretty dead...
But if the helpers were not sound that would have shown up in bug reports. The code I wrote is fully portable.

I've got a 1U SPARC here onto which I've finally managed to get the current Debian, but I can't remember (and have very limited time to check) what the situation is regarding FPC since the OS is now 64-bit and I haven't a clue how good its multiarch support is.

For a substantial number of years I had an adequate number of running SPARC/PPC/ARM systems running Lazarus/FPC natively, and I can assure you that problems /do/ show up due to unexpected endianness dependency and- more urgently- operations which the OS thinks should be word-aligned.

I'll try to fire the SPARC up and see where I get to, but I've got rather a lot of problems at the moment.
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Some fun with bitmanipulations
« Reply #11 on: October 10, 2019, 01:43:33 pm »
a.setbit(7) evaluates to ShortInt := ShortInt or 128.
This give a range check error, not only on 64-bit platforms b.t.w.

Try to compile this:

Code: Pascal  [Select][+][-]
  1. var
  2.   a: shortint = 0 or 128;

This gives: Error: range check error while evaluating constants (128 must be between -128 and 127)

You also cannot do Integer.SetBit(31), but that gives a compile time error:  range check error while evaluating constants (2147483648 must be between -2147483648 and 2147483647)

Bart
« Last Edit: October 10, 2019, 01:51:12 pm by Bart »

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Some fun with bitmanipulations
« Reply #12 on: October 10, 2019, 02:32:07 pm »
Code: Pascal  [Select][+][-]
  1. {$mode delphi}{$H+}
  2. {$R+}
  3. uses
  4.   sysutils, ordinalbits;
  5.  
  6. var a:ShortInt = 0;
  7.  
  8.     HighB: TByteBitIndex = High(TByteBitIndex);             B: Byte = 0;
  9.     HighSh: TShortIntBitIndex = High(TShortIntBitIndex);    Sh: ShortInt = 0;
  10.     HighW: TWordBitIndex = High(TWordBitIndex);             W: Word = 0;
  11.     HighSm: TSmallIntBitIndex = High(TSmallIntBitIndex);    Sm: SmallInt = 0;
  12.     HighC: TCardinalBitIndex = High(TCardinalBitIndex);     C: Cardinal = 0;
  13.     HighLI: TIntegerBitIndex = High(TIntegerBitIndex);      LI: Integer = 0;
  14.     HighNU: TNativeUIntBitIndex = High(TNativeUIntBitIndex);NU: NativeUInt = 0;
  15.     HighNI: TNativeIntBitIndex = High(TNativeIntBitIndex);  NI: NativeInt = 0;
  16.     HighQ: TQwordBitIndex = High(TQwordBitIndex);           Q: QWORD = 0;
  17.     HighI64: TInt64BitIndex = High(TInt64BitIndex);         I64: Int64 = 0;
  18.  
  19.  
  20. begin
  21.   {$ifdef cpu32}
  22.   writeln('Compiled for 32-bit');
  23.   {$endif}
  24.   {$ifdef cpu64}
  25.   writeln('Compiled for 64-bit');
  26.   {$endif}
  27.  
  28.   try
  29.     write(format('Byte.SetBit(%.2d)      : ',[HighB]));
  30.     B.SetBit(HighB);
  31.     writeln(format('OK: [%s] ',[B.ToBinString]));
  32.   except
  33.     on e: exception do writeln(e.message);
  34.   end;
  35.  
  36.   try
  37.     write(format('ShortInt.SetBit(%.2d)  : ',[HighSh]));
  38.     Sh.SetBit(HighSh);
  39.     writeln(format('OK: [%s] ',[Sh.ToBinString]));
  40.   except
  41.     on e: exception do writeln(e.message);
  42.   end;
  43.  
  44.   try
  45.     write(format('Word.SetBit(%d)      : ',[HighW]));
  46.     W.SetBit(HighW);
  47.     writeln(format('OK: [%s] ',[W.ToBinString]));
  48.   except
  49.     on e: exception do writeln(e.message);
  50.   end;
  51.  
  52.   try
  53.     write(format('SmallInt.SetBit(%d)  : ',[HighSm]));
  54.     Sm.SetBit(HighSm);
  55.     writeln(format('OK: [%s] ',[Sm.ToBinString]));
  56.   except
  57.     on e: exception do writeln(e.message);
  58.   end;
  59.  
  60.   try
  61.     write(format('Cardinal.SetBit(%d)  : ',[HighC]));
  62.     C.SetBit(HighC);
  63.     writeln(format('OK: [%s] ',[C.ToBinString]));
  64.   except
  65.     on e: exception do writeln(e.message);
  66.   end;
  67.  
  68.   try
  69.     write(format('LongInt.SetBit(%d)   : ',[HighLI]));
  70.     LI.SetBit(HighLI);                              //LI.SetBit(31) gives compiletime rangecheck error
  71.     writeln(format('OK: [%s] ',[LI.ToBinString]));
  72.   except
  73.     on e: exception do writeln(e.message);
  74.   end;
  75.  
  76.   try
  77.     write(format('NativeUint.SetBit(%d): ',[HighNU]));
  78.     NU.SetBit(HighNU);
  79.     writeln(format('OK: [%s] ',[NU.ToBinString]));
  80.   except
  81.     on e: exception do writeln(e.message);
  82.   end;
  83.  
  84.   try
  85.     write(format('NativeInt.SetBit(%d) : ',[HighNI]));
  86.     NI.SetBit(HighNI);                              //NI.SetBit(31) gives compiletime rangecheck error in 32-bit mode, NI.SetBit(63) is allowed in 64-bit
  87.     writeln(format('OK: [%s] ',[NI.ToBinString]));
  88.   except
  89.     on e: exception do writeln(e.message);
  90.   end;
  91.  
  92.   try
  93.     write(format('QWORD.SetBit(%d)     : ',[HighQ]));
  94.     Q.SetBit(HighQ);
  95.     writeln(format('OK: [%s] ',[Q.ToBinString]));
  96.   except
  97.     on e: exception do writeln(e.message);
  98.   end;
  99.  
  100.   try
  101.     write(format('Int64.SetBit(%d)     : ',[HighI64]));
  102.     I64.SetBit(HighI64);
  103.     writeln(format('OK: [%s] ',[I64.ToBinString]));
  104.   except
  105.     on e: exception do writeln(e.message);
  106.   end;
  107. end.

Output (on Windows):
Code: [Select]
Compiled for 32-bit
Byte.SetBit(07)      : OK: [10000000]
ShortInt.SetBit(07)  : Range check error
Word.SetBit(15)      : OK: [1000000000000000]
SmallInt.SetBit(15)  : Range check error
Cardinal.SetBit(31)  : OK: [10000000000000000000000000000000]
LongInt.SetBit(31)   : OK: [10000000000000000000000000000000]
NativeUint.SetBit(31): OK: [10000000000000000000000000000000]
NativeInt.SetBit(31) : OK: [10000000000000000000000000000000]
QWORD.SetBit(63)     : OK: [1000000000000000000000000000000000000000000000000000000000000000]
Int64.SetBit(63)     : OK: [1000000000000000000000000000000000000000000000000000000000000000]

C:\Users\Bart\LazarusProjecten\bugs\Console\ordinalbits>bits
Compiled for 64-bit
Byte.SetBit(07)      : OK: [10000000]
ShortInt.SetBit(07)  : Range check error
Word.SetBit(15)      : OK: [1000000000000000]
SmallInt.SetBit(15)  : Range check error
Cardinal.SetBit(31)  : OK: [10000000000000000000000000000000]
LongInt.SetBit(31)   : OK: [10000000000000000000000000000000]
NativeUint.SetBit(63): OK: [1000000000000000000000000000000000000000000000000000000000000000]
NativeInt.SetBit(63) : OK: [1000000000000000000000000000000000000000000000000000000000000000]
QWORD.SetBit(63)     : OK: [1000000000000000000000000000000000000000000000000000000000000000]
Int64.SetBit(63)     : OK: [1000000000000000000000000000000000000000000000000000000000000000]

Notice that at runtime you can do Integer.SetBit(31), but at compiletime this is not allowed.
The same for NativeInt in 32-bit mode.

(I would have expected that this problem would arise for all of the unsigned ordinals.)

Wondering what will happen on 16-bit DOS.

Bart

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Some fun with bitmanipulations
« Reply #13 on: October 10, 2019, 03:23:26 pm »
Casting everything to an unsigned type might be a solution?

In ordinalbits.pas:
Code: Pascal  [Select][+][-]
  1. implementation
  2. {$MACRO ON}
  3. // byte
  4. {$define TORDINALBITHELPER:=TByteBitHelper}
  5. {$define TORDINALBITINDEX:=TByteBitIndex}
  6. {$define TORDINALTYPE:=byte}
  7. {$define TORDINALUNSIGNEDTYPE:=byte}
  8. {$i ordinalbits.inc}
  9. // shortint
  10. {$define TORDINALBITHELPER:=TShortIntBitHelper}
  11. {$define TORDINALBITINDEX:=TShortIntBitIndex}
  12. {$define TORDINALTYPE:=ShortInt}
  13. {$define TORDINALUNSIGNEDTYPE:=byte}
  14. {$i ordinalbits.inc}
  15. // word
  16. {$define TORDINALBITHELPER:=TWordBitHelper}
  17. {$define TORDINALBITINDEX:=TWordBitIndex}
  18. {$define TORDINALTYPE:=Word}
  19. {$define TORDINALUNSIGNEDTYPE:=Word}
  20. {$i ordinalbits.inc}
  21. // smallint
  22. {$define TORDINALBITHELPER:=TSmallIntBitHelper}
  23. {$define TORDINALBITINDEX:=TSmallIntBitIndex}
  24. {$define TORDINALTYPE:=SmallInt}
  25. {$define TORDINALUNSIGNEDTYPE:=Word}
  26. {$i ordinalbits.inc}
  27. // cardinal
  28. {$define TORDINALBITHELPER:=TCardinalBitHelper}
  29. {$define TORDINALBITINDEX:=TCardinalBitIndex}
  30. {$define TORDINALTYPE:=Cardinal}
  31. {$define TORDINALUNSIGNEDTYPE:=Cardinal}
  32. {$i ordinalbits.inc}
  33. // integer
  34. {$define TORDINALBITHELPER:=TIntegerBitHelper}
  35. {$define TORDINALBITINDEX:=TIntegerBitIndex}
  36. {$define TORDINALTYPE:=integer}
  37. {$define TORDINALUNSIGNEDTYPE:=DWORD}
  38. {$i ordinalbits.inc}
  39. // nativeuInt
  40. {$define TORDINALBITHELPER:=TNativeUintBitHelper}
  41. {$define TORDINALBITINDEX:=TNativeUintBitIndex}
  42. {$define TORDINALTYPE:=NativeUint}
  43. {$define TORDINALUNSIGNEDTYPE:=NativeUint}
  44. {$i ordinalbits.inc}
  45. // nativeint
  46. {$define TORDINALBITHELPER:=TNativeIntBitHelper}
  47. {$define TORDINALBITINDEX:=TNativeIntBitIndex}
  48. {$define TORDINALTYPE:=NativeInt}
  49. {$define TORDINALUNSIGNEDTYPE:=NativeUInt}
  50. {$i ordinalbits.inc}
  51. // qword
  52. {$define TORDINALBITHELPER:=TQwordBitHelper}
  53. {$define TORDINALBITINDEX:=TQwordBitIndex}
  54. {$define TORDINALTYPE:=Qword}
  55. {$define TORDINALUNSIGNEDTYPE:=QWORD}
  56. {$i ordinalbits.inc}
  57. // int64
  58. {$define TORDINALBITHELPER:=TInt64BitHelper}
  59. {$define TORDINALBITINDEX:=TInt64BitIndex}
  60. {$define TORDINALTYPE:=Int64}
  61. {$define TORDINALUNSIGNEDTYPE:=QWORD}
  62. {$i ordinalbits.inc}
  63. end.  

And then ordinalbits.inc:
Code: Pascal  [Select][+][-]
  1. // note that all the typecasts are necessary when doing bit manipulations
  2. // also note a boolean cast for testbit (faster code) does not work for
  3. // all types, because of the fixed size of boolean and a subsequent
  4. // rangecheck error, hence compare to zero and with the correct type.
  5. Function TORDINALBITHELPER.ToBinString: string; inline;
  6. begin
  7.   Result:=BinStr(Self,SizeOf(TORDINALTYPE)*8);
  8. end;
  9.  
  10. Procedure TORDINALBITHELPER.SetBit(const index: TORDINALBITINDEX); inline;
  11. begin
  12.   TORDINAlUNSIGNEDTYPE(Self) := TORDINALUNSIGNEDTYPE(Self) or (TORDINALUNSIGNEDTYPE(1) shl index);
  13. end;
  14.  
  15. Procedure TORDINALBITHELPER.ClearBit(const index: TORDINALBITINDEX); inline;
  16. begin
  17.   TORDINALUNSIGNEDTYPE(Self):=TORDINALUNSIGNEDTYPE(Self) and not (TORDINALUNSIGNEDTYPE(1) shl index);
  18. end;
  19.  
  20. Procedure TORDINALBITHELPER.ToggleBit(const index: TORDINALBITINDEX); inline;
  21. begin
  22.   TORDINALUNSIGNEDTYPE(Self) := TORDINALUNSIGNEDTYPE(Self) xor (TORDINALUNSIGNEDTYPE(1) shl index);
  23. end;
  24.  
  25. Function TORDINALBITHELPER.TestBit(const Index: TORDINALBITINDEX):Boolean; inline;
  26. begin
  27.   Result := TORDINALUNSIGNEDTYPE(Self) and (TORDINALUNSIGNEDTYPE(1) shl index) <> 0;
  28. end;

Bart

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Re: Some fun with bitmanipulations
« Reply #14 on: October 10, 2019, 04:06:09 pm »
Still all of that should have shown up in my tests (with trunk), but the unsigned solution is a good alternative.
One remark though, is that a ShortInt value anded with 128 (which is a unsigned byte value or wider and NOT a shortint value) is maybe propagated by the compiler to the next higher type... 128 is certainly not shortint.... It should be interpreted as 0 or expanded result..or a rangecheck error..
Second: is it possible that sysutils is compiled with {$R-} ? That would explain my tests.. (Will check that)
The suggested solution *should* not be necessary, since all overloads are well within the range for the type.
Did you check with a recent trunk? I still can't reproduce the issue, so may be only 3.0.4 and 3.2.0?

Anyway: the unsigned solution is not a matter of great importance to me, so I will apply it.

Thanks all for the help! It shows it is considered  useful  :)
« Last Edit: October 10, 2019, 04:23:51 pm by Thaddy »
Specialize a type, not a var.

 

TinyPortal © 2005-2018