Bit field arrays unsupported?

[ballpointpenthief]

Hello,
I don't seem to be allowed to have arrays of bit fields?
Are there any ways round this? And what about good ways?

I tried typedef quickly with no luck.

Surely I should be allowed to do whatever I like with my memory...

Thanks for any info.
Matt

[Dann Corbit]

"ballpointpenthief" <Ma*************@gmail.com> wrote in message
news:11**********************@b68g2000cwa.googlegr oups.com...

Hello,
I don't seem to be allowed to have arrays of bit fields? That's right. Not in C. In C++ you can do it by operator overloading.
Are there any ways round this? And what about good ways? No. But bit sets can give approximately the same functionality:

From the C-FAQ:
20.8: How can I implement sets or arrays of bits?

A: Use arrays of char or int, with a few macros to access the
desired bit at the proper index. Here are some simple macros to
use with arrays of char:

#include <limits.h> /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))

(If you don't have <limits.h>, try using 8 for CHAR_BIT.)

References: H&S Sec. 7.6.7 pp. 211-216.
I tried typedef quickly with no luck.
No surprise there. A char is the smallest addressible unit in the C
language.
Surely I should be allowed to do whatever I like with my memory...
C can sort of do it. If you need the real array syntax eye-candy, then use
C++ instead.
Thanks for any info.
Matt

[Michael Mair]

ballpointpenthief schrieb:

I don't seem to be allowed to have arrays of bit fields?
Is that a question?
Are there any ways round this? And what about good ways?
No. None.
I tried typedef quickly with no luck.
No wonder.

The smallest unit of storage a pointer can point to is a
byte; the smallest possible size of an object is 1 byte.
unsigned char, for example, always has size 1 byte.
If you increase a valid pointer to unsigned char by 1, it
points to one past the previous byte (often: the next byte).
As arrays are introduced in terms of pointers, they cannot
address anything smaller than 1 byte. (a[i] effectively is
*((a)+(i)).)

What you _can_ do, if the fancy strikes you, is one of the
following:
1) Declare a structure type containing the bit-field and
declare arrays of this structure type.
2) If n is the number of bits you intended for your bitfield
type, calculate N = lcm(n, CHAR_BIT) and define appropriate
access macros which give you or set the "n-bit element" to
be accessed (create access macros for
unsigned char[N/CHAR_BIT] in order to access N/n "n-bit
elements" and work from there).

Surely I should be allowed to do whatever I like with my memory...

If you think so. There are some limits imposed by nature, some
by the way you access your memory (among those the semantics
of the language you use) and some by your personal ability.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Frederick Gotham]

Michael Mair posted:

If you increase a valid pointer to unsigned char by 1, it
points to one past the previous byte (often: the next byte).

I'm curious about how you worded that...

In what circumstances would it point to anything other than "the next
byte"?

--

Frederick Gotham

[pete]

Frederick Gotham wrote:

Michael Mair posted:

If you increase a valid pointer to unsigned char by 1, it
points to one past the previous byte (often: the next byte).

I'm curious about how you worded that...

In what circumstances would it point
to anything other than "the next byte"?

When "the previous byte" is the last byte of memory.

--
pete

[Frederick Gotham]

pete posted:

Frederick Gotham wrote:

Michael Mair posted:

> If you increase a valid pointer to unsigned char by 1, it
> points to one past the previous byte (often: the next byte).

I'm curious about how you worded that...

In what circumstances would it point
to anything other than "the next byte"?

When "the previous byte" is the last byte of memory.

Hmm...

The C language guarantees that you can have a pointer to "one past the
last element of an array"; therefore the following program is well-formed
and absent of undefined behaviour.
int main(void)
{
char buffer[56];

char *p = buffer + 56;
}
However... in order to facilitate this, it must be possible to store a
particular address in a pointer variable, and for that address to fulfill
the following criteria:

(A) The address is non-null.
(B) The address is not the address of a legitimate object.

You can't have a pointer to "two past the end", so the following code is
broken:

int main(void)
{
char buffer[56];

char *p = buffer + 57;
}
Given that there will always be a legitimate "border address" which
doesn't refer to a legitimate object, we can always assume that when we
increment a valid char pointer, it will always point to the next byte.
Am I right?

