1// tFixInt.h 
2// 
3// A tFixInt is a fixed sized integer type that may be larger than the native types. It is _not_ a 'big' integer class 
4// in that the size of the int is fixed at compile time. This loss of dynamic precision is well worth the efficiency 
5// gains and simple memory layout that a fixed size affords. tFixInt is ideal for storing integer values where a uint32 
6// or uint64 is not big enough. In general, use tBitField if you don't need arithmetic as it will be even faster. 
7// The tFixIntU is the unsigned version of a tFixInt. tFixIntU is a superclass of a tFixInt. This header also typedefs 
8// some commonly used sizes. Specifically it allows one to use the types tint128, tint256, tint512, tuint128, tuint256, 
9// and tuint512 simply by including this header. 
10// 
11// Copyright (c) 2004-2006, 2015, 2017, 2020 Tristan Grimmer. 
12// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
13// granted, provided that the above copyright notice and this permission notice appear in all copies. 
14// 
15// This class is based on the BigInt number class by M Phillips - 2005. http://homepages.ihug.co.nz/~aurora76/Malc/ 
16// The original header follows in the next paragraph. It should be considered part of the copyright notice and 
17// included with all copies of this work. 
18// 
19// Original header text: 
20// "Thanks also to Zero Soma Valintine, Edward King, and David Brackman for several bug fixes. This code is provided 
21// as-is with no warranties or guarantees of any kind. Permission to use and modify this code however you like, to suit 
22// your needs, and redistribute the modified source, hereby granted. But please retain my name, email address, and 
23// website link at the top of the resulting source file. And please send an email to M Phillips (mbp2@i4free.co.nz or 
24// mbp2nz@ihug.co.nz) a) if you use this file in a released product, or b) if you find any bugs, or c) if you have any 
25// suggestions." 
26// 
27// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
29// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
30// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
31// PERFORMANCE OF THIS SOFTWARE. 
32 
33#pragma once 
34#include "Foundation/tString.h" 
35#include "Foundation/tFundamentals.h" 
36template<int> class tFixInt; 
37 
38 
39// NumBits is the number of bits in the tFixIntU. Good values might be something like 128, or even 256. NumBits must be 
40// a multiple of 32. Fixed int classes are supported by tPrintf so just call something like: 
41// tsPrintf(str, "%032|128X", val128) to convert it to a string. 
42template<int NumBits> class tFixIntU 
43{ 
44public: 
45 tFixIntU() { tStaticAssertMsg(NumBits % 32 == 0, "tFixIntU must be a multiple of 32 bits in size."); } 
46 
47 // Disabled CopyCons so class remains a POD-type. Allows it to be passed to tPrintf for non MSVC compilers. 
48 // tFixIntU(const tFixIntU& src) { Set(src); } 
49 // tFixIntU(const tFixInt<NumBits>& src) { Set(src); } 
50 
51 // A base argument of < 2 means determine the base from a prefix supplied inside the string itself, like "0x". 
52 // See tStd::tStrtoi for a full description of the behaviour. 
53 tFixIntU(const char* s, int base = -1) { Set(s, base); } 
54 tFixIntU(int8 v) { Set(v); } 
55 tFixIntU(int16 v) { Set(v); } 
56 tFixIntU(int v) { Set(v); } 
57 tFixIntU(int64 v) { Set(v); } 
58 tFixIntU(uint8 v) { Set(v); } 
59 tFixIntU(uint16 v) { Set(v); } 
60 tFixIntU(uint v) { Set(v); } 
61 tFixIntU(uint64 v) { Set(v); } 
62 tFixIntU(float v) { Set(v); } 
63 tFixIntU(double v) { Set(v); } 
64 
65 void Set(const tFixIntU& src) { *this = src; } 
66 void Set(const tFixInt<NumBits>& src) { *this = src.AsUnsigned(); } 
67 void Set(const char* s, int base = -1) { *this = tStd::tStrtoiT< tFixInt<NumBits> >(s, base); } 
68 void Set(int8 v) { Init(v, (v >= 0) ? 0 : 0xFF); } 
69 void Set(int16 v) { Init(v, (v >= 0) ? 0 : 0xFF); } 
70 void Set(int v) { Init(v, (v >= 0) ? 0 : 0xFF); } 
71 void Set(int64 v) { Init(v, (v >= 0) ? 0 : 0xFF); } 
72 void Set(uint8 v) { Init(v); } 
73 void Set(uint16 v) { Init(v); } 
74 void Set(uint v) { Init(v); } 
75 void Set(uint64 v) { Init(v); } 
76 void Set(float); 
77 void Set(double); 
78 
79 operator int8() const { int8 r; Extract(r); return r; } 
80 operator int16() const { int16 r; Extract(r); return r; } 
81 operator int() const { int r; Extract(r); return r; } 
82 operator int64() const { int64 r; Extract(r); return r; } 
83 operator uint8() const { uint8 r; Extract(r); return r; } 
84 operator uint16() const { uint16 r; Extract(r); return r; } 
85 operator uint() const { uint r; Extract(r); return r; } 
86 operator uint64() const { uint64 r; Extract(r); return r; } 
87 operator float() const; 
88 operator double() const; 
89 
90 static inline void Swap(tFixIntU& a, tFixIntU& b) { for (int i = 0; i < NumBaseInts; i++) tStd::tSwap(a.IntData[i], b.IntData[i]); } 
91 tFixIntU& operator=(const tFixInt<NumBits>& v) { return *this = v.AsUnsigned(); } 
92 template<int N, bool LhsGreater> struct AssignHelper { template <typename T> void operator()(tFixIntU& lhs, const T& rhs) const; }; 
93 template<int N> struct AssignHelper<N, false> { template <typename T> void operator()(tFixIntU& lhs, const T& rhs) const; }; 
94 template<int N> tFixIntU& operator=(const tFixIntU<N>& rhs) { AssignHelper<N, (NumBits>N)>()(*this, rhs); return *this; } 
95 
96 void MakeZero() { for (int i = 0; i < NumBaseInts; i++) IntData[i] = 0; } 
97 void MakeMaxInt() { for (int i = 0; i < NumBaseInts; i++) IntData[i] = 0xFFFFFFFF; } 
98 
99 const tFixInt<NumBits>& AsSigned() const { return reinterpret_cast<const tFixInt<NumBits>&>(*this); } 
100 tFixInt<NumBits>& AsSigned() { return reinterpret_cast<tFixInt<NumBits>&>(*this); } 
101 tString GetAsString(int base) const; 
102 
103 void ClearBit(int index); 
104 void SetBit(int index); 
105 void ToggleBit(int index); 
106 bool GetBit(int index) const; 
107 
108 tFixIntU& operator&=(const tFixIntU& v) { for (int i = 0; i < NumBaseInts; i++) IntData[i] &= v.IntData[i]; return *this; } 
109 tFixIntU& operator|=(const tFixIntU& v) { for (int i = 0; i < NumBaseInts; i++) IntData[i] |= v.IntData[i]; return *this; } 
110 tFixIntU& operator^=(const tFixIntU& v) { for (int i = 0; i < NumBaseInts; i++) IntData[i] ^= v.IntData[i]; return *this; } 
111 tFixIntU& operator>>=(int shift); 
112 tFixIntU& operator<<=(int shift); 
113 tFixIntU& operator+=(const tFixIntU&); 
114 tFixIntU& operator-=(const tFixIntU&); 
115 tFixIntU& operator/=(const tFixIntU& v) { *this = tDivide(*this, v); return *this; } 
116 tFixIntU& operator/=(int v) { *this = tDivide(*this, v); return *this; } 
117 tFixIntU& operator%=(const tFixIntU& v) { tDivide(*this, v, this); return *this; } 
118 tFixIntU& operator%=(int v) { int r; tDivide(*this, v, &r); *this = r; return *this; } 
119 tFixIntU operator>>(int shift) const { tFixIntU result(*this); result >>= shift; return result; } 
120 tFixIntU operator<<(int shift) const { tFixIntU result(*this); result <<= shift; return result; } 
121 tFixIntU& operator*=(const uint32 v); 
122 tFixIntU& operator*=(const tFixIntU& v); 
123 
124 // Interestingly, friend functions declared (and even defined) inside class declarations are not considered in the 
125 // scope of the enclosing class; they are in the outer scope. Makes perfect sense, just didn't know before. 
126 friend bool operator==(const tFixIntU& a, const tFixIntU& b) { for (int i = 0; i < NumBaseInts; i++) if (a.IntData[i] != b.IntData[i]) return false; return true; } 
127 friend bool operator!=(const tFixIntU& a, const tFixIntU& b) { return !(a == b); } 
128 friend bool operator>(const tFixIntU& a, const tFixIntU& b) { return (b < a); } 
129 friend bool operator<=(const tFixIntU& a, const tFixIntU& b) { return !(b < a); } 
130 friend bool operator>=(const tFixIntU& a, const tFixIntU& b) { return !(a < b); } 
131 friend tFixIntU operator&(const tFixIntU& a, const tFixIntU& b) { tFixIntU result; for (int i = 0; i < NumBaseInts; i++) result.IntData[i] = a.IntData[i] & b.IntData[i]; return result; } 
132 friend tFixIntU operator|(const tFixIntU& a, const tFixIntU& b) { tFixIntU result; for (int i = 0; i < NumBaseInts; i++) result.IntData[i] = a.IntData[i] | b.IntData[i]; return result; } 
133 friend tFixIntU operator^(const tFixIntU& a, const tFixIntU& b) { tFixIntU result; for (int i = 0; i < NumBaseInts; i++) result.IntData[i] = a.IntData[i] ^ b.IntData[i]; return result; } 
134 friend tFixIntU operator+(const tFixIntU& a, const tFixIntU& b) { tFixIntU result; result = a; result += b; return result; } 
135 friend tFixIntU operator-(const tFixIntU& a, const tFixIntU& b) { tFixIntU result; result = a; result -= b; return result; } 
136 friend tFixIntU operator*(const tFixIntU& a, const tFixIntU& b) { tFixIntU result; result = a; result *= b; return result; } 
137 friend tFixIntU operator/(const tFixIntU& a, const tFixIntU& b) { return tDivide(a, b); } 
138 friend tFixIntU operator%(const tFixIntU& a, const tFixIntU& b) { tFixIntU result; tDivide(a, b, &result); return result; } 
139 
140 tFixIntU& operator++(); 
141 tFixIntU operator++(int) /* The dummy int means postfix. */ { tFixIntU result; result = *this; ++*this; return result; } 
142 tFixIntU& operator--(); 
143 tFixIntU operator--(int) { tFixIntU result; result = *this; --*this; return result; } 
144 
145 // We may want to consider the pitfalls of operator bool() here. See http://www.artima.com/cppsource/safebool.html 
146 operator bool() const { for (int i = 0; i < NumBaseInts; i++) if (IntData[i]) return true; return false; } // Non-zero returns true. 
147 bool operator!() const { for (int i = 0; i < NumBaseInts; i++) if (IntData[i]) return false; return true; } // Only zero returns true. 
148 tFixIntU operator~() const { tFixIntU result; for (int i = 0; i < NumBaseInts; i++) result.IntData[i] = ~IntData[i]; return result; } 
149 tFixIntU operator+() const { return *this; } // Unary positive. 
150 tFixIntU operator-() const { tFixIntU result; for (int i = 0; i < NumBaseInts; i++) result.IntData[i] = ~IntData[i]; ++result; return result; } // Negates a number. 
151 
152 friend bool operator<(const tFixIntU& a, int b) { return a < tFixInt<NumBits>(b).AsUnsigned(); } 
153 friend bool operator>(const tFixIntU& a, int b) { return tFixInt<NumBits>(b).AsUnsigned() < a; } 
154 friend bool operator<=(const tFixIntU& a, int b) { return !(tFixInt<NumBits>(b).AsUnsigned() < a); } 
155 friend bool operator>=(const tFixIntU& a, int b) { return !(a < tFixInt<NumBits>(b).AsUnsigned()); } 
156 friend bool operator==(const tFixIntU& a, int b) { return a == tFixInt<NumBits>(b).AsUnsigned(); } 
157 friend bool operator!=(const tFixIntU& a, int b) { return a != tFixInt<NumBits>(b).AsUnsigned(); } 
158 friend bool operator<(int a, const tFixIntU& b) { return tFixInt<NumBits>(a).AsUnsigned() < b; } 
159 friend bool operator>(int a, const tFixIntU& b) { return b < tFixInt<NumBits>(a).AsUnsigned(); } 
160 friend bool operator<=(int a, const tFixIntU& b) { return !(b < tFixInt<NumBits>(a).AsUnsigned()); } 
161 friend bool operator>=(int a, const tFixIntU& b) { return !(tFixInt<NumBits>(a).AsUnsigned() < b); } 
162 friend bool operator==(int a, const tFixIntU& b) { return tFixInt<NumBits>(a).AsUnsigned() == b; } 
163 friend bool operator!=(int a, const tFixIntU& b) { return tFixInt<NumBits>(a).AsUnsigned() != b; } 
164 
165 friend tFixIntU operator&(const tFixIntU& a, int b) { return a & tFixIntU(b); } 
166 friend tFixIntU operator|(const tFixIntU& a, int b) { return a | tFixIntU(b); } 
167 friend tFixIntU operator^(const tFixIntU& a, int b) { return a ^ tFixIntU(b); } 
168 friend tFixIntU operator&(int a, const tFixIntU& b) { return tFixIntU(a) & b; } 
169 friend tFixIntU operator|(int a, const tFixIntU& b) { return tFixIntU(a) | b; } 
170 friend tFixIntU operator^(int a, const tFixIntU& b) { return tFixIntU(a) ^ b; } 
171 friend tFixIntU operator+(const tFixIntU& a, int b) { return a + tFixInt<NumBits>(b).AsUnsigned(); } 
172 friend tFixIntU operator-(const tFixIntU& a, int b) { return a - tFixInt<NumBits>(b).AsUnsigned(); } 
173 friend tFixIntU operator*(const tFixIntU& a, int b) { return a * tFixInt<NumBits>(b).AsUnsigned(); } 
174 friend tFixIntU operator/(const tFixIntU& a, int b) { return tDivide(a, b); } 
175 friend int operator%(const tFixIntU& a, int b) { int result; tDivide(a, b, &result); return result; } 
176 friend tFixIntU operator+(int a, const tFixIntU& b) { return tFixInt<NumBits>(a).AsUnsigned() + b; } 
177 friend tFixIntU operator-(int a, const tFixIntU& b) { return tFixInt<NumBits>(a).AsUnsigned() - b; } 
178 friend tFixIntU operator*(int a, const tFixIntU& b) { return tFixInt<NumBits>(a).AsUnsigned() * b; } 
179 friend tFixIntU operator/(int a, const tFixIntU& b) { return tFixInt<NumBits>(a).AsUnsigned() / b; } 
180 friend tFixIntU operator%(int a, const tFixIntU& b) { return tFixInt<NumBits>(a).AsUnsigned() % b; } 
181 
182 void RotateRight(int shift); 
183 int FindHighestBitSet() const; 
184 int FindLowestBitSet() const; 
185 
186 // Returns how many uint32s are used to store the integer. 
187 int GetRawCount() const { return NumBaseInts; } 
188 void GetRawData(uint32* dest) const /* Least significant at the beginning. */ { tAssert(dest); tMemcpy(dest, IntData, NumBaseInts*4); } 
189 void SetRawData(const uint32* src) { tAssert(src); tMemcpy(IntData, src, NumBaseInts*4); int r = NumBits%32; uint32& e = IntData[NumBaseInts-1]; e &= r ? ~((0xFFFFFFFF >> r) << r) : 0xFFFFFFFF; } // Least significant at the beginning. Clears any unused bits for you. 
190 uint32& RawElement(int i) { return IntData[i]; } 
191 uint32 GetRawElement(int i) const { return IntData[i]; } 
192 
193 // As expected, there will be one of these per unique template instantiation. 
194 static const int NumBaseInts = NumBits / 32; 
195 
196 // LS stands for Least Significant. MS stands for Most Significant. 
197 #ifdef ENDIAN_BIG 
198 static const int LSIndex = NumBaseInts-1; 
199 static const int MSIndex = 0; 
200 static int BaseIndex(int x) { return LSIndex - x; } 
201 #else 
202 static const int LSIndex = 0; 
203 static const int MSIndex = NumBaseInts-1; 
204 static int BaseIndex(int x) { return x; } 
205 #endif 
206 
207 uint32 IntData[NumBaseInts]; // IntData[0] is the LEAST significant uint32. 
208 
209protected: 
210 template<typename T> void Init(T, uint8 fill = 0); 
211 template<typename T> void Extract(T&, uint8 fill = 0) const; 
212}; 
213 
214 
215// Not all operators should be members, especially binary ones, if you want to be properly object oriented. 
216template<int N> bool operator<(const tFixIntU<N>& a, const tFixIntU<N>& b); 
217template<int N> tFixIntU<N> tSqrt(const tFixIntU<N>&); // Square root. 
218template<int N> tFixIntU<N> tCurt(const tFixIntU<N>&); // Cube root. 
219template<int N> tFixIntU<N> tFactorial(const tFixIntU<N>&); 
220template<int N> bool tIsPow2(const tFixIntU<N>&); 
221template<int N> tFixIntU<N> tNextPow2(const tFixIntU<N>&); 
222template<int N> uint32 tCeilLog2(const tFixIntU<N>&); 
223template<int N> tFixIntU<N> tPow(tFixIntU<N> a, int b); 
224template<int N> tFixIntU<N> tModPow(tFixIntU<N> base, tFixIntU<N> exp, const tFixIntU<N>& mod); 
225 
226 
227// tDivide is here because it offers divide with remainder unlike the binary operator/(). There's also a version here 
228// that is faster if you only need to divide by a smaller (positive) integer. 
229template<int N> tFixIntU<N> tDivide(tFixIntU<N> a, tFixIntU<N> b, tFixIntU<N>* remainder = nullptr); 
230template<int N> tFixIntU<N> tDivide(tFixIntU<N> a, int b, int* remainder = nullptr); 
231 
232 
233// Now we overload the unsigned functions to provide the necessary differences for signed numbers. 
234template<int NumBits> class tFixInt : public tFixIntU<NumBits> 
235{ 
236public: 
237 using tFixIntU<NumBits>::Init; 
238 using tFixIntU<NumBits>::Extract; 
239 using tFixIntU<NumBits>::IntData; 
240 using tFixIntU<NumBits>::MSIndex; 
241 
242 tFixInt() { tStaticAssertMsg(NumBits % 32 == 0, "tFixInt must be a multiple of 32 bits in size."); } 
243 tFixInt(const char* s, int base = -1) { Set(s, base); } 
244 tFixInt(int8 v) { Set(v); } 
245 tFixInt(int16 v) { Set(v); } 
246 tFixInt(int v) { Set(v); } 
247 tFixInt(int64 v) { Set(v); } 
248 tFixInt(uint8 v) { Set(v); } 
249 tFixInt(uint16 v) { Set(v); } 
250 tFixInt(uint v) { Set(v); } 
251 tFixInt(uint64 v) { Set(v); } 
252 tFixInt(float v) { Set(v); } 
253 tFixInt(double v) { Set(v); } 
254 
255 void Set(const char* s, int base = -1) { *this = tStd::tStrtoiT< tFixInt<NumBits> >(s, base); } 
256 void Set(int8 v) { Init(v, (v >= 0) ? 0 : 0xFF); } 
257 void Set(int16 v) { Init(v, (v >= 0) ? 0 : 0xFF); } 
258 void Set(int v) { Init(v, (v >= 0) ? 0 : 0xFF); } 
259 void Set(int64 v) { Init(v, (v >= 0) ? 0 : 0xFF); } 
260 void Set(uint8 v) { Init(v); } 
261 void Set(uint16 v) { Init(v); } 
262 void Set(uint v) { Init(v); } 
263 void Set(uint64 v) { Init(v); } 
264 void Set(float); 
265 void Set(double); 
266 
267 operator int8() const { int8 v; Extract(v, (*this >= 0) ? 0 : 0xFF); return v; } 
268 operator int16() const { int16 v; Extract(v, (*this >= 0) ? 0 : 0xFF); return v; } 
269 operator int() const { int v; Extract(v, (*this >= 0) ? 0 : 0xFF); return v; } 
270 operator int64() const { int64 v; Extract(v, (*this >= 0) ? 0 : 0xFF); return v; } 
271 operator uint8() const { uint8 v; Extract(v); return v; } 
272 operator uint16() const { uint16 v; Extract(v); return v; } 
273 operator uint() const { uint v; Extract(v); return v; } 
274 operator uint64() const { uint64 v; Extract(v); return v; } 
275 operator float() const { if (IntData[MSIndex] >> (32-1) != 0u) return -(float)(-*this).AsUnsigned(); else return (float)AsUnsigned(); } 
276 operator double() const { if (IntData[MSIndex] >> (32-1) != 0u) return -(double)(-*this).AsUnsigned(); else return (double)AsUnsigned(); } 
277 
278 template<int N> tFixInt(const tFixInt<N>& v) { *this = v;} 
279 template<int N> tFixInt(const tFixIntU<N>& v) { *this = v.AsSigned();} 
280 template<int N> tFixInt& operator=(const tFixIntU<N>& v) { return *this = v.AsSigned(); } 
281 template<int N, bool LhsGreater> struct AssignHelper { template <typename T2> void operator()(tFixInt& lhs, const T2& rhs) const; }; 
282 template<int N> struct AssignHelper<N, false> { template <typename T2> void operator()(tFixInt& lhs, const T2& rhs) const; }; 
283 template<int N> tFixInt& operator=(const tFixInt<N>& rhs) { AssignHelper< N, (NumBits>N) >()(*this, rhs); return *this; } 
284 void MakeMin() { *this = tFixIntU<NumBits>(1) << (NumBits-1); } 
285 void MakeMax() { MakeMin(*this); --(*this); } 
286 
287 const tFixIntU<NumBits>& AsUnsigned() const { return reinterpret_cast< const tFixIntU<NumBits>& >(*this); } 
288 tFixIntU<NumBits>& AsUnsigned() { return reinterpret_cast< tFixIntU<NumBits>& >(*this); } 
289 
290 tFixInt& operator&=(const tFixInt& v) { return ( AsUnsigned() &= v.AsUnsigned() ).AsSigned(); } 
291 tFixInt& operator|=(const tFixInt& v) { return ( AsUnsigned() |= v.AsUnsigned() ).AsSigned(); } 
292 tFixInt& operator^=(const tFixInt& v) { return ( AsUnsigned() ^= v.AsUnsigned() ).AsSigned(); } 
293 tFixInt& operator>>=(int shift); 
294 tFixInt& operator<<=(int shift) { return ( AsUnsigned() <<= shift ).AsSigned(); } 
295 tFixInt& operator*=(const tFixInt& v); 
296 tFixInt& operator/=(const tFixInt& v) { return *this = Divide(*this, v, 0); } 
297 tFixInt& operator%=(const tFixInt& v) { Divide(*this, v, this); return *this; } 
298 
299 friend bool operator==(const tFixInt& a, const tFixInt& b) { return a.AsUnsigned() == b.AsUnsigned(); } 
300 friend bool operator!=(const tFixInt& a, const tFixInt& b) { return a.AsUnsigned() != b.AsUnsigned(); } 
301 friend bool operator>(const tFixInt& a, const tFixInt& b) { return (b < a); } 
302 friend bool operator<=(const tFixInt& a, const tFixInt& b) { return !(b < a); } 
303 friend bool operator>=(const tFixInt& a, const tFixInt& b) { return !(a < b); } 
304 
305 const tFixInt operator>>(int shift) const { tFixInt result; result = *this; return (result >>= shift); } 
306 const tFixInt operator<<(int shift) const { return (AsUnsigned() << shift).AsSigned(); } 
307 friend const tFixInt operator&(const tFixInt& a, const tFixInt& b) { return ( a.AsUnsigned() & b.AsUnsigned() ).AsSigned(); } 
308 friend const tFixInt operator|(const tFixInt& a, const tFixInt& b) { return ( a.AsUnsigned() | b.AsUnsigned() ).AsSigned(); } 
309 friend const tFixInt operator^(const tFixInt& a, const tFixInt& b) { return ( a.AsUnsigned() ^ b.AsUnsigned() ).AsSigned(); } 
310 friend const tFixInt operator+(const tFixInt& a, const tFixInt& b) { return ( a.AsUnsigned() + b.AsUnsigned() ).AsSigned(); } 
311 friend const tFixInt operator-(const tFixInt& a, const tFixInt& b) { return ( a.AsUnsigned() - b.AsUnsigned() ).AsSigned(); } 
312 friend const tFixInt operator*(const tFixInt& a, const tFixInt& b) { tFixInt result; result = a; return (result *= b); } 
313 friend const tFixInt operator/(const tFixInt& a, const tFixInt& b) { return tDivide(a, b); } 
314 friend const tFixInt operator%(const tFixInt& a, const tFixInt& b) { tFixInt result; tDivide(a, b, &result); return result; } 
315 
316 tFixInt& operator++() { return (++AsUnsigned()).AsSigned(); } 
317 const tFixInt operator++(int) { return (AsUnsigned()++).AsSigned(); } // @todo Check. 
318 tFixInt& operator--() { return (--AsUnsigned()).AsSigned(); } 
319 const tFixInt operator--(int) { return (AsUnsigned()--).AsSigned(); } // @todo Check. 
320 const tFixInt operator~() const { return ( ~AsUnsigned() ).AsSigned(); } 
321 tFixInt& operator+() const { return (tFixInt&)*this; } // Unary positive. 
322 const tFixInt operator-() const { return ( -AsUnsigned() ).AsSigned(); } // Unary negate. 
323 
324 friend bool operator<(const tFixInt& a, int b) { return a < tFixInt(b); } 
325 friend bool operator>(const tFixInt& a, int b) { return tFixInt(b) < a; } 
326 friend bool operator<=(const tFixInt& a, int b) { return !(tFixInt(b) < a); } 
327 friend bool operator>=(const tFixInt& a, int b) { return !(a < tFixInt(b)); } 
328 friend bool operator==(const tFixInt& a, int b) { return a == tFixInt(b); } 
329 friend bool operator!=(const tFixInt& a, int b) { return a != tFixInt(b); } 
330 friend bool operator<(int a, const tFixInt& b) { return tFixInt(a) < b; } 
331 friend bool operator>(int a, const tFixInt& b) { return b < tFixInt(a); } 
332 friend bool operator<=(int a, const tFixInt& b) { return !(b < tFixInt(a)); } 
333 friend bool operator>=(int a, const tFixInt& b) { return !(tFixInt(a) < b); } 
334 friend bool operator==(int a, const tFixInt& b) { return tFixInt(a) == b; } 
335 friend bool operator!=(int a, const tFixInt& b) { return tFixInt(a) != b; } 
336 
337 friend const tFixInt operator&(const tFixInt& a, int b) { return a & tFixInt(b); } 
338 friend const tFixInt operator|(const tFixInt& a, int b) { return a | tFixInt(b); } 
339 friend const tFixInt operator^(const tFixInt& a, int b) { return a ^ tFixInt(b); } 
340 friend const tFixInt operator&(int a, const tFixInt& b) { return tFixInt(a) & b; } 
341 friend const tFixInt operator|(int a, const tFixInt& b) { return tFixInt(a) | b; } 
342 friend const tFixInt operator^(int a, const tFixInt& b) { return tFixInt(a) ^ b; } 
343 
344 friend const tFixInt operator+(const tFixInt& a, int b) { return a + tFixInt(b); } 
345 friend const tFixInt operator-(const tFixInt& a, int b) { return a - tFixInt(b); } 
346 friend const tFixInt operator*(const tFixInt& a, int b) { return a * tFixInt(b); } 
347 friend const tFixInt operator/(const tFixInt& a, int b) { return tDivide(a, b); } 
348 friend const int operator%(const tFixInt& a, int b) { int r; tDivide(a, b, &r); return r; } 
349 friend const tFixInt operator+(int a, const tFixInt& b) { return tFixInt(a) + b; } 
350 friend const tFixInt operator-(int a, const tFixInt& b) { return tFixInt(a) - b; } 
351 friend const tFixInt operator*(int a, const tFixInt& b) { return tFixInt(a) * b; } 
352 friend const tFixInt operator/(int a, const tFixInt& b) { return tFixInt(a) / b; } 
353 friend const tFixInt operator%(int a, const tFixInt& b) { return tFixInt(a) % b; } 
354}; 
355 
356 
357// Not all operators should be members, especially binary ones, if you want to be properly object oriented. tDivide is 
358// here because it offers divide with remainder unlike the binary operator/(). There's also a version here that is 
359// faster if you only need to divide by a smaller (positive) integer. 
360template<int N> bool operator<(const tFixInt<N>& a, const tFixInt<N>& b); 
361template<int N> tFixInt<N> tSqrt(const tFixInt<N>&); // Square root. 
362template<int N> tFixInt<N> tCurt(const tFixInt<N>&); // cube root. 
363template<int N> tFixInt<N> tAbs(const tFixInt<N>& v); 
364template<int N> tFixInt<N> tFactorial(const tFixInt<N>&); 
365template<int N> tFixInt<N> tPow(const tFixInt<N>& a, int b); 
366template<int N> bool tIsPrime(const tFixInt<N>&); 
367template<int N> tFixInt<N> tDivide(const tFixInt<N>& a, const tFixInt<N>& b, tFixInt<N>* remainder = nullptr); 
368template<int N> tFixInt<N> tDivide(const tFixInt<N>& a, int b, int* remainder = nullptr); 
369 
370 
371// The Tacent tint types are based on the Tacent fix integer (tFixInt). They can represent large integers and allow all 
372// arithmetic and bit operations. They are a bit slower than native 32 or 64 bit integers; however, they are still fixed 
373// size at runtime and therefore faster than other BigInteger implementations that can grow arbitrarily large. The tint 
374// types support both signed and unsigned versions. 
375typedef tFixInt<128> tint128; 
376typedef tFixInt<256> tint256; 
377typedef tFixInt<512> tint512; 
378typedef tFixIntU<128> tuint128; 
379typedef tFixIntU<256> tuint256; 
380typedef tFixIntU<512> tuint512; 
381 
382 
383// Implementation below this line. 
384 
385 
386template<int N> inline void tFixIntU<N>::Set(float v) 
387{ 
388 *this = 0; 
389 if (v != v || (v == v && v-v != 0.0f)) // nan or +/-inf 
390 return; 
391 
392 bool neg = false; 
393 if (v < 0.f) 
394 { 
395 v = -v; 
396 neg = true; 
397 } 
398 
399 if (v < 1.0f) 
400 return; 
401 
402 int e; 
403 float mant = tStd::tFrexp(v, &e); 
404 while (mant > 0.0f && e-- > 0) 
405 { 
406 mant *= 2.0f; 
407 if (mant >= 1.0f) 
408 { 
409 mant -= 1.0f; 
410 if (e < N) 
411 SetBit(e); 
412 } 
413 } 
414 if (neg) 
415 *this = -*this; 
416} 
417 
418 
419template<int N> inline void tFixIntU<N>::Set(double v) 
420{ 
421 *this = 0; 
422 if (v != v || (v == v && v-v != 0.0)) // nan or +/-inf 
423 return; 
424 
425 bool neg = false; 
426 if (v < 0.0) 
427 { 
428 v = -v; 
429 neg = true; 
430 } 
431 
432 if (v < 1.0) 
433 return; 
434 
435 int e; 
436 double mant = tStd::tFrexp(v, &e); 
437 while (mant > 0.0 && e-- > 0) 
438 { 
439 mant *= 2.0; 
440 if (mant >= 1.0) 
441 { 
442 mant -= 1.0; 
443 if (e < N) 
444 SetBit(e); 
445 } 
446 } 
447 
448 if (neg) 
449 *this = -*this; 
450} 
451 
452 
453template<int N> inline tFixIntU<N>::operator float() const 
454{ 
455 static const float multiplier = (float(0xFFFFFFFF) + 1.0f); 
456 float result = 0; 
457 
458 #ifdef ENDIAN_BIG 
459 for (int i = 0; i < NumBaseInts; i++) 
460 #else 
461 for (int i = NumBaseInts-1; i >= 0; i--) 
462 #endif 
463 result = result * multiplier + IntData[i]; 
464 
465 return result; 
466} 
467 
468 
469template<int N> inline tFixIntU<N>::operator double() const 
470{ 
471 static const double multiplier = (double(0xFFFFFFFF) + 1.0); 
472 double result = 0; 
473 
474 #ifdef ENDIAN_BIG 
475 for (int i = 0; i < NumBaseInts; i++) 
476 #else 
477 for (int i = NumBaseInts-1; i >= 0; i--) 
478 #endif 
479 result = result * multiplier + IntData[i]; 
480 
481 return result; 
482} 
483 
484 
485template<int N> inline tString tFixIntU<N>::GetAsString(int base) const 
486{ 
487 // Worst case for string length required is base 2, where N characters are needed. 
488 tString str(N); 
489 tStd::tItostrT< tFixIntU<N> >(*this, str.Text(), N+1, base); 
490 return str; 
491} 
492 
493 
494template<int N> inline void tFixIntU<N>::ClearBit(int b) 
495{ 
496 #ifdef ENDIAN_BIG 
497 IntData[LSIndex - b/32] &= ~(uint32(1)<<(b%32)); 
498 #else 
499 IntData[b/32] &= ~(uint32(1)<<(b%32)); 
500 #endif 
501} 
502 
503 
504template<int N> inline void tFixIntU<N>::SetBit(int b) 
505{ 
506 #ifdef ENDIAN_BIG 
507 IntData[LSIndex - b/32] |= uint32(1)<<(b%32); 
508 #else 
509 IntData[b/32] |= uint32(1)<<(b%32); 
510 #endif 
511} 
512 
513 
514template<int N> inline void tFixIntU<N>::ToggleBit(int b) 
515{ 
516 #ifdef ENDIAN_BIG 
517 IntData[LSIndex - b/32] ^= uint32(1)<<(b%32); 
518 #else 
519 IntData[b/32] ^= uint32(1)<<(b%32); 
520 #endif 
521} 
522 
523 
524template<int N> inline bool tFixIntU<N>::GetBit(int b) const 
525{ 
526 #ifdef ENDIAN_BIG 
527 return (IntData[LSIndex - b/32] & (uint32(1)<<(b%32))) != 0; 
528 #else 
529 return (IntData[b/32] & (uint32(1)<<(b%32))) != 0; 
530 #endif  
531} 
532 
533 
534template<int N> template<typename T> inline void tFixIntU<N>::Init(T v, uint8 fill) 
535{ 
536 if (sizeof(v) <= sizeof(IntData)) 
537 { 
538 #ifdef ENDIAN_BIG 
539 tStd::tMemset(IntData, 0, sizeof(IntData) - sizeof(v)); 
540 tStd::tMemcpy(reinterpret_cast<char*>(IntData) + sizeof(IntData) - sizeof(v), &v, sizeof(v)); 
541 #else 
542 tStd::tMemcpy(IntData, &v, sizeof(v)); 
543 tStd::tMemset(reinterpret_cast<char*>(IntData) + sizeof(v), fill, sizeof(IntData) - sizeof(v)); 
544 #endif 
545 } 
546 else 
547 { 
548 #ifdef ENDIAN_BIG 
549 tStd::tMemcpy(reinterpret_cast<char*>(IntData) - sizeof(IntData) + sizeof(v), reinterpret_cast<char*>(&v) - sizeof(IntData) + sizeof(v), sizeof(IntData)); 
550 #else 
551 tStd::tMemcpy(IntData, &v, sizeof(IntData)); 
552 #endif 
553 } 
554} 
555 
556 
557template<int N> template<typename T> inline void tFixIntU<N>::Extract(T& v, uint8 fill) const 
558{ 
559 if (sizeof(v) <= sizeof(IntData)) 
560 { 
561 #ifdef ENDIAN_BIG 
562 tStd::tMemcpy(&v, reinterpret_cast<char*>(IntData) + sizeof(IntData) - sizeof(v), sizeof(v)); 
563 #else 
564 tStd::tMemcpy(&v, IntData, sizeof(v)); 
565 #endif 
566 } 
567 else 
568 { 
569 #ifdef ENDIAN_BIG 
570 tStd::tMemcpy(reinterpret_cast<char*>(&v) - sizeof(IntData) + sizeof(v), IntData, sizeof(IntData)); 
571 tStd::tMemset(&v, 0, int(sizeof(IntData) - sizeof(v))); 
572 #else 
573 tStd::tMemcpy(&v, IntData, sizeof(IntData)); 
574 tStd::tMemset(reinterpret_cast<char*>(&v) + sizeof(v), fill, int(sizeof(v) - sizeof(IntData))); 
575 #endif 
576 } 
577} 
578 
579 
580template<int N> template<int B, bool LhsGreater> template<typename T> inline void tFixIntU<N>::AssignHelper<B, LhsGreater>::operator()(tFixIntU& lhs, const T& rhs) const 
581{ 
582 const uint32* const rhsData = (uint32*)&rhs; 
583 int i = 0; 
584 #ifdef ENDIAN_BIG 
585 tAssert(!"Fix this to take into account smaller sized type."); 
586 for (; i < NumBaseInts - N / 32; i++) 
587 lhs.IntData[BaseIndex(i)] = 0u; 
588 for (; i < NumBaseInts; i++) 
589 lhs.IntData[BaseIndex(i)] = rhsData[BaseIndex(i)]; 
590 #else 
591 // If rhs is smaller, copy what we can over and fill in the rest with 0. 
592 // If lhs is smaller, we may lose info (like casting an int to a short). 
593 int lhsNum = lhs.NumBaseInts; 
594 int rhsNum = rhs.NumBaseInts; 
595 for (; i < tMath::tMin(lhsNum, rhsNum); i++) 
596 lhs.IntData[BaseIndex(i)] = rhsData[BaseIndex(i)]; 
597 for (; i < NumBaseInts; i++) 
598 lhs.IntData[BaseIndex(i)] = 0u; 
599 #endif 
600} 
601 
602 
603template<int N> template<int B> template<typename T> inline void tFixIntU<N>::AssignHelper<B, false>::operator()(tFixIntU& lhs, const T& rhs) const 
604{ 
605 const uint32* rhsData = (uint32*)&rhs; 
606 #ifdef ENDIAN_BIG 
607 rhsData += (N-B) / 32; 
608 #endif 
609 for (int i = 0; i < NumBaseInts; i++) 
610 lhs.IntData[BaseIndex(i)] = rhsData[BaseIndex(i)]; 
611} 
612 
613 
614template<int N> inline tFixIntU<N> tDivide(tFixIntU<N> a, tFixIntU<N> b, tFixIntU<N>* remainder) 
615{ 
616 int shiftcnt = 0; 
617 if (!b) 
618 { 
619 shiftcnt = 1 / shiftcnt; 
620 tFixIntU<N> r; 
621 r.MakeMaxInt(); 
622 return r; 
623 } 
624 
625 shiftcnt = a.FindHighestBitSet() - b.FindHighestBitSet(); 
626 if (shiftcnt > 0) 
627 b <<= shiftcnt; 
628 
629 if (b > a) 
630 { 
631 b >>= 1; 
632 --shiftcnt; 
633 } 
634 
635 tFixIntU<N> c(0u); 
636 while (shiftcnt >= 0) 
637 { 
638 if (b <= a)\ 
639 { 
640 a -= b; 
641 c.SetBit(shiftcnt); 
642 } 
643 b >>= 1; 
644 --shiftcnt; 
645 } 
646 
647 if (remainder) 
648 *remainder = a; 
649 return c; 
650} 
651 
652 
653template<int N> inline tFixIntU<N> tDivide(tFixIntU<N> a, int b, int* remainder) 
654{ 
655 // Special version of division that's fast but only works with small divisors. 'a' must be positive. 
656 tAssert(b); 
657 uint32 temp = 0; 
658 bool seenNonZero = false; 
659 tFixInt<N> result = 0; 
660 
661 #ifdef ENDIAN_BIG 
662 for (int i = 0; i < a.GetRawCount(); i++) 
663 #else 
664 for (int i = a.GetRawCount()-1; i >= 0; i--) 
665 #endif 
666 { 
667 if (seenNonZero || a.RawElement(i) != 0) 
668 { 
669 uint32 sh1 = a.RawElement(i) >> 16; 
670 temp = (temp << 16) + sh1; 
671 sh1 = temp / b; 
672 temp %= b; 
673 
674 uint32 sh2 = (a.RawElement(i) << 16) >> 16; 
675 temp = (temp << 16) + sh2; 
676 sh2 = temp / b; 
677 temp %= b; 
678 
679 result.RawElement(i) = (sh1 << 16) | sh2; 
680 seenNonZero = true; 
681 } 
682 } 
683 if (remainder) 
684 *remainder = int(temp); 
685 
686 return result; 
687} 
688 
689 
690template<int N> inline tFixIntU<N>& tFixIntU<N>::operator*=(const tFixIntU& m) 
691{ 
692 // This method of multiplication is exactly how you do long multiplication by hand except 
693 // that it's base 2 instead of base 10. 
694 tFixIntU v(m); 
695 tFixIntU t; 
696 t = *this; 
697 *this = tFixIntU(0u); 
698 do 
699 { 
700 if ((v.IntData[LSIndex] & 1U) != 0u) 
701 *this += t; 
702 v >>= 1; 
703 t <<= 1; 
704 } while (!!v); 
705 
706 return *this; 
707} 
708 
709 
710template<int N> inline tFixIntU<N>& tFixIntU<N>::operator*=(const uint32 m) 
711{ 
712 uint32 v = m; 
713 tFixIntU t; 
714 t = *this; 
715 *this = (tFixIntU)0u; 
716 int shift = 0; 
717 while (v) 
718 { 
719 // Skip consecutive zeroes all at once. 
720 while ((v & 1U) == 0) 
721 { 
722 v >>= 1; 
723 ++shift; 
724 } 
725 t <<= shift; 
726 v >>= 1; 
727 shift = 1; 
728 *this += t; 
729 } 
730 return *this; 
731} 
732 
733 
734template<int N> inline bool operator<(const tFixIntU<N>& a, const tFixIntU<N>& b) 
735{ 
736 #ifdef ENDIAN_BIG 
737 for (int i = 0; i < tFixIntU<N>::NumBaseInts; i++) 
738 #else 
739 for (int i = a.GetRawCount()-1; i >= 0; i--) 
740 #endif 
741 { 
742 if (a.GetRawElement(i) < b.GetRawElement(i)) 
743 return true; 
744 if (a.GetRawElement(i) > b.GetRawElement(i)) 
745 return false; 
746 } 
747 
748 return false; 
749} 
750 
751 
752template<int N> inline tFixIntU<N>& tFixIntU<N>::operator>>=(int shift) 
753{ 
754 int source = shift / 32; 
755 int remaindershift = shift & (32-1); 
756 int othershift = 32 - remaindershift; 
757 
758 #ifdef ENDIAN_BIG 
759 for (int i = NumBaseInts-1; i >= 0; i--) 
760 #else 
761 for (int i = 0; i < NumBaseInts; i++) 
762 #endif 
763 { 
764 if (source < NumBaseInts) 
765 { 
766 IntData[i] = IntData[BaseIndex(source)] >> remaindershift; 
767 if (++source < NumBaseInts && othershift < 32) 
768 IntData[i] |= IntData[BaseIndex(source)] << othershift; 
769 } 
770 else 
771 { 
772 IntData[i] = 0u; 
773 } 
774 } 
775 return *this; 
776} 
777 
778 
779template<int N> inline tFixIntU<N>& tFixIntU<N>::operator<<=(int shift) 
780{ 
781 int source = NumBaseInts-1 - shift / 32; 
782 int remaindershift = shift & (32-1); 
783 int othershift = 32 - remaindershift; 
784 
785 #ifdef ENDIAN_BIG 
786 for (int i = 0; i < NumBaseInts; i++) 
787 #else 
788 for (int i = NumBaseInts-1; i >= 0; i--) 
789 #endif 
790 { 
791 if (source >= 0) 
792 { 
793 IntData[i] = IntData[BaseIndex(source)] << remaindershift; 
794 if (--source >= 0 && othershift < 32) 
795 IntData[i] |= IntData[BaseIndex(source)] >> othershift; 
796 } 
797 else 
798 { 
799 IntData[i] = 0u; 
800 } 
801 } 
802 return *this; 
803} 
804 
805 
806template<int N> inline tFixIntU<N>& tFixIntU<N>::operator+=(const tFixIntU& v) 
807{ 
808 uint32 carry = 0u; 
809 #ifdef ENDIAN_BIG 
810 for (int i = NumBaseInts-1; i >= 0; i--) 
811 #else 
812 for (int i = 0; i < NumBaseInts; i++) 
813 #endif 
814 { 
815 IntData[i] += v.IntData[i] + carry; 
816 if (!carry) 
817 carry = (IntData[i] < v.IntData[i]); 
818 else 
819 carry = (IntData[i] <= v.IntData[i]); 
820 } 
821 return *this; 
822} 
823 
824 
825template<int N> inline tFixIntU<N>& tFixIntU<N>::operator-=(const tFixIntU& v) 
826{ 
827 uint32 borrow = 0u, prevdigit; 
828 
829 #ifdef ENDIAN_BIG 
830 for (int i = NumBaseInts-1; i >= 0; i--) 
831 #else 
832 for (int i = 0; i < NumBaseInts; i++) 
833 #endif 
834 { 
835 prevdigit = IntData[i]; 
836 IntData[i] -= v.IntData[i] + borrow; 
837 if (!borrow) 
838 borrow = (prevdigit < v.IntData[i]); 
839 else 
840 borrow = (prevdigit <= v.IntData[i]); 
841 } 
842 return *this; 
843} 
844 
845 
846template<int N> inline tFixIntU<N>& tFixIntU<N>::operator++() 
847{ 
848 ++IntData[LSIndex]; 
849 #ifdef ENDIAN_BIG 
850 for (int i = NumBaseInts-1; i > 0; i--) 
851 { 
852 if (!IntData[i]) 
853 ++IntData[i-1]; 
854 else 
855 break; 
856 } 
857 #else 
858 for (int i = 0; i < NumBaseInts-1; i++) 
859 { 
860 if (!IntData[i]) 
861 ++IntData[i+1]; 
862 else 
863 break; 
864 } 
865 #endif 
866 return *this; 
867} 
868 
869 
870template<int N> inline tFixIntU<N>& tFixIntU<N>::operator--() 
871{ 
872 --IntData[LSIndex]; 
873 #ifdef ENDIAN_BIG 
874 for (int i = NumBaseInts-1; i > 0; i--) 
875 { 
876 if (IntData[i] == 0xFFFFFFFF) 
877 --IntData[i-1]; 
878 else 
879 break; 
880 } 
881 #else 
882 for (int i = 0; i < NumBaseInts-1; i++) 
883 { 
884 if (IntData[i] == 0xFFFFFFFF) 
885 --IntData[i+1]; 
886 else 
887 break; 
888 } 
889 #endif 
890 return *this; 
891} 
892 
893 
894template<int N> inline tFixIntU<N> tSqrt(const tFixIntU<N>& v) 
895{ 
896 static const tFixIntU<N> mask = ~tFixIntU<N>(1); 
897 if (!v) 
898 return v; 
899 
900 tFixIntU<N> x = v >> (v.FindHighestBitSet()>>1); 
901 tFixIntU<N> dx; 
902 do 
903 { 
904 // We are really performing the fuction: dx = (y/x - x) / 2 but since these are unsigned numbers we MUST 
905 // do the subtraction last in order for the x += dx evaluation to work properly. 
906 dx = (v>>1)/x - (x>>1); 
907 x += dx; 
908 } while (!!(dx & mask)); 
909  
910 // truncate answer 
911 if (x*x > v) 
912 --x; 
913 
914 return x; 
915} 
916 
917 
918template<int N> inline tFixIntU<N> tCurt(const tFixIntU<N>& v) 
919{ 
920 if (!v) 
921 return v; 
922 
923 tFixIntU<N> x = v >> ((2*v.FindHighestBitSet())/3); 
924 tFixIntU<N> dx; 
925 do 
926 { 
927 dx = (v/(x*x) - x)/3; 
928 x += dx; 
929 } while (!!dx); 
930 
931 if (x*x*x > v) 
932 --x; 
933 
934 return x; 
935} 
936 
937 
938template<int N> inline tFixIntU<N> tFactorial(const tFixIntU<N>& v) 
939{ 
940 uint32 f = v; 
941 
942 // If the number to take the factorial of is bigger than can fit into an unsigned long then the there's no way in 
943 // hell the result can be stored in conventional PC memory anyway. 
944 tFixIntU<N> result = 1; 
945 while (f > 0u) 
946 result *= f--; 
947 
948 return result; 
949} 
950 
951 
952template<int N> inline void tFixIntU<N>::RotateRight(int shift) 
953{ 
954 tFixIntU result; 
955 int source = (shift / 32) % NumBaseInts; 
956 int remaindershift = shift & (32-1); 
957 
958 if (remaindershift != 0) 
959 { 
960 int othershift = 32 - remaindershift; 
961 
962 #ifdef ENDIAN_BIG 
963 for (int i = NumBaseInts-1; i >= 0; i--) 
964 #else 
965 for (int i = 0; i < NumBaseInts; i++) 
966 #endif 
967 { 
968 int source1 = source; 
969 if (++source == NumBaseInts) 
970 source = 0; 
971 result.IntData[i] = (IntData[BaseIndex(source1)] >> remaindershift) | (IntData[BaseIndex(source)] << othershift); 
972 } 
973 } 
974 else 
975 { 
976 #ifdef ENDIAN_BIG 
977 for (int i = NumBaseInts-1; i >= 0; i--) 
978 #else 
979 for (int i = 0; i < NumBaseInts; i++) 
980 #endif 
981 { 
982 result.IntData[i] = IntData[BaseIndex(source)]; 
983 if (++source == NumBaseInts) 
984 source = 0; 
985 } 
986 } 
987 *this = result; 
988} 
989 
990 
991template<int N> inline int tFixIntU<N>::FindHighestBitSet() const 
992{ 
993 int result = N-1; 
994 #ifdef ENDIAN_BIG 
995 for (int i = 0; i < tFixIntU<N>::NumBaseInts; i++) 
996 #else 
997 for (int i = tFixIntU<N>::NumBaseInts-1; i >= 0; i--) 
998 #endif 
999 { 
1000 if (IntData[i] != 0) 
1001 { 
1002 uint32 temp = IntData[i]; 
1003 uint32 tempMax = 0xFFFFFFFF; 
1004 int shift = 16; 
1005 do 
1006 { 
1007 tempMax <<= shift; 
1008 if ((temp & tempMax) == 0) 
1009 { 
1010 result -= shift; 
1011 temp = temp << shift; 
1012 } 
1013 } while ((shift>>=1) > 0); 
1014 break; 
1015 } 
1016 result -= 32; 
1017 } 
1018 return result; 
1019} 
1020 
1021 
1022template<int N> inline int tFixIntU<N>::FindLowestBitSet() const 
1023{ 
1024 int result = 0; 
1025 #ifdef ENDIAN_BIG 
1026 for (int i = NumBaseInts-1; i >= 0; i--) 
1027 #else 
1028 for (int i = 0; i < NumBaseInts; i++) 
1029 #endif 
1030 { 
1031 if (IntData[i] != 0) 
1032 { 
1033 uint32 temp = IntData[i]; 
1034 uint32 tempMax = 0xFFFFFFFF; 
1035 int shift = 16; 
1036 do 
1037 { 
1038 tempMax >>= shift; 
1039 if ((temp & tempMax) == 0) 
1040 { 
1041 result += shift; 
1042 temp = temp >> shift; 
1043 } 
1044 } while ((shift>>=1) > 0); 
1045 break; 
1046 } 
1047 result += 32; 
1048 } 
1049 return result; 
1050} 
1051 
1052 
1053template<int N> inline bool tIsPow2(const tFixIntU<N>& v) 
1054{ 
1055 bool found = false; 
1056 for (int i = 0; i < tFixIntU<N>::NumBaseInts; i++) 
1057 { 
1058 if (v.IntData[i] != 0) 
1059 { 
1060 if (found) 
1061 return false; 
1062 if ((v.IntData[i] & (v.IntData[i]-1)) != 0) 
1063 return false; 
1064 
1065 found = true; 
1066 } 
1067 } 
1068 return true; 
1069} 
1070 
1071 
1072template<int N> inline tFixIntU<N> tNextPow2(const tFixIntU<N>& v) 
1073{ 
1074 tFixIntU<N> result; 
1075 result = v - (tFixIntU<N>)1U; 
1076 int shift = 1; 
1077 do 
1078 { 
1079 result |= result >> shift; 
1080 shift <<= 1; 
1081 } while (shift < N); 
1082 ++result; 
1083 return result; 
1084} 
1085 
1086 
1087template<int N> inline uint32 tCeilLog2(const tFixIntU<N>& v) 
1088{ 
1089 tFixIntU<N> temp, temp2; 
1090 uint32 result = 0u; 
1091 int shift = N >> 1; 
1092 
1093 temp = v; 
1094 do 
1095 { 
1096 temp2 = temp >> shift; 
1097 if (!!temp2) 
1098 { 
1099 temp = temp2; 
1100 result |= shift; 
1101 } 
1102 } while ((shift >>= 1) > 0); 
1103 return result; 
1104} 
1105 
1106 
1107template<int N> inline tFixIntU<N> tPow(tFixIntU<N> a, int b) 
1108{ 
1109 tFixIntU<N> result; 
1110 if (b < 0) 
1111 return (tFixIntU<N>)0; 
1112 
1113 result = (tFixIntU<N>)1U; 
1114 
1115 if (a == result) 
1116 return result; 
1117 while (b) 
1118 { 
1119 if (b & 1) 
1120 result *= a; 
1121 b >>= 1; 
1122 a *= a; 
1123 } 
1124 return result; 
1125} 
1126 
1127 
1128template<int N> inline tFixIntU<N> tModPow(tFixIntU<N> base, tFixIntU<N> exp, const tFixIntU<N>& mod) 
1129{ 
1130 tFixIntU<N> result; 
1131 result = 1; 
1132 while (exp > 0) 
1133 { 
1134 if (!!(exp & 1)) 
1135 result = (result * base) % mod; 
1136 exp >>= 1; 
1137 base = (base * base) % mod; 
1138 } 
1139 return result; 
1140} 
1141 
1142 
1143template<int N> inline void tFixInt<N>::Set(float f) 
1144{ 
1145 *this = 0; 
1146 if (f != f || (f == f && f-f != 0.f)) // NAN or +/-inf. 
1147 { 
1148 tFixIntU<N>::SetBit(N-1); 
1149 return; 
1150 } 
1151 
1152 bool neg = false; 
1153 if (f < 0.f) 
1154 { 
1155 f = -f; 
1156 neg = true; 
1157 } 
1158 
1159 if (f < 1.0f) 
1160 return; 
1161 
1162 int e; 
1163 float mant = tStd::tFrexp(f, &e); 
1164 while (mant > 0.0f && e-- > 0) 
1165 { 
1166 mant *= 2.0f; 
1167 if (mant >= 1.0f) 
1168 { 
1169 mant -= 1.0f; 
1170 if (e < N) 
1171 tFixIntU<N>::SetBit(e); 
1172 } 
1173 } 
1174 
1175 if (neg) 
1176 *this = -*this; 
1177} 
1178 
1179 
1180template<int N> inline void tFixInt<N>::Set(double d) 
1181{ 
1182 *this = 0; 
1183 if (d != d || (d == d && d-d != 0.0)) // nan or +/-inf 
1184 { 
1185 tFixIntU<N>::SetBit(N-1); 
1186 return; 
1187 } 
1188 
1189 bool neg = false; 
1190 if (d < 0.0) 
1191 { 
1192 d = -d; 
1193 neg = true; 
1194 } 
1195 
1196 if (d < 1.0) 
1197 return; 
1198 
1199 int e; 
1200 double mant = tStd::tFrexp(d, &e); 
1201 while (mant > 0.0 && e-- > 0) 
1202 { 
1203 mant *= 2.0; 
1204 if (mant >= 1.0) 
1205 { 
1206 mant -= 1.0; 
1207 if (e < N) 
1208 tFixIntU<N>::SetBit(e); 
1209 } 
1210 } 
1211 
1212 if (neg) 
1213 *this = -*this; 
1214} 
1215 
1216 
1217template<int B> template<int N, bool LhsGreater> template<typename T2> inline void tFixInt<B>::AssignHelper<N, LhsGreater>::operator()(tFixInt& lhs, const T2& rhs) const 
1218{ 
1219 const uint32* const accessorHack = (uint32*)&rhs; 
1220 int i = 0; 
1221  
1222 #ifdef ENDIAN_BIG 
1223 tAssert(!"Fix this to take into account smaller sized type."); 
1224 if (rhs < tFixInt<N>(0u)) // Sign extend. 
1225 { 
1226 for (; i < tFixIntU<B>::NumBaseInts - N / 32; i++) 
1227 lhs.IntData[tFixIntU<B>::BaseIndex(i)] = 0xFFFFFFFF; 
1228 } 
1229 else 
1230 { 
1231 for (; i < tFixIntU<B>::NumBaseInts - N / 32; i++) 
1232 lhs.IntData[tFixIntU<B>::BaseIndex(i)] = 0u; 
1233 } 
1234 
1235 for (; i < tFixIntU<B>::NumBaseInts; i++) 
1236 lhs.IntData[tFixIntU<B>::BaseIndex(i)] = accessorHack[tFixIntU<B>::BaseIndex(i)]; 
1237 
1238 #else 
1239 int lhsNum = lhs.NumBaseInts; 
1240 int rhsNum = rhs.NumBaseInts; 
1241 for (; i < tMath::tMin(lhsNum, rhsNum); i++) 
1242 lhs.IntData[tFixInt<B>::BaseIndex(i)] = accessorHack[tFixInt<B>::BaseIndex(i)]; 
1243 
1244 if (rhs < tFixInt<N>(0u)) // Sign extend. 
1245 { 
1246 for (; i < tFixIntU<B>::NumBaseInts; i++) 
1247 lhs.IntData[tFixIntU<B>::BaseIndex(i)] = 0xFFFFFFFF; 
1248 } 
1249 else 
1250 { 
1251 for (; i < tFixIntU<B>::NumBaseInts; i++) 
1252 lhs.IntData[tFixIntU<B>::BaseIndex(i)] = 0u; 
1253 } 
1254 #endif 
1255} 
1256 
1257 
1258template<int B> template<int N> template<typename T2> inline void tFixInt<B>::AssignHelper<N, false>::operator()(tFixInt& lhs, const T2& rhs) const 
1259{ 
1260 const uint32 *accessorHack = (uint32*)&rhs; 
1261 #ifdef ENDIAN_BIG 
1262 accessorHack += (N-B) / 32; 
1263 #endif 
1264 for (int i = 0; i < tFixIntU<B>::NumBaseInts; i++) 
1265 lhs.IntData[tFixIntU<B>::BaseIndex(i)] = accessorHack[tFixIntU<B>::BaseIndex(i)]; 
1266} 
1267 
1268 
1269template<int N> inline tFixInt<N>& tFixInt<N>::operator>>=(int shift) 
1270{ 
1271 if (IntData[MSIndex] >> (32-1) != 0) 
1272 { 
1273 int source = shift / 32; 
1274 int remaindershift = shift & (32-1); 
1275 int othershift = 32 - remaindershift; 
1276 
1277 #ifdef ENDIAN_BIG 
1278 for (int i = tFixIntU<N>::NumBaseInts-1; i >= 0; i--) 
1279 #else 
1280 for (int i = 0; i < tFixIntU<N>::NumBaseInts; i++) 
1281 #endif 
1282 { 
1283 if (source < tFixIntU<N>::NumBaseInts) 
1284 { 
1285 IntData[i] = this->IntData[tFixIntU<N>::BaseIndex(source++)] >> remaindershift; 
1286 if (othershift < 32) 
1287 IntData[i] |= ((source < tFixIntU<N>::NumBaseInts) ? IntData[tFixIntU<N>::BaseIndex(source)] : 0xFFFFFFFF) << othershift; 
1288 } 
1289 else 
1290 { 
1291 IntData[i] = 0xFFFFFFFF; 
1292 } 
1293 } 
1294 } 
1295 else 
1296 { 
1297 AsUnsigned() >>= shift; 
1298 } 
1299 return *this; 
1300} 
1301 
1302 
1303template<int N> inline tFixInt<N>& tFixInt<N>::operator*=(const tFixInt& v) 
1304{ 
1305 if (IntData[MSIndex] >> (32-1) != 0u) 
1306 { 
1307 *this = -*this; 
1308 if (v.IntData[MSIndex] >> (32-1) != 0u) 
1309 { 
1310 return (AsUnsigned() *= (-v).AsUnsigned()).AsSigned(); 
1311 } 
1312 else 
1313 { 
1314 AsUnsigned() *= v.AsUnsigned(); 
1315 return *this = -*this; 
1316 } 
1317 } 
1318 else 
1319 { 
1320 if (v.IntData[MSIndex] >> (32-1) != 0u) 
1321 { 
1322 AsUnsigned() *= (-v).AsUnsigned(); 
1323 return *this = -*this; 
1324 } 
1325 else 
1326 { 
1327 return (AsUnsigned() *= v.AsUnsigned()).AsSigned(); 
1328 } 
1329 } 
1330} 
1331 
1332 
1333template<int N> inline bool operator<(const tFixInt<N>& a, const tFixInt<N>& b) 
1334{ 
1335 uint32 lhsHighChunk = a.IntData[tFixIntU<N>::MSIndex] ^ (uint32(1) << (32-1)); 
1336 uint32 rhsHighChunk = b.IntData[tFixIntU<N>::MSIndex] ^ (uint32(1) << (32-1)); 
1337 
1338 if (lhsHighChunk < rhsHighChunk) 
1339 return true; 
1340 if (lhsHighChunk > rhsHighChunk) 
1341 return false; 
1342 
1343 #ifdef ENDIAN_BIG 
1344 for (int i = 1; i < tFixIntU<N>::NumBaseInts-1; i++) 
1345 #else 
1346 for (int i = tFixIntU<N>::NumBaseInts-2; i >= 0; i--) 
1347 #endif 
1348 { 
1349 if (a.IntData[i] < b.IntData[i]) 
1350 return true; 
1351 if (a.IntData[i] > b.IntData[i]) 
1352 return false; 
1353 } 
1354 return false; 
1355} 
1356 
1357 
1358template<int N> inline tFixInt<N> tSqrt(const tFixInt<N>& v) 
1359{ 
1360 if (v.IntData[tFixIntU<N>::MSIndex] >> (32-1) != 0u) 
1361 return tFixInt<N>(0u); // If negative just return zero. 
1362 
1363 return tSqrt(v.AsUnsigned()).AsSigned(); 
1364} 
1365 
1366 
1367template<int N> inline tFixInt<N> tCurt(const tFixInt<N>& v) 
1368{ 
1369 tFixInt<N> x, dx; 
1370 
1371 if (!v) 
1372 { 
1373 return v; 
1374 } 
1375 else 
1376 { 
1377 x = v >> ((2*v.FindHighestBitSet())/3); 
1378 
1379 do 
1380 { 
1381 dx = (v/(x*x) - x)/3; 
1382 x += dx; 
1383 } while (!!dx); 
1384 
1385 if (v < 0) // Truncate answer. 
1386 { 
1387 if (x*x*x < v) 
1388 ++x; 
1389 } 
1390 else 
1391 { 
1392 if (x*x*x > v) 
1393 --x; 
1394 } 
1395 return x; 
1396 } 
1397} 
1398 
1399 
1400template<int N> inline tFixInt<N> tAbs(const tFixInt<N>& v) 
1401{ 
1402 return (v.IntData[tFixIntU<N>::MSIndex] >> (32-1) != 0u) ? -v : v; 
1403} 
1404 
1405 
1406template<int N> inline tFixInt<N> tFactorial(const tFixInt<N>& v) 
1407{ 
1408 if (v.IntData[tFixIntU<N>::MSIndex] >> (32-1) != 0u) 
1409 return tFixInt<N>(0u); 
1410 
1411 return tFactorial(v.AsUnsigned()).AsSigned(); 
1412} 
1413 
1414 
1415template<int N> inline tFixInt<N> tPow(const tFixInt<N>& a, int b) 
1416{ 
1417 tFixInt<N> temp; 
1418 temp = tPow(tAbs(a).AsUnsigned(), b).AsSigned(); 
1419 return ((a.IntData[tFixIntU<N>::MSIndex] >> (32-1) != 0u) && ((b & 1) != 0)) ? -temp : temp; 
1420} 
1421 
1422 
1423template<int N> inline bool tIsPrime(const tFixInt<N>& v) 
1424{ 
1425 if (v.IntData[tFixIntU<N>::MSIndex] >> (32-1) != 0u) 
1426 return false; 
1427 return v.AsUnsigned().tIsPrime(); 
1428} 
1429 
1430 
1431template<int N> inline tFixInt<N> tDivide(const tFixInt<N>& a, const tFixInt<N>& b, tFixInt<N>* remainder) 
1432{ 
1433 tAssert(b != 0); 
1434 if (a.IntData[tFixInt<N>::MSIndex] >> (32-1) != 0u) 
1435 { 
1436 tFixInt<N> result; 
1437 if (b.IntData[tFixInt<N>::MSIndex] >> (32-1) != 0u) 
1438 result = tDivide((-a).AsUnsigned(), (-b).AsUnsigned(), (tFixIntU<N>*)remainder).AsSigned(); 
1439 else 
1440 result = -tDivide((-a).AsUnsigned(), b.AsUnsigned(), (tFixIntU<N>*)remainder).AsSigned(); 
1441  
1442 if (remainder) 
1443 *remainder = -*remainder; 
1444  
1445 return result; 
1446 } 
1447 else 
1448 { 
1449 if (b.IntData[tFixInt<N>::MSIndex] >> (32-1) != 0u) 
1450 return -tDivide(a.AsUnsigned(), (-b).AsUnsigned(), (tFixIntU<N>*)remainder).AsSigned(); 
1451 else 
1452 return tDivide(a.AsUnsigned(), b.AsUnsigned(), (tFixIntU<N>*)remainder).AsSigned(); 
1453 } 
1454} 
1455 
1456 
1457template<int N> inline tFixInt<N> tDivide(const tFixInt<N>& a, int b, int* remainder) 
1458{ 
1459 tAssert(b != 0); 
1460 if (a.IntData[tFixInt<N>::MSIndex] >> (32-1) != 0u) 
1461 { 
1462 tFixInt<N> result; 
1463 if (b < 0) 
1464 result = tDivide((-a).AsUnsigned(), -b, remainder).AsSigned(); 
1465 else 
1466 result = -tDivide((-a).AsUnsigned(), b, remainder).AsSigned(); 
1467  
1468 if (remainder) 
1469 *remainder = -*remainder; 
1470  
1471 return result; 
1472 } 
1473 else 
1474 { 
1475 if (b < 0) 
1476 return -tDivide(a.AsUnsigned(), -b, remainder).AsSigned(); 
1477 else 
1478 return tDivide(a.AsUnsigned(), b, remainder).AsSigned(); 
1479 } 
1480} 
1481