PIC Microcontoller Bit Math Method

Reverse bit order in a byte

to change b7 b6 b5 b4 b3 b2 b1 b0 to b0 b1 b2 b3 b4 b5 b6 b7.

Quickest

256 byte lookup table

Total Program Instructions: 2 + 256 Total Instructions Executed: 2

Most code efficient

A small, slower approach is to rotate the source byte right one bit (putting the rightmost bit in the carry flag), then rotate the destination byte left one bit (putting the carry flag in the rightmost bit of your destination register). Repeat this cycle 8 times. Your destination byte will have to be a temp register. Enter with byte to be reversed in WREG, exits with reversed byte in WREG. Reverse is trashed.

;**************************************
;SPIN by Jim Robertson
;enter byte to reverse in abuff.
;exit with reversed byte in bbuff
;KnownZero must be zero of course. Code will leave knownZero as 0

;(Do NOT use with interrupt driven code that may use KnownZero!)


               bsf KnownZero,3  ;count = 8
yyr6           rrf abuff
               rlf bbuff
               decfsz KnownZero
               goto yyr6


Total Program Instructions:  5 Total Instructions Executed: 26

This can, of course, be unrolled for faster execution at the cost of more code space.

RevWReg:
rlcf WREG,f 	; W   = d6 d5 d4 d3 d2 d1 d0 C  {C = d7}
rrcf Reverse,f 	; Rev = d7 R7 R6 R5 R4 R3 R2 R1 {C = R0}
rlcf WREG,f 	; W   = d5 d4 d3 d2 d1 d0 C  R0 {C = d6}
rrcf Reverse,f 	; Rev = d6 d7 R7 R6 R5 R4 R3 R2 {C = R1}
rlcf WREG,f 	; W   = d4 d3 d2 d1 d0 C  R0 R1 {C = d5}
rrcf Reverse,f 	; Rev = d5 d6 d7 R7 R6 R5 R4 R3 {C = R2}
rlcf WREG,f 	; W   = d3 d2 d1 d0 C  R0 R1 R2 {C = d4}
rrcf Reverse,f 	; Rev = d4 d5 d6 d7 R7 R6 R5 R4 {C = R3}
rlcf WREG,f 	; W   = d2 d1 d0 C  R0 R1 R2 R3 {C = d3}
rrcf Reverse,f 	; Rev = d3 d4 d5 d6 d7 R7 R6 R5 {C = R4}
rlcf WREG,f 	; W   = d1 d0 C  R0 R1 R2 R3 R4 {C = d2}
rrcf Reverse,f 	; Rev = d2 d3 d4 d5 d6 d7 R7 R6 {C = R5}
rlcf WREG,f 	; W   = d0 C  R0 R1 R2 R3 R4 R5 {C = d1}
rrcf Reverse,f 	; Rev = d1 d2 d3 d4 d5 d6 d7 R7 {C = R6}
rlcf WREG,f 	; W   = C  R0 R1 R2 R3 R4 R5 R6 {C = d0}
rrcf Reverse,w 	; W   = d0 d1 d2 d3 d4 d5 d6 d7 {C = R7}
return

Mike Harrison says:

.. or if you're short of registers, how about this :

  movlw 080
  movwf dest
 
loop
   rlf src
  rrf dest
  skpc ; loop until marker bit falls out the end
  goto loop  

Middle

;       Input X  = abcdefgh , Output X = hgfedcba
;       Written by Dmitry A. Kiryashov 2000
;       12 clocks/words

reverse8bit:

        swapf   X,W     ;efghabcd
        xorwf   X,W     ;efghabcd
                        ;abcdefgh

        andlw   0x66    ;.fg..bc.
                        ;.bc..fg.

        xorwf   X,F     ;afgdebch
;
        rrf     X,W
        rrf     X,F     ;hafgdebc
;
        andlw   0x55    ;.a.g.e.c
        addwf   X,F     ;h.f.d.b.
                        ;a.g.e.c.
        rrf     X,F     ;.h.f.d.b
                        ;.a.g.e.c

        addwf   X,F     ;ahgfedcb
;
        rlf     X,W
        rlf     X,F     ;hgfedcba
                        ;it can be replaced
                        ;with rlf X,W
                        ;if necessary...

Total Program Instructions: 7 + 19 Total Instructions executed: 13

eg.

        movf    original,w
        call      rev_nibble
        movwf result
        swapf     result,f
        swapf     original,w
        call      rev_nibble
        iorwf    result,f

  rev_nibble
        andlw    0x0F
        addwf    pcl,f
        retlw       00	;0000 -> 0000
        retlw       08	;0001 -> 1000
        retlw       04	;0010 -> 0100
        retlw       0C	;0011 -> 1100
        retlw       02	;0100 -> 0010
        retlw       0B	;0101 -> 1010
        retlw       06	;0110 -> 0110
        retlw       0E	;0111 -> 1110
        retlw       01	;1000 -> 0001
        retlw       09	;1001 -> 1001
        retlw       05	;1010 -> 0101
        retlw       0D	;1011 -> 1101
        retlw       03	;1100 -> 0011
        retlw       0B	;1101 -> 1011
        retlw       07	;1110 -> 0111
        retlw       0F	;1111 -> 1111

