Searching \ for 'Reversing the order of bits in a register.' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=reversing+order
Search entire site for: 'Reversing the order of bits in a register.'.

Truncated match.
PICList Thread
'Reversing the order of bits in a register.'
2000\03\17@055059 by Andy Baker

flavicon
face
Dear All,

Another one of those algorithm challenges (apologies if this is a well known
one):

How do I reverse the bits in an 8 bit register in as few instructions as
possible?

i.e. you start with a byte 'abcdefgh' and end up with 'hgfedcba'.

The reason I'd like to know is that I've got my data lines to an LCD display
reversed on my PCB,, but don't want to redesgin the PCB as it is otherwise
OK.

Cheers,

Andy

--
Andy Baker  spam_OUTabTakeThisOuTspamdatcon.co.uk
Network Convergence Group
Data Connection Ltd., Chester, UK
http://www.datcon.co.uk/
Tel: +44 (0) 1244 313440  Fax: +44 (0) 1244 312422

2000\03\17@055708 by paulb

flavicon
face
Andy Baker wrote:

> Another one of those algorithm challenges (apologies if this is a well
> known one):

 Is it *ever*!

 Did you try searching the archive with keyword "reverse"?
--
 Cheers,
       Paul B.

2000\03\17@094859 by M. Adam Davis

flavicon
face
Well, the simplest and most straightforward uses a scratch register, and takes
18 cycles:

Your scratch register is SCRATCH, your variable is REVERSE

;This will end up with REVERSE = reverse reversed
;                      SCRATCH = reverse reversed
;                      CARRY   = the original MSB of SCRATCH
RLF    REVERSE    ; Rotate the MSB into CARRY
RRF    SCRATCH    ; Rotate CARRY into the MSB
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
MOVF   SCRATCH, W ; Move scratch
MOVWF  REVERSE    ; into Reverse

In the end both REVERSE and SCRATCH have the reversed bits.  Get rid of the last
two instructions, add an RLF REVERSE, and you end up reversing both SCRATCH and
REVERSE, with their reversed versions in each other's register, and CARRY is
preserved after the routine!

;This will end up with REVERSE = scratch reversed
;                      SCRATCH = reverse reversed
;                      CARRY   = CARRY
RLF    REVERSE    ; Rotate the MSB into CARRY
RRF    SCRATCH    ; Rotate CARRY into the MSB
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE
RRF    SCRATCH
RLF    REVERSE    ;Rotate the MSB (which was originally in carry)
                 ;into CARRY

I imagine there is a shorter routine (using subtraction and xor) but I don't
have the time to explore it (though I love math problems like this.  It would be
neat to make a 3-5 instruction routine that will do this...)  I imagine this
will suit your needs.

-Adam

Andy Baker wrote:
{Quote hidden}

2000\03\17@102624 by jamesnewton

face picon face
That is covered in the FAQ. See:
http://www.piclist.com/faq
under routines, math, bit operations, reverse bit order in a byte. Please
let me know if anything is missing from that routine library.

---
James Newton jamesnewtonspamKILLspamgeocities.com 1-619-652-0593
http://techref.massmind.org NEW! FINALLY A REAL NAME!
Members can add private/public comments/pages ($0 TANSTAAFL web hosting)


{Original Message removed}

2000\03\18@025912 by w. v. ooijen / f. hanneman

picon face
Using 4 bit mode (assuming a HD44780) migt save some reversing...
Wouter

----------
> From: Andy Baker <.....ABKILLspamspam.....DATCON.CO.UK>
> To: EraseMEPICLISTspam_OUTspamTakeThisOuTMITVMA.MIT.EDU
> Subject: Reversing the order of bits in a register.
> Date: Friday, March 17, 2000 11:49
>
> Dear All,
>
> Another one of those algorithm challenges (apologies if this is a well
known
> one):
>
> How do I reverse the bits in an 8 bit register in as few instructions as
> possible?
>
> i.e. you start with a byte 'abcdefgh' and end up with 'hgfedcba'.
>
> The reason I'd like to know is that I've got my data lines to an LCD
display
> reversed on my PCB,, but don't want to redesgin the PCB as it is
otherwise
{Quote hidden}

2000\03\19@002122 by Nikolai Golovchenko

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


Nikolai

On Friday, March 17, 2000 Andy Baker wrote:
{Quote hidden}

2000\03\19@005933 by Byron A Jeff

face picon face
Nickolei's solution edited out for brevity.

>
> On Friday, March 17, 2000 Andy Baker wrote:
> > Dear All,
>
> > Another one of those algorithm challenges (apologies if this is a well known
> > one):
>
> > How do I reverse the bits in an 8 bit register in as few instructions as
> > possible?
>
> > i.e. you start with a byte 'abcdefgh' and end up with 'hgfedcba'.
>
> > The reason I'd like to know is that I've got my data lines to an LCD display
> > reversed on my PCB,, but don't want to redesgin the PCB as it is otherwise
> > OK.
>
> > Cheers,
>
> > Andy

