Post by thread:Challenge: Reverse 7 bits

There hasn't been a "programming challenge" lately. Here's a problem I'm looking at: I have a 7 bit ASCII character which was transmitted serially LSB first, but received MSB first. Thus, I need to reverse the order of the bits (I can't change the receiver, since other parts of the data are transmitted MSB first). For example, 0011010 should come out as 0101100. The routine should be a subroutine which gets the input value in W and returns the result in W. It is OK to assume the high bit of W will be 0, and the high bit of the result must be 0 (the routine works only on the low 7 bits) The obvious answer is a lookup table of 128 entries, but this is a big portion of the code space in an '84. Speed is not important, so I'm going to replace the lookup table with an "analytical" method. Here's a completely arbitrary scoring scheme which favors using less ROM and RAM (low score is better): Each ROM location used : 8 points Each RAM location used : 30 points Each instruction cycle (to convert once): 1 point Uses less than 25 instruction cycles: -40 points Under these rules, the lookup table scores a whopping 998 points, though it does qualify for the speed bonus. My first attempt at a solution (below) is 211 points (10 ROM, 3 RAM, 41 cycles). The 30 point penalty for RAM should encourage you to look for a way that doesn't use 3 RAM locations (it shouldn't be too hard to use W as a loop counter, for example). ; revbits ; Reverses the low 7 bits of a byte. The eighth bit in is ignored, out is 0. ; Input/output in W. Uses tmp, tmp2, ii. revbits movwf tmp ;Store input value. movlw .7 ;Loop count movwf ii clrf tmp2 ;Be sure bit 7 of output is 0. revbitsl rrf tmp,f ;Get an input bit rlf tmp2,f ;Put to output. decfsz ii,f goto revbitsl movfw tmp2 ;Load output value into W. return

On Wed, 29 Oct 1997 10:50:06 -0500, you wrote: >There hasn't been a "programming challenge" lately. Here's a problem I'm >looking at: I have a 7 bit ASCII character which was transmitted >serially LSB first, but received MSB first. Thus, I need to reverse the >order of the bits (I can't change the receiver, since other parts of the >data are transmitted MSB first). For example, 0011010 should come out as >0101100. The routine should be a subroutine which gets the input value >in W and returns the result in W. It is OK to assume the high bit of W >will be 0, and the high bit of the result must be 0 (the routine works >only on the low 7 bits) >Each ROM location used : 8 points >Each RAM location used : 30 points >Each instruction cycle (to convert once): 1 point >Uses less than 25 instruction cycles: -40 points > Compact version : 9 rom, 2 ram, 40 cycles - 172 points movwf temp movlw 2 ; end marker movwf temp2 loop rrf temp rlf temp2 skpc goto loop ; loop until bit falls out end movf temp2,w return Fast & low RAM version : 17 rom, 1 ram, 18 cycles - 144 points movwf temp clrw btfsc temp,0 iorlw 040 btfsc temp,1 iorlw 020 btfsc temp,2 iorlw 010 btfsc temp,3 iorlw 008 btfsc temp,4 iorlw 004 btfsc temp,5 iorlw 002 btfsc temp,6 iorlw 001 return

At 10:50 AM 29/10/97 -0500, you wrote: {Quote hidden}>There hasn't been a "programming challenge" lately. Here's a problem I'm >looking at: I have a 7 bit ASCII character which was transmitted >serially LSB first, but received MSB first. Thus, I need to reverse the >order of the bits (I can't change the receiver, since other parts of the >data are transmitted MSB first). For example, 0011010 should come out as >0101100. The routine should be a subroutine which gets the input value >in W and returns the result in W. It is OK to assume the high bit of W >will be 0, and the high bit of the result must be 0 (the routine works >only on the low 7 bits) > >The obvious answer is a lookup table of 128 entries, but this is a big >portion of the code space in an '84. Speed is not important, so I'm >going to replace the lookup table with an "analytical" method. Here's a >completely arbitrary scoring scheme which favors using less ROM and RAM >(low score is better): > >Each ROM location used : 8 points >Each RAM location used : 30 points >Each instruction cycle (to convert once): 1 point >Uses less than 25 instruction cycles: -40 points a real dirty solution: revbits movwf tmp andlw 0x08 btfsc tmp,0 iorlw 0x40 btfsc tmp,1 iorlw 0x20 btfsc tmp,2 iorlw 0x10 btfsc tmp,4 iorlw 0x04 btfsc tmp,5 iorlw 0x02 btfsc tmp,6 iorlw 0x01 RAM 1 * 30 = 30 ROM 14 * 8 = 112 Cycle 14 * 1 = 14 ================== SCORE: 156 Correct? add some points for Return if needed antti http://avrbasic.com -- AVR Basic Compiler http://sistudio.com/bswfe -- Basic Stamp Windows Front End

