Bit shifts

[Jose E. Marchesi]

> Hello people.
>
>
> As James already noticed, the existing implementation of the standard
> bit shifting operators SHR and SHL just uses the same C semantics, and
> also it is broken.
>
> The Revised Report defines the following semantics for the operators.
> Note that below I use the notation c[N] to mean the Nth bit in c, but we
> know bits values cannot be sliced like that.
>
>     op SHL = (bits a, int b) bits:
>        if ABS b <= bits_width
>        then bits c := a;
>             to ABS b

Note that there are no loop iterations if b = 0 (the implicit counter in
the loop gets initialized to 1).  In that case the value is returned
intact as expected.

The correspondin implementation is:

  /* Rotate the bits in BITS according to the value of SHIFT:
  
     - If ABS(SHIFT) => bits_width, the operation is a nop.
     - If SHIFT is positive, BITS gets shifted SHIFT bits to the right.
     - If SHIFT is negative, BITS gets shifted ABS(SHIFT) bits to the left.
  */
  
  tree
  a68_bits_shift (tree shift, tree bits)
  {
    shift = save_expr (shift);
    bits = save_expr (bits);
  
    tree shift_type = TREE_TYPE (shift);
    tree bits_type = TREE_TYPE (bits);
    tree abs_shift = save_expr (fold_build1 (ABS_EXPR, TREE_TYPE (shift), shift));
  
    tree shifted_right = fold_build2 (RSHIFT_EXPR, bits_type, bits, abs_shift);
    tree shifted_left = fold_build2 (LSHIFT_EXPR, bits_type, bits, abs_shift);
  
    tree shifted_bits = fold_build3 (COND_EXPR, TREE_TYPE (bits),
  				   fold_build2 (GE_EXPR, shift_type,
  						shift, build_zero_cst (shift_type)),
  				   shifted_right, shifted_left);
    return fold_build3 (COND_EXPR,
  		      TREE_TYPE (bits),
  		      fold_build2 (LT_EXPR, TREE_TYPE (abs_shift),
  				   abs_shift, a68_bits_width (bits_type)),
  		      shifted_bits, bits);
  }

The resulting GENERIC tree has no undefined behavior whatsoever.  It
also runs Jame's testscase properly.

>             do if b > 0
>                then for i from 2 to bits_width
>                     do c[i-1] := c[i] od;
>                     c[bits_width] := false
>                else
>                     for i from bits_width by -1 to 2
>                     do c[i] := c[i-1] od;
>                     c[1] := false
>                fi
>             od;
>             c
>        fi;
>
>     op SHR = (bits x, int n) bits: x SHL -n;
>
>> From the above, we see that:
>
> 1. The shift count is signed.  It's sign determines the direction of
>    shifting, meaning that SHR by a negative count is a left shift, and a
>    SHL by a negative count is a right shift.
>
> 2. Attempting to shift by more than the width of the bits value, in
>    either direction, is a no-op.  No run-time error nor undefined.
>
> 3. We don't have signed shifting and its associated problems in Algol
>    68, because `bits' values do not have signedness.  The resulting bits
>    (conceptually a multiple of booleans) will be interpreted when/if the
>    operator ABS is applied to it, resulting in a signed integral value
>    which may be negative, but none of that is of relevance in
>    unconverted `bits' values.
>
> I am fixing the implementation of these operators in ga68 in order to
> follow these semantics, document it in the manual and adding a few
> tests.
>
> Salud!