Can you perform fixed-length bit reversal in #defines / preprocessor directives?

Question

I am writing C code (not c++) for a target with very limited ROM, but I want the code to be easy to customize for other similar targets with #defines. I have #defines used to specify the address and other values of the device, but as a code-saving technique, these values are necessary bitwise reversed. I can enter these by first manually reversing them, but this would be confusing for future use. Can I define some sort of macro that performs a bitwise reversal?

I interpret this as asking about reversing constants (i.e. you want to do the work at compile time.) Is this correct? — pburka, Oct 25 '13 at 15:20

score 3 · Answer 1 · edited May 23 '17 at 10:28

3

As seen here (Best Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C), there is no single operation to switch the order in c. Because of this, if you were to create a #define macro to perform the operation, it would actually perform quite a bit of work on each use (as well as significantly increasing the size of your binary if used often). I would recommend manually creating the other ordered constant and just using clear documentation to ensure the information about them is not lost.

edited May 23 '17 at 10:28

Community

1
1

answered Oct 25 '13 at 15:01

Andrew Ring

3,185
1
23
28

+1: for the most straight forward approach of providing *clear* documentation. – alk Oct 25 '13 at 15:07
If it's only used on constants, it won't increase the size of the code at all. – R.. GitHub STOP HELPING ICE Oct 25 '13 at 15:34
I can agree that the compiler might resolve the calculation on the constants resulting in the constant only, however depending on your algorithm and compiler in use, it may instead leave a set of inlined instructions. In this case, that set of instructions would be replacing your 'constant' for every use of it. This, in turn, will increase the size of the *binary* (not the code). Since the target is a limited ROM, these extra instructions may be unacceptable. – Andrew Ring Oct 25 '13 at 15:38
1

As long as it's a constant expression the compiler must be capable of evaluating it at compile time, but isn't required to do so. See http://stackoverflow.com/questions/436300/are-constant-c-expressions-evaluated-at-compile-time-or-at-runtime for more info. Of course there's never any guarantee that a compiler won't replace a constant with instructions that result in the same value. – pburka Oct 25 '13 at 16:34

score 1 · Answer 2 · answered Oct 25 '13 at 15:08

For the sake of readable code I'd not recommend it, but you could do something like

#define NUMBER 2

#define BIT_0(number_) ((number_ & (1<<0)) >> 0)
#define BIT_1(number_) ((number_ & (1<<1)) >> 1)

#define REVERSE_BITS(number_) ((BIT_1(number_) << 0) + (BIT_0(number_) << 1))

int main() {

    printf("%d --> %d", NUMBER, REVERSE_BITS(NUMBER));

}

rici · Answer 3 · 2013-10-25T18:12:56.257

There are techniques for this kind of operation (see the Boost Preprocessor library, for example), but most of the time the easiest solution is to use an external preprocessor written in some language in which bit manipulation is easier.

For example, here is a little python script which will replace all instances of @REV(xxxx)@ where xxxx is a hexadecimal string with the bit-reversed constant of the same length:

#!/bin/python
import re
import sys

reg = re.compile("""@REV\(([0-9a-fA-F]+)\)@""")
def revbits(s):
  return "0X%x" % int(bin(int(s, base=16))[-1:1:-1].ljust(4*len(s), '0'), base=2)

for l in sys.stdin:
  sys.stdout.write(reg.sub(lambda m: revbits(m.group(1)), l))

And here is a version in awk:

awk 'BEGIN{R["0"]="0";R["1"]="8";R["2"]="4";R["3"]="C";
           R["4"]="2";R["5"]="A";R["6"]="6";R["7"]="E";
           R["8"]="1";R["9"]="9";R["A"]="5";R["B"]="D";
           R["C"]="3";R["D"]="B";R["E"]="7";R["F"]="F";
           R["a"]="5";R["b"]="D";R["c"]="3";R["d"]="B";
           R["e"]="7";R["f"]="F";}

     function bitrev(x,    i, r) {
       r = ""
       for (i = length(x); i; --i)
         r = r R[substr(x,i,1)]
       return r 
     }
     {while (match($0, /@REV\([[:xdigit:]]+\)@/))
        $0 = substr($0, 1, RSTART-1) "0X" bitrev(substr($0, RSTART+5, RLENGTH-7)) substr($0, RSTART+RLENGTH)
     }1' \
     <<<"foo @REV(23)@ yy @REV(9)@ @REV(DEADBEEF)@"
foo 0X32 yy 0X9 0Xfeebdaed

pburka · Accepted Answer · 2013-10-26T01:36:24.187

I think something like this ought to work:

#define REV2(x)  ((((x)&1)<<1) | (((x)>>1)&1))
#define REV4(x)  ((REV2(x)<<2) | (REV2((x)>>2)))
#define REV8(x)  ((REV4(x)<<4) | (REV4((x)>>4)))
#define REV16(x) ((REV8(x)<<8) | (REV8((x)>>8)))
#define REV32(x) ((REV16(x)<<16) | (REV16((x)>>16)))

It uses only simple operations which are all safe for constant expressions, and it's very likely that the compiler will evaluate these at compile time.

You can ensure that they're evaluated at compile time by using them in a context which requires a constant expression. For example, you could initialize a static variable or declare an enum:

enum {
    VAL_A = SOME_NUMBER,
    LAV_A = REV32(VAL_A),
};

Can you perform fixed-length bit reversal in #defines / preprocessor directives?

4 Answers4