Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!agate!ucbvax!bloom-beacon!mit-eddie!uw-beaver!microsoft!jangr
From: jangr@microsoft.UUCP (Jan Gray)
Newsgroups: comp.arch
Subject: Re: HW v. SW (bit reversal)
Message-ID: <1191@microsoft.UUCP>
Date: 8 Nov 88 06:33:59 GMT
References: <156@gloom.UUCP> <18931@apple.Apple.COM> <40@sopwith.UUCP> <998@l.cc.purdue.edu> <1622@scolex> <866@cernvax.UUCP> <7629@aw.sei.cmu.edu>
Reply-To: jangr@microsoft.UUCP (Jan Gray)
Organization: Microsoft Corp., Redmond WA
Lines: 48

In article <7629@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes:
>Here's my quick and dirty attempt at the same in software, on the
>MIPS R2000.  We assume DEST := bitrevword(SRC), where both are
>4-byte variables, and T is a 256-byte lookup table of reversed
>bytes:

You can avoid all memory references using this slightly slower approach:
	; r0 -- input	
	; r1 -- scratch
	; r2 -- 0x00FF00FF
	; r3 -- 0x0F0F0F0F
	; r4 -- 0x33333333
	; r5 -- 0x55555555
					;abcdefghijklmnopqrstuvwxyz123456
	srl	r1,r0,16 ; swap 16 bits	;----------------abcdefghijklmnop
	sll	r0,r0,16		;qrstuvwxyz123456----------------
	or	r0,r0,r1		;qrstuvwxyz123456abcdefghijklmnop

	and	r1,r0,r2 ; swap 8 bits	;--------yz123456--------ijklmnop
	xor	r0,r0,r1		;qrstuvwx--------abcdefgh--------
	srl	r0,r0,8			;--------qrstuvwx--------abcdefgh
	sll	r1,r1,8			;yz123456--------ijklmnop--------
	or	r0,r0,r1		;yz123456qrstuvwxijklmnopabcdefgh

	and	r1,r0,r3 ; swap 4 bits	;----3456----uvwx----mnop----efgh
	xor	r0,r0,r1		;yz12----qrst----ijkl----abcd----
	srl	r0,r0,4			;----yz12----qrst----ijkl----abcd
	sll	r1,r1,4			;3456----uvwx----mnop----efgh----
	or	r0,r0,r1		;3456yz12uvwxqrstmnopijklefghabcd

	and	r1,r0,r4 ; swap 2 bits	;--56--12--wx--st--op--kl--gh--cd
	xor	r0,r0,r1		;34--yz--uv--qr--mn--ij--ef--ab--
	srl	r0,r0,2			;--34--yz--uv--qr--mn--ij--ef--ab
	sll	r1,r1,2			;56--12--wx--st--op--kl--gh--cd--
	or	r0,r0,r1		;563412yzwxuvstqropmnklijghefcdab

	and	r1,r0,r5 ; swap 1 bits	;-6-4-2-z-x-v-t-r-p-n-l-j-h-f-d-b
	xor	r0,r0,r1		;5-3-1-y-w-u-s-q-o-m-k-i-g-e-c-a-
	srl	r0,r0,1			;-5-3-1-y-w-u-s-q-o-m-k-i-g-e-c-a
	sll	r1,r1,1			;6-4-2-z-x-v-t-r-p-n-l-j-h-f-d-b-
	or	r0,r0,r1		;654321zyxwvutsrqponmlkjihgfedcba

We could even save a couple of instructions if the Rx000 supplied an
"op rd,rs1,rs2<<n" form, a la Acorn or HP Precision Architecture.

According to an old preprint of Knuth chapter 7.1, *any* permutation of n
bits can be achieved in O(lg n) logical operations.

Jan Gray  uunet!microsoft!jangr  Microsoft Corp., Redmond Wash.  206-882-8080