Add SkDivMod with a special case for ARM.

Add SkDivMod with a special case for ARM.

BUG=skia:1663
Committed: http://code.google.com/p/skia/source/detail?r=11482

[mtklein, 2013-09-20 18:34:39]

I see 10-15% improvement on imagecache bench, and 2x on the new divmod benches.

[djsollen, 2013-09-20 18:51:52]

can you update skbitmap.cpp::get_upper_left_from_offset to use this new function
as well?

[mtklein, 2013-09-20 18:59:34]

On 2013/09/20 18:51:52, djsollen wrote:
> can you update skbitmap.cpp::get_upper_left_from_offset to use this new
function
> as well?

You bet.  Have a look?

[reed1, 2013-09-20 19:02:39]

https://codereview.chromium.org/24159009/diff/9001/include/core/SkMath.h
File include/core/SkMath.h (right):

https://codereview.chromium.org/24159009/diff/9001/include/core/SkMath.h#newc...
include/core/SkMath.h:181: inline void SkDivMod(T x, T y, T* div, T* mod) {
1. SkTDivMode
2. add dox
3. rename x to numer? y to denom?

https://codereview.chromium.org/24159009/diff/9001/src/core/SkBitmap.cpp
File src/core/SkBitmap.cpp (right):

https://codereview.chromium.org/24159009/diff/9001/src/core/SkBitmap.cpp#newc...
src/core/SkBitmap.cpp:915: size_t xSizeT, ySizeT;
do we really need to have two local vars to call this? :(
If we had SkDivMod32() hard coded to int32_t, could we avoid this?

[mtklein, 2013-09-20 19:29:35]

https://codereview.chromium.org/24159009/diff/9001/include/core/SkMath.h
File include/core/SkMath.h (right):

https://codereview.chromium.org/24159009/diff/9001/include/core/SkMath.h#newc...
include/core/SkMath.h:181: inline void SkDivMod(T x, T y, T* div, T* mod) {
On 2013/09/20 19:02:39, reed1 wrote:
> 1. SkTDivMode
> 2. add dox
> 3. rename x to numer? y to denom?

Done.

https://codereview.chromium.org/24159009/diff/9001/src/core/SkBitmap.cpp
File src/core/SkBitmap.cpp (right):

https://codereview.chromium.org/24159009/diff/9001/src/core/SkBitmap.cpp#newc...
src/core/SkBitmap.cpp:915: size_t xSizeT, ySizeT;
On 2013/09/20 19:02:39, reed1 wrote:
> do we really need to have two local vars to call this? :(
> If we had SkDivMod32() hard coded to int32_t, could we avoid this?

We could, but that'd force offset and rowBytes to cast down.

How do you feel about this version, which allows the inputs and outputs to be
different types?

[reed1, 2013-09-20 19:59:50]

suggestion for unittest:

10,000 random ints passed to your macro, and to  { div = a / b; mod = a % b; }
and then assert that the two results are equal.

Seems cheap enough, and then we know we're cool when a and/or b are negative or
zero...

[tomhudson, 2013-09-23 09:25:26]

On 2013/09/20 19:59:50, reed1 wrote:
> suggestion for unittest:
> 
> 10,000 random ints passed to your macro, and to  { div = a / b; mod = a % b; }
> and then assert that the two results are equal.
> 
> Seems cheap enough, and then we know we're cool when a and/or b are negative
or
> zero...

If we're only doing unsigned int div, I think what we have now would be fine.
The software integer divide implementation on ARM is constant-complexity (lg a)
any very straightforward - it doubles b until it's bigger than a, then
repeatedly halves and subtracts. So I don't know that we're gaining any coverage
by randomizing the variables.

If we're doing signed int div, it's a lot more complex, I'm not sure the
optimization is correct, and we need to guarantee we hit those cases in the unit
test.

Oops, that was an important caveat to omit from the original bug, wasn't it?

[mtklein, 2013-09-23 11:44:30]

On 2013/09/23 09:25:26, tomhudson wrote:
> On 2013/09/20 19:59:50, reed1 wrote:
> > suggestion for unittest:
> > 
> > 10,000 random ints passed to your macro, and to  { div = a / b; mod = a % b;
}
> > and then assert that the two results are equal.
> > 
> > Seems cheap enough, and then we know we're cool when a and/or b are negative
> or
> > zero...
> 
> If we're only doing unsigned int div, I think what we have now would be fine.
> The software integer divide implementation on ARM is constant-complexity (lg
a)
> any very straightforward - it doubles b until it's bigger than a, then
> repeatedly halves and subtracts. So I don't know that we're gaining any
coverage
> by randomizing the variables.
> 
> If we're doing signed int div, it's a lot more complex, I'm not sure the
> optimization is correct, and we need to guarantee we hit those cases in the
unit
> test.
> 
> Oops, that was an important caveat to omit from the original bug, wasn't it?

I think we should be okay here.  C++ requires
  (a/b)*b + a%b  = a       (b != 0)

Swap sides and that's
  a%b = a - (a/b)*b.        (b != 0)

I'll add tests to cover the edge cases here.

[mtklein, 2013-09-24 15:09:52]

On 2013/09/23 11:44:30, mtklein wrote:
> On 2013/09/23 09:25:26, tomhudson wrote:
> > On 2013/09/20 19:59:50, reed1 wrote:
> > > suggestion for unittest:
> > > 
> > > 10,000 random ints passed to your macro, and to  { div = a / b; mod = a %
b;
> }
> > > and then assert that the two results are equal.
> > > 
> > > Seems cheap enough, and then we know we're cool when a and/or b are
negative
> > or
> > > zero...
> > 
> > If we're only doing unsigned int div, I think what we have now would be
fine.
> > The software integer divide implementation on ARM is constant-complexity (lg
> a)
> > any very straightforward - it doubles b until it's bigger than a, then
> > repeatedly halves and subtracts. So I don't know that we're gaining any
> coverage
> > by randomizing the variables.
> > 
> > If we're doing signed int div, it's a lot more complex, I'm not sure the
> > optimization is correct, and we need to guarantee we hit those cases in the
> unit
> > test.
> > 
> > Oops, that was an important caveat to omit from the original bug, wasn't it?
> 
> I think we should be okay here.  C++ requires
>   (a/b)*b + a%b  = a       (b != 0)
> 
> Swap sides and that's
>   a%b = a - (a/b)*b.        (b != 0)
> 
> I'll add tests to cover the edge cases here.

Added both edge case tests and randomly generated ones.

[tomhudson, 2013-09-25 12:38:59]

Thanks for adding the tests; LGTM.

[reed1, 2013-09-26 15:44:32]

lgtm

[commit-bot: I haz the power, 2013-09-26 16:10:21]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/mtklein@google.com/24159009/28001

[commit-bot: I haz the power, 2013-09-26 19:22:59]

Change committed as 11482