How to reverse bits...

[Martin Weitzel]

In article <401 at sun13.scri.fsu.edu> mayne at VSSERV.SCRI.FSU.EDU (William (Bill) Mayne) writes:
>Returning to the bit reversal question, how would you or others
>construct the table of reversed bit bytes? In several assembly
>languages I've used the preprocessor would make this quite easy.

Yes, but was it done in the same way with all those preprocessors?
Note that C is a portable language, which said assemblers surely
were not. I don't say that the C preprocessor must be limited
in its features because the portability of C. It's only that I
would allways prefer C *despite* its limited preprocessor because
of portabiliy.

>In C I think I'd have to resort to either computing the table
>at run time or having a program compute it and write out an
>#include file to define it.

IMHO the latter is a very clean, friendly, and portable approach.
Whom does it hurt (especially if you use "make" to manage your
project and produce those generated files automatically before
the ones that include them)? A programmer who knows C will have
to learn nothing new about esoteric preprocessor features and
still understand what is done, as the initializing program is
written in C.

BTW: If the C preprocessor were ever extended to have loops and more
(in C-2001?), I fear we programmers would have to learn just another
language. Of course, it would be a nice idea if an enhanced preprocessor
could be made somehow an interpreter for a subset of C, so that there
were not to learn much new.

>You may infer from this that I have
>been somewhat spoiled and am no great fan of the very limited
>preprocessor facilities provided by C, though I really like the
>language.

If you like the C language, you probably like UNIX too and there
you have an alternative if the C preprocessor is too limited: "m4".

Again back to the original question. I too would use a table, but
after some discussion in this thread I got curious how much code it
would afford to reverse bit patterns "on the fly". So I've written
the following short program, which is a bit generalized so that it
can be used for bit patterns of arbitrary length up to the size of
an unsigned int.

--------------------------------------------------------------------
/*
 * Bit-Reversal Makro:
 * Treat b as a pattern of n bits, counting
 * from 0 (least significant) to n-1 (most
 * significant). R(b,i,n) returns the i-th
 * bit in its reversed position n-1-i.
*/

#define R(b,i,n)	((i) < ((n)+1)/2)\
			? ((b) & (1<<(i))) << ((n) - 2*(i) - 1)\
			: ((b) & (1<<(i))) >> (2*(i) - (n) + 1)

/*
 * Pattern-Reversal Function:
 * Reverse the bit pattern specified in b,
 * with respect to its n least significant
 * bits. Return reversed pattern as result.
*/

unsigned int revbits(b, n)
	unsigned int b;
	int n;
{
	register int i, k;
	for (i = k = 0; i < n; i++)
		k |= R(b, i, n);
	return k;
}

#ifdef TEST

void printbits(b, n, s)
	unsigned int b;
	int n;
	char *s;
{
	while (n-- > 0)
		putchar(b & (1<<n) ? '1' : '0');
	while (*s)
		putchar(*s++);
}

main(argc, argv)
	int argc;
	char *argv[];
{
	while (*++argv) {
		int a, i, ts = atoi(*argv);
		if (ts <= 0) continue;
		a = 1; while ((~0 << a) & ts-1) a++;
		for (i = 0; i < ts; i++) {
			printbits(i, a, "   --   ");
			printbits(revbits(i, a), a, "\n");
		}
	}
}

#endif
--------------------------------------------------------------------

Compiling this on an 80386 (with TEST not defined, of course) shows
only 112 bytes of code, so that it is well below the size of a table
required to invert 8 bits (for a char). Of course, you can use the
revbits function to (dynamically) initialize a table, if speed is the
problem, or you can use it as a base for writing static initializations
of tables as the poster (Bill) proposed above.
-- 
Martin Weitzel, email: martin at mwtech.UUCP, voice: 49-(0)6151-6 56 83