RE: [Algorithms] Byte Swapping

[Daniel K. <Dan...@ix...>]

Hi Listizens,

well, if you look at the line
y = (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF) ^ (x<<8);

especially at the first xor op
(x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF)

then you see that the result of the first assignment
(x = x>>16 | x<<16), let's call it 'z'

is used in the calculation of the second term
(x = (x^x>>8) & 0x00FF00FF)   or   (x = (z^z>>8) & 0x00ff00ff)

The new result will overwrite the old content of x (which was z),
i.e. the whole operation
y = (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF) ^ (x<<8)

doesnt equal y = z ^ x ^ (x<<8) as expected
but y = x ^ x ^ (x<<8)   which basically is  y = 0 ^(x<<8) = (x<<8) !

That gets us
x = 0x01020304
new x #1 (=z) = 0x03040102
new x #2 = (0x03040102 ^ 0x00030401) & 0x00ff00ff = 0x00070003
y = 0 ^ (0x00070003<<8) = 0x07000300.


When you write it as
y = x = (x>>16)|(x<<16);
y ^= (x = ((x^(x>>8)) & 0x00FF00FF));
y ^= (x<<8);

the 'z' from above is stored in 'y' as well.
That's why the threeliner gives the correct result...


Cheers,

Daniel.


> -----Original Message-----
> From: Charles Bloom [mailto:cb...@cb...]
> Sent: Tuesday, July 18, 2000 4:50 AM
> To: gda...@li...
> Subject: Re: [Algorithms] Byte Swapping
> 
> 
> 
> Hmm... I'm not sure what's wrong with it, it's some C order 
> of operations
> problem
> that I'm not familiar with.  If you expand it out into simple steps :
> 
> y = x = (x>>16)|(x<<16);
> y ^= (x = ((x^(x>>8)) & 0x00FF00FF));
> y ^= (x<<8);
> 
> then it works just fine.  If you have four bytes ABCD, the first line
> turns them into CDAB.  The second line gives you (0D0B^0C0A).  The
> last line is thus (D0B0^C0A0).  Put them all together :
> 
> y = CDAB^0D0B^0C0A^D0B0^C0A0 = DCBA
> 
> Anyway, this is all just a curiosity because I don't think that's the
> most efficient way to do it :^)
> 
> At 12:36 PM 7/18/2000 +1000, you wrote:
> >It looks like the way this is meant to work is that it swaps 
> the top and
> >bottom 16 bits then proceeds to do the old 3 xor byte swapping  trick
> >(x^=y^=x) for each of the two 16 bit segments but I think 
> the code is a
> >little bit broken. I can't see how that second bit works.
> >
> >
> >-----Original Message-----
> >From: brian sharon <br...@hu...>
> >To: gda...@li...
> ><gda...@li...>
> >Date: Tuesday, 18 July 2000 12:02
> >Subject: Re: [Algorithms] Byte Swapping
> >
> >
> >>
> >>> From: Charles Bloom <cb...@cb...>
> >>>
> >>> Jumping in late : I'm sure you don't need it now, but
> >>> here's a crazy ANSI C byte-swapper :
> >>>
> >>> let x = a 32 bit ulong , ABCD
> >>> then y = DCBA
> >>>
> >>> y = (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF) ^ (x<<8);
> >>>
> >>
> >>wow, I'll say that's crazy...but unfortunately 
> non-functional.  see the
> >>results of this program:
> >>
> >>#include <stdio.h>
> >>
> >>long swap1(long x)
> >>{
> >>    return (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 
> 0x00FF00FF) ^ (x<<8);
> >>}
> >>
> >>long swap2(long x)
> >>{
> >>    return         ((x >> 24) & 0x000000FF)
> >>            |    ((x >> 8 ) & 0x0000FF00)
> >>            |    ((x << 8 ) & 0x00FF0000)
> >>            |    ((x << 24) & 0xFF000000)
> >>            ;
> >>}
> >>
> >>int main(int argc, char **argv)
> >>{
> >>    long test = 0x01020304;
> >>
> >>    printf("swap1: 0x%08X 0x%08X 0x%08X \n", test, swap1(test),
> >>swap1(swap1(test)));
> >>
> >>    printf("swap2: 0x%08X 0x%08X 0x%08X \n", test, swap2(test),
> >>swap2(swap2(test)));
> >>}
> >>
> >>swap1: 0x01020304 0x07000300 0x03000700
> >>swap2: 0x01020304 0x04030201 0x01020304
> >>
> >>
> >>
> >
> [snip]
>