Mike Keitz says:

My challenge elicited many interesting results. For the benefit of those trying to lurk and learn, I'll summarize and try to explain. My apologies to any of the contributors I inadvertently don't give credit to.

There were 3 basic approaches to the problem, of which 2 are rather obvious and the third (maybe best) is obscure. The first approach is to shift bits out of the source bit LSB first and assemble them into the destination byte MSB first, like my hastily coded example did.

One problem with this is that the PIC shift instructions work only on RAM, not on the W register. So it's necessary to use two RAM bytes to process the results. Either a loop or an inline construct can be used to do the shifting. Since each shift is only 2 instructions / 2 cycles, the overhead in controlling the loop is the majority of processing time. But my application has a lot of time, so this isn't a problem. I liked Mike Harrison's solution using one of the bits in the destination to control the loop:

; Code based on Mike Harrison's entry:
        movwf   src     ;Store source
        movlw   b'00000010'     ;When the 1 falls out, done.
        movwf   dest
loop
        rrf     src             ;Take a bit out of src
        rlf     dest            ;and put it into dest
        skpc                    ;Did the 1 come out yet?
        goto    loop            ;No, do another bit.
        movfw   dest            ;Load result into W
        return                  ;and return

This routine is the best in terms of code words used: only 9. But it takes 7 trips through the loop to convert a character. Scott Dattalo claims that the shifting technique can be used in a pipeline fashion to convert two bytes at once. I'll take his word for it.

The next major approach I'll call the brute-force bit assembly technique. This uses bit tests of the source byte in RAM to OR bits into the proper positions in W. Most responders noticed that bit 3 is already in the proper position, so only 6 test/sets are required. Dimtry further refined the concept, realizing that using a swapf instruction on the byte would land 2 bits in the proper positions at the outset. This solution is decent, but holds no special advantage over the xor method which John Payson developed later in the game.

The xor method can be described as follows: Two bits A and B need to be reversed. They are in a byte AB. If A and B are both 1, or both 0, the byte doesn't need to be changed. If A and B are different, inverting both A and B will reverse them.

00 -> 00, 01 -> 10, 10 -> 01, 11 -> 11

The core of Payson's xor method works on pairs of bits. It xors the two source bits with each other to see if a change should be made. And it xors both bits (in W) with 1 if they are to be changed. This takes 4 PIC instructions (example is for bits 0 and 1):

        btfsc   src,0
        xorlw   b'11'
        btfsc   src,1
        xorlw   b'11'

If both source bits are 0, then neither xorlw executes, so W is unchanged. If both source bits are 1, then both xorlw's execute, causing both bits in W to remain at 1. If one bit is 1 and the other 0, then one xor executes. This inverts both bits in W, reversing them.

