Bitmanipulation in Ada

Bitmanipulation in Ada

[Bernd Specht]

Hi, 

i have some questions regarding bitmanipulations:

1. I found bitwise "and", "or" and "xor" operations, but as far as I 
understand they are applicable only for modular types or packed boolean 
arrays. Is this correct?


2. I did not found shift and rotate operations. Did I miss something or are 
there really none?


3. When I want treat a value both as an integer and as a boolean array, how 
can i do this? In pascal I would use a tagless record like 

TYPE ov is record
  case boolean of
    true : i : integer;
    false  : byte_array;
  end;
  end;

Such overlay structures are not valid with Ada, so what do instead?

thanks

Re: Bitmanipulation in Ada

[Ludovic Brenta]

 (Bernd Specht) writes:
> Hi, 
>
> i have some questions regarding bitmanipulations:
>
> 1. I found bitwise "and", "or" and "xor" operations, but as far as I 
> understand they are applicable only for modular types or packed boolean 
> arrays. Is this correct?

Yes.

> 2. I did not found shift and rotate operations. Did I miss something or are 
> there really none?

These operations are usually carried out in hardware for certain sizes
of modular integers only.  Consequently, these operations are defined
in package Interfaces (see RM 3.5.4(31) and B.2).  Package Interfaces
defines the following subprograms:

   function Shift_Left  (Value  : Unsigned_n;
                         Amount : Natural) return Unsigned_n;
   function Shift_Right (Value  : Unsigned_n;
                         Amount : Natural) return Unsigned_n;
   function Shift_Right_Arithmetic (Value  : Unsigned_n;
                                    Amount : Natural)
     return Unsigned_n;
   function Rotate_Left  (Value  : Unsigned_n;
                          Amount : Natural) return Unsigned_n;
   function Rotate_Right (Value  : Unsigned_n;
                          Amount : Natural) return Unsigned_n;

Each compiler provides Unsigned_n types for various values of n
corresponding to natural sizes of the target hardware.

Doing bit rotations in the general case does not necessarily make
sense, because the modulo of the type may not be a power of two.

> 3. When I want treat a value both as an integer and as a boolean array, how 
> can i do this? In pascal I would use a tagless record like 
>
> TYPE ov is record
>   case boolean of
>     true : i : integer;
>     false  : byte_array;
>   end;
>   end;
>
> Such overlay structures are not valid with Ada, so what do instead?

Have you considered a variant record?

type Ov (T : Boolean) is record
   case T is
      when True => I : Integer;
      when False => B : Byte_Array;
   end T;
end record;

If what you really want is to convert an integer to a byte array, use
Unchecked_Conversion:

with Ada.Unchecked_Conversion;
procedure P is
   type Byte_Array is array (1 .. Integer'Size) of Boolean;
   pragma Pack (Byte_Array);
   for Byte_Array'Size use Integer'Size;
   function To_Byte_Array is new
      Ada.Unchecked_Conversion (Source => Integer, Target => Byte_Array);
   I : Integer := 42;
   B : Byte_Array := To_Byte_Array (I);
begin
   null;
end P;


-- 
Ludovic Brenta.

Re: Bitmanipulation in Ada

[Bernd Specht]

Ludovic Brenta <ludovic.brenta@insalien.org> wrote in
news:87k6vwrwym.fsf@insalien.org: 

>  (Bernd Specht) writes:
>> Hi, 

Thanks.

>> 2. I did not found shift and rotate operations. Did I miss something
>> or are there really none? 
> 
> These operations are usually carried out in hardware for certain sizes
> of modular integers only.  Consequently, these operations are defined
> in package Interfaces (see RM 3.5.4(31) and B.2).  Package Interfaces
> defines the following subprograms:
> 
>    function Shift_Left  (Value  : Unsigned_n;
>                          Amount : Natural) return Unsigned_n;
>    function Shift_Right (Value  : Unsigned_n;
>                          Amount : Natural) return Unsigned_n;
>    function Shift_Right_Arithmetic (Value  : Unsigned_n;
>                                     Amount : Natural)
>      return Unsigned_n;
>    function Rotate_Left  (Value  : Unsigned_n;
>                           Amount : Natural) return Unsigned_n;
>    function Rotate_Right (Value  : Unsigned_n;
>                           Amount : Natural) return Unsigned_n;


Ok. Is there a reason why it is not (directly) available in the language 
itself like the and/or/xor or the >> and << in C?
 
>> 3. When I want treat a value both as an integer and as a boolean
>> array, how can i do this? In pascal I would use a tagless record like 
>> Such overlay structures are not valid with Ada, so what do instead?
> 
> Have you considered a variant record?
> 
> type Ov (T : Boolean) is record
>    case T is
>       when True => I : Integer;
>       when False => B : Byte_Array;
>    end T;
> end record;

I found, that (at least GNAT) different storage locations are used for i and 
b.
 
> If what you really want is to convert an integer to a byte array, use
> Unchecked_Conversion:

OK, but this would result in an assignment operation (a memory move on 
maschine code level). What I want is a real "overlay" (same storage location 
used for both), so reading the value would not need extra instructions.
 

Re: Bitmanipulation in Ada

[(see below)]

On 18/8/04 9:37 pm, in article
Xns9549E5E9CFFB1BerndSpechgmxcom@151.189.20.10, "Bernd Specht"
<Bernd.Specht@gmx.com> wrote:

> 3. When I want treat a value both as an integer and as a boolean array, how
> can i do this? In pascal I would use a tagless record like
> 
> TYPE ov is record
> case boolean of
>   true : i : integer;
>   false  : byte_array;
> end;
> end;
> 
> Such overlay structures are not valid with Ada, so what do instead?

Such usages are not valid in (ISO Standard) Pascal either,
but you don't let that stop you. 8-)

-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk

Re: Bitmanipulation in Ada

[Ludovic Brenta]

 (Bernd Specht) writes:
> Ok. Is there a reason why it is not (directly) available in the language 
> itself like the and/or/xor or the >> and << in C?

Yes.  As I said, in Ada, modular types do not necessarily have a power
of two as their modulo; nor do they necessarily have a "natural" size.
You could have for example:

type T is mod 17;
for T'Size use 43;

Since C only has modular types, and since all types in C have
"natural" sizes, it makes sense to provide the shift and rotate
operations in the language.

>> If what you really want is to convert an integer to a byte array, use
>> Unchecked_Conversion:
>
> OK, but this would result in an assignment operation (a memory move on 
> maschine code level). What I want is a real "overlay" (same storage location 
> used for both), so reading the value would not need extra instructions.

Ah, OK.

procedure P is
   type Byte_Array is array (1 .. Integer'Size) of Boolean;
   pragma Pack (Byte_Array);
   for Byte_Array'Size use Integer'Size;
   I : Integer := 42;
   B : Byte_Array;

   -- Specify that B and I are at the same address
   for B'Address use I'Address;
begin
   for J in B'Range loop
      Ada.Text_IO.Put_Line (Boolean'Image (B (J)));
   end loop;
end P;

HTH

-- 
Ludovic Brenta.

Re: Bitmanipulation in Ada

[Ed Falis]

On 18 Aug 2004 21:10:30 GMT, Bernd Specht <Bernd.Specht@gmx.com> wrote:

> Ok. Is there a reason why it is not (directly) available in the language
> itself like the and/or/xor or the >> and << in C?

Doesn't really matter, since most implementations directly generate the  
code for these (they treat them as "instrinsic").

>

> OK, but this would result in an assignment operation (a memory move on
> maschine code level). What I want is a real "overlay" (same storage  
> location
> used for both), so reading the value would not need extra instructions.

In all implementations of which I'm aware (and I've been in the Ada  
compiler business for over 20 years) no code would be generated for an  
unchecked conversion where the source and target have the same size.

You sound like you're looking for things to complain about, by the way.

- Ed



-- 
"When I was a kid, I wanted to grow up to be a wise man. Somehow, I just  
turned out to be a wise guy".

Re: Bitmanipulation in Ada

[Martin Dowie]

Bernd Specht wrote:
> 2. I did not found shift and rotate operations. Did I miss something
> or are there really none?

Check out package "Interfaces" they are all there - as are some common
predefined types.

> 3. When I want treat a value both as an integer and as a boolean
> array, how can i do this? In pascal I would use a tagless record like

Assuming you had a _really_ good reason to need to think of the data in both
terms, you have a number of options:

1) Unchecked_Conversion;

procedure Foo (Y : Unsigned_8) is
   procedure To_Array_8 is
      new Ada.Unchecked_Conversion (Unsigned_8, Array_8);
   X : Array_8 := To_Array_8 (Y);
begin
...

2) Address clause to 'overlay' 2 variables at the same address;

