Jump to content

interpolation algorithm


rasteri

Recommended Posts

I'm not great at programming or math, so forgive me for the dumb question.

Is it possible to write an entirely 8-bit interpolation algorithm? Eg :

You have two unsigned chars a and b, with values 100 and 200.

You also have an interpolation factor i, between 0 and 255.

When i=0, output=100 (a)

when i=255, output=200 (b)

when i=127, output=150

I'd prefer it not to use integers or floats...

(as you might have guessed, I'm thinking 8-bit variable speed sample playback... if there's another way to do this, I'd like to know!)

Link to comment
Share on other sites

EXACTLY what I needed. Thanks!

EDIT: so something like...

unsigned char interpolate(unsigned char a, unsigned char b, unsigned char i)
{

  PRODL = a;
  PRODH = i;
__asm
    movf _PRODL, W
    mulwf _PRODH, 0
__endasm;
  a=PRODH;

  PRODL = b;
  PRODH = 255-i;
__asm
    movf _PRODL, W
    mulwf _PRODH, 0
__endasm;
  b=PRODH;

  return a+b;
}

This is untested (I'm at work!). Seem correct/efficient?

Link to comment
Share on other sites

Just cut out the shift of the 7bit value to make it 8bit :)

unsigned char interpolate(unsigned char i, unsigned char a, unsigned char b)
{
  PRODL = i;
  PRODH = b-a+1;

__asm
    movf _PRODL, W
    mulwf _PRODH, 0
__endasm;

  return a + PRODH;
}

Uhm how about:
unsigned char interpolate(unsigned char i, unsigned char a, unsigned char b)
{
  return ( (unsigned char) ( (b-(a + 1) ) * i ) ) + a;
}
It's less optimised than the ASM version (actually the function itself takes as long but it uses one more auto register so there are two instructions to save and restore it when the function is called. The speed difference is only calling overhead) Slightly OT: I'm pretty darned sure that *should* work... But uhm... It outputs code that uses PRODL instead of PRODH, which means it's outputting the low byte of the 16bit result.. Shouldn't it be outputting the high byte if it's truncating to 8bit? Is it just me or did I just find a bug? Surely someone would have noticed this before...... but that's not right... Just to simplify:
;	.line	111; main.c	mytest = MIOS_PARAMETER1*MIOS_PARAMETER2;
	MOVF	_MIOS_PARAMETER1, W
	MULWF	_MIOS_PARAMETER2
	MOVFF	PRODL, _mytest

Uhm... am I going crazy or is that just wrong?

Edit: I put the typecast back in there. I took it out for clarity but think I should leave it in for completeness. It compiles the same, either way.

Link to comment
Share on other sites

i'm not sure what point you are trying to make with those examples, but the reason we take the lsb is that as long as you don't overflow, math still works.  this would not be the case if we took the msb.

Sure, math works if you use LSB and don't overflow; but math works if you take MSB and do overflow :)

I guess my point is... C is weird / how can you get the correct result without a shift?

Link to comment
Share on other sites

...but math works if you take MSB and do overflow :)...

no it doesn't, taking the msb would not only require an overflow, but implicitly divide by 256 every time.

also when you assign or cast a char to an int, would you suggest assigning it's bits to the msb?

hehe, i bet you are just goading me into posting more,

guru curse looms large...

Link to comment
Share on other sites

  • 1 month later...

Sorry, I do not completely get it. If b < a then for me, the algorithm does not work.

example (d is decimal, b is binary):

a is d3  b00000011
b is d15 b00001111

put the next value in prodh, differentiate two cases:

1)  b-a+1 is d13   b00001101
2)  a-b+1 is d245 b11110101

Now multiply i with prodh. Lets say i is an 8 bit value of 100

1)  b00001101 * b01100100 = prodl contains b00010100 and prodh contains b00000101 this results in a final value of d8 (d5 of prodh plus the min d3 makes d8). is this correct?
     d100/d255 gives something like 0.39, mutiply this with 12 and you get 4.7, seems fair enough.

2)  b11110101 * b01100100 = prodl contains b10110100 and prodh contains b01011111. This is wrong.

