Thread: Swap Byte

Hello,

Help needed to optimize following program.

Code:

	int num,i, byte =0;

	printf(" Enter the number\n");
	scanf("%d",&num);
	printf("Number is %x\n",num);
	
	i = 0;
	
	do
	{
		if (num%2)
		{
			byte = byte << 1;
			byte |= 0x01;
		}
		else
			byte = byte << 1;

		num = num>>1; 
		i++;
	} while(i&7);
	printf("Reversed number = %x and %d \n",byte, i);
}

Thanks,
Tiger

What i am looking at is,

1. Loop takes 8 iterations, even if most significant bits are 0. Any logic that avoid unncessary iteration.

2. There are no division in above program. Any replcacement for mod is greately apppreciated.

Let me know.

tiger

Originally posted by Roaring_Tiger
1. Loop takes 8 iterations, even if most significant bits are 0. Any logic that avoid unncessary iteration.
2. There are no division in above program. Any replcacement for mod is greately apppreciated.

A lookup table and other techniques are suggested in the following thread. Addressing your two questions, is something like the following what you had in mind?

Code:

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

unsigned char foo(unsigned char value)
{
    unsigned char mask = 1 << (CHAR_BIT - 1), result = 0;
    while(value) /* skip most significant bits that are zero */
    {
        if(value & 1) /* replace mod (machine dependency) */
        {
            result |= mask;
        }
        mask  >>= 1;
        value >>= 1;
    }
    return result;
}

int main(void)
{
    unsigned char value = 5;
    printf("value = %X, reversed = %X\n", value, foo(value));
    return 0;
}

/* my output
value = 5, reversed = A0
*/

I rarely find the use of bitfields to be an optimization when it comes to speed because what appears to be a simple assignment is often implmented by masking and shifting. For example,

Code:

   ;
   ;        b.sbyte.u5 = a.sbyte.u2;
   ;
        mov       cl,byte ptr [ebp-1]
        shr       ecx,2
        and       ecx,1
        and       cl,1
        shl       ecx,5
        mov       dl,byte ptr [eax]
        and       dl,-33
        or        cl,dl
        mov       byte ptr [eax],cl

Bitfields may pack data more tightly, but this size benefit may be taken at the cost of speed. Some exceptions might be on architectures that actually have bit-addressable memory in which an assignment would be an assignment.

I had run a little comparison, which is less than perfect, but is as follows.

Code:

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

unsigned char foo(unsigned char value)
{
    unsigned char mask = 1 << (CHAR_BIT - 1), result = 0;
    while ( value ) /* skip most significant bits that are zero */
    {
        if ( value & 1 ) /* replace mod (machine dependency) */
        {
            result |= mask;
        }
        mask  >>= 1;
        value >>= 1;
    }
    return result;
}

unsigned char bar(unsigned char num)
{
    unsigned char byte = 0;
    int i = 0;
    do
    {
        if ( num % 2 )
        {
            byte = byte << 1;
            byte |= 0x01;
        }
        else
            byte = byte << 1;

        num = num >> 1;
        i++;
    } while ( i & 7 );
    return byte;
}

unsigned char baz(unsigned char value)
{
    union byteu
    {
        unsigned char byte;
        struct
        {
            unsigned char u0:1;
            unsigned char u1:1;
            unsigned char u2:1;
            unsigned char u3:1;
            unsigned char u4:1;
            unsigned char u5:1;
            unsigned char u6:1;
            unsigned char u7:1;
        } sbyte;
    } a, b;

    a.byte = value;

    b.sbyte.u7 = a.sbyte.u0;
    b.sbyte.u6 = a.sbyte.u1;
    b.sbyte.u5 = a.sbyte.u2;
    b.sbyte.u4 = a.sbyte.u3;
    b.sbyte.u3 = a.sbyte.u4;
    b.sbyte.u2 = a.sbyte.u5;
    b.sbyte.u1 = a.sbyte.u6;
    b.sbyte.u0 = a.sbyte.u7;

    return b.byte;
}