procedure Foo (Y : Unsigned_8) is
   X : Array_8;
   for X'Address use Y'Address;
begin
...

3) Variant record with a representation clause;

type Variant (Is_Array : Boolean := False) is
record
   case Is_Array is
      when False =>
         U : Unsigned_8;
      when True =>
         A : Array_8;
   end case;
end record;
for Variant use
record
   U at 0 range 0 .. 7;
   A at 0 range 0 .. 7;
end record;

This will leave it to the compiler where to put "Is_Array"

There are pros and cons to each - I'd rather use Ada.Unchecked_Conversion to
make it explicit that I'm switching representations.

Cheers

-- Martin

Re: Bitmanipulation in Ada

[Martin Dowie]

(see below) wrote:
> On 18/8/04 9:37 pm, in article
> Xns9549E5E9CFFB1BerndSpechgmxcom@151.189.20.10, "Bernd Specht"
> <Bernd.Specht@gmx.com> wrote:
>
>> 3. When I want treat a value both as an integer and as a boolean
>> array, how can i do this? In pascal I would use a tagless record like
>>
>> TYPE ov is record
>> case boolean of
>>   true : i : integer;
>>   false  : byte_array;
>> end;
>> end;
>>
>> Such overlay structures are not valid with Ada, so what do instead?
>
> Such usages are not valid in (ISO Standard) Pascal either,
> but you don't let that stop you. 8-)

Where does the standard deem this "not valid" in Ada?

Re: Bitmanipulation in Ada

[Björn Persson]

Martin Dowie wrote:

> 2) Address clause to 'overlay' 2 variables at the same address;
> 
> procedure Foo (Y : Unsigned_8) is
>    X : Array_8;
>    for X'Address use Y'Address;
> begin
> ....

Y should probably be declared "in out" here.

> 3) Variant record with a representation clause;
> 
> type Variant (Is_Array : Boolean := False) is
> record
>    case Is_Array is
>       when False =>
>          U : Unsigned_8;
>       when True =>
>          A : Array_8;
>    end case;
> end record;
> for Variant use
> record
>    U at 0 range 0 .. 7;
>    A at 0 range 0 .. 7;
> end record;

If you turn off the discriminant check.

-- 
Björn Persson                              PGP key A88682FD
                    omb jor ers @sv ge.
                    r o.b n.p son eri nu

Re: Bitmanipulation in Ada

[Jeffrey Carter]

Bernd Specht wrote:
> Ok. Is there a reason why it is not (directly) available in the
> language itself like the and/or/xor or the >> and << in C?

Shift and rotate operations only make sense for types that are a
"natural" size for the underlying hardware. Those are the only kind of
integer types available in C. Since Ada also provides user-defined
numeric types, which may not be a natural size for the hardware, these
can only be provided for types which are a natural size.

> OK, but this would result in an assignment operation (a memory move
> on maschine code level). What I want is a real "overlay" (same
> storage location used for both), so reading the value would not need
> extra instructions.

That may be what you want. What a software engineer wants is the 
clearest software that meets the requirements. Unchecked_Conversion will 
almost always provide this.

