<div dir="ltr">Elegant and very impressive!<div><br><br><div class="gmail_quote">On Wed, Mar 17, 2010 at 1:21 PM, Marcus Comstedt <span dir="ltr"><<a href="mailto:marcus@mc.pp.se">marcus@mc.pp.se</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im"><br>
yotam barnoy <<a href="mailto:yotambarnoy@gmail.com">yotambarnoy@gmail.com</a>> writes:<br>
<br>
> If it's efficiency we're after, then the multiplication is a small part of<br>
> the cost - division is much more expensive (about 4 times more on MIPS).<br>
><br>
> The problem is that we need to multiply by more correct ratios than our<br>
> shifting simplifications allow. For example to convert a 5 bit channel to 8<br>
> bits, we need to multiply by 255/31 = 8.225 instead of 8, which is what we<br>
> currently do.<br>
<br>
</div>Don't get too hooked up on these fractions.  There's a much simpler<br>
way.  What we're doing now is inserting 0 bits in the "loss"<br>
positions.  What we should do, to get the correct result, is to repeat<br>
the most significant bits in those positions.  So in the case of 5 bit<br>
to 8 bit, we should take the top 3 bits of the 5 bit value and insert<br>
to the bottom 3 bit positions.<br>
<br>
  r = (r << 3)|(r >> 2);<br>
<br>
No multiplications, divisions or conditionals.  What you get is<br>
actually a multiplication with binary 100.01, or 8.25 in decimal.<br>
This is more than your computed 8.225, but due to the fact that we<br>
always get rounding downwards, we actually get the right result anyway<br>
(the 8.225 value assumes rounding towards nearest integer).<br>
<font color="#888888"><br>
<br>
  // Marcus<br>
<br>
<br>
</font></blockquote></div><br></div></div>