What am I not getting (maybe I should go to bed?)

What I want to do is this assembler function: I have to 8-bit values a and b, and need to linearly interpolate between these in 4, 5 or 6 bit steps (ie 16, 32 or 64 steps), the step number is given in i (which has 4,  5 or 6 bit)

for example:

a is 100

b is 187

example for 5-bit i

if i is 0, then the result should be 100

if i is 63, then the result should be 187

if i is 23, then the result should be 131

And I cannot reproduce the above example. When I use an i with less bits, do I have to shift it left as well? and do I have to fill up the lower digits with 1 or 0?

Any help is very much appreciated, thanks.

ALEXander.

Link to comment
Share on other sites

Hi,

sorry, still having problems. This is my code, very similar to the code in MB64_POT_ScaleValue.

;; --------------------------------------------------------------------------
;;  FUNCTION: pca9635_Interpolate
;;  C_DECLARATION: void ASM_Interpolate(unsigned char step, unsigned char val1, unsigned char val2)
;;  DESCRIPTION: Testing the interpolation algorithm: interpolate between  value 1 and value 2 in
;;				 16 steps and return the corresponding step value.
;;
;;  IN:		4bit step			in WREG
;;		    8bit value 1		in MIOS_PARAMETER1
;;		    8bit value 2		in MIOS_PARAMETER2
;;
;;  C IN:	step number			in step
;;			value 1				in val1
;;			value 2				in val2
;;
;;  OUT:    interpolated value	in WREG
;;
;;  C OUT:	interpolated value as unsigned char
;;
;;  USES:	MIOS_PARAMETER3
;; --------------------------------------------------------------------------

;_pca9635_interpolate ; (for C)
pca9635_interpolate
#if _pca9635_def==1	; note this is using the define from the fix in the asm file!
	incf _mod_skel_var, F, BANKED
#endif

	;save step value in variable
	movwf	pca9635_StepCounter

	;find out if we have to swap the values
	;move MIOS_PARAMETER1 into W
	movf	MIOS_PARAMETER2, W
	;compare, skip the swap if MIOS_PARAMETER2 > MIOS_PARAMETER1
	cpfsgt	MIOS_PARAMETER1
	rgoto	pca9635_interpolate_NoSwap

	;we just swap the values and invert the step counter
	;using a temporary variable
	movff	MIOS_PARAMETER1, pca9635_Temp
	movff	MIOS_PARAMETER2, MIOS_PARAMETER1
	movff	pca9635_Temp, MIOS_PARAMETER2
	;invert the step counter and delete the upper nibble (for four bit counter)
	comf	pca9635_StepCounter, F
	movlw	0x0f
	andwf	pca9635_StepCounter, F

pca9635_interpolate_NoSwap

	;now find the difference between MIDI_PARAMETER1 and MIDI_PARAMETER2
	;load MIDI_PARAMETER1 into W
	movf	MIOS_PARAMETER1, W
	;subtract W from MIOS_PARAMETER2, store result in W
	subwf	MIOS_PARAMETER2, W
	;add 1 for rounding errors
	addlw	1

	;now divide this value by the number of steps
	;because the next operation is a floating point 16bit calculaton, we leave it
	;as it is and take away the decimals later

	;to get the result in the upper byte PRODH, shift the step
	;counter four to the left (for 4-bit counter)

	rlncf	pca9635_StepCounter, F
	rlncf	pca9635_StepCounter, F
	rlncf	pca9635_StepCounter, F
	rlncf	pca9635_StepCounter, F

	;therefore, multiply the difference with the number of steps
	mulwf	pca9635_StepCounter

	;now we just need to get the high byte
	movf	PRODH, W

	;add the MIOS_PARAMETER1 (the low value)
	addwf	MIOS_PARAMETER1, W

					;test send the result
					call	MIOS_MIDI_TxBufferPut

	return

Essentially, I get the difference of the two values, and multiply them with a 4-bit step counter which is shifted 4 bits to the left. The result then is in PRODH. But the closer I come to the high value, the more inaccurate it gets: If the max value is 150, the min value is 100 and the step number is 15 (from 0-15 steps), then I get 147 and not 150. What did I do wrong?

