Bug 160565 - Undefined behavior in StdLibExtras.h, bitCount
Summary: Undefined behavior in StdLibExtras.h, bitCount
Status: RESOLVED INVALID
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2016-08-04 13:45 PDT by Jonathan Bedard
Modified: 2016-08-05 10:02 PDT (History)
6 users (show)

See Also:


Attachments
Patch (1.64 KB, patch)
2016-08-04 14:20 PDT, Jonathan Bedard
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jonathan Bedard 2016-08-04 13:45:46 PDT
In StdLibExtras.h bitCount, there is undefined behavior on return.  The line:
    return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24
almost always has undefined behavior.  In this case, the overflow is expected.  However, compiler optimization (given that this function is an inline) with constants may preform unexpected operations
Comment 1 Jonathan Bedard 2016-08-04 14:20:43 PDT
Created attachment 285364 [details]
Patch
Comment 2 Jonathan Bedard 2016-08-05 09:05:57 PDT
Here is the error message clang's undefined behavior sanitizer emits for this particular error:

/Volumes/Data/Code/UndefinedBehavior/OpenSource/WebKitBuild/Debug/usr/local/include/wtf/StdLibExtras.h:163:48: runtime error: unsigned integer overflow: 1025 * 16843009 cannot be represented in type 'unsigned int'

Further investigation on this has revealed that clang is combining some 'suspicious' behaviors with 'undefined' behaviors, and this is a case of 'suspicious' behavior, but, as per C++ 2014 standard 3.9.1, 4, unsigned types overflow with modulo 2^n, which is our desired behavior in this case.  In short, the behavior corrected here is both defined and desired.

Undefined behavior sanitizer information: http://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html

C++ standard:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf

No fix is needed.  Marking as resolved.