colonel@gloria.UUCP (George Sicherman) (11/20/84)
[Yuk! Why would you want to eat THAT?] > Ummm... it's easy to push the register mask when you moveml the registers > to be saved on entry to a subroutine in the 68000, but moveml mask,(a7)- > and moveml mask,(a7)+ expect the mask reversed from each other! How > do you propose to invert a 16-bit mask end-for-end (i.e. 11100...001 > <=> 100...00111 ) and still have a fast calling sequence? What's the fastest way to reverse a 16-bit mask in C? In 68000 asl? (Maybe this should be in net.puzzle!) -- Col. G. L. Sicherman ...seismo!rochester!rocksanne!rocksvax!sunybcs!gloria!colonel
ado@elsie.UUCP (Arthur David Olson) (11/25/84)
[Usenet brand software--ask for it by name] > What's the fastest way to reverse a 16-bit mask in C? In 68000 asl? > (Maybe this should be in net.puzzle!) Nah. . .too easy: static int revtab[65536] = { 0x0000, 0x8000, 0x4000, 0xc000, /* . . .16,382 lines of code left out to keep net costs down. . . */ 0x3fff, 0xbfff, 0x7fff, 0xffff }; #define reverse(value) (revtab[(unsigned int) value]) . . .with suitable documentation about range and type of the parameter being the responsibility of the caller. :-) -- Mask is a Wrather Corporation trademark--as Clayton Moore knows all too well. -- ..decvax!seismo!elsie!ado (301) 496-5688 DEC, VAX and Elsie are Digital Equipment and Borden trademarks
ken@rochester.UUCP (Ken Yap) (11/25/84)
>What's the fastest way to reverse a 16-bit mask in C? In 68000 asl?
Actually the 65536 combination answer wasn't too far from a plausible
method - split the word up into 2 8 bit bytes and then do two lookups.
Then swap bytes. This way you only need one 256 byte table.
You could do lookups on nybbles, etc, ad nauseum.
--
Ken Yap
UUCP: (..!{allegra, decvax, seismo}!rochester!ken)
ARPA: ken@rochester.arpa
USnail: Ken Yap, Dept. of Comp. Sci., U. of Rochester, NY 14627.smh@mit-eddie.UUCP (Steven M. Haflich) (11/25/84)
Much more space-efficient and only slightly slower is the following:
char revbytes[256] = { 0x00, 0x80, 0x40, 0xc0, ... , 0x7f, 0xff };
#define reverse(v) ((revbytes((v)&0xff)<<8)|revbytes(((v)>>8)&0xff))
That's the general idea. This is not perfectly portable, but then,
neither was the original problem. Depending on particular C
implementation, various dodges may be necessary to prevent the infamous
char sign extension problem: either by declaring revbytes to be
"unsigned char", or else by anding each mention of revbytes with 0xff.
Also, note that the argument gets evaluated twice, but this could be
corrected if necessary.
Steve Haflichgwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (11/25/84)
> What's the fastest way to reverse a 16-bit mask in C? In 68000 asl?
I think it is probably to have an array of reversed masks of size 2^16
and use the forward mask as an index into the array.
Do I win a prize?gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (11/25/84)
> >What's the fastest way to reverse a 16-bit mask in C? In 68000 asl? > > Actually the 65536 combination answer wasn't too far from a plausible > method - split the word up into 2 8 bit bytes and then do two lookups. > Then swap bytes. This way you only need one 256 byte table. > > You could do lookups on nybbles, etc, ad nauseum. Hey! Take this to the logical extreme: split into 16 1-bit fields, then you can dispense with the table altogether (since the reversal of a 1-bit field is itself). :-)
geoff@desint.UUCP (Geoff Kuenning) (11/26/84)
In article <691@gloria.UUCP> colonel@gloria.UUCP (George Sicherman) writes: >What's the fastest way to reverse a 16-bit mask in C? In 68000 asl? >(Maybe this should be in net.puzzle!) Try this: static unsigned char revtab[256] = {0x80, 0x40, 0xC0, 0x20, 0xA0,...}; short bitrev (mask) register unsigned short mask; { return (revtab[mask & 0xFF] << 8) | revtab[mask >> 8]; } Note: I haven't actually tried compiling this program. It depends on the compiler generating a zero-filling right-shift for unsigned shorts. If yours does not, you will need to use: return (revtab[mask & 0xFF] << 8) | revtab[(mask >> 8) & 0xFF]; -- Geoff Kuenning ...!ihnp4!trwrb!desint!geoff
eryk@unisoft.UUCP (Eryk Vershen) (11/29/84)
Apropos of nothing here is a cute way to reverse bits due to C. Strachey.
int mask[] = {
0x55555555,
0x33333333,
0x0F0F0F0F,
0x00FF00FF,
0x0000FFFF
}
long
bitrev(val)
long val;
{
register long i;
register int j ,k;
i = val;
j = 16;
k = 4;
while (j) {
i = ((i & mask[k]) << j) | ((i >> j) & mask[k]);
j >>= 1;
k--;
}
return(i);
}
/*
* Proof of the above (by example).
*
* j=16 i=abcdefghijklmnopqrstuvwxyz012345
* 8 qrstuvwxyz012345abcdefghijklmnop
* 4 yz012345qrstuvwxijklmnopabcdefgh
* 2 2345yz01uvwxqrstmnopijklefghabcd
* 1 452301yzwxuvstqropmnklijghefcdab
* 0 543210zyxwvutsrqponmlkjihgfedcba
*/
--
- eryk vershen
ucbvax!unisoft!eryk
"overcoming computer literacy"robison@uiucdcsb.UUCP (12/02/84)
Reverse a bit mask? That's easy! Treat the bit mask as a 16-bit vector. Then just apply two fourier transformations! - Arch @ uiucdcs
hamilton@uiucuxc.UUCP (12/12/84)
i'm straying even further from the subject, but eryk vershen's note
reminded me of some cute code i found somewhere long ago:
/* onebits - count 1-bits in an int
* using Reingold, Nievergelt & Deo's Combinatorial Algorithm #1.3.
*/
static unsigned long int Hi[5] =
{ 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 };
static unsigned long int Lo[5] =
{ 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF };
onebits (n)
register unsigned long int n;
{
register int shift;
register unsigned long int *H = Hi, *L = Lo;
for (shift = 1; shift <= 16; shift *= 2)
n = ((n & *H++) >> shift) + (n & *L++);
return (n);
}
wayne ({decvax,ucbvax}!pur-ee!uiucdcs!uiucuxc!)hamiltonix269@sdcc6.UUCP (12/19/84)
fig() It is quite simple, to reverse a bit mask, merely get a ones compliment (sp?). that is ~mask mask = 011101 /* binary notation, leading zero */ 010 = ~mask this is convenient for purists who *know* that 0 is always FALSE and that !0 is the value of TRUE, ~0 is most definitely the opposite of 0, but I may be asking for it. fourier transforms? Must be a nice machine for that overhead :-).