zadd.c - libzahl - big integer library
(HTM) git clone git://git.suckless.org/libzahl
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) 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"(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 }