size_t or int for malloc-type functions?

[jacob navia]

Rcently I posted code in this group, to help a user
that asked to know how he could find out the size of
a block allocated with malloc.

As always when I post something, the same group
of people started to try to find possible errors,
a harmless passtime they seem to enjoy.

One of their remarks was that I used "int" instead of
"size_t" for the input of my allocator function.

As I explained, I prefer a signed type to the
unsigned size_t because small negative number will be
confused with huge integers when interpreted as unsigned.

I researched a bit the subject, and I found a type

ssize_t

The name is defined for instance in
http://www.delorie.com/gnu/docs/glibc/libc_239.html

Data Type: ssize_t
This data type is used to represent the sizes of blocks that can be
read or written in a single operation. It is similar to size_t, but must
be a signed type.

Another reference to this type appears in:
http://bochs.sourceforge.net/cgi-bin...dent?i=ssize_t
with
#define ssize_t long

This concern with the usage of an unsigned type that can be
easily lead to errors (of course only for people that do
make errors like me...) is also expressed in the document
ISO/IEC JTC1 SC22 WG14 N1135 :
"Specification for Safer, More Secure C Library Functions"
where they propose:

Extremely large object sizes are frequently a sign that an object’s size
was calculated incorrectly. For example, negative numbers appear as very
large positive numbers when converted to an unsigned type like size_t.

Also, some implementations do not support objects as large as the
maximum value that can be represented by type size_t.

For those reasons, it is sometimes beneficial to restrict the range of
object sizes to detect programming errors.

They propose having an unsigned rsize_t, but a macro RSIZE_MAX that
would limit the range of the object size.

I post this to document why having an "int" as an argument to a
malloc-type function is not such a bad idea.

Your opinion may differ.

jacob

[Keith Thompson]

"Spiros Bousbouras" <sp****@gmail.comwrites:

jacob navia wrote:

[...]

>Exactly. If you see my message, it meant that the
discussion proposed to avoid

c = malloc(a*b)

because of the overflow problems, and proposed to
change that to

c = calloc(a,b);

Then people started arguing that "overflow doesn't exist"
etc etc.

I think a consensus would be to accept calloc as a "safer"
alternative to just multiplying without overflow check.

I have only read parts of the thread here and there so it
may have been explained already but why is calloc(a,b)
safer ? Generally you don't know that the calloc implementation
checks for wraparound. Even if you have seen the source
code of the calloc you're using and know that it checks for
wraparound you can't know that a newer version of the
library will still do the same. It seems to me that if a and b
are large enough to make wraparound probable then the
only safe option is to check for that before calling malloc()
or calloc().

