bit numbers in packed arrays of Boolean

bit numbers in packed arrays of Boolean

[Stephen Leake]

I was pleasantly surprised to discover that given this code compiled
with GNAT 6.2.1 for an Intel processor:

   subtype Bit_Index_16_Type is Integer range 0 .. 15;
   type Bit_Array_16_Type is array (Bit_Index_16_Type) of Boolean;
   pragma Pack (Bit_Array_16_Type);
   for Bit_Array_16_Type'Size use 16;

   function To_Bit_Array is new Ada.Unchecked_Conversion
     (Source => Interfaces.Unsigned_16,
      Target => Bit_Array_16_Type);

   Word : constant Interfaces.Unsigned_16 := 2#1000_0000_0000_0000#; 
   Bits : constant Bit_Array_16_Type := To_Bit_Array (Word);

the index of Bit_Array_Type indexes the bits of Unsigned_16 in
little-endian order. That is, Bits (15) = 1 (most significant bit), Bits
(0) = 0 (least significant bit).

LRM 13.9(5) says Bit_Array_16_Type and Unsigned_16 have the same
representation, but it does not specifically address the index order.

Is this bit order required by some other clause? Do other compilers
follow it?

I don't have access to GNAT for a big-endian processor; can anyone
confirm what happens there?

Ideally, there would be a way to force the other bit order, as
'Bit_Order does for records.
  
-- 
-- Stephe

Re: bit numbers in packed arrays of Boolean

[Yannick Duchêne (Hibou57)]

Le Tue, 31 Aug 2010 13:14:48 +0200, Stephen Leake  
<stephen_leake@stephe-leake.org> a écrit:
> LRM 13.9(5) says Bit_Array_16_Type and Unsigned_16 have the same
> representation, but it does not specifically address the index order.
At least ARM 3.6 Array Types does not states anything. But as you used  
Unchecked_Conversion, it is unlikely to be portable or this result could  
be enforced. Let say this is the result of a compiler with descent default  
behaviors.

ARM 13.9 Unchecked Type Conversions says:

    11.a/2  Implementation defined: The effect of unchecked conversion for
    instances with nonscalar result types whose effect is not defined by
    the language.

And do not believe the reference defines anything for an array of 16  
bit-layout booleans.

Possibly depends on how the index is interpreted: as an index in the  
polynomial representation of the word value or as a bit index ? Both would  
be legitimate for a compiler.

That was my humble opinion on the topic.


-- 
“Dual licensing is the Perl's way to disinfect the GNU General Public  
Virus!” (anonymous)

Re: bit numbers in packed arrays of Boolean

[Niklas Holsti]

Stephen Leake wrote:
> I was pleasantly surprised to discover that given this code compiled
> with GNAT 6.2.1 for an Intel processor:
> 
>    subtype Bit_Index_16_Type is Integer range 0 .. 15;
>    type Bit_Array_16_Type is array (Bit_Index_16_Type) of Boolean;
>    pragma Pack (Bit_Array_16_Type);
>    for Bit_Array_16_Type'Size use 16;
> 
>    function To_Bit_Array is new Ada.Unchecked_Conversion
>      (Source => Interfaces.Unsigned_16,
>       Target => Bit_Array_16_Type);
> 
>    Word : constant Interfaces.Unsigned_16 := 2#1000_0000_0000_0000#; 
>    Bits : constant Bit_Array_16_Type := To_Bit_Array (Word);
> 
> the index of Bit_Array_Type indexes the bits of Unsigned_16 in
> little-endian order. That is, Bits (15) = 1 (most significant bit), Bits
> (0) = 0 (least significant bit).
> 
> LRM 13.9(5) says Bit_Array_16_Type and Unsigned_16 have the same
> representation,

Well, not quite, as I understand that point in the LRM. It says that 
(under several conditions) the *value* of the object Bits has the same 
representation as the *value* of the object Word.

It makes no sense to say that (or even to ask if) the two types 
Bit_Array_16_Type and Unsigned_16 have the same representation, because 
their value-sets are disjoint, so we cannot ask if they represent "the 
same value" in the same way.

> but it does not specifically address the index order.

Right. So we do not know at which index in Bits a given bit from Word 
ends up. I believe they could even be in some scrambled order, not 
necessarily 0 .. 15 or 15 .. 0.

> Is this bit order required by some other clause?

I believe not. This is one reason why, when I need to access specific 
bits in a word, I prefer to use Unsigned_xx types and their masking and 
shifting operations, not packed arrays. I use packed arrays only when 
the index order does not matter (or when portability does not matter, 
which is basically never).

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

Re: bit numbers in packed arrays of Boolean

[Yannick Duchêne (Hibou57)]

Le Tue, 31 Aug 2010 14:34:35 +0200, Niklas Holsti  
<niklas.holsti@tidorum.invalid> a écrit:
> Well, not quite, as I understand that point in the LRM. It says that  
> (under several conditions) the *value* of the object Bits has the same  
> representation as the *value* of the object Word.
I suppose, for scalar types only, isn't it ? An exact reference would be  
welcome anyway. Can you recall one please ?


