Re: Byte/Bit Twiddling in Ada

Re: Byte/Bit Twiddling in Ada

[Keith Allan Shillington]

Assumptions( Longword => 32 bits, Ada => Ada95 );

Given that: take this:

  type Longword is mod 2**32;  -- your milage may vary

  L, M: Longword;

begin

  L := 16#DEADBEEF#;

  M := L or 16#21727110#;

-- M should now be 16#FFFFFFFF#

want more?  See RM95 3.5.4

Jim Kruse <kruse@xilinx.com> wrote in article
<5dvfnn$olj@neocad.xilinx.com>...
> I'm relaying a question for a friend without Net access.
> 
> Is there any portable way to do byte and bit manipulation in Ada, on a
> long word?  I found no mention of this topic in the FAQ.
> 
> He is trying to avoid any non-Ada construct.  By this I think he means
> architecture-specific features (apparently there is a mechanism on the
> DEC Alpha machines, but he's not using an Alpha).
> 
> My friend is trying to write some code that does byte swapping,
> presumably to handle conversions to and from IEEE number formats.
> 
> Is there a package or library that handles this problem?
> 
> --
> Jim Kruse
> Xilinx, Inc.
> PGP Public Key available upon request
> 

Re: Byte/Bit Twiddling in Ada

[Matthew Heaney]

In article <5dvfnn$olj@neocad.xilinx.com>, kruse@xilinx.com (Jim Kruse) wrote:


>Is there any portable way to do byte and bit manipulation in Ada, on a
>long word?  I found no mention of this topic in the FAQ.

Yes.  It may be that using Unchecked_Conversion is called for.

On the other hand, if you're on a UNIX box you may be able to bind to
htons, for example.

>
>My friend is trying to write some code that does byte swapping,
>presumably to handle conversions to and from IEEE number formats.

Well, here's an example of byte-swapping a longword (32 bits) that uses
Unchecked_Conversion.  Note also that bit manipulation is fully supported
in Ada; see the package Interfaces.

type Byte is new Integer_8;
type Byte_Array is array (Positive range <>) of Byte;

subtype Longword_As_Byte_Array is Byte_Array (1 .. 4);

function To_Byte_Array is 
   new Unchecked_Conversion (
      Source => Integer_32, 
      Target  => Longword_As_Byte_Array);

function To_Longword is
   new Unchecked_Conversion (
      Source => Longword_As_Byte_Array,
      Target => Integer_32);

function Byte_Swapped (O : Integer_32) return Integer_32 is
   The_Byte_Array : Longword_As_Byte_Array :=
      To_Byte_Array (O);
begin
   The_Byte_Array := 
      The_Byte_Array (4) &
      The_Byte_Array (3) &
      The_Byte_Array (2) &
      The_Byte_Array (1);

   return To_Longword (The_Byte_Array);
end;

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: Byte/Bit Twiddling in Ada

[Mats Weber]

> Is there any portable way to do byte and bit manipulation in Ada, on a
> long word?  I found no mention of this topic in the FAQ.

longword_bits : constant := 32;

type longword is array (0 .. longword_bits - 1) of boolean;
pramga pack(longword);
for longword'size use longword_bits;

then you can do any bit-twiddling on variables of type Longword, e.g.

A, B : Longword;

A(0 .. 15) := A(16 .. 31);  -- copy low-order 16 bits 
                            -- into high order 16 bits

A(0 .. 30) := A(1 .. 31);  -- right shift
A := A(31) & A(0 .. 30);   -- rotate left

You can use Unchecked_Conversion if you want to manipulate floating
point values at the bit level (at your own risk). In this case, set
Longword_Bits = <your floating point type>'Size;

(Robert, what kind of code would GNAT generate for these instructions ?
Does the optimizer recognize the CPU's instruction set ?)

> My friend is trying to write some code that does byte swapping,
> presumably to handle conversions to and from IEEE number formats.

Another possibility is using representation clauses:

type Mantissa is range -2 ** 22 .. 2 ** 22 - 1;
type Exponent is range -2 ** 8 .. 2 ** 8 - 1;

type Float_Rec is
   record
      Mant : Mantissa;
      Expo : Exponent;
   end record;

pragma Pack(Float_Rec);
for Float_Rec'Size use 32;

for Float_Rec use 
   record at mod 4;  -- if you want them aligned
      Mant at 0 range 0 .. 22;
      Expo at 0 range 23 .. 31;
   end record;

Note: I did this without looking at the reference of any floating point
type, and I did not check the code with a compiler. But it should work
once adapted.

Re: Byte/Bit Twiddling in Ada

[Robert Dewar]

Mats asked:

<<(Robert, what kind of code would GNAT generate for these instructions ?
Does the optimizer recognize the CPU's instruction set ?)>>

in reference to slices of bit-packed arrays.

GNAT certainly is in the business of recognizing the CPU instruction set!
That's what the code generation of gcc is all about.

However, that is not the issue here, the issue is very special handling
of these kinds of slices at a level where the GCC optimizer could 
generate good code. This is not currently done.

Note that if you want to do shifts or rotates, the use of modular types
is probably more convenient and natural than writing strange concatenations
and slice assignments. Yes, of course these could be optimized, but we
have rarely seen people try to do, say your rotate case, this way, so it
seems a low priority specialization.

On the other hand, general slice assignments are a useful facility, but
again, this is a relatively rare construct in the code we have seen.
You can of course achieve these kind of effects with shifting and
masking on modular values.

GNAT *does* generate good code for messing with individual bits of a bit
packed array, which seems the most common usage.

Re: Byte/Bit Twiddling in Ada

[Robert Dewar]

Mats said

<<A(0 .. 15) := A(16 .. 31);  -- copy low-order 16 bits
                            -- into high order 16 bits

A(0 .. 30) := A(1 .. 31);  -- right shift
A := A(31) & A(0 .. 30);   -- rotate left>>


You are making entirely unwarranted assumptions about the mapping of
bit positions to high or low order, there is no such guarantee. Even
if you know the endianness, you cannot make such assumptions.

If you want a right shift, the portable way to write this is to use
the predefined right shift operation!

Note that in GNAT, the shift operators can be defined for any integer
type, including user defined ones, by writing the appropriate 
pragma Import (Intrinsic) declarations. This however is defintiely
NOT required to work by the RM. The only thing the RM guarantees is
that the predefined shift operations in interfaces will work.

Re: Byte/Bit Twiddling in Ada

[wiljan]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote in article
<dewar.856015429@merv>...
> GNAT certainly is in the business of recognizing the CPU instruction set!
> That's what the code generation of gcc is all about.
> 
[snip]
> 
> GNAT *does* generate good code for messing with individual bits of a bit
> packed array, which seems the most common usage.
> 
I do not agree on that Robert, Plese check out the following program:

with Ada.Text_Io; use Ada.Text_Io;
procedure testsetcomp is

   type set is array(0..31) of boolean;
   pragma pack (set);

   A, B : Set;
begin
   A := (5..10=>True, others=>False);
   B := (others=>False);
   B (5..10) := (others=>True);
   if A <= B then
      Put_Line ("A<=B");
   else
      Put_Line ("not A<=B");
   end if;
end testsetcomp;

When I check the code generated using gnat -S -O2 -gnatp on above source
I find the compiler generating loops for all kind of things.
It generates loops for the variable initialisation.
It also generates loops to perform the A<=B operation.
I think this is normal usage of packed arrays. I actually use them a lot as
if
they where sets.
Anyway GNAT generates very bad code for this. Somehow it is not a lot
of knowledge about the packed arrays. I whould expect GNAT to
generate only code for the call to:
      Put_Line ("A<=B");
That all which is actually needed in above code.

Wiljan

Re: Byte/Bit Twiddling in Ada

[Robert Dewar]

Wiljan said

<<> GNAT *does* generate good code for messing with individual bits of a bit   
> packed array, which seems the most common usage.                           
>                                                                            
I do not agree on that Robert, Plese check out the following program:        
                                                                             
with Ada.Text_Io; use Ada.Text_Io;                                           
procedure testsetcomp is                                                     
                                                                             
   type set is array(0..31) of boolean;                                      
   pragma pack (set);                                                        
                                                                             
   A, B : Set;                                                               
begin                                                                        
   A := (5..10=>True, others=>False);                                        
   B := (others=>False);                                                     
   B (5..10) := (others=>True);                                              
   if A <= B then                                                            
      Put_Line ("A<=B");                                                     
   else                                                                      
      Put_Line ("not A<=B");                                                 
   end if;                                                                   
end testsetcomp;                                                             
                                                                             
When I check the code generated using gnat -S -O2 -gnatp on above source     
I find the compiler generating loops for all kind of things.                 
>>


Robert replies, well you may or may not agree with me, but the above
example is entirely irrelevant to the statement I made, which is that
the code for messing with INDIVIDUAL bits of a bit packed array is good.
In the above examples, EVERY reference to the packed array is to a collection
of bits -- PRECISELY what I noted was not handled very well!!!

Wiljan said

<<Anyway GNAT generates very bad code for this. Somehow it is not a lot
of knowledge about the packed arrays. I whould expect GNAT to
generate only code for the call to:
      Put_Line ("A<=B");
That all which is actually needed in above code.
>>


Well this is a nice example of why this sort of stuff is not as easy as
you think. The issue of whether A<=B can be done in a single compare or
requires bit by bit code depends on the ordering of the bits in the
array which is not specified by the language. Typically at least in the
little-endian case, where A(0) and B(0), the most significant bits in the
semantics of the comparison, are at the LEAST significant bit position in
the word.

Sure there is lots of special casing possible, and *some* of it will get
done in time. But this is certainly not at the top of the list of important
optimizations!