Version 1.1 of acs/ac-00109.txt

Unformatted version of acs/ac-00109.txt version 1.1
Other versions for file acs/ac-00109.txt

!standard B.2(6)          05-01-27 AC95-00109/01
!class Amendment 05-01-27
!status received no action 05-01-27
!status received 04-12-10
!subject Generic shift routines
!summary
!appendix

!topic Generic shift routines
!reference RM95 B.2
!from Adam Beneschan 04-12-10
!discussion

We found some publicly available Ada code on the Internet, the Ada Web
Server, that relies on an undocumented GNAT feature:

      function Shift_Left
        (Value  : in Stream_Element;  -- i.e. Ada.Streams.Stream_Element
         Amount : in Natural)
           return Stream_Element;
      pragma Import (Intrinsic, Shift_Left);

This appears to point up a missing feature in Ada.  There doesn't
appear to be a way to accomplish this portably, even though there are
shift routines in Interfaces.  To use the shift routines in
Interfaces, you have to convert the Stream_Element to the appropriate
Unsigned_<n> type, and the problem is that Stream_Element is defined
as "mod <implementation-defined>", so you cannot write code that work
correctly on every implementation if the modulus of Stream_Element
varies from one implementation to the next.

Possible solution: Add generic versions of the five shift functions in
Interfaces: Generic_Shift_Left, Generic_Shift_Right, etc.  They would
take a generic formal modular parameter (although I don't know what
they would do if given something whose modulus is not a power of 2).
These generics wouldn't have to be in Interfaces---they could be
declared somewhere else.  Presumably, for modular types whose sizes
correspond to sizes that the target machine works with easily (mod
2**8, mod 2**16, mod 2**32), calling an instance of the function would
result in a single machine instruction.

****************************************************************

From: Pascal Obry
Sent: Friday, December 10, 2004  12:28 PM

 > We found some publicly available Ada code on the Internet, the Ada Web
 > Server, that relies on an undocumented GNAT feature:

This is not an undocumented GNAT feature. It is said in the GNAT Reference
Manual section "5. Intrinsic Subprograms":

<<
In standard Ada 95, the Rotate_Left function is available only for the
predefined modular types in package Interfaces. However, in GNAT it is
possible to define a Rotate_Left function for a user defined modular type or
any signed integer type as in this example:
...
>>

Idem for [Shift/Rotate]_[Left/Right]. Now I agree with you that this is
not portable.

****************************************************************

From: Adam Beneschan
Sent: Friday, December 10, 2004  12:53 PM

Sorry about that.  It looks like I was looking at an old version of
the GNAT Reference Manual.

****************************************************************

From: Pascal Obry
Sent: Friday, December 10, 2004  1:09 PM

No problem. BTW, I would be in favor of making this feature (all user's
defined modular type must support [Shift/Rotate]_[Left/Right]) standard. I
think it is cleaner than your generic proposal. But I strongly agree with you
that we need a solution to support this in Ada.

****************************************************************

From: Adam Beneschan
Sent: Friday, December 10, 2004  1:14 PM