Actually Andy your specification is somewhat vague. Does the few instructions
refer to actual instructions executed or total instruction size of the code.

For example the absolute shortest execution time is simply to have a 256
byte lookup table and jump to the appropriate entry. No more than 6
instructions executed taking 10 cycles but the total code cost is 260
instructions in memory.

Let's see if I can come up with a quick compromise that utilizes the
swapf instruction and a 16 byte lookup table:

swapbyte:
       movf    byte,W          ; get the low nybble
       andlw   15              ; And mask it off
       call    reverse         ; reverse the nybble
       movwf   out             ; Save it
       swapf   out,F           ; Swap to high position
       swapf   byte,W          ; Get the high nybble
       andlw   15              ; Mask
       call    reverse         ; reverse
       iorwf   out,F           ; Merge with other nybble
       return

reverse:
       addwf   PCL,F           ; jumptable
       retlw   15              ; reverse of 0
       retlw   14              ; reverse of 1
       ...
       retlw   0               ; reverse of 15

Let's see the mainline code takes 14 cycles. The reverse takes 4. So
Nickolei's code is faster.

BAJ

2000\03\19@044035 by Snail Instruments

flavicon
face
>How do I reverse the bits in an 8 bit register in as few instructions as
>possible?
>
>i.e. you start with a byte 'abcdefgh' and end up with 'hgfedcba'.
>
>The reason I'd like to know is that I've got my data lines to an LCD display
>reversed on my PCB,, but don't want to redesgin the PCB as it is otherwise
>OK.

I remember similar thing happened to me, too. Text that was constant, I
output to the display already reversed and for the digits I used lookup
table.

Josef

2000\03\19@085157 by Jim Robertson

flavicon
face
At 12:58 AM 3/19/00 -0500, you wrote:




This is what I use for my 17Cxx programmer that also has the i/o lines
swapped. This is optimized for space but is considerably slower than
other solutions. However it is up to you to decide your priorities.

;**************************************
;SPIN
;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

Jim


>Nickolei's solution edited out for brevity.
>
>>
>> On Friday, March 17, 2000 Andy Baker wrote:
>> > Dear All,
>>
>> > Another one of those algorithm challenges (apologies if this is a well
known
>> > one):
>>
>> > How do I reverse the bits in an 8 bit register in as few instructions as
>> > possible?
>>
>> > i.e. you start with a byte 'abcdefgh' and end up with 'hgfedcba'.
>>
>> > The reason I'd like to know is that I've got my data lines to an LCD
display
>> > reversed on my PCB,, but don't want to redesgin the PCB as it is
otherwise
{Quote hidden}

Regards,

Jim Robertson
NEWFOUND ELECTRONICS
________________________________________
Email: KILLspamnewfoundKILLspamspampipeline.com.au
http://www.new-elect.com
MPLAB compatible PIC programmers.
________________________________________

2000\03\19@091929 by Scott Dattalo

face
flavicon
face
On Sun, 19 Mar 2000, Nikolai Golovchenko wrote:

{Quote hidden}

For a single byte there is a 14-cycle solution. But since it looks like your
having fun, I wouldn't want to spoil anything. :)

BTW, John Payson posted the original solution (for reversing 7 bits). Dmitry
optimized it slightly (again for 7 bits). John's trick is applicable here as
well.

Hint, for the general case, it takes 4 cycles to swap 2 bits. However, it only
takes 2 cycles for the first two bits.

Scott

2000\03\19@135043 by mike

flavicon
face
On Mon, 20 Mar 2000 00:46:49 +1100, you wrote:

{Quote hidden}

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

2000\03\20@033912 by Nikolai Golovchenko

flavicon
face
On Sunday, March 19, 2000 Scott Dattalo wrote:
> For a single byte there is a 14-cycle solution. But since it looks like your
> having fun, I wouldn't want to spoil anything. :)

I have more fun to learn from PICLIST members :)

> BTW, John Payson posted the original solution (for reversing 7 bits). Dmitry
> optimized it slightly (again for 7 bits). John's trick is applicable here as
> well.

> Hint, for the general case, it takes 4 cycles to swap 2 bits. However, it only
> takes 2 cycles for the first two bits.

> Scott

AFAIR, Dmitry used swap to place two bits in place, and then xor'd to
swap individual pairs of bits.

How about this:
;In =   abcdefgh
;Out =  hgfedcba

       rlf In, w       ;carry = a
       swapf In, f     ;In = efghabcd
       rlf In, w       ;w  = fghabcda  (-g---c-a), carry = e

       andlw 0xEF
       skpnc
       iorlw 0x10      ;w  = fghebcda  (-g-e-c-a)

       btfsc In, 6
       xorlw 0xA0
       btfsc In, 4
       xorlw 0xA0      ;w  = hgfebcda  (hgfe-c-a)

       btfsc In, 2
       xorlw 0x0A
       btfsc In, 0
       xorlw 0x0A      ;w  = hgfedcba

