Squeezing bytes out of a struct

Hi,

[I'll post this here instead of c.l.c as I suspect folks here
are far more adept at "squeezing bytes" out of things (vs.
the "desktop jocks")]

While arguably not legitimate, the following is in the
*spirit* of the language (consider much of this pseudo-code):

typedef struct {
size_t length;
int foo;
char bar;
element_t array;
} fussbucket_t;

fussbucket_t sample;

sample.array[0] = (element_t) foo;
sample.array[1] = (element_t) bar;

ASSERT(sample.array == sample.array[0]);

etc.

To accommodate cases where sizeof(array) is "too large"
(whatever that means) to dangle off the bussbucket_t,
you could optionally store a pointer to the array in
place of array[0]. E.g.,

typedef struct {
size_t length;
int foo;
char bar;
union {
element_t array;
element_t *pointer;
} u;
} fussbucket_t;

fussbucket_t sample;
element_t longArray[A_BIG_NUMBER];

sample.u.array[0] = &longArray[0];

If sizeof(element_t) is smaller than sizeof(element_t *),
then you can cheat and pack a few element_t's into the
union. I.e., as if:

struct {
size_t length;
int foo;
char bar;
union {
element_t array[sizeof(element_t *)/sizeof(element_t)];
element_t *pointer;
} u;
}

I *think* this may be portable -- I haven't even checked the
syntax to see if I've shot myself in the foot before I even got
started! :< Is there a cleaner way of doing this? I can
already see some pathological cases where it would *look* right
and yet result in entities that would choke at run-time.

Thx!
--don

D Yuniskis wrote:

[Grrr... should probably have run this through cc before posting :< ]

> typedef struct {
> size_t length;
> int foo;
> char bar;
> element_t array;
> } fussbucket_t;
>
> fussbucket_t sample;
>
> sample.array[0] = (element_t) foo;
> sample.array[1] = (element_t) bar;

sample.array[0] = (element_t) fu;
sample.array[1] = (element_t) baz;

(eliminate any confusion with struct members)

> To accommodate cases where sizeof(array) is "too large"
> (whatever that means) to dangle off the bussbucket_t,

s/bussbucket_t/fussbucket_t/

> typedef struct {
> size_t length;
> int foo;
> char bar;
> union {
> element_t array;
> element_t *pointer;
> } u;
> } fussbucket_t;
>
> fussbucket_t sample;
> element_t longArray[A_BIG_NUMBER];
>
> sample.u.array[0] = &longArray[0];

sample.u.pointer = &longArray[0];

[sorry!]

On Mon, 26 Oct 2009 21:45:07 +0100, David Brown
<> wrote:

>D Yuniskis wrote:
>> Hi,
>>
>> [I'll post this here instead of c.l.c as I suspect folks here
>> are far more adept at "squeezing bytes" out of things (vs.
>> the "desktop jocks")]
>>
>
>It's probably fair to say that the c.l.c. crowd are more concerned with
>what is theoretically correct in C, while in c.a.e. we are more
>concerned with practical working code.
>
>> While arguably not legitimate, the following is in the
>> *spirit* of the language (consider much of this pseudo-code):
>>
>
>Your code is inarguably not legitimate, and is not in the "spirit" of
>any language I know of.
>
>It would help enormously if you could give a short description of what
>you are trying to do - it's very hard to guess from this post. Your
>second "correction" post doesn't really help either - it is still
>mangled code, and mixing in partial quotations from your first post with
>partial corrections and smart-ass "sed" notation makes it even less clear.
>
>Figure out what you are trying to do, and explain it in a post. Then
>someone will probably be able to help you.
>
>mvh.,

The best I could make of it is that the op wanted something like:

typedef struct {
size_t length;
int foo;
char bar;
element_t array[1];
} fussbucket_t;

And then use:

fussbucket_t* sample= (fussbucket_t *) malloc(
sizeof( fussbucket_t )+
sizeof( element_t ) * (n-1)
);
sample->length = n;
sample->array[0] = (element_t) foo;
sample->array[1] = (element_t) bar;

