Path: utzoo!attcan!uunet!husc6!purdue!haven!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.arch
Subject: bit reversal instr/sw (was Re: HW v. SW)
Message-ID: <14495@mimsy.UUCP>
Date: 11 Nov 88 16:44:06 GMT
References: <156@gloom.UUCP> <18931@apple.Apple.COM> <40@sopwith.UUCP> <866@cernvax.UUCP>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 17

In article <866@cernvax.UUCP> hjm@cernvax.UUCP (Hubert Matthews) writes:
>The INMOS T800 has an instruction bitrevword, which turns a
>little-endian word into a big-endian word, effectively doing a
>reflection in the middle. ... In software, it takes quite some time.
>In hardware it takes just over 1 microsecond on a 30MHz part.

The MIT X Window system library has to reverse the bits in a byte,
word, or longword.  It uses a 256-element table lookup, possibly
iterated (unrolled) for word and longword flips.  Expand the table
to 16 bits (65536 elements) and you can do it in 4 VAX instructions;
otherwise it takes 8.  Not so slow after all. . . .

(Of course, PCC does not manage to use 8 instructions, at least not
without much help.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris