This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Integer overflow in operator new
- From: "J.C. Pizarro" <jcpiza at gmail dot com>
- To: "Ross Smith" <r-smith at ihug dot co dot nz>, "Ross Ridge" <rridge at csclub dot uwaterloo dot ca>, "Joe Buck" <Joe dot Buck at synopsys dot com>
- Cc: gcc at gcc dot gnu dot org
- Date: Mon, 9 Apr 2007 03:22:29 +0200
- Subject: Re: Integer overflow in operator new
Joe Buck wrote:
> > > inline size_t __compute_size(size_t num, size_t size) {
> > > size_t product = num * size;
> > > return product >= num ? product : ~size_t(0);
> > > }
2007/4/9, Ross Smith <r-smith@ihug.co.nz> wrote:
On Monday, 9 April 2007 10:23, Florian Weimer wrote:
> * Ross Ridge:
> > Florian Weimer writes:
> >>I don't think this check is correct. Consider num = 0x33333334 and
> >>size = 6. It seems that the check is difficult to perform
> >> efficiently unless the architecture provides unsigned
> >> multiplication with overflow detection, or an instruction to
> >> implement __builtin_clz.
> >
> > This should work instead:
> >
> > inline size_t __compute_size(size_t num, size_t size) {
> > if (num > ~size_t(0) / size)
> > return ~size_t(0);
> > return num * size;
> > }
>
> Yeah, but that division is fairly expensive if it can't be performed
> at compile time. OTOH, if __compute_size is inlined in all places,
> code size does increase somewhat.
You could avoid the division in nearly all cases by checking for
reasonably-sized arguments first:
inline size_t __compute_size(size_t num, size_t size) {
static const int max_bits = sizeof(size_t) * CHAR_BITS;
int low_num, low_size;
low_num = num < ((size_t)1 << (max_bits * 5 / 8));
low_size = size < ((size_t)1 << (max_bits * 3 / 8));
if (__builtin_expect(low_num && low_size, 1)
|| num <= ~(size_t)0 / size)
return num * size;
else
return ~size_t(0);
}
This code is bigger than Joe Buck's.
I'm sorry, the previous 3rd source code .c is an error mine.
-----------------------------------------
Joe Buck's code: 10 instructions
Ross Ridge's code: 16 instructions
Ross Smith's code: 23 instructions
-----------------------------------------
Joe Buck's code: 9 instructions
__compute_size:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx
movl %edx, %eax
imull 12(%ebp), %eax
cmpl %edx, %eax
orl $-1, %eax
popl %ebp
ret
Ross Ridge's code: 16 instructions
__compute_size:
pushl %ebp
movl %esp, %ebp
orl $-1, %eax
xorl %edx, %edx
movl 12(%ebp), %ecx
divl %ecx
pushl %ebx
movl 8(%ebp), %ebx
orl $-1, %edx
cmpl %eax, %ebx
movl %ebx, %edx
imull %ecx, %edx
popl %ebx
movl %edx, %eax
popl %ebp
ret
Ross Smith's code: 23 instructions
__compute_size:
pushl %ebp
movl %esp, %ebp
pushl %ebx
movl 8(%ebp), %ebx
cmpl $1048575, %ebx
movl 12(%ebp), %ecx
setbe %dl
xorl %eax, %eax
cmpl $4095, %ecx
setbe %al
andb $1, %dl
testl %eax, %eax
orl $-1, %eax
xorl %edx, %edx
divl %ecx
orl $-1, %edx
cmpl %eax, %ebx
movl %ebx, %edx
imull %ecx, %edx
popl %ebx
movl %edx, %eax
popl %ebp
ret
J.C. Pizarro