16-Bit char pointers valid?

[Frederick Gotham]

I think someone posted elsewhere on the group that we must be able to
address at least 65 535 bytes in C... ? (Or something along those lines).

A 16-Bit unsigned integer type has 65 536 unique values. If our char
pointer is 16-Bit, then it too can contain 65 536 unique values. Take
away 1 for the null pointer value, and we have 65 535 unique byte
addresses.

So, at first glance, it looks like a 16-Bit char pointer is just about
sufficient to satisfy C's need for 65 535 bytes.

However, adding to the debate about:

char buffer[64];

const char * const p_null = 0;
const char * const p_over = buffer + 64;

assert( p_null == p_over );
If, hypothetically speaking, the pointer to "one past last" could NOT be
equal to the null pointer, then the addresses would have to be
distributed something like the following:

0x0000 to 0xFFFD inclusive : Valid byte addresses
0xFFFE : Pointer to "one past last"
0xFFFF : Null pointer value

The problem with this, however, is that 0x0000 to 0xFFFD inclusive
constitutes only 65 534 unique addresses... and this seems to not satisfy
C's need for 65 535 bytes.

So it seems to me that if p_over can't be equal to p_null, then char*
must be at least 17-Bit.

Any thoughts?

[Gordon Burditt]

>I think someone posted elsewhere on the group that we must be able to

address at least 65 535 bytes in C... ? (Or something along those lines).
Addressing at least 65,535 bytes doesn't have to mean having an array
that large.
A 16-Bit unsigned integer type has 65 536 unique values. If our char
pointer is 16-Bit, then it too can contain 65 536 unique values. Take
away 1 for the null pointer value, and we have 65 535 unique byte
addresses.

So, at first glance, it looks like a 16-Bit char pointer is just about
sufficient to satisfy C's need for 65 535 bytes.

However, adding to the debate about:

char buffer[64];

const char * const p_null = 0;
const char * const p_over = buffer + 64;

assert( p_null == p_over );
If, hypothetically speaking, the pointer to "one past last" could NOT be
equal to the null pointer, then the addresses would have to be
distributed something like the following:

0x0000 to 0xFFFD inclusive : Valid byte addresses
0xFFFE : Pointer to "one past last"
0xFFFF : Null pointer value

The problem with this, however, is that 0x0000 to 0xFFFD inclusive
constitutes only 65 534 unique addresses... and this seems to not satisfy
C's need for 65 535 bytes.
0xfffe addresses a byte distinct from all the other bytes
you mentioned.
So it seems to me that if p_over can't be equal to p_null, then char*
must be at least 17-Bit.

I disagree. p_over addresses a byte. You can't use the byte but
you can still address it.

Gordon L. Burditt

[Harald van Dijk]

Gordon Burditt wrote:

I think someone posted elsewhere on the group that we must be able to
address at least 65 535 bytes in C... ? (Or something along those lines).

Addressing at least 65,535 bytes doesn't have to mean having an array
that large.

"65535 bytes in an object" when every object can be accessed as an
array of (unsigned) char does mean having an array that large.

(Disclaimer repeated: there is a strict reading of the standard that
disagrees with this, but using that reading, no implementation, hosted
or otherwise, is required to accept even a single strictly conforming
program, which is clearly ridiculous.)

[Keith Thompson]

Frederick Gotham <fg*******@SPAM.com> writes:

I think someone posted elsewhere on the group that we must be able to
address at least 65 535 bytes in C... ? (Or something along those lines).
The actual requirement is (C99 5.2.4.1):

The implementation shall be able to translate and execute at least
one program that contains at least one instance of every one of
the following limits:

...

65535 bytes in an object (in a hosted environment only)
A 16-Bit unsigned integer type has 65 536 unique values. If our char
pointer is 16-Bit, then it too can contain 65 536 unique values. Take
away 1 for the null pointer value, and we have 65 535 unique byte
addresses.
Right.
So, at first glance, it looks like a 16-Bit char pointer is just about
sufficient to satisfy C's need for 65 535 bytes.

However, adding to the debate about:

char buffer[64];

const char * const p_null = 0;
const char * const p_over = buffer + 64;

assert( p_null == p_over );
If, hypothetically speaking, the pointer to "one past last" could NOT be
equal to the null pointer, then the addresses would have to be
distributed something like the following:

0x0000 to 0xFFFD inclusive : Valid byte addresses
0xFFFE : Pointer to "one past last"
0xFFFF : Null pointer value

The problem with this, however, is that 0x0000 to 0xFFFD inclusive
constitutes only 65 534 unique addresses... and this seems to not satisfy
C's need for 65 535 bytes.

So it seems to me that if p_over can't be equal to p_null, then char*
must be at least 17-Bit.

Yes, if a pointer just past the end of an array cannot be null, then
you need at least 17 bits for char*.

Even if it can be null, that single object plus the null pointer takes
up all 65536 possible char* values; no other objects can exist in the
program. The single program also has to have, among other things,
4095 characters in a string literal; each character in the literal has
to have a unique address. Conceivably an implementation could cheat
if the address isn't actually used, but I don't believe an
implementation could *usefully* satisfy 5.2.4.1 with 16-bit pointers.

