Basic table lookup and interpolation/extrapolation

Official FreeEMS vanilla firmware development, the heart and soul of the system!
Post Reply
User avatar
Fred
Moderator
Posts: 15431
Joined: Tue Jan 15, 2008 2:31 pm
Location: Home sweet home!
Contact:

Basic table lookup and interpolation/extrapolation

Post by Fred »

Because of the embedded nature of the code I'll be writing, we can't just use an array object and get a value back from a pair of coordinates. Well, at least not without implementing it from the ground up in an efficient accurate way.

An array for us has two dimensions, so we'll need to size references, X and Y.
We'll need a single 1 by (X*Y) table to hold the data
We'll also need two separate tables, 1xX and 1xY to hold the position data for each axises location.
In case our look up values are off the table we want a single bit that tells us if we are going to just use the edge value, or extrapolate outward from the last two rows.

For each axis there will be a two use cases :
The look up is exactly on an axis value
The look up value lies between two axis values

The first case is of course trivial, the latter will be handled in the following way

Retrieve both bounding values and interpolate between them.

In the case where the value rests between points on both axis then we will end up retrieving four values and doing 3 interpolations. Two vertical and one horizontal or vice versa.

This final value will be returned to the caller.

This function can then be used with appropriate addressing information (probably including the page of ram to read from) to read a value from any table.

short getValue(Xsize, Ysize, XaxisAddress, YaxisAddress, MainAddress, RPAGE, Xlookup, Ylookup, edgeBehaviour)

This function should always return a valid value within the confines of the units used. It should never error. It is the responsibility of the coder to ensure the data is where its supposed to be.

A matching setValue function can be defined to match the getValue one, it might look like this :

void setValue(Xsize, Ysize, XaxisAddress, YaxisAddress, MainAddress, RPAGE, Xvalue, Yvalue, cellValue)

This function should return quietly in code terms in all cases, but should report an error to the logging facility if the Xvalue or Yvalue is not valid in the X or Y 1 wide tables respectively.

In order to prevent this method being misused, I propose that a further abstraction could be done such that the required figures themselves except the last three are given by a lookup table based on a unique identifier number and stored in flash from the initial burn. This style of interface would ensure a good level of layer separation and safety from bad addresses being passed into the code from external tuning utilities etc.

Additionally we will need similar but more simple methods for setting the values in a 1xY table that represents the axis spacing.

void setAxisValue(axisSize, axisAddress, RPAGE, position, value)
short getAxisValue(axisSize, axisAddress, RPAGE, position)

Both of these should return quietly in code and log an error with the logging service if the position index is out of range (0 to (size - 1)).
get should return with a predictable and reasonable default value such as the top or bottom figure or an extreme figure to signify an error if the position index is out of range.
set should do nothing other than log if the position index is out of range.

A similar lookup scheme could keep this abstracted away too.

All implementation details and mistakes/gotchas should be commented on. I know Java pretty well, but not C, so I'm learning fast and mistakes are likely.

Admin.
DIYEFI.org - where Open Source means Open Source, and Free means Freedom
FreeEMS.org - the open source engine management system
FreeEMS dev diary and its comments thread and my turbo truck!
n00bs, do NOT PM or email tech questions! Use the forum!
The ever growing list of FreeEMS success stories!
User avatar
Fred
Moderator
Posts: 15431
Joined: Tue Jan 15, 2008 2:31 pm
Location: Home sweet home!
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by Fred »

Wow, it's been a long time since I posted this thread! The good news is I'm no longer noob, the better news is, I had it more or less right when I posted this thread.

I've implemented this function now for 19x24 x unsigned short tables.

The function is of the form :

Code: Select all

