Compile-time look-up table

Go To Last Post
14 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hello All,

I would like to create a compile time lookup table.

In short, I have a scenario that looks like:

packet->commandByte = AddParityByte(COMMAND_FLAG1 | COMMAND_FLAG2);

AddParityByte is a function that implements the calcuation of the parity bit for this device, which will be constant for any particular byte.

Of course, this adds the overhead of calling a function. If I could be bothered, I could create something like:

packet->commandByte = COMMAND_FLAG1_FLAG_2_WITH_PARITY;

But of course becomes a maintainence nightmare if I have to change the flags.

Offline, it's easy to create the lookup table required, but I would like to implement it in the pre-processor such that it just spits out the constant expression.

In other words, I would like to implement the following function using the C pre-processor:

// I want this semantic to compile to a literal 
// if given a hard-coded literal.
//
// A compiler error otherwise
uint8_t LookupHardConstant(uint8_t hardConstant)
{
  switch (hardConstant)
  {
    case 0: return 236;   // These numbers could be whatever
    case 1: return 17;
    ....
    case 255: return 148
  }
}

Does anyone know of a way to do this?

-- Damien

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

did you check what the compiler generated in the first place? The optimizer may surprise you.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

glitch wrote:
did you check what the compiler generated in the first place? The optimizer may surprise you.

Damn... makes me wish I had brought my laptop home from work :P

It was implemented as a function with all the necessary bit-shifts for the calculation. I still need it written as a function for the return data, but it will save some run-time (and flash space) if I can reduce fixed commands to a constant expression at compile time.

I might implement something shortly and have a look... I need an excuse to setup the AVR toolchain for Linux :)

-- Damien

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I know how to this in AVR Studio's ASM2, and I'm pretty sure you can do the equivalent with C.

You could create a big multi line macro with a whole bunch of #if statements to act as the switch.

Something kinda like (but probably still wrong)

#define LookupHardConstant (hardConstant) \
  #if hardConstant == 0 \
      236 \
  #elif hardConstant == 1 \
      17   \
....
  #endif  \

you could generate this pretty easily using an excel spreadsheet.

The backslash at the end of every line tells the compiler it is still part of the macro definition.

I'm still learning C, so I have no idea if it will work, but it might!

Adam
http://en.wikipedia.org/wiki/C_p...

-
Adam Fraser-Kruck

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

#defines cannot contain additional macro directives, so the #if will not work. however, normal C statements are fine, and given a constant input, and constant output, the compiler should reduce it down to just the selected constant.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Don't know if this helps, but concatenation may be another option-

//'indirect' usage example
#define TEST1 1
//the 'table'
#define P_0 236
#define P_1 17
//the macros
//two needed to expand n if n is
//also a define
#define _LOOKUP_P(n) P_##n
#define LOOKUP_P(n) _LOOKUP_P(n)
//example
PORTB=LOOKUP_P(0);
PORTB=LOOKUP_P(TEST1);
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

My general inclination is to avoid the preprocessor until there is no alternative. I'm at home and don't have access to avr-gcc, but I suspect that if you do

static const uint6_t ptbl[256] = {
236,
17,
//...
248 };

//...

    uint8_t parity = ptbl[hardConstant];

//...

that the gcc will be clever enough to realise that it can substitute the table lookup with a simple load of the appropriate constant, which is I think what you want. Whether it will be clever enough then to eliminate the table from the object code I am not so sure.

It's definitely worth an experiment, but if ever you use the table with a non-compile-time-constant index, then you will definitely link 256 bytes of table into your object code.

Christopher Hicks
==

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

static const goes into sram.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

only if the table does not get optimized away.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well, if there already is an algorithm to calculate the parity byte from the original message, the same algorithm might also be performed by preprocessor. I would not try CRC with preprocessor though, but simple checksums should work.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

glitch wrote:
did you check what the compiler generated in the first place? The optimizer may surprise you.

The optimiser did surprise me :)

Using:

damien@damien-desktop:~/code/avr/compile_time_table$ avr-gcc --version
avr-gcc (GCC) 4.3.3

And optimisation switch -Os:


#include 
#include 

static inline uint8_t ConstantLookupTable(uint8_t input)
{
    switch(input)
    {
        case 0:  return 128;
        case 1:  return 129;
        case 2:  return 255;
        case 3:  return 0;
        default: return 55;
    }
}

int main(void)
{
    while(1)
    {
        PORTB_OUT = ConstantLookupTable((1 << 6) | (1 << 2));
    }

    return 0;
}

Yields the following:

int main(void)
{
    while(1)
    {
        PORTB_OUT = ConstantLookupTable((1 << 6) | (1 << 2));
 244:	87 e3       	ldi	r24, 0x37	; 55
 246:	80 93 24 06 	sts	0x0624, r24
 24a:	fd cf       	rjmp	.-6      	; 0x246 

0000024c <_exit>:
 24c:	f8 94       	cli

0000024e <__stop_program>:
 24e:	ff cf       	rjmp	.-2      	; 0x24e <__stop_program>

Yep, loads a literal :)

-- Damien

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

STS? What is PORTB_OUT declared as?

Why is it using "sts 0x0624, r24" instead of "out"?

-
Adam Fraser-Kruck

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

As 0x624 is a memory address then presumably PORTB_OUT is just a variable holding a value that will later be output to PORTB.

I guess the confusing name is using all upper case for a variable name when that's usually reserved for macro names.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

adam_fk wrote:
STS? What is PORTB_OUT declared as?

Why is it using "sts 0x0624, r24" instead of "out"?

It's compiled for an atxmega128A1. IIRC the registers are mapped into the memory space. PORTB_OUT is defined as:

#define PORTB_OUT  _SFR_MEM8(0x0624)