In many cases, Unchecked_Conversion will generate no code, and need not 
involve an assignment. In well designed software, the part(s) of the 
software that deals with values as an integer and those that deal with 
them as bit arrays will be kept separate. So you do something like:

with Ada.Unchecked_Conversion;
procedure Deals_2_Ways is
    type Bit_Array is array (1 .. Integer'Size) of Boolean;
    pragma Pack (Bit_Array);
    for Bit_Array'Component_Size use 1;
    for Bit_Array'Size use Integer'Size;

    function Get return Integer is separate;

    Value : Integer := Get;

    procedure Deal_With_Integer (Value : in out Integer) is separate;
    procedure Deal_With_Bit_Array (Value : in out Bit_Array) is separate;

    function To_Bit is new Ada.Unchecked_Conversion
    (Source => Integer, Target => Bit_Array);
begin -- Deals_2_Ways
    Deal_With_Integer (Value => Value);
    Deal_With_Bit_Array (Value => To_Bit (Value) );
end Deals_2_Ways;

-- 
Jeff Carter
"I'm particularly glad that these lovely children were
here today to hear that speech. Not only was it authentic
frontier gibberish, it expressed a courage little seen
in this day and age."
Blazing Saddles
88

Re: Bitmanipulation in Ada

[Egil H. H�vik]

"Martin Dowie" <martin.dowie@btopenworld.com> wrote in message
news:cg0j57$bal$1@sparta.btinternet.com...
> Bernd Specht wrote:
<snip>
>
> 2) Address clause to 'overlay' 2 variables at the same address;
>
> procedure Foo (Y : Unsigned_8) is
>    X : Array_8;

You would probably want a "pragma Import (Ada, X)" here, to suppress any
default initializations...  B.1(24)


>    for X'Address use Y'Address;
> begin
> ...



~egilhh

Re: Bitmanipulation in Ada

[(see below)]

On 18/8/04 10:56 pm, in article cg0j9n$bkq$1@sparta.btinternet.com, "Martin
Dowie" <martin.dowie@btopenworld.com> wrote:

...
>>> TYPE ov is record
>>> case boolean of
>>>   true : i : integer;
>>>   false  : byte_array;
>>> end;
>>> end;
>>> 
>>> Such overlay structures are not valid with Ada, so what do instead?
>> 
>> Such usages are not valid in (ISO Standard) Pascal either,
>> but you don't let that stop you. 8-)
> 
> Where does the standard deem this "not valid" in Ada?

I'm not sure who Martin is asking, nor what about; but:

If "this" means Pascal-style tagless variant records, see the RM, section
3.8.1 "Variant Parts and Discrete Choices", where no such syntax appears.

If "this" means assigning a value of type T1 to a field F1 of a variant V1
of a record structure R and retrieving a value of type T2 from a field F2 of
a variant V2, "R.F1 := T1_Val; ...; T2_var := R.F2" then:

 (a) If the variant has not been changed from V1 to V2, then a discriminant
     check on access to F2 will raise a Constraint_Error.
 (b) If the variant has been changed to V2, then F2 has been given a new
     value and so does not retain the value placed in F1.
 (c) It cannot even be assumed that F1 and F2 coincide, unless a
      representation specification can be used to that effect.

(I suspect Martin knows all this perfectly well, so I wonder why he asks.)
-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk

Re: Bitmanipulation in Ada

[Martin Dowie]

"(see below)" <byaldnif@blueyonder.co.uk> wrote in message
news:BD4A8509.96EBD%
> (I suspect Martin knows all this perfectly well, so I wonder why he asks.)

Bill, sorry I misread the original email (not even yours!) and had magic-ed
in a discriminent in the Pascal version - that'll teach me to write to
newsgroups at 11pm!

Cheers

-- Martin

Re: Bitmanipulation in Ada

[Bernd Specht]

"Ed Falis" <falis@verizon.net> wrote in news:opscx5geap5afhvo@localhost:

> On 18 Aug 2004 21:10:30 GMT, Bernd Specht <Bernd.Specht@gmx.com> wrote:
> 
>> OK, but this would result in an assignment operation (a memory move on
>> maschine code level). What I want is a real "overlay" (same storage  
>> location used for both), so reading the value would not need extra
>> instructions. 
> 
> In all implementations of which I'm aware (and I've been in the Ada  
> compiler business for over 20 years) no code would be generated for an  
> unchecked conversion where the source and target have the same size.

Sorry, but that's absolutely *nonsense*

Have a look at Ludovics code:

