Re: Representation clauses for base-64 encoding

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 11-12-27 13:23 , Georg Bauhaus wrote:
> On 25.12.11 11:17, Niklas Holsti wrote:

Actually, George Bauhaus wrote:

>>> There is middle ground, I think, insofar as it is possible
>>> to extract bits in Ada without thinking about shifts and masks,
>>> or logical operations.
>
> Just saying that using Ada, one may write operations involving
> single bits or slices of single bits simply by using arrays
> of Booleans that are packed.

Whether a Boolean array is packed to Component_Size = 1, with no gaps, 
depends on the Ada compiler. It is not a hard requirement in the Ada RM, 
as I understand it.

> I think I didn't say that one may read portably from I/O ports?

That's right, you didn't. But the "Base 64 encoding" problem by 
definition starts from a sequence of 8-bit groups, with a defined bit 
order: the first 6-bit group must be the high 6 bits of the first 8-bit 
group, and so on. This is a core part of the problem.

>>> Without claiming [...] portability of bit indexing
>>> of bits in a single octet [...]
>
> Thanks for illustrating my words in my code. ;-)

I didn't understand what you meant by that "without claiming", which is 
why I asked you to be clearer about the "desirable properties" that you 
assumed.

>> What are these "desirable properties" on which you rely, and where in the LRM
>> are they guaranteed?
>
> Everything (the "desirable properties") that an interested party
> might conclude after reading LRM 13.2.

All of RM 13.2 is non-binding recommendation; the text defines the 
recommended level of support, using "should". The only "shall" in 13.2 
is in a legality rule. No properties of packed Boolean arrays are 
"guaranteed" by 13.2.

> Yes, on some planet there
> might be an Ada compiler that does not handle packed bits
> reasonably well. ;-)

This is the kind of argument I am used to seeing in comp.lang.c: "it 
works for me, so never mind that the C standard says it is undefined 
behaviour".

Why didn't the RM authors write strict "shall" requirements in RM 13.2, 
and the rest of chapter 13? Apparently, they felt that some Ada 
compilers would not be able to implement all the recommendations with 
reasonable effort and performance.

> 13.2 drops alignment requirements dropped, in particular, so that
> I do not need to think about boundaries of storage element size
> groups of bits.

But there is not even a recommendation on the order in which bits in a 
packed Boolean array are indexed, as far as I can see.

> The Ada 85 Quality and Style Guide has this to say, in Chapter 10,
> http://www.adaic.org/resources/add_content/docs/95style/html/sec_10/10-6-3.html
>
> "Use modular types rather than packed Boolean arrays
>   when measured performance indicates."
>
> "Measured performance indicates", then , whether or not to
> resort to explicit shifting and logical operations.

Sure, if your program is too slow (but works) using packed Boolean 
arrays, you can try to speed it up by using modular types instead (but 
it might not become faster). That says nothing about portability; if you 
were happy with the limited (IMO) portability of packed Boolean arrays, 
you will not lose portability by moving to modular types (but you may 
have to find out in which order your Ada compiler indexes packed Boolean 
arrays, in order to transform your program correctly).

>
> I looked at how compilers will translate operations on slices of
> Booleans (-Os is an interesting option with GNAT). They will emit
> instructions for shifting and logical operations; no surprise.

No surprise, I agree. But the problem is the undefined indexing order.

Packed Boolean arrays are good and useful for bit-vector operations. But 
Unchecked_Conversion to and from other types, such as modular types, is 
not portable.

>
> So, would there be a portable Base64 algorithm that reads from
> a stream of storage elements, perhaps from a typical controller's
> 8-bit I/O port, that
>
> (*) shifts and "reasons" more reliably, readably, and portably,
>

Sure, use some Interfaces.Unsigned_N as a bit-buffer, as I sketched in 
an earlier message.

> (*) performs shifts and logical operations much faster
>      than the shifts and logical operations generated by
>      typical compilers for bit slices or representations,
>

You want a portable method that is *much faster* than less portable 
methods? That is a lot to ask...

The Unsigned_N-bit-buffer method is probably no slower than the 
unportable bit-slice method. The Unsigned_N-bit-buffer method may be 
slower than the method that uses records with representation clauses to 
convert three 8-bit groups into four 6-bix groups at a time, but the 
latter needsa machine with at least 24-bit "machine scalars".

> (*) runs on heterogeneous hardware with word size<= 16 bits?

The bit-buffer method works easily with any Unsigned_N with N >= 8+5 = 
13, so Unsigned_16 is ok. It can be made to work with just Unsigned_8, 
but with more difficulty.

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