--

Frederick Gotham

[pete]

Frederick Gotham wrote:

pete posted:

Frederick Gotham wrote:

Michael Mair posted:

> If you increase a valid pointer to unsigned char by 1, it
> points to one past the previous byte (often: the next byte).

I'm curious about how you worded that...

In what circumstances would it point
to anything other than "the next byte"?
When "the previous byte" is the last byte of memory.

Hmm...

The C language guarantees that you can have a pointer to "one past the
last element of an array";
therefore the following program is well-formed
and absent of undefined behaviour.

Yes.
int main(void)
{
char buffer[56];

char *p = buffer + 56;
}

However... in order to facilitate this, it must be possible to store a
particular address in a pointer variable,
and for that address to fulfill
the following criteria:

(A) The address is non-null.
(B) The address is not the address of a legitimate object.

You can't have a pointer to "two past the end",
so the following code is broken:
Yes.
int main(void)
{
char buffer[56];

char *p = buffer + 57;
}

Given that there will always be a legitimate "border address" which
doesn't refer to a legitimate object,
we can always assume that when we
increment a valid char pointer, it will always point to the next byte.

Am I right?

Not quite.

There's no guarantee that the address after an object
is not the address of another object.
new.c prints out "equal" when I run it.

/* BEGIN new.c */

#include <stdio.h>

int main(void)
{
int one, two;

if (&one == &two + 1) {
puts("equal");
} else {
puts("not equal");
}
return 0;
}

/* END new.c */

--
pete

[Frederick Gotham]

pete posted:

Given that there will always be a legitimate "border address" which
doesn't refer to a legitimate object,
we can always assume that when we
increment a valid char pointer, it will always point to the next byte.

Am I right?

Not quite.

There's no guarantee that the address after an object
is not the address of another object.

Okay I see what you mean as regards the "one past the end" address
possibly being the address of an unrelated, legitimate object.

However, I still think we're guaranteed that when we increment a char*,
that it always points to the next byte.

My reasoning is as follows:

Let's say that a char* is 8-Bit on a particular system, and therefore
that it has 256 unique values. Take away 1 for the null pointer value,
and we're left with 255 unique memory addresses. Therefore, no matter how
much memory the system actually has, it's effectively limited to 255
bits.

When dealing with arrays, if we make a comparison between the address of
"one past the last", and the address of the last element, then it must
compare greater, i.e.:

char buffer[56];

assert( buffer + 56 > buffer + 55 );

This suggest that on this system, we can only actually address 247 unique
addresses (because our pointer is only 8-Bit).

If the last eight bits are unaccessible, then when we increment a
legitimate address, it should always point to the next address.

(Actually... something far more simple comes to mind. The following
program must run properly, and for that to happen, the incrementation of
a char* must also yield the address of the next byte:)

int main(void)
{
char buffer[56];

char *p = buffer + 55; /* Points to last element */
/* But we know we can go one past the end, so let's do it: */
++p; /* Now points to one past the end */
/* Now let's verify the pointer arithmetic: */
( p - (buffer + 55) ) == 1

p > (buffer + 55)
/* We're not allowed increment again though! */
}


--

Frederick Gotham

[Jack Klein]

On Wed, 21 Jun 2006 02:30:01 GMT, Frederick Gotham
<fg*******@SPAM.com> wrote in comp.lang.c:

pete posted:

Frederick Gotham wrote:

Michael Mair posted:

> If you increase a valid pointer to unsigned char by 1, it
> points to one past the previous byte (often: the next byte).

I'm curious about how you worded that...

In what circumstances would it point
to anything other than "the next byte"?
When "the previous byte" is the last byte of memory.

Hmm...

The C language guarantees that you can have a pointer to "one past the
last element of an array"; therefore the following program is well-formed
and absent of undefined behaviour.
int main(void)
{
char buffer[56];

char *p = buffer + 56;
}
However... in order to facilitate this, it must be possible to store a
particular address in a pointer variable, and for that address to fulfill
the following criteria:

(A) The address is non-null.
(B) The address is not the address of a legitimate object.

