size of a pointer on 4-bit system

[Ben Bacarisse]

On 2/1/13 5:41 AM, BartC wrote:


The sizeof operator can be defined in a way that satisfies all
the Standard's requirements but still allows this example to
allocate only 100 nibbles.

So what would be the value of sizeof(*x)? It can only really
be 1 or 0. [snip elaboration]

Actually that isn't right. Using 'sizeof' on a non-standard
datatype may behave in unexpected ways. Here's a hint: sizeof
yields a result of type size_t; size_t is an (unsigned) integer
type; integer types larger than character types may have padding
bits. Can you fill in the rest?

What, that extra information is stored in those padding bits? How is
that going to help?

What bit-pattern could be returned by sizeof(*x) that would make
100*sizeof(*x) yield 50 instead of 100?

one simple solution is to have the sizeof operator not return a size_t
for the nybble type, but some special type that does math "funny" to get
the right value, for example a fixed point type with 1 fractional bit.
When doing arithmetic on this type, the compiler can get the "right"
answer, and also do the right thing when converting it to a standard
type.

I don't see how that can be permitted, at least without twisting
things some more! The type of a sizeof expression is size_t (an
unsigned integer type) and the result must be "an integer".

Here's another way of looking at it that may help. Using sizeof
is supposed to give the size of its operand in bytes. For a
four-bit data type, that should be a number strictly between
zero and one. Under 6.5 p5, such a circumstance qualifies as an
exceptional condition and therefore is undefined behavior.

