Truncated match.
PICList
Thread
'Challenge: Reverse 7 bits'
1997\10\29@110436
by
Mike Keitz

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
1997\10\29@115604
by
wwl

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
1997\10\29@120814
by
Antti Lukats

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
1997\10\29@121828
by
STEENKAMP [M.ING E&E]

> 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
1997\10\29@121835
by
Bob Buege

In a message dated 971029 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
1997\10\29@123705
by
Andrew Warren

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 211point 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
1997\10\29@133243
by
sdattalo

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 superduper
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. \<
(*)/(*)
1997\10\29@133837
by
sdattalo
Scott Dattalo wrote:
oops:
{Quote hidden}> 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
The 'movlw 8' is out of order...:
revbits:
movwf temp1
rrf temp2,W
movlw 8
movwf temp3
1997\10\29@140632
by
John Payson
> >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
How about this...
movwf source
btfsc source,0
xorlw h'41'
btfsc source,6
xorlw h'41'
btfsc source,1
xorlw h'22'
btfsc source,5
xorlw h'22'
btfsc source,2
xorlw h'14'
btfsc source,4
xorlw h'14'
Rom==13, RAM==1, Cycles==13, bonus==40
8*13 + 30 + 13  40 == 107
I don't think it's possible to score better than that; it may be possible to
design a faster/smaller one using two temp. locations but the 30point penalty
would kill off any savings; a 9ROM, 9cycle version would score
8*9 + 30*2 + 9  40 = 101
which would be a slight savings, but I don't think such a thing is possible.
Can anyone else manage it?
1997\10\29@160716
by
Dmitry Kiryashov
Hello John .
> How about this...
>
> movwf source
> btfsc source,0
> xorlw h'41'
> btfsc source,6
> xorlw h'41'
> btfsc source,1
> xorlw h'22'
> btfsc source,5
> xorlw h'22'
> btfsc source,2
> xorlw h'14'
> btfsc source,4
> xorlw h'14'
>
> Rom==13, RAM==1, Cycles==13, bonus==40
> 8*13 + 30 + 13  40 == 107
John ! You are genius !!! You tell me idea how to swap bits.
And i know how to improve you solution.
swapf source,w
btfsc source,3
xorlw 0x88
btfsc source,6
xorlw 0x05
btfsc source,4
xorlw 0x05
btfsc source,2
xorlw 0x50
btfsc source,0
xorlw 0x50
return
WBR Dmitry .
1997\10\30@013020
by
Mike Keitz

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 bruteforce 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.
1997\10\30@023346
by
William Chops Westfield
There is a clever algorithm for bit reversal "discovered" at MIT (I
think) a long time ago. Do:
mult a,#100040020001 ;Make some copies
and a, #210210210010 ; select some bits
div a, #377 ; cast out / squeeze...
All the numbers are octal. The words are 36 bits long and the initial
multiply is allowed to get an arithmatic overflow.
Three instuctions. Five words (36 bits each). Totally inapplicable to
the PIC, but pretty weird...
BillW
1997\10\30@065833
by
Mike Smith
1997\10\30@095639
by
myke predko
Dmitry wrote:
>John ! You are genius !!! You tell me idea how to swap bits.
>And i know how to improve you solution.
>
> swapf source,w
> btfsc source,3
> xorlw 0x88
> btfsc source,6
> xorlw 0x05
> btfsc source,4
> xorlw 0x05
> btfsc source,2
> xorlw 0x50
> btfsc source,0
> xorlw 0x50
> return
>
>WBR Dmitry .
Well done Dmitry! *Really* impressive and going into my "snippet" bucket
(who knows when you'll have to reverse bits?)!
myke
Check out "Programming and Customizing the PIC Microcontroller" at:
http://www.myke.com
More... (looser matching)
 Last day of these posts
 In 1997
, 1998 only
 Today
 New search...