Faster way to convert a number from range to another range

Question

According to this SO question, it is possible to convert a number range to another (linear conversion) by calculating:

NewValue = (((OldValue - OldMin) * NewRange) / OldRange) + NewMin

However, I want to know if there is another faster way to do this.

Consider a microcontroller with no division instruction, converting massive amount of a ranges to another ranges (i.e. 24-bit color/pixels from image file to 18-bit color/pixels for the LCD display) would take sometime. I was thinking is there any way to optimze this.

The only alternative to integer division here is a floating point multiplication. No matter which way you turn, you cannot alter the rules of fundamental math. — Sam Varshavchik, Jan 02 '17 at 03:11
I could imagine floating point operations would be even slower on those devices. — Kong Chun Ho, Jan 02 '17 at 03:13
Your given example of converting range (0,2^24-1) to (0,2^18-1) could be done with a bit shift (plus an add, if you want to round to nearest) — Drew Dormann, Jan 02 '17 at 03:16
@KongChunHo `NewValue = OldValue >> 6` will drop the 6 least significant bits. Be sure your values are `unsigned`. — Drew Dormann, Jan 02 '17 at 03:38
"Faster way to convert a number from range to another range" --> in general, no. For select values and sub-ranges, yes. Yet this code does not post types, nor ranges. So unclear — chux - Reinstate Monica, Jan 02 '17 at 04:24
@SamVarshavchik: never say "the only". In this particular case, a simple shift will most probably do. In other cases, fixed-point will be better. — Yves Daoust, Jan 02 '17 at 10:14
@DrewDormann: you don't shift the number as a whole ! Rather, you shift every component separately by two bits. — Yves Daoust, Jan 02 '17 at 10:20

Yakk - Adam Nevraumont · Answer 1 · 2017-01-03T12:56:33.367

4

24 bit color is usually 8 x 3 (3 components, 8 bits per).

18 bit color is 6 x 3.

A simple >>2 converts the range of 8 bit values to 6 bit values, "rounding down". And shift operations are fast on most hardware.

Rounding to nearest is harder mainly because of overflow. Starrt with this:

(x+2)>>2

in a 16 bit value. The result is a value from 0 to 2^6, not 0 to 2^6-1 like you want. You'll have to detect that last case.

If you can afford the ROM, a lookup table can be used. 256 entries isn't all that many. This may be more worth considering if you want to apply gamma or other corrections.

But really, just >>2 and/or mask each component, then shift and mask into place.

int32 r = ((pix>>2)&(0x3F<<0))|((pix>>4)&(0x3F<<6))|((pix>>6)&(0x3F<<12));

Where pix is a 32 bit value storing your 24 bit pixel and r stores the 18 bit result.

This kind of optimization requires profiling in as close to a real environment as possible.

edited Jan 03 '17 at 12:56

answered Jan 02 '17 at 04:59

Yakk - Adam Nevraumont

250,370
26
305
497

1

Rounding to nearest isn't a good idea here. Simply discarding the low two bits results in a uniform transform, where exactly 4 source values map onto 1 destination value, throughout the entire range including ends. – Ben Voigt Jan 02 '17 at 07:54
Why you are just ripping off each 2 MSB (i.e. `&0x3F`)? Wouldn't that make the ratio different? – Kong Chun Ho Jan 03 '17 at 05:33
@KongChunHo Oops took 6 LSB in each byte, not 6 MSB. Fixing. – Yakk - Adam Nevraumont Jan 03 '17 at 12:56

Faster way to convert a number from range to another range

1 Answers1