+Andrew Davie Posted February 17, 2021 Share Posted February 17, 2021 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. 5 Quote Link to comment Share on other sites More sharing options...
+splendidnut Posted February 17, 2021 Share Posted February 17, 2021 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) Quote Link to comment Share on other sites More sharing options...
+Andrew Davie Posted February 17, 2021 Author Share Posted February 17, 2021 (edited) 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 February 17, 2021 by Andrew Davie replaced with a more elegant line 1 Quote Link to comment Share on other sites More sharing options...
+batari Posted February 17, 2021 Share Posted February 17, 2021 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! 2 Quote Link to comment Share on other sites More sharing options...
+Andrew Davie Posted February 17, 2021 Author Share Posted February 17, 2021 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. Quote Link to comment Share on other sites More sharing options...
+batari Posted February 17, 2021 Share Posted February 17, 2021 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. Quote Link to comment Share on other sites More sharing options...
ChildOfCv Posted February 17, 2021 Share Posted February 17, 2021 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. Quote Link to comment Share on other sites More sharing options...
explorer Posted February 18, 2021 Share Posted February 18, 2021 (edited) 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 November 15, 2022 by explorer Raku version, command line 2 Quote Link to comment Share on other sites More sharing options...
Recommended Posts
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.