!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_ type, and the problem is that Stream_Element is defined as "mod ", 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.) ****************************************************************