views:

356

answers:

6

I'm working on a verification-tool for some VHDL-Code in MATLAB/Octave. Therefore I need data types which generate "real" overflows:

intmax('int32') + 1
ans = -2147483648

Later on, it would be helpful if I can define the bit width of a variable, but that is not so important right now.

When I build a C-like example, where a variable gets increased until it's smaller than zero, it spins forever and ever:

test = int32(2^30);
while (test > 0)
    test = test + int32(1);
end

Another approach I tried was a custom "overflow"-routine which was called every time after a number is changed. This approach was painfully slow, not practicable and not working in all cases at all. Any suggestions?

A: 

I ran the following snippet of code

test = int32(2^31-12);
for i = 1:24
    test = test + int32(1)
end

with unexpected results. It seems that, for Matlab, intmax('int32')+1==intmax('int32'). I'm running 2010a on a 64-bit Mac OS X.

Not sure that this as an answer, more confirmation that Matlab behaves counterintuitively. However, the documentation for the intmax() function states:

Any value larger than the value returned by intmax saturates to the intmax value when cast to a 32-bit integer.

So I guess Matlab is behaving as documented.

High Performance Mark
A: 

Hm, yes...

Actually, I was able to solve the problem with my custom "overflow"-Subroutine... Now it runs painfully slow, but without unexpected behaviour! My mistake was a missing round(), since Matlab/Octave will introduce small errors.

But if someone knows a faster solution, I would be glad to try it!

function ret = overflow_sg(arg,bw)

    % remove possible rounding errors, and prepare returnvalue (if number is inside boundaries, nothing will happen)
    ret = round(arg);

    argsize = size(ret);

    for i = 1:argsize(1)
        for j = 1:argsize(2)
            ret(i,j) = flow_sg(ret(i,j),bw);
        end
    end

end%function

%---

function ret = flow_sg(arg,bw)
    ret = arg;
    while (ret < (-2^(bw-1)))
        ret = ret + 2^bw;
    end

    % Check for overflows:
    while (ret > (2^(bw-1)-1))
        ret = ret - 2^bw;
    end
end%function
marvin2k
A: 

Take a look at the intwarning function.

AVB
A: 

If 64 bits is enough to not overflow, and you need a lot of these, perhaps do this:

function ret = overflow_sg(arg,bw)
  mask = int64(0);
  for i=1:round(bw)
    mask = bitset(mask,i);
  end
  topbit = bitshift(int64(1),round(bw-1));
  subfrom = double(bitshift(topbit,1))


  ret = bitand( int64(arg) , mask );
  i = (ret >= topbit);
  ret(i) = int64(double(ret(i))-subfrom);
  if (bw<=32)
    ret = int32(ret);
  end
end

Almost everything is done as a matrix calculation, and a lot is done with bits, and everything is done in one step (no while loops), so it should be pretty fast. If you're going to populate it with rand, subtract 0.5 since it assumes it should round to integer values (rather than truncate).

Rex Kerr
+4  A: 

In MATLAB, one option you have is to overload the methods that handle arithmetic operations for integer data types, creating your own custom overflow behavior that will result in a "wrap-around" of the integer value. As stated in the documentation:

You can define or overload your own methods for int* (as you can for any object) by placing the appropriately named method in an @int* folder within a folder on your path. Type help datatypes for the names of the methods you can overload.

The remarks section in the arithmetic operator documentation lists the equivalent methods for the arithmetic operators. The binary addition operation A+B is actually handled by the function plus(A,B). Therefore, you can create a folder called @int32 (placed in another folder on your MATLAB path) and put a function plus.m in there that will be used instead of the built-in method for int32 data types.

Here's an example of how you could design your overloaded plus function in order to create the overflow/underflow behavior you want:

function C = plus(A,B)
%# NOTE: This code sample is designed to work for scalar values of
%#       the inputs. If one or more of the inputs is non-scalar,
%#       the code below will need to be vectorized to accommodate,
%#       and error checking of the input sizes will be needed.

  if (A > 0) && (B > (intmax-A))  %# An overflow condition

    C = builtin('plus',intmin,...
                B-(intmax-A)-1);  %# Wraps around to negative

  elseif (A < 0) && (B < (intmin-A))  %# An underflow condition

    C = builtin('plus',intmax,...
                B-(intmin-A-1));  %# Wraps around to positive

  else

    C = builtin('plus',A,B);  %# No problems; call the built-in plus.m

  end

end

Notice that I call the built-in plus method (using the BUILTIN function) to perform addition of int32 values that I know will not suffer overflow/underflow problems. If I were to instead perform the integer addition using the operation A+B it would result in a recursive call to my overloaded plus method, which could lead to additional computational overhead or (in the worst-case scenario where the last line was C = A+B;) infinite recursion.

Here's a test, showing the wrap-around overflow behavior in action:

>> A = int32(2147483642);  %# A value close to INTMAX
>> for i = 1:10, A = A+1; disp(A); end
  2147483643

  2147483644

  2147483645

  2147483646

  2147483647   %# INTMAX

 -2147483648   %# INTMIN

 -2147483647

 -2147483646

 -2147483645

 -2147483644
gnovice
+1 for coming up with operator overloading!
Jonas
+1 Effective but scary. I think this should come with a caveat that replacing operators on standard types could interact poorly with other libraries or Matlab functions that are expecting Matlab's normal "+" behavior on them. (Even if MathWorks does recommend it in the doco.) Powerful for quick one-offs, problematic for large codebases.
Andrew Janke
@Andrew: You make a good point. I envision this kind of solution only being used for the specific tool the OP is creating, but it could be easy to forget to revert back to the old `int32` method(s) once the tool is finished running. To only use this for a specific piece of code, I would have a command at the beginning of that code that added the parent folder of the `@int32` folder to the path, then removed it from the path when it finished running.
gnovice
I wonder if you could use the new MCOS namespaces to protect it. Create a +cstylemath namespace and stick your @int32 overrides and marvin2k's code that wants to call them in there. Easy to do, plus that'd be lexically scoped instead of dynamically scoped: other functions would still see the normal @int32 behavior, even if they were called from within functions in +cstylemath. And it doesn't need a try/catch to clean up the path modification.
Andrew Janke
+1  A: 

If you want to get C style numeric operations, you can use a MEX function to call the C operators directly, and by definition they'll work like C data types.

This method is a lot more work than gnovice's overrides, but it should integrate better into a large codebase and is safer than altering the definition for built-in types, so I think it should be mentioned for completeness.

Here's a MEX file which performs the C "+" operation on a Matlab array. Make one of these for each operator you want C-style behavior on.

/* c_plus.c - MEX function: C-style (not Matlab-style) "+" operation */

#include "mex.h"
#include "matrix.h"
#include <stdio.h>

