Extend bit width

Code
01: unsigned int extend(unsigned int value, unsigned int smallSize, unsigned int bigSize)
02: {
03:   // i.e. to extend from 5 to 8 bits, use extend(x,5,8)
04:   unsigned int leftShift  = bigSize - smallSize;
05:   unsigned int rightShift = bigSize - leftShift;
06:
07:   // extend and fill lower bits smartly
08:   return (value << leftShift) | (value >> rightShift);
09: }
 bits.stephan-brumme.com

Explanation Especially for graphic cards, values are often truncated to a few bits, i.e. 5 bits per color channel.
When used to actually draw pixels, these values have to be extended to 8 bits while preserving three important properties:
1. scaling must be as linear as possible
2. zero must remain zero
3. the maximum possible input must be mapped to the maximum possible output

In terms of a graphics designer, colors must not be falsified and especially White must remain White while Black remains Black.

A simple left shift suffices properties 1 and 2. However, it fails when it comes to requirement 3.
In the example given, 0x1F is the maximum value for 5 bits but a left shift by 3 bits generates 0xF8 which is clearly not 0xFF.

The presented method not only performs the shift (line 4 and line 8) but also maps the highest bits to the lowest bits, too,
and thus solves the problem (line 5 and line 8).
Note: if the input bit width is less than half the output bit width, requirement 3 is not always fulfilled.

Compilers convert lines 4 and 5 to constant values. The only actual code is to be found in line 8.

Restrictions • none

These ads
help me to pay
my server bills

Performance • constant time, data independent

+ Intel® Pentium™ D:
• extend: ≈ 5.5 cycles per number

+ Intel® Core™ 2:
• extend: ≈ 3 cycles per number

+ Intel® Core™ i7:
• extend: ≈ 5 cycles per number
Performance Chart
CPU cycles
(full optimization,
lower values are better)

Assembler Output
extend:
01:   push esi
02:   mov esi, eax
03:   shr eax, cl
04:   mov cl, dl
05:   shl esi, cl
06:   or  eax, ebx
07:   pop esi
 bits.stephan-brumme.com

Download The full source code including a test program is available for download.

References http://sol.gfxile.net/boolean.html

More Twiddled Bits
  1. Absolute value of a float
  2. Absolute value of an integer
  3. Approximative inverse of a float
  4. Bit manipulation basics
  5. Bit mask of lowest bit not set
  6. Count bits set in parallel a.k.a. Population Count
  7. Detects zero bytes inside a 32 bit integer
  8. Endianess
  9. Extend bit width
  10. Float inverse square root approximation
  11. Float square root approximation
  12. Is power of two
  13. Minimum / maximum of integers
  14. Parity
  15. Position of lowest bit set
  16. Round up to the next power of two
  17. Sign comparison
  18. Sign of a 32 bit integer
  19. Swap two values
Extra: Javascript bit manipulator

... or go to the index