Fix PR47973: Addressing integer division edge case with INT_MIN

[akuran]

Summary

Adjustment to integer division in int_div_impl.inc to avoid undefined behaviour that can occur as a result of having INT_MIN as one of the parameters.

[akuran]

Restart build

[akuran]

Ping

[sepavloff]

compiler-rt/lib/builtins/int_div_impl.inc

77

What is the purpose of using addition+negation instead of subtraction?

[akuran]

compiler-rt/lib/builtins/int_div_impl.inc

77

(fixuint_t)a^s_a will always be some unsigned value, and with just subtraction we have <unsigned> - s_a. And when s_a = -1, s_a will get promoted to an unsigned value UINT_MAX, resulting in <unsigned> - UINT_MAX which can result in undefined behaviour. By negating s_a first we'd ensure that the operation there is always just either +0 or +1.

[sepavloff]

LGTM

compiler-rt/lib/builtins/int_div_impl.inc

for (; sr > 0; --sr) {
     r -= d & s;
   }
   return r;
 }
 
 #ifdef COMPUTE_UDIV
 static __inline fixint_t __divXi3(fixint_t a, fixint_t b) {
   const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1;
-  fixint_t s_a = a >> N;                   // s_a = a < 0 ? -1 : 0
-  fixint_t s_b = b >> N;                   // s_b = b < 0 ? -1 : 0
-  a = (a ^ s_a) - s_a;                     // negate if s_a == -1
-  b = (b ^ s_b) - s_b;                     // negate if s_b == -1
-  s_a ^= s_b;                              // sign of quotient
-  return (COMPUTE_UDIV(a, b) ^ s_a) - s_a; // negate if s_a == -1
+  fixint_t s_a = a >> N;                            // s_a = a < 0 ? -1 : 0
+  fixint_t s_b = b >> N;                            // s_b = b < 0 ? -1 : 0
+  fixuint_t a_u = (fixuint_t)(a ^ s_a) + (-s_a);    // negate if s_a == -1
+  fixuint_t b_u = (fixuint_t)(b ^ s_b) + (-s_b);    // negate if s_b == -1
+  s_a ^= s_b;                                       // sign of quotient
+  return (COMPUTE_UDIV(a_u, b_u) ^ s_a) + (-s_a);   // negate if s_a == -1
 }
 #endif // COMPUTE_UDIV
 
 #ifdef ASSIGN_UMOD
 static __inline fixint_t __modXi3(fixint_t a, fixint_t b) {
   const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1;
-  fixint_t s = b >> N;    // s = b < 0 ? -1 : 0
-  b = (b ^ s) - s;        // negate if s == -1
-  s = a >> N;             // s = a < 0 ? -1 : 0
-  a = (a ^ s) - s;        // negate if s == -1
+  fixint_t s = b >> N;                              // s = b < 0 ? -1 : 0
+  fixuint_t b_u = (fixuint_t)(b ^ s) + (-s);        // negate if s == -1
+  s = a >> N;                                       // s = a < 0 ? -1 : 0
+  fixuint_t a_u = (fixuint_t)(a ^ s) + (-s);        // negate if s == -1
   fixuint_t res;
-  ASSIGN_UMOD(res, a, b);
-  return (res ^ s) - s;   // negate if s == -1
+  ASSIGN_UMOD(res, a_u, b_u);
+  return (res ^ s) + (-s);                          // negate if s == -1
 }
 #endif // ASSIGN_UMOD