0

In this answer about brute-forcing 2048 AI, a lookup table storing "2048 array shifts" is precomputed to save needless repetitive calculation. In C, to compute this lookup table at compile time, the way I know of is the "caveman-simple solution" where the table itself is generated as another file that is then #included, something like this python script to generate lut.include (replace with 2048-specific code):

#!/usr/bin/python

def swapbits(x):
    ret=0
    for i in range(8):
        if x&(1<<i): ret |= 1<<(7-i)
    return ret

print "const uint8_t bitswap[] = {",
print ", ".join("0x%02x"%swapbits(x) for x in range(256)),
print "}"

Is there any cleaner approach? That is, maybe some preprocessor trickery to generate these tables? With C++ this should be possible with constexpr.

KamilCuk
  • 120,984
  • 8
  • 59
  • 111
qwr
  • 9,525
  • 5
  • 58
  • 102
  • 3
    In short: No there's no other way. C doesn't have any compile-time computing abilities. – Some programmer dude Dec 03 '21 at 21:00
  • Are you using a build tool like make or cmake? – Pat9RB Dec 03 '21 at 22:48
  • This is a simple program where the array is fixed but it would not be hard to incorporate build tools if I needed to – qwr Dec 03 '21 at 23:54
  • `any cleaner approach?` What is "cleaner"? How to measure this property of code? – KamilCuk Dec 04 '21 at 02:09
  • Cleaner meaning does not involve another script and included file, with any code readability improvements that come along with that. – qwr Dec 04 '21 at 12:36
  • You can use a bunch of macros, I did this many years ago for table-driven CRC calculation. Unfortunately I don't have access to that code anymore, and even if I had, it's closed-source. One lesson I learned: Some compilers limit the allowed line length after expanding macros and/or the number of macros. Using `enum` is a possible solution. Again unfortunately, I don't have the time to work out an example for an answer. You might find something if you search the web with this idea. – the busybee Dec 04 '21 at 13:53
  • `Cleaner meaning does not involve another script and included file` C preprocessor has no loops, no if statements, not conditional. In C preprocessor, one way or the other, you _have to_ enumerate all possible cases. You can write calculations in it, but you end up writing 256 consecutive numbers anyway. I doubt that will make it any "cleaner". – KamilCuk Dec 25 '21 at 10:15

1 Answers1

1

C preprocessor has no loops. You have to write all numbers in C preprocessor, one way or the other.

Cleaner meaning does not involve another script and included file

First, implement a constant expression swapping bits:

#define SWAPBITS(x)  ((x&1)<<7)|((x&2)<<6)|((x&3)<<5).... etc.

Then you just write all the numbers:

const uint8_t arr[] = 
   SWAPBITS(0),
   SWAPBITS(1),
   ... etc. ...
   // Because you do not want to use external script, write all the numbers manually here.
};

If the "included file" can be lifted, you can use BOOST_PP_REPEAT. Note that that macro literally lists all iterations it can be called with. Similar with P99_REPEAT from p99 library.

#include <boost/preprocessor/repetition/repeat.hpp>
#define SWAPBITS(x)  .. as above ..
#define SWAPBITS_DECL(z, n, t)  SWAPBITS(n),
const uint8_t arr[] = {
   BOOST_PP_REPEAT(256, SWAPBITS_DECL,)
};
KamilCuk
  • 120,984
  • 8
  • 59
  • 111
  • Doesn't the C PP have `#if` for conditional? Also are there any GCC specific extensions that allow looping? – qwr Dec 25 '21 at 20:20
  • Right, you are right. What I was thinking about is that you can't do that "inline" inside a macro `#define MACRO { #if stuff #deifne this #else #define this #endif }`. So some expressions are not possible - basically macro expansion has to expand to single syntactic form. If that would be possible - macros could define other macros, conditionally - then one way or the other people would find a way to write loops. – KamilCuk Dec 25 '21 at 20:23
  • @qwr: No, no looping extensions that I've ever heard of. People have accomplished loop-like behavior with recursive includes, e.g. https://www.ioccc.org/1995/vanschnitz.c, but this is best left to the IOCCC. – Nate Eldredge Dec 25 '21 at 20:36
  • `are there any GCC specific extensions that allow looping?` No. PPl just preprocess files with other preprocessors - M4 most notably, but nowadays other templating languages, or just write short generators, just like you did. It happens that C code is generated, it quite normal. – KamilCuk Dec 25 '21 at 21:00