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