IGNORED

# Reverse bit-generation in C at compile-time

## Recommended Posts

This was fun. I was too lazy to write a simple tool to generate a table of 256 bit-reversed values (i.e,. 00000010b --> 01000000b) to put in some C code.

So I figured a way to use #defines in the C code to do it for me. I end up with a 256 byte table, as expected, but did none of the work to get it.

Well, figuring the defines, but that seemed quicker than generating a tool to do it

```// COMPILE-TIME REVERSE BITS IN BYTE
#define RVS(a) ( \
((((a) >> 0) & 1) << 7) \
| ((((a) >> 1) & 1) << 6) \
| ((((a) >> 2) & 1) << 5) \
| ((((a) >> 3) & 1) << 4) \
| ((((a) >> 4) & 1) << 3) \
| ((((a) >> 5) & 1) << 2) \
| ((((a) >> 6) & 1) << 1) \
| ((((a) >> 7) & 1) << 0) \
)

#define P0(a) RVS(a)
#define P1(a) P0(a), P0(a+1)
#define P2(a) P1(a), P1(a+2)
#define P3(a) P2(a), P2(a+4)
#define P4(a) P3(a), P3(a+8)
#define P5(a) P4(a), P4(a+16)
#define P6(a) P5(a), P5(a+32)
#define P7(a) P6(a), P6(a+64)
#define P8(a) P7(a), P7(a+128)

// Want to call RVS(n) for 0-255 values. The weird #defines above aloow a single-call
// It's effectively a recursive power-of-two call of the base RVS macro

unsigned int BitRev[] = {
P8(0),
};```

The BitRev table gets the 256 bit-reversed bytes.

It does it by calling the "macro" P8, which expects P7 to do the table for it, in two halves (0-127) and (128-255).

P7 expects P6 to do the work of each of those halves -- giving P6 two halves to work on.... those being 64 bytes long...

all the way down to P0, whose job is to bit-reverse a single byte.

The reverse macro (#define) does the actual bit-reversal as a bit of bit-manipulation which the compiler will resolve down to a byte at compile time.

I know it's whacky, but it's fun-whacky, and does give an interesting way to use #defines "recursively" -- although more chained than recursive.

Just thought it worth sharing.

##### Share on other sites

Interesting, though I wouldn't call that lazy code being as that seems a bit more work than writing a simple 'for' loop to do the job.

I just looked thru my projects and I wrote a tool to generate a file containing a table of reversed values for use in Paint The City.  (25 lines)

##### Share on other sites

It's actually a one-liner in python... I just really wanted to do it in the code...

`[print(',{:08b}b0'.format(i)[::-1]) for i in range(256)]`

I guess the challenge now is... can anyone write a shorter version - any language?

Edited by Andrew Davie
replaced with a more elegant line
##### Share on other sites

3 hours ago, Andrew Davie said:

It's actually a one-liner in python... I just really wanted to do it in the code...

```
[print(',{:08b}b0'.format(i)[::-1]) for i in range(256)]```

I guess the challenge now is... can anyone write a shorter version - any language?

ARMv6 (and above) assembly:

```RBIT R0, R1
LSR R0, R0, #24```

Two instructions, 8 bytes. Beat that!

##### Share on other sites

2 hours ago, batari said:

ARMv6 (and above) assembly:

```
RBIT R0, R1
LSR R0, R0, #24```

Two instructions, 8 bytes. Beat that!

Nice, but not the challenge... You *have* to output the data so it can be cut/paste into source code.

That's the whole point. And iterate over 256 bytes.

In other words, output a 256-byte comma-separated human-readable ASCII block.

##### Share on other sites

57 minutes ago, Andrew Davie said:

Nice, but not the challenge... You *have* to output the data so it can be cut/paste into source code.

That's the whole point. And iterate over 256 bytes.

In other words, output a 256-byte comma-separated human-readable ASCII block.

There's no need. It solves the general problem you presented in a way that improves both execution time and code size over either a table method or a code method.

##### Share on other sites

It's possible it could have been done simpler in M4, which IIRC was what K&R first proposed as the C preprocessor.  But it's a language in itself and most people didn't want to have to learn 2 languages at once, so most people outside of the Autotools don't even know of its existence.

##### Share on other sites

On 2/17/2021 at 6:28 PM, Andrew Davie said:

I guess the challenge now is... can anyone write a shorter version - any language?

With Perl, from command line:

`perl -E 'say unpack "b8", chr for 0..255' `

With Raku:

`raku -e 'sprintf("%08b",\$_).comb.reverse.join.say for 0..^2⁸'`

Edited by explorer
Raku version, command line

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.