Because a calloc() implementation that blindly multiplies its two
arguments without checking whether the result wraps around is
non-conforming. If the user writes malloc(a*b), and the
multiplication wraps around, malloc() *must* attempt to allocated the
number of bytes specified by the (possibly wrapped) result of a*b; if
the user writes calloc(a, b), calloc() must attempt to allocate enough
memory for enough space for "a" objects of size "b" bytes each, and
must return NULL if it fails to do so. (But some calloc()
implementations do fail to check for wraparound, and are therefore
non-conforming, so in practice using calloc() isn't that much safer.)

But I question jacob's use of the word "consensus". I've been
following this discussion, and I haven't seen anyone else agree that
using calloc() is the proper solution; it imposes the additional
overhead of initializing the allocated memory to all-bits-zero, which
could be sigificant for the large allocations we're talking about.

Using calloc() rather than malloc() in this case merely detects the
error of attempting to allocate more than SIZE_MAX bytes. Detecting
errors is good, but avoiding them in the first place is better, and
using calloc() doesn't avoid the error, it merely diagnoses it better.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Richard]

"Spiros Bousbouras" <sp****@gmail.comwrites:

jacob navia wrote:

>Spiros Bousbouras a écrit :

Peter Nilsson wrote:

ku****@wizard.net wrote:

Yes, but it's unnecessary to consider rings in general in order to
understand
unsigned integers.
Hear hear for that. All the discussion about
rings does is to obfuscate the issue. It is also
out of topic.

Exactly. If you see my message, it meant that the
discussion proposed to avoid

c = malloc(a*b)

because of the overflow problems, and proposed to
change that to

c = calloc(a,b);

Then people started arguing that "overflow doesn't exist"
etc etc.

I think a consensus would be to accept calloc as a "safer"
alternative to just multiplying without overflow check.

I have only read parts of the thread here and there so it
may have been explained already but why is calloc(a,b)
safer ?

Because calloc takes care of the math and necessary wraparound
checks. if your multiplication wraps before the call to malloc then
malloc will try to allocate that "corrupt" number of bytes.

[Keith Thompson]

Keith Thompson <ks***@mib.orgwrites:
[...]

Because a calloc() implementation that blindly multiplies its two
arguments without checking whether the result wraps around is
non-conforming. If the user writes malloc(a*b), and the
multiplication wraps around, malloc() *must* attempt to allocated the
number of bytes specified by the (possibly wrapped) result of a*b; if
the user writes calloc(a, b), calloc() must attempt to allocate enough
memory for enough space for "a" objects of size "b" bytes each, and
must return NULL if it fails to do so. (But some calloc()
implementations do fail to check for wraparound, and are therefore
non-conforming, so in practice using calloc() isn't that much safer.)

On re-reading the above, I see that it was potentially unclear.

calloc(a, b) must attempt to allocate a*b bytes, where a*b denotes the
result of multiplying a by b *without* reducing the result modulo
SIZE_MAX+1. For example, given:
size_t a = SIZE_MAX;
size_t b = SIZE_MAX;
a * b == 1 when the multiplication is done in type size_t, but if
calloc(SIZE_MAX, SIZE_MAX) allocates only 1 byte, it's non-conforming.
On the other hand, malloc(SIZE_MAX * SIZE_MAX) *must* attempt to
allocate 1 byte, because the wraparound occurs before malloc() is
called.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[CBFalconer]

Richard Tobin wrote:

CBFalconer <cb********@maineline.netwrote:

>>I looked for that, but all I found was that size_t is the type
returned by sizeof, and that cannot be applied to objects
allocated by [mc]alloc().

>Regardless, I believe we can imply that conclusion. C can only
operate on objects. The size of an object is garnered by sizeof,
and is of type size_t. malloc doesn't return generic objects, it
returns pointers.

I didn't say it returned them. Are you suggesting that the pointer
returned by malloc (or calloc) doesn't point to an object?

No, I am saying it doesn't create objects. It creates space into
which you may stuff an object, and returns a pointer to that
space. It isn't a valid object until it is stuffed (possibly by
calloc).

Please don't strip attributions for material you quote.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

[CBFalconer]

ku****@wizard.net wrote:

>
CBFalconer wrote:

Richard Tobin wrote:

CBFalconer <cb********@maineline.netwrote:
>
>It's a conclusion that has to be drawn, because it does say
>somewhere that size_t can describe the size of any object.
>
I looked for that, but all I found was that size_t is the type
returned by sizeof, and that cannot be applied to objects
allocated by [mc]alloc().

Regardless, I believe we can imply that conclusion.

It it certainly possible to imply it; it's been implied frequently by
many different people. The question is whether it's possible to infer
it. I've not seen valid arguments inferring that conclusion from actual
citations from the C standard.

... The size of an object is garnered by sizeof,

Citation please, for the applicability of sizeof to dynamically
allocated objects?

struct foo ( whatever };
struct foo *p;
p = malloc(sizeof *p);
size = sizeof(*p);

Note that you can't apply sizeof to void.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

[Douglas A. Gwyn]

"Jun Woong" <wo***@icu.ac.krwrote in message
news:11*********************@s80g2000cwa.googlegro ups.com...

if (n == 0 || ((size_t) -1) / n >= s)

I'd like to request that people please not assume that -1
is represented by all 1 value bits.
((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

[Keith Thompson]

CBFalconer <cb********@yahoo.comwrites:

Richard Tobin wrote:

>CBFalconer <cb********@maineline.netwrote:

>>>I looked for that, but all I found was that size_t is the type
returned by sizeof, and that cannot be applied to objects
allocated by [mc]alloc().

>>Regardless, I believe we can imply that conclusion. C can only
operate on objects. The size of an object is garnered by sizeof,
and is of type size_t. malloc doesn't return generic objects, it
returns pointers.

I didn't say it returned them. Are you suggesting that the pointer
returned by malloc (or calloc) doesn't point to an object?

No, I am saying it doesn't create objects. It creates space into
which you may stuff an object, and returns a pointer to that
space. It isn't a valid object until it is stuffed (possibly by
calloc).

But it does create objects. An object is a "region of data storage in
the execution environment, the contents of which can represent values"
(C99 3.14); the space allocated by malloc() or calloc() qualifies.

If you're saying it's not an object before a value is assigned to it,
but becomes on after a value has been assigned to it, consider this:

{
int obj;
}

Is "obj" an object? I say it is, even if it's uninitialized.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

CBFalconer <cb********@yahoo.comwrites:

ku****@wizard.net wrote:

[...]

>Citation please, for the applicability of sizeof to dynamically
allocated objects?

struct foo ( whatever };
struct foo *p;
p = malloc(sizeof *p);
size = sizeof(*p);

Note that you can't apply sizeof to void.

Good point.

The general case of an array object allocated by calloc() is more
complicated. It's straightforward if the number of elements is a
constant:

struct foo *p = calloc(10, sizeof *p);
size = sizeof (struct foo[10]);

but more generally:

struct foo *p = calloc(n, sizeof *p);
size = sizeof(struct foo[n]);

I believe the latter is legal; "struct foo[n]" is a VLA type. And if
n * sizeof(struct foo) exceeds SIZE_MAX, I suppose apply sizeof
invokes undefined behavior.

But I don't believe UB is invoked *until* you attempt to apply sizeof.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

"Douglas A. Gwyn" <DA****@null.netwrites:

"Jun Woong" <wo***@icu.ac.krwrote in message
news:11*********************@s80g2000cwa.googlegro ups.com...

> if (n == 0 || ((size_t) -1) / n >= s)

I'd like to request that people please not assume that -1
is represented by all 1 value bits.
((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

Can (size_t)-1 and (size_t)0 - 1 differ? If so, how?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Richard Heathfield]

Douglas A. Gwyn said:

"Jun Woong" <wo***@icu.ac.krwrote in message
news:11*********************@s80g2000cwa.googlegro ups.com...

> if (n == 0 || ((size_t) -1) / n >= s)

I'd like to request that people please not assume that -1
is represented by all 1 value bits.

Are people assuming that? I thought they were deducing from the reduction
rule for unsigned types that (size_t)-1 is the largest possible value of a
size_t, and *therefore*, with unsigned integer types being pure binary
representations, it is a size_t with every value bit set (i.e. "all 1 value
bits" is a consequence, not a cause).

((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

Could you please explain how (size_t)-1 might *not* have all value bits set,
in a conforming implementation?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Chris Dollin]

Spiros Bousbouras wrote:

That's not what "onto" means. Just by virtue of the fact
that + and * are functions we know that for every pair
(a,b) there's going to be an image under + and an image
under * ie a+b and a*b are both going to be defined.

Functions don't have to be total: consider, for example,
division.

--
Chris "first on the Underground!" Dollin
"- born in the lab under strict supervision -", - Magenta, /Genetesis/

[Clark S. Cox III]

Douglas A. Gwyn wrote:

"Jun Woong" <wo***@icu.ac.krwrote in message
news:11*********************@s80g2000cwa.googlegro ups.com...

> if (n == 0 || ((size_t) -1) / n >= s)

I'd like to request that people please not assume that -1
is represented by all 1 value bits.

Where do you see that assumption?

((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

How could ((size_t)0 - 1) or (~(size_t)0) differ in any way from
((size_t)-1)?

--
Clark S. Cox III
cl*******@gmail.com

[Francois Grieu]

In article <12*************@corp.supernews.com>,
"Clark S. Cox III" <cl*******@gmail.comwrote:

((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

How could ((size_t)0 - 1) or (~(size_t)0) differ in any way from
((size_t)-1)?

Because -1 is of type signed int and thus it's cast
to size_t undefined, is not it ?
François Grieu

[Richard Heathfield]

Francois Grieu said:

In article <12*************@corp.supernews.com>,
"Clark S. Cox III" <cl*******@gmail.comwrote:

((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

How could ((size_t)0 - 1) or (~(size_t)0) differ in any way from
((size_t)-1)?

Because -1 is of type signed int and thus it's cast
to size_t undefined, is not it ?

Why?

The Standard has this to say on implicit and explicit conversions, in
6.3.1.3 Signed and Unsigned Integers:

"Otherwise, if the new type is unsigned, the value is converted by
repeatedly adding or subtracting one more than the maximum value that can
be represented in the new type until the value is in the range of the new
type."

That looks pretty defined to me. What am I missing?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Clark S. Cox III]

Francois Grieu wrote:

In article <12*************@corp.supernews.com>,
"Clark S. Cox III" <cl*******@gmail.comwrote:

>>((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

How could ((size_t)0 - 1) or (~(size_t)0) differ in any way from
((size_t)-1)?

Because -1 is of type signed int and thus it's cast
to size_t undefined, is not it ?

No, it most certainly is not. When a signed integer is converted to an
unsigned integer (like size_t), the value is converted according to
modulo arithmetic (i.e. -1, becomes the maximum possible value, -2
becomes one less than the maximum value, etc.)

--
Clark S. Cox III
cl*******@gmail.com

[Peter Nilsson]

Clark S. Cox III wrote:

Douglas A. Gwyn wrote:

if (n == 0 || ((size_t) -1) / n >= s)

I'd like to request that people please not assume that -1
is represented by all 1 value bits.

Where do you see that assumption?

((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

How could ((size_t)0 - 1) or (~(size_t)0) differ in any way from
((size_t)-1)?

They could differ (potentially for the worse) if size_t was subject
to integral promotion. Though you're unlikely to find an implementation
where that is the case.

--
Peter

[Jun Woong]

Peter Nilsson wrote:

Clark S. Cox III wrote:

Douglas A. Gwyn wrote:

if (n == 0 || ((size_t) -1) / n >= s)
>
I'd like to request that people please not assume that -1
is represented by all 1 value bits.

Where do you see that assumption?

((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

How could ((size_t)0 - 1) or (~(size_t)0) differ in any way from
((size_t)-1)?

They could differ (potentially for the worse) if size_t was subject
to integral promotion. Though you're unlikely to find an implementation
where that is the case.

Interestingly, if size_t is subject to integral promotion, only
((size_t)-1) works correctly.
--
Jun, Woong (woong at icu.ac.kr)
Samsung Electronics Co., Ltd.

``All opinions expressed are mine, and do not represent
the official opinions of any organization.''

[Clark S. Cox III]

Peter Nilsson wrote:

Clark S. Cox III wrote:

Douglas A. Gwyn wrote:

if (n == 0 || ((size_t) -1) / n >= s)
I'd like to request that people please not assume that -1
is represented by all 1 value bits.

Where do you see that assumption?

((size_t)0 - 1) is one nice way to get all 1 value bits of
the desired width. You could also use ~(size_t)0.

How could ((size_t)0 - 1) or (~(size_t)0) differ in any way from
((size_t)-1)?

They could differ (potentially for the worse) if size_t was subject
to integral promotion. Though you're unlikely to find an implementation
where that is the case.

Ahh, I hadn't thought of that. But, as you indicated, this actually
argues that (size_t)-1 is the "correct" construct; in the presence of
integral promotion, it is the only on that still yields the maximum
possible size_t value.
--
Clark S. Cox III
cl*******@gmail.com

[Spiros Bousbouras]

Chris Dollin wrote:

Spiros Bousbouras wrote:

That's not what "onto" means. Just by virtue of the fact
that + and * are functions we know that for every pair
(a,b) there's going to be an image under + and an image
under * ie a+b and a*b are both going to be defined.

Functions don't have to be total: consider, for example,
division.

I think in recursion theory you may have a distinction
between total and non-total functions but in every other
branch of mathematics I've seen and certainly in algebra
you don't ; function means "total" function. In particular,
every textbook on set theory will tell you that a function
from a set A into a set B is a subset of AxB such that for
*every* a in A there is exactly one b in B such that (a,b) is
in f. Algebra uses the set-theoretic definition of a function.

[Chris Dollin]

Spiros Bousbouras wrote:

Chris Dollin wrote:

>Spiros Bousbouras wrote:

That's not what "onto" means. Just by virtue of the fact
that + and * are functions we know that for every pair
(a,b) there's going to be an image under + and an image
under * ie a+b and a*b are both going to be defined.

Functions don't have to be total: consider, for example,
division.

I think in recursion theory you may have a distinction
between total and non-total functions but in every other
branch of mathematics I've seen and certainly in algebra
you don't ; function means "total" function. In particular,
every textbook on set theory will tell you that a function
from a set A into a set B is a subset of AxB such that for
*every* a in A there is exactly one b in B such that (a,b) is
in f. Algebra uses the set-theoretic definition of a function.

Division.

--
Chris "first on the Underground!" Dollin
The shortcuts are all full of people using them.

[Douglas A. Gwyn]

"Clark S. Cox III" <cl*******@gmail.comwrote in message
news:12*************@corp.supernews.com...

Peter Nilsson wrote:

>They could differ (potentially for the worse) if size_t was subject
to integral promotion. Though you're unlikely to find an implementation
where that is the case.

Ahh, I hadn't thought of that. But, as you indicated, this actually
argues that (size_t)-1 is the "correct" construct; in the presence of
integral promotion, it is the only on that still yields the maximum
possible size_t value.

Actually I missed that the promotion and conversion rules would
produce the right result for (size_t)-1. However, why doesn't
~(size_t)0 work?

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

Douglas A. Gwyn wrote:

"Clark S. Cox III" <cl*******@gmail.comwrote in message
news:12*************@corp.supernews.com...

Peter Nilsson wrote:

They could differ (potentially for the worse) if size_t was subject
to integral promotion. Though you're unlikely to find an implementation
where that is the case.

Ahh, I hadn't thought of that. But, as you indicated, this actually
argues that (size_t)-1 is the "correct" construct; in the presence of
integral promotion, it is the only on that still yields the maximum
possible size_t value.

Actually I missed that the promotion and conversion rules would
produce the right result for (size_t)-1. However, why doesn't
~(size_t)0 work?

If size_t is promoted to int, ~(size_t)0 is equivalent to
~(int)(size_t)0, or simply ~0. It might have been nice if ~'s operand
didn't undergo the integer promotions, but it does.

[CBFalconer]

"Douglas A. Gwyn" wrote:

"Clark S. Cox III" <cl*******@gmail.comwrote in message

>Peter Nilsson wrote:

>>They could differ (potentially for the worse) if size_t was
subject to integral promotion. Though you're unlikely to find
an implementation where that is the case.

Ahh, I hadn't thought of that. But, as you indicated, this
actually argues that (size_t)-1 is the "correct" construct; in
the presence of integral promotion, it is the only on that still
yields the maximum possible size_t value.

Actually I missed that the promotion and conversion rules would
produce the right result for (size_t)-1. However, why doesn't
~(size_t)0 work?

Because that is sensitive to the storage format. It may be 2's
complement, 1's complement, or sign-magnitude. ~(size_t)0 will
only work for 2's complement, thus not portable.

--
"I have a creative mind. You (singular) are eccentric.
He is insane. We are losing sight of reality.
You (plural) are smoking crack. They are certifiable."
Declension of verbs, per Lewin Edwards

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

CBFalconer wrote:

"Douglas A. Gwyn" wrote:

"Clark S. Cox III" <cl*******@gmail.comwrote in message

Peter Nilsson wrote:

They could differ (potentially for the worse) if size_t was
subject to integral promotion. Though you're unlikely to find
an implementation where that is the case.

Ahh, I hadn't thought of that. But, as you indicated, this
actually argues that (size_t)-1 is the "correct" construct; in
the presence of integral promotion, it is the only on that still
yields the maximum possible size_t value.

Actually I missed that the promotion and conversion rules would
produce the right result for (size_t)-1. However, why doesn't
~(size_t)0 work?

Because that is sensitive to the storage format. It may be 2's
complement, 1's complement, or sign-magnitude. ~(size_t)0 will
only work for 2's complement, thus not portable.

Depending on how you use it, ~(size_t)0 is not guaranteed to work for
2's complement. If size_t promotes to signed int, ~(size_t)0 has type
int and value -1. You don't get SIZE_MAX unless you then convert /that/
to size_t.

[Clark S. Cox III]

Douglas A. Gwyn wrote:

"Clark S. Cox III" <cl*******@gmail.comwrote in message
news:12*************@corp.supernews.com...

>Peter Nilsson wrote:

>>They could differ (potentially for the worse) if size_t was subject
to integral promotion. Though you're unlikely to find an implementation
where that is the case.

Ahh, I hadn't thought of that. But, as you indicated, this actually
argues that (size_t)-1 is the "correct" construct; in the presence of
integral promotion, it is the only on that still yields the maximum
possible size_t value.

Actually I missed that the promotion and conversion rules would
produce the right result for (size_t)-1. However, why doesn't
~(size_t)0 work?

Because, if size_t promotes to int, applying the '~' operator will
provide a result that is a (signed) int. This int will *only* have the
value of -1 on twos-compliment machines; converting *that* -1 back to
size_t will result in the correct value

Works on twos-complement machines:
size_t foo = (size_t)~(size_t)0;
size_t bar = (size_t)~0;

Works on all machines:
size_t baz = (size_t)-1;
--
Clark S. Cox III
cl*******@gmail.com

[Douglas A. Gwyn]

CBFalconer wrote:

"Douglas A. Gwyn" wrote:

Actually I missed that the promotion and conversion rules would
produce the right result for (size_t)-1. However, why doesn't
~(size_t)0 work?

Because that is sensitive to the storage format. It may be 2's
complement, 1's complement, or sign-magnitude. ~(size_t)0 will
only work for 2's complement, thus not portable.

No, that was my complaint about -1, which I was thinking
for ones-complement would have produced x...FFFFFE rather
than the desired x...FFFFFF A bitwise complement of an
all-0 bit pattern should give all 1 bits.

[Clark S. Cox III]

Douglas A. Gwyn wrote:

CBFalconer wrote:

>"Douglas A. Gwyn" wrote:

>>Actually I missed that the promotion and conversion rules would
produce the right result for (size_t)-1. However, why doesn't
~(size_t)0 work?

Because that is sensitive to the storage format. It may be 2's
complement, 1's complement, or sign-magnitude. ~(size_t)0 will
only work for 2's complement, thus not portable.

No, that was my complaint about -1, which I was thinking
for ones-complement would have produced x...FFFFFE rather
than the desired x...FFFFFF

This is not the case. We are guaranteed that *any* signed "-1", when
converted to an unsigned type will be the maximum possible value for
that type. The representation doesn't matter, only the value. Period.

--
Clark S. Cox III
cl*******@gmail.com

[CBFalconer]

"Douglas A. Gwyn" wrote:

CBFalconer wrote:

>"Douglas A. Gwyn" wrote:

>>Actually I missed that the promotion and conversion rules would
produce the right result for (size_t)-1. However, why doesn't
~(size_t)0 work?

Because that is sensitive to the storage format. It may be 2's
complement, 1's complement, or sign-magnitude. ~(size_t)0 will
only work for 2's complement, thus not portable.

No, that was my complaint about -1, which I was thinking
for ones-complement would have produced x...FFFFFE rather
than the desired x...FFFFFF A bitwise complement of an
all-0 bit pattern should give all 1 bits.

But the conversion from int to unsigned is specified to make that
correction. A negative value doesn't fit into the range of an
unsigned type, so the standard specifies that it is corrected by
adding SIZE_MAX+1 until the result is in range. Works every time.

--
"I was born lazy. I am no lazier now than I was forty years
ago, but that is because I reached the limit forty years ago.
You can't go beyond possibility." -- Mark Twain

[Cesar Rabak]

Steve Summit escreveu:

"santosh" <sa*********@gmail.comwrites:

>>In which case I suppose calloc() should check whether the total memory
requested can be represented by the size_t type without causing
wrap-around.

With perfect 20/20 hindsight I agree, but...

Keith Thompson writes:

>Right. In fact, it *must* do so

I'd be much more inclined to agree with this if the Standard
explicitly said

If the product nmemb * size cannot be represented as a
size_t, the calloc function returns NULL.

I wish the Standard did say that. This is really a grey area, a
longstanding source of bugs and misunderstanding. (See e.g. the
related c.l.c. FAQ 7.16.)

Without the explicit statement (and as the arguments presented by
several knowledgeable posters in this thread prove), I think an
implementor could be excused for assuming that the Standard's
intent was

If the product nmemb * size cannot be represented as a
size_t, the behavior is undefined.

...although since the Standard doesn't say *that* explicitly,
either, it's sort of doubly or meta undefined!

I disagree that we accept 'meta undefinedness' as conceptually Standard
compliant.

As the Standard _requires_ the memory allocated by calloc be nmemb
elements of size size, and zero all of it, I think a better
interpretation would be that non returning that [amount of memory] is
not compliant.

The issue FAQ 7.16 covers malloc, when the programmer makes the product,
not the internal function implementation as calloc.

[Spiros Bousbouras]

Chris Dollin wrote:

Spiros Bousbouras wrote:

Chris Dollin wrote:

Spiros Bousbouras wrote:

That's not what "onto" means. Just by virtue of the fact
that + and * are functions we know that for every pair
(a,b) there's going to be an image under + and an image
under * ie a+b and a*b are both going to be defined.

Functions don't have to be total: consider, for example,
division.

I think in recursion theory you may have a distinction
between total and non-total functions but in every other
branch of mathematics I've seen and certainly in algebra
you don't ; function means "total" function. In particular,
every textbook on set theory will tell you that a function
from a set A into a set B is a subset of AxB such that for
*every* a in A there is exactly one b in B such that (a,b) is
in f. Algebra uses the set-theoretic definition of a function.

Division.

Which operation do you mean by division ? If you
mean for example the usual a/b where a,b are real
numbers then it's not an operation in the formal
sense of the word although informally it may be called
such.

[Chris Dollin]

Spiros Bousbouras wrote:

Chris Dollin wrote:

>Spiros Bousbouras wrote:

Chris Dollin wrote:
Spiros Bousbouras wrote:

That's not what "onto" means. Just by virtue of the fact
that + and * are functions we know that for every pair
(a,b) there's going to be an image under + and an image
under * ie a+b and a*b are both going to be defined.

Functions don't have to be total: consider, for example,
division.

I think in recursion theory you may have a distinction
between total and non-total functions but in every other
branch of mathematics I've seen and certainly in algebra
you don't ; function means "total" function. In particular,
every textbook on set theory will tell you that a function
from a set A into a set B is a subset of AxB such that for
*every* a in A there is exactly one b in B such that (a,b) is
in f. Algebra uses the set-theoretic definition of a function.

Division.

Which operation do you mean by division ?

Integer division with remainder: "the usual" division, at
least in my head.

If you
mean for example the usual a/b where a,b are real
numbers then it's not an operation in the formal
sense of the word although informally it may be called
such.

Presumably it's not a formal operation because it's not
a total function.

--
Chris "electric hedgehog" Dollin
The "good old days" used to be much better.

[Chris Dollin]

Chris Dollin wrote:

Spiros Bousbouras wrote:

>Which operation do you mean by division ?

Integer division with remainder: "the usual" division, at
least in my head.

Grrr. /Without/ (discarding) remainder. (Otherwise the function is from
NxN -NxN rather than -N. Not that it matters if we're talking
totality, but staying in the spirit of algebra.)

(This is sufficiently offtopical to go to email, yes?)

--
Chris "electric hedgehog" Dollin
"I'm still here and I'm holding the answers" - Karnataka, /Love and Affection/

[Charlie Gordon]

"CBFalconer" <cb********@yahoo.coma écrit dans le message de news:
45***************@yahoo.com...

Jun Woong wrote:

>Harald van D©¦k wrote:

CBFalconer wrote:

[...]

>>>>
void *calloc(size_t n, size_t s) {
void *result;
size_t sz;

result = NULL;
if (SIZE_MAX / n < s) {

What if n == 0 ?

That should be

if (n == 0 || s == 0 || SIZE_MAX / n s) {

or something like that.

The version I have just put in nmalloc.c (not yet published) is:

/* calloc included here to ensure that it handles the
same range of sizes (s * n) as does malloc. The
multiplication n*s can wrap, yielding a too small
value, so we must ensure calloc rejects this.
*/
void *ncalloc(size_t n, size_t s)
{
void *result;
size_t sz;

result = NULL;
if (!n || ((size_t)-1) / n s) {
sz = n * s;
if ((result = nmalloc(sz))) memset(result, 0, sz);
}
return result;
} (* ncalloc *)

which makes the output of ncalloc be that of nmalloc(0) whenever
either n or s is 0. I think there is still a possible glitch when
((size_t)-1) / n) == s. The only thing that needs protection
agains n==0 is the division. s==0 will simply force sz==0.

As was pointed out later in this thread, >= is required to allow ncalloc(1,
SIZE_MAX). But IMHO it is more efficient to write this:

if (n <= 1 || SIZE_MAX / n >= s)

indeed, you should probably compare both arguments to 1 to avoid computing a
potentially costly division in the very common cases s==1 or n==1

if (n <= 1 || s <= 1 || SIZE_MAX / n >= s) ...

Whether it is more advisable to compute SIZE_MAX / n or SIZE_MAX / s is
debatable.

Another idea to avoid the division is to compare (n | s) to a value known to
be less than square root of SIZE_MAX, such as
(((size_t)1 << (CHAR_BIT * sizeof(size_t) / 2)) - 1) but that might not be
100% portable.

Chqrlie.

[David R Tribble]

Charlie Gordon wrote:

[...]
indeed, you should probably compare both arguments to 1 to avoid computing a
potentially costly division in the very common cases s==1 or n==1
if (n <= 1 || s <= 1 || SIZE_MAX / n >= s) ...
Whether it is more advisable to compute SIZE_MAX / n or SIZE_MAX / s is
debatable.

Another idea to avoid the division is to compare (n | s) to a value known to
be less than square root of SIZE_MAX, such as
(((size_t)1 << (CHAR_BIT * sizeof(size_t) / 2)) - 1) but that might not be
100% portable.

Yes, that's what I've been trying to remember for the last two days!

Basically, the width of n*s must be less than SIZE_MAX, which is
true only if the combined width of the significant (non-zero) bits of
both is less than sqrt(SIZE_MAX). No need to use 'long long'
arithmetic (which might be relatively expensive).

There is also the problem (not mentioned so far) of allowing for
the extra space required in the allocated block for bookkeeping
(typically consisting of a size_t and maybe a pointer to the next
block in the allocation pool). In other words, I doubt that
malloc(SIZE_MAX)
will work on most systems.

-drt

[Wojtek Lerch]

"David R Tribble" <da***@tribble.comwrote in message
news:11**********************@m58g2000cwm.googlegr oups.com...

Charlie Gordon wrote:

>[...]
Another idea to avoid the division is to compare (n | s) to a value known
to
be less than square root of SIZE_MAX, such as
(((size_t)1 << (CHAR_BIT * sizeof(size_t) / 2)) - 1) but that might not
be
100% portable.

I don't think so. It'll make calloc( 256, 1 ) fail on a system with
SIZE_MAX=65535.

Basically, the width of n*s must be less than SIZE_MAX, which is
true only if the combined width of the significant (non-zero) bits of
both is less than sqrt(SIZE_MAX). No need to use 'long long'
arithmetic (which might be relatively expensive).

Yes, if by "combined" you mean added, and by sqrt(SIZE_MAX) you mean the
width of size_t. It's a simple consequence of the mathematical fact that
log(n*s) == log(n) + log(s).

But is there an inexpensive way to compute the "width" of a given integer in
C?

[CBFalconer]

David R Tribble wrote:

>

.... snip ...

>
There is also the problem (not mentioned so far) of allowing for
the extra space required in the allocated block for bookkeeping
(typically consisting of a size_t and maybe a pointer to the next
block in the allocation pool). In other words, I doubt that
malloc(SIZE_MAX)
will work on most systems.

No problem. If the system can't do it, it returns NULL.

--
Some informative links:
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/ (taming google)
<http://members.fortunecity.com/nnqweb/ (newusers)

[David R Tribble]

David R Tribble wrote:

>Basically, the width of n*s must be less than SIZE_MAX, which is
true only if the combined width of the significant (non-zero) bits of
both is less than sqrt(SIZE_MAX). No need to use 'long long'
arithmetic (which might be relatively expensive).

Wojtek Lerch wrote:

Yes, if by "combined" you mean added, and by sqrt(SIZE_MAX) you mean the
width of size_t. It's a simple consequence of the mathematical fact that
log(n*s) == log(n) + log(s).

But is there an inexpensive way to compute the "width" of a given integer in C?

I think there may be a HAKMEM trick that sets all the bits below the
most significant 1 bit to zero, but I could not find it with a cursory
scan of
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
Something about or-ing an int with its two's-complement, or
something like that.

-drt

[Arthur J. O'Dwyer]

On Thu, 25 Jan 2007, David R Tribble wrote:

Wojtek Lerch wrote:

>But is there an inexpensive way to compute the "width" of a given
integer in C?

I think there may be a HAKMEM trick that sets all the bits below the
most significant 1 bit to zero, but I could not find it with a cursory
scan of
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
Something about or-ing an int with its two's-complement, or
something like that.

uintfoo_t x = (uintfoo_t)-1;
x ^= x>>1;

gets you the most significant bit of an unsigned type; that's easy.
But getting from "0x1000" to "16 bits" in constant time is tough
(in C; of course, some assembly languages give you that operation).
I think the answer to Wojtek's question is "No."

HTH,
-Arthur

[Ben Bacarisse]

"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrites:

On Thu, 25 Jan 2007, David R Tribble wrote:

>Wojtek Lerch wrote:

>>But is there an inexpensive way to compute the "width" of a given
integer in C?

I think there may be a HAKMEM trick that sets all the bits below the
most significant 1 bit to zero, but I could not find it with a cursory
scan of
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
Something about or-ing an int with its two's-complement, or
something like that.

uintfoo_t x = (uintfoo_t)-1;
x ^= x>>1;

gets you the most significant bit of an unsigned type; that's easy.
But getting from "0x1000" to "16 bits" in constant time is tough
(in C; of course, some assembly languages give you that operation).
I think the answer to Wojtek's question is "No."

Surely CHAR_BIT * sizeof unsigned int does it for unsigned integers?
There are problem with "non-value" bits (probably the wrong term) in
signed integer types, but the OP did not specify.

--
Ben.

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

Ben Bacarisse wrote:

"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrites:

On Thu, 25 Jan 2007, David R Tribble wrote:

Wojtek Lerch wrote:
But is there an inexpensive way to compute the "width" of a given
integer in C?

I think there may be a HAKMEM trick that sets all the bits below the
most significant 1 bit to zero, but I could not find it with a cursory
scan of
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
Something about or-ing an int with its two's-complement, or
something like that.

uintfoo_t x = (uintfoo_t)-1;
x ^= x>>1;

gets you the most significant bit of an unsigned type; that's easy.
But getting from "0x1000" to "16 bits" in constant time is tough
(in C; of course, some assembly languages give you that operation).
I think the answer to Wojtek's question is "No."

Surely CHAR_BIT * sizeof unsigned int does it for unsigned integers?
There are problem with "non-value" bits (probably the wrong term) in
signed integer types, but the OP did not specify.

Almost all signed and unsigned integer types may have padding bits.

[Ben Bacarisse]

"Harald van Dijk" <tr*****@gmail.comwrites:

Ben Bacarisse wrote:

>"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrites:

On Thu, 25 Jan 2007, David R Tribble wrote:
Wojtek Lerch wrote:
But is there an inexpensive way to compute the "width" of a given
integer in C?

I think there may be a HAKMEM trick that sets all the bits below the
most significant 1 bit to zero, but I could not find it with a cursory
scan of
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
Something about or-ing an int with its two's-complement, or
something like that.

uintfoo_t x = (uintfoo_t)-1;
x ^= x>>1;

gets you the most significant bit of an unsigned type; that's easy.
But getting from "0x1000" to "16 bits" in constant time is tough
(in C; of course, some assembly languages give you that operation).
I think the answer to Wojtek's question is "No."

Surely CHAR_BIT * sizeof unsigned int does it for unsigned integers?
There are problem with "non-value" bits (probably the wrong term) in
signed integer types, but the OP did not specify.

Almost all signed and unsigned integer types may have padding bits.

Ah, yes. You are, of course, quite right. It is trap representations
that unsigned types don't have.

It is possible to tell if an unsigned type has padding in O(1) time,
but one can't tell how many there are.

--
Ben.

[Wojtek Lerch]

"Ben Bacarisse" <be********@bsb.me.ukwrote in message
news:87************@bsb.me.uk...

"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrites:

>On Thu, 25 Jan 2007, David R Tribble wrote:

>>Wojtek Lerch wrote:
But is there an inexpensive way to compute the "width" of a given
integer in C?

I think the answer to Wojtek's question is "No."

Surely CHAR_BIT * sizeof unsigned int does it for unsigned integers?

I didn't mean the width of an integer type; when I said "width" (in quotes),
I was referring to what David Tribble described as the "width of the
significant (non-zero) bits" -- in other words, the minimum width (in the
normal sense) of a type capable of representing a given value. In other
words, I was looking for a formula that takes a positive integer value X and
produces W such that X >(W-1) == 1.

[Ben Bacarisse]

"Wojtek Lerch" <Wo******@yahoo.cawrites:

"Ben Bacarisse" <be********@bsb.me.ukwrote in message
news:87************@bsb.me.uk...

>"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrites:

>>On Thu, 25 Jan 2007, David R Tribble wrote:
Wojtek Lerch wrote:
But is there an inexpensive way to compute the "width" of a given
integer in C?
I think the answer to Wojtek's question is "No."

Surely CHAR_BIT * sizeof unsigned int does it for unsigned integers?

I didn't mean the width of an integer type; when I said "width" (in
quotes), I was referring to what David Tribble described as the "width
of the significant (non-zero) bits" -- in other words, the minimum
width (in the normal sense) of a type capable of representing a given
value. In other words, I was looking for a formula that takes a
positive integer value X and produces W such that X >(W-1) == 1.

Sorry, I was not paying attention. I offer this in compensation,
although if you like bit-fiddling you will hate it:

For X != 0, ilogb((double)(unsigned int)X) + 1 does what you want, I
think. Those who know hardware can say how many thousand cycles
converting to double will cost. The ilogb is probably fast, though!

--
Ben.

[CBFalconer]

Wojtek Lerch wrote:

"Ben Bacarisse" <be********@bsb.me.ukwrote in message

>"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrites:

>>Wojtek Lerch wrote:

>>>But is there an inexpensive way to compute the "width" of a
given integer in C?

>>I think the answer to Wojtek's question is "No."

Surely CHAR_BIT * sizeof unsigned int does it for unsigned
integers?

I didn't mean the width of an integer type; when I said "width"
(in quotes), I was referring to what David Tribble described as
the "width of the significant (non-zero) bits" -- in other words,
the minimum width (in the normal sense) of a type capable of
representing a given value. In other words, I was looking for a
formula that takes a positive integer value X and produces W such
that X >(W-1) == 1.

I think rounding up log2 covers it.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

[Wojtek Lerch]

"CBFalconer" <cb********@yahoo.comwrote in message
news:45**************@yahoo.com...

Wojtek Lerch wrote:

>>>Wojtek Lerch wrote:

>>>>But is there an inexpensive way to compute the "width" of a
given integer in C?

>[...] In other words, I was looking for a
formula that takes a positive integer value X and produces W such
that X >(W-1) == 1.

I think rounding up log2 covers it.

Is it likely to be less expensive than an integer division?

[Keith Thompson]

Ben Bacarisse <be********@bsb.me.ukwrites:

"Harald van Dþÿ
3k" <tr*****@gmail.comwrites:

[...]

Almost all signed and unsigned integer types may have padding bits.

Ah, yes. You are, of course, quite right. It is trap representations
that unsigned types don't have.

I'm fairly sure unsigned types (other than unsigned char) can have
trap representations.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Ben Bacarisse]

Keith Thompson <ks***@mib.orgwrites:

Ben Bacarisse <[e-mail]:

>"Harald van Dþÿ 3k" <[e-mail]:

[...]

Almost all signed and unsigned integer types may have padding bits.

>Ah, yes. You are, of course, quite right. It is trap representations
that unsigned types don't have.

I'm fairly sure unsigned types (other than unsigned char) can have
trap representations.

Sigh. Yes. I was mis-remembering the fact that trap representations
can't result from valid operations on valid unsigned values and it
came out as the erroneous statement above. I'll shut up now.

[BTW, your post presented un-surmountable obstacles to my news reader
(despite its similarity to yours) so I had to read in Google groups
and paste your message into this reply. I hope I have not
misrepresented anything in the process.]

--
Ben.

[Keith Thompson]

Ben Bacarisse <be********@bsb.me.ukwrites:
[...]

[BTW, your post presented un-surmountable obstacles to my news reader
(despite its similarity to yours) so I had to read in Google groups
and paste your message into this reply. I hope I have not
misrepresented anything in the process.]

Yes, it showed up as a bunch of '?' characters in mine, but some
people apparently were able to read it anyway.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Ian Collins]

Keith Thompson wrote:

Ben Bacarisse <be********@bsb.me.ukwrites:
[...]

>>[BTW, your post presented un-surmountable obstacles to my news reader
(despite its similarity to yours) so I had to read in Google groups
and paste your message into this reply. I hope I have not
misrepresented anything in the process.]

Yes, it showed up as a bunch of '?' characters in mine, but some
people apparently were able to read it anyway.

For some reason, you managed to post with charset=utf-16be!

--
Ian Collins.

[Richard Tobin]

In article <51*************@mid.individual.net>,
Ian Collins <ia******@hotmail.comwrote:

>Yes, it showed up as a bunch of '?' characters in mine, but some
people apparently were able to read it anyway.

>For some reason, you managed to post with charset=utf-16be!

The post was labelled that, but was in fact mostly in ascii, so
old-fashioned newsreaders that don't understand mime had no problem.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.