Efficient Bit Vector Manipulation.

Efficient Bit Vector Manipulation.

[Vincent]

 Hello Ada language experts,

I need to extract in a very efficient way, information from the bit sequence that represents a 32 bits Positive number, named I > 0. 

What i would like to do is :

- find the length of the bit sequence, i.e. the number of bits a given value of I needs to be represented properly as a binary number. This can be computed by taking the first non zero bit starting from the MSB of I. Then, we call k = length( I ) - 1. k is the number of useful bits, i.e. the bits following the first 1.

For instance : 
 - I = 1 is represented by 1 and k = 0.
 - I = 2 is represented by 10 and k = 1.
 - I = 3 is represented by 11 and k = 1.
 - I = 4 is represented by 100 and k = 2. 

Then I would like to :
- extract the b = floor(k/2) bits leading the first 1 starting from MSB and convert them to an integer : B
- extract the remaining e = Ceiling (k/2) bits and convert them to an integer : E.

then I = 2^k + B * 2^b + E

How can I do that efficiently in Ada ? I mean I thought of using boolean arrays but will this
be optimized by the compiler to CPU instructions ? I used to know how to do it in assembly langage on the Intel 386 but that seems not portable at all :-). Maybe I should use shifts. 

Any suggestion ?

Kind regards,

Vincent

Re: Efficient Bit Vector Manipulation.

[Colin Paul de Gloucester]

Hello,

The code which yields the most efficient output from one compiler
might not yield the most efficient output from another compiler, and
vice versa.

Kind regards,
Nicholas Collin Paul de Gloucester

Re: Efficient Bit Vector Manipulation.

[Niklas Holsti]

On 15-05-15 15:07 , Vincent wrote:
> Hello Ada language experts,
>
> I need to extract in a very efficient way, information from the bit
> sequence that represents a 32 bits Positive number, named I > 0.
>
> What i would like to do is :
>
> - find the length of the bit sequence, i.e. the number of bits a
> given value of I needs to be represented properly as a binary number.
> This can be computed by taking the first non zero bit starting from
> the MSB of I.

Very well-known problem... see

http://en.wikipedia.org/wiki/Find_first_set

and

http://graphics.stanford.edu/~seander/bithacks.html

The latter page gives C code, which should be easy to translate to Ada 
using the modular types from Interfaces and their shift operations.

Same suggestion for the rest of your questions: use modular types, 
shifts and masks.

I doubt that any compiler provides good optimization of such operations 
on Boolean arrays, even if packed to one bit per element. Anyway, the 
Ada RM does not define in which order the bits are indexed, so code 
using Boolean arrays would be unportable if it uses Unchecked_Conversion 
to converts between integers and arrays.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Efficient Bit Vector Manipulation.

[Jeffrey R. Carter]

On 05/15/2015 05:07 AM, Vincent wrote:
> 
> I need to extract in a very efficient way, information from the bit sequence
> that represents a 32 bits Positive number, named I > 0.

Given your need to extract sequences of bits as integers, I'd say using an
Unsigned_* type from Interfaces would probably be best. This also has the
advantage of being endian independent.

Finding the most-significant 1 bit can be done with a binary search. Shifting
and masking out the B and E values is then fairly simple.

-- 
Jeff Carter
"C++ is like jamming a helicopter inside a Miata
and expecting some sort of improvement."
Drew Olbrich
51

Re: Efficient Bit Vector Manipulation.

[vincent.diemunsch]

Le vendredi 15 mai 2015 18:25:59 UTC+2, Niklas Holsti a écrit :

> Very well-known problem... see
> http://en.wikipedia.org/wiki/Find_first_set
> and
> http://graphics.stanford.edu/~seander/bithacks.html
> 
> The latter page gives C code, which should be easy to translate to Ada 
> using the modular types from Interfaces and their shift operations.

Thank you very much Niklas, there is all I need here for finding the first 1 bit !
 
> Same suggestion for the rest of your questions: use modular types, 
> shifts and masks.
> 
> I doubt that any compiler provides good optimization of such operations 
> on Boolean arrays, even if packed to one bit per element. Anyway, the 
> Ada RM does not define in which order the bits are indexed, so code 
> using Boolean arrays would be unportable if it uses Unchecked_Conversion 
> to converts between integers and arrays.

So there is a need for an optimized Bit Vector package based on packed 
boolean arrays, and implemented both as shifts for portability and as
assembly instructions for the most common machines.

Kind regards,

Vincent

Re: Efficient Bit Vector Manipulation.

[vincent.diemunsch]

Le vendredi 15 mai 2015 18:58:15 UTC+2, Jeffrey R. Carter a écrit :

