8000 BUG: Don't produce undefined behavior for a << b if b >= bitsof(a) by eric-wieser · Pull Request #13739 · numpy/numpy · GitHub
[go: up one dir, main page]
Skip to content

BUG: Don't produce undefined behavior for a << b if b >= bitsof(a) #13739

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 7 commits into from
Sep 14, 2019
Merged

BUG: Don't produce undefined behavior for a << b if b >= bitsof(a) #13739

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
24b2a2d
BUG: shift operator cycles, fixes #2449
jaimefrio Mar 27, 2016
b12a869
Merge tag 'branch-points/1.16.x' into bit_shifts
eric-wieser Jun 8, 2019
e487889
Merge tag 'branch-points/1.17.x' into HEAD
eric-wieser Sep 13, 2019
ff11d01
Merge commit 'edf8a5f' into HEAD
eric-wieser Sep 13, 2019
fca077c
MAINT: Respond to review comments on gh-7473
eric-wieser Jun 9, 2019
79d7bc2
MAINT: Move shift implementation to npy_math
eric-wieser Jun 12, 2019
6cf6ece
BUG: Disable -O3 on right_shift on compilers which emit an internal e…
eric-wieser Jun 12, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
22 changes: 22 additions & 0 deletions numpy/core/include/numpy/npy_math.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -162,6 +162,28 @@ NPY_INPLACE npy_long npy_lcml(npy_long a, npy_long b);
NPY_INPLACE npy_longlong npy_gcdll(npy_longlong a, npy_longlong b);
NPY_INPLACE npy_longlong npy_lcmll(npy_longlong a, npy_longlong b);

NPY_INPLACE npy_ubyte npy_rshiftuhh(npy_ubyte a, npy_ubyte b);
NPY_INPLACE npy_ubyte npy_lshiftuhh(npy_ubyte a, npy_ubyte b);
NPY_INPLACE npy_ushort npy_rshiftuh(npy_ushort a, npy_ushort b);
NPY_INPLACE npy_ushort npy_lshiftuh(npy_ushort a, npy_ushort b);
NPY_INPLACE npy_uint npy_rshiftu(npy_uint a, npy_uint b);
NPY_INPLACE npy_uint npy_lshiftu(npy_uint a, npy_uint b);
NPY_INPLACE npy_ulong npy_rshiftul(npy_ulong a, npy_ulong b);
NPY_INPLACE npy_ulong npy_lshiftul(npy_ulong a, npy_ulong b);
NPY_INPLACE npy_ulonglong npy_rshiftull(npy_ulonglong a, npy_ulonglong b);
NPY_INPLACE npy_ulonglong npy_lshiftull(npy_ulonglong a, npy_ulonglong b);

NPY_INPLACE npy_byte npy_rshifthh(npy_byte a, npy_byte b);
NPY_INPLACE npy_byte npy_lshifthh(npy_byte a, npy_byte b);
NPY_INPLACE npy_short npy_rshifth(npy_short a, npy_short b);
NPY_INPLACE npy_short npy_lshifth(npy_short a, npy_short b);
NPY_INPLACE npy_int npy_rshift(npy_int a, npy_int b);
NPY_INPLACE npy_int npy_lshift(npy_int a, npy_int b);
NPY_INPLACE npy_long npy_rshiftl(npy_long a, npy_long b);
NPY_INPLACE npy_long npy_lshiftl(npy_long a, npy_long b);
NPY_INPLACE npy_longlong npy_rshiftll(npy_longlong a, npy_longlong b);
NPY_INPLACE npy_longlong npy_lshiftll(npy_longlong a, npy_longlong b);

/*
* C99 double math funcs
*/
Expand Down
6 changes: 6 additions & 0 deletions numpy/core/setup.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -463,6 +463,12 @@ def generate_config_h(ext, build_dir):
rep = check_long_double_representation(config_cmd)
moredefs.append(('HAVE_LDOUBLE_%s' % rep, 1))

if check_for_right_shift_internal_compiler_error(config_cmd):
moredefs.append('NPY_DO_NOT_OPTIMIZE_LONG_right_shift')
moredefs.append('NPY_DO_NOT_OPTIMIZE_ULONG_right_shift')
moredefs.append('NPY_DO_NOT_OPTIMIZE_LONGLONG_right_shift')
moredefs.append('NPY_DO_NOT_OPTIMIZE_ULONGLONG_right_shift')

# Py3K check
if sys.version_info[0] == 3:
moredefs.append(('NPY_PY3K', 1))
Expand Down
39 changes: 39 additions & 0 deletions numpy/core/setup_common.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5,6 +5,7 @@
import warnings
import copy
import binascii
import textwrap

from numpy.distutils.misc_util import mingw32

Expand Down Expand Up @@ -414,3 +415,41 @@ def long_double_representation(lines):
else:
# We never detected the after_sequence
raise ValueError("Could not lock sequences (%s)" % saw)