You can't have a pointer to "two past the end", so the following code is
broken:

int main(void)
{
char buffer[56];

char *p = buffer + 57;
}
Given that there will always be a legitimate "border address" which
doesn't refer to a legitimate object, we can always assume that when we
increment a valid char pointer, it will always point to the next byte.
Am I right?

No, not in all cases. Let's back up to the original statement by
Michael Mair:

"If you increase a valid pointer to unsigned char by 1, it
points to one past the previous byte (often: the next byte)."

Now let's rewrite your code snippet to match Mike's statement:

int main(void)
{
unsigned char buffer[56];
unsigned char *p = buffer + 55; /* 1: point to last element */
++p; /* 2: point to one past end of array */
++p; /* 3: point two past end of array */
}

The line marked 1: sets the pointer to the address of an existing
unsigned char that the program has the right to read, write, and
modify.

The line marked 2: sets the pointer to the address of one past the end
of the array. There may or may not be a byte there. Any attempt to
dereference that pointer, read or write, is undefined behavior. On
some systems the attempt might well cause the operating system to trap
and terminate the program.

So while this is a "valid unsigned char pointer value", it is not a
"valid pointer to unsigned char", since it is not allowed to be used
to access an unsigned char. Likewise, NULL is a "valid unsigned char
pointer value", but it is not a "valid pointer to unsigned char".

As for your code:
int main(void)
{
char buffer[56];

char *p = buffer + 57;
}

The array has 56 elements, indexed 0 through 55. It is legal to point
to, but not access, buffer + 56, one past the end. It is not legal to
even form a pointer to more than one past the end. The expression
"buffer + 57" produces undefined behavior. The result might well be
an immediate OS termination, although I don't know of any architecture
off-hand where forming, but not dereferencing, an invalid pointer
value traps.

This is a somewhat different case than assuming that either there are
no padding bits in integer types, or that if there are, their values
are irrelevant. There are code efficiencies possible with that
assumption. There are none to be had by forming invalid pointer
values.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

[Old Wolf]

Frederick Gotham wrote:

The C language guarantees that you can have a pointer to "one past the
last element of an array";

However... in order to facilitate this, it must be possible to store a
particular address in a pointer variable, and for that address to fulfill
the following criteria:

(A) The address is non-null.

That isn't a criterion. For example, the following system is
conforming (I think):

16-bit pointers
addresses 0x0000 through 0xFFFE are valid locations
0xFFFF is a null pointer

Then if you happen to have an array of 15 bytes whose address
is 0xFFF0, then the one-past-the-end pointer will be a null
pointer, but none of the other rules of C are violated; for example
if you subtract 0xFFFF and 0xFFF0 you get back 15, the size of
the array.

[pete]

Frederick Gotham wrote:

pete posted:

Given that there will always be a legitimate "border address" which
doesn't refer to a legitimate object,
we can always assume that when we
increment a valid char pointer, it will always
point to the next byte.

Am I right?
Not quite.

There's no guarantee that the address after an object
is not the address of another object.

Okay I see what you mean as regards the "one past the end" address
possibly being the address of an unrelated, legitimate object.

However, I still think we're
guaranteed that when we increment a char*,
that it always points to the next byte.

There's always a last byte.
If your pointer points to the last byte
and you increment that pointer,
how can it possibly be pointing to the next one,
when there is no next one?

My reasoning is as follows:

Let's say that a char* is 8-Bit on a particular system,
and therefore
that it has 256 unique values. Take away 1 for the null pointer value,
and we're left with 255 unique memory addresses.
Therefore, no matter how
much memory the system actually has, it's effectively limited to 255
bits.

When dealing with arrays,
if we make a comparison between the address of
"one past the last", and the address of the last element, then it must
compare greater, i.e.:

char buffer[56];

assert( buffer + 56 > buffer + 55 );

This suggest that on this system,
we can only actually address 247 unique
addresses (because our pointer is only 8-Bit).
I think you're mixing up bits and bytes.
If the last eight bits are unaccessible, then when we increment a
legitimate address, it should always point to the next address.