Thanks, ALEXander.

Link to comment
Share on other sites

Am I going right with the assumption that in the code, W is 0, F is 1 and BANKED is 1, used as constants to increase readability?

Yes, these are standard defines of the assembler (or sometimes defined in the PIC specific header file, somewhere in a gputils directory)

Essentially, I get the difference of the two values, and multiply them with a 4-bit step counter which is shifted 4 bits to the left. The result then is in PRODH. But the closer I come to the high value, the more inaccurate it gets: If the max value is 150, the min value is 100 and the step number is 15 (from 0-15 steps), then I get 147 and not 150. What did I do wrong?

Have a look into the project.map file - is the pca9635_StepCounter variable located at an address >= 0x80? In such a case, you have to set the bank ("SET_BSR pca9635_StepCounter"), and (to be sure, sometimes done automatically) the ", BANKED" attribute for correct addressing.

Another potential issue: "rlncf" shifts the carry flag into the LSB, but you haven't cleared it before starting the 4 shift operations. Accordingly, either "1" or "0" is shifted into the variable.

Best Regards, Thorsten.

Link to comment
Share on other sites

Hi,

I think I mixed things up here: If you divide a difference by 16, you actually get 17 steps, including the step zero. So everything is correct, only the last step happens when the StepCounter reaches 16, not 15 (which is binary 1111 and is the highest value in 4 bits). If I want step 0 to be the minimum value and step 15 to be the maximum value, I will have to divide the difference by 15, not by 16 (which would be much more difficult, because then it is not a shift operation).

So the solution seems like using one additional bit for the step counter, just for the value of 16. Or does anybody have a better idea?

Thanks for the tips about the banked acces and the carry flag, I think I am starting to understand how the PIC works now.

Best, ALEXander.

PS: Illustration: Minvalue is 100, Maxvalue is 150, 16 is the number of steps

1) Divide 50 by 16

2) Add n times (50/16) to the min value, starting with n = 0

n=0          min value

n=1          min value + step

n=2          min value + 2*step

...

n=15        min  value + 15*step (which is not yet the max value!)

n=16        max value!

Link to comment
Share on other sites

I guess my point is... C is weird / how can you get the correct result without a shift?

why the hell you don't want to make a shift  ??? ? there are shift operators in C++ !

check this:

http://www-numi.fnal.gov/offline_software/srt_public_context/WebDocs/Companion/cxx_crib/shift.html

or this:

http://www.fredosaurus.com/notes-cpp/expressions/bitops.html

and mind the operator precedence on writing expressions with multiple operators in it:

http://www.cppreference.com/operator_precedence.html

Link to comment
Share on other sites

...hmm. don't know. didn't want to "underestimate" you.. but what's wrong with a shift? it's a native operation of the processor, therefore fast and there's a native operator in C?

maybe you could use a byte-address to do what you want?:

unsigned int i=0xffbb;
unsigned char msb = *(&i);//msb==0xff now
unsigned char lsb = *((&i)+1);//lsb==0xbb now
this (could) also work (an array var is nothing else than a pointer), but they say it's "bad style":
[s]unsigned int i=0xffbb;
unsigned char msb = (&i)[0];//msb==0xff now
unsigned char lsb = (&i)[1];//lsb==0xbb now[/s]
[glow=red,2,300]correction: I think you need to typecast also:[/glow]
unsigned int i=0xffbb;
unsigned char msb = *((unsigned char *)&i);//msb==0xff now
unsigned char lsb = *((unsigned char *)((&i)+1));//lsb==0xbb now

or

unsigned int i=0xffbb;
unsigned char msb = ((unsigned char *)&i)[0];//msb==0xff now
unsigned char lsb = ((unsigned char *)&i)[1];//lsb==0xbb now

this look a bit weired, I didn't test if the syntax is correct, maybe it works.

Anyway, it should be possible to address a byte inside any var and cast it

as unsigned char.. dereferencing can be done with either * or array index.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
×
  • Create New...