!standard B.2(9)                                     18-04-26  AI12-0264-1/03
!class ramification 18-03-28
!status Amendment 1-2012 18-04-05
!status WG9 Approved 16-06-22
!status ARG Approved 8-0-2  18-04-02
!status work item 18-03-28
!status received 18-03-13
!priority Low
!difficulty Easy
!subject Overshifting and overrotating
!summary 

The language defines the results of all shifting and rotating operations,
based only on the modulus of the unsigned type.

!question

How do the Shift_ family of functions handle "overshifting", e.g. if
Shift_Left is called with an Amount large enough that the number
represented by the result would not fit in the type of the operand. Is
this implementation-defined? (No.)

!response

B.2 defines package Interfaces, which is a required (not optional) package
of an Ada implementation. It explicitly allows implementation-defined types
to be declared in the package (and implementation-defined child packages).
However, these are the only things that are allowed to be
implementation-defined about this package; everything else is specified
by the language.

So the results of "overshifting" and "overrotating" using these operations
is defined by the language: for instance, it is 0 for Shift_Left and
Shift_Right.

!wording

Add after B.2(9.a):

AARM To Be Honest: "Shifting" and "rotating" have the conventional meaning.
Neither of these terms is usefully defined by the usual normative references
of the Standard, so we provide pseudo-code here to describe the intended
semantics of the above wording (all operations in these examples are using
modular semantics).

[Editor's note: "n" here is italicized in both Unsigned_n and when it stands
alone, as in "2**(n-1)".]

      function Rotate_Left (Value : Unsigned_n; Amount : Natural)
         return Unsigned_n is
         Result : Unsigned_n := Value;
         Bit : Unsigned_n range 0 .. 1;
      begin
         for Count in 1 .. Amount loop
             Bit := Result/2**(n-1); -- High-bit of Result 
             Result := Result*2 + Bit;
         end loop;
         return Result;
      end Rotate_Left;


      function Rotate_Right (Value : Unsigned_n; Amount : Natural)
         return Unsigned_n is
         Result : Unsigned_n := Value;
         Bit : Unsigned_n range 0 .. 1;
      begin
         for Count in 1 .. Amount loop
            Bit := Result mod 2; -- Low-bit of Result
            Result := Result/2 + (Bit * 2**(n-1));
         end loop;
         return Result;
      end Rotate_Right;

  
      function Shift_Left (Value : Unsigned_n; Amount : Natural)
         return Unsigned_n is
         Result : Unsigned_n := Value;
      begin
         for Count in 1 .. Amount loop
            Result := Result * 2;
         end loop;
         return Result;
      end Shift_Left;

      function Shift_Right (Value : Unsigned_n; Amount : Natural)
         return Unsigned_n is
         Result : Unsigned_n := Value;
      begin
         for Count in 1 .. Amount loop
            Result := Result / 2;
         end loop;
         return Result;
      end Shift_Right;


      function Shift_Right_Arithmetic (Value : Unsigned_n; Amount : Natural)
         return Unsigned_n is
         Result : Unsigned_n := Value;
         Neg : constant Boolean :=
            Result/2**(n-1) = 1; -- High-bit of Result 
      begin
         for Count in 1 .. Amount loop
            if Neg then
               Result := Result / 2 + 2**(n-1);
            else
               Result := Result / 2;
            end if;
         end loop;
         return Result;
      end Shift_Right_Arithmetic;

[Editor's note: We use iteration in all of these examples (even though
some can be simplified) in order to show the relationship with the normative
wording, specifically how "The Amount parameter gives the number of bits by
which to shift or rotate" is interpreted.]

These generally correspond to machine instructions, although there may not
be an exact match in terms of boundary conditions, as Ada requires the correct
result to be produced for all values of Amount. 
End AARM Note.

!discussion

