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 47int 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 56int64_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 78unsigned 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 87uint64_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 108int 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 117int64_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 139unsigned subu(unsigned x, unsigned y, bool& overflow) 140{ 141 if (x < y) 142 overflow = true; 143 return x - y; 144} 145 146/// ditto 147uint64_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 164int negs(int x, bool& overflow) 165{ 166 if (x == (int)INT32_MIN) 167 overflow = true; 168 return -x; 169} 170 171/// ditto 172int64_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 192int 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 201int64_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 223unsigned 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 232uint64_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