Fast and safe method for XOR folding

[robert.h.lowe]

Hi,

I'm looking for a computationally fast means of XOR folding
the individual bytes of an unsigned 32-bit int, and an unsigned
16-bit int. Can I point a char * at the address of each of
the int's (in succession), and safely access each byte?
Danger, danger, Will Robinsin!?? Any better ideas?? I'm
assuming this is faster than a series of 8-bit right shifts
followed by ORs with 255 as input to the XOR. E.g.

int i;
char *base;
uint32_t y = <blah>;
uint8_t x = 0;

base = (char *) &y;

for (i=0; i<4; i++) {
x ^= *(base+i);
}

(yes, differences in endianess will result in different byte ordering,
which might be important if only certain bytes were to be factored
into the result.)

versus

int i;
uint32_t y = <blah>;
uint8_t x = 0;

for (i=0; i<4; i++) {
x ^= ((t >> (8*i)) | 255); /* or some destructive variant for t */
/* ...to avoid the multiplication
*/
}

Also, should this result in too many collisions (as a hash key),
widening the space will have to result in shifts, e.g. 9 or 10-bits
plus a small number of bits left over... perhaps just better to do
it that way to begin with?

TIA,
Robert

 

[pete]

Hi,

I'm looking for a computationally fast means of XOR folding
the individual bytes of an unsigned 32-bit int, and an unsigned
16-bit int. Can I point a char * at the address of each of
the int's (in succession), and safely access each byte?
Danger, danger, Will Robinsin!?? Any better ideas?? I'm
assuming this is faster than a series of 8-bit right shifts
followed by ORs with 255 as input to the XOR. E.g.

int i;
char *base;

Make that

unsigned char *base;

unsigned char is the most appropriate type
for bitwise operations on bytes.
Having a sign bit introduces complications.

 

[Eric Sosman]

Hi,

I'm looking for a computationally fast means of XOR folding
the individual bytes of an unsigned 32-bit int, and an unsigned
16-bit int.

I can't find the 16-bit value in your example.

Can I point a char * at the address of each of
the int's (in succession), and safely access each byte?

Yes. As "pete" has already noted, though, it would be
better to use an `unsigned char*'.

Danger, danger, Will Robinsin!?? Any better ideas?? I'm
assuming this is faster than a series of 8-bit right shifts
followed by ORs with 255 as input to the XOR.

Such assumptions are (1) not justifiable in terms of the
C language, but only in terms of particular implementations,
and (2) stupid. Measure, measure, measure! (Better yet, ask
yourself how much difference it could possibly make. If you
shave three milliwiggles off the computation of a byte you
will then transmit via carrier pigeon, what have you saved?)

[...]
(yes, differences in endianess will result in different byte ordering,
which might be important if only certain bytes were to be factored
into the result.)

Thought exercise: Can you find four 8-bit values such that
the computed XOR of all four depends on the order in which they
are presented to the computation? (Incentive: If you find them,
you will have earned immortality as the person who exposed the
fundamental fallacies of Boolean algebra and overthrew the
foundations of computing. Everlasting fame -- go for it!)

Also, should this result in too many collisions (as a hash key),
widening the space will have to result in shifts, e.g. 9 or 10-bits
plus a small number of bits left over... perhaps just better to do
it that way to begin with?

I find myself unable to make sense of this paragraph. You
evidently have some sort of purpose in mind for this computation
on the bytes of an integer, and there's a hint that it might
have something to do with hashing -- but there's certainly not
enough information here for anyone to say whether X or Y is
"better."

 

[pete]

Eric Sosman wrote:

Thought exercise: Can you find four 8-bit values such that
the computed XOR of all four depends on the order in which they
are presented to the computation?

If you have a four byte unsigned type and a two byte
unsigned data type, both with no padding,
then it can be done with only 2 XOR operations,
by folding it in half, twice.

0x12u ^ 0x34 ^ 0x56 ^ 0x78 is 0x8
0x12345678 folded in half twice is 0x8
0x12345678 folded sequentialy is 0x8

/* BEGIN new.c */

#include <stdio.h>
#include <assert.h>
#include <limits.h>

int main(void)
{
long unsigned data = 0x12345678;
unsigned short temp;
unsigned char folded;

assert(sizeof(long) == 4 && sizeof(short) == 2
&& ULONG_MAX == 0xffffffff && USHRT_MAX == 0xffff);

printf("0x12u ^ 0x34 ^ 0x56 ^ 0x78 is 0x%x\n",
0x12u ^ 0x34 ^ 0x56 ^ 0x78);

temp = (unsigned short)
(*(unsigned short *)&data ^ *((unsigned short *)&data + 1));
folded = (unsigned char)
(*(unsigned char *)&temp ^ *((unsigned char *)&temp + 1));
printf("0x12345678 folded in half twice is 0x%x\n",
(unsigned)folded);

folded = (unsigned char)
(* (unsigned char *)&data
^ *((unsigned char *)&data + 1)
^ *((unsigned char *)&data + 2)
^ *((unsigned char *)&data + 3));
printf("0x12345678 folded sequentialy is 0x%x\n",
(unsigned)folded);


return 0;
}

/* END new.c */

 

[Peter Nilsson]

Hi,

I'm looking for a computationally fast means of XOR folding
the individual bytes of an unsigned 32-bit int, and an unsigned
16-bit int. ...

int i;
char *base;
uint32_t y = <blah>;
uint8_t x = 0;

base = (char *) &y;

for (i=0; i<4; i++) {
x ^= *(base+i);
}

(yes, differences in endianess will result in different byte ordering,
which might be important if only certain bytes were to be factored
into the result.)

You seem to be ignoring the golden rule that the person who wrote the
compiler is often a better programmer than you are (or I am.)

uint32_t y = <blah>;
uint32_t z = y ^ (y >> 16);
uint8_t x = z ^ (z >> 8);

As Eric says, measure, measure, measure.

 

[Robert]

I can't find the 16-bit value in your example.

It wasn't present, but the principle was.

Yes. As "pete" has already noted, though, it would be
better to use an `unsigned char*'.


Such assumptions are (1) not justifiable in terms of the
C language, but only in terms of particular implementations,
and (2) stupid. Measure, measure, measure! (Better yet, ask
yourself how much difference it could possibly make. If you
shave three milliwiggles off the computation of a byte you
will then transmit via carrier pigeon, what have you saved?)

Yes; the advice is well taken. Amdahls' law, work to make the
common case fast, etc. In this case, the carrier pigeons have
already come home to roost.

[...]
(yes, differences in endianess will result in different byte ordering,
which might be important if only certain bytes were to be factored
into the result.)

Thought exercise: Can you find four 8-bit values such that
the computed XOR of all four depends on the order in which they
are presented to the computation? (Incentive: If you find them,
you will have earned immortality as the person who exposed the
fundamental fallacies of Boolean algebra and overthrew the
foundations of computing. Everlasting fame -- go for it!)

No, but it is quite possible that a subset of the total number of
8-bit bytes contains more information and therefore yields a
better result. Therefore the computation might justifiably be
limited to those bytes, and they are on one end or the other
because the endianess of the underlying implementation, then it
makes a difference. Sorry -- I was vague. I am attempting to
learn through experimentation. If you are like all the people I
know, then you learned a lot the same way; if not maybe you
will be the immortal one.

I find myself unable to make sense of this paragraph. You
evidently have some sort of purpose in mind for this computation
on the bytes of an integer, and there's a hint that it might
have something to do with hashing -- but there's certainly not
enough information here for anyone to say whether X or Y is
"better."

I should not have asked for the value judgement -- I'll measure!
Thanks for the response, Eric!!!

-r