10000 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 1 commit
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
Prev Previous commit
Next Next commit
MAINT: Move shift implementation to npy_math 
This avoids duplication, as suggested in review.
The suffices `l`, `ull` etc are for consistency with `strtoull` and friends.
`h` and `uhh` are inspired from the C99 printf specifiers.
  • Loading branch information
@eric-wieser
eric-wieser committed Sep 13, 2019
commit 79d7bc276afbe89c746e462d28d4bfbb4fc56148
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
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**/
45 changes: 15 additions & 30 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 @@ -808,46 +809,30 @@ NPY_NO_EXPORT NPY_GCC_OPT_3 @ATTR@ void
* 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@,
if (NPY_LIKELY(in2 < sizeof(@type@) * CHAR_BIT)) {
*out = in1 << in2;
}
else {
*out = 0;
}
);
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 NPY_GCC_OPT_3 void
@TYPE@_right_shift@isa@(char **args, npy_intp *dimensions, npy_intp *steps,
void *NPY_UNUSED(func))
{
#if @SIGNED@
BINARY_LOOP_FAST(@type@, @type@, {
if (NPY_LIKELY(in2 < sizeof(@type@) * CHAR_BIT)) {
*out = in1 >> in2;
}
else if (in1 < 0) {
*out = (@type@)-1; /* shift right preserves the sign bit */
}
else {
*out = 0;
}
});
#else
BINARY_LOOP_FAST(@type@, @type@, {
if (NPY_LIKELY(in2 < sizeof(@type@) * CHAR_BIT)) {
*out = in1 >> in2;
}
else {
*out = 0;
}
});
#endif
BINARY_LOOP_FAST(@type@, @type@, *out = npy_rshift@c@(in1, in2));
}


Expand Down
40 changes: 3 additions & 37 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 @@ -251,7 +251,7 @@ static void
* 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#
* #issigned = 1, 0, 1, 0, 1, 0, 1, 0, 1, 0#
* #suffix = hh,uhh,h,uh,,u,l,ul,ll,ull#
*/

/**begin repeat1
Expand All @@ -263,42 +263,8 @@ static void

/**end repeat1**/

/* Note: these need to be kept in sync with the shift ufuncs */

#define @name@_ctype_lshift(arg1, arg2, out) \
do { \
if (NPY_LIKELY((arg2) < sizeof(@type@) * CHAR_BIT)) { \
*(out) = (arg1) << (arg2); \
} \
else { \
*(out) = 0; \
} \
} while (0)

#if @issigned@
#define @name@_ctype_rshift(arg1, arg2, out) \
do { \
if (NPY_LIKELY((arg2) < sizeof(@type@) * CHAR_BIT)) { \
*(out) = (arg1) >> (arg2); \
} \
else if ((arg1) < 0) { \
*(out) = -1; \
} \
else { \
*(out) = 0; \
} \
} while (0)
#else
#define @name@_ctype_rshift(arg1, arg2, out) \
do { \
if (NPY_LIKELY((arg2) < sizeof(@type@) * CHAR_BIT)) { \
*(out) = (arg1) >> (arg2); \
} \
else { \
*(out) = 0; \
} \
} while (0)
#endif
#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**/

Expand Down
0