(Actually... something far more simple comes to mind. The following
program must run properly, and for that to happen,
the incrementation of
a char* must also yield the address of the next byte:)

int main(void)
{
char buffer[56];

char *p = buffer + 55; /* Points to last element */

/* But we know we can go one past the end, so let's do it: */

++p; /* Now points to one past the end */

/* Now let's verify the pointer arithmetic: */

( p - (buffer + 55) ) == 1

p > (buffer + 55)

/* We're not allowed increment again though! */
}

--
pete

[Frederick Gotham]

pete posted:

However, I still think we're
guaranteed that when we increment a char*,
that it always points to the next byte.

There's always a last byte.
If your pointer points to the last byte
and you increment that pointer,
how can it possibly be pointing to the next one,
when there is no next one?

Okay bear with me for a second...

Let's assume the following:

CHAR_BIT == 8
sizeof( char* ) == 1

If we imagine that the memory addresses are stored exactly like unsigned
integers, then a "char*" can have 256 unique values. We know that one of
these must represent null, so that leaves us with 255 unique values.

If it were possible to use the "last byte" as storage, then its address
would be 0xFF. However, the Standard says we can have a pointer to "one
past the end"... but how can we achieve this if our "char*" is already at
its maximum value? It will have to roll back to zero -- and I gather that
this is the kind of rationale behind the original statement which was
worded along the lines of "it usually points to the next byte".

My thoughts are that the highest usable byte is 0xFE (rather than 0xFF),
because only then we can have a pointer to one past the end, and this
pointer will work perfectly in comparisons and in pointer arithemtic,
i.e.:

char c;

const char * const p_last = &c;

const char * const p_over = &c + 1;

assert ( p_over > p_last );

assert ( p_over - p_last == 1 );

This suggest that on this system,
we can only actually address 247 unique
addresses (because our pointer is only 8-Bit).

I think you're mixing up bits and bytes.

Indeed...

[Frederick Gotham]

Old Wolf posted:

For example, the following system is
conforming (I think):

16-bit pointers
addresses 0x0000 through 0xFFFE are valid locations
0xFFFF is a null pointer

If I'm not mistaken, it would have to be like the following:

16-Bit pointers
Addresses 0x0000 to 0xFFFD inclusive are valid locations.
Address 0xFFFE serves as the address of "one past end".
Address 0xFFFF is the null pointer.

If it were possible to have a char located at 0xFFFE, then the value for
"one past end" would roll back to zero.

I'm not sure, but I HOPE, that the value for "one past end" can't be
null... it would hinder code such as the following:

#include <stddef.h>

void Func( char **p, size_t len )
{
/* 'p' points to an array of char* */

/* An element in the array may be a legitimate pointer,
or a pointer to one past the end, or it may be null
to indicate that it doesn't point to anything */
if (!p)
{
/* If it were possible for "one past the end" to
be null, then the body of this "if" statement
would be executed... but that's not what we want!

*/
}

}

Then if you happen to have an array of 15 bytes whose address
is 0xFFF0, then the one-past-the-end pointer will be a null
pointer

Based on what I wrote above, I would say that the highest address a char
[15] can have is: 0xFFE9

[Harald van Dijk]

Frederick Gotham wrote:

Old Wolf posted:

For example, the following system is
conforming (I think):

16-bit pointers
addresses 0x0000 through 0xFFFE are valid locations
0xFFFF is a null pointer
If I'm not mistaken, it would have to be like the following:

16-Bit pointers
Addresses 0x0000 to 0xFFFD inclusive are valid locations.
Address 0xFFFE serves as the address of "one past end".
Address 0xFFFF is the null pointer.

Then you cannot have an object of 65535 bytes, which is the official
minimum for hosted implementations. (A strict reading of the standard
disagrees, but that same reading states that there is no requirement
for compilers to accept any strictly conforming program, which is
clearly ridiculous.)
If it were possible to have a char located at 0xFFFE, then the value for
"one past end" would roll back to zero.
That was the point.
I'm not sure, but I HOPE, that the value for "one past end" can't be
null... it would hinder code such as the following:

Yes, if you assume "one past the end" cannot be null, and it turns out
it can be, your code won't work.