"David Brown" <> wrote in message
news:eqGdnY3Ij-...
>
> It's probably fair to say that the c.l.c. crowd are more concerned with
> what is theoretically correct in C, while in c.a.e. we are more concerned
> with practical working code.
>

Agreed. Not only working but also maintainable. The sample code posted was
anything but that.

--
Chris Burrows
CFB Software
http://www.cfbsoftware.com

D Yuniskis wrote:
> Hi,
>
> [I'll post this here instead of c.l.c as I suspect folks here
> are far more adept at "squeezing bytes" out of things (vs.
> the "desktop jocks")]
>
> While arguably not legitimate, the following is in the
> *spirit* of the language (consider much of this pseudo-code):
>
> typedef struct {
> size_t length;
> int foo;
> char bar;
> element_t array;
> } fussbucket_t;
>
> fussbucket_t sample;
>
> sample.array[0] = (element_t) foo;
> sample.array[1] = (element_t) bar;

You can only index array types and pointer types. What is the type of
element_t?

> ASSERT(sample.array == sample.array[0]);

That is true if array is a multidimensional array, but not, in general,
otherwise.

> To accommodate cases where sizeof(array) is "too large"
> (whatever that means) to dangle off the bussbucket_t,
> you could optionally store a pointer to the array in
> place of array[0]. E.g.,
>
> typedef struct {
> size_t length;
> int foo;
> char bar;
> union {
> element_t array;
> element_t *pointer;
> } u;
> } fussbucket_t;
>
> fussbucket_t sample;
> element_t longArray[A_BIG_NUMBER];
>
> sample.u.array[0] = &longArray[0];
>
> If sizeof(element_t) is smaller than sizeof(element_t *),
> then you can cheat and pack a few element_t's into the
> union. I.e., as if:
>
> struct {
> size_t length;
> int foo;
> char bar;
> union {
> element_t array[sizeof(element_t *)/sizeof(element_t)];
> element_t *pointer;
> } u;
> }
>
> I *think* this may be portable -- I haven't even checked the
> syntax to see if I've shot myself in the foot before I even got
> started!

That works if sizeof(element_t*) >= sizeof(element_t). Of course, that
is true only for small types. In the general case, if that is not true,
you have declared an array of zero elements, which isn't allowed in that
part of the declaration.

You could make it work by using a max() macro:
element_t
array[max(sizeof(element_t),sizeof(element_t*))/sizeof(element_t)];

which guarantees at least one item in array. Unfortunately, you cannot
use the standard preprocessor for selecting different code, depending on
which is greater.

--
Thad

Jon Kirwan wrote:
> On Mon, 26 Oct 2009 21:45:07 +0100, David Brown
> <> wrote:
>
>> D Yuniskis wrote:
>>> Hi,
>>>
>>> [I'll post this here instead of c.l.c as I suspect folks here
>>> are far more adept at "squeezing bytes" out of things (vs.
>>> the "desktop jocks")]
>>>
>> It's probably fair to say that the c.l.c. crowd are more concerned with
>> what is theoretically correct in C, while in c.a.e. we are more
>> concerned with practical working code.
>>
>>> While arguably not legitimate, the following is in the
>>> *spirit* of the language (consider much of this pseudo-code):
>>>
>> Your code is inarguably not legitimate, and is not in the "spirit" of
>> any language I know of.
>>
>> It would help enormously if you could give a short description of what
>> you are trying to do - it's very hard to guess from this post. Your
>> second "correction" post doesn't really help either - it is still
>> mangled code, and mixing in partial quotations from your first post with
>> partial corrections and smart-ass "sed" notation makes it even less clear.
>>
>> Figure out what you are trying to do, and explain it in a post. Then
>> someone will probably be able to help you.
>>
>> mvh.,
>
> The best I could make of it is that the op wanted something like:
>
> typedef struct {
> size_t length;
> int foo;
> char bar;
> element_t array[1];
> } fussbucket_t;
>
> And then use:
>
> fussbucket_t* sample= (fussbucket_t *) malloc(
> sizeof( fussbucket_t )+
> sizeof( element_t ) * (n-1)
> );
> sample->length = n;
> sample->array[0] = (element_t) foo;
> sample->array[1] = (element_t) bar;
> .
> .
>
> up to some limit determined by sample->length.
>
> But I think that is standard c and discussed in the standard.
>

