2024-04-16 22:28 AEST
  

View Issue Details [ Jump to Notes ] [ Issue History ] [ Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0000141mercuryBugpublic2010-04-01 15:372010-04-01 18:32
Reportermgiuca 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityN/A
StatusnewResolutionopen 
Product Version 
Target VersionFixed in Version 
Summary0000141: integer has no method for converting to int with wraparound
DescriptionThe integer.int function converts an integer to an int but aborts if the integer is out of range.

It is occasionally useful to convert an integer to an int with out-of-range numbers being wrapped (truncated) just like conversion from int to short in C, for example.

I have attached a patch which adds a function integer.int_with_overflow which does this.
Additional InformationThe patch sort-of relies upon two's complement (it would probably work for one's complement or sign-bit form as well, but does make some bit-level assumptions). I have included an XXX comment to this effect. I assume this is OK since there are other such comments in the same file.
TagsNo tags attached.
Attached Files
  • patch file icon integer.patch (1,243 bytes) 2010-04-01 15:37 - 
    Index: library/integer.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/integer.m,v
retrieving revision 1.29
diff -u -r1.29 integer.m
--- library/integer.m	23 Nov 2007 07:35:56 -0000	1.29
+++ library/integer.m	1 Apr 2010 04:32:42 -0000
@@ -97,6 +97,10 @@
 :- func integer.float(integer) = float.
 :- func integer.int(integer) = int.
 
+    % As above but wraps on overflow rather than aborting.
+    %
+:- func integer.int_with_overflow(integer) = int.
+
 :- func integer.zero = integer.
 
 :- func integer.one = integer.
@@ -1001,6 +1005,17 @@
         error("integer.int: domain error (conversion would overflow)")
     ).
 
+% Since most machines are 2's complement, we take the AND with max_int*2 + 1,
+% which is an int with all bits set to 1.
+% XXX: What about machines that aren't 2's complement?
+% Note: Can't just call int_list, as int overflow in Mercury is undefined.
+
+integer.int_with_overflow(Integer) = Int :-
+    AllBits = (integer(int.max_int) << 1) \/ integer.one,
+    Wrapped = Integer /\ AllBits,
+    Wrapped = i(_Sign, Digits),
+    Int = int_list(Digits, 0).
+
 :- func int_list(list(int), int) = int.
 
 int_list([], Accum) = Accum.
    patch file icon integer.patch (1,243 bytes) 2010-04-01 15:37 +
  • patch file icon integer-2.patch (1,249 bytes) 2010-04-01 18:09 - 
    Index: library/integer.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/integer.m,v
retrieving revision 1.29
diff -u -r1.29 integer.m
--- library/integer.m	23 Nov 2007 07:35:56 -0000	1.29
+++ library/integer.m	1 Apr 2010 07:07:49 -0000
@@ -97,6 +97,10 @@
 :- func integer.float(integer) = float.
 :- func integer.int(integer) = int.
 
+    % As above but wraps on overflow rather than aborting.
+    %
+:- func integer.int_with_overflow(integer) = int.
+
 :- func integer.zero = integer.
 
 :- func integer.one = integer.
@@ -1001,6 +1005,17 @@
         error("integer.int: domain error (conversion would overflow)")
     ).
 
+% XXX: Assuming that the range is that of 2's complement.
+% X' = ((X + max_int+1) `mod` (max_int+1) * 2) - (max_int+1)
+% Note: Can't just call int_list, as int overflow in Mercury is undefined.
+
+integer.int_with_overflow(Integer) = Int :-
+    MaxPlusOne = integer(int.max_int) + integer.one,
+    Wrapped = ((Integer + MaxPlusOne) `mod` (MaxPlusOne * integer(2)))
+                - MaxPlusOne,
+    Wrapped = i(_Sign, Digits),
+    Int = int_list(Digits, 0).
+
 :- func int_list(list(int), int) = int.
 
 int_list([], Accum) = Accum.
    patch file icon integer-2.patch (1,249 bytes) 2010-04-01 18:09 +

-Relationships
+Relationships

-Notes

~0000258

mgiuca (reporter)

2010-04-01 16:05

 Irk... that patch is wrong. The "Wrapped" value is not necessarily in int range (I thought it worked because conversion to int truncated anyway, but you can't assume that since it's specified as undefined.)

Positive integers in range 2^31 to 2^32-1 need to become negative, and vice versa for negative integers in range -2^31-1 to -2^32. This is tricky to do with integer bit operations since they specifically *don't* wrap values. I'm thinking it'll be easier to use mod/rem but I'll have to think hard about it. Does anyone have a better mathematical formula for wraparound conversion?

Also, is there a test suite I need to write test cases for?

~0000259

mgiuca (reporter)

2010-04-01 16:14

 A valid formula appears to be (at least for 2's complement):

((X + int_max + 1) `mod` (int_max+1) * 2) - int_max - 1

Is this overly complicated?

~0000260

mgiuca (reporter)

2010-04-01 18:10

 Added a new patch (integer-2.patch) which uses the above formula.

I'm aware that there is a formal patch review process, and this isn't it. I'm just seeing if anyone is interested first.

~0000261

juliensf (administrator)

2010-04-01 18:32

 Hi Matt,

Yes, we're interested - could you please submit your patch to the mercury-reviews list.
(Or ask one of the developers to do so on your behalf)

The review process used in the Mercury project is documented here:
http://www.mercury.csse.unimelb.edu.au/information/doc-latest/reviews.html

Cheers,
Julien.
+Notes

-Issue History
Date Modified Username Field Change
2010-04-01 15:37 mgiuca New Issue
2010-04-01 15:37 mgiuca File Added: integer.patch
2010-04-01 16:05 mgiuca Note Added: 0000258
2010-04-01 16:14 mgiuca Note Added: 0000259
2010-04-01 18:09 mgiuca File Added: integer-2.patch
2010-04-01 18:10 mgiuca Note Added: 0000260
2010-04-01 18:32 juliensf Note Added: 0000261
+Issue History