Re: Bitmanipulation in Ada

["Francois G. Dorais" <dorais@gauss.dartmouth.edu>]

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!