Bit-level control of layout of packed arrays

[sttaft]

This issue was discussed in the general issue #134 . I am moving the discussion here so it is not lost.

[sttaft]

hw762 commented yesterday
hw762
yesterday

I'd like to see representation clause (esp. Bit_Order) available for arrays, so it is easier to deal with bit-level structures used for data exchange.

sttaft
18 hours ago
Member

I'd like to see representation clause (esp. Bit_Order) available for arrays, so it is easier to deal with bit-level structures used for data exchange.

Ada provides bit-level control over the size of components of a packed array, and bit-level control over the representation of a record. GNAT provides endianness control of scalars via Scalar_Storage_Order. I am curious what further control you would expect.

hw762
12 hours ago

    I'd like to see representation clause (esp. Bit_Order) available for arrays, so it is easier to deal with bit-level structures used for data exchange.

Ada provides bit-level control over the size of components of a packed array, and bit-level control over the representation of a record. GNAT provides endianness control of scalars via Scalar_Storage_Order. I am curious what further control you would expect.

I encountered this when I tried to implement this spec: https://arrow.apache.org/docs/format/Columnar.html#validity-bitmaps

In short, I need an Ada boolean array that is organized like the bitmap specified in the link to communicate with C. This bitmap's storage unit is byte, and the bits follow the Least-Significant-Bit Ordering within each byte. The closest I can get is type Validity is array (Natural range <>) of Boolean with Component_Size => 1, Pack, but this doesn't guarantee the LSB ordering, because I can't set bit order for array.

sttaft
10 hours ago
Member

I encountered this when I tried to implement this spec: https://arrow.apache.org/docs/format/Columnar.html#validity-bitmaps

In short, I need an Ada boolean array that is organized like the bitmap specified in the link to communicate with C. This bitmap's storage unit is byte, and the bits follow the Least-Significant-Bit Ordering within each byte. The closest I can get is type Validity is array (Natural range <>) of Boolean with Component_Size => 1, Pack, but this doesn't guarantee the LSB ordering, because I can't set bit order for array.

Good point. There is no Bit_Order attribute for packed arrays, so which bit of the byte would correspond to index 0 of a bit-packed array (0..7) is going to be determined by the Default_Bit_Order of the machine. You could write:

pragma Assert (System.Default_Bit_Order = Low_Order_First);

to be sure that you are on a machine where the low-order bit is number 0, or you could do all of your indexing into the bit-packed array using a function to compute the index as a function of the value of System.Default_Bit_Order.

Allowing Bit_Order to be specified on a bit-packed array would seem to make sense.

hw762
9 hours ago

Good point. There is no Bit_Order attribute for packed arrays, so which bit of the byte would correspond to index 0 of a bit-packed array (0..7) is going to be determined by the Default_Bit_Order of the machine. You could write:

pragma Assert (System.Default_Bit_Order = Low_Order_First);

to be sure that you are on a machine where the low-order bit is number 0, or you could do all of your indexing into the bit-packed array using a function to compute the index as a function of the value of System.Default_Bit_Order.

Allowing Bit_Order to be specified on a bit-packed array would seem to make sense.

I don't think Default_Bit_Order is required for the arrays. If I read the spec right, Ada compiler is allowed to specify bits in arbitrary order, and the compiler is probably allowed to start the index on the 3rd bit.

9 hours ago
sttaft
9 hours ago
Member

I don't think Default_Bit_Order is required for the arrays.

Default_Bit_Order is a constant declared in System. It isn't specific to arrays or records, though it is true that its primary impact is on record representation clauses. On the other hand, 13.5.3(2) says:

...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.

The term "first bit" would seem to relate as well to the first element of a bit=packed array, though perhaps that is wishful thinking.

If I read the spec right, Ada compiler is allowed to specify bits in arbitrary order, and the compiler is probably allowed to start the index on the 3rd bit.

I'd be curious what gave you that impression. The language doesn't seem to imply this arbitrariness, though I suppose it doesn't say much about the exact mapping between the Nth array component and bits in memory. In general, the language doesn't specify semantics that are considered "obvious", instead saying "conventional meaning" (such as the meaning of "+"), but perhaps it should in this case ...

8 hours ago
liampwll
8 hours ago

I'd be curious what gave you that impression. The language doesn't seem to imply this arbitrariness, though I suppose it doesn't say much about the exact mapping between the Nth array component and bits in memory. In general, the language doesn't specify semantics that are considered "obvious", instead saying "conventional meaning" (such as the meaning of "+"), but perhaps it should in this case ...

