Re: [boost] Is there interest in portable integer overflow detection, with policy based handling?

Subject: Re: [boost] Is there interest in portable integer overflow detection, with policy based handling?
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2012-02-24 05:49:49

Le 24/02/12 05:33, Ben Robinson a écrit :
> On Thu, Feb 23, 2012 at 1:35 AM, Vicente J. Botet Escriba<
> vicente.botet_at_[hidden]>  wrote:
>
>>   Hi,
>>
>> I've found this use of METAASSERT that trouble my understanding
>>
>> // Prevent implicit conversion from one verified type to another
>> // on assignment via operator T() on the right-hand-side.
>> template<class R>
>> verified_int(R const prevented) {
>> BOOST_METAASSERT_MSG(sizeof(R) == 0, CANNOT_CONSTRUCT_FROM_A_**
>> DIFFERENTLY_TYPED_VERIFIED_**INT, (R));
>> }
>>
>>
>> This doesn't prevent the implicit conversion, but makes it fail. This mean
>> that if I have a function f overloaded with verified_int<X>  and type
>> ConvertibleFromR
>>
>> void f(verified_int<X>);
>> void f(ConvertibleFromR);
>>
>> the call
>>
>> R r;
>> f(r);
>>
>> will result on ambiguous resolution.
>>
>> I will explain the rational behind the implementation choices of the
> binary math operators for VerifiedInt.  When performing multiple operations
> (let's take addition for example), the order of operations is important.
> Compare:
>
> verified_uint8_t a = 250;
>
> verified_uint8_t b = a - 50 + 50;
>
> verified_uint8_t c = a + 50 - 50;
>
> Clearly computing b will not cause an overflow, but computing c will.  The
> order of operations is left to right.  If the policy is to saturate, b will
> equal 250, and c will equal 205.
Let see how the built-in behave
   {
     unsigned char a=250;
     unsigned char b=50;
     unsigned char c=50;
     unsigned char r=a-b+c;
     std::cout <<"a-50+50 = "<< int(r) << std::endl;
   }
   {
     unsigned char a=250;
     unsigned char b=50;
     unsigned char c=50;
     unsigned char r=a+b-c;
     std::cout <<"a+50-50 = "<< int(r) << std::endl;
   }

The result is
a-50+50 = 250
a+50-50 = 250

> VerifiedInts are also implicitly convertible to their underlying data
> type.  This presents a detection problem when the non-verified int is on
> the LHS of a math operation.  Take:
>
> verified_uint8_t a = 250;
>
> verified_uint8_t b = 50 + a;
>
> Since a is implicitly convertable to a uint8_t, the compiler will perform
> this conversion implicitly, and the result will be an undetected overflow.
I don't think so. 50+a is 300 which when assigned to b will overflow.
> It is for this reason, that I have supplied binary math operators where
> only the RHS is a verified_int, and I have statically asserted them to
> cause a compiler error.  If the user wants to write such an expression,
> they can statically cast 'a' to a uint8_t.
>
I really think there is a design problem here. I, as a possible user, 
will not accept to do this kind of cast.
>> I don't know if the rationale to have on each overflow policy almost all
>> the operation logic is due to performance constraints.
>> Have you considered an overflow policy that contains only the action to do
>> when there is an overflow?
>>
> I chose to allow the policy author to make a single function call to
> determine if overflow has occured, and provide no restrictions on
> implementing the resulting behavior.  The policy author not only has access
> to the type of overflow, but both values in the case of a math operation,
> which would permit creating a periodic policy for example.  Or a policy
> could be created which only checks assignment, and has no run-time cost for
> the math operations, etc...  If more structure is desired, I could provide
> it, but felt the trade-off wasn't worth it, considering I simplified the
> detection logic to a single function call, provided in a single header.
>
>
It is good to isolate the overflow detection logic. However, with your 
design, the user adding a new policy needs to define the overflow policy 
for each one of the operations.
Up to now your library manage with 4 check operations 
(add,substract,multiply/devide) + assignment, but what will happens if 
you add (or worst yet the user adds) an operation that needs to be 
checked? Should all the overflow policies be updated with this new 
checked operation? I was thinking, for example, to scale (*2^n or  
2^(-n). This design seems to don't scale well.

Have you tried to isolate the overflow actions in a policy following 
this interface

struct OverflowPolicy {
   template <typename T, typename U>
   T on_positive_overflow(U value);
   template <typename T>
   T on_negative_overflow(U value);
};

Ignore policy will just return the value, exception policy will throw 
the corresponding exception, saturate will return the 
integer_traits<L>::const_max or integer_traits<L>::const_min, assert 
policy will assert false and return the value, a modulus policy will 
return the value modulo the range of T.

I would expect the compiler to optimize the following code

if (detect_positive_overflow(new_val)) {
   value_=new_val;
} else if (detect_negative_overflow(new_val)) {
   value_=new_val;
} else {
   value_=new_val;
}

as if

value_=new_val;

but I have no checked it yet.

If this optimization is confirmed, this design will scale and should 
perform as well as the built-in types.
If this optimization is not confirmed, it could be an good argument to 
choose an alternative design (maybe the yours) that would perform as 
well as the built-in types for the ignore policy.
Maybe the overflow policy is not enough orthogonal and the library 
should just work for a predefined set of overflow policies.

BTW, it is surprising the way a nan-verified_int<T>is introduced with 
the nan_overflow policy, as the policy is doing much more than checking 
for overflow. I don't see how the user can make the difference between 
nan-integer and integer_traits<L>::const_max. It is curious that 0/0 
doesn't results in nan. Note that I never used a nan-integer with fixed 
size integers :(

Best,
Vicente