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  
 34  static __inline uint64_t
 35  multi_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  
 44  typedef struct {
 45  	uint64_t high;
 46  	uint64_t low;
 47  } uint128_data_t;
 48  
 49  /* 128-bit addition: acc += add */
 50  static __inline void
 51  add128_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 */
 61  static __inline void
 62  mul64x64(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  
 94  static __inline uint64_t
 95  multi_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_ */