There's some other subtlety that needs to be defined here too. For example: If we have a bit-packed array which is smaller than a storage unit then which side of the storage unit is it aligned to? What about spanning multiple storage units where size does not fit cleanly in to n storage units?

7 hours ago
sttaft
7 hours ago
Member

There's some other subtlety that needs to be defined here too. For example: If we have a bit-packed array which is smaller than a storage unit then which side of the storage unit is it aligned to? What about spanning multiple storage units where size does not fit cleanly in to n storage units?

You have convinced me we need to specify this more completely. My sense is that once it is clear where the first element goes, the rest will be pretty clear, but I agree that the position of the first element of a bit-packed array needs to be more clearly specified, and perhaps be controllable via a Bit_Order attribute.
nholsti
nholsti commented 2 hours ago
nholsti
2 hours ago · edited by nholsti

My sense is that once it is clear where the first element goes, the rest will be pretty clear, but I agree that the position of the first element of a bit-packed array needs to be more clearly specified, and perhaps be controllable via a Bit_Order attribute.

I think it is more complex than that. The C bitmap structure that @hw762 wants to match is defined on the C side as an array of unsigned char. To access bit number j, the array is indexed with j/8 to get an unsigned char, from which one accesses bit number j mod 8, counting from the least significant bit. If one tries to match the whole bitmap with type Validity is array (Natural range <>) of Boolean with Component_Size => 1, Pack then that can cover many storage units. Nothing currently constrains the Ada side to access the array in Storage_Unit pieces or in unsigned char pieces; it could also access the array in "word" pieces (say, 64 bits) and then index bits in the word. So the order of Storage_Units in a word also comes into it. To make it simpler the new feature should perhaps be limited to packed arrays that are no larger than the maximum scalar.

For @hw762 to have a portable solution, the Ada side should define the bitmap as an array of Interfaces.C.unsigned_char, and only use 8-bit packed Boolean arrays to access the desired bit in the unsigned_char (via Unchecked_Conversion). Even that has some intricacies if C unsigned char is larger than 8 bits, but that is quite rare.

I, too, have been frustrated by the inability to control the bit-level index order of packed arrays. For example, I had a target system with 32 levels of interrupts, and several 32-bit control registers with one bit per interrupt level, but I could not describe those registers as packed Boolean arrays because of this index/bit order problem. Of course I worked around it by using shift-and-mask to implement my own bit-level access operations. It was annoying, but I don't know if it was annoying enough to merit a fix to Ada.

liampwll
1 hour ago

The C bitmap structure that @liampwll wants to match

@hw762 for the original rather than me.

it could also access the array in "word" pieces (say, 64 bits) and then index bits in the word.

I think in the rare cases where this matters you're probably better off making the whole array Atomic (or Volatile_Full_Access in GNAT) and manually dividing it in to chunks of the size you want.

