please dont rip this site

SX Microcontroller Bit Math Method

Reverse bit order in a byte

to change b7 b6 b5 b4 b3 b2 b1 b0 to b0 b1 b2 b3 b4 b5 b6 b7.

Quickest

256 byte lookup table

Total Program Instructions: 2 + 256 Total Instructions Executed: 2

Most code efficient

A small, slower approach is to rotate the source byte right one bit (putting the rightmost bit in the carry flag), then rotate the destination byte left one bit (putting the carry flag in the rightmost bit of your destination register). Repeat this cycle 8 times. Your destination byte will have to be a temp register. Enter with byte to be reversed in W, exits with reversed byte in W. Reverse is trashed.

;**************************************
;SPIN by Jim Robertson
;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!)


	setb	KnownZero.3	;count = 8
yyr6	rr	abuff
	rl	bbuff
	decsz	KnownZero
	jmp	yyr6


Total Program Instructions:  5 Total Instructions Executed: 26

This can, of course, be unrolled for faster execution at the cost of more code space.

RevWReg:
        rl WREG         ; W   = d6 d5 d4 d3 d2 d1 d0 C  {C = d7}
        rr Reverse      ; Rev = d7 R7 R6 R5 R4 R3 R2 R1 {C = R0}
        rl WREG         ; W   = d5 d4 d3 d2 d1 d0 C  R0 {C = d6}
        rr Reverse      ; Rev = d6 d7 R7 R6 R5 R4 R3 R2 {C = R1}
        rl WREG         ; W   = d4 d3 d2 d1 d0 C  R0 R1 {C = d5}
        rr Reverse      ; Rev = d5 d6 d7 R7 R6 R5 R4 R3 {C = R2}
        rl WREG         ; W   = d3 d2 d1 d0 C  R0 R1 R2 {C = d4}
        rr Reverse      ; Rev = d4 d5 d6 d7 R7 R6 R5 R4 {C = R3}
        rl WREG         ; W   = d2 d1 d0 C  R0 R1 R2 R3 {C = d3}
        rr Reverse      ; Rev = d3 d4 d5 d6 d7 R7 R6 R5 {C = R4}
        rl WREG         ; W   = d1 d0 C  R0 R1 R2 R3 R4 {C = d2}
        rr Reverse      ; Rev = d2 d3 d4 d5 d6 d7 R7 R6 {C = R5}
        rl WREG         ; W   = d0 C  R0 R1 R2 R3 R4 R5 {C = d1}
        rr Reverse      ; Rev = d1 d2 d3 d4 d5 d6 d7 R7 {C = R6}
        rl WREG         ; W   = C  R0 R1 R2 R3 R4 R5 R6 {C = d0}
        mov W,    >>Reverse; W   = d0 d1 d2 d3 d4 d5 d6 d7 {C = R7}
        ret

Mike Harrison says:

.. or if you're short of registers, how about this :
	mov	W, #080
	mov	dest, W

loop
	rl	src
	rr	dest
	sb	C	; loop until marker bit falls out the end
	jmp	loop

Middle

;       Input X  = abcdefgh , Output X = hgfedcba
;       Written by Dmitry A. Kiryashov 2000
;       12 clocks/words

reverse8bit:

	mov	W, <>X		;efghabcd
	xor	W, X		;efghabcd
				;abcdefgh

	and	W, #$66	;.fg..bc.
				;.bc..fg.

	xor	X, W		;afgdebch
;
	mov	W, >>X
	rr	X		;hafgdebc
;
	and	W, #$55	;.a.g.e.c
	add	X, W		;h.f.d.b.
				;a.g.e.c.
	rr	X		;.h.f.d.b
				;.a.g.e.c

	add	X, W		;ahgfedcb
;
	mov	W, <<X
	rl	X		;hgfedcba
				;it can be replaced
;with	mov	W, <<X
				;if necessary...

Total Program Instructions: 7 + 19 Total Instructions executed: 13

eg.

	mov	W, original
	call	rev_nibble
	mov	result, W
	swap	result
	mov	W, <>original
	call	rev_nibble
	or	result, W

  rev_nibble
	and	W, #$0F
	add	PC, W
	retw	#00	;0000 -> 0000
	retw	#08	;0001 -> 1000
	retw	#04	;0010 -> 0100
	retw	#0C	;0011 -> 1100
	retw	#02	;0100 -> 0010
	retw	#0B	;0101 -> 1010
	retw	#06	;0110 -> 0110
	retw	#0E	;0111 -> 1110
	retw	#01	;1000 -> 0001
	retw	#09	;1001 -> 1001
	retw	#05	;1010 -> 0101
	retw	#0D	;1011 -> 1101
	retw	#03	;1100 -> 0011
	retw	#0B	;1101 -> 1011
	retw	#07	;1110 -> 0111
	retw	#0F	;1111 -> 1111

Mike Keitz says:

My challenge 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:
	mov	src, W			;Store source
	mov	W, #%00000010	;When the 1 falls out, done.
	mov	dest, W
loop
	rr	src			;Take a bit out of src
	rl	dest			;and put it into dest
	sb	C			;Did the 1 come out yet?
	jmp	loop			;No, do another bit.
	mov	W, dest		;Load result into W
	ret				;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):

	snb	src.0
	xor	W, #%11
	snb	src.1
	xor	W, #%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.

	mov	source, W	;source = 0ABCDEFG
	mov	W, <>source	;W= DEFG0ABC
	snb	source.3	; If D = 1,
	xor	W, #$88	;convert now sure W= 0EFGDABC

	snb	source.6	;Test bit A
	xor	W, #$05	;Invert bits A and C
	snb	source.4	;Test bit C
	xor	W, #$05	;Invert bits A and C
				;now W = 0EFGDCBA
	snb	source.2	;Do the same with E and G
	xor	W, #$50
	snb	source.0
	xor	W, #$50
				;so now W = 0GFEDCBA (done)
	ret

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 xor w, fr 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.

Most Flexible

Nikolai Golovchenko says

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.
In      ds 1
Out     ds 1

A_MASK EQU 1
B_MASK EQU 2
C_MASK EQU 4
D_MASK EQU 8
E_MASK EQU 16
F_MASK EQU 32
G_MASK EQU 64
H_MASK EQU 128

	clr	W
	snb	In.7
	or	W, #A_MASK
	snb	In.6
	or	W, #B_MASK
	snb	In.5
	or	W, #C_MASK
	snb	In.4
	or	W, #D_MASK
	snb	In.3
	or	W, #E_MASK
	snb	In.2
	or	W, #F_MASK
	snb	In.1
	or	W, #G_MASK
	snb	In.0
	or	W, #H_MASK
	mov	Out, W

file: /Techref/scenix/lib/math/bit/revbits_sx.htm, 9KB, , updated: 2004/6/10 13:40, local time: 2024/11/29 21:13,
TOP NEW HELP FIND: 
18.222.166.127:LOG IN

 ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?
Please DO link to this page! Digg it! / MAKE!

<A HREF="http://sxlist.com/Techref/scenix/lib/math/bit/revbits_sx.htm"> SX Microcontroller Bit Math Method Reverse bit order in a byte</A>

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

 

Welcome to sxlist.com!


Site supported by
sales, advertizing,
& kind contributors
just like you!

Please don't rip/copy
(here's why

Copies of the site on CD
are available at minimal cost.
 

Welcome to sxlist.com!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .