Jump to content
IGNORED

Reverse bit-generation in C at compile-time


Andrew Davie

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 :P

// 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.

 

 

  • Like 5
Link to comment
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.

 

ADDENDUM

 

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)

Link to comment
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
  • Like 1
Link to comment
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!

  • Like 2
Link to comment
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.

 

 

Link to comment
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.

Link to comment
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
  • Like 2
Link to comment
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...