C/C++ trick: static lookup table generation

There are two major ways of using lookup tables (LUTs) in C/C++ code:

  • build them at runtime,
  • embed them in the code.

One major advantage of runtime initialisation is the choice between static initialisation (at program startup), or lazy initialisation (on demand) to save memory. Also, the generating code can be complex, or use information that is only available at runtime.

In the case of an embedded table, the generation cost is only at compile time, which can be very useful. Also, the compiler may take advantage of its early knowledge of the table contents to optimise code. However, quite often the content of embedded tables is abstruse and hardly useful to someone viewing the code. Usually this is due to the use of an external program for generation, sometimes in a completely different language. But the generation can also often be done using the C/C++ preprocessor.

Practical example

Consider the bit interleaving routine at Sean Eron Anderson's Bit Twiddling Hacks page (which, by the way, I recommend you read and bookmark). It uses the following LUT (shortened for brevity):

static const unsigned short MortonTable256[256] = 
{
  0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, 
  0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 
  0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, 
  ... 32 lines in total ...
  0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
};

The MortonTable256 table has, as its name suggests, 256 elements. It was pregenerated by some external piece of code which probably looked like this:

for (int i = 0; i < 256; i++)
    MortonTable256[i] = (i & 1) | ((i & 2) << 1) | ((i & 4) << 2) | ((i & 8) << 3);

The problem with that external piece of code is that it is external. You cannot write it in this form and have it fill the table at compile time.

If you only take the output of this table, the information on how the table was created is lost. It makes it impractical to build another table that has, for instance, all values shifted one bit left. Even if such a table was created using a modified version of the above code, switching between the two tables would be a hassle unless both versions were kept between preprocessor tests.

Preprocessor iterator

Here is one way to get the best of both worlds. First, declare the following iterator macros. They can be declared somewhere in a global .h, maybe with more descriptive names:

#define S4(i)    S1((i)),   S1((i)+1),     S1((i)+2),     S1((i)+3)
#define S16(i)   S4((i)),   S4((i)+4),     S4((i)+8),     S4((i)+12)
#define S64(i)   S16((i)),  S16((i)+16),   S16((i)+32),   S16((i)+48)
#define S256(i)  S64((i)),  S64((i)+64),   S64((i)+128),  S64((i)+192)
#define S1024(i) S256((i)), S256((i)+256), S256((i)+512), S256((i)+768)

Their purpose is simple: calling eg. S16(i) will expand to S1(i), S1(i+1), …, S1(i+15). Similarly, S256(i) will call S1 with values from i to i + 255 times.

And this is how to use them in our example:

static const unsigned short MortonTable256[256] = 
{
#define S1(i) ((i & 1) | ((i & 2) << 1) | ((i & 4) << 2) | ((i & 8) << 3))
    S256(0)
#undef S1
};

That's it! The table will be built at compile time, and you get to keep the logic behind it.

A more complex example

Jeroen van der Zijp's fast half float conversions paper describes table-based methods to convert between 16-bit and 32-bit floating point values. The construction of one of the LUTs is as follows:

void generatetables(){
  for(unsigned int i=0; i<256; ++i){
    int e=i-127;
    if(e<-24){                  // Very small numbers map to zero
      basetable[i|0x000]=0x0000;
      basetable[i|0x100]=0x8000;
    } else if(e<-14){             // Small numbers map to denorms
      basetable[i|0x000]=(0x0400>>(-e-14));
      basetable[i|0x100]=(0x0400>>(-e-14)) | 0x8000;
    } else if(e<=15){             // Normal numbers just lose precision
      basetable[i|0x000]=((e+15)<<10);
      basetable[i|0x100]=((e+15)<<10) | 0x8000;
    } else if(e<128){             // Large numbers map to Infinity
      basetable[i|0x000]=0x7C00;
      basetable[i|0x100]=0xFC00;
    } else{                       // Infinity and NaN's stay Infinity and NaN's
      basetable[i|0x000]=0x7C00;
      basetable[i|0x100]=0xFC00;
    }
  }
}

And this is the compile-time version :

