Bit operations in Ada

Bit operations in Ada

[Dennis Hoppe]

Hello,

I'm new to Ada and bitwise operations is a new challenge in this realm. 
My objective is to manipulate some bit strings in Ada, especially:

a) addition/subtraction mod 2**n,
b) change bits directly (e.g, via array access)
c) shift operations
d) rotate operations
e) and, xor, not, or

I started with an array of booleans of size 2**n, that provides neat 
access to individual bits by means of an index. Unfortunately, 
addition/subtraction mod 2**n is not supported, but essential for me.

Next, I tried modular types (mod 2**n), but ended up with not having 
direct access to individual bits. My last attempt was to use 
Interfaces.Unsinged_n. It is a solid package that simplifies the usage 
of bitwise operations for me by adding shift and rotate operations. 
Addition modulo n works well, but I have to dispense with direct bit 
access, too.

So, what is coming next? Should I go with Interfaces.Unsinged_n and
provide a suitable function that converts the used type into an array of 
boolean? Maybe, I'm ought to use directly an array of boolean and try to 
convert the array into an Unsigned_n; if required to add two bit-strings.

I'm looking forward for some answers.

Best regards,
   Dennis

Best regards,
   Dennis

Re: Bit operations in Ada

[Ludovic Brenta]

Dennis Hoppe <dennis.hoppe@hoppinet.de> writes:
> Hello,
>
> I'm new to Ada and bitwise operations is a new challenge in this
> realm. My objective is to manipulate some bit strings in Ada,
> especially:
>
> a) addition/subtraction mod 2**n,
> b) change bits directly (e.g, via array access)
> c) shift operations
> d) rotate operations
> e) and, xor, not, or
>
> I started with an array of booleans of size 2**n, that provides neat
> access to individual bits by means of an index. Unfortunately,
> addition/subtraction mod 2**n is not supported, but essential for me.
>
> Next, I tried modular types (mod 2**n), but ended up with not having
> direct access to individual bits. My last attempt was to use
> Interfaces.Unsinged_n. It is a solid package that simplifies the usage
> of bitwise operations for me by adding shift and rotate
> operations. Addition modulo n works well, but I have to dispense with
> direct bit access, too.
>
> So, what is coming next? Should I go with Interfaces.Unsinged_n and
> provide a suitable function that converts the used type into an array
> of boolean? Maybe, I'm ought to use directly an array of boolean and
> try to convert the array into an Unsigned_n; if required to add two
> bit-strings.

IIUC, modular types such as Interfaces.Unsigned_n provide all
operations you need except for direct bit access.

Solution 1:

You can access bits using "and", "or", "not", "**" and "=" like so:

declare
  A : Interfaces.Unsigned_32 := 2#00000000000000000000000000000000#;
  use type Interfaces.Unsigned_32;
  Is_Bit_8_Set : Boolean;
begin
  A := A or 2 ** 5;  -- Set bit 5 to 1
  Is_Bit_8_Set := A and 2 ** 8 /= 0; -- read bit 8
end;

Solution 2:

If this is too difficult or error-prone, you could wrap that into
inlined subprograms like so:

type Bit_Number is range 0 .. 31;

procedure Set (Bit      : in Bit_Number;
               In_Value : in out Interfaces.Unsigned_32;
               To       : in     Boolean) is
   use type Interfaces.Unsigned_32;
begin
   if To = True then
      In_Value := In_Value or 2 ** Bit;
   else
      In_Value := In_Value and not 2 ** Bit;
   end if;
end Set;

function Is_Set (Bit      : in Bit_Number;
                 In_Value : in Interfaces.Unsigned_32) return Boolean is
   use type Interfaces.Unsigned_32;
begin
   return In_Value and 2 ** Bit /= 0;
end Is_Set;

Solution 3:

Another alternative is Unchecked_Conversion:

type Bit_Number is range 0 .. 31;
type Bit_Field is array (Bit_Number) of Boolean;
pragma Pack (Bit_Field);
function To_Bit_Field is
  new Ada.Unchecked_Conversion (Source => Interfaces.Unsigned_32,
                                Target => Bit_Field);
function To_Unsigned_32 is
  new Ada.Unchecked_Conversion (Source => Bit_Field,
                                Target => Interfaces.Unsigned_32);

procedure Set (Bit      : in Bit_Number;
               In_Value : in out Interfaces.Unsigned_32;
               To       : in     Boolean) is
   Field : Bit_Field := To_Bit_Field (In_Value);
begin
   Field (Bit) := To;
   In_Value := To_Unsigned_32 (Field);
end Set;

HTH

-- 
Ludovic Brenta.

Re: Bit operations in Ada

[Robert A Duff]

Dennis Hoppe <dennis.hoppe@hoppinet.de> writes:

> Hello,
>
> I'm new to Ada and bitwise operations is a new challenge in this
> realm. My objective is to manipulate some bit strings in Ada, especially:
>
> a) addition/subtraction mod 2**n,
> b) change bits directly (e.g, via array access)
> c) shift operations
> d) rotate operations
> e) and, xor, not, or

