3

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.

Community
  • 1
  • 1
Kong Chun Ho
  • 268
  • 4
  • 14
  • 3
    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
  • 2
    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
  • @DrewDormann Can you give out an example? – Kong Chun Ho Jan 02 '17 at 03:23
  • 1
    @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
  • 1
    @SamVarshavchik: never say "the only". In this particular case, a simple shift will most probably do. In other cases, fixed-point will be better. –  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. –  Jan 02 '17 at 10:20
  • What's the word length of the microcontroller ? –  Jan 02 '17 at 10:28

1 Answers1

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.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524