size_t or int for malloc-type functions?

[Mark McIntyre]

65521 x 65552 is 65296 and NOT 4295032592

<sarcasm>
Apparently an entire realm of mathematics has been lost to the world.

Luckily I kept a papyrus scroll describing modular maths in my
pyramid, against just such an eventuality. We'd better hope the
barbarians don't try to set fire to it.
</sarcasm>

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[jacob navia]

Ben Pfaff a écrit :

Actually you do. However, the behaviour on overflow is well-defined.

C99 6.2.5p9 makes it pretty clear that the Standard takes Richard's
point of view:

A computation involving unsigned operands can never
overflow, [...]

wrong

If you quote the full text it says:

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned
integer type is reduced modulo the number that is one greater than the
largest value that can be represented by the resulting type

When the result "cannot be represented by the resulting
integer type" ... If this is not overflow I do not know
what overflow actually means!!!!

This famous paragraph just says that when the computation overflows
it will be reduced modulo "the number that is one greater than
the largest value". I.e. the behavior all CPUs had since ages when
a multiplication overflows!!!

This is just playing with words for NO REASON!!!

 

[Mark McIntyre]

"argument" means the value passed in. In this code:

#include <stdlib.h>
int foo() { malloc(-1); }

the argument to malloc is the value -1 (of type int).

No, thats just how you typed it. As far as malloc is concerned, you
passed UINT_MAX.

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Keith Thompson]

lcc-win32 uses this:

void *calloc(size_t n,size_t s)
{
long long siz = (long long)n * (long long)s;
void *result;
if (siz>>32)
return 0;
result = malloc((size_t)siz);
if (result)
memset(result,0,(size_t)siz);
return result;
}

Which of course is non-portable; there's no guarantee that long long
is bigger than size_t, or that size_t is 32 bits. (That's not a
criticism; code in a C library implementation is not required to be
portable.)

Incidentally, the casts in the arguments to malloc() and memset()
aren't necessary; the value of siz will be converted implicitly to
size_t as long as the declarations of malloc() and memset() are
visible. That's a style issue; the generated code should be the same
with or without the casts.

I wonder if "siz&~0xFFFFFFFF" might be marginally more efficient than
"siz>>32". It tests the upper 32 bits of siz without having to shift
them into the lower 32 bits. I have no particular expectation that it
*is* more efficient, and it's the kind of micro-optimization I
wouldn't recommend in ordinary code, but it might be appropriate in a
runtime library. (I expect it would be faster on some systems, slower
on others, and equivalent on yet others, but if you're only targeting
a single platform it's something to think about.)

sizeof(long long)=8*8
sizeof(size_t)=4*8

Quibble: I think you mean:

CHAR_BIT=8
sizeof(long long)=8
sizeof(size_t)=4

As you know, sizeof yields the size in bytes, not in bits.

 

[Ben Pfaff]

Ben Pfaff a écrit :

Richard Heathfield wrote:
No, you don't get overflow with unsigned types.
Actually you do. However, the behaviour on overflow is well-defined.

C99 6.2.5p9 makes it pretty clear that the Standard takes Richard's
point of view:

A computation involving unsigned operands can never
overflow, [...]

wrong

If you quote the full text it says:

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned
integer type is reduced modulo the number that is one greater than the
largest value that can be represented by the resulting type

When the result "cannot be represented by the resulting
integer type" ... If this is not overflow I do not know
what overflow actually means!!!!

Based on its use in the Standard, I'd guess that the meaning of
overflow in the committee's minds is an exceptional condition
that yields undefined behavior. Because out-of-range unsigned
values are not treated exceptionally and do not yield undefined
behavior, they are not examples of overflow under this
definition. Indeed, the Standard uses "integer overflow" as its
stock example of undefined behavior, not "signed integer
overflow", because "unsigned integer overflow" is a contradiction
in terms according to this definition.

Here is part of what the Rationale says about integer overflow.
I believe that it supports my position:

The keyword unsigned is something of a misnomer, suggesting
as it does in arithmetic that it is non-negative but
capable of overflow. The semantics of the C type unsigned
is that of modulus, or wrap-around, arithmetic for which
overflow has no meaning. The result of an unsigned
arithmetic operation is thus always defined, whereas the
result of a signed operation may be undefined.

 

[Ben Pfaff]

void *calloc(size_t n,size_t s)
{
long long siz = (long long)n * (long long)s;
void *result;
if (siz>>32)
return 0;
result = malloc((size_t)siz);
if (result)
memset(result,0,(size_t)siz);
return result;
}

[...]

I wonder if "siz&~0xFFFFFFFF" might be marginally more efficient than
"siz>>32". [...]

I'd recommend "siz > SIZE_MAX" as being both clear and portable.

 

[jacob navia]

Keith Thompson a écrit :

Which of course is non-portable; there's no guarantee that long long
is bigger than size_t, or that size_t is 32 bits. (That's not a
criticism; code in a C library implementation is not required to be
portable.)

This is portable to all systems where
1) long long is 64 bits
2) size_t is 32 bits

