linear interpolation / Assembler / ATMega32

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

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 55

Or 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.

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 ;) )

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

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 = 45

Alternative 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.

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

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.

"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

"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.

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

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