OLD | NEW |
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ | 1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
2 /* cairo - a vector graphics library with display and print output | 2 /* cairo - a vector graphics library with display and print output |
3 * | 3 * |
4 * Copyright © 2004 Keith Packard | 4 * Copyright © 2004 Keith Packard |
5 * | 5 * |
6 * This program is free software; you can redistribute it and/or modify | 6 * This program is free software; you can redistribute it and/or modify |
7 * it under the terms of the GNU General Public License version 2 as | 7 * it under the terms of the GNU General Public License version 2 as |
8 * published by the Free Software Foundation; | 8 * published by the Free Software Foundation; |
9 * | 9 * |
10 * This program is distributed in the hope that it will be useful, | 10 * This program is distributed in the hope that it will be useful, |
(...skipping 21 matching lines...) Expand all Loading... |
32 #include "cairo-wideint-private.h" | 32 #include "cairo-wideint-private.h" |
33 | 33 |
34 /** | 34 /** |
35 * \file | 35 * \file |
36 * \ingroup highprec | 36 * \ingroup highprec |
37 * Implementation of the cairo_x functions which implement high precision arithm
etic. | 37 * Implementation of the cairo_x functions which implement high precision arithm
etic. |
38 */ | 38 */ |
39 | 39 |
40 #if HAVE_UINT64_T | 40 #if HAVE_UINT64_T |
41 | 41 |
42 const char * cairo_impl64 = "uint64_t"; | 42 const char * cairo_impl64 = "uint64_t"; ///< implementation name |
43 | 43 |
| 44 /// uint32 to uint64 conversion |
44 #define _cairo_uint32s_to_uint64(h,l) ((uint64_t) (h) << 32 | (l)) | 45 #define _cairo_uint32s_to_uint64(h,l) ((uint64_t) (h) << 32 | (l)) |
45 | 46 |
| 47 /** |
| 48 * uint64 quotient remainder divide. |
| 49 *· |
| 50 * \param num numerator |
| 51 * \param den denominator |
| 52 * \returns quotient and remainder |
| 53 */ |
46 cairo_uquorem64_t | 54 cairo_uquorem64_t |
47 _cairo_uint64_divrem (cairo_uint64_t num, cairo_uint64_t den) | 55 _cairo_uint64_divrem (cairo_uint64_t num, cairo_uint64_t den) |
48 { | 56 { |
49 cairo_uquorem64_t qr; | 57 cairo_uquorem64_t qr; |
50 | 58 |
51 qr.quo = num / den; | 59 qr.quo = num / den; |
52 qr.rem = num % den; | 60 qr.rem = num % den; |
53 return qr; | 61 return qr; |
54 } | 62 } |
55 | 63 |
56 #else | 64 #else |
57 | 65 |
58 const char * cairo_impl64 = "uint32_t"; | 66 const char * cairo_impl64 = "uint32_t"; ///< implementation name |
59 | 67 |
| 68 /** |
| 69 * uint32 to uint64 conversion. |
| 70 *· |
| 71 * \param i uint32 |
| 72 * \returns uint64 |
| 73 */ |
60 cairo_uint64_t | 74 cairo_uint64_t |
61 _cairo_uint32_to_uint64 (uint32_t i) | 75 _cairo_uint32_to_uint64 (uint32_t i) |
62 { | 76 { |
63 cairo_uint64_t q; | 77 cairo_uint64_t q; |
64 | 78 |
65 q.lo = i; | 79 q.lo = i; |
66 q.hi = 0; | 80 q.hi = 0; |
67 return q; | 81 return q; |
68 } | 82 } |
69 | 83 |
| 84 /** |
| 85 * int32 to int64 conversion. |
| 86 * |
| 87 * \param i int32 |
| 88 * \returns int64 |
| 89 */ |
70 cairo_int64_t | 90 cairo_int64_t |
71 _cairo_int32_to_int64 (int32_t i) | 91 _cairo_int32_to_int64 (int32_t i) |
72 { | 92 { |
73 cairo_uint64_t q; | 93 cairo_uint64_t q; |
74 | 94 |
75 q.lo = i; | 95 q.lo = i; |
76 q.hi = i < 0 ? -1 : 0; | 96 q.hi = i < 0 ? -1 : 0; |
77 return q; | 97 return q; |
78 } | 98 } |
79 | 99 |
| 100 /** |
| 101 * uint32 pair to uint64 conversion. |
| 102 * |
| 103 * \param h uint32 |
| 104 * \param l uint32 |
| 105 * \returns uint64 |
| 106 */ |
80 static cairo_uint64_t | 107 static cairo_uint64_t |
81 _cairo_uint32s_to_uint64 (uint32_t h, uint32_t l) | 108 _cairo_uint32s_to_uint64 (uint32_t h, uint32_t l) |
82 { | 109 { |
83 cairo_uint64_t q; | 110 cairo_uint64_t q; |
84 | 111 |
85 q.lo = l; | 112 q.lo = l; |
86 q.hi = h; | 113 q.hi = h; |
87 return q; | 114 return q; |
88 } | 115 } |
89 | 116 |
| 117 /** |
| 118 * uint64 addition. |
| 119 * |
| 120 * \param a uint64 |
| 121 * \param b uint64 |
| 122 * \returns uint64 |
| 123 */ |
90 cairo_uint64_t | 124 cairo_uint64_t |
91 _cairo_uint64_add (cairo_uint64_t a, cairo_uint64_t b) | 125 _cairo_uint64_add (cairo_uint64_t a, cairo_uint64_t b) |
92 { | 126 { |
93 cairo_uint64_t s; | 127 cairo_uint64_t s; |
94 | 128 |
95 s.hi = a.hi + b.hi; | 129 s.hi = a.hi + b.hi; |
96 s.lo = a.lo + b.lo; | 130 s.lo = a.lo + b.lo; |
97 if (s.lo < a.lo) | 131 if (s.lo < a.lo) |
98 s.hi++; | 132 s.hi++; |
99 return s; | 133 return s; |
100 } | 134 } |
101 | 135 |
| 136 /** |
| 137 * uint64 subtraction. |
| 138 * |
| 139 * \param a uint64 |
| 140 * \param b uint64 |
| 141 * \returns uint64 |
| 142 */ |
102 cairo_uint64_t | 143 cairo_uint64_t |
103 _cairo_uint64_sub (cairo_uint64_t a, cairo_uint64_t b) | 144 _cairo_uint64_sub (cairo_uint64_t a, cairo_uint64_t b) |
104 { | 145 { |
105 cairo_uint64_t s; | 146 cairo_uint64_t s; |
106 | 147 |
107 s.hi = a.hi - b.hi; | 148 s.hi = a.hi - b.hi; |
108 s.lo = a.lo - b.lo; | 149 s.lo = a.lo - b.lo; |
109 if (s.lo > a.lo) | 150 if (s.lo > a.lo) |
110 s.hi--; | 151 s.hi--; |
111 return s; | 152 return s; |
112 } | 153 } |
113 | 154 |
| 155 /// low 16 bits of uint32 |
114 #define uint32_lo(i) ((i) & 0xffff) | 156 #define uint32_lo(i) ((i) & 0xffff) |
| 157 /// high 16 bits of uint32 |
115 #define uint32_hi(i) ((i) >> 16) | 158 #define uint32_hi(i) ((i) >> 16) |
| 159 /// carry 16 bits of uint32 |
116 #define uint32_carry16 ((1) << 16) | 160 #define uint32_carry16 ((1) << 16) |
117 | 161 |
| 162 /** |
| 163 * uint32 x uint32 multiplication. |
| 164 * |
| 165 * \param a uint32 |
| 166 * \param b uint32 |
| 167 * \returns uint64 |
| 168 */ |
118 cairo_uint64_t | 169 cairo_uint64_t |
119 _cairo_uint32x32_64_mul (uint32_t a, uint32_t b) | 170 _cairo_uint32x32_64_mul (uint32_t a, uint32_t b) |
120 { | 171 { |
121 cairo_uint64_t s; | 172 cairo_uint64_t s; |
122 | 173 |
123 uint16_t ah, al, bh, bl; | 174 uint16_t ah, al, bh, bl; |
124 uint32_t r0, r1, r2, r3; | 175 uint32_t r0, r1, r2, r3; |
125 | 176 |
126 al = uint32_lo (a); | 177 al = uint32_lo (a); |
127 ah = uint32_hi (a); | 178 ah = uint32_hi (a); |
128 bl = uint32_lo (b); | 179 bl = uint32_lo (b); |
129 bh = uint32_hi (b); | 180 bh = uint32_hi (b); |
130 | 181 |
131 r0 = (uint32_t) al * bl; | 182 r0 = (uint32_t) al * bl; |
132 r1 = (uint32_t) al * bh; | 183 r1 = (uint32_t) al * bh; |
133 r2 = (uint32_t) ah * bl; | 184 r2 = (uint32_t) ah * bl; |
134 r3 = (uint32_t) ah * bh; | 185 r3 = (uint32_t) ah * bh; |
135 | 186 |
136 r1 += uint32_hi(r0); /* no carry possible */ | 187 r1 += uint32_hi(r0); /* no carry possible */ |
137 r1 += r2; /* but this can carry */ | 188 r1 += r2; /* but this can carry */ |
138 if (r1 < r2) /* check */ | 189 if (r1 < r2) /* check */ |
139 r3 += uint32_carry16; | 190 r3 += uint32_carry16; |
140 | 191 |
141 s.hi = r3 + uint32_hi(r1); | 192 s.hi = r3 + uint32_hi(r1); |
142 s.lo = (uint32_lo (r1) << 16) + uint32_lo (r0); | 193 s.lo = (uint32_lo (r1) << 16) + uint32_lo (r0); |
143 return s; | 194 return s; |
144 } | 195 } |
145 | 196 |
| 197 /** |
| 198 * int32 x int32 multiplication. |
| 199 * |
| 200 * \param a int32 |
| 201 * \param b int32 |
| 202 * \returns int64 |
| 203 */ |
146 cairo_int64_t | 204 cairo_int64_t |
147 _cairo_int32x32_64_mul (int32_t a, int32_t b) | 205 _cairo_int32x32_64_mul (int32_t a, int32_t b) |
148 { | 206 { |
149 cairo_int64_t s; | 207 cairo_int64_t s; |
150 s = _cairo_uint32x32_64_mul ((uint32_t) a, (uint32_t) b); | 208 s = _cairo_uint32x32_64_mul ((uint32_t) a, (uint32_t) b); |
151 if (a < 0) | 209 if (a < 0) |
152 s.hi -= b; | 210 s.hi -= b; |
153 if (b < 0) | 211 if (b < 0) |
154 s.hi -= a; | 212 s.hi -= a; |
155 return s; | 213 return s; |
156 } | 214 } |
157 | 215 |
| 216 /** |
| 217 * uint64 x uint64 multiplication. |
| 218 * |
| 219 * \param a uint64 |
| 220 * \param b uint64 |
| 221 * \returns uint64 |
| 222 */ |
158 cairo_uint64_t | 223 cairo_uint64_t |
159 _cairo_uint64_mul (cairo_uint64_t a, cairo_uint64_t b) | 224 _cairo_uint64_mul (cairo_uint64_t a, cairo_uint64_t b) |
160 { | 225 { |
161 cairo_uint64_t s; | 226 cairo_uint64_t s; |
162 | 227 |
163 s = _cairo_uint32x32_64_mul (a.lo, b.lo); | 228 s = _cairo_uint32x32_64_mul (a.lo, b.lo); |
164 s.hi += a.lo * b.hi + a.hi * b.lo; | 229 s.hi += a.lo * b.hi + a.hi * b.lo; |
165 return s; | 230 return s; |
166 } | 231 } |
167 | 232 |
| 233 /** |
| 234 * uint64 logical shift left. |
| 235 * |
| 236 * \param a uint64 |
| 237 * \param shift bits to shift |
| 238 * \returns uint64 |
| 239 */ |
168 cairo_uint64_t | 240 cairo_uint64_t |
169 _cairo_uint64_lsl (cairo_uint64_t a, int shift) | 241 _cairo_uint64_lsl (cairo_uint64_t a, int shift) |
170 { | 242 { |
171 if (shift >= 32) | 243 if (shift >= 32) |
172 { | 244 { |
173 a.hi = a.lo; | 245 a.hi = a.lo; |
174 a.lo = 0; | 246 a.lo = 0; |
175 shift -= 32; | 247 shift -= 32; |
176 } | 248 } |
177 if (shift) | 249 if (shift) |
178 { | 250 { |
179 a.hi = a.hi << shift | a.lo >> (32 - shift); | 251 a.hi = a.hi << shift | a.lo >> (32 - shift); |
180 a.lo = a.lo << shift; | 252 a.lo = a.lo << shift; |
181 } | 253 } |
182 return a; | 254 return a; |
183 } | 255 } |
184 | 256 |
| 257 /** |
| 258 * uint64 logical shift right. |
| 259 * |
| 260 * \param a uint64 |
| 261 * \param shift bits to shift |
| 262 * \returns uint64 |
| 263 */ |
185 cairo_uint64_t | 264 cairo_uint64_t |
186 _cairo_uint64_rsl (cairo_uint64_t a, int shift) | 265 _cairo_uint64_rsl (cairo_uint64_t a, int shift) |
187 { | 266 { |
188 if (shift >= 32) | 267 if (shift >= 32) |
189 { | 268 { |
190 a.lo = a.hi; | 269 a.lo = a.hi; |
191 a.hi = 0; | 270 a.hi = 0; |
192 shift -= 32; | 271 shift -= 32; |
193 } | 272 } |
194 if (shift) | 273 if (shift) |
195 { | 274 { |
196 a.lo = a.lo >> shift | a.hi << (32 - shift); | 275 a.lo = a.lo >> shift | a.hi << (32 - shift); |
197 a.hi = a.hi >> shift; | 276 a.hi = a.hi >> shift; |
198 } | 277 } |
199 return a; | 278 return a; |
200 } | 279 } |
201 | 280 |
202 #define _cairo_uint32_rsa(a,n) ((uint32_t) (((int32_t) (a)) >> (n))) | 281 #define _cairo_uint32_rsa(a,n) ((uint32_t) (((int32_t) (a)) >> (n))) |
203 | 282 |
| 283 /** |
| 284 * uint64 arithmatic shift right. |
| 285 * |
| 286 * \param a uint64 |
| 287 * \param shift bits to shift |
| 288 * \returns uint64 |
| 289 */ |
204 cairo_int64_t | 290 cairo_int64_t |
205 _cairo_uint64_rsa (cairo_int64_t a, int shift) | 291 _cairo_uint64_rsa (cairo_int64_t a, int shift) |
206 { | 292 { |
207 if (shift >= 32) | 293 if (shift >= 32) |
208 { | 294 { |
209 a.lo = a.hi; | 295 a.lo = a.hi; |
210 a.hi = _cairo_uint32_rsa (a.hi, 31); | 296 a.hi = _cairo_uint32_rsa (a.hi, 31); |
211 shift -= 32; | 297 shift -= 32; |
212 } | 298 } |
213 if (shift) | 299 if (shift) |
214 { | 300 { |
215 a.lo = a.lo >> shift | a.hi << (32 - shift); | 301 a.lo = a.lo >> shift | a.hi << (32 - shift); |
216 a.hi = _cairo_uint32_rsa (a.hi, shift); | 302 a.hi = _cairo_uint32_rsa (a.hi, shift); |
217 } | 303 } |
218 return a; | 304 return a; |
219 } | 305 } |
220 | 306 |
| 307 /** |
| 308 * uint64 less than. |
| 309 * |
| 310 * \param a uint64 |
| 311 * \param b uint64 |
| 312 * \returns 1 if less than or 0 if not |
| 313 */ |
221 int | 314 int |
222 _cairo_uint64_lt (cairo_uint64_t a, cairo_uint64_t b) | 315 _cairo_uint64_lt (cairo_uint64_t a, cairo_uint64_t b) |
223 { | 316 { |
224 return (a.hi < b.hi || | 317 return (a.hi < b.hi || |
225 (a.hi == b.hi && a.lo < b.lo)); | 318 (a.hi == b.hi && a.lo < b.lo)); |
226 } | 319 } |
227 | 320 |
| 321 /** |
| 322 * uint64 equal. |
| 323 * |
| 324 * \param a uint64 |
| 325 * \param b uint64 |
| 326 * \returns 1 if equal or 0 if not |
| 327 */ |
228 int | 328 int |
229 _cairo_uint64_eq (cairo_uint64_t a, cairo_uint64_t b) | 329 _cairo_uint64_eq (cairo_uint64_t a, cairo_uint64_t b) |
230 { | 330 { |
231 return a.hi == b.hi && a.lo == b.lo; | 331 return a.hi == b.hi && a.lo == b.lo; |
232 } | 332 } |
233 | 333 |
| 334 /** |
| 335 * int64 less than. |
| 336 * |
| 337 * \param a int64 |
| 338 * \param b int64 |
| 339 * \returns 1 if less than or 0 if not |
| 340 */ |
234 int | 341 int |
235 _cairo_int64_lt (cairo_int64_t a, cairo_int64_t b) | 342 _cairo_int64_lt (cairo_int64_t a, cairo_int64_t b) |
236 { | 343 { |
237 if (_cairo_int64_negative (a) && !_cairo_int64_negative (b)) | 344 if (_cairo_int64_negative (a) && !_cairo_int64_negative (b)) |
238 return 1; | 345 return 1; |
239 if (!_cairo_int64_negative (a) && _cairo_int64_negative (b)) | 346 if (!_cairo_int64_negative (a) && _cairo_int64_negative (b)) |
240 return 0; | 347 return 0; |
241 return _cairo_uint64_lt (a, b); | 348 return _cairo_uint64_lt (a, b); |
242 } | 349 } |
243 | 350 |
| 351 /** |
| 352 * uint64 not. |
| 353 * |
| 354 * \param a uint64 |
| 355 * \returns uint64 |
| 356 */ |
244 cairo_uint64_t | 357 cairo_uint64_t |
245 _cairo_uint64_not (cairo_uint64_t a) | 358 _cairo_uint64_not (cairo_uint64_t a) |
246 { | 359 { |
247 a.lo = ~a.lo; | 360 a.lo = ~a.lo; |
248 a.hi = ~a.hi; | 361 a.hi = ~a.hi; |
249 return a; | 362 return a; |
250 } | 363 } |
251 | 364 |
| 365 /** |
| 366 * uint64 negate. |
| 367 * |
| 368 * \param a uint64 |
| 369 * \returns uint64 |
| 370 */ |
252 cairo_uint64_t | 371 cairo_uint64_t |
253 _cairo_uint64_negate (cairo_uint64_t a) | 372 _cairo_uint64_negate (cairo_uint64_t a) |
254 { | 373 { |
255 a.lo = ~a.lo; | 374 a.lo = ~a.lo; |
256 a.hi = ~a.hi; | 375 a.hi = ~a.hi; |
257 if (++a.lo == 0) | 376 if (++a.lo == 0) |
258 ++a.hi; | 377 ++a.hi; |
259 return a; | 378 return a; |
260 } | 379 } |
261 | 380 |
262 /* | 381 /** |
263 * Simple bit-at-a-time divide. | 382 * uint64 quotient remainder divide. |
| 383 * |
| 384 * \param num numerator |
| 385 * \param den denominator |
| 386 * \returns quotient remainder |
264 */ | 387 */ |
265 cairo_uquorem64_t | 388 cairo_uquorem64_t |
266 _cairo_uint64_divrem (cairo_uint64_t num, cairo_uint64_t den) | 389 _cairo_uint64_divrem (cairo_uint64_t num, cairo_uint64_t den) |
267 { | 390 { |
268 cairo_uquorem64_t qr; | 391 cairo_uquorem64_t qr; |
269 cairo_uint64_t bit; | 392 cairo_uint64_t bit; |
270 cairo_uint64_t quo; | 393 cairo_uint64_t quo; |
271 | 394 |
272 bit = _cairo_uint32_to_uint64 (1); | 395 bit = _cairo_uint32_to_uint64 (1); |
273 | 396 |
(...skipping 16 matching lines...) Expand all Loading... |
290 bit = _cairo_uint64_rsl (bit, 1); | 413 bit = _cairo_uint64_rsl (bit, 1); |
291 den = _cairo_uint64_rsl (den, 1); | 414 den = _cairo_uint64_rsl (den, 1); |
292 } | 415 } |
293 qr.quo = quo; | 416 qr.quo = quo; |
294 qr.rem = num; | 417 qr.rem = num; |
295 return qr; | 418 return qr; |
296 } | 419 } |
297 | 420 |
298 #endif /* !HAVE_UINT64_T */ | 421 #endif /* !HAVE_UINT64_T */ |
299 | 422 |
| 423 /** |
| 424 * int64 quotient remainder divide. |
| 425 * |
| 426 * \param num numerator |
| 427 * \param den denomerator |
| 428 * \returns 1 if less than or 0 if not |
| 429 */ |
300 cairo_quorem64_t | 430 cairo_quorem64_t |
301 _cairo_int64_divrem (cairo_int64_t num, cairo_int64_t den) | 431 _cairo_int64_divrem (cairo_int64_t num, cairo_int64_t den) |
302 { | 432 { |
303 int num_neg = _cairo_int64_negative (num); | 433 int num_neg = _cairo_int64_negative (num); |
304 int den_neg = _cairo_int64_negative (den); | 434 int den_neg = _cairo_int64_negative (den); |
305 cairo_uquorem64_t uqr; | 435 cairo_uquorem64_t uqr; |
306 cairo_quorem64_t qr; | 436 cairo_quorem64_t qr; |
307 | 437 |
308 if (num_neg) | 438 if (num_neg) |
309 num = _cairo_int64_negate (num); | 439 num = _cairo_int64_negate (num); |
310 if (den_neg) | 440 if (den_neg) |
311 den = _cairo_int64_negate (den); | 441 den = _cairo_int64_negate (den); |
312 uqr = _cairo_uint64_divrem (num, den); | 442 uqr = _cairo_uint64_divrem (num, den); |
313 if (num_neg) | 443 if (num_neg) |
314 qr.rem = _cairo_int64_negate (uqr.rem); | 444 qr.rem = _cairo_int64_negate (uqr.rem); |
315 else | 445 else |
316 qr.rem = uqr.rem; | 446 qr.rem = uqr.rem; |
317 if (num_neg != den_neg) | 447 if (num_neg != den_neg) |
318 qr.quo = (cairo_int64_t) _cairo_int64_negate (uqr.quo); | 448 qr.quo = (cairo_int64_t) _cairo_int64_negate (uqr.quo); |
319 else | 449 else |
320 qr.quo = (cairo_int64_t) uqr.quo; | 450 qr.quo = (cairo_int64_t) uqr.quo; |
321 return qr; | 451 return qr; |
322 } | 452 } |
323 | 453 |
324 #if HAVE_UINT128_T | 454 #if HAVE_UINT128_T |
325 | 455 |
326 const char * cairo_impl128 = "uint128_t"; | 456 const char * cairo_impl128 = "uint128_t"; |
327 | 457 |
| 458 /** |
| 459 * uint128 quotient remainder divide. |
| 460 * |
| 461 * \param num numerator |
| 462 * \param den denomerator |
| 463 * \returns quotient remainder |
| 464 */ |
328 cairo_uquorem128_t | 465 cairo_uquorem128_t |
329 _cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den) | 466 _cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den) |
330 { | 467 { |
331 cairo_uquorem128_t qr; | 468 cairo_uquorem128_t qr; |
332 | 469 |
333 qr.quo = num / den; | 470 qr.quo = num / den; |
334 qr.rem = num % den; | 471 qr.rem = num % den; |
335 return qr; | 472 return qr; |
336 } | 473 } |
337 | 474 |
338 #else | 475 #else |
339 | 476 |
340 const char * cairo_impl128 = "cairo_uint64_t"; | 477 const char * cairo_impl128 = "cairo_uint64_t"; ///< implementation name |
341 | 478 |
| 479 /** |
| 480 * uint32 to uint128 conversion. |
| 481 * |
| 482 * \param i uint32 |
| 483 * \returns uint128 |
| 484 */ |
342 cairo_uint128_t | 485 cairo_uint128_t |
343 _cairo_uint32_to_uint128 (uint32_t i) | 486 _cairo_uint32_to_uint128 (uint32_t i) |
344 { | 487 { |
345 cairo_uint128_t q; | 488 cairo_uint128_t q; |
346 | 489 |
347 q.lo = _cairo_uint32_to_uint64 (i); | 490 q.lo = _cairo_uint32_to_uint64 (i); |
348 q.hi = _cairo_uint32_to_uint64 (0); | 491 q.hi = _cairo_uint32_to_uint64 (0); |
349 return q; | 492 return q; |
350 } | 493 } |
351 | 494 |
| 495 /** |
| 496 * int32 to int128 conversion. |
| 497 * |
| 498 * \param i int32 |
| 499 * \returns int128 |
| 500 */ |
352 cairo_int128_t | 501 cairo_int128_t |
353 _cairo_int32_to_int128 (int32_t i) | 502 _cairo_int32_to_int128 (int32_t i) |
354 { | 503 { |
355 cairo_int128_t q; | 504 cairo_int128_t q; |
356 | 505 |
357 q.lo = _cairo_int32_to_int64 (i); | 506 q.lo = _cairo_int32_to_int64 (i); |
358 q.hi = _cairo_int32_to_int64 (i < 0 ? -1 : 0); | 507 q.hi = _cairo_int32_to_int64 (i < 0 ? -1 : 0); |
359 return q; | 508 return q; |
360 } | 509 } |
361 | 510 |
| 511 /** |
| 512 * uint64 to uint128 conversion. |
| 513 * |
| 514 * \param i uint64 |
| 515 * \returns uint128 |
| 516 */ |
362 cairo_uint128_t | 517 cairo_uint128_t |
363 _cairo_uint64_to_uint128 (cairo_uint64_t i) | 518 _cairo_uint64_to_uint128 (cairo_uint64_t i) |
364 { | 519 { |
365 cairo_uint128_t q; | 520 cairo_uint128_t q; |
366 | 521 |
367 q.lo = i; | 522 q.lo = i; |
368 q.hi = _cairo_uint32_to_uint64 (0); | 523 q.hi = _cairo_uint32_to_uint64 (0); |
369 return q; | 524 return q; |
370 } | 525 } |
371 | 526 |
| 527 /** |
| 528 * int64 to int128 conversion. |
| 529 * |
| 530 * \param i int64 |
| 531 * \returns int128 |
| 532 */ |
372 cairo_int128_t | 533 cairo_int128_t |
373 _cairo_int64_to_int128 (cairo_int64_t i) | 534 _cairo_int64_to_int128 (cairo_int64_t i) |
374 { | 535 { |
375 cairo_int128_t q; | 536 cairo_int128_t q; |
376 | 537 |
377 q.lo = i; | 538 q.lo = i; |
378 q.hi = _cairo_int32_to_int64 (_cairo_int64_negative(i) ? -1 : 0); | 539 q.hi = _cairo_int32_to_int64 (_cairo_int64_negative(i) ? -1 : 0); |
379 return q; | 540 return q; |
380 } | 541 } |
381 | 542 |
| 543 /** |
| 544 * uint128 addition. |
| 545 * |
| 546 * \param a uint128 |
| 547 * \param b uint128 |
| 548 * \returns uint128 |
| 549 */ |
382 cairo_uint128_t | 550 cairo_uint128_t |
383 _cairo_uint128_add (cairo_uint128_t a, cairo_uint128_t b) | 551 _cairo_uint128_add (cairo_uint128_t a, cairo_uint128_t b) |
384 { | 552 { |
385 cairo_uint128_t s; | 553 cairo_uint128_t s; |
386 | 554 |
387 s.hi = _cairo_uint64_add (a.hi, b.hi); | 555 s.hi = _cairo_uint64_add (a.hi, b.hi); |
388 s.lo = _cairo_uint64_add (a.lo, b.lo); | 556 s.lo = _cairo_uint64_add (a.lo, b.lo); |
389 if (_cairo_uint64_lt (s.lo, a.lo)) | 557 if (_cairo_uint64_lt (s.lo, a.lo)) |
390 s.hi = _cairo_uint64_add (s.hi, _cairo_uint32_to_uint64 (1)); | 558 s.hi = _cairo_uint64_add (s.hi, _cairo_uint32_to_uint64 (1)); |
391 return s; | 559 return s; |
392 } | 560 } |
393 | 561 |
| 562 /** |
| 563 * uint128 subtraction. |
| 564 * |
| 565 * \param a uint128 |
| 566 * \param b uint128 |
| 567 * \returns uint128 |
| 568 */ |
394 cairo_uint128_t | 569 cairo_uint128_t |
395 _cairo_uint128_sub (cairo_uint128_t a, cairo_uint128_t b) | 570 _cairo_uint128_sub (cairo_uint128_t a, cairo_uint128_t b) |
396 { | 571 { |
397 cairo_uint128_t s; | 572 cairo_uint128_t s; |
398 | 573 |
399 s.hi = _cairo_uint64_sub (a.hi, b.hi); | 574 s.hi = _cairo_uint64_sub (a.hi, b.hi); |
400 s.lo = _cairo_uint64_sub (a.lo, b.lo); | 575 s.lo = _cairo_uint64_sub (a.lo, b.lo); |
401 if (_cairo_uint64_gt (s.lo, a.lo)) | 576 if (_cairo_uint64_gt (s.lo, a.lo)) |
402 s.hi = _cairo_uint64_sub (s.hi, _cairo_uint32_to_uint64(1)); | 577 s.hi = _cairo_uint64_sub (s.hi, _cairo_uint32_to_uint64(1)); |
403 return s; | 578 return s; |
404 } | 579 } |
405 | 580 |
406 #if HAVE_UINT64_T | 581 #if HAVE_UINT64_T |
407 | 582 |
| 583 /// lo 32 bits of uint64 |
408 #define uint64_lo32(i) ((i) & 0xffffffff) | 584 #define uint64_lo32(i) ((i) & 0xffffffff) |
| 585 /// hi 32 bits of unit64 |
409 #define uint64_hi32(i) ((i) >> 32) | 586 #define uint64_hi32(i) ((i) >> 32) |
| 587 /// lo 32 bits of unit64 |
410 #define uint64_lo(i) ((i) & 0xffffffff) | 588 #define uint64_lo(i) ((i) & 0xffffffff) |
| 589 /// hi 32 bits of unit64 |
411 #define uint64_hi(i) ((i) >> 32) | 590 #define uint64_hi(i) ((i) >> 32) |
| 591 /// shift unit64 32 bits |
412 #define uint64_shift32(i) ((i) << 32) | 592 #define uint64_shift32(i) ((i) << 32) |
| 593 /// carry uint64 32 bits |
413 #define uint64_carry32 (((uint64_t) 1) << 32) | 594 #define uint64_carry32 (((uint64_t) 1) << 32) |
414 | 595 |
415 #else | 596 #else |
416 | 597 |
417 #define uint64_lo32(i) ((i).lo) | 598 #define uint64_lo32(i) ((i).lo) |
418 #define uint64_hi32(i) ((i).hi) | 599 #define uint64_hi32(i) ((i).hi) |
419 | 600 |
| 601 /** |
| 602 * uint64 lo 32 bits. |
| 603 * |
| 604 * \param i uint64 |
| 605 * \returns uint64 |
| 606 */ |
420 static cairo_uint64_t | 607 static cairo_uint64_t |
421 uint64_lo (cairo_uint64_t i) | 608 uint64_lo (cairo_uint64_t i) |
422 { | 609 { |
423 cairo_uint64_t s; | 610 cairo_uint64_t s; |
424 | 611 |
425 s.lo = i.lo; | 612 s.lo = i.lo; |
426 s.hi = 0; | 613 s.hi = 0; |
427 return s; | 614 return s; |
428 } | 615 } |
429 | 616 |
| 617 /** |
| 618 * uint64 hi 32 bits. |
| 619 * |
| 620 * \param i uint64 |
| 621 * \returns uint64 |
| 622 */ |
430 static cairo_uint64_t | 623 static cairo_uint64_t |
431 uint64_hi (cairo_uint64_t i) | 624 uint64_hi (cairo_uint64_t i) |
432 { | 625 { |
433 cairo_uint64_t s; | 626 cairo_uint64_t s; |
434 | 627 |
435 s.lo = i.hi; | 628 s.lo = i.hi; |
436 s.hi = 0; | 629 s.hi = 0; |
437 return s; | 630 return s; |
438 } | 631 } |
439 | 632 |
| 633 /** |
| 634 * uint64 shift 32 bits. |
| 635 * |
| 636 * \param i uint64 |
| 637 * \returns uint64 |
| 638 */ |
440 static cairo_uint64_t | 639 static cairo_uint64_t |
441 uint64_shift32 (cairo_uint64_t i) | 640 uint64_shift32 (cairo_uint64_t i) |
442 { | 641 { |
443 cairo_uint64_t s; | 642 cairo_uint64_t s; |
444 | 643 |
445 s.lo = 0; | 644 s.lo = 0; |
446 s.hi = i.lo; | 645 s.hi = i.lo; |
447 return s; | 646 return s; |
448 } | 647 } |
449 | 648 |
450 static const cairo_uint64_t uint64_carry32 = { 0, 1 }; | 649 static const cairo_uint64_t uint64_carry32 = { 0, 1 }; |
451 | 650 |
452 #endif | 651 #endif |
453 | 652 |
| 653 /** |
| 654 * uint64 x uint64 multiplication. |
| 655 * |
| 656 * \param a uint64 |
| 657 * \param b uint64 |
| 658 * \returns uint128 |
| 659 */ |
454 cairo_uint128_t | 660 cairo_uint128_t |
455 _cairo_uint64x64_128_mul (cairo_uint64_t a, cairo_uint64_t b) | 661 _cairo_uint64x64_128_mul (cairo_uint64_t a, cairo_uint64_t b) |
456 { | 662 { |
457 cairo_uint128_t s; | 663 cairo_uint128_t s; |
458 uint32_t ah, al, bh, bl; | 664 uint32_t ah, al, bh, bl; |
459 cairo_uint64_t r0, r1, r2, r3; | 665 cairo_uint64_t r0, r1, r2, r3; |
460 | 666 |
461 al = uint64_lo32 (a); | 667 al = uint64_lo32 (a); |
462 ah = uint64_hi32 (a); | 668 ah = uint64_hi32 (a); |
463 bl = uint64_lo32 (b); | 669 bl = uint64_lo32 (b); |
464 bh = uint64_hi32 (b); | 670 bh = uint64_hi32 (b); |
465 | 671 |
466 r0 = _cairo_uint32x32_64_mul (al, bl); | 672 r0 = _cairo_uint32x32_64_mul (al, bl); |
467 r1 = _cairo_uint32x32_64_mul (al, bh); | 673 r1 = _cairo_uint32x32_64_mul (al, bh); |
468 r2 = _cairo_uint32x32_64_mul (ah, bl); | 674 r2 = _cairo_uint32x32_64_mul (ah, bl); |
469 r3 = _cairo_uint32x32_64_mul (ah, bh); | 675 r3 = _cairo_uint32x32_64_mul (ah, bh); |
470 | 676 |
471 r1 = _cairo_uint64_add (r1, uint64_hi (r0)); /* no carry possible */ | 677 r1 = _cairo_uint64_add (r1, uint64_hi (r0)); /* no carry possible */ |
472 r1 = _cairo_uint64_add (r1, r2); /* but this can carry */ | 678 r1 = _cairo_uint64_add (r1, r2); /* but this can carry */ |
473 if (_cairo_uint64_lt (r1, r2)) /* check */ | 679 if (_cairo_uint64_lt (r1, r2)) /* check */ |
474 r3 = _cairo_uint64_add (r3, uint64_carry32); | 680 r3 = _cairo_uint64_add (r3, uint64_carry32); |
475 | 681 |
476 s.hi = _cairo_uint64_add (r3, uint64_hi(r1)); | 682 s.hi = _cairo_uint64_add (r3, uint64_hi(r1)); |
477 s.lo = _cairo_uint64_add (uint64_shift32 (r1), | 683 s.lo = _cairo_uint64_add (uint64_shift32 (r1), |
478 uint64_lo (r0)); | 684 uint64_lo (r0)); |
479 return s; | 685 return s; |
480 } | 686 } |
481 | 687 |
| 688 /** |
| 689 * int64 x int64 multiplication. |
| 690 * |
| 691 * \param a int64 |
| 692 * \param b int64 |
| 693 * \returns int128 |
| 694 */ |
482 cairo_int128_t | 695 cairo_int128_t |
483 _cairo_int64x64_128_mul (cairo_int64_t a, cairo_int64_t b) | 696 _cairo_int64x64_128_mul (cairo_int64_t a, cairo_int64_t b) |
484 { | 697 { |
485 cairo_int128_t s; | 698 cairo_int128_t s; |
486 s = _cairo_uint64x64_128_mul (_cairo_int64_to_uint64(a), | 699 s = _cairo_uint64x64_128_mul (_cairo_int64_to_uint64(a), |
487 _cairo_int64_to_uint64(b)); | 700 _cairo_int64_to_uint64(b)); |
488 if (_cairo_int64_negative (a)) | 701 if (_cairo_int64_negative (a)) |
489 s.hi = _cairo_uint64_sub (s.hi, | 702 s.hi = _cairo_uint64_sub (s.hi, |
490 _cairo_int64_to_uint64 (b)); | 703 _cairo_int64_to_uint64 (b)); |
491 if (_cairo_int64_negative (b)) | 704 if (_cairo_int64_negative (b)) |
492 s.hi = _cairo_uint64_sub (s.hi, | 705 s.hi = _cairo_uint64_sub (s.hi, |
493 _cairo_int64_to_uint64 (a)); | 706 _cairo_int64_to_uint64 (a)); |
494 return s; | 707 return s; |
495 } | 708 } |
496 | 709 |
| 710 /** |
| 711 * uint128 x uint128 multiplication. |
| 712 * |
| 713 * \param a uint128 |
| 714 * \param b uint128 |
| 715 * \returns uint128 |
| 716 */ |
497 cairo_uint128_t | 717 cairo_uint128_t |
498 _cairo_uint128_mul (cairo_uint128_t a, cairo_uint128_t b) | 718 _cairo_uint128_mul (cairo_uint128_t a, cairo_uint128_t b) |
499 { | 719 { |
500 cairo_uint128_t s; | 720 cairo_uint128_t s; |
501 | 721 |
502 s = _cairo_uint64x64_128_mul (a.lo, b.lo); | 722 s = _cairo_uint64x64_128_mul (a.lo, b.lo); |
503 s.hi = _cairo_uint64_add (s.hi, | 723 s.hi = _cairo_uint64_add (s.hi, |
504 _cairo_uint64_mul (a.lo, b.hi)); | 724 _cairo_uint64_mul (a.lo, b.hi)); |
505 s.hi = _cairo_uint64_add (s.hi, | 725 s.hi = _cairo_uint64_add (s.hi, |
506 _cairo_uint64_mul (a.hi, b.lo)); | 726 _cairo_uint64_mul (a.hi, b.lo)); |
507 return s; | 727 return s; |
508 } | 728 } |
509 | 729 |
| 730 /** |
| 731 * uint128 logical shift left. |
| 732 * |
| 733 * \param a uint128 |
| 734 * \param shift bits to shift |
| 735 * \returns uint128 |
| 736 */ |
510 cairo_uint128_t | 737 cairo_uint128_t |
511 _cairo_uint128_lsl (cairo_uint128_t a, int shift) | 738 _cairo_uint128_lsl (cairo_uint128_t a, int shift) |
512 { | 739 { |
513 if (shift >= 64) | 740 if (shift >= 64) |
514 { | 741 { |
515 a.hi = a.lo; | 742 a.hi = a.lo; |
516 a.lo = _cairo_uint32_to_uint64 (0); | 743 a.lo = _cairo_uint32_to_uint64 (0); |
517 shift -= 64; | 744 shift -= 64; |
518 } | 745 } |
519 if (shift) | 746 if (shift) |
520 { | 747 { |
521 a.hi = _cairo_uint64_add (_cairo_uint64_lsl (a.hi, shift), | 748 a.hi = _cairo_uint64_add (_cairo_uint64_lsl (a.hi, shift), |
522 _cairo_uint64_rsl (a.lo, (64 - shift))); | 749 _cairo_uint64_rsl (a.lo, (64 - shift))); |
523 a.lo = _cairo_uint64_lsl (a.lo, shift); | 750 a.lo = _cairo_uint64_lsl (a.lo, shift); |
524 } | 751 } |
525 return a; | 752 return a; |
526 } | 753 } |
527 | 754 |
| 755 /** |
| 756 * uint128 logical shift right. |
| 757 * |
| 758 * \param a uint128 |
| 759 * \param shift bits to shift |
| 760 * \returns uint128 |
| 761 */ |
528 cairo_uint128_t | 762 cairo_uint128_t |
529 _cairo_uint128_rsl (cairo_uint128_t a, int shift) | 763 _cairo_uint128_rsl (cairo_uint128_t a, int shift) |
530 { | 764 { |
531 if (shift >= 64) | 765 if (shift >= 64) |
532 { | 766 { |
533 a.lo = a.hi; | 767 a.lo = a.hi; |
534 a.hi = _cairo_uint32_to_uint64 (0); | 768 a.hi = _cairo_uint32_to_uint64 (0); |
535 shift -= 64; | 769 shift -= 64; |
536 } | 770 } |
537 if (shift) | 771 if (shift) |
538 { | 772 { |
539 a.lo = _cairo_uint64_add (_cairo_uint64_rsl (a.lo, shift), | 773 a.lo = _cairo_uint64_add (_cairo_uint64_rsl (a.lo, shift), |
540 _cairo_uint64_lsl (a.hi, (64 - shift))); | 774 _cairo_uint64_lsl (a.hi, (64 - shift))); |
541 a.hi = _cairo_uint64_rsl (a.hi, shift); | 775 a.hi = _cairo_uint64_rsl (a.hi, shift); |
542 } | 776 } |
543 return a; | 777 return a; |
544 } | 778 } |
545 | 779 |
| 780 /** |
| 781 * uint128 arithmetic shift right. |
| 782 * |
| 783 * \param a uint128 |
| 784 * \param shift bits to shift |
| 785 * \returns uint128 |
| 786 */ |
546 cairo_uint128_t | 787 cairo_uint128_t |
547 _cairo_uint128_rsa (cairo_int128_t a, int shift) | 788 _cairo_uint128_rsa (cairo_int128_t a, int shift) |
548 { | 789 { |
549 if (shift >= 64) | 790 if (shift >= 64) |
550 { | 791 { |
551 a.lo = a.hi; | 792 a.lo = a.hi; |
552 a.hi = _cairo_uint64_rsa (a.hi, 64-1); | 793 a.hi = _cairo_uint64_rsa (a.hi, 64-1); |
553 shift -= 64; | 794 shift -= 64; |
554 } | 795 } |
555 if (shift) | 796 if (shift) |
556 { | 797 { |
557 a.lo = _cairo_uint64_add (_cairo_uint64_rsl (a.lo, shift), | 798 a.lo = _cairo_uint64_add (_cairo_uint64_rsl (a.lo, shift), |
558 _cairo_uint64_lsl (a.hi, (64 - shift))); | 799 _cairo_uint64_lsl (a.hi, (64 - shift))); |
559 a.hi = _cairo_uint64_rsa (a.hi, shift); | 800 a.hi = _cairo_uint64_rsa (a.hi, shift); |
560 } | 801 } |
561 return a; | 802 return a; |
562 } | 803 } |
563 | 804 |
| 805 /** |
| 806 * uint128 less than. |
| 807 * |
| 808 * \param a uint128 |
| 809 * \param b uint128 |
| 810 * \returns 1 if less than or 0 if not |
| 811 */ |
564 int | 812 int |
565 _cairo_uint128_lt (cairo_uint128_t a, cairo_uint128_t b) | 813 _cairo_uint128_lt (cairo_uint128_t a, cairo_uint128_t b) |
566 { | 814 { |
567 return (_cairo_uint64_lt (a.hi, b.hi) || | 815 return (_cairo_uint64_lt (a.hi, b.hi) || |
568 (_cairo_uint64_eq (a.hi, b.hi) && | 816 (_cairo_uint64_eq (a.hi, b.hi) && |
569 _cairo_uint64_lt (a.lo, b.lo))); | 817 _cairo_uint64_lt (a.lo, b.lo))); |
570 } | 818 } |
571 | 819 |
| 820 /** |
| 821 * int128 less than. |
| 822 * |
| 823 * \param a int128 |
| 824 * \param b int128 |
| 825 * \returns 1 if less than or 0 if not |
| 826 */ |
572 int | 827 int |
573 _cairo_int128_lt (cairo_int128_t a, cairo_int128_t b) | 828 _cairo_int128_lt (cairo_int128_t a, cairo_int128_t b) |
574 { | 829 { |
575 if (_cairo_int128_negative (a) && !_cairo_int128_negative (b)) | 830 if (_cairo_int128_negative (a) && !_cairo_int128_negative (b)) |
576 return 1; | 831 return 1; |
577 if (!_cairo_int128_negative (a) && _cairo_int128_negative (b)) | 832 if (!_cairo_int128_negative (a) && _cairo_int128_negative (b)) |
578 return 0; | 833 return 0; |
579 return _cairo_uint128_lt (a, b); | 834 return _cairo_uint128_lt (a, b); |
580 } | 835 } |
581 | 836 |
| 837 /** |
| 838 * uint128 equal. |
| 839 * |
| 840 * \param a uint128 |
| 841 * \param b uint128 |
| 842 * \returns 1 if less than or 0 if not |
| 843 */ |
582 int | 844 int |
583 _cairo_uint128_eq (cairo_uint128_t a, cairo_uint128_t b) | 845 _cairo_uint128_eq (cairo_uint128_t a, cairo_uint128_t b) |
584 { | 846 { |
585 return (_cairo_uint64_eq (a.hi, b.hi) && | 847 return (_cairo_uint64_eq (a.hi, b.hi) && |
586 _cairo_uint64_eq (a.lo, b.lo)); | 848 _cairo_uint64_eq (a.lo, b.lo)); |
587 } | 849 } |
588 | 850 |
589 #if HAVE_UINT64_T | 851 #if HAVE_UINT64_T |
| 852 /// set MSB |
590 #define _cairo_msbset64(q) (q & ((uint64_t) 1 << 63)) | 853 #define _cairo_msbset64(q) (q & ((uint64_t) 1 << 63)) |
591 #else | 854 #else |
| 855 /// set MSB |
592 #define _cairo_msbset64(q) (q.hi & ((uint32_t) 1 << 31)) | 856 #define _cairo_msbset64(q) (q.hi & ((uint32_t) 1 << 31)) |
593 #endif | 857 #endif |
594 | 858 |
| 859 /** |
| 860 * uint128 bit-at-a-time quotient remainder divide. |
| 861 * |
| 862 * \param num numerator |
| 863 * \param den denominator |
| 864 * \returns 1 if less than or 0 if not |
| 865 */ |
595 cairo_uquorem128_t | 866 cairo_uquorem128_t |
596 _cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den) | 867 _cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den) |
597 { | 868 { |
598 cairo_uquorem128_t qr; | 869 cairo_uquorem128_t qr; |
599 cairo_uint128_t bit; | 870 cairo_uint128_t bit; |
600 cairo_uint128_t quo; | 871 cairo_uint128_t quo; |
601 | 872 |
602 bit = _cairo_uint32_to_uint128 (1); | 873 bit = _cairo_uint32_to_uint128 (1); |
603 | 874 |
604 /* normalize to make den >= num, but not overflow */ | 875 /* normalize to make den >= num, but not overflow */ |
(...skipping 13 matching lines...) Expand all Loading... |
618 quo = _cairo_uint128_add (quo, bit); | 889 quo = _cairo_uint128_add (quo, bit); |
619 } | 890 } |
620 bit = _cairo_uint128_rsl (bit, 1); | 891 bit = _cairo_uint128_rsl (bit, 1); |
621 den = _cairo_uint128_rsl (den, 1); | 892 den = _cairo_uint128_rsl (den, 1); |
622 } | 893 } |
623 qr.quo = quo; | 894 qr.quo = quo; |
624 qr.rem = num; | 895 qr.rem = num; |
625 return qr; | 896 return qr; |
626 } | 897 } |
627 | 898 |
| 899 /** |
| 900 * uint128 negate. |
| 901 * |
| 902 * \param a uint128 |
| 903 * \returns uint128 |
| 904 */ |
628 cairo_uint128_t | 905 cairo_uint128_t |
629 _cairo_uint128_negate (cairo_uint128_t a) | 906 _cairo_uint128_negate (cairo_uint128_t a) |
630 { | 907 { |
631 a.lo = _cairo_uint64_not (a.lo); | 908 a.lo = _cairo_uint64_not (a.lo); |
632 a.hi = _cairo_uint64_not (a.hi); | 909 a.hi = _cairo_uint64_not (a.hi); |
633 return _cairo_uint128_add (a, _cairo_uint32_to_uint128 (1)); | 910 return _cairo_uint128_add (a, _cairo_uint32_to_uint128 (1)); |
634 } | 911 } |
635 | 912 |
| 913 /** |
| 914 * uint128 not. |
| 915 * |
| 916 * \param a uint128 |
| 917 * \returns uint128 |
| 918 */ |
636 cairo_uint128_t | 919 cairo_uint128_t |
637 _cairo_uint128_not (cairo_uint128_t a) | 920 _cairo_uint128_not (cairo_uint128_t a) |
638 { | 921 { |
639 a.lo = _cairo_uint64_not (a.lo); | 922 a.lo = _cairo_uint64_not (a.lo); |
640 a.hi = _cairo_uint64_not (a.hi); | 923 a.hi = _cairo_uint64_not (a.hi); |
641 return a; | 924 return a; |
642 } | 925 } |
643 | 926 |
644 #endif /* !HAVE_UINT128_T */ | 927 #endif /* !HAVE_UINT128_T */ |
645 | 928 |
| 929 /** |
| 930 * int128 quotient remainder divide. |
| 931 * |
| 932 * \param num int128 |
| 933 * \param den int128 |
| 934 * \returns quotient remainder |
| 935 */ |
646 cairo_quorem128_t | 936 cairo_quorem128_t |
647 _cairo_int128_divrem (cairo_int128_t num, cairo_int128_t den) | 937 _cairo_int128_divrem (cairo_int128_t num, cairo_int128_t den) |
648 { | 938 { |
649 int num_neg = _cairo_int128_negative (num); | 939 int num_neg = _cairo_int128_negative (num); |
650 int den_neg = _cairo_int128_negative (den); | 940 int den_neg = _cairo_int128_negative (den); |
651 cairo_uquorem128_t uqr; | 941 cairo_uquorem128_t uqr; |
652 cairo_quorem128_t qr; | 942 cairo_quorem128_t qr; |
653 | 943 |
654 if (num_neg) | 944 if (num_neg) |
655 num = _cairo_int128_negate (num); | 945 num = _cairo_int128_negate (num); |
(...skipping 12 matching lines...) Expand all Loading... |
668 } | 958 } |
669 | 959 |
670 /** | 960 /** |
671 * _cairo_uint_96by64_32x64_divrem: | 961 * _cairo_uint_96by64_32x64_divrem: |
672 * | 962 * |
673 * Compute a 32 bit quotient and 64 bit remainder of a 96 bit unsigned | 963 * Compute a 32 bit quotient and 64 bit remainder of a 96 bit unsigned |
674 * dividend and 64 bit divisor. If the quotient doesn't fit into 32 | 964 * dividend and 64 bit divisor. If the quotient doesn't fit into 32 |
675 * bits then the returned remainder is equal to the divisor, and the | 965 * bits then the returned remainder is equal to the divisor, and the |
676 * quotient is the largest representable 64 bit integer. It is an | 966 * quotient is the largest representable 64 bit integer. It is an |
677 * error to call this function with the high 32 bits of `num' being | 967 * error to call this function with the high 32 bits of `num' being |
678 * non-zero. */ | 968 * non-zero. |
| 969 * |
| 970 * \param num uint128 |
| 971 * \param den uint164 |
| 972 * \returns quotient remainder |
| 973 */ |
679 cairo_uquorem64_t | 974 cairo_uquorem64_t |
680 _cairo_uint_96by64_32x64_divrem (cairo_uint128_t num, | 975 _cairo_uint_96by64_32x64_divrem (cairo_uint128_t num, |
681 cairo_uint64_t den) | 976 cairo_uint64_t den) |
682 { | 977 { |
683 cairo_uquorem64_t result; | 978 cairo_uquorem64_t result; |
684 cairo_uint64_t B = _cairo_uint32s_to_uint64 (1, 0); | 979 cairo_uint64_t B = _cairo_uint32s_to_uint64 (1, 0); |
685 | 980 |
686 /* These are the high 64 bits of the *96* bit numerator. We're | 981 /* These are the high 64 bits of the *96* bit numerator. We're |
687 * going to represent the numerator as xB + y, where x is a 64, | 982 * going to represent the numerator as xB + y, where x is a 64, |
688 * and y is a 32 bit number. */ | 983 * and y is a 32 bit number. */ |
(...skipping 90 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
779 remainder = _cairo_uint64_sub (remainder, den); | 1074 remainder = _cairo_uint64_sub (remainder, den); |
780 quotient++; | 1075 quotient++; |
781 } | 1076 } |
782 | 1077 |
783 result.quo = _cairo_uint32_to_uint64 (quotient); | 1078 result.quo = _cairo_uint32_to_uint64 (quotient); |
784 result.rem = remainder; | 1079 result.rem = remainder; |
785 } | 1080 } |
786 return result; | 1081 return result; |
787 } | 1082 } |
788 | 1083 |
| 1084 /** |
| 1085 * _cairo_int_96by64_32x64_divrem: |
| 1086 * |
| 1087 * Compute a 32 bit quotient and 64 bit remainder of a 96 bit unsigned |
| 1088 * dividend and 64 bit divisor. If the quotient doesn't fit into 32 |
| 1089 * bits then the returned remainder is equal to the divisor, and the |
| 1090 * quotient is the largest representable 64 bit integer. It is an |
| 1091 * error to call this function with the high 32 bits of `num' being |
| 1092 * non-zero.· |
| 1093 * |
| 1094 * \param num int128 |
| 1095 * \param den int64 |
| 1096 * \returns quotient remainder |
| 1097 */ |
789 cairo_quorem64_t | 1098 cairo_quorem64_t |
790 _cairo_int_96by64_32x64_divrem (cairo_int128_t num, cairo_int64_t den) | 1099 _cairo_int_96by64_32x64_divrem (cairo_int128_t num, cairo_int64_t den) |
791 { | 1100 { |
792 int num_neg = _cairo_int128_negative (num); | 1101 int num_neg = _cairo_int128_negative (num); |
793 int den_neg = _cairo_int64_negative (den); | 1102 int den_neg = _cairo_int64_negative (den); |
794 cairo_uint64_t nonneg_den; | 1103 cairo_uint64_t nonneg_den; |
795 cairo_uquorem64_t uqr; | 1104 cairo_uquorem64_t uqr; |
796 cairo_quorem64_t qr; | 1105 cairo_quorem64_t qr; |
797 | 1106 |
798 if (num_neg) | 1107 if (num_neg) |
(...skipping 14 matching lines...) Expand all Loading... |
813 if (num_neg) | 1122 if (num_neg) |
814 qr.rem = _cairo_int64_negate (uqr.rem); | 1123 qr.rem = _cairo_int64_negate (uqr.rem); |
815 else | 1124 else |
816 qr.rem = uqr.rem; | 1125 qr.rem = uqr.rem; |
817 if (num_neg != den_neg) | 1126 if (num_neg != den_neg) |
818 qr.quo = _cairo_int64_negate (uqr.quo); | 1127 qr.quo = _cairo_int64_negate (uqr.quo); |
819 else | 1128 else |
820 qr.quo = uqr.quo; | 1129 qr.quo = uqr.quo; |
821 return qr; | 1130 return qr; |
822 } | 1131 } |
OLD | NEW |