Ada Programming/Attributes/'Bit Order

Computing » Computer Science » Computer Programming » Ada Programming

Description

R'Bit_Order is a representation attribute used to specify the bit numbering of a record representation clause (for a record type). The bit ordering is of type System.Bit_Order, and may be either:

High_Order_First when the bit 0 is the most significant bit
Low_Order_First when the bit 0 is the least significant bit

assuming the bit sequence is interpreted as an integer value. The constant System.Default_Bit_Order represents the native bit numbering of the platform.

It is worth noting that the bit ordering only affects the bit numbering for a record representation clause, and not the byte order of its (multibyte) fields. ^[1]

Introduction

Storage units are ordered by their addresses. Let's look at an integer occupying several bytes (let's assume a byte being 8 bits for this discussion).

On a big endian (BE) machine, the integer's most significant byte is stored at the least address.
On a little endian (LE) machine, its least significant byte is stored at the least address.

So in order to be able to count bits consecutively across byte boundaries, Ada counts bits within a byte according to the endianness from most significant bit (MSB) 0 to least significant bit (LSB) on BE and the other way round on LE.^[2]

This is how it looks (conveniently writing left to right on BE, right to left on LE):

BE Byte    0 1 2 …  (counting bytes, i.e. addresses, left to right; higher addresses to the right)
LE Byte  … 2 1 0    (counting bytes right to left; higher addresses to the left)

         MSB         LSB
BE  Bit  0 1 2 3 4 5 6 7  (counting bits within a byte left to right)
LE  Bit  7 6 5 4 3 2 1 0  (counting bits right to left)

We're used to writing left to right, but for LE, as you can see, it's convenient to write addresses from right to left. So on BE, a sequence of bytes and bits is counted like this:

Byte 00                      01                      02
Bit  00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 …
                             00 01 02 03 04 05 06 07 08 09 10 11 12 13 …  (we can equally begin to count at byte 01)

In order to be able to write and count consecutively on LE, we have to write right to left like for example in the Arabian or Hebrew scripts (the MSB is always on the left; this seems to be a global trait in all modern scripts):

Byte                  02                      01                      00
Bit  … 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
     … 13 12 11 10 09 08 07 06 05 04 03 02 01 00

In a record representation like the following (of course only one of the two lines specifying X may be present)

for T use record
  X at 0 range 13 .. 17;  -- these two lines…
  X at 1 range  5 ..  9;  -- … are equivalent
end record;

the component X occupies the bits shown in boldface. The byte number (0 resp. is 1) is called Position, the bounds are called First_Bit (13 resp. 5) and Last_Bit (17 resp. 9); there are corresponding attributes 'Position, 'First_Bit and 'Last_Bit. (The meaning of the component X is irrelevant here, only its size is relevant.) As you can see, X is a crossborder component. Thus the result of applying the attribute 'Bit_Order to a record with crossborder components depends on the Ada generation.

Ada 95

Ada 95 defines the result of the attribute for the non-native bit order only when applied within a storage unit or when an item completely fills a sequence of storage units. By applying the attribute to a record, we force the compiler to count bits in the indicated manner, independent of the machine architecture.

type Rec is record
  A at 0 range 0 .. 5;
  B at 0 range 6 .. 7;
end record;
for Rec'Bit_Order use High_Order_First;

The component B occupies the bits shown in boldface:

Byte 0
Bit  0 1 2 3 4 5 6 7

The layout of this record will be the same on BE and on LE machines, i.e. the representation is endian-independent.

We could equally well have defined this record like so and arrived at the same endian-independent layout:

type Rec is record
  A at 0 range 2 .. 7;
  B at 0 range 0 .. 1;
end record;
for Rec'Bit_Order use Low_Order_First;

Byte               0
Bit  7 6 5 4 3 2 1 0

However a record like the following, where B is crossborder, is only valid on a BE machine, i.e. in the native bit order.