I also thought it was something like that he meant. But then it looked
like he wanted to have space for a few element_ts within the original
struct, or alternatively a pointer to an external array of element_ts,
and that he hoped to have the same simple syntax for accessing everything.

As you say, arrays of length 1 used as above are legal in standard C.
With C99, you can use a flexible array (i.e., "element_t array[];"), but
I'm not sure if sizeof(fussbucket_t) is then valid (it should work as
desired in gcc, but is not necessarily standard). But it saves space if
the array is sometimes empty, and makes the malloc size calculation
slightly neater.

With gcc, you can also use "element_t array[0];" for pretty much the
same effect in this case.

> So that left me more certain I don't understand.
>
> Oh, well.
>
> Jon

[I've merged in some of the corrections I posted earlier
but have refrained from making all syntactic changes]

Thad Smith wrote:
> D Yuniskis wrote:
>
>> typedef struct {
>> size_t length;
>> int fu;
>> char baz;
>> element_t array;
>> } fussbucket_t;
>>
>> fussbucket_t sample;
>>
>> sample.array[0] = (element_t) foo;
>> sample.array[1] = (element_t) bar;
>
> You can only index array types and pointer types. What is the type of
> element_t?

Yes, this was intended just to illustrate dangling the
balance of the "array" off the end of the struct. See the
later example for better syntax...

>> ASSERT(sample.array == sample.array[0]);
>
> That is true if array is a multidimensional array, but not, in general,
> otherwise.

Again, it is intended to state that the 0th element of
the array resides within the struct. How else could I
express it (array[0] == array[0] is too obvious :> )

>> To accommodate cases where sizeof(array) is "too large"
>> (whatever that means) to dangle off the bussbucket_t,
>> you could optionally store a pointer to the array in
>> place of array[0]. E.g.,
>>
>> typedef struct {
>> size_t length;
>> int fu;
>> char baz;
>> union {
>> element_t array;
>> element_t *pointer;
>> } u;
>> } fussbucket_t;
>>
>> fussbucket_t sample;
>> element_t longArray[A_BIG_NUMBER];
>>
>> sample.u.array[0] = &longArray[0];
>>
>> If sizeof(element_t) is smaller than sizeof(element_t *),
>> then you can cheat and pack a few element_t's into the
>> union. I.e., as if:
>>
>> struct {
>> size_t length;
>> int fu;
>> char baz;
>> union {
>> element_t array[sizeof(element_t *)/sizeof(element_t)];
>> element_t *pointer;
>> } u;
>> }
>>
>> I *think* this may be portable -- I haven't even checked the
>> syntax to see if I've shot myself in the foot before I even got
>> started!
>
> That works if sizeof(element_t*) >= sizeof(element_t).

Yes, as I said:
"If sizeof(element_t) is smaller than sizeof(element_t *), ..."
it also works if sizeof(element_t *) == sizeof(element_t) but
that degenerates to the original example.

> Of course, that is true only for small types.

Exactly. If element_t is "big" (relatively speaking), then
there are no economies in this approach. But, in *practice*,
this lets me pack as many as eight in.

Aside from the syntactic complexity, there is no real
cost to this approach (though on some older compilers
the extra addressing could benefit from a good peephole
optimizer).

On more modern platforms, there was an unexpected and notable
performance *benefit* (besides space economies). I
suspect this may be a side-effect of references to the
struct's members priming the cache (exploiting locality
of reference between the "element_t's" and the other
struct members that are associated with them).

> In the general case, if that is not true,
> you have declared an array of zero elements, which isn't allowed
> in that part of the declaration.

The risk only happens when sizeof(element_t) > sizeof(element_t *).
This is something that the developer has to safeguard against
as there is no way that I can "#error" at compile time. What
I have done is added a tiny executable to my makefile that
essentially compares the sizeof's, prints an error message
and returns a nonzero result code that causes the make(1) to
fail with the message that it displays.