I'm curious why you want to do all these things on the same type.
You say, "My objective is...", but what's the higher-level objective?

Anyway, I would use Unchecked_Conversion between a modular type and a
packed array of Boolean, as suggested by Ludovic Brenta.
Possibly wrapped in useful functions.

Instead of pragma Pack, I would use
"for Bit_Field'Component_Size use 1;".
They both do the same thing, but conceptually, "pack" means
"I want small things, so whole-object operations are faster,
at the expense of per-component operations", whereas the
Component_Size clause means "I depend on the exact bit size
for correctness".

- Bob

Re: Bit operations in Ada

[Jeffrey R. Carter]

Dennis Hoppe wrote:
> 
> I'm new to Ada and bitwise operations is a new challenge in this realm. 
> My objective is to manipulate some bit strings in Ada, especially:
> 
> a) addition/subtraction mod 2**n,
> b) change bits directly (e.g, via array access)
> c) shift operations
> d) rotate operations
> e) and, xor, not, or
> 
> I started with an array of booleans of size 2**n, that provides neat 
> access to individual bits by means of an index. Unfortunately, 
> addition/subtraction mod 2**n is not supported, but essential for me.

Arrays of Boolean certainly seem nice for direct bit access, until you realize 
that the language does not define what bit corresponds to which index value, and 
any such code is completely compiler-dependent and non-portable, and you have to 
experiment with each compiler/platform combination to figure out how it works there.

Modular types require creating a mask and applying it to the value correctly to 
access or change individual bits, but once this is done correctly, the 
operations are reusable and compiler- and platform independent, so I generally 
prefer this approach.

Shift and rotation operations are restricted to the modular types in Interfaces, 
for some reason; I think this decision was probably a mistake. But it's not a 
major impediment to getting things done.

-- 
Jeff Carter
"Beyond 100,000 lines of code you
should probably be coding in Ada."
P. J. Plauger
26

Re: Bit operations in Ada

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message 
news:wcc63t4ejd1.fsf@shell01.TheWorld.com...
> Dennis Hoppe <dennis.hoppe@hoppinet.de> writes:
>
>> I'm new to Ada and bitwise operations is a new challenge in this
>> realm. My objective is to manipulate some bit strings in Ada, especially:
>>
>> a) addition/subtraction mod 2**n,
>> b) change bits directly (e.g, via array access)
>> c) shift operations
>> d) rotate operations
>> e) and, xor, not, or
>
> I'm curious why you want to do all these things on the same type.
> You say, "My objective is...", but what's the higher-level objective?

I agree with Bob. Most of the time, you are better off not doing bit 
operations explicitly at all in Ada: let the compiler do them instead. That 
is to say, use record types and representation clauses to specify the 
structures you need, and let the compiler do all of the work.

For instance, I have a card game evaluation program that starts like this:

    type Suits is (Hearts, Diamonds, Spades, Clubs);
    subtype Red_Suits is Suits range Hearts .. Diamonds;
    subtype Black_Suits is Suits range Spades .. Clubs;

    type Pips is (Empty, Ace, Deuce, Three, Four, Five, Six, Seven, Eight, 
Nine, Ten,
        Jack, Queen, King);

    type Card_Type is record
        Pip  : Pips;
        Suit : Suits;
    end record;
    for Card_Type use record
        Pip at 0 range 0 .. 3;
        Suit at 0 range 4 .. 5;
    end record;
    for Card_Type'Size use 6;

    NO_CARD : constant Card_Type := (Suit => Hearts, Pip => Empty);

    type Card_Array_Type is array (Natural range <>) of Card_Type;
    for Card_Array_Type'Component_Size use 6;

This lets code find out the suit or pip value of a card separately, while 
still providing a convinient way to do operations on a whole card or list of 
cards. And with little waste of space.

(I should point out that the application actually ended up using a different 
way to compress arrays of cards, using knowledge of the starting position to 
save lots more space, and ultimately, Card_Array_Type was changed to use 8 
bit elements for better performance. Beware of premature optimization.)

There are a few cases where you really need to use shifts explicitly 
(encryption comes to mind), but then the need for single bit access is 
non-existent. In those cases, the modular types in Interfaces are your best 
bet.

                              Randy.

Re: Bit operations in Ada (Thank you)

[Dennis Hoppe]

Robert A Duff wrote:
> I'm curious why you want to do all these things on the same type.
> You say, "My objective is...", but what's the higher-level objective?

The higher-level objective is to get involved in cryptoanalysis.


> Anyway, I would use Unchecked_Conversion between a modular type and a
> packed array of Boolean, as suggested by Ludovic Brenta.
> Possibly wrapped in useful functions.
>
> Instead of pragma Pack, I would use
> "for Bit_Field'Component_Size use 1;".
> They both do the same thing, but conceptually, "pack" means
> "I want small things, so whole-object operations are faster,
> at the expense of per-component operations", whereas the
> Component_Size clause means "I depend on the exact bit size
> for correctness".
>
> - Bob

