* bit numbers in packed arrays of Boolean @ 2010-08-31 11:14 Stephen Leake 2010-08-31 11:34 ` Yannick Duchêne (Hibou57) ` (2 more replies) 0 siblings, 3 replies; 11+ messages in thread From: Stephen Leake @ 2010-08-31 11:14 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 11:14 bit numbers in packed arrays of Boolean Stephen Leake @ 2010-08-31 11:34 ` Yannick Duchêne (Hibou57) 2010-08-31 12:34 ` Niklas Holsti 2010-08-31 18:13 ` Jeffrey Carter 2 siblings, 0 replies; 11+ messages in thread From: Yannick Duchêne (Hibou57) @ 2010-08-31 11:34 UTC (permalink / raw) 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) ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 11:14 bit numbers in packed arrays of Boolean Stephen Leake 2010-08-31 11:34 ` Yannick Duchêne (Hibou57) @ 2010-08-31 12:34 ` Niklas Holsti 2010-08-31 12:41 ` Yannick Duchêne (Hibou57) 2010-09-02 20:09 ` Randy Brukardt 2010-08-31 18:13 ` Jeffrey Carter 2 siblings, 2 replies; 11+ messages in thread From: Niklas Holsti @ 2010-08-31 12:34 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 12:34 ` Niklas Holsti @ 2010-08-31 12:41 ` Yannick Duchêne (Hibou57) 2010-08-31 13:08 ` Dmitry A. Kazakov 2010-09-02 20:09 ` Randy Brukardt 1 sibling, 1 reply; 11+ messages in thread From: Yannick Duchêne (Hibou57) @ 2010-08-31 12:41 UTC (permalink / raw) 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) ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 12:41 ` Yannick Duchêne (Hibou57) @ 2010-08-31 13:08 ` Dmitry A. Kazakov 2010-08-31 13:40 ` Yannick Duchêne (Hibou57) 0 siblings, 1 reply; 11+ messages in thread From: Dmitry A. Kazakov @ 2010-08-31 13:08 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 13:08 ` Dmitry A. Kazakov @ 2010-08-31 13:40 ` Yannick Duchêne (Hibou57) 2010-08-31 13:57 ` sjw ` (2 more replies) 0 siblings, 3 replies; 11+ messages in thread From: Yannick Duchêne (Hibou57) @ 2010-08-31 13:40 UTC (permalink / raw) 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) ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 13:40 ` Yannick Duchêne (Hibou57) @ 2010-08-31 13:57 ` sjw 2010-08-31 14:07 ` Dmitry A. Kazakov 2010-08-31 14:30 ` Niklas Holsti 2 siblings, 0 replies; 11+ messages in thread From: sjw @ 2010-08-31 13:57 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 13:40 ` Yannick Duchêne (Hibou57) 2010-08-31 13:57 ` sjw @ 2010-08-31 14:07 ` Dmitry A. Kazakov 2010-08-31 14:30 ` Niklas Holsti 2 siblings, 0 replies; 11+ messages in thread From: Dmitry A. Kazakov @ 2010-08-31 14:07 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 13:40 ` Yannick Duchêne (Hibou57) 2010-08-31 13:57 ` sjw 2010-08-31 14:07 ` Dmitry A. Kazakov @ 2010-08-31 14:30 ` Niklas Holsti 2 siblings, 0 replies; 11+ messages in thread From: Niklas Holsti @ 2010-08-31 14:30 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 12:34 ` Niklas Holsti 2010-08-31 12:41 ` Yannick Duchêne (Hibou57) @ 2010-09-02 20:09 ` Randy Brukardt 1 sibling, 0 replies; 11+ messages in thread From: Randy Brukardt @ 2010-09-02 20:09 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: bit numbers in packed arrays of Boolean 2010-08-31 11:14 bit numbers in packed arrays of Boolean Stephen Leake 2010-08-31 11:34 ` Yannick Duchêne (Hibou57) 2010-08-31 12:34 ` Niklas Holsti @ 2010-08-31 18:13 ` Jeffrey Carter 2 siblings, 0 replies; 11+ messages in thread From: Jeffrey Carter @ 2010-08-31 18:13 UTC (permalink / raw) 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 --- ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2010-09-02 20:09 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2010-08-31 11:14 bit numbers in packed arrays of Boolean Stephen Leake 2010-08-31 11:34 ` Yannick Duchêne (Hibou57) 2010-08-31 12:34 ` Niklas Holsti 2010-08-31 12:41 ` Yannick Duchêne (Hibou57) 2010-08-31 13:08 ` Dmitry A. Kazakov 2010-08-31 13:40 ` Yannick Duchêne (Hibou57) 2010-08-31 13:57 ` sjw 2010-08-31 14:07 ` Dmitry A. Kazakov 2010-08-31 14:30 ` Niklas Holsti 2010-09-02 20:09 ` Randy Brukardt 2010-08-31 18:13 ` Jeffrey Carter
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox