555798 - create global helpers for integer ops that handle overflow

Status: RESOLVED FIXED

(Core :: General, defect)

Description

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

It would be handy if we had some global helpers somewhere for a handful of safe integer ops that checked for overflow.  Something like:

bool safe_ab(const int32& a, const int32& b, int32& out);
bool safe_a_plus_b(const int32& a, const int32& b, int32& out);
bool safe_ab_plus_c(const int32& a, const int32& b, const int32& c, int32& out);

and similar for uint32.

Comment 1

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I think it might make more sense to have a C++ safe-int class that represents "integer OR error" so you can do a bunch of calculations and then check for error at the end. There would be a "get" method that gives you the result as an int, and which aborts if there's an error (so you should check for error before calling it). Similar to the way FP NaNs work.

Comment 2

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Sure, that would work as well, and would be easier to use.  I see CERT has an IntegerLib at http://www.cert.org/secure-coding/integralsecurity.html

Comment 3

[Jeff Muizelaar [:jrmuizel]]

There is also SafeInt: http://safeint.codeplex.com/

Comment 4

[Jeff Muizelaar [:jrmuizel]]

Attachment: A prototype implementation

Here's a prototype implementation. It is basically a c++ wrapper around IntegerLib and is used as follows:

safe_int<int> a(5);
safe_int<int> b(7);

a *= b;

if (a.overflow) {
   handle_errors;
}

Comment 5

[Jeff Muizelaar [:jrmuizel]]

Attachment: A concrete example of safe_int use.

Comment 6

[Robert O'Callahan (:roc) (email my personal email if necessary)]

putting the overflow check behind an inline function would be helpful for future evolution I think

Comment 7

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Jeff: I want!

roc: what do you mean?

Comment 8

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I mean if you access a .overflow field then it always has to be a field, but if you use an inline function you can change it to use a bit mask or a comparison to a magic value or something else

Comment 9

[Jeff Muizelaar [:jrmuizel]]

Gerv,

The license text for IntegerLib is the following which I assume should be fine:

 * Copyright (c) 2005 Carnegie Mellon University.
 * All rights reserved.

 * Permission to use this software and its documentation for any purpose is hereby granted, 
 * provided that the above copyright notice appear and that both that copyright notice and 
 * this permission notice appear in supporting documentation, and that the name of CMU not 
 * be used in advertising or publicity pertaining to distribution of the software without 
 * specific, written prior permission.
 * 
 * CMU DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES 
 * OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR 
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 
 * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, RISING OUT OF OR IN 
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 

It would be nice to keep our modifications under the same license. How should this be done? Should we add Copyright (c) 2010 Mozilla Foundation and copies of the rights and warranty texts with CMU replaced with Mozilla Foundation?

Comment 10

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: an implementation

Here's an implementation based on templates.

it supports all types from 8bit to 64bit.
it supports both signed and unsigned.
it is only ~250 LOC.
it implements pretty much the same API as Jeff's original proposal.

Comment 11

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: test for safeint implementation

This is a pretty thorough test.

Comment 12

[Benoit Jacob [:bjacob] (mostly away)]

some more notes:

 - it doesn't carry significant code from IntegerLib. The only thing it uses from it is the formulas themselves, but those can be found at thousands of places on the Internet. So, credit them informally, but no need to consider copyright and licenses. And it's too generic code to be patent-sensitive.

 - it doesn't allow any implicit conversion to/from plain integers. If we had explicit conversion operators in C++98, we could consider this, but since we don't (they're coming in C++0x), it would be unsafe, so the API requires one to call .value() to get the integer value; and from there it seemed to make sense not to allow any implicit conversion, so the ctor is explicit, and safe_int*int is not allowed.

Comment 13

[Benoit Jacob [:bjacob] (mostly away)]

Huh, I didn't see that this had been reported by Vlad.

Jeff/Vlad, feel free to reassign the reviewing to Vlad :-)

Comment 14

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: implementation, simplified, polished

Still don't know whether to ask Jeff or Vlad for review :-)

This new version has less template testosterone, since the goal is to get this accepted ;-) and NSPR defines anyway all integer types for us (PRInt64...)

It also adds unary operator-(), and simplifies a few more things.

Comment 15

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: test for safeint implementation, updated

This updated test is more exhaustive.

Comment 16

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: test for safeint implementation, v3

