[M3devel] Enumeration or subrange value out of range

[Tony Hosking]

Rodney,

Thank-you for your (as-usual) incredibly lucid explanation.

Jay,

On Nov 29, 2010, at 6:01 PM, Jay K wrote:

> 
> ps: anding with 16_FFFFFFFF should optimize to nothing on a 32 bit machine.
> And *hopefully* a 64bit targeting compiler would "notice" and make some
> optimizations, such as only doing 32bit load/stores, but I could easily
> imagine it not doing that.
> 
> 
> Imho, it really would be nice to have the following types, with operator+, etc.:
> 
> 
> unsigned/signed 8/16/32/64bit integer with silent overflow/exception upon overflow
> 2 x 4 x 2 => 16 types

This would be a nightmare.  (i.e., over many of our dead bodies...)

> C and C++ programmers the world over have 8 of these types (unspecified
> what signed overflow does, but overwhelmingly it is silent).

Let them rot in C hell.

> The underlying backend exposes those 8 as well.

But only for the purpose of accessing stored values (as Rodney explained).  All operations are performed at INTEGER/Word.T granularity.

> 
> 
> - Jay
> 
> 
> ----------------------------------------
>> Date: Mon, 29 Nov 2010 16:36:30 -0600
>> From: rodney_bates at lcwb.coop
>> To: kcdurocher at gmail.com
>> CC: m3devel at elegosoft.com
>> Subject: Re: [M3devel] Enumeration or subrange value out of range
>> 
>> 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
>>> 
>>>