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
60/* 64x64 -> 128 bit multiplication */
61static __inline void
62mul64x64(uint64_t x, uint64_t y, uint128_data_t *prod)
63{
64 uint128_data_t add;
65 /*
66 * Split the two 64-bit multiplicands into 32-bit parts:
67 * x => 2^32 * x1 + x2
68 * y => 2^32 * y1 + y2
69 */
70 uint32_t x1 = (uint32_t)(x >> 32);
71 uint32_t x2 = (uint32_t)x;
72 uint32_t y1 = (uint32_t)(y >> 32);
73 uint32_t y2 = (uint32_t)y;
74 /*
75 * direct multiplication:
76 * x * y => 2^64 * (x1 * y1) + 2^32 (x1 * y2 + x2 * y1) + (x2 * y2)
77 * The first and last terms are direct assignmenet into the uint128_t
78 * structure. Then we add the middle two terms separately, to avoid
79 * 64-bit overflow. (We could use the Karatsuba algorithm to save
80 * one multiply, but it is harder to deal with 64-bit overflows.)
81 */
82 prod->high = (uint64_t)x1 * (uint64_t)y1;
83 prod->low = (uint64_t)x2 * (uint64_t)y2;
84 add.low = (uint64_t)x1 * (uint64_t)y2;
85 add.high = (add.low >> 32);
86 add.low <<= 32;
87 add128_128(prod, &add);
88 add.low = (uint64_t)x2 * (uint64_t)y1;
89 add.high = (add.low >> 32);
90 add.low <<= 32;
91 add128_128(prod, &add);
92}
93
94static __inline uint64_t
95multi_overflow(uint64_t a, uint64_t b)
96{
97 uint128_data_t prod;
98 mul64x64(a, b, &prod);
99 return prod.high;
100}
101
102#endif /* __LP64__ */
103#endif /* _ARITHMETIC_128_H_ */
104