B.2(9) is the Implementation Requirement that gives the definition and
operation of the shifting and rotating operations. It says:

  For each such modular type in Interfaces, shifting and rotating subprograms
  as specified in the declaration of Interfaces above. These subprograms are 
  Intrinsic. They operate on a bit-by-bit basis, using the binary
  representation of the value of the operands to yield a binary representation
  for the result. The Amount parameter gives the number of bits by which to 
  shift or rotate. For shifting, zero bits are shifted in, except in the case
  of Shift_Right_Arithmetic, where one bits are shifted in if Value is at
  least half the modulus. 

However, "shifting" and "rotating" are not defined by the Standard, the
English meaning is not specific enough to define these operations, and the
terms are not defined by the normative mathematical reference for the
Standard.

Since "everyone knows" what these operations do -- they're commonly
implemented directly in hardware -- we chose not to modify the normative
wording. More precisely defining the terms is just as likely to introduce bugs
as define the behavior. However, we do add an AARM To-Be-Honest note so that
any future questions about the intended semantics can be answered there.

!ASIS

No ASIS effect.

!ACATS test

Nothing new here (we hope), so an ACATS test is not needed. Existing test
CXB2001 include a few examples of overshifting. We could create a test
specifically to check overshifting, especially using very large Amounts, but
that seems to be of fairly low value.

!appendix

!topic Restricting allowed behaviour of Interfaces w.r.t overshifting
!reference Ada 202x RMB.2(7--10)
!from Christoffer Stjernlöf (18-03-13)
!keywords interfaces shifting erroneous execution implementation defined
!discussion

Hello! I hope this is the right place to turn to.

My issue, specifically, is regarding how the Shift_ family of functions
handle "overshifting", e.g. if Shift_Left is called with an Amount large
enough that the number represented by the result would not fit in the
type of the operand. I realise this is implementation defined. What I'm
suggesting is that the standard more explicitly restricts the number of
valid behaviours.

There are at least three ways the implementation can react to over-
shifting:

1. The overshifted bits could be silently dropped. This is what happens
   with GNAT when I test it; it is the way many other languages treat
   the situation; and it appears to be what many Ada users assume from
   their implementation too.

2. The program could raise a CONSTRAINT_ERROR or something along those
   lines. This would sorta-kinda fit in with the rest of Ada.

3. The execution could become erroneous. This is what C does (and,
   according to rumour, even some hardware circuits.)

You have probably guessed already that I'd like the standard to
explicitly forbid option three, but I have no idea of the economies
involved in such a decision.

(Maybe the standard already forbids it, only the wording used does not
make that immediately obvious.)

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

From: Niklas Holsti
Sent: Wednesday, March 14, 2018  10:56 AM

> !topic Restricting allowed behaviour of Interfaces w.r.t overshifting 
> !reference Ada 202x RMB.2(7--10) !from Christoffer Stjernlöf 
> (18-03-13) !keywords interfaces shifting erroneous execution 
> implementation defined !discussion
>
> Hello! I hope this is the right place to turn to.

I believe it is the right place (but comp.lang.ada could also have been).

> My issue, specifically, is regarding how the Shift_ family of 
> functions handle "overshifting", e.g. if Shift_Left is called with an 
> Amount large enough that the number represented by the result would 
> not fit in the type of the operand. I realise this is implementation defined.

Why do you think that the behaviour is implementation-defined? I don't see 
anything suggesting that in the RM, current or draft.

The concrete declaration of package Interfaces is implementation-defined 
because the supported bit-widths depend on the implementation. The behaviour
of the shift operations is described without mentioning the implementation.

> There are at least three ways the implementation can react to over-
> shifting:
>
> 1. The overshifted bits could be silently dropped. This is what happens
>    with GNAT when I test it; it is the way many other languages treat
>    the situation; and it appears to be what many Ada users assume from
>    their implementation too.

I have understood that this is what the RM says, with the background that all 
operations on modular types should be understood in the modular way.

As the question has now been raised, I agree the RM should be extended to say
clearly what happens for such "overshifting"; perhaps as a "Ramification"
annotation.

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

From: Tucker Taft
Sent: Wednesday, March 14, 2018  11:17 AM

>> Hello! I hope this is the right place to turn to.
> 
> I believe it is the right place (but comp.lang.ada could also have been).

