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/

371. anonymous -- 2018-07-01 12:44

Thanks for the <a href="https://nrs.com/">great</a> post. [url="https://www.ua.com/"]great[/url]

Wiki Sentex

372. anonymous -- 2018-07-16 18:18

It is easier and more convenient for their employees, in which employees will be able to access Kroger-related news and information, work schedule, discounts and much more. https://greatpeopleme.xyz/www-greatpeople-me/

373. Jason -- 2018-07-24 11:21

Great post thanks for sharing https://mymaleextrareview.com/

374. anonymous -- 2018-07-28 14:32

I really like what you guys are usually up too. This sort of clever work and exposure! Keep up the superb works guys I've incorporated you guys to my blogroll.

https://www.creditcardvalid.com/4-best-credit-card-products-bad-credit-history/

375. free essay samples -- 2018-07-31 08:10

I have taken time to go through the article and i recommend to those students looking for research materials. We also offer free essay samples https://www.rightwritings.com/compare-two-cities-essay/

376. anonymous -- 2018-07-31 22:55

After the registration of your gift card you need activate your card by using your Gift Card verification number, card account number, and the CVV number. https://mygiftcardsitee.xyz/www-mygiftcardsite-com/

377. anonymous -- 2018-08-07 08:25

Students often feel issues in writing assignment, so to make students comfortable in assignment we help them to write their assignments. If ever you feel any problem in writing something you can visit our website Assignment Help. https://www.allassignmenthelp.com/

378. Best Writers Reviews -- 2018-08-08 13:07

Our My Assignment Help Reviews go through hundreds of websites each month to select only the best. We also offer reviews of such websites which are not up to the mark so that you may know about them as well. http://www.bestwritersreviews.com/a-review-on-allassignmenthelp-com

379. infonicnisha@gmail.com -- 2018-08-14 08:16

Be a topper of your university by taking nursing assignment help Nursing Assignment Help https://www.studentsassignmenthelp.com/nursing-assignment-help/ from the professional experts of StudentsAssignmentHelp.com. We have highly qualified and certified professionals they make your task easy.

380. Assignment help Ireland -- 2018-08-14 13:53

Get the assignment help Ireland services by the expert assignment writers at Students Assignment Help. Our experts are fluent in writing assignments without missing the deadlines as they have earned their degrees from the renowned colleges and universities around the world. For more info visit https://www.studentsassignmenthelp.com/ie/

Add New Comment