Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#6229 closed defect (fixed)

Template function(s) for overflow checking

Reported by: Kurt Schwehr Owned by: warmerdam
Priority: normal Milestone:
Component: default Version: unspecified
Severity: normal Keywords:
Cc:

Description

size_t VSIMemHandle::Read( void * pBuffer, size_t nSize, size_t nCount )

{
    // FIXME: Integer overflow check should be placed here:
    size_t nBytesToRead = nSize * nCount;

Here is the start to a set of C++ templated functions to check for overflow. I propose these go in the cpl_conv.h. Comments on the implementation, where the code should go, or the template naming?

// Keep headers at the top.

#if defined(__cplusplus) && !defined(CPL_SUPRESS_CPLUSPLUS)
#include <limits>
#endif  // __cplusplus

// yada yada

#if defined(__cplusplus) && !defined(CPL_SUPRESS_CPLUSPLUS)

// Return true if adding the two arguments will overflow their type.
// Both arguments and the destination must be of the same type for this to be a valid check.
template<typename T>
bool CPLAddWillOverflow( T a, T b ) {
  if (a > b) {
    if (  ( std::numeric_limits<T>::max() - a  ) < b )
      return true;
    return false;
  }
  if (  ( std::numeric_limits<T>::max() - b ) < a )
    return true;
  return false;
}

#endif  // __cplusplus

It may be possible to check that both argument types are the same in C++14 and fail to compile if they are not with a static_assert.

Attached is a quick test c++ file.

Attachments (1)

integer_overflow.cc (3.1 KB ) - added by Kurt Schwehr 8 years ago.
Example of using CPLAddWillOverflow() with unsigned short and short

Download all attachments as: .zip

Change History (7)

by Kurt Schwehr, 8 years ago

Attachment: integer_overflow.cc added

Example of using CPLAddWillOverflow() with unsigned short and short

comment:1 by Kurt Schwehr, 8 years ago

And I haven't looked at what happens with negative values for signed types

comment:2 by Even Rouault, 8 years ago

For unsigned types, this would be a bit expensive (no need to compare a > b ), so perhaps having a check for std::numeric_limits<T>::is_signed to have 2 implementations ? And perhaps add the 2 types as template classes and add a static assert they are the same (if that can be done directly, or otherwise test they have same signedness, bitdeph, integerness/floatingpointness) ?

comment:3 by Even Rouault, 8 years ago

In fact looking more at this issue, I'd suggest to match gcc 5 / clang 3.4 ( http://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins ) builtins similar operations, and route the implementation towards them if available

#ifndef __has_builtin
#define __has_builtin(x) 0
#endif

bool CPL_uadd_overflow(unsigned int a, unsigned int b, unsigned int* pres)
{
#if __GNUC__ >= 5 || __has_builtin(__builtin_uadd_overflow)
    return __builtin_uadd_overflow(a,b,pres);
#else
    *pres = a + b;
    return (a > 0xFFFFFFFFU - b);
#endif
}

The following with clang 3.4 / gcc 5.2 generates very efficient, branchless code :

0000000000000000 <_Z17CPL_uadd_overflowjjPj>:
   0:	01 f7                	add    %esi,%edi
   2:	0f 92 c0             	setb   %al
   5:	89 3a                	mov    %edi,(%rdx)
   7:	c3                   	retq  

whereas the generic implementation generates (no branch, but still an extra not and cmp) :

0000000000000000 <_Z17CPL_uadd_overflowjjPj>:
   0:	8d 04 3e             	lea    (%rsi,%rdi,1),%eax
   3:	89 02                	mov    %eax,(%rdx)
   5:	f7 d6                	not    %esi
   7:	39 fe                	cmp    %edi,%esi
   9:	0f 92 c0             	setb   %al
   c:	c3                   	retq   
Last edited 8 years ago by Even Rouault (previous) (diff)

comment:4 by Even Rouault, 7 years ago

Resolution: fixed
Status: newclosed

In 39485:

Add cpl_safemaths.hpp to detect integer overflows (fixes #6229)

comment:5 by Even Rouault, 7 years ago

In 39486:

Use cpl_safemaths.hpp in PDS and ISIS3 drivers (refs #6229)

comment:6 by Even Rouault, 7 years ago

In 39490:

cpl_safemaths.hpp: for MSVC 2010 or later, use safeint.h (refs #6229)

Note: See TracTickets for help on using tickets.