CnC_Remastered_Collection

Command and Conquer: Red Alert
Log | Files | Refs | README | LICENSE

INT.H (13459B)

      1 //
      2 // Copyright 2020 Electronic Arts Inc.
      3 //
      4 // TiberianDawn.DLL and RedAlert.dll and corresponding source code is free 
      5 // software: you can redistribute it and/or modify it under the terms of 
      6 // the GNU General Public License as published by the Free Software Foundation, 
      7 // either version 3 of the License, or (at your option) any later version.
      8 
      9 // TiberianDawn.DLL and RedAlert.dll and corresponding source code is distributed 
     10 // in the hope that it will be useful, but with permitted additional restrictions 
     11 // under Section 7 of the GPL. See the GNU General Public License in LICENSE.TXT 
     12 // distributed with this program. You should have received a copy of the 
     13 // GNU General Public License along with permitted additional restrictions 
     14 // with this program. If not, see https://github.com/electronicarts/CnC_Remastered_Collection
     15 
     16 /* $Header: /CounterStrike/INT.H 1     3/03/97 10:24a Joe_bostic $ */
     17 /***********************************************************************************************
     18  ***              C O N F I D E N T I A L  ---  W E S T W O O D  S T U D I O S               ***
     19  ***********************************************************************************************
     20  *                                                                                             *
     21  *                 Project Name : Command & Conquer                                            *
     22  *                                                                                             *
     23  *                    File Name : INT.H                                                        *
     24  *                                                                                             *
     25  *                   Programmer : Joe L. Bostic                                                *
     26  *                                                                                             *
     27  *                   Start Date : 04/26/96                                                     *
     28  *                                                                                             *
     29  *                  Last Update : April 26, 1996 [JLB]                                         *
     30  *                                                                                             *
     31  *---------------------------------------------------------------------------------------------*
     32  * Functions:                                                                                  *
     33  * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
     34 
     35 
     36 #ifndef INT_H
     37 #define INT_H
     38 
     39 #include <memory.h>
     40 #include	<limits.h>
     41 #include	<assert.h>
     42 #include	"mp.h"
     43 #include	"straw.h"
     44 
     45 //#pragma warn -inl
     46 
     47 template<int PRECISION>
     48 class Int {
     49 	public:
     50 
     51 		/*
     52 		**	Constructors and initializers.
     53 		*/
     54 		Int(void) {XMP_Init(&reg[0], 0, PRECISION);}
     55 		Int(unsigned long value) {XMP_Init(&reg[0], value, PRECISION);}
     56 
     57 		void Randomize(Straw & rng, int bitcount) {XMP_Randomize(&reg[0], rng, bitcount, PRECISION);}
     58 		void Randomize(Straw & rng, const Int & minval, const Int & maxval) {XMP_Randomize(&reg[0], rng, minval, maxval, PRECISION); reg[0] |= 1;}
     59 
     60 		/*
     61 		**	Convenient conversion operators to get at the underlying array of
     62 		**	integers. Big number math is basically manipulation of arbitrary
     63 		**	length arrays.
     64 		*/
     65 		operator digit * () {return & reg[0];}
     66 		operator const digit * () const {return & reg[0];}
     67 
     68 		/*
     69 		**	Array access operator (references bit position). Bit 0 is the first bit.
     70 		*/
     71 		bool operator[](unsigned bit) const {return(XMP_Test_Bit(&reg[0], bit));}
     72 
     73 		/*
     74 		**	Unary operators.
     75 		*/
     76 		Int & operator ++ (void) {XMP_Inc(&reg[0], PRECISION);return(*this);}
     77 		Int & operator -- (void) {XMP_Dec(&reg[0], PRECISION);return(*this);}
     78 		int operator ! (void) const {return(XMP_Test_Eq_Int(&reg[0], 0, PRECISION));}
     79 		Int operator ~ (void) {XMP_Not(&reg[0], PRECISION);return(*this);}
     80 		Int operator - (void) const {Int a = *this;a.Negate();return (a);}
     81 
     82 		/*
     83 		**	Attribute query functions.
     84 		*/
     85 		int ByteCount(void) const {return(XMP_Count_Bytes(&reg[0], PRECISION));}
     86 		int BitCount(void) const {return(XMP_Count_Bits(&reg[0], PRECISION));}
     87 		bool Is_Negative(void) const {return(XMP_Is_Negative(&reg[0], PRECISION));}
     88 		unsigned MaxBitPrecision() const {return PRECISION*(sizeof(unsigned long)*CHAR_BIT);}
     89 		bool IsSmallPrime(void) const {return(XMP_Is_Small_Prime(&reg[0], PRECISION));}
     90 		bool SmallDivisorsTest(void) const {return(XMP_Small_Divisors_Test(&reg[0], PRECISION));}
     91 		bool FermatTest(unsigned rounds) const {return(XMP_Fermat_Test(&reg[0], rounds, PRECISION));}
     92 		bool IsPrime(void) const {return(XMP_Is_Prime(&reg[0], PRECISION));}
     93 		bool RabinMillerTest(Straw & rng, unsigned int rounds) const {return(XMP_Rabin_Miller_Test(rng, &reg[0], rounds, PRECISION));}
     94 
     95 		/*
     96 		**	'in-place' binary operators.
     97 		*/
     98 		Int & operator += (const Int & number) {Carry = XMP_Add(&reg[0], &reg[0], number, 0, PRECISION);return(*this);}
     99 		Int & operator -= (const Int & number) {Borrow = XMP_Sub(&reg[0], &reg[0], number, 0, PRECISION);return(*this);}
    100 		Int & operator *= (const Int & multiplier) {Remainder = *this;Error=XMP_Signed_Mult(&reg[0], Remainder, multiplier, PRECISION);return(*this);}
    101 		Int & operator /= (const Int & t) {*this = (*this) / t;return *this;}
    102 		Int & operator %= (const Int & t) {*this = (*this) % t;return *this;}
    103 		Int &  operator <<= (int bits) {XMP_Shift_Left_Bits(&reg[0], bits, PRECISION);return *this;}
    104 		Int &  operator >>= (int bits) {XMP_Shift_Right_Bits(&reg[0], bits, PRECISION);return *this;}
    105 
    106 		/*
    107 		**	Mathematical binary operators.
    108 		*/
    109 		Int operator + (const Int & number) const {Int term;Carry = XMP_Add(term, &reg[0], number, 0, PRECISION);return(term);}
    110 		Int operator + (unsigned short b) const {Int result;Carry=XMP_Add_Int(result, &reg[0], b, 0, PRECISION);return(result);}
    111 //		friend Int<PRECISION> operator + (digit b, const Int<PRECISION> & a) {return(Int<PRECISION>(b) + a);}
    112 		Int operator - (const Int & number) const {Int term;Borrow = XMP_Sub(term, &reg[0], number, 0, PRECISION);return(term);}
    113 		Int operator - (unsigned short b) const {Int result;Borrow = XMP_Sub_Int(result, &reg[0], b, 0, PRECISION);return(result);}
    114 //		friend Int<PRECISION> operator - (digit b, const Int<PRECISION> & a) {return(Int<PRECISION>(b) - a);}
    115 		Int operator * (const Int & multiplier) const {Int result;Error=XMP_Signed_Mult(result, &reg[0], multiplier, PRECISION);return result;}
    116 		Int operator * (unsigned short b) const {Int result;Error=XMP_Unsigned_Mult_Int(result, &reg[0], b, PRECISION);return(result);}
    117 //		friend Int<PRECISION> operator * (digit b, const Int<PRECISION> & a) {return(Int<PRECISION>(b) * a);}
    118 		Int operator / (const Int & divisor) const {Int quotient = *this;XMP_Signed_Div(Remainder, quotient, &reg[0], divisor, PRECISION);return (quotient);}
    119 		Int operator / (unsigned long b) const {return(*this / Int<PRECISION>(b));}
    120 		Int operator / (unsigned short divisor) const {Int quotient;Error=XMP_Unsigned_Div_Int(quotient, &reg[0], divisor, PRECISION);return(quotient);}
    121 //		friend Int<PRECISION> operator / (digit a, const Int<PRECISION> & b) {return(Int<PRECISION>(a) / b);}
    122 		Int operator % (const Int & divisor) const {Int remainder;XMP_Signed_Div(remainder, Remainder, &reg[0], divisor, PRECISION);return(remainder);}
    123 		Int operator % (unsigned long b) const {return(*this % Int<PRECISION>(b));}
    124 		unsigned short operator % (unsigned short divisor) const {return(XMP_Unsigned_Div_Int(Remainder, &reg[0], divisor, PRECISION));}
    125 //		friend Int<PRECISION> operator % (digit a, const Int<PRECISION> & b) {return(Int<PRECISION>(a) % b);}
    126 
    127 		/*
    128 		**	Bitwise binary operators.
    129 		*/
    130 		Int operator >> (int bits) const {Int result = *this; XMP_Shift_Right_Bits(result, bits, PRECISION);return result;}
    131 		Int operator << (int bits) const {Int result = *this; XMP_Shift_Left_Bits(result, bits, PRECISION);return result;}
    132 
    133 		/*
    134 		**	Comparison binary operators.
    135 		*/
    136 		int operator == (const Int &b) const {return (memcmp(&reg[0], &b.reg[0], (MAX_BIT_PRECISION/CHAR_BIT))==0);}
    137 		int operator != (const Int& b) const {return !(*this == b);}
    138 		int operator > (const Int & number) const {return(XMP_Compare(&reg[0], number, PRECISION) > 0);}
    139 		int operator >= (const Int & number) const {return(XMP_Compare(&reg[0], number, PRECISION) >= 0);}
    140 		int operator < (const Int & number) const {return(XMP_Compare(&reg[0], number, PRECISION) < 0);}
    141 		int operator <= (const Int & number) const {return(XMP_Compare(&reg[0], number, PRECISION) <= 0);}
    142 
    143 		/*
    144 		**	Misc. mathematical and logical functions.
    145 		*/
    146 		void Negate(void) {XMP_Neg(&reg[0], PRECISION);}
    147 		Int Abs(void) {XMP_Abs(&reg[0], PRECISION);return(*this);}
    148 		Int times_b_mod_c(Int const & multiplier, Int const & modulus) const {
    149 			Int result;
    150 			Error=xmp_stage_modulus(modulus, PRECISION);
    151 			Error=XMP_Mod_Mult(result, &reg[0], multiplier, PRECISION);
    152 			XMP_Mod_Mult_Clear(PRECISION);
    153 			return result;
    154 		}
    155 
    156 		Int exp_b_mod_c(const Int & e, const Int & m) const {
    157 			Int result;
    158 			Error=xmp_exponent_mod(result, &reg[0], e, m, PRECISION);
    159 			return result;
    160 		}
    161 
    162 
    163 		static Int Unsigned_Mult(Int const & multiplicand, Int const & multiplier) {Int product;Error=XMP_Unsigned_Mult(&product.reg[0], &multiplicand.reg[0], &multiplier.reg[0], PRECISION);return(product);}
    164 		static void Unsigned_Divide(Int & remainder, Int & quotient, const Int & dividend, const Int & divisor) {Error=XMP_Unsigned_Div(remainder, quotient, dividend, divisor, PRECISION);}
    165 		static void Signed_Divide(Int & remainder, Int & quotient, const Int & dividend, const Int & divisor) {XMP_Signed_Div(remainder, quotient, dividend, divisor, PRECISION);}
    166 		Int Inverse(const Int & modulus) const {Int result;XMP_Inverse_A_Mod_B(result, &reg[0], modulus, PRECISION);return(result);}
    167 
    168 		static Int Decode_ASCII(char const * string) {Int result;XMP_Decode_ASCII(string, result, PRECISION);return(result);}
    169 
    170 		// Number (sign independand) inserted into buffer.
    171 		int Encode(unsigned char *output) const {return(XMP_Encode(output, &reg[0], PRECISION));}
    172 		int Encode(unsigned char * output, unsigned length) const {return(XMP_Encode(output, length, &reg[0], PRECISION));}
    173 		void Signed_Decode(const unsigned char * from, int frombytes) {XMP_Signed_Decode(&reg[0], from, frombytes, PRECISION);}
    174 		void Unsigned_Decode(const unsigned char * from, int frombytes) {XMP_Unsigned_Decode(&reg[0], from, frombytes, PRECISION);}
    175 
    176 		// encode Int using Distinguished Encoding Rules, returns size of output
    177 		int DEREncode(unsigned char * output) const {return(XMP_DER_Encode(&reg[0], output, PRECISION));}
    178 		void DERDecode(const unsigned char *input) {XMP_DER_Decode(&reg[0], input, PRECISION);}
    179 
    180 		// Friend helper functions.
    181 		friend Int<PRECISION> Generate_Prime(Straw & rng, int pbits, Int<PRECISION> const * = 0);
    182 		friend Int<PRECISION> Gcd(const Int<PRECISION> & a, const Int<PRECISION> & b);
    183 //		friend bool NextPrime(Int<PRECISION> & p, const Int<PRECISION> & max, bool blumInt=false);
    184 //		friend Int<PRECISION> a_exp_b_mod_pq(const Int<PRECISION> & a, const Int<PRECISION> & ep, const Int<PRECISION> & eq, const Int<PRECISION> & p, const Int<PRECISION> & q, const Int<PRECISION> & u);
    185 
    186 		static int Error;
    187 
    188 		// Carry result from last addition.
    189 		static bool Carry;
    190 
    191 		// Borrow result from last subtraction.
    192 		static bool Borrow;
    193 
    194 		// Remainder value from the various division routines.
    195 		static Int Remainder;
    196 
    197 
    198 	private:
    199 		digit reg[PRECISION];
    200 
    201 
    202 		struct RemainderTable
    203 		{
    204 			RemainderTable(const Int<PRECISION> & p) : HasZeroEntry(false)
    205 			{
    206 				for (unsigned i = 0; i < ARRAY_SIZE(primeTable); i++) {
    207 					table[i] = p % primeTable[i];
    208 				}
    209 			}
    210 			bool HasZero() const {return(HasZeroEntry);}
    211 			void Increment(unsigned short increment = 1)
    212 			{
    213 				HasZeroEntry = false;
    214 				for (unsigned int i = 0; i < ARRAY_SIZE(primeTable); i++) {
    215 					table[i] += increment;
    216 					while (table[i] >= primeTable[i]) {
    217 						table[i] -= primeTable[i];
    218 					}
    219 					HasZeroEntry = (HasZeroEntry || !table[i]);
    220 				}
    221 			}
    222 			void Increment(const RemainderTable & rtQ)
    223 			{
    224 				HasZeroEntry = false;
    225 				for (unsigned int i = 0; i < ARRAY_SIZE(primeTable); i++) {
    226 					table[i] += rtQ.table[i];
    227 					if (table[i] >= primeTable[i]) {
    228 						table[i] -= primeTable[i];
    229 					}
    230 					HasZeroEntry = (HasZeroEntry || !table[i]);
    231 				}
    232 			}
    233 
    234 			bool HasZeroEntry;
    235 			unsigned short table[ARRAY_SIZE(primeTable)];
    236 		};
    237 
    238 };
    239 
    240 
    241 template<class T>
    242 T Gcd(const T & a, const T & n)
    243 {
    244 	T g[3]={n, a, 0UL};
    245 
    246 	unsigned int i = 1;
    247 	while (!!g[i%3]) {
    248 		g[(i+1)%3] = g[(i-1)%3] % g[i%3];
    249 		i++;
    250 	}
    251 	return g[(i-1)%3];
    252 }
    253 
    254 
    255 
    256 //#pragma warning 604 9
    257 //#pragma warning 595 9
    258 template<class T>
    259 T Generate_Prime(Straw & rng, int pbits, T const *)
    260 {
    261 	T minQ = (T(1UL) << (unsigned short)(pbits-(unsigned short)2));
    262 	T maxQ = ((T(1UL) << (unsigned short)(pbits-(unsigned short)1)) - (unsigned short)1);
    263 
    264 	T q;
    265 	T p;
    266 
    267 	do {
    268 		q.Randomize(rng, minQ, maxQ);
    269 		p = (q*2) + (unsigned short)1;
    270 
    271 		T::RemainderTable rtQ(q);
    272 		T::RemainderTable rtP(p);
    273 
    274 		while (rtQ.HasZero() || rtP.HasZero() || !q.IsPrime() || !p.IsPrime()) {
    275 			q += 2;
    276 			p += 4;
    277 			if (q > maxQ) break;
    278 
    279 			rtQ.Increment(2);
    280 			rtP.Increment(4);
    281 		}
    282 	} while (q > maxQ);
    283 
    284 	return(p);
    285 }
    286 
    287 
    288 
    289 
    290 
    291 
    292 typedef Int<MAX_UNIT_PRECISION>	bignum;
    293 typedef Int<MAX_UNIT_PRECISION>	BigInt;
    294 
    295 
    296 
    297 //BigInt Gcd(const BigInt & a, const BigInt & n);
    298 //BigInt Generate_Prime(RandomNumberGenerator & rng, int pbits, BigInt const * dummy);
    299 
    300 #endif
    301