-- 
“Dual licensing is the Perl's way to disinfect the GNU General Public  
Virus!” (anonymous)

Re: bit numbers in packed arrays of Boolean

[Dmitry A. Kazakov]

On Tue, 31 Aug 2010 14:41:10 +0200, Yannick Duch�ne (Hibou57) wrote:

> Le Tue, 31 Aug 2010 14:34:35 +0200, Niklas Holsti  
> <niklas.holsti@tidorum.invalid> a �crit:
>> Well, not quite, as I understand that point in the LRM. It says that  
>> (under several conditions) the *value* of the object Bits has the same  
>> representation as the *value* of the object Word.
> I suppose, for scalar types only, isn't it ? An exact reference would be  
> welcome anyway. Can you recall one please ?

RM 13.1(//2):

"The representation of an object consists of a certain number of bits (the
size of the object). For an object of an elementary type, these are the
bits that are normally read or updated by the machine code when loading,
storing, or operating-on the value of the object. For an object of a
composite type, these are the bits reserved for this object, and include
bits occupied by subcomponents of the object. If the size of an object is
greater than that of its subtype, the additional bits are padding bits. For
an elementary object, these padding bits are normally read and updated
along with the others. For a composite object, padding bits might not be
read or updated in any given composite operation, depending on the
implementation."

The representation = memory pattern. When RM says that S and T have same
representation that is merely same pattern. It tells nothing about ordering
of bits. Any combination of 8-bits is same representation of Unsigned_8 and
Boolean array (1..8).

So I think Niklas is right.

I don't even know if 2**n Unsigned_8 should produce a singleton array. E.g.
it is possible, but unlikely, that 2 could become (True, False, True, True,
True, False, True, False).

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: bit numbers in packed arrays of Boolean

[Yannick Duchêne (Hibou57)]

Le Tue, 31 Aug 2010 15:08:02 +0200, Dmitry A. Kazakov  
<mailbox@dmitry-kazakov.de> a écrit:
> The representation = memory pattern. When RM says that S and T have same
> representation that is merely same pattern. It tells nothing about  
> ordering
> of bits. Any combination of 8-bits is same representation of Unsigned_8  
> and
> Boolean array (1..8).
If I understand correctly, this suggests bits representation should be  
accessed (read/write) all the same way, whatever the type it implements.

If that is, may be this would be better to word it more explicitly. But  
this would be OK for elementary types only as this could always be broken  
for composite types with some representation clause combinations.  
Providing this is OK, this could not be enforced for the example array  
type which is the subject of this topic. Or else, this would require some  
conditions about paddings.

I still feel this is implementation defined and I would not rely on it (or  
else I missed something).

A tricky and imaginary example by the way: imagine a clever compiler with  
clever optimization, which would detect the application mostly access the  
nth item of the array and far less oftenly access any other items, now let  
say the target CPU has a special instruction to access bit value at #0  
(common practice on CISC processor), then it could choose to map this nth  
item on bit #0.

Do you feel the language would disallow such an optimization ? if it does  
not, this example shows this is implementation defined.

Side note: a compiler could do something similar for an unpacked array as  
well ; it could move the nth item at offset 0, to save processing of an  
offset while accessing an element which was determined as far more  
frequently accessed than the others.

Seems possible ?

-- 
“Dual licensing is the Perl's way to disinfect the GNU General Public  
Virus!” (anonymous)

Re: bit numbers in packed arrays of Boolean

[sjw]

On Aug 31, 2:40 pm, Yannick Duchêne (Hibou57)
<yannick_duch...@yahoo.fr> wrote:

> A tricky and imaginary example by the way: imagine a clever compiler with  
> clever optimization, which would detect the application mostly access the  
> nth item of the array and far less oftenly access any other items, now let  
> say the target CPU has a special instruction to access bit value at #0  
> (common practice on CISC processor), then it could choose to map this nth  
> item on bit #0.
>
> Do you feel the language would disallow such an optimization ? if it does  
> not, this example shows this is implementation defined.

I think this would be a very bad idea. My first reaction involved
"deserving a good kicking", perhaps that's a little extreme.

Re: bit numbers in packed arrays of Boolean

[Dmitry A. Kazakov]

On Tue, 31 Aug 2010 15:40:40 +0200, Yannick Duch�ne (Hibou57) wrote:

> Le Tue, 31 Aug 2010 15:08:02 +0200, Dmitry A. Kazakov  
> <mailbox@dmitry-kazakov.de> a �crit:
>> The representation = memory pattern. When RM says that S and T have same
>> representation that is merely same pattern. It tells nothing about ordering
>> of bits. Any combination of 8-bits is same representation of Unsigned_8  
>> and Boolean array (1..8).

> If I understand correctly, this suggests bits representation should be  
> accessed (read/write) all the same way, whatever the type it implements.

The representation is accessed when bytes, words etc are read and written.

