Difference between revisions of "Bit manipulation"

From Lazarus wiki
Jump to navigationJump to search
m (Fixed syntax highlighting)
 
(6 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 +
{{Bit manipulation}}
  
=masked operations=
+
==Masked operations==
  
This is basic general low level approach to handle bit manipulation. Main advantage is that operations can be performed with groups of bits at once. But user have to deal with all operations by itself. Another problem is max range of used values in function parameters. As opposed to C templates using preprocessor there must be separate implemented functions for each ordinal type for best performance.
+
This is a basic low level approach to handle bit manipulation. Main advantage is that operations can be performed with groups of bits at once. But the user has to deal with all operations by himself. Another problem is max range of used values in function parameters. There must be separate implemented functions for each ordinal type for best performance (as opposed to C templates using preprocessor).
  
<syntaxhighlight>
+
<syntaxhighlight lang="pascal">
 
procedure ClearBit(var Value: QWord; Index: Byte);
 
procedure ClearBit(var Value: QWord; Index: Byte);
 
begin
 
begin
   Value := Value and ((1 shl Index) xor High(QWord)));
+
   Value := Value and ((QWord(1) shl Index) xor High(QWord));
 
end;
 
end;
  
 
procedure SetBit(var Value: QWord; Index: Byte);
 
procedure SetBit(var Value: QWord; Index: Byte);
 
begin
 
begin
   Value := Value or (QWord(State) shl Index);
+
   Value:= Value or (QWord(1) shl Index);
 
end;
 
end;
  
procedure PutBit(var Value: QWord; Index: Byte; State: Boolean);  
+
procedure PutBit(var Value: QWord; Index: Byte; State: Boolean);
 
begin
 
begin
   Value := (Value and ((1 shl Index) xor High(QWord))) or (QWord(State) shl Index);
+
   Value := (Value and ((QWord(1) shl Index) xor High(QWord))) or (QWord(State) shl Index);
 
end;
 
end;
  
Line 26: Line 27:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
=bitpacked record=
+
==Bitpacked record==
  
FPC has useful extension which allow to not only byte packing but also bit packing of records. This allow not only to define bit structures using Boolean type or subrange type 0..1 but also n-state or n-bits fields in record as subrange type 0..3 for 2 bits. This conjunction with record case construction combined structure can be defined which allow to access memory as byte or as individual bits.
+
FPC has useful extension which allow not only byte packing but also bit packing of records. This allow not only to define bit structures using Boolean type or subrange type 0..1 but also n-state or n-bits fields in record, e.g. subrange type 0..3 for 2 bits. This conjunction with record case construction combined structure can be defined which allow to access memory as byte or as individual bits.
  
<syntaxhighlight>
+
<syntaxhighlight lang="pascal">
 
TByteBits = bitpacked record
 
TByteBits = bitpacked record
 
   Bit0, Bit1, Bit2, Bit3, Bit4, Bit5, Bit6, Bit7: Boolean;
 
   Bit0, Bit1, Bit2, Bit3, Bit4, Bit5, Bit6, Bit7: Boolean;
Line 37: Line 38:
 
TByteEx = packed record
 
TByteEx = packed record
 
   case Integer of
 
   case Integer of
     0: (ByteAccess: Byte);
+
     0: (ByteAccess: Byte);
 
     1: (BitAccess: TByteBits);
 
     1: (BitAccess: TByteBits);
 
end;
 
end;
Line 51: Line 52:
 
