1 2 /********************************************** 3 * This module implements integral arithmetic primitives that check 4 * for out-of-range results. 5 * This is a translation to C++ of D's core.checkedint 6 * 7 * Integral arithmetic operators operate on fixed width types. 8 * Results that are not representable in those fixed widths are silently 9 * truncated to fit. 10 * This module offers integral arithmetic primitives that produce the 11 * same results, but set an 'overflow' flag when such truncation occurs. 12 * The setting is sticky, meaning that numerous operations can be cascaded 13 * and then the flag need only be checked at the end. 14 * Whether the operation is signed or unsigned is indicated by an 's' or 'u' 15 * suffix, respectively. While this could be achieved without such suffixes by 16 * using overloading on the signedness of the types, the suffix makes it clear 17 * which is happening without needing to examine the types. 18 * 19 * While the generic versions of these functions are computationally expensive 20 * relative to the cost of the operation itself, compiler implementations are free 21 * to recognize them and generate equivalent and faster code. 22 * 23 * References: $(LINK2 http://blog.regehr.org/archives/1139, Fast Integer Overflow Checks) 24 * Copyright: Copyright (C) 2014-2019 by The D Language Foundation, All Rights Reserved 25 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 26 * Authors: Walter Bright 27 * Source: https://github.com/D-Programming-Language/dmd/blob/master/src/root/checkedint.c 28 */ 29 30 #include "dsystem.h" 31 #include "checkedint.h" 32 33 34 /******************************* 35 * Add two signed integers, checking for overflow. 36 * 37 * The overflow is sticky, meaning a sequence of operations can 38 * be done and overflow need only be checked at the end. 39 * Params: 40 * x = left operand 41 * y = right operand 42 * overflow = set if an overflow occurs, is not affected otherwise 43 * Returns: 44 * the sum 45 */ 46 47 int adds(int x, int y, bool& overflow) 48 { 49 int64_t r = (int64_t)x + (int64_t)y; 50 if (r < INT32_MIN || r > INT32_MAX) 51 overflow = true; 52 return (int)r; 53 } 54 55 /// ditto 56 int64_t adds(int64_t x, int64_t y, bool& overflow) 57 { 58 int64_t r = (uint64_t)x + (uint64_t)y; 59 if ((x < 0 && y < 0 && r >= 0) || 60 (x >= 0 && y >= 0 && r < 0)) 61 overflow = true; 62 return r; 63 } 64 65 /******************************* 66 * Add two unsigned integers, checking for overflow (aka carry). 67 * 68 * The overflow is sticky, meaning a sequence of operations can 69 * be done and overflow need only be checked at the end. 70 * Params: 71 * x = left operand 72 * y = right operand 73 * overflow = set if an overflow occurs, is not affected otherwise 74 * Returns: 75 * the sum 76 */ 77 78 unsigned addu(unsigned x, unsigned y, bool& overflow) 79 { 80 unsigned r = x + y; 81 if (r < x || r < y) 82 overflow = true; 83 return r; 84 } 85 86 /// ditto 87 uint64_t addu(uint64_t x, uint64_t y, bool& overflow) 88 { 89 uint64_t r = x + y; 90 if (r < x || r < y) 91 overflow = true; 92 return r; 93 } 94 95 /******************************* 96 * Subtract two signed integers, checking for overflow. 97 * 98 * The overflow is sticky, meaning a sequence of operations can 99 * be done and overflow need only be checked at the end. 100 * Params: 101 * x = left operand 102 * y = right operand 103 * overflow = set if an overflow occurs, is not affected otherwise 104 * Returns: 105 * the sum 106 */ 107 108 int subs(int x, int y, bool& overflow) 109 { 110 int64_t r = (int64_t)x - (int64_t)y; 111 if (r < INT32_MIN || r > INT32_MAX) 112 overflow = true; 113 return (int)r; 114 } 115 116 /// ditto 117 int64_t subs(int64_t x, int64_t y, bool& overflow) 118 { 119 int64_t r = (uint64_t)x - (uint64_t)y; 120 if ((x < 0 && y >= 0 && r >= 0) || 121 (x >= 0 && y < 0 && (r < 0 || y == INT64_MIN))) 122 overflow = true; 123 return r; 124 } 125 126 /******************************* 127 * Subtract two unsigned integers, checking for overflow (aka borrow). 128 * 129 * The overflow is sticky, meaning a sequence of operations can 130 * be done and overflow need only be checked at the end. 131 * Params: 132 * x = left operand 133 * y = right operand 134 * overflow = set if an overflow occurs, is not affected otherwise 135 * Returns: 136 * the sum 137 */ 138 139 unsigned subu(unsigned x, unsigned y, bool& overflow) 140 { 141 if (x < y) 142 overflow = true; 143 return x - y; 144 } 145 146 /// ditto 147 uint64_t subu(uint64_t x, uint64_t y, bool& overflow) 148 { 149 if (x < y) 150 overflow = true; 151 return x - y; 152 } 153 154 /*********************************************** 155 * Negate an integer. 156 * 157 * Params: 158 * x = operand 159 * overflow = set if x cannot be negated, is not affected otherwise 160 * Returns: 161 * the negation of x 162 */ 163 164 int negs(int x, bool& overflow) 165 { 166 if (x == (int)INT32_MIN) 167 overflow = true; 168 return -x; 169 } 170 171 /// ditto 172 int64_t negs(int64_t x, bool& overflow) 173 { 174 if (x == INT64_MIN) 175 overflow = true; 176 return -x; 177 } 178 179 /******************************* 180 * Multiply two signed integers, checking for overflow. 181 * 182 * The overflow is sticky, meaning a sequence of operations can 183 * be done and overflow need only be checked at the end. 184 * Params: 185 * x = left operand 186 * y = right operand 187 * overflow = set if an overflow occurs, is not affected otherwise 188 * Returns: 189 * the sum 190 */ 191 192 int muls(int x, int y, bool& overflow) 193 { 194 int64_t r = (int64_t)x * (int64_t)y; 195 if (r < INT32_MIN || r > INT32_MAX) 196 overflow = true; 197 return (int)r; 198 } 199 200 /// ditto 201 int64_t muls(int64_t x, int64_t y, bool& overflow) 202 { 203 int64_t r = (uint64_t)x * (uint64_t)y; 204 int64_t not0or1 = ~(int64_t)1; 205 if ((x & not0or1) && ((r == y) ? r : (r / x) != y)) 206 overflow = true; 207 return r; 208 } 209 210 /******************************* 211 * Multiply two unsigned integers, checking for overflow (aka carry). 212 * 213 * The overflow is sticky, meaning a sequence of operations can 214 * be done and overflow need only be checked at the end. 215 * Params: 216 * x = left operand 217 * y = right operand 218 * overflow = set if an overflow occurs, is not affected otherwise 219 * Returns: 220 * the sum 221 */ 222 223 unsigned mulu(unsigned x, unsigned y, bool& overflow) 224 { 225 uint64_t r = (uint64_t)x * (uint64_t)y; 226 if (r > UINT32_MAX) 227 overflow = true; 228 return (unsigned)r; 229 } 230 231 /// ditto 232 uint64_t mulu(uint64_t x, uint64_t y, bool& overflow) 233 { 234 uint64_t r = x * y; 235 if (x && (r / x) != y) 236 overflow = true; 237 return r; 238 } 239