Ada-comment is better if you want the "official" Ada language maintenance 
group (ARG) to be aware of your concern.

>> My issue, specifically, is regarding how the Shift_ family of 
>> functions handle "overshifting", e.g. if Shift_Left is called with an 
>> Amount large enough that the number represented by the result would 
>> not fit in the type of the operand. I realise this is implementation defined.
> 
> Why do you think that the behaviour is implementation-defined? I don't see 
> anything suggesting that in the RM, current or draft.
> 
> The concrete declaration of package Interfaces is implementation-defined
> because the supported bit-widths depend on the implementation. The
> behaviour of the shift operations is described without mentioning the 
> implementation.

Agreed.  There was no intent for the semantics of a shift operation to be
implementation-defined.
 
>> There are at least three ways the implementation can react to over-
>> shifting:
>> 
>> 1. The overshifted bits could be silently dropped. This is what happens
>>   with GNAT when I test it; it is the way many other languages treat
>>   the situation; and it appears to be what many Ada users assume from
>>   their implementation too.
> 
> I have understood that this is what the RM says, with the background that 
> all operations on modular types should be understood in the modular way.

Correct.  Modular types in general never produce an exception on "overflow."
Perhaps we should have defined an equivalence with multiplying by 2, followed
by performing a "mod" operation on the result.  That in any case was the
intent.
 
> As the question has now been raised, I agree the RM should be extended to
> say clearly what happens for such "overshifting"; perhaps as a
> "Ramification" annotation.

Yes, it wouldn't hurt to clarify the equivalence with multiplying by 2,
mod T'Modulus.

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

From: Randy Brukardt
Sent: Wednesday, March 14, 2018  9:11 PM

> Agreed.  There was no intent for the semantics of a shift operation to 
> be implementation-defined.

I certainly agree with the intent. Moreover, the wording of B.2 says that the
types in package Interfaces are implementation-defined, there is nothing in
the subclause that would make anything else in the package 
implementation-defined. However, the only definition of these operations is 
given in Implementation Requirements, and it says:

  For each such modular type in Interfaces, shifting and rotating subprograms
  as specified in the declaration of Interfaces above. These subprograms are 
  Intrinsic. They operate on a bit-by-bit basis, using the binary
  representation of the value of the operands to yield a binary representation
  for the result. The Amount parameter gives the number of bits by which to 
  shift or rotate. For shifting, zero bits are shifted in, except in the case
  of Shift_Right_Arithmetic, where one bits are shifted in if Value is at
  least half the modulus. 

Neither the terms "shift" or "rotate" is defined by the Standard, I doubt that
the English meaning is of any use, and the mathematical references (using the
Mathworld.com engine) don't make much sense in this context (the definition of
shift made no sense when applied to bits, and there is no definition of
rotate, the closest is of "rotation", which has a cool rotating polygon on the
page but otherwise is no help). Thus they're formally undefined. So *I*
interpreted them as matching the five equivalent instructions on the Intel 
8086. Moreover, "the number of bits to shift or rotate" doesn't seem to fit
into any obvious definition either. *I* interpreted those as essentially 
iterating a single bit shift or rotate that many times.

If we really want to match the intent, we have to describe these operations in
more detail, or at least put in a To-Be-Honest note. We could steal the 
definitions from the Pentium processor manual I have on the shelf. They're in
pseudo code in something that looks like Algol (I've dropped the carry bit 
stuff and used the names of the Ada parameters):

      (* ROL - Rotate Left *)
      temp <- Amount;
      while (temp <> 0) do
          tempbit <- high-bit of (Value);
          Value <- Value*2 + tempbit;
          temp <- temp - 1;
      od;