with Ada.Unchecked_Conversion;
procedure P is
   type Byte_Array is array (1 .. Integer'Size) of Boolean;
   pragma Pack (Byte_Array);
   for Byte_Array'Size use Integer'Size;
   function To_Byte_Array is new
      Ada.Unchecked_Conversion (Source => Integer, Target => Byte_Array);
   I : Integer := 42;
   B : Byte_Array := To_Byte_Array (I);
begin
   null;
end P;


You agree that "I" and "B" are located at different adresses? Do you 
*really* think that you need *no* code to move data from one address to 
another??? That's wrong! You need at least *one* instruction, and this can 
be time consuming - especially if the data is missaligned and/or the code 
runs in a multiprocessor environment.


> You sound like you're looking for things to complain about, by the way.

Sorry - but you seem to be a blatherer.


>  (and I've been in the Ada compiler business for over 20 years) 

Wow! Be happy.


> 
> - Ed

*plonk*

Re: Bitmanipulation in Ada

[Bernd Specht]

Jeffrey Carter <spam@spam.com> wrote in news:wSSUc.27249$9Y6.977
@newsread1.news.pas.earthlink.net:

> Bernd Specht wrote:
> That may be what you want. What a software engineer wants is the 
> clearest software that meets the requirements. Unchecked_Conversion will 
> almost always provide this.

Sure.

 
> In many cases, Unchecked_Conversion will generate no code, and need not 
> involve an assignment. In well designed software, the part(s) of the 
> software that deals with values as an integer and those that deal with 
> them as bit arrays will be kept separate. So you do something like:

Always? What do you think about bitscrambling software which has to treat 
data alternating as bitvector and as integer value in a loop like this (not 
exeactly this for securitity reasons):

...
loop
  declare
    x : boolean;
  begin
     x := b(k);
     b(k) := b(32 - k);
     b (32 - k) := x;
     I := I * prime1 mod prime2;
  end;
end loop;


Can you find an equivalent algorithm where you can separate the bit-ops and 
the integer-ops?

Re: Bitmanipulation in Ada

[Ed Falis]

On 19 Aug 2004 17:30:17 GMT, Bernd Specht <Bernd.Specht@gmx.com> wrote

> EF wrote:
>> In all implementations of which I'm aware (and I've been in the Ada
>> compiler business for over 20 years) no code would be generated for an
>> unchecked conversion where the source and target have the same size.
>
> Sorry, but that's absolutely *nonsense*

> You agree that "I" and "B" are located at different adresses? Do you
> *really* think that you need *no* code to move data from one address to
> another??? That's wrong! You need at least *one* instruction, and this  
> can
> be time consuming - especially if the data is missaligned and/or the code
> runs in a multiprocessor environment.

I believe your original complaint was about cost of conversion, not of  
assignment - and this is what I was responding to.  The conversion costs  
nothing (in the implementations I'm aware of).  If you assign, you of  
course have at least one instruction, regardless of the types.  If the  
conversion appeared as part of an expression being evaluated, there would  
be no overhead related to it.

Of course, if you insist on separately-named entities, then try:

with Ada.Unchecked_Conversion;
procedure P is
    type Byte_Array is array (1 .. Integer'Size) of Boolean;
    pragma Pack (Byte_Array);
    for Byte_Array'Size use Integer'Size;
    function To_Byte_Array is new
       Ada.Unchecked_Conversion (Source => Integer, Target => Byte_Array);
    I : Integer := 42;
    B : Byte_Array renames To_Byte_Array (I);
begin
    null;
end P;


Compile some code and take a look at the generated assembly language.

- Ed

Re: Bitmanipulation in Ada

[Bernd Specht]

Many thanks, this will help me a lot.


"Martin Dowie" <martin.dowie@btopenworld.com> wrote in
news:cg0j57$bal$1@sparta.btinternet.com: 

> Bernd Specht wrote:
>> 2. I did not found shift and rotate operations. Did I miss something
>> or are there really none? 
> 
> Check out package "Interfaces" they are all there - as are some common
> predefined types.
> 
>> 3. When I want treat a value both as an integer and as a boolean
>> array, how can i do this? In pascal I would use a tagless record like
> 
> Assuming you had a _really_ good reason to need to think of the data in
> both terms, you have a number of options:
> 
> 1) Unchecked_Conversion;
> 
> procedure Foo (Y : Unsigned_8) is
>    procedure To_Array_8 is
>       new Ada.Unchecked_Conversion (Unsigned_8, Array_8);
>    X : Array_8 := To_Array_8 (Y);
> begin
> ...
> 
> 2) Address clause to 'overlay' 2 variables at the same address;
> 
> procedure Foo (Y : Unsigned_8) is
>    X : Array_8;
>    for X'Address use Y'Address;
> begin
> ...
> 
> 3) Variant record with a representation clause;
> 
> type Variant (Is_Array : Boolean := False) is
> record
>    case Is_Array is
>       when False =>
>          U : Unsigned_8;
>       when True =>
>          A : Array_8;
>    end case;
> end record;
> for Variant use
> record
>    U at 0 range 0 .. 7;
>    A at 0 range 0 .. 7;
> end record;
> 
> This will leave it to the compiler where to put "Is_Array"
> 
> There are pros and cons to each - I'd rather use
> Ada.Unchecked_Conversion to make it explicit that I'm switching
> representations. 
> 
> Cheers
> 
> -- Martin
> 
> 

Re: Bitmanipulation in Ada

[Martin Dowie]

Bernd Specht wrote:
> Always? What do you think about bitscrambling software which has to
> treat data alternating as bitvector and as integer value in a loop
> like this (not exeactly this for securitity reasons):
>
> ...
> loop
>   declare
>     x : boolean;
>   begin
>      x := b(k);
>      b(k) := b(32 - k);
>      b (32 - k) := x;
>      I := I * prime1 mod prime2;
>   end;
> end loop;
>
>
> Can you find an equivalent algorithm where you can separate the
> bit-ops and the integer-ops?

Sorry, I'm missing something... Are "I" and "b" different views of the same
address space?

Re: Bitmanipulation in Ada

[Bernd Specht]

"Martin Dowie" <martin.dowie@btopenworld.com> wrote in
news:cg2qcj$de0$1@titan.btinternet.com: 

> Bernd Specht wrote:
>> Always? What do you think about bitscrambling software which has to
>> treat data alternating as bitvector and as integer value in a loop
>> like this (not exeactly this for securitity reasons):
>>
>> ...
>> loop
>>   declare
>>     x : boolean;
>>   begin
>>      x := b(k);
>>      b(k) := b(32 - k);
>>      b (32 - k) := x;
>>      I := I * prime1 mod prime2;
>>   end;
>> end loop;
>>
>>
>> Can you find an equivalent algorithm where you can separate the
>> bit-ops and the integer-ops? 
> 
> Sorry, I'm missing something... Are "I" and "b" different views of the
> same address space?
> 


Sorry, I and b are as mentioned earlier: 

>> TYPE ov is record
>> case boolean of
>>   true : i : integer;
>>   false  : byte_array;
>> end;
>> end;

Re: Bitmanipulation in Ada

[Jeffrey Carter]

Bernd Specht wrote:
> Jeffrey Carter <spam@spam.com> wrote in news:wSSUc.27249$9Y6.977
> @newsread1.news.pas.earthlink.net:
>>In many cases, Unchecked_Conversion will generate no code, and need not 
>>involve an assignment. In well designed software, the part(s) of the 
>>software that deals with values as an integer and those that deal with 
>>them as bit arrays will be kept separate. So you do something like:
> 
> Always? What do you think about bitscrambling software which has to treat 
> data alternating as bitvector and as integer value in a loop like this (not 
> exeactly this for securitity reasons):

