Mirror a Byte / X86 embedded assembly (in visual studio 2010)

Question

I am having trouble mirroring a byte and cannot find any techniques through google. What I am trying to accomplish is mirror the contents of a byte, aka: 10000000 = 00000001 10010111 = 11101001 etc...

I am using assembly embedded into C in Visual Studio 2010. Thank you in advanced for your time and help

Edit: Speed is not necessary, sorry for not pointing that out. It MUST be written in assembly.

Answer 1

As long as you don't care about speed, you can do a rotate right via carry (rcr) from your source, and a rotate left via carry (rcl) on your destination (or vice versa).

If you want it to be fast, just use a table lookup (since you only want one byte at a time, it'll only be a 256 byte table).

Answer 2

For a byte, use a lookup table. The table will fit in L1 cache and it will be fast.

For longer values, one can use shifting and masking in ways which make things faster than doing it one bit at a time. For instance, for 32-bit values:

uint32_t bit_reverse_32(uint32_t x)
{
    x = ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
    x = ((x & 0x33333333) << 2) | ((x >> 2) & 0x33333333);
    x = ((x & 0x0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F);
    x = ((x & 0x00FF00FF) << 8) | ((x >> 8) & 0x00FF00FF);
    x = (x << 16) | (x >> 16);
    return x;
}

Conversion of this C code into assembly is left as an exercise, or, even better, is left as a job for a C compiler, which does that kind of things for a living.

Answer 3

I assume from the fact that you've dropped to assembler level that you're after speed. If so, the fastest way to do this is via a lookup table. At which point, you don't need assembler (because it will be just as fast in C).

Note that many embedded platforms (typically DSPs) will have a native bit-reverse instruction. But this is probably of little use to you!

Answer 4

I'm not sure if you need to use assembly. Since you are already embedding assembly in C, you can make a simple lookup table in C and skip the assembly altogether...

byte const mirror[256] = {
0x00, 0x80, 0x40, 0xc0, ...
};

Answer 5

Divide and conqueror: divide the byte in half, flip the left half, flip the right half, then flip both halves. e.g., 10000100

divide: 1000 0100

left: 0001

right: 0010

both: 0010 0001

00100001

This reduces the size of the table from 256 bytes to 16 bytes so you can easily verify that it's doing the flip correctly, at the cost of some extra computation.

Answer 6

Here's a not-recommended solution, just for fun. I checked a few of the conversions but not all. Table-lookup is definitely the way to go and the accepted answer of rotating into and out of carry is what I've used in the past.

The solution below uses a multiplication to space the lower 4 bits into higher bits and then the modulus of a 2**n-1 number to roll the bits back down.

Here's a version in one step but uses 64 bit multiply: http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv

#include <stdlib.h>
#include <stdio.h>

int _tmain(int argc, _TCHAR* argv[])
{
    int x, y;

    for (x=0; x<256; x++)
    {

        // magic number / bit distribution way of flipping 4 bits
        // y = ((x * 0x00082082 & 0x01122408) % 255) >> 2;
        _asm 
        {
            mov ecx, x          // get operand
            mov eax, ecx        // get lower 4 bits into eax
            and eax, 0x0f
            mov ebx, 0x82082    // get magic multiplier into ebx
            imul eax, ebx       // distribute lower into upper bits
            and eax, 0x1122408  // and out the bits we want
            mov edx, 0          // initilialize upper DX:AX bits
            mov edi, 0xff       // modulo divisor
            idiv edi            // divide, leaving remainder in DX
            shr edx, 2          // adjust result
            mov esi, edx        // stash first half of flipped bits
            shl esi, 4

            // repeat with upper bits
            mov eax, ecx
            shr eax, 4
            imul eax, ebx
            and eax, 0x1122408
            mov edx, 0
            idiv edi
            shr edx, 2
            or edx, esi

            mov y, edx
        };

        printf("x %08x reverse %08x\n", x, y);
    }   

    return 0;
}