unsigned short lookupMainTable(mainTable *Table, unsigned short realRPM, unsigned short realLoad){
It will be used as follows :

VE = lookupMainTable(&VETableMain, RPM, Load);

Where load is pre-configured by logic above.

Which is clean and simple. A pointer to a struct containing the table is passed in along with the x,y coordinates of the required VE or Advance value. The members of the passed in struct are used to obtain the value through the following process :
  • figure out which two cells of the rpm axis values list you are between - not too slow
  • figure out which two cells of the load axis values list you are between - not too slow
  • look up four corner values using saved indices - fast
  • get two interpolated load values using saved indices and saved axis values - slowish : uses unsigned longs and non native math
  • get final value via interpolation of the two load values using saved indices and axis - slowish : uses unsigned longs and non native math
Return the value calculated.

The remaining space in the 1k block occupied by the struct is used for an ID string for the table. The struct occupies exactly 1024 bytes and is easily relocatable to ram for real time tuning.

For those afraid of large tables, just configure the two axis counts to the values of your dreams less than 19 and 24 and your table is that small automatically.

Behaviour off the edge and outside the table is also nice returning the value nearest to the requested spot

The code is simple and clean and about as fast as I can see it being. If it turns out to be an issue it can be optimised in future. Indeed, it can be replaced with an entirely different data structure in future without affecting the rest of the code. Such is modular clean design.

I look forward to putting it to good use in future :-)

Fred.
DIYEFI.org - where Open Source means Open Source, and Free means Freedom
FreeEMS.org - the open source engine management system
FreeEMS dev diary and its comments thread and my turbo truck!
n00bs, do NOT PM or email tech questions! Use the forum!
The ever growing list of FreeEMS success stories!
shameem
LQFP112 - Up with the play
Posts: 135
Joined: Thu May 01, 2008 6:30 pm
Location: Ann Arbor, MI
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by shameem »

Forgive my noobishness and poor reading skills - how is the table designed or to put it another way how is it accessed?

If the table is like this-
Image

so is the lookup going to be like this -
func(x1,y1)->memloc1: a11
func(x1,y2)->memloc2: a12
func(x1,y3)->memloc3: a13
func(x2,y1)->memloc1: a21
func(x2,y2)->memloc2: a22
func(x2,y3)->memloc3: a23

the func could be just extracting the matrix element (row, column etc) as a single number and adding it to a base address -
something like (y-1) * (num rows) + x +BASE - is it how its done?
User avatar
Fred
Moderator
Posts: 15431
Joined: Tue Jan 15, 2008 2:31 pm
Location: Home sweet home!
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by Fred »

Code: Select all

	/* Obtain the four corners surrounding the spot of interest */
	unsigned short lowRPMLowLoad = Table->Table[(Table->LoadLength * lowRPMIndex) + lowLoadIndex];
	unsigned short lowRPMHighLoad = Table->Table[(Table->LoadLength * lowRPMIndex) + highLoadIndex];
	unsigned short highRPMLowLoad = Table->Table[(Table->LoadLength * highRPMIndex) + lowLoadIndex];
	unsigned short highRPMHighLoad = Table->Table[(Table->LoadLength * highRPMIndex) + highLoadIndex];
Like that. The indices are obtained by iterating through the axis lists to find the bounding pair.

I hope that helps :-)

Fred.
DIYEFI.org - where Open Source means Open Source, and Free means Freedom
FreeEMS.org - the open source engine management system
FreeEMS dev diary and its comments thread and my turbo truck!
n00bs, do NOT PM or email tech questions! Use the forum!
The ever growing list of FreeEMS success stories!
shameem
LQFP112 - Up with the play
Posts: 135
Joined: Thu May 01, 2008 6:30 pm
Location: Ann Arbor, MI
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by shameem »

So it exactly like this - (y-1) * (num rows) + x +BASE

numrows - Table->LoadLength

y - lowRPMIndex

x - lowLoadIndex

Got it now....