#define CYCLES 100000000

int main(void)
{
    const char *name[] = { "foo", "bar", "baz" };
    unsigned char (*const function[])(unsigned char) = { foo, bar, baz };
    unsigned char value = 5;
    size_t i,j;
    printf("foo(%X) = %X\n", value, foo(value));
    printf("bar(%X) = %X\n", value, bar(value));
    printf("baz(%X) = %X\n", value, baz(value));
    fflush(stdout);
    for ( i = 0; i < sizeof(function)/sizeof(*function); ++i )
    {
        clock_t end, start = clock();
        for ( j = 0; j < CYCLES; ++j )
        {
            function [ i ] (j);
        }
        end = clock();
        printf("%s = %f\n", name [ i ], (end - start) / CLOCKS_PER_SEC);
        fflush(stdout);
    }

    return 0;
}

Here are the results I obtained.

Code:

foo(5) = A0
bar(5) = A0
baz(5) = A0
foo = 9.614000
bar = 12.738000
baz = 17.766000

If optimizing for speed was the goal, this bitfields implementation was 39% slower than the original.

[OT]
>Vola.
Perhaps you mean voilà.
[/OT]

Originally posted by Sebastiani
Quzahs solution completes the task in less than a dozen operations - all of them assignment, none are comparisons either. That is what makes this solution superior. You have comparisons for loop bounds, lots of arithametic and so forth, which make for a more intensive program and hence, longer code segments, more register accesses, long math, etc.

I guess you missed a point I was trying to make: this solution may be "superior" on one implementation, and inferior on another (as in the example I gave).

Two specific questions Roaring_Tiger asked were how to avoid unnecessary loop iterations and how to avoid a division. These were the points I addressed. Since quzah already showed an alternate approach, I tried to answer Roaring_Tiger's question as posted -- and offered a comparison to quzah's code. Note that in the implementation I tested, the loop with comparisons was faster than the bitfields. Surely this is a quality of implementation issue, but definitely something worth mention.

If you really want to trim things down to minimal operations, why ignore the lookup table approach found in the link I posted? There you would have only one assignment. Or using similarly unrolled loops, the comparisons and explicit shift operations may be faster than bitfield assignment. On not. Again, I find it relevant to at least mention this.

Generalizing that certain C contructs will always generate optimum code is not a wise thing to do.

Hi all!

Just one question: what happened to the "standard" solution for this problem?

Code:

unsigned char quux(unsigned char value)
{
   value = ((value&0xaa)>>1) | ((value&0x55)<<1);
   value = ((value&0xcc)>>2) | ((value&0x33)<<2);
   return (value>>4) | (value<<4);
}

I found this one still a bit faster:

Code:

unsigned char quuux(unsigned char value)
{
   static unsigned char tab[16]=
         {0x0,0x8,0x4,0xc,0x2,0xa,0x6,0xe,
          0x1,0x9,0x5,0xd,0x3,0xb,0x7,0xf};
   return (tab[value&0xf]<<4) | (tab[value>>4]);
}

I got (on a 1000MHz Athlon):

Code:

foo(5) = A0
bar(5) = A0
baz(5) = A0
quux(5) = A0
quuux(5) = A0
baseline(5) = 0
foo = 9.210000
bar = 9.980000
baz = 3.340000
quux = 1.950000
quuux = 1.730000
baseline = 1.130000

Where the function baseline is obviously wrong, but shows the cost of the function call itself:

Code:

unsigned char baseline(unsigned char value)
{
   return 0;
}

If I change the inner loop to call the function quux directly, instead of indirectly, it runs in 0.6 seconds:

Code:

        volatile int result;
        clock_t end, start = clock();
        for ( j = 0; j < CYCLES; ++j )
        {
           result=quuux(j);
        }
        end = clock();

Where the variable result is marked volatile, to make sure that the compiler really calls the function quuux... (it automatically inlined the function and then optimized it out alltogether)

Have fun,
alex