type Rec is record
  A at 0 range 0 .. 5;
  B at 0 range 6 .. 9;
end record;
for Rec'Bit_Order use High_Order_First;

Byte  0                       1
Bit   0  1  2  3  4  5  6  7  0  1  2  3  4  5  6  7
#    00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

Compiled on a LE machine, the compiler will complain that B occupies non-contiguous storage and reject the code, since the byte order is not affected by the attribute (remember, the next byte with bit numbers 8 to 15 has to be put on the left):

Byte                         1                       0
Bit    00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07
#      08 09 10 11 12 13 14 15 00 01 02 03 04 05 06 07

As an example of a record where items fill a range of complete storage units take:

type Rec is record
  A at 0 range 0 ..  7;
  B at 1 range 0 .. 15;
end record;
for Rec'Bit_Order use High_Order_First;

This is valid on both architectures leading to the layout:

BE    0                       1                       2
Bit  00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

LE                         2                       1                       0
Bit  08 09 10 11 12 13 14 15 00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07

where A fills the bits in normal face, B those in bold face. As you can see, it doesn't matter that bits are counted in this strange way on LE since component B fills its two bytes completely.

Ada 2005

For the native bit order, there is no change. Record representation specifications have worked since Ada 83. Only the attribute 'Bit_Order has been introduced in Ada 95 with the restrictions as shown above.

In order to improve the situation for non-native bit orders, Ada 2005 introduces the notion of machine scalars. A machine scalar is a conceptual hardware based unsigned integer within which bits are counted and the components positioned as requested.