> On Wed, 29 Oct 1997 10:50:06 -0500, you wrote: > > >There hasn't been a "programming challenge" lately. Here's a problem I'm > >looking at: I have a 7 bit ASCII character which was transmitted > >serially LSB first, but received MSB first. Thus, I need to reverse the > >order of the bits (I can't change the receiver, since other parts of the > >data are transmitted MSB first). For example, 0011010 should come out as > >0101100. The routine should be a subroutine which gets the input value > >in W and returns the result in W. It is OK to assume the high bit of W > >will be 0, and the high bit of the result must be 0 (the routine works > >only on the low 7 bits) > > > >Each ROM location used : 8 points > >Each RAM location used : 30 points > >Each instruction cycle (to convert once): 1 point > >Uses less than 25 instruction cycles: -40 points > > > [snip] {Quote hidden}> > Fast & low RAM version : 17 rom, 1 ram, 18 cycles - 144 points > > movwf temp > clrw > btfsc temp,0 > iorlw 040 > btfsc temp,1 > iorlw 020 > btfsc temp,2 > iorlw 010 You can leave out this one - its already in the corect place. {Quote hidden}> btfsc temp,3 > iorlw 008 > btfsc temp,4 > iorlw 004 > btfsc temp,5 > iorlw 002 > btfsc temp,6 > iorlw 001 > return Gives you 15 ROM, 1 RAM, 16 Cycles = 126 points Niki

In a message dated 97-10-29 11:06:58 EST, you write: {Quote hidden}> There hasn't been a "programming challenge" lately. Here's a problem I'm > looking at: I have a 7 bit ASCII character which was transmitted > serially LSB first, but received MSB first. Thus, I need to reverse the > order of the bits (I can't change the receiver, since other parts of the > data are transmitted MSB first). For example, 0011010 should come out as > 0101100. The routine should be a subroutine which gets the input value > in W and returns the result in W. It is OK to assume the high bit of W > will be 0, and the high bit of the result must be 0 (the routine works > only on the low 7 bits) > > The obvious answer is a lookup table of 128 entries, but this is a big > portion of the code space in an '84. Speed is not important, so I'm > going to replace the lookup table with an "analytical" method. Here's a > completely arbitrary scoring scheme which favors using less ROM and RAM > (low score is better): > > Each ROM location used : 8 points > Each RAM location used : 30 points > Each instruction cycle (to convert once): 1 point > Uses less than 25 instruction cycles: -40 points > > Under these rules, the lookup table scores a whopping 998 points, though > it does qualify for the speed bonus. My first attempt at a solution > (below) is 211 points (10 ROM, 3 RAM, 41 cycles). The 30 point penalty > for RAM should encourage you to look for a way that doesn't use 3 RAM > locations (it shouldn't be too hard to use W as a loop counter, for > example). > > ; revbits > ; Reverses the low 7 bits of a byte. The eighth bit in is ignored, out > is 0. > ; Input/output in W. Uses tmp, tmp2, ii. > revbits > movwf tmp ;Store input value. > movlw .7 ;Loop count > movwf ii > clrf tmp2 ;Be sure bit 7 of output is 0. > revbitsl > rrf tmp,f ;Get an input bit > rlf tmp2,f ;Put to output. > decfsz ii,f > goto revbitsl > movfw tmp2 ;Load output value into W. > return > > Your solution can be improved dramatically with just a single slight modification. Get rid of the loop. Loops are so common in programming that they become the first solution sought in many applications where they aren't needed. In this case since the loop is very short and is only executed 7 times the overhead of using the loop exceeds its value. The following code is a duplication of your code with the loop unravelled. ; revbits ; Reverses the low 7 bits of a byte. The eighth bit in is ignored, out is 0. ; Input/output in W. Uses tmp, tmp2, ii. revbits movwf tmp ;Store input value. clrf tmp2 ;Be sure bit 7 of output is 0. revbitsl rrf tmp,f ;Get an input bit rlf tmp2,f ;Put bit 6 to output. rrf tmp,f ;Get an input bit rlf tmp2,f ;Put bit 5 to output. rrf tmp,f ;Get an input bit rlf tmp2,f ;Put bit 4 to output. rrf tmp,f ;Get an input bit rlf tmp2,f ;Put bit 3 to output. rrf tmp,f ;Get an input bit rlf tmp2,f ;Put bit 2 to output. rrf tmp,f ;Get an input bit rlf tmp2,f ;Put bit 1 to output. rrf tmp,f ;Get an input bit rlf tmp2,f ;Put bit 0 to output. movfw tmp2 ;Load output value into W. return Scoring: 18 ROM 2 RAM 19 cycles 18*8 = 144 2*30= 60 19*1= 19 bonus= -40 total= 183 Bob

Mike Keitz <spam_OUTPICLISTTakeThisOuTMITVMA.MIT.EDU> wrote: > There hasn't been a "programming challenge" lately. Here's a > problem I'm looking at: I have a 7 bit ASCII character which was > transmitted serially LSB first, but received MSB first. Thus, I > need to reverse the order of the bits (I can't change the receiver, > since other parts of the data are transmitted MSB first). For > example, 0011010 should come out as 0101100. The routine should be > a subroutine which gets the input value in W and returns the result > in W. It is OK to assume the high bit of W will be 0, and the high > bit of the result must be 0 (the routine works only on the low 7 > bits) > > Each ROM location used : 8 points > Each RAM location used : 30 points > Each instruction cycle (to convert once): 1 point > Uses less than 25 instruction cycles: -40 points > > Under these rules, the lookup table scores a whopping 998 points, > though it does qualify for the speed bonus. My first attempt at a > solution (below) is 211 points (10 ROM, 3 RAM, 41 cycles). Mike: John Payson has one that'll score less than 160 points... Maybe he'll post it. If you just unroll your 211-point solution, you get this: REVBITS: MOVWF SOURCE RRF SOURCE RLF DEST RRF SOURCE RLF DEST RRF SOURCE RLF DEST RRF SOURCE RLF DEST RRF SOURCE RLF DEST RRF SOURCE RLF DEST RRF SOURCE RLF DEST,W ANDLW 01111111B RETURN 17 ROM, 2 RAM, 18 cycles. Score = 17*8 + 2*30 + 18 - 40 = 174. The last time the subject came up on the list, Mark Palmer offered a BTFSC/IORLW solution which used two registers; I showed how it could be modified to use one: REVBITS: MOVWF SOURCE MOVLW 0 BTFSC SOURCE,6 IORLW 00000001B BTFSC SOURCE,5 IORLW 00000010B BTFSC SOURCE,4 IORLW 00000100B BTFSC SOURCE,3 IORLW 00001000B BTFSC SOURCE,2 IORLW 00010000B BTFSC SOURCE,1 IORLW 00100000B BTFSC SOURCE,0 IORLW 01000000B RETURN 17 ROM, 1 RAM, 18 cycles. Score = 17*8 + 1*30 + 18 - 40 = 144. -Andy === Andrew Warren - .....fastfwdKILLspam@spam@ix.netcom.com === Fast Forward Engineering - Vista, California === http://www.geocities.com/SiliconValley/2499

