OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 /** | 5 /** |
6 * An immutable 64-bit signed integer, in the range [-2^63, 2^63 - 1]. | 6 * An immutable 64-bit signed integer, in the range [-2^63, 2^63 - 1]. |
7 * Arithmetic operations may overflow in order to maintain this range. | 7 * Arithmetic operations may overflow in order to maintain this range. |
8 */ | 8 */ |
9 class int64 implements intx { | 9 class int64 implements intx { |
10 | 10 |
(...skipping 348 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
359 c1 += c0 >> _BITS; | 359 c1 += c0 >> _BITS; |
360 c0 &= _MASK; | 360 c0 &= _MASK; |
361 c2 += c1 >> _BITS; | 361 c2 += c1 >> _BITS; |
362 c1 &= _MASK; | 362 c1 &= _MASK; |
363 c2 &= _MASK_2; | 363 c2 &= _MASK_2; |
364 | 364 |
365 return new int64._bits(c0, c1, c2); | 365 return new int64._bits(c0, c1, c2); |
366 } | 366 } |
367 | 367 |
368 int64 operator %(other) { | 368 int64 operator %(other) { |
369 if (other.isZero()) { | 369 if (other.isZero) { |
370 throw new IntegerDivisionByZeroException(); | 370 throw new IntegerDivisionByZeroException(); |
371 } | 371 } |
372 if (this.isZero()) { | 372 if (this.isZero) { |
373 return ZERO; | 373 return ZERO; |
374 } | 374 } |
375 int64 o = _promote(other).abs(); | 375 int64 o = _promote(other).abs(); |
376 _divMod(this, o, true); | 376 _divMod(this, o, true); |
377 return _remainder < 0 ? (_remainder + o) : _remainder; | 377 return _remainder < 0 ? (_remainder + o) : _remainder; |
378 } | 378 } |
379 | 379 |
380 int64 operator ~/(other) => _divMod(this, _promote(other), false); | 380 int64 operator ~/(other) => _divMod(this, _promote(other), false); |
381 | 381 |
382 // int64 remainder(other) => this - (this ~/ other) * other; | 382 // int64 remainder(other) => this - (this ~/ other) * other; |
383 int64 remainder(other) { | 383 int64 remainder(other) { |
384 if (other.isZero()) { | 384 if (other.isZero) { |
385 throw new IntegerDivisionByZeroException(); | 385 throw new IntegerDivisionByZeroException(); |
386 } | 386 } |
387 int64 o = _promote(other).abs(); | 387 int64 o = _promote(other).abs(); |
388 _divMod(this, o, true); | 388 _divMod(this, o, true); |
389 return _remainder; | 389 return _remainder; |
390 } | 390 } |
391 | 391 |
392 int64 operator &(other) { | 392 int64 operator &(other) { |
393 int64 o = _promote(other); | 393 int64 o = _promote(other); |
394 int a0 = _l & o._l; | 394 int a0 = _l & o._l; |
(...skipping 159 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
554 } | 554 } |
555 | 555 |
556 bool operator >(other) { | 556 bool operator >(other) { |
557 return this.compareTo(other) > 0; | 557 return this.compareTo(other) > 0; |
558 } | 558 } |
559 | 559 |
560 bool operator >=(other) { | 560 bool operator >=(other) { |
561 return this.compareTo(other) >= 0; | 561 return this.compareTo(other) >= 0; |
562 } | 562 } |
563 | 563 |
564 bool isEven() => (_l & 0x1) == 0; | 564 bool get isEven => (_l & 0x1) == 0; |
565 bool isMaxValue() => (_h == _MASK_2 >> 1) && _m == _MASK && _l == _MASK; | 565 bool get isMaxValue => (_h == _MASK_2 >> 1) && _m == _MASK && _l == _MASK; |
566 bool isMinValue() => _h == _SIGN_BIT_VALUE && _m == 0 && _l == 0; | 566 bool get isMinValue => _h == _SIGN_BIT_VALUE && _m == 0 && _l == 0; |
567 bool isNegative() => (_h >> (_BITS2 - 1)) != 0; | 567 bool get isNegative => (_h >> (_BITS2 - 1)) != 0; |
568 bool isOdd() => (_l & 0x1) == 1; | 568 bool get isOdd => (_l & 0x1) == 1; |
569 bool isZero() => _h == 0 && _m == 0 && _l == 0; | 569 bool get isZero => _h == 0 && _m == 0 && _l == 0; |
570 | 570 |
571 /** | 571 /** |
572 * Returns a hash code based on all the bits of this [int64]. | 572 * Returns a hash code based on all the bits of this [int64]. |
573 */ | 573 */ |
574 int get hashCode { | 574 int get hashCode { |
575 int bottom = ((_m & 0x3ff) << _BITS) | _l; | 575 int bottom = ((_m & 0x3ff) << _BITS) | _l; |
576 int top = (_h << 12) | ((_m >> 10) & 0xfff); | 576 int top = (_h << 12) | ((_m >> 10) & 0xfff); |
577 return bottom ^ top; | 577 return bottom ^ top; |
578 } | 578 } |
579 | 579 |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
667 * Returns [this]. | 667 * Returns [this]. |
668 */ | 668 */ |
669 int64 toInt64() => this; | 669 int64 toInt64() => this; |
670 | 670 |
671 /** | 671 /** |
672 * Returns the value of this [int64] as a decimal [String]. | 672 * Returns the value of this [int64] as a decimal [String]. |
673 */ | 673 */ |
674 // TODO(rice) - Make this faster by converting several digits at once. | 674 // TODO(rice) - Make this faster by converting several digits at once. |
675 String toString() { | 675 String toString() { |
676 int64 a = this; | 676 int64 a = this; |
677 if (a.isZero()) { | 677 if (a.isZero) { |
678 return "0"; | 678 return "0"; |
679 } | 679 } |
680 if (a.isMinValue()) { | 680 if (a.isMinValue) { |
681 return "-9223372036854775808"; | 681 return "-9223372036854775808"; |
682 } | 682 } |
683 | 683 |
684 String result = ""; | 684 String result = ""; |
685 bool negative = false; | 685 bool negative = false; |
686 if (a.isNegative()) { | 686 if (a.isNegative) { |
687 negative = true; | 687 negative = true; |
688 a = -a; | 688 a = -a; |
689 } | 689 } |
690 | 690 |
691 int64 ten = new int64._bits(10, 0, 0); | 691 int64 ten = new int64._bits(10, 0, 0); |
692 while (!a.isZero()) { | 692 while (!a.isZero) { |
693 a = _divMod(a, ten, true); | 693 a = _divMod(a, ten, true); |
694 result = "${_remainder._l}$result"; | 694 result = "${_remainder._l}$result"; |
695 } | 695 } |
696 if (negative) { | 696 if (negative) { |
697 result = "-$result"; | 697 result = "-$result"; |
698 } | 698 } |
699 return result; | 699 return result; |
700 } | 700 } |
701 | 701 |
702 // TODO(rice) - Make this faster by avoiding arithmetic. | 702 // TODO(rice) - Make this faster by avoiding arithmetic. |
703 String toHexString() { | 703 String toHexString() { |
704 int64 x = new int64._copy(this); | 704 int64 x = new int64._copy(this); |
705 if (isZero()) { | 705 if (isZero) { |
706 return "0"; | 706 return "0"; |
707 } | 707 } |
708 String hexStr = ""; | 708 String hexStr = ""; |
709 int64 digit_f = new int64.fromInt(0xf); | 709 int64 digit_f = new int64.fromInt(0xf); |
710 while (!x.isZero()) { | 710 while (!x.isZero) { |
711 int digit = x._l & 0xf; | 711 int digit = x._l & 0xf; |
712 hexStr = "${_hexDigit(digit)}$hexStr"; | 712 hexStr = "${_hexDigit(digit)}$hexStr"; |
713 x = x.shiftRightUnsigned(4); | 713 x = x.shiftRightUnsigned(4); |
714 } | 714 } |
715 return hexStr; | 715 return hexStr; |
716 } | 716 } |
717 | 717 |
718 String toRadixString(int radix) { | 718 String toRadixString(int radix) { |
719 if ((radix <= 1) || (radix > 16)) { | 719 if ((radix <= 1) || (radix > 16)) { |
720 throw "Bad radix: $radix"; | 720 throw "Bad radix: $radix"; |
721 } | 721 } |
722 int64 a = this; | 722 int64 a = this; |
723 if (a.isZero()) { | 723 if (a.isZero) { |
724 return "0"; | 724 return "0"; |
725 } | 725 } |
726 if (a.isMinValue()) { | 726 if (a.isMinValue) { |
727 return _minValues[radix]; | 727 return _minValues[radix]; |
728 } | 728 } |
729 | 729 |
730 String result = ""; | 730 String result = ""; |
731 bool negative = false; | 731 bool negative = false; |
732 if (a.isNegative()) { | 732 if (a.isNegative) { |
733 negative = true; | 733 negative = true; |
734 a = -a; | 734 a = -a; |
735 } | 735 } |
736 | 736 |
737 int64 r = new int64._bits(radix, 0, 0); | 737 int64 r = new int64._bits(radix, 0, 0); |
738 while (!a.isZero()) { | 738 while (!a.isZero) { |
739 a = _divMod(a, r, true); | 739 a = _divMod(a, r, true); |
740 result = "${_hexDigit(_remainder._l)}$result"; | 740 result = "${_hexDigit(_remainder._l)}$result"; |
741 } | 741 } |
742 return negative ? "-$result" : result; | 742 return negative ? "-$result" : result; |
743 } | 743 } |
744 | 744 |
745 String toDebugString() { | 745 String toDebugString() { |
746 return "int64[_l=$_l, _m=$_m, _h=$_h]"; | 746 return "int64[_l=$_l, _m=$_m, _h=$_h]"; |
747 } | 747 } |
748 | 748 |
(...skipping 120 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
869 // Align the leading one bits of a and b by shifting b left. | 869 // Align the leading one bits of a and b by shifting b left. |
870 int shift = b.numberOfLeadingZeros() - a.numberOfLeadingZeros(); | 870 int shift = b.numberOfLeadingZeros() - a.numberOfLeadingZeros(); |
871 int64 bshift = b << shift; | 871 int64 bshift = b << shift; |
872 | 872 |
873 // Quotient must be a new instance since we mutate it. | 873 // Quotient must be a new instance since we mutate it. |
874 int64 quotient = new int64(); | 874 int64 quotient = new int64(); |
875 while (shift >= 0) { | 875 while (shift >= 0) { |
876 bool gte = _trialSubtract(a, bshift); | 876 bool gte = _trialSubtract(a, bshift); |
877 if (gte) { | 877 if (gte) { |
878 quotient._setBit(shift); | 878 quotient._setBit(shift); |
879 if (a.isZero()) { | 879 if (a.isZero) { |
880 break; | 880 break; |
881 } | 881 } |
882 } | 882 } |
883 | 883 |
884 bshift._toShru1(); | 884 bshift._toShru1(); |
885 shift--; | 885 shift--; |
886 } | 886 } |
887 | 887 |
888 if (negative) { | 888 if (negative) { |
889 quotient._negate(); | 889 quotient._negate(); |
890 } | 890 } |
891 | 891 |
892 if (computeRemainder) { | 892 if (computeRemainder) { |
893 if (aIsNegative) { | 893 if (aIsNegative) { |
894 _remainder = -a; | 894 _remainder = -a; |
895 if (aIsMinValue) { | 895 if (aIsMinValue) { |
896 _remainder = _remainder - ONE; | 896 _remainder = _remainder - ONE; |
897 } | 897 } |
898 } else { | 898 } else { |
899 _remainder = a; | 899 _remainder = a; |
900 } | 900 } |
901 } | 901 } |
902 | 902 |
903 return quotient; | 903 return quotient; |
904 } | 904 } |
905 | 905 |
906 int64 _divModByMinValue(bool computeRemainder) { | 906 int64 _divModByMinValue(bool computeRemainder) { |
907 // MIN_VALUE / MIN_VALUE == 1, remainder = 0 | 907 // MIN_VALUE / MIN_VALUE == 1, remainder = 0 |
908 // (x != MIN_VALUE) / MIN_VALUE == 0, remainder == x | 908 // (x != MIN_VALUE) / MIN_VALUE == 0, remainder == x |
909 if (isMinValue()) { | 909 if (isMinValue) { |
910 if (computeRemainder) { | 910 if (computeRemainder) { |
911 _remainder = ZERO; | 911 _remainder = ZERO; |
912 } | 912 } |
913 return ONE; | 913 return ONE; |
914 } | 914 } |
915 if (computeRemainder) { | 915 if (computeRemainder) { |
916 _remainder = this; | 916 _remainder = this; |
917 } | 917 } |
918 return ZERO; | 918 return ZERO; |
919 } | 919 } |
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
989 return int32._numberOfTrailingZeros(m) + _BITS; | 989 return int32._numberOfTrailingZeros(m) + _BITS; |
990 } | 990 } |
991 if (h != 0 && m == 0 && l == 0) { | 991 if (h != 0 && m == 0 && l == 0) { |
992 return int32._numberOfTrailingZeros(h) + _BITS01; | 992 return int32._numberOfTrailingZeros(h) + _BITS01; |
993 } | 993 } |
994 | 994 |
995 return -1; | 995 return -1; |
996 } | 996 } |
997 | 997 |
998 int64 _divMod(int64 a, int64 b, bool computeRemainder) { | 998 int64 _divMod(int64 a, int64 b, bool computeRemainder) { |
999 if (b.isZero()) { | 999 if (b.isZero) { |
1000 throw new IntegerDivisionByZeroException(); | 1000 throw new IntegerDivisionByZeroException(); |
1001 } | 1001 } |
1002 if (a.isZero()) { | 1002 if (a.isZero) { |
1003 if (computeRemainder) { | 1003 if (computeRemainder) { |
1004 _remainder = ZERO; | 1004 _remainder = ZERO; |
1005 } | 1005 } |
1006 return ZERO; | 1006 return ZERO; |
1007 } | 1007 } |
1008 // MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0. | 1008 // MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0. |
1009 if (b.isMinValue()) { | 1009 if (b.isMinValue) { |
1010 return a._divModByMinValue(computeRemainder); | 1010 return a._divModByMinValue(computeRemainder); |
1011 } | 1011 } |
1012 // Normalize b to abs(b), keeping track of the parity in 'negative'. | 1012 // Normalize b to abs(b), keeping track of the parity in 'negative'. |
1013 // We can do this because we have already ensured that b != MIN_VALUE. | 1013 // We can do this because we have already ensured that b != MIN_VALUE. |
1014 bool negative = false; | 1014 bool negative = false; |
1015 if (b.isNegative()) { | 1015 if (b.isNegative) { |
1016 b = -b; | 1016 b = -b; |
1017 negative = !negative; | 1017 negative = !negative; |
1018 } | 1018 } |
1019 // If b == 2^n, bpower will be n, otherwise it will be -1. | 1019 // If b == 2^n, bpower will be n, otherwise it will be -1. |
1020 int bpower = b._powerOfTwo(); | 1020 int bpower = b._powerOfTwo(); |
1021 | 1021 |
1022 // True if the original value of a is negative. | 1022 // True if the original value of a is negative. |
1023 bool aIsNegative = false; | 1023 bool aIsNegative = false; |
1024 // True if the original value of a is int64.MIN_VALUE. | 1024 // True if the original value of a is int64.MIN_VALUE. |
1025 bool aIsMinValue = false; | 1025 bool aIsMinValue = false; |
1026 | 1026 |
1027 /* | 1027 /* |
1028 * Normalize a to a positive value, keeping track of the sign change in | 1028 * Normalize a to a positive value, keeping track of the sign change in |
1029 * 'negative' (which tracks the sign of both a and b and is used to | 1029 * 'negative' (which tracks the sign of both a and b and is used to |
1030 * determine the sign of the quotient) and 'aIsNegative' (which is used to | 1030 * determine the sign of the quotient) and 'aIsNegative' (which is used to |
1031 * determine the sign of the remainder). | 1031 * determine the sign of the remainder). |
1032 * | 1032 * |
1033 * For all values of a except MIN_VALUE, we can just negate a and modify | 1033 * For all values of a except MIN_VALUE, we can just negate a and modify |
1034 * negative and aIsNegative appropriately. When a == MIN_VALUE, negation is | 1034 * negative and aIsNegative appropriately. When a == MIN_VALUE, negation is |
1035 * not possible without overflowing 64 bits, so instead of computing | 1035 * not possible without overflowing 64 bits, so instead of computing |
1036 * abs(MIN_VALUE) / abs(b) we compute (abs(MIN_VALUE) - 1) / abs(b). The | 1036 * abs(MIN_VALUE) / abs(b) we compute (abs(MIN_VALUE) - 1) / abs(b). The |
1037 * only circumstance under which these quotients differ is when b is a power | 1037 * only circumstance under which these quotients differ is when b is a power |
1038 * of two, which will divide abs(MIN_VALUE) == 2^64 exactly. In this case, | 1038 * of two, which will divide abs(MIN_VALUE) == 2^64 exactly. In this case, |
1039 * we can get the proper result by shifting MIN_VALUE in unsigned fashion. | 1039 * we can get the proper result by shifting MIN_VALUE in unsigned fashion. |
1040 * | 1040 * |
1041 * We make a single copy of a before the first operation that needs to | 1041 * We make a single copy of a before the first operation that needs to |
1042 * modify its value. | 1042 * modify its value. |
1043 */ | 1043 */ |
1044 bool aIsCopy = false; | 1044 bool aIsCopy = false; |
1045 if (a.isMinValue()) { | 1045 if (a.isMinValue) { |
1046 aIsMinValue = true; | 1046 aIsMinValue = true; |
1047 aIsNegative = true; | 1047 aIsNegative = true; |
1048 // If b is not a power of two, treat -a as MAX_VALUE (instead of the | 1048 // If b is not a power of two, treat -a as MAX_VALUE (instead of the |
1049 // actual value (MAX_VALUE + 1)). | 1049 // actual value (MAX_VALUE + 1)). |
1050 if (bpower == -1) { | 1050 if (bpower == -1) { |
1051 a = new int64._copy(MAX_VALUE); | 1051 a = new int64._copy(MAX_VALUE); |
1052 aIsCopy = true; | 1052 aIsCopy = true; |
1053 negative = !negative; | 1053 negative = !negative; |
1054 } else { | 1054 } else { |
1055 // Signed shift of MIN_VALUE produces the right answer. | 1055 // Signed shift of MIN_VALUE produces the right answer. |
1056 int64 c = a >> bpower; | 1056 int64 c = a >> bpower; |
1057 if (negative) { | 1057 if (negative) { |
1058 c._negate(); | 1058 c._negate(); |
1059 } | 1059 } |
1060 if (computeRemainder) { | 1060 if (computeRemainder) { |
1061 _remainder = ZERO; | 1061 _remainder = ZERO; |
1062 } | 1062 } |
1063 return c; | 1063 return c; |
1064 } | 1064 } |
1065 } else if (a.isNegative()) { | 1065 } else if (a.isNegative) { |
1066 aIsNegative = true; | 1066 aIsNegative = true; |
1067 a = -a; | 1067 a = -a; |
1068 aIsCopy = true; | 1068 aIsCopy = true; |
1069 negative = !negative; | 1069 negative = !negative; |
1070 } | 1070 } |
1071 | 1071 |
1072 // Now both a and b are non-negative. | 1072 // Now both a and b are non-negative. |
1073 // If b is a power of two, just shift. | 1073 // If b is a power of two, just shift. |
1074 if (bpower != -1) { | 1074 if (bpower != -1) { |
1075 return _divModByShift(a, bpower, negative, aIsCopy, aIsNegative, | 1075 return _divModByShift(a, bpower, negative, aIsCopy, aIsNegative, |
(...skipping 10 matching lines...) Expand all Loading... |
1086 } | 1086 } |
1087 } | 1087 } |
1088 return ZERO; | 1088 return ZERO; |
1089 } | 1089 } |
1090 | 1090 |
1091 // Generate the quotient using bit-at-a-time long division. | 1091 // Generate the quotient using bit-at-a-time long division. |
1092 return _divModHelper(aIsCopy ? a : new int64._copy(a), b, negative, | 1092 return _divModHelper(aIsCopy ? a : new int64._copy(a), b, negative, |
1093 aIsNegative, aIsMinValue, computeRemainder); | 1093 aIsNegative, aIsMinValue, computeRemainder); |
1094 } | 1094 } |
1095 } | 1095 } |
OLD | NEW |