To reverse a 7 bit value, 3 pairs of bits need to be reversed. A direct application of the xor method takes 12 instructions (plus a couple to store and remove from RAM). Dmitry noticed again that a swapf instruction would place 2 bits in proper position, though it would move the fourth bit "D" (which doesn't need to move) out of position. Repairing this, then reversing the 2 remaining pairs of bits with the xor method, still saves a cycle over John's method. Dmitry's code, with my comments, is below.

        movwf   source          ;source = 0ABCDEFG
        swapf   source,w        ;W= DEFG0ABC
        btfsc   source,3        ; If D = 1,
         xorlw  0x88            ;convert now sure W= 0EFGDABC

        btfsc   source,6        ;Test bit A
         xorlw  0x05            ;Invert bits A and C
        btfsc   source,4        ;Test bit C
         xorlw  0x05            ;Invert bits A and C
                                ;now W = 0EFGDCBA
        btfsc   source,2        ;Do the same with E and G
         xorlw  0x50
        btfsc   source,0
         xorlw  0x50
                                ;so now W = 0GFEDCBA (done)
        return

This looks about the best if speed is critical. As a final thought on the matter, notice that the reversed result xor the starting value is always of the form 0abc0cba. There are only 8 ways to do the reverse. Bits abc are calculated as A xor G, B xor F, and C xor E. If there is an easy way to do this calculation and set up 0abc0cba in W, then a xorwf could reverse the bits in one fell swoop. Offhand, I couldn't find a way that does this faster than Dmitry's though. Maybe a small table could be of use.

Most Flexible

Nikolai Golovchenko says

;From the practical point of view, it's better to have ability to
;reassign pins in any order. I use pins masks always - it's easier to
;route PCB then.

        cblock
        In
        Out
        endc

#define A_MASK 1
#define B_MASK 2
#define C_MASK 4
#define D_MASK 8
#define E_MASK 16
#define F_MASK 32
#define G_MASK 64
#define H_MASK 128

        clrw
        btfsc In, 7
        iorlw A_MASK
        btfsc In, 6
        iorlw B_MASK
        btfsc In, 5
        iorlw C_MASK
        btfsc In, 4
        iorlw D_MASK
        btfsc In, 3
        iorlw E_MASK
        btfsc In, 2
        iorlw F_MASK
        btfsc In, 1
        iorlw G_MASK
        btfsc In, 0
        iorlw H_MASK
        movwf Out

Techniques for exploiting the parallelism of bitwise operations [incl bit reversals, counting, and Morton keys] by Ron Gutman

Comments:

• ~NOSPAM~haggart~NOSPAM~ at KILLspamslac.stanford.edu

  I'm totally new at this and I haven't yet tested my code, but I came up with this concept for word reversal before discovering this page and I can't see why it wouldn't work. It is for a PIC 16F870 with 4MHz crystal. It takes 2n+1 instructions, n being the number of bits you want to change, and one register file large enough to hold them.
  
  The idea is to first clear all bits (assign a value of 0) in the target word (the one which will end up reversed). You then use the PIC's bit test instruction (btfsc) to check each bit of the source word one at a time, to see if that bit is already a zero. If it is, you skip the next instruction, which is an unconditional bit set (bsf) pointing to the desired bit of the target word. Since you started out by filling the target word with 0s, you only need to use the bit-set instruction on those bits in the source word that contain 1s. And since each of these instructions is bit-specific, you can stuff the bits into the target word in any order you want, allowing word-reversal. My code is:
  
  clrf targetword
  btfsc sourceword,7
  bsf targetword,0
  btfsc sourceword,6
  bsf targetword,1
  btfsc sourceword,5
  bsf targetword,2
  btfsc sourceword,4
  bsf targetword,3
  btfsc sourceword,3
  bsf targetword,4
  btfsc sourceword,2
  bsf targetword,5
  btfsc sourceword,1
  bsf targetword,6
  btfsc sourceword,0
  bsf targetword,7; the register "targetword" now contains a reversed version of the register "sourceword"
  
  It seems to me that the execution speed will depend on the number of 1s and 0s in the source word. If you know that it's likely to contain more 1s than 0s most of the time, you could probably speed it up by first setting the target word to all 1s instead of all 0s, then using the btfss and bcf instructions instead of the btfsc and bsf instructions as above. The concept is the same.
  
  It also seems to me that this scheme can be used to create an ordered byte out of randomly-assigned I/O pins, making it easier to do board layouts. But again, I'm a complete newbie at this and I might be missing something. Please let me know if I am!
  
  -Craig Haggart
  Sunnyvale, California
  haggart@slac.stanford.edu
  

  +
• ~NOSPAM~reganryan~NOSPAM~ at KILLspamhotmail.com

  There is another method for reverse bit order in a byte that doesn't seem to be covered on this page http://www.piclist.com/techref/microchip/math/bit/revbits.htm and that's using hardware. Why not wire B0-B7 to C7-C0 respectively and execute the following: movf in,w movwf portc ; assuming that it is already set as output [nop] ; may not be necessary movf portb,w ; assuming that it is already set as input movwf out Presto! Only 4-5 instructions and no extra RAM required. regards, Regan Ryan

Christopher Wall Says:

I think one correction needs to be made to the following "Middle" method by Dmitry A. Kiryashov. As it is right now, it doesn't work when both 'a' and 'h' are '1'.

Example:

;   instruction   X           W           CarryBit
                  1010 0011   xxxx xxxx   x
    swapf   X,W   1010 0011   0011 1010   x   
    xorwf   X,W   1010 0011   1001 1001   x
    andlw   0x66  1010 0011   0000 0000   x
    xorwf   X,F   1010 0011   0000 0000   x
    rrf     X,W   1010 0011   1101 0001   x
    rrf     X,F   1101 0001   1101 0001   x
    andlw   0x55  1101 0001   0101 0001   x
    addwf   X,F   0010 0010   0101 0001   1
    rrf     X,F   0001 0001   0101 0001   1
    addwf   X,F   0110 0010   0101 0001   1
    rlf     X,W   0110 0010   1100 0100   1
    rlf     X,F   1100 0100   1100 0100   1

0b11000100 is not the reverse of 0b10100011 By changing the last "rrf" instruction to a rrcf (rotate file right through carry) this now opperated correctly:

;   instruction   X           W           CarryBit
                  1010 0011   xxxx xxxx   x
    swapf   X,W   1010 0011   0011 1010   x   
    xorwf   X,W   1010 0011   1001 1001   x
    andlw   0x66  1010 0011   0000 0000   x
    xorwf   X,F   1010 0011   0000 0000   x
    rrf     X,W   1010 0011   1101 0001   x
    rrf     X,F   1101 0001   1101 0001   x
    andlw   0x55  1101 0001   0101 0001   x
    addwf   X,F   0010 0010   0101 0001   1
    rrcf    X,F   1001 0001   0101 0001   0
    addwf   X,F   1110 0010   0101 0001   0
    rlf     X,W   1110 0010   1100 0101   0
    rlf     X,F   1100 0100   1100 0101   0

  .