interpolation algorithm

[rasteri]

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

[audiocommander]

sure,

here's an example:

http://www.ucapps.de/mios_c_send_range.html

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

hmm... okay...

[rasteri]

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?

[stryd_one]

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.

[rasteri]

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

<SNIP>

Will that still work if b < a?

[bugfight]

that's no bug, it's by design.  if you typecast to a smaller integer type, you get the lsb.

[stryd_one]

Thx bf... C is so strange sometimes...what the heck would you want the LSB for?!

rasteri: try it!

[bugfight]

Thx bf... C is so strange sometimes...what the heck would you want the LSB for?!

...

no problemo.

imagine you did this:

unsigned int a, b;
unsigned char c;

a = 1;
b = 2;
c = a + b;

what should the value of c be?

[stryd_one]

unsigned int a, b;
unsigned char c;

a = 100;
b = 200;
c = a + b;

Now what should it be?

[bugfight]

that's what you call overflow error, same as if they were all chars.

this is why this implicit conversion will usually throw a compiler warning...

[stryd_one]

what about this:

unsigned int a, b;
unsigned char c;

a = 100;
b = 200;
c = (char) ( (int)a + (int)b ); 

or, yaknow,

unsigned int a, b, x;
unsigned char c;

a = 100;
b = 200;
x =  (int)a + (int)b; 
c = (char) x

[bugfight]

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.

[stryd_one]

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?

[bugfight]

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

[nILS]

Don't worry about the curse - you can just go back and delete the posts from 2007 as well  ;)

[stryd_one]

And I thought I had some weird OCD ;D

So I guess it's bitshift or nothing! I still like ASM better :)

[wackazong]

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.

[TK.]

See the original function (MB64_POT_ScaleValue), how to handle the inversion.

Best Regards, Thorsten.

[wackazong]

OK, thanks.

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?

Best, ALEXander.

[wackazong]

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.

[TK.]

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.

[wackazong]

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!

[This N°9]

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

[stryd_one]

I know all that, I'm not *that* new... I just thought C would be smart enough to do it without manipulation. Not "I don't want to use a bitshift" but "Isn't there a way to do it without one?"

[This N°9]

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