Fix float to int conversion in base/numerics

Fix float to int conversion in base/numerics

This addresses the bug where range checks are incorrect when
converting from a floating point value to an integral value of
higher precision but lower width. It also reverts a previous
attempted fix that eliminated false negatives but introduced
false positives.

BUG=522989
Committed: https://crrev.com/fafe071bac241504791c2904af9fbfea476274c8
Cr-Commit-Position: refs/heads/master@{#348706}

[jschuh, 2015-09-11 20:10:02]

The CQ bit was checked by jschuh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-09-11 20:10:23]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1338553003/1
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1338553003/1

[jschuh, 2015-09-11 20:28:30]

The CQ bit was checked by jschuh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-09-11 20:28:47]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1338553003/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1338553003/20001

[commit-bot: I haz the power, 2015-09-11 21:42:05]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-09-11 21:42:05]

Dry run: Try jobs failed on following builders:
  linux_chromium_chromeos_rel_ng on tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[jschuh, 2015-09-11 22:19:01]

Patchset #1 (id:1) has been deleted

[jschuh, 2015-09-11 22:19:08]

Patchset #1 (id:20001) has been deleted

[jschuh, 2015-09-11 22:20:11]

The CQ bit was checked by jschuh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-09-11 22:20:28]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1338553003/40001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1338553003/40001

[jschuh, 2015-09-11 22:23:01]

Should be ready to go, but we'll see what the CQ dry run looks like on other
architectures. I've added copious comments and tests for this corner case, so we
should be good now.

Bruce, Tom suggested we should loop you into the joy that is the safe numerics
code, since we don't have Albert around as a third. So, have fun with this one.
:)

[jschuh, 2015-09-11 22:32:51]

jschuh@chromium.org changed reviewers:
+ brucedawson@chromium.org, tsepez@chromium.org

[jschuh, 2015-09-11 22:32:51]

Ugh, I hit the back button so it cleared the CC fields, so I'm resending.

Anyway, this should be ready to go, but we'll see what the CQ dry run looks like
on other architectures. I've added copious comments and tests for this corner
case, so we should be good now.

Bruce, Tom suggested we should loop you into the joy that is the safe numerics
code. Since we don't have Albert around as a third anymore, we can get you up to
speed as an owner. So, have fun with this one. :)

[brucedawson, 2015-09-11 23:23:27]

I'm happy to be pulled in on FPU stuff. I haven't dealt with this
issue before but I have heard of it.

This blog post may be worth mentioning as a reference - perhaps add
it to the comments?
http://forrestthewoods.com/perfect-prevention-of-int-overflows/

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_conv...
File base/numerics/safe_conversions_impl.h (right):

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_conv...
base/numerics/safe_conversions_impl.h:117: //      floats, which round to
nearest and thus result in a value of larger
The FPU can be set to various rounding modes, some of which would then cause the
original code to work correctly. I believe that the new code works regardless of
rounding mode (because the calculated integer constant converts with no
rounding) but it might be good to state that.

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_conv...
base/numerics/safe_conversions_impl.h:125: // type is an integral of larger
precision than a source floating-point type.
Could clarify what it is truncated to, perhaps with an example for float to int.

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_nume...
File base/numerics/safe_numerics_unittest.cc (right):

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_nume...
base/numerics/safe_numerics_unittest.cc:622: TEST(SafeNumerics,
IsValueInRangeForNumericType) {
An additional class of tests would be to generate the various maximums and
confirm that that value converts to float without rounding. This could be done
by going int->float->double and int->double and confirming that the results are
the same, or round-tripping, or doing the conversion and then checking
EM_INEXACT with controlfp to validate that the conversion is exact (eg. can
enable FP exceptions for EM_INEXACT so that we crash if the conversion rounds).

Unfortunately the fiddly IEEE exception stuff is probably all non-portable.

[jschuh, 2015-09-12 00:43:12]

Bruce, are comfortable signing of? Because I'm an owner (since I wrote this mess
in the first place) and that would be sufficient review.

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_conv...
File base/numerics/safe_conversions_impl.h (right):

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_conv...
base/numerics/safe_conversions_impl.h:117: //      floats, which round to
nearest and thus result in a value of larger
On 2015/09/11 23:23:27, brucedawson wrote:
> The FPU can be set to various rounding modes, some of which would then cause
the
> original code to work correctly. I believe that the new code works regardless
of
> rounding mode (because the calculated integer constant converts with no
> rounding) but it might be good to state that.

