Byte/Bit Twiddling in Ada 
Author Message
 Byte/Bit Twiddling in Ada

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



Mon, 02 Aug 1999 03:00:00 GMT  
 Byte/Bit Twiddling in Ada


Quote:
>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.

what exactly does you friend wish to do?
Imagining for example a floating point value read as 4 bytes
exp1, exp2, man, exp3 and stored internally as exp1..3,man
(s)he could try declaring a record type with a representation clause
which gave access to the various components of the value
type ext_fp_type is
    exp_1_and_2 : <8 bit integer>  mapped to bits 0 .. 15
    mantissa   : <8 bit integer>         mapped to bits 16 .. 23
    exp_3 : <8 bit integer>   mapped to bits 24 .. 31
end
you can then write sub-programs to convert to and from your
preferred format etc

Quote:

{snip}
>Is there a package or library that handles this problem?

I couldn't find one.

Quote:

>--
>Jim Kruse
>Xilinx, Inc.
>PGP Public Key available upon request

excuse the lack of correct Ada syntax - I'm tired and on my way out of
the building


   type OPINION is access PERSONAL_THOUGHTS_AND_BIAS;
   OPINION_STATED : new OPINION := not LOGICA.OPINION;
Logica UK Ltd.   +44 171 637 9111   http://www.logica.com



Mon, 02 Aug 1999 03:00:00 GMT  
 Byte/Bit Twiddling in Ada

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



Quote:
> 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



Tue, 03 Aug 1999 03:00:00 GMT  
 Byte/Bit Twiddling in Ada

Quote:

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

Quote:

>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

(818) 985-1271



Tue, 03 Aug 1999 03:00:00 GMT  
 Byte/Bit Twiddling in Ada

Quote:
> 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 ?)

Quote:
> 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.



Tue, 03 Aug 1999 03:00:00 GMT  
 Byte/Bit Twiddling in Ada

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.



Wed, 04 Aug 1999 03:00:00 GMT  
 Byte/Bit Twiddling in Ada

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.



Wed, 04 Aug 1999 03:00:00 GMT  
 Byte/Bit Twiddling in Ada



Quote:
> 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



Wed, 04 Aug 1999 03:00:00 GMT  
 Byte/Bit Twiddling in Ada

Wiljan said

<<> GNAT *does* generate good code for messing with individual bits of a bit  

Quote:
> 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!



Sun, 15 Aug 1999 03:00:00 GMT  
 
 [ 9 post ] 

 Relevant Pages 

1. Intel Bit/Byte Order Conversion for Alsys Ada ?

2. Bit Twiddling??

3. Bit twiddling on Parallel port

4. UUDECODE - Bit-twiddling in Arexx

5. SIMD-like bit-twiddling on odd-sized quantities

6. New Mathematical bit-twiddle - stage on of a isPerfectSquare()

7. Crazy bit-twiddle algorithms needed!

8. Bit twiddling functions

9. Bit twiddling functions

10. Bit Twiddling in IBM (LE) COBOL

11. help - bit twiddling anomoly

12. Twiddle binary bit in Cobol?

 

 
Powered by phpBB® Forum Software