[Frederick Gotham]

Yes, if you assume "one past the end" cannot be null, and it turns out
it can be, your code won't work.

Are you saying that the Standard allows the "one past the end" pointer to
be equal to the null pointer value?
#include <stdio.h>
int main(void)
{
unsigned char array[59];

unsigned char *p = array + 59;

if (!p) printf("One past end compares equal to null!");
}
Even so... in such cases where the "one past end" pointer value can be
equal to the null pointer value, does the Standard stipulate that this
value will also compare greater than every other pointer value?

Consider the following loop:
for( unsigned char *p = array; p != p_over; ++p ) DoSomething();
in contrast to the following loop:
for( unsigned char *p = array; p < p_over; ++p ) DoSomething();
The latter loop could possibly malfunction if "p_over" is equal to the
null pointer, and if the null pointer DOESN'T compare greater than all
other addresses.

Hmm...

[Keith Thompson]

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

Yes, if you assume "one past the end" cannot be null, and it turns out
it can be, your code won't work.

Please don't snip attribution lines. The above was written by "Harald
van D?k" (sorry, it appears with the '?' on my system).
Are you saying that the Standard allows the "one past the end" pointer to
be equal to the null pointer value?

The standard doesn't say that it can't, but I think it was an
oversight. There was discussed at length recently; see the
"Insufficient guarantees for null pointers?" thread in comp.std.c.

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

Frederick Gotham wrote:

Yes, if you assume "one past the end" cannot be null, and it turns out
it can be, your code won't work.
Are you saying that the Standard allows the "one past the end" pointer to
be equal to the null pointer value?

There is a guarantee that null pointer constants won't compare equal to
a pointer to any object or function. There is no guarantee that null
pointer constants won't compare equal to any other valid pointer value.
Even so... in such cases where the "one past end" pointer value can be
equal to the null pointer value, does the Standard stipulate that this
value will also compare greater than every other pointer value?
Yes. (As long as you obtained the value via address manipulation,
anyway; perhaps not if you convert 0 to this pointer type, even if it
would have the same representation.)
Consider the following loop:
for( unsigned char *p = array; p != p_over; ++p ) DoSomething();
in contrast to the following loop:
for( unsigned char *p = array; p < p_over; ++p ) DoSomething();
The latter loop could possibly malfunction if "p_over" is equal to the
null pointer, and if the null pointer DOESN'T compare greater than all
other addresses.

Both fragments must behave the same, even if p_over can be a null
pointer.

[pete]

Frederick Gotham wrote:

pete posted:

However, I still think we're
guaranteed that when we increment a char*,
that it always points to the next byte.

There's always a last byte.
If your pointer points to the last byte
and you increment that pointer,
how can it possibly be pointing to the next one,
when there is no next one?

Okay bear with me for a second...

Let's assume the following:

CHAR_BIT == 8
sizeof( char* ) == 1

If we imagine that the memory addresses are
stored exactly like unsigned
integers, then a "char*" can have 256 unique values.
We know that one of
these must represent null,
so that leaves us with 255 unique values.

If it were possible to use the "last byte" as storage,
then its address would be 0xFF.
However,
the Standard says we can have a pointer to "one
past the end"...
but how can we achieve this if our "char*" is already at
its maximum value?

Perhaps it's the case that an 8 bit pointer can only give you
NULL
plus 254 byte addresses
plus one address that may or may not correspond to a byte of memory.

The highest representable address may correspond to a byte
of memory, but there's no reason why it has to.

--
pete

[Frederick Gotham]

Keith Thompson posted:

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

Yes, if you assume "one past the end" cannot be null, and it turns
out it can be, your code won't work.
Please don't snip attribution lines. The above was written by "Harald
van D?k" (sorry, it appears with the '?' on my system).

Sorry, I usually specify who wrote what, but the poster's name came up as
garbage on my system.

Are you saying that the Standard allows the "one past the end"
pointer to be equal to the null pointer value?

The standard doesn't say that it can't, but I think it was an
oversight. There was discussed at length recently; see the
"Insufficient guarantees for null pointers?" thread in comp.std.c.

Thanks... I'll go take a look now.