Yes, this should be reliable and completely portable since it truncates the
value to match the resolution of the target ieee floating point.

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_conv...
base/numerics/safe_conversions_impl.h:125: // type is an integral of larger
precision than a source floating-point type.
On 2015/09/11 23:23:27, brucedawson wrote:
> Could clarify what it is truncated to, perhaps with an example for float to
int.

Done.

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_nume...
File base/numerics/safe_numerics_unittest.cc (right):

https://codereview.chromium.org/1338553003/diff/60001/base/numerics/safe_nume...
base/numerics/safe_numerics_unittest.cc:622: TEST(SafeNumerics,
IsValueInRangeForNumericType) {
On 2015/09/11 23:23:27, brucedawson wrote:
> An additional class of tests would be to generate the various maximums and
> confirm that that value converts to float without rounding. This could be done
> by going int->float->double and int->double and confirming that the results
are
> the same, or round-tripping, or doing the conversion and then checking
> EM_INEXACT with controlfp to validate that the conversion is exact (eg. can
> enable FP exceptions for EM_INEXACT so that we crash if the conversion
rounds).
> 
> Unfortunately the fiddly IEEE exception stuff is probably all non-portable.

Yup. In a previous iteration I had to add some platform-specific FP handling due
to compiler quirks. Now that I was able to remove it I have no intention of
bringing it back.

[brucedawson, 2015-09-12 00:45:55]

Let me poke at it a bit more. Best to get it perfect the first time.

[Peter Kasting, 2015-09-12 00:51:22]

Did you guys look at the implementation of clampTo() in
src/third_party/WebKit/Source/wtf/MathExtras.h?  It seems like it's kind of
related to what you're doing here and has to deal with the same kinds of edge
cases.  I dunno if it'd be helpful at all, though the unittests for it do cover
a lot of interesting corners so maybe that part would be a good reference.

[brucedawson, 2015-09-12 01:28:43]

The clamping looks correct (as long as we never run on a ones-complement or
signed-magnitude machine :-). However I couldn't see tests of magic numbers to
make sure they convert properly. That would seem helpful. We can either
hard-code such numbers 0x7FFFFF80 for int and 0xFFFFFF00 for unsigned) or do
something like this:

template <typename T>
T GetMaxConvertibleToFloat() {
  for (T i = std::numeric_limits<T>::max(); /**/; --i) {
    if (float(i) == double(i)) {
      return i;
    }
  }
}

With those magic numbers it's easy to write a few tests that verify that those
values are preserved by saturated_cast from float, but that the next values
above (nextafterf) are not.

That validates that the correct cutoff point is being used, using different
logic.

FWIW.

lgtm

https://codereview.chromium.org/1338553003/diff/80001/base/numerics/safe_conv...
File base/numerics/safe_conversions_impl.h (right):

https://codereview.chromium.org/1338553003/diff/80001/base/numerics/safe_conv...
base/numerics/safe_conversions_impl.h:145: ? (DstLimits::digits -
SrcLimits::digits)
Clever. 31 - 24 gives the magic. Or 32-24 for unsigned. It makes my head hurt,
but it seems good.

https://codereview.chromium.org/1338553003/diff/80001/base/numerics/safe_conv...
base/numerics/safe_conversions_impl.h:147: return DstLimits::max() -
static_cast<Dst>((UINTMAX_C(1) << shift) - 1);
Maybe another comment explaining why this doesn't work:
  return DstLimits::max() - ((Dst(1) << shift) - 1);
(because the compiler gives warnings about shifting of floats).

[jschuh, 2015-09-12 01:59:37]