I can think of no other way to enforce this requirement.

> You could make it work by using a max() macro:
> element_t
> array[max(sizeof(element_t),sizeof(element_t*))/sizeof(element_t)];

This is only legal in newer C (C99?). E.g.,
you couldn't put such a declaration in file scope... (?)

> which guarantees at least one item in array. Unfortunately, you cannot
> use the standard preprocessor for selecting different code, depending on
> which is greater.

Exactly. An unfortunate consequence of sizeof not being valid
in the preprocessor (though I have found many compilers that
*will* recognize its use there).

There is also a hazard that can bite a sloppy coder if
sizeof(element_t *) mod sizeof(element_t) != 0. But,
you can't protect against incompetence :-) (I guess
I could provide a macro to simplify accessing the array
elements while avoiding this hazard).

Chris Burrows wrote:
> Agreed. Not only working but also maintainable. The sample code posted was
> anything but that.

Perhaps you could suggest how this could be made *more*
maintainable? (keeping in mind that you don't want to
make it *brittle* in the process!)

The following should compile and "work". I can't imagine
how to change it to make it more "maintainable" :-(

=====================================
typedef struct {
size_t length;
int fu;
char baz;
union {
element_t *pointer;
element_t array[sizeof(element_t *)/sizeof(element_t)];
} u;
} fussbucket_t;

#define FREEBIES (sizeof(element_t *)/sizeof(element_t))

int main(int argc, char *argv[])
{
fussbucket_t fuss, *fptr;
element_t elem, longArray[(CNT)];
int count;

ASSERT((CNT) > 0);
ASSERT((NUM) >= 0);
ASSERT(sizeof(element_t *) >= sizeof(element_t)); /* FREEBIES > 0 */

/* trivial case */
fuss.u.array[0] = elem; /* guaranteed to fit */

/* optimization */
for (count = 0; count < (FREEBIES); count++) {
fuss.u.array[count] = elem; /* guaranteed to fit */
}

/* dangling elements */
fptr = (fussbucket_t *)
malloc(sizeof(fussbucket_t) + ((NUM) * sizeof(element_t)));
ASSERT(fptr != NULL);

for (count = 0; count < (FREEBIES) + (NUM); count++) {
fptr->u.array[count] = elem; /* guaranteed to fit */
}
free(fptr);

/* external storage */
fuss.u.pointer = &longArray[0];
for (count = 0; count < (CNT); count++) {
*fuss.u.pointer++ = elem; /* guaranteed to fit */
}

return 0;
}

On Tue, 27 Oct 2009 09:26:07 -0700, D Yuniskis
<> wrote:

>Chris Burrows wrote:
>> Agreed. Not only working but also maintainable. The sample code posted was
>> anything but that.
>
>Perhaps you could suggest how this could be made *more*
>maintainable? (keeping in mind that you don't want to
>make it *brittle* in the process!)
>
>The following should compile and "work". I can't imagine
>how to change it to make it more "maintainable" :-(
>
A big thing that makes code maintainable is good comments.
Describe what each variable/structure/type is used for.
Describe input & output parameters. Include a description of
each function/procedure's purpose, assumptions, and limitations.

"D Yuniskis" <> wrote in message
news:hc76jv$n5q$...
> Chris Burrows wrote:
>> Agreed. Not only working but also maintainable. The sample code posted
>> was anything but that.
>
> Perhaps you could suggest how this could be made *more*
> maintainable? (keeping in mind that you don't want to
> make it *brittle* in the process!)
>

Some more information is required first. AFAICS you have proposed a solution
without clearly describing the problem domain that it is attempting to
address.

What exactly are you trying to achieve?

What alternative solutions have you rejected and why?

Have some particular real-world circumstances driven you to devise such an
obscure approach or is this just an intellectual exercise?

--
Chris Burrows
CFB Software
Armaide: ARM Integrated Development System
http://www.cfbsoftware.com/armaide