Mike Keitz wrote: > > There hasn't been a "programming challenge" lately. Here's a problem I'm > looking at: I have a 7 bit ASCII character which was transmitted > serially LSB first, but received MSB first. Thus, I need to reverse the > order of the bits Steve Hardy's solution with Payson's modification reverses two bytes simultaneously (and this is essentially Mike's solution unrolled): revbits movwf temp1 rlf temp2,W rrf temp1,F rlf temp2,F rrf temp1,F rlf temp2,F rrf temp1,F rlf temp2,F rrf temp1,F rlf temp2,F rrf temp1,F rlf temp2,F rrf temp1,F rlf temp2,F rrf temp1,F rlf temp2,F rrf temp1,F rlf temp2,F rrf temp1,W RETURN Note that the state of W is preserved. Thus we have two copies of the input byte, the "unreversed" one in W and the "reversed" one in temp2. If you were super-duper clever, you would read in two ASCII values, store the first in temp2 and then run the above algorithm. This would kill two stones with one bird. ; get first ASCII byte: movwf temp2 ;other code stuff ;get second ASCII byte call revbits Which when tallied gives 21 Rom (excluding the call) 2 Ram 22 cycles less than 25 instructions 2 conversions or (21*8 + 2*30 + 22 - 40)/2 = 105 points Another solution optimized for size: revbits: movwf temp1 bsf temp1,7 clrf temp2 rlf temp1,F rrf temp2,F skpnc goto $-3 return 8*8 + 2*30 + 45 - 40 = 129 Another solution optimized for points: ; get first ASCII byte: movwf temp2 ;other code stuff ;get second ASCII byte call revbits revbits: movwf temp1 movlw 8 movwf temp3 rrf temp2,W rlf temp1,F rrf temp2,F decfsz temp3,F goto $-3 return Which when tallied gives 10 Rom (excluding the call) 3 Ram 47 cycles less than 25 instructions 2 conversions or (10*8 + 3*30 + 47 - 40)/2 = 88.5 points But having just thrown this stuff out, I'm sure someone else (e.g. Dmitry) will figure a way to shave a few more points. Scott -- __o I buy pizza instead of gas. \< (*)/(*)

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.