I don't see any claims for "always" in my statements.

> ...
> loop
>   declare
>     x : boolean;
>   begin
>      x := b(k);
>      b(k) := b(32 - k);
>      b (32 - k) := x;
>      I := I * prime1 mod prime2;
>   end;
> end loop;
> 
> Can you find an equivalent algorithm where you can separate the bit-ops and 
> the integer-ops?

Assuming that I and B are Integer and Bit_Array versions of the same 
value, sure. Replace the assignment to I with

Update_Integer (Value => To_Integer (B) );

where

procedure Update_Integer (Value : in out Integer) is
    -- null;
begin -- Update_Integer
    Value := Value * Prime1 mod Prime2;
end Update_Integer;

and To_Integer is an appropriate instantiation of Unchecked_Conversion. 
If measurement shows that the overhead of calling a procedure causes you 
to violate timing requirements, you can inline the procedure.

-- 
Jeff Carter
"Sons of a silly person."
Monty Python & the Holy Grail
02

Re: Bitmanipulation in Ada

[Martin Dowie]

Bernd Specht wrote:
>> Sorry, I'm missing something... Are "I" and "b" different views of
>> the same address space?
>>
>
>
> Sorry, I and b are as mentioned earlier:
>
>>> TYPE ov is record
>>> case boolean of
>>>   true : i : integer;
>>>   false  : byte_array;
>>> end;
>>> end;

Ok so I is a 32-bit integer and b is a packed array of boolean (in your demo
a 32-bit 'byte').

Re: Bitmanipulation in Ada

[Björn Persson]

Jeffrey Carter wrote:

> Replace the assignment to I with
> 
> Update_Integer (Value => To_Integer (B) );

You can't send a function result to an in out parameter, can you? Make 
Update_Integer a function instead:

function Updated_Integer(I : Integer) return Integer is
begin
    return I * prime1 mod prime2;
end Updated_Integer;
....
loop
   declare
     x : boolean;
   begin
      x := b(k);
      b(k) := b(32 - k);
      b (32 - k) := x;
      b := To_Bit_Array(Updated_Integer(To_Integer(b)));
   end;
end loop;

-- 
Björn Persson                              PGP key A88682FD
                    omb jor ers @sv ge.
                    r o.b n.p son eri nu

Re: Bitmanipulation in Ada

[Martin Dowie]

Bernd Specht wrote:
> Sorry, I and b are as mentioned earlier:
>
>>> TYPE ov is record
>>> case boolean of
>>>   true : i : integer;
>>>   false  : byte_array;
>>> end;
>>> end;

Well, this isn't a complete solution (I've got a 4-year old to put to bed
right now...) but it could send you on an alternative course (if the
algorithm you posted is doing what I think it is! ;-)

procedure Alternative (I : Unsigned_32) is
   K1, K2 : Unsigned_32;
begin
   K1 := 16#8000_0000#;
   K2 := 16#0000_0001#;
   loop
      declare
         K1_Mask_Off : Unsigned_32 := 16#FFFF_FFFF# xor K1;
         K1_Mask_On : Unsigned_32 := 16#FFFF_FFFF# and K1;
         X1, X2 : Unsigned_32;
      begin
         Put ("K1"); IO.Put (K1, Base => 16); New_Line;
         Put ("K2"); IO.Put (K2, Base => 16); New_Line;
         Put ("K1_Mask_Off = "); IO.Put (K1_Mask_Off, Base => 16); New_Line;
         Put ("K1_Mask_On = "); IO.Put (K1_Mask_On, Base => 16); New_Line;
         X1 := I and K1;
         X2 := I and K2;
         K1 := Shift_Right (K1, 1);
         K2 := Shift_Left (K2, 1);
         exit when K2 = 0;
      end;
   end loop;
end Alternative;

The idea behind your loop (I think) is to swap bits from either end from
MSBit to LSBit with a prime number 'twist' in each step? You can do this
using the above as the basis for that solution - all in 'Unsigned_32'.

Cheers

-- Martin

Re: Bitmanipulation in Ada

[Francois G. Dorais]

Bernd Specht wrote:
> Always? What do you think about bitscrambling software which has to treat 
> data alternating as bitvector and as integer value in a loop like this (not 
> exeactly this for securitity reasons):
> 
> ...
> loop
>   declare
>     x : boolean;
>   begin
>      x := b(k);
>      b(k) := b(32 - k);
>      b (32 - k) := x;
>      I := I * prime1 mod prime2;
>   end;
> end loop;
> 
> 
> Can you find an equivalent algorithm where you can separate the bit-ops and 
> the integer-ops?

A generic solution for the above is to encapsulate the bit 
fiddling in an inlined procedure. For example, consider the 
following where I replaced your bit operation by one which 
doesn't implicitly need a copy (to store the K-th bit in 
your example.)

	with Ada.Unchecked_Conversion;

	[...]

	type Unsigned_32 is mod 2 ** 32;
	for Unsigned_32'Size use 32;

	subtype Bit_Index_32 is Integer range 0 .. 31;
	-- This avoids many range checks...

	procedure Bit_Fiddle
	  (U : in out Unsigned_32;
            K : in Bit_Index_32) is

	   type Bits_32 is array (Bit_Index_32) of Boolean;
	   for Bits_32'Component_Size use 1;

	   function To_Unsigned is new Ada.Unchecked_Conversion 
(Bits_32, Unsigned_32);
    	   function To_Bits is new Ada.Unchecked_Conversion 
(Unsigned_32, Bits_32);

	   B : Bits_32 := To_Bits(U);

	begin
	   B(K) := B(31 - K);
	   U := To_Unsigned(B);
	end Bit_Fiddle;

	pragma Inline (Bit_Fiddle);

	[...]