We need a more elaborated record example now (the values returned by the corresponding attributes 'Position, 'First_ and 'Last_Bit (in native bit order) are given as comments; note that the bit numbers returned are always counted starting with the byte in which the component begins):

for T use record
  I at 0 range  0 .. 15;  -- at 0 range 0 .. 15
  A at 2 range  0 .. 12;  -- at 2 range 0 .. 12
  B at 2 range 13 .. 17;  -- at 3 range 5 ..  9
  C at 2 range 18 .. 23;  -- at 4 range 2 ..  7
  D at 5 range  0 ..  7;  -- at 5 range 0 ..  7
end record;

Let's assume I is a 16 bit (signed or unsigned) integer, the other components are of some unspecified types with the given size requirements. The complete record's size is 48. This is how it looks like on BE and LE machines:

Byte 0       1       2       3       4       5
  BE 012345678901234501234567890123456789012301234567
     IIIIIIIIIIIIIIIIAAAAAAAAAAAAABBBBBCCCCCCDDDDDDDD

     DDDDDDDDCCCCCCBBBBBAAAAAAAAAAAAAIIIIIIIIIIIIIIII
  LE 765432103210987654321098765432105432109876543210
Byte        5       4       3       2       1       0

In the following, we're going to show how far we can go to reach endian-independence of the representation. The result will be that we only have to swap bytes after transfer from one architecture to the other when the new Ada 2005 features are used correctly.

For the following, we'll assume that we are on a big-endian machine, so that we append the corresponding attribute to the representation:

for T use record
  I at 0 range  0 .. 15;
  A at 2 range  0 .. 12;
  B at 2 range 13 .. 17;
  C at 2 range 18 .. 23;
  D at 5 range  0 ..  7;
end record;
for T'Bit_Order use High_Order_First;

When this is compiled on a little-endian machine, all components with the same Position are taken together and put in a matching machine scalar. The machine scalar is positioned at the given Position, but inside the bits are counted from the opposite side.

Let's take the first component, I. It uses 16 bits, so a 16 bit machine scalar will do. It is positioned at byte 0, but inside the compiler will count from the high order bit side. This is how it looks (NNBO - non-native bit order):

                                     IIIIIIIIIIIIIIII
NNBO                                 0123456789012345
Byte        5       4       3       2       1       0

Now to the next Position 2. The respective components A, B, C use together three bytes, so a 32 bit machine scalar is needed. It is positioned at byte 2, and inside the count will again start from the opposite side. This is how it looks:

                                     IIIIIIIIIIIIIIII
NNBO 012345678901234567890123456789010123456789012345
Byte        5       4       3       2       1       0

The bit count starts at the high order bit of byte 5 and continues down to the low order bit of byte 2. The components A, B, C are positioned inside this scalar according to the respective ranges. Thus we arrive at this layout:

     AAAAAAAAAAAAABBBBBCCCCCC        IIIIIIIIIIIIIIII
NNBO 012345678901234567890123456789010123456789012345
Byte        5       4       3       2       1       0

We immediately see the conflict with component D, whose range is already occupied by A, and the compiler will of course complain and reject the code. The solution is simple: Just instead of locating D at Position 5, we change this to the (on BE) equivalent line like so:

for T use record
  I at 0 range  0 .. 15;
  A at 2 range  0 .. 12;
  B at 2 range 13 .. 17;
  C at 2 range 18 .. 23;
--D at 5 range  0 ..  7;
  D at 2 range 24 .. 31;
end record;
for T'Bit_Order use High_Order_First;

And, drum roll, on LE, we now have (for comparison, the native layout is also given):

     AAAAAAAAAAAAABBBBBCCCCCCDDDDDDDDIIIIIIIIIIIIIIII
NNBO 012345678901234567890123456789010123456789012345
Byte        5       4       3       2       1       0

     IIIIIIIIIIIIIIIIAAAAAAAAAAAAABBBBBCCCCCCDDDDDDDD
  BE 012345678901234501234567890123456789012345678901
Byte 0       1       2       3       4       5

In the non-native bit order, the values returned by the corresponding attributes 'Position, 'First_ and 'Last_Bit are exactly those given in the record specification.

As an additional service, GNAT's compilation output will give you the values as counted in the native bit order within the machine scalar:

       range
"I"   0 .. 15
"A"  19 .. 31
"B"  14 .. 18
"C"   8 .. 13
"D"   0 ..  7

     AAAAAAAAAAAAABBBBBCCCCCCDDDDDDDDIIIIIIIIIIIIIIII
NNBO 012345678901234567890123456789010123456789012345
  LE 109876543210987654321098765432105432109876543210
Byte        5       4       3       2       1       0

This is as far as we can get with the current Ada standard.

Data Transfer

Let us transfer a value of this record from the native big-endian machine to a little-endian machine. For demonstration purposes, the high-order parts of the crossborder items are shown in upper case, the low-order parts in lower case.

     IIIIIIIIiiiiiiiiAAAAAAAAaaaaaBBBbbCCCCCCDDDDDDDD
  BE 012345678901234501234567890123456789012345678901
Byte 0       1       2       3       4       5

The bytes will be transferred in the given order. Since the bit order attribute does not reorder the bytes after transfer, on the target machine we will receive the data in scrambled order:

     DDDDDDDDbbCCCCCCaaaaaBBBAAAAAAAAiiiiiiiiIIIIIIII
NNBO 012345678901234567890123456789010123456789012345
Byte        5       4       3       2       1       0

All we have to do to arrive at the desired end, is to swap bytes 0↔1, 2↔5, 3↔4:

     AAAAAAAAaaaaaBBBbbCCCCCCDDDDDDDDIIIIIIIIiiiiiiii
NNBO 012345678901234567890123456789010123456789012345
Byte        5       4       3       2       1       0

Example

The following two sets of representation clauses specify the same register layout in any machine / compiler (Ada 2005 and later):

type Device_Register is
    record
       Ready : Status_Flag;
       Error : Error_Flag;
       Data  : Unsigned_16;
    end record;

for  Device_Register use
    record
       Ready at 0 range  0 .. 0;
       Error at 0 range  1 .. 1;
       -- Reserved bits
       Data  at 0 range 16 .. 31;
    end record;
for Device_Register'Size      use 32;
for Device_Register'Bit_Order use System.Low_Order_First;

pragma Atomic (Device_Register);

If the bit order is modified, the bit numbering of all the elements of the record representation clause must be reversed:

type Device_Register is
    record
       Ready : Status_Flag;
       Error : Error_Flag;
       Data  : Unsigned_16;
    end record;

for  Device_Register use
    record
       Ready at 0 range 31 .. 31;   -- Bit numbering has changed
       Error at 0 range 30 .. 30;   -- Bit numbering has changed
       -- Reserved bits
       Data  at 0 range  0 .. 15;   -- Bit numbering has changed (but byte order is not affected)
    end record;
for Device_Register'Size      use 32;
for Device_Register'Bit_Order use System.High_Order_First; -- Reverse bit order

pragma Atomic (Device_Register);

Both can be interchangeably used in the same machine. But note that in two machines with different endianness the Data field will have the native byte order regardless of the bit order specified in the representation clauses.

Incorrect Usage

The 'Bit_Order attribute is not intended to convert data between a big-endian and a little-endian machine (it affects bit numbering, not byte order). The compiler will not generate code to reorder multi-byte fields when a non-native bit order is specified.^[3]^[4]^[5]

References

↑ Note that when the ARM talks about "big endian" and "little endian" in the definition of the 'Bit_Order attribute it really means bit endianness, not byte endianness. (Nowadays the term endianness is usually reserved for talking about byte order, although it can also be used for bit numbering.) Thus, in this context, when the ARM says "little endian" it refers to "LSB 0", and when it says "big endian" this is the same as "MSB 0":
«High_Order_First (known in the vernacular as “big endian”) means that the first bit of a storage element (bit 0) is the most significant bit (interpreting the sequence of bits that represent a component as an unsigned integer value). Low_Order_First (known in the vernacular as “little endian”) means the opposite: the first bit is the least significant.» [LRM, §13.5.3(2)]
↑ ISO/IEC 8652:1987. "13.4 Record Representation Clauses". Ada 83 Reference Manual. The range defines the bit positions of the storage place, relative to the storage unit. The first storage unit of a record is numbered zero. The first bit of a storage unit is numbered zero. The ordering of bits in a storage unit is machine_dependent and may extend to adjacent storage units. {{cite book}}: Unknown parameter |chapterurl= ignored (|chapter-url= suggested) (help)
↑ AI95-00133-01 (1996-05-07). "Controlling bit ordering". Class: binding interpretation. Ada Rapporteur Group. Bit_Order clauses are concerned with the numbering of bits and not concerned with data flipping interoperability.
↑ ISO/IEC 8652:2007. "13.5.3 Bit Ordering (9/2)". Ada 2005 Reference Manual. Retrieved 2008-06-02. Bit_Order clauses make it possible to write record_representation_clauses that can be ported between machines having different bit ordering. They do not guarantee transparent exchange of data between such machines. {{cite book}}: Unknown parameter |chapterurl= ignored (|chapter-url= suggested) (help)
↑ Thomas Quinot (2013). "Gem #140: Bridging the Endianness Gap". AdaCore. Retrieved 2013-01-31. the order in which the bytes that constitute machine scalars are written to memory is not changed by the Bit_Order attribute -- only the indices of bits within machine scalars are changed. {{cite web}}: Unknown parameter |month= ignored (help)

Interfacing

Record representation clauses are a unique feature of the Ada language as far as the authors know, so there is no need to have a feature similar to attribute 'Bit_Order in other programming languages. It is common practice in other programming languages to use masks and bit operations explicitly, thus the native bit numbering must always be used.

Ada Programming/Attributes/'Bit Order

Description

Introduction

Ada 95

Ada 2005

Data Transfer

Example

Incorrect Usage

References

Interfacing

See also

Wikibook

Ada Reference Manual

Ada Rationale

References and notes

Further reading