zadd.c (5611B)
1 /* See LICENSE file for copyright and license details. */ 2 #include "internals.h" 3 4 5 #if defined(__x86_64__) && !defined(ZAHL_NO_ASM) 6 # define ASM3(code) \ 7 __asm__ __volatile__ (code : [x]"+r"(carry), [a]"+r"(ac), [b]"+r"(bc), [c]"+r"(cc)) 8 9 # define ASM2(code) \ 10 __asm__ __volatile__ (code : [x]"+r"(carry), [a]"+r"(ac), [b]"+r"(bc)) 11 12 # define ADD2(off) \ 13 "\n movq "#off"(%[b]), %[x]" \ 14 "\n adcq %[x], "#off"(%[a])" 15 16 # define ADD3(off) \ 17 "\n movq "#off"(%[b]), %[x]" \ 18 "\n adcq "#off"(%[c]), %[x]" \ 19 "\n movq %[x], "#off"(%[a])" 20 21 # define WRAP_CARRY(interior) \ 22 "\n addq $-1, %[x]" \ 23 interior \ 24 "\n movq $1, %[x]" \ 25 "\n jc 1f" \ 26 "\n movq $0, %[x]" \ 27 "\n 1:" 28 /* 29 * I have already tried setc, cmovnc, cmovc, and adc, 30 * instead of the last four lines. There does not seem 31 * to be any better why to store the carry flag. 32 */ 33 34 # define ASM_ADD(N) \ 35 do { \ 36 register zahl_char_t carry = 0; \ 37 size_t i; \ 38 for (i = 0; (INC(4)), (i += 4) <= n;) \ 39 ASM##N(WRAP_CARRY(ADD##N(-32) ADD##N(-24) ADD##N(-16) ADD##N(-8))); \ 40 switch (n & 3) { \ 41 case 3: \ 42 ASM##N(WRAP_CARRY(ADD##N(-32) ADD##N(-24) ADD##N(-16))); \ 43 break; \ 44 case 2: \ 45 ASM##N(WRAP_CARRY(ADD##N(-32) ADD##N(-24))); \ 46 break; \ 47 case 1: \ 48 ASM##N(WRAP_CARRY(ADD##N(-32))); \ 49 break; \ 50 default: \ 51 break; \ 52 } \ 53 i = n; \ 54 while (carry) { \ 55 carry = libzahl_add_overflow(a->chars + i, a->chars[i], 1); \ 56 i++; \ 57 } \ 58 if (a->used < i) \ 59 a->used = i; \ 60 } while (0) 61 #endif 62 63 64 static inline void 65 zadd_impl_4(z_t a, z_t b, z_t c, size_t n) 66 { 67 #ifdef ASM_ADD 68 register zahl_char_t *ac = a->chars, *bc = b->chars, *cc = c->chars; 69 # define INC(P) (ac += (P), bc += (P), cc += (P)) 70 ASM_ADD(3); 71 # undef INC 72 #else 73 zahl_char_t carry = 0, tcarry; 74 zahl_char_t *ac = a->chars, *bc = b->chars, *cc = c->chars; 75 size_t i; 76 77 for (i = 0; i < n; i++) { 78 tcarry = libzahl_add_overflow(ac + i, bc[i], cc[i]); 79 carry = tcarry | (zahl_char_t)libzahl_add_overflow(ac + i, ac[i], carry); 80 } 81 82 while (carry) { 83 carry = libzahl_add_overflow(ac + i, ac[i], 1); 84 i++; 85 } 86 87 if (a->used < i) 88 a->used = i; 89 #endif 90 } 91 92 static inline void 93 zadd_impl_3(z_t a, z_t b, size_t n) 94 { 95 #ifdef ASM_ADD 96 register zahl_char_t *ac = a->chars, *bc = b->chars; 97 # define INC(P) (ac += (P), bc += (P)) 98 ASM_ADD(2); 99 # undef INC 100 #else 101 zadd_impl_4(a, a, b, n); 102 #endif 103 } 104 105 static inline void 106 libzahl_zadd_unsigned(z_t a, z_t b, z_t c) 107 { 108 size_t size, n; 109 110 if (unlikely(zzero(b))) { 111 zabs(a, c); 112 return; 113 } else if (unlikely(zzero(c))) { 114 zabs(a, b); 115 return; 116 } 117 118 size = MAX(b->used, c->used); 119 n = b->used + c->used - size; 120 121 ENSURE_SIZE(a, size + 1); 122 a->chars[size] = 0; 123 124 if (a == b) { 125 if (a->used < c->used) { 126 n = c->used; 127 zmemset(a->chars + a->used, 0, n - a->used); 128 } 129 zadd_impl_3(a, c, n); 130 } else if (unlikely(a == c)) { 131 if (a->used < b->used) { 132 n = b->used; 133 zmemset(a->chars + a->used, 0, n - a->used); 134 } 135 zadd_impl_3(a, b, n); 136 } else if (likely(b->used > c->used)) { 137 zmemcpy(a->chars + n, b->chars + n, size - n); 138 a->used = size; 139 zadd_impl_4(a, b, c, n); 140 } else { 141 zmemcpy(a->chars + n, c->chars + n, size - n); 142 a->used = size; 143 zadd_impl_4(a, b, c, n); 144 } 145 146 SET_SIGNUM(a, 1); 147 } 148 149 void 150 zadd_unsigned(z_t a, z_t b, z_t c) 151 { 152 libzahl_zadd_unsigned(a, b, c); 153 } 154 155 void 156 zadd_unsigned_assign(z_t a, z_t b) 157 { 158 size_t size, n; 159 160 if (unlikely(zzero(a))) { 161 zabs(a, b); 162 return; 163 } else if (unlikely(zzero(b))) { 164 return; 165 } 166 167 size = MAX(a->used, b->used); 168 n = a->used + b->used - size; 169 170 ENSURE_SIZE(a, size + 1); 171 a->chars[size] = 0; 172 173 if (a->used < b->used) { 174 n = b->used; 175 zmemset(a->chars + a->used, 0, n - a->used); 176 } 177 zadd_impl_3(a, b, n); 178 179 SET_SIGNUM(a, 1); 180 } 181 182 void 183 zadd(z_t a, z_t b, z_t c) 184 { 185 if (unlikely(zzero(b))) { 186 SET(a, c); 187 } else if (unlikely(zzero(c))) { 188 SET(a, b); 189 } else if (unlikely(znegative(b))) { 190 if (znegative(c)) { 191 libzahl_zadd_unsigned(a, b, c); 192 SET_SIGNUM(a, -zsignum(a)); 193 } else { 194 zsub_unsigned(a, c, b); 195 } 196 } else if (unlikely(znegative(c))) { 197 zsub_unsigned(a, b, c); 198 } else { 199 libzahl_zadd_unsigned(a, b, c); 200 } 201 }