How to define 14-bit lookup table for PIC/XC8 (if it's possible to do without assembly)?

Question

I'm writing the firmware for a simple testing device that would need to store a very large lookup table (I need 13500 entries with values 0..100 decimal). The target PIC MCU is PIC16F1829 (8K words of program memory), and the compiler is XC8.

Obviously, this won't work:

static const uint8_t table[13500] = { 0x01, 0x23, ... };

as it will be stored as a sequence of RETLW instructions, each taking one program word, and we only have ~8K of these.

However, I can pack two 7-bit values into one 14-bit word, so if I had the capability of doing

static const uint14_t table[6750] = { 0x1181, ... };

I can imagine that reading table[0] should translate to using the flash memory read functionality to read the progmem word there. I can do the unpacking afterwards.

The actual setup/work code on the MCU would be quite minimal, about 300 words, so I'm within bounds.

Is there a way to define such arrays cleanly (using C constructs only), or one has to resort to assembly, as discussed here?

Edit:

The intended use of this lookup table is to replay a specific waveform using filtered PWM. The setup/work code is very minimal, it only initializes the PWM module and writes the waveform to the PWM period register at regular intervals. I don't think the unpacking would add a lot of code, it's just a few shifts.

Edit #2:

Since some of answers/comments suggest or assume properties of the data and suggest not storing it in full, but using interpolation, computation or compression:

The data comes from measured physical quantity which was recorded via a separate device. Reproducing it verbatim is important (so interpolation isn't recommended). It is also reasonably random, since gzip only achieves 35% compression when the data is stored in binary, in bytes. Since each byte only uses 101 different values instead of 255, by Huffman encoding alone you'd expect ~17% compression. Also the cost of adding the inflate algorithm for this PIC is probably more than the compression saves...

Edit #3:

The RETLW trick the XC8 compiler uses seems to not be a common knowledge, so let's explain why I'm talking about RETLW all the time and dismissing answers because of it.

The 8-bit PIC micros are examples of a Harvard architecture, with separated code and data address spaces. So if you wanted an initialized global array like

char mytable[5] = { 1, 2, 3, 4, 5 };

storing these 5 bytes is not as simple as putting them somewhere in the flash inside the PIC and later mapping them into the data segment, You just cannot say "these 5 bytes are part of the data segment". Since this code is valid C, XC8 has to implement it by running some initialization code that literally does something akin to mytable[0] = 1; mytable[1] = 2; .... This is very expensive in terms of code space required to do this initialization and is to be avoided by any seasoned PIC dev.

However, you can forego some of this penalty by making your table const:

const char mytable[5] = { 1, 2, 3, 4, 5 };

Since the compiler knows you cannot change those values, you might get away with not actually keeping them in the data address space. They may reside in the code address space only. So if you wanted mytable[i], the compiler internally replaces it with a function call (something like fetch_mytable(i)), and implements this function using an array of instructions in the code address space, something like this

... prologue: address computation, jump to address ...
retlw 1
retlw 2
retlw 3
retlw 4
retlw 5

This is the body of the function fetch_mytable(i), and in the prologue you do a computed goto based on i, and the respective RETLW instruction is jumped to; it stores the desired value into the W register and returns from the function.

This method is simple and quick, and is a first class citizen in the XC8 compiler environment - it does this kind of trick quietly under the hood for static/global const arrays.

My gripe with this method is that it takes 5 program words (70 bits = 5*14) to store just 40 bits worth of data (5*8). Each RETLW instruction "wastes" 6 bits for the RETLW opcode. Each PIC instruction is 14 bits, the program memory is organized into words of 14 bits, but this is not exposed in C.

Another approach for implementing a lookup table is similar, but instead of the RETLW array, up to 14 bit values can be stored in the program memory directly. And instead of doing a computed goto, use the program memory readout mechanism (EEADR/EECON1 et al) to read the program word of a particular address. This approach is slower, as it requires more boilerplate readout code, but doesn't waste any bits, and for a large array it really makes a difference.

So my question is whether this second approach can also be accessed from C, as a first class citizen, just like the other method. I've tried making an array of uint16_t's, but still the first method is used, with each uint16 being represented by a pair of RETLWs.

Answer 1

You ask the question "How to define 14-bit lookup table for PIC/XC8 (if it's possible to do without assembly)?"

It is almost possible to do this in XC8 without assembly. Assembly must be used to define the table because XC8 does not have any C language extension to declare constant data in code space as packed 14-bit words.

To do this requires at least two source files.

C language file:

/*
 * File:     main.c
 * Author:   dan1138
 * Target:   PIC16F1829
 * Compiler: XC8 v2.00
 * IDE:      MPLABX v5.10
 *
 * Created on February 25, 2019, 12:24 AM
 */
#include <xc.h>
#include <stdint.h>
typedef unsigned char   uint7_t;

extern const uint7_t PWM_Table;
extern const uint7_t PWM_TableEnd;

volatile uint16_t Address_PWM_Table;

uint7_t ReadPWM_Table( void ) 
{
    uint8_t INTCON_save;
    uint7_t TableValue;

    INTCON_save = INTCON;
    EEADR = Address_PWM_Table >> 1;
    EECON1bits.CFGS = 0;
    EECON1bits.EEPGD = 1;
    INTCONbits.GIE = 0;
    EECON1bits.RD = 1;
    NOP();
    NOP();
    if (INTCON_save & 0x80) INTCONbits.GIE = 1;
    if (!(Address_PWM_Table & 1))
    {
        TableValue = EEDATL & 0x7F;
    }
    else 
    {
        TableValue = ( EEDATH << 1 );
        if (EEDATL & 0x80) TableValue |= 1;
    }
    Address_PWM_Table++;
    return TableValue;
}
/* 
 * Main application
 */
volatile uint7_t DataFromTable;
void main(void) 
{
    /* 
     * Main application loop
     */
    uint16_t TableElements;

    for(;;)
    {
        Address_PWM_Table = ((unsigned int)&PWM_Table)<<1;
        TableElements = (unsigned int)(&PWM_TableEnd-&PWM_Table)<<1;
        if (TableElements) do
        {
            DataFromTable = ReadPWM_Table();
        } while (TableElements--);
    }
}

Assembly language file:

; 
; File:     PWM_Table.as
; Author:   dan1138
; Target:   PIC16F1829
; Compiler: XC8 v2.00
; IDE:      MPLABX v5.10
; 
; Created on February 25, 2019, 12:24 AM
;   
; The DABS directive allows ASPIC code to "reserve" a range of code space
; and prevent the linker from locating anything there.
; 
; Using the psect "abs" option allows the ASPIC code to declare code and
; ignores the class bindings.
;
; Finally the "org" ASPIC directive can place the psect at where the DABS
; directive reserved the memory area.
;
; This example defines a PWM_Table of 13500 7-bit values.
; 
; Note: There is a drawback with this method. An absolute psect storage
; does not get counted as allocated space by the linker. This makes the
; storage usage map inaccurate.
; 
#include <xc.inc>

    global _PWM_Table,_PWM_TableEnd
;
; Pack two 7-bit values in one 14-bit instruction word
;
; Walk a one bit through all 7 bits of a table read.
;
    psect   PWM_Table,abs,class=PWMTAB,delta=2,noexec ; PIC10/12/16
    org       0x5a2
    DABS    0,0x5a2,6750  ; 0=code space, 0x5a2=start address, 6750=number of instruction words. These values must be numeric constants.
_PWM_Table: 
    rept (13500/12)
    dw 0x0101,0x0404,0x1010,0x1040,0x0410,0x0104
    endm
_PWM_TableEnd:

Answer 2

If the values in the table / array go from small to large (ie in order) then you can put them into excel, plot it and fit a trend line then get the equation. Then your code only needs to do the calculation rather than having a massive lookup table.

Answer 3

So, with 101 possible values, you're bound to use at least 7 bits per data word.

You should feel absolutely free to pack eight data words into a 7 B struct; C does allow that:

struct eight_words 
{
  unsigned int word0 : 7;
  unsigned int word1 : 7;
  unsigned int word2 : 7;
  unsigned int word3 : 7;
  unsigned int word4 : 7;
  unsigned int word5 : 7;
  unsigned int word6 : 7;
  unsigned int word7 : 7;
} __attribute__ ((__packed__));
const struct eight_words table[13500/8] = { {.word0 = 0x00, .word1 = 0x23, …} , {.word0 = …}};

and the __packed__ attribute will make any decent compiler actually emit structures of size 7 Bytes.

Access then is super simple. You can either just use pointers to your eight_words struct:

// get the 1000. element
unsigned int index, offset, value;
index = 1000/8; // integer math!
offset = 1000 - index * 8;
switch(offset)
{
  case 0: value = table[index].word0; break;
  case 1: value = table[index].word1; break;
  …
  case 7: value = table[index].word7; break;
}

or you just do a bit of pointer arithmetic:

// get the 1000. element
uint64_t* array = (char*) table;
unsigned int index, offset, value;
index = 1000/8; // integer math!
offset = 1000 - index * 8;
value = (array[index*7] >> (offset*7)) & (0xF);

That should both amount to roughly the same assembly, a few bytes in machine code.

Note that PWM sequence does sound like you're trying to reproduce some band-limited signal. For such, good compressors exist. Especially since you're only planning to access the data sequentially, and since even of your 7 bits, 27 values don't occur and, probably, a few bit combos are way more likely than others:

Simply use some simple LZW or huffman (low dict size) compressor and decompressor. These are a couple hundred bytes in machine code.