Bit manipulation

From Free Pascal wiki
Revision as of 08:35, 8 November 2012 by Chronos (talk | contribs)


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.

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

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

procedure PutBit(var Value: QWord; Index: Byte; State: Boolean); 
begin
  Value := (Value and ((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 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.

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 array of all states which is of boolean type then set can be also used as bit array. But it require to use $PACKSET and $PACKENUM compiler directives to change size of set. 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 have similar use as in Delphi. It provide 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;