GopherProxy

	zadd.c - libzahl - big integer library
	git clone git://git.suckless.org/libzahl
	Log
	Files
	Refs
	README
	LICENSE
	---
	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…
	8
	9 # define ASM2(code) \
	10 __asm__ __volatile__ (code : [x]"+r"(carry), [a]"+r"(ac), [b]"+r…
	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…
	40 switch (n & 3) { …
	41 case 3: …
	42 ASM##N(WRAP_CARRY(ADD##N(-32) ADD##N(-24) ADD##N…
	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->ch…
	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->ch…
	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 + …
	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 }