Thank you Jeffrey for your response,

> Given your need to extract sequences of bits as integers, I'd say using an
> Unsigned_* type from Interfaces would probably be best. This also has the
> advantage of being endian independent.

Yes, I'll do that.

> 
> Finding the most-significant 1 bit can be done with a binary search. Shifting
> and masking out the B and E values is then fairly simple.

It is not as simple as I hoped ! But ok, it is not difficult. Just a bit boring and
prone to errors.

Kind regards,

Vincent  

Re: Efficient Bit Vector Manipulation.

[Dennis Lee Bieber]

On Fri, 15 May 2015 14:48:37 +0200, Colin Paul de Gloucester <not@real.com>
declaimed the following:

>Hello,
>
>The code which yields the most efficient output from one compiler
>might not yield the most efficient output from another compiler, and
>vice versa.
>
	Especially if one has data stored in the bit-banded overlay of an ARM
MCU.
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

Re: Efficient Bit Vector Manipulation.

[robin.vowels]

On Friday, May 15, 2015 at 10:07:41 PM UTC+10, Vincent wrote:
> Hello Ada language experts,
> 
> I need to extract in a very efficient way, information from the bit sequence that represents a 32 bits Positive number, named I > 0. 
> 
> What i would like to do is :
> 
> - find the length of the bit sequence, i.e. the number of bits a given value of I needs to be represented properly as a binary number. This can be computed by taking the first non zero bit starting from the MSB of I. Then, we call k = length( I ) - 1. k is the number of useful bits, i.e. the bits following the first 1.
> 
> For instance : 
>  - I = 1 is represented by 1 and k = 0.
>  - I = 2 is represented by 10 and k = 1.
>  - I = 3 is represented by 11 and k = 1.
>  - I = 4 is represented by 100 and k = 2. 
> 
> Then I would like to :
> - extract the b = floor(k/2) bits leading the first 1 starting from MSB and convert them to an integer : B
> - extract the remaining e = Ceiling (k/2) bits and convert them to an integer : E.
> 
> then I = 2^k + B * 2^b + E
> 
> How can I do that efficiently in Ada ? I mean I thought of using boolean arrays but will this
> be optimized by the compiler to CPU instructions ? I used to know how to do it in assembly langage on the Intel 386 but that seems not portable at all :-). Maybe I should use shifts. 
> 
> Any suggestion ?

In PL/I there are specific functions for extracting bits from an integer.
These include IAND (and there are others, probably not relevent here).
Shifting is performed by ISRL and ISLL.
All of these operations (and others) have direct CPU instructions.

Re: Efficient Bit Vector Manipulation.

[Stefan.Lucks]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1546 bytes --]

On Fri, 15 May 2015, Vincent wrote:

> I need to extract in a very efficient way, information from the bit 
> sequence that represents a 32 bits Positive number, named I > 0.

A good way to represent a 32-bit Positive number may be

   type Int is mod 2**32;

> - find the length of the bit sequence, i.e. the number of bits a given 
[...]
> For instance :
> - I = 1 is represented by 1 and k = 0.
> - I = 2 is represented by 10 and k = 1.
> - I = 3 is represented by 11 and k = 1.
> - I = 4 is represented by 100 and k = 2.

The following should give you the k you ask for:

   type Position_Type is range 0 .. 32;

    function Significant_Bits(I: Int) return Position_Type is
       Result: Position_Type := 0;
       Value:  Int := I;
    begin
       while Value > 1 loop
 	 Result := Result + 1;
 	 Value := Value / 2;
       end loop;
       return Result;
    end Significant_Bits;

> Then I would like to :
> - extract the b = floor(k/2) bits leading the first 1 starting from MSB and convert them to an integer : B
> - extract the remaining e = Ceiling (k/2) bits and convert them to an integer : E.
>
> then I = 2^k + B * 2^b + E

This looks like a homework problem -- so I will not give you a complete 
solution. But the above should give you a good start.


Stefan.

------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
uni-weimar.de/de/medien/professuren/mediensicherheit/people/stefan-lucks
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--

Re: Efficient Bit Vector Manipulation.

[vincent.diemunsch]

> The following should give you the k you ask for:
> 
>    type Position_Type is range 0 .. 32;
> 
>     function Significant_Bits(I: Int) return Position_Type is
>        Result: Position_Type := 0;
>        Value:  Int := I;
>     begin
>        while Value > 1 loop
>  	 Result := Result + 1;
>  	 Value := Value / 2;
>        end loop;
>        return Result;
>     end Significant_Bits;
> 

Thank you Stephan. This is indeed the obvious solution.
There are much faster ones on the site given by Niklas.