Go Down

### Topic: Bit Flipping Nibbles and Bytes (Read 14642 times)previous topic - next topic

#### filmo

##### Oct 22, 2009, 04:41 am
[size=12]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.)[/size]
Code: [Select]
`// 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;}`
[size=12]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 ??[/size]

#1
##### Oct 22, 2009, 07:05 am
Quote
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?

#### retrolefty

#2
##### Oct 22, 2009, 07:16 am
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

#### Fjornir

#3
##### Oct 22, 2009, 07:41 am
Couldn't this be done faster and easier with the ROL instruction?

#### AWOL

#4
##### Oct 22, 2009, 08:51 am
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.
I speak for myself, not Arduino.

#### TBAr

#5
##### Oct 24, 2009, 03:54 amLast Edit: Oct 24, 2009, 03:58 am by TBAr Reason: 1
Quote
Quote
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?

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

#### westfw

#6
##### Oct 24, 2009, 08:31 am
Quote
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.)

#### raron

#7
##### Oct 24, 2009, 02:25 pm
Quote
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

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

Code: [Select]
`int number = 3 ; // some number... int bits = 5 ; // nr of bits in some numberint 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.

#### kotoko

#8
##### Oct 26, 2009, 07:45 pm
Thanks for such an interesting post!

#### borref

#9
##### Oct 26, 2009, 08:48 pm
Here's another contribution which offers a good compromise between speed and size.
Code: [Select]
`// 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;    } `

#### crimony

#10
##### Oct 26, 2009, 11:56 pm
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.

#### raron

#11
##### Oct 27, 2009, 12:55 am
BenF: Beautiful algorithm!

#### westfw

#12
##### Oct 27, 2009, 05:34 am
Quote
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:
Code: [Select]
`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!)

#### Osgeld

#13
##### Oct 29, 2009, 04:45 am
care to explain that in [size=24]FULL[/size] detail please

#### westfw

#14
##### Oct 29, 2009, 08:34 am
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:
Code: [Select]
`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)`

Go Up