Incidentally, the casts in the arguments to malloc() and memset()
aren't necessary; the value of siz will be converted implicitly to
size_t as long as the declarations of malloc() and memset() are
visible.

True.

That's a style issue; the generated code should be the same

with or without the casts.

I wonder if "siz&~0xFFFFFFFF" might be marginally more efficient than
"siz>>32". It tests the upper 32 bits of siz without having to shift
them into the lower 32 bits. I have no particular expectation that it
*is* more efficient, and it's the kind of micro-optimization I
wouldn't recommend in ordinary code, but it might be appropriate in a
runtime library. (I expect it would be faster on some systems, slower
on others, and equivalent on yet others, but if you're only targeting
a single platform it's something to think about.)

In the 32 bit version of lcc-win32 (the other is called lcc-win64)
a long long is splitted anyway, a shift of 32 produces actually
no shifts in my implementation, I just access the upper 32 bits.
If its in memory I access the upper 32 bits, and if it is in
the register pair EAX:EDX I just access EDX.

I am used to this since I programmed this optimization, and
then I do not realize that other compilers would be maybe different.

Quibble: I think you mean:

CHAR_BIT=8
sizeof(long long)=8
sizeof(size_t)=4

As you know, sizeof yields the size in bytes, not in bits.

Yes. Thanks

 

[Keith Thompson]

Actually you do. However, the behaviour on overflow is well-defined.

I suppose you could quibble about the exact meaning of the word
'overflow', but it is clear what Navia's meaning is and it serves no
purpose to pretend he is saying something other than what he is.

The standard's use of the term "overflow" is unambiguous. It
explicitly does *not* use that term to refer to an unsigned
calculation whose "mathematical result" cannot be represented in the
result type.

It easily *could* have use the term "overflow" to describe this (and I
think I would have been happier if it had), but it didn't. We're not
going to be able to communicate about this unless we have a common
vocabulary; I suggest that the only common vocabulary that we can use
is the one used by the standard.

Yes, I know what jacob means by "overflow", but communication would be
easier if he'd refrain from using that term in contradiction to the
way the standard uses it, especially in the context of the very
section of the standard that says quite clearly that unsigned
operations cannot overflow. It's like saying that a system with
CHAR_BIT==16 has 2-byte characters. Call it "wraparound", or
"reduction modulo 2**N", or at least put the word "overflow" in
quotation marks and make it clear that you're not using the term the
way the standard does.

 

[Kenny McCormack]

Actually you do. However, the behaviour on overflow is well-defined.

I suppose you could quibble about the exact meaning of the word
'overflow', but it is clear what Navia's meaning is and it serves no
purpose to pretend he is saying something other than what he is.

Obviously true - for anyone with an IQ above 15.

But pigs will fly and hell will freeze over before heathfield admits to
so much as understanding, much less agreeing with, anything posted by Navia.

As someone else pointed out, part of the ethos of clc is that to even
admit to understanding someone's post is to be seen as, to some extent,
agreeing with it. In order to keep up your macho reputation, you have
to totally misrepresent any post by anyone you don't like.

 

[Kenny McCormack]

"argument" means the value passed in. In this code:

#include <stdlib.h>
int foo() { malloc(-1); }

the argument to malloc is the value -1 (of type int).

The type "size_t" w.r.t. malloc is known as the "formal parameter type"
(often the word 'formal' is dropped for convenience's sake).

Obviously true. But the dim bulbs around here are never going to admit it.

 

[Mark McIntyre]

This is portable to all systems where
1) long long is 64 bits
2) size_t is 32 bits

Which limits it to a fairly small subset of systems, by the way...
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[jacob navia]

Ben Pfaff a écrit :

Based on its use in the Standard, I'd guess that the meaning of
overflow in the committee's minds is an exceptional condition
that yields undefined behavior. Because out-of-range unsigned
values are not treated exceptionally and do not yield undefined
behavior, they are not examples of overflow under this
definition. Indeed, the Standard uses "integer overflow" as its
stock example of undefined behavior, not "signed integer
overflow", because "unsigned integer overflow" is a contradiction
in terms according to this definition.

Here is part of what the Rationale says about integer overflow.
I believe that it supports my position:

The keyword unsigned is something of a misnomer, suggesting
as it does in arithmetic that it is non-negative but
capable of overflow. The semantics of the C type unsigned
is that of modulus, or wrap-around, arithmetic for which
overflow has no meaning. The result of an unsigned
arithmetic operation is thus always defined, whereas the
result of a signed operation may be undefined.