which would make Ada pseudo code something like (adjusting for the fact that 
these are functions and "n" here is the italized "n" from Unsigned_n):

     function Rotate_Left (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
        Bit : Unsigned_n;
     begin
        while Count /= 0 loop
            Bit := Result mod 2**(n-1)/2**(n-1); --high-bit of Result 
            Result := Result*2 + Bit;
            Count := Count - 1;
        end loop;
     end Rotate_Left;

     function Rotate_Right (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
        Bit : Unsigned_n;
     begin
        while Count /= 0 loop
            Bit := Result mod 2; -- low-bit of Result
            Result := Result/2 + (Bit * 2**(n-1));
            Count := Count - 1;
        end loop;
     end Rotate_Right;

     function Shift_Left (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
     begin
        while Count /= 0 loop
            Result := Result * 2;
            Count := Count - 1;
        end loop;
     end Shift_Left;

     function Shift_Right (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
     begin
        while Count /= 0 loop
            Result := Result / 2;
            Count := Count - 1;
        end loop;
     end Shift_Right;

     function Shift_Right_Arithmetic (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
        Neg : Boolean :=
          (Result mod 2**(n-1)/2**(n-1) = 1; -- High-bit of Result 
     begin
        while Count /= 0 loop
            if Neg then
               Result := Result / 2 + 2**(n-1);
            else
               Result := Result / 2;
            end if;
            Count := Count - 1;
        end loop;
     end Shift_Right_Arithmetic;

Probably we'd want a note that these typically correspond to hardware 
instructions. For the Intel x86, these correspond to ROL/ROR/SHL/SHR/SAR.

(Aside: The OP's question probably comes from the rather bizarre design of 
these instructions. On the original 8086, there was no counted shifts, you had
to use the single bit version. Then shifts that took a register parameter were
added, but only the bottom 5 bits of the register were used.
Then on later processors, the operation started using all 8-bits. For C, they
probably just wanted to use these instructions without adornment, thus the 
implementation-defined behavior of overshifting. But Ada never has worked that
way in anyone's mind - operations either work as defined or raise an exception
[not justified here].

For Janus/Ada, our optimizer includes various identities, which include 
"overshifted" shifts: A - A = 0, A / A = 1, A ShiftL 32 = 0, etc. If the count
is dynamic (like a function call), then this doesn't happen, so we have to
make sure that the generated code is consistent with that -- regardless of
whatever the hardware does. That's the Ada way. :-)

...
> Yes, it wouldn't hurt to clarify the equivalence with multiplying by 
> 2, mod T'Modulus.

That's just the Shift_Left case (the easiest). We'd need all five operations 
(see above for one way to do it - the math above is "obviously" modular since
the types are modular types). And it hardly is a clarification -- as I noted 
above, by the definitions of the RM, shift and rotate are pretty much
undefined (even though everyone "knows" what is meant).

Sounds like an AI is needed; we could make it a ramification (if we're not 
going to change the normative text) but adding an extensive AARM note probably
ought to be vetted by the group.

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

From: Randy Brukardt
Sent: Thursday, March 15, 2018  12:33 AM

...
>      function Rotate_Left (Value : Unsigned_n; Amount : Natural)
>         return Unsigned_n is
>         Count : Natural := Amount;
>         Result : Unsigned_n := Value;
>         Bit : Unsigned_n;
>      begin
>         while Count /= 0 loop
>             Bit := Result mod 2**(n-1)/2**(n-1); --high-bit of Result 
>             Result := Result*2 + Bit;
>             Count := Count - 1;
>         end loop;
>      end Rotate_Left;

These routines have a few paren issues, are missing "return Result", and 
probably ought to use a for loop. Could also add bounds to Bit to make the
intent clearer. For the above:

      function Rotate_Left (Value : Unsigned_n; Amount : Natural)
         return Unsigned_n is
         Result : Unsigned_n := Value;
         Bit : Unsigned_n range 0 .. 1;
      begin
         for Cnt in 1 .. Amount loop
             Bit := (Result mod 2**(n-1))/2**(n-1); --high-bit of Result 
             Result := Result*2 + Bit;
         end loop;
         return Result;
      end Rotate_Left;

The others could be changed similarly, I'll leave that as an exercise for
the editor. :-)

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

From: Jeff Cousins
Sent: Thursday, March 15, 2018  12:53 PM

Doing all five, I think it should be:

      function Rotate_Left (Value : Unsigned_n; Amount : Natural)
         return Unsigned_n is
         Result : Unsigned_n := Value;
         Bit : Unsigned_n range 0 .. 1;
         use type Unsigned_n;
      begin
         for Cnt in 1 .. Amount loop
--             Bit := (Result mod 2**(n-1))/2**(n-1); -- High-bit of Result 
             Bit := Result/2**(n-1); -- High-bit of Result 
             Result := Result*2 + Bit;
         end loop;
         return Result;
      end Rotate_Left;


     function Rotate_Right (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
        Bit : Unsigned_n;
        use type Unsigned_n;
     begin
        while Count /= 0 loop
            Bit := Result mod 2; -- Low-bit of Result
            Result := Result/2 + (Bit * 2**(n-1));
            Count := Count - 1;
        end loop;
        return Result;
     end Rotate_Right;

  
    function Shift_Left (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
        use type Unsigned_n;
     begin
        while Count /= 0 loop
            Result := Result * 2;
            Count := Count - 1;
        end loop;
        return Result;
     end Shift_Left;

     function Shift_Right (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
        use type Unsigned_n;
     begin
        while Count /= 0 loop
            Result := Result / 2;
            Count := Count - 1;
        end loop;
        return Result;
     end Shift_Right;


     function Shift_Right_Arithmetic (Value : Unsigned_n; Amount : Natural)
        return Unsigned_n is
        Count : Natural := Amount;
        Result : Unsigned_n := Value;
        use type Unsigned_n;
        Neg : constant Boolean :=
--          (Result mod 2**(n-1))/2**(n-1) = 1; -- High-bit of Result 
          Result/2**(n-1) = 1; -- High-bit of Result 
     begin
        while Count /= 0 loop
            if Neg then
               Result := Result / 2 + 2**(n-1);
            else
              Result := Result / 2;
            end if;
            Count := Count - 1;
        end loop;
        return Result;
     end Shift_Right_Arithmetic;

In Rotate_Left I’ve changed (Result mod 2**(n-1)) to just Result, as I 
believe that the mod turns the top bit to 0, effectively turning the 
Rotate into a Shift.

Similarly for Shift_Right_Arithmetic, otherwise Neg could only be 0.

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

From: Jeff Cousins
Sent: Thursday, March 15, 2018  12:57 PM

Sorry, ignore the

use type Unsigned_n;

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

From: Jeffrey R. Carter
Sent: Thursday, March 15, 2018  3:28 PM

>    function Shift_Left (Value : Unsigned_n; Amount : Natural)
>         return Unsigned_n is
>         Count : Natural := Amount;
>         Result : Unsigned_n := Value;
>         use type Unsigned_n;
>      begin
>         while Count /= 0 loop
>             Result := Result * 2;
>             Count := Count - 1;
>         end loop;
>         return Result;
>      end Shift_Left;
> 
>      function Shift_Right (Value : Unsigned_n; Amount : Natural)
>         return Unsigned_n is
>         Count : Natural := Amount;
>         Result : Unsigned_n := Value;
>         use type Unsigned_n;
>      begin
>         while Count /= 0 loop
>             Result := Result / 2;
>             Count := Count - 1;
>         end loop;
>         return Result;
>      end Shift_Right;

Surely these can just be

if Amount >= n then
   return 0;
end if;
return Value * 2 ** Amount;

and

if Amount >= n then
   return 0;
end if;
return Value / 2 ** Amount;

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

From: Randy Brukardt
Sent: Thursday, March 15, 2018  5:43 PM

If these were to be normative definitions, then you are right. But I was
expecting that they would be just explanatory (in the AARM only), and in
that case, one has to explain the actual wording in this pseudo code. In
particular, "Amount gives the number of bits to shift" needs to be explained
in terms of shifting one bit Amount times -- thus the loop. The definition you
are giving essentially is begging the question by saying that shifting more
than n bits gives zero -- but there is no way to get that conclusion from the
normative wording (that's where the original question came from). It follows 
naturally from the iterative definition, so it's not necessary to assume the
answer.

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