nsz Git - libfirm/blob - ir/tv/tc_calc.c

   1 #include "irnode.h"
   2 #include "tc_calc.h"
   3
   4 /* shift bits with sign extension */
   5 #define SHRS(v, c)      ((v) < 0 ? ~((~(v)) >> (c)) : (v) >> (c))
   6
   7 #define SIGN(v) ((v)->part[0] & TC_VALUE_PART_SIGN_BIT)
   8
   9 /* the carry and overflow bits */
  10 int tc_Carry, tc_Overflow;
  11
  12 /**
  13  * Produce a tc_value from a long value
  14  */
  15 void tc_from_long(tc_value *tcv, long value) {
  16         int i;
  17
  18         for (i = NUM_VALUE_PARTS - 1; i >= 0; --i) {
  19                 long part = value & TC_VALUE_PART_MASK;
  20                 tcv->part[i] = (tc_value_part)part;
  21                 value = SHRS(value, TC_VALUE_PART_SIZE);
  22         }
  23 }
  24
  25 /**
  26  * Bit complement an tc_value: res = ~a.
  27  */
  28 void tc_not(const tc_value *a, tc_value *res) {
  29         int     i;
  30
  31         for (i = NUM_VALUE_PARTS - 1; i >= 0; --i)
  32                 res->part[i] = ~a->part[i] & TC_VALUE_PART_MAX_UINT;
  33 }
  34
  35 /**
  36  * Logical AND of two tc_values: res = a & b.
  37  */
  38 void tc_and(const tc_value *a, const tc_value *b, tc_value *res) {
  39         int     i;
  40
  41         for (i = NUM_VALUE_PARTS - 1; i >= 0; --i)
  42                 res->part[i] = a->part[i] & b->part[i];
  43 }
  44
  45 /**
  46  * Logical OR of two tc_values: res = a | b.
  47  */
  48 void tc_or(const tc_value *a, const tc_value *b, tc_value *res) {
  49         int     i;
  50
  51         for (i = NUM_VALUE_PARTS - 1; i >= 0; --i)
  52                 res->part[i] = a->part[i] | b->part[i];
  53 }
  54
  55 /**
  56  * Logical exclusive OR of two tc_values: res = a ^ b.
  57  */
  58 void tc_eor(const tc_value *a, const tc_value *b, tc_value *res) {
  59         int     i;
  60
  61         for (i = NUM_VALUE_PARTS - 1; i >= 0; --i)
  62                 res->part[i] = a->part[i] ^ b->part[i];
  63 }
  64
  65
  66 /**
  67  * Compare two tc_value's.
  68  */
  69 pn_Cmp tc_cmp(const tc_value *a, const tc_value *b, int signed_cmp) {
  70         int i;
  71
  72         if (signed_cmp) {
  73                 int sign_a = SIGN(a);
  74
  75                 if (sign_a != !SIGN(b))
  76                         return sign_a ? pn_Cmp_Lt : pn_Cmp_Gt;
  77         }
  78         for (i = 0; i < NUM_VALUE_PARTS; ++i) {
  79                 if (a->part[i] > b->part[i])
  80                         return pn_Cmp_Gt;
  81                 if (a->part[i] < b->part[i])
  82                         return pn_Cmp_Lt;
  83         }
  84         return pn_Cmp_Eq;
  85 }
  86
  87 /**
  88  * Add two tc_values: res = a + b. Sets carry and overflow.
  89  */
  90 void tc_add(const tc_value *a, const tc_value *b, tc_value *res) {
  91         int     i, carry = 0, sign_a;
  92
  93         tc_Carry = tc_Overflow = 0;
  94
  95         for (i = NUM_VALUE_PARTS - 1; i >= 0; --i) {
  96                 tc_temp t = (tc_temp)a->part[i] + (tc_temp)b->part[i] + carry;
  97                 if (t > TC_VALUE_PART_MAX_UINT) {
  98                         t -= TC_VALUE_PART_MAX_UINT;
  99                         carry = 1;
 100                 } else
 101                         carry = 0;
 102                 res->part[i] = (tc_value_part)t;
 103         }
 104         /* Check for overflow. */
 105         tc_Carry = carry;
 106
 107         /* A signed overflow occurred if the two operands have the same sign and
 108        the result has a different sign. */
 109         sign_a = SIGN(a);
 110     tc_Overflow = (sign_a == SIGN(b)) && (sign_a != SIGN(res));
 111 }
 112
 113 /**
 114  * Subtract two tc_values: res = a - b. Sets carry and overflow.
 115  */
 116 void tc_sub(const tc_value *a, const tc_value *b, tc_value *res) {
 117         int         i, sign_a;
 118         tc_temp borrow = 0;
 119
 120         tc_Carry = tc_Overflow = 0;
 121         for (i = NUM_VALUE_PARTS - 1; i >= 0; --i) {
 122                 tc_temp t;
 123                 t = (tc_temp)a->part[i] - (tc_temp)b->part[i] - borrow;
 124                 if (t < 0) {
 125                         t += TC_VALUE_PART_MAX_UINT + 1;
 126                         borrow = 1;
 127                 } else
 128                         borrow = 0;
 129                 res->part[i] = (tc_value_part)t;
 130         }
 131         /* Check for underflow or overflow. */
 132         tc_Carry = borrow;
 133         /* A signed overflow occurred if the two operands have the same sign and
 134        the result has a different sign. */
 135         sign_a = SIGN(a);
 136     tc_Overflow = (sign_a == SIGN(b)) && (sign_a != SIGN(res));
 137 }
 138
 139 /**
 140  * Negate an tc_value: res = -a. Sets carry and overflow.
 141  */
 142 void tc_neg(const tc_value *a, tc_value *res) {
 143         tc_from_long(res, 0);
 144         tc_sub(res, a, res);
 145 }
 146
 147 #define NUM_WORK_PARTS (NUM_VALUE_PARTS * 2)
 148
 149 /**
 150  * Multiply two unsigned tc_values producing a double precision result : w = a * b.
 151  */
 152 static void _tc_umul(const tc_value *a, const tc_value *b, tc_value_part *w) {
 153         const tc_value_part *u = a->part;
 154         const tc_value_part *v = b->part;
 155
 156         int i, j;
 157
 158         for (i = 0; i < NUM_WORK_PARTS; ++i)
 159                 w[i] = 0;
 160
 161         for (j = NUM_VALUE_PARTS - 1; j >= 0; --j) {
 162                 tc_temp k = 0;
 163                 for (i = NUM_VALUE_PARTS - 1; i >= 0; --i) {
 164                         tc_temp t = u[i] * v[j] + k;
 165                         w[i + j] = t & TC_VALUE_PART_MASK;
 166                         k = t >> 16;
 167                 }
 168                 w[j + NUM_VALUE_PARTS] = k & TC_VALUE_PART_MASK;
 169         }
 170 }
 171
 172 /**
 173  * Multiply two unsigned tc_values: res = a * b.
 174  */
 175 void tc_umul(const tc_value *a, const tc_value *b, tc_value *res) {
 176         tc_value_part w[NUM_WORK_PARTS];
 177         int i, ov = 0;
 178
 179         _tc_umul(a, b, w);
 180
 181         /* copy the lower result bits */
 182         for (i = 0; i < NUM_VALUE_PARTS; ++i)
 183                 res->part[i] = (tc_value_part)w[i];
 184
 185         /* check for overflow */
 186         for (; i < NUM_WORK_PARTS; ++i) {
 187                 if (w[i] != 0) {
 188                         ov = 0;
 189                         break;
 190                 }
 191         }
 192         tc_Overflow = tc_Carry = ov;
 193 }
 194
 195
 196 /**
 197  * Multiply two signed tc_values: res = a * b.
 198  */
 199 void tc_smul(const tc_value *a, const tc_value *b, tc_value *res) {
 200         tc_value_part w[NUM_WORK_PARTS];
 201         int i, ov = 0, neg_res = 0;
 202         const tc_value *u = a, *v = b;
 203         tc_value na, nb;
 204
 205         if (SIGN(a)) {
 206                 tc_neg(a, &na);
 207                 u = &na;
 208                 neg_res = ~neg_res;
 209         }
 210         if (SIGN(b)) {
 211                 tc_neg(b, &nb);
 212                 v = &nb;
 213                 neg_res = ~neg_res;
 214         }
 215
 216         _tc_umul(u, v, w);
 217
 218         /* copy the lower result bits */
 219         for (i = 0; i < NUM_VALUE_PARTS; ++i)
 220                 res->part[i] = (tc_value_part)w[i];
 221
 222         /* check for overflow */
 223         for (; i < NUM_WORK_PARTS; ++i) {
 224                 if (w[i] != 0) {
 225                         ov = 0;
 226                         break;
 227                 }
 228         }
 229
 230         if (neg_res)
 231                 tc_neg(res, res);
 232
 233         tc_Overflow = tc_Carry = ov;
 234 }
 235
 236 /**
 237  * Multiply two unsigned tc_values: divres = a / b, modres = a % b.
 238  */
 239 static void _tc_divmodu(const tc_value *a, const tc_value *b, tc_value **divres, tc_value **modres) {
 240         static tc_value zero;
 241         int overflow;
 242
 243         /* Check for division by 0, 0 / x, and a < b */
 244         tc_from_long(&zero, 0);
 245         if (tc_cmp(b, &zero, 0) == pn_Cmp_Eq) {
 246                 /* div by zero. */
 247                 *divres = &zero;
 248                 *modres = &zero;
 249                 tc_Carry = tc_Overflow = 1;
 250                 return;
 251         }
 252         if (tc_cmp(a, &zero, 0) == pn_Cmp_Eq) {
 253                 /* 0 / b = 0 */
 254                 *divres = &zero;
 255                 *modres = &zero;
 256                 tc_Carry = tc_Overflow = 0;
 257                 return;
 258         }
 259         if (tc_cmp(a, b, 0) == pn_Cmp_Lt) {
 260                 /* a < b ==> a / b = 0 mod a */
 261                 *divres = &zero;
 262                 *modres = a;
 263                 tc_Carry = tc_Overflow = 0;
 264                 return;
 265         }
 266
 267 }