C/Ada memory alignment for BIT STRING type

[maxime-esa]

I inspected the memory layout of the C and Ada backends for BIT STRINGs, and it turns out that they do not align – and there is no way they can align with the current design.

In the C backend the BIT STRING types are stored and packed in an array of bytes, with MSB0 convention (bit 0 on the left, as per ASN.1 standard):

struct MyBitString  {
     int nCount,    // number of bits
     byte arr[n]     // number of bits / 8
}

In Ada, an array of BIT (unsigned int with range 0..1) is generated. And unfortunately while each BIT element uses 1 bit making the total size identical between C and Ada, the memory layout is different.

In Ada, the indexing of the BIT array does not relate to how it is stored in memory. In practice, the compiler stores the bits in LSB0 and in little endian form (on x86).

So if we have:

T ::= BIT STRING (SIZE(10)) 

In C if I set bit 0 and bit 9 to 1, the layout will be :

Byte 1         byte 2
10000000 01 (000000)

But in Ada (doing var.data(1) := 1 and var.data(10) := 1) it will be:

Byte 1 (bit 0 on the right)        Byte 2
00000001                                   00000010

As you see they don’t match, and there is no way to make them match (I checked all Ada Representation Clauses, but none will solve this).
To understand why, look at the indexing of the Ada array: it’s from 1 to 10, and not from 0 to 10. So already here there is a problem: at no point we say that we want the bit 0 on the left to be set. The index numbering is independent from the memory layout decided by the compiler

We could use an array index from 0 to 9 but that would not solve the issue. Actually I tried to make 100% sure, and I used gdb to inspect the memory layout:

(Note: there is actually one Ada representation clause (Bit_Order) that covers the bit ordering, but unfortunately it does not apply to arrays of bits or booleans. Only to records containing a sequence of named Boolean fields. In that case you can indicate in what order you want them stored.)

I think the only way to solve the issue is to generate the same structure as in C : an array of bytes containing the packed bits in MSB0 order. It won’t be possible to assign individual bits as easily but it is the only way I see to keep C/Ada memory alignment.

Since I don’t think there are many users of BIT STRINGs in Ada right now (Opengeode in TASTE is the main one, and it is transparent for the user anyway) I think the modification will not break too many people.
The modification in the type definition is trivial of course but I am not sure about the consequences for the uPER/ACN/XER encoders.