Bitpacking can be controlled using compiler directive [http://www.freepascal.org/docs-html/prog/progsu6.html $BITPACKING]
 
Bitpacking can be controlled using compiler directive [http://www.freepascal.org/docs-html/prog/progsu6.html $BITPACKING]
  
=set=
+
==Set==
  
Because sets are basically array of all states which is of boolean type then set can be also used as bit array. But it require to use [http://www.freepascal.org/docs-html/prog/progsu59.html#x65-640001.1.59 $PACKSET] and [http://www.freepascal.org/docs-html/prog/progsu57.html#x63-620001.1.57 $PACKENUM] compiler directives to change size of set. It has also some limitations on max size of set.
+
Because sets are basically an array of all states which is of boolean type, then set can be also used as bit array. But it requires use of [http://www.freepascal.org/docs-html/prog/progsu61.html $PACKSET] and [http://www.freepascal.org/docs-html/prog/progsu59.html $PACKENUM] compiler directives to change set size. It has also some limitations on max size of set.
  
<syntaxhighlight>
+
<syntaxhighlight lang="pascal">
 
{$packset 1}
 
{$packset 1}
 
{$packenum 1}
 
{$packenum 1}
Line 63: Line 64:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
=TBits=
+
==TBits==
  
This class is part of FPC RTL library contained in Classes unit and have similar use as in Delphi. It provide only some basic methods for bit manipulation.
+
This class is part of FPC RTL library contained in Classes unit and has a similar use as in Delphi. It provides only some basic methods for bit manipulation.
  
<syntaxhighlight>
+
<syntaxhighlight lang="pascal">
 
   TBits = class(TObject)
 
   TBits = class(TObject)
 
   public
 
   public
Line 96: Line 97:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
=Record property and value index=
+
==Record property and value index==
  
Another interesting implementation of bit aligned structure can be used with capabilities of advanced records (FPC 2.6.0+). For all properties you have to use setter and getter which can handle general bit manipulations and set index which is passed to these methods. For more information refer to [http://www.freepascal.org/docs-html/ref/refsu31.html Indexed properties]. Because index is only one therefore it have to be divided to two parameters to describe location and size on bit value. In case of following example offset can by 0..255 and size of value 0..255 bits. Another problem is that you have to ensure that defined structure components will not overlay.
+
Another interesting implementation of bit aligned structure can be used with capabilities of advanced records (FPC 2.6.0+). For all properties you have to use setter and getter which can handle general bit manipulations and set index which is passed to these methods. For more information refer to [http://www.freepascal.org/docs-html/ref/refsu31.html Indexed properties]. Because index is only one, it has to be divided to two parameters to describe location and size on bit value. In case of the following example, the offset can be 0..255 and size of value 0..255 bits. Another problem is that you have to ensure that defined structure components will not overlay.
  
<syntaxhighlight>
+
<syntaxhighlight lang="pascal">
 
{$mode delphi}
 
{$mode delphi}
  
Line 144: Line 145:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 +
[[Category:FPC]]
 +
[[Category:Code Snippets]]
 
[[Category:Tutorials]]
 
[[Category:Tutorials]]

Latest revision as of 01:27, 7 February 2020

Deutsch (de) English (en) français (fr)

Masked operations

This is a basic low level approach to handle bit manipulation. Main advantage is that operations can be performed with groups of bits at once. But the user has to deal with all operations by himself. Another problem is max range of used values in function parameters. There must be separate implemented functions for each ordinal type for best performance (as opposed to C templates using preprocessor).

procedure ClearBit(var Value: QWord; Index: Byte);
begin
  Value := Value and ((QWord(1) shl Index) xor High(QWord));
end;

procedure SetBit(var Value: QWord; Index: Byte);
begin
  Value:=  Value or (QWord(1) shl Index);
end;

procedure PutBit(var Value: QWord; Index: Byte; State: Boolean);
begin
  Value := (Value and ((QWord(1) shl Index) xor High(QWord))) or (QWord(State) shl Index);
end;

function GetBit(Value: QWord; Index: Byte): Boolean;
begin
  Result := ((Value shr Index) and 1) = 1;
end;

Bitpacked record

FPC has useful extension which allow not only byte packing but also bit packing of records. This allow not only to define bit structures using Boolean type or subrange type 0..1 but also n-state or n-bits fields in record, e.g. subrange type 0..3 for 2 bits. This conjunction with record case construction combined structure can be defined which allow to access memory as byte or as individual bits.

TByteBits = bitpacked record
  Bit0, Bit1, Bit2, Bit3, Bit4, Bit5, Bit6, Bit7: Boolean;
end;

TByteEx = packed record
  case Integer of
    0: (ByteAccess: Byte);
    1: (BitAccess: TByteBits);
end;

TSomeBitLevelStructure = bitpacked record
  OneBit: 0..1;
  TwoBits: 0..3;
  FourBits: 0..15;
  EightBits: 0..255
end;

Bitpacking can be controlled using compiler directive $BITPACKING

Set

Because sets are basically an array of all states which is of boolean type, then set can be also used as bit array. But it requires use of $PACKSET and $PACKENUM compiler directives to change set size. It has also some limitations on max size of set.

{$packset 1}
{$packenum 1}

type
  TByteBits = set of (Bit0, Bit1, Bit2, Bit3, Bit4, Bit5, Bit6, Bit7);

TBits

This class is part of FPC RTL library contained in Classes unit and has a similar use as in Delphi. It provides only some basic methods for bit manipulation.

   TBits = class(TObject)
   public
      constructor Create(TheSize : longint = 0); virtual;
      destructor Destroy; override;
      function  GetFSize : longint;
      procedure SetOn(Bit : longint);
      procedure Clear(Bit : longint);
      procedure Clearall;
      procedure AndBits(BitSet : TBits);
      procedure OrBits(BitSet : TBits);
      procedure XorBits(BitSet : TBits);
      procedure NotBits(BitSet : TBits);
      function  Get(Bit : longint) : boolean;
      procedure Grow(NBit : longint);
      function  Equals(Obj : TObject): Boolean; override; overload;
      function  Equals(BitSet : TBits) : Boolean; overload;
      procedure SetIndex(Index : longint);
      function  FindFirstBit(State : boolean) : longint;
      function  FindNextBit : longint;
      function  FindPrevBit : longint;

      { functions and properties to match TBits class }
      function OpenBit: longint;
      property Bits[Bit: longint]: Boolean read get write SetBit; default;
      property Size: longint read FBSize write setSize;
   end;

Record property and value index

Another interesting implementation of bit aligned structure can be used with capabilities of advanced records (FPC 2.6.0+). For all properties you have to use setter and getter which can handle general bit manipulations and set index which is passed to these methods. For more information refer to Indexed properties. Because index is only one, it has to be divided to two parameters to describe location and size on bit value. In case of the following example, the offset can be 0..255 and size of value 0..255 bits. Another problem is that you have to ensure that defined structure components will not overlay.

{$mode delphi}

  TSomeBitStructure = record
  private
    RawData: Word;
    function GetBits(const AIndex: Integer): Integer; inline;
    procedure SetBits(const AIndex: Integer; const AValue: Integer); inline;
  public
    // High byte of index offset, low byte of index is bit count
    property OneBit: Integer index $0001 read GetBits write SetBits;
    property TwoBits: Integer index $0102 read GetBits write SetBits;
    property FourBits: Integer index $0304 read GetBits write SetBits;
    property EightBits: Integer index $0708 read GetBits write SetBits;
  end;

{$OPTIMIZATION ON}
{$OVERFLOWCHECKS OFF}
function TSomeBitStructure.GetBits(const AIndex: Integer): Integer;
var
  Offset: Integer;
  BitCount: Integer;
  Mask: Integer;
begin
  BitCount := AIndex and $FF;
  Offset := AIndex shr 8;
  Mask := ((1 shl BitCount) - 1);
  Result := (RawData shr Offset) and Mask;
end;

procedure TSomeBitStructure.SetBits(const AIndex: Integer; const AValue: Integer);
var
  Offset: Integer;
  BitCount: Integer;
  Mask: Integer;
begin
  BitCount := AIndex and $FF;
  Offset := AIndex shr 8;
  Mask := ((1 shl BitCount) - 1);
  Assert(aValue <= Mask);
  RawData := (RawData and (not (Mask shl Offset))) or (AValue shl Offset);
end;