Interpolation

[Kevin Timmerman]

> <thormj at iname.com> wrote:
> > Solution #2:
> > Can anyone provide me with a *quick* 2 point linear interpolation
> > (1d map)... and a quick 4 point interpolation (2d map)?
> >
> > My current code looks like:
> > return (x-curve[i-1].x)*(curve[i].y - curve[i-1].y)/
> >          (curve[i].x - curve[i-1].x) + curve[i-1].y;
> >
> > This is for a 68hc11 uC, so the less math the better. :-/


Here is some 68HC11 asm code from Bosch/VW Digifant ECU.....

*--------------------------------------------------------------        
*
*	Simple table lookup for 16 byte table
*
* Entry: B - Index ( 0 to $FF )
*	X - Table address
*
* Exit:	B - Lookup value
*	X - Points to lookup value
*

tbl_lu  LSRB
	LSRB
	LSRB
	LSRB
	ABX
	LDAB    ,X
	RTS


*--------------------------------------------------------------
*	Interpolated table lookup
*
* Entry: B - Table index
*		0 - $F0 for 16 byte table
*		0 - $FF for 17 byte table
*	X - Table address
*
* Exit:	B - Interpolated table lookup
*	A - Zero
*	X - Address of uninterpolated value
*

tbl_itp	PSHB			; Save index
	LSRB			; Divide by 16
	LSRB
	LSRB
	LSRB
	ABX			; Adjust table pointer
	PULB			; Restore index
	JSR	interp		; Interpolate
	CLRA
	RTS



*-------------------------------------------------------------------
*
*	2D interpolation of 16 * 16 table
*
* Entry: A - Table Y (row) 0 to $F0
*	B - Table X (column) 0 to $FF
*	X - Table address
*
* Exit:	B - Interpolated result
*	X - Trashed
*	A - Trashed
*

interp2d			;4AC3
	STAA    tmp3		; Save row
	STAB    tmp4		; Save column
	LSRB			; Divide column by 16
	LSRB
	LSRB
	LSRB
	STAB    tmp1		; Save column/16
	LDAB    tmp3		; Get row
	ANDB    #$F0            ; Mask
	ADDB    tmp1		; Add column
				; B = row/16*16 + column/16
	ABX			; Adjust table address
	LDAA    tmp3		; Get row
	LDAB    tmp4		; Get column
	CMPA    #$F0		; Row at max ??
	BCS     row_ok		; 2D interpolate if not
	LDAA    #$F0		; Limit row to $F0
	CMPB    #$F0		; Column max ??
	BNE     LBL4AE6		; 1D Interpolate if not
	LDAB    $00,X           ; Get uninterpolated value
	BRA     LBL4AE9		; Return
LBL4AE6	JSR     interp		; Interpolate within row
LBL4AE9	BRA     LBL4B10		; Return
row_ok	CMPB    #$F0		; Column max ???
	BNE     col_ok		; 1D interpolate if it is
	LDAA    ,X		; Get low
	STAA    tmp1		; Save
	LDAA    $10,X		; Get high
	STAA    tmp2		; Save
	BRA     LBL4B08		; Interpolate...
col_ok  JSR     interp		; Interpolate row
	STAB    tmp1		; Save
	LDAB    #$10		; Next row
	ABX
	LDAB    tmp4		; Get column (for interp index)
	JSR     interp		; Interpolate row
	STAB    tmp2		; Save
LBL4B08	LDAB    tmp3		; Get row (for interp index)
	LDX     #tmp1		; Interpolate saved values
	JSR     interp
LBL4B10	RTS



*--------------------------------------------------------------
*
*	Interpolation for 16 byte tables
*
*	B = ( ( low * (16-index) ) + ( high * index ) ) / 16
*
* Entry: B - interpolation index, only lowest four bits used
*	[X] - low value
*	[X+1] - high value
*
* Exit: B - interpolated value
*	A - zero (trashed)
*

interp
	ANDB    #$0F		; Use only lowest four bits
	PSHB			; Save for later
	LDAA    1,X		; Get high
	MUL			; high * index
	PSHB			; Save
	PSHA
	LDAA    ,X		; Get low
	PSHX			; Save X
	TSX			; S -> X
	LDAB    4,X		; Get saved index off stack
	SUBB    #$10		; index = 16 - index
	NEGB
	MUL			; low * (16 - index)
	ADDD    2,X		; Add low*(16-index) to (high*index) from stack
	ADDD    #$0008		; Rounding
	LSRD			; Divide by 16
	LSRD
	LSRD
	LSRD
	PULX			; Restore X
	INS			; Cleanup stack
	INS
	INS
	RTS