On a further note - do you use Floor/Ceil to get the bounds? Could it be further optimized - like if the value is 3.9 round it up and use 4 since its good enough but if its 3.5 use the interpolation method or something like that.... Or is it not worth it?
User avatar
Fred
Moderator
Posts: 15431
Joined: Tue Jan 15, 2008 2:31 pm
Location: Home sweet home!
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by Fred »

Check your email for the full source.

Floor and Ceil are library functions aren't they? There is a library for us, but I strongly doubt it would be faster than this and it would need porting anyway.

As for value specific logic. I thought about it, but I only considered it for when the axis and the lookup are ==, even then I decided not to, and to do the calcs anyway. That way the run time is consistent and it's only once in a blue moon it will be the same anyway. I think smooth interpolation with no steps is very important to smooth running, so a cut off limit is a bad idea IMO.

Fred.
DIYEFI.org - where Open Source means Open Source, and Free means Freedom
FreeEMS.org - the open source engine management system
FreeEMS dev diary and its comments thread and my turbo truck!
n00bs, do NOT PM or email tech questions! Use the forum!
The ever growing list of FreeEMS success stories!
shameem
LQFP112 - Up with the play
Posts: 135
Joined: Thu May 01, 2008 6:30 pm
Location: Ann Arbor, MI
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by shameem »

Is the rpm interval constant? i.e. are the rpm values gonna go 500, 1000, 1500, 2000 etc.....
If it is a constant - can the bounds be calculated by doing
lowrpm = table[current rpm (modulus) interval]
highrpm=lowrpm+interval

Will this be more appropriate instead of iterating through all the rows (or columns) in the table -ofcourse this wont work at all if the interval is not constant....
User avatar
Fred
Moderator
Posts: 15431
Joined: Tue Jan 15, 2008 2:31 pm
Location: Home sweet home!
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by Fred »

Yeah, it's user configurable. Constant spacing is only for "cheap" systems ;-) We wouldn't need those extra arrays at all if it were constant spacing.

Fred.
DIYEFI.org - where Open Source means Open Source, and Free means Freedom
FreeEMS.org - the open source engine management system
FreeEMS dev diary and its comments thread and my turbo truck!
n00bs, do NOT PM or email tech questions! Use the forum!
The ever growing list of FreeEMS success stories!
User avatar
Fred
Moderator
Posts: 15431
Joined: Tue Jan 15, 2008 2:31 pm
Location: Home sweet home!
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by Fred »

I should add that there is another reason not to write special code for being on an axis or close to it etc :

Statistics.

It may be 50% faster if you hit an axis, and 90% faster if you hit a vertex, but those are only 0.0001% of events, 99.9999% will be paying an extra 5% slower for the extra logic. So, if you add it up, almost certainly it comes up slower with the "otimisations" on a statistical basis :-)

Additionally extra logic = extra bugs.

KISS is best for most stuff most of the time :-)

Fred.
DIYEFI.org - where Open Source means Open Source, and Free means Freedom
FreeEMS.org - the open source engine management system
FreeEMS dev diary and its comments thread and my turbo truck!
n00bs, do NOT PM or email tech questions! Use the forum!
The ever growing list of FreeEMS success stories!
User avatar
Fred
Moderator
Posts: 15431
Joined: Tue Jan 15, 2008 2:31 pm
Location: Home sweet home!
Contact:

Re: Basic table lookup and interpolation/extrapolation

Post by Fred »

Weird. Today I went searching for the place in the 68hc11 GCC manual where it said "single dimensional arrays are supported" and I couldn't find it... It seems like X dimensional arrays ARE supported after all. I'm glad I didn't use them though, as configurable table size is pretty cool for the main tables at least until we change them to random points.

Could be useful for other smaller tables though.

Fred.
DIYEFI.org - where Open Source means Open Source, and Free means Freedom
FreeEMS.org - the open source engine management system
FreeEMS dev diary and its comments thread and my turbo truck!
n00bs, do NOT PM or email tech questions! Use the forum!
The ever growing list of FreeEMS success stories!
Post Reply