Here are the results from a previous thread on this issue (which was actually about reversing 7 bits, so it might be a bit different.) Date: Thu, 30 Oct 1997 01:34:34 -0500 From: Mike Keitz Subject: Re: Challenge: Reverse 7 bits My cahllenge 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. Thanks for playing.