GNAT compiles the above without copy instructions if it 
doesn't need to. For example, try

	[...]

	for K in Bit_Index_32 loop
	   Bit_Fiddle(X, K);
	   X := X + 16#39A2_D071#;
	end loop;

	[...]

I got the following x86 asm code from gnat 3.15p (with 
options "-S -O2 -gnaton") It uses register ebx for the loop 
counter K, it stores value 31 in edi throughout and X is 
initially in register esi.

	[...]
	xorl %ebx,%ebx
	addl $16,%esp
	movl $31,%edi
	.align 4
.L65:
	movl $1,%eax
	movl %ebx,%ecx
	sall %cl,%eax
	notl %eax
	movl %esi,%edx
	andl %eax,%edx
	movl %edi,%eax
	subl %ebx,%eax
	movl %eax,%ecx
	shrl %cl,%esi
	movl %esi,%eax
	andl $1,%eax
	movl %ebx,%ecx
	sall %cl,%eax
	movl %edx,%esi
	orl %eax,%esi
	addl $966971505,%esi
	incl %ebx
	cmpl $31,%ebx
	jle .L65
	[...]

This is not necessarily optimal code, but it's pretty decent.

But since your example already needs a copy to save the k-th 
bit and probably more for the mul/mod, it's propbably more 
efficient to force the bit array B to be distinct from the 
integer I. The following should do what you want pretty 
efficiently. (I took the liberty to replace your mul/mod by 
an arithmetically correct one...)

	[...]

	type Unsigned_32 is mod 2 ** 32;
	for Unsigned_32'Size use 32;

	subtype Bit_Index_32 is Integer range 0 .. 31;

	type Bits_32 is array (Bit_Index_32) of Boolean;
	for Bits_32'Component_Size use 1;

	function To_Unsigned is new Ada.Unchecked_Conversion 
(Bits_32, Unsigned_32);
    	function To_Bits is new Ada.Unchecked_Conversion 
(Unsigned_32, Bits_32);

	function Mul_Mod (Op_1, Op_2, Modulus : Unsigned_32) return 
Unsigned_32 is
	   type Unsigned_64 is mod 2 ** 64;
	begin
	   return Unsigned_32((Unsigned_64(Op_1) * 
Unsigned_64(Op_2)) mod Unsigned_64(Modulus));
	end Mul_Mod;

	pragma Inline (Mul_Mod);

	[...]

	for K in Bit_Index_32 loop
             declare
                B : Bits_32 := To_Bits(I);
             begin
                B(K) := B(31 - K);
                B(31 - K) := To_Bits(I)(K);
                I := Mul_Mod(To_Unsigned(B), Prime_1, Prime_2);
             end;
	end loop;

	[...]

Try it with GNAT and look at the generated code, you might 
be surprized.

However, I know that bit arrays are usually not optimally 
handled by most compilers (for any language.) GNAT seems to 
do a pretty decent job in general, but when I have to do 
this kind of thing and time optimization is very important, 
I use the tools provided by package Interfaces and do the 
bit-fiddling code myself (as one would do in C) or else I 
use package System.Machine_Code to insert some hand 
optimized assembly code where needed. Alas, there is no such 
thing as a perfect compiler!

Re: Bitmanipulation in Ada

[Jeffrey Carter]

Bj�rn Persson wrote:

> You can't send a function result to an in out parameter, can you? Make 
> Update_Integer a function instead:

You can pass a conversion as a parameter; that's been around since at 
least Ada 83. Unchecked_Conversion is technically a function, but it's 
special, since it generally doesn't generate any code, much less a 
function call. You're correct, though; this should be a function.

-- 
Jeff Carter
"Sons of a silly person."
Monty Python & the Holy Grail
02

Re: Bitmanipulation in Ada

[Jean-Pierre Rosen]

Bernd Specht a écrit :

> Always? What do you think about bitscrambling software which has to treat 
> data alternating as bitvector and as integer value in a loop like this (not 
> exeactly this for securitity reasons):
> 
> ...
> loop
>   declare
>     x : boolean;
>   begin
>      x := b(k);
>      b(k) := b(32 - k);
>      b (32 - k) := x;
>      I := I * prime1 mod prime2;
>   end;
> end loop;
> 

Such software does not use signed integers, but modular integers. And 
you have all the bit operations you need on modular integers.
-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Bitmanipulation in Ada

[Pascal Obry]

"Francois G. Dorais" <dorais@gauss.dartmouth.edu> writes:

> This is not necessarily optimal code, but it's pretty decent.

Do not forget that the GCC backend with 3.15p is GCC 2.8.1. The latest version
of GNAT is based on GCC 3.4.x and there is lot more optimizations done by this
new backend.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Bitordering? was Re: Bitmanipulation in Ada

[Alfred Hilscher]

Sorry that I interfere here, I have a question in this context, too.

When I declare an boolean array with eight elements 1..8 (e.g. to
address a hardware port with eight status bits), how are they ordered is
X(1) the msb or the lsb of the byte?

X(1) = 2**7 and X(8) = 2**0

or

X(1) = 2**0 and X(8) = 2**7


Bernd Specht schrieb:
> 
> Hi,
> 
> i have some questions regarding bitmanipulations:

[...]


-----------------------------------------------------
To send me mail, please replace "Spam" by "Jedermann"
-----------------------------------------------------

Re: Bitmanipulation in Ada

[Bernd Specht]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 817 bytes --]

Jean-Pierre Rosen <rosen@adalog.fr> wrote in
news:1394gc.kok.ln@skymaster: 

> Bernd Specht a �crit :
> 
>> Always? What do you think about bitscrambling software which has to
>> treat data alternating as bitvector and as integer value in a loop
>> like this (not exeactly this for securitity reasons):
>> 
>> ...
>> loop
>>   declare
>>     x : boolean;
>>   begin
>>      x := b(k);
>>      b(k) := b(32 - k);
>>      b (32 - k) := x;
>>      I := I * prime1 mod prime2;
>>   end;
>> end loop;
>> 
> 
> Such software does not use signed integers, but modular integers. And 
> you have all the bit operations you need on modular integers.


