Calculate CRC32 strings in compile-time

By its programmer nature, I really dislike nonoptimality and redundancy in code. And so, reading once again at work the source code of our project, again came across one feature in the way of translating product strings into different languages.

Localization here is quite simple. All strings requiring translation are wrapped in the _TR() macro:

 wprintf(L"%s\n", _TR("Some translating string")); 

The macro returns the desired version of the text depending on the currently used language. It is defined as follows:

 #define _TR(x) g_Translator.Translate(x) 

Here, the global object g_Translator , which, in the Translate() function, counts crc32 from the specified line in runtime, searches in its xml-base for a translation with a matching checksum and returns it.

I will not judge whether such a decision is justified, but it is time-tested and proved to be quite reliable. And everything would be fine, but such a solution is not without flaws: in fact, the function does extra work - the checksums could be calculated once at the compilation stage, and later used ready-made numerical values. It would also eliminate the need to store duplicate strings in the executable image, because they are already in the external xml file with translations.
')
A little googling at the request of “compile-time crc32” I quickly realized that the task was not the most trivial, but I could not find any ready-made solutions.

Using template metaprogramming in its pure form, unfortunately, will not work here. Any reference to the characters of the string used as a template parameter prevents the compiler from minimizing recursive calls to the template function. For example, this article discusses creating only tables for crc32 calculations. And from the fully standard-compliant solutions there was only one - Boost.MPL . Here it is proposed to use the following entry form:

 meta::hash_cstring< mpl::string<'bunn','ies'> >::value; 

Instead of using string literals, it is proposed to break the string into pieces and give it to individual template parameters. But besides the bizarreness of the record used, in order to convert all 2450 lines of the project to this form, you would have to write an external code generator and teach the entire project team a new form of recording.
Slipped on the forums also messages that in the new C ++ 11 this idea is implemented using the classic template metaprogramming and the keyword constexpr , but, unfortunately, it is not possible to simply transfer the project from a long pedigree to a new standard.

There was another idea using a code generator. It would be possible to make a pre-build event, on which to translate strings to this form:

 _TR(0x12345678/*"Some hashing string"*/); 

But again, I wanted something universal ... I wanted such a magical _TR() , which would simply leave behind pure crc32 without any extra movements. And then I started to reinvent my bike.

Attempt # 1. Pure macros

At this stage, there was only one thought in my head: apart from templates, macros are computed before compilation - you need to use them!

I created a new project in Visual Studio, setting the optimization settings to maximum inline and maximum speed. I decided to analyze the success / failure of folding the lines to the hash in the well-known user-mode debugger OllyDbg , so I would like to see in the resulting exe only one small section per code and data without unnecessary garbage. To do this, I disabled the C-runtime, which, together with several other receivers, allowed me to get an empty exe of only 2 KB in size.

After several experiments, I gave the simplest implementation of the crc32 calculation for strings of no more than 3 characters:

 static const unsigned int Crc32Table[256] = { 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, /* ... ,*/ 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D }; template <typename T, int N> char (&array_length(T (&)[N]))[N]; //       #define lengthof(x) (sizeof(array_length(x))) //    crc32 #define TR_CRC(crc,i,s) (crc >> 8)^Crc32Table[(crc^s[i])&0xFF] //            #define TR_CRC_COND(crc,i,s) (i<lengthof(s)-1 ? TR_CRC(crc,i,s):crc) //   CRC     ( 3 ) #define _TR(s) TR_CRC_COND(TR_CRC_COND(TR_CRC_COND(TR_CRC_COND(0xFFFFFFFF,0,s),1,s),2,s),3,s)^0xFFFFFFFF int main(int argc, char *argv[]) { //     ,    - DWORD, //             Olly Sleep(_TR("123")); } 

In the implementation of macros, the main problem is that we cannot expand the cycle of calculating crc for the required number of iterations along the length of the string, as in template metaprogramming. A macro will always recount as many iterations as it should be laid initially. For example, in the example above, the string "1" would still be calculated in 4 iterations (maximum 3 characters + '\ 0'), despite the fact that it has only one character length. This is bypassed by a conditional operation that slips the value of crc from the previous iteration, if the string is already calculated to the last character.

Running the resulting exe in the debugger, I saw the cherished PUSH 884863D2 , the correctness of which calculation is easily confirmed by the first online crc32 calculator.



It's time to see how much the compilation rate drops, if you spread the macro for the length of the line that allowed you to cover the requirements of the project. The longest line in the translation database was a little shorter than 350 characters, so I wanted to lay at least the limit of 500 characters.

Thus, I generated the macro body, in abbreviated form, which looked like this:

 #define _TR(s) TR_CRC_COND(TR_CRC_COND(/*...*/TR_CRC_COND(TR_CRC_COND(0xFFFFFFFF,0,s),1,s),2,s),3,s)/*...*/,448,s),449,s)^0xFFFFFFFF 

But here I was disappointed when the compiler gave its cold: "fatal error C1009: compiler limit: macros nested too deeply . " Empirically, we managed to find out that the nesting limit is somewhere in the region of 300.

Attempt # 2. __Forceinline function

Then there were still several attempts to use inline functions instead of nested macros, but everything eventually slipped into either a similar error (I don’t remember exactly, but the compiler cursed too complicated grammar) or an excessively long compilation.

After all the torment, I was almost ready to abandon this idea, but I decided to try to write one large __forceinline function with a bunch of consecutive calculations and line length checks (for some reason I was sure that such a compiler would never turn into a constant):

 //  ,       #define CRC_STUB_(i) if (i<N-1) { crc = (crc>>8) ^ Crc32Table[(crc^s[i])&0xFF] } template <int N> static __forceinline DWORD CRC_ARR_CALC_(const char (&s)[N]) { static const unsigned int Crc32Table[256] = { 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, /* ... ,*/ 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D }; DWORD crc = 0; CRC_STUB_(0);CRC_STUB_(1);CRC_STUB_(2);CRC_STUB_(3);CRC_STUB_(4);CRC_STUB_(5);CRC_STUB_(6);CRC_STUB_(7);CRC_STUB_(8);CRC_STUB_(9);CRC_STUB_(10);CRC_STUB_(11);CRC_STUB_(12);CRC_STUB_(13);CRC_STUB_(14);CRC_STUB_(15);CRC_STUB_(16);CRC_STUB_(17); /* ... */ CRC_STUB_(498);CRC_STUB_(499); return crc; } 

And it worked! The compiler pretty quickly folded the whole code into one number, leaving neither the rows themselves nor even the Crc32Table table in the resulting binary. To correctly compile such an implementation, only the / O2 switch is sufficient. It only remained to add the overloaded version of the g_Translator.Translate() method with crc32 as a parameter, and the g_Translator.Translate() .

After introducing the code into the project, the compilation of the release build became longer by 1-2 minutes, but the binary has become easier by 200 Kb, and now it doesn’t make the processors of users involved in unnecessary work, allowing their laptops to work on battery a little longer :)

The full source for the test project can be found here: 7z , tar.gz