void mexFunction(
                 int nlhs,       mxArray *plhs[],
                 int nrhs, const mxArray *prhs[]
                 )
{
    mxArray     *out;
    /* In production code, input/output type and bounds checks would go here. */
    const mxArray     *a = prhs[0];
    const mxArray     *b = prhs[1];
    int         i, n;
    int *a_int32, *b_int32, *out_int32;
    short *a_int16, *b_int16, *out_int16;

    mxClassID datatype = mxGetClassID(a);
    int n_a = mxGetNumberOfElements(a);
    int n_b = mxGetNumberOfElements(b);
    int         a_is_scalar = n_a == 1;
    int         b_is_scalar = n_b == 1;
    n = n_a >= n_b ? n_a : n_b;
    out = mxCreateNumericArray(mxGetNumberOfDimensions(a), mxGetDimensions(a),
            datatype, mxIsComplex(a));

    switch (datatype) {
        case mxINT32_CLASS:
            a_int32 = (int*) mxGetData(a);
            b_int32 = (int*) mxGetData(b);
            out_int32 = (int*) mxGetData(out);
            for (i=0; i<n; i++) {
                if (a_is_scalar) {
                    out_int32[i] = a_int32[i] + b_int32[i];
                } else if (b_is_scalar) {
                    out_int32[i] = a_int32[i] + b_int32[0];
                } else {
                    out_int32[i] = a_int32[i] + b_int32[i];
                }
            }
            break;
        case mxINT16_CLASS:
            a_int16 = (short*) mxGetData(a);
            b_int16 = (short*) mxGetData(b);
            out_int16 = (short*) mxGetData(out);
            for (i=0; i<n; i++) {
                if (a_is_scalar) {
                    out_int16[i] = a_int16[0] + b_int16[i];
                } else if (b_is_scalar) {
                    out_int16[i] = a_int16[i] + b_int16[0];
                } else {
                    out_int16[i] = a_int16[i] + b_int16[i];
                }
            }
            break;
        /* Yes, you'd have to add a separate case for every numeric mxClassID... */
        /* In C++ you could do it with a template. */
        default:
            mexErrMsgTxt("Unsupported array type");
            break;
    }

    plhs[0] = out;
}

Then you have to figure out how to invoke it from your Matlab code. If you're writing all the code, you could just call "c_plus(a, b)" instead of "a + b" everywhere. Alternately, you could create your own numeric wrapper class, e.g. @cnumeric, that holds a Matlab numeric array in its field and defines plus() and other operations that invoke the approprate C style MEX function.

classdef cnumeric
    properties
        x % the underlying Matlab numeric array
    end
    methods
        function obj = cnumeric(x)
            obj.x = x;
        end

        function out = plus(a,b)
            [a,b] = promote(a, b); % for convenience, and to mimic Matlab implicit promotion
            if ~isequal(class(a.x), class(b.x))
                error('inputs must have same wrapped type');
            end
            out_x = c_plus(a.x, b.x);
            out = cnumeric(out_x);
        end

        % You'd have to define the math operations that you want normal
        % Matlab behavior on, too
        function out = minus(a,b)
            [a,b] = promote(a, b);
            out = cnumeric(a.x - b.x);
        end

        function display(obj)
            fprintf('%s = \ncnumeric: %s\n', inputname(1), num2str(obj.x));
        end

        function [a,b] = promote(a,b)
        %PROMOTE Implicit promotion of numeric to cnumeric and doubles to int
            if isnumeric(a); a = cnumeric(a); end
            if isnumeric(b); b = cnumeric(b); end
            if isinteger(a.x) && isa(b.x, 'double')
                b.x = cast(b.x, class(a.x));
            end
            if isinteger(b.x) && isa(a.x, 'double')
                a.x = cast(a.x, class(b.x));
            end
        end
    end

end

Then wrap your numbers in the @cnumeric where you want C-style int behavior and do math with them.

>> cnumeric(int32(intmax))
ans = 
cnumeric: 2147483647
>> cnumeric(int32(intmax)) - 1
ans = 
cnumeric: 2147483646
>> cnumeric(int32(intmax)) + 1
ans = 
cnumeric: -2147483648
>> cnumeric(int16(intmax('int16')))
ans = 
cnumeric: 32767
>> cnumeric(int16(intmax('int16'))) + 1
ans = 
cnumeric: -32768

There's your C-style overflow behavior, isolated from breaking the primitive @int32 type. Plus, you can pass a @cnumeric object in to other functions that are expecting regular numerics and it'll "work" as long as they treat their inputs polymorphically.

Performance caveat: because this is an object, + will have the slower speed of a method dispatch instead of a builtin. If you have few calls on large arrays, this'll be fast, because the actual numeric operations are in C. Lots of calls on small arrays, could slow things down, because you're paying the per method call overhead a lot.

Andrew Janke
+1: Quite a bit more work, but a cool idea. I suppose even another solution would be to take the overloaded methods from my solution and just make a new user-defined object using those methods (like your solution, but without the MEX files).
gnovice

related questions