CFBigNumber.c

   1 /*
   2  * Copyright (c) 2014 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 /*      CFBigNumber.c
  25         Copyright (c) 2012-2013, Apple Inc. All rights reserved.
  26         Responsibility: Christopher Kane
  27         Original author: Zhi Feng Huang
  28 */
  29
  30 #include <CoreFoundation/CFBigNumber.h>
  31 #include <limits.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <stdio.h>
  35 #include "CFInternal.h"
  36
  37
  38 typedef struct {
  39     int64_t high;
  40     uint64_t low;
  41 } CFSInt128Struct;
  42
  43 #define kCFNumberSInt128Type 17
  44
  45 CF_EXPORT CFNumberType _CFNumberGetType2(CFNumberRef number);
  46
  47 #if __LP64__
  48
  49 #ifndef _INT128_T
  50 #define _INT128_T
  51 typedef __int128_t  int128_t;
  52 #endif
  53
  54 #ifndef _UINT128_T
  55 #define _UINT128_T
  56 typedef __uint128_t uint128_t;
  57 #endif
  58
  59 #ifndef INT128_MIN
  60 #define INT128_MIN  ((__int128_t)0 - ((__int128_t)1 << 126) - ((__int128_t)1 << 126))
  61 #endif
  62
  63 #ifndef INT128_MAX
  64 #define INT128_MAX  ((__int128_t)-1 + ((__int128_t)1 << 126) + ((__int128_t)1 << 126))
  65 #endif
  66
  67 #ifndef UINT128_MAX
  68 #define UINT128_MAX (((__uint128_t)1 << 127) - (__uint128_t)1 + ((__uint128_t)1 << 127))
  69 #endif
  70
  71 #endif
  72
  73
  74 #define BIG_DIGITS_LIMIT    1000000000L
  75 #define BIG_DIGITS_LIMIT_2  ((uint64_t)BIG_DIGITS_LIMIT * (uint64_t)BIG_DIGITS_LIMIT)
  76 #define BIG_DIGITS_LIMIT_3  ((__uint128_t)BIG_DIGITS_LIMIT_2 * (__uint128_t)BIG_DIGITS_LIMIT)
  77 #define BIG_DIGITS_LIMIT_4  ((__uint128_t)BIG_DIGITS_LIMIT_3 * (__uint128_t)BIG_DIGITS_LIMIT)
  78
  79 #define GET_FIFTH_DIGIT(A)  (A / BIG_DIGITS_LIMIT_4)
  80 #define GET_FOURTH_DIGIT(A) (A / BIG_DIGITS_LIMIT_3)
  81 #define GET_THIRD_DIGIT(A)  (A / BIG_DIGITS_LIMIT_2)
  82 #define GET_SECOND_DIGIT(A) (A / BIG_DIGITS_LIMIT)
  83
  84 #define GET_REMAINDER_FIFTH_DIGIT(A,B)  (A - B * BIG_DIGITS_LIMIT_4)
  85 #define GET_REMAINDER_FOURTH_DIGIT(A,B) (A - B * BIG_DIGITS_LIMIT_3)
  86 #define GET_REMAINDER_THIRD_DIGIT(A,B)  (A - B * BIG_DIGITS_LIMIT_2)
  87 #define GET_REMAINDER_SECOND_DIGIT(A,B) (A - B * BIG_DIGITS_LIMIT)
  88
  89
  90 void _CFBigNumInitWithInt8(_CFBigNum *r, int8_t inNum) {
  91     memset(r, 0, sizeof(*r));
  92     uint8_t unsignInNum = inNum;
  93     if (inNum < 0) {
  94         r->sign = -1;
  95         unsignInNum = -1 * inNum;
  96     }
  97     r->digits[0] = unsignInNum;
  98 }
  99
 100 void _CFBigNumInitWithInt16(_CFBigNum *r, int16_t inNum) {
 101     memset(r, 0, sizeof(*r));
 102     uint16_t unsignInNum = inNum;
 103     if (inNum < 0) {
 104         r->sign = -1;
 105         unsignInNum = -1 * inNum;
 106     }
 107     r->digits[0] = unsignInNum;
 108 }
 109
 110 void _CFBigNumInitWithInt32(_CFBigNum *r, int32_t inNum) {
 111     memset(r, 0, sizeof(*r));
 112     uint32_t unsignInNum = inNum;
 113     if (inNum < 0) {
 114         r->sign = -1;
 115         unsignInNum = -1 * inNum;
 116     }
 117     uint32_t dig0 = GET_SECOND_DIGIT(unsignInNum);
 118     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, dig0);
 119     r->digits[1] = dig0;
 120 }
 121
 122 void _CFBigNumInitWithInt64(_CFBigNum *r, int64_t inNum) {
 123     memset(r, 0, sizeof(*r));
 124     uint64_t unsignInNum = inNum;
 125     if (inNum < 0) {
 126         r->sign = -1;
 127         unsignInNum = -1 * inNum;
 128     }
 129     uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
 130     unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (uint64_t)dig2);
 131     uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
 132     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (uint64_t)dig1);
 133     r->digits[1] = dig1;
 134     r->digits[2] = dig2;
 135 }
 136
 137 #ifdef __LP64__
 138 void _CFBigNumInitWithInt128(_CFBigNum *r, __int128_t inNum) {
 139     memset(r, 0, sizeof(*r));
 140     __uint128_t unsignInNum = inNum;
 141     if (inNum < 0) {
 142         r->sign = -1;
 143         unsignInNum = -1 * inNum;
 144     }
 145     uint32_t dig4 = GET_FIFTH_DIGIT(unsignInNum);
 146     unsignInNum = GET_REMAINDER_FIFTH_DIGIT(unsignInNum, (__uint128_t)dig4);
 147     uint32_t dig3 = GET_FOURTH_DIGIT(unsignInNum);
 148     unsignInNum = GET_REMAINDER_FOURTH_DIGIT(unsignInNum, (__uint128_t)dig3);
 149     uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
 150     unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (__uint128_t)dig2);
 151     uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
 152     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (__uint128_t)dig1);
 153     r->digits[1] = dig1;
 154     r->digits[2] = dig2;
 155     r->digits[3] = dig3;
 156     r->digits[4] = dig4;
 157 }
 158 #endif
 159
 160 void _CFBigNumInitWithUInt8(_CFBigNum *r, uint8_t inNum) {
 161     memset(r, 0, sizeof(*r));
 162     uint8_t unsignInNum = inNum;
 163     r->digits[0] = unsignInNum;
 164 }
 165
 166 void _CFBigNumInitWithUInt16(_CFBigNum *r, uint16_t inNum) {
 167     memset(r, 0, sizeof(*r));
 168     uint16_t unsignInNum = inNum;
 169     r->digits[0] = unsignInNum;
 170 }
 171
 172 void _CFBigNumInitWithUInt32(_CFBigNum *r, uint32_t inNum) {
 173     memset(r, 0, sizeof(*r));
 174     uint32_t unsignInNum = inNum;
 175     uint32_t dig0 = GET_SECOND_DIGIT(unsignInNum);
 176     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, dig0);
 177     r->digits[1] = dig0;
 178 }
 179
 180 void _CFBigNumInitWithUInt64(_CFBigNum *r, uint64_t inNum) {
 181     memset(r, 0, sizeof(*r));
 182     uint64_t unsignInNum = inNum;
 183     uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
 184     unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (uint64_t)dig2);
 185     uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
 186     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (uint64_t)dig1);
 187     r->digits[1] = dig1;
 188     r->digits[2] = dig2;
 189 }
 190
 191 #ifdef __LP64__
 192 void _CFBigNumInitWithUInt128(_CFBigNum *r, __uint128_t inNum) {
 193     memset(r, 0, sizeof(*r));
 194     __uint128_t unsignInNum = inNum;
 195     uint32_t dig4 = GET_FIFTH_DIGIT(unsignInNum);
 196     unsignInNum = GET_REMAINDER_FIFTH_DIGIT(unsignInNum, (__uint128_t)dig4);
 197     uint32_t dig3 = GET_FOURTH_DIGIT(unsignInNum);
 198     unsignInNum = GET_REMAINDER_FOURTH_DIGIT(unsignInNum, (__uint128_t)dig3);
 199     uint32_t dig2 = GET_THIRD_DIGIT(unsignInNum);
 200     unsignInNum = GET_REMAINDER_THIRD_DIGIT(unsignInNum, (__uint128_t)dig2);
 201     uint32_t dig1 = GET_SECOND_DIGIT(unsignInNum);
 202     r->digits[0] = GET_REMAINDER_SECOND_DIGIT(unsignInNum, (__uint128_t)dig1);
 203     r->digits[1] = dig1;
 204     r->digits[2] = dig2;
 205     r->digits[3] = dig3;
 206     r->digits[4] = dig4;
 207 }
 208 #endif
 209
 210
 211 int8_t _CFBigNumGetInt8(const _CFBigNum *num) {
 212     int8_t result = num->digits[0];
 213     if (num->sign < 0) {
 214         result = -1 * result;
 215     }
 216     return result;
 217 }
 218
 219 int16_t _CFBigNumGetInt16(const _CFBigNum *num) {
 220     int16_t result = num->digits[0];
 221     if (num->sign < 0) {
 222         result = -1 * result;
 223     }
 224     return result;
 225 }
 226
 227 int32_t _CFBigNumGetInt32(const _CFBigNum *num) {
 228     int32_t result = num->digits[0];
 229     result += num->digits[1] * BIG_DIGITS_LIMIT;
 230     if (num->sign < 0) {
 231         result = -1 * result;
 232     }
 233     return result;
 234 }
 235
 236 int64_t _CFBigNumGetInt64(const _CFBigNum *num) {
 237     int64_t result = num->digits[0];
 238     result += (int64_t)num->digits[1] * BIG_DIGITS_LIMIT;
 239     result += (int64_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
 240     if (num->sign < 0) {
 241         result = -1 * result;
 242     }
 243     return result;
 244 }
 245
 246 #if __LP64__
 247 __int128_t _CFBigNumGetInt128(const _CFBigNum *num) {
 248     __int128_t result = num->digits[0];
 249     result += (__int128_t)num->digits[1] * BIG_DIGITS_LIMIT;
 250     result += (__int128_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
 251     result += (__int128_t)num->digits[3] * BIG_DIGITS_LIMIT_3;
 252     result += (__int128_t)num->digits[4] * BIG_DIGITS_LIMIT_4;
 253     if (num->sign < 0) {
 254         result = -1 * result;
 255     }
 256     return result;
 257 }
 258 #endif
 259
 260 uint8_t _CFBigNumGetUInt8(const _CFBigNum *num) {
 261     uint8_t result = num->digits[0];
 262     return result;
 263 }
 264
 265 uint16_t _CFBigNumGetUInt16(const _CFBigNum *num) {
 266     uint16_t result = num->digits[0];
 267     return result;
 268 }
 269
 270 uint32_t _CFBigNumGetUInt32(const _CFBigNum *num) {
 271     uint32_t result = num->digits[0];
 272     result += num->digits[1] * BIG_DIGITS_LIMIT;
 273     return result;
 274 }
 275
 276 uint64_t _CFBigNumGetUInt64(const _CFBigNum *num) {
 277     uint64_t result = num->digits[0];
 278     result += (uint64_t)num->digits[1] * BIG_DIGITS_LIMIT;
 279     result += (uint64_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
 280     return result;
 281 }
 282
 283 #if __LP64__
 284 __uint128_t _CFBigNumGetUInt128(const _CFBigNum *num) {
 285     __uint128_t result = num->digits[0];
 286     result += (__uint128_t)num->digits[1] * BIG_DIGITS_LIMIT;
 287     result += (__uint128_t)num->digits[2] * BIG_DIGITS_LIMIT_2;
 288     result += (__uint128_t)num->digits[3] * BIG_DIGITS_LIMIT_3;
 289     result += (__uint128_t)num->digits[4] * BIG_DIGITS_LIMIT_4;
 290     return result;
 291 }
 292 #endif
 293
 294
 295 void _CFBigNumInitWithCFNumber(_CFBigNum *r, CFNumberRef inNum) {
 296     uint8_t bytes[128 + 16];
 297     memset(bytes, 0, sizeof(bytes));
 298     // round bytes up to next multiple of 16; compiler attributes won't always guarantee big alignment
 299     void *bytesa = (uint8_t *)(((uintptr_t)bytes / 16) * 16 + 16);
 300     CFNumberType type = _CFNumberGetType2(inNum);
 301     CFNumberGetValue(inNum, type, bytesa);
 302     _CFBigNumInitWithBytes(r, bytesa, type);
 303 }
 304
 305 void _CFBigNumInitWithBytes(_CFBigNum *r, const void *bytes, CFNumberType type) {
 306     switch (type) {
 307     case kCFNumberSInt8Type:
 308         _CFBigNumInitWithInt8(r, *(int8_t *)bytes);
 309         return;
 310     case kCFNumberSInt16Type:
 311         _CFBigNumInitWithInt16(r, *(int16_t *)bytes);
 312         return;
 313     case kCFNumberSInt32Type:
 314         _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
 315         return;
 316     case kCFNumberSInt64Type:
 317         _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
 318         return;
 319     case kCFNumberCharType:
 320         _CFBigNumInitWithInt8(r, *(int8_t *)bytes);
 321         return;
 322     case kCFNumberShortType:
 323         _CFBigNumInitWithInt16(r, *(int16_t *)bytes);
 324         return;
 325     case kCFNumberIntType:
 326         _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
 327         return;
 328     case kCFNumberLongType:
 329         if (sizeof(long) == 8) {
 330             _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
 331         } else {
 332             _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
 333         }
 334         return;
 335     case kCFNumberLongLongType:
 336         _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
 337         return;
 338     case kCFNumberCFIndexType:
 339         if (sizeof(CFIndex) == 8) {
 340             _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
 341         } else {
 342             _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
 343         }
 344         return;
 345     case kCFNumberNSIntegerType:
 346         if (sizeof(long) == 8) { // NSInteger follows long
 347             _CFBigNumInitWithInt64(r, *(int64_t *)bytes);
 348         } else {
 349             _CFBigNumInitWithInt32(r, *(int32_t *)bytes);
 350         }
 351         return;
 352 #if __LP64__
 353     case kCFNumberSInt128Type: {
 354         CFSInt128Struct s;
 355         memmove(&s, bytes, sizeof(CFSInt128Struct)); // the hard way because bytes might not be aligned
 356         __int128_t val = (__int128_t)s.low + ((__int128_t)s.high << 64);
 357         _CFBigNumInitWithInt128(r, val);
 358         return;
 359     }
 360 #endif
 361     default:
 362         return;
 363     }
 364 }
 365
 366 CFNumberRef _CFNumberCreateWithBigNum(const _CFBigNum *input) {
 367     if (0 == input->digits[4] && 0 == input->digits[3] && 0 == input->digits[2] && 0 == input->digits[1]) {
 368         // This bumps up the size of the most negative n-bit value to the next larger size; oh well
 369         if (input->digits[0] <= INT8_MAX) {
 370             int8_t num = _CFBigNumGetInt8(input);
 371             CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt8Type, (const void *)&num);
 372             return result;
 373         } else if (input->digits[0] <= INT16_MAX) {
 374             int16_t num = _CFBigNumGetInt16(input);
 375             CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt16Type, (const void *)&num);
 376             return result;
 377         }
 378     }
 379     _CFBigNum maxlimit, minlimit;
 380     if (0 == input->digits[4] && 0 == input->digits[3] && 0 == input->digits[2]) {
 381         _CFBigNumInitWithInt32(&maxlimit, INT32_MAX);
 382         _CFBigNumInitWithInt32(&minlimit, INT32_MIN);
 383         CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
 384         CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
 385         if ((kCFCompareLessThan == cr || kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
 386             int32_t num = _CFBigNumGetInt32(input);
 387             CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt32Type, (const void *)&num);
 388             return result;
 389         }
 390     }
 391     if (0 == input->digits[4] && 0 == input->digits[3]) {
 392         _CFBigNumInitWithInt64(&maxlimit, INT64_MAX);
 393         _CFBigNumInitWithInt64(&minlimit, INT64_MIN);
 394         CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
 395         CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
 396         if ((kCFCompareLessThan == cr || kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
 397             int64_t num = _CFBigNumGetInt64(input);
 398             CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt64Type, (const void *)&num);
 399             return result;
 400         }
 401     }
 402 #if __LP64__
 403     _CFBigNumInitWithInt128(&maxlimit, INT128_MAX);
 404     _CFBigNumInitWithInt128(&minlimit, INT128_MIN);
 405     CFComparisonResult cr = _CFBigNumCompare(input, &maxlimit);
 406     CFComparisonResult crn = _CFBigNumCompare(input, &minlimit);
 407     if ((kCFCompareLessThan == cr || kCFCompareEqualTo == cr) && (kCFCompareLessThan != crn)) {
 408         __int128_t num = _CFBigNumGetInt128(input);
 409         CFNumberRef result = CFNumberCreate(kCFAllocatorSystemDefault, kCFNumberSInt128Type, (const void *)&num);
 410         return result;
 411     }
 412 #endif
 413     return NULL;
 414 }
 415
 416 CFComparisonResult _CFBigNumCompare(const _CFBigNum *a, const _CFBigNum *b) {
 417     Boolean sameSign = a->sign == b->sign;
 418     if (sameSign) {
 419         Boolean negative = a->sign < 0;
 420         for (CFIndex i = sizeof(a->digits) / sizeof(a->digits[0]); i--;) {
 421             if (a->digits[i] < b->digits[i]) {
 422                 return !negative ? kCFCompareLessThan : kCFCompareGreaterThan;
 423             }
 424             if (a->digits[i] > b->digits[i]) {
 425                 return negative ? kCFCompareLessThan : kCFCompareGreaterThan;
 426             }
 427         }
 428         return kCFCompareEqualTo;
 429     }
 430     return (a->sign < b->sign) ? kCFCompareLessThan : kCFCompareGreaterThan;
 431 }
 432
 433 // abs(a) < abs(b)
 434 // do not care about the sign
 435 static Boolean _CFBigNumAbsoluteLessThan(const _CFBigNum *a, const _CFBigNum *b) {
 436     for (CFIndex i = sizeof(a->digits) / sizeof(a->digits[0]); i--;) {
 437         if (a->digits[i] < b->digits[i]) {
 438             return true;
 439         }
 440         if (a->digits[i] > b->digits[i]) {
 441             return false;
 442         }
 443     }
 444     return false;
 445 }
 446
 447 // r = a * -1
 448 void _CFBigNumNeg(_CFBigNum *r, const _CFBigNum *a) {
 449     memmove(r, a, sizeof(*a));
 450     Boolean aIsZero = true;
 451     for (CFIndex i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
 452         if (a->digits[i] != 0) {
 453             aIsZero = false;
 454             break;
 455         }
 456     }
 457     // if a is zero, we do not flip the sign
 458     if (!aIsZero) {
 459         // 0  -> -1
 460         // -1 -> 0
 461         r->sign = r->sign * r->sign - 1;
 462     }
 463 }
 464
 465 uint8_t _CFBigNumAdd(_CFBigNum *r, const _CFBigNum *a, const _CFBigNum *b) {
 466     uint8_t carry = 0;
 467     Boolean sameSign = a->sign == b->sign;
 468     if (sameSign) {
 469         for (CFIndex i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
 470             uint32_t result = a->digits[i] + b->digits[i] + carry;
 471             if (result > BIG_DIGITS_LIMIT) {
 472                 carry = 1;
 473                 result -= BIG_DIGITS_LIMIT;
 474             } else {
 475                 carry = 0;
 476             }
 477             r->digits[i] = result;
 478         }
 479         r->sign = a->sign;
 480         return carry;
 481     } else {
 482         // the algorithm here is to find the larger one and do the subtraction and then neg the result if necessary
 483         const _CFBigNum *bigNum = NULL;
 484         const _CFBigNum *smallNum = NULL;
 485         if (_CFBigNumAbsoluteLessThan(a, b)) {
 486             bigNum = b;
 487             smallNum = a;
 488         } else {
 489             bigNum = a;
 490             smallNum = b;
 491         }
 492         for (int i = 0; i < sizeof(a->digits) / sizeof(a->digits[0]); i++) {
 493             int64_t result = (int64_t)bigNum->digits[i] - (int64_t)smallNum->digits[i] - carry;
 494             if (result < 0) {
 495                 carry = 1;
 496                 result += BIG_DIGITS_LIMIT;
 497             } else {
 498                 carry = 0;
 499             }
 500             r->digits[i] = result;
 501         }
 502         if (bigNum->sign < 0) {
 503             r->sign = -1;
 504         } else {
 505             r->sign = 0;
 506         }
 507         return carry;
 508     }
 509 }
 510
 511 uint8_t _CFBigNumSub(_CFBigNum *r, const _CFBigNum *a, const _CFBigNum *b) {
 512     _CFBigNum nb;
 513     _CFBigNumNeg(&nb, b);
 514     return _CFBigNumAdd(r, a, &nb);
 515 }
 516
 517
 518 void _CFBigNumToCString(const _CFBigNum *vp, Boolean leading_zeros, Boolean leading_plus, char *buffer, size_t buflen) {
 519     if (vp->sign < 0) {
 520         *buffer++ = '-';
 521         buflen--;
 522     } else if (leading_plus) {
 523         *buffer++ = '+';
 524         buflen--;
 525     }
 526     char tmp[46];
 527     snprintf(tmp, sizeof(tmp), "%09u%09u%09u%09u%09u", vp->digits[4], vp->digits[3], vp->digits[2], vp->digits[1], vp->digits[0]);
 528     if (leading_zeros) {
 529         memset(buffer, '0', buflen);
 530         uint32_t tocopy = __CFMin(sizeof(tmp), buflen);
 531         memmove(buffer + buflen - tocopy, tmp + sizeof(tmp) - tocopy, tocopy); // copies trailing nul from tmp to nul-terminate
 532     } else {
 533         char *s = tmp;
 534         while (*s == '0') s++;
 535         if (*s == 0) s--; // if tmp is all zeros, copy out at least one zero
 536         strlcpy(buffer, s, buflen);
 537     }
 538 }
 539
 540 void _CFBigNumFromCString(_CFBigNum *r, const char *string) {
 541     memset(r, 0, sizeof(*r));
 542     char *copy = (char *)calloc(strlen(string)+1, sizeof(char));
 543     memcpy(copy, string, strlen(string)+1);
 544     char *working = copy;
 545     if (*working == '-') {
 546         r->sign = -1;
 547         working++;
 548     } else if (*working == '+') {
 549         working++;
 550     }
 551     while (*working == '0') {
 552         working++;
 553     }
 554
 555     size_t length = strlen(working);
 556     if (length == 0) { // the number is zero
 557         return;
 558     }
 559     int curDigit = 0;
 560     while (curDigit + 1 < sizeof(r->digits) / sizeof(r->digits[0]) && 9 < length) {
 561         uint32_t digit = atol(working+length-9);
 562         r->digits[curDigit] = digit;
 563         *(working+length-9) = 0;
 564         length -= 9;
 565         curDigit++;
 566     }
 567     uint32_t digit = atol(working);
 568     r->digits[curDigit] = digit;
 569     free(copy);
 570 }
 571
 572 char *_CFBigNumCopyDescription(const _CFBigNum *num) {
 573     char *result = (char *)calloc(1024, sizeof(char));
 574     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]);
 575     return result;
 576 }
 577