{
  "$type": "site.standard.document",
  "description": "String Interpolation Is All You Need.",
  "path": "/blog/abusing-the-c-preprocessor/",
  "publishedAt": "2013-10-01T00:00:00+00:00",
  "site": "at://did:plc:wamidydbgu3u6fk3yckaglnz/site.standard.publication/self",
  "tags": [
    "c",
    "cursed"
  ],
  "textContent": "I've always wondered what could be done with the C preprocessor. The existence of projects such as Boost Preprocessor and the infamous Brainfuck interpreter are a testament to its wide-ranging capabilities.\nOf course, the best way to learn is to do, and I felt like indulging in some masochism. So - onwards!\nToken pasting is the main (see: only) operation in the C preprocessor. Two tokens (input strings) are added together (concatenated); while this seems rather limited, you'll see it has plenty of potential:\nWe use two macros here because our main c:JOIN macro needs to expand its arguments (which will be macros themselves!) before passing it onto c:JOIN_INTERNAL - otherwise, the macros will go through without being expanded, which will not produce the desired results.\nBinary Operators\nXOR\nAND\nNow, we have token pasting. We know that we can add together tokens to produce new tokens. Say we have two tokens, representing bits: c:0 and c:1. If we token paste them together, we get c:01. Now, if we token paste that with another token, say c:XOR_, we can get c:XOR_01, which is another token.\nWe know that the preprocessor is all too happy to expand these - so what if we made a truth table of tokens? By defining macros which correspond to our tokens (c:XOR_00, c:XOR_01, etc), the values of these macros are substituted when we token paste c:XOR_, c:0, and c:1 together - we have created an operator!\nBy defining the truth table for XOR and AND, we've set up the basic building blocks that we need for our 4-bit adder.\nFull Adder\nHere lies the core of the adder. These macros transcode the logic behind the full adder - the equations have been reproduced in the comments.\nThese macros basically chain together the c:XOR and c:AND operators we made before, so that we can calculate the output and Carry Out bits from our input (the A, B and Carry In bits).\nTo calculate an addition, we call c:FULL_ADD_OUT and c:FULL_ADD_CARRY for each output bit; the parameters are the corresponding input bits, and the Carry Out from the last bit. Basically, we chain each full adder by its Carry Out output. For the first full adder, we simply pass 0 into Carry In.\nConversion\nBinary numbers are a convenient representation for computational arithmetic, as we can see in our implementation of the full adder. Unfortunately, they're slightly less convenient for humans and compilers expecting human input. With some clever token pasting trickery, we can define conversion operators:\nc:NUMBER_TO_BINARY takes in a base-10 number from 0 to 15, adds it to c:NUMBER_TO_BINARY_, and then returns the appropriate token; this expands to the binary format that our adder uses.\nc:BINARY_TO_NUMBER takes in four bits, pastes them together (c:0, 1, 1, 0 becomes c:0110), and then pastes that with c:BINARY_TO_NUMBER_, which expands to a normal base-10 number.\nOf note is that there are two macros - c:BINARY_TO_NUMBER_INTERNAL, and c:BINARY_TO_NUMBER. You see, this macro suffers from the same problem as c:JOIN - it needs to expand its arguments before we can use it! c:BINARY_TO_NUMBER simply expands the arguments and passes it to c:BINARY_TO_NUMBER_INTERNAL, which produces the correct token.\nFour-Bit Addition\nAnd now: four-bit addition. Looks nasty? That's because it is. This macro spits out four bits, just like our c:NUMBER_TO_BINARY macros.\nEach bit is the result of c:FULL_ADD_OUT; as there's no way to save the c:FULL_ADD_CARRY from each bit, we deal with this problem in a questionable manner: we manually nest the c:FULL_ADD_CARRY macros. The last bit has no carry, so we set it to zero; the second-last bit has the carry from the last bit; the third-last bit has the carry from the second-last bit, which is itself defined in terms of the last bit's carry; and so on, until we reach the first bit.\nAfter unpacking, we can see that this is a rather simple process that results in the 4-bit addition of the numbers we pass in. We have to wrap c:ADD_A_B_4BIT in c:ADD_A_B_4BIT_NUMBERS so that macros that we pass in, such as the c:NUMBER macros, get converted to binary. Phew!\nTesting\nFor the conclusion, our test case. We have our standard c:int main() function, and a seemingly standard c:printf showing an addition. But wait! In lieu of actual numbers, we have c:NUMBER_1, c:NUMBER_2, and our addition macro.\nc:NUMBER_1 and c:NUMBER_2 aren't defined in the actual code: we provide them as a compile-time argument (via -D). This code is relatively simple: our two numbers are converted to binary, run through our addition macro, and the result is converted back into a number, just in time to be passed into our c:printf.\nTime to test this sucker!\nAin't she a beaut?\nAnd to round things out, here's the expanded version of the c:int main() function after the C preprocessor has run.\nI hope you've enjoyed this brief look at the mysterious, powerful, and quite frankly insane C preprocessor. A compiling version of the full code can be found here. At the time of testing, this code worked in GCC and Clang, but not Visual C++.",
  "title": "Abusing The C Preprocessor: Writing A 4-Bit Adder"
}