In fact, thats right :-o

Can I declare full 32-bit modular types? Ada itself has no 32-bit unsigned 
(except in Interfaces.C). Natural is only a *subrange* from Integer.

Re: Bitmanipulation in Ada

[Bernd Specht]

"Martin Dowie" <martin.dowie@btopenworld.com> wrote in
news:cg32ja$qru$1@titan.btinternet.com: 

> Bernd Specht wrote:
> Well, this isn't a complete solution (I've got a 4-year old to put to
> bed right now...) but it could send you on an alternative course (if
> the algorithm you posted is doing what I think it is! ;-)

I think you're right.

> The idea behind your loop (I think) is to swap bits from either end
> from MSBit to LSBit with a prime number 'twist' in each step?

Yes, but thats not exactly my task. I do some kind of data scrambling for 
transmission over public network.

> You can
> do this using the above as the basis for that solution - all in
> 'Unsigned_32'. 

Yes, I think so. Thanks.

Re: Bitmanipulation in Ada

[Ed Falis]

On 20 Aug 2004 21:20:49 GMT, Bernd Specht <Bernd.Specht@gmx.com> wrote:

> Can I declare full 32-bit modular types?

You can use the "sized" versions provided in package Interfaces (eg  
Unsigned_32), or declare your own:

"type Word is mod 2 ** 32;

- Ed

-- 
"When I was a kid, I wanted to grow up to be a wise man. Somehow, I just  
turned out to be a wise guy".

Re: Bitordering? was Re: Bitmanipulation in Ada

[Nick Roberts]

On Fri, 20 Aug 2004 22:57:40 +0200, Alfred Hilscher  
<SPAM@alfred-hilscher.de> wrote:

> When I declare an boolean array with eight elements 1..8 (e.g. to
> address a hardware port with eight status bits), how are they
> ordered is X(1) the msb or the lsb of the byte?

It is undefined.

The typical way to deal with this kind of situation is to use a
record type with a record representation clause. For example:

    type Frobnosticator_Status is
       record
          Ready, Complete, Motor_On, Fault, Power_Low: Boolean;
       end record;

    for Frobnosticator_Status'Bit_Order use System.Low_Order_First;

    for Frobnosticator_Status use
       record
          Ready     at 0 range 0..0;
          Complete  at 0 range 1..1;
          Motor_On  at 0 range 3..3;
          Fault     at 0 range 6..6;
          Power_Low at 0 range 7..7;
       end record;

    for Frobnosticator_Status'Size use 8;

This lot specifies exactly where each bit is, and what it means.
In this example, I've used representation clauses to tell the
compiler to consider the LSB to be bit number 0 for this record,
and to tell it that the record is 8 bits in size. I've associated
a specific bit with each Boolean component (bits 2, 4, and 5 are
unused).

If I declare:

    Status: Frobnosticator_Status;
    for Status'Address use Frob_1_Status_Address;
    pragma Volatile(Status);

to map the variable 'Status' to frobnosticator number 1's status
port, I can read off its status bits by name:

    if Status.Fault then
       Put_Line( Current_Error, "Frob #1 went down" );
       raise Hardware_Failure;
    end if;
    ...

Does this help you?

-- 
Nick Roberts

Re: Bitordering? was Re: Bitmanipulation in Ada

[Jim Rogers]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1901 bytes --]

"Nick Roberts" <nick.roberts@acm.org> wrote in 
news:opsc2yf8zvp4pfvb@bram-2:

> On Fri, 20 Aug 2004 22:57:40 +0200, Alfred Hilscher  
> <SPAM@alfred-hilscher.de> wrote:
> 
>> When I declare an boolean array with eight elements 1..8 (e.g. to
>> address a hardware port with eight status bits), how are they
>> ordered is X(1) the msb or the lsb of the byte?
> 
> It is undefined.

It is undefined in an array. It can be defined in a record.

The Ada LRM, section 13.5.3 deals with bit ordering issues.
To quoute:

A bit ordering is a method of interpreting the meaning of the storage 
place attributes. High_Order_First (known in the vernacular as �big 
endian�) means that the first bit of a storage element (bit 0) is the 
most significant bit (interpreting the sequence of bits that represent a 
component as an unsigned integer value). Low_Order_First (known in the 
vernacular as �little endian�) means the opposite: the first bit is the 
least significant. 

For every specific record subtype S, the following attribute is defined: 

S�Bit_Order Denotes the bit ordering for the type of S. The value of this 
attribute is of type System.Bit_Order. Bit_Order may be specified for 
specific record types via an attribute_definition_clause; the expression 
of such a clause shall be static. 

If Word_Size = Storage_Unit, the default bit ordering is implementation 
defined. If Word_Size > Storage_Unit, the default bit ordering is the 
same as the ordering of storage elements in a word, when interpreted as 
an integer. 

The storage place attributes of a component of a type are interpreted 
according to the bit ordering of the type. 

Implementation Advice 

The recommended level of support for the nondefault bit ordering is: 

If Word_Size = Storage_Unit, then the implementation should support the 
nondefault bit ordering in addition to the default bit ordering.

Jim Rogers

Re: Bitordering? was Re: Bitmanipulation in Ada

[Simon Wright]

Jim Rogers <jimmaureenrogers@worldnet.att.net> writes:

> >> When I declare an boolean array with eight elements 1..8 (e.g. to
> >> address a hardware port with eight status bits), how are they
> >> ordered is X(1) the msb or the lsb of the byte?
> > 
> > It is undefined.
> 
> It is undefined in an array. It can be defined in a record.

I think you have to use pragma Pack before the boolean elements are
packed into bits?

I don't have a big-endian machine here, but I'm pretty sure that GNAT
orders a packed boolean array as you would expect from
System.Default_Bit_Order (I used it as a demonstration to the
unbelievers that bit ordering actually matters!)