;14 instructions so far
;1 more to copy w to Out
       movwf Out

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

Nikolai

2000\03\20@073513 by Scott Dattalo

face
flavicon
face
On Mon, 20 Mar 2000, Nikolai Golovchenko wrote:

> On Sunday, March 19, 2000 Scott Dattalo wrote:
> > For a single byte there is a 14-cycle solution. But since it looks like your
> > having fun, I wouldn't want to spoil anything. :)
>
> I have more fun to learn from PICLIST members :)
>
> > BTW, John Payson posted the original solution (for reversing 7 bits). Dmitry
> > optimized it slightly (again for 7 bits). John's trick is applicable here as
> > well.
>
> > Hint, for the general case, it takes 4 cycles to swap 2 bits. However, it only
> > takes 2 cycles for the first two bits.
>
> > Scott
>
> AFAIR, Dmitry used swap to place two bits in place, and then xor'd to
> swap individual pairs of bits.

yep.

{Quote hidden}

That looks like it'll work. Here's what I had in mind:

; In  = abcdefgh
; Out = hgfedcba
   rlf     In,w
   rlf     In,w     ; bcdefgha  (---e---a)

   btfsc   In,0     ; swap b and h (magnetism?)
    xorlw  0x82
   btfsc   In,6
    xorlw  0x82     ; hcdefgba  (h--e--ba)

   btfsc   In,1     ; swap c and g
    xorlw  0x44
   btfsc   In,5
    xorlw  0x44     ; hgdefcba  (hg-e-cba)

   btfsc   In,2     ; swap d and f
    xorlw  0x28
   btfsc   In,4
    xorlw  0x28     ; hgfedcba

On an 18cxxx, you can shave a cycle by:

; In  = abcdefgh
; Out = hgfedcba
   rlfnc   In,w     ; bcdefgha

Scott

2000\03\20@113637 by jamesnewton

face picon face
Its all at
http://www.piclist.com
under routines, math, bit operations, reversing bit order in a byte

---
James Newton RemoveMEjamesnewtonTakeThisOuTspamgeocities.com 1-619-652-0593
http://techref.massmind.org NEW! FINALLY A REAL NAME!
Members can add private/public comments/pages ($0 TANSTAAFL web hosting)


{Original Message removed}

2000\03\20@133634 by Scott Dattalo

face
flavicon
face
On Mon, 20 Mar 2000, James Newton wrote:

> Its all at
> http://www.piclist.com
> under routines, math, bit operations, reversing bit order in a byte

This url put me on the faq page. ?

Anyway, you most probably will want to add Steve Hardy's simultaneous two-byte
reversing algorithm that someone else posted just the other day. It takes only
16 cycles. And John Payson needs an honorable mention in there as well.

This is the only reference I could find to Steve Hardy's algorithm.

http://www.infosite.com/~jkeyzer/piclist/1999/Nov/0022.html

and of course, Adam just repeated this with:

http://www.infosite.com/~jkeyzer/piclist/2000/Mar/1839.html


Scott

2000\03\20@135258 by jamesnewton

face picon face
<BLOCKQUOTE Author="Scott Dattalo">
On Mon, 20 Mar 2000, James Newton wrote:
> Its all at
> http://www.piclist.com/
> under routines, math, bit operations, reversing bit order in a byte
This url put me on the faq page. ?
</BLOCKQUOTE>

Oops!
http://www.piclist.com/FAQ
under routines, math, bit operations, reversing bit order in a byte.

or

http://www.piclist.com
under PIC FAQ, routines, math, bit operations, reversing bit order in a
byte.

the piclist.com homepage is the PICList FAQ and the FAQ under that is the
PIC FAQ. Hope that's not too confusing.

The direct (ugly) link is
http://www.piclist.com/techref/default.asp?url=microchip/math/bit/revbits

and I believe I have covered all, please let me know if I missed one. They
are arranged by smallest, fastest and most flexible.

---
James Newton spamBeGonejamesnewtonspamBeGonespamgeocities.com 1-619-652-0593
http://techref.massmind.org NEW! FINALLY A REAL NAME!
Members can add private/public comments/pages ($0 TANSTAAFL web hosting)


{Original Message removed}

2000\03\20@173621 by Dmitry Kiryashov

flavicon
face
Hi Scott and Nikolai and others ;-) Sorry I was a little bit busy...

I guess we guys always have some fun solving some challenges ;-)

Here is procedure I've done for myself recently to overcome the
same situation.

;       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...

WBR Dmitry.


----------


Nikolai Golovchenko wrote:
{Quote hidden}

2000\03\20@231811 by Nikolai Golovchenko

flavicon
face
Congratulations! Wow!

I knew you had something to say :)

Nikolai

Monday, March 20, 2000, 11:28:35 PM, you wrote:
{Quote hidden}

More... (looser matching)
- Last day of these posts
- In 2000 , 2001 only
- Today
- New search...