Yes, I know that, and I agree that the semantics of unsigned is
wrap around. What I am saying is that when "the result cannot be
represented" and this wrap around semantics reduces the result,
this reduced result is mathematically WRONG in the sense of the USUAL
multiplication operation.

PHEW!!!!

Specifically when I use the malloc (p * sizeof *p) "idiom"
even if the semantics are well defined this is NOT what I
inteded with that multiplication!!!!

There is no point in throwing me standards texts because I am not
questioning them. I am just saying that this "results that cannot be
represented" lead to a wrong result being passed to malloc!!!


I just can't understand why it is impossible to agree in such
an evident stuff !!!

 

[Ben Pfaff]

Ben Pfaff a écrit :

Yes, I know that, and I agree that the semantics of unsigned is
wrap around. What I am saying is that when "the result cannot be
represented" and this wrap around semantics reduces the result,
this reduced result is mathematically WRONG in the sense of the USUAL
multiplication operation.

The problem that we have here is one of definitions. The
Standard defines "overflow" one way; you are defining it another.
If you want to say that the customary mathematical result and the
modulo result are different, that's one thing, but calling it
overflow just confuses everyone who is familiar with the C
language.

 

[CBFalconer]

Kenny McCormack wrote:
.... snip ...

It's not claptrap, unlike what Dubya is spewing, and I would
therefore certainly hope he's sufficiently intelligent and
mathematically well-educated to believe it. I'd recommend
reading up on the mathematical concept of rings before you
claim otherwise.

It's all in the sig.

--
+-------------------+ .:\:\:/:/:.
| PLEASE DO NOT F :.:\:\:/:/:.:
| FEED THE TROLLS | :=.' - - '.=:
| | '=(\ 9 9 /)='
| Thank you, | ( (_) )
| Management | /`-vvv-'\
+-------------------+ / \
| | @@@ / /|,,,,,|\ \
| | @@@ /_// /^\ \\_\
@x@@x@ | | |/ WW( ( ) )WW
\||||/ | | \| __\,,\ /,,/__
\||/ | | | jgs (______Y______)
/\/\/\/\/\/\/\/\//\/\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
==============================================================

fix (vb.): 1. to paper over, obscure, hide from public view; 2.
to work around, in a way that produces unintended consequences
that are worse than the original problem. Usage: "Windows ME
fixes many of the shortcomings of Windows 98 SE". - Hutchinson

 

[CBFalconer]

.... snip ...

Or are you implying that

65521 x 65552 is 65296 and NOT 4295032592

Yes, if done with unsigned shorts, i.e. any unsigned 16 bit type.
That's what the standard prescribes. Have you ever bothered to
read the standard? Without doing so how can you dare to modify the
lcc compiler?

 

[Keith Thompson]

Keith Thompson a écrit :

This is portable to all systems where
1) long long is 64 bits
2) size_t is 32 bits

[...]

Yes, and only to such systems. That's what I meant by "non-portable".

 

[CBFalconer]

jacob navia wrote:
.... snip ...

Rings are the mathematical construct that correspond to the way
in which the C standard defines arithmetic for unsigned types.

IIRC a ring defines a set of objects that are members of the ring,
and a set of operations on those objects, such that <m1 operation
m2> yields a member of the ring. unsigned objects and the
operations +, -, and * meet this definiton. The operation / does
not. Exponentiation does. Many bits have been dropped in my
memory, however.

The point is that you can prove things about the behaviour of
rings, and then immediately apply those results to anything that
meets the definition. Something like subroutines.

 

[Nelu]

christian.bau a écrit :

lcc-win32 uses this:

void *calloc(size_t n,size_t s)
{
long long siz = (long long)n * (long long)s;
void *result;
if (siz>>32)
return 0;
result = malloc((size_t)siz);
if (result)
memset(result,0,(size_t)siz);
return result;
}

Why not:

void *calloc(size_t n, size_t s) {
void *result;
size_t sz;
if(SIZE_MAX/n<s) {
sz=n*s;
result=malloc(n*s);
if(result) {
memset(result,0,sz);
return result;
}
}
return NULL;
}

?

 

[slebetman]

Nevertheless this behavior of unsigned C arithmetic is
sureley NEVER CORRECT and I have never seen a useful
program that relies on this behavior for something useful.

Plenty of CRC and checksum generating code find this behavior useful.
Can't believe you've never seen them since they're all over the place.

 

[Nelu]

Why not:

void *calloc(size_t n, size_t s) {
void *result;
size_t sz;
if(SIZE_MAX/n<s) {

Sorry, '>'.