Preprocessor fun; \xdigits

[Arthur J. O'Dwyer]

Okay, here's a useless and contrived challenge for
those here who know the preprocessor better than I
do.
Introduction: For a school project, we must <ot>build
a malloc package for a Linux system.</ot> It has to
satisfy several bizarre constraints in order to make the
grading robot happy, including the following:

No named objects of non-scalar type and static storage
duration. I.e., no static arrays, no structs at file
scope, etc., etc. [My paraphrase of the real constraint,
which is of course more vaguely specified. But that's
the gist of it.]

Naturally, I want to have a global array something like
the following:

static const size_t bucket_sizes[] = {
1, 2, 3, 4, 5, [...],
32, 48, 64, 96, 128, [...],
1024, 2048, 4096, [...],
(size_t)-1
};

for use with a segregated-storage-type malloc package.
(The array holds the sizes of storage available to the
system, and we keep linked lists of blocks of those
sizes, blah blah blah...)
But I can't do that, because it would violate the
rules of the robot. Yes, I've asked the TA, and yes,
really we can't have global arrays.
So the design issue is: How best to handle the initialization
of an "array," without actually making it a real C array?
Obviously, I could write

static int *bucket_sizes = NULL;

[...]
bucket_sizes = get_some_memory(LOTS);
bucket_sizes[0] = 1;
bucket_sizes[1] = 2;
bucket_sizes[2] = 3;
[...]

....but that's just ridiculously ugly and bad.
So I thought I might be able to keep the nice array
structure by using the following *VERY UNPORTABLE*
method:

static const int *bucket_sizes = (const int *)
"\x01\x00\x00\x00"
"\x02\x00\x00\x00"
"\x03\x00\x00\x00"
[...]
"\x00\x04\x00\x00"
"\x00\x08\x00\x00"
"\x00\x10\x00\x00"
[...]
"\xFF\xFF\xFF\xFF"
;

Now, this is still ugly, but it is allowed by the
TA (yes, I checked, honestly it is!), and it looks
to me like it *should* be easy to come up with a
system of macros so that I could easily write:

BEGIN_ARRAY(bucket_sizes)
ARRAY_ELEM(00,00,00,01)
ARRAY_ELEM(00,00,00,02)
ARRAY_ELEM(00,00,00,03)
ARRAY_ELEM(00,00,04,00)
ARRAY_ELEM(00,00,08,00)
ARRAY_ELEM(00,00,10,00)
ARRAY_ELEM(FF,FF,FF,FF)
END_ARRAY

and somehow get that string representation out of
the macros. But I can't figure out if there's any
way to insert the necessary \x's in front of each
hex digit pair and still trick the compiler into
thinking it's one token.

Can anyone help with this?
Or show that it can't be done the way I want?
Or (even better) give a "better" alternative
that still obeys the robot's rules about global
data structures?

Thanks much,
-Arthur

 

[Arthur J. O'Dwyer]

static const int *bucket_sizes = (const int *)
"\x01\x00\x00\x00"
"\x02\x00\x00\x00"
[...]

system of macros so that I could easily write:

BEGIN_ARRAY(bucket_sizes)
ARRAY_ELEM(00,00,00,01)
ARRAY_ELEM(00,00,00,02)
ARRAY_ELEM(00,00,00,03)
ARRAY_ELEM(00,00,04,00)
ARRAY_ELEM(00,00,08,00)
ARRAY_ELEM(00,00,10,00)
ARRAY_ELEM(FF,FF,FF,FF)
END_ARRAY

Wouldn't you know it, as soon as I posted that, I went
back to the source I was struggling with and produced
the following [half-tested]:

#define G(X) #X
#define F(X,Y) G(X ## Y)
#define E(X) F(\x, X)
#define ARRAY_ELEM(w,x,y,z) E(z) E(y) E(x) E(w)
#define BEGIN_ARRAY(foo) static const int *foo = (const int *)
#define END_ARRAY ;

Just to check: That's all legal C90, right?
Or is gcc hiding something from me again?


Better ideas still welcomed,
-Arthur

 

[Ben Pfaff]

Naturally, I want to have a global array something like
the following:

static const size_t bucket_sizes[] = {
1, 2, 3, 4, 5, [...],
32, 48, 64, 96, 128, [...],
1024, 2048, 4096, [...],
(size_t)-1
};
[...]

But I can't do that, because it would violate the
rules of the robot. Yes, I've asked the TA, and yes,
really we can't have global arrays.
So the design issue is: How best to handle the initialization
of an "array," without actually making it a real C array?

Following is untested, uncompiled, and poorly proofread:

static size_t *bucket_sizes;
static size_t n_buckets, m_buckets;

static void add_bucket (size_t value)
{
if (n_buckets >= m_buckets) {
m_buckets = (m_buckets + 8) * 3 / 2;
bucket_sizes = realloc (bucket_sizes,
sizeof *bucket_sizes * m_buckets);
}
bucket_sizes[n_buckets++] = value;
}

static void init_buckets (void)
{
size_t size;

for (size = 1; size < 32; size++)
add_bucket (size);

for (size = 32; size < 1024; size *= 2) {
add_bucket (size);
add_bucket (size * 3 / 2);
}

/* I *think* this is correct. Caveat programmer. */
for (size = 1024; size >= 1024; size *= 2)
add_bucket (size);

add_bucket (-1);
}

 

[Ben Pfaff]

Wouldn't you know it, as soon as I posted that, I went
back to the source I was struggling with and produced
the following [half-tested]:

#define G(X) #X
#define F(X,Y) G(X ## Y)
#define E(X) F(\x, X)
#define ARRAY_ELEM(w,x,y,z) E(z) E(y) E(x) E(w)
#define BEGIN_ARRAY(foo) static const int *foo = (const int *)
#define END_ARRAY ;

You're planning to turn this in as part of a class? Or as part
of an International Obfuscated C Coding Contest entry?

 

[Arthur J. O'Dwyer]

Naturally, I want to have a global array something like
the following: ^^^^^^^^^^^^^^

static const size_t bucket_sizes[] = {
1, 2, 3, 4, 5, [...],
32, 48, 64, 96, 128, [...],
1024, 2048, 4096, [...],
(size_t)-1
};

[...]

for (size = 1; size < 32; size++)
add_bucket (size);

for (size = 32; size < 1024; size *= 2) {
add_bucket (size);
add_bucket (size * 3 / 2);
}

Sorry, Ben, I wasn't as clear as I could've been.
The bucket sizes aren't as nicely fixed as all
that; they're meant to be listed out in a neat
little [hah!] array whose elements can be looked
at and modified by the maintainer (that's me).
I already wrote a little tool that looks at
what size blocks are being requested by the test
suite and give me a neat listing of the sizes I
should be using for best performance. [It tells
me, for instance, that I don't need a bucket for
"5", but I do need a bucket for "4072".]

Thanks for taking the time to look at it, though.
And re your other post: Yes, for a class. No,
not for the IOCCC -- it's not *nearly* obfuscated
enough. Heck, it's about as clear as I can make
it, within the rules!
Now the relevant portion of the code looks
like this (comments show macro substitution
results):

BEGIN(segr_size) /* size_t *segr_size = (size_t*) */
HEX_ELEM(00,02) /* "\x02\x00\x00\x00" */
HEX_ELEM(00,03) /* "\x03\x00\x00\x00" */
[...]
HEX_ELEM(15,DA) /* "\xDA\x15\x00\x00" */
LAST_ELEM /* "\xFF\xFF\xFF\xFF" */
END(segr_size); /* ; */

I don't suppose anyone has any clever ways of
computing the length of the string pointed to by
'segr_size' as an integer constant expression,
do they? ;-)

Thanks,
-Arthur

 

[Ben Pfaff]

for (size = 1; size < 32; size++)
add_bucket (size);

for (size = 32; size < 1024; size *= 2) {
add_bucket (size);
add_bucket (size * 3 / 2);
}

Sorry, Ben, I wasn't as clear as I could've been.
The bucket sizes aren't as nicely fixed as all
that; they're meant to be listed out in a neat
little [hah!] array whose elements can be looked
at and modified by the maintainer (that's me).

Something like this then?

#include <stddef.h>
#include <stdarg.h>

void add_buckets (unsigned long first, ...)
{
va_list args;

if (first == -1)
return;
add_bucket (first);

va_start (args, first);
for (; {
unsigned long next = va_arg (args, unsigned long);
if (next == -1)
break;
add_bucket (next);
}
va_end (args);
}

....
add_buckets (1ul, 2ul, 3ul, ..., -1ul);
....

 

[Matt Gregory]

No named objects of non-scalar type and static storage
duration. I.e., no static arrays, no structs at file
scope, etc., etc. [My paraphrase of the real constraint,
which is of course more vaguely specified. But that's
the gist of it.]

What about:

int get_bucket_size(int i)
{
const size_t bucket_sizes[] = {
1, 2, 3, 4, 5, [...],
32, 48, 64, 96, 128, [...],
1024, 2048, 4096, [...],
(size_t)-1
};
return bucket_sizes;
}

?/MG

 

[Christian Bau]

Can anyone help with this?
Or show that it can't be done the way I want?
Or (even better) give a "better" alternative
that still obeys the robot's rules about global
data structures?

It is your task to find a solution that demonstrates good programming
practices, while at the same time formally obeying the given
restrictions and demonstrating their stupidity.

Write your code using static structs as you would normally do it.
Restrict yourself to reading and writing struct members, on +=, -=
operators etc. Test the code until it is working. Since this is
something that you _are_ supposed to learn, there will be no help with
this.

Start a new file. Should look like

#ifdef GOOD_SOLUTION
<original code>
#else
<stupid code>
#endif

The <stupid code> is initially your original code. Then you change it
step by step to obey the rules. Define two macros

#structget(dst,type,name,member) dst = name.member
#structput(type,name,member,src) name.member = src

If you had a static struct

static struct xstruct x;

and an assignment x.y = z;

then replace this with

structput (struct xstruct, x, y, z);

If you had an access like

z = x.y;

the replace this with

structget (z, struct xstruct, x, y);

Test until your code is working. Now you are ready to please the grading
robot: Replace each static struct with a char* of the same name.
Allocate enough memory for each at initialisation time. Then replace the
get/put macros:

#define structget(dst,type,name,member) \
do { type dummy; memcpy (&dummy, name, sizeof type); \
dst = dummy.member; } while (0)

#define structput(type,name,member,src) \
do { type dummy; memcpy (&dummy, name, sizeof type); \
dummy.member = src; memcpy (name, &dummy, sizeof type); \
} while (0)

To make sure that your grading robot has no valid excuses to grade you
down, change things slightly:

#ifdef GOOD_SOLUTION
<original code>
#else
<struct declarations>
#if EFFICIENT_CODE
static struct xstruct x;
...
#define structget... (first version)
#else
static unsigned char* x;
...
#define structput... (second version)
#endif
#endif