nholsti
31 minutes ago

    The C bitmap structure that [@liampwll](https://github.com/liampwll) wants to match

[@hw762](https://github.com/hw762) for the original rather than me.

Apologies (corrected in my comment).

    it could also access the array in "word" pieces (say, 64 bits) and then index bits in the word.

I think in the rare cases where this matters you're probably better off making the whole array Atomic (or Volatile_Full_Access in GNAT) and manually dividing it in to chunks of the size you want.

Atomicity and volatility are not relevant for the lay-out of packed arrays as such, so I believe you misunderstood my point. Consider the C bitmap that @hw762 wants to use and bit number 10, say. In C, that is bit number 2 in unsigned char number 1, that is, in the second octet (assuming 8-bit chars). Assume that the Ada type is defined as a packed array of bits, many octets long, and the compiler accesses it in 32-bit word-sized units. Depending on the octet endianness of the processor, octet number 1 can be mapped to the second-lowest octet or the second-highest octet in the first 32-bit word, so it would have different bit number in the word, depending on octet endianness, and so a different index in the Ada array, I would assume. The C bitmap and the Ada bitmap would match for one endianness but not for the other.

You may ask why an Ada compiler should access a packed Boolean array in units larger than an octet. It seems to me that using register-wide accesses would make better use of memory bandwidth and register space, but no doubt that will depend on details of the processor and the compiler.

mosteo
29 minutes ago
Member

I am curious what further control you would expect.

I found that there's no way to specify row-major or column-major that isn't tied to the Fortran interface. Arguably this should be a general feature and not part of Fortran interfacing.

Furthermore, it doesn't work (in GNAT) when used together with Pack.

I posted more details about this here: https://forum.ada-lang.io/t/specifying-major-order-for-packed-matrix/2125

In my case what I was doing was this: https://github.com/mosteo/braillart

Plenty of workaround available, but I found surprising that for all the control that there is for individual bits in records, I couldn't do the same with arrays.

[kevlar700]

Sorry if I haven't payed enough attention to the details but doesn't it work when you specify the bit size using component_size => 1?

"https://github.com/AdaCore/Ada_Drivers_Library/blob/master/arch/ARM/STM32/svd/stm32f429x/stm32_svd-gpio.ads"

   subtype MODER_Element is HAL.UInt2;

   --  MODER array
   type MODER_Field_Array is array (0 .. 15) of MODER_Element
     with Component_Size => 2, Size => 32;

   --  GPIO port mode register
   type MODER_Register
     (As_Array : Boolean := False)
   is record
      case As_Array is
         when False =>
            --  MODER as a value
            Val : HAL.UInt32;
         when True =>
            --  MODER as an array
            Arr : MODER_Field_Array;
      end case;
   end record
     with Unchecked_Union, Size => 32, Volatile_Full_Access,
          Bit_Order => System.Low_Order_First;

   for MODER_Register use record
      Val at 0 range 0 .. 31;
      Arr at 0 range 0 .. 31;
   end record;

   --  OTYPER_OT array
   type OTYPER_OT_Field_Array is array (0 .. 15) of Boolean
     with Component_Size => 1, Size => 16;

   --  Type definition for OTYPER_OT
   type OTYPER_OT_Field
     (As_Array : Boolean := False)
   is record
      case As_Array is
         when False =>
            --  OT as a value
            Val : HAL.UInt16;
         when True =>
            --  OT as an array
            Arr : OTYPER_OT_Field_Array;
      end case;
   end record
     with Unchecked_Union, Size => 16;

Edit: Perhaps in this case the array bit order just matches the system bit order. I forget the details without testing and never encounter high order except for networks where bytes are used. I do have a comment in this file relating to pack but I don't have the time to be precise about this.

https://github.com/kevlar700/hex_string/blob/main/hex_string_test/src/hex_string_test.adb

-- even "with pack" this works without a use clause but this is here to
-- limit warning(s) to those that are interesting in this case. Namely
-- that Test_Array_2 within Input_2_T above is not affected by the
-- High_Order_First. Note that using High_Order_First on a little endian
-- machine can incur byte swapping overheads. High_Order_First does however
-- provide some consistency to the reader. Where byte reversal of the whole
-- record would not.

[jprosen]

Can't you just use an array of System. Unsigned_8? There you have all the bit manipulations you need

[nholsti]

Can't you just use an array of System. Unsigned_8? There you have all the bit manipulations you need

Certainly you could. And you could also omit record representation clauses from Ada and use shift-and-mask to access the fields in a packed record. The point is that while you can use a packed Boolean array to view, say, a 32-bit word as a vector of 32 Booleans, you cannot control whether index zero corresponds to the least significant bit or the most significant bit or to something in between. That currently missing control over the mapping of the packed array elements to bit fields is what is sought here.

[nholsti]

@sttaft wrote:

which bit of the byte would correspond to index 0 of a bit-packed array (0..7) is going to be determined by the Default_Bit_Order of the machine

I did not find such a rule in the Ada RM. Can you say where it is?

[hw762]

To match this specification (here in case the formatting makes it hard to find, also summarized below):

• Byte storage unit
• Little-endian byte order in the array
• Least significant bit enumeration

Is something like this:

type Validity is array (Natural range <>) of Interface.Unsigned_8 with Convention => C;
function Get_Bit(V : Validity; B : Natural) return Boolean;
procedure Set_Bit(V : Validity; B : Natural; Val : Boolean);
-- ...

Where the storage unit is enforced by hand (via uint8 array), and wrapper functions that correctly performs bit operation using bitmasks. However, if Ada has a way to specify bit order for array, then it just becomes this hypothetical version:

type Validity is array (Natural range <>) of Boolean with Component_Size => 1, Pack, Bit_Order => System.Low_Bit_Order;

And this in turn makes something like this much easier:

type Table (Size : Natural) is record
  V : Validity (1 .. Size);
  D : Data (1 .. Size);
end record;

... because you can't put Size / 8 in a discriminant.