look up tables

[Mike]

Hi

I would like to realise a simple lookup table in C. I have
got a const array with 16 values. I have 4 input values of
type integer with 32 bits. I loop then over the single bits
and in each iteration I would like to use the current 4 bits
of the 4 input operands to make a table lookup. I thought of
doing it with bitmasks. Is this a nice way to do it or is there
a more efficient way?

int LUT[16] = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

int A.B,C,D = rand();
int mask = 1;

int i;
int tmp;
for(i = 0; i < 32; i++) {
tmp = 8*(A & mask) + 4*(B & mask) + 2*(C & mask)+ (D & mask);
lookup_val[i] = LUT[tmp];
mask<<1;
}

Many thanks

[Eric Sosman]

Mike wrote On 11/29/07 12:34,:

Hi

I would like to realise a simple lookup table in C. I have
got a const array with 16 values. I have 4 input values of
type integer with 32 bits. I loop then over the single bits
and in each iteration I would like to use the current 4 bits
of the 4 input operands to make a table lookup. I thought of
doing it with bitmasks. Is this a nice way to do it or is there
a more efficient way?

int LUT[16] = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

int A.B,C,D = rand();
int mask = 1;

int i;
int tmp;
for(i = 0; i < 32; i++) {
tmp = 8*(A & mask) + 4*(B & mask) + 2*(C & mask)+ (D & mask);
lookup_val[i] = LUT[tmp];
mask<<1;
}

Many thanks

[Eric Sosman]

(Apologies for the earlier incomplete reply.)

Mike wrote On 11/29/07 12:34,:

Hi

I would like to realise a simple lookup table in C. I have
got a const array with 16 values. I have 4 input values of
type integer with 32 bits. I loop then over the single bits
and in each iteration I would like to use the current 4 bits
of the 4 input operands to make a table lookup. I thought of
doing it with bitmasks. Is this a nice way to do it or is there
a more efficient way?

int LUT[16] = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

int A.B,C,D = rand();

Peculiar syntax ...

int mask = 1;

int i;
int tmp;
for(i = 0; i < 32; i++) {
tmp = 8*(A & mask) + 4*(B & mask) + 2*(C & mask)+ (D & mask);

Note that this calculation will not necessarily yield a
value in the range 0..15. (Hint: What happens on the second
iteration, if A is equal to 2?)

lookup_val[i] = LUT[tmp];

Since LUT[tmp] == tmp for all valid tmp, why bother with
a lookup table at all?

mask<<1;

This will make trouble the last two times through the
loop. At the end of the i==30 iteration you'll try to
double a `mask' value that is bigger than half the maximum
possible `int' value, so the result won't fit in an `int'
(assumed to be 32 bits in this case). Pretty much anything
at all can happen, but the most likely outcome is that
`mask' will become a very large *negative* number -- and
this will raise yet another kind of Hell with the calculation
of `tmp' the next time through the loop.

On the final iteration, you'll try to double that very
large negative `mask', and again the result will be out of
range for an `int', and again anything at all might happen.

This is why bit-fiddling is almost always done with
`unsigned' types, where there are no sign bits to cause
trouble.

}

--
Er*********@sun.com

[Joe]

On Nov 29, 12:34 pm, Mike <[e-mail]:

Hi

I would like to realise a simple lookup table in C. I have
got a const array with 16 values. I have 4 input values of
type integer with 32 bits. I loop then over the single bits
and in each iteration I would like to use the current 4 bits
of the 4 input operands to make a table lookup. I thought of
doing it with bitmasks. Is this a nice way to do it or is there
a more efficient way?

int LUT[16] = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

int A.B,C,D = rand();
int mask = 1;

int i;
int tmp;
for(i = 0; i < 32; i++) {
tmp = 8*(A & mask) + 4*(B & mask) + 2*(C & mask)+ (D & mask);
lookup_val[i] = LUT[tmp];
mask<<1;

}

Many thanks

I think you are assuming that "(A & mask)" is a boolean, returning 0
or 1. It is not. Maybe do this instead:
tmp = ((A & mask)?8:0) | ((B & mask)?4:0) | ((C & mask)?2:0) | ((D
& mask)?1:0);

There may be a better way to to this in assembly, which often has
various bit shifting/fiddling functions. In C, you have to rely on the
optimizer to make use of assembly features. So, if speed is critical,
the best approach is just to try it a few different ways and time it.

Joe Krahn

[CBFalconer]

Mike wrote:

>
I would like to realise a simple lookup table in C. I have
got a const array with 16 values. I have 4 input values of
type integer with 32 bits. I loop then over the single bits
and in each iteration I would like to use the current 4 bits
of the 4 input operands to make a table lookup. I thought of
doing it with bitmasks. Is this a nice way to do it or is there
a more efficient way?

int LUT[16] = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

int A.B,C,D = rand();
int mask = 1;

int i;
int tmp;
for(i = 0; i < 32; i++) {
tmp = 8*(A & mask) + 4*(B & mask) + 2*(C & mask)+ (D & mask);
lookup_val[i] = LUT[tmp];
mask<<1;
}

Hasn't a chance of working. To start with, why are you declaring
the B field of A? Anyhow, A.B and C are initialized to random
values, and D is initialized to a random value with an undeclared
routine (no #includes shown). Then you are using struct A, and
later field B, as integers. Then you are left shifting an integer,
that is initialized to 1, 32 times and discarding the result.
Almost certainly that causes an overflow and undefined behaviour or
it does absolutely nothing.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

[Philip Potter]

CBFalconer wrote:

Mike wrote:

>I would like to realise a simple lookup table in C. I have
got a const array with 16 values. I have 4 input values of
type integer with 32 bits. I loop then over the single bits
and in each iteration I would like to use the current 4 bits
of the 4 input operands to make a table lookup. I thought of
doing it with bitmasks. Is this a nice way to do it or is there
a more efficient way?

int LUT[16] = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

int A.B,C,D = rand();
int mask = 1;

int i;
int tmp;
for(i = 0; i < 32; i++) {
tmp = 8*(A & mask) + 4*(B & mask) + 2*(C & mask)+ (D & mask);
lookup_val[i] = LUT[tmp];
mask<<1;
}

Hasn't a chance of working. To start with, why are you declaring
the B field of A? Anyhow, A.B and C are initialized to random
values,

They are /not/ initialized to any value at all. Not even a "random"
value, which is a confusing term in this context. Whatever value they
happen to start with cannot be used in a strictly conforming program.

and D is initialized to a random value with an undeclared
routine (no #includes shown).

That's fair enough, because this is not a complete program, it's a code
snippet, as evidenced by the for loop outside of a function.

Then you are using struct A, and
later field B, as integers.

In clearer words, "You misspelled A,B,C,D as A.B,C,D".

Then you are left shifting an integer,
that is initialized to 1, 32 times and discarding the result.
Almost certainly that causes an overflow and undefined behaviour or
it does absolutely nothing.

1<<1 cannot possibly cause an overflow, and no other shifting takes
place in the program. (I hadn't noticed that he was discarding the
result, good catch.)