CFBigNumber.c

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