Bit Flipping Nibbles and Bytes

Forum 2005-2010 (read only) Software Syntax & Programs
1

Byte = 8 bits, Nibble = 4 bits

Some times you need to flip a byte or nibble from LSB to MSB.

For example "1100 0101" to "1010 0011"

Took me a while to find this, so I thought I'd share. Any comments or improvements welcome. (I'm not an expert coder, so I'm sure one of you wizards can polish this quite a bit.)

// send nibbleShift a decimal number
// example "nibbleShift(3)" returns '12'
// "0011" becomes "1100"
int nibbleShift(int num) {
  int var = 0;     
  int i, x, y, p;
  int s = 4;    // number of bits in 'num'. (This case a 4bit nibble)

  for (i = 0; i < (s / 2); i++) {
    // extract bit on the left, from MSB
    p = s - i - 1;
    x = num & (1 << p);
    x = x >> p;  
    // extract bit on the right, from LSB
    y = num & (1 << i);
    y = y >> i;
  
    var = var | (x << i);       // apply x
    var = var | (y << p);       // apply y
  }
  return var;
}

To flip a whole byte, change the size of 's' to 8
Then if you input '3' you'll get '192' as the result.
"0000 0011" becomes "1100 000"

The other route with a nibble or byte flip is to do a table lookup. I'd be curious to hear what you think about which would be faster an the arduino; doing a table lookup or manually calculating it ??

2

Some times you need to flip a byte or nibble from LSB to MSB

The curiosity is killing me. When have you need to do this?

3

I recall once in the 80s where I had to flip the bits in a byte to get the CRC calculations to work for a communications link to a hardware remote telemetry unit (RTU), seems the device did their CRC generation in hardware and flipped the bits in relationship from the 'standard CRC-16' method. I did it in Turbo Pascal on a Kaypro CP/M system.

Lefty

4

Couldn't this be done faster and easier with the ROL instruction?

5

http://www.scribd.com/doc/2348626/Bit-Twiddling-Hacks

6

Some times you need to flip a byte or nibble from LSB to MSB

The curiosity is killing me. When have you need to do this?

During a job interview? :slight_smile:

for (byte i=0, byte j=7; i<8; ) { // adjust values for nibbles
  bitWrite(newbyte, i++, bitRead(oldbyte, j--)); // adjust bitRead offset for nibbles
}
7

Couldn't this be done faster and easier with the ROL instruction?

Yes, this is a good example of something where Assembler has a big advantage over C, just by virtue of being able to access the "carry" bit...

A table lookup is much faster, though. Even using progmem.

CRC algorithms tend to be bitwise symetric. If you had a byte-wide algorithm for calculating a CRC assuming that the bits of the input bytes were in one order, there was probably a very similar algorithm that would have allowed the input bytes to have the reverse bit order (possibly involving a bitswap of the final result.) Although to be honest, I think the last time I was faced with such a task, I gave up and did a bitwise CRC (which is easy to do in either direction.)

8

The curiosity is killing me. When have you need to do this?

The FFT algorithm for one involves some bit reversing early on. How those mathemagicians figured that one out I have no idea. That btw is probably why I haven't managed to implement FFT in arduino yet, so I took a break from it :stuck_out_tongue:

Extracting the relevant bits (pardon the pun) from the bit-reversing algorithm it should be something like this:

int number = 3 ; // some number... 
int bits = 5 ; // nr of bits in some number
int reversed = 0;
for ( int b=0 ; b < bits ; b++ ) reversed = ( reversed << 1 ) | ( 0x0001 & ( number >> b ) );

I hope I got that right. Then 3 (00011) should be 24 (11000), etc.. For more than 16 bits one should probably use "0x00000001 & ..." etc in the last part above (up to 32 bits).
How fast it is I don't know, and a table is probably always faster than some algorithm.

9

Thanks for such an interesting post!

10

Here's another contribution which offers a good compromise between speed and size.

// Reverse the order of bits in a byte. 
// I.e. MSB is swapped with LSB, etc. 
unsigned char Bit_Reverse( unsigned char x ) 
{ 
    x = ((x >> 1) & 0x55) | ((x << 1) & 0xaa); 
    x = ((x >> 2) & 0x33) | ((x << 2) & 0xcc); 
    x = ((x >> 4) & 0x0f) | ((x << 4) & 0xf0); 
    return x;    
}
11