static uint16_t const basetable[512] =
{
#define S1(i) (((i) < 103) ? 0x0000 : \
               ((i) < 113) ? 0x0400 >> (0x1f & (113 - (i))) : \
               ((i) < 143) ? ((i) - 112) << 10 : 0x7c00)
    S256(0),
#undef S1
#define S1(i) (0x8000 | basetable[i])
    S256(0),
#undef S1
};

In this case the macro code is slightly bigger and was slightly rewritten, but is no more complicated than the original code. Note also the elegant reuse of previous values in the second half of the table.

This trick is certainly not new, but since I have found practical uses for it, I thought you may find it useful, too.

  • Posted: 2011-12-20 22:21 (Updated: 2011-12-20 22:26)
  • Author: sam
  • Categories: code tip

Comments

1. anonymous -- 2011-12-21 11:21

An example of a trig lookup table (Taylor series maybe) would be excellent.

2. anonymous -- 2011-12-22 14:42

U should start using D Programming-Language ;).....

3. sam -- 2011-12-22 16:43

@anonymous #1: unfortunately there are two problems with this. First, most parameters for trigonometric functions would at some point use floating point computation, and constant expressions are only available in C++11. Second, I believe Taylor series are not a good solution and better polynomials should be preferred, but the complexity of these polynomials is such that I believe this kind of coefficients are best computed in a separate pass.

4. iliis.junk@gmail.com -- 2013-11-19 15:11

Thanks, this is indeed useful. Something that you may have to look out for is operator precedence:

#define S1(i)  i*10

This will produce wrong results, as i is first replaced by i+x and the evaluation happens afterwards:

S256(0) -> 0*10, 0+1*10, ... , 0+64+1*10, ...

In short: Always surround i with brackets when defining S1:

#define S1(i)  (i)*10
287. This Site -- 2017-02-01 07:26

30YGOE This blog is very good! How did you make it !?

288. Learn More -- 2017-02-01 11:03

7ZjvrB Wow, incredible blog format! How lengthy have you ever been running a blog for? you make blogging look easy. The whole glance of your website is great, as well as the content!

344. XRumerTest -- 2017-04-03 02:05

Hello. And Bye.

345. anonymous -- 2017-11-20 12:16

Practically by definition query tables can devour a great deal of room. Subsequently it is critical that you know about precisely how much space is being expended. The most ideal approach to do this is to utilize the C99 information sorts so you know for beyond any doubt what the fundamental stockpiling unit is. Thus, if your information sort is 'int' at that point I'd recommend that you are doing yourself an insult. If you want information about Assignments please visit our website http://www.assignmentbay.co.uk

346. anonymous -- 2017-11-28 12:30

Play the most amazing online happy wheel game one of the best site for the players you join the best action to play this happy wheels free just click here http://happywheels.me online thanks for the visit here i sure you like this very much.

347. anonymous -- 2018-01-16 08:03

You have posted a great tutorial which i like reading. I have learned a lot from this post. I will share the post with my friends hope they find it informative. Purchase Garage Shelving from http://garageshelvingco.uk/

348. anonymous -- 2018-01-26 08:06

Table generation has been done for the approval of the modes for the people. The use of the paper and https://www.huffingtonpost.com/nancy-laws/the-shocking-truth-about-_5_b_7041934.html to become sound and ideal for the advantageous looks for the individuals.

349. Jake William -- 2018-02-02 12:08

Which is the most excellent C programming book to C programming interviews and practice tricky C MCQ problems? Otherwise I will have to Buy Essay Online Any suggestion.

350. mark petterson -- 2018-02-28 12:49

Writing Spot is the best essay provider in the uk. students can get their essay and coursework project this is the best chance for students because writing spot giving best discounts on his service so get your | Academic Writing Services

351. Marlin -- 2018-03-01 10:36

These tricks are absolutely operating and amazingly easy to understand. I implement this coding peaks in table generation with the rule of C/C++. Now, I have done my essay assignment report on this programming subject but writing format is not accurate. Is there any https://www.7dollaressay.com/editing-services/formatting.php who can make my assignment with proper structure and make it professional?

352. Jane -- 2018-03-17 15:53

