Want to scale int to int with integer math

Question

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?

Answer 1

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;

Answer 2

I understand this is an old thread, but I just wanted to share some tricks you can use to to scale with a float a bit more efficiently, if the scaling constants are fixed and known in advance. Compilers often use these tricks when there is a division with an integer literal, to avoid the usually expensive div instruction (which can take many dozens of cycles on many architectures).

Obviously, unless you really need to shave these several cycles off of each scaling operation, this is the definition of premature optimization.

Anyway, the idea is to change your floating point factor into an approximation which has a power of two in its denominator, so that you can replace the division with a multiplication (typically 1 cycle) and a right shift operation (again typically 1 cycle for operations on integers matching the architecture word size).

In your case, you would aim to replace the 1/127 part with a right shift, i.e. a division with a power of two. Since you need to scale with 80/127 (which is approx. 0.62992) and the input fits into 7 bits, you can choose something like 161/256 (I presumed you have a 16-bit controller, so I just multiplied 0.62992 with 256 since your input values all fit in the low byte of the word).

So the function then becomes:

// scale 0..127 into 20..100
uint8_t scale(uint8_t input)
{
    uint16_t low = input * 161;   // <- this will move the result into the high 8 bits
    low += 1 << 7;                // <- adding a "half bit" before shifting (like +0.5)
    low >>= 8;                    // <- cheap division by 256
    low += 20;                    // <- and finally, add offset

    return (uint8_t)(low);
}

On a 32-bit microcontroller, you would choose a larger factor to get a better approximation. It's often faster for the cpu/compiler to work with the native word size, because it doesn't need to truncate or extend register values to get to smaller integer sizes.

Since 127 needs 7 bits, you can choose a 24-bits denominator and still be sure the multiplied value will fit inside the 32-bit word, i.e.:

// 0.62992 == 10568325 / ‭16777216‬ == 10568325 / (1<<24)
uint8_t scale_32(uint8_t input)
{
    uint32_t low = input * 10568325;
    low += 1 << 23;
    low >>= 24;
    low += 20;
    return (uint8_t)(low);
}

You can use the godbolt online compiler to compare the assemblies of these functions in different compilers/architectures.