Searching \ for 'Challenge: Reverse 7 bits' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: techref.massmind.org/techref/index.htm?key=reverse+bits
Search entire site for: 'Challenge: Reverse 7 bits'.

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

picon face
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

picon face
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

flavicon
face
At 10:50 AM 29/10/97 -0500, you wrote:
{Quote hidden}

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]

flavicon
picon face
> 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}

You can leave out this one - its already in the corect place.
{Quote hidden}

Gives you 15 ROM, 1 RAM, 16 Cycles = 126 points

Niki

1997\10\29@121835 by Bob Buege

picon face
In a message dated 97-10-29 11:06:58 EST, you write:

{Quote hidden}

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

face
flavicon
face
Mike Keitz <spam_OUTPICLISTTakeThisOuTspamMITVMA.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 - .....fastfwdKILLspamspam@spam@ix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499

1997\10\29@133243 by sdattalo

face
flavicon
face
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.    \<
                             (*)/(*)

1997\10\29@133837 by sdattalo

face
flavicon
face
Scott Dattalo wrote:

oops:
{Quote hidden}

The 'movlw 8' is out of order...:

revbits:
   movwf  temp1

   rrf    temp2,W

   movlw  8
   movwf  temp3

1997\10\29@140632 by John Payson

picon face
> >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 30-point penalty
would kill off any savings; a 9-ROM, 9-cycle 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

flavicon
face
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

picon face
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.

1997\10\30@023346 by William Chops Westfield

face picon face
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

flavicon
face
-----Original Message-----
From: William Chops Westfield <billwspamKILLspamCISCO.COM>
To: .....PICLISTKILLspamspam.....MITVMA.MIT.EDU <EraseMEPICLISTspam_OUTspamTakeThisOuTMITVMA.MIT.EDU>
Date: Thursday, 30 October 1997 18:04
Subject: Re: Challenge: Reverse 7 bits


{Quote hidden}

Typical assembly comments!  <g>

Anyone care to explain it?

MikeS
<mikesmith_ozspamspam_OUTrelaymail.net>

1997\10\30@095639 by myke predko

flavicon
face
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...