Thanks for giving us the explanation with detailed examples. You can try the movie hd app for android. Download this movies hd android app to enjoy films. You can do the download movie hd app new version here. Install the hd movie app and relish with it. Just get the movies application and make use of it.Thank you once again for putting your efforts on this topic. Best!

353. Scott Stevens -- 2018-05-05 07:34

Composing Spot is the best article supplier in the UK. understudies can get their paper and coursework venture this is the most obvious opportunity for understudies since composing spot giving best rebates on his administration so get your.https://www.writemyessays.org.uk/essay-writing-service.php

354. anonymous -- 2018-05-05 11:36

A basic essay includes three primary components: creation, frame, and end. Following this format will help you write and prepare an essay. however, flexibility is essential. even as retaining this primary Essay Writing Essay Writing format in thoughts, permit the topic and particular mission guide the writing and corporation.

355. Nathan -- 2018-05-05 18:43

Get expert Homework help. How often have you ever been sitting slumped over your desk late at night doing a 'warfare' with what looks as if a by no means finishing pile of Do My Homework and in frustration you have got cried out 'why cannot someone simply do my homework for me?' it is so clean to get pissed off.

356. Nina -- 2018-05-07 08:51

We are a Dublin based professional schooling development employer which provides academic assistance to that task Write My Assignment in 0.33 level publications in the USA. Our services encompass assist, consultation, and editing offerings in addition to sampling papers for undergraduate and postgraduate students.

357. Natasha -- 2018-05-07 08:53

Your pattern paper may be finished by using a postgraduate mentor who has completed your particular direction which guarantees an expertise of what's required to attain premiere results. Our Can You Write My Essay for Me true documents may be used as a guideline when drawing close the challenge yourself. We're the first provider in the USA to provide grinds for assignments!

358. quickbooks help support -- 2018-05-15 11:51

If you are using quickbook and if you are having any type of difficulty in using it then contact <a href="http://technicaldeputy.com/">intuit quickbooks support</a> anytime.

359. Ginger -- 2018-05-16 13:28

If you don"t mind proceed with this extraordinary work and I anticipate a greater amount of your magnificent blog entries Ginger

360. Leeks -- 2018-05-16 19:22

It's late finding this act. At least, it's a thing to be familiar with that there are such events exist. I agree with your Blog and I will be back to inspect it more in the future so please keep up your act. Leeks

361. Avocado -- 2018-05-16 22:01

I wish more writers of this sort of substance would take the time you did to explore and compose so well. I am exceptionally awed with your vision and knowledge. Avocado

362. Carrots -- 2018-05-18 21:39

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well.. Carrots

363. Watermelon -- 2018-05-18 21:47

so happy to find good place to many here in the post, the writing is just great, thanks for the post. Watermelon

364. Carbohydrates -- 2018-05-18 21:53

Really impressive post. I read it whole and going to share it with my social circules. I enjoyed your article and planning to rewrite it on my own blog. Carbohydrates

365. Cucumber -- 2018-05-19 12:27

I would also motivate just about every person to save this web page for any favorite assistance to assist posted the appearance. Cucumber

366. Selenium -- 2018-05-19 14:10

This was incredibly an exquisite implementation of your ideas Selenium

367. Kevinngatess92 -- 2018-05-23 08:04

Programming in C++ (or for that remember, in any language) is an existence-lengthy pursuit, and you never prevent learning. In this Best Custom Writing Experts article, I’ve looked at simply the tip of the iceberg; but, in my programming experience going all of the way lower back to the Eighties and even earlier, the issues in this article are factors that, for me as a minimum, arise time and again.

368. Alfredo C. Burgess -- 2018-05-29 06:26

Only Professional Writers Can Make This Kind Of Material, Cheers Managerial Accounting Project Help

369. roberta.gray12 -- 2018-05-29 10:53

Only Professional Writers Can Make This Kind Of Material, Cheers Assignment Help Online

370. anonymous -- 2018-06-07 12:59

Create useful source code for an application and have it compile into linkable object code with no warnings or errors. That is to my knowledge the coolest thing that can happen. https://writecheapessay.com/

Add New Comment