I am on SDCC 2.8.0, so very limited in memory and code size. Say I have an input value that ranges between 0 and 127, I want to scale it to 20 - 100. Normally I would do:
int scale(int input, int min, int max)
{
// assuming max is always greater than min
float range = (float)max - (float)min;
int output = min + int((range / 127.f) * (float)input);
return output;
}
By calling scale(64, 20, 100); I get 60, which is exactly half way between 20 and 100.
How can this be done without using the floating point numbers? Any bitshift magic?
If (max-min)<(INT_MAX/127) then you can naivly multiply (max-min)*input before dividing /127
Else, you'll have to decompose operations in order to avoid overflow and undefined behavior...
In later case, a naive possibility would be to divide both multipliers by 127.
A=Q1*127+R1
B=Q2*127+R2
A*B = (Q1*Q2*127 + Q1*R2 + Q2*R1) * 127 + R1*R2
(A*B)/127 = Q1*Q2*127 + Q1*R2 + Q2*R1 + (R1*R2/127)
or in C:
unsigned int range=max-min;
unsigned int output = min
+ (range/127)*(input/127)*127
+ (range/127)*(input%127)
+ (range%127)*(input/127)
+ (range%127)*(input%127) / 127;
It's pretty sure that there are more efficient formulation with bit-shifting >>8, the compiler might already do it well, but maybe not so well and we might better help him:
A=Q1*128+R1
B= 0*128+R2 (because B<=127)
A*B = (Q1*R2) * (127+1) + R1*R2
(A*B)/127 = Q1*R2 + (Q1*R2 + R1*R2)/127
and in C:
EDIT
Ahem, my intention was to divide by 128, that is >>7, and I incorrectly wrote >>8 same for remainder which should be &0x7F not &0xFF
It's certainly better to be less obscure and just write /128 and %128 because we can trust the compiler to translate these ops into simple bit ops nowadays...
unsigned int range=max-min;
unsigned int high=(range / 128)*input;
unsigned int low =(range % 128)*input;
unsigned int output = min + high + (high+low)/127;
EDIT2
For balancing the distribution a little bit better, we might apply some sort of rounding rather than truncation like this:
unsigned int output = min + high + (high+low+63)/127;