[The thread has become split and I don't want to say essentially the
same things in two places so I'll just reply here.]

The source of the UB is immaterial to my complaint, which should really
be directed at myself: I should have known better! Given the nature of
UB, the first part of your teaser:

"The sizeof operator can be defined in a way that satisfies all the
Standard's requirements"

is essentially meaningless. Of course we can satisfy all the standard
requirements for undefined behaviour -- there are none!

I thought you meant more than that. I thought you meant more than "it
can be made to work".

I was meaning to say something stronger, or at least how I think
of it is stronger.

Yes, I know. But to be clear my remark was to Richard Damon who might
have been suggesting (I was not sure -- hence the interrogative) a more
global kind of undefined behaviour as a way of dealing with what he saw
as a problematic case (the two examples above). It seems from other
posts that he was not going there, but was,like you, imagining a more
localised UB.

There is local undefined behavior at sizeof,
because of the exceptional condition, and another local undefined
behavior for a size_t with non-zero fraction bits. However, once
these two local undefined behaviors are defined, everything else
proceeds definedly (not counting things like pointers to the new
type, etc, which also have to be defined, but I think you get the
idea). The presence of undefined behavior is repaired purely
locally by defining the semantics for these two specific cases, and
otherwise has no effect (again assuming that other aspects have
been defined suitably).

Absolutely. I saw no problem with making it work, and having extra bits
available allows the problem of returning a non-standard value to be
contained, as it were. (My thought was to imagine a type-tagged memory
architecture which is just fancy padding bits by another name.)

 

[Tim Rentsch]

On 2/1/13 5:41 AM, BartC wrote:


The sizeof operator can be defined in a way that satisfies all
the Standard's requirements but still allows this example to
allocate only 100 nibbles.

So what would be the value of sizeof(*x)? It can only really
be 1 or 0. [snip elaboration]

Actually that isn't right. Using 'sizeof' on a non-standard
datatype may behave in unexpected ways. Here's a hint: sizeof
yields a result of type size_t; size_t is an (unsigned) integer
type; integer types larger than character types may have padding
bits. Can you fill in the rest?

What, that extra information is stored in those padding bits? How is
that going to help?

What bit-pattern could be returned by sizeof(*x) that would make
100*sizeof(*x) yield 50 instead of 100?

one simple solution is to have the sizeof operator not return a size_t
for the nybble type, but some special type that does math "funny" to get
the right value, for example a fixed point type with 1 fractional bit.
When doing arithmetic on this type, the compiler can get the "right"
answer, and also do the right thing when converting it to a standard
type.

I don't see how that can be permitted, at least without twisting
things some more! The type of a sizeof expression is size_t (an
unsigned integer type) and the result must be "an integer".

Here's another way of looking at it that may help. Using sizeof
is supposed to give the size of its operand in bytes. For a
four-bit data type, that should be a number strictly between
zero and one. Under 6.5 p5, such a circumstance qualifies as an
exceptional condition and therefore is undefined behavior.

[The thread has become split and I don't want to say essentially the
same things in two places so I'll just reply here.]

The source of the UB is immaterial to my complaint, which should really
be directed at myself: I should have known better! Given the nature of
UB, the first part of your teaser:

"The sizeof operator can be defined in a way that satisfies all the
Standard's requirements"

is essentially meaningless. Of course we can satisfy all the standard
requirements for undefined behaviour -- there are none!

I thought you meant more than that. I thought you meant more than
"it can be made to work". [snip subsequent parts]

What I found confusing was you not understanding what it was I
was trying to say. Or, perhaps better, the context in which my
remarks were expressed. I thought for a long time in writing
just one paragraph in my response to your other posting, trying
to figure out what your meta-model is for how you read and what
you wrote. It was baffling. Still is, I am sorry to say.

As for my statement being meaningless, I don't think it is. If I
may offer an analogy, consider the relationship between factorial
and the gamma function (shifted by one so they align on integers).
The gamma function can be seen as an extension of factorial.
Saying that means more than just the two functions matching where
factorial is defined. Similarly, the extended definition of
sizeof satisfies both what sizeof must do on standard types, and
smoothly extends that to cover types like nibble, without changing
the interpretation at all for how standard types work. How size_t
is represented, or what kind of type it is, or what type is
produced by sizeof -- none of those things change when types like
nibble enter the picture. That there is a simple, single
definition of sizeof and size_t that does both jobs -- conforms to
the letter of the Standard for standard types, and behaves as
people may expect for non-standard types -- is a noteworthy
statement. Based on the responses I think it's fair to say at
least some other people saw this meaning in my earlier statement.
Is your interpretation right and theirs wrong? Or is there more
than one reasonable interpretation?

 

[glen herrmannsfeldt]

(snip)

I am not sure that a fractional type meets the requirements for size_t.
The problem is that size_t is defined as an "unsigned integral type",
and math on such types is well defined and does not allow for fractional
bits. This is why I was proposing that sizeof needs to return something
besides size_t for the _Nybble type.
(snip)

Making the conversion of the _Size_t type to size_t, when the conversion
isn't exact, generate a warning could at least help locate problematical
cases, and perhaps let you change the declaration to _Size_t. Note that
your second case, while it allocates too much space, will at least run
properly, even if it will be wasteful.

I think that it is better that the way this is implemented keeps
conforming code correct. Since sizeof(char)/2 MUST be 0 by the rules of
Standard C, size_t can not hold fractional bits.

It seems to be well understood that high bits of pointers can be
used on word addressable machines to indicate bytes within words.

I believe it was mentioned earlier that high bits of sizeof()
and size_t could be used. I don't know that it is possible to
make it work, but that might be one of the things suggested.

Seems to me that if all the usual cases work, and if the new
cases (with nybble) also work, then it should be fine.

-- glen

 

[David Thompson]

glen herrmannsfeldt wrote:

Many, starting with the PDP-11's, today's Atmel AVR's, etc.

Nit: *some* PDP-11s. Higher-end models had separate "instruction" and
"data" spaces, and 3 privilege levels; middle had combined-I&D and 2
levels; original and later cheapest models had no memory management
and only 1 (implicit) privilege level.

 

[BartC]

It seems to be well understood that high bits of pointers can be
used on word addressable machines to indicate bytes within words.

Sometimes, unless the hardware reserves them or requires them to be a
certain pattern.

But with 32-bits, there *are* no spare bits! Maybe with 64-bit pointers (and
the manipulation done by software), but remember this thread started by
talking about 4-bit systems!

I believe it was mentioned earlier that high bits of sizeof()
and size_t could be used. I don't know that it is possible to
make it work, but that might be one of the things suggested.

size_t is a standard integer format. To make use of the high bits, you would
lose unacceptable range in a 32-bit type. And both 32/64-bit integers would
need lots of bit-twiddling to the do the simplest operation. While having
what in reality would be 29/61-bit integers would just be too odd! (For
4-bits, you could have 31/63-bit integers, but you're not going to go to all
this trouble, and not have a Bit type as well.)

Seems to me that if all the usual cases work, and if the new
cases (with nybble) also work, then it should be fine.

Someone should try it then! I've implemented 1-, 2- and 4-bit types in a
language, and they were enough different that they needed their own
dedicated handling compared with byte-multiple/byte-aligned scalars, rather
than try and shoe-horn them in by introducing new tagged integer types,
which are even more trouble to deal with that the bit-types!

 

[James Kuyper]

Sometimes, unless the hardware reserves them or requires them to be a
certain pattern.

But with 32-bits, there *are* no spare bits!

Whether or not there are any spare bits depends upon both the size of
the pointer and the size of the memory addressed by them; you cannot
determine that there are no spare bits, just by looking at the number of
bits.

size_t is a standard integer format. To make use of the high bits, you would
lose unacceptable range in a 32-bit type.

Again, whether or not it's unacceptable depends upon the context. On a
machine where no object can have as many as 2^30 bytes, the loss of
range caused by using the two highest bits for something else would be
perfectly acceptable.

 

[BartC]

On 02/04/2013 08:30 AM, BartC wrote:

Again, whether or not it's unacceptable depends upon the context. On a
machine where no object can have as many as 2^30 bytes, the loss of
range caused by using the two highest bits for something else would be
perfectly acceptable.

Any machine with that amount of memory would quite likely want to be able to
address 4GB rather than be limited to 1or 2GB. I think people would want a
better reason for limiting scalability of a system than just the need to
have nibble types in a language! (Which can be reasonably handled by
other means without too much trouble, even without language extensions.)

So I'd prefer a solution which doesn't impact the normal capabilities of the
hardware and language.

 

[Keith Thompson]

Sometimes, unless the hardware reserves them or requires them to be a
certain pattern.

But with 32-bits, there *are* no spare bits! Maybe with 64-bit pointers (and
the manipulation done by software), but remember this thread started by
talking about 4-bit systems!

It's unlikely that a 4-bit system would be able to address 4 gigabytes
(or even 4 giganybbles) of either virtual or physical memory. If you're
designing a system with that big an address space, you're probably going
to use at least a 16-bit processor.

size_t is a standard integer format. To make use of the high bits, you would
lose unacceptable range in a 32-bit type. And both 32/64-bit integers would
need lots of bit-twiddling to the do the simplest operation. While having
what in reality would be 29/61-bit integers would just be too odd! (For
4-bits, you could have 31/63-bit integers, but you're not going to go to all
this trouble, and not have a Bit type as well.)

It's plausible that our 4-bit system could easily address 4-bit nybbles,
but not individual bits. For bits, you could use bit fields or bitwise
operators, just as we do on less exotic systems.

size_t is (a typedef for) some predefined integer type. The standard
gives considerable latitude for how it's represented. It needn't be any
of the language-defined types; those could have more conventional
representations, and whatever size_t is defined to be could have
"padding bits".

[...]

 

[Keith Thompson]

I am not sure that a fractional type meets the requirements for size_t.
The problem is that size_t is defined as an "unsigned integral type",
and math on such types is well defined and does not allow for fractional
bits. This is why I was proposing that sizeof needs to return something
besides size_t for the _Nybble type.

The extra bits would be padding bits as far as any language-defined
operations are concerned. Arithmetic operations would happen to set
those bits consistently, but you wouldn't be able to access them other
than by performing undefined, or at least unspecified, operations.

For example, `(size_t)1 / 2` would yield a result that would compare
equal to 0, but if you look at the padding bits of the result and
interpret them as fractional bits, you can interpret it as 1/2
(a value midway between 0 and 1).

 

[James Kuyper]

Any machine with that amount of memory would quite likely want to be able to
address 4GB rather than be limited to 1or 2GB. ...

A system might use 32-bit pointers even if it has as few 65536 bytes of
addressable memory (though it's far more plausible if it has somewhat
more than that, say 4 MB). It needn't have anywhere near to 1GB of memory.

 

[Keith Thompson]

The sizeof operator can be defined in a way that satisfies all
the Standard's requirements but still allows this example to
allocate only 100 nibbles.

So what would be the value of sizeof(*x)? It can only really
be 1 or 0. [snip elaboration]

Actually that isn't right. Using 'sizeof' on a non-standard
datatype may behave in unexpected ways. Here's a hint: sizeof
yields a result of type size_t; size_t is an (unsigned) integer
type; integer types larger than character types may have padding
bits. Can you fill in the rest?

What, that extra information is stored in those padding bits? How is
that going to help?

What bit-pattern could be returned by sizeof(*x) that would make
100*sizeof(*x) yield 50 instead of 100?

one simple solution is to have the sizeof operator not return a
size_t for the nybble type, but some special type that does math
"funny" to get the right value, for example a fixed point type
with 1 fractional bit. When doing arithmetic on this type, the
compiler can get the "right" answer, and also do the right thing
when converting it to a standard type.

This is basically the idea, except the result isn't a new type
but is always a size_t. The key insight is that size_t can be
what is in effect a fixed-point type (with three fraction bits,
for example), but still satisfy the requirements for being an
integer type by designating the fraction bits as "padding bits".
Any combination of fraction bits other than all zeroes would be
a trap representation, allowing both standard behavior and
extended behavior in the same data type (ie, size_t).

[...]

It's an interesting idea, if your goal is to have a completely
conforming C (C11, I suppose) implementation for a 4-bit system
in which you can write programs that can deal naturally with 4-bit
objects, and arrays of 4-bit objects. I think that making size_t a
kind of hybrid type, with extra bits that are padding bits as far
as any strictly conforming code is concerned, but fraction bits
for implementation-specific code, *could* achieve that goal.

But in real life, I think the *real* goal would be to create a
useful software development environment for the target 4-bit system,
and I don't think a conforming C implementation would be the best
solution. It's quite possible that such a system would be so tiny
that nothing above the level of assembly language would be worth
the effort. Or perhaps it would make sense to implement a C-like
language that violates the standard by setting CHAR_BIT==4, and/or
by decoupling the idea of the smallest addressible storage unit from
character types. Perhaps it wouldn't support floating-point either.
I think the result would be easier to implement, and less confusing
to programmers, than the conforming C with 4-bit extensions that
you propose.

One of C's great strengths is the ability to write code that's
portable across all conforming C implementations. Any code written
for a 4-bit system would likely be intended *only* for that system.

(If C hadn't conflated addressible storage units with characters,
we could have an implementation with genuine 4-bit types, and
sizeof(char) could consistently be 2. But it's too late for that.)

 

[glen herrmannsfeldt]

On Wed, 30 Jan 2013 15:47:35 -0500, Roberto Waltman

Nit: *some* PDP-11s. Higher-end models had separate "instruction" and
"data" spaces, and 3 privilege levels; middle had combined-I&D and 2
levels; original and later cheapest models had no memory management
and only 1 (implicit) privilege level.

As well as I understand it, for the PDP-11 that is separate virtual
address space, but a single physical address space.

At the time, I was thinking about processors like the 8048 that
have separate physical (usually ROM) address space for code,
and RAM for data. There is a way to load data from code
(ROM) address space, but no way to store, and no way to
execute instructions from data (RAM) address space.

But yes, for a user space program, C compiler or compiled
code, running on a PDP-11 under RSX-11, the separate address
spaces would matter.

Most of my PDP-11 work has been under RT11SJ where that doesn't
come up. Does the PDP-11 in separate I/D mode have a way to
load data (look-up tables) from I space?

-- glen

 

[Roberto Waltman]

As well as I understand it, for the PDP-11 that is separate virtual
address space, but a single physical address space.

Correct, and maybe it should not be called a "true" Harvard
architecture, since with a single physical bus there is no parallelism
between code and data access.

Most of my PDP-11 work has been under RT11SJ where that doesn't
come up. Does the PDP-11 in separate I/D mode have a way to
load data (look-up tables) from I space?

Yes - "Move to/from previous data/instruction space"
I don't recall if these were "privileged" (system mode only)
instructions.

 

[Tim Rentsch]

The extra bits would be padding bits as far as any language-defined
operations are concerned. Arithmetic operations would happen to
set those bits consistently, but you wouldn't be able to access
them other than by performing undefined, or at least unspecified,
operations.

For example, `(size_t)1 / 2` would yield a result that would
compare equal to 0, but if you look at the padding bits of the
result and interpret them as fractional bits, you can interpret
it as 1/2 (a value midway between 0 and 1).

If you think about this a little while I expect you'll see that
expressions like (size_t)1 / 2 must not set any "fraction" bits.
This expression is well-defined by the Standard - it must behave
exactly like 0 in all respects for all subsequent operations (ie,
operations whose behavior is defined by the Standard). The only
value operations that produce size_t representations with non-zero
fractions must have an element of undefined behavior, or possibly
implementation-defined behavior. This expression is completely
defined so it mustn't do that.

 

[Tim Rentsch]

[re implementing 4-bit wide data types, sizeof, size_t, etc]

one simple solution is to have the sizeof operator not return a
size_t for the nybble type, but some special type that does math
"funny" to get the right value, for example a fixed point type
with 1 fractional bit. When doing arithmetic on this type, the
compiler can get the "right" answer, and also do the right thing
when converting it to a standard type.

This is basically the idea, except the result isn't a new type
but is always a size_t. The key insight is that size_t can be
what is in effect a fixed-point type (with three fraction bits,
for example), but still satisfy the requirements for being an
integer type by designating the fraction bits as "padding bits".
Any combination of fraction bits other than all zeroes would be
a trap representation, allowing both standard behavior and
extended behavior in the same data type (ie, size_t).

[...]

It's an interesting idea, if your goal is to have a completely
conforming C (C11, I suppose) implementation for a 4-bit system
in which you can write programs that can deal naturally with 4-bit
objects, and arrays of 4-bit objects. I think that making size_t a
kind of hybrid type, with extra bits that are padding bits as far
as any strictly conforming code is concerned, but fraction bits
for implementation-specific code, *could* achieve that goal.

But in real life, I think the *real* goal would be to create a
useful software development environment for the target 4-bit system,
and I don't think a conforming C implementation would be the best
solution. [snip elaboration]

Two comments.

One, the point of this scheme is to support addressing, and
especially arrays, for data types narrower than 8 bits. That
might be a machine with a 4-bit wide data path and/or ALU's, but
it doesn't have to be. It could be a typical large cpu of today,
and even one that doesn't natively support sub-byte addressing.
For example, it could be provided on x86 cpus. What I think is
interesting is that this capability could be provided in a way
that fits in quite neatly with Standard C.

Two, as far as small 4-bit systems go, I think the main holdup
for using standard C is the minimum width of certain data types.
An implementation with char, short, and int being 8 bits, and
long/size_t being 15 bits (plus 1 padding/fraction bit), and
long long being 16 bits, but otherwise conforming (and presumably
extended with some 4-bit data types) is probably small enough to
be usable at the same time as being close enough to regular C
so that switching between the two languages could be done fairly
easily. A lot of small programs would just work with no changes
needed.

 

[Tim Rentsch]

This is basically the idea, except the result isn't a new type
but is always a size_t. The key insight is that size_t can be
what is in effect a fixed-point type (with three fraction bits,
for example), but still satisfy the requirements for being an
integer type by designating the fraction bits as "padding bits".
Any combination of fraction bits other than all zeroes would be
a trap representation, allowing both standard behavior and
extended behavior in the same data type (ie, size_t).

I am not sure that a fractional type meets the requirements for
size_t. The problem is that size_t is defined as an "unsigned
integral type", and math on such types is well defined and does
not allow for fractional bits. [snip]

What I am suggesting is not a pure fixed-point type but a kind of
combination. Any operation on operand values whose fraction bits
are zero produces the same result as the corresponding integer
operation would (and specifically the fraction bits of the result
would be zero). This approach ensures the size_t type will meet
the Standard's requirements for an integer type.

Making the conversion of the _Size_t type to size_t, when the
conversion isn't exact, generate a warning could at least help
locate problematical cases, and perhaps let you change the
declaration to _Size_t. Note that your second case, while it
allocates too much space, will at least run properly, even if it
will be wasteful.

I don't like introducing another type because it increases the
distance between the extended language and Standard C. And I
really don't like the idea of having to use a non-standard type
when a standard type could do the job.

Re: calloc() and space allocation - the problem is sometimes the
space allocated would be too large by a factor of two!

I think that it is better that the way this is implemented keeps
conforming code correct. Since sizeof(char)/2 MUST be 0 by the
rules of Standard C, size_t can not hold fractional bits.

I think you're assuming that all operations on size_t values
would behave as the corresponding fixed-point operations would,
eg, sizeof(char)/2 would be 0.5. That isn't what I'm suggesting.
All operations on size_t values whose fraction bits are zero
would produce the same results as the corresponding operations
on integer values.

 

[Keith Thompson]

If you think about this a little while I expect you'll see that
expressions like (size_t)1 / 2 must not set any "fraction" bits.
This expression is well-defined by the Standard - it must behave
exactly like 0 in all respects for all subsequent operations (ie,
operations whose behavior is defined by the Standard). The only
value operations that produce size_t representations with non-zero
fractions must have an element of undefined behavior, or possibly
implementation-defined behavior. This expression is completely
defined so it mustn't do that.

Hmm.

There can be representations for an integer 0 other than all-bits-zero,
so I'm not sure that having `(size_t)1 / 2` set some of the
padding/fraction bits to 1 would be forbidden. But certainly
`(size_t)1 / 2 * 2` must be 0.

On the other hand, we'd want `sizeof (_Nybble[2])` to denote 1
8-bit byte, and `sizeof (_Nybble[2]) / 2` to denote 1 4-bit nybble.

The only way I can think of to make this work consistently would
be to add another padding bit to size_t, a flag that indicates
whether it's an ordinary C size value or something that takes
nybbles into account.

I'm even more convinced that it wouldn't be worth the effort. The C
language is not conveniently portable to 4-bit addressable systems
(or trinary systems, or analog systems, or ...).

 

[glen herrmannsfeldt]

(snip regarding nybble addressing in C)

I'm even more convinced that it wouldn't be worth the effort. The C
language is not conveniently portable to 4-bit addressable systems
(or trinary systems, or analog systems, or ...).

As I learn more about the 4004, I am also more convinced.

It seems that program memory is byte addressed with a 12 bit
addressing space. Even so, it is possible to read/write
nybbles in program space (the latter, presumably, only if
it is in RAM).

Index registers (register pairs) are 8 bits, so much of the
pointer discussion won't be very interesting.

You can do indirect branching within a (256 byte) ROM.
Cross ROM requires either a direct branch, subroutine
(three level stack built into the 4004) call, or return
from subroutine.

Data memory is specified as 5120 bits, which I believe
is 1280 nybbles. I believe that is five address spaces
of 256 nybbles each, addressed with separate instructions.

(The 4002 RAM holds 80 nybbles. For the full data space
you need some other type of RAM.)

-- glen

 

[BartC]

(snip regarding nybble addressing in C)


As I learn more about the 4004, I am also more convinced.

Adapting C to work with such a processor is a waste of time I think.

But sub-byte data types are still useful whatever the processor or whether
they are individually addressable by hardware.

(These would be 1, 4 and 2-bits in order of usefulness. They fill in the
missing sizes at the start of this sequence: 8, 16, 32, 64, ..., so a 5-bit
type probably isn't necessary..)

This can be done now, with a crude collection of functions, but would nice
to have it as part of the language:

bit s[256]; //32 bytes
bit* p = &s[123];

sizeof() would still need to be byte-based; you don't want to mess about
with that part of the language. Something new is needed to work with
bit-types.

 

[Shao Miller]

Adapting C to work with such a processor is a waste of time I think.

But sub-byte data types are still useful whatever the processor or
whether they are individually addressable by hardware.

(These would be 1, 4 and 2-bits in order of usefulness. They fill in the
missing sizes at the start of this sequence: 8, 16, 32, 64, ..., so a
5-bit type probably isn't necessary..)

This can be done now, with a crude collection of functions, but would
nice to have it as part of the language:

Why do they have to be crude? Functions that the implementation
provides as extensions needn't be crude at all, and could translate with
whatever efficiency is possible.

bit s[256]; //32 bytes
bit* p = &s[123];

/* Is this allowed? */
struct {
int i;
bit ba[5];
double d;
} foo;
size_t sz = sizeof foo;

sizeof() would still need to be byte-based; you don't want to mess about
with that part of the language. Something new is needed to work with
bit-types.

It's 'sizeof', not 'sizeof()', if you please. Else we could discuss the
'()+()' operator, the '*()' and '()*()' operators, etc.