From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,LOTS_OF_MONEY autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,9dec3ff1604723d9 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news1.google.com!newshub.sdsu.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!elk.ncren.net!news.bu.edu!newshost.Dartmouth.EDU!not-for-mail From: "Francois G. Dorais" Newsgroups: comp.lang.ada Subject: Re: Bitmanipulation in Ada Date: Thu, 19 Aug 2004 17:24:17 -0400 Organization: Dartmouth College, Hanover, NH, USA Message-ID: References: <87k6vwrwym.fsf@insalien.org> NNTP-Posting-Host: tarski.kiewit.dartmouth.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Trace: merrimack.Dartmouth.EDU 1092950657 32243 129.170.28.217 (19 Aug 2004 21:24:17 GMT) X-Complaints-To: abuse@Dartmouth.EDU NNTP-Posting-Date: 19 Aug 2004 21:24:17 GMT User-Agent: Mozilla Thunderbird 0.5 (X11/20040306) X-Accept-Language: en-us, en In-Reply-To: Xref: g2news1.google.com comp.lang.ada:2877 Date: 2004-08-19T21:24:17+00:00 List-Id: 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!