> A tricky and imaginary example by the way: imagine a clever compiler with  
> clever optimization, which would detect the application mostly access the  
> nth item of the array and far less oftenly access any other items, now let  
> say the target CPU has a special instruction to access bit value at #0  
> (common practice on CISC processor), then it could choose to map this nth  
> item on bit #0.
> 
> Do you feel the language would disallow such an optimization ? if it does  
> not, this example shows this is implementation defined.

AFAIK there is no requirement for Unchecked_Conversion be meaningful. The
compiler is allowed do whatever it wishes with the representation if the
type semantics is not violated.

After all, some objects can be optimized away. What is the representation
of a non-resident object?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: bit numbers in packed arrays of Boolean

[Niklas Holsti]

Yannick Duchêne (Hibou57) wrote:
> Le Tue, 31 Aug 2010 15:08:02 +0200, Dmitry A. Kazakov 
> <mailbox@dmitry-kazakov.de> a écrit:
>> The representation = memory pattern. When RM says that S and T have same
>> representation that is merely same pattern. It tells nothing about 
>> ordering of bits. Any combination of 8-bits is same representation of 
>> Unsigned_8 and Boolean array (1..8).
> If I understand correctly, this suggests bits representation should be 
> accessed (read/write) all the same way, whatever the type it implements.

I'm not sure what you mean, but for me the *type* used to access a 
memory location is the factor that determines what the bits, and each 
bit, represents. The correspondence between bits in Unsigned_8 and a 
packed array of 8 Booleans is entirely implementation-defined, but can 
be inspected by Unchecked_Conversion between the types.

I'm not sure if the standard even requires, for a packed array of 8 
Booleans of Size 8 bits, that each one of those bits should represent 
exactly one of the Boolean components. But even if one component is 
represented in one bit, the encoding (whether 0 is False and 1 is True, 
or vice versa) is implementation-defined (and could, I believe, be 
different depending on the index of the component... although that would 
be weird).

> I still feel this is implementation defined and I would not rely on it 
> (or else I missed something).

I think Dmitry and I agree, with you, that it is implementation-defined.

> A tricky and imaginary example by the way: imagine a clever compiler 
> with clever optimization, which would detect the application mostly 
> access the nth item of the array and far less oftenly access any other 
> items, now let say the target CPU has a special instruction to access 
> bit value at #0 (common practice on CISC processor), then it could 
> choose to map this nth item on bit #0.
> 
> Do you feel the language would disallow such an optimization ?

No. I think that the basic RM does not say anything about the order of 
components in an array, whether Packed or not. (See below for Annexes.)

> Side note: a compiler could do something similar for an unpacked array 
> as well ; it could move the nth item at offset 0, to save processing of 
> an offset while accessing an element which was determined as far more 
> frequently accessed than the others.
> 
> Seems possible ?

In principle, yes.

Pragma Convention C or Fortran should impose some ordering rules, from 
the C/Fortran rules, and perhaps something is also implied by the 
Implementation Advice on the Ada/C interface in RM B.3(62.1/2 through 
75). For example, the rule RM B.3(70) says that an Ada "array (..) of T" 
should be passed to C as "*t", where t is the C type corresponding to 
the Ada type T. For this to be a useful rule, the components in the Ada 
array must be laid out as in the C case, that is, with the address 
increasing monotonically with the index. Which is, of course, the 
natural lay-out that one would expect, in any case.

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

Re: bit numbers in packed arrays of Boolean

[Jeffrey Carter]

On 08/31/2010 04:14 AM, Stephen Leake wrote:
>
> LRM 13.9(5) says Bit_Array_16_Type and Unsigned_16 have the same
> representation, but it does not specifically address the index order.
>
> Is this bit order required by some other clause? Do other compilers
> follow it?

Packed arrays of Boolean have been around since Ada 80, and prior to Ada 95 were 
the only way to access individual bits. Note that the Boolean operations "and", 
"or", "xor", and "not" may be applied to such arrays.

Unfortunately, the ARM does not specify how indices are mapped to individual bit 
positions, so this is entirely compiler dependent. Typically compilers map the 
lowest index onto the lowest bit number supported by the H/W, so this depends on 
the platform, but the ARM allows any mapping from indices to bit positions. As a 
result, any use of packed arrays of Boolean to access specific bits is not portable.

-- 
Jeff Carter
"C++ is like giving an AK-47 to a monk, shooting him
full of crack and letting him loose in a mall and
expecting him to balance your checking account
'when he has the time.'"
Drew Olbrich
52

--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

Re: bit numbers in packed arrays of Boolean

[Randy Brukardt]

"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:8e4b6rF1dlU1@mid.individual.net...
...
>> Is this bit order required by some other clause?
>
> I believe not. This is one reason why, when I need to access specific bits 
> in a word, I prefer to use Unsigned_xx types and their masking and 
> shifting operations, not packed arrays. I use packed arrays only when the 
> index order does not matter (or when portability does not matter, which is 
> basically never).

I don't think so, either. I've generally used a record type (with a record 
representation clause) if I care where the bits are. This would be a bit 
annoying in this case (16 distinct components), but often I've found that 
you don't really need the conversion in the first place if you have an 
appropriately represented record. YMMV.

                               Randy.