gcc/d/dmd/checkedint.c

   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-2018 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/port.c
  28  */
  29
  30 #include <assert.h>
  31
  32 #include "checkedint.h"
  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 }