Hi all, i`m searching an ASM-example for 2d lin. interpolation. (No need for floating point) In the EEPROM is stored an table, like so .eseg LTable: .db 0, 75 .db 40, 37 .db 60, 48 .db 80, 180 .db 100, 170 (The first byte in every .db line is the index, the second the value.) Now i need the interpolated value for an index 55. The calculation for that is not so difficult: 48 - 37 X = 37 + --------- * (55 - 40) 60 - 40 So result is 45 for the index 55 But, how is this do do in Assembler? And how to handle negative slope? Perhaps, someone can post example code, or a link? Thanks for your time,and best regards Rolf

linear interpolation / Assembler / ATMega32
Started by ●June 12, 2004
Reply by ●June 12, 20042004-06-12
On Saturday, in article <cafeto$1mc$03$1@news.t-online.com> rolf_gsxr@gmx.net "Rolf Bredemeier" wrote:>Hi all, > >i`m searching an ASM-example for 2d lin. interpolation. >(No need for floating point)But you do need FIXED point..>In the EEPROM is stored an table, like so > >.eseg >LTable: >.db 0, 75 >.db 40, 37 >.db 60, 48 >.db 80, 180 >.db 100, 170 > >(The first byte in every .db line is the index, the second the value.) > >Now i need the interpolated value for an index 55. > >The calculation for that is not so difficult: > > 48 - 37 >X = 37 + --------- * (55 - 40) > 60 - 40 > >So result is 45 for the index 55Or in integer maths (assembler) 11 X = 37 + -- * 15 15 X = 37 + 0 * 15 = 37 What precision do you need?? Does your hardware support 8 x 8 or 16 x 16 bit Multiply? Does your hardware support 16 / 16 bit? For most cases work out the precision and accuracy you require in BINARY places, then multiply up numbers that are used in the divide and multiply by at LEAST that number of places do the calculation and remove fixed point multiplier to give integer result you need. Remember 6 binary bits of precision is not the same as 6 binary bits of accuracy as some fractions are always awkward (prime numbers especially).>But, how is this do do in Assembler?Depends on the target and what instructions it has. Also what register and data sizes it supports in assembler. As well as the points above.>And how to handle negative slope?That is the least of your worries, you need to trap for divide by zero. negative slope just means you add a negative number! Remember that a positive / negative gives a negative number so does a negative / positive number, similarly a positive * negative number gives a negative number.>Perhaps, someone can post example code, or a link?You need to give more info as on controllers I use (H8 series) a lot of this is easy because it has 32bit registers as well hardware mult and div instructions. On some processors you will need to do multi byte arithmetic as they only support 8 bit data types.>Thanks for your time,and best regards > >Rolf > > > > >-- Paul Carpenter | paul@pcserv.demon.co.uk <http://www.pcserv.demon.co.uk/> Main Site <http://www.gnuh8.org.uk/> GNU H8 & mailing list info. <http://www.badweb.org.uk/> For those web sites you hate.
Reply by ●June 12, 20042004-06-12
In article <20040612.1834.300462snz@pcserv.demon.co.uk>, paul$@pcserv.demon.co.uk says...> On Saturday, in article <cafeto$1mc$03$1@news.t-online.com> > rolf_gsxr@gmx.net "Rolf Bredemeier" wrote: ><snip>> >In the EEPROM is stored an table, like so > > > >.eseg > >LTable: > >.db 0, 75 > >.db 40, 37 > >.db 60, 48 > >.db 80, 180 > >.db 100, 170 > > > >(The first byte in every .db line is the index, the second the value.) > > > >Now i need the interpolated value for an index 55. > > > >The calculation for that is not so difficult: > > > > 48 - 37 > >X = 37 + --------- * (55 - 40) > > 60 - 40 > > > >So result is 45 for the index 55 > > Or in integer maths (assembler) > > 11 > X = 37 + -- * 15 > 15Or more properly (taking into account finite precision, elementary numerical analysis and the fact that 60-40 = 20 ;) ) X = 37 + (11*15)/20 X = 37 + 165/20 X = 37 + 8 X = 45 Of course this chops rather than rounds so the question of precision still comes up. Also you need an intermediate value of 2n+1 bits (where n is the number of bits in your original values), check against overflows and of course against divide by zero. You also need to be careful that the table step size isn't too large. Some of those checks can be eliminated if you can guarantee the composition of the table. As long as you don't need better than +-1 than there is no need to have any representation other than whole numbers. Robert
Reply by ●June 12, 20042004-06-12
On Saturday, in article <OuLyc.11817$0FI1.4791@news01.bloor.is.net.cable.rogers.com> radsett@junk.aeolusdevelopment.cm "R Adsett" wrote:>In article <20040612.1834.300462snz@pcserv.demon.co.uk>, >paul$@pcserv.demon.co.uk says... >> On Saturday, in article <cafeto$1mc$03$1@news.t-online.com> >> rolf_gsxr@gmx.net "Rolf Bredemeier" wrote: >> ><snip> >> >In the EEPROM is stored an table, like so >> > >> >.eseg >> >LTable: >> >.db 0, 75 >> >.db 40, 37 >> >.db 60, 48 >> >.db 80, 180 >> >.db 100, 170 >> > >> >(The first byte in every .db line is the index, the second the value.) >> > >> >Now i need the interpolated value for an index 55. >> > >> >The calculation for that is not so difficult: >> > >> > 48 - 37 >> >X = 37 + --------- * (55 - 40) >> > 60 - 40 >> > >> >So result is 45 for the index 55 >> >> Or in integer maths (assembler) >> >> 11 >> X = 37 + -- * 15 >> 15 >Or more properly (taking into account finite precision, elementary >numerical analysis and the fact that 60-40 = 20 ;) )Damn retyped it several times to line up everything then put wrong value in....>X = 37 + (11*15)/20 >X = 37 + 165/20 >X = 37 + 8 >X = 45Alternative method..>Of course this chops rather than rounds so the question of precision >still comes up.Doesn't it always come up...> Also you need an intermediate value of 2n+1 bits (where >n is the number of bits in your original values), check against overflows >and of course against divide by zero. You also need to be careful >that the table step size isn't too large. Some of those checks can be >eliminated if you can guarantee the composition of the table. > >As long as you don't need better than +-1 than there is no need to have >any representation other than whole numbers.As one says depending on required precision... -- Paul Carpenter | paul@pcserv.demon.co.uk <http://www.pcserv.demon.co.uk/> Main Site <http://www.gnuh8.org.uk/> GNU H8 & mailing list info. <http://www.badweb.org.uk/> For those web sites you hate.
Reply by ●June 12, 20042004-06-12
In article <20040612.2240.300468snz@pcserv.demon.co.uk>, paul$@pcserv.demon.co.uk says...> On Saturday, in article > <OuLyc.11817$0FI1.4791@news01.bloor.is.net.cable.rogers.com> > radsett@junk.aeolusdevelopment.cm "R Adsett" wrote: > > >Or more properly (taking into account finite precision, elementary > >numerical analysis and the fact that 60-40 = 20 ;) ) > > Damn retyped it several times to line up everything then put wrong value > in....I hate it when that happens :)> >As long as you don't need better than +-1 than there is no need to have > >any representation other than whole numbers. > > As one says depending on required precision...Mind you if the OP needs better than +/- 1 the first thing to address is the data representation in the table. I don't know if the AVR has (or has a SW library that has) an 8bit x 8bit to 16bit multiply and a 16bit / 8 bit -> 8bit divide but if it does than with a few 'reasonble restrictions' on the table there will be no worry about overflows or loss of precision. Robert
Reply by ●June 12, 20042004-06-12
In article <8SLyc.12123$0FI1.7776@news01.bloor.is.net.cable.rogers.com>, R Adsett <radsett@junk.aeolusdevelopment.cm> wrote:>I don't know if the AVR has (or has a SW library that has) an 8bit x 8bit >to 16bit multiply and a 16bit / 8 bit -> 8bit divide but if it does than >with a few 'reasonble restrictions' on the table there will be no worry >about overflows or loss of precision.That's the MULS instruction. Divide, if it exists, seems it would be a library subroutine. I should check this out in the WinAVR toolchain. Regards. Mel.
Reply by ●June 13, 20042004-06-13
"Rolf Bredemeier" <rolf_gsxr@gmx.net> wrote in message news:cafeto$1mc$03$1@news.t-online.com...> .eseg > LTable: > .db 0, 75 > .db 40, 37 > .db 60, 48 > .db 80, 180 > .db 100, 170 > > (The first byte in every .db line is the index, the second the value.) >Just a suggestion or three: if you drop the index and add a value for 20, you'll use less eeprom space. you will know that index = offset * 20. Your values are very coarse. and the result is not likely to be very accurate. This appears to be a complex curve (at least a cubic). I would throw in some extra values. You could insert a value every 10, or perhaps 8 (the arithmetic becomes simpler/faster/cheaper if the index is a power of 2 as multiplies and particularly divides can be replaced by shifts. ..... but I'm not going to write the assembler for you, sorry. Cheers, Alf
Reply by ●June 13, 20042004-06-13
"Mel Wilson" <mwilson@the-wire.com> wrote in message news:ZB7yAls/KX6W089yn@the-wire.com...> In article <8SLyc.12123$0FI1.7776@news01.bloor.is.net.cable.rogers.com>, > R Adsett <radsett@junk.aeolusdevelopment.cm> wrote: > >I don't know if the AVR has (or has a SW library that has) an 8bit x 8bit > >to 16bit multiply and a 16bit / 8 bit -> 8bit divide but if it does than > >with a few 'reasonble restrictions' on the table there will be no worry > >about overflows or loss of precision. > > That's the MULS instruction. Divide, if it exists, seems > it would be a library subroutine. I should check this out > in the WinAVR toolchain. > > Regards. Mel.You'll notice that the denominator is a constant. There are two ways of handling this simply. The first is to multiply by a constant of the reciprocal of the denominator (i.e. 1/20 - or 2^N * 1/20 in the exemplar case), or better still change the interval to 2^N (e.g. 8 or 16) and shift right N to accomplish the division. Cheers, Alf.
Reply by ●June 13, 20042004-06-13
Hi Paul! Paul Carpenter wrote:> But you do need FIXED point..I think no, because +/-1 is good enough.> You need to give more info as on controllers I use (H8 series) a lot > of this is easy because it has 32bit registers as well hardware mult > and div instructions. > > On some processors you will need to do multi byte arithmetic as they > only support 8 bit data types.In the subject of my posting the type of MC is given, AVR ATMega32. This device does not support DIV, and has only 8 bit Registers. But math software routines are available. Unfortunately i'm not an good asm-programmer. Due to that fact, to write such an interpol function in asm, it will take the rest of my life. So i need a piece of code, which i can use as "black box". Values in, result out... Anyway many thanks for your answer, it shows me some significant details and explain the principle. And, of course, also thanks do Mel and Robert. Regards and greetings from Petershagen, Rolf begin 666 wink.gif M1TE&.#EA#P`/`+,``````+^_O___```````````````````````````````` M`````````````````````"'Y! $```$`+ `````/``\```0T,$@):ITX5,'Y MQ4 G>E,XC@`EF.MJIJSEQ>PI;C9:YZYGOQK?C12<R8C%7P;7^60TEA0F`@`[ ` end
Reply by ●June 13, 20042004-06-13
Hi Alf!> Just a suggestion or three: if you drop the index and add a value for > 20, you'll use less eeprom space. you will know that index = offset > * 20. Your values are very coarse. and the result is not likely to > be very accurate. This appears to be a complex curve (at least a > cubic). I would throw in some extra values. You could insert a > value every 10, or perhaps 8 (the arithmetic becomes > simpler/faster/cheaper if the index is a power of 2 as multiplies and > particularly divides can be replaced by shifts.My values only an example, in reality there are more entrys in the table, perhaps 20 for an not linear analog value from 0 to 100 percent.>..... but I'm not > going to write the assembler for you, sorry.I am afraid for that, but i understand ;-)) Best regards, and thanks for the tip to do index steps by eight. Rolf
