Binary set - how to calculate offset?

[A. Farber]

Hello C programmers,

I have a small web game with the server part written in C
which runs on OpenBSD (Linux and Cygwin work too).

I've found out, that for me it's most comfortable to
make the different player states to be of power of 2:

typedef enum user_phase {
CONNECTING = 0,
CHAT_LOBBY = 1,
CHAT_TABLE = 2,
KIBITZING = 4,
BIDDING_1 = 8,
TAKING_TALON_1 = 16,
TAKING_TALON_2 = 32,
DISCARDING_1 = 64,
DISCARDING_2 = 128,
DECLARING = 256,
BIDDING_2 = 512,
ALL_PASSED = 1024,
PLAYING = 2048,
PHASE_MAX = 4096
} user_phase;

/* all phases from above except CONNECTING */
#define ALL_PHASES ((uint32_t) 0xFFFFFFFF)

That way I can check quickly for several phases
at once, for example here in event handling table:

static const EVENT_ENTRY EVENT_TABLE[] = {
/* valid phases args table turn */
{ ALL_PHASES, NO, ANY, ANY, handle_alive },
{ ALL_PHASES, YES, ANY, ANY, handle_chat },
{ ALL_PHASES ^ KIBITZING, NO, ANY, NO, handle_kuku },
{ CHAT_LOBBY, YES, NO, ANY, handle_join },
{ ALL_PHASES ^ CHAT_LOBBY, NO, YES, ANY, handle_lobby },
{ BIDDING_1 | BIDDING_2, YES, YES, YES, handle_bid },
{ ALL_PASSED | PLAYING, YES, YES, YES, handle_card }
};

However my problem is to perform the backward
mapping: given a user_phase, how do I found out,
which power of 2 is it (sorry for my awkward language)?

For example here how I find phase names currently:

static const char* PHASE_NAMES[] = {
"CONNECTING",
"CHAT_LOBBY",
"CHAT_TABLE",
"KIBITZING",
"BIDDING_1",
"TAKING_TALON_1",
"TAKING_TALON_2",
"DISCARDING_1",
"DISCARDING_2",
"DECLARING",
"BIDDING_2",
"ALL_PASSED",
"PLAYING"
};

const char*
phase_name(user_phase phase)
{
unsigned i;

for (i = 0; i < sizeof(PHASE_NAMES) / sizeof(char*); i++)
if ((uint32_t)(1 << i) == phase)
return PHASE_NAMES;

return "UNKNOWN";
}

Is there a better way maybe?

Thank you
Alex

 

[Eric Sosman]

A. Farber wrote On 05/04/07 10:26,:

[...]

However my problem is to perform the backward
mapping: given a user_phase, how do I found out,
which power of 2 is it (sorry for my awkward language)?

(The snipped material makes clear that user_phase
is an enum value equal to a positive integral power of 2.)

Stripped to its essentials, you are looking for the
binary logarithm of a value. There are many ways to do
this, some of which are described at

http://graphics.stanford.edu/~seander/bithacks.html

WARNING: Some of the hacks on this page rely on non-portable
assumptions, not always mentioned explicitly. Be alert!
Also, the claims about operation count, branch counts, and
so on are strongly platform-dependent.

 

[Old Wolf]

I've found out, that for me it's most comfortable to
make the different player states to be of power of 2:

typedef enum user_phase {
CONNECTING = 0,
CHAT_LOBBY = 1,
CHAT_TABLE = 2, [...]
PLAYING = 2048,
PHASE_MAX = 4096

I find it is clearer to use hexadecimal constants in this
situation; it also helps to reduce typoes, sign, and
out-of-range constant problems.

/* all phases from above except CONNECTING */
#define ALL_PHASES ((uint32_t) 0xFFFFFFFF)

What is the purpose of that cast?

NB. 0xFFFFFFFF is already an unsigned int (unless you
are on a system where int is less than 32 bits, in which
the code is still correct but it will be a long or an unsigned
long).

That way I can check quickly for several phases
at once, for example here in event handling table:

static const EVENT_ENTRY EVENT_TABLE[] = {

A minor point; uppercase identifiers starting with E are
reserved for implementation use whenever <errno.h> is
included. Suppose you were coding on an embedded
air conditioning system, the system vendor might have
defined an error condition where the entry to an air vent
was malfunctioning: E VENT_ENTRY !

/* valid phases args table turn */

{ CHAT_LOBBY, YES, NO, ANY, handle_join },
{ ALL_PHASES ^ CHAT_LOBBY, NO, YES, ANY, handle_lobby },
{ BIDDING_1 | BIDDING_2, YES, YES, YES, handle_bid },
{ ALL_PASSED | PLAYING, YES, YES, YES, handle_card }

However my problem is to perform the backward
mapping: given a user_phase, how do I found out,
which power of 2 is it (sorry for my awkward language)?

They way I do such things is (note, I like to always
prefix my enums to avoid unexpected clashes and
avoid causing undefind behaviour if one starts with E):

enum
{ PHASE_NONE
, PHASE_FOO
, PHASE_BAR
, PHASE_QUX
, NUM_PHASES
};

char const *phase_names[] =
{ "(none)"
, "foo"
, "bar"
, "qux"
};

STATIC_ASSERT( NUM_PHASES == dimof(phase_names) );

Note, this can be hard to keep in sync if the tables are
large. So it is possible to combine those two into one file, eg.
MAGIC( PHASE_FOO, "foo" )
MAGIC( PHASE_BAR, "bar" )
and then include this file in both your .h and .c files but
with MAGIC defined to produce the enum if it is a .h, and
produce the string table if it is a .c .

For the flags table, assuming your goal is compactness:
#define FT(X) P_##X = 1UL << PHASE_##X
enum
{ FT(FOO)
, FT(BAR)
, FT(QUX)
};
#undef FT

then the table will look like:
{ P_ALL_PASSED | P_PLAYING, YES, YES, YES, handle_card }
etc.

 

[David Thompson]

NB. 0xFFFFFFFF is already an unsigned int (unless you
are on a system where int is less than 32 bits, in which
the code is still correct but it will be a long or an unsigned
long).

Or int is more than 32 (nonpadding) bits in which case that fits in,
and is, signed int. (Although it would then safely promote to unsigned
int where needed in an expression, which is probably enough.)

enum
{ PHASE_NONE
, PHASE_FOO
, PHASE_BAR
, PHASE_QUX

BTW the canonical metaname is quux with two u's. Not to be confused
with two yous, two ewes, you toos, U-2s, yoohoos, tutus, or youse. <G>

- formerly david.thompson1 || achar(64) || worldnet.att.net