-- 
Simon Wright                               100% Ada, no bugs.

Re: Bitordering? was Re: Bitmanipulation in Ada

[Georg Bauhaus]

Nick Roberts <nick.roberts@acm.org> wrote:
: On Fri, 20 Aug 2004 22:57:40 +0200, Alfred Hilscher  
: <SPAM@alfred-hilscher.de> wrote:
: 
:> When I declare an boolean array with eight elements 1..8 (e.g. to
:> address a hardware port with eight status bits), how are they
:> ordered is X(1) the msb or the lsb of the byte?
: 
: It is undefined.
: 
: The typical way to deal with this kind of situation is to use a
: record type with a record representation clause. For example:

[...]

You might also be interested in the Bit Order paper by Norman Cohen
available in the grab bag at http://www.ada-auth.org


-- Georg

Re: Bitordering? was Re: Bitmanipulation in Ada

[Alfred Hilscher]

Georg Bauhaus schrieb:
> 
> Nick Roberts <nick.roberts@acm.org> wrote:
> : On Fri, 20 Aug 2004 22:57:40 +0200, Alfred Hilscher
> : <SPAM@alfred-hilscher.de> wrote:
> :
> :> When I declare an boolean array with eight elements 1..8 (e.g. to
> :> address a hardware port with eight status bits), how are they
> :> ordered is X(1) the msb or the lsb of the byte?
> :
> : It is undefined.
> :
> : The typical way to deal with this kind of situation is to use a
> : record type with a record representation clause. For example:
> 
> [...]
> 
> You might also be interested in the Bit Order paper by Norman Cohen
> available in the grab bag at http://www.ada-auth.org
> 
> -- Georg

Very interessting. Thanks.

I worked in the range of telecommunication (with CHILL) and our compiler
had directives (pragmas) to tell him which variable should be treated as
big-endian, bzw little endian. In the case of mixed expressions, the
compiler generated code to change the representation. This siplyfied the
code in some situations.


-----------------------------------------------------
To send me mail, please replace "Spam" by "Jedermann"
-----------------------------------------------------

Re: Bitordering? was Re: Bitmanipulation in Ada

[Alfred Hilscher]

Nick Roberts schrieb:
> 
> On Fri, 20 Aug 2004 22:57:40 +0200, Alfred Hilscher
> <SPAM@alfred-hilscher.de> wrote:
> 
>     ...
> 
> Does this help you?


Yes it does. Although it is not what I expected.

My first idea was something like this:

type flags is (buffer_empty, overrun, parity_error, frame_error,
timed_out, break_detected, receiving, idle);

type port is array (flags) of boolean;  pragma pack (port);

status_port : port;  for port use at 16#0004#;

...

for s in overrun .. break_detected
loop
  if status_port (s) 
  then 
    return flags'pos (s);
  end if;
end loop;

return 0;



So instead I have to write:

type port is record
       buffer_empty : boolean;
       ...
end record;

...

if status_port (overrun)
then
  return 7;
elsif status_port (parity_error)
then
  return 6;

...

else
  return 0;
end if;

Is this correct? Ok, it is a bit more to write, but this should not
matter.

Regards,
Alfred


-----------------------------------------------------
To send me mail, please replace "Spam" by "Jedermann"
-----------------------------------------------------

Re: Bitordering? was Re: Bitmanipulation in Ada

[Nick Roberts]

On Mon, 23 Aug 2004 20:47:10 +0200, Alfred Hilscher  
<SPAM@alfred-hilscher.de> wrote:

>> Does this help you?
>
> Yes it does. Although it is not what I expected.
> ...
> Is this correct?

In essence, yes.

> Ok, it is a bit more to write, but this should not matter.

Exactly. The Ada ethic is that the clarity of the code matters more
than its conciseness.

I'd suggest you declare the record type like this:

with System;

    ...

    type Status_Flags is
       record
          Buffer_Empty,
          Overrun,
          Parity_Error,
          Frame_Error,
          Timed_Out,
          Break_Detected,
          Receiving,
          Idle:            Boolean;
       end record;

    for Status_Flags'Size use 8;
    for Status_Flags'Bit_Order use System.Low_Order_First;

    for Status_Flags use
       record
          Buffer_Empty    at 0 range 7..7;
          Overrun         at 0 range 6..6;
          Parity_Error    at 0 range 5..5;
          Frame_Error     at 0 range 4..4;
          Timed_Out       at 0 range 3..3;
          Break_Detected  at 0 range 2..2;
          Receiving       at 0 range 1..1;
          Idle            at 0 range 0..0;
       end record;

Note that I have numbered the bits here so that the LSB is 0 and the
MSB is 7. If it would be more convenient for you to have it the other
way round, change System.Low_Order_First to System.High_Order_First.
Please check that the right flags are associated with the right bits!

You could write a clarifying function such as:

    function Shows_Error (Flags: in Status_Flags) return Boolean is
    begin
       return Flags.Buffer_Empty or
              Flags.Overrun or
              Flags.Parity_Error or
              Flags.Frame_Error or
              Flags.Timed_Out or
              Flags.Break_Detected;
    end;

You might declare a memory-mapped port like this:

    Status: Status_Flags;
    for Status'Address use 16#0004#;
    pragma Volatile(Status);

You could handle status values using an 'if' structure such as:

    if Shows_Error(Status) then
       if Status.Buffer_Empty then
          ...
       elsif Status.Overrun then
          ...
       elsif Status.Parity_Error then
          ...
       elsif Status.Frame_Error then
          ...
       elsif Status.Timed_Out then
          ...
       elsif Status.Break_Detected then
          ...
       end if;
    else
       if Status.Receiving then
          ...
       elsif Status.Idle then
          ...
       else
          ...
       end if;
    end if;

Note that these nested 'if' statements do not necessarily have the
structure that meets the required logic of your program (you will have
to work that out yourself). It is merely an illustration. HTH

-- 
Nick Roberts