Simple Bitmask problem

P

Patrick

Hi there,

I have a simple problem to solve but somehow I am too stupid to figure
out where is the error.
Basically, I wanna shift each element of the array by an amount of n,
whereas the n highest
bits shifted out should be the n-least significant bits of the next
higher word. I tried doing this
by shifting the words the amount of n to the left which works fine. In
the next step I shift the lower
word 32-n positions to the right and OR the result with the higher
word which should add the then
bits I shifted out in the former step. Here is the code:

uint32 p_lo[] = { 0x00, 0x00, 0x00, 0x00 };

for (j = 0; j < 64; j ++ )
{
p_lo[0] <<= (j % 32);
p_lo[1] <<= (j % 32);
p_lo[1] |= (p_lo[0] >> (32 - (j % 32)));
}

Unfortuantely the outcome is nonsense... Anyone an idea what I am
missing?

Many thanks,
Patrick
 
E

Eric Sosman

Patrick wrote On 07/18/07 15:04,:
Hi there,

I have a simple problem to solve but somehow I am too stupid to figure
out where is the error.
Basically, I wanna shift each element of the array by an amount of n,
whereas the n highest
bits shifted out should be the n-least significant bits of the next
higher word. I tried doing this
by shifting the words the amount of n to the left which works fine. In
the next step I shift the lower
word 32-n positions to the right and OR the result with the higher
word which should add the then
bits I shifted out in the former step. Here is the code:

uint32 p_lo[] = { 0x00, 0x00, 0x00, 0x00 };

for (j = 0; j < 64; j ++ )
{
p_lo[0] <<= (j % 32);
p_lo[1] <<= (j % 32);
p_lo[1] |= (p_lo[0] >> (32 - (j % 32)));
}

Unfortuantely the outcome is nonsense... Anyone an idea what I am
missing?

It looks like you're missing more than one thing.
To begin with, it's extremely difficult to tell how
far you've shifted an array that holds only zeroes!
Also, the loop attempts to shift by 0+1+...+31+0+...+31
bit positions, or 992 places in all; no matter what
values you start with, there'll be nothing but zeroes
left when you're done.

Boyond that I can see two other possible problems,
one fundamental and the other a gotcha:

The fundamental problem is that when you left-
shift bits "off the high end" (or right-shift bits
"off the low end"), the "off the end" bits disappear.
You fetch a value from p_lo[0], left-shift it, and
then store the result back into p_lo[0] again -- and
now, there is no way to discover what the lost bits
were. You have lost all record of their values, and
your efforts to reconsistute them are hopeless. The
same goes for p_lo[1]: after the left-shift, the lost
bits are, well, lost. Lost forever.

If you want to preserve some of those bits, you
must not overwrite them until their values no longer
matter to you. Since you want to copy the "to be lost"
bits of p_lo[0] into the low-order positions of p_lo[1],
you must calculate p_lo[1] *before* losing the p_lo[0]
bits, not after.

The gotcha shows up in the way you attempt to merge
p_lo[0] bits into p_lo[1]. Consider what happens when
j % 32 is zero, that is, when j is 0 or 32. You will
attempt to right-shift the value from p_lo[0] by 32
bits, but the value only *has* 32 bits. In C, you can
only shift by an amount that is strictly *less* than
the width of the value; you can shift a 32-bit number by
0 bits, 1 bit, 2, bits, ..., 31 bits, but you cannot shift
it by 32 bits. Exactly what happens when you try it
depends on how the machine happens to perform shifts: Some
will happily shift 32 places to the right and yield zero
(which is what you want, but C doesn't guarantee it), some
will act as if you had right-shifted by zero places, and
some may do even less predictable things ("make demons fly
out of your nose"). It's a boundary case where C just
throws up its hands and lets the hardware do whatever it
feels like -- so if you don't want to be at the mercy of
the hardware's whim, you had better not attempt the too-
wide shift.
 
P

pete

Patrick said:
Hi there,

I have a simple problem to solve but somehow I am too stupid to figure
out where is the error.
Basically, I wanna shift each element of the array by an amount of n,
whereas the n highest
bits shifted out should be the n-least significant bits of the next
higher word. I tried doing this
by shifting the words the amount of n to the left which works fine. In
the next step I shift the lower
word 32-n positions to the right and OR the result with the higher
word which should add the then
bits I shifted out in the former step. Here is the code:

uint32 p_lo[] = { 0x00, 0x00, 0x00, 0x00 };

for (j = 0; j < 64; j ++ )
{
p_lo[0] <<= (j % 32);
p_lo[1] <<= (j % 32);
p_lo[1] |= (p_lo[0] >> (32 - (j % 32)));
}

Unfortuantely the outcome is nonsense... Anyone an idea what I am
missing?

/* BEGIN new.c output */

D_Word[0] is 0x12345678
D_Word[1] is 0x9abcdef0
LEFT_SHIFT 12
D_Word[0] is 0x45678000
D_Word[1] is 0xcdef0123

/* END new.c output */


/* BEGIN new.c */

#include <stdio.h>

#define LEFT_SHIFT 12

int main(void)
{
long unsigned D_Word[] = {0x12345678, 0x9abcdef0};

puts("/* BEGIN new.c output */\n");
printf("D_Word[0] is 0x%x\n", D_Word[0]);
printf("D_Word[1] is 0x%x\n", D_Word[1]);
puts("LEFT_SHIFT 12");
D_Word[1] <<= LEFT_SHIFT;
D_Word[1] |= D_Word[0] >> 32 - LEFT_SHIFT;
D_Word[0] <<= LEFT_SHIFT;
printf("D_Word[0] is 0x%x\n", D_Word[0]);
printf("D_Word[1] is 0x%x\n", D_Word[1]);
puts("\n/* END new.c output */");
return 0;
}

/* END new.c */
 
T

Thad Smith

Patrick said:
Basically, I wanna shift each element of the array by an amount of n,
whereas the n highest
bits shifted out should be the n-least significant bits of the next
higher word. I tried doing this
by shifting the words the amount of n to the left which works fine. In
the next step I shift the lower
word 32-n positions to the right and OR the result with the higher
word which should add the then
bits I shifted out in the former step. Here is the code:

uint32 p_lo[] = { 0x00, 0x00, 0x00, 0x00 };

for (j = 0; j < 64; j ++ )
{
p_lo[0] <<= (j % 32);
p_lo[1] <<= (j % 32);
p_lo[1] |= (p_lo[0] >> (32 - (j % 32)));
}

Unfortuantely the outcome is nonsense... Anyone an idea what I am
missing?

In my opinion, the most important missing item is a rigorous
specification. Off the top of my head, I expect to know what input to
be shifted, the number of bits to shift, the shift count, what bits are
shifted in, the type of array elements, how many bits are in each array
element, and which array element is considered the most significant.

Given a rigorous specification, you could write the function code and I
could write a test determine if the code works as specified without
looking at the code. Try writing a synopsis for your shift function
that includes a full specification. Writing, testing, and using the
code then becomes a lot easier. ;-)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top