Note that the C90 requirement was 32768 bytes, so a conforming hosted
C90 implementation could probably get away with using 16-bit pointers
(though I don't know of any that do so).

--
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.

[pete]

Keith Thompson wrote:

Note that the C90 requirement was 32768 bytes, so a conforming hosted
C90 implementation could probably get away with using 16-bit pointers
(though I don't know of any that do so).

I have the impression that they were thinking
of 16 bit ptrdiff_t, when they wrote that requirement.

--
pete

[Richard Heathfield]

Keith Thompson said:

Note that the C90 requirement was 32768 bytes

32767.

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

[Keith Thompson]

Richard Heathfield <in*****@invalid.invalid> writes:

Keith Thompson said:

Note that the C90 requirement was 32768 bytes

32767.

Obviously I was expressing the number in base 9.99992154311217.

Sheesh!

--
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.

[Harald van Dijk]

Keith Thompson wrote:

Frederick Gotham <fg*******@SPAM.com> writes:

I think someone posted elsewhere on the group that we must be able to
address at least 65 535 bytes in C... ? (Or something along those lines).

The actual requirement is (C99 5.2.4.1):

The implementation shall be able to translate and execute at least
one program that contains at least one instance of every one of
the following limits:

...

65535 bytes in an object (in a hosted environment only)

A 16-Bit unsigned integer type has 65 536 unique values. If our char
pointer is 16-Bit, then it too can contain 65 536 unique values. Take
away 1 for the null pointer value, and we have 65 535 unique byte
addresses.

Right.

So, at first glance, it looks like a 16-Bit char pointer is just about
sufficient to satisfy C's need for 65 535 bytes.

However, adding to the debate about:

char buffer[64];

const char * const p_null = 0;
const char * const p_over = buffer + 64;

assert( p_null == p_over );
If, hypothetically speaking, the pointer to "one past last" could NOT be
equal to the null pointer, then the addresses would have to be
distributed something like the following:

0x0000 to 0xFFFD inclusive : Valid byte addresses
0xFFFE : Pointer to "one past last"
0xFFFF : Null pointer value

The problem with this, however, is that 0x0000 to 0xFFFD inclusive
constitutes only 65 534 unique addresses... and this seems to not satisfy
C's need for 65 535 bytes.

So it seems to me that if p_over can't be equal to p_null, then char*
must be at least 17-Bit.

Yes, if a pointer just past the end of an array cannot be null, then
you need at least 17 bits for char*.

Even if it can be null, that single object plus the null pointer takes
up all 65536 possible char* values; no other objects can exist in the
program. The single program also has to have, among other things,
4095 characters in a string literal; each character in the literal has
to have a unique address. Conceivably an implementation could cheat
if the address isn't actually used, but I don't believe an
implementation could *usefully* satisfy 5.2.4.1 with 16-bit pointers.

A string literal can be used in the initialiser for the object of 65535
bytes, if it is an array of char, or is a struct containing such an
array. This does not require cheating, and does not require more than
65536 distinct pointer values.

[Keith Thompson]

"Harald van Dijk" <tr*****@gmail.com> writes:

Keith Thompson wrote:

[...]

Yes, if a pointer just past the end of an array cannot be null, then
you need at least 17 bits for char*.

Even if it can be null, that single object plus the null pointer takes
up all 65536 possible char* values; no other objects can exist in the
program. The single program also has to have, among other things,
4095 characters in a string literal; each character in the literal has
to have a unique address. Conceivably an implementation could cheat
if the address isn't actually used, but I don't believe an
implementation could *usefully* satisfy 5.2.4.1 with 16-bit pointers.

A string literal can be used in the initialiser for the object of 65535
bytes, if it is an array of char, or is a struct containing such an
array. This does not require cheating, and does not require more than
65536 distinct pointer values.

5.2.4.1 also requires 127 parameters in one function definition and
127 arguments in one function call. Each parameter needs a distinct
address if the function is called.

It still *might* be possible to conform with 16-bit pointers, but it
would be a serious challenge, and hardly worth the effort (unless you
want to submit the first entry to an International Obfuscated C
Compiler Contest).

--
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.

[Harald van Dijk]

Keith Thompson wrote:

"Harald van Dijk" <tr*****@gmail.com> writes:

Keith Thompson wrote: [...]

Yes, if a pointer just past the end of an array cannot be null, then
you need at least 17 bits for char*.

Even if it can be null, that single object plus the null pointer takes
up all 65536 possible char* values; no other objects can exist in the
program. The single program also has to have, among other things,
4095 characters in a string literal; each character in the literal has
to have a unique address. Conceivably an implementation could cheat
if the address isn't actually used, but I don't believe an
implementation could *usefully* satisfy 5.2.4.1 with 16-bit pointers.

A string literal can be used in the initialiser for the object of 65535
bytes, if it is an array of char, or is a struct containing such an
array. This does not require cheating, and does not require more than
65536 distinct pointer values.

5.2.4.1 also requires 127 parameters in one function definition and
127 arguments in one function call. Each parameter needs a distinct
address if the function is called.

I thought that wasn't necessary if they could be declared with
"register", but I now realise that would apply to the 65535 bytes as
well. There are some other ways around this, but I think they all rely
on compiler extensions, which (to me) makes them cheats.
It still *might* be possible to conform with 16-bit pointers, but it
would be a serious challenge, and hardly worth the effort (unless you
want to submit the first entry to an International Obfuscated C
Compiler Contest).

Definitely not worth the effort if the implementation can simply be
called a freestanding one, which happens to support most of what is
required of hosted implementations.