1*2c2f96dcSApple OSS Distributions /*
2*2c2f96dcSApple OSS Distributions * Copyright (c) 1999, 2003, 2006, 2007, 2010 Apple Inc. All rights reserved.
3*2c2f96dcSApple OSS Distributions *
4*2c2f96dcSApple OSS Distributions * @APPLE_LICENSE_HEADER_START@
5*2c2f96dcSApple OSS Distributions *
6*2c2f96dcSApple OSS Distributions * This file contains Original Code and/or Modifications of Original Code
7*2c2f96dcSApple OSS Distributions * as defined in and that are subject to the Apple Public Source License
8*2c2f96dcSApple OSS Distributions * Version 2.0 (the 'License'). You may not use this file except in
9*2c2f96dcSApple OSS Distributions * compliance with the License. Please obtain a copy of the License at
10*2c2f96dcSApple OSS Distributions * http://www.opensource.apple.com/apsl/ and read it before using this
11*2c2f96dcSApple OSS Distributions * file.
12*2c2f96dcSApple OSS Distributions *
13*2c2f96dcSApple OSS Distributions * The Original Code and all software distributed under the License are
14*2c2f96dcSApple OSS Distributions * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15*2c2f96dcSApple OSS Distributions * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16*2c2f96dcSApple OSS Distributions * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17*2c2f96dcSApple OSS Distributions * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18*2c2f96dcSApple OSS Distributions * Please see the License for the specific language governing rights and
19*2c2f96dcSApple OSS Distributions * limitations under the License.
20*2c2f96dcSApple OSS Distributions *
21*2c2f96dcSApple OSS Distributions * @APPLE_LICENSE_HEADER_END@
22*2c2f96dcSApple OSS Distributions */
23*2c2f96dcSApple OSS Distributions /*
24*2c2f96dcSApple OSS Distributions * Code duplicated from Libc/gen/nanosleep.c
25*2c2f96dcSApple OSS Distributions */
26*2c2f96dcSApple OSS Distributions
27*2c2f96dcSApple OSS Distributions #ifndef _ARITHMETIC_128_H_
28*2c2f96dcSApple OSS Distributions #define _ARITHMETIC_128_H_
29*2c2f96dcSApple OSS Distributions
30*2c2f96dcSApple OSS Distributions #include <stdint.h>
31*2c2f96dcSApple OSS Distributions
32*2c2f96dcSApple OSS Distributions #if __LP64__
33*2c2f96dcSApple OSS Distributions
34*2c2f96dcSApple OSS Distributions static __inline uint64_t
multi_overflow(uint64_t a,uint64_t b)35*2c2f96dcSApple OSS Distributions multi_overflow(uint64_t a, uint64_t b)
36*2c2f96dcSApple OSS Distributions {
37*2c2f96dcSApple OSS Distributions __uint128_t prod;
38*2c2f96dcSApple OSS Distributions prod = (__uint128_t)a * (__uint128_t)b;
39*2c2f96dcSApple OSS Distributions return (uint64_t) (prod >> 64);
40*2c2f96dcSApple OSS Distributions }
41*2c2f96dcSApple OSS Distributions
42*2c2f96dcSApple OSS Distributions #else
43*2c2f96dcSApple OSS Distributions
44*2c2f96dcSApple OSS Distributions typedef struct {
45*2c2f96dcSApple OSS Distributions uint64_t high;
46*2c2f96dcSApple OSS Distributions uint64_t low;
47*2c2f96dcSApple OSS Distributions } uint128_data_t;
48*2c2f96dcSApple OSS Distributions
49*2c2f96dcSApple OSS Distributions /* 128-bit addition: acc += add */
50*2c2f96dcSApple OSS Distributions static __inline void
add128_128(uint128_data_t * acc,uint128_data_t * add)51*2c2f96dcSApple OSS Distributions add128_128(uint128_data_t *acc, uint128_data_t *add)
52*2c2f96dcSApple OSS Distributions {
53*2c2f96dcSApple OSS Distributions acc->high += add->high;
54*2c2f96dcSApple OSS Distributions acc->low += add->low;
55*2c2f96dcSApple OSS Distributions if (acc->low < add->low) {
56*2c2f96dcSApple OSS Distributions acc->high++; // carry
57*2c2f96dcSApple OSS Distributions }
58*2c2f96dcSApple OSS Distributions }
59*2c2f96dcSApple OSS Distributions
60*2c2f96dcSApple OSS Distributions /* 64x64 -> 128 bit multiplication */
61*2c2f96dcSApple OSS Distributions static __inline void
mul64x64(uint64_t x,uint64_t y,uint128_data_t * prod)62*2c2f96dcSApple OSS Distributions mul64x64(uint64_t x, uint64_t y, uint128_data_t *prod)
63*2c2f96dcSApple OSS Distributions {
64*2c2f96dcSApple OSS Distributions uint128_data_t add;
65*2c2f96dcSApple OSS Distributions /*
66*2c2f96dcSApple OSS Distributions * Split the two 64-bit multiplicands into 32-bit parts:
67*2c2f96dcSApple OSS Distributions * x => 2^32 * x1 + x2
68*2c2f96dcSApple OSS Distributions * y => 2^32 * y1 + y2
69*2c2f96dcSApple OSS Distributions */
70*2c2f96dcSApple OSS Distributions uint32_t x1 = (uint32_t)(x >> 32);
71*2c2f96dcSApple OSS Distributions uint32_t x2 = (uint32_t)x;
72*2c2f96dcSApple OSS Distributions uint32_t y1 = (uint32_t)(y >> 32);
73*2c2f96dcSApple OSS Distributions uint32_t y2 = (uint32_t)y;
74*2c2f96dcSApple OSS Distributions /*
75*2c2f96dcSApple OSS Distributions * direct multiplication:
76*2c2f96dcSApple OSS Distributions * x * y => 2^64 * (x1 * y1) + 2^32 (x1 * y2 + x2 * y1) + (x2 * y2)
77*2c2f96dcSApple OSS Distributions * The first and last terms are direct assignmenet into the uint128_t
78*2c2f96dcSApple OSS Distributions * structure. Then we add the middle two terms separately, to avoid
79*2c2f96dcSApple OSS Distributions * 64-bit overflow. (We could use the Karatsuba algorithm to save
80*2c2f96dcSApple OSS Distributions * one multiply, but it is harder to deal with 64-bit overflows.)
81*2c2f96dcSApple OSS Distributions */
82*2c2f96dcSApple OSS Distributions prod->high = (uint64_t)x1 * (uint64_t)y1;
83*2c2f96dcSApple OSS Distributions prod->low = (uint64_t)x2 * (uint64_t)y2;
84*2c2f96dcSApple OSS Distributions add.low = (uint64_t)x1 * (uint64_t)y2;
85*2c2f96dcSApple OSS Distributions add.high = (add.low >> 32);
86*2c2f96dcSApple OSS Distributions add.low <<= 32;
87*2c2f96dcSApple OSS Distributions add128_128(prod, &add);
88*2c2f96dcSApple OSS Distributions add.low = (uint64_t)x2 * (uint64_t)y1;
89*2c2f96dcSApple OSS Distributions add.high = (add.low >> 32);
90*2c2f96dcSApple OSS Distributions add.low <<= 32;
91*2c2f96dcSApple OSS Distributions add128_128(prod, &add);
92*2c2f96dcSApple OSS Distributions }
93*2c2f96dcSApple OSS Distributions
94*2c2f96dcSApple OSS Distributions static __inline uint64_t
multi_overflow(uint64_t a,uint64_t b)95*2c2f96dcSApple OSS Distributions multi_overflow(uint64_t a, uint64_t b)
96*2c2f96dcSApple OSS Distributions {
97*2c2f96dcSApple OSS Distributions uint128_data_t prod;
98*2c2f96dcSApple OSS Distributions mul64x64(a, b, &prod);
99*2c2f96dcSApple OSS Distributions return prod.high;
100*2c2f96dcSApple OSS Distributions }
101*2c2f96dcSApple OSS Distributions
102*2c2f96dcSApple OSS Distributions #endif /* __LP64__ */
103*2c2f96dcSApple OSS Distributions #endif /* _ARITHMETIC_128_H_ */
104