Many thanks for your detailed explanation of possible solutions, 
Ludovic. I would like to also thank the "rest of the group". I stumbled
upon Ada.Unchecked_Conversion, but wasn't sure, if this is the way to
enforce some behaviour in Ada. I guess, I wil give this solution a try
and replace the pack pragma with your approach, Bob.

Best regards,
   Dennis

Re: Bit operations in Ada

[Simon Wright]

Ludovic Brenta <ludovic@ludovic-brenta.org> writes:

> Another alternative is Unchecked_Conversion:
>
> type Bit_Number is range 0 .. 31;
> type Bit_Field is array (Bit_Number) of Boolean;
> pragma Pack (Bit_Field);
> function To_Bit_Field is
>   new Ada.Unchecked_Conversion (Source => Interfaces.Unsigned_32,
>                                 Target => Bit_Field);

Whether this does what you want may depend on whether the machine is
big-endian (eg, SPARC, PowerPC etc) or not (Intel etc).

Re: Bit operations in Ada (endianness)

[Dennis Hoppe]

Hi,

I have another question regarding litte and big-endian. Is there
any way to declare, that the type

   type Bit_Field is array (Bit_Number) of Boolean;

is represented by litte or big-endian? Bit_Number is a generic
paremeter (mod <>). I figured out to set the endianness to
record types, but it does not work for the above array type.

I also wonder, if I can query the operating system via Ada,
which endianness it uses.

Thank you in advance,
   Dennis Hoppe



Simon Wright wrote:
> Ludovic Brenta <ludovic@ludovic-brenta.org> writes:
> 
>> Another alternative is Unchecked_Conversion:
>>
>> type Bit_Number is range 0 .. 31;
>> type Bit_Field is array (Bit_Number) of Boolean;
>> pragma Pack (Bit_Field);
>> function To_Bit_Field is
>>   new Ada.Unchecked_Conversion (Source => Interfaces.Unsigned_32,
>>                                 Target => Bit_Field);
> 
> Whether this does what you want may depend on whether the machine is
> big-endian (eg, SPARC, PowerPC etc) or not (Intel etc).

Re: Bit operations in Ada (endianness)

[(see below)]

On 02/06/2008 14:27, in article g20sg4$nkb$1@aioe.org, "Dennis Hoppe"
<dennis.hoppe@hoppinet.de> wrote:
 
> I also wonder, if I can query the operating system via Ada,
> which endianness it uses.

No need to talk to the OS.
Try something like this:

   -- N.B. not tested as written!

   not_little_endian : exception;

   type i08 is mod 2**8;
   type i64 is mod 2**64;

   type i08_group is array (0..7) of i08;
   for  i08_group'Component_Size use 8;
   for  i08_group'Size use 64;

   the_i64       : i64 := 0;
   the_i08_group : i08_group;
   for the_i08_group'Address use the_i64'Address;
   pragma Import (Ada, the_i08_group);
   --
   the_i08_group(0) := 1;
   if the_i64 /= 1 then
      raise not_little_endian
   end if;
-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk

Re: Bit operations in Ada (endianness)

[Ludovic Brenta]

Dennis Hoppe <dennis.hoppe@hoppinet.de> writes:

> Hi,
>
> I have another question regarding litte and big-endian. Is there
> any way to declare, that the type
>
>   type Bit_Field is array (Bit_Number) of Boolean;
>
> is represented by litte or big-endian? Bit_Number is a generic
> paremeter (mod <>). I figured out to set the endianness to
> record types, but it does not work for the above array type.

The arithmetic on modular types does what you need, so the problem
only arises when using the bit-array representation.  You need to
invert the index explicitly on little-endian machines.

> I also wonder, if I can query the operating system via Ada,
> which endianness it uses.

Look at System.Default_Bit_Order.

So a solution might look like:

generic
   type Bit_Number is mod <>;
package Bit_Fields is
   type Bit_Field is array (Bit_Number) of Boolean;
   function Index (N : Bit_Number) return Bit_Number;
end Bit_Numbers;

with System;
package body Bit_Numbers is
   function Index (N : Bit_Number) return Bit_Number is
   begin
      case System.Default_Bit_Order is
         when System.High_Order_First => return N;
         when System.Low_Order_First  => return Bit_Number'Last - N;
      end case;
   end Index;
end Bit_Numbers;

HTH

-- 
Ludovic Brenta.

Re: Bit operations in Ada (endianness)

[Jeffrey R. Carter]

(see below) wrote:
> On 02/06/2008 14:27, in article g20sg4$nkb$1@aioe.org, "Dennis Hoppe"
> <dennis.hoppe@hoppinet.de> wrote:
>  
>> I also wonder, if I can query the operating system via Ada,
>> which endianness it uses.
> 
> No need to talk to the OS.
> Try something like this:

[large hunk of code omitted]

Or you can just check System.Default_Bit_Order.

Bit order is not technically the same as byte order, but I'm not aware of any 
system on which they're different.

-- 
Jeff Carter
"He didn't get that nose from playing ping-pong."
Never Give a Sucker an Even Break
110