[M3devel] Enumeration or subrange value out of range

[Rodney M. Bates]

The packed subrange type with an all-positive range doesn't do what
I suspect you think it does.  The subrange only affects what values
can be legally stored in a variable, and the packed size only affects
memory allocation when it is used as an element of an array or field
of a record or object.  None of this changes the semantics of the
arithmetic operators +, -, Word.Xor, etc. when applied to values
of this type.

In Modula-3, all intermediate arithmetic is done in the native word
size, in this case 64 bits.  And the builtin operators +, etc. apply signed
interpretation to the bit values.  Only when you assign to a variable (or do
any of a number of equivalent things, e.g., pass to a VALUE parameter)
is a range check done.  There is no trimming of intermediate results
to 32 bits, despite the application of your arithmetic operators to variables
of your UInt32 subrange type.

So, without vetting the algorithm or knowing sample input, I can pretty
well guess that things like LeftShift are shifting bits into the upper
half of the word.  Then when you try to assign to a UInt32 variable,
you have a value outside its range.

One way to do this would be to always And to 16_FFFFFFFF in your expression,
before you store the result.  This would ensure values within range, and,
I suspect, the values you really want.

Note that Modula-3 handles unsigned rather differently than many languages.
You can use a subrange type, as you did, but it has to be a true subrange
of INTEGER, so you can't get the normally-negative part of the range of
INTEGER to be interpreted as positive, above the normal positive half of
INTEGER.

Should you really need full native-word-sized unsigned arithmetic, you
use the type Word.T.  But this is actually the same type as INTEGER, so
naming it Word.T is just a programmer readability courtesy.  The builtin
operators +, -, etc. apply signed interpretation to the bits in a word.
The operators from Word (Word.Plus, etc.) operate on values of the same
type (INTEGER=Word.T), but apply unsigned interpretation to the entire
word range.

It would no doubt be good to replace your + operators with Word.Plus,
to emphasize unsigned arithmetic.  For + and -, in the absence of
overflow checks, the signed and unsigned arithmetic are the same,
of course, but it would be another readability courtesy.  And if we
ever get a compiler with overflow checking, it would still work right.

I would suggest using the signed subrange [-16_7FFFFFFF-1 .. 16_7FFFFFFF], while
still And-ing results to 16_FFFFFFFF.  I think this would make your code portable
between 32-bit and 64-bit machines.  All your arithmetic would just be
applying unsigned interpretation to the bits, and the signed subrange would
work like INTEGER on a 32-bit machine and as you have coded on 64 bits.
All bit combinations (with no bits set in the upper half of a 64-bit word)
would be in range.  Of course, this all interacts with your client code
and they type they use.

Or maybe you could just dispense with trying to use the type system to
enforce your ranges and use Word.T.  If you always And your results to
16_FFFFFFFF, it will ensure they are within the desired range.  There
are some client interface design issues here, which you test program
is not involved enough to expose.

On another subject, it looks like your algorithms will either crash or
won't work meaningfully unless v has exactly two elements and k has exactly
4.  So using fixed array types instead of open might be a sensible way to
use the type system to help here.

P.S.  BITS 32 FOR ... does nothing to autonomous variables v0, etc., The
compiler is free to represent them in any way that can hold the range, and it
may well give them 64 bits on a 64-bit machine.  In any case, even
if it gave them only 32, it would, by the semantics of the language,
have to expand them to 64 before doing any arithmetic on them.


HTH.  Rodney Bates


Ken Durocher wrote:
> I am trying to write the Tiny Encryption Algorithm (TEA) in Modula-3, 
> but I ran into a problem.  The code compiles fine, but I get a runtime 
> error. I'm running 5.8.6 RELEASE on AMD64.
> 
> P.S. Is there already an unsigned int32 type?  Is there a better way to 
> create one?
> 
> Here's the code:
> 
> INTERFACE Tea;
> 
> TYPE UInt32 = BITS 32 FOR [0 .. 16_FFFFFFFF];
> 
> PROCEDURE Encrypt(VAR v: ARRAY OF UInt32; VAR k: ARRAY OF UInt32);
> PROCEDURE Decrypt(VAR v: ARRAY OF UInt32; VAR k: ARRAY OF UInt32);
> 
> END Tea.
> 
> ***
> 
> MODULE Tea;
> 
> FROM Word IMPORT Xor, LeftShift, RightShift;
> 
> VAR
>   delta := 16_9e3779b9;
> 
> PROCEDURE Encrypt(VAR v: ARRAY OF UInt32; VAR k: ARRAY OF UInt32) =
>   VAR
>     v0 := v[0]; v1 := v[1];
>     k0 := k[0]; k1 := k[1]; 
>     k2 := k[2]; k3 := k[3];   
>     sum: UInt32 := 0;
> 
>   BEGIN
>     FOR i := 0 TO 31 DO
>       sum := sum + delta;
>       v0 := v0 + (Xor(LeftShift(v1, 4) + k0, Xor((sum + v1), 
> RightShift(v1, 5) + k1)));
>       v1 := v1 + (Xor(LeftShift(v0, 4) + k2, Xor((sum + v0), 
> RightShift(v0, 5) + k3)));
>     END;
>     v[0] := v0; v[1] := v1;
>   END Encrypt;
> 
> PROCEDURE Decrypt(VAR v: ARRAY OF UInt32; VAR k: ARRAY OF UInt32) =
>   VAR
>     v0 := v[0]; v1 := v[1];
>     k0 := k[0]; k1 := k[1];
>     k2 := k[2]; k3 := k[3];
>     sum: UInt32 := 16_c6ef3720;
>   BEGIN
>     FOR i := 0 TO 32 DO
>       v1 := v1 - Xor(LeftShift(v0, 4) + k2, Xor((sum + v0), 
> RightShift(v0, 5) + k3));
>       v0 := v0 - Xor(LeftShift(v1, 4) + k0, Xor((sum + v1), 
> RightShift(v1, 5) + k1));
>       sum := sum - delta;
>     END;
>     v[0] := v0; v[1] := v0;
>   END Decrypt;
> 
> BEGIN
> END Tea.
> 
> ***
> 
> MODULE Main;
> 
> IMPORT IO, Fmt, Tea;
> 
> VAR
>   v := ARRAY [0..1] OF Tea.UInt32 {16_48690000, 0};
>   k := ARRAY [0..3] OF Tea.UInt32 {16_74657374, 0, 0, 0};
> 
> BEGIN
>   Tea.Encrypt(v,k);
>   IO.Put(Fmt.Unsigned(v[0]));
>   IO.Put(" - ");
>   IO.Put(Fmt.Unsigned(v[1]));
>   IO.Put("\n");
> END Main.
> 
> And the error:
> 
> ***
> *** runtime error:
> ***    An enumeration or subrange value was out of range.
> ***    file "../Tea.m3", line 18
> ***
> 
> Aborted
> 
>