My favourite resource for this type of thing is Jorg's fxt book: http://www.jjj.de/fxt/
A library is available too of course.

12

BenF: Beautiful algorithm! :slight_smile:

13

BenF: Beautiful algorithm!

Well, perhaps it's nice on a CPU that shifts more than one bit per instruction. On the AVR used in arduino, it compiles to significantly larger and slower code (well like 56 vs 36 bytes) than the obvious and inelegant assembler:

unsigned char bitswap (unsigned char x)
{
  byte result;

    asm("mov __tmp_reg__, %[in] \n\t"
      "lsl __tmp_reg__  \n\t"   /* shift out high bit to carry */
      "ror %[out] \n\t"  /* rotate carry __tmp_reg__to low bit (eventually) */
      "lsl __tmp_reg__  \n\t"   /* 2 */
      "ror %[out] \n\t"
      "lsl __tmp_reg__  \n\t"   /* 3 */
      "ror %[out] \n\t"
      "lsl __tmp_reg__  \n\t"   /* 4 */
      "ror %[out] \n\t"
      
      "lsl __tmp_reg__  \n\t"   /* 5 */
      "ror %[out] \n\t"
      "lsl __tmp_reg__  \n\t"   /* 6 */
      "ror %[out] \n\t"
      "lsl __tmp_reg__  \n\t"   /* 7 */
      "ror %[out] \n\t"
      "lsl __tmp_reg__  \n\t"   /* 8 */
      "ror %[out] \n\t"
      : [out] "=r" (result) : [in] "r" (x));
      return(result);
}

(tested! Has the same results as Bit_Reverse!)

14

care to explain that in FULL detail please

15

The "elegant" algorithm or the ugly assembly language?

For the assembler:
"lsl" is "Logical Shift Left." The bits of the register (tmp_reg) are shifted "upward" one place, and the most significant bit is shifted into the "carry" status flag, which you can sort of think of as a temporary 1-bit register.
So if you had 10100000 to start with, after the first shift you have 1 in the Carry bit, and 01000000 in the register.

"ror" is "rotate right through carry", which does exactly the reverse: the register (%[out]) is shifted right/downward, and the old value of the carry bit moves into the most significant bit of the register.
If THAT register had xyzxyzzz (random bits that we don't care about, really, because they'll all dissappear), after the first ror, it will contain 1xyzxyzz (the carry gets the bit that's shifted out, z, as well, but we don't care about that either, because the next lsl will overwrite it.)

So we're pushing the bits leftward out of our original register and rightward into a new register. After we've done this twice, the source register will have 10000000 and the destination 01xyzxyz. After the third time we have 00000000 and 101xyzxy. After 8 repetitions, we'll have 00000000 and 00000101, which is the reversed bit pattern that we wanted.

The somewhat odd formats of the register names (%[in], %[out], tmp_reg) and other bits of weird syntax (": [out] "=r" (result) : [in] "r" (x)") are FEATURES provided by the C compiler to permit assembler to co-exist and mix (and even optimize) with C/C++ code. They're best handled by having a big screen and calling up a relevant tutorial in another window; they certainly don't make the code particularly readable if you're only familiar with the syntax that Atmel defines and documents. "\n\t" is supposed to aid formatting in listings (newline, tab.) The whole thing would look a lot clearer in "pure" assembler, something like:

bitrev: ;;; Accept a byte in R24, reverse the bits and return the result in R24 as well.
        ;;; Uses R0 as a temporary register.
    mov R0, R24    ;copy our input value into R0
    lsl R0         ;shift input left into carry 
    ror R24        ;rotate carry right into output
    lsl R0
    ror R24
    lsl R0
    ror R24
    lsl R0
    ror R24       ; (4 bits done)
    lsl R0
    ror R24
    lsl R0
    ror R24
    lsl R0
    ror R24
    lsl R0
    ror R24      ; (8 bits done.  Finished!)
    ret          ; return with our result in R24 (R0 trashed)