1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 | |
29 | |
30 | |
31 | |
32 | |
33 | |
34 | |
35 | |
36 | |
37 | |
38 | |
39 | |
40 | |
41 | |
42 | |
43 | |
44 | |
45 | |
46 | |
47 | |
48 | |
49 | |
50 | |
51 | |
52 | |
53 | #include "math.h" |
54 | #include "dmath.h" |
55 | #include "dragon4.h" |
56 | |
57 | |
58 | |
59 | |
60 | |
61 | const tU32 c_BigInt_MaxBlocks = 35; |
62 | |
63 | |
64 | |
65 | |
66 | |
67 | |
68 | |
69 | |
70 | struct tBigInt |
71 | { |
72 | |
73 | tBigInt & operator=(const tBigInt &rhs) |
74 | { |
75 | tU32 length = rhs.m_length; |
76 | tU32 * pLhsCur = m_blocks; |
77 | for (const tU32 *pRhsCur = rhs.m_blocks, *pRhsEnd = pRhsCur + length; |
78 | pRhsCur != pRhsEnd; |
79 | ++pLhsCur, ++pRhsCur) |
80 | { |
81 | *pLhsCur = *pRhsCur; |
82 | } |
83 | m_length = length; |
84 | return *this; |
85 | } |
86 | |
87 | |
88 | tU32 GetLength() const { |
89 | return m_length; |
90 | } |
91 | tU32 GetBlock(tU32 idx) const { |
92 | return m_blocks[idx]; |
93 | } |
94 | |
95 | |
96 | void SetZero() { |
97 | m_length = 0; |
98 | } |
99 | tB IsZero() const { |
100 | return m_length == 0; |
101 | } |
102 | |
103 | |
104 | void SetU64(tU64 val) |
105 | { |
106 | if (val > 0xFFFFFFFF) |
107 | { |
108 | m_blocks[0] = val & 0xFFFFFFFF; |
109 | m_blocks[1] = (val >> 32) & 0xFFFFFFFF; |
110 | m_length = 2; |
111 | } |
112 | else if (val != 0) |
113 | { |
114 | m_blocks[0] = val & 0xFFFFFFFF; |
115 | m_length = 1; |
116 | } |
117 | else |
118 | { |
119 | m_length = 0; |
120 | } |
121 | } |
122 | |
123 | void SetU32(tU32 val) |
124 | { |
125 | if (val != 0) |
126 | { |
127 | m_blocks[0] = val; |
128 | m_length = (val != 0); |
129 | } |
130 | else |
131 | { |
132 | m_length = 0; |
133 | } |
134 | } |
135 | |
136 | tU32 GetU32() const { |
137 | return (m_length == 0) ? 0 : m_blocks[0]; |
138 | } |
139 | |
140 | |
141 | tU32 m_length; |
142 | tU32 m_blocks[c_BigInt_MaxBlocks]; |
143 | }; |
144 | |
145 | |
146 | |
147 | |
148 | static tS32 BigInt_Compare(const tBigInt & lhs, const tBigInt & rhs) |
149 | { |
150 | |
151 | tS32 lengthDiff = lhs.m_length - rhs.m_length; |
152 | if (lengthDiff != 0) |
153 | return lengthDiff; |
154 | |
155 | |
156 | for (tS32 i = lhs.m_length - 1; i >= 0; --i) |
157 | { |
158 | if (lhs.m_blocks[i] == rhs.m_blocks[i]) |
159 | continue; |
160 | else if (lhs.m_blocks[i] > rhs.m_blocks[i]) |
161 | return 1; |
162 | else |
163 | return -1; |
164 | } |
165 | |
166 | |
167 | return 0; |
168 | } |
169 | |
170 | |
171 | |
172 | |
173 | static void BigInt_Add(tBigInt * pResult, const tBigInt & lhs, const tBigInt & rhs) |
174 | { |
175 | |
176 | const tBigInt * pLarge; |
177 | const tBigInt * pSmall; |
178 | if (lhs.m_length < rhs.m_length) |
179 | { |
180 | pSmall = &lhs; |
181 | pLarge = &rhs; |
182 | } |
183 | else |
184 | { |
185 | pSmall = &rhs; |
186 | pLarge = &lhs; |
187 | } |
188 | |
189 | const tU32 largeLen = pLarge->m_length; |
190 | const tU32 smallLen = pSmall->m_length; |
191 | |
192 | |
193 | pResult->m_length = largeLen; |
194 | |
195 | |
196 | tU64 carry = 0; |
197 | const tU32 * pLargeCur = pLarge->m_blocks; |
198 | const tU32 * pLargeEnd = pLargeCur + largeLen; |
199 | const tU32 * pSmallCur = pSmall->m_blocks; |
200 | const tU32 * pSmallEnd = pSmallCur + smallLen; |
201 | tU32 * pResultCur = pResult->m_blocks; |
202 | while (pSmallCur != pSmallEnd) |
203 | { |
204 | tU64 sum = carry + (tU64)(*pLargeCur) + (tU64)(*pSmallCur); |
205 | carry = sum >> 32; |
206 | (*pResultCur) = sum & 0xFFFFFFFF; |
207 | ++pLargeCur; |
208 | ++pSmallCur; |
209 | ++pResultCur; |
210 | } |
211 | |
212 | |
213 | while (pLargeCur != pLargeEnd) |
214 | { |
215 | tU64 sum = carry + (tU64)(*pLargeCur); |
216 | carry = sum >> 32; |
217 | (*pResultCur) = sum & 0xFFFFFFFF; |
218 | ++pLargeCur; |
219 | ++pResultCur; |
220 | } |
221 | |
222 | |
223 | if (carry != 0) |
224 | { |
225 | RJ_ASSERT(carry == 1); |
226 | RJ_ASSERT((tU32)(pResultCur - pResult->m_blocks) == largeLen && (largeLen < c_BigInt_MaxBlocks)); |
227 | *pResultCur = 1; |
228 | pResult->m_length = largeLen + 1; |
229 | } |
230 | else |
231 | { |
232 | pResult->m_length = largeLen; |
233 | } |
234 | } |
235 | |
236 | |
237 | |
238 | |
239 | static void BigInt_Multiply(tBigInt * pResult, const tBigInt &lhs, const tBigInt &rhs) |
240 | { |
241 | RJ_ASSERT( pResult != &lhs && pResult != &rhs ); |
242 | |
243 | |
244 | const tBigInt * pLarge; |
245 | const tBigInt * pSmall; |
246 | if (lhs.m_length < rhs.m_length) |
247 | { |
248 | pSmall = &lhs; |
249 | pLarge = &rhs; |
250 | } |
251 | else |
252 | { |
253 | pSmall = &rhs; |
254 | pLarge = &lhs; |
255 | } |
256 | |
257 | |
258 | tU32 maxResultLen = pLarge->m_length + pSmall->m_length; |
259 | RJ_ASSERT( maxResultLen <= c_BigInt_MaxBlocks ); |
260 | |
261 | |
262 | for(tU32 * pCur = pResult->m_blocks, *pEnd = pCur + maxResultLen; pCur != pEnd; ++pCur) |
263 | *pCur = 0; |
264 | |
265 | |
266 | const tU32 *pLargeBeg = pLarge->m_blocks; |
267 | const tU32 *pLargeEnd = pLargeBeg + pLarge->m_length; |
268 | |
269 | |
270 | tU32 *pResultStart = pResult->m_blocks; |
271 | for(const tU32 *pSmallCur = pSmall->m_blocks, *pSmallEnd = pSmallCur + pSmall->m_length; |
272 | pSmallCur != pSmallEnd; |
273 | ++pSmallCur, ++pResultStart) |
274 | { |
275 | |
276 | const tU32 multiplier = *pSmallCur; |
277 | if (multiplier != 0) |
278 | { |
279 | const tU32 *pLargeCur = pLargeBeg; |
280 | tU32 *pResultCur = pResultStart; |
281 | tU64 carry = 0; |
282 | do |
283 | { |
284 | tU64 product = (*pResultCur) + (*pLargeCur)*(tU64)multiplier + carry; |
285 | carry = product >> 32; |
286 | *pResultCur = product & 0xFFFFFFFF; |
287 | ++pLargeCur; |
288 | ++pResultCur; |
289 | } while(pLargeCur != pLargeEnd); |
290 | |
291 | RJ_ASSERT(pResultCur < pResult->m_blocks + maxResultLen); |
292 | *pResultCur = (tU32)(carry & 0xFFFFFFFF); |
293 | } |
294 | } |
295 | |
296 | |
297 | if (maxResultLen > 0 && pResult->m_blocks[maxResultLen - 1] == 0) |
298 | pResult->m_length = maxResultLen-1; |
299 | else |
300 | pResult->m_length = maxResultLen; |
301 | } |
302 | |
303 | |
304 | |
305 | |
306 | static void BigInt_Multiply(tBigInt * pResult, const tBigInt & lhs, tU32 rhs) |
307 | { |
308 | |
309 | tU32 carry = 0; |
310 | tU32 *pResultCur = pResult->m_blocks; |
311 | const tU32 *pLhsCur = lhs.m_blocks; |
312 | const tU32 *pLhsEnd = lhs.m_blocks + lhs.m_length; |
313 | for ( ; pLhsCur != pLhsEnd; ++pLhsCur, ++pResultCur ) |
314 | { |
315 | tU64 product = (tU64)(*pLhsCur) * rhs + carry; |
316 | *pResultCur = (tU32)(product & 0xFFFFFFFF); |
317 | carry = product >> 32; |
318 | } |
319 | |
320 | |
321 | if (carry != 0) |
322 | { |
323 | |
324 | RJ_ASSERT(lhs.m_length + 1 <= c_BigInt_MaxBlocks); |
325 | *pResultCur = (tU32)carry; |
326 | pResult->m_length = lhs.m_length + 1; |
327 | } |
328 | else |
329 | { |
330 | pResult->m_length = lhs.m_length; |
331 | } |
332 | } |
333 | |
334 | |
335 | |
336 | |
337 | static void BigInt_Multiply2(tBigInt * pResult, const tBigInt &in) |
338 | { |
339 | |
340 | tU32 carry = 0; |
341 | |
342 | tU32 *pResultCur = pResult->m_blocks; |
343 | const tU32 *pLhsCur = in.m_blocks; |
344 | const tU32 *pLhsEnd = in.m_blocks + in.m_length; |
345 | for ( ; pLhsCur != pLhsEnd; ++pLhsCur, ++pResultCur ) |
346 | { |
347 | tU32 cur = *pLhsCur; |
348 | *pResultCur = (cur << 1) | carry; |
349 | carry = cur >> 31; |
350 | } |
351 | |
352 | if (carry != 0) |
353 | { |
354 | |
355 | RJ_ASSERT(in.m_length + 1 <= c_BigInt_MaxBlocks); |
356 | *pResultCur = carry; |
357 | pResult->m_length = in.m_length + 1; |
358 | } |
359 | else |
360 | { |
361 | pResult->m_length = in.m_length; |
362 | } |
363 | } |
364 | |
365 | |
366 | |
367 | |
368 | static void BigInt_Multiply2(tBigInt * pResult) |
369 | { |
370 | |
371 | tU32 carry = 0; |
372 | |
373 | tU32 *pCur = pResult->m_blocks; |
374 | tU32 *pEnd = pResult->m_blocks + pResult->m_length; |
375 | for ( ; pCur != pEnd; ++pCur ) |
376 | { |
377 | tU32 cur = *pCur; |
378 | *pCur = (cur << 1) | carry; |
379 | carry = cur >> 31; |
380 | } |
381 | |
382 | if (carry != 0) |
383 | { |
384 | |
385 | RJ_ASSERT(pResult->m_length + 1 <= c_BigInt_MaxBlocks); |
386 | *pCur = carry; |
387 | ++pResult->m_length; |
388 | } |
389 | } |
390 | |
391 | |
392 | |
393 | |
394 | static void BigInt_Multiply10(tBigInt * pResult) |
395 | { |
396 | |
397 | tU64 carry = 0; |
398 | |
399 | tU32 *pCur = pResult->m_blocks; |
400 | tU32 *pEnd = pResult->m_blocks + pResult->m_length; |
401 | for ( ; pCur != pEnd; ++pCur ) |
| 14 | | Loop condition is false. Execution continues on line 408 | |
|
402 | { |
403 | tU64 product = (tU64)(*pCur) * 10ull + carry; |
404 | (*pCur) = (tU32)(product & 0xFFFFFFFF); |
405 | carry = product >> 32; |
406 | } |
407 | |
408 | if (carry != 0) |
| |
409 | { |
410 | |
411 | RJ_ASSERT(pResult->m_length + 1 <= c_BigInt_MaxBlocks); |
412 | *pCur = (tU32)carry; |
413 | ++pResult->m_length; |
414 | } |
415 | } |
416 | |
417 | |
418 | |
419 | static tU32 g_PowerOf10_U32[] = |
420 | { |
421 | 1, |
422 | 10, |
423 | 100, |
424 | 1000, |
425 | 10000, |
426 | 100000, |
427 | 1000000, |
428 | 10000000, |
429 | }; |
430 | |
431 | |
432 | |
433 | |
434 | |
435 | |
436 | |
437 | |
438 | static tBigInt g_PowerOf10_Big[] = |
439 | { |
440 | |
441 | { 1, { 100000000 } }, |
442 | |
443 | { 2, { 0x6fc10000, 0x002386f2 } }, |
444 | |
445 | { 4, { 0x00000000, 0x85acef81, 0x2d6d415b, 0x000004ee, } }, |
446 | |
447 | { 7, { 0x00000000, 0x00000000, 0xbf6a1f01, 0x6e38ed64, 0xdaa797ed, 0xe93ff9f4, 0x00184f03, } }, |
448 | |
449 | { 14, { 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x2e953e01, 0x03df9909, 0x0f1538fd, |
450 | 0x2374e42f, 0xd3cff5ec, 0xc404dc08, 0xbccdb0da, 0xa6337f19, 0xe91f2603, 0x0000024e, |
451 | } |
452 | }, |
453 | |
454 | { 27, { 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, |
455 | 0x00000000, 0x982e7c01, 0xbed3875b, 0xd8d99f72, 0x12152f87, 0x6bde50c6, 0xcf4a6e70, |
456 | 0xd595d80f, 0x26b2716e, 0xadc666b0, 0x1d153624, 0x3c42d35a, 0x63ff540e, 0xcc5573c0, |
457 | 0x65f9ef17, 0x55bc28f2, 0x80dcc7f7, 0xf46eeddc, 0x5fdcefce, 0x000553f7, |
458 | } |
459 | } |
460 | }; |
461 | |
462 | |
463 | |
464 | |
465 | static void BigInt_Pow10(tBigInt * pResult, tU32 exponent) |
466 | { |
467 | |
468 | RJ_ASSERT(exponent < 512); |
469 | |
470 | |
471 | tBigInt temp1; |
472 | tBigInt temp2; |
473 | tBigInt *pCurTemp = &temp1; |
474 | tBigInt *pNextTemp = &temp2; |
475 | |
476 | |
477 | tU32 smallExponent = exponent & 0x7; |
478 | pCurTemp->SetU32(g_PowerOf10_U32[smallExponent]); |
479 | |
480 | |
481 | exponent >>= 3; |
482 | tU32 tableIdx = 0; |
483 | |
484 | |
485 | while (exponent != 0) |
486 | { |
487 | |
488 | if(exponent & 1) |
489 | { |
490 | |
491 | BigInt_Multiply( pNextTemp, *pCurTemp, g_PowerOf10_Big[tableIdx] ); |
492 | |
493 | |
494 | tBigInt * pSwap = pCurTemp; |
495 | pCurTemp = pNextTemp; |
496 | pNextTemp = pSwap; |
497 | } |
498 | |
499 | |
500 | ++tableIdx; |
501 | exponent >>= 1; |
502 | } |
503 | |
504 | |
505 | *pResult = *pCurTemp; |
506 | } |
507 | |
508 | |
509 | |
510 | |
511 | static void BigInt_MultiplyPow10(tBigInt * pResult, const tBigInt & in, tU32 exponent) |
512 | { |
513 | |
514 | RJ_ASSERT(exponent < 512); |
515 | |
516 | |
517 | tBigInt temp1; |
518 | tBigInt temp2; |
519 | tBigInt *pCurTemp = &temp1; |
520 | tBigInt *pNextTemp = &temp2; |
521 | |
522 | |
523 | tU32 smallExponent = exponent & 0x7; |
524 | if (smallExponent != 0) |
525 | { |
526 | BigInt_Multiply( pCurTemp, in, g_PowerOf10_U32[smallExponent] ); |
527 | } |
528 | else |
529 | { |
530 | *pCurTemp = in; |
531 | } |
532 | |
533 | |
534 | exponent >>= 3; |
535 | tU32 tableIdx = 0; |
536 | |
537 | |
538 | while (exponent != 0) |
539 | { |
540 | |
541 | if(exponent & 1) |
542 | { |
543 | |
544 | BigInt_Multiply( pNextTemp, *pCurTemp, g_PowerOf10_Big[tableIdx] ); |
545 | |
546 | |
547 | tBigInt * pSwap = pCurTemp; |
548 | pCurTemp = pNextTemp; |
549 | pNextTemp = pSwap; |
550 | } |
551 | |
552 | |
553 | ++tableIdx; |
554 | exponent >>= 1; |
555 | } |
556 | |
557 | |
558 | *pResult = *pCurTemp; |
559 | } |
560 | |
561 | |
562 | |
563 | |
564 | static inline void BigInt_Pow2(tBigInt * pResult, tU32 exponent) |
565 | { |
566 | tU32 blockIdx = exponent / 32; |
567 | RJ_ASSERT( blockIdx < c_BigInt_MaxBlocks ); |
568 | |
569 | for ( tU32 i = 0; i <= blockIdx; ++i) |
570 | pResult->m_blocks[i] = 0; |
571 | |
572 | pResult->m_length = blockIdx + 1; |
573 | |
574 | tU32 bitIdx = (exponent % 32); |
575 | pResult->m_blocks[blockIdx] |= (1 << bitIdx); |
576 | } |
577 | |
578 | |
579 | |
580 | |
581 | |
582 | |
583 | |
584 | |
585 | |
586 | |
587 | |
588 | |
589 | |
590 | |
591 | |
592 | |
593 | |
594 | static tU32 BigInt_DivideWithRemainder_MaxQuotient9(tBigInt * pDividend, const tBigInt & divisor) |
595 | { |
596 | |
597 | |
598 | RJ_ASSERT( !divisor.IsZero() && |
599 | divisor.m_blocks[divisor.m_length-1] >= 8 && |
600 | divisor.m_blocks[divisor.m_length-1] < 0xFFFFFFFF && |
601 | pDividend->m_length <= divisor.m_length ); |
602 | |
603 | |
604 | |
605 | tU32 length = divisor.m_length; |
606 | if (pDividend->m_length < divisor.m_length) |
| |
607 | return 0; |
608 | |
609 | const tU32 * pFinalDivisorBlock = divisor.m_blocks + length - 1; |
610 | tU32 * pFinalDividendBlock = pDividend->m_blocks + length - 1; |
611 | |
612 | |
613 | |
614 | tU32 quotient = *pFinalDividendBlock / (*pFinalDivisorBlock + 1); |
615 | RJ_ASSERT(quotient <= 9); |
616 | |
617 | |
618 | if (quotient != 0) |
| 35 | | Assuming 'quotient' is equal to 0 | |
|
| |
619 | { |
620 | |
621 | const tU32 *pDivisorCur = divisor.m_blocks; |
622 | tU32 *pDividendCur = pDividend->m_blocks; |
623 | |
624 | tU64 borrow = 0; |
625 | tU64 carry = 0; |
626 | do |
627 | { |
628 | tU64 product = (tU64)*pDivisorCur * (tU64)quotient + carry; |
629 | carry = product >> 32; |
630 | |
631 | tU64 difference = (tU64)*pDividendCur - (product & 0xFFFFFFFF) - borrow; |
632 | borrow = (difference >> 32) & 1; |
633 | |
634 | *pDividendCur = difference & 0xFFFFFFFF; |
635 | |
636 | ++pDivisorCur; |
637 | ++pDividendCur; |
638 | } while(pDivisorCur <= pFinalDivisorBlock); |
639 | |
640 | |
641 | while (length > 0 && pDividend->m_blocks[length - 1] == 0) |
642 | --length; |
643 | |
644 | pDividend->m_length = length; |
645 | } |
646 | |
647 | |
648 | |
649 | if ( BigInt_Compare(*pDividend, divisor) >= 0 ) |
| |
650 | { |
651 | ++quotient; |
652 | |
653 | |
654 | const tU32 *pDivisorCur = divisor.m_blocks; |
655 | tU32 *pDividendCur = pDividend->m_blocks; |
656 | |
657 | tU64 borrow = 0; |
658 | do |
| 38 | | Loop condition is true. Execution continues on line 660 | |
|
659 | { |
660 | tU64 difference = (tU64)*pDividendCur - (tU64)*pDivisorCur - borrow; |
| 39 | | The left operand of '-' is a garbage value |
|
661 | borrow = (difference >> 32) & 1; |
662 | |
663 | *pDividendCur = difference & 0xFFFFFFFF; |
664 | |
665 | ++pDivisorCur; |
666 | ++pDividendCur; |
667 | } while(pDivisorCur <= pFinalDivisorBlock); |
668 | |
669 | |
670 | while (length > 0 && pDividend->m_blocks[length - 1] == 0) |
671 | --length; |
672 | |
673 | pDividend->m_length = length; |
674 | } |
675 | |
676 | return quotient; |
677 | } |
678 | |
679 | |
680 | |
681 | |
682 | static void BigInt_ShiftLeft(tBigInt * pResult, tU32 shift) |
683 | { |
684 | RJ_ASSERT( shift != 0 ); |
685 | |
686 | tU32 shiftBlocks = shift / 32; |
687 | tU32 shiftBits = shift % 32; |
688 | |
689 | |
690 | const tU32 * pInBlocks = pResult->m_blocks; |
691 | tS32 inLength = pResult->m_length; |
692 | RJ_ASSERT( inLength + shiftBlocks < c_BigInt_MaxBlocks ); |
693 | |
694 | |
695 | if (shiftBits == 0) |
| |
696 | { |
697 | |
698 | for (tU32 * pInCur = pResult->m_blocks + inLength, *pOutCur = pInCur + shiftBlocks; |
699 | pInCur >= pInBlocks; |
700 | --pInCur, --pOutCur) |
701 | { |
702 | *pOutCur = *pInCur; |
703 | } |
704 | |
705 | |
706 | for ( tU32 i = 0; i < shiftBlocks; ++i) |
707 | pResult->m_blocks[i] = 0; |
708 | |
709 | pResult->m_length += shiftBlocks; |
710 | } |
711 | |
712 | else |
713 | { |
714 | tS32 inBlockIdx = inLength - 1; |
715 | tU32 outBlockIdx = inLength + shiftBlocks; |
716 | |
717 | |
718 | RJ_ASSERT( outBlockIdx < c_BigInt_MaxBlocks ); |
719 | pResult->m_length = outBlockIdx + 1; |
720 | |
721 | |
722 | const tU32 lowBitsShift = (32 - shiftBits); |
723 | tU32 highBits = 0; |
724 | tU32 block = pResult->m_blocks[inBlockIdx]; |
725 | tU32 lowBits = block >> lowBitsShift; |
726 | while ( inBlockIdx > 0 ) |
| 26 | | Loop condition is false. Execution continues on line 740 | |
|
727 | { |
728 | pResult->m_blocks[outBlockIdx] = highBits | lowBits; |
729 | highBits = block << shiftBits; |
730 | |
731 | --inBlockIdx; |
732 | --outBlockIdx; |
733 | |
734 | block = pResult->m_blocks[inBlockIdx]; |
735 | lowBits = block >> lowBitsShift; |
736 | } |
737 | |
738 | |
739 | RJ_ASSERT( outBlockIdx == shiftBlocks + 1 ); |
740 | pResult->m_blocks[outBlockIdx] = highBits | lowBits; |
741 | pResult->m_blocks[outBlockIdx-1] = block << shiftBits; |
742 | |
743 | |
744 | for ( tU32 i = 0; i < shiftBlocks; ++i) |
| 27 | | Loop condition is false. Execution continues on line 748 | |
|
745 | pResult->m_blocks[i] = 0; |
746 | |
747 | |
748 | if (pResult->m_blocks[pResult->m_length - 1] == 0) |
| |
749 | --pResult->m_length; |
750 | } |
751 | } |
752 | |
753 | |
754 | |
755 | |
756 | |
757 | |
758 | |
759 | |
760 | |
761 | |
762 | |
763 | |
764 | |
765 | |
766 | |
767 | |
768 | |
769 | tU32 Dragon4 |
770 | ( |
771 | const tU64 mantissa, |
772 | const tS32 exponent, |
773 | const tU32 mantissaHighBitIdx, |
774 | const tB hasUnequalMargins, |
775 | const tCutoffMode cutoffMode, |
776 | tU32 cutoffNumber, |
777 | tC8 * pOutBuffer, |
778 | tU32 bufferSize, |
779 | tS32 * pOutExponent |
780 | ) |
781 | { |
782 | tC8 * pCurDigit = pOutBuffer; |
783 | |
784 | RJ_ASSERT( bufferSize > 0 ); |
785 | |
786 | |
787 | if (mantissa == 0) |
| 1 | Assuming 'mantissa' is not equal to 0 | |
|
| |
788 | { |
789 | *pCurDigit = '0'; |
790 | *pOutExponent = 0; |
791 | return 1; |
792 | } |
793 | |
794 | |
795 | |
796 | |
797 | tBigInt scale; |
798 | |
799 | tBigInt scaledValue; |
800 | tBigInt scaledMarginLow; |
801 | |
802 | |
803 | |
804 | |
805 | |
806 | tBigInt * pScaledMarginHigh; |
807 | tBigInt optionalMarginHigh; |
808 | |
809 | if ( hasUnequalMargins ) |
| 3 | | Assuming 'hasUnequalMargins' is 0 | |
|
| |
810 | { |
811 | |
812 | if (exponent > 0) |
813 | { |
814 | |
815 | |
816 | |
817 | |
818 | |
819 | |
820 | |
821 | scaledValue.SetU64( 4 * mantissa ); |
822 | BigInt_ShiftLeft( &scaledValue, exponent ); |
823 | |
824 | |
825 | scale.SetU32( 4 ); |
826 | |
827 | |
828 | BigInt_Pow2( &scaledMarginLow, exponent ); |
829 | |
830 | |
831 | BigInt_Pow2( &optionalMarginHigh, exponent + 1 ); |
832 | } |
833 | |
834 | else |
835 | { |
836 | |
837 | |
838 | |
839 | scaledValue.SetU64( 4 * mantissa ); |
840 | |
841 | |
842 | BigInt_Pow2(&scale, -exponent + 2 ); |
843 | |
844 | |
845 | scaledMarginLow.SetU32( 1 ); |
846 | |
847 | |
848 | optionalMarginHigh.SetU32( 2 ); |
849 | } |
850 | |
851 | |
852 | pScaledMarginHigh = &optionalMarginHigh; |
853 | } |
854 | else |
855 | { |
856 | |
857 | if (exponent > 0) |
| 5 | | Assuming 'exponent' is <= 0 | |
|
| |
858 | { |
859 | |
860 | |
861 | |
862 | |
863 | |
864 | |
865 | |
866 | scaledValue.SetU64( 2 * mantissa ); |
867 | BigInt_ShiftLeft( &scaledValue, exponent ); |
868 | |
869 | |
870 | scale.SetU32( 2 ); |
871 | |
872 | |
873 | BigInt_Pow2( &scaledMarginLow, exponent ); |
874 | } |
875 | |
876 | else |
877 | { |
878 | |
879 | |
880 | |
881 | scaledValue.SetU64( 2 * mantissa ); |
882 | |
883 | |
884 | BigInt_Pow2(&scale, -exponent + 1 ); |
885 | |
886 | |
887 | scaledMarginLow.SetU32( 1 ); |
888 | } |
889 | |
890 | |
891 | pScaledMarginHigh = &scaledMarginLow; |
892 | } |
893 | |
894 | |
895 | |
896 | |
897 | |
898 | |
899 | |
900 | |
901 | |
902 | |
903 | |
904 | |
905 | |
906 | |
907 | |
908 | |
909 | const tF64 log10_2 = 0.30102999566398119521373889472449; |
910 | tS32 digitExponent = (tS32)(ceil(tF64((tS32)mantissaHighBitIdx + exponent) * log10_2 - 0.69)); |
911 | |
912 | |
913 | |
914 | |
915 | |
916 | |
917 | if (cutoffMode == CutoffMode_FractionLength && digitExponent <= -(tS32)cutoffNumber) |
| 7 | | Assuming 'cutoffMode' is not equal to CutoffMode_FractionLength | |
|
918 | { |
919 | digitExponent = -(tS32)cutoffNumber + 1; |
920 | } |
921 | |
922 | |
923 | if (digitExponent > 0) |
| 8 | | Assuming 'digitExponent' is <= 0 | |
|
| |
924 | { |
925 | |
926 | tBigInt temp; |
927 | BigInt_MultiplyPow10( &temp, scale, digitExponent ); |
928 | scale = temp; |
929 | } |
930 | else if (digitExponent < 0) |
| 10 | | Assuming 'digitExponent' is >= 0 | |
|
| |
931 | { |
932 | |
933 | |
934 | tBigInt pow10; |
935 | BigInt_Pow10( &pow10, -digitExponent); |
936 | |
937 | tBigInt temp; |
938 | BigInt_Multiply( &temp, scaledValue, pow10); |
939 | scaledValue = temp; |
940 | |
941 | BigInt_Multiply( &temp, scaledMarginLow, pow10); |
942 | scaledMarginLow = temp; |
943 | |
944 | if (pScaledMarginHigh != &scaledMarginLow) |
945 | BigInt_Multiply2( pScaledMarginHigh, scaledMarginLow ); |
946 | } |
947 | |
948 | |
949 | tBigInt scaledValueHigh; |
950 | BigInt_Add( &scaledValueHigh, scaledValue, *pScaledMarginHigh ); |
951 | if( BigInt_Compare(scaledValueHigh,scale) >= 0 ) |
| |
952 | { |
953 | |
954 | |
955 | |
956 | digitExponent = digitExponent + 1; |
957 | } |
958 | else |
959 | { |
960 | |
961 | |
962 | BigInt_Multiply10( &scaledValue ); |
| 13 | | Calling 'BigInt_Multiply10' | |
|
| 16 | | Returning from 'BigInt_Multiply10' | |
|
963 | BigInt_Multiply10( &scaledMarginLow ); |
964 | if (pScaledMarginHigh != &scaledMarginLow) |
| |
965 | BigInt_Multiply2( pScaledMarginHigh, scaledMarginLow ); |
966 | } |
967 | |
968 | |
969 | |
970 | tS32 cutoffExponent = digitExponent - bufferSize; |
971 | switch(cutoffMode) |
| 18 | | Control jumps to 'case CutoffMode_TotalLength:' at line 978 | |
|
972 | { |
973 | |
974 | case CutoffMode_Unique: |
975 | break; |
976 | |
977 | |
978 | case CutoffMode_TotalLength: |
979 | { |
980 | tS32 desiredCutoffExponent = digitExponent - (tS32)cutoffNumber; |
981 | if (desiredCutoffExponent > cutoffExponent) |
| |
982 | cutoffExponent = desiredCutoffExponent; |
983 | } |
984 | break; |
| 20 | | Execution continues on line 997 | |
|
985 | |
986 | |
987 | case CutoffMode_FractionLength: |
988 | { |
989 | tS32 desiredCutoffExponent = -(tS32)cutoffNumber; |
990 | if (desiredCutoffExponent > cutoffExponent) |
991 | cutoffExponent = desiredCutoffExponent; |
992 | } |
993 | break; |
994 | } |
995 | |
996 | |
997 | *pOutExponent = digitExponent-1; |
998 | |
999 | |
1000 | |
1001 | |
1002 | |
1003 | |
1004 | |
1005 | |
1006 | RJ_ASSERT( scale.GetLength() > 0 ); |
1007 | tU32 hiBlock = scale.GetBlock( scale.GetLength() - 1 ); |
1008 | if (hiBlock < 8 || hiBlock > 429496729) |
| 21 | | Assuming 'hiBlock' is >= 8 | |
|
| 22 | | Assuming 'hiBlock' is > 429496729 | |
|
| |
1009 | { |
1010 | |
1011 | |
1012 | |
1013 | |
1014 | |
1015 | |
1016 | tU32 hiBlockLog2 = LogBase2(hiBlock); |
1017 | RJ_ASSERT(hiBlockLog2 < 3 || hiBlockLog2 > 27); |
1018 | tU32 shift = (32 + 27 - hiBlockLog2) % 32; |
1019 | |
1020 | BigInt_ShiftLeft( &scale, shift ); |
1021 | BigInt_ShiftLeft( &scaledValue, shift); |
| 24 | | Calling 'BigInt_ShiftLeft' | |
|
| 29 | | Returning from 'BigInt_ShiftLeft' | |
|
1022 | BigInt_ShiftLeft( &scaledMarginLow, shift); |
1023 | if (pScaledMarginHigh != &scaledMarginLow) |
| |
1024 | BigInt_Multiply2( pScaledMarginHigh, scaledMarginLow ); |
1025 | } |
1026 | |
1027 | |
1028 | |
1029 | tB low; |
1030 | tB high; |
1031 | tU32 outputDigit; |
1032 | |
1033 | if (cutoffMode == CutoffMode_Unique) |
| |
1034 | { |
1035 | |
1036 | |
1037 | |
1038 | for (;;) |
1039 | { |
1040 | digitExponent = digitExponent-1; |
1041 | |
1042 | |
1043 | outputDigit = BigInt_DivideWithRemainder_MaxQuotient9(&scaledValue, scale); |
1044 | RJ_ASSERT( outputDigit < 10 ); |
1045 | |
1046 | |
1047 | BigInt_Add( &scaledValueHigh, scaledValue, *pScaledMarginHigh ); |
1048 | |
1049 | |
1050 | |
1051 | low = BigInt_Compare(scaledValue, scaledMarginLow) < 0; |
1052 | high = BigInt_Compare(scaledValueHigh, scale) > 0; |
1053 | if (low | high | (digitExponent == cutoffExponent)) |
1054 | break; |
1055 | |
1056 | |
1057 | *pCurDigit = (tC8)('0' + outputDigit); |
1058 | ++pCurDigit; |
1059 | |
1060 | |
1061 | BigInt_Multiply10( &scaledValue ); |
1062 | BigInt_Multiply10( &scaledMarginLow ); |
1063 | if (pScaledMarginHigh != &scaledMarginLow) |
1064 | BigInt_Multiply2( pScaledMarginHigh, scaledMarginLow ); |
1065 | } |
1066 | } |
1067 | else |
1068 | { |
1069 | |
1070 | |
1071 | |
1072 | low = false; |
1073 | high = false; |
1074 | |
1075 | for (;;) |
| 32 | | Loop condition is true. Entering loop body | |
|
1076 | { |
1077 | digitExponent = digitExponent-1; |
1078 | |
1079 | |
1080 | outputDigit = BigInt_DivideWithRemainder_MaxQuotient9(&scaledValue, scale); |
| 33 | | Calling 'BigInt_DivideWithRemainder_MaxQuotient9' | |
|
1081 | RJ_ASSERT( outputDigit < 10 ); |
1082 | |
1083 | if ( scaledValue.IsZero() | (digitExponent == cutoffExponent) ) |
1084 | break; |
1085 | |
1086 | |
1087 | *pCurDigit = (tC8)('0' + outputDigit); |
1088 | ++pCurDigit; |
1089 | |
1090 | |
1091 | BigInt_Multiply10(&scaledValue); |
1092 | } |
1093 | } |
1094 | |
1095 | |
1096 | |
1097 | tB roundDown = low; |
1098 | |
1099 | |
1100 | if (low == high) |
1101 | { |
1102 | |
1103 | |
1104 | |
1105 | |
1106 | |
1107 | BigInt_Multiply2(&scaledValue); |
1108 | tS32 compare = BigInt_Compare(scaledValue, scale); |
1109 | roundDown = compare < 0; |
1110 | |
1111 | |
1112 | if (compare == 0) |
1113 | roundDown = (outputDigit & 1) == 0; |
1114 | } |
1115 | |
1116 | |
1117 | if (roundDown) |
1118 | { |
1119 | *pCurDigit = (tC8)('0' + outputDigit); |
1120 | ++pCurDigit; |
1121 | } |
1122 | else |
1123 | { |
1124 | |
1125 | if (outputDigit == 9) |
1126 | { |
1127 | |
1128 | for (;;) |
1129 | { |
1130 | |
1131 | if (pCurDigit == pOutBuffer) |
1132 | { |
1133 | |
1134 | *pCurDigit = '1'; |
1135 | ++pCurDigit; |
1136 | *pOutExponent += 1; |
1137 | break; |
1138 | } |
1139 | |
1140 | --pCurDigit; |
1141 | if (*pCurDigit != '9') |
1142 | { |
1143 | |
1144 | *pCurDigit += 1; |
1145 | ++pCurDigit; |
1146 | break; |
1147 | } |
1148 | } |
1149 | } |
1150 | else |
1151 | { |
1152 | |
1153 | *pCurDigit = (tC8)('0' + outputDigit + 1); |
1154 | ++pCurDigit; |
1155 | } |
1156 | } |
1157 | |
1158 | |
1159 | RJ_ASSERT(pCurDigit - pOutBuffer <= (tPtrDiff)bufferSize); |
1160 | return pCurDigit - pOutBuffer; |
1161 | } |