Sounds like defining some new attributes might be the way to go
(T'Shift_Left(X,N), etc.)

****************************************************************

From: Randy Brukardt
Sent: Friday, December 10, 2004  2:01 PM

In order to do that, you would have to figure out what it means for a
non-binary modulus. And you'd have to decide whether it really is worth
making compilers support it for oddball types that have a modulus that is a
power of two:
    type Small is mod 2**6;

It would be better (if these things are really useful, which I doubt) to
define this on other predefined types (like Stream_Element), and leave it at
that.

But it is almost always better to avoid using shifting altogether in your
code (because you always have to go to look up what it means exactly if
you're debugging), and simply use appropriate multiplies and divides. You'll
get the same code so long as your compiler is reasonable (most are) and the
multiply or divide is by a constant. (That isn't true for signed types, but
we're talking about modular types here.) The only place where shift
operations help is when you don't know the shift amount until runtime; then
the only way to use the hardware instructions is to have special operations
like the ones in Interfaces. But that only works if the type matches the
hardware.

In this particular case, the whole debate is kinda silly.
Stream_Element'Size = 8 on every Ada 95 compiler that has ever existed other
than the U2200 one we did (and I very much doubt that anyone cares about
that compiler, given that we never sold a copy...). So the only
non-portability is theoretical, not real.

****************************************************************

From: Tucker Taft
Sent: Friday, December 10, 2004  3:24 PM

I think having such a generic would be useful as well,
though I agree there are some issues with non-binary
moduli that would have to be addressed (such as it
fails to instantiate, or it raises Program_Error).

I agree that multiply/divide is generally more portable
when it works, but rotate obviously can't be accomplished
this way.  Also, we somewhat cooked our own goose by
providing these Rotate/Shift operations in the first place.
Actually, the GNAT approach of simply making
pragma Import(Intrinsic, Shift_Left) work as desired
isn't bad.  We could create minimal requirements for
support of "natural"-sized power-of-2 modular types, and
allow implementors to go beyond that if they so choose.
This would presumably go in C.1 Access to Machine Operations.

It's lighter weight than a generic, and can be very
implementation-oriented rather.

****************************************************************

From: Nick Roberts
Sent: Friday, December 10, 2004  3:29 PM

> It would be better (if these things are really useful, which
> I doubt) to define this on other predefined types (like
> Stream_Element), and leave it at that.

Bit rotation of values of the type Stream_Element would be useful, without a
shadow of doubt, in order to be able to read compacted values of arbitrary
bit lengths (within limits) from a file. Reading a file which uses a modern
compression algorithm almost always requires doing this. The same applies to
writing such files.

> But it is almost always better to avoid using shifting
> altogether in your code (because you always have to go to
> look up what it means exactly if you're debugging), and
> simply use appropriate multiplies and divides.

It might be considered a little more evident to use an operation that is
named "Shift_...", if that is what you are really doing. Furthermore,
rotation cannot be achieved this way, and it is rotation that would be most
useful for values of the type Stream_Element, for the reasons I have given.

> ... then the only way
> to use the hardware instructions is to have special
> operations like the ones in Interfaces. But that only works
> if the type matches the hardware.

Agreed.

> In this particular case, the whole debate is kinda silly.
> Stream_Element'Size = 8 on every Ada 95 compiler that has
> ever existed other than the U2200 one we did (and I very much
> doubt that anyone cares about that compiler, given that we
> never sold a copy...). So the only non-portability is
> theoretical, not real.

But I think adding Rotate_Left and Rotate_Right for Stream_Element to the
standard would be justified, because they would be useful, easily added to
the standard, easily implemented, and there would be an advantage (albeit a
small one) to their being standard.

Suggested wording:

[Add to package Ada.Streams in 13.13.1:]

   function Rotate_Left  (Value:  in Stream_Element;
                          Amount: in Natural) return Stream_Element;

   function Rotate_Right (Value:  in Stream_Element;
                          Amount: in Natural) return Stream_Element;

[Add a paragraph after 13.13.1 (9) with wording taken from B.2 (9):]

For the type Stream_Element, rotating functions are specified in the
specification of package Ada.Streams above. These functions are Intrinsic.
They operate on a bit-by-bit basis, using the binary representation of the
value of the operand Value to yield a binary representation for the result.
The Amount parameter gives the number of bits by which to rotate.

[End.]

I note that B.2 (9) does not define the meaning of 'left' and 'right'. To be
pedantic, one might add something like this:

Each bit numbered i, in the representation of a value, contributes 2^i to
the value if the bit is 1 (and contributes zero if the bit is 0). Shifting
left by Amount 1 causes bit i+1 to take the value of bit i, for all i in the
range 0 to w-2, where w is the number of bits representing the value. Bit 0
takes the value that is 'shifted in'.

A more succinct form is:

Shifting left by Amount 1 causes each bit i+1 to take the value of bit i.

****************************************************************

From: Pascal Leroy
Sent: Friday, December 10, 2004  5:00 PM

Nothing is easily added to the Standard at this point.  The core language is
going into final review by the ARG on December 15th, and the only changes
permitted at this point are either editorial or fixes to severe inconsistencies
found during the review.  Don't even think of adding any new feature now.  (Of
course, suggestions will be filed for consideration for the next revision, but
that's at least 5 years from now.)

****************************************************************


Questions? Ask the ACAA Technical Agent