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

[Ludovic Brenta]

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.

[Robert A Duff]

Dennis Hoppe <dennis...@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

[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

[Randy Brukardt]

"Robert A Duff" <bob...@shell01.TheWorld.com> wrote in message
news:wcc63t4...@shell01.TheWorld.com...

> Dennis Hoppe <dennis...@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.

[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

[Simon Wright]

Ludovic Brenta <lud...@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).

[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

[(see below)]

On 02/06/2008 14:27, in article g20sg4$nkb$1...@aioe.org, "Dennis Hoppe"

<dennis...@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

[Ludovic Brenta]

Dennis Hoppe <dennis...@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.

[Jeffrey R. Carter]

(see below) wrote:
> On 02/06/2008 14:27, in article g20sg4$nkb$1...@aioe.org, "Dennis Hoppe"
> <dennis...@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