def check_for_right_shift_internal_compiler_error(cmd):
"""
On our arm CI, this fails with an internal compilation error

The failure looks like the following, and can be reproduced on ARM64 GCC 5.4:

<source>: In function 'right_shift':
<source>:4:20: internal compiler error: in expand_shift_1, at expmed.c:2349
ip1[i] = ip1[i] >> in2;
^
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.
Compiler returned: 1

This function returns True if this compiler bug is present, and we need to
turn off optimization for the function
"""
cmd._check_compiler()
has_optimize = cmd.try_compile(textwrap.dedent("""\
__attribute__((optimize("O3"))) void right_shift() {}
"""), None, None)
if not has_optimize:
return False

no_err = cmd.try_compile(textwrap.dedent("""\
typedef long the_type; /* fails also for unsigned and long long */
__attribute__((optimize("O3"))) void right_shift(the_type in2, the_type *ip1, int n) {
for (int i = 0; i < n; i++) {
if (in2 < (the_type)sizeof(the_type) * 8) {
ip1[i] = ip1[i] >> in2;
}
}
}
"""), None, None)
return not no_err
41 changes: 41 additions & 0 deletions numpy/core/src/npymath/npy_math_internal.h.src
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -716,3 +716,44 @@ npy_@func@@c@(@type@ a, @type@ b)
return npy_@func@u@c@(a < 0 ? -a : a, b < 0 ? -b : b);
}
/**end repeat**/

