Debian Codegraph @

extern/ttmath/ttmathint.h

raw
1 /*
2 * This file is a part of TTMath Bignum Library
3 * and is distributed under the (new) BSD licence.
4 * Author: Tomasz Sowa <[email protected]>
5 */
6
7 /*
8 * Copyright (c) 2006-2011, Tomasz Sowa
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions are met:
13 *
14 * * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 *
17 * * Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 *
21 * * Neither the name Tomasz Sowa nor the names of contributors to this
22 * project may be used to endorse or promote products derived
23 * from this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
35 * THE POSSIBILITY OF SUCH DAMAGE.
36 */
37
38
39
40 #ifndef headerfilettmathint
41 #define headerfilettmathint
42
43 /*!
44 \file ttmathint.h
45 \brief template class Int<uint>
46 */
47
48 #include "ttmathuint.h"
49
50 namespace ttmath
51 {
52
53
54 /*!
55 \brief Int implements a big integer value with a sign
56
57 value_size - how many bytes specify our value
58 on 32bit platforms: value_size=1 -> 4 bytes -> 32 bits
59 on 64bit platforms: value_size=1 -> 8 bytes -> 64 bits
60 value_size = 1,2,3,4,5,6....
61 */
62 template<uint value_size>
63 class Int : public UInt<value_size>
64 {
65 public:
66
67 /*!
68 this method sets the max value which this class can hold
69 (all bits will be one besides the last one)
70 */
71 void SetMax()
72 {
73 UInt<value_size>::SetMax();
74 UInt<value_size>::table[value_size-1] = ~ TTMATH_UINT_HIGHEST_BIT;
75 }
76
77
78 /*!
79 this method sets the min value which this class can hold
80 (all bits will be zero besides the last one which is one)
81 */
82 void SetMin()
83 {
84 UInt<value_size>::SetZero();
85 UInt<value_size>::table[value_size-1] = TTMATH_UINT_HIGHEST_BIT;
86 }
87
88
89 /*!
90 this method sets -1 as the value
91 (-1 is equal the max value in an unsigned type)
92 */
93 void SetSignOne()
94 {
95 UInt<value_size>::SetMax();
96 }
97
98
99 /*!
100 we change the sign of the value
101
102 if it isn't possible to change the sign this method returns 1
103 else return 0 and changing the sign
104 */
105 uint ChangeSign()
106 {
107 /*
108 if the value is equal that one which has been returned from SetMin
109 (only the highest bit is set) that means we can't change sign
110 because the value is too big (bigger about one)
111
112 e.g. when value_size = 1 and value is -2147483648 we can't change it to the
113 2147483648 because the max value which can be held is 2147483647
114
115 we don't change the value and we're using this fact somewhere in some methods
116 (if we look on our value without the sign we get the correct value
117 eg. -2147483648 in Int<1> will be 2147483648 on the UInt<1> type)
118 */
119 if( UInt<value_size>::IsOnlyTheHighestBitSet() )
120 return 1;
121
122 UInt<value_size> temp(*this);
123 UInt<value_size>::SetZero();
124 UInt<value_size>::Sub(temp);
125
126 return 0;
127 }
128
129
130
131 /*!
132 this method sets the sign
133
134 e.g. 1 -> -1
135 -2 -> -2
136
137 from a positive value we make a negative value,
138 if the value is negative we do nothing
139 */
140 void SetSign()
141 {
142 if( IsSign() )
143 return;
144
145 ChangeSign();
146 }
147
148
149
150 /*!
151 this method returns true if there's the sign
152
153 (the highest bit will be converted to the bool)
154 */
155 bool IsSign() const
156 {
157 return UInt<value_size>::IsTheHighestBitSet();
158 }
159
160
161
162 /*!
163 it sets an absolute value
164
165 it can return carry (1) (look on ChangeSign() for details)
166 */
167 uint Abs()
168 {
169 if( !IsSign() )
170 return 0;
171
172 return ChangeSign();
173 }
174
175
176
177
178 /*!
179 *
180 * basic mathematic functions
181 *
182 */
183
184 private:
185
186 uint CorrectCarryAfterAdding(bool p1_is_sign, bool p2_is_sign)
187 {
188 if( !p1_is_sign && !p2_is_sign )
189 {
190 if( UInt<value_size>::IsTheHighestBitSet() )
191 return 1;
192 }
193
194 if( p1_is_sign && p2_is_sign )
195 {
196 if( ! UInt<value_size>::IsTheHighestBitSet() )
197 return 1;
198 }
199
200 return 0;
201 }
202
203
204 public:
205
206 /*!
207 this method adds two value with a sign and returns a carry
208
209 we're using methods from the base class because values are stored with U2
210 we must only make the carry correction
211
212 this = p1(=this) + p2
213
214 when p1>=0 i p2>=0 carry is set when the highest bit of value is set
215 when p1<0 i p2<0 carry is set when the highest bit of value is clear
216 when p1>=0 i p2<0 carry will never be set
217 when p1<0 i p2>=0 carry will never be set
218 */
219 uint Add(const Int<value_size> & ss2)
220 {
221 bool p1_is_sign = IsSign();
222 bool p2_is_sign = ss2.IsSign();
223
224 UInt<value_size>::Add(ss2);
225
226 return CorrectCarryAfterAdding(p1_is_sign, p2_is_sign);
227 }
228
229
230 /*!
231 this method adds one *unsigned* word (at a specific position)
232 and returns a carry (if it was)
233
234 look at a description in UInt<>::AddInt(...)
235 */
236 uint AddInt(uint value, uint index = 0)
237 {
238 bool p1_is_sign = IsSign();
239
240 UInt<value_size>::AddInt(value, index);
241
242 return CorrectCarryAfterAdding(p1_is_sign, false);
243 }
244
245
246 /*!
247 this method adds two *unsigned* words to the existing value
248 and these words begin on the 'index' position
249
250 index should be equal or smaller than value_size-2 (index <= value_size-2)
251 x1 - lower word, x2 - higher word
252
253 look at a description in UInt<>::AddTwoInts(...)
254 */
255 uint AddTwoInts(uint x2, uint x1, uint index)
256 {
257 bool p1_is_sign = IsSign();
258
259 UInt<value_size>::AddTwoInts(x2, x1, index);
260
261 return CorrectCarryAfterAdding(p1_is_sign, false);
262 }
263
264 private:
265
266 uint CorrectCarryAfterSubtracting(bool p1_is_sign, bool p2_is_sign)
267 {
268 if( !p1_is_sign && p2_is_sign )
269 {
270 if( UInt<value_size>::IsTheHighestBitSet() )
271 return 1;
272 }
273
274 if( p1_is_sign && !p2_is_sign )
275 {
276 if( ! UInt<value_size>::IsTheHighestBitSet() )
277 return 1;
278 }
279
280 return 0;
281 }
282
283 public:
284
285 /*!
286 this method subtracts two values with a sign
287
288 we don't use the previous Add because the method ChangeSign can
289 sometimes return carry
290
291 this = p1(=this) - p2
292
293 when p1>=0 i p2>=0 carry will never be set
294 when p1<0 i p2<0 carry will never be set
295 when p1>=0 i p2<0 carry is set when the highest bit of value is set
296 when p1<0 i p2>=0 carry is set when the highest bit of value is clear
297 */
298 uint Sub(const Int<value_size> & ss2)
299 {
300 bool p1_is_sign = IsSign();
301 bool p2_is_sign = ss2.IsSign();
302
303 UInt<value_size>::Sub(ss2);
304
305 return CorrectCarryAfterSubtracting(p1_is_sign, p2_is_sign);
306 }
307
308
309 /*!
310 this method subtracts one *unsigned* word (at a specific position)
311 and returns a carry (if it was)
312 */
313 uint SubInt(uint value, uint index = 0)
314 {
315 bool p1_is_sign = IsSign();
316
317 UInt<value_size>::SubInt(value, index);
318
319 return CorrectCarryAfterSubtracting(p1_is_sign, false);
320 }
321
322
323 /*!
324 this method adds one to the value and returns carry
325 */
326 uint AddOne()
327 {
328 bool p1_is_sign = IsSign();
329
330 UInt<value_size>::AddOne();
331
332 return CorrectCarryAfterAdding(p1_is_sign, false);
333 }
334
335
336 /*!
337 this method subtracts one from the value and returns carry
338 */
339 uint SubOne()
340 {
341 bool p1_is_sign = IsSign();
342
343 UInt<value_size>::SubOne();
344
345 return CorrectCarryAfterSubtracting(p1_is_sign, false);
346 }
347
348
349 private:
350
351
352 uint CheckMinCarry(bool ss1_is_sign, bool ss2_is_sign)
353 {
354 /*
355 we have to examine the sign of the result now
356 but if the result is with the sign then:
357 1. if the signs were the same that means the result is too big
358 (the result must be without a sign)
359 2. if the signs were different that means if the result
360 is different from that one which has been returned from SetMin()
361 that is carry (result too big) but if the result is equal SetMin()
362 there'll be ok (and the next SetSign will has no effect because
363 the value is actually negative -- look at description of that case
364 in ChangeSign())
365 */
366 if( IsSign() )
367 {
368 if( ss1_is_sign != ss2_is_sign )
369 {
370 /*
371 there can be one case where signs are different and
372 the result will be equal the value from SetMin() (only the highest bit is set)
373 (this situation is ok)
374 */
375 if( !UInt<value_size>::IsOnlyTheHighestBitSet() )
376 return 1;
377 }
378 else
379 {
380 // signs were the same
381 return 1;
382 }
383 }
384
385 return 0;
386 }
387
388
389 public:
390
391
392 /*!
393 multiplication: this = this * ss2
394
395 it can return a carry
396 */
397 uint MulInt(sint ss2)
398 {
399 bool ss1_is_sign, ss2_is_sign;
400 uint c;
401
402 ss1_is_sign = IsSign();
403
404 /*
405 we don't have to check the carry from Abs (values will be correct
406 because next we're using the method MulInt from the base class UInt
407 which is without a sign)
408 */
409 Abs();
410
411 if( ss2 < 0 )
412 {
413 ss2 = -ss2;
414 ss2_is_sign = true;
415 }
416 else
417 {
418 ss2_is_sign = false;
419 }
420
421 c = UInt<value_size>::MulInt((uint)ss2);
422 c += CheckMinCarry(ss1_is_sign, ss2_is_sign);
423
424 if( ss1_is_sign != ss2_is_sign )
425 SetSign();
426
427 return c;
428 }
429
430
431
432 /*!
433 multiplication this = this * ss2
434
435 it returns carry if the result is too big
436 (we're using the method from the base class but we have to make
437 one correction in account of signs)
438 */
439 uint Mul(Int<value_size> ss2)
440 {
441 bool ss1_is_sign, ss2_is_sign;
442 uint c;
443
444 ss1_is_sign = IsSign();
445 ss2_is_sign = ss2.IsSign();
446
447 /*
448 we don't have to check the carry from Abs (values will be correct
449 because next we're using the method Mul from the base class UInt
450 which is without a sign)
451 */
452 Abs();
453 ss2.Abs();
454
455 c = UInt<value_size>::Mul(ss2);
456 c += CheckMinCarry(ss1_is_sign, ss2_is_sign);
457
458 if( ss1_is_sign != ss2_is_sign )
459 SetSign();
460
461 return c;
462 }
463
464
465 /*!
466 division this = this / ss2
467 returned values:
468 0 - ok
469 1 - division by zero
470
471 for example: (result means 'this')
472 20 / 3 --> result: 6 remainder: 2
473 -20 / 3 --> result: -6 remainder: -2
474 20 / -3 --> result: -6 remainder: 2
475 -20 / -3 --> result: 6 remainder: -2
476
477 in other words: this(old) = ss2 * this(new)(result) + remainder
478 */
479 uint Div(Int<value_size> ss2, Int<value_size> * remainder = 0)
480 {
481 bool ss1_is_sign, ss2_is_sign;
482
483 ss1_is_sign = IsSign();
484 ss2_is_sign = ss2.IsSign();
485
486 /*
487 we don't have to test the carry from Abs as well as in Mul
488 */
489 Abs();
490 ss2.Abs();
491
492 uint c = UInt<value_size>::Div(ss2, remainder);
493
494 if( ss1_is_sign != ss2_is_sign )
495 SetSign();
496
497 if( ss1_is_sign && remainder )
498 remainder->SetSign();
499
500 return c;
501 }
502
503 uint Div(const Int<value_size> & ss2, Int<value_size> & remainder)
504 {
505 return Div(ss2, &remainder);
506 }
507
508
509 /*!
510 division this = this / ss2 (ss2 is int)
511 returned values:
512 0 - ok
513 1 - division by zero
514
515 for example: (result means 'this')
516 20 / 3 --> result: 6 remainder: 2
517 -20 / 3 --> result: -6 remainder: -2
518 20 / -3 --> result: -6 remainder: 2
519 -20 / -3 --> result: 6 remainder: -2
520
521 in other words: this(old) = ss2 * this(new)(result) + remainder
522 */
523 uint DivInt(sint ss2, sint * remainder = 0)
524 {
525 bool ss1_is_sign, ss2_is_sign;
526
527 ss1_is_sign = IsSign();
528
529 /*
530 we don't have to test the carry from Abs as well as in Mul
531 */
532 Abs();
533
534 if( ss2 < 0 )
535 {
536 ss2 = -ss2;
537 ss2_is_sign = true;
538 }
539 else
540 {
541 ss2_is_sign = false;
542 }
543
544 uint rem;
545 uint c = UInt<value_size>::DivInt((uint)ss2, &rem);
546
547 if( ss1_is_sign != ss2_is_sign )
548 SetSign();
549
550 if( remainder )
551 {
552 if( ss1_is_sign )
553 *remainder = -sint(rem);
554 else
555 *remainder = sint(rem);
556 }
557
558 return c;
559 }
560
561
562 uint DivInt(sint ss2, sint & remainder)
563 {
564 return DivInt(ss2, &remainder);
565 }
566
567
568 private:
569
570
571 /*!
572 power this = this ^ pow
573 this can be negative
574 pow is >= 0
575 */
576 uint Pow2(const Int<value_size> & pow)
577 {
578 bool was_sign = IsSign();
579 uint c = 0;
580
581 if( was_sign )
582 c += Abs();
583
584 uint c_temp = UInt<value_size>::Pow(pow);
585 if( c_temp > 0 )
586 return c_temp; // c_temp can be: 0, 1 or 2
587
588 if( was_sign && (pow.table[0] & 1) == 1 )
589 // negative value to the power of odd number is negative
590 c += ChangeSign();
591
592 return (c==0)? 0 : 1;
593 }
594
595
596 public:
597
598
599 /*!
600 power this = this ^ pow
601
602 return values:
603 0 - ok
604 1 - carry
605 2 - incorrect arguments 0^0 or 0^(-something)
606 */
607 uint Pow(Int<value_size> pow)
608 {
609 if( !pow.IsSign() )
610 return Pow2(pow);
611
612 if( UInt<value_size>::IsZero() )
613 // if 'pow' is negative then
614 // 'this' must be different from zero
615 return 2;
616
617 if( pow.ChangeSign() )
618 return 1;
619
620 Int<value_size> t(*this);
621 uint c_temp = t.Pow2(pow);
622 if( c_temp > 0 )
623 return c_temp;
624
625 UInt<value_size>::SetOne();
626 if( Div(t) )
627 return 1;
628
629 return 0;
630 }
631
632
633
634 /*!
635 *
636 * convertion methods
637 *
638 */
639 private:
640
641
642 /*!
643 an auxiliary method for converting both from UInt and Int
644 */
645 template<uint argument_size>
646 uint FromUIntOrInt(const UInt<argument_size> & p, bool UInt_type)
647 {
648 uint min_size = (value_size < argument_size)? value_size : argument_size;
649 uint i;
650
651 for(i=0 ; i<min_size ; ++i)
652 UInt<value_size>::table[i] = p.table[i];
653
654
655 if( value_size > argument_size )
656 {
657 uint fill;
658
659 if( UInt_type )
660 fill = 0;
661 else
662 fill = (p.table[argument_size-1] & TTMATH_UINT_HIGHEST_BIT)?
663 TTMATH_UINT_MAX_VALUE : 0;
664
665 // 'this' is longer than 'p'
666 for( ; i<value_size ; ++i)
667 UInt<value_size>::table[i] = fill;
668 }
669 else
670 {
671 uint test = (UInt<value_size>::table[value_size-1] & TTMATH_UINT_HIGHEST_BIT)?
672 TTMATH_UINT_MAX_VALUE : 0;
673
674 if( UInt_type && test!=0 )
675 return 1;
676
677 for( ; i<argument_size ; ++i)
678 if( p.table[i] != test )
679 return 1;
680 }
681
682 return 0;
683 }
684
685 public:
686
687 /*!
688 this method converts an Int<another_size> type into this class
689
690 this operation has mainly sense if the value from p
691 can be held in this type
692
693 it returns a carry if the value 'p' is too big
694 */
695 template<uint argument_size>
696 uint FromInt(const Int<argument_size> & p)
697 {
698 return FromUIntOrInt(p, false);
699 }
700
701
702 /*!
703 this method converts the sint type into this class
704 */
705 uint FromInt(sint value)
706 {
707 uint fill = ( value<0 ) ? TTMATH_UINT_MAX_VALUE : 0;
708
709 for(uint i=1 ; i<value_size ; ++i)
710 UInt<value_size>::table[i] = fill;
711
712 UInt<value_size>::table[0] = uint(value);
713
714 // there'll never be a carry here
715 return 0;
716 }
717
718
719 /*!
720 this method converts UInt<another_size> into this class
721 */
722 template<uint argument_size>
723 uint FromUInt(const UInt<argument_size> & p)
724 {
725 return FromUIntOrInt(p, true);
726 }
727
728
729 /*!
730 this method converts UInt<another_size> into this class
731 */
732 template<uint argument_size>
733 uint FromInt(const UInt<argument_size> & p)
734 {
735 return FromUIntOrInt(p, true);
736 }
737
738
739 /*!
740 this method converts the uint type into this class
741 */
742 uint FromUInt(uint value)
743 {
744 for(uint i=1 ; i<value_size ; ++i)
745 UInt<value_size>::table[i] = 0;
746
747 UInt<value_size>::table[0] = value;
748
749 // there can be a carry here when the size of this value is equal one word
750 // and the 'value' has the highest bit set
751 if( value_size==1 && (value & TTMATH_UINT_HIGHEST_BIT)!=0 )
752 return 1;
753
754 return 0;
755 }
756
757
758 /*!
759 this method converts the uint type into this class
760 */
761 uint FromInt(uint value)
762 {
763 return FromUInt(value);
764 }
765
766
767 /*!
768 the default assignment operator
769 */
770 /* Int<value_size> & operator=(const Int<value_size> & p)
771 {
772 FromInt(p);
773
774 return *this;
775 }
776 */
777
778 /*!
779 this operator converts an Int<another_size> type to this class
780
781 it doesn't return a carry
782 */
783 /* template<uint argument_size>
784 Int<value_size> & operator=(const Int<argument_size> & p)
785 {
786 FromInt(p);
787
788 return *this;
789 }
790 */
791
792 /*!
793 this method converts the sint type to this class
794 */
795 Int<value_size> & operator=(sint i)
796 {
797 FromInt(i);
798
799 return *this;
800 }
801
802
803 /*!
804 a constructor for converting the uint to this class
805 */
806 /* Int(sint i)
807 {
808 FromInt(i);
809 }
810 */
811
812 /*!
813 a copy constructor
814 */
815 /* Int(const Int<value_size> & u)
816 {
817 FromInt(u);
818 }
819 */
820
821 /*!
822 a constructor for copying from another types
823 */
824 /* template<uint argument_size>
825 Int(const Int<argument_size> & u)
826 {
827 // look that 'size' we still set as 'value_size' and not as u.value_size
828 FromInt(u);
829 }
830 */
831
832
833 /*!
834 this operator converts an UInt<another_size> type to this class
835
836 it doesn't return a carry
837 */
838 template<uint argument_size>
839 Int<value_size> & operator=(const UInt<argument_size> & p)
840 {
841 FromUInt(p);
842
843 return *this;
844 }
845
846
847 /*!
848 this method converts the Uint type to this class
849 */
850 Int<value_size> & operator=(uint i)
851 {
852 FromUInt(i);
853
854 return *this;
855 }
856
857
858 /*!
859 a constructor for converting the uint to this class
860 */
861 /* Int(uint i)
862 {
863 FromUInt(i);
864 }
865 */
866
867 /*!
868 a constructor for copying from another types
869 */
870 /* template<uint argument_size>
871 Int(const UInt<argument_size> & u)
872 {
873 // look that 'size' we still set as 'value_size' and not as u.value_size
874 FromUInt(u);
875 }
876 */
877
878
879 #ifdef TTMATH_PLATFORM32
880
881
882 /*!
883 this method converts unsigned 64 bit int type to this class
884 ***this method is created only on a 32bit platform***
885 */
886 uint FromUInt(ulint n)
887 {
888 uint c = UInt<value_size>::FromUInt(n);
889
890 if( c )
891 return 1;
892
893 if( value_size == 1 )
894 return ((UInt<value_size>::table[0] & TTMATH_UINT_HIGHEST_BIT) == 0) ? 0 : 1;
895
896 if( value_size == 2 )
897 return ((UInt<value_size>::table[1] & TTMATH_UINT_HIGHEST_BIT) == 0) ? 0 : 1;
898
899 return 0;
900 }
901
902
903 /*!
904 this method converts unsigned 64 bit int type to this class
905 ***this method is created only on a 32bit platform***
906 */
907 uint FromInt(ulint n)
908 {
909 return FromUInt(n);
910 }
911
912
913 /*!
914 this method converts signed 64 bit int type to this class
915 ***this method is created only on a 32bit platform***
916 */
917 uint FromInt(slint n)
918 {
919 uint mask = (n < 0) ? TTMATH_UINT_MAX_VALUE : 0;
920
921 UInt<value_size>::table[0] = (uint)(ulint)n;
922
923 if( value_size == 1 )
924 {
925 if( uint(ulint(n) >> 32) != mask )
926 return 1;
927
928 return ((UInt<value_size>::table[0] & TTMATH_UINT_HIGHEST_BIT) == (mask & TTMATH_UINT_HIGHEST_BIT)) ? 0 : 1;
929 }
930
931 UInt<value_size>::table[1] = (uint)(ulint(n) >> 32);
932
933 for(uint i=2 ; i<value_size ; ++i)
934 UInt<value_size>::table[i] = mask;
935
936 return 0;
937 }
938
939
940 /*!
941 this operator converts unsigned 64 bit int type to this class
942 ***this operator is created only on a 32bit platform***
943 */
944 Int<value_size> & operator=(ulint n)
945 {
946 FromUInt(n);
947
948 return *this;
949 }
950
951
952 /*!
953 a constructor for converting unsigned 64 bit int to this class
954 ***this constructor is created only on a 32bit platform***
955 */
956 /* Int(ulint n)
957 {
958 FromUInt(n);
959 }
960 */
961
962 /*!
963 this operator converts signed 64 bit int type to this class
964 ***this operator is created only on a 32bit platform***
965 */
966 Int<value_size> & operator=(slint n)
967 {
968 FromInt(n);
969
970 return *this;
971 }
972
973
974 /*!
975 a constructor for converting signed 64 bit int to this class
976 ***this constructor is created only on a 32bit platform***
977 */
978 /* Int(slint n)
979 {
980 FromInt(n);
981 }
982 */
983 #endif
984
985
986
987
988 #ifdef TTMATH_PLATFORM64
989
990 /*!
991 this method converts 32 bit unsigned int type to this class
992 ***this operator is created only on a 64bit platform***
993 */
994 uint FromUInt(unsigned int i)
995 {
996 return FromUInt(uint(i));
997 }
998
999
1000 /*!
1001 this method converts 32 bit unsigned int type to this class
1002 ***this operator is created only on a 64bit platform***
1003 */
1004 uint FromInt(unsigned int i)
1005 {
1006 return FromUInt(i);
1007 }
1008
1009
1010 /*!
1011 this method converts 32 bit signed int type to this class
1012 ***this operator is created only on a 64bit platform***
1013 */
1014 uint FromInt(signed int i)
1015 {
1016 return FromInt(sint(i));
1017 }
1018
1019
1020 /*!
1021 this method converts 32 bit unsigned int type to this class
1022 ***this operator is created only on a 64bit platform***
1023 */
1024 Int<value_size> & operator=(unsigned int i)
1025 {
1026 FromUInt(i);
1027
1028 return *this;
1029 }
1030
1031
1032 /*!
1033 a constructor for converting 32 bit unsigned int to this class
1034 ***this constructor is created only on a 64bit platform***
1035 */
1036 /* Int(unsigned int i)
1037 {
1038 FromUInt(i);
1039 }
1040 */
1041
1042 /*!
1043 this operator converts 32 bit signed int type to this class
1044 ***this operator is created only on a 64bit platform***
1045 */
1046 Int<value_size> & operator=(signed int i)
1047 {
1048 FromInt(i);
1049
1050 return *this;
1051 }
1052
1053
1054 /*!
1055 a constructor for converting 32 bit signed int to this class
1056 ***this constructor is created only on a 64bit platform***
1057 */
1058 /* Int(signed int i)
1059 {
1060 FromInt(i);
1061 }
1062 */
1063 #endif
1064
1065
1066
1067 /*!
1068 a constructor for converting string to this class (with the base=10)
1069 */
1070 /* Int(const char * s)
1071 {
1072 FromString(s);
1073 }
1074 */
1075
1076 /*!
1077 a constructor for converting a string to this class (with the base=10)
1078 */
1079 /* Int(const std::string & s)
1080 {
1081 FromString( s.c_str() );
1082 }
1083 */
1084
1085 #ifndef TTMATH_DONT_USE_WCHAR
1086
1087 /*!
1088 a constructor for converting string to this class (with the base=10)
1089 */
1090 Int(const wchar_t * s)
1091 {
1092 FromString(s);
1093 }
1094
1095
1096 /*!
1097 a constructor for converting a string to this class (with the base=10)
1098 */
1099 Int(const std::wstring & s)
1100 {
1101 FromString( s.c_str() );
1102 }
1103
1104 #endif
1105
1106
1107 /*!
1108 a default constructor
1109
1110 we don't clear table etc.
1111 */
1112 /* Int()
1113 {
1114 }
1115 */
1116
1117 /*!
1118 the destructor
1119 */
1120 /* ~Int()
1121 {
1122 }
1123 */
1124
1125 /*!
1126 this method returns the lowest value from table with a sign
1127
1128 we must be sure when we using this method whether the value
1129 will hold in an sint type or not (the rest value from table must be zero or -1)
1130 */
1131 sint ToInt() const
1132 {
1133 return sint( UInt<value_size>::table[0] );
1134 }
1135
1136
1137 /*!
1138 this method converts the value to uint type
1139 can return a carry if the value is too long to store it in uint type
1140 */
1141 uint ToUInt(uint & result) const
1142 {
1143 uint c = UInt<value_size>::ToUInt(result);
1144
1145 if( value_size == 1 )
1146 return (result & TTMATH_UINT_HIGHEST_BIT) == 0 ? 0 : 1;
1147
1148 return c;
1149 }
1150
1151
1152 /*!
1153 this method converts the value to uint type
1154 can return a carry if the value is too long to store it in uint type
1155 */
1156 uint ToInt(uint & result) const
1157 {
1158 return ToUInt(result);
1159 }
1160
1161
1162 /*!
1163 this method converts the value to sint type
1164 can return a carry if the value is too long to store it in sint type
1165 */
1166 uint ToInt(sint & result) const
1167 {
1168 result = sint( UInt<value_size>::table[0] );
1169 uint mask = IsSign() ? TTMATH_UINT_MAX_VALUE : 0;
1170
1171 if( (result & TTMATH_UINT_HIGHEST_BIT) != (mask & TTMATH_UINT_HIGHEST_BIT) )
1172 return 1;
1173
1174 for(uint i=1 ; i<value_size ; ++i)
1175 if( UInt<value_size>::table[i] != mask )
1176 return 1;
1177
1178 return 0;
1179 }
1180
1181
1182 #ifdef TTMATH_PLATFORM32
1183
1184 /*!
1185 this method converts the value to ulint type (64 bit unsigned integer)
1186 can return a carry if the value is too long to store it in ulint type
1187 *** this method is created only on a 32 bit platform ***
1188 */
1189 uint ToUInt(ulint & result) const
1190 {
1191 uint c = UInt<value_size>::ToUInt(result);
1192
1193 if( value_size == 1 )
1194 return (UInt<value_size>::table[0] & TTMATH_UINT_HIGHEST_BIT) == 0 ? 0 : 1;
1195
1196 if( value_size == 2 )
1197 return (UInt<value_size>::table[1] & TTMATH_UINT_HIGHEST_BIT) == 0 ? 0 : 1;
1198
1199 return c;
1200 }
1201
1202
1203 /*!
1204 this method converts the value to ulint type (64 bit unsigned integer)
1205 can return a carry if the value is too long to store it in ulint type
1206 *** this method is created only on a 32 bit platform ***
1207 */
1208 uint ToInt(ulint & result) const
1209 {
1210 return ToUInt(result);
1211 }
1212
1213
1214 /*!
1215 this method converts the value to slint type (64 bit signed integer)
1216 can return a carry if the value is too long to store it in slint type
1217 *** this method is created only on a 32 bit platform ***
1218 */
1219 uint ToInt(slint & result) const
1220 {
1221 if( value_size == 1 )
1222 {
1223 result = slint(sint(UInt<value_size>::table[0]));
1224 }
1225 else
1226 {
1227 uint low = UInt<value_size>::table[0];
1228 uint high = UInt<value_size>::table[1];
1229
1230 result = low;
1231 result |= (ulint(high) << TTMATH_BITS_PER_UINT);
1232
1233 uint mask = IsSign() ? TTMATH_UINT_MAX_VALUE : 0;
1234
1235 if( (high & TTMATH_UINT_HIGHEST_BIT) != (mask & TTMATH_UINT_HIGHEST_BIT) )
1236 return 1;
1237
1238 for(uint i=2 ; i<value_size ; ++i)
1239 if( UInt<value_size>::table[i] != mask )
1240 return 1;
1241 }
1242
1243 return 0;
1244 }
1245
1246 #endif
1247
1248
1249
1250 #ifdef TTMATH_PLATFORM64
1251
1252 /*!
1253 this method converts the value to a 32 bit unsigned integer
1254 can return a carry if the value is too long to store it in this type
1255 *** this method is created only on a 64 bit platform ***
1256 */
1257 uint ToUInt(unsigned int & result) const
1258 {
1259 uint c = UInt<value_size>::ToUInt(result);
1260
1261 if( c || IsSign() )
1262 return 1;
1263
1264 return 0;
1265 }
1266
1267
1268 /*!
1269 this method converts the value to a 32 bit unsigned integer
1270 can return a carry if the value is too long to store it in this type
1271 *** this method is created only on a 64 bit platform ***
1272 */
1273 uint ToInt(unsigned int & result) const
1274 {
1275 return ToUInt(result);
1276 }
1277
1278
1279 /*!
1280 this method converts the value to a 32 bit signed integer
1281 can return a carry if the value is too long to store it in this type
1282 *** this method is created only on a 64 bit platform ***
1283 */
1284 uint ToInt(int & result) const
1285 {
1286 uint first = UInt<value_size>::table[0];
1287
1288 result = int(first);
1289 uint mask = IsSign() ? TTMATH_UINT_MAX_VALUE : 0;
1290
1291 if( (first >> 31) != (mask >> 31) )
1292 return 1;
1293
1294 for(uint i=1 ; i<value_size ; ++i)
1295 if( UInt<value_size>::table[i] != mask )
1296 return 1;
1297
1298 return 0;
1299 }
1300
1301 #endif
1302
1303
1304
1305 /*!
1306 an auxiliary method for converting to a string
1307 */
1308 template<class string_type>
1309 void ToStringBase(string_type & result, uint b = 10) const
1310 {
1311 if( IsSign() )
1312 {
1313 Int<value_size> temp(*this);
1314 temp.Abs();
1315 temp.UInt<value_size>::ToStringBase(result, b, true);
1316 }
1317 else
1318 {
1319 UInt<value_size>::ToStringBase(result, b, false);
1320 }
1321 }
1322
1323 /*!
1324 this method converts the value to a string with a base equal 'b'
1325 */
1326 void ToString(std::string & result, uint b = 10) const
1327 {
1328 return ToStringBase(result, b);
1329 }
1330
1331
1332 /*!
1333 this method converts the value to a string with a base equal 'b'
1334 */
1335 std::string ToString(uint b = 10) const
1336 {
1337 std::string result;
1338 ToStringBase(result, b);
1339
1340 return result;
1341 }
1342
1343
1344 #ifndef TTMATH_DONT_USE_WCHAR
1345
1346 /*!
1347 this method converts the value to a string with a base equal 'b'
1348 */
1349 void ToString(std::wstring & result, uint b = 10) const
1350 {
1351 return ToStringBase(result, b);
1352 }
1353
1354
1355 /*!
1356 this method converts the value to a string with a base equal 'b'
1357 */
1358 std::wstring ToWString(uint b = 10) const
1359 {
1360 std::wstring result;
1361 ToStringBase(result, b);
1362
1363 return result;
1364 }
1365
1366 #endif
1367
1368
1369
1370 private:
1371
1372 /*!
1373 an auxiliary method for converting from a string
1374 */
1375 template<class char_type>
1376 uint FromStringBase(const char_type * s, uint b = 10, const char_type ** after_source = 0, bool * value_read = 0)
1377 {
1378 bool is_sign = false;
1379
1380 Misc::SkipWhiteCharacters(s);
1381
1382 if( *s == '-' )
1383 {
1384 is_sign = true;
1385 Misc::SkipWhiteCharacters(++s);
1386 }
1387 else
1388 if( *s == '+' )
1389 {
1390 Misc::SkipWhiteCharacters(++s);
1391 }
1392
1393 if( UInt<value_size>::FromString(s,b,after_source,value_read) )
1394 return 1;
1395
1396 if( is_sign )
1397 {
1398 Int<value_size> mmin;
1399
1400 mmin.SetMin();
1401
1402 /*
1403 the reference to mmin will be automatically converted to the reference
1404 to UInt type
1405 (this value can be equal mmin -- look at a description in ChangeSign())
1406 */
1407 if( UInt<value_size>::operator>( mmin ) )
1408 return 1;
1409
1410 /*
1411 if the value is equal mmin the method ChangeSign() does nothing (only returns 1 but we ignore it)
1412 */
1413 ChangeSign();
1414 }
1415 else
1416 {
1417 Int<value_size> mmax;
1418
1419 mmax.SetMax();
1420
1421 if( UInt<value_size>::operator>( mmax ) )
1422 return 1;
1423 }
1424
1425 return 0;
1426 }
1427
1428
1429 public:
1430
1431 /*!
1432 this method converts a string into its value
1433 it returns carry=1 if the value will be too big or an incorrect base 'b' is given
1434
1435 string is ended with a non-digit value, for example:
1436 "-12" will be translated to -12
1437 as well as:
1438 "- 12foo" will be translated to -12 too
1439
1440 existing first white characters will be ommited
1441 (between '-' and a first digit can be white characters too)
1442
1443 after_source (if exists) is pointing at the end of the parsed string
1444
1445 value_read (if exists) tells whether something has actually been read (at least one digit)
1446 */
1447 uint FromString(const char * s, uint b = 10, const char ** after_source = 0, bool * value_read = 0)
1448 {
1449 return FromStringBase(s, b, after_source, value_read);
1450 }
1451
1452
1453 /*!
1454 this method converts a string into its value
1455 */
1456 uint FromString(const wchar_t * s, uint b = 10, const wchar_t ** after_source = 0, bool * value_read = 0)
1457 {
1458 return FromStringBase(s, b, after_source, value_read);
1459 }
1460
1461
1462 /*!
1463 this method converts a string into its value
1464 it returns carry=1 if the value will be too big or an incorrect base 'b' is given
1465 */
1466 uint FromString(const std::string & s, uint b = 10)
1467 {
1468 return FromString( s.c_str(), b );
1469 }
1470
1471
1472 /*!
1473 this operator converts a string into its value (with base = 10)
1474 */
1475 Int<value_size> & operator=(const char * s)
1476 {
1477 FromString(s);
1478
1479 return *this;
1480 }
1481
1482
1483 #ifndef TTMATH_DONT_USE_WCHAR
1484
1485
1486 /*!
1487 this method converts a string into its value
1488 it returns carry=1 if the value will be too big or an incorrect base 'b' is given
1489 */
1490 uint FromString(const std::wstring & s, uint b = 10)
1491 {
1492 return FromString( s.c_str(), b );
1493 }
1494
1495
1496 /*!
1497 this operator converts a string into its value (with base = 10)
1498 */
1499 Int<value_size> & operator=(const wchar_t * s)
1500 {
1501 FromString(s);
1502
1503 return *this;
1504 }
1505
1506
1507 /*!
1508 this operator converts a string into its value (with base = 10)
1509 */
1510 Int<value_size> & operator=(const std::wstring & s)
1511 {
1512 FromString( s.c_str() );
1513
1514 return *this;
1515 }
1516
1517 #endif
1518
1519
1520 /*!
1521 this operator converts a string into its value (with base = 10)
1522 */
1523 Int<value_size> & operator=(const std::string & s)
1524 {
1525 FromString( s.c_str() );
1526
1527 return *this;
1528 }
1529
1530
1531
1532 /*!
1533 *
1534 * methods for comparing
1535 *
1536 *
1537 */
1538
1539 bool operator==(const Int<value_size> & l) const
1540 {
1541 return UInt<value_size>::operator==(l);
1542 }
1543
1544 bool operator!=(const Int<value_size> & l) const
1545 {
1546 return UInt<value_size>::operator!=(l);
1547 }
1548
1549 bool operator<(const Int<value_size> & l) const
1550 {
1551 sint i=value_size-1;
1552
1553 sint a1 = sint(UInt<value_size>::table[i]);
1554 sint a2 = sint(l.table[i]);
1555
1556 if( a1 != a2 )
1557 return a1 < a2;
1558
1559
1560 for(--i ; i>=0 ; --i)
1561 {
1562 if( UInt<value_size>::table[i] != l.table[i] )
1563 // comparison as unsigned int
1564 return UInt<value_size>::table[i] < l.table[i];
1565 }
1566
1567 // they're equal
1568 return false;
1569 }
1570
1571
1572 bool operator>(const Int<value_size> & l) const
1573 {
1574 sint i=value_size-1;
1575
1576 sint a1 = sint(UInt<value_size>::table[i]);
1577 sint a2 = sint(l.table[i]);
1578
1579 if( a1 != a2 )
1580 return a1 > a2;
1581
1582
1583 for(--i ; i>=0 ; --i)
1584 {
1585 if( UInt<value_size>::table[i] != l.table[i] )
1586 // comparison as unsigned int
1587 return UInt<value_size>::table[i] > l.table[i];
1588 }
1589
1590 // they're equal
1591 return false;
1592 }
1593
1594
1595 bool operator<=(const Int<value_size> & l) const
1596 {
1597 sint i=value_size-1;
1598
1599 sint a1 = sint(UInt<value_size>::table[i]);
1600 sint a2 = sint(l.table[i]);
1601
1602 if( a1 != a2 )
1603 return a1 < a2;
1604
1605
1606 for(--i ; i>=0 ; --i)
1607 {
1608 if( UInt<value_size>::table[i] != l.table[i] )
1609 // comparison as unsigned int
1610 return UInt<value_size>::table[i] < l.table[i];
1611 }
1612
1613 // they're equal
1614 return true;
1615 }
1616
1617
1618 bool operator>=(const Int<value_size> & l) const
1619 {
1620 sint i=value_size-1;
1621
1622 sint a1 = sint(UInt<value_size>::table[i]);
1623 sint a2 = sint(l.table[i]);
1624
1625 if( a1 != a2 )
1626 return a1 > a2;
1627
1628
1629 for(--i ; i>=0 ; --i)
1630 {
1631 if( UInt<value_size>::table[i] != l.table[i] )
1632 // comparison as unsigned int
1633 return UInt<value_size>::table[i] > l.table[i];
1634 }
1635
1636 // they're equal
1637 return true;
1638 }
1639
1640
1641
1642 /*!
1643 *
1644 * standard mathematical operators
1645 *
1646 */
1647
1648
1649 /*!
1650 an operator for changing the sign
1651
1652 it's not changing 'this' but the changed value will be returned
1653 */
1654 Int<value_size> operator-() const
1655 {
1656 Int<value_size> temp(*this);
1657
1658 temp.ChangeSign();
1659
1660 return temp;
1661 }
1662
1663
1664 Int<value_size> operator-(const Int<value_size> & p2) const
1665 {
1666 Int<value_size> temp(*this);
1667
1668 temp.Sub(p2);
1669
1670 return temp;
1671 }
1672
1673
1674 Int<value_size> & operator-=(const Int<value_size> & p2)
1675 {
1676 Sub(p2);
1677
1678 return *this;
1679 }
1680
1681
1682 Int<value_size> operator+(const Int<value_size> & p2) const
1683 {
1684 Int<value_size> temp(*this);
1685
1686 temp.Add(p2);
1687
1688 return temp;
1689 }
1690
1691
1692 Int<value_size> & operator+=(const Int<value_size> & p2)
1693 {
1694 Add(p2);
1695
1696 return *this;
1697 }
1698
1699
1700 Int<value_size> operator*(const Int<value_size> & p2) const
1701 {
1702 Int<value_size> temp(*this);
1703
1704 temp.Mul(p2);
1705
1706 return temp;
1707 }
1708
1709
1710 Int<value_size> & operator*=(const Int<value_size> & p2)
1711 {
1712 Mul(p2);
1713
1714 return *this;
1715 }
1716
1717
1718 Int<value_size> operator/(const Int<value_size> & p2) const
1719 {
1720 Int<value_size> temp(*this);
1721
1722 temp.Div(p2);
1723
1724 return temp;
1725 }
1726
1727
1728 Int<value_size> & operator/=(const Int<value_size> & p2)
1729 {
1730 Div(p2);
1731
1732 return *this;
1733 }
1734
1735
1736 Int<value_size> operator%(const Int<value_size> & p2) const
1737 {
1738 Int<value_size> temp(*this);
1739 Int<value_size> remainder;
1740
1741 temp.Div(p2, remainder);
1742
1743 return remainder;
1744 }
1745
1746
1747 Int<value_size> & operator%=(const Int<value_size> & p2)
1748 {
1749 Int<value_size> remainder;
1750
1751 Div(p2, remainder);
1752 operator=(remainder);
1753
1754 return *this;
1755 }
1756
1757
1758 /*!
1759 Prefix operator e.g. ++variable
1760 */
1761 UInt<value_size> & operator++()
1762 {
1763 AddOne();
1764
1765 return *this;
1766 }
1767
1768
1769 /*!
1770 Postfix operator e.g. variable++
1771 */
1772 UInt<value_size> operator++(int)
1773 {
1774 UInt<value_size> temp( *this );
1775
1776 AddOne();
1777
1778 return temp;
1779 }
1780
1781
1782 UInt<value_size> & operator--()
1783 {
1784 SubOne();
1785
1786 return *this;
1787 }
1788
1789
1790 UInt<value_size> operator--(int)
1791 {
1792 UInt<value_size> temp( *this );
1793
1794 SubOne();
1795
1796 return temp;
1797 }
1798
1799
1800 Int<value_size> operator>>(int move) const
1801 {
1802 Int<value_size> temp( *this );
1803
1804 temp.Rcr(move, UInt<value_size>::IsTheHighestBitSet() ? 1 : 0);
1805
1806 return temp;
1807 }
1808
1809
1810 UInt<value_size> & operator>>=(int move)
1811 {
1812 UInt<value_size>::Rcr(move, UInt<value_size>::IsTheHighestBitSet() ? 1 : 0);
1813
1814 return *this;
1815 }
1816
1817
1818
1819 /*!
1820 *
1821 * input/output operators for standard streams
1822 *
1823 */
1824
1825 private:
1826
1827 /*!
1828 an auxiliary method for outputing to standard streams
1829 */
1830 template<class ostream_type, class string_type>
1831 static ostream_type & OutputToStream(ostream_type & s, const Int<value_size> & l)
1832 {
1833 string_type ss;
1834
1835 l.ToString(ss);
1836 s << ss;
1837
1838 return s;
1839 }
1840
1841
1842
1843 public:
1844
1845
1846 /*!
1847 output to standard streams
1848 */
1849 friend std::ostream & operator<<(std::ostream & s, const Int<value_size> & l)
1850 {
1851 return OutputToStream<std::ostream, std::string>(s, l);
1852 }
1853
1854
1855 #ifndef TTMATH_DONT_USE_WCHAR
1856
1857 /*!
1858 output to standard streams
1859 */
1860 friend std::wostream & operator<<(std::wostream & s, const Int<value_size> & l)
1861 {
1862 return OutputToStream<std::wostream, std::wstring>(s, l);
1863 }
1864
1865 #endif
1866
1867
1868
1869 private:
1870
1871 /*!
1872 an auxiliary method for converting from a string
1873 */
1874 template<class istream_type, class string_type, class char_type>
1875 static istream_type & InputFromStream(istream_type & s, Int<value_size> & l)
1876 {
1877 string_type ss;
1878
1879 // char or wchar_t for operator>>
1880 char_type z;
1881
1882 // operator>> omits white characters if they're set for ommiting
1883 s >> z;
1884
1885 if( z=='-' || z=='+' )
1886 {
1887 ss += z;
1888 s >> z; // we're reading a next character (white characters can be ommited)
1889 }
1890
1891 // we're reading only digits (base=10)
1892 while( s.good() && Misc::CharToDigit(z, 10)>=0 )
1893 {
1894 ss += z;
1895 z = static_cast<char_type>(s.get());
1896 }
1897
1898 // we're leaving the last readed character
1899 // (it's not belonging to the value)
1900 s.unget();
1901
1902 l.FromString(ss);
1903
1904 return s;
1905 }
1906
1907
1908 public:
1909
1910 /*!
1911 input from standard streams
1912 */
1913 friend std::istream & operator>>(std::istream & s, Int<value_size> & l)
1914 {
1915 return InputFromStream<std::istream, std::string, char>(s, l);
1916 }
1917
1918
1919 #ifndef TTMATH_DONT_USE_WCHAR
1920
1921 /*!
1922 input from standard streams
1923 */
1924 friend std::wistream & operator>>(std::wistream & s, Int<value_size> & l)
1925 {
1926 return InputFromStream<std::wistream, std::wstring, wchar_t>(s, l);
1927 }
1928 #endif
1929
1930
1931 };
1932
1933 } // namespace
1934
1935 #endif