CoreFoundation/NumberDate.subproj/CFBigNumber.c - third_party/swift-corelibs-foundation - Git at Google

 /*	CFBigNumber.c
 	Copyright (c) 2012-2016, Apple Inc. and the Swift project authors

 	Portions Copyright (c) 2014-2016 Apple Inc. and the Swift project authors
 	Licensed under Apache License v2.0 with Runtime Library Exception
 	See http://swift.org/LICENSE.txt for license information
 	See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 	Responsibility: Christopher Kane
 	Original author: Zhi Feng Huang
 */

 #include <CoreFoundation/CFBigNumber.h>
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
 #include "CFInternal.h"


 typedef struct {
     int64_t high;
     uint64_t low;
 } CFSInt128Struct;

 #define kCFNumberSInt128Type 17

 CF_EXPORT CFNumberType _CFNumberGetType2(CFNumberRef number);

 #if __LP64__

 #ifndef _INT128_T
 #define _INT128_T
 typedef __int128_t  int128_t;
 #endif

 #ifndef _UINT128_T
 #define _UINT128_T
 typedef __uint128_t uint128_t;
 #endif

 #ifndef INT128_MIN
 #define INT128_MIN  ((__int128_t)0 - ((__int128_t)1 << 126) - ((__int128_t)1 << 126))
 #endif

 #ifndef INT128_MAX
 #define INT128_MAX  ((__int128_t)-1 + ((__int128_t)1 << 126) + ((__int128_t)1 << 126))
 #endif

 #ifndef UINT128_MAX
 #define UINT128_MAX (((__uint128_t)1 << 127) - (__uint128_t)1 + ((__uint128_t)1 << 127))
 #endif

 #endif


 #define BIG_DIGITS_LIMIT    1000000000L
 #define BIG_DIGITS_LIMIT_2  ((uint64_t)BIG_DIGITS_LIMIT * (uint64_t)BIG_DIGITS_LIMIT)
 #define BIG_DIGITS_LIMIT_3  ((__uint128_t)BIG_DIGITS_LIMIT_2 * (__uint128_t)BIG_DIGITS_LIMIT)
 #define BIG_DIGITS_LIMIT_4  ((__uint128_t)BIG_DIGITS_LIMIT_3 * (__uint128_t)BIG_DIGITS_LIMIT)

 #define GET_FIFTH_DIGIT(A)  (A / BIG_DIGITS_LIMIT_4)
 #define GET_FOURTH_DIGIT(A) (A / BIG_DIGITS_LIMIT_3)
 #define GET_THIRD_DIGIT(A)  (A / BIG_DIGITS_LIMIT_2)
 #define GET_SECOND_DIGIT(A) (A / BIG_DIGITS_LIMIT)

 #define GET_REMAINDER_FIFTH_DIGIT(A,B)  (A - B * BIG_DIGITS_LIMIT_4)
 #define GET_REMAINDER_FOURTH_DIGIT(A,B) (A - B * BIG_DIGITS_LIMIT_3)
 #define GET_REMAINDER_THIRD_DIGIT(A,B)  (A - B * BIG_DIGITS_LIMIT_2)
 #define GET_REMAINDER_SECOND_DIGIT(A,B) (A - B * BIG_DIGITS_LIMIT)


 void _CFBigNumInitWithInt8(_CFBigNum *r, int8_t inNum) {
     memset(r, 0, sizeof(*r));
     uint8_t unsignInNum = inNum;
     if (inNum < 0) {
         r->sign = -1;
         unsignInNum = -1 * inNum;
     }
     r->digits[0] = unsignInNum;
 }

 void _CFBigNumInitWithInt16(_CFBigNum *r, int16_t inNum) {
     memset(r, 0, sizeof(*r));
     uint16_t unsignInNum = inNum;
     if (inNum < 0) {
         r->sign = -1;
         unsignInNum = -1 * inNum;
     }
     r->digits[0] = unsignInNum;
 }

 void _CFBigNumInitWithInt32(_CFBigNum *r, int32_t inNum) {
     memset(r, 0, sizeof(*r));
     uint32_t unsignInNum = inNum;
     if (inNum < 0) {
         r->sign = -1;
         unsignInNum = -1 * inNum;
     }
     uint32_t dig0 = GET_SECOND_DIGIT(unsignInNum);
     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, dig0);
     r->digits[1] = dig0;
 }

 void _CFBigNumInitWithInt64(_CFBigNum *r, int64_t inNum) {
     memset(r, 0, sizeof(*r));
     uint64_t unsignInNum = inNum;
     if (inNum < 0) {
         r->sign = -1;
         unsignInNum = -1 * inNum;
     }
     uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
     unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (uint64_t)dig2);
     uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (uint64_t)dig1);
     r->digits[1] = dig1;
     r->digits[2] = dig2;
 }

 #ifdef __LP64__
 void _CFBigNumInitWithInt128(_CFBigNum *r, __int128_t inNum) {
     memset(r, 0, sizeof(*r));
     __uint128_t unsignInNum = inNum;
     if (inNum < 0) {
         r->sign = -1;
         unsignInNum = -1 * inNum;
     }
     uint32_t dig4 = GET_FIFTH_DIGIT(unsignInNum);
     unsignInNum = GET_REMAINDER_FIFTH_DIGIT(unsignInNum, (__uint128_t)dig4);
     uint32_t dig3 = GET_FOURTH_DIGIT(unsignInNum);
     unsignInNum = GET_REMAINDER_FOURTH_DIGIT(unsignInNum, (__uint128_t)dig3);
     uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
     unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (__uint128_t)dig2);
     uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (__uint128_t)dig1);
     r->digits[1] = dig1;
     r->digits[2] = dig2;
     r->digits[3] = dig3;
     r->digits[4] = dig4;
 }
 #endif

 void _CFBigNumInitWithUInt8(_CFBigNum *r, uint8_t inNum) {
     memset(r, 0, sizeof(*r));
     uint8_t unsignInNum = inNum;
     r->digits[0] = unsignInNum;
 }

 void _CFBigNumInitWithUInt16(_CFBigNum *r, uint16_t inNum) {
     memset(r, 0, sizeof(*r));
     uint16_t unsignInNum = inNum;
     r->digits[0] = unsignInNum;
 }

 void _CFBigNumInitWithUInt32(_CFBigNum *r, uint32_t inNum) {
     memset(r, 0, sizeof(*r));
     uint32_t unsignInNum = inNum;
     uint32_t dig0 = GET_SECOND_DIGIT(unsignInNum);
     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, dig0);
     r->digits[1] = dig0;
 }

 void _CFBigNumInitWithUInt64(_CFBigNum *r, uint64_t inNum) {
     memset(r, 0, sizeof(*r));
     uint64_t unsignInNum = inNum;
     uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
     unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (uint64_t)dig2);
     uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (uint64_t)dig1);
     r->digits[1] = dig1;
     r->digits[2] = dig2;
 }

 #ifdef __LP64__
 void _CFBigNumInitWithUInt128(_CFBigNum *r, __uint128_t inNum) {
     memset(r, 0, sizeof(*r));
     __uint128_t unsignInNum = inNum;
     uint32_t dig4 = GET_FIFTH_DIGIT(unsignInNum);
     unsignInNum = GET_REMAINDER_FIFTH_DIGIT(unsignInNum, (__uint128_t)dig4);
     uint32_t dig3 = GET_FOURTH_DIGIT(unsignInNum);
     unsignInNum = GET_REMAINDER_FOURTH_DIGIT(unsignInNum, (__uint128_t)dig3);
     uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
     unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (__uint128_t)dig2);
     uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (__uint128_t)dig1);
     r->digits[1] = dig1;
     r->digits[2] = dig2;
     r->digits[3] = dig3;
     r->digits[4] = dig4;
 }
 #endif


 int8_t _CFBigNumGetInt8(const _CFBigNum *num) {
     int8_t result = num->digits[0];
     if (num->sign < 0) {
         result = -1 * result;
     }
     return result;
 }

 int16_t _CFBigNumGetInt16(const _CFBigNum *num) {
     int16_t result = num->digits[0];
     if (num->sign < 0) {
         result = -1 * result;
     }
     return result;
 }

 int32_t _CFBigNumGetInt32(const _CFBigNum *num) {
     int32_t result = num->digits[0];
     result += num->digits[1] * BIG_DIGITS_LIMIT;
     if (num->sign < 0) {
         result = -1 * result;
     }
     return result;
 }

 int64_t _CFBigNumGetInt64(const _CFBigNum *num) {
     int64_t result = num->digits[0];
     result += (int64_t)num->digits[1] * BIG_DIGITS_LIMIT;
     result += (int64_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
     if (num->sign < 0) {
         result = -1 * result;
     }
     return result;
 }

 #if __LP64__
 __int128_t _CFBigNumGetInt128(const _CFBigNum *num) {
     __int128_t result = num->digits[0];
     result += (__int128_t)num->digits[1] * BIG_DIGITS_LIMIT;
     result += (__int128_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
     result += (__int128_t)num->digits[3] * BIG_DIGITS_LIMIT_3;
     result += (__int128_t)num->digits[4] * BIG_DIGITS_LIMIT_4;
     if (num->sign < 0) {
         result = -1 * result;
     }
     return result;
 }
 #endif

 uint8_t _CFBigNumGetUInt8(const _CFBigNum *num) {
     uint8_t result = num->digits[0];
     return result;
 }

 uint16_t _CFBigNumGetUInt16(const _CFBigNum *num) {
     uint16_t result = num->digits[0];
     return result;
 }

 uint32_t _CFBigNumGetUInt32(const _CFBigNum *num) {
     uint32_t result = num->digits[0];
     result += num->digits[1] * BIG_DIGITS_LIMIT;
     return result;
 }

 uint64_t _CFBigNumGetUInt64(const _CFBigNum *num) {
     uint64_t result = num->digits[0];
     result += (uint64_t)num->digits[1] * BIG_DIGITS_LIMIT;
     result += (uint64_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
     return result;
 }

 #if __LP64__
 __uint128_t _CFBigNumGetUInt128(const _CFBigNum *num) {
     __uint128_t result = num->digits[0];
     result += (__uint128_t)num->digits[1] * BIG_DIGITS_LIMIT;
     result += (__uint128_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
     result += (__uint128_t)num->digits[3] * BIG_DIGITS_LIMIT_3;
     result += (__uint128_t)num->digits[4] * BIG_DIGITS_LIMIT_4;
     return result;
 }
 #endif


 void _CFBigNumInitWithCFNumber(_CFBigNum *r, CFNumberRef inNum) {
     uint8_t bytes[128 + 16];
     memset(bytes, 0, sizeof(bytes));
     // round bytes up to next multiple of 16; compiler attributes won't always guarantee big alignment
     void *bytesa = (uint8_t *)(((uintptr_t)bytes / 16) * 16 + 16);
     CFNumberType type = _CFNumberGetType2(inNum);
     CFNumberGetValue(inNum, type, bytesa);
     _CFBigNumInitWithBytes(r, bytesa, type);
 }

 void _CFBigNumInitWithBytes(_CFBigNum *r, const void *bytes, CFNumberType type) {
     switch (type) {
     case kCFNumberSInt8Type:
         _CFBigNumInitWithInt8(r, *(int8_t *)bytes);
         return;
     case kCFNumberSInt16Type:
         _CFBigNumInitWithInt16(r, *(int16_t *)bytes);
         return;
     case kCFNumberSInt32Type:
         _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
         return;
     case kCFNumberSInt64Type:
         _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
         return;
     case kCFNumberCharType:
         _CFBigNumInitWithInt8(r, *(int8_t *)bytes);
         return;
     case kCFNumberShortType:
         _CFBigNumInitWithInt16(r, *(int16_t *)bytes);
         return;
     case kCFNumberIntType:
         _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
         return;
     case kCFNumberLongType:
         if (sizeof(long) == 8) {
             _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
         } else {
             _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
         }
         return;
     case kCFNumberLongLongType:
         _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
         return;
     case kCFNumberCFIndexType:
         if (sizeof(CFIndex) == 8) {
             _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
         } else {
             _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
         }
         return;
     case kCFNumberNSIntegerType:
         if (sizeof(long) == 8) { // NSInteger follows long
             _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
         } else {
             _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
         }
         return;
 #if __LP64__
     case kCFNumberSInt128Type: {
         CFSInt128Struct s;
         memmove(&s, bytes, sizeof(CFSInt128Struct)); // the hard way because bytes might not be aligned
         __int128_t val = (__int128_t)s.low + ((__int128_t)s.high << 64);
         _CFBigNumInitWithInt128(r, val);
         return;
     }
 #endif
     default:
         return;
     }
 }

 CFNumberRef _CFNumberCreateWithBigNum(const _CFBigNum *input) {
     if (0 == input->digits[4] && 0 == input->digits[3] && 0 == input->digits[2] && 0 == input->digits[1]) {
         // This bumps up the size of the most negative n-bit value to the next larger size; oh well
         if (input->digits[0] <= INT8_MAX) {
             int8_t num = _CFBigNumGetInt8(input);
             CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt8Type, (const void *)&num);
             return result;
         } else if (input->digits[0] <= INT16_MAX) {
             int16_t num = _CFBigNumGetInt16(input);
             CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt16Type, (const void *)&num);
             return result;
         }
     }
     _CFBigNum maxlimit, minlimit;
     if (0 == input->digits[4] && 0 == input->digits[3] && 0 == input->digits[2]) {
         _CFBigNumInitWithInt32(&maxlimit, INT32_MAX);
         _CFBigNumInitWithInt32(&minlimit, INT32_MIN);
         CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
         CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
         if ((kCFCompareLessThan == cr || kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
             int32_t num = _CFBigNumGetInt32(input);
             CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt32Type, (const void *)&num);
             return result;
         }
     }
     if (0 == input->digits[4] && 0 == input->digits[3]) {
         _CFBigNumInitWithInt64(&maxlimit, INT64_MAX);
         _CFBigNumInitWithInt64(&minlimit, INT64_MIN);
         CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
         CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
         if ((kCFCompareLessThan == cr || kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
             int64_t num = _CFBigNumGetInt64(input);
             CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt64Type, (const void *)&num);
             return result;
         }
     }
 #if __LP64__
     _CFBigNumInitWithInt128(&maxlimit, INT128_MAX);
     _CFBigNumInitWithInt128(&minlimit, INT128_MIN);
     CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
     CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
     if ((kCFCompareLessThan == cr || kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
         __int128_t num = _CFBigNumGetInt128(input);
         CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt128Type, (const void *)&num);
         return result;
     }
 #endif
     return NULL;
 }

 CFComparisonResult _CFBigNumCompare(const _CFBigNum *a, const _CFBigNum *b) {
     Boolean sameSign = a->sign == b->sign;
     if (sameSign) {
         Boolean negative = a->sign < 0;
         for (CFIndex i = sizeof(a->digits) / sizeof(a->digits[0]); i--;) {
             if (a->digits[i] < b->digits[i]) {
                 return !negative ? kCFCompareLessThan : kCFCompareGreaterThan;
             }
             if (a->digits[i] > b->digits[i]) {
                 return negative ? kCFCompareLessThan : kCFCompareGreaterThan;
             }
         }
         return kCFCompareEqualTo;
     }
     return (a->sign < b->sign) ? kCFCompareLessThan : kCFCompareGreaterThan;
 }

 // abs(a) < abs(b)
 // do not care about the sign
 static Boolean _CFBigNumAbsoluteLessThan(const _CFBigNum *a, const _CFBigNum *b) {
     for (CFIndex i = sizeof(a->digits) / sizeof(a->digits[0]); i--;) {
         if (a->digits[i] < b->digits[i]) {
             return true;
         }
         if (a->digits[i] > b->digits[i]) {
             return false;
         }
     }
     return false;
 }

 // r = a * -1
 void _CFBigNumNeg(_CFBigNum *r, const _CFBigNum *a) {
     memmove(r, a, sizeof(*a));
     Boolean aIsZero = true;
     for (CFIndex i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
         if (a->digits[i] != 0) {
             aIsZero = false;
             break;
         }
     }
     // if a is zero, we do not flip the sign
     if (!aIsZero) {
         // 0  -> -1
         // -1 -> 0
         r->sign = r->sign * r->sign - 1;
     }
 }

 uint8_t _CFBigNumAdd(_CFBigNum *r, const _CFBigNum *a, const _CFBigNum *b) {
     uint8_t carry = 0;
     Boolean sameSign = a->sign == b->sign;
     if (sameSign) {
         for (CFIndex i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
             uint32_t result = a->digits[i] + b->digits[i] + carry;
             if (result > BIG_DIGITS_LIMIT) {
                 carry = 1;
                 result -= BIG_DIGITS_LIMIT;
             } else {
                 carry = 0;
             }
             r->digits[i] = result;
         }
         r->sign = a->sign;
         return carry;
     } else {
         // the algorithm here is to find the larger one and do the subtraction and then neg the result if necessary
         const _CFBigNum *bigNum = NULL;
         const _CFBigNum *smallNum = NULL;
         if (_CFBigNumAbsoluteLessThan(a, b)) {
             bigNum = b;
             smallNum = a;
         } else {
             bigNum = a;
             smallNum = b;
         }
         for (int i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
             int64_t result = (int64_t)bigNum->digits[i] - (int64_t)smallNum->digits[i] - carry;
             if (result < 0) {
                 carry = 1;
                 result += BIG_DIGITS_LIMIT;
             } else {
                 carry = 0;
             }
             r->digits[i] = result;
         }
         if (bigNum->sign < 0) {
             r->sign = -1;
         } else {
             r->sign = 0;
         }
         return carry;
     }
 }

 uint8_t _CFBigNumSub(_CFBigNum *r, const _CFBigNum *a, const _CFBigNum *b) {
     _CFBigNum nb;
     _CFBigNumNeg(&nb, b);
     return _CFBigNumAdd(r, a, &nb);
 }


 void _CFBigNumToCString(const _CFBigNum *vp, Boolean leading_zeros, Boolean leading_plus, char *buffer, size_t buflen) {
     if (vp->sign < 0) {
         *buffer++ = '-';
         buflen--;
     } else if (leading_plus) {
         *buffer++ = '+';
         buflen--;
     }
     char tmp[46];
     snprintf(tmp, sizeof(tmp), "%09u%09u%09u%09u%09u", vp->digits[4], vp->digits[3], vp->digits[2], vp->digits[1], vp->digits[0]);
     if (leading_zeros) {
         memset(buffer, '0', buflen);
         uint32_t tocopy = __CFMin(sizeof(tmp), buflen);
         memmove(buffer + buflen - tocopy, tmp + sizeof(tmp) - tocopy, tocopy); // copies trailing nul from tmp to nul-terminate
     } else {
         char *s = tmp;
         while (*s == '0') s++;
         if (*s == 0) s--; // if tmp is all zeros, copy out at least one zero
         strlcpy(buffer, s, buflen);
     }
 }

 void _CFBigNumFromCString(_CFBigNum *r, const char *string) {
     memset(r, 0, sizeof(*r));
     char *copy = (char *)calloc(strlen(string)+1, sizeof(char));
     memcpy(copy, string, strlen(string)+1);
     char *working = copy;
     if (*working == '-') {
         r->sign = -1;
         working++;
     } else if (*working == '+') {
         working++;
     }
     while (*working == '0') {
         working++;
     }

     size_t length = strlen(working);
     if (length == 0) { // the number is zero
         free(copy);
         return;
     }
     int curDigit = 0;
     while (curDigit + 1 < sizeof(r->digits) / sizeof(r->digits[0]) && 9 < length) {
         uint32_t digit = atol(working+length-9);
         r->digits[curDigit] = digit;
         *(working+length-9) = 0;
         length -= 9;
         curDigit++;
     }
     uint32_t digit = atol(working);
     r->digits[curDigit] = digit;
     free(copy);
 }

 char *_CFBigNumCopyDescription(const _CFBigNum *num) {
     char *result = (char *)calloc(1024, sizeof(char));
     sprintf(result, "sign:%s 1st:%u 2nd:%u 3rd:%u 4th:%u 5th:%u", num->sign < 0 ? "-" : "+", num->digits[0], num->digits[1], num->digits[2], num->digits[3], num->digits[4]);
     return result;
 }
	/* CFBigNumber.c
	Copyright (c) 2012-2016, Apple Inc. and the Swift project authors

	Portions Copyright (c) 2014-2016 Apple Inc. and the Swift project authors
	Licensed under Apache License v2.0 with Runtime Library Exception
	See http://swift.org/LICENSE.txt for license information
	See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	Responsibility: Christopher Kane
	Original author: Zhi Feng Huang
	*/

	#include <CoreFoundation/CFBigNumber.h>
	#include <limits.h>
	#include <stdlib.h>
	#include <string.h>
	#include <stdio.h>
	#include "CFInternal.h"


	typedef struct {
	int64_t high;
	uint64_t low;
	} CFSInt128Struct;

	#define kCFNumberSInt128Type 17

	CF_EXPORT CFNumberType _CFNumberGetType2(CFNumberRef number);

	#if __LP64__

	#ifndef _INT128_T
	#define _INT128_T
	typedef __int128_t int128_t;
	#endif

	#ifndef _UINT128_T
	#define _UINT128_T
	typedef __uint128_t uint128_t;
	#endif

	#ifndef INT128_MIN
	#define INT128_MIN ((__int128_t)0 - ((__int128_t)1 << 126) - ((__int128_t)1 << 126))
	#endif

	#ifndef INT128_MAX
	#define INT128_MAX ((__int128_t)-1 + ((__int128_t)1 << 126) + ((__int128_t)1 << 126))
	#endif

	#ifndef UINT128_MAX
	#define UINT128_MAX (((__uint128_t)1 << 127) - (__uint128_t)1 + ((__uint128_t)1 << 127))
	#endif

	#endif


	#define BIG_DIGITS_LIMIT 1000000000L
	#define BIG_DIGITS_LIMIT_2 ((uint64_t)BIG_DIGITS_LIMIT * (uint64_t)BIG_DIGITS_LIMIT)
	#define BIG_DIGITS_LIMIT_3 ((__uint128_t)BIG_DIGITS_LIMIT_2 * (__uint128_t)BIG_DIGITS_LIMIT)
	#define BIG_DIGITS_LIMIT_4 ((__uint128_t)BIG_DIGITS_LIMIT_3 * (__uint128_t)BIG_DIGITS_LIMIT)

	#define GET_FIFTH_DIGIT(A) (A / BIG_DIGITS_LIMIT_4)
	#define GET_FOURTH_DIGIT(A) (A / BIG_DIGITS_LIMIT_3)
	#define GET_THIRD_DIGIT(A) (A / BIG_DIGITS_LIMIT_2)
	#define GET_SECOND_DIGIT(A) (A / BIG_DIGITS_LIMIT)

	#define GET_REMAINDER_FIFTH_DIGIT(A,B) (A - B * BIG_DIGITS_LIMIT_4)
	#define GET_REMAINDER_FOURTH_DIGIT(A,B) (A - B * BIG_DIGITS_LIMIT_3)
	#define GET_REMAINDER_THIRD_DIGIT(A,B) (A - B * BIG_DIGITS_LIMIT_2)
	#define GET_REMAINDER_SECOND_DIGIT(A,B) (A - B * BIG_DIGITS_LIMIT)


	void _CFBigNumInitWithInt8(_CFBigNum *r, int8_t inNum) {
	memset(r, 0, sizeof(*r));
	uint8_t unsignInNum = inNum;
	if (inNum < 0) {
	r->sign = -1;
	unsignInNum = -1 * inNum;
	}
	r->digits[0] = unsignInNum;
	}

	void _CFBigNumInitWithInt16(_CFBigNum *r, int16_t inNum) {
	memset(r, 0, sizeof(*r));
	uint16_t unsignInNum = inNum;
	if (inNum < 0) {
	r->sign = -1;
	unsignInNum = -1 * inNum;
	}
	r->digits[0] = unsignInNum;
	}

	void _CFBigNumInitWithInt32(_CFBigNum *r, int32_t inNum) {
	memset(r, 0, sizeof(*r));
	uint32_t unsignInNum = inNum;
	if (inNum < 0) {
	r->sign = -1;
	unsignInNum = -1 * inNum;
	}
	uint32_t dig0 = GET_SECOND_DIGIT(unsignInNum);
	r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, dig0);
	r->digits[1] = dig0;
	}

	void _CFBigNumInitWithInt64(_CFBigNum *r, int64_t inNum) {
	memset(r, 0, sizeof(*r));
	uint64_t unsignInNum = inNum;
	if (inNum < 0) {
	r->sign = -1;
	unsignInNum = -1 * inNum;
	}
	uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
	unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (uint64_t)dig2);
	uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
	r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (uint64_t)dig1);
	r->digits[1] = dig1;
	r->digits[2] = dig2;
	}

	#ifdef __LP64__
	void _CFBigNumInitWithInt128(_CFBigNum *r, __int128_t inNum) {
	memset(r, 0, sizeof(*r));
	__uint128_t unsignInNum = inNum;
	if (inNum < 0) {
	r->sign = -1;
	unsignInNum = -1 * inNum;
	}
	uint32_t dig4 = GET_FIFTH_DIGIT(unsignInNum);
	unsignInNum = GET_REMAINDER_FIFTH_DIGIT(unsignInNum, (__uint128_t)dig4);
	uint32_t dig3 = GET_FOURTH_DIGIT(unsignInNum);
	unsignInNum = GET_REMAINDER_FOURTH_DIGIT(unsignInNum, (__uint128_t)dig3);
	uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
	unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (__uint128_t)dig2);
	uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
	r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (__uint128_t)dig1);
	r->digits[1] = dig1;
	r->digits[2] = dig2;
	r->digits[3] = dig3;
	r->digits[4] = dig4;
	}
	#endif

	void _CFBigNumInitWithUInt8(_CFBigNum *r, uint8_t inNum) {
	memset(r, 0, sizeof(*r));
	uint8_t unsignInNum = inNum;
	r->digits[0] = unsignInNum;
	}

	void _CFBigNumInitWithUInt16(_CFBigNum *r, uint16_t inNum) {
	memset(r, 0, sizeof(*r));
	uint16_t unsignInNum = inNum;
	r->digits[0] = unsignInNum;
	}

	void _CFBigNumInitWithUInt32(_CFBigNum *r, uint32_t inNum) {
	memset(r, 0, sizeof(*r));
	uint32_t unsignInNum = inNum;
	uint32_t dig0 = GET_SECOND_DIGIT(unsignInNum);
	r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, dig0);
	r->digits[1] = dig0;
	}

	void _CFBigNumInitWithUInt64(_CFBigNum *r, uint64_t inNum) {
	memset(r, 0, sizeof(*r));
	uint64_t unsignInNum = inNum;
	uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
	unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (uint64_t)dig2);
	uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
	r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (uint64_t)dig1);
	r->digits[1] = dig1;
	r->digits[2] = dig2;
	}

	#ifdef __LP64__
	void _CFBigNumInitWithUInt128(_CFBigNum *r, __uint128_t inNum) {
	memset(r, 0, sizeof(*r));
	__uint128_t unsignInNum = inNum;
	uint32_t dig4 = GET_FIFTH_DIGIT(unsignInNum);
	unsignInNum = GET_REMAINDER_FIFTH_DIGIT(unsignInNum, (__uint128_t)dig4);
	uint32_t dig3 = GET_FOURTH_DIGIT(unsignInNum);
	unsignInNum = GET_REMAINDER_FOURTH_DIGIT(unsignInNum, (__uint128_t)dig3);
	uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
	unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (__uint128_t)dig2);
	uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
	r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (__uint128_t)dig1);
	r->digits[1] = dig1;
	r->digits[2] = dig2;
	r->digits[3] = dig3;
	r->digits[4] = dig4;
	}
	#endif


	int8_t _CFBigNumGetInt8(const _CFBigNum *num) {
	int8_t result = num->digits[0];
	if (num->sign < 0) {
	result = -1 * result;
	}
	return result;
	}

	int16_t _CFBigNumGetInt16(const _CFBigNum *num) {
	int16_t result = num->digits[0];
	if (num->sign < 0) {
	result = -1 * result;
	}
	return result;
	}

	int32_t _CFBigNumGetInt32(const _CFBigNum *num) {
	int32_t result = num->digits[0];
	result += num->digits[1] * BIG_DIGITS_LIMIT;
	if (num->sign < 0) {
	result = -1 * result;
	}
	return result;
	}

	int64_t _CFBigNumGetInt64(const _CFBigNum *num) {
	int64_t result = num->digits[0];
	result += (int64_t)num->digits[1] * BIG_DIGITS_LIMIT;
	result += (int64_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
	if (num->sign < 0) {
	result = -1 * result;
	}
	return result;
	}

	#if __LP64__
	__int128_t _CFBigNumGetInt128(const _CFBigNum *num) {
	__int128_t result = num->digits[0];
	result += (__int128_t)num->digits[1] * BIG_DIGITS_LIMIT;
	result += (__int128_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
	result += (__int128_t)num->digits[3] * BIG_DIGITS_LIMIT_3;
	result += (__int128_t)num->digits[4] * BIG_DIGITS_LIMIT_4;
	if (num->sign < 0) {
	result = -1 * result;
	}
	return result;
	}
	#endif

	uint8_t _CFBigNumGetUInt8(const _CFBigNum *num) {
	uint8_t result = num->digits[0];
	return result;
	}

	uint16_t _CFBigNumGetUInt16(const _CFBigNum *num) {
	uint16_t result = num->digits[0];
	return result;
	}

	uint32_t _CFBigNumGetUInt32(const _CFBigNum *num) {
	uint32_t result = num->digits[0];
	result += num->digits[1] * BIG_DIGITS_LIMIT;
	return result;
	}

	uint64_t _CFBigNumGetUInt64(const _CFBigNum *num) {
	uint64_t result = num->digits[0];
	result += (uint64_t)num->digits[1] * BIG_DIGITS_LIMIT;
	result += (uint64_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
	return result;
	}

	#if __LP64__
	__uint128_t _CFBigNumGetUInt128(const _CFBigNum *num) {
	__uint128_t result = num->digits[0];
	result += (__uint128_t)num->digits[1] * BIG_DIGITS_LIMIT;
	result += (__uint128_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
	result += (__uint128_t)num->digits[3] * BIG_DIGITS_LIMIT_3;
	result += (__uint128_t)num->digits[4] * BIG_DIGITS_LIMIT_4;
	return result;
	}
	#endif


	void _CFBigNumInitWithCFNumber(_CFBigNum *r, CFNumberRef inNum) {
	uint8_t bytes[128 + 16];
	memset(bytes, 0, sizeof(bytes));
	// round bytes up to next multiple of 16; compiler attributes won't always guarantee big alignment
	void bytesa = (uint8_t )(((uintptr_t)bytes / 16) * 16 + 16);
	CFNumberType type = _CFNumberGetType2(inNum);
	CFNumberGetValue(inNum, type, bytesa);
	_CFBigNumInitWithBytes(r, bytesa, type);
	}

	void _CFBigNumInitWithBytes(_CFBigNum r, const void bytes, CFNumberType type) {
	switch (type) {
	case kCFNumberSInt8Type:
	_CFBigNumInitWithInt8(r, (int8_t )bytes);
	return;
	case kCFNumberSInt16Type:
	_CFBigNumInitWithInt16(r, (int16_t )bytes);
	return;
	case kCFNumberSInt32Type:
	_CFBigNumInitWithInt32(r, (int32_t )bytes);
	return;
	case kCFNumberSInt64Type:
	_CFBigNumInitWithInt64(r, (int64_t )bytes);
	return;
	case kCFNumberCharType:
	_CFBigNumInitWithInt8(r, (int8_t )bytes);
	return;
	case kCFNumberShortType:
	_CFBigNumInitWithInt16(r, (int16_t )bytes);
	return;
	case kCFNumberIntType:
	_CFBigNumInitWithInt32(r, (int32_t )bytes);
	return;
	case kCFNumberLongType:
	if (sizeof(long) == 8) {
	_CFBigNumInitWithInt64(r, (int64_t )bytes);
	} else {
	_CFBigNumInitWithInt32(r, (int32_t )bytes);
	}
	return;
	case kCFNumberLongLongType:
	_CFBigNumInitWithInt64(r, (int64_t )bytes);
	return;
	case kCFNumberCFIndexType:
	if (sizeof(CFIndex) == 8) {
	_CFBigNumInitWithInt64(r, (int64_t )bytes);
	} else {
	_CFBigNumInitWithInt32(r, (int32_t )bytes);
	}
	return;
	case kCFNumberNSIntegerType:
	if (sizeof(long) == 8) { // NSInteger follows long
	_CFBigNumInitWithInt64(r, (int64_t )bytes);
	} else {
	_CFBigNumInitWithInt32(r, (int32_t )bytes);
	}
	return;
	#if __LP64__
	case kCFNumberSInt128Type: {
	CFSInt128Struct s;
	memmove(&s, bytes, sizeof(CFSInt128Struct)); // the hard way because bytes might not be aligned
	__int128_t val = (__int128_t)s.low + ((__int128_t)s.high << 64);
	_CFBigNumInitWithInt128(r, val);
	return;
	}
	#endif
	default:
	return;
	}
	}

	CFNumberRef _CFNumberCreateWithBigNum(const _CFBigNum *input) {
	if (0 == input->digits[4] && 0 == input->digits[3] && 0 == input->digits[2] && 0 == input->digits[1]) {
	// This bumps up the size of the most negative n-bit value to the next larger size; oh well
	if (input->digits[0] <= INT8_MAX) {
	int8_t num = _CFBigNumGetInt8(input);
	CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt8Type, (const void *)&num);
	return result;
	} else if (input->digits[0] <= INT16_MAX) {
	int16_t num = _CFBigNumGetInt16(input);
	CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt16Type, (const void *)&num);
	return result;
	}
	}
	_CFBigNum maxlimit, minlimit;
	if (0 == input->digits[4] && 0 == input->digits[3] && 0 == input->digits[2]) {
	_CFBigNumInitWithInt32(&maxlimit, INT32_MAX);
	_CFBigNumInitWithInt32(&minlimit, INT32_MIN);
	CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
	CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
	if ((kCFCompareLessThan == cr \|\| kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
	int32_t num = _CFBigNumGetInt32(input);
	CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt32Type, (const void *)&num);
	return result;
	}
	}
	if (0 == input->digits[4] && 0 == input->digits[3]) {
	_CFBigNumInitWithInt64(&maxlimit, INT64_MAX);
	_CFBigNumInitWithInt64(&minlimit, INT64_MIN);
	CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
	CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
	if ((kCFCompareLessThan == cr \|\| kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
	int64_t num = _CFBigNumGetInt64(input);
	CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt64Type, (const void *)&num);
	return result;
	}
	}
	#if __LP64__
	_CFBigNumInitWithInt128(&maxlimit, INT128_MAX);
	_CFBigNumInitWithInt128(&minlimit, INT128_MIN);
	CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
	CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
	if ((kCFCompareLessThan == cr \|\| kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
	__int128_t num = _CFBigNumGetInt128(input);
	CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt128Type, (const void *)&num);
	return result;
	}
	#endif
	return NULL;
	}

	CFComparisonResult _CFBigNumCompare(const _CFBigNum a, const _CFBigNum b) {
	Boolean sameSign = a->sign == b->sign;
	if (sameSign) {
	Boolean negative = a->sign < 0;
	for (CFIndex i = sizeof(a->digits) / sizeof(a->digits[0]); i--;) {
	if (a->digits[i] < b->digits[i]) {
	return !negative ? kCFCompareLessThan : kCFCompareGreaterThan;
	}
	if (a->digits[i] > b->digits[i]) {
	return negative ? kCFCompareLessThan : kCFCompareGreaterThan;
	}
	}
	return kCFCompareEqualTo;
	}
	return (a->sign < b->sign) ? kCFCompareLessThan : kCFCompareGreaterThan;
	}

	// abs(a) < abs(b)
	// do not care about the sign
	static Boolean _CFBigNumAbsoluteLessThan(const _CFBigNum a, const _CFBigNum b) {
	for (CFIndex i = sizeof(a->digits) / sizeof(a->digits[0]); i--;) {
	if (a->digits[i] < b->digits[i]) {
	return true;
	}
	if (a->digits[i] > b->digits[i]) {
	return false;
	}
	}
	return false;
	}

	// r = a * -1
	void _CFBigNumNeg(_CFBigNum r, const _CFBigNum a) {
	memmove(r, a, sizeof(*a));
	Boolean aIsZero = true;
	for (CFIndex i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
	if (a->digits[i] != 0) {
	aIsZero = false;
	break;
	}
	}
	// if a is zero, we do not flip the sign
	if (!aIsZero) {
	// 0 -> -1
	// -1 -> 0
	r->sign = r->sign * r->sign - 1;
	}
	}

	uint8_t _CFBigNumAdd(_CFBigNum r, const _CFBigNum a, const _CFBigNum *b) {
	uint8_t carry = 0;
	Boolean sameSign = a->sign == b->sign;
	if (sameSign) {
	for (CFIndex i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
	uint32_t result = a->digits[i] + b->digits[i] + carry;
	if (result > BIG_DIGITS_LIMIT) {
	carry = 1;
	result -= BIG_DIGITS_LIMIT;
	} else {
	carry = 0;
	}
	r->digits[i] = result;
	}
	r->sign = a->sign;
	return carry;
	} else {
	// the algorithm here is to find the larger one and do the subtraction and then neg the result if necessary
	const _CFBigNum *bigNum = NULL;
	const _CFBigNum *smallNum = NULL;
	if (_CFBigNumAbsoluteLessThan(a, b)) {
	bigNum = b;
	smallNum = a;
	} else {
	bigNum = a;
	smallNum = b;
	}
	for (int i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
	int64_t result = (int64_t)bigNum->digits[i] - (int64_t)smallNum->digits[i] - carry;
	if (result < 0) {
	carry = 1;
	result += BIG_DIGITS_LIMIT;
	} else {
	carry = 0;
	}
	r->digits[i] = result;
	}
	if (bigNum->sign < 0) {
	r->sign = -1;
	} else {
	r->sign = 0;
	}
	return carry;
	}
	}

	uint8_t _CFBigNumSub(_CFBigNum r, const _CFBigNum a, const _CFBigNum *b) {
	_CFBigNum nb;
	_CFBigNumNeg(&nb, b);
	return _CFBigNumAdd(r, a, &nb);
	}


	void _CFBigNumToCString(const _CFBigNum vp, Boolean leading_zeros, Boolean leading_plus, char buffer, size_t buflen) {
	if (vp->sign < 0) {
	*buffer++ = '-';
	buflen--;
	} else if (leading_plus) {
	*buffer++ = '+';
	buflen--;
	}
	char tmp[46];
	snprintf(tmp, sizeof(tmp), "%09u%09u%09u%09u%09u", vp->digits[4], vp->digits[3], vp->digits[2], vp->digits[1], vp->digits[0]);
	if (leading_zeros) {
	memset(buffer, '0', buflen);
	uint32_t tocopy = __CFMin(sizeof(tmp), buflen);
	memmove(buffer + buflen - tocopy, tmp + sizeof(tmp) - tocopy, tocopy); // copies trailing nul from tmp to nul-terminate
	} else {
	char *s = tmp;
	while (*s == '0') s++;
	if (*s == 0) s--; // if tmp is all zeros, copy out at least one zero
	strlcpy(buffer, s, buflen);
	}
	}

	void _CFBigNumFromCString(_CFBigNum r, const char string) {
	memset(r, 0, sizeof(*r));
	char copy = (char )calloc(strlen(string)+1, sizeof(char));
	memcpy(copy, string, strlen(string)+1);
	char *working = copy;
	if (*working == '-') {
	r->sign = -1;
	working++;
	} else if (*working == '+') {
	working++;
	}
	while (*working == '0') {
	working++;
	}

	size_t length = strlen(working);
	if (length == 0) { // the number is zero
	free(copy);
	return;
	}
	int curDigit = 0;
	while (curDigit + 1 < sizeof(r->digits) / sizeof(r->digits[0]) && 9 < length) {
	uint32_t digit = atol(working+length-9);
	r->digits[curDigit] = digit;
	*(working+length-9) = 0;
	length -= 9;
	curDigit++;
	}
	uint32_t digit = atol(working);
	r->digits[curDigit] = digit;
	free(copy);
	}

	char _CFBigNumCopyDescription(const _CFBigNum num) {
	char result = (char )calloc(1024, sizeof(char));
	sprintf(result, "sign:%s 1st:%u 2nd:%u 3rd:%u 4th:%u 5th:%u", num->sign < 0 ? "-" : "+", num->digits[0], num->digits[1], num->digits[2], num->digits[3], num->digits[4]);
	return result;
	}