Re: Integer overflow in operator new

["J.C. Pizarro" <jcpiza at gmail dot com>]

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