/* Unlike LCM and GCD, we need byte and short variants for the shift operators,
* since the result is dependent on the width of the type
*/
/**begin repeat
*
* #type = byte, short, int, long, longlong#
* #c = hh,h,,l,ll#
*/
/**begin repeat1
*
* #u = u,#
* #is_signed = 0,1#
*/
NPY_INPLACE npy_@u@@type@
npy_lshift@u@@c@(npy_@u@@type@ a, npy_@u@@type@ b)
{
if (NPY_LIKELY((size_t)b < sizeof(a) * CHAR_BIT)) {
return a << b;
}
else {
return 0;
}
}
NPY_INPLACE npy_@u@@type@
npy_rshift@u@@c@(npy_@u@@type@ a, npy_@u@@type@ b)
{
if (NPY_LIKELY((size_t)b < sizeof(a) * CHAR_BIT)) {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do we want to deal with the possibility that b is negative?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not that currently the shift value is cast to unsigned and masked, at least on my hardware.

In [1]: a = array([1,2,3,4])                                                    

In [2]: a << -1                                                                 
Out[2]: 
array([-9223372036854775808,                    0, -9223372036854775808,
                          0])

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think there was a comment in the old/new code about that as well. Maybe we can push it off to another PR? That seems the easiest way forward? We can ignore the codecov failures.

Copy link
Member
@mattip mattip Jul 3, 2019 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

xref gh-13898

return a >> b;
}
#if @is_signed@
else if (a < 0) {
return (npy_@u@@type@)-1; /* preserve the sign bit */
}
#endif
else {
return 0;
}
}
/**end repeat1**/
/**end repeat**/
49 changes: 45 additions & 4 deletions numpy/core/src/umath/loops.c.src
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -699,6 +699,7 @@ BOOL_@kind@(char **args, npy_intp *dimensions, npy_intp *steps, void *NPY_UNUSED
* #ftype = npy_float, npy_float, npy_float, npy_float, npy_double, npy_double,
* npy_double, npy_double, npy_double, npy_double#
* #SIGNED = 1, 0, 1, 0, 1, 0, 1, 0, 1, 0#
* #c = hh,uhh,h,uh,,u,l,ul,ll,ull#
*/

#define @TYPE@_floor_divide @TYPE@_divide
Expand Down Expand Up @@ -776,16 +777,15 @@ NPY_NO_EXPORT NPY_GCC_OPT_3 @ATTR@ void

/**begin repeat2
* Arithmetic
* #kind = add, subtract, multiply, bitwise_and, bitwise_or, bitwise_xor,
* left_shift, right_shift#
* #OP = +, -,*, &, |, ^, <<, >>#
* #kind = add, subtract, multiply, bitwise_and, bitwise_or, bitwise_xor#
* #OP = +, -, *, &, |, ^#
*/

#if @CHK@
NPY_NO_EXPORT NPY_GCC_OPT_3 @ATTR@ void
@TYPE@_@kind@@isa@(char **args, npy_intp *dimensions, npy_intp *steps, void *NPY_UNUSED(func))
{
if(IS_BINARY_REDUCE) {
if (IS_BINARY_REDUCE) {
BINARY_REDUCE_LOOP(@type@) {
io1 @OP@= *(@type@ *)ip2;
}
Expand All @@ -799,6 +799,47 @@ NPY_NO_EXPORT NPY_GCC_OPT_3 @ATTR@ void

/**end repeat2**/

/*
* Arithmetic bit shift operations.
*
* Intel hardware masks bit shift values, so large shifts wrap around
* and can produce surprising results. The special handling ensures that
* behavior is independent of compiler or hardware.
* TODO: We could implement consistent behavior for negative shifts,
* which is undefined in C.
*/

#define INT_left_shift_needs_clear_floatstatus
#define UINT_left_shift_needs_clear_floatstatus

NPY_NO_EXPORT NPY_GCC_OPT_3 void
@TYPE@_left_shift@isa@(char **args, npy_intp *dimensions, npy_intp *steps,
void *NPY_UNUSED(func))
{
BINARY_LOOP_FAST(@type@, @type@, *out = npy_lshift@c@(in1, in2));

#ifdef @TYPE@_left_shift_needs_clear_floatstatus
// For some reason, our macOS CI sets an "invalid" flag here, but only
// for some types.
npy_clear_floatstatus_barrier((char*)dimensions);
Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I have no idea why this happens. Is our macOS run x86, or something else? Do we have a resident macOS expert?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I have no idea, was thinking about putting it in godbold, but it is quite a lot of code around it (and I am not sure it is likely to show anything in any case).

@charris, I think I am good with this as is. But you had a look at it before and know npy_math stuff better. The floatstatus thing (and I guess the compile time check) are a bit unfortunate though...

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could be a clang thing.

#endif
}

#undef INT_left_shift_needs_clear_floatstatus
#undef UINT_left_shift_needs_clear_floatstatus

NPY_NO_EXPORT
#ifndef NPY_DO_NOT_OPTIMIZE_@TYPE@_right_shift
NPY_GCC_OPT_3
#endif
void
@TYPE@_right_shift@isa@(char **args, npy_intp *dimensions, npy_intp *steps,
void *NPY_UNUSED(func))
{
BINARY_LOOP_FAST(@type@, @type@, *out = npy_rshift@c@(in1, in2));
}


/**begin repeat2
* #kind = equal, not_equal, greater, greater_equal, less, less_equal,
* logical_and, logical_or#
Expand Down
13 changes: 7 additions & 6 deletions numpy/core/src/umath/scalarmath.c.src
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -246,25 +246,26 @@ static void
/**end repeat**/



/* QUESTION: Should we check for overflow / underflow in (l,r)shift? */

/**begin repeat
* #name = byte, ubyte, short, ushort, int, uint,
* long, ulong, longlong, ulonglong#
* #type = npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int, npy_uint,
* npy_long, npy_ulong, npy_longlong, npy_ulonglong#
* #suffix = hh,uhh,h,uh,,u,l,ul,ll,ull#
*/

/**begin repeat1
* #oper = and, xor, or, lshift, rshift#
* #op = &, ^, |, <<, >>#
* #oper = and, xor, or#
* #op = &, ^, |#
*/

#define @name@_ctype_@oper@(arg1, arg2, out) *(out) = (arg1) @op@ (arg2)

/**end repeat1**/

#define @name@_ctype_lshift(arg1, arg2, out) *(out) = npy_lshift@suffix@(arg1, arg2)
#define @name@_ctype_rshift(arg1, arg2, out) *(out) = npy_rshift@suffix@(arg1, arg2)

/**end repeat**/

/**begin repeat
Expand Down Expand Up @@ -570,7 +571,7 @@ static void
* 1) Convert the types to the common type if both are scalars (0 return)
* 2) If both are not scalars use ufunc machinery (-2 return)
* 3) If both are scalars but cannot be cast to the right type
* return NotImplmented (-1 return)
* return NotImplemented (-1 return)
*
* 4) Perform the function on the C-type.
* 5) If an error condition occurred, check to see
Expand Down
28 changes: 28 additions & 0 deletions numpy/core/tests/test_scalarmath.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -664,3 +664,31 @@ def test_builtin_abs(self):

def test_numpy_abs(self):
self._test_abs_func(np.abs)


class TestBitShifts(object):

@pytest.mark.parametrize('type_code', np.typecodes['AllInteger'])
@pytest.mark.parametrize('op',
[operator.rshift, operator.lshift], ids=['>>', '<<'])
def test_shift_all_bits(self, type_code, op):
""" Shifts where the shift amount is the width of the type or wider """
# gh-2449
dt = np.dtype(type_code)
nbits = dt.itemsize * 8
for val in [5, -5]:
for shift in [nbits, nbits + 4]:
val_scl = dt.type(val)
shift_scl = dt.type(shift)
res_scl = op(val_scl, shift_scl)
if val_scl < 0 and op is operator.rshift:
# sign bit is preserved
assert_equal(res_scl, -1)
else:
assert_equal(res_scl, 0)

# Result on scalars should be the same as on arrays
val_arr = np.array([val]*32, dtype=dt)
shift_arr = np.array([shift]*32, dtype=dt)
res_arr = op(val_arr, shift_arr)
assert_equal(res_arr, res_scl)
0