This new test version checks that invalidity is correctly preserved, so that we don't have the bad surprise to figure some day that x+y*z-t is flagged as valid even though z isn't...!

Comment 17

[Gervase Markham [:gerv]]

(In reply to comment #9)
> The license text for IntegerLib is the following which I assume should be fine:

Are we still using this? If so, yes, that licence is fine but needs to be added to about:licence. Please file a separate bug for that in mozilla.org / Licensing.

> It would be nice to keep our modifications under the same license. How should
> this be done?

The normal method is just to make modifications and leave the licence as-is :-)

Gerv

Comment 18

[Benoit Jacob [:bjacob] (mostly away)]

(In reply to comment #17)
> (In reply to comment #9)
> > The license text for IntegerLib is the following which I assume should be fine:
> 
> Are we still using this?

As mentioned in comment 12, my version doesn't use code from IntegerLib except for the formulas themselves, the only nontrivial 2 lines of code deriving from IntegerLib code are:

the signed addition check:
line 73:  bool( (((x+y)^x)&((x+y)^y)) >> (sizeof(T)*8-1) )

the signed substraction check:
line 82:  bool( ((x^y)&((x-y)^x)) >> (sizeof(T)*8-1) )

Since these are only generic formulas, and equivalent formulas can be found at other places on the internet, for example:
https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow

I don't really think that these formulas are subject to copyright. However, talking about this really showed a simplification so I'm going to post a new version using simpler formulas, making them really different from IntegerLib code.

For the multiplication checks, we really don't use any significant IntegerLib code. I started from that code and "digested" it, and it completely breaks down to trivial things that I rewrote "in my own idiom".

Comment 19

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: implementation v3

New in this version:
 - the last formulas copied from IntegerLib have been "digested" i.e. only the basic idea remains, and a comment explains what that idea is, it's really very simple, e.g. for addition:

// addition is valid if the sign of x+y is equal to either that of x
// or that of y
   has_sign_bit<T>(binary_complement<T>(((x+y)^x) & ((x+y)^y)))

- we are now storing m_is_valid as a T, not as a bool, and are doing bit-wise operations instead of logic operations, this should reduce the number of integer conversions and give better code.

Comment 20

[Gervase Markham [:gerv]]

OK, then there is no licensing issue :-)

Gerv

Comment 21

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Comment on attachment 454018 [details]
implementation v3

This looks great to me; would like jeff to look it over as well, if he hasn't looked at the final version.

I suggest that this should live in xpcom/ds/SafeInt.h, inside the mozilla namespace.  Should probably name the main class SafeInt instead of safeint too, just for consistency.  Also needs a MPL/GPL/LGPL tri-license header, grab one from an existing file.

Comment 22

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Oh -- doesn't this need to implement division?

Comment 23

[Benoit Jacob [:bjacob] (mostly away)]

No it currently doesn't, but Jeff asked for it too and it's very easy to implement, so let's do it. FYI (looking at IntegerLib) there is only one nontrivial thing to check in division, besides div by zero, it's that min_value / -1 is invalid because |min_value| > max_value.

Comment 24

[Benoit Jacob [:bjacob] (mostly away)]

> No it currently doesn't

I mean, it currently doesn't implement division --- but yes this would be nice to have.

Comment 25

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Ok great -- want to do division and do the boilerplate stuff like header, Makefile.in change etc (follow what TimeStamp.h does), and I'll r+ a new patch?

Comment 26

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: implementation, v4

OK, here's a new version for Jeff to review. Changes since v3:
 - supports division
 - doesn't rely on std::numeric_limits anymore, because that may not be supported on actual PRInt... types (indeed, depending on the platform, they may be defined as compiler built-in types).
 - actually blocks usage on unsupported types. V3 was only checking that a type of same size and same signedness was supported, but it didn't check that it was actually the same type. That was dangerous, because it wouldn't catch usage of safeint<some_broken_pseudo_int_type>.

Comment 27

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: test for safeint implementation, v4

Here is the corresponding updated test.

Comment 28

[Benoit Jacob [:bjacob] (mostly away)]

(In reply to comment #25)
> Ok great -- want to do division and do the boilerplate stuff like header,
> Makefile.in change etc (follow what TimeStamp.h does), and I'll r+ a new patch?

Ah ok, will do that next week.

Comment 29

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: Add SafeInt class

Here's the patch!

Changes since v4:
 - move to xpcom/ds and xpcom/tests
 - adapt to xpcom coding style
 - After discussion with Jeff, we decided to make it allow implicit (plain integer) -> SafeInt conversion, as well as mixing plain ints with SafeInt in arithmetic expressions (the result type is the SafeInt type; different SafeInt types cannot be mixed). Jeff: in the end I found a simple way of allowing all cases including e.g. 2+x.
 - unit tests improvements.

Vlad: in the Makefile.in, TimeStamp was inside of a ifndef MOZ_ENABLE_LIBXUL, so here it was not being built. So I added my test outside of that ifndef.

Comment 30

[Benoit Jacob [:bjacob] (mostly away)]

Ah yes, and also, more changes since v4:
 - refactors our code handling the different integer types, it's saner now, and more extensible.
 - the safeguard against using SafeInt on an unsupported type has been redone, it no longer adds a dummy template parameter to SafeInt and gives much saner compile errors.

Comment 31

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: Add SafeInt class, updated

Minor update:
 - let the test return g_tests_failed > 0
 - add SafeInt.h to the Makefile.in

Comment 32

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: Add SafeInt class, updated again

Here's yet another update, fixing the construction-from-plain-integer problem.

The problem was: should the SafeInt<T> constructor taking a T be explicit or not?

 * if it was explicit, doing SafeInt<PRInt8> x(1); was not allowed, as 1 is not of type PRInt8

 * if it was not explicit, doing SafeInt<PRUint8> x(-1) was allowed and was dangerous, as -1 would be implicitly casted to PRUint8 without generating an error.


The new version fixes this problem by making this constructor non-explicit BUT letting its argument be of a separate type U (separate template param) so that no implicit conversion takes place before the constructor is called, so that the constructor can explicitly do a is_in_range<T>(x) check. This is completely flexible and safe at the same time!

Comment 33

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: Add SafeInt class, updated again again

Oops, the documentation for the constructor was outdated. This update only fixes documentation.

Comment 34

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: Add CheckedInt class

After discussion with Jeff and Ehsan:
 - rename SafeInt to CheckedInt
     (it's more precise and SafeInt is the name used by Microsoft already)
 - methods name changes:
     Value()  ---> value()
     IsValid() ---> valid()

Comment 35

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 454952 [details] [diff] [review]
Add CheckedInt class

I only looked quickly and at this point care more about the external api then anything else. It all seems sane enough :)

Comment 36

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Comment on attachment 454952 [details] [diff] [review]
Add CheckedInt class

yup, looks good!

Comment 37

[Benoit Jacob [:bjacob] (mostly away)]

OK great! This is on the tryserver and I am preparing a patch to make WebGL use it.

Comment 38

[Benoit Jacob [:bjacob] (mostly away)]

http://hg.mozilla.org/mozilla-central/rev/c6b9defb1972

Comment 39

[[e-mail]]

Comment on attachment 454952 [details] [diff] [review]
Add CheckedInt class

>+template<typename T> struct is_unsupported_type { enum { answer = 0 }; };
>+template<> struct is_unsupported_type<unsupported_type> { enum { answer = 1 }; };
You only use this in one spot, and you then go and use ? 0 : 1 to flip the value; why not change this to struct is_supported_type instead?

>+        is_signed = (T(-1) > T(0)) ? 0 : 1
<= also works.

>+        return (x <= integer_traits<T>::max()) &
>+               (x >= integer_traits<T>::min());
Did you mean && ?
[Having looked at the rest of the patch I see you combining "bool" variables with & but I know there's a difference here. Your code compiles as
(x <= integer_traits<T>::max() ? 1 : 0)&(x >= integer_traits<T>::min() ? 1 : 0)
but using && it would compile as
(x <= integer_traits<T>::max() ? (x >= integer_traits<T>::min() ? 1 : 0) : 0)]

>+    /** Constructs a valid checked integer with uninitialized value */
>+    CheckedInt() : mIsValid(1)
Uninitialized values are valid?

>+        T result = -value();
>+        /* give the compiler a good chance to perform RVO */
>+        return CheckedInt(result,
>+                       mIsValid & CheckedInt_internal::is_sub_valid(T(0), value(), result));
It looks strange that you use value() to access mValue but you access mIsValid directly. (And you are consistently inconsistent, too!)
[Also your indentation happens to be off in this line.]

Comment 40

[Benoit Jacob [:bjacob] (mostly away)]

(In reply to comment #39)
> Comment on attachment 454952 [details] [diff] [review]
> Add CheckedInt class
> 
> >+template<typename T> struct is_unsupported_type { enum { answer = 0 }; };
> >+template<> struct is_unsupported_type<unsupported_type> { enum { answer = 1 }; };
> You only use this in one spot, and you then go and use ? 0 : 1 to flip the
> value; why not change this to struct is_supported_type instead?

I thought about this but on the other hand, this makes it more explicit that this is just comparing for equality with unsupported_type.

> 
> >+        is_signed = (T(-1) > T(0)) ? 0 : 1
> <= also works.

Sure...

> 
> >+        return (x <= integer_traits<T>::max()) &
> >+               (x >= integer_traits<T>::min());
> Did you mean && ?

Tough one. I really meant & because I want my boolean variables here to be of type T, not bool, in order to limit the number of type conversions. But >= and <= return bool, so I guess I should rather write:
  T(x <= integer_traits<T>::max()) &
  T(x >= integer_traits<T>::min());
and count on the compiler to be smart enough to optimize <= and >= to stay within type T. Or perhaps I should optimize that manually by doing substractions and checking the sign bit. The point is that no branching is needed here.

> [Having looked at the rest of the patch I see you combining "bool" variables
> with & but I know there's a difference here. Your code compiles as
> (x <= integer_traits<T>::max() ? 1 : 0)&(x >= integer_traits<T>::min() ? 1 : 0)
> but using && it would compile as
> (x <= integer_traits<T>::max() ? (x >= integer_traits<T>::min() ? 1 : 0) : 0)]

I know, and I really don't want that, I would like to limit the number of branchings, by doing as much as possible by bit operations on type T.

> 
> >+    /** Constructs a valid checked integer with uninitialized value */
> >+    CheckedInt() : mIsValid(1)
> Uninitialized values are valid?

We sure can initialize by zero instead, it doesn't cost much compared to the rest. I would rather not take the route of considering uninitialized as invalid as that would dilute the meaning of invalid.

> 
> >+        T result = -value();
> >+        /* give the compiler a good chance to perform RVO */
> >+        return CheckedInt(result,
> >+                       mIsValid & CheckedInt_internal::is_sub_valid(T(0), value(), result));
> It looks strange that you use value() to access mValue but you access mIsValid
> directly. (And you are consistently inconsistent, too!)
> [Also your indentation happens to be off in this line.]

Yes, good point, moving to using mValue.

(patch coming).

Comment 41

[Benoit Jacob [:bjacob] (mostly away)]

It turns out that GCC 4.4 / x86-64 is much more clever than us. First, it realizes that since the conditions here have no side effect, & and && are logically equivalent. Second, regardless of & vs && and regardless of casting to integer type or not, it just generates this super-optimized assembly (here case where x is int and T is short:)

	addl	$32768, %edi
	xorl	%eax, %eax
	cmpl	$65535, %edi
	setbe	%al
	ret

i.e. it realizes that by shifting the problem (addl) it can turn this into an unsigned int range check, i.e. only one comparison needed; and it does by itself optimize this comparison by just checking the sign bit.

Comment 42

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: remove futile optimizations, use mValue member, and init by zero

This patch:
 * removes the "optimizations" that were seen to be futile in previous comment
 * makes default ctor init by zero
 * makes the code use mValue member instead of value()

Notice that another patch is coming in bug 601535.

Comment 43

[[e-mail]]

(In reply to comment #40)
> (In reply to comment #39)
> > why not change this to struct is_supported_type instead?
> I thought about this but on the other hand, this makes it more explicit that
> this is just comparing for equality with unsupported_type.
"twice_bigger_type_is_supported" confused me here.

> > >+        return (x <= integer_traits<T>::max()) &
> > >+               (x >= integer_traits<T>::min());
> > Did you mean && ?
> The point is that no branching is needed here.
Sorry, I forgot that we now have instructions such as setbe.

> > >+    /** Constructs a valid checked integer with uninitialized value */
> > >+    CheckedInt() : mIsValid(1)
> > Uninitialized values are valid?
> I would rather not take the route of considering uninitialized as invalid
> as that would dilute the meaning of invalid.
I can't see how you can claim that uninitialized is valid.

Comment 44

[[e-mail]]

Comment on attachment 481467 [details] [diff] [review]
remove futile optimizations, use mValue member, and init by zero

>diff --git a/gfx/angle/src/compiler/util.h b/gfx/angle/src/compiler/util.h
Some other patch?

>         T result = -value();
Ironically you didn't change the instance that I quoted ;-) In fact you missed at least one other value(), maybe you searched for .value() ?

>-                         lhs.mIsValid & rhs.mIsValid & is_op_valid);
>+                         lhs.mIsValid && rhs.mIsValid && is_op_valid);
As I mentioned, I know why you wanted to use & here, so I went back and edited my original comment, and now I don't have any objection to &s in this code.

Comment 45

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: v2: remove futile optimizations, use mValue member, and init by zero

Comment 46

[Benoit Jacob [:bjacob] (mostly away)]

(In reply to comment #44)
> Comment on attachment 481467 [details] [diff] [review]
> remove futile optimizations, use mValue member, and init by zero
> 
> >diff --git a/gfx/angle/src/compiler/util.h b/gfx/angle/src/compiler/util.h
> Some other patch?

Yes, sorry!

> 
> >         T result = -value();
> Ironically you didn't change the instance that I quoted ;-) In fact you missed
> at least one other value(), maybe you searched for .value() ?

That's exactly what I did... should be fixed in the new patch.

> 
> >-                         lhs.mIsValid & rhs.mIsValid & is_op_valid);
> >+                         lhs.mIsValid && rhs.mIsValid && is_op_valid);
> As I mentioned, I know why you wanted to use & here, so I went back and edited
> my original comment, and now I don't have any objection to &s in this code.

But actually, _I_ am now convinced that this change (& ---> &&) is useful: it makes the code more explicit (you wouldn't have had to ask a question if it had been like that) while not making any difference in the resulting executable.

Comment 47

[[e-mail]]

Comment on attachment 481567 [details] [diff] [review]
v2: remove futile optimizations, use mValue member, and init by zero

>-        return (x <= integer_traits<T>::max_value()) &
>+        return (x <= integer_traits<T>::max_value()) &&
>                (x >= integer_traits<T>::min_value());
[All the (somewhat old) compilers I tried do better with & than &&...]

> {                                                                     \
>-    T x = lhs.value();                                                \
>-    T y = rhs.value();                                                \
>+    T x = lhs.mValue;                                                \
>+    T y = rhs.mValue;                                                \
>     T result = x OP y;                                                \
>     T is_op_valid                                                     \
>         = CheckedInt_internal::is_##NAME##_valid(x, y, result);       \
>     /* give the compiler a good chance to perform RVO */              \
>     return CheckedInt<T>(result,                                      \
>-                         lhs.mIsValid & rhs.mIsValid & is_op_valid);  \
>+                         lhs.mIsValid && rhs.mIsValid && is_op_valid);  \
[Oops, the \s don't line up any more...]

Comment 48

[Benoit Jacob [:bjacob] (mostly away)]

(In reply to comment #47)
> Comment on attachment 481567 [details] [diff] [review]
> v2: remove futile optimizations, use mValue member, and init by zero
> 
> >-        return (x <= integer_traits<T>::max_value()) &
> >+        return (x <= integer_traits<T>::max_value()) &&
> >                (x >= integer_traits<T>::min_value());
> [All the (somewhat old) compilers I tried do better with & than &&...]

Ah! Thanks for the information. & it is, then.

Comment 49

[Joe Drew (not getting mail)]

Comment on attachment 481567 [details] [diff] [review]
v2: remove futile optimizations, use mValue member, and init by zero

a=me as long as it passes try

Comment 50

[Benoit Jacob [:bjacob] (mostly away)]

http://hg.mozilla.org/mozilla-central/rev/80fd91b34453

Comment 51

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: fix CheckedInt compilation for standard types

This fixes compilation of CheckedInt<T> where T is a standard integer type like |long| that doesn't match any of the PRInt... types.

Not asking for review for now as I don't want to disturb people in these times of fixing hard-blockers.

Comment 52

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: fix CheckedInt compilation for standard types

updated: keep generating good compile errors when using unsupported type.

Comment 53

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

please create a new bug for the above fixes -- this one's already been fixed :)  can mark the new one as blocking this one.