On 2015/09/12 00:51:22, Peter Kasting wrote:
> Did you guys look at the implementation of clampTo() in
> src/third_party/WebKit/Source/wtf/MathExtras.h?  It seems like it's kind of
> related to what you're doing here and has to deal with the same kinds of edge
> cases.  I dunno if it'd be helpful at all, though the unittests for it do
cover
> a lot of interesting corners so maybe that part would be a good reference.

pkasting@ - Thanks, but the overlap is pretty superficial. safe_conversions.h
and safe_math.h are a security library for safely manipulating buffers in memory
(and intentionally designed to make it hard to screw up). I added minimal
floating point support to cover graphics buffer calculations, but the bulk of
the code supports safe handling of boundary conditions like overflow, underflow,
and truncation during simple arithmetic operations on integral types.

[jschuh, 2015-09-12 02:24:17]

On 2015/09/12 01:28:43, brucedawson wrote:
> The clamping looks correct (as long as we never run on a ones-complement or
> signed-magnitude machine :-). However I couldn't see tests of magic numbers to
> make sure they convert properly. That would seem helpful. We can either
> hard-code such numbers 0x7FFFFF80 for int and 0xFFFFFF00 for unsigned) or do
> something like this:
> 
> template <typename T>
> T GetMaxConvertibleToFloat() {
>   for (T i = std::numeric_limits<T>::max(); /**/; --i) {
>     if (float(i) == double(i)) {
>       return i;
>     }
>   }
> }
> 
> With those magic numbers it's easy to write a few tests that verify that those
> values are preserved by saturated_cast from float, but that the next values
> above (nextafterf) are not.
> 
> That validates that the correct cutoff point is being used, using different
> logic.

You got me. I didn't think reimplementing the truncation logic from the
templates would be a meaningful test, but I really like this suggestion (because
the cost of the loop during the tests will be de minimis). I'll add it in before
I land the change.


> FWIW.
> 
> lgtm
> 
>
https://codereview.chromium.org/1338553003/diff/80001/base/numerics/safe_conv...
> File base/numerics/safe_conversions_impl.h (right):
> 
>
https://codereview.chromium.org/1338553003/diff/80001/base/numerics/safe_conv...
> base/numerics/safe_conversions_impl.h:145: ? (DstLimits::digits -
> SrcLimits::digits)
> Clever. 31 - 24 gives the magic. Or 32-24 for unsigned. It makes my head hurt,
> but it seems good.

They went to all the trouble of writing the spec and the headers. Someone really
should put them to good use. ;)


>
https://codereview.chromium.org/1338553003/diff/80001/base/numerics/safe_conv...
> base/numerics/safe_conversions_impl.h:147: return DstLimits::max() -
> static_cast<Dst>((UINTMAX_C(1) << shift) - 1);
> Maybe another comment explaining why this doesn't work:
>   return DstLimits::max() - ((Dst(1) << shift) - 1);
> (because the compiler gives warnings about shifting of floats).

Sure.

[jschuh, 2015-09-14 18:04:04]

The CQ bit was checked by jschuh@chromium.org

[jschuh, 2015-09-14 18:04:04]

The patchset sent to the CQ was uploaded after l-g-t-m from
brucedawson@chromium.org
Link to the patchset: https://codereview.chromium.org/1338553003/#ps100001
(title: "more tests")

[commit-bot: I haz the power, 2015-09-14 18:04:32]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1338553003/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1338553003/100001

[commit-bot: I haz the power, 2015-09-14 20:21:30]

Committed patchset #4 (id:100001)

[commit-bot: I haz the power, 2015-09-14 20:22:08]

Patchset 4 (id:??) landed as
https://crrev.com/fafe071bac241504791c2904af9fbfea476274c8
Cr-Commit-Position: refs/heads/master@{#348706}

[commit-bot: I haz the power, 2015-09-23 12:36:44]

Patchset 4 (id:??) landed as
https://crrev.com/fafe071bac241504791c2904af9fbfea476274c8
Cr-Commit-Position: refs/heads/master@{#348706}