Stephen Paulger / ttmath

Library for big numbers from http://www.ttmath.org/

Dependents:   PIDHeater82 Conceptcontroller_v_1_0 AlarmClockApp COG4050_adxl355_tilt ... more

TTMath is a small library which allows one to perform arithmetic operations with big unsigned integer, big signed integer and big floating point numbers. It provides standard mathematical operations like adding, subtracting, multiplying, dividing.

TTMath is BSD Licensed (new/modified BSD)

For more information about ttmath see http://www.ttmath.org/

ttmathuint.h@0:04a9f72bbca7, 2013-07-30 (annotated)

Committer:
stevep
Date:
Tue Jul 30 18:43:48 2013 +0000
Revision:
0:04a9f72bbca7
v0.9.3 of ttmath

Who changed what in which revision?

UserRevisionLine numberNew contents of line
stevep 0:04a9f72bbca7 1 /*
stevep 0:04a9f72bbca7 2 * This file is a part of TTMath Bignum Library
stevep 0:04a9f72bbca7 3 * and is distributed under the (new) BSD licence.
stevep 0:04a9f72bbca7 4 * Author: Tomasz Sowa <t.sowa@ttmath.org>
stevep 0:04a9f72bbca7 5 */
stevep 0:04a9f72bbca7 6
stevep 0:04a9f72bbca7 7 /*
stevep 0:04a9f72bbca7 8 * Copyright (c) 2006-2011, Tomasz Sowa
stevep 0:04a9f72bbca7 9 * All rights reserved.
stevep 0:04a9f72bbca7 10 *
stevep 0:04a9f72bbca7 11 * Redistribution and use in source and binary forms, with or without
stevep 0:04a9f72bbca7 12 * modification, are permitted provided that the following conditions are met:
stevep 0:04a9f72bbca7 13 *
stevep 0:04a9f72bbca7 14 * * Redistributions of source code must retain the above copyright notice,
stevep 0:04a9f72bbca7 15 * this list of conditions and the following disclaimer.
stevep 0:04a9f72bbca7 16 *
stevep 0:04a9f72bbca7 17 * * Redistributions in binary form must reproduce the above copyright
stevep 0:04a9f72bbca7 18 * notice, this list of conditions and the following disclaimer in the
stevep 0:04a9f72bbca7 19 * documentation and/or other materials provided with the distribution.
stevep 0:04a9f72bbca7 20 *
stevep 0:04a9f72bbca7 21 * * Neither the name Tomasz Sowa nor the names of contributors to this
stevep 0:04a9f72bbca7 22 * project may be used to endorse or promote products derived
stevep 0:04a9f72bbca7 23 * from this software without specific prior written permission.
stevep 0:04a9f72bbca7 24 *
stevep 0:04a9f72bbca7 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
stevep 0:04a9f72bbca7 26 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
stevep 0:04a9f72bbca7 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
stevep 0:04a9f72bbca7 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
stevep 0:04a9f72bbca7 29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
stevep 0:04a9f72bbca7 30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
stevep 0:04a9f72bbca7 31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
stevep 0:04a9f72bbca7 32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
stevep 0:04a9f72bbca7 33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
stevep 0:04a9f72bbca7 34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
stevep 0:04a9f72bbca7 35 * THE POSSIBILITY OF SUCH DAMAGE.
stevep 0:04a9f72bbca7 36 */
stevep 0:04a9f72bbca7 37
stevep 0:04a9f72bbca7 38
stevep 0:04a9f72bbca7 39
stevep 0:04a9f72bbca7 40 #ifndef headerfilettmathuint
stevep 0:04a9f72bbca7 41 #define headerfilettmathuint
stevep 0:04a9f72bbca7 42
stevep 0:04a9f72bbca7 43
stevep 0:04a9f72bbca7 44 /*!
stevep 0:04a9f72bbca7 45 \file ttmathuint.h
stevep 0:04a9f72bbca7 46 \brief template class UInt<uint>
stevep 0:04a9f72bbca7 47 */
stevep 0:04a9f72bbca7 48
stevep 0:04a9f72bbca7 49 #include <iostream>
stevep 0:04a9f72bbca7 50 #include <iomanip>
stevep 0:04a9f72bbca7 51
stevep 0:04a9f72bbca7 52
stevep 0:04a9f72bbca7 53 #include "ttmathtypes.h"
stevep 0:04a9f72bbca7 54 #include "ttmathmisc.h"
stevep 0:04a9f72bbca7 55
stevep 0:04a9f72bbca7 56
stevep 0:04a9f72bbca7 57
stevep 0:04a9f72bbca7 58 /*!
stevep 0:04a9f72bbca7 59 \brief a namespace for the TTMath library
stevep 0:04a9f72bbca7 60 */
stevep 0:04a9f72bbca7 61 namespace ttmath
stevep 0:04a9f72bbca7 62 {
stevep 0:04a9f72bbca7 63
stevep 0:04a9f72bbca7 64 /*!
stevep 0:04a9f72bbca7 65 \brief UInt implements a big integer value without a sign
stevep 0:04a9f72bbca7 66
stevep 0:04a9f72bbca7 67 value_size - how many bytes specify our value
stevep 0:04a9f72bbca7 68 on 32bit platforms: value_size=1 -> 4 bytes -> 32 bits
stevep 0:04a9f72bbca7 69 on 64bit platforms: value_size=1 -> 8 bytes -> 64 bits
stevep 0:04a9f72bbca7 70 value_size = 1,2,3,4,5,6....
stevep 0:04a9f72bbca7 71 */
stevep 0:04a9f72bbca7 72 template<uint value_size>
stevep 0:04a9f72bbca7 73 class UInt
stevep 0:04a9f72bbca7 74 {
stevep 0:04a9f72bbca7 75 public:
stevep 0:04a9f72bbca7 76
stevep 0:04a9f72bbca7 77 /*!
stevep 0:04a9f72bbca7 78 buffer for the integer value
stevep 0:04a9f72bbca7 79 table[0] - the lowest word of the value
stevep 0:04a9f72bbca7 80 */
stevep 0:04a9f72bbca7 81 uint table[value_size];
stevep 0:04a9f72bbca7 82
stevep 0:04a9f72bbca7 83
stevep 0:04a9f72bbca7 84
stevep 0:04a9f72bbca7 85 /*!
stevep 0:04a9f72bbca7 86 some methods used for debugging purposes
stevep 0:04a9f72bbca7 87 */
stevep 0:04a9f72bbca7 88
stevep 0:04a9f72bbca7 89
stevep 0:04a9f72bbca7 90 /*!
stevep 0:04a9f72bbca7 91 this method is only for debugging purposes or when we want to make
stevep 0:04a9f72bbca7 92 a table of a variable (constant) in ttmathbig.h
stevep 0:04a9f72bbca7 93
stevep 0:04a9f72bbca7 94 it prints the table in a nice form of several columns
stevep 0:04a9f72bbca7 95 */
stevep 0:04a9f72bbca7 96 template<class ostream_type>
stevep 0:04a9f72bbca7 97 void PrintTable(ostream_type & output) const
stevep 0:04a9f72bbca7 98 {
stevep 0:04a9f72bbca7 99 // how many columns there'll be
stevep 0:04a9f72bbca7 100 const int columns = 8;
stevep 0:04a9f72bbca7 101
stevep 0:04a9f72bbca7 102 int c = 1;
stevep 0:04a9f72bbca7 103 for(int i=value_size-1 ; i>=0 ; --i)
stevep 0:04a9f72bbca7 104 {
stevep 0:04a9f72bbca7 105 output << "0x" << std::setfill('0');
stevep 0:04a9f72bbca7 106
stevep 0:04a9f72bbca7 107 #ifdef TTMATH_PLATFORM32
stevep 0:04a9f72bbca7 108 output << std::setw(8);
stevep 0:04a9f72bbca7 109 #else
stevep 0:04a9f72bbca7 110 output << std::setw(16);
stevep 0:04a9f72bbca7 111 #endif
stevep 0:04a9f72bbca7 112
stevep 0:04a9f72bbca7 113 output << std::hex << table[i];
stevep 0:04a9f72bbca7 114
stevep 0:04a9f72bbca7 115 if( i>0 )
stevep 0:04a9f72bbca7 116 {
stevep 0:04a9f72bbca7 117 output << ", ";
stevep 0:04a9f72bbca7 118
stevep 0:04a9f72bbca7 119 if( ++c > columns )
stevep 0:04a9f72bbca7 120 {
stevep 0:04a9f72bbca7 121 output << std::endl;
stevep 0:04a9f72bbca7 122 c = 1;
stevep 0:04a9f72bbca7 123 }
stevep 0:04a9f72bbca7 124 }
stevep 0:04a9f72bbca7 125 }
stevep 0:04a9f72bbca7 126
stevep 0:04a9f72bbca7 127 output << std::dec << std::endl;
stevep 0:04a9f72bbca7 128 }
stevep 0:04a9f72bbca7 129
stevep 0:04a9f72bbca7 130
stevep 0:04a9f72bbca7 131 /*!
stevep 0:04a9f72bbca7 132 this method is used when macro TTMATH_DEBUG_LOG is defined
stevep 0:04a9f72bbca7 133 */
stevep 0:04a9f72bbca7 134 template<class char_type, class ostream_type>
stevep 0:04a9f72bbca7 135 static void PrintVectorLog(const char_type * msg, ostream_type & output, const uint * vector, uint vector_len)
stevep 0:04a9f72bbca7 136 {
stevep 0:04a9f72bbca7 137 output << msg << std::endl;
stevep 0:04a9f72bbca7 138
stevep 0:04a9f72bbca7 139 for(uint i=0 ; i<vector_len ; ++i)
stevep 0:04a9f72bbca7 140 output << " table[" << i << "]: " << vector[i] << std::endl;
stevep 0:04a9f72bbca7 141 }
stevep 0:04a9f72bbca7 142
stevep 0:04a9f72bbca7 143
stevep 0:04a9f72bbca7 144 /*!
stevep 0:04a9f72bbca7 145 this method is used when macro TTMATH_DEBUG_LOG is defined
stevep 0:04a9f72bbca7 146 */
stevep 0:04a9f72bbca7 147 template<class char_type, class ostream_type>
stevep 0:04a9f72bbca7 148 static void PrintVectorLog(const char_type * msg, uint carry, ostream_type & output, const uint * vector, uint vector_len)
stevep 0:04a9f72bbca7 149 {
stevep 0:04a9f72bbca7 150 PrintVectorLog(msg, output, vector, vector_len);
stevep 0:04a9f72bbca7 151 output << " carry: " << carry << std::endl;
stevep 0:04a9f72bbca7 152 }
stevep 0:04a9f72bbca7 153
stevep 0:04a9f72bbca7 154
stevep 0:04a9f72bbca7 155 /*!
stevep 0:04a9f72bbca7 156 this method is used when macro TTMATH_DEBUG_LOG is defined
stevep 0:04a9f72bbca7 157 */
stevep 0:04a9f72bbca7 158 template<class char_type, class ostream_type>
stevep 0:04a9f72bbca7 159 void PrintLog(const char_type * msg, ostream_type & output) const
stevep 0:04a9f72bbca7 160 {
stevep 0:04a9f72bbca7 161 PrintVectorLog(msg, output, table, value_size);
stevep 0:04a9f72bbca7 162 }
stevep 0:04a9f72bbca7 163
stevep 0:04a9f72bbca7 164
stevep 0:04a9f72bbca7 165 /*!
stevep 0:04a9f72bbca7 166 this method is used when macro TTMATH_DEBUG_LOG is defined
stevep 0:04a9f72bbca7 167 */
stevep 0:04a9f72bbca7 168 template<class char_type, class ostream_type>
stevep 0:04a9f72bbca7 169 void PrintLog(const char_type * msg, uint carry, ostream_type & output) const
stevep 0:04a9f72bbca7 170 {
stevep 0:04a9f72bbca7 171 PrintVectorLog(msg, output, table, value_size);
stevep 0:04a9f72bbca7 172 output << " carry: " << carry << std::endl;
stevep 0:04a9f72bbca7 173 }
stevep 0:04a9f72bbca7 174
stevep 0:04a9f72bbca7 175
stevep 0:04a9f72bbca7 176 /*!
stevep 0:04a9f72bbca7 177 this method returns the size of the table
stevep 0:04a9f72bbca7 178 */
stevep 0:04a9f72bbca7 179 uint Size() const
stevep 0:04a9f72bbca7 180 {
stevep 0:04a9f72bbca7 181 return value_size;
stevep 0:04a9f72bbca7 182 }
stevep 0:04a9f72bbca7 183
stevep 0:04a9f72bbca7 184
stevep 0:04a9f72bbca7 185 /*!
stevep 0:04a9f72bbca7 186 this method sets zero
stevep 0:04a9f72bbca7 187 */
stevep 0:04a9f72bbca7 188 void SetZero()
stevep 0:04a9f72bbca7 189 {
stevep 0:04a9f72bbca7 190 // in the future here can be 'memset'
stevep 0:04a9f72bbca7 191
stevep 0:04a9f72bbca7 192 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 193 table[i] = 0;
stevep 0:04a9f72bbca7 194
stevep 0:04a9f72bbca7 195 TTMATH_LOG("UInt::SetZero")
stevep 0:04a9f72bbca7 196 }
stevep 0:04a9f72bbca7 197
stevep 0:04a9f72bbca7 198
stevep 0:04a9f72bbca7 199 /*!
stevep 0:04a9f72bbca7 200 this method sets one
stevep 0:04a9f72bbca7 201 */
stevep 0:04a9f72bbca7 202 void SetOne()
stevep 0:04a9f72bbca7 203 {
stevep 0:04a9f72bbca7 204 SetZero();
stevep 0:04a9f72bbca7 205 table[0] = 1;
stevep 0:04a9f72bbca7 206
stevep 0:04a9f72bbca7 207 TTMATH_LOG("UInt::SetOne")
stevep 0:04a9f72bbca7 208 }
stevep 0:04a9f72bbca7 209
stevep 0:04a9f72bbca7 210
stevep 0:04a9f72bbca7 211 /*!
stevep 0:04a9f72bbca7 212 this method sets the max value which this class can hold
stevep 0:04a9f72bbca7 213 (all bits will be one)
stevep 0:04a9f72bbca7 214 */
stevep 0:04a9f72bbca7 215 void SetMax()
stevep 0:04a9f72bbca7 216 {
stevep 0:04a9f72bbca7 217 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 218 table[i] = TTMATH_UINT_MAX_VALUE;
stevep 0:04a9f72bbca7 219
stevep 0:04a9f72bbca7 220 TTMATH_LOG("UInt::SetMax")
stevep 0:04a9f72bbca7 221 }
stevep 0:04a9f72bbca7 222
stevep 0:04a9f72bbca7 223
stevep 0:04a9f72bbca7 224 /*!
stevep 0:04a9f72bbca7 225 this method sets the min value which this class can hold
stevep 0:04a9f72bbca7 226 (for an unsigned integer value the zero is the smallest value)
stevep 0:04a9f72bbca7 227 */
stevep 0:04a9f72bbca7 228 void SetMin()
stevep 0:04a9f72bbca7 229 {
stevep 0:04a9f72bbca7 230 SetZero();
stevep 0:04a9f72bbca7 231
stevep 0:04a9f72bbca7 232 TTMATH_LOG("UInt::SetMin")
stevep 0:04a9f72bbca7 233 }
stevep 0:04a9f72bbca7 234
stevep 0:04a9f72bbca7 235
stevep 0:04a9f72bbca7 236 /*!
stevep 0:04a9f72bbca7 237 this method swappes this for an argument
stevep 0:04a9f72bbca7 238 */
stevep 0:04a9f72bbca7 239 void Swap(UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 240 {
stevep 0:04a9f72bbca7 241 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 242 {
stevep 0:04a9f72bbca7 243 uint temp = table[i];
stevep 0:04a9f72bbca7 244 table[i] = ss2.table[i];
stevep 0:04a9f72bbca7 245 ss2.table[i] = temp;
stevep 0:04a9f72bbca7 246 }
stevep 0:04a9f72bbca7 247 }
stevep 0:04a9f72bbca7 248
stevep 0:04a9f72bbca7 249
stevep 0:04a9f72bbca7 250 #ifdef TTMATH_PLATFORM32
stevep 0:04a9f72bbca7 251
stevep 0:04a9f72bbca7 252 /*!
stevep 0:04a9f72bbca7 253 this method copies the value stored in an another table
stevep 0:04a9f72bbca7 254 (warning: first values in temp_table are the highest words -- it's different
stevep 0:04a9f72bbca7 255 from our table)
stevep 0:04a9f72bbca7 256
stevep 0:04a9f72bbca7 257 we copy as many words as it is possible
stevep 0:04a9f72bbca7 258
stevep 0:04a9f72bbca7 259 if temp_table_len is bigger than value_size we'll try to round
stevep 0:04a9f72bbca7 260 the lowest word from table depending on the last not used bit in temp_table
stevep 0:04a9f72bbca7 261 (this rounding isn't a perfect rounding -- look at the description below)
stevep 0:04a9f72bbca7 262
stevep 0:04a9f72bbca7 263 and if temp_table_len is smaller than value_size we'll clear the rest words
stevep 0:04a9f72bbca7 264 in the table
stevep 0:04a9f72bbca7 265 */
stevep 0:04a9f72bbca7 266 void SetFromTable(const uint * temp_table, uint temp_table_len)
stevep 0:04a9f72bbca7 267 {
stevep 0:04a9f72bbca7 268 uint temp_table_index = 0;
stevep 0:04a9f72bbca7 269 sint i; // 'i' with a sign
stevep 0:04a9f72bbca7 270
stevep 0:04a9f72bbca7 271 for(i=value_size-1 ; i>=0 && temp_table_index<temp_table_len; --i, ++temp_table_index)
stevep 0:04a9f72bbca7 272 table[i] = temp_table[ temp_table_index ];
stevep 0:04a9f72bbca7 273
stevep 0:04a9f72bbca7 274
stevep 0:04a9f72bbca7 275 // rounding mantissa
stevep 0:04a9f72bbca7 276 if( temp_table_index < temp_table_len )
stevep 0:04a9f72bbca7 277 {
stevep 0:04a9f72bbca7 278 if( (temp_table[temp_table_index] & TTMATH_UINT_HIGHEST_BIT) != 0 )
stevep 0:04a9f72bbca7 279 {
stevep 0:04a9f72bbca7 280 /*
stevep 0:04a9f72bbca7 281 very simply rounding
stevep 0:04a9f72bbca7 282 if the bit from not used last word from temp_table is set to one
stevep 0:04a9f72bbca7 283 we're rouding the lowest word in the table
stevep 0:04a9f72bbca7 284
stevep 0:04a9f72bbca7 285 in fact there should be a normal addition but
stevep 0:04a9f72bbca7 286 we don't use Add() or AddTwoInts() because these methods
stevep 0:04a9f72bbca7 287 can set a carry and then there'll be a small problem
stevep 0:04a9f72bbca7 288 for optimization
stevep 0:04a9f72bbca7 289 */
stevep 0:04a9f72bbca7 290 if( table[0] != TTMATH_UINT_MAX_VALUE )
stevep 0:04a9f72bbca7 291 ++table[0];
stevep 0:04a9f72bbca7 292 }
stevep 0:04a9f72bbca7 293 }
stevep 0:04a9f72bbca7 294
stevep 0:04a9f72bbca7 295 // cleaning the rest of the mantissa
stevep 0:04a9f72bbca7 296 for( ; i>=0 ; --i)
stevep 0:04a9f72bbca7 297 table[i] = 0;
stevep 0:04a9f72bbca7 298
stevep 0:04a9f72bbca7 299
stevep 0:04a9f72bbca7 300 TTMATH_LOG("UInt::SetFromTable")
stevep 0:04a9f72bbca7 301 }
stevep 0:04a9f72bbca7 302
stevep 0:04a9f72bbca7 303 #endif
stevep 0:04a9f72bbca7 304
stevep 0:04a9f72bbca7 305
stevep 0:04a9f72bbca7 306 #ifdef TTMATH_PLATFORM64
stevep 0:04a9f72bbca7 307 /*!
stevep 0:04a9f72bbca7 308 this method copies the value stored in an another table
stevep 0:04a9f72bbca7 309 (warning: first values in temp_table are the highest words -- it's different
stevep 0:04a9f72bbca7 310 from our table)
stevep 0:04a9f72bbca7 311
stevep 0:04a9f72bbca7 312 ***this method is created only on a 64bit platform***
stevep 0:04a9f72bbca7 313
stevep 0:04a9f72bbca7 314 we copy as many words as it is possible
stevep 0:04a9f72bbca7 315
stevep 0:04a9f72bbca7 316 if temp_table_len is bigger than value_size we'll try to round
stevep 0:04a9f72bbca7 317 the lowest word from table depending on the last not used bit in temp_table
stevep 0:04a9f72bbca7 318 (this rounding isn't a perfect rounding -- look at the description below)
stevep 0:04a9f72bbca7 319
stevep 0:04a9f72bbca7 320 and if temp_table_len is smaller than value_size we'll clear the rest words
stevep 0:04a9f72bbca7 321 in the table
stevep 0:04a9f72bbca7 322
stevep 0:04a9f72bbca7 323 warning: we're using 'temp_table' as a pointer at 32bit words
stevep 0:04a9f72bbca7 324 */
stevep 0:04a9f72bbca7 325 void SetFromTable(const unsigned int * temp_table, uint temp_table_len)
stevep 0:04a9f72bbca7 326 {
stevep 0:04a9f72bbca7 327 uint temp_table_index = 0;
stevep 0:04a9f72bbca7 328 sint i; // 'i' with a sign
stevep 0:04a9f72bbca7 329
stevep 0:04a9f72bbca7 330 for(i=value_size-1 ; i>=0 && temp_table_index<temp_table_len; --i, ++temp_table_index)
stevep 0:04a9f72bbca7 331 {
stevep 0:04a9f72bbca7 332 table[i] = uint(temp_table[ temp_table_index ]) << 32;
stevep 0:04a9f72bbca7 333
stevep 0:04a9f72bbca7 334 ++temp_table_index;
stevep 0:04a9f72bbca7 335
stevep 0:04a9f72bbca7 336 if( temp_table_index<temp_table_len )
stevep 0:04a9f72bbca7 337 table[i] |= temp_table[ temp_table_index ];
stevep 0:04a9f72bbca7 338 }
stevep 0:04a9f72bbca7 339
stevep 0:04a9f72bbca7 340
stevep 0:04a9f72bbca7 341 // rounding mantissa
stevep 0:04a9f72bbca7 342 if( temp_table_index < temp_table_len )
stevep 0:04a9f72bbca7 343 {
stevep 0:04a9f72bbca7 344 if( (temp_table[temp_table_index] & TTMATH_UINT_HIGHEST_BIT) != 0 )
stevep 0:04a9f72bbca7 345 {
stevep 0:04a9f72bbca7 346 /*
stevep 0:04a9f72bbca7 347 very simply rounding
stevep 0:04a9f72bbca7 348 if the bit from not used last word from temp_table is set to one
stevep 0:04a9f72bbca7 349 we're rouding the lowest word in the table
stevep 0:04a9f72bbca7 350
stevep 0:04a9f72bbca7 351 in fact there should be a normal addition but
stevep 0:04a9f72bbca7 352 we don't use Add() or AddTwoInts() because these methods
stevep 0:04a9f72bbca7 353 can set a carry and then there'll be a small problem
stevep 0:04a9f72bbca7 354 for optimization
stevep 0:04a9f72bbca7 355 */
stevep 0:04a9f72bbca7 356 if( table[0] != TTMATH_UINT_MAX_VALUE )
stevep 0:04a9f72bbca7 357 ++table[0];
stevep 0:04a9f72bbca7 358 }
stevep 0:04a9f72bbca7 359 }
stevep 0:04a9f72bbca7 360
stevep 0:04a9f72bbca7 361 // cleaning the rest of the mantissa
stevep 0:04a9f72bbca7 362 for( ; i >= 0 ; --i)
stevep 0:04a9f72bbca7 363 table[i] = 0;
stevep 0:04a9f72bbca7 364
stevep 0:04a9f72bbca7 365 TTMATH_LOG("UInt::SetFromTable")
stevep 0:04a9f72bbca7 366 }
stevep 0:04a9f72bbca7 367
stevep 0:04a9f72bbca7 368 #endif
stevep 0:04a9f72bbca7 369
stevep 0:04a9f72bbca7 370
stevep 0:04a9f72bbca7 371
stevep 0:04a9f72bbca7 372
stevep 0:04a9f72bbca7 373
stevep 0:04a9f72bbca7 374 /*!
stevep 0:04a9f72bbca7 375 *
stevep 0:04a9f72bbca7 376 * basic mathematic functions
stevep 0:04a9f72bbca7 377 *
stevep 0:04a9f72bbca7 378 */
stevep 0:04a9f72bbca7 379
stevep 0:04a9f72bbca7 380
stevep 0:04a9f72bbca7 381
stevep 0:04a9f72bbca7 382
stevep 0:04a9f72bbca7 383 /*!
stevep 0:04a9f72bbca7 384 this method adds one to the existing value
stevep 0:04a9f72bbca7 385 */
stevep 0:04a9f72bbca7 386 uint AddOne()
stevep 0:04a9f72bbca7 387 {
stevep 0:04a9f72bbca7 388 return AddInt(1);
stevep 0:04a9f72bbca7 389 }
stevep 0:04a9f72bbca7 390
stevep 0:04a9f72bbca7 391
stevep 0:04a9f72bbca7 392 /*!
stevep 0:04a9f72bbca7 393 this method subtracts one from the existing value
stevep 0:04a9f72bbca7 394 */
stevep 0:04a9f72bbca7 395 uint SubOne()
stevep 0:04a9f72bbca7 396 {
stevep 0:04a9f72bbca7 397 return SubInt(1);
stevep 0:04a9f72bbca7 398 }
stevep 0:04a9f72bbca7 399
stevep 0:04a9f72bbca7 400
stevep 0:04a9f72bbca7 401 private:
stevep 0:04a9f72bbca7 402
stevep 0:04a9f72bbca7 403
stevep 0:04a9f72bbca7 404 /*!
stevep 0:04a9f72bbca7 405 an auxiliary method for moving bits into the left hand side
stevep 0:04a9f72bbca7 406
stevep 0:04a9f72bbca7 407 this method moves only words
stevep 0:04a9f72bbca7 408 */
stevep 0:04a9f72bbca7 409 void RclMoveAllWords(uint & rest_bits, uint & last_c, uint bits, uint c)
stevep 0:04a9f72bbca7 410 {
stevep 0:04a9f72bbca7 411 rest_bits = bits % TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 412 uint all_words = bits / TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 413 uint mask = ( c ) ? TTMATH_UINT_MAX_VALUE : 0;
stevep 0:04a9f72bbca7 414
stevep 0:04a9f72bbca7 415
stevep 0:04a9f72bbca7 416 if( all_words >= value_size )
stevep 0:04a9f72bbca7 417 {
stevep 0:04a9f72bbca7 418 if( all_words == value_size && rest_bits == 0 )
stevep 0:04a9f72bbca7 419 last_c = table[0] & 1;
stevep 0:04a9f72bbca7 420 // else: last_c is default set to 0
stevep 0:04a9f72bbca7 421
stevep 0:04a9f72bbca7 422 // clearing
stevep 0:04a9f72bbca7 423 for(uint i = 0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 424 table[i] = mask;
stevep 0:04a9f72bbca7 425
stevep 0:04a9f72bbca7 426 rest_bits = 0;
stevep 0:04a9f72bbca7 427 }
stevep 0:04a9f72bbca7 428 else
stevep 0:04a9f72bbca7 429 if( all_words > 0 )
stevep 0:04a9f72bbca7 430 {
stevep 0:04a9f72bbca7 431 // 0 < all_words < value_size
stevep 0:04a9f72bbca7 432
stevep 0:04a9f72bbca7 433 sint first, second;
stevep 0:04a9f72bbca7 434 last_c = table[value_size - all_words] & 1; // all_words is greater than 0
stevep 0:04a9f72bbca7 435
stevep 0:04a9f72bbca7 436 // copying the first part of the value
stevep 0:04a9f72bbca7 437 for(first = value_size-1, second=first-all_words ; second>=0 ; --first, --second)
stevep 0:04a9f72bbca7 438 table[first] = table[second];
stevep 0:04a9f72bbca7 439
stevep 0:04a9f72bbca7 440 // setting the rest to 'c'
stevep 0:04a9f72bbca7 441 for( ; first>=0 ; --first )
stevep 0:04a9f72bbca7 442 table[first] = mask;
stevep 0:04a9f72bbca7 443 }
stevep 0:04a9f72bbca7 444
stevep 0:04a9f72bbca7 445 TTMATH_LOG("UInt::RclMoveAllWords")
stevep 0:04a9f72bbca7 446 }
stevep 0:04a9f72bbca7 447
stevep 0:04a9f72bbca7 448 public:
stevep 0:04a9f72bbca7 449
stevep 0:04a9f72bbca7 450 /*!
stevep 0:04a9f72bbca7 451 moving all bits into the left side 'bits' times
stevep 0:04a9f72bbca7 452 return value <- this <- C
stevep 0:04a9f72bbca7 453
stevep 0:04a9f72bbca7 454 bits is from a range of <0, man * TTMATH_BITS_PER_UINT>
stevep 0:04a9f72bbca7 455 or it can be even bigger then all bits will be set to 'c'
stevep 0:04a9f72bbca7 456
stevep 0:04a9f72bbca7 457 the value c will be set into the lowest bits
stevep 0:04a9f72bbca7 458 and the method returns state of the last moved bit
stevep 0:04a9f72bbca7 459 */
stevep 0:04a9f72bbca7 460 uint Rcl(uint bits, uint c=0)
stevep 0:04a9f72bbca7 461 {
stevep 0:04a9f72bbca7 462 uint last_c = 0;
stevep 0:04a9f72bbca7 463 uint rest_bits = bits;
stevep 0:04a9f72bbca7 464
stevep 0:04a9f72bbca7 465 if( bits == 0 )
stevep 0:04a9f72bbca7 466 return 0;
stevep 0:04a9f72bbca7 467
stevep 0:04a9f72bbca7 468 if( bits >= TTMATH_BITS_PER_UINT )
stevep 0:04a9f72bbca7 469 RclMoveAllWords(rest_bits, last_c, bits, c);
stevep 0:04a9f72bbca7 470
stevep 0:04a9f72bbca7 471 if( rest_bits == 0 )
stevep 0:04a9f72bbca7 472 {
stevep 0:04a9f72bbca7 473 TTMATH_LOG("UInt::Rcl")
stevep 0:04a9f72bbca7 474 return last_c;
stevep 0:04a9f72bbca7 475 }
stevep 0:04a9f72bbca7 476
stevep 0:04a9f72bbca7 477 // rest_bits is from 1 to TTMATH_BITS_PER_UINT-1 now
stevep 0:04a9f72bbca7 478 if( rest_bits == 1 )
stevep 0:04a9f72bbca7 479 {
stevep 0:04a9f72bbca7 480 last_c = Rcl2_one(c);
stevep 0:04a9f72bbca7 481 }
stevep 0:04a9f72bbca7 482 else if( rest_bits == 2 )
stevep 0:04a9f72bbca7 483 {
stevep 0:04a9f72bbca7 484 // performance tests showed that for rest_bits==2 it's better to use Rcl2_one twice instead of Rcl2(2,c)
stevep 0:04a9f72bbca7 485 Rcl2_one(c);
stevep 0:04a9f72bbca7 486 last_c = Rcl2_one(c);
stevep 0:04a9f72bbca7 487 }
stevep 0:04a9f72bbca7 488 else
stevep 0:04a9f72bbca7 489 {
stevep 0:04a9f72bbca7 490 last_c = Rcl2(rest_bits, c);
stevep 0:04a9f72bbca7 491 }
stevep 0:04a9f72bbca7 492
stevep 0:04a9f72bbca7 493 TTMATH_LOGC("UInt::Rcl", last_c)
stevep 0:04a9f72bbca7 494
stevep 0:04a9f72bbca7 495 return last_c;
stevep 0:04a9f72bbca7 496 }
stevep 0:04a9f72bbca7 497
stevep 0:04a9f72bbca7 498 private:
stevep 0:04a9f72bbca7 499
stevep 0:04a9f72bbca7 500 /*!
stevep 0:04a9f72bbca7 501 an auxiliary method for moving bits into the right hand side
stevep 0:04a9f72bbca7 502
stevep 0:04a9f72bbca7 503 this method moves only words
stevep 0:04a9f72bbca7 504 */
stevep 0:04a9f72bbca7 505 void RcrMoveAllWords(uint & rest_bits, uint & last_c, uint bits, uint c)
stevep 0:04a9f72bbca7 506 {
stevep 0:04a9f72bbca7 507 rest_bits = bits % TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 508 uint all_words = bits / TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 509 uint mask = ( c ) ? TTMATH_UINT_MAX_VALUE : 0;
stevep 0:04a9f72bbca7 510
stevep 0:04a9f72bbca7 511
stevep 0:04a9f72bbca7 512 if( all_words >= value_size )
stevep 0:04a9f72bbca7 513 {
stevep 0:04a9f72bbca7 514 if( all_words == value_size && rest_bits == 0 )
stevep 0:04a9f72bbca7 515 last_c = (table[value_size-1] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0;
stevep 0:04a9f72bbca7 516 // else: last_c is default set to 0
stevep 0:04a9f72bbca7 517
stevep 0:04a9f72bbca7 518 // clearing
stevep 0:04a9f72bbca7 519 for(uint i = 0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 520 table[i] = mask;
stevep 0:04a9f72bbca7 521
stevep 0:04a9f72bbca7 522 rest_bits = 0;
stevep 0:04a9f72bbca7 523 }
stevep 0:04a9f72bbca7 524 else if( all_words > 0 )
stevep 0:04a9f72bbca7 525 {
stevep 0:04a9f72bbca7 526 // 0 < all_words < value_size
stevep 0:04a9f72bbca7 527
stevep 0:04a9f72bbca7 528 uint first, second;
stevep 0:04a9f72bbca7 529 last_c = (table[all_words - 1] & TTMATH_UINT_HIGHEST_BIT) ? 1 : 0; // all_words is > 0
stevep 0:04a9f72bbca7 530
stevep 0:04a9f72bbca7 531 // copying the first part of the value
stevep 0:04a9f72bbca7 532 for(first=0, second=all_words ; second<value_size ; ++first, ++second)
stevep 0:04a9f72bbca7 533 table[first] = table[second];
stevep 0:04a9f72bbca7 534
stevep 0:04a9f72bbca7 535 // setting the rest to 'c'
stevep 0:04a9f72bbca7 536 for( ; first<value_size ; ++first )
stevep 0:04a9f72bbca7 537 table[first] = mask;
stevep 0:04a9f72bbca7 538 }
stevep 0:04a9f72bbca7 539
stevep 0:04a9f72bbca7 540 TTMATH_LOG("UInt::RcrMoveAllWords")
stevep 0:04a9f72bbca7 541 }
stevep 0:04a9f72bbca7 542
stevep 0:04a9f72bbca7 543 public:
stevep 0:04a9f72bbca7 544
stevep 0:04a9f72bbca7 545 /*!
stevep 0:04a9f72bbca7 546 moving all bits into the right side 'bits' times
stevep 0:04a9f72bbca7 547 c -> this -> return value
stevep 0:04a9f72bbca7 548
stevep 0:04a9f72bbca7 549 bits is from a range of <0, man * TTMATH_BITS_PER_UINT>
stevep 0:04a9f72bbca7 550 or it can be even bigger then all bits will be set to 'c'
stevep 0:04a9f72bbca7 551
stevep 0:04a9f72bbca7 552 the value c will be set into the highest bits
stevep 0:04a9f72bbca7 553 and the method returns state of the last moved bit
stevep 0:04a9f72bbca7 554 */
stevep 0:04a9f72bbca7 555 uint Rcr(uint bits, uint c=0)
stevep 0:04a9f72bbca7 556 {
stevep 0:04a9f72bbca7 557 uint last_c = 0;
stevep 0:04a9f72bbca7 558 uint rest_bits = bits;
stevep 0:04a9f72bbca7 559
stevep 0:04a9f72bbca7 560 if( bits == 0 )
stevep 0:04a9f72bbca7 561 return 0;
stevep 0:04a9f72bbca7 562
stevep 0:04a9f72bbca7 563 if( bits >= TTMATH_BITS_PER_UINT )
stevep 0:04a9f72bbca7 564 RcrMoveAllWords(rest_bits, last_c, bits, c);
stevep 0:04a9f72bbca7 565
stevep 0:04a9f72bbca7 566 if( rest_bits == 0 )
stevep 0:04a9f72bbca7 567 {
stevep 0:04a9f72bbca7 568 TTMATH_LOG("UInt::Rcr")
stevep 0:04a9f72bbca7 569 return last_c;
stevep 0:04a9f72bbca7 570 }
stevep 0:04a9f72bbca7 571
stevep 0:04a9f72bbca7 572 // rest_bits is from 1 to TTMATH_BITS_PER_UINT-1 now
stevep 0:04a9f72bbca7 573 if( rest_bits == 1 )
stevep 0:04a9f72bbca7 574 {
stevep 0:04a9f72bbca7 575 last_c = Rcr2_one(c);
stevep 0:04a9f72bbca7 576 }
stevep 0:04a9f72bbca7 577 else if( rest_bits == 2 )
stevep 0:04a9f72bbca7 578 {
stevep 0:04a9f72bbca7 579 // performance tests showed that for rest_bits==2 it's better to use Rcr2_one twice instead of Rcr2(2,c)
stevep 0:04a9f72bbca7 580 Rcr2_one(c);
stevep 0:04a9f72bbca7 581 last_c = Rcr2_one(c);
stevep 0:04a9f72bbca7 582 }
stevep 0:04a9f72bbca7 583 else
stevep 0:04a9f72bbca7 584 {
stevep 0:04a9f72bbca7 585 last_c = Rcr2(rest_bits, c);
stevep 0:04a9f72bbca7 586 }
stevep 0:04a9f72bbca7 587
stevep 0:04a9f72bbca7 588 TTMATH_LOGC("UInt::Rcr", last_c)
stevep 0:04a9f72bbca7 589
stevep 0:04a9f72bbca7 590 return last_c;
stevep 0:04a9f72bbca7 591 }
stevep 0:04a9f72bbca7 592
stevep 0:04a9f72bbca7 593
stevep 0:04a9f72bbca7 594 /*!
stevep 0:04a9f72bbca7 595 this method moves all bits into the left side
stevep 0:04a9f72bbca7 596 (it returns value how many bits have been moved)
stevep 0:04a9f72bbca7 597 */
stevep 0:04a9f72bbca7 598 uint CompensationToLeft()
stevep 0:04a9f72bbca7 599 {
stevep 0:04a9f72bbca7 600 uint moving = 0;
stevep 0:04a9f72bbca7 601
stevep 0:04a9f72bbca7 602 // a - index a last word which is different from zero
stevep 0:04a9f72bbca7 603 sint a;
stevep 0:04a9f72bbca7 604 for(a=value_size-1 ; a>=0 && table[a]==0 ; --a);
stevep 0:04a9f72bbca7 605
stevep 0:04a9f72bbca7 606 if( a < 0 )
stevep 0:04a9f72bbca7 607 return moving; // all words in table have zero
stevep 0:04a9f72bbca7 608
stevep 0:04a9f72bbca7 609 if( a != value_size-1 )
stevep 0:04a9f72bbca7 610 {
stevep 0:04a9f72bbca7 611 moving += ( value_size-1 - a ) * TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 612
stevep 0:04a9f72bbca7 613 // moving all words
stevep 0:04a9f72bbca7 614 sint i;
stevep 0:04a9f72bbca7 615 for(i=value_size-1 ; a>=0 ; --i, --a)
stevep 0:04a9f72bbca7 616 table[i] = table[a];
stevep 0:04a9f72bbca7 617
stevep 0:04a9f72bbca7 618 // setting the rest word to zero
stevep 0:04a9f72bbca7 619 for(; i>=0 ; --i)
stevep 0:04a9f72bbca7 620 table[i] = 0;
stevep 0:04a9f72bbca7 621 }
stevep 0:04a9f72bbca7 622
stevep 0:04a9f72bbca7 623 uint moving2 = FindLeadingBitInWord( table[value_size-1] );
stevep 0:04a9f72bbca7 624 // moving2 is different from -1 because the value table[value_size-1]
stevep 0:04a9f72bbca7 625 // is not zero
stevep 0:04a9f72bbca7 626
stevep 0:04a9f72bbca7 627 moving2 = TTMATH_BITS_PER_UINT - moving2 - 1;
stevep 0:04a9f72bbca7 628 Rcl(moving2);
stevep 0:04a9f72bbca7 629
stevep 0:04a9f72bbca7 630 TTMATH_LOG("UInt::CompensationToLeft")
stevep 0:04a9f72bbca7 631
stevep 0:04a9f72bbca7 632 return moving + moving2;
stevep 0:04a9f72bbca7 633 }
stevep 0:04a9f72bbca7 634
stevep 0:04a9f72bbca7 635
stevep 0:04a9f72bbca7 636 /*!
stevep 0:04a9f72bbca7 637 this method looks for the highest set bit
stevep 0:04a9f72bbca7 638
stevep 0:04a9f72bbca7 639 result:
stevep 0:04a9f72bbca7 640 if 'this' is not zero:
stevep 0:04a9f72bbca7 641 return value - true
stevep 0:04a9f72bbca7 642 'table_id' - the index of a word <0..value_size-1>
stevep 0:04a9f72bbca7 643 'index' - the index of this set bit in the word <0..TTMATH_BITS_PER_UINT)
stevep 0:04a9f72bbca7 644
stevep 0:04a9f72bbca7 645 if 'this' is zero:
stevep 0:04a9f72bbca7 646 return value - false
stevep 0:04a9f72bbca7 647 both 'table_id' and 'index' are zero
stevep 0:04a9f72bbca7 648 */
stevep 0:04a9f72bbca7 649 bool FindLeadingBit(uint & table_id, uint & index) const
stevep 0:04a9f72bbca7 650 {
stevep 0:04a9f72bbca7 651 for(table_id=value_size-1 ; table_id!=0 && table[table_id]==0 ; --table_id);
stevep 0:04a9f72bbca7 652
stevep 0:04a9f72bbca7 653 if( table_id==0 && table[table_id]==0 )
stevep 0:04a9f72bbca7 654 {
stevep 0:04a9f72bbca7 655 // is zero
stevep 0:04a9f72bbca7 656 index = 0;
stevep 0:04a9f72bbca7 657
stevep 0:04a9f72bbca7 658 return false;
stevep 0:04a9f72bbca7 659 }
stevep 0:04a9f72bbca7 660
stevep 0:04a9f72bbca7 661 // table[table_id] is different from 0
stevep 0:04a9f72bbca7 662 index = FindLeadingBitInWord( table[table_id] );
stevep 0:04a9f72bbca7 663
stevep 0:04a9f72bbca7 664 return true;
stevep 0:04a9f72bbca7 665 }
stevep 0:04a9f72bbca7 666
stevep 0:04a9f72bbca7 667
stevep 0:04a9f72bbca7 668 /*!
stevep 0:04a9f72bbca7 669 this method looks for the smallest set bit
stevep 0:04a9f72bbca7 670
stevep 0:04a9f72bbca7 671 result:
stevep 0:04a9f72bbca7 672 if 'this' is not zero:
stevep 0:04a9f72bbca7 673 return value - true
stevep 0:04a9f72bbca7 674 'table_id' - the index of a word <0..value_size-1>
stevep 0:04a9f72bbca7 675 'index' - the index of this set bit in the word <0..TTMATH_BITS_PER_UINT)
stevep 0:04a9f72bbca7 676
stevep 0:04a9f72bbca7 677 if 'this' is zero:
stevep 0:04a9f72bbca7 678 return value - false
stevep 0:04a9f72bbca7 679 both 'table_id' and 'index' are zero
stevep 0:04a9f72bbca7 680 */
stevep 0:04a9f72bbca7 681 bool FindLowestBit(uint & table_id, uint & index) const
stevep 0:04a9f72bbca7 682 {
stevep 0:04a9f72bbca7 683 for(table_id=0 ; table_id<value_size && table[table_id]==0 ; ++table_id);
stevep 0:04a9f72bbca7 684
stevep 0:04a9f72bbca7 685 if( table_id >= value_size )
stevep 0:04a9f72bbca7 686 {
stevep 0:04a9f72bbca7 687 // is zero
stevep 0:04a9f72bbca7 688 index = 0;
stevep 0:04a9f72bbca7 689 table_id = 0;
stevep 0:04a9f72bbca7 690
stevep 0:04a9f72bbca7 691 return false;
stevep 0:04a9f72bbca7 692 }
stevep 0:04a9f72bbca7 693
stevep 0:04a9f72bbca7 694 // table[table_id] is different from 0
stevep 0:04a9f72bbca7 695 index = FindLowestBitInWord( table[table_id] );
stevep 0:04a9f72bbca7 696
stevep 0:04a9f72bbca7 697 return true;
stevep 0:04a9f72bbca7 698 }
stevep 0:04a9f72bbca7 699
stevep 0:04a9f72bbca7 700
stevep 0:04a9f72bbca7 701 /*!
stevep 0:04a9f72bbca7 702 getting the 'bit_index' bit
stevep 0:04a9f72bbca7 703
stevep 0:04a9f72bbca7 704 bit_index bigger or equal zero
stevep 0:04a9f72bbca7 705 */
stevep 0:04a9f72bbca7 706 uint GetBit(uint bit_index) const
stevep 0:04a9f72bbca7 707 {
stevep 0:04a9f72bbca7 708 TTMATH_ASSERT( bit_index < value_size * TTMATH_BITS_PER_UINT )
stevep 0:04a9f72bbca7 709
stevep 0:04a9f72bbca7 710 uint index = bit_index / TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 711 uint bit = bit_index % TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 712
stevep 0:04a9f72bbca7 713 uint temp = table[index];
stevep 0:04a9f72bbca7 714 uint res = SetBitInWord(temp, bit);
stevep 0:04a9f72bbca7 715
stevep 0:04a9f72bbca7 716 return res;
stevep 0:04a9f72bbca7 717 }
stevep 0:04a9f72bbca7 718
stevep 0:04a9f72bbca7 719
stevep 0:04a9f72bbca7 720 /*!
stevep 0:04a9f72bbca7 721 setting the 'bit_index' bit
stevep 0:04a9f72bbca7 722 and returning the last state of the bit
stevep 0:04a9f72bbca7 723
stevep 0:04a9f72bbca7 724 bit_index bigger or equal zero
stevep 0:04a9f72bbca7 725 */
stevep 0:04a9f72bbca7 726 uint SetBit(uint bit_index)
stevep 0:04a9f72bbca7 727 {
stevep 0:04a9f72bbca7 728 TTMATH_ASSERT( bit_index < value_size * TTMATH_BITS_PER_UINT )
stevep 0:04a9f72bbca7 729
stevep 0:04a9f72bbca7 730 uint index = bit_index / TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 731 uint bit = bit_index % TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 732 uint res = SetBitInWord(table[index], bit);
stevep 0:04a9f72bbca7 733
stevep 0:04a9f72bbca7 734 TTMATH_LOG("UInt::SetBit")
stevep 0:04a9f72bbca7 735
stevep 0:04a9f72bbca7 736 return res;
stevep 0:04a9f72bbca7 737 }
stevep 0:04a9f72bbca7 738
stevep 0:04a9f72bbca7 739
stevep 0:04a9f72bbca7 740 /*!
stevep 0:04a9f72bbca7 741 this method performs a bitwise operation AND
stevep 0:04a9f72bbca7 742 */
stevep 0:04a9f72bbca7 743 void BitAnd(const UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 744 {
stevep 0:04a9f72bbca7 745 for(uint x=0 ; x<value_size ; ++x)
stevep 0:04a9f72bbca7 746 table[x] &= ss2.table[x];
stevep 0:04a9f72bbca7 747
stevep 0:04a9f72bbca7 748 TTMATH_LOG("UInt::BitAnd")
stevep 0:04a9f72bbca7 749 }
stevep 0:04a9f72bbca7 750
stevep 0:04a9f72bbca7 751
stevep 0:04a9f72bbca7 752 /*!
stevep 0:04a9f72bbca7 753 this method performs a bitwise operation OR
stevep 0:04a9f72bbca7 754 */
stevep 0:04a9f72bbca7 755 void BitOr(const UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 756 {
stevep 0:04a9f72bbca7 757 for(uint x=0 ; x<value_size ; ++x)
stevep 0:04a9f72bbca7 758 table[x] |= ss2.table[x];
stevep 0:04a9f72bbca7 759
stevep 0:04a9f72bbca7 760 TTMATH_LOG("UInt::BitOr")
stevep 0:04a9f72bbca7 761 }
stevep 0:04a9f72bbca7 762
stevep 0:04a9f72bbca7 763
stevep 0:04a9f72bbca7 764 /*!
stevep 0:04a9f72bbca7 765 this method performs a bitwise operation XOR
stevep 0:04a9f72bbca7 766 */
stevep 0:04a9f72bbca7 767 void BitXor(const UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 768 {
stevep 0:04a9f72bbca7 769 for(uint x=0 ; x<value_size ; ++x)
stevep 0:04a9f72bbca7 770 table[x] ^= ss2.table[x];
stevep 0:04a9f72bbca7 771
stevep 0:04a9f72bbca7 772 TTMATH_LOG("UInt::BitXor")
stevep 0:04a9f72bbca7 773 }
stevep 0:04a9f72bbca7 774
stevep 0:04a9f72bbca7 775
stevep 0:04a9f72bbca7 776 /*!
stevep 0:04a9f72bbca7 777 this method performs a bitwise operation NOT
stevep 0:04a9f72bbca7 778 */
stevep 0:04a9f72bbca7 779 void BitNot()
stevep 0:04a9f72bbca7 780 {
stevep 0:04a9f72bbca7 781 for(uint x=0 ; x<value_size ; ++x)
stevep 0:04a9f72bbca7 782 table[x] = ~table[x];
stevep 0:04a9f72bbca7 783
stevep 0:04a9f72bbca7 784 TTMATH_LOG("UInt::BitNot")
stevep 0:04a9f72bbca7 785 }
stevep 0:04a9f72bbca7 786
stevep 0:04a9f72bbca7 787
stevep 0:04a9f72bbca7 788 /*!
stevep 0:04a9f72bbca7 789 this method performs a bitwise operation NOT but only
stevep 0:04a9f72bbca7 790 on the range of <0, leading_bit>
stevep 0:04a9f72bbca7 791
stevep 0:04a9f72bbca7 792 for example:
stevep 0:04a9f72bbca7 793 BitNot2(8) = BitNot2( 1000(bin) ) = 111(bin) = 7
stevep 0:04a9f72bbca7 794 */
stevep 0:04a9f72bbca7 795 void BitNot2()
stevep 0:04a9f72bbca7 796 {
stevep 0:04a9f72bbca7 797 uint table_id, index;
stevep 0:04a9f72bbca7 798
stevep 0:04a9f72bbca7 799 if( FindLeadingBit(table_id, index) )
stevep 0:04a9f72bbca7 800 {
stevep 0:04a9f72bbca7 801 for(uint x=0 ; x<table_id ; ++x)
stevep 0:04a9f72bbca7 802 table[x] = ~table[x];
stevep 0:04a9f72bbca7 803
stevep 0:04a9f72bbca7 804 uint mask = TTMATH_UINT_MAX_VALUE;
stevep 0:04a9f72bbca7 805 uint shift = TTMATH_BITS_PER_UINT - index - 1;
stevep 0:04a9f72bbca7 806
stevep 0:04a9f72bbca7 807 if(shift)
stevep 0:04a9f72bbca7 808 mask >>= shift;
stevep 0:04a9f72bbca7 809
stevep 0:04a9f72bbca7 810 table[table_id] ^= mask;
stevep 0:04a9f72bbca7 811 }
stevep 0:04a9f72bbca7 812 else
stevep 0:04a9f72bbca7 813 table[0] = 1;
stevep 0:04a9f72bbca7 814
stevep 0:04a9f72bbca7 815
stevep 0:04a9f72bbca7 816 TTMATH_LOG("UInt::BitNot2")
stevep 0:04a9f72bbca7 817 }
stevep 0:04a9f72bbca7 818
stevep 0:04a9f72bbca7 819
stevep 0:04a9f72bbca7 820
stevep 0:04a9f72bbca7 821 /*!
stevep 0:04a9f72bbca7 822 *
stevep 0:04a9f72bbca7 823 * Multiplication
stevep 0:04a9f72bbca7 824 *
stevep 0:04a9f72bbca7 825 *
stevep 0:04a9f72bbca7 826 */
stevep 0:04a9f72bbca7 827
stevep 0:04a9f72bbca7 828 public:
stevep 0:04a9f72bbca7 829
stevep 0:04a9f72bbca7 830 /*!
stevep 0:04a9f72bbca7 831 multiplication: this = this * ss2
stevep 0:04a9f72bbca7 832
stevep 0:04a9f72bbca7 833 it can return a carry
stevep 0:04a9f72bbca7 834 */
stevep 0:04a9f72bbca7 835 uint MulInt(uint ss2)
stevep 0:04a9f72bbca7 836 {
stevep 0:04a9f72bbca7 837 uint r1, r2, x1;
stevep 0:04a9f72bbca7 838 uint c = 0;
stevep 0:04a9f72bbca7 839
stevep 0:04a9f72bbca7 840 UInt<value_size> u(*this);
stevep 0:04a9f72bbca7 841 SetZero();
stevep 0:04a9f72bbca7 842
stevep 0:04a9f72bbca7 843 if( ss2 == 0 )
stevep 0:04a9f72bbca7 844 {
stevep 0:04a9f72bbca7 845 TTMATH_LOGC("UInt::MulInt(uint)", 0)
stevep 0:04a9f72bbca7 846 return 0;
stevep 0:04a9f72bbca7 847 }
stevep 0:04a9f72bbca7 848
stevep 0:04a9f72bbca7 849 for(x1=0 ; x1<value_size-1 ; ++x1)
stevep 0:04a9f72bbca7 850 {
stevep 0:04a9f72bbca7 851 MulTwoWords(u.table[x1], ss2, &r2, &r1);
stevep 0:04a9f72bbca7 852 c += AddTwoInts(r2,r1,x1);
stevep 0:04a9f72bbca7 853 }
stevep 0:04a9f72bbca7 854
stevep 0:04a9f72bbca7 855 // x1 = value_size-1 (last word)
stevep 0:04a9f72bbca7 856 MulTwoWords(u.table[x1], ss2, &r2, &r1);
stevep 0:04a9f72bbca7 857 c += (r2!=0) ? 1 : 0;
stevep 0:04a9f72bbca7 858 c += AddInt(r1, x1);
stevep 0:04a9f72bbca7 859
stevep 0:04a9f72bbca7 860 TTMATH_LOGC("UInt::MulInt(uint)", c)
stevep 0:04a9f72bbca7 861
stevep 0:04a9f72bbca7 862 return (c==0)? 0 : 1;
stevep 0:04a9f72bbca7 863 }
stevep 0:04a9f72bbca7 864
stevep 0:04a9f72bbca7 865
stevep 0:04a9f72bbca7 866 /*!
stevep 0:04a9f72bbca7 867 multiplication: result = this * ss2
stevep 0:04a9f72bbca7 868
stevep 0:04a9f72bbca7 869 we're using this method only when result_size is greater than value_size
stevep 0:04a9f72bbca7 870 if so there will not be a carry
stevep 0:04a9f72bbca7 871 */
stevep 0:04a9f72bbca7 872 template<uint result_size>
stevep 0:04a9f72bbca7 873 void MulInt(uint ss2, UInt<result_size> & result) const
stevep 0:04a9f72bbca7 874 {
stevep 0:04a9f72bbca7 875 TTMATH_ASSERT( result_size > value_size )
stevep 0:04a9f72bbca7 876
stevep 0:04a9f72bbca7 877 uint r2,r1;
stevep 0:04a9f72bbca7 878 uint x1size=value_size;
stevep 0:04a9f72bbca7 879 uint x1start=0;
stevep 0:04a9f72bbca7 880
stevep 0:04a9f72bbca7 881 result.SetZero();
stevep 0:04a9f72bbca7 882
stevep 0:04a9f72bbca7 883 if( ss2 == 0 )
stevep 0:04a9f72bbca7 884 {
stevep 0:04a9f72bbca7 885 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
stevep 0:04a9f72bbca7 886 return;
stevep 0:04a9f72bbca7 887 }
stevep 0:04a9f72bbca7 888
stevep 0:04a9f72bbca7 889 if( value_size > 2 )
stevep 0:04a9f72bbca7 890 {
stevep 0:04a9f72bbca7 891 // if the value_size is smaller than or equal to 2
stevep 0:04a9f72bbca7 892 // there is no sense to set x1size and x1start to another values
stevep 0:04a9f72bbca7 893
stevep 0:04a9f72bbca7 894 for(x1size=value_size ; x1size>0 && table[x1size-1]==0 ; --x1size);
stevep 0:04a9f72bbca7 895
stevep 0:04a9f72bbca7 896 if( x1size == 0 )
stevep 0:04a9f72bbca7 897 {
stevep 0:04a9f72bbca7 898 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
stevep 0:04a9f72bbca7 899 return;
stevep 0:04a9f72bbca7 900 }
stevep 0:04a9f72bbca7 901
stevep 0:04a9f72bbca7 902 for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start);
stevep 0:04a9f72bbca7 903 }
stevep 0:04a9f72bbca7 904
stevep 0:04a9f72bbca7 905 for(uint x1=x1start ; x1<x1size ; ++x1)
stevep 0:04a9f72bbca7 906 {
stevep 0:04a9f72bbca7 907 MulTwoWords(table[x1], ss2, &r2, &r1 );
stevep 0:04a9f72bbca7 908 result.AddTwoInts(r2,r1,x1);
stevep 0:04a9f72bbca7 909 }
stevep 0:04a9f72bbca7 910
stevep 0:04a9f72bbca7 911 TTMATH_VECTOR_LOG("UInt::MulInt(uint, UInt<>)", result.table, result_size)
stevep 0:04a9f72bbca7 912
stevep 0:04a9f72bbca7 913 return;
stevep 0:04a9f72bbca7 914 }
stevep 0:04a9f72bbca7 915
stevep 0:04a9f72bbca7 916
stevep 0:04a9f72bbca7 917
stevep 0:04a9f72bbca7 918 /*!
stevep 0:04a9f72bbca7 919 the multiplication 'this' = 'this' * ss2
stevep 0:04a9f72bbca7 920
stevep 0:04a9f72bbca7 921 algorithm: 100 - means automatically choose the fastest algorithm
stevep 0:04a9f72bbca7 922 */
stevep 0:04a9f72bbca7 923 uint Mul(const UInt<value_size> & ss2, uint algorithm = 100)
stevep 0:04a9f72bbca7 924 {
stevep 0:04a9f72bbca7 925 switch( algorithm )
stevep 0:04a9f72bbca7 926 {
stevep 0:04a9f72bbca7 927 case 1:
stevep 0:04a9f72bbca7 928 return Mul1(ss2);
stevep 0:04a9f72bbca7 929
stevep 0:04a9f72bbca7 930 case 2:
stevep 0:04a9f72bbca7 931 return Mul2(ss2);
stevep 0:04a9f72bbca7 932
stevep 0:04a9f72bbca7 933 case 3:
stevep 0:04a9f72bbca7 934 return Mul3(ss2);
stevep 0:04a9f72bbca7 935
stevep 0:04a9f72bbca7 936 case 100:
stevep 0:04a9f72bbca7 937 default:
stevep 0:04a9f72bbca7 938 return MulFastest(ss2);
stevep 0:04a9f72bbca7 939 }
stevep 0:04a9f72bbca7 940 }
stevep 0:04a9f72bbca7 941
stevep 0:04a9f72bbca7 942
stevep 0:04a9f72bbca7 943 /*!
stevep 0:04a9f72bbca7 944 the multiplication 'result' = 'this' * ss2
stevep 0:04a9f72bbca7 945
stevep 0:04a9f72bbca7 946 since the 'result' is twice bigger than 'this' and 'ss2'
stevep 0:04a9f72bbca7 947 this method never returns a carry
stevep 0:04a9f72bbca7 948
stevep 0:04a9f72bbca7 949 algorithm: 100 - means automatically choose the fastest algorithm
stevep 0:04a9f72bbca7 950 */
stevep 0:04a9f72bbca7 951 void MulBig(const UInt<value_size> & ss2,
stevep 0:04a9f72bbca7 952 UInt<value_size*2> & result,
stevep 0:04a9f72bbca7 953 uint algorithm = 100)
stevep 0:04a9f72bbca7 954 {
stevep 0:04a9f72bbca7 955 switch( algorithm )
stevep 0:04a9f72bbca7 956 {
stevep 0:04a9f72bbca7 957 case 1:
stevep 0:04a9f72bbca7 958 return Mul1Big(ss2, result);
stevep 0:04a9f72bbca7 959
stevep 0:04a9f72bbca7 960 case 2:
stevep 0:04a9f72bbca7 961 return Mul2Big(ss2, result);
stevep 0:04a9f72bbca7 962
stevep 0:04a9f72bbca7 963 case 3:
stevep 0:04a9f72bbca7 964 return Mul3Big(ss2, result);
stevep 0:04a9f72bbca7 965
stevep 0:04a9f72bbca7 966 case 100:
stevep 0:04a9f72bbca7 967 default:
stevep 0:04a9f72bbca7 968 return MulFastestBig(ss2, result);
stevep 0:04a9f72bbca7 969 }
stevep 0:04a9f72bbca7 970 }
stevep 0:04a9f72bbca7 971
stevep 0:04a9f72bbca7 972
stevep 0:04a9f72bbca7 973
stevep 0:04a9f72bbca7 974 /*!
stevep 0:04a9f72bbca7 975 the first version of the multiplication algorithm
stevep 0:04a9f72bbca7 976 */
stevep 0:04a9f72bbca7 977
stevep 0:04a9f72bbca7 978 private:
stevep 0:04a9f72bbca7 979
stevep 0:04a9f72bbca7 980 /*!
stevep 0:04a9f72bbca7 981 multiplication: this = this * ss2
stevep 0:04a9f72bbca7 982
stevep 0:04a9f72bbca7 983 it returns carry if it has been
stevep 0:04a9f72bbca7 984 */
stevep 0:04a9f72bbca7 985 uint Mul1Ref(const UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 986 {
stevep 0:04a9f72bbca7 987 TTMATH_REFERENCE_ASSERT( ss2 )
stevep 0:04a9f72bbca7 988
stevep 0:04a9f72bbca7 989 UInt<value_size> ss1( *this );
stevep 0:04a9f72bbca7 990 SetZero();
stevep 0:04a9f72bbca7 991
stevep 0:04a9f72bbca7 992 for(uint i=0; i < value_size*TTMATH_BITS_PER_UINT ; ++i)
stevep 0:04a9f72bbca7 993 {
stevep 0:04a9f72bbca7 994 if( Add(*this) )
stevep 0:04a9f72bbca7 995 {
stevep 0:04a9f72bbca7 996 TTMATH_LOGC("UInt::Mul1", 1)
stevep 0:04a9f72bbca7 997 return 1;
stevep 0:04a9f72bbca7 998 }
stevep 0:04a9f72bbca7 999
stevep 0:04a9f72bbca7 1000 if( ss1.Rcl(1) )
stevep 0:04a9f72bbca7 1001 if( Add(ss2) )
stevep 0:04a9f72bbca7 1002 {
stevep 0:04a9f72bbca7 1003 TTMATH_LOGC("UInt::Mul1", 1)
stevep 0:04a9f72bbca7 1004 return 1;
stevep 0:04a9f72bbca7 1005 }
stevep 0:04a9f72bbca7 1006 }
stevep 0:04a9f72bbca7 1007
stevep 0:04a9f72bbca7 1008 TTMATH_LOGC("UInt::Mul1", 0)
stevep 0:04a9f72bbca7 1009
stevep 0:04a9f72bbca7 1010 return 0;
stevep 0:04a9f72bbca7 1011 }
stevep 0:04a9f72bbca7 1012
stevep 0:04a9f72bbca7 1013
stevep 0:04a9f72bbca7 1014 public:
stevep 0:04a9f72bbca7 1015
stevep 0:04a9f72bbca7 1016 /*!
stevep 0:04a9f72bbca7 1017 multiplication: this = this * ss2
stevep 0:04a9f72bbca7 1018 can return carry
stevep 0:04a9f72bbca7 1019 */
stevep 0:04a9f72bbca7 1020 uint Mul1(const UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 1021 {
stevep 0:04a9f72bbca7 1022 if( this == &ss2 )
stevep 0:04a9f72bbca7 1023 {
stevep 0:04a9f72bbca7 1024 UInt<value_size> copy_ss2(ss2);
stevep 0:04a9f72bbca7 1025 return Mul1Ref(copy_ss2);
stevep 0:04a9f72bbca7 1026 }
stevep 0:04a9f72bbca7 1027 else
stevep 0:04a9f72bbca7 1028 {
stevep 0:04a9f72bbca7 1029 return Mul1Ref(ss2);
stevep 0:04a9f72bbca7 1030 }
stevep 0:04a9f72bbca7 1031 }
stevep 0:04a9f72bbca7 1032
stevep 0:04a9f72bbca7 1033
stevep 0:04a9f72bbca7 1034 /*!
stevep 0:04a9f72bbca7 1035 multiplication: result = this * ss2
stevep 0:04a9f72bbca7 1036
stevep 0:04a9f72bbca7 1037 result is twice bigger than 'this' and 'ss2'
stevep 0:04a9f72bbca7 1038 this method never returns carry
stevep 0:04a9f72bbca7 1039 */
stevep 0:04a9f72bbca7 1040 void Mul1Big(const UInt<value_size> & ss2_, UInt<value_size*2> & result)
stevep 0:04a9f72bbca7 1041 {
stevep 0:04a9f72bbca7 1042 UInt<value_size*2> ss2;
stevep 0:04a9f72bbca7 1043 uint i;
stevep 0:04a9f72bbca7 1044
stevep 0:04a9f72bbca7 1045 // copying *this into result and ss2_ into ss2
stevep 0:04a9f72bbca7 1046 for(i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 1047 {
stevep 0:04a9f72bbca7 1048 result.table[i] = table[i];
stevep 0:04a9f72bbca7 1049 ss2.table[i] = ss2_.table[i];
stevep 0:04a9f72bbca7 1050 }
stevep 0:04a9f72bbca7 1051
stevep 0:04a9f72bbca7 1052 // cleaning the highest bytes in result and ss2
stevep 0:04a9f72bbca7 1053 for( ; i < value_size*2 ; ++i)
stevep 0:04a9f72bbca7 1054 {
stevep 0:04a9f72bbca7 1055 result.table[i] = 0;
stevep 0:04a9f72bbca7 1056 ss2.table[i] = 0;
stevep 0:04a9f72bbca7 1057 }
stevep 0:04a9f72bbca7 1058
stevep 0:04a9f72bbca7 1059 // multiply
stevep 0:04a9f72bbca7 1060 // (there will not be a carry)
stevep 0:04a9f72bbca7 1061 result.Mul1( ss2 );
stevep 0:04a9f72bbca7 1062
stevep 0:04a9f72bbca7 1063 TTMATH_LOG("UInt::Mul1Big")
stevep 0:04a9f72bbca7 1064 }
stevep 0:04a9f72bbca7 1065
stevep 0:04a9f72bbca7 1066
stevep 0:04a9f72bbca7 1067
stevep 0:04a9f72bbca7 1068 /*!
stevep 0:04a9f72bbca7 1069 the second version of the multiplication algorithm
stevep 0:04a9f72bbca7 1070
stevep 0:04a9f72bbca7 1071 this algorithm is similar to the 'schoolbook method' which is done by hand
stevep 0:04a9f72bbca7 1072 */
stevep 0:04a9f72bbca7 1073
stevep 0:04a9f72bbca7 1074 /*!
stevep 0:04a9f72bbca7 1075 multiplication: this = this * ss2
stevep 0:04a9f72bbca7 1076
stevep 0:04a9f72bbca7 1077 it returns carry if it has been
stevep 0:04a9f72bbca7 1078 */
stevep 0:04a9f72bbca7 1079 uint Mul2(const UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 1080 {
stevep 0:04a9f72bbca7 1081 UInt<value_size*2> result;
stevep 0:04a9f72bbca7 1082 uint i, c = 0;
stevep 0:04a9f72bbca7 1083
stevep 0:04a9f72bbca7 1084 Mul2Big(ss2, result);
stevep 0:04a9f72bbca7 1085
stevep 0:04a9f72bbca7 1086 // copying result
stevep 0:04a9f72bbca7 1087 for(i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 1088 table[i] = result.table[i];
stevep 0:04a9f72bbca7 1089
stevep 0:04a9f72bbca7 1090 // testing carry
stevep 0:04a9f72bbca7 1091 for( ; i<value_size*2 ; ++i)
stevep 0:04a9f72bbca7 1092 if( result.table[i] != 0 )
stevep 0:04a9f72bbca7 1093 {
stevep 0:04a9f72bbca7 1094 c = 1;
stevep 0:04a9f72bbca7 1095 break;
stevep 0:04a9f72bbca7 1096 }
stevep 0:04a9f72bbca7 1097
stevep 0:04a9f72bbca7 1098 TTMATH_LOGC("UInt::Mul2", c)
stevep 0:04a9f72bbca7 1099
stevep 0:04a9f72bbca7 1100 return c;
stevep 0:04a9f72bbca7 1101 }
stevep 0:04a9f72bbca7 1102
stevep 0:04a9f72bbca7 1103
stevep 0:04a9f72bbca7 1104 /*!
stevep 0:04a9f72bbca7 1105 multiplication: result = this * ss2
stevep 0:04a9f72bbca7 1106
stevep 0:04a9f72bbca7 1107 result is twice bigger than this and ss2
stevep 0:04a9f72bbca7 1108 this method never returns carry
stevep 0:04a9f72bbca7 1109 */
stevep 0:04a9f72bbca7 1110 void Mul2Big(const UInt<value_size> & ss2, UInt<value_size*2> & result)
stevep 0:04a9f72bbca7 1111 {
stevep 0:04a9f72bbca7 1112 Mul2Big2<value_size>(table, ss2.table, result);
stevep 0:04a9f72bbca7 1113
stevep 0:04a9f72bbca7 1114 TTMATH_LOG("UInt::Mul2Big")
stevep 0:04a9f72bbca7 1115 }
stevep 0:04a9f72bbca7 1116
stevep 0:04a9f72bbca7 1117
stevep 0:04a9f72bbca7 1118 private:
stevep 0:04a9f72bbca7 1119
stevep 0:04a9f72bbca7 1120 /*!
stevep 0:04a9f72bbca7 1121 an auxiliary method for calculating the multiplication
stevep 0:04a9f72bbca7 1122
stevep 0:04a9f72bbca7 1123 arguments we're taking as pointers (this is to improve the Mul3Big2()- avoiding
stevep 0:04a9f72bbca7 1124 unnecessary copying objects), the result should be taken as a pointer too,
stevep 0:04a9f72bbca7 1125 but at the moment there is no method AddTwoInts() which can operate on pointers
stevep 0:04a9f72bbca7 1126 */
stevep 0:04a9f72bbca7 1127 template<uint ss_size>
stevep 0:04a9f72bbca7 1128 void Mul2Big2(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result)
stevep 0:04a9f72bbca7 1129 {
stevep 0:04a9f72bbca7 1130 uint x1size = ss_size, x2size = ss_size;
stevep 0:04a9f72bbca7 1131 uint x1start = 0, x2start = 0;
stevep 0:04a9f72bbca7 1132
stevep 0:04a9f72bbca7 1133 if( ss_size > 2 )
stevep 0:04a9f72bbca7 1134 {
stevep 0:04a9f72bbca7 1135 // if the ss_size is smaller than or equal to 2
stevep 0:04a9f72bbca7 1136 // there is no sense to set x1size (and others) to another values
stevep 0:04a9f72bbca7 1137
stevep 0:04a9f72bbca7 1138 for(x1size=ss_size ; x1size>0 && ss1[x1size-1]==0 ; --x1size);
stevep 0:04a9f72bbca7 1139 for(x2size=ss_size ; x2size>0 && ss2[x2size-1]==0 ; --x2size);
stevep 0:04a9f72bbca7 1140
stevep 0:04a9f72bbca7 1141 for(x1start=0 ; x1start<x1size && ss1[x1start]==0 ; ++x1start);
stevep 0:04a9f72bbca7 1142 for(x2start=0 ; x2start<x2size && ss2[x2start]==0 ; ++x2start);
stevep 0:04a9f72bbca7 1143 }
stevep 0:04a9f72bbca7 1144
stevep 0:04a9f72bbca7 1145 Mul2Big3<ss_size>(ss1, ss2, result, x1start, x1size, x2start, x2size);
stevep 0:04a9f72bbca7 1146 }
stevep 0:04a9f72bbca7 1147
stevep 0:04a9f72bbca7 1148
stevep 0:04a9f72bbca7 1149
stevep 0:04a9f72bbca7 1150 /*!
stevep 0:04a9f72bbca7 1151 an auxiliary method for calculating the multiplication
stevep 0:04a9f72bbca7 1152 */
stevep 0:04a9f72bbca7 1153 template<uint ss_size>
stevep 0:04a9f72bbca7 1154 void Mul2Big3(const uint * ss1, const uint * ss2, UInt<ss_size*2> & result, uint x1start, uint x1size, uint x2start, uint x2size)
stevep 0:04a9f72bbca7 1155 {
stevep 0:04a9f72bbca7 1156 uint r2, r1;
stevep 0:04a9f72bbca7 1157
stevep 0:04a9f72bbca7 1158 result.SetZero();
stevep 0:04a9f72bbca7 1159
stevep 0:04a9f72bbca7 1160 if( x1size==0 || x2size==0 )
stevep 0:04a9f72bbca7 1161 return;
stevep 0:04a9f72bbca7 1162
stevep 0:04a9f72bbca7 1163 for(uint x1=x1start ; x1<x1size ; ++x1)
stevep 0:04a9f72bbca7 1164 {
stevep 0:04a9f72bbca7 1165 for(uint x2=x2start ; x2<x2size ; ++x2)
stevep 0:04a9f72bbca7 1166 {
stevep 0:04a9f72bbca7 1167 MulTwoWords(ss1[x1], ss2[x2], &r2, &r1);
stevep 0:04a9f72bbca7 1168 result.AddTwoInts(r2, r1, x2+x1);
stevep 0:04a9f72bbca7 1169 // here will never be a carry
stevep 0:04a9f72bbca7 1170 }
stevep 0:04a9f72bbca7 1171 }
stevep 0:04a9f72bbca7 1172 }
stevep 0:04a9f72bbca7 1173
stevep 0:04a9f72bbca7 1174
stevep 0:04a9f72bbca7 1175 public:
stevep 0:04a9f72bbca7 1176
stevep 0:04a9f72bbca7 1177
stevep 0:04a9f72bbca7 1178 /*!
stevep 0:04a9f72bbca7 1179 multiplication: this = this * ss2
stevep 0:04a9f72bbca7 1180
stevep 0:04a9f72bbca7 1181 This is Karatsuba Multiplication algorithm, we're using it when value_size is greater than
stevep 0:04a9f72bbca7 1182 or equal to TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE macro (defined in ttmathuint.h).
stevep 0:04a9f72bbca7 1183 If value_size is smaller then we're using Mul2Big() instead.
stevep 0:04a9f72bbca7 1184
stevep 0:04a9f72bbca7 1185 Karatsuba multiplication:
stevep 0:04a9f72bbca7 1186 Assume we have:
stevep 0:04a9f72bbca7 1187 this = x = x1*B^m + x0
stevep 0:04a9f72bbca7 1188 ss2 = y = y1*B^m + y0
stevep 0:04a9f72bbca7 1189 where x0 and y0 are less than B^m
stevep 0:04a9f72bbca7 1190 the product from multiplication we can show as:
stevep 0:04a9f72bbca7 1191 x*y = (x1*B^m + x0)(y1*B^m + y0) = z2*B^(2m) + z1*B^m + z0
stevep 0:04a9f72bbca7 1192 where
stevep 0:04a9f72bbca7 1193 z2 = x1*y1
stevep 0:04a9f72bbca7 1194 z1 = x1*y0 + x0*y1
stevep 0:04a9f72bbca7 1195 z0 = x0*y0
stevep 0:04a9f72bbca7 1196 this is standard schoolbook algorithm with O(n^2), Karatsuba observed that z1 can be given in other form:
stevep 0:04a9f72bbca7 1197 z1 = (x1 + x0)*(y1 + y0) - z2 - z0 / z1 = (x1*y1 + x1*y0 + x0*y1 + x0*y0) - x1*y1 - x0*y0 = x1*y0 + x0*y1 /
stevep 0:04a9f72bbca7 1198 and to calculate the multiplication we need only three multiplications (with some additions and subtractions)
stevep 0:04a9f72bbca7 1199
stevep 0:04a9f72bbca7 1200 Our objects 'this' and 'ss2' we divide into two parts and by using recurrence we calculate the multiplication.
stevep 0:04a9f72bbca7 1201 Karatsuba multiplication has O( n^(ln(3)/ln(2)) )
stevep 0:04a9f72bbca7 1202 */
stevep 0:04a9f72bbca7 1203 uint Mul3(const UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 1204 {
stevep 0:04a9f72bbca7 1205 UInt<value_size*2> result;
stevep 0:04a9f72bbca7 1206 uint i, c = 0;
stevep 0:04a9f72bbca7 1207
stevep 0:04a9f72bbca7 1208 Mul3Big(ss2, result);
stevep 0:04a9f72bbca7 1209
stevep 0:04a9f72bbca7 1210 // copying result
stevep 0:04a9f72bbca7 1211 for(i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 1212 table[i] = result.table[i];
stevep 0:04a9f72bbca7 1213
stevep 0:04a9f72bbca7 1214 // testing carry
stevep 0:04a9f72bbca7 1215 for( ; i<value_size*2 ; ++i)
stevep 0:04a9f72bbca7 1216 if( result.table[i] != 0 )
stevep 0:04a9f72bbca7 1217 {
stevep 0:04a9f72bbca7 1218 c = 1;
stevep 0:04a9f72bbca7 1219 break;
stevep 0:04a9f72bbca7 1220 }
stevep 0:04a9f72bbca7 1221
stevep 0:04a9f72bbca7 1222 TTMATH_LOGC("UInt::Mul3", c)
stevep 0:04a9f72bbca7 1223
stevep 0:04a9f72bbca7 1224 return c;
stevep 0:04a9f72bbca7 1225 }
stevep 0:04a9f72bbca7 1226
stevep 0:04a9f72bbca7 1227
stevep 0:04a9f72bbca7 1228
stevep 0:04a9f72bbca7 1229 /*!
stevep 0:04a9f72bbca7 1230 multiplication: result = this * ss2
stevep 0:04a9f72bbca7 1231
stevep 0:04a9f72bbca7 1232 result is twice bigger than this and ss2,
stevep 0:04a9f72bbca7 1233 this method never returns carry,
stevep 0:04a9f72bbca7 1234 (Karatsuba multiplication)
stevep 0:04a9f72bbca7 1235 */
stevep 0:04a9f72bbca7 1236 void Mul3Big(const UInt<value_size> & ss2, UInt<value_size*2> & result)
stevep 0:04a9f72bbca7 1237 {
stevep 0:04a9f72bbca7 1238 Mul3Big2<value_size>(table, ss2.table, result.table);
stevep 0:04a9f72bbca7 1239
stevep 0:04a9f72bbca7 1240 TTMATH_LOG("UInt::Mul3Big")
stevep 0:04a9f72bbca7 1241 }
stevep 0:04a9f72bbca7 1242
stevep 0:04a9f72bbca7 1243
stevep 0:04a9f72bbca7 1244
stevep 0:04a9f72bbca7 1245 private:
stevep 0:04a9f72bbca7 1246
stevep 0:04a9f72bbca7 1247 /*!
stevep 0:04a9f72bbca7 1248 an auxiliary method for calculating the Karatsuba multiplication
stevep 0:04a9f72bbca7 1249
stevep 0:04a9f72bbca7 1250 result_size is equal ss_size*2
stevep 0:04a9f72bbca7 1251 */
stevep 0:04a9f72bbca7 1252 template<uint ss_size>
stevep 0:04a9f72bbca7 1253 void Mul3Big2(const uint * ss1, const uint * ss2, uint * result)
stevep 0:04a9f72bbca7 1254 {
stevep 0:04a9f72bbca7 1255 const uint * x1, * x0, * y1, * y0;
stevep 0:04a9f72bbca7 1256
stevep 0:04a9f72bbca7 1257
stevep 0:04a9f72bbca7 1258 if( ss_size>1 && ss_size<TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE )
stevep 0:04a9f72bbca7 1259 {
stevep 0:04a9f72bbca7 1260 UInt<ss_size*2> res;
stevep 0:04a9f72bbca7 1261 Mul2Big2<ss_size>(ss1, ss2, res);
stevep 0:04a9f72bbca7 1262
stevep 0:04a9f72bbca7 1263 #ifdef __clang__
stevep 0:04a9f72bbca7 1264 #pragma clang diagnostic push
stevep 0:04a9f72bbca7 1265 #pragma clang diagnostic ignored "-Wtautological-compare"
stevep 0:04a9f72bbca7 1266 #endif
stevep 0:04a9f72bbca7 1267
stevep 0:04a9f72bbca7 1268 for(uint i=0 ; i<ss_size*2 ; ++i)
stevep 0:04a9f72bbca7 1269 result[i] = res.table[i];
stevep 0:04a9f72bbca7 1270
stevep 0:04a9f72bbca7 1271 #ifdef __clang__
stevep 0:04a9f72bbca7 1272 #pragma clang diagnostic pop
stevep 0:04a9f72bbca7 1273 #endif
stevep 0:04a9f72bbca7 1274
stevep 0:04a9f72bbca7 1275 return;
stevep 0:04a9f72bbca7 1276 }
stevep 0:04a9f72bbca7 1277 else
stevep 0:04a9f72bbca7 1278 if( ss_size == 1 )
stevep 0:04a9f72bbca7 1279 {
stevep 0:04a9f72bbca7 1280 return MulTwoWords(*ss1, *ss2, &result[1], &result[0]);
stevep 0:04a9f72bbca7 1281 }
stevep 0:04a9f72bbca7 1282
stevep 0:04a9f72bbca7 1283
stevep 0:04a9f72bbca7 1284 if( (ss_size & 1) == 1 )
stevep 0:04a9f72bbca7 1285 {
stevep 0:04a9f72bbca7 1286 // ss_size is odd
stevep 0:04a9f72bbca7 1287 x0 = ss1;
stevep 0:04a9f72bbca7 1288 y0 = ss2;
stevep 0:04a9f72bbca7 1289 x1 = ss1 + ss_size / 2 + 1;
stevep 0:04a9f72bbca7 1290 y1 = ss2 + ss_size / 2 + 1;
stevep 0:04a9f72bbca7 1291
stevep 0:04a9f72bbca7 1292 // the second vectors (x1 and y1) are smaller about one from the first ones (x0 and y0)
stevep 0:04a9f72bbca7 1293 Mul3Big3<ss_size/2 + 1, ss_size/2, ss_size*2>(x1, x0, y1, y0, result);
stevep 0:04a9f72bbca7 1294 }
stevep 0:04a9f72bbca7 1295 else
stevep 0:04a9f72bbca7 1296 {
stevep 0:04a9f72bbca7 1297 // ss_size is even
stevep 0:04a9f72bbca7 1298 x0 = ss1;
stevep 0:04a9f72bbca7 1299 y0 = ss2;
stevep 0:04a9f72bbca7 1300 x1 = ss1 + ss_size / 2;
stevep 0:04a9f72bbca7 1301 y1 = ss2 + ss_size / 2;
stevep 0:04a9f72bbca7 1302
stevep 0:04a9f72bbca7 1303 // all four vectors (x0 x1 y0 y1) are equal in size
stevep 0:04a9f72bbca7 1304 Mul3Big3<ss_size/2, ss_size/2, ss_size*2>(x1, x0, y1, y0, result);
stevep 0:04a9f72bbca7 1305 }
stevep 0:04a9f72bbca7 1306 }
stevep 0:04a9f72bbca7 1307
stevep 0:04a9f72bbca7 1308
stevep 0:04a9f72bbca7 1309
stevep 0:04a9f72bbca7 1310 #ifdef _MSC_VER
stevep 0:04a9f72bbca7 1311 #pragma warning (disable : 4717)
stevep 0:04a9f72bbca7 1312 //warning C4717: recursive on all control paths, function will cause runtime stack overflow
stevep 0:04a9f72bbca7 1313 //we have the stop point in Mul3Big2() method
stevep 0:04a9f72bbca7 1314 #endif
stevep 0:04a9f72bbca7 1315
stevep 0:04a9f72bbca7 1316
stevep 0:04a9f72bbca7 1317 /*!
stevep 0:04a9f72bbca7 1318 an auxiliary method for calculating the Karatsuba multiplication
stevep 0:04a9f72bbca7 1319
stevep 0:04a9f72bbca7 1320 x = x1*B^m + x0
stevep 0:04a9f72bbca7 1321 y = y1*B^m + y0
stevep 0:04a9f72bbca7 1322
stevep 0:04a9f72bbca7 1323 first_size - is the size of vectors: x0 and y0
stevep 0:04a9f72bbca7 1324 second_size - is the size of vectors: x1 and y1 (can be either equal first_size or smaller about one from first_size)
stevep 0:04a9f72bbca7 1325
stevep 0:04a9f72bbca7 1326 x*y = (x1*B^m + x0)(y1*B^m + y0) = z2*B^(2m) + z1*B^m + z0
stevep 0:04a9f72bbca7 1327 where
stevep 0:04a9f72bbca7 1328 z0 = x0*y0
stevep 0:04a9f72bbca7 1329 z2 = x1*y1
stevep 0:04a9f72bbca7 1330 z1 = (x1 + x0)*(y1 + y0) - z2 - z0
stevep 0:04a9f72bbca7 1331 */
stevep 0:04a9f72bbca7 1332 template<uint first_size, uint second_size, uint result_size>
stevep 0:04a9f72bbca7 1333 void Mul3Big3(const uint * x1, const uint * x0, const uint * y1, const uint * y0, uint * result)
stevep 0:04a9f72bbca7 1334 {
stevep 0:04a9f72bbca7 1335 uint i, c, xc, yc;
stevep 0:04a9f72bbca7 1336
stevep 0:04a9f72bbca7 1337 UInt<first_size> temp, temp2;
stevep 0:04a9f72bbca7 1338 UInt<first_size*3> z1;
stevep 0:04a9f72bbca7 1339
stevep 0:04a9f72bbca7 1340 // z0 and z2 we store directly in the result (we don't use any temporary variables)
stevep 0:04a9f72bbca7 1341 Mul3Big2<first_size>(x0, y0, result); // z0
stevep 0:04a9f72bbca7 1342 Mul3Big2<second_size>(x1, y1, result+first_size*2); // z2
stevep 0:04a9f72bbca7 1343
stevep 0:04a9f72bbca7 1344 // now we calculate z1
stevep 0:04a9f72bbca7 1345 // temp = (x0 + x1)
stevep 0:04a9f72bbca7 1346 // temp2 = (y0 + y1)
stevep 0:04a9f72bbca7 1347 // we're using temp and temp2 with UInt<first_size>, although there can be a carry but
stevep 0:04a9f72bbca7 1348 // we simple remember it in xc and yc (xc and yc can be either 0 or 1),
stevep 0:04a9f72bbca7 1349 // and (x0 + x1)*(y0 + y1) we calculate in this way (schoolbook algorithm):
stevep 0:04a9f72bbca7 1350 //
stevep 0:04a9f72bbca7 1351 // xc | temp
stevep 0:04a9f72bbca7 1352 // yc | temp2
stevep 0:04a9f72bbca7 1353 // --------------------
stevep 0:04a9f72bbca7 1354 // (temp * temp2)
stevep 0:04a9f72bbca7 1355 // xc*temp2 |
stevep 0:04a9f72bbca7 1356 // yc*temp |
stevep 0:04a9f72bbca7 1357 // xc*yc |
stevep 0:04a9f72bbca7 1358 // ---------- z1 --------
stevep 0:04a9f72bbca7 1359 //
stevep 0:04a9f72bbca7 1360 // and the result is never larger in size than 3*first_size
stevep 0:04a9f72bbca7 1361
stevep 0:04a9f72bbca7 1362 xc = AddVector(x0, x1, first_size, second_size, temp.table);
stevep 0:04a9f72bbca7 1363 yc = AddVector(y0, y1, first_size, second_size, temp2.table);
stevep 0:04a9f72bbca7 1364
stevep 0:04a9f72bbca7 1365 Mul3Big2<first_size>(temp.table, temp2.table, z1.table);
stevep 0:04a9f72bbca7 1366
stevep 0:04a9f72bbca7 1367 #ifdef __clang__
stevep 0:04a9f72bbca7 1368 #pragma clang diagnostic push
stevep 0:04a9f72bbca7 1369 #pragma clang diagnostic ignored "-Wtautological-compare"
stevep 0:04a9f72bbca7 1370 #endif
stevep 0:04a9f72bbca7 1371
stevep 0:04a9f72bbca7 1372 // clearing the rest of z1
stevep 0:04a9f72bbca7 1373 for(i=first_size*2 ; i<first_size*3 ; ++i)
stevep 0:04a9f72bbca7 1374 z1.table[i] = 0;
stevep 0:04a9f72bbca7 1375
stevep 0:04a9f72bbca7 1376 #ifdef __clang__
stevep 0:04a9f72bbca7 1377 #pragma clang diagnostic pop
stevep 0:04a9f72bbca7 1378 #endif
stevep 0:04a9f72bbca7 1379
stevep 0:04a9f72bbca7 1380 if( xc )
stevep 0:04a9f72bbca7 1381 {
stevep 0:04a9f72bbca7 1382 c = AddVector(z1.table+first_size, temp2.table, first_size*3-first_size, first_size, z1.table+first_size);
stevep 0:04a9f72bbca7 1383 TTMATH_ASSERT( c==0 )
stevep 0:04a9f72bbca7 1384 }
stevep 0:04a9f72bbca7 1385
stevep 0:04a9f72bbca7 1386 if( yc )
stevep 0:04a9f72bbca7 1387 {
stevep 0:04a9f72bbca7 1388 c = AddVector(z1.table+first_size, temp.table, first_size*3-first_size, first_size, z1.table+first_size);
stevep 0:04a9f72bbca7 1389 TTMATH_ASSERT( c==0 )
stevep 0:04a9f72bbca7 1390 }
stevep 0:04a9f72bbca7 1391
stevep 0:04a9f72bbca7 1392
stevep 0:04a9f72bbca7 1393 if( xc && yc )
stevep 0:04a9f72bbca7 1394 {
stevep 0:04a9f72bbca7 1395 #ifdef __clang__
stevep 0:04a9f72bbca7 1396 #pragma clang diagnostic push
stevep 0:04a9f72bbca7 1397 #pragma clang diagnostic ignored "-Wtautological-compare"
stevep 0:04a9f72bbca7 1398 #endif
stevep 0:04a9f72bbca7 1399
stevep 0:04a9f72bbca7 1400 for( i=first_size*2 ; i<first_size*3 ; ++i )
stevep 0:04a9f72bbca7 1401 if( ++z1.table[i] != 0 )
stevep 0:04a9f72bbca7 1402 break; // break if there was no carry
stevep 0:04a9f72bbca7 1403
stevep 0:04a9f72bbca7 1404 #ifdef __clang__
stevep 0:04a9f72bbca7 1405 #pragma clang diagnostic pop
stevep 0:04a9f72bbca7 1406 #endif
stevep 0:04a9f72bbca7 1407 }
stevep 0:04a9f72bbca7 1408
stevep 0:04a9f72bbca7 1409 // z1 = z1 - z2
stevep 0:04a9f72bbca7 1410 c = SubVector(z1.table, result+first_size*2, first_size*3, second_size*2, z1.table);
stevep 0:04a9f72bbca7 1411 TTMATH_ASSERT(c==0)
stevep 0:04a9f72bbca7 1412
stevep 0:04a9f72bbca7 1413 // z1 = z1 - z0
stevep 0:04a9f72bbca7 1414 c = SubVector(z1.table, result, first_size*3, first_size*2, z1.table);
stevep 0:04a9f72bbca7 1415 TTMATH_ASSERT(c==0)
stevep 0:04a9f72bbca7 1416
stevep 0:04a9f72bbca7 1417 // here we've calculated the z1
stevep 0:04a9f72bbca7 1418 // now we're adding it to the result
stevep 0:04a9f72bbca7 1419
stevep 0:04a9f72bbca7 1420 if( first_size > second_size )
stevep 0:04a9f72bbca7 1421 {
stevep 0:04a9f72bbca7 1422 uint z1_size = result_size - first_size;
stevep 0:04a9f72bbca7 1423 TTMATH_ASSERT( z1_size <= first_size*3 )
stevep 0:04a9f72bbca7 1424
stevep 0:04a9f72bbca7 1425 #ifdef __clang__
stevep 0:04a9f72bbca7 1426 #pragma clang diagnostic push
stevep 0:04a9f72bbca7 1427 #pragma clang diagnostic ignored "-Wtautological-compare"
stevep 0:04a9f72bbca7 1428 #endif
stevep 0:04a9f72bbca7 1429
stevep 0:04a9f72bbca7 1430 for(i=z1_size ; i<first_size*3 ; ++i)
stevep 0:04a9f72bbca7 1431 {
stevep 0:04a9f72bbca7 1432 TTMATH_ASSERT( z1.table[i] == 0 )
stevep 0:04a9f72bbca7 1433 }
stevep 0:04a9f72bbca7 1434
stevep 0:04a9f72bbca7 1435 #ifdef __clang__
stevep 0:04a9f72bbca7 1436 #pragma clang diagnostic pop
stevep 0:04a9f72bbca7 1437 #endif
stevep 0:04a9f72bbca7 1438
stevep 0:04a9f72bbca7 1439 c = AddVector(result+first_size, z1.table, result_size-first_size, z1_size, result+first_size);
stevep 0:04a9f72bbca7 1440 TTMATH_ASSERT(c==0)
stevep 0:04a9f72bbca7 1441 }
stevep 0:04a9f72bbca7 1442 else
stevep 0:04a9f72bbca7 1443 {
stevep 0:04a9f72bbca7 1444 c = AddVector(result+first_size, z1.table, result_size-first_size, first_size*3, result+first_size);
stevep 0:04a9f72bbca7 1445 TTMATH_ASSERT(c==0)
stevep 0:04a9f72bbca7 1446 }
stevep 0:04a9f72bbca7 1447 }
stevep 0:04a9f72bbca7 1448
stevep 0:04a9f72bbca7 1449
stevep 0:04a9f72bbca7 1450
stevep 0:04a9f72bbca7 1451 #ifdef _MSC_VER
stevep 0:04a9f72bbca7 1452 #pragma warning (default : 4717)
stevep 0:04a9f72bbca7 1453 #endif
stevep 0:04a9f72bbca7 1454
stevep 0:04a9f72bbca7 1455
stevep 0:04a9f72bbca7 1456 public:
stevep 0:04a9f72bbca7 1457
stevep 0:04a9f72bbca7 1458
stevep 0:04a9f72bbca7 1459 /*!
stevep 0:04a9f72bbca7 1460 multiplication this = this * ss2
stevep 0:04a9f72bbca7 1461 */
stevep 0:04a9f72bbca7 1462 uint MulFastest(const UInt<value_size> & ss2)
stevep 0:04a9f72bbca7 1463 {
stevep 0:04a9f72bbca7 1464 UInt<value_size*2> result;
stevep 0:04a9f72bbca7 1465 uint i, c = 0;
stevep 0:04a9f72bbca7 1466
stevep 0:04a9f72bbca7 1467 MulFastestBig(ss2, result);
stevep 0:04a9f72bbca7 1468
stevep 0:04a9f72bbca7 1469 // copying result
stevep 0:04a9f72bbca7 1470 for(i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 1471 table[i] = result.table[i];
stevep 0:04a9f72bbca7 1472
stevep 0:04a9f72bbca7 1473 // testing carry
stevep 0:04a9f72bbca7 1474 for( ; i<value_size*2 ; ++i)
stevep 0:04a9f72bbca7 1475 if( result.table[i] != 0 )
stevep 0:04a9f72bbca7 1476 {
stevep 0:04a9f72bbca7 1477 c = 1;
stevep 0:04a9f72bbca7 1478 break;
stevep 0:04a9f72bbca7 1479 }
stevep 0:04a9f72bbca7 1480
stevep 0:04a9f72bbca7 1481 TTMATH_LOGC("UInt::MulFastest", c)
stevep 0:04a9f72bbca7 1482
stevep 0:04a9f72bbca7 1483 return c;
stevep 0:04a9f72bbca7 1484 }
stevep 0:04a9f72bbca7 1485
stevep 0:04a9f72bbca7 1486
stevep 0:04a9f72bbca7 1487 /*!
stevep 0:04a9f72bbca7 1488 multiplication result = this * ss2
stevep 0:04a9f72bbca7 1489
stevep 0:04a9f72bbca7 1490 this method is trying to select the fastest algorithm
stevep 0:04a9f72bbca7 1491 (in the future this method can be improved)
stevep 0:04a9f72bbca7 1492 */
stevep 0:04a9f72bbca7 1493 void MulFastestBig(const UInt<value_size> & ss2, UInt<value_size*2> & result)
stevep 0:04a9f72bbca7 1494 {
stevep 0:04a9f72bbca7 1495 if( value_size < TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE )
stevep 0:04a9f72bbca7 1496 return Mul2Big(ss2, result);
stevep 0:04a9f72bbca7 1497
stevep 0:04a9f72bbca7 1498 uint x1size = value_size, x2size = value_size;
stevep 0:04a9f72bbca7 1499 uint x1start = 0, x2start = 0;
stevep 0:04a9f72bbca7 1500
stevep 0:04a9f72bbca7 1501 for(x1size=value_size ; x1size>0 && table[x1size-1]==0 ; --x1size);
stevep 0:04a9f72bbca7 1502 for(x2size=value_size ; x2size>0 && ss2.table[x2size-1]==0 ; --x2size);
stevep 0:04a9f72bbca7 1503
stevep 0:04a9f72bbca7 1504 if( x1size==0 || x2size==0 )
stevep 0:04a9f72bbca7 1505 {
stevep 0:04a9f72bbca7 1506 // either 'this' or 'ss2' is equal zero - the result is zero too
stevep 0:04a9f72bbca7 1507 result.SetZero();
stevep 0:04a9f72bbca7 1508 return;
stevep 0:04a9f72bbca7 1509 }
stevep 0:04a9f72bbca7 1510
stevep 0:04a9f72bbca7 1511 for(x1start=0 ; x1start<x1size && table[x1start]==0 ; ++x1start);
stevep 0:04a9f72bbca7 1512 for(x2start=0 ; x2start<x2size && ss2.table[x2start]==0 ; ++x2start);
stevep 0:04a9f72bbca7 1513
stevep 0:04a9f72bbca7 1514 uint distancex1 = x1size - x1start;
stevep 0:04a9f72bbca7 1515 uint distancex2 = x2size - x2start;
stevep 0:04a9f72bbca7 1516
stevep 0:04a9f72bbca7 1517 if( distancex1 < 3 || distancex2 < 3 )
stevep 0:04a9f72bbca7 1518 // either 'this' or 'ss2' have only 2 (or 1) items different from zero (side by side)
stevep 0:04a9f72bbca7 1519 // (this condition in the future can be improved)
stevep 0:04a9f72bbca7 1520 return Mul2Big3<value_size>(table, ss2.table, result, x1start, x1size, x2start, x2size);
stevep 0:04a9f72bbca7 1521
stevep 0:04a9f72bbca7 1522
stevep 0:04a9f72bbca7 1523 // Karatsuba multiplication
stevep 0:04a9f72bbca7 1524 Mul3Big(ss2, result);
stevep 0:04a9f72bbca7 1525
stevep 0:04a9f72bbca7 1526 TTMATH_LOG("UInt::MulFastestBig")
stevep 0:04a9f72bbca7 1527 }
stevep 0:04a9f72bbca7 1528
stevep 0:04a9f72bbca7 1529
stevep 0:04a9f72bbca7 1530 /*!
stevep 0:04a9f72bbca7 1531 *
stevep 0:04a9f72bbca7 1532 * Division
stevep 0:04a9f72bbca7 1533 *
stevep 0:04a9f72bbca7 1534 *
stevep 0:04a9f72bbca7 1535 */
stevep 0:04a9f72bbca7 1536
stevep 0:04a9f72bbca7 1537 public:
stevep 0:04a9f72bbca7 1538
stevep 0:04a9f72bbca7 1539
stevep 0:04a9f72bbca7 1540 /*!
stevep 0:04a9f72bbca7 1541 division by one unsigned word
stevep 0:04a9f72bbca7 1542
stevep 0:04a9f72bbca7 1543 returns 1 when divisor is zero
stevep 0:04a9f72bbca7 1544 */
stevep 0:04a9f72bbca7 1545 uint DivInt(uint divisor, uint * remainder = 0)
stevep 0:04a9f72bbca7 1546 {
stevep 0:04a9f72bbca7 1547 if( divisor == 0 )
stevep 0:04a9f72bbca7 1548 {
stevep 0:04a9f72bbca7 1549 if( remainder )
stevep 0:04a9f72bbca7 1550 *remainder = 0; // this is for convenience, without it the compiler can report that 'remainder' is uninitialized
stevep 0:04a9f72bbca7 1551
stevep 0:04a9f72bbca7 1552 TTMATH_LOG("UInt::DivInt")
stevep 0:04a9f72bbca7 1553
stevep 0:04a9f72bbca7 1554 return 1;
stevep 0:04a9f72bbca7 1555 }
stevep 0:04a9f72bbca7 1556
stevep 0:04a9f72bbca7 1557 if( divisor == 1 )
stevep 0:04a9f72bbca7 1558 {
stevep 0:04a9f72bbca7 1559 if( remainder )
stevep 0:04a9f72bbca7 1560 *remainder = 0;
stevep 0:04a9f72bbca7 1561
stevep 0:04a9f72bbca7 1562 TTMATH_LOG("UInt::DivInt")
stevep 0:04a9f72bbca7 1563
stevep 0:04a9f72bbca7 1564 return 0;
stevep 0:04a9f72bbca7 1565 }
stevep 0:04a9f72bbca7 1566
stevep 0:04a9f72bbca7 1567 UInt<value_size> dividend(*this);
stevep 0:04a9f72bbca7 1568 SetZero();
stevep 0:04a9f72bbca7 1569
stevep 0:04a9f72bbca7 1570 sint i; // i must be with a sign
stevep 0:04a9f72bbca7 1571 uint r = 0;
stevep 0:04a9f72bbca7 1572
stevep 0:04a9f72bbca7 1573 // we're looking for the last word in ss1
stevep 0:04a9f72bbca7 1574 for(i=value_size-1 ; i>0 && dividend.table[i]==0 ; --i);
stevep 0:04a9f72bbca7 1575
stevep 0:04a9f72bbca7 1576 for( ; i>=0 ; --i)
stevep 0:04a9f72bbca7 1577 DivTwoWords(r, dividend.table[i], divisor, &table[i], &r);
stevep 0:04a9f72bbca7 1578
stevep 0:04a9f72bbca7 1579 if( remainder )
stevep 0:04a9f72bbca7 1580 *remainder = r;
stevep 0:04a9f72bbca7 1581
stevep 0:04a9f72bbca7 1582 TTMATH_LOG("UInt::DivInt")
stevep 0:04a9f72bbca7 1583
stevep 0:04a9f72bbca7 1584 return 0;
stevep 0:04a9f72bbca7 1585 }
stevep 0:04a9f72bbca7 1586
stevep 0:04a9f72bbca7 1587 uint DivInt(uint divisor, uint & remainder)
stevep 0:04a9f72bbca7 1588 {
stevep 0:04a9f72bbca7 1589 return DivInt(divisor, &remainder);
stevep 0:04a9f72bbca7 1590 }
stevep 0:04a9f72bbca7 1591
stevep 0:04a9f72bbca7 1592
stevep 0:04a9f72bbca7 1593
stevep 0:04a9f72bbca7 1594 /*!
stevep 0:04a9f72bbca7 1595 division this = this / ss2
stevep 0:04a9f72bbca7 1596
stevep 0:04a9f72bbca7 1597 return values:
stevep 0:04a9f72bbca7 1598 0 - ok
stevep 0:04a9f72bbca7 1599 1 - division by zero
stevep 0:04a9f72bbca7 1600 'this' will be the quotient
stevep 0:04a9f72bbca7 1601 'remainder' - remainder
stevep 0:04a9f72bbca7 1602 */
stevep 0:04a9f72bbca7 1603 uint Div( const UInt<value_size> & divisor,
stevep 0:04a9f72bbca7 1604 UInt<value_size> * remainder = 0,
stevep 0:04a9f72bbca7 1605 uint algorithm = 3)
stevep 0:04a9f72bbca7 1606 {
stevep 0:04a9f72bbca7 1607 switch( algorithm )
stevep 0:04a9f72bbca7 1608 {
stevep 0:04a9f72bbca7 1609 case 1:
stevep 0:04a9f72bbca7 1610 return Div1(divisor, remainder);
stevep 0:04a9f72bbca7 1611
stevep 0:04a9f72bbca7 1612 case 2:
stevep 0:04a9f72bbca7 1613 return Div2(divisor, remainder);
stevep 0:04a9f72bbca7 1614
stevep 0:04a9f72bbca7 1615 case 3:
stevep 0:04a9f72bbca7 1616 default:
stevep 0:04a9f72bbca7 1617 return Div3(divisor, remainder);
stevep 0:04a9f72bbca7 1618 }
stevep 0:04a9f72bbca7 1619 }
stevep 0:04a9f72bbca7 1620
stevep 0:04a9f72bbca7 1621 uint Div(const UInt<value_size> & divisor, UInt<value_size> & remainder, uint algorithm = 3)
stevep 0:04a9f72bbca7 1622 {
stevep 0:04a9f72bbca7 1623 return Div(divisor, &remainder, algorithm);
stevep 0:04a9f72bbca7 1624 }
stevep 0:04a9f72bbca7 1625
stevep 0:04a9f72bbca7 1626
stevep 0:04a9f72bbca7 1627
stevep 0:04a9f72bbca7 1628 private:
stevep 0:04a9f72bbca7 1629
stevep 0:04a9f72bbca7 1630 /*!
stevep 0:04a9f72bbca7 1631 return values:
stevep 0:04a9f72bbca7 1632 0 - none has to be done
stevep 0:04a9f72bbca7 1633 1 - division by zero
stevep 0:04a9f72bbca7 1634 2 - division should be made
stevep 0:04a9f72bbca7 1635 */
stevep 0:04a9f72bbca7 1636 uint Div_StandardTest( const UInt<value_size> & v,
stevep 0:04a9f72bbca7 1637 uint & m, uint & n,
stevep 0:04a9f72bbca7 1638 UInt<value_size> * remainder = 0)
stevep 0:04a9f72bbca7 1639 {
stevep 0:04a9f72bbca7 1640 switch( Div_CalculatingSize(v, m, n) )
stevep 0:04a9f72bbca7 1641 {
stevep 0:04a9f72bbca7 1642 case 4: // 'this' is equal v
stevep 0:04a9f72bbca7 1643 if( remainder )
stevep 0:04a9f72bbca7 1644 remainder->SetZero();
stevep 0:04a9f72bbca7 1645
stevep 0:04a9f72bbca7 1646 SetOne();
stevep 0:04a9f72bbca7 1647 TTMATH_LOG("UInt::Div_StandardTest")
stevep 0:04a9f72bbca7 1648 return 0;
stevep 0:04a9f72bbca7 1649
stevep 0:04a9f72bbca7 1650 case 3: // 'this' is smaller than v
stevep 0:04a9f72bbca7 1651 if( remainder )
stevep 0:04a9f72bbca7 1652 *remainder = *this;
stevep 0:04a9f72bbca7 1653
stevep 0:04a9f72bbca7 1654 SetZero();
stevep 0:04a9f72bbca7 1655 TTMATH_LOG("UInt::Div_StandardTest")
stevep 0:04a9f72bbca7 1656 return 0;
stevep 0:04a9f72bbca7 1657
stevep 0:04a9f72bbca7 1658 case 2: // 'this' is zero
stevep 0:04a9f72bbca7 1659 if( remainder )
stevep 0:04a9f72bbca7 1660 remainder->SetZero();
stevep 0:04a9f72bbca7 1661
stevep 0:04a9f72bbca7 1662 SetZero();
stevep 0:04a9f72bbca7 1663 TTMATH_LOG("UInt::Div_StandardTest")
stevep 0:04a9f72bbca7 1664 return 0;
stevep 0:04a9f72bbca7 1665
stevep 0:04a9f72bbca7 1666 case 1: // v is zero
stevep 0:04a9f72bbca7 1667 TTMATH_LOG("UInt::Div_StandardTest")
stevep 0:04a9f72bbca7 1668 return 1;
stevep 0:04a9f72bbca7 1669 }
stevep 0:04a9f72bbca7 1670
stevep 0:04a9f72bbca7 1671 TTMATH_LOG("UInt::Div_StandardTest")
stevep 0:04a9f72bbca7 1672
stevep 0:04a9f72bbca7 1673 return 2;
stevep 0:04a9f72bbca7 1674 }
stevep 0:04a9f72bbca7 1675
stevep 0:04a9f72bbca7 1676
stevep 0:04a9f72bbca7 1677
stevep 0:04a9f72bbca7 1678 /*!
stevep 0:04a9f72bbca7 1679 return values:
stevep 0:04a9f72bbca7 1680 0 - ok
stevep 0:04a9f72bbca7 1681 'm' - is the index (from 0) of last non-zero word in table ('this')
stevep 0:04a9f72bbca7 1682 'n' - is the index (from 0) of last non-zero word in v.table
stevep 0:04a9f72bbca7 1683 1 - v is zero
stevep 0:04a9f72bbca7 1684 2 - 'this' is zero
stevep 0:04a9f72bbca7 1685 3 - 'this' is smaller than v
stevep 0:04a9f72bbca7 1686 4 - 'this' is equal v
stevep 0:04a9f72bbca7 1687
stevep 0:04a9f72bbca7 1688 if the return value is different than zero the 'm' and 'n' are undefined
stevep 0:04a9f72bbca7 1689 */
stevep 0:04a9f72bbca7 1690 uint Div_CalculatingSize(const UInt<value_size> & v, uint & m, uint & n)
stevep 0:04a9f72bbca7 1691 {
stevep 0:04a9f72bbca7 1692 m = n = value_size-1;
stevep 0:04a9f72bbca7 1693
stevep 0:04a9f72bbca7 1694 for( ; n!=0 && v.table[n]==0 ; --n);
stevep 0:04a9f72bbca7 1695
stevep 0:04a9f72bbca7 1696 if( n==0 && v.table[n]==0 )
stevep 0:04a9f72bbca7 1697 return 1;
stevep 0:04a9f72bbca7 1698
stevep 0:04a9f72bbca7 1699 for( ; m!=0 && table[m]==0 ; --m);
stevep 0:04a9f72bbca7 1700
stevep 0:04a9f72bbca7 1701 if( m==0 && table[m]==0 )
stevep 0:04a9f72bbca7 1702 return 2;
stevep 0:04a9f72bbca7 1703
stevep 0:04a9f72bbca7 1704 if( m < n )
stevep 0:04a9f72bbca7 1705 return 3;
stevep 0:04a9f72bbca7 1706 else
stevep 0:04a9f72bbca7 1707 if( m == n )
stevep 0:04a9f72bbca7 1708 {
stevep 0:04a9f72bbca7 1709 uint i;
stevep 0:04a9f72bbca7 1710 for(i = n ; i!=0 && table[i]==v.table[i] ; --i);
stevep 0:04a9f72bbca7 1711
stevep 0:04a9f72bbca7 1712 if( table[i] < v.table[i] )
stevep 0:04a9f72bbca7 1713 return 3;
stevep 0:04a9f72bbca7 1714 else
stevep 0:04a9f72bbca7 1715 if (table[i] == v.table[i] )
stevep 0:04a9f72bbca7 1716 return 4;
stevep 0:04a9f72bbca7 1717 }
stevep 0:04a9f72bbca7 1718
stevep 0:04a9f72bbca7 1719 return 0;
stevep 0:04a9f72bbca7 1720 }
stevep 0:04a9f72bbca7 1721
stevep 0:04a9f72bbca7 1722
stevep 0:04a9f72bbca7 1723 public:
stevep 0:04a9f72bbca7 1724
stevep 0:04a9f72bbca7 1725 /*!
stevep 0:04a9f72bbca7 1726 the first division algorithm
stevep 0:04a9f72bbca7 1727 radix 2
stevep 0:04a9f72bbca7 1728 */
stevep 0:04a9f72bbca7 1729 uint Div1(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
stevep 0:04a9f72bbca7 1730 {
stevep 0:04a9f72bbca7 1731 uint m,n, test;
stevep 0:04a9f72bbca7 1732
stevep 0:04a9f72bbca7 1733 test = Div_StandardTest(divisor, m, n, remainder);
stevep 0:04a9f72bbca7 1734 if( test < 2 )
stevep 0:04a9f72bbca7 1735 return test;
stevep 0:04a9f72bbca7 1736
stevep 0:04a9f72bbca7 1737 if( !remainder )
stevep 0:04a9f72bbca7 1738 {
stevep 0:04a9f72bbca7 1739 UInt<value_size> rem;
stevep 0:04a9f72bbca7 1740
stevep 0:04a9f72bbca7 1741 return Div1_Calculate(divisor, rem);
stevep 0:04a9f72bbca7 1742 }
stevep 0:04a9f72bbca7 1743
stevep 0:04a9f72bbca7 1744 return Div1_Calculate(divisor, *remainder);
stevep 0:04a9f72bbca7 1745 }
stevep 0:04a9f72bbca7 1746
stevep 0:04a9f72bbca7 1747
stevep 0:04a9f72bbca7 1748 /*!
stevep 0:04a9f72bbca7 1749 the first division algorithm
stevep 0:04a9f72bbca7 1750 radix 2
stevep 0:04a9f72bbca7 1751 */
stevep 0:04a9f72bbca7 1752 uint Div1(const UInt<value_size> & divisor, UInt<value_size> & remainder)
stevep 0:04a9f72bbca7 1753 {
stevep 0:04a9f72bbca7 1754 return Div1(divisor, &remainder);
stevep 0:04a9f72bbca7 1755 }
stevep 0:04a9f72bbca7 1756
stevep 0:04a9f72bbca7 1757
stevep 0:04a9f72bbca7 1758 private:
stevep 0:04a9f72bbca7 1759
stevep 0:04a9f72bbca7 1760 uint Div1_Calculate(const UInt<value_size> & divisor, UInt<value_size> & rest)
stevep 0:04a9f72bbca7 1761 {
stevep 0:04a9f72bbca7 1762 if( this == &divisor )
stevep 0:04a9f72bbca7 1763 {
stevep 0:04a9f72bbca7 1764 UInt<value_size> divisor_copy(divisor);
stevep 0:04a9f72bbca7 1765 return Div1_CalculateRef(divisor_copy, rest);
stevep 0:04a9f72bbca7 1766 }
stevep 0:04a9f72bbca7 1767 else
stevep 0:04a9f72bbca7 1768 {
stevep 0:04a9f72bbca7 1769 return Div1_CalculateRef(divisor, rest);
stevep 0:04a9f72bbca7 1770 }
stevep 0:04a9f72bbca7 1771 }
stevep 0:04a9f72bbca7 1772
stevep 0:04a9f72bbca7 1773
stevep 0:04a9f72bbca7 1774 uint Div1_CalculateRef(const UInt<value_size> & divisor, UInt<value_size> & rest)
stevep 0:04a9f72bbca7 1775 {
stevep 0:04a9f72bbca7 1776 TTMATH_REFERENCE_ASSERT( divisor )
stevep 0:04a9f72bbca7 1777
stevep 0:04a9f72bbca7 1778 sint loop;
stevep 0:04a9f72bbca7 1779 sint c;
stevep 0:04a9f72bbca7 1780
stevep 0:04a9f72bbca7 1781 rest.SetZero();
stevep 0:04a9f72bbca7 1782 loop = value_size * TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 1783 c = 0;
stevep 0:04a9f72bbca7 1784
stevep 0:04a9f72bbca7 1785
stevep 0:04a9f72bbca7 1786 div_a:
stevep 0:04a9f72bbca7 1787 c = Rcl(1, c);
stevep 0:04a9f72bbca7 1788 c = rest.Add(rest,c);
stevep 0:04a9f72bbca7 1789 c = rest.Sub(divisor,c);
stevep 0:04a9f72bbca7 1790
stevep 0:04a9f72bbca7 1791 c = !c;
stevep 0:04a9f72bbca7 1792
stevep 0:04a9f72bbca7 1793 if(!c)
stevep 0:04a9f72bbca7 1794 goto div_d;
stevep 0:04a9f72bbca7 1795
stevep 0:04a9f72bbca7 1796
stevep 0:04a9f72bbca7 1797 div_b:
stevep 0:04a9f72bbca7 1798 --loop;
stevep 0:04a9f72bbca7 1799 if(loop)
stevep 0:04a9f72bbca7 1800 goto div_a;
stevep 0:04a9f72bbca7 1801
stevep 0:04a9f72bbca7 1802 c = Rcl(1, c);
stevep 0:04a9f72bbca7 1803 TTMATH_LOG("UInt::Div1_Calculate")
stevep 0:04a9f72bbca7 1804 return 0;
stevep 0:04a9f72bbca7 1805
stevep 0:04a9f72bbca7 1806
stevep 0:04a9f72bbca7 1807 div_c:
stevep 0:04a9f72bbca7 1808 c = Rcl(1, c);
stevep 0:04a9f72bbca7 1809 c = rest.Add(rest,c);
stevep 0:04a9f72bbca7 1810 c = rest.Add(divisor);
stevep 0:04a9f72bbca7 1811
stevep 0:04a9f72bbca7 1812 if(c)
stevep 0:04a9f72bbca7 1813 goto div_b;
stevep 0:04a9f72bbca7 1814
stevep 0:04a9f72bbca7 1815
stevep 0:04a9f72bbca7 1816 div_d:
stevep 0:04a9f72bbca7 1817 --loop;
stevep 0:04a9f72bbca7 1818 if(loop)
stevep 0:04a9f72bbca7 1819 goto div_c;
stevep 0:04a9f72bbca7 1820
stevep 0:04a9f72bbca7 1821 c = Rcl(1, c);
stevep 0:04a9f72bbca7 1822 c = rest.Add(divisor);
stevep 0:04a9f72bbca7 1823
stevep 0:04a9f72bbca7 1824 TTMATH_LOG("UInt::Div1_Calculate")
stevep 0:04a9f72bbca7 1825
stevep 0:04a9f72bbca7 1826 return 0;
stevep 0:04a9f72bbca7 1827 }
stevep 0:04a9f72bbca7 1828
stevep 0:04a9f72bbca7 1829
stevep 0:04a9f72bbca7 1830 public:
stevep 0:04a9f72bbca7 1831
stevep 0:04a9f72bbca7 1832 /*!
stevep 0:04a9f72bbca7 1833 the second division algorithm
stevep 0:04a9f72bbca7 1834
stevep 0:04a9f72bbca7 1835 return values:
stevep 0:04a9f72bbca7 1836 0 - ok
stevep 0:04a9f72bbca7 1837 1 - division by zero
stevep 0:04a9f72bbca7 1838 */
stevep 0:04a9f72bbca7 1839 uint Div2(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
stevep 0:04a9f72bbca7 1840 {
stevep 0:04a9f72bbca7 1841 if( this == &divisor )
stevep 0:04a9f72bbca7 1842 {
stevep 0:04a9f72bbca7 1843 UInt<value_size> divisor_copy(divisor);
stevep 0:04a9f72bbca7 1844 return Div2Ref(divisor_copy, remainder);
stevep 0:04a9f72bbca7 1845 }
stevep 0:04a9f72bbca7 1846 else
stevep 0:04a9f72bbca7 1847 {
stevep 0:04a9f72bbca7 1848 return Div2Ref(divisor, remainder);
stevep 0:04a9f72bbca7 1849 }
stevep 0:04a9f72bbca7 1850 }
stevep 0:04a9f72bbca7 1851
stevep 0:04a9f72bbca7 1852
stevep 0:04a9f72bbca7 1853 /*!
stevep 0:04a9f72bbca7 1854 the second division algorithm
stevep 0:04a9f72bbca7 1855
stevep 0:04a9f72bbca7 1856 return values:
stevep 0:04a9f72bbca7 1857 0 - ok
stevep 0:04a9f72bbca7 1858 1 - division by zero
stevep 0:04a9f72bbca7 1859 */
stevep 0:04a9f72bbca7 1860 uint Div2(const UInt<value_size> & divisor, UInt<value_size> & remainder)
stevep 0:04a9f72bbca7 1861 {
stevep 0:04a9f72bbca7 1862 return Div2(divisor, &remainder);
stevep 0:04a9f72bbca7 1863 }
stevep 0:04a9f72bbca7 1864
stevep 0:04a9f72bbca7 1865
stevep 0:04a9f72bbca7 1866 private:
stevep 0:04a9f72bbca7 1867
stevep 0:04a9f72bbca7 1868 /*!
stevep 0:04a9f72bbca7 1869 the second division algorithm
stevep 0:04a9f72bbca7 1870
stevep 0:04a9f72bbca7 1871 return values:
stevep 0:04a9f72bbca7 1872 0 - ok
stevep 0:04a9f72bbca7 1873 1 - division by zero
stevep 0:04a9f72bbca7 1874 */
stevep 0:04a9f72bbca7 1875 uint Div2Ref(const UInt<value_size> & divisor, UInt<value_size> * remainder = 0)
stevep 0:04a9f72bbca7 1876 {
stevep 0:04a9f72bbca7 1877 uint bits_diff;
stevep 0:04a9f72bbca7 1878 uint status = Div2_Calculate(divisor, remainder, bits_diff);
stevep 0:04a9f72bbca7 1879 if( status < 2 )
stevep 0:04a9f72bbca7 1880 return status;
stevep 0:04a9f72bbca7 1881
stevep 0:04a9f72bbca7 1882 if( CmpBiggerEqual(divisor) )
stevep 0:04a9f72bbca7 1883 {
stevep 0:04a9f72bbca7 1884 Div2(divisor, remainder);
stevep 0:04a9f72bbca7 1885 SetBit(bits_diff);
stevep 0:04a9f72bbca7 1886 }
stevep 0:04a9f72bbca7 1887 else
stevep 0:04a9f72bbca7 1888 {
stevep 0:04a9f72bbca7 1889 if( remainder )
stevep 0:04a9f72bbca7 1890 *remainder = *this;
stevep 0:04a9f72bbca7 1891
stevep 0:04a9f72bbca7 1892 SetZero();
stevep 0:04a9f72bbca7 1893 SetBit(bits_diff);
stevep 0:04a9f72bbca7 1894 }
stevep 0:04a9f72bbca7 1895
stevep 0:04a9f72bbca7 1896 TTMATH_LOG("UInt::Div2")
stevep 0:04a9f72bbca7 1897
stevep 0:04a9f72bbca7 1898 return 0;
stevep 0:04a9f72bbca7 1899 }
stevep 0:04a9f72bbca7 1900
stevep 0:04a9f72bbca7 1901
stevep 0:04a9f72bbca7 1902 /*!
stevep 0:04a9f72bbca7 1903 return values:
stevep 0:04a9f72bbca7 1904 0 - we've calculated the division
stevep 0:04a9f72bbca7 1905 1 - division by zero
stevep 0:04a9f72bbca7 1906 2 - we have to still calculate
stevep 0:04a9f72bbca7 1907
stevep 0:04a9f72bbca7 1908 */
stevep 0:04a9f72bbca7 1909 uint Div2_Calculate(const UInt<value_size> & divisor, UInt<value_size> * remainder,
stevep 0:04a9f72bbca7 1910 uint & bits_diff)
stevep 0:04a9f72bbca7 1911 {
stevep 0:04a9f72bbca7 1912 uint table_id, index;
stevep 0:04a9f72bbca7 1913 uint divisor_table_id, divisor_index;
stevep 0:04a9f72bbca7 1914
stevep 0:04a9f72bbca7 1915 uint status = Div2_FindLeadingBitsAndCheck( divisor, remainder,
stevep 0:04a9f72bbca7 1916 table_id, index,
stevep 0:04a9f72bbca7 1917 divisor_table_id, divisor_index);
stevep 0:04a9f72bbca7 1918
stevep 0:04a9f72bbca7 1919 if( status < 2 )
stevep 0:04a9f72bbca7 1920 {
stevep 0:04a9f72bbca7 1921 TTMATH_LOG("UInt::Div2_Calculate")
stevep 0:04a9f72bbca7 1922 return status;
stevep 0:04a9f72bbca7 1923 }
stevep 0:04a9f72bbca7 1924
stevep 0:04a9f72bbca7 1925 // here we know that 'this' is greater than divisor
stevep 0:04a9f72bbca7 1926 // then 'index' is greater or equal 'divisor_index'
stevep 0:04a9f72bbca7 1927 bits_diff = index - divisor_index;
stevep 0:04a9f72bbca7 1928
stevep 0:04a9f72bbca7 1929 UInt<value_size> divisor_copy(divisor);
stevep 0:04a9f72bbca7 1930 divisor_copy.Rcl(bits_diff, 0);
stevep 0:04a9f72bbca7 1931
stevep 0:04a9f72bbca7 1932 if( CmpSmaller(divisor_copy, table_id) )
stevep 0:04a9f72bbca7 1933 {
stevep 0:04a9f72bbca7 1934 divisor_copy.Rcr(1);
stevep 0:04a9f72bbca7 1935 --bits_diff;
stevep 0:04a9f72bbca7 1936 }
stevep 0:04a9f72bbca7 1937
stevep 0:04a9f72bbca7 1938 Sub(divisor_copy, 0);
stevep 0:04a9f72bbca7 1939
stevep 0:04a9f72bbca7 1940 TTMATH_LOG("UInt::Div2_Calculate")
stevep 0:04a9f72bbca7 1941
stevep 0:04a9f72bbca7 1942 return 2;
stevep 0:04a9f72bbca7 1943 }
stevep 0:04a9f72bbca7 1944
stevep 0:04a9f72bbca7 1945
stevep 0:04a9f72bbca7 1946 /*!
stevep 0:04a9f72bbca7 1947 return values:
stevep 0:04a9f72bbca7 1948 0 - we've calculated the division
stevep 0:04a9f72bbca7 1949 1 - division by zero
stevep 0:04a9f72bbca7 1950 2 - we have to still calculate
stevep 0:04a9f72bbca7 1951 */
stevep 0:04a9f72bbca7 1952 uint Div2_FindLeadingBitsAndCheck( const UInt<value_size> & divisor,
stevep 0:04a9f72bbca7 1953 UInt<value_size> * remainder,
stevep 0:04a9f72bbca7 1954 uint & table_id, uint & index,
stevep 0:04a9f72bbca7 1955 uint & divisor_table_id, uint & divisor_index)
stevep 0:04a9f72bbca7 1956 {
stevep 0:04a9f72bbca7 1957 if( !divisor.FindLeadingBit(divisor_table_id, divisor_index) )
stevep 0:04a9f72bbca7 1958 {
stevep 0:04a9f72bbca7 1959 // division by zero
stevep 0:04a9f72bbca7 1960 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
stevep 0:04a9f72bbca7 1961 return 1;
stevep 0:04a9f72bbca7 1962 }
stevep 0:04a9f72bbca7 1963
stevep 0:04a9f72bbca7 1964 if( !FindLeadingBit(table_id, index) )
stevep 0:04a9f72bbca7 1965 {
stevep 0:04a9f72bbca7 1966 // zero is divided by something
stevep 0:04a9f72bbca7 1967
stevep 0:04a9f72bbca7 1968 SetZero();
stevep 0:04a9f72bbca7 1969
stevep 0:04a9f72bbca7 1970 if( remainder )
stevep 0:04a9f72bbca7 1971 remainder->SetZero();
stevep 0:04a9f72bbca7 1972
stevep 0:04a9f72bbca7 1973 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
stevep 0:04a9f72bbca7 1974
stevep 0:04a9f72bbca7 1975 return 0;
stevep 0:04a9f72bbca7 1976 }
stevep 0:04a9f72bbca7 1977
stevep 0:04a9f72bbca7 1978 divisor_index += divisor_table_id * TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 1979 index += table_id * TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 1980
stevep 0:04a9f72bbca7 1981 if( divisor_table_id == 0 )
stevep 0:04a9f72bbca7 1982 {
stevep 0:04a9f72bbca7 1983 // dividor has only one 32-bit word
stevep 0:04a9f72bbca7 1984
stevep 0:04a9f72bbca7 1985 uint r;
stevep 0:04a9f72bbca7 1986 DivInt(divisor.table[0], &r);
stevep 0:04a9f72bbca7 1987
stevep 0:04a9f72bbca7 1988 if( remainder )
stevep 0:04a9f72bbca7 1989 {
stevep 0:04a9f72bbca7 1990 remainder->SetZero();
stevep 0:04a9f72bbca7 1991 remainder->table[0] = r;
stevep 0:04a9f72bbca7 1992 }
stevep 0:04a9f72bbca7 1993
stevep 0:04a9f72bbca7 1994 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
stevep 0:04a9f72bbca7 1995
stevep 0:04a9f72bbca7 1996 return 0;
stevep 0:04a9f72bbca7 1997 }
stevep 0:04a9f72bbca7 1998
stevep 0:04a9f72bbca7 1999
stevep 0:04a9f72bbca7 2000 if( Div2_DivisorGreaterOrEqual( divisor, remainder,
stevep 0:04a9f72bbca7 2001 table_id, index,
stevep 0:04a9f72bbca7 2002 divisor_index) )
stevep 0:04a9f72bbca7 2003 {
stevep 0:04a9f72bbca7 2004 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
stevep 0:04a9f72bbca7 2005 return 0;
stevep 0:04a9f72bbca7 2006 }
stevep 0:04a9f72bbca7 2007
stevep 0:04a9f72bbca7 2008
stevep 0:04a9f72bbca7 2009 TTMATH_LOG("UInt::Div2_FindLeadingBitsAndCheck")
stevep 0:04a9f72bbca7 2010
stevep 0:04a9f72bbca7 2011 return 2;
stevep 0:04a9f72bbca7 2012 }
stevep 0:04a9f72bbca7 2013
stevep 0:04a9f72bbca7 2014
stevep 0:04a9f72bbca7 2015 /*!
stevep 0:04a9f72bbca7 2016 return values:
stevep 0:04a9f72bbca7 2017 true if divisor is equal or greater than 'this'
stevep 0:04a9f72bbca7 2018 */
stevep 0:04a9f72bbca7 2019 bool Div2_DivisorGreaterOrEqual( const UInt<value_size> & divisor,
stevep 0:04a9f72bbca7 2020 UInt<value_size> * remainder,
stevep 0:04a9f72bbca7 2021 uint table_id, uint index,
stevep 0:04a9f72bbca7 2022 uint divisor_index )
stevep 0:04a9f72bbca7 2023 {
stevep 0:04a9f72bbca7 2024 if( divisor_index > index )
stevep 0:04a9f72bbca7 2025 {
stevep 0:04a9f72bbca7 2026 // divisor is greater than this
stevep 0:04a9f72bbca7 2027
stevep 0:04a9f72bbca7 2028 if( remainder )
stevep 0:04a9f72bbca7 2029 *remainder = *this;
stevep 0:04a9f72bbca7 2030
stevep 0:04a9f72bbca7 2031 SetZero();
stevep 0:04a9f72bbca7 2032
stevep 0:04a9f72bbca7 2033 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
stevep 0:04a9f72bbca7 2034
stevep 0:04a9f72bbca7 2035 return true;
stevep 0:04a9f72bbca7 2036 }
stevep 0:04a9f72bbca7 2037
stevep 0:04a9f72bbca7 2038 if( divisor_index == index )
stevep 0:04a9f72bbca7 2039 {
stevep 0:04a9f72bbca7 2040 // table_id == divisor_table_id as well
stevep 0:04a9f72bbca7 2041
stevep 0:04a9f72bbca7 2042 uint i;
stevep 0:04a9f72bbca7 2043 for(i = table_id ; i!=0 && table[i]==divisor.table[i] ; --i);
stevep 0:04a9f72bbca7 2044
stevep 0:04a9f72bbca7 2045 if( table[i] < divisor.table[i] )
stevep 0:04a9f72bbca7 2046 {
stevep 0:04a9f72bbca7 2047 // divisor is greater than 'this'
stevep 0:04a9f72bbca7 2048
stevep 0:04a9f72bbca7 2049 if( remainder )
stevep 0:04a9f72bbca7 2050 *remainder = *this;
stevep 0:04a9f72bbca7 2051
stevep 0:04a9f72bbca7 2052 SetZero();
stevep 0:04a9f72bbca7 2053
stevep 0:04a9f72bbca7 2054 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
stevep 0:04a9f72bbca7 2055
stevep 0:04a9f72bbca7 2056 return true;
stevep 0:04a9f72bbca7 2057 }
stevep 0:04a9f72bbca7 2058 else
stevep 0:04a9f72bbca7 2059 if( table[i] == divisor.table[i] )
stevep 0:04a9f72bbca7 2060 {
stevep 0:04a9f72bbca7 2061 // divisor is equal 'this'
stevep 0:04a9f72bbca7 2062
stevep 0:04a9f72bbca7 2063 if( remainder )
stevep 0:04a9f72bbca7 2064 remainder->SetZero();
stevep 0:04a9f72bbca7 2065
stevep 0:04a9f72bbca7 2066 SetOne();
stevep 0:04a9f72bbca7 2067
stevep 0:04a9f72bbca7 2068 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
stevep 0:04a9f72bbca7 2069
stevep 0:04a9f72bbca7 2070 return true;
stevep 0:04a9f72bbca7 2071 }
stevep 0:04a9f72bbca7 2072 }
stevep 0:04a9f72bbca7 2073
stevep 0:04a9f72bbca7 2074 TTMATH_LOG("UInt::Div2_DivisorGreaterOrEqual")
stevep 0:04a9f72bbca7 2075
stevep 0:04a9f72bbca7 2076 return false;
stevep 0:04a9f72bbca7 2077 }
stevep 0:04a9f72bbca7 2078
stevep 0:04a9f72bbca7 2079
stevep 0:04a9f72bbca7 2080 public:
stevep 0:04a9f72bbca7 2081
stevep 0:04a9f72bbca7 2082 /*!
stevep 0:04a9f72bbca7 2083 the third division algorithm
stevep 0:04a9f72bbca7 2084 */
stevep 0:04a9f72bbca7 2085 uint Div3(const UInt<value_size> & ss2, UInt<value_size> * remainder = 0)
stevep 0:04a9f72bbca7 2086 {
stevep 0:04a9f72bbca7 2087 if( this == &ss2 )
stevep 0:04a9f72bbca7 2088 {
stevep 0:04a9f72bbca7 2089 UInt<value_size> copy_ss2(ss2);
stevep 0:04a9f72bbca7 2090 return Div3Ref(copy_ss2, remainder);
stevep 0:04a9f72bbca7 2091 }
stevep 0:04a9f72bbca7 2092 else
stevep 0:04a9f72bbca7 2093 {
stevep 0:04a9f72bbca7 2094 return Div3Ref(ss2, remainder);
stevep 0:04a9f72bbca7 2095 }
stevep 0:04a9f72bbca7 2096 }
stevep 0:04a9f72bbca7 2097
stevep 0:04a9f72bbca7 2098
stevep 0:04a9f72bbca7 2099 /*!
stevep 0:04a9f72bbca7 2100 the third division algorithm
stevep 0:04a9f72bbca7 2101 */
stevep 0:04a9f72bbca7 2102 uint Div3(const UInt<value_size> & ss2, UInt<value_size> & remainder)
stevep 0:04a9f72bbca7 2103 {
stevep 0:04a9f72bbca7 2104 return Div3(ss2, &remainder);
stevep 0:04a9f72bbca7 2105 }
stevep 0:04a9f72bbca7 2106
stevep 0:04a9f72bbca7 2107
stevep 0:04a9f72bbca7 2108 private:
stevep 0:04a9f72bbca7 2109
stevep 0:04a9f72bbca7 2110 /*!
stevep 0:04a9f72bbca7 2111 the third division algorithm
stevep 0:04a9f72bbca7 2112
stevep 0:04a9f72bbca7 2113 this algorithm is described in the following book:
stevep 0:04a9f72bbca7 2114 "The art of computer programming 2" (4.3.1 page 272)
stevep 0:04a9f72bbca7 2115 Donald E. Knuth
stevep 0:04a9f72bbca7 2116 !! give the description here (from the book)
stevep 0:04a9f72bbca7 2117 */
stevep 0:04a9f72bbca7 2118 uint Div3Ref(const UInt<value_size> & v, UInt<value_size> * remainder = 0)
stevep 0:04a9f72bbca7 2119 {
stevep 0:04a9f72bbca7 2120 uint m,n, test;
stevep 0:04a9f72bbca7 2121
stevep 0:04a9f72bbca7 2122 test = Div_StandardTest(v, m, n, remainder);
stevep 0:04a9f72bbca7 2123 if( test < 2 )
stevep 0:04a9f72bbca7 2124 return test;
stevep 0:04a9f72bbca7 2125
stevep 0:04a9f72bbca7 2126 if( n == 0 )
stevep 0:04a9f72bbca7 2127 {
stevep 0:04a9f72bbca7 2128 uint r;
stevep 0:04a9f72bbca7 2129 DivInt( v.table[0], &r );
stevep 0:04a9f72bbca7 2130
stevep 0:04a9f72bbca7 2131 if( remainder )
stevep 0:04a9f72bbca7 2132 {
stevep 0:04a9f72bbca7 2133 remainder->SetZero();
stevep 0:04a9f72bbca7 2134 remainder->table[0] = r;
stevep 0:04a9f72bbca7 2135 }
stevep 0:04a9f72bbca7 2136
stevep 0:04a9f72bbca7 2137 TTMATH_LOG("UInt::Div3")
stevep 0:04a9f72bbca7 2138
stevep 0:04a9f72bbca7 2139 return 0;
stevep 0:04a9f72bbca7 2140 }
stevep 0:04a9f72bbca7 2141
stevep 0:04a9f72bbca7 2142
stevep 0:04a9f72bbca7 2143 // we can only use the third division algorithm when
stevep 0:04a9f72bbca7 2144 // the divisor is greater or equal 2^32 (has more than one 32-bit word)
stevep 0:04a9f72bbca7 2145 ++m;
stevep 0:04a9f72bbca7 2146 ++n;
stevep 0:04a9f72bbca7 2147 m = m - n;
stevep 0:04a9f72bbca7 2148 Div3_Division(v, remainder, m, n);
stevep 0:04a9f72bbca7 2149
stevep 0:04a9f72bbca7 2150 TTMATH_LOG("UInt::Div3")
stevep 0:04a9f72bbca7 2151
stevep 0:04a9f72bbca7 2152 return 0;
stevep 0:04a9f72bbca7 2153 }
stevep 0:04a9f72bbca7 2154
stevep 0:04a9f72bbca7 2155
stevep 0:04a9f72bbca7 2156
stevep 0:04a9f72bbca7 2157 private:
stevep 0:04a9f72bbca7 2158
stevep 0:04a9f72bbca7 2159
stevep 0:04a9f72bbca7 2160 void Div3_Division(UInt<value_size> v, UInt<value_size> * remainder, uint m, uint n)
stevep 0:04a9f72bbca7 2161 {
stevep 0:04a9f72bbca7 2162 TTMATH_ASSERT( n>=2 )
stevep 0:04a9f72bbca7 2163
stevep 0:04a9f72bbca7 2164 UInt<value_size+1> uu, vv;
stevep 0:04a9f72bbca7 2165 UInt<value_size> q;
stevep 0:04a9f72bbca7 2166 uint d, u_value_size, u0, u1, u2, v1, v0, j=m;
stevep 0:04a9f72bbca7 2167
stevep 0:04a9f72bbca7 2168 u_value_size = Div3_Normalize(v, n, d);
stevep 0:04a9f72bbca7 2169
stevep 0:04a9f72bbca7 2170 if( j+n == value_size )
stevep 0:04a9f72bbca7 2171 u2 = u_value_size;
stevep 0:04a9f72bbca7 2172 else
stevep 0:04a9f72bbca7 2173 u2 = table[j+n];
stevep 0:04a9f72bbca7 2174
stevep 0:04a9f72bbca7 2175 Div3_MakeBiggerV(v, vv);
stevep 0:04a9f72bbca7 2176
stevep 0:04a9f72bbca7 2177 for(uint i = j+1 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2178 q.table[i] = 0;
stevep 0:04a9f72bbca7 2179
stevep 0:04a9f72bbca7 2180 while( true )
stevep 0:04a9f72bbca7 2181 {
stevep 0:04a9f72bbca7 2182 u1 = table[j+n-1];
stevep 0:04a9f72bbca7 2183 u0 = table[j+n-2];
stevep 0:04a9f72bbca7 2184 v1 = v.table[n-1];
stevep 0:04a9f72bbca7 2185 v0 = v.table[n-2];
stevep 0:04a9f72bbca7 2186
stevep 0:04a9f72bbca7 2187 uint qp = Div3_Calculate(u2,u1,u0, v1,v0);
stevep 0:04a9f72bbca7 2188
stevep 0:04a9f72bbca7 2189 Div3_MakeNewU(uu, j, n, u2);
stevep 0:04a9f72bbca7 2190 Div3_MultiplySubtract(uu, vv, qp);
stevep 0:04a9f72bbca7 2191 Div3_CopyNewU(uu, j, n);
stevep 0:04a9f72bbca7 2192
stevep 0:04a9f72bbca7 2193 q.table[j] = qp;
stevep 0:04a9f72bbca7 2194
stevep 0:04a9f72bbca7 2195 // the next loop
stevep 0:04a9f72bbca7 2196 if( j-- == 0 )
stevep 0:04a9f72bbca7 2197 break;
stevep 0:04a9f72bbca7 2198
stevep 0:04a9f72bbca7 2199 u2 = table[j+n];
stevep 0:04a9f72bbca7 2200 }
stevep 0:04a9f72bbca7 2201
stevep 0:04a9f72bbca7 2202 if( remainder )
stevep 0:04a9f72bbca7 2203 Div3_Unnormalize(remainder, n, d);
stevep 0:04a9f72bbca7 2204
stevep 0:04a9f72bbca7 2205 *this = q;
stevep 0:04a9f72bbca7 2206
stevep 0:04a9f72bbca7 2207 TTMATH_LOG("UInt::Div3_Division")
stevep 0:04a9f72bbca7 2208 }
stevep 0:04a9f72bbca7 2209
stevep 0:04a9f72bbca7 2210
stevep 0:04a9f72bbca7 2211 void Div3_MakeNewU(UInt<value_size+1> & uu, uint j, uint n, uint u_max)
stevep 0:04a9f72bbca7 2212 {
stevep 0:04a9f72bbca7 2213 uint i;
stevep 0:04a9f72bbca7 2214
stevep 0:04a9f72bbca7 2215 for(i=0 ; i<n ; ++i, ++j)
stevep 0:04a9f72bbca7 2216 uu.table[i] = table[j];
stevep 0:04a9f72bbca7 2217
stevep 0:04a9f72bbca7 2218 // 'n' is from <1..value_size> so and 'i' is from <0..value_size>
stevep 0:04a9f72bbca7 2219 // then table[i] is always correct (look at the declaration of 'uu')
stevep 0:04a9f72bbca7 2220 uu.table[i] = u_max;
stevep 0:04a9f72bbca7 2221
stevep 0:04a9f72bbca7 2222 for( ++i ; i<value_size+1 ; ++i)
stevep 0:04a9f72bbca7 2223 uu.table[i] = 0;
stevep 0:04a9f72bbca7 2224
stevep 0:04a9f72bbca7 2225 TTMATH_LOG("UInt::Div3_MakeNewU")
stevep 0:04a9f72bbca7 2226 }
stevep 0:04a9f72bbca7 2227
stevep 0:04a9f72bbca7 2228
stevep 0:04a9f72bbca7 2229 void Div3_CopyNewU(const UInt<value_size+1> & uu, uint j, uint n)
stevep 0:04a9f72bbca7 2230 {
stevep 0:04a9f72bbca7 2231 uint i;
stevep 0:04a9f72bbca7 2232
stevep 0:04a9f72bbca7 2233 for(i=0 ; i<n ; ++i)
stevep 0:04a9f72bbca7 2234 table[i+j] = uu.table[i];
stevep 0:04a9f72bbca7 2235
stevep 0:04a9f72bbca7 2236 if( i+j < value_size )
stevep 0:04a9f72bbca7 2237 table[i+j] = uu.table[i];
stevep 0:04a9f72bbca7 2238
stevep 0:04a9f72bbca7 2239 TTMATH_LOG("UInt::Div3_CopyNewU")
stevep 0:04a9f72bbca7 2240 }
stevep 0:04a9f72bbca7 2241
stevep 0:04a9f72bbca7 2242
stevep 0:04a9f72bbca7 2243 /*!
stevep 0:04a9f72bbca7 2244 we're making the new 'vv'
stevep 0:04a9f72bbca7 2245 the value is actually the same but the 'table' is bigger (value_size+1)
stevep 0:04a9f72bbca7 2246 */
stevep 0:04a9f72bbca7 2247 void Div3_MakeBiggerV(const UInt<value_size> & v, UInt<value_size+1> & vv)
stevep 0:04a9f72bbca7 2248 {
stevep 0:04a9f72bbca7 2249 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2250 vv.table[i] = v.table[i];
stevep 0:04a9f72bbca7 2251
stevep 0:04a9f72bbca7 2252 vv.table[value_size] = 0;
stevep 0:04a9f72bbca7 2253
stevep 0:04a9f72bbca7 2254 TTMATH_LOG("UInt::Div3_MakeBiggerV")
stevep 0:04a9f72bbca7 2255 }
stevep 0:04a9f72bbca7 2256
stevep 0:04a9f72bbca7 2257
stevep 0:04a9f72bbca7 2258 /*!
stevep 0:04a9f72bbca7 2259 we're moving all bits from 'v' into the left side of the n-1 word
stevep 0:04a9f72bbca7 2260 (the highest bit at v.table[n-1] will be equal one,
stevep 0:04a9f72bbca7 2261 the bits from 'this' we're moving the same times as 'v')
stevep 0:04a9f72bbca7 2262
stevep 0:04a9f72bbca7 2263 return values:
stevep 0:04a9f72bbca7 2264 d - how many times we've moved
stevep 0:04a9f72bbca7 2265 return - the next-left value from 'this' (that after table[value_size-1])
stevep 0:04a9f72bbca7 2266 */
stevep 0:04a9f72bbca7 2267 uint Div3_Normalize(UInt<value_size> & v, uint n, uint & d)
stevep 0:04a9f72bbca7 2268 {
stevep 0:04a9f72bbca7 2269 // v.table[n-1] is != 0
stevep 0:04a9f72bbca7 2270
stevep 0:04a9f72bbca7 2271 uint bit = (uint)FindLeadingBitInWord(v.table[n-1]);
stevep 0:04a9f72bbca7 2272 uint move = (TTMATH_BITS_PER_UINT - bit - 1);
stevep 0:04a9f72bbca7 2273 uint res = table[value_size-1];
stevep 0:04a9f72bbca7 2274 d = move;
stevep 0:04a9f72bbca7 2275
stevep 0:04a9f72bbca7 2276 if( move > 0 )
stevep 0:04a9f72bbca7 2277 {
stevep 0:04a9f72bbca7 2278 v.Rcl(move, 0);
stevep 0:04a9f72bbca7 2279 Rcl(move, 0);
stevep 0:04a9f72bbca7 2280 res = res >> (bit + 1);
stevep 0:04a9f72bbca7 2281 }
stevep 0:04a9f72bbca7 2282 else
stevep 0:04a9f72bbca7 2283 {
stevep 0:04a9f72bbca7 2284 res = 0;
stevep 0:04a9f72bbca7 2285 }
stevep 0:04a9f72bbca7 2286
stevep 0:04a9f72bbca7 2287 TTMATH_LOG("UInt::Div3_Normalize")
stevep 0:04a9f72bbca7 2288
stevep 0:04a9f72bbca7 2289 return res;
stevep 0:04a9f72bbca7 2290 }
stevep 0:04a9f72bbca7 2291
stevep 0:04a9f72bbca7 2292
stevep 0:04a9f72bbca7 2293 void Div3_Unnormalize(UInt<value_size> * remainder, uint n, uint d)
stevep 0:04a9f72bbca7 2294 {
stevep 0:04a9f72bbca7 2295 for(uint i=n ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2296 table[i] = 0;
stevep 0:04a9f72bbca7 2297
stevep 0:04a9f72bbca7 2298 Rcr(d,0);
stevep 0:04a9f72bbca7 2299
stevep 0:04a9f72bbca7 2300 *remainder = *this;
stevep 0:04a9f72bbca7 2301
stevep 0:04a9f72bbca7 2302 TTMATH_LOG("UInt::Div3_Unnormalize")
stevep 0:04a9f72bbca7 2303 }
stevep 0:04a9f72bbca7 2304
stevep 0:04a9f72bbca7 2305
stevep 0:04a9f72bbca7 2306 uint Div3_Calculate(uint u2, uint u1, uint u0, uint v1, uint v0)
stevep 0:04a9f72bbca7 2307 {
stevep 0:04a9f72bbca7 2308 UInt<2> u_temp;
stevep 0:04a9f72bbca7 2309 uint rp;
stevep 0:04a9f72bbca7 2310 bool next_test;
stevep 0:04a9f72bbca7 2311
stevep 0:04a9f72bbca7 2312 TTMATH_ASSERT( v1 != 0 )
stevep 0:04a9f72bbca7 2313
stevep 0:04a9f72bbca7 2314 u_temp.table[1] = u2;
stevep 0:04a9f72bbca7 2315 u_temp.table[0] = u1;
stevep 0:04a9f72bbca7 2316 u_temp.DivInt(v1, &rp);
stevep 0:04a9f72bbca7 2317
stevep 0:04a9f72bbca7 2318 TTMATH_ASSERT( u_temp.table[1]==0 || u_temp.table[1]==1 )
stevep 0:04a9f72bbca7 2319
stevep 0:04a9f72bbca7 2320 do
stevep 0:04a9f72bbca7 2321 {
stevep 0:04a9f72bbca7 2322 bool decrease = false;
stevep 0:04a9f72bbca7 2323
stevep 0:04a9f72bbca7 2324 if( u_temp.table[1] == 1 )
stevep 0:04a9f72bbca7 2325 decrease = true;
stevep 0:04a9f72bbca7 2326 else
stevep 0:04a9f72bbca7 2327 {
stevep 0:04a9f72bbca7 2328 UInt<2> temp1, temp2;
stevep 0:04a9f72bbca7 2329
stevep 0:04a9f72bbca7 2330 UInt<2>::MulTwoWords(u_temp.table[0], v0, temp1.table+1, temp1.table);
stevep 0:04a9f72bbca7 2331 temp2.table[1] = rp;
stevep 0:04a9f72bbca7 2332 temp2.table[0] = u0;
stevep 0:04a9f72bbca7 2333
stevep 0:04a9f72bbca7 2334 if( temp1 > temp2 )
stevep 0:04a9f72bbca7 2335 decrease = true;
stevep 0:04a9f72bbca7 2336 }
stevep 0:04a9f72bbca7 2337
stevep 0:04a9f72bbca7 2338 next_test = false;
stevep 0:04a9f72bbca7 2339
stevep 0:04a9f72bbca7 2340 if( decrease )
stevep 0:04a9f72bbca7 2341 {
stevep 0:04a9f72bbca7 2342 u_temp.SubOne();
stevep 0:04a9f72bbca7 2343
stevep 0:04a9f72bbca7 2344 rp += v1;
stevep 0:04a9f72bbca7 2345
stevep 0:04a9f72bbca7 2346 if( rp >= v1 ) // it means that there wasn't a carry (r<b from the book)
stevep 0:04a9f72bbca7 2347 next_test = true;
stevep 0:04a9f72bbca7 2348 }
stevep 0:04a9f72bbca7 2349 }
stevep 0:04a9f72bbca7 2350 while( next_test );
stevep 0:04a9f72bbca7 2351
stevep 0:04a9f72bbca7 2352 TTMATH_LOG("UInt::Div3_Calculate")
stevep 0:04a9f72bbca7 2353
stevep 0:04a9f72bbca7 2354 return u_temp.table[0];
stevep 0:04a9f72bbca7 2355 }
stevep 0:04a9f72bbca7 2356
stevep 0:04a9f72bbca7 2357
stevep 0:04a9f72bbca7 2358
stevep 0:04a9f72bbca7 2359 void Div3_MultiplySubtract( UInt<value_size+1> & uu,
stevep 0:04a9f72bbca7 2360 const UInt<value_size+1> & vv, uint & qp)
stevep 0:04a9f72bbca7 2361 {
stevep 0:04a9f72bbca7 2362 // D4 (in the book)
stevep 0:04a9f72bbca7 2363
stevep 0:04a9f72bbca7 2364 UInt<value_size+1> vv_temp(vv);
stevep 0:04a9f72bbca7 2365 vv_temp.MulInt(qp);
stevep 0:04a9f72bbca7 2366
stevep 0:04a9f72bbca7 2367 if( uu.Sub(vv_temp) )
stevep 0:04a9f72bbca7 2368 {
stevep 0:04a9f72bbca7 2369 // there was a carry
stevep 0:04a9f72bbca7 2370
stevep 0:04a9f72bbca7 2371 //
stevep 0:04a9f72bbca7 2372 // !!! this part of code was not tested
stevep 0:04a9f72bbca7 2373 //
stevep 0:04a9f72bbca7 2374
stevep 0:04a9f72bbca7 2375 --qp;
stevep 0:04a9f72bbca7 2376 uu.Add(vv);
stevep 0:04a9f72bbca7 2377
stevep 0:04a9f72bbca7 2378 // can be a carry from this additions but it should be ignored
stevep 0:04a9f72bbca7 2379 // because it cancels with the borrow from uu.Sub(vv_temp)
stevep 0:04a9f72bbca7 2380 }
stevep 0:04a9f72bbca7 2381
stevep 0:04a9f72bbca7 2382 TTMATH_LOG("UInt::Div3_MultiplySubtract")
stevep 0:04a9f72bbca7 2383 }
stevep 0:04a9f72bbca7 2384
stevep 0:04a9f72bbca7 2385
stevep 0:04a9f72bbca7 2386
stevep 0:04a9f72bbca7 2387
stevep 0:04a9f72bbca7 2388
stevep 0:04a9f72bbca7 2389
stevep 0:04a9f72bbca7 2390 public:
stevep 0:04a9f72bbca7 2391
stevep 0:04a9f72bbca7 2392
stevep 0:04a9f72bbca7 2393 /*!
stevep 0:04a9f72bbca7 2394 power this = this ^ pow
stevep 0:04a9f72bbca7 2395 binary algorithm (r-to-l)
stevep 0:04a9f72bbca7 2396
stevep 0:04a9f72bbca7 2397 return values:
stevep 0:04a9f72bbca7 2398 0 - ok
stevep 0:04a9f72bbca7 2399 1 - carry
stevep 0:04a9f72bbca7 2400 2 - incorrect argument (0^0)
stevep 0:04a9f72bbca7 2401 */
stevep 0:04a9f72bbca7 2402 uint Pow(UInt<value_size> pow)
stevep 0:04a9f72bbca7 2403 {
stevep 0:04a9f72bbca7 2404 if(pow.IsZero() && IsZero())
stevep 0:04a9f72bbca7 2405 // we don't define zero^zero
stevep 0:04a9f72bbca7 2406 return 2;
stevep 0:04a9f72bbca7 2407
stevep 0:04a9f72bbca7 2408 UInt<value_size> start(*this);
stevep 0:04a9f72bbca7 2409 UInt<value_size> result;
stevep 0:04a9f72bbca7 2410 result.SetOne();
stevep 0:04a9f72bbca7 2411 uint c = 0;
stevep 0:04a9f72bbca7 2412
stevep 0:04a9f72bbca7 2413 while( !c )
stevep 0:04a9f72bbca7 2414 {
stevep 0:04a9f72bbca7 2415 if( pow.table[0] & 1 )
stevep 0:04a9f72bbca7 2416 c += result.Mul(start);
stevep 0:04a9f72bbca7 2417
stevep 0:04a9f72bbca7 2418 pow.Rcr2_one(0);
stevep 0:04a9f72bbca7 2419 if( pow.IsZero() )
stevep 0:04a9f72bbca7 2420 break;
stevep 0:04a9f72bbca7 2421
stevep 0:04a9f72bbca7 2422 c += start.Mul(start);
stevep 0:04a9f72bbca7 2423 }
stevep 0:04a9f72bbca7 2424
stevep 0:04a9f72bbca7 2425 *this = result;
stevep 0:04a9f72bbca7 2426
stevep 0:04a9f72bbca7 2427 TTMATH_LOGC("UInt::Pow(UInt<>)", c)
stevep 0:04a9f72bbca7 2428
stevep 0:04a9f72bbca7 2429 return (c==0)? 0 : 1;
stevep 0:04a9f72bbca7 2430 }
stevep 0:04a9f72bbca7 2431
stevep 0:04a9f72bbca7 2432
stevep 0:04a9f72bbca7 2433 /*!
stevep 0:04a9f72bbca7 2434 square root
stevep 0:04a9f72bbca7 2435 e.g. Sqrt(9) = 3
stevep 0:04a9f72bbca7 2436 ('digit-by-digit' algorithm)
stevep 0:04a9f72bbca7 2437 */
stevep 0:04a9f72bbca7 2438 void Sqrt()
stevep 0:04a9f72bbca7 2439 {
stevep 0:04a9f72bbca7 2440 UInt<value_size> bit, temp;
stevep 0:04a9f72bbca7 2441
stevep 0:04a9f72bbca7 2442 if( IsZero() )
stevep 0:04a9f72bbca7 2443 return;
stevep 0:04a9f72bbca7 2444
stevep 0:04a9f72bbca7 2445 UInt<value_size> value(*this);
stevep 0:04a9f72bbca7 2446
stevep 0:04a9f72bbca7 2447 SetZero();
stevep 0:04a9f72bbca7 2448 bit.SetZero();
stevep 0:04a9f72bbca7 2449 bit.table[value_size-1] = (TTMATH_UINT_HIGHEST_BIT >> 1);
stevep 0:04a9f72bbca7 2450
stevep 0:04a9f72bbca7 2451 while( bit > value )
stevep 0:04a9f72bbca7 2452 bit.Rcr(2);
stevep 0:04a9f72bbca7 2453
stevep 0:04a9f72bbca7 2454 while( !bit.IsZero() )
stevep 0:04a9f72bbca7 2455 {
stevep 0:04a9f72bbca7 2456 temp = *this;
stevep 0:04a9f72bbca7 2457 temp.Add(bit);
stevep 0:04a9f72bbca7 2458
stevep 0:04a9f72bbca7 2459 if( value >= temp )
stevep 0:04a9f72bbca7 2460 {
stevep 0:04a9f72bbca7 2461 value.Sub(temp);
stevep 0:04a9f72bbca7 2462 Rcr(1);
stevep 0:04a9f72bbca7 2463 Add(bit);
stevep 0:04a9f72bbca7 2464 }
stevep 0:04a9f72bbca7 2465 else
stevep 0:04a9f72bbca7 2466 {
stevep 0:04a9f72bbca7 2467 Rcr(1);
stevep 0:04a9f72bbca7 2468 }
stevep 0:04a9f72bbca7 2469
stevep 0:04a9f72bbca7 2470 bit.Rcr(2);
stevep 0:04a9f72bbca7 2471 }
stevep 0:04a9f72bbca7 2472
stevep 0:04a9f72bbca7 2473 TTMATH_LOG("UInt::Sqrt")
stevep 0:04a9f72bbca7 2474 }
stevep 0:04a9f72bbca7 2475
stevep 0:04a9f72bbca7 2476
stevep 0:04a9f72bbca7 2477
stevep 0:04a9f72bbca7 2478 /*!
stevep 0:04a9f72bbca7 2479 this method sets n first bits to value zero
stevep 0:04a9f72bbca7 2480
stevep 0:04a9f72bbca7 2481 For example:
stevep 0:04a9f72bbca7 2482 let n=2 then if there's a value 111 (bin) there'll be '100' (bin)
stevep 0:04a9f72bbca7 2483 */
stevep 0:04a9f72bbca7 2484 void ClearFirstBits(uint n)
stevep 0:04a9f72bbca7 2485 {
stevep 0:04a9f72bbca7 2486 if( n >= value_size*TTMATH_BITS_PER_UINT )
stevep 0:04a9f72bbca7 2487 {
stevep 0:04a9f72bbca7 2488 SetZero();
stevep 0:04a9f72bbca7 2489 TTMATH_LOG("UInt::ClearFirstBits")
stevep 0:04a9f72bbca7 2490 return;
stevep 0:04a9f72bbca7 2491 }
stevep 0:04a9f72bbca7 2492
stevep 0:04a9f72bbca7 2493 uint * p = table;
stevep 0:04a9f72bbca7 2494
stevep 0:04a9f72bbca7 2495 // first we're clearing the whole words
stevep 0:04a9f72bbca7 2496 while( n >= TTMATH_BITS_PER_UINT )
stevep 0:04a9f72bbca7 2497 {
stevep 0:04a9f72bbca7 2498 *p++ = 0;
stevep 0:04a9f72bbca7 2499 n -= TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 2500 }
stevep 0:04a9f72bbca7 2501
stevep 0:04a9f72bbca7 2502 if( n == 0 )
stevep 0:04a9f72bbca7 2503 {
stevep 0:04a9f72bbca7 2504 TTMATH_LOG("UInt::ClearFirstBits")
stevep 0:04a9f72bbca7 2505 return;
stevep 0:04a9f72bbca7 2506 }
stevep 0:04a9f72bbca7 2507
stevep 0:04a9f72bbca7 2508 // and then we're clearing one word which has left
stevep 0:04a9f72bbca7 2509 // mask -- all bits are set to one
stevep 0:04a9f72bbca7 2510 uint mask = TTMATH_UINT_MAX_VALUE;
stevep 0:04a9f72bbca7 2511
stevep 0:04a9f72bbca7 2512 mask = mask << n;
stevep 0:04a9f72bbca7 2513
stevep 0:04a9f72bbca7 2514 (*p) &= mask;
stevep 0:04a9f72bbca7 2515
stevep 0:04a9f72bbca7 2516 TTMATH_LOG("UInt::ClearFirstBits")
stevep 0:04a9f72bbca7 2517 }
stevep 0:04a9f72bbca7 2518
stevep 0:04a9f72bbca7 2519
stevep 0:04a9f72bbca7 2520 /*!
stevep 0:04a9f72bbca7 2521 this method returns true if the highest bit of the value is set
stevep 0:04a9f72bbca7 2522 */
stevep 0:04a9f72bbca7 2523 bool IsTheHighestBitSet() const
stevep 0:04a9f72bbca7 2524 {
stevep 0:04a9f72bbca7 2525 return (table[value_size-1] & TTMATH_UINT_HIGHEST_BIT) != 0;
stevep 0:04a9f72bbca7 2526 }
stevep 0:04a9f72bbca7 2527
stevep 0:04a9f72bbca7 2528
stevep 0:04a9f72bbca7 2529 /*!
stevep 0:04a9f72bbca7 2530 this method returns true if the lowest bit of the value is set
stevep 0:04a9f72bbca7 2531 */
stevep 0:04a9f72bbca7 2532 bool IsTheLowestBitSet() const
stevep 0:04a9f72bbca7 2533 {
stevep 0:04a9f72bbca7 2534 return (*table & 1) != 0;
stevep 0:04a9f72bbca7 2535 }
stevep 0:04a9f72bbca7 2536
stevep 0:04a9f72bbca7 2537
stevep 0:04a9f72bbca7 2538 /*!
stevep 0:04a9f72bbca7 2539 returning true if only the highest bit is set
stevep 0:04a9f72bbca7 2540 */
stevep 0:04a9f72bbca7 2541 bool IsOnlyTheHighestBitSet() const
stevep 0:04a9f72bbca7 2542 {
stevep 0:04a9f72bbca7 2543 #ifdef __clang__
stevep 0:04a9f72bbca7 2544 #pragma clang diagnostic push
stevep 0:04a9f72bbca7 2545 #pragma clang diagnostic ignored "-Wtautological-compare"
stevep 0:04a9f72bbca7 2546 #endif
stevep 0:04a9f72bbca7 2547
stevep 0:04a9f72bbca7 2548 for(uint i=0 ; i<value_size-1 ; ++i)
stevep 0:04a9f72bbca7 2549 if( table[i] != 0 )
stevep 0:04a9f72bbca7 2550 return false;
stevep 0:04a9f72bbca7 2551
stevep 0:04a9f72bbca7 2552 #ifdef __clang__
stevep 0:04a9f72bbca7 2553 #pragma clang diagnostic pop
stevep 0:04a9f72bbca7 2554 #endif
stevep 0:04a9f72bbca7 2555 if( table[value_size-1] != TTMATH_UINT_HIGHEST_BIT )
stevep 0:04a9f72bbca7 2556 return false;
stevep 0:04a9f72bbca7 2557
stevep 0:04a9f72bbca7 2558 return true;
stevep 0:04a9f72bbca7 2559 }
stevep 0:04a9f72bbca7 2560
stevep 0:04a9f72bbca7 2561
stevep 0:04a9f72bbca7 2562 /*!
stevep 0:04a9f72bbca7 2563 returning true if only the lowest bit is set
stevep 0:04a9f72bbca7 2564 */
stevep 0:04a9f72bbca7 2565 bool IsOnlyTheLowestBitSet() const
stevep 0:04a9f72bbca7 2566 {
stevep 0:04a9f72bbca7 2567 if( table[0] != 1 )
stevep 0:04a9f72bbca7 2568 return false;
stevep 0:04a9f72bbca7 2569
stevep 0:04a9f72bbca7 2570 for(uint i=1 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2571 if( table[i] != 0 )
stevep 0:04a9f72bbca7 2572 return false;
stevep 0:04a9f72bbca7 2573
stevep 0:04a9f72bbca7 2574 return true;
stevep 0:04a9f72bbca7 2575 }
stevep 0:04a9f72bbca7 2576
stevep 0:04a9f72bbca7 2577
stevep 0:04a9f72bbca7 2578 /*!
stevep 0:04a9f72bbca7 2579 this method returns true if the value is equal zero
stevep 0:04a9f72bbca7 2580 */
stevep 0:04a9f72bbca7 2581 bool IsZero() const
stevep 0:04a9f72bbca7 2582 {
stevep 0:04a9f72bbca7 2583 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2584 if(table[i] != 0)
stevep 0:04a9f72bbca7 2585 return false;
stevep 0:04a9f72bbca7 2586
stevep 0:04a9f72bbca7 2587 return true;
stevep 0:04a9f72bbca7 2588 }
stevep 0:04a9f72bbca7 2589
stevep 0:04a9f72bbca7 2590
stevep 0:04a9f72bbca7 2591 /*!
stevep 0:04a9f72bbca7 2592 returning true if first 'bits' bits are equal zero
stevep 0:04a9f72bbca7 2593 */
stevep 0:04a9f72bbca7 2594 bool AreFirstBitsZero(uint bits) const
stevep 0:04a9f72bbca7 2595 {
stevep 0:04a9f72bbca7 2596 TTMATH_ASSERT( bits <= value_size * TTMATH_BITS_PER_UINT )
stevep 0:04a9f72bbca7 2597
stevep 0:04a9f72bbca7 2598 uint index = bits / TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 2599 uint rest = bits % TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 2600 uint i;
stevep 0:04a9f72bbca7 2601
stevep 0:04a9f72bbca7 2602 for(i=0 ; i<index ; ++i)
stevep 0:04a9f72bbca7 2603 if(table[i] != 0 )
stevep 0:04a9f72bbca7 2604 return false;
stevep 0:04a9f72bbca7 2605
stevep 0:04a9f72bbca7 2606 if( rest == 0 )
stevep 0:04a9f72bbca7 2607 return true;
stevep 0:04a9f72bbca7 2608
stevep 0:04a9f72bbca7 2609 uint mask = TTMATH_UINT_MAX_VALUE >> (TTMATH_BITS_PER_UINT - rest);
stevep 0:04a9f72bbca7 2610
stevep 0:04a9f72bbca7 2611 return (table[i] & mask) == 0;
stevep 0:04a9f72bbca7 2612 }
stevep 0:04a9f72bbca7 2613
stevep 0:04a9f72bbca7 2614
stevep 0:04a9f72bbca7 2615
stevep 0:04a9f72bbca7 2616 /*!
stevep 0:04a9f72bbca7 2617 *
stevep 0:04a9f72bbca7 2618 * conversion methods
stevep 0:04a9f72bbca7 2619 *
stevep 0:04a9f72bbca7 2620 */
stevep 0:04a9f72bbca7 2621
stevep 0:04a9f72bbca7 2622
stevep 0:04a9f72bbca7 2623
stevep 0:04a9f72bbca7 2624 /*!
stevep 0:04a9f72bbca7 2625 this method converts an UInt<another_size> type to this class
stevep 0:04a9f72bbca7 2626
stevep 0:04a9f72bbca7 2627 this operation has mainly sense if the value from p is
stevep 0:04a9f72bbca7 2628 equal or smaller than that one which is returned from UInt<value_size>::SetMax()
stevep 0:04a9f72bbca7 2629
stevep 0:04a9f72bbca7 2630 it returns a carry if the value 'p' is too big
stevep 0:04a9f72bbca7 2631 */
stevep 0:04a9f72bbca7 2632 template<uint argument_size>
stevep 0:04a9f72bbca7 2633 uint FromUInt(const UInt<argument_size> & p)
stevep 0:04a9f72bbca7 2634 {
stevep 0:04a9f72bbca7 2635 uint min_size = (value_size < argument_size)? value_size : argument_size;
stevep 0:04a9f72bbca7 2636 uint i;
stevep 0:04a9f72bbca7 2637
stevep 0:04a9f72bbca7 2638 for(i=0 ; i<min_size ; ++i)
stevep 0:04a9f72bbca7 2639 table[i] = p.table[i];
stevep 0:04a9f72bbca7 2640
stevep 0:04a9f72bbca7 2641
stevep 0:04a9f72bbca7 2642 if( value_size > argument_size )
stevep 0:04a9f72bbca7 2643 {
stevep 0:04a9f72bbca7 2644 // 'this' is longer than 'p'
stevep 0:04a9f72bbca7 2645
stevep 0:04a9f72bbca7 2646 for( ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2647 table[i] = 0;
stevep 0:04a9f72bbca7 2648 }
stevep 0:04a9f72bbca7 2649 else
stevep 0:04a9f72bbca7 2650 {
stevep 0:04a9f72bbca7 2651 for( ; i<argument_size ; ++i)
stevep 0:04a9f72bbca7 2652 if( p.table[i] != 0 )
stevep 0:04a9f72bbca7 2653 {
stevep 0:04a9f72bbca7 2654 TTMATH_LOGC("UInt::FromUInt(UInt<>)", 1)
stevep 0:04a9f72bbca7 2655 return 1;
stevep 0:04a9f72bbca7 2656 }
stevep 0:04a9f72bbca7 2657 }
stevep 0:04a9f72bbca7 2658
stevep 0:04a9f72bbca7 2659 TTMATH_LOGC("UInt::FromUInt(UInt<>)", 0)
stevep 0:04a9f72bbca7 2660
stevep 0:04a9f72bbca7 2661 return 0;
stevep 0:04a9f72bbca7 2662 }
stevep 0:04a9f72bbca7 2663
stevep 0:04a9f72bbca7 2664
stevep 0:04a9f72bbca7 2665 /*!
stevep 0:04a9f72bbca7 2666 this method converts an UInt<another_size> type to this class
stevep 0:04a9f72bbca7 2667
stevep 0:04a9f72bbca7 2668 this operation has mainly sense if the value from p is
stevep 0:04a9f72bbca7 2669 equal or smaller than that one which is returned from UInt<value_size>::SetMax()
stevep 0:04a9f72bbca7 2670
stevep 0:04a9f72bbca7 2671 it returns a carry if the value 'p' is too big
stevep 0:04a9f72bbca7 2672 */
stevep 0:04a9f72bbca7 2673 template<uint argument_size>
stevep 0:04a9f72bbca7 2674 uint FromInt(const UInt<argument_size> & p)
stevep 0:04a9f72bbca7 2675 {
stevep 0:04a9f72bbca7 2676 return FromUInt(p);
stevep 0:04a9f72bbca7 2677 }
stevep 0:04a9f72bbca7 2678
stevep 0:04a9f72bbca7 2679
stevep 0:04a9f72bbca7 2680 /*!
stevep 0:04a9f72bbca7 2681 this method converts the uint type to this class
stevep 0:04a9f72bbca7 2682 */
stevep 0:04a9f72bbca7 2683 uint FromUInt(uint value)
stevep 0:04a9f72bbca7 2684 {
stevep 0:04a9f72bbca7 2685 for(uint i=1 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2686 table[i] = 0;
stevep 0:04a9f72bbca7 2687
stevep 0:04a9f72bbca7 2688 table[0] = value;
stevep 0:04a9f72bbca7 2689
stevep 0:04a9f72bbca7 2690 TTMATH_LOG("UInt::FromUInt(uint)")
stevep 0:04a9f72bbca7 2691
stevep 0:04a9f72bbca7 2692 // there'll never be a carry here
stevep 0:04a9f72bbca7 2693 return 0;
stevep 0:04a9f72bbca7 2694 }
stevep 0:04a9f72bbca7 2695
stevep 0:04a9f72bbca7 2696
stevep 0:04a9f72bbca7 2697 /*!
stevep 0:04a9f72bbca7 2698 this method converts the uint type to this class
stevep 0:04a9f72bbca7 2699 */
stevep 0:04a9f72bbca7 2700 uint FromInt(uint value)
stevep 0:04a9f72bbca7 2701 {
stevep 0:04a9f72bbca7 2702 return FromUInt(value);
stevep 0:04a9f72bbca7 2703 }
stevep 0:04a9f72bbca7 2704
stevep 0:04a9f72bbca7 2705
stevep 0:04a9f72bbca7 2706 /*!
stevep 0:04a9f72bbca7 2707 this method converts the sint type to this class
stevep 0:04a9f72bbca7 2708 */
stevep 0:04a9f72bbca7 2709 uint FromInt(sint value)
stevep 0:04a9f72bbca7 2710 {
stevep 0:04a9f72bbca7 2711 uint c = FromUInt(uint(value));
stevep 0:04a9f72bbca7 2712
stevep 0:04a9f72bbca7 2713 if( c || value < 0 )
stevep 0:04a9f72bbca7 2714 return 1;
stevep 0:04a9f72bbca7 2715
stevep 0:04a9f72bbca7 2716 return 0;
stevep 0:04a9f72bbca7 2717 }
stevep 0:04a9f72bbca7 2718
stevep 0:04a9f72bbca7 2719
stevep 0:04a9f72bbca7 2720 /*!
stevep 0:04a9f72bbca7 2721 this operator converts an UInt<another_size> type to this class
stevep 0:04a9f72bbca7 2722
stevep 0:04a9f72bbca7 2723 it doesn't return a carry
stevep 0:04a9f72bbca7 2724 */
stevep 0:04a9f72bbca7 2725 template<uint argument_size>
stevep 0:04a9f72bbca7 2726 UInt<value_size> & operator=(const UInt<argument_size> & p)
stevep 0:04a9f72bbca7 2727 {
stevep 0:04a9f72bbca7 2728 FromUInt(p);
stevep 0:04a9f72bbca7 2729
stevep 0:04a9f72bbca7 2730 return *this;
stevep 0:04a9f72bbca7 2731 }
stevep 0:04a9f72bbca7 2732
stevep 0:04a9f72bbca7 2733
stevep 0:04a9f72bbca7 2734 /*!
stevep 0:04a9f72bbca7 2735 the assignment operator
stevep 0:04a9f72bbca7 2736 */
stevep 0:04a9f72bbca7 2737 UInt<value_size> & operator=(const UInt<value_size> & p)
stevep 0:04a9f72bbca7 2738 {
stevep 0:04a9f72bbca7 2739 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2740 table[i] = p.table[i];
stevep 0:04a9f72bbca7 2741
stevep 0:04a9f72bbca7 2742 TTMATH_LOG("UInt::operator=(UInt<>)")
stevep 0:04a9f72bbca7 2743
stevep 0:04a9f72bbca7 2744 return *this;
stevep 0:04a9f72bbca7 2745 }
stevep 0:04a9f72bbca7 2746
stevep 0:04a9f72bbca7 2747
stevep 0:04a9f72bbca7 2748 /*!
stevep 0:04a9f72bbca7 2749 this method converts the uint type to this class
stevep 0:04a9f72bbca7 2750 */
stevep 0:04a9f72bbca7 2751 UInt<value_size> & operator=(uint i)
stevep 0:04a9f72bbca7 2752 {
stevep 0:04a9f72bbca7 2753 FromUInt(i);
stevep 0:04a9f72bbca7 2754
stevep 0:04a9f72bbca7 2755 return *this;
stevep 0:04a9f72bbca7 2756 }
stevep 0:04a9f72bbca7 2757
stevep 0:04a9f72bbca7 2758
stevep 0:04a9f72bbca7 2759 /*!
stevep 0:04a9f72bbca7 2760 a constructor for converting the uint to this class
stevep 0:04a9f72bbca7 2761 */
stevep 0:04a9f72bbca7 2762 UInt(uint i)
stevep 0:04a9f72bbca7 2763 {
stevep 0:04a9f72bbca7 2764 FromUInt(i);
stevep 0:04a9f72bbca7 2765 }
stevep 0:04a9f72bbca7 2766
stevep 0:04a9f72bbca7 2767
stevep 0:04a9f72bbca7 2768 /*!
stevep 0:04a9f72bbca7 2769 this method converts the sint type to this class
stevep 0:04a9f72bbca7 2770 */
stevep 0:04a9f72bbca7 2771 UInt<value_size> & operator=(sint i)
stevep 0:04a9f72bbca7 2772 {
stevep 0:04a9f72bbca7 2773 FromInt(i);
stevep 0:04a9f72bbca7 2774
stevep 0:04a9f72bbca7 2775 return *this;
stevep 0:04a9f72bbca7 2776 }
stevep 0:04a9f72bbca7 2777
stevep 0:04a9f72bbca7 2778
stevep 0:04a9f72bbca7 2779 /*!
stevep 0:04a9f72bbca7 2780 a constructor for converting the sint to this class
stevep 0:04a9f72bbca7 2781
stevep 0:04a9f72bbca7 2782 look at the description of UInt::operator=(sint)
stevep 0:04a9f72bbca7 2783 */
stevep 0:04a9f72bbca7 2784 UInt(sint i)
stevep 0:04a9f72bbca7 2785 {
stevep 0:04a9f72bbca7 2786 FromInt(i);
stevep 0:04a9f72bbca7 2787 }
stevep 0:04a9f72bbca7 2788
stevep 0:04a9f72bbca7 2789
stevep 0:04a9f72bbca7 2790 #ifdef TTMATH_PLATFORM32
stevep 0:04a9f72bbca7 2791
stevep 0:04a9f72bbca7 2792
stevep 0:04a9f72bbca7 2793 /*!
stevep 0:04a9f72bbca7 2794 this method converts unsigned 64 bit int type to this class
stevep 0:04a9f72bbca7 2795 ***this method is created only on a 32bit platform***
stevep 0:04a9f72bbca7 2796 */
stevep 0:04a9f72bbca7 2797 uint FromUInt(ulint n)
stevep 0:04a9f72bbca7 2798 {
stevep 0:04a9f72bbca7 2799 table[0] = (uint)n;
stevep 0:04a9f72bbca7 2800
stevep 0:04a9f72bbca7 2801 if( value_size == 1 )
stevep 0:04a9f72bbca7 2802 {
stevep 0:04a9f72bbca7 2803 uint c = ((n >> TTMATH_BITS_PER_UINT) == 0) ? 0 : 1;
stevep 0:04a9f72bbca7 2804
stevep 0:04a9f72bbca7 2805 TTMATH_LOGC("UInt::FromUInt(ulint)", c)
stevep 0:04a9f72bbca7 2806 return c;
stevep 0:04a9f72bbca7 2807 }
stevep 0:04a9f72bbca7 2808
stevep 0:04a9f72bbca7 2809 table[1] = (uint)(n >> TTMATH_BITS_PER_UINT);
stevep 0:04a9f72bbca7 2810
stevep 0:04a9f72bbca7 2811 for(uint i=2 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 2812 table[i] = 0;
stevep 0:04a9f72bbca7 2813
stevep 0:04a9f72bbca7 2814 TTMATH_LOG("UInt::FromUInt(ulint)")
stevep 0:04a9f72bbca7 2815
stevep 0:04a9f72bbca7 2816 return 0;
stevep 0:04a9f72bbca7 2817 }
stevep 0:04a9f72bbca7 2818
stevep 0:04a9f72bbca7 2819
stevep 0:04a9f72bbca7 2820 /*!
stevep 0:04a9f72bbca7 2821 this method converts unsigned 64 bit int type to this class
stevep 0:04a9f72bbca7 2822 ***this method is created only on a 32bit platform***
stevep 0:04a9f72bbca7 2823 */
stevep 0:04a9f72bbca7 2824 uint FromInt(ulint n)
stevep 0:04a9f72bbca7 2825 {
stevep 0:04a9f72bbca7 2826 return FromUInt(n);
stevep 0:04a9f72bbca7 2827 }
stevep 0:04a9f72bbca7 2828
stevep 0:04a9f72bbca7 2829
stevep 0:04a9f72bbca7 2830 /*!
stevep 0:04a9f72bbca7 2831 this method converts signed 64 bit int type to this class
stevep 0:04a9f72bbca7 2832 ***this method is created only on a 32bit platform***
stevep 0:04a9f72bbca7 2833 */
stevep 0:04a9f72bbca7 2834 uint FromInt(slint n)
stevep 0:04a9f72bbca7 2835 {
stevep 0:04a9f72bbca7 2836 uint c = FromUInt(ulint(n));
stevep 0:04a9f72bbca7 2837
stevep 0:04a9f72bbca7 2838 if( c || n < 0 )
stevep 0:04a9f72bbca7 2839 return 1;
stevep 0:04a9f72bbca7 2840
stevep 0:04a9f72bbca7 2841 return 0;
stevep 0:04a9f72bbca7 2842 }
stevep 0:04a9f72bbca7 2843
stevep 0:04a9f72bbca7 2844
stevep 0:04a9f72bbca7 2845 /*!
stevep 0:04a9f72bbca7 2846 this operator converts unsigned 64 bit int type to this class
stevep 0:04a9f72bbca7 2847 ***this operator is created only on a 32bit platform***
stevep 0:04a9f72bbca7 2848 */
stevep 0:04a9f72bbca7 2849 UInt<value_size> & operator=(ulint n)
stevep 0:04a9f72bbca7 2850 {
stevep 0:04a9f72bbca7 2851 FromUInt(n);
stevep 0:04a9f72bbca7 2852
stevep 0:04a9f72bbca7 2853 return *this;
stevep 0:04a9f72bbca7 2854 }
stevep 0:04a9f72bbca7 2855
stevep 0:04a9f72bbca7 2856
stevep 0:04a9f72bbca7 2857 /*!
stevep 0:04a9f72bbca7 2858 a constructor for converting unsigned 64 bit int to this class
stevep 0:04a9f72bbca7 2859 ***this constructor is created only on a 32bit platform***
stevep 0:04a9f72bbca7 2860 */
stevep 0:04a9f72bbca7 2861 UInt(ulint n)
stevep 0:04a9f72bbca7 2862 {
stevep 0:04a9f72bbca7 2863 FromUInt(n);
stevep 0:04a9f72bbca7 2864 }
stevep 0:04a9f72bbca7 2865
stevep 0:04a9f72bbca7 2866
stevep 0:04a9f72bbca7 2867 /*!
stevep 0:04a9f72bbca7 2868 this operator converts signed 64 bit int type to this class
stevep 0:04a9f72bbca7 2869 ***this operator is created only on a 32bit platform***
stevep 0:04a9f72bbca7 2870 */
stevep 0:04a9f72bbca7 2871 UInt<value_size> & operator=(slint n)
stevep 0:04a9f72bbca7 2872 {
stevep 0:04a9f72bbca7 2873 FromInt(n);
stevep 0:04a9f72bbca7 2874
stevep 0:04a9f72bbca7 2875 return *this;
stevep 0:04a9f72bbca7 2876 }
stevep 0:04a9f72bbca7 2877
stevep 0:04a9f72bbca7 2878
stevep 0:04a9f72bbca7 2879 /*!
stevep 0:04a9f72bbca7 2880 a constructor for converting signed 64 bit int to this class
stevep 0:04a9f72bbca7 2881 ***this constructor is created only on a 32bit platform***
stevep 0:04a9f72bbca7 2882 */
stevep 0:04a9f72bbca7 2883 UInt(slint n)
stevep 0:04a9f72bbca7 2884 {
stevep 0:04a9f72bbca7 2885 FromInt(n);
stevep 0:04a9f72bbca7 2886 }
stevep 0:04a9f72bbca7 2887
stevep 0:04a9f72bbca7 2888 #endif
stevep 0:04a9f72bbca7 2889
stevep 0:04a9f72bbca7 2890
stevep 0:04a9f72bbca7 2891
stevep 0:04a9f72bbca7 2892 #ifdef TTMATH_PLATFORM64
stevep 0:04a9f72bbca7 2893
stevep 0:04a9f72bbca7 2894
stevep 0:04a9f72bbca7 2895 /*!
stevep 0:04a9f72bbca7 2896 this method converts 32 bit unsigned int type to this class
stevep 0:04a9f72bbca7 2897 ***this operator is created only on a 64bit platform***
stevep 0:04a9f72bbca7 2898 */
stevep 0:04a9f72bbca7 2899 uint FromUInt(unsigned int i)
stevep 0:04a9f72bbca7 2900 {
stevep 0:04a9f72bbca7 2901 return FromUInt(uint(i));
stevep 0:04a9f72bbca7 2902 }
stevep 0:04a9f72bbca7 2903
stevep 0:04a9f72bbca7 2904 /*!
stevep 0:04a9f72bbca7 2905 this method converts 32 bit unsigned int type to this class
stevep 0:04a9f72bbca7 2906 ***this operator is created only on a 64bit platform***
stevep 0:04a9f72bbca7 2907 */
stevep 0:04a9f72bbca7 2908 uint FromInt(unsigned int i)
stevep 0:04a9f72bbca7 2909 {
stevep 0:04a9f72bbca7 2910 return FromUInt(uint(i));
stevep 0:04a9f72bbca7 2911 }
stevep 0:04a9f72bbca7 2912
stevep 0:04a9f72bbca7 2913
stevep 0:04a9f72bbca7 2914 /*!
stevep 0:04a9f72bbca7 2915 this method converts 32 bit signed int type to this class
stevep 0:04a9f72bbca7 2916 ***this operator is created only on a 64bit platform***
stevep 0:04a9f72bbca7 2917 */
stevep 0:04a9f72bbca7 2918 uint FromInt(signed int i)
stevep 0:04a9f72bbca7 2919 {
stevep 0:04a9f72bbca7 2920 return FromInt(sint(i));
stevep 0:04a9f72bbca7 2921 }
stevep 0:04a9f72bbca7 2922
stevep 0:04a9f72bbca7 2923
stevep 0:04a9f72bbca7 2924 /*!
stevep 0:04a9f72bbca7 2925 this operator converts 32 bit unsigned int type to this class
stevep 0:04a9f72bbca7 2926 ***this operator is created only on a 64bit platform***
stevep 0:04a9f72bbca7 2927 */
stevep 0:04a9f72bbca7 2928 UInt<value_size> & operator=(unsigned int i)
stevep 0:04a9f72bbca7 2929 {
stevep 0:04a9f72bbca7 2930 FromUInt(i);
stevep 0:04a9f72bbca7 2931
stevep 0:04a9f72bbca7 2932 return *this;
stevep 0:04a9f72bbca7 2933 }
stevep 0:04a9f72bbca7 2934
stevep 0:04a9f72bbca7 2935
stevep 0:04a9f72bbca7 2936 /*!
stevep 0:04a9f72bbca7 2937 a constructor for converting 32 bit unsigned int to this class
stevep 0:04a9f72bbca7 2938 ***this constructor is created only on a 64bit platform***
stevep 0:04a9f72bbca7 2939 */
stevep 0:04a9f72bbca7 2940 UInt(unsigned int i)
stevep 0:04a9f72bbca7 2941 {
stevep 0:04a9f72bbca7 2942 FromUInt(i);
stevep 0:04a9f72bbca7 2943 }
stevep 0:04a9f72bbca7 2944
stevep 0:04a9f72bbca7 2945
stevep 0:04a9f72bbca7 2946 /*!
stevep 0:04a9f72bbca7 2947 an operator for converting 32 bit signed int to this class
stevep 0:04a9f72bbca7 2948 ***this constructor is created only on a 64bit platform***
stevep 0:04a9f72bbca7 2949 */
stevep 0:04a9f72bbca7 2950 UInt<value_size> & operator=(signed int i)
stevep 0:04a9f72bbca7 2951 {
stevep 0:04a9f72bbca7 2952 FromInt(i);
stevep 0:04a9f72bbca7 2953
stevep 0:04a9f72bbca7 2954 return *this;
stevep 0:04a9f72bbca7 2955 }
stevep 0:04a9f72bbca7 2956
stevep 0:04a9f72bbca7 2957
stevep 0:04a9f72bbca7 2958 /*!
stevep 0:04a9f72bbca7 2959 a constructor for converting 32 bit signed int to this class
stevep 0:04a9f72bbca7 2960 ***this constructor is created only on a 64bit platform***
stevep 0:04a9f72bbca7 2961 */
stevep 0:04a9f72bbca7 2962 UInt(signed int i)
stevep 0:04a9f72bbca7 2963 {
stevep 0:04a9f72bbca7 2964 FromInt(i);
stevep 0:04a9f72bbca7 2965 }
stevep 0:04a9f72bbca7 2966
stevep 0:04a9f72bbca7 2967
stevep 0:04a9f72bbca7 2968 #endif
stevep 0:04a9f72bbca7 2969
stevep 0:04a9f72bbca7 2970
stevep 0:04a9f72bbca7 2971
stevep 0:04a9f72bbca7 2972
stevep 0:04a9f72bbca7 2973
stevep 0:04a9f72bbca7 2974 /*!
stevep 0:04a9f72bbca7 2975 a constructor for converting a string to this class (with the base=10)
stevep 0:04a9f72bbca7 2976 */
stevep 0:04a9f72bbca7 2977 UInt(const char * s)
stevep 0:04a9f72bbca7 2978 {
stevep 0:04a9f72bbca7 2979 FromString(s);
stevep 0:04a9f72bbca7 2980 }
stevep 0:04a9f72bbca7 2981
stevep 0:04a9f72bbca7 2982
stevep 0:04a9f72bbca7 2983 /*!
stevep 0:04a9f72bbca7 2984 a constructor for converting a string to this class (with the base=10)
stevep 0:04a9f72bbca7 2985 */
stevep 0:04a9f72bbca7 2986 UInt(const std::string & s)
stevep 0:04a9f72bbca7 2987 {
stevep 0:04a9f72bbca7 2988 FromString( s.c_str() );
stevep 0:04a9f72bbca7 2989 }
stevep 0:04a9f72bbca7 2990
stevep 0:04a9f72bbca7 2991
stevep 0:04a9f72bbca7 2992 #ifndef TTMATH_DONT_USE_WCHAR
stevep 0:04a9f72bbca7 2993
stevep 0:04a9f72bbca7 2994 /*!
stevep 0:04a9f72bbca7 2995 a constructor for converting a string to this class (with the base=10)
stevep 0:04a9f72bbca7 2996 */
stevep 0:04a9f72bbca7 2997 UInt(const wchar_t * s)
stevep 0:04a9f72bbca7 2998 {
stevep 0:04a9f72bbca7 2999 FromString(s);
stevep 0:04a9f72bbca7 3000 }
stevep 0:04a9f72bbca7 3001
stevep 0:04a9f72bbca7 3002
stevep 0:04a9f72bbca7 3003 /*!
stevep 0:04a9f72bbca7 3004 a constructor for converting a string to this class (with the base=10)
stevep 0:04a9f72bbca7 3005 */
stevep 0:04a9f72bbca7 3006 UInt(const std::wstring & s)
stevep 0:04a9f72bbca7 3007 {
stevep 0:04a9f72bbca7 3008 FromString( s.c_str() );
stevep 0:04a9f72bbca7 3009 }
stevep 0:04a9f72bbca7 3010
stevep 0:04a9f72bbca7 3011 #endif
stevep 0:04a9f72bbca7 3012
stevep 0:04a9f72bbca7 3013
stevep 0:04a9f72bbca7 3014
stevep 0:04a9f72bbca7 3015
stevep 0:04a9f72bbca7 3016 /*!
stevep 0:04a9f72bbca7 3017 a default constructor
stevep 0:04a9f72bbca7 3018
stevep 0:04a9f72bbca7 3019 we don't clear the table
stevep 0:04a9f72bbca7 3020 */
stevep 0:04a9f72bbca7 3021 UInt()
stevep 0:04a9f72bbca7 3022 {
stevep 0:04a9f72bbca7 3023 // when macro TTMATH_DEBUG_LOG is defined
stevep 0:04a9f72bbca7 3024 // we set special values to the table
stevep 0:04a9f72bbca7 3025 // in order to be everywhere the same value of the UInt object
stevep 0:04a9f72bbca7 3026 // without this it would be difficult to analyse the log file
stevep 0:04a9f72bbca7 3027 #ifdef TTMATH_DEBUG_LOG
stevep 0:04a9f72bbca7 3028 #ifdef TTMATH_PLATFORM32
stevep 0:04a9f72bbca7 3029 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 3030 table[i] = 0xc1c1c1c1;
stevep 0:04a9f72bbca7 3031 #else
stevep 0:04a9f72bbca7 3032 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 3033 table[i] = 0xc1c1c1c1c1c1c1c1;
stevep 0:04a9f72bbca7 3034 #endif
stevep 0:04a9f72bbca7 3035 #endif
stevep 0:04a9f72bbca7 3036 }
stevep 0:04a9f72bbca7 3037
stevep 0:04a9f72bbca7 3038
stevep 0:04a9f72bbca7 3039 /*!
stevep 0:04a9f72bbca7 3040 a copy constructor
stevep 0:04a9f72bbca7 3041 */
stevep 0:04a9f72bbca7 3042 UInt(const UInt<value_size> & u)
stevep 0:04a9f72bbca7 3043 {
stevep 0:04a9f72bbca7 3044 for(uint i=0 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 3045 table[i] = u.table[i];
stevep 0:04a9f72bbca7 3046
stevep 0:04a9f72bbca7 3047 TTMATH_LOG("UInt::UInt(UInt<>)")
stevep 0:04a9f72bbca7 3048 }
stevep 0:04a9f72bbca7 3049
stevep 0:04a9f72bbca7 3050
stevep 0:04a9f72bbca7 3051
stevep 0:04a9f72bbca7 3052 /*!
stevep 0:04a9f72bbca7 3053 a template for producting constructors for copying from another types
stevep 0:04a9f72bbca7 3054 */
stevep 0:04a9f72bbca7 3055 template<uint argument_size>
stevep 0:04a9f72bbca7 3056 UInt(const UInt<argument_size> & u)
stevep 0:04a9f72bbca7 3057 {
stevep 0:04a9f72bbca7 3058 // look that 'size' we still set as 'value_size' and not as u.value_size
stevep 0:04a9f72bbca7 3059 FromUInt(u);
stevep 0:04a9f72bbca7 3060 }
stevep 0:04a9f72bbca7 3061
stevep 0:04a9f72bbca7 3062
stevep 0:04a9f72bbca7 3063
stevep 0:04a9f72bbca7 3064
stevep 0:04a9f72bbca7 3065 /*!
stevep 0:04a9f72bbca7 3066 a destructor
stevep 0:04a9f72bbca7 3067 */
stevep 0:04a9f72bbca7 3068 ~UInt()
stevep 0:04a9f72bbca7 3069 {
stevep 0:04a9f72bbca7 3070 }
stevep 0:04a9f72bbca7 3071
stevep 0:04a9f72bbca7 3072
stevep 0:04a9f72bbca7 3073 /*!
stevep 0:04a9f72bbca7 3074 this method returns the lowest value from table
stevep 0:04a9f72bbca7 3075
stevep 0:04a9f72bbca7 3076 we must be sure when we using this method whether the value
stevep 0:04a9f72bbca7 3077 will hold in an uint type or not (the rest value from the table must be zero)
stevep 0:04a9f72bbca7 3078 */
stevep 0:04a9f72bbca7 3079 uint ToUInt() const
stevep 0:04a9f72bbca7 3080 {
stevep 0:04a9f72bbca7 3081 return table[0];
stevep 0:04a9f72bbca7 3082 }
stevep 0:04a9f72bbca7 3083
stevep 0:04a9f72bbca7 3084
stevep 0:04a9f72bbca7 3085 /*!
stevep 0:04a9f72bbca7 3086 this method converts the value to uint type
stevep 0:04a9f72bbca7 3087 can return a carry if the value is too long to store it in uint type
stevep 0:04a9f72bbca7 3088 */
stevep 0:04a9f72bbca7 3089 uint ToUInt(uint & result) const
stevep 0:04a9f72bbca7 3090 {
stevep 0:04a9f72bbca7 3091 result = table[0];
stevep 0:04a9f72bbca7 3092
stevep 0:04a9f72bbca7 3093 for(uint i=1 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 3094 if( table[i] != 0 )
stevep 0:04a9f72bbca7 3095 return 1;
stevep 0:04a9f72bbca7 3096
stevep 0:04a9f72bbca7 3097 return 0;
stevep 0:04a9f72bbca7 3098 }
stevep 0:04a9f72bbca7 3099
stevep 0:04a9f72bbca7 3100
stevep 0:04a9f72bbca7 3101 /*!
stevep 0:04a9f72bbca7 3102 this method converts the value to uint type
stevep 0:04a9f72bbca7 3103 can return a carry if the value is too long to store it in uint type
stevep 0:04a9f72bbca7 3104 */
stevep 0:04a9f72bbca7 3105 uint ToInt(uint & result) const
stevep 0:04a9f72bbca7 3106 {
stevep 0:04a9f72bbca7 3107 return ToUInt(result);
stevep 0:04a9f72bbca7 3108 }
stevep 0:04a9f72bbca7 3109
stevep 0:04a9f72bbca7 3110
stevep 0:04a9f72bbca7 3111 /*!
stevep 0:04a9f72bbca7 3112 this method converts the value to sint type (signed integer)
stevep 0:04a9f72bbca7 3113 can return a carry if the value is too long to store it in sint type
stevep 0:04a9f72bbca7 3114 */
stevep 0:04a9f72bbca7 3115 uint ToInt(sint & result) const
stevep 0:04a9f72bbca7 3116 {
stevep 0:04a9f72bbca7 3117 result = sint(table[0]);
stevep 0:04a9f72bbca7 3118
stevep 0:04a9f72bbca7 3119 if( (result & TTMATH_UINT_HIGHEST_BIT) != 0 )
stevep 0:04a9f72bbca7 3120 return 1;
stevep 0:04a9f72bbca7 3121
stevep 0:04a9f72bbca7 3122 for(uint i=1 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 3123 if( table[i] != 0 )
stevep 0:04a9f72bbca7 3124 return 1;
stevep 0:04a9f72bbca7 3125
stevep 0:04a9f72bbca7 3126 return 0;
stevep 0:04a9f72bbca7 3127 }
stevep 0:04a9f72bbca7 3128
stevep 0:04a9f72bbca7 3129
stevep 0:04a9f72bbca7 3130 #ifdef TTMATH_PLATFORM32
stevep 0:04a9f72bbca7 3131
stevep 0:04a9f72bbca7 3132 /*!
stevep 0:04a9f72bbca7 3133 this method converts the value to ulint type (64 bit unsigned integer)
stevep 0:04a9f72bbca7 3134 can return a carry if the value is too long to store it in ulint type
stevep 0:04a9f72bbca7 3135 *** this method is created only on a 32 bit platform ***
stevep 0:04a9f72bbca7 3136 */
stevep 0:04a9f72bbca7 3137 uint ToUInt(ulint & result) const
stevep 0:04a9f72bbca7 3138 {
stevep 0:04a9f72bbca7 3139 if( value_size == 1 )
stevep 0:04a9f72bbca7 3140 {
stevep 0:04a9f72bbca7 3141 result = table[0];
stevep 0:04a9f72bbca7 3142 }
stevep 0:04a9f72bbca7 3143 else
stevep 0:04a9f72bbca7 3144 {
stevep 0:04a9f72bbca7 3145 uint low = table[0];
stevep 0:04a9f72bbca7 3146 uint high = table[1];
stevep 0:04a9f72bbca7 3147
stevep 0:04a9f72bbca7 3148 result = low;
stevep 0:04a9f72bbca7 3149 result |= (ulint(high) << TTMATH_BITS_PER_UINT);
stevep 0:04a9f72bbca7 3150
stevep 0:04a9f72bbca7 3151 for(uint i=2 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 3152 if( table[i] != 0 )
stevep 0:04a9f72bbca7 3153 return 1;
stevep 0:04a9f72bbca7 3154 }
stevep 0:04a9f72bbca7 3155
stevep 0:04a9f72bbca7 3156 return 0;
stevep 0:04a9f72bbca7 3157 }
stevep 0:04a9f72bbca7 3158
stevep 0:04a9f72bbca7 3159
stevep 0:04a9f72bbca7 3160 /*!
stevep 0:04a9f72bbca7 3161 this method converts the value to ulint type (64 bit unsigned integer)
stevep 0:04a9f72bbca7 3162 can return a carry if the value is too long to store it in ulint type
stevep 0:04a9f72bbca7 3163 *** this method is created only on a 32 bit platform ***
stevep 0:04a9f72bbca7 3164 */
stevep 0:04a9f72bbca7 3165 uint ToInt(ulint & result) const
stevep 0:04a9f72bbca7 3166 {
stevep 0:04a9f72bbca7 3167 return ToUInt(result);
stevep 0:04a9f72bbca7 3168 }
stevep 0:04a9f72bbca7 3169
stevep 0:04a9f72bbca7 3170
stevep 0:04a9f72bbca7 3171 /*!
stevep 0:04a9f72bbca7 3172 this method converts the value to slint type (64 bit signed integer)
stevep 0:04a9f72bbca7 3173 can return a carry if the value is too long to store it in slint type
stevep 0:04a9f72bbca7 3174 *** this method is created only on a 32 bit platform ***
stevep 0:04a9f72bbca7 3175 */
stevep 0:04a9f72bbca7 3176 uint ToInt(slint & result) const
stevep 0:04a9f72bbca7 3177 {
stevep 0:04a9f72bbca7 3178 ulint temp;
stevep 0:04a9f72bbca7 3179
stevep 0:04a9f72bbca7 3180 uint c = ToUInt(temp);
stevep 0:04a9f72bbca7 3181 result = slint(temp);
stevep 0:04a9f72bbca7 3182
stevep 0:04a9f72bbca7 3183 if( c || result < 0 )
stevep 0:04a9f72bbca7 3184 return 1;
stevep 0:04a9f72bbca7 3185
stevep 0:04a9f72bbca7 3186 return 0;
stevep 0:04a9f72bbca7 3187 }
stevep 0:04a9f72bbca7 3188
stevep 0:04a9f72bbca7 3189 #endif
stevep 0:04a9f72bbca7 3190
stevep 0:04a9f72bbca7 3191
stevep 0:04a9f72bbca7 3192
stevep 0:04a9f72bbca7 3193 #ifdef TTMATH_PLATFORM64
stevep 0:04a9f72bbca7 3194
stevep 0:04a9f72bbca7 3195 /*!
stevep 0:04a9f72bbca7 3196 this method converts the value to a 32 unsigned integer
stevep 0:04a9f72bbca7 3197 can return a carry if the value is too long to store it in this type
stevep 0:04a9f72bbca7 3198 *** this method is created only on a 64 bit platform ***
stevep 0:04a9f72bbca7 3199 */
stevep 0:04a9f72bbca7 3200 uint ToUInt(unsigned int & result) const
stevep 0:04a9f72bbca7 3201 {
stevep 0:04a9f72bbca7 3202 result = (unsigned int)table[0];
stevep 0:04a9f72bbca7 3203
stevep 0:04a9f72bbca7 3204 if( (table[0] >> 32) != 0 )
stevep 0:04a9f72bbca7 3205 return 1;
stevep 0:04a9f72bbca7 3206
stevep 0:04a9f72bbca7 3207 for(uint i=1 ; i<value_size ; ++i)
stevep 0:04a9f72bbca7 3208 if( table[i] != 0 )
stevep 0:04a9f72bbca7 3209 return 1;
stevep 0:04a9f72bbca7 3210
stevep 0:04a9f72bbca7 3211 return 0;
stevep 0:04a9f72bbca7 3212 }
stevep 0:04a9f72bbca7 3213
stevep 0:04a9f72bbca7 3214
stevep 0:04a9f72bbca7 3215 /*!
stevep 0:04a9f72bbca7 3216 this method converts the value to a 32 unsigned integer
stevep 0:04a9f72bbca7 3217 can return a carry if the value is too long to store it in this type
stevep 0:04a9f72bbca7 3218 *** this method is created only on a 64 bit platform ***
stevep 0:04a9f72bbca7 3219 */
stevep 0:04a9f72bbca7 3220 uint ToInt(unsigned int & result) const
stevep 0:04a9f72bbca7 3221 {
stevep 0:04a9f72bbca7 3222 return ToUInt(result);
stevep 0:04a9f72bbca7 3223 }
stevep 0:04a9f72bbca7 3224
stevep 0:04a9f72bbca7 3225
stevep 0:04a9f72bbca7 3226 /*!
stevep 0:04a9f72bbca7 3227 this method converts the value to a 32 signed integer
stevep 0:04a9f72bbca7 3228 can return a carry if the value is too long to store it in this type
stevep 0:04a9f72bbca7 3229 *** this method is created only on a 64 bit platform ***
stevep 0:04a9f72bbca7 3230 */
stevep 0:04a9f72bbca7 3231 uint ToInt(int & result) const
stevep 0:04a9f72bbca7 3232 {
stevep 0:04a9f72bbca7 3233 unsigned int temp;
stevep 0:04a9f72bbca7 3234
stevep 0:04a9f72bbca7 3235 uint c = ToUInt(temp);
stevep 0:04a9f72bbca7 3236 result = int(temp);
stevep 0:04a9f72bbca7 3237
stevep 0:04a9f72bbca7 3238 if( c || result < 0 )
stevep 0:04a9f72bbca7 3239 return 1;
stevep 0:04a9f72bbca7 3240
stevep 0:04a9f72bbca7 3241 return 0;
stevep 0:04a9f72bbca7 3242 }
stevep 0:04a9f72bbca7 3243
stevep 0:04a9f72bbca7 3244
stevep 0:04a9f72bbca7 3245 #endif
stevep 0:04a9f72bbca7 3246
stevep 0:04a9f72bbca7 3247
stevep 0:04a9f72bbca7 3248
stevep 0:04a9f72bbca7 3249
stevep 0:04a9f72bbca7 3250 protected:
stevep 0:04a9f72bbca7 3251
stevep 0:04a9f72bbca7 3252 /*!
stevep 0:04a9f72bbca7 3253 an auxiliary method for converting into the string
stevep 0:04a9f72bbca7 3254 it returns the log (with the base 2) from x
stevep 0:04a9f72bbca7 3255 where x is in <2;16>
stevep 0:04a9f72bbca7 3256 */
stevep 0:04a9f72bbca7 3257 double ToStringLog2(uint x) const
stevep 0:04a9f72bbca7 3258 {
stevep 0:04a9f72bbca7 3259 static double log_tab[] = {
stevep 0:04a9f72bbca7 3260 1.000000000000000000,
stevep 0:04a9f72bbca7 3261 0.630929753571457437,
stevep 0:04a9f72bbca7 3262 0.500000000000000000,
stevep 0:04a9f72bbca7 3263 0.430676558073393050,
stevep 0:04a9f72bbca7 3264 0.386852807234541586,
stevep 0:04a9f72bbca7 3265 0.356207187108022176,
stevep 0:04a9f72bbca7 3266 0.333333333333333333,
stevep 0:04a9f72bbca7 3267 0.315464876785728718,
stevep 0:04a9f72bbca7 3268 0.301029995663981195,
stevep 0:04a9f72bbca7 3269 0.289064826317887859,
stevep 0:04a9f72bbca7 3270 0.278942945651129843,
stevep 0:04a9f72bbca7 3271 0.270238154427319741,
stevep 0:04a9f72bbca7 3272 0.262649535037193547,
stevep 0:04a9f72bbca7 3273 0.255958024809815489,
stevep 0:04a9f72bbca7 3274 0.250000000000000000
stevep 0:04a9f72bbca7 3275 };
stevep 0:04a9f72bbca7 3276
stevep 0:04a9f72bbca7 3277 if( x<2 || x>16 )
stevep 0:04a9f72bbca7 3278 return 0;
stevep 0:04a9f72bbca7 3279
stevep 0:04a9f72bbca7 3280 return log_tab[x-2];
stevep 0:04a9f72bbca7 3281 }
stevep 0:04a9f72bbca7 3282
stevep 0:04a9f72bbca7 3283
stevep 0:04a9f72bbca7 3284 public:
stevep 0:04a9f72bbca7 3285
stevep 0:04a9f72bbca7 3286
stevep 0:04a9f72bbca7 3287 /*!
stevep 0:04a9f72bbca7 3288 an auxiliary method for converting to a string
stevep 0:04a9f72bbca7 3289 it's used from Int::ToString() too (negative is set true then)
stevep 0:04a9f72bbca7 3290 */
stevep 0:04a9f72bbca7 3291 template<class string_type>
stevep 0:04a9f72bbca7 3292 void ToStringBase(string_type & result, uint b = 10, bool negative = false) const
stevep 0:04a9f72bbca7 3293 {
stevep 0:04a9f72bbca7 3294 UInt<value_size> temp(*this);
stevep 0:04a9f72bbca7 3295 uint rest, table_id, index, digits;
stevep 0:04a9f72bbca7 3296 double digits_d;
stevep 0:04a9f72bbca7 3297 char character;
stevep 0:04a9f72bbca7 3298
stevep 0:04a9f72bbca7 3299 result.clear();
stevep 0:04a9f72bbca7 3300
stevep 0:04a9f72bbca7 3301 if( b<2 || b>16 )
stevep 0:04a9f72bbca7 3302 return;
stevep 0:04a9f72bbca7 3303
stevep 0:04a9f72bbca7 3304 if( !FindLeadingBit(table_id, index) )
stevep 0:04a9f72bbca7 3305 {
stevep 0:04a9f72bbca7 3306 result = '0';
stevep 0:04a9f72bbca7 3307 return;
stevep 0:04a9f72bbca7 3308 }
stevep 0:04a9f72bbca7 3309
stevep 0:04a9f72bbca7 3310 if( negative )
stevep 0:04a9f72bbca7 3311 result = '-';
stevep 0:04a9f72bbca7 3312
stevep 0:04a9f72bbca7 3313 digits_d = table_id; // for not making an overflow in uint type
stevep 0:04a9f72bbca7 3314 digits_d *= TTMATH_BITS_PER_UINT;
stevep 0:04a9f72bbca7 3315 digits_d += index + 1;
stevep 0:04a9f72bbca7 3316 digits_d *= ToStringLog2(b);
stevep 0:04a9f72bbca7 3317 digits = static_cast<uint>(digits_d) + 3; // plus some epsilon
stevep 0:04a9f72bbca7 3318
stevep 0:04a9f72bbca7 3319 if( result.capacity() < digits )
stevep 0:04a9f72bbca7 3320 result.reserve(digits);
stevep 0:04a9f72bbca7 3321
stevep 0:04a9f72bbca7 3322 do
stevep 0:04a9f72bbca7 3323 {
stevep 0:04a9f72bbca7 3324 temp.DivInt(b, &rest);
stevep 0:04a9f72bbca7 3325 character = static_cast<char>(Misc::DigitToChar(rest));
stevep 0:04a9f72bbca7 3326 result.insert(result.end(), character);
stevep 0:04a9f72bbca7 3327 }
stevep 0:04a9f72bbca7 3328 while( !temp.IsZero() );
stevep 0:04a9f72bbca7 3329
stevep 0:04a9f72bbca7 3330 size_t i1 = negative ? 1 : 0; // the first is a hyphen (when negative is true)
stevep 0:04a9f72bbca7 3331 size_t i2 = result.size() - 1;
stevep 0:04a9f72bbca7 3332
stevep 0:04a9f72bbca7 3333 for( ; i1 < i2 ; ++i1, --i2 )
stevep 0:04a9f72bbca7 3334 {
stevep 0:04a9f72bbca7 3335 char tempc = static_cast<char>(result[i1]);
stevep 0:04a9f72bbca7 3336 result[i1] = result[i2];
stevep 0:04a9f72bbca7 3337 result[i2] = tempc;
stevep 0:04a9f72bbca7 3338 }
stevep 0:04a9f72bbca7 3339 }
stevep 0:04a9f72bbca7 3340
stevep 0:04a9f72bbca7 3341
stevep 0:04a9f72bbca7 3342
stevep 0:04a9f72bbca7 3343 /*!
stevep 0:04a9f72bbca7 3344 this method converts the value to a string with a base equal 'b'
stevep 0:04a9f72bbca7 3345 */
stevep 0:04a9f72bbca7 3346 void ToString(std::string & result, uint b = 10) const
stevep 0:04a9f72bbca7 3347 {
stevep 0:04a9f72bbca7 3348 return ToStringBase(result, b);
stevep 0:04a9f72bbca7 3349 }
stevep 0:04a9f72bbca7 3350
stevep 0:04a9f72bbca7 3351
stevep 0:04a9f72bbca7 3352 std::string ToString(uint b = 10) const
stevep 0:04a9f72bbca7 3353 {
stevep 0:04a9f72bbca7 3354 std::string result;
stevep 0:04a9f72bbca7 3355 ToStringBase(result, b);
stevep 0:04a9f72bbca7 3356
stevep 0:04a9f72bbca7 3357 return result;
stevep 0:04a9f72bbca7 3358 }
stevep 0:04a9f72bbca7 3359
stevep 0:04a9f72bbca7 3360
stevep 0:04a9f72bbca7 3361 #ifndef TTMATH_DONT_USE_WCHAR
stevep 0:04a9f72bbca7 3362
stevep 0:04a9f72bbca7 3363 void ToString(std::wstring & result, uint b = 10) const
stevep 0:04a9f72bbca7 3364 {
stevep 0:04a9f72bbca7 3365 return ToStringBase(result, b);
stevep 0:04a9f72bbca7 3366 }
stevep 0:04a9f72bbca7 3367
stevep 0:04a9f72bbca7 3368 std::wstring ToWString(uint b = 10) const
stevep 0:04a9f72bbca7 3369 {
stevep 0:04a9f72bbca7 3370 std::wstring result;
stevep 0:04a9f72bbca7 3371 ToStringBase(result, b);
stevep 0:04a9f72bbca7 3372
stevep 0:04a9f72bbca7 3373 return result;
stevep 0:04a9f72bbca7 3374 }
stevep 0:04a9f72bbca7 3375
stevep 0:04a9f72bbca7 3376 #endif
stevep 0:04a9f72bbca7 3377
stevep 0:04a9f72bbca7 3378
stevep 0:04a9f72bbca7 3379
stevep 0:04a9f72bbca7 3380 private:
stevep 0:04a9f72bbca7 3381
stevep 0:04a9f72bbca7 3382 /*!
stevep 0:04a9f72bbca7 3383 an auxiliary method for converting from a string
stevep 0:04a9f72bbca7 3384 */
stevep 0:04a9f72bbca7 3385 template<class char_type>
stevep 0:04a9f72bbca7 3386 uint FromStringBase(const char_type * s, uint b = 10, const char_type ** after_source = 0, bool * value_read = 0)
stevep 0:04a9f72bbca7 3387 {
stevep 0:04a9f72bbca7 3388 UInt<value_size> base( b );
stevep 0:04a9f72bbca7 3389 UInt<value_size> temp;
stevep 0:04a9f72bbca7 3390 sint z;
stevep 0:04a9f72bbca7 3391 uint c = 0;
stevep 0:04a9f72bbca7 3392
stevep 0:04a9f72bbca7 3393 SetZero();
stevep 0:04a9f72bbca7 3394 temp.SetZero();
stevep 0:04a9f72bbca7 3395 Misc::SkipWhiteCharacters(s);
stevep 0:04a9f72bbca7 3396
stevep 0:04a9f72bbca7 3397 if( after_source )
stevep 0:04a9f72bbca7 3398 *after_source = s;
stevep 0:04a9f72bbca7 3399
stevep 0:04a9f72bbca7 3400 if( value_read )
stevep 0:04a9f72bbca7 3401 *value_read = false;
stevep 0:04a9f72bbca7 3402
stevep 0:04a9f72bbca7 3403 if( b<2 || b>16 )
stevep 0:04a9f72bbca7 3404 return 1;
stevep 0:04a9f72bbca7 3405
stevep 0:04a9f72bbca7 3406
stevep 0:04a9f72bbca7 3407 for( ; (z=Misc::CharToDigit(*s, b)) != -1 ; ++s)
stevep 0:04a9f72bbca7 3408 {
stevep 0:04a9f72bbca7 3409 if( value_read )
stevep 0:04a9f72bbca7 3410 *value_read = true;
stevep 0:04a9f72bbca7 3411
stevep 0:04a9f72bbca7 3412 if( c == 0 )
stevep 0:04a9f72bbca7 3413 {
stevep 0:04a9f72bbca7 3414 temp.table[0] = z;
stevep 0:04a9f72bbca7 3415
stevep 0:04a9f72bbca7 3416 c += Mul(base); // !! IMPROVE ME: there can be used MulInt here
stevep 0:04a9f72bbca7 3417 c += Add(temp);
stevep 0:04a9f72bbca7 3418 }
stevep 0:04a9f72bbca7 3419 }
stevep 0:04a9f72bbca7 3420
stevep 0:04a9f72bbca7 3421 if( after_source )
stevep 0:04a9f72bbca7 3422 *after_source = s;
stevep 0:04a9f72bbca7 3423
stevep 0:04a9f72bbca7 3424 TTMATH_LOGC("UInt::FromString", c)
stevep 0:04a9f72bbca7 3425
stevep 0:04a9f72bbca7 3426 return (c==0)? 0 : 1;
stevep 0:04a9f72bbca7 3427 }
stevep 0:04a9f72bbca7 3428
stevep 0:04a9f72bbca7 3429
stevep 0:04a9f72bbca7 3430 public:
stevep 0:04a9f72bbca7 3431
stevep 0:04a9f72bbca7 3432
stevep 0:04a9f72bbca7 3433 /*!
stevep 0:04a9f72bbca7 3434 this method converts a string into its value
stevep 0:04a9f72bbca7 3435 it returns carry=1 if the value will be too big or an incorrect base 'b' is given
stevep 0:04a9f72bbca7 3436
stevep 0:04a9f72bbca7 3437 string is ended with a non-digit value, for example:
stevep 0:04a9f72bbca7 3438 "12" will be translated to 12
stevep 0:04a9f72bbca7 3439 as well as:
stevep 0:04a9f72bbca7 3440 "12foo" will be translated to 12 too
stevep 0:04a9f72bbca7 3441
stevep 0:04a9f72bbca7 3442 existing first white characters will be ommited
stevep 0:04a9f72bbca7 3443
stevep 0:04a9f72bbca7 3444 if the value from s is too large the rest digits will be skipped
stevep 0:04a9f72bbca7 3445
stevep 0:04a9f72bbca7 3446 after_source (if exists) is pointing at the end of the parsed string
stevep 0:04a9f72bbca7 3447
stevep 0:04a9f72bbca7 3448 value_read (if exists) tells whether something has actually been read (at least one digit)
stevep 0:04a9f72bbca7 3449 */
stevep 0:04a9f72bbca7 3450 uint FromString(const char * s, uint b = 10, const char ** after_source = 0, bool * value_read = 0)
stevep 0:04a9f72bbca7 3451 {
stevep 0:04a9f72bbca7 3452 return FromStringBase(s, b, after_source, value_read);
stevep 0:04a9f72bbca7 3453 }
stevep 0:04a9f72bbca7 3454
stevep 0:04a9f72bbca7 3455
stevep 0:04a9f72bbca7 3456 /*!
stevep 0:04a9f72bbca7 3457 this method converts a string into its value
stevep 0:04a9f72bbca7 3458
stevep 0:04a9f72bbca7 3459 (it returns carry=1 if the value will be too big or an incorrect base 'b' is given)
stevep 0:04a9f72bbca7 3460 */
stevep 0:04a9f72bbca7 3461 uint FromString(const std::string & s, uint b = 10)
stevep 0:04a9f72bbca7 3462 {
stevep 0:04a9f72bbca7 3463 return FromString( s.c_str(), b );
stevep 0:04a9f72bbca7 3464 }
stevep 0:04a9f72bbca7 3465
stevep 0:04a9f72bbca7 3466
stevep 0:04a9f72bbca7 3467 /*!
stevep 0:04a9f72bbca7 3468 this operator converts a string into its value (with base = 10)
stevep 0:04a9f72bbca7 3469 */
stevep 0:04a9f72bbca7 3470 UInt<value_size> & operator=(const char * s)
stevep 0:04a9f72bbca7 3471 {
stevep 0:04a9f72bbca7 3472 FromString(s);
stevep 0:04a9f72bbca7 3473
stevep 0:04a9f72bbca7 3474 return *this;
stevep 0:04a9f72bbca7 3475 }
stevep 0:04a9f72bbca7 3476
stevep 0:04a9f72bbca7 3477
stevep 0:04a9f72bbca7 3478 /*!
stevep 0:04a9f72bbca7 3479 this operator converts a string into its value (with base = 10)
stevep 0:04a9f72bbca7 3480 */
stevep 0:04a9f72bbca7 3481 UInt<value_size> & operator=(const std::string & s)
stevep 0:04a9f72bbca7 3482 {
stevep 0:04a9f72bbca7 3483 FromString( s.c_str() );
stevep 0:04a9f72bbca7 3484
stevep 0:04a9f72bbca7 3485 return *this;
stevep 0:04a9f72bbca7 3486 }
stevep 0:04a9f72bbca7 3487
stevep 0:04a9f72bbca7 3488
stevep 0:04a9f72bbca7 3489
stevep 0:04a9f72bbca7 3490 #ifndef TTMATH_DONT_USE_WCHAR
stevep 0:04a9f72bbca7 3491
stevep 0:04a9f72bbca7 3492 /*!
stevep 0:04a9f72bbca7 3493 this method converts a string into its value
stevep 0:04a9f72bbca7 3494 */
stevep 0:04a9f72bbca7 3495 uint FromString(const wchar_t * s, uint b = 10, const wchar_t ** after_source = 0, bool * value_read = 0)
stevep 0:04a9f72bbca7 3496 {
stevep 0:04a9f72bbca7 3497 return FromStringBase(s, b, after_source, value_read);
stevep 0:04a9f72bbca7 3498 }
stevep 0:04a9f72bbca7 3499
stevep 0:04a9f72bbca7 3500
stevep 0:04a9f72bbca7 3501 /*!
stevep 0:04a9f72bbca7 3502 this method converts a string into its value
stevep 0:04a9f72bbca7 3503
stevep 0:04a9f72bbca7 3504 (it returns carry=1 if the value will be too big or an incorrect base 'b' is given)
stevep 0:04a9f72bbca7 3505 */
stevep 0:04a9f72bbca7 3506 uint FromString(const std::wstring & s, uint b = 10)
stevep 0:04a9f72bbca7 3507 {
stevep 0:04a9f72bbca7 3508 return FromString( s.c_str(), b );
stevep 0:04a9f72bbca7 3509 }
stevep 0:04a9f72bbca7 3510
stevep 0:04a9f72bbca7 3511
stevep 0:04a9f72bbca7 3512 /*!
stevep 0:04a9f72bbca7 3513 this operator converts a string into its value (with base = 10)
stevep 0:04a9f72bbca7 3514 */
stevep 0:04a9f72bbca7 3515 UInt<value_size> & operator=(const wchar_t * s)
stevep 0:04a9f72bbca7 3516 {
stevep 0:04a9f72bbca7 3517 FromString(s);
stevep 0:04a9f72bbca7 3518
stevep 0:04a9f72bbca7 3519 return *this;
stevep 0:04a9f72bbca7 3520 }
stevep 0:04a9f72bbca7 3521
stevep 0:04a9f72bbca7 3522
stevep 0:04a9f72bbca7 3523 /*!
stevep 0:04a9f72bbca7 3524 this operator converts a string into its value (with base = 10)
stevep 0:04a9f72bbca7 3525 */
stevep 0:04a9f72bbca7 3526 UInt<value_size> & operator=(const std::wstring & s)
stevep 0:04a9f72bbca7 3527 {
stevep 0:04a9f72bbca7 3528 FromString( s.c_str() );
stevep 0:04a9f72bbca7 3529
stevep 0:04a9f72bbca7 3530 return *this;
stevep 0:04a9f72bbca7 3531 }
stevep 0:04a9f72bbca7 3532
stevep 0:04a9f72bbca7 3533 #endif
stevep 0:04a9f72bbca7 3534
stevep 0:04a9f72bbca7 3535
stevep 0:04a9f72bbca7 3536 /*!
stevep 0:04a9f72bbca7 3537 *
stevep 0:04a9f72bbca7 3538 * methods for comparing
stevep 0:04a9f72bbca7 3539 *
stevep 0:04a9f72bbca7 3540 */
stevep 0:04a9f72bbca7 3541
stevep 0:04a9f72bbca7 3542
stevep 0:04a9f72bbca7 3543 /*!
stevep 0:04a9f72bbca7 3544 this method returns true if 'this' is smaller than 'l'
stevep 0:04a9f72bbca7 3545
stevep 0:04a9f72bbca7 3546 'index' is an index of the first word from will be the comparison performed
stevep 0:04a9f72bbca7 3547 (note: we start the comparison from back - from the last word, when index is -1 /default/
stevep 0:04a9f72bbca7 3548 it is automatically set into the last word)
stevep 0:04a9f72bbca7 3549 I introduced it for some kind of optimization made in the second division algorithm (Div2)
stevep 0:04a9f72bbca7 3550 */
stevep 0:04a9f72bbca7 3551 bool CmpSmaller(const UInt<value_size> & l, sint index = -1) const
stevep 0:04a9f72bbca7 3552 {
stevep 0:04a9f72bbca7 3553 sint i;
stevep 0:04a9f72bbca7 3554
stevep 0:04a9f72bbca7 3555 if( index==-1 || index>=sint(value_size) )
stevep 0:04a9f72bbca7 3556 i = value_size - 1;
stevep 0:04a9f72bbca7 3557 else
stevep 0:04a9f72bbca7 3558 i = index;
stevep 0:04a9f72bbca7 3559
stevep 0:04a9f72bbca7 3560
stevep 0:04a9f72bbca7 3561 for( ; i>=0 ; --i)
stevep 0:04a9f72bbca7 3562 {
stevep 0:04a9f72bbca7 3563 if( table[i] != l.table[i] )
stevep 0:04a9f72bbca7 3564 return table[i] < l.table[i];
stevep 0:04a9f72bbca7 3565 }
stevep 0:04a9f72bbca7 3566
stevep 0:04a9f72bbca7 3567 // they're equal
stevep 0:04a9f72bbca7 3568 return false;
stevep 0:04a9f72bbca7 3569 }
stevep 0:04a9f72bbca7 3570
stevep 0:04a9f72bbca7 3571
stevep 0:04a9f72bbca7 3572
stevep 0:04a9f72bbca7 3573 /*!
stevep 0:04a9f72bbca7 3574 this method returns true if 'this' is bigger than 'l'
stevep 0:04a9f72bbca7 3575
stevep 0:04a9f72bbca7 3576 'index' is an index of the first word from will be the comparison performed
stevep 0:04a9f72bbca7 3577 (note: we start the comparison from back - from the last word, when index is -1 /default/
stevep 0:04a9f72bbca7 3578 it is automatically set into the last word)
stevep 0:04a9f72bbca7 3579
stevep 0:04a9f72bbca7 3580 I introduced it for some kind of optimization made in the second division algorithm (Div2)
stevep 0:04a9f72bbca7 3581 */
stevep 0:04a9f72bbca7 3582 bool CmpBigger(const UInt<value_size> & l, sint index = -1) const
stevep 0:04a9f72bbca7 3583 {
stevep 0:04a9f72bbca7 3584 sint i;
stevep 0:04a9f72bbca7 3585
stevep 0:04a9f72bbca7 3586 if( index==-1 || index>=sint(value_size) )
stevep 0:04a9f72bbca7 3587 i = value_size - 1;
stevep 0:04a9f72bbca7 3588 else
stevep 0:04a9f72bbca7 3589 i = index;
stevep 0:04a9f72bbca7 3590
stevep 0:04a9f72bbca7 3591
stevep 0:04a9f72bbca7 3592 for( ; i>=0 ; --i)
stevep 0:04a9f72bbca7 3593 {
stevep 0:04a9f72bbca7 3594 if( table[i] != l.table[i] )
stevep 0:04a9f72bbca7 3595 return table[i] > l.table[i];
stevep 0:04a9f72bbca7 3596 }
stevep 0:04a9f72bbca7 3597
stevep 0:04a9f72bbca7 3598 // they're equal
stevep 0:04a9f72bbca7 3599 return false;
stevep 0:04a9f72bbca7 3600 }
stevep 0:04a9f72bbca7 3601
stevep 0:04a9f72bbca7 3602
stevep 0:04a9f72bbca7 3603 /*!
stevep 0:04a9f72bbca7 3604 this method returns true if 'this' is equal 'l'
stevep 0:04a9f72bbca7 3605
stevep 0:04a9f72bbca7 3606 'index' is an index of the first word from will be the comparison performed
stevep 0:04a9f72bbca7 3607 (note: we start the comparison from back - from the last word, when index is -1 /default/
stevep 0:04a9f72bbca7 3608 it is automatically set into the last word)
stevep 0:04a9f72bbca7 3609 */
stevep 0:04a9f72bbca7 3610 bool CmpEqual(const UInt<value_size> & l, sint index = -1) const
stevep 0:04a9f72bbca7 3611 {
stevep 0:04a9f72bbca7 3612 sint i;
stevep 0:04a9f72bbca7 3613
stevep 0:04a9f72bbca7 3614 if( index==-1 || index>=sint(value_size) )
stevep 0:04a9f72bbca7 3615 i = value_size - 1;
stevep 0:04a9f72bbca7 3616 else
stevep 0:04a9f72bbca7 3617 i = index;
stevep 0:04a9f72bbca7 3618
stevep 0:04a9f72bbca7 3619
stevep 0:04a9f72bbca7 3620 for( ; i>=0 ; --i)
stevep 0:04a9f72bbca7 3621 if( table[i] != l.table[i] )
stevep 0:04a9f72bbca7 3622 return false;
stevep 0:04a9f72bbca7 3623
stevep 0:04a9f72bbca7 3624 return true;
stevep 0:04a9f72bbca7 3625 }
stevep 0:04a9f72bbca7 3626
stevep 0:04a9f72bbca7 3627
stevep 0:04a9f72bbca7 3628
stevep 0:04a9f72bbca7 3629 /*!
stevep 0:04a9f72bbca7 3630 this method returns true if 'this' is smaller than or equal 'l'
stevep 0:04a9f72bbca7 3631
stevep 0:04a9f72bbca7 3632 'index' is an index of the first word from will be the comparison performed
stevep 0:04a9f72bbca7 3633 (note: we start the comparison from back - from the last word, when index is -1 /default/
stevep 0:04a9f72bbca7 3634 it is automatically set into the last word)
stevep 0:04a9f72bbca7 3635 */
stevep 0:04a9f72bbca7 3636 bool CmpSmallerEqual(const UInt<value_size> & l, sint index=-1) const
stevep 0:04a9f72bbca7 3637 {
stevep 0:04a9f72bbca7 3638 sint i;
stevep 0:04a9f72bbca7 3639
stevep 0:04a9f72bbca7 3640 if( index==-1 || index>=sint(value_size) )
stevep 0:04a9f72bbca7 3641 i = value_size - 1;
stevep 0:04a9f72bbca7 3642 else
stevep 0:04a9f72bbca7 3643 i = index;
stevep 0:04a9f72bbca7 3644
stevep 0:04a9f72bbca7 3645
stevep 0:04a9f72bbca7 3646 for( ; i>=0 ; --i)
stevep 0:04a9f72bbca7 3647 {
stevep 0:04a9f72bbca7 3648 if( table[i] != l.table[i] )
stevep 0:04a9f72bbca7 3649 return table[i] < l.table[i];
stevep 0:04a9f72bbca7 3650 }
stevep 0:04a9f72bbca7 3651
stevep 0:04a9f72bbca7 3652 // they're equal
stevep 0:04a9f72bbca7 3653 return true;
stevep 0:04a9f72bbca7 3654 }
stevep 0:04a9f72bbca7 3655
stevep 0:04a9f72bbca7 3656
stevep 0:04a9f72bbca7 3657
stevep 0:04a9f72bbca7 3658 /*!
stevep 0:04a9f72bbca7 3659 this method returns true if 'this' is bigger than or equal 'l'
stevep 0:04a9f72bbca7 3660
stevep 0:04a9f72bbca7 3661 'index' is an index of the first word from will be the comparison performed
stevep 0:04a9f72bbca7 3662 (note: we start the comparison from back - from the last word, when index is -1 /default/
stevep 0:04a9f72bbca7 3663 it is automatically set into the last word)
stevep 0:04a9f72bbca7 3664 */
stevep 0:04a9f72bbca7 3665 bool CmpBiggerEqual(const UInt<value_size> & l, sint index=-1) const
stevep 0:04a9f72bbca7 3666 {
stevep 0:04a9f72bbca7 3667 sint i;
stevep 0:04a9f72bbca7 3668
stevep 0:04a9f72bbca7 3669 if( index==-1 || index>=sint(value_size) )
stevep 0:04a9f72bbca7 3670 i = value_size - 1;
stevep 0:04a9f72bbca7 3671 else
stevep 0:04a9f72bbca7 3672 i = index;
stevep 0:04a9f72bbca7 3673
stevep 0:04a9f72bbca7 3674
stevep 0:04a9f72bbca7 3675 for( ; i>=0 ; --i)
stevep 0:04a9f72bbca7 3676 {
stevep 0:04a9f72bbca7 3677 if( table[i] != l.table[i] )
stevep 0:04a9f72bbca7 3678 return table[i] > l.table[i];
stevep 0:04a9f72bbca7 3679 }
stevep 0:04a9f72bbca7 3680
stevep 0:04a9f72bbca7 3681 // they're equal
stevep 0:04a9f72bbca7 3682 return true;
stevep 0:04a9f72bbca7 3683 }
stevep 0:04a9f72bbca7 3684
stevep 0:04a9f72bbca7 3685
stevep 0:04a9f72bbca7 3686 /*
stevep 0:04a9f72bbca7 3687 operators for comparising
stevep 0:04a9f72bbca7 3688 */
stevep 0:04a9f72bbca7 3689
stevep 0:04a9f72bbca7 3690 bool operator<(const UInt<value_size> & l) const
stevep 0:04a9f72bbca7 3691 {
stevep 0:04a9f72bbca7 3692 return CmpSmaller(l);
stevep 0:04a9f72bbca7 3693 }
stevep 0:04a9f72bbca7 3694
stevep 0:04a9f72bbca7 3695
stevep 0:04a9f72bbca7 3696 bool operator>(const UInt<value_size> & l) const
stevep 0:04a9f72bbca7 3697 {
stevep 0:04a9f72bbca7 3698 return CmpBigger(l);
stevep 0:04a9f72bbca7 3699 }
stevep 0:04a9f72bbca7 3700
stevep 0:04a9f72bbca7 3701
stevep 0:04a9f72bbca7 3702 bool operator==(const UInt<value_size> & l) const
stevep 0:04a9f72bbca7 3703 {
stevep 0:04a9f72bbca7 3704 return CmpEqual(l);
stevep 0:04a9f72bbca7 3705 }
stevep 0:04a9f72bbca7 3706
stevep 0:04a9f72bbca7 3707
stevep 0:04a9f72bbca7 3708 bool operator!=(const UInt<value_size> & l) const
stevep 0:04a9f72bbca7 3709 {
stevep 0:04a9f72bbca7 3710 return !operator==(l);
stevep 0:04a9f72bbca7 3711 }
stevep 0:04a9f72bbca7 3712
stevep 0:04a9f72bbca7 3713
stevep 0:04a9f72bbca7 3714 bool operator<=(const UInt<value_size> & l) const
stevep 0:04a9f72bbca7 3715 {
stevep 0:04a9f72bbca7 3716 return CmpSmallerEqual(l);
stevep 0:04a9f72bbca7 3717 }
stevep 0:04a9f72bbca7 3718
stevep 0:04a9f72bbca7 3719 bool operator>=(const UInt<value_size> & l) const
stevep 0:04a9f72bbca7 3720 {
stevep 0:04a9f72bbca7 3721 return CmpBiggerEqual(l);
stevep 0:04a9f72bbca7 3722 }
stevep 0:04a9f72bbca7 3723
stevep 0:04a9f72bbca7 3724
stevep 0:04a9f72bbca7 3725 /*!
stevep 0:04a9f72bbca7 3726 *
stevep 0:04a9f72bbca7 3727 * standard mathematical operators
stevep 0:04a9f72bbca7 3728 *
stevep 0:04a9f72bbca7 3729 */
stevep 0:04a9f72bbca7 3730
stevep 0:04a9f72bbca7 3731 UInt<value_size> operator-(const UInt<value_size> & p2) const
stevep 0:04a9f72bbca7 3732 {
stevep 0:04a9f72bbca7 3733 UInt<value_size> temp(*this);
stevep 0:04a9f72bbca7 3734
stevep 0:04a9f72bbca7 3735 temp.Sub(p2);
stevep 0:04a9f72bbca7 3736
stevep 0:04a9f72bbca7 3737 return temp;
stevep 0:04a9f72bbca7 3738 }
stevep 0:04a9f72bbca7 3739
stevep 0:04a9f72bbca7 3740 UInt<value_size> & operator-=(const UInt<value_size> & p2)
stevep 0:04a9f72bbca7 3741 {
stevep 0:04a9f72bbca7 3742 Sub(p2);
stevep 0:04a9f72bbca7 3743
stevep 0:04a9f72bbca7 3744 return *this;
stevep 0:04a9f72bbca7 3745 }
stevep 0:04a9f72bbca7 3746
stevep 0:04a9f72bbca7 3747 UInt<value_size> operator+(const UInt<value_size> & p2) const
stevep 0:04a9f72bbca7 3748 {
stevep 0:04a9f72bbca7 3749 UInt<value_size> temp(*this);
stevep 0:04a9f72bbca7 3750
stevep 0:04a9f72bbca7 3751 temp.Add(p2);
stevep 0:04a9f72bbca7 3752
stevep 0:04a9f72bbca7 3753 return temp;
stevep 0:04a9f72bbca7 3754 }
stevep 0:04a9f72bbca7 3755
stevep 0:04a9f72bbca7 3756 UInt<value_size> & operator+=(const UInt<value_size> & p2)
stevep 0:04a9f72bbca7 3757 {
stevep 0:04a9f72bbca7 3758 Add(p2);
stevep 0:04a9f72bbca7 3759
stevep 0:04a9f72bbca7 3760 return *this;
stevep 0:04a9f72bbca7 3761 }
stevep 0:04a9f72bbca7 3762
stevep 0:04a9f72bbca7 3763
stevep 0:04a9f72bbca7 3764 UInt<value_size> operator*(const UInt<value_size> & p2) const
stevep 0:04a9f72bbca7 3765 {
stevep 0:04a9f72bbca7 3766 UInt<value_size> temp(*this);
stevep 0:04a9f72bbca7 3767
stevep 0:04a9f72bbca7 3768 temp.Mul(p2);
stevep 0:04a9f72bbca7 3769
stevep 0:04a9f72bbca7 3770 return temp;
stevep 0:04a9f72bbca7 3771 }
stevep 0:04a9f72bbca7 3772
stevep 0:04a9f72bbca7 3773
stevep 0:04a9f72bbca7 3774 UInt<value_size> & operator*=(const UInt<value_size> & p2)
stevep 0:04a9f72bbca7 3775 {
stevep 0:04a9f72bbca7 3776 Mul(p2);
stevep 0:04a9f72bbca7 3777
stevep 0:04a9f72bbca7 3778 return *this;
stevep 0:04a9f72bbca7 3779 }
stevep 0:04a9f72bbca7 3780
stevep 0:04a9f72bbca7 3781
stevep 0:04a9f72bbca7 3782 UInt<value_size> operator/(const UInt<value_size> & p2) const
stevep 0:04a9f72bbca7 3783 {
stevep 0:04a9f72bbca7 3784 UInt<value_size> temp(*this);
stevep 0:04a9f72bbca7 3785
stevep 0:04a9f72bbca7 3786 temp.Div(p2);
stevep 0:04a9f72bbca7 3787
stevep 0:04a9f72bbca7 3788 return temp;
stevep 0:04a9f72bbca7 3789 }
stevep 0:04a9f72bbca7 3790
stevep 0:04a9f72bbca7 3791
stevep 0:04a9f72bbca7 3792 UInt<value_size> & operator/=(const UInt<value_size> & p2)
stevep 0:04a9f72bbca7 3793 {
stevep 0:04a9f72bbca7 3794 Div(p2);
stevep 0:04a9f72bbca7 3795
stevep 0:04a9f72bbca7 3796 return *this;
stevep 0:04a9f72bbca7 3797 }
stevep 0:04a9f72bbca7 3798
stevep 0:04a9f72bbca7 3799
stevep 0:04a9f72bbca7 3800 UInt<value_size> operator%(const UInt<value_size> & p2) const
stevep 0:04a9f72bbca7 3801 {
stevep 0:04a9f72bbca7 3802 UInt<value_size> temp(*this);
stevep 0:04a9f72bbca7 3803 UInt<value_size> remainder;
stevep 0:04a9f72bbca7 3804
stevep 0:04a9f72bbca7 3805 temp.Div( p2, remainder );
stevep 0:04a9f72bbca7 3806
stevep 0:04a9f72bbca7 3807 return remainder;
stevep 0:04a9f72bbca7 3808 }
stevep 0:04a9f72bbca7 3809
stevep 0:04a9f72bbca7 3810
stevep 0:04a9f72bbca7 3811 UInt<value_size> & operator%=(const UInt<value_size> & p2)
stevep 0:04a9f72bbca7 3812 {
stevep 0:04a9f72bbca7 3813 UInt<value_size> remainder;
stevep 0:04a9f72bbca7 3814
stevep 0:04a9f72bbca7 3815 Div( p2, remainder );
stevep 0:04a9f72bbca7 3816 operator=(remainder);
stevep 0:04a9f72bbca7 3817
stevep 0:04a9f72bbca7 3818 return *this;
stevep 0:04a9f72bbca7 3819 }
stevep 0:04a9f72bbca7 3820
stevep 0:04a9f72bbca7 3821
stevep 0:04a9f72bbca7 3822 /*!
stevep 0:04a9f72bbca7 3823 Prefix operator e.g ++variable
stevep 0:04a9f72bbca7 3824 */
stevep 0:04a9f72bbca7 3825 UInt<value_size> & operator++()
stevep 0:04a9f72bbca7 3826 {
stevep 0:04a9f72bbca7 3827 AddOne();
stevep 0:04a9f72bbca7 3828
stevep 0:04a9f72bbca7 3829 return *this;
stevep 0:04a9f72bbca7 3830 }
stevep 0:04a9f72bbca7 3831
stevep 0:04a9f72bbca7 3832
stevep 0:04a9f72bbca7 3833 /*!
stevep 0:04a9f72bbca7 3834 Postfix operator e.g variable++
stevep 0:04a9f72bbca7 3835 */
stevep 0:04a9f72bbca7 3836 UInt<value_size> operator++(int)
stevep 0:04a9f72bbca7 3837 {
stevep 0:04a9f72bbca7 3838 UInt<value_size> temp( *this );
stevep 0:04a9f72bbca7 3839
stevep 0:04a9f72bbca7 3840 AddOne();
stevep 0:04a9f72bbca7 3841
stevep 0:04a9f72bbca7 3842 return temp;
stevep 0:04a9f72bbca7 3843 }
stevep 0:04a9f72bbca7 3844
stevep 0:04a9f72bbca7 3845
stevep 0:04a9f72bbca7 3846 UInt<value_size> & operator--()
stevep 0:04a9f72bbca7 3847 {
stevep 0:04a9f72bbca7 3848 SubOne();
stevep 0:04a9f72bbca7 3849
stevep 0:04a9f72bbca7 3850 return *this;
stevep 0:04a9f72bbca7 3851 }
stevep 0:04a9f72bbca7 3852
stevep 0:04a9f72bbca7 3853
stevep 0:04a9f72bbca7 3854 UInt<value_size> operator--(int)
stevep 0:04a9f72bbca7 3855 {
stevep 0:04a9f72bbca7 3856 UInt<value_size> temp( *this );
stevep 0:04a9f72bbca7 3857
stevep 0:04a9f72bbca7 3858 SubOne();
stevep 0:04a9f72bbca7 3859
stevep 0:04a9f72bbca7 3860 return temp;
stevep 0:04a9f72bbca7 3861 }
stevep 0:04a9f72bbca7 3862
stevep 0:04a9f72bbca7 3863
stevep 0:04a9f72bbca7 3864
stevep 0:04a9f72bbca7 3865 /*!
stevep 0:04a9f72bbca7 3866 *
stevep 0:04a9f72bbca7 3867 * bitwise operators
stevep 0:04a9f72bbca7 3868 *
stevep 0:04a9f72bbca7 3869 */
stevep 0:04a9f72bbca7 3870
stevep 0:04a9f72bbca7 3871 UInt<value_size> operator~() const
stevep 0:04a9f72bbca7 3872 {
stevep 0:04a9f72bbca7 3873 UInt<value_size> temp( *this );
stevep 0:04a9f72bbca7 3874
stevep 0:04a9f72bbca7 3875 temp.BitNot();
stevep 0:04a9f72bbca7 3876
stevep 0:04a9f72bbca7 3877 return temp;
stevep 0:04a9f72bbca7 3878 }
stevep 0:04a9f72bbca7 3879
stevep 0:04a9f72bbca7 3880
stevep 0:04a9f72bbca7 3881 UInt<value_size> operator&(const UInt<value_size> & p2) const
stevep 0:04a9f72bbca7 3882 {
stevep 0:04a9f72bbca7 3883 UInt<value_size> temp( *this );
stevep 0:04a9f72bbca7 3884
stevep 0:04a9f72bbca7 3885 temp.BitAnd(p2);
stevep 0:04a9f72bbca7 3886
stevep 0:04a9f72bbca7 3887 return temp;
stevep 0:04a9f72bbca7 3888 }
stevep 0:04a9f72bbca7 3889
stevep 0:04a9f72bbca7 3890
stevep 0:04a9f72bbca7 3891 UInt<value_size> & operator&=(const UInt<value_size> & p2)
stevep 0:04a9f72bbca7 3892 {
stevep 0:04a9f72bbca7 3893 BitAnd(p2);
stevep 0:04a9f72bbca7 3894
stevep 0:04a9f72bbca7 3895 return *this;
stevep 0:04a9f72bbca7 3896 }
stevep 0:04a9f72bbca7 3897
stevep 0:04a9f72bbca7 3898
stevep 0:04a9f72bbca7 3899 UInt<value_size> operator|(const UInt<value_size> & p2) const
stevep 0:04a9f72bbca7 3900 {
stevep 0:04a9f72bbca7 3901 UInt<value_size> temp( *this );
stevep 0:04a9f72bbca7 3902
stevep 0:04a9f72bbca7 3903 temp.BitOr(p2);
stevep 0:04a9f72bbca7 3904
stevep 0:04a9f72bbca7 3905 return temp;
stevep 0:04a9f72bbca7 3906 }
stevep 0:04a9f72bbca7 3907
stevep 0:04a9f72bbca7 3908
stevep 0:04a9f72bbca7 3909 UInt<value_size> & operator|=(const UInt<value_size> & p2)
stevep 0:04a9f72bbca7 3910 {
stevep 0:04a9f72bbca7 3911 BitOr(p2);
stevep 0:04a9f72bbca7 3912
stevep 0:04a9f72bbca7 3913 return *this;
stevep 0:04a9f72bbca7 3914 }
stevep 0:04a9f72bbca7 3915
stevep 0:04a9f72bbca7 3916
stevep 0:04a9f72bbca7 3917 UInt<value_size> operator^(const UInt<value_size> & p2) const
stevep 0:04a9f72bbca7 3918 {
stevep 0:04a9f72bbca7 3919 UInt<value_size> temp( *this );
stevep 0:04a9f72bbca7 3920
stevep 0:04a9f72bbca7 3921 temp.BitXor(p2);
stevep 0:04a9f72bbca7 3922
stevep 0:04a9f72bbca7 3923 return temp;
stevep 0:04a9f72bbca7 3924 }
stevep 0:04a9f72bbca7 3925
stevep 0:04a9f72bbca7 3926
stevep 0:04a9f72bbca7 3927 UInt<value_size> & operator^=(const UInt<value_size> & p2)
stevep 0:04a9f72bbca7 3928 {
stevep 0:04a9f72bbca7 3929 BitXor(p2);
stevep 0:04a9f72bbca7 3930
stevep 0:04a9f72bbca7 3931 return *this;
stevep 0:04a9f72bbca7 3932 }
stevep 0:04a9f72bbca7 3933
stevep 0:04a9f72bbca7 3934
stevep 0:04a9f72bbca7 3935 UInt<value_size> operator>>(int move) const
stevep 0:04a9f72bbca7 3936 {
stevep 0:04a9f72bbca7 3937 UInt<value_size> temp( *this );
stevep 0:04a9f72bbca7 3938
stevep 0:04a9f72bbca7 3939 temp.Rcr(move);
stevep 0:04a9f72bbca7 3940
stevep 0:04a9f72bbca7 3941 return temp;
stevep 0:04a9f72bbca7 3942 }
stevep 0:04a9f72bbca7 3943
stevep 0:04a9f72bbca7 3944
stevep 0:04a9f72bbca7 3945 UInt<value_size> & operator>>=(int move)
stevep 0:04a9f72bbca7 3946 {
stevep 0:04a9f72bbca7 3947 Rcr(move);
stevep 0:04a9f72bbca7 3948
stevep 0:04a9f72bbca7 3949 return *this;
stevep 0:04a9f72bbca7 3950 }
stevep 0:04a9f72bbca7 3951
stevep 0:04a9f72bbca7 3952
stevep 0:04a9f72bbca7 3953 UInt<value_size> operator<<(int move) const
stevep 0:04a9f72bbca7 3954 {
stevep 0:04a9f72bbca7 3955 UInt<value_size> temp( *this );
stevep 0:04a9f72bbca7 3956
stevep 0:04a9f72bbca7 3957 temp.Rcl(move);
stevep 0:04a9f72bbca7 3958
stevep 0:04a9f72bbca7 3959 return temp;
stevep 0:04a9f72bbca7 3960 }
stevep 0:04a9f72bbca7 3961
stevep 0:04a9f72bbca7 3962
stevep 0:04a9f72bbca7 3963 UInt<value_size> & operator<<=(int move)
stevep 0:04a9f72bbca7 3964 {
stevep 0:04a9f72bbca7 3965 Rcl(move);
stevep 0:04a9f72bbca7 3966
stevep 0:04a9f72bbca7 3967 return *this;
stevep 0:04a9f72bbca7 3968 }
stevep 0:04a9f72bbca7 3969
stevep 0:04a9f72bbca7 3970
stevep 0:04a9f72bbca7 3971 /*!
stevep 0:04a9f72bbca7 3972 *
stevep 0:04a9f72bbca7 3973 * input/output operators for standard streams
stevep 0:04a9f72bbca7 3974 *
stevep 0:04a9f72bbca7 3975 * (they are very simple, in the future they should be changed)
stevep 0:04a9f72bbca7 3976 *
stevep 0:04a9f72bbca7 3977 */
stevep 0:04a9f72bbca7 3978
stevep 0:04a9f72bbca7 3979
stevep 0:04a9f72bbca7 3980 private:
stevep 0:04a9f72bbca7 3981
stevep 0:04a9f72bbca7 3982
stevep 0:04a9f72bbca7 3983 /*!
stevep 0:04a9f72bbca7 3984 an auxiliary method for outputing to standard streams
stevep 0:04a9f72bbca7 3985 */
stevep 0:04a9f72bbca7 3986 template<class ostream_type, class string_type>
stevep 0:04a9f72bbca7 3987 static ostream_type & OutputToStream(ostream_type & s, const UInt<value_size> & l)
stevep 0:04a9f72bbca7 3988 {
stevep 0:04a9f72bbca7 3989 string_type ss;
stevep 0:04a9f72bbca7 3990
stevep 0:04a9f72bbca7 3991 l.ToString(ss);
stevep 0:04a9f72bbca7 3992 s << ss;
stevep 0:04a9f72bbca7 3993
stevep 0:04a9f72bbca7 3994 return s;
stevep 0:04a9f72bbca7 3995 }
stevep 0:04a9f72bbca7 3996
stevep 0:04a9f72bbca7 3997
stevep 0:04a9f72bbca7 3998 public:
stevep 0:04a9f72bbca7 3999
stevep 0:04a9f72bbca7 4000
stevep 0:04a9f72bbca7 4001 /*!
stevep 0:04a9f72bbca7 4002 output to standard streams
stevep 0:04a9f72bbca7 4003 */
stevep 0:04a9f72bbca7 4004 friend std::ostream & operator<<(std::ostream & s, const UInt<value_size> & l)
stevep 0:04a9f72bbca7 4005 {
stevep 0:04a9f72bbca7 4006 return OutputToStream<std::ostream, std::string>(s, l);
stevep 0:04a9f72bbca7 4007 }
stevep 0:04a9f72bbca7 4008
stevep 0:04a9f72bbca7 4009
stevep 0:04a9f72bbca7 4010 #ifndef TTMATH_DONT_USE_WCHAR
stevep 0:04a9f72bbca7 4011
stevep 0:04a9f72bbca7 4012 /*!
stevep 0:04a9f72bbca7 4013 output to standard streams
stevep 0:04a9f72bbca7 4014 */
stevep 0:04a9f72bbca7 4015 friend std::wostream & operator<<(std::wostream & s, const UInt<value_size> & l)
stevep 0:04a9f72bbca7 4016 {
stevep 0:04a9f72bbca7 4017 return OutputToStream<std::wostream, std::wstring>(s, l);
stevep 0:04a9f72bbca7 4018 }
stevep 0:04a9f72bbca7 4019
stevep 0:04a9f72bbca7 4020 #endif
stevep 0:04a9f72bbca7 4021
stevep 0:04a9f72bbca7 4022
stevep 0:04a9f72bbca7 4023
stevep 0:04a9f72bbca7 4024 private:
stevep 0:04a9f72bbca7 4025
stevep 0:04a9f72bbca7 4026 /*!
stevep 0:04a9f72bbca7 4027 an auxiliary method for reading from standard streams
stevep 0:04a9f72bbca7 4028 */
stevep 0:04a9f72bbca7 4029 template<class istream_type, class string_type, class char_type>
stevep 0:04a9f72bbca7 4030 static istream_type & InputFromStream(istream_type & s, UInt<value_size> & l)
stevep 0:04a9f72bbca7 4031 {
stevep 0:04a9f72bbca7 4032 string_type ss;
stevep 0:04a9f72bbca7 4033
stevep 0:04a9f72bbca7 4034 // char or wchar_t for operator>>
stevep 0:04a9f72bbca7 4035 char_type z;
stevep 0:04a9f72bbca7 4036
stevep 0:04a9f72bbca7 4037 // operator>> omits white characters if they're set for ommiting
stevep 0:04a9f72bbca7 4038 s >> z;
stevep 0:04a9f72bbca7 4039
stevep 0:04a9f72bbca7 4040 // we're reading only digits (base=10)
stevep 0:04a9f72bbca7 4041 while( s.good() && Misc::CharToDigit(z, 10)>=0 )
stevep 0:04a9f72bbca7 4042 {
stevep 0:04a9f72bbca7 4043 ss += z;
stevep 0:04a9f72bbca7 4044 z = static_cast<char_type>(s.get());
stevep 0:04a9f72bbca7 4045 }
stevep 0:04a9f72bbca7 4046
stevep 0:04a9f72bbca7 4047 // we're leaving the last read character
stevep 0:04a9f72bbca7 4048 // (it's not belonging to the value)
stevep 0:04a9f72bbca7 4049 s.unget();
stevep 0:04a9f72bbca7 4050
stevep 0:04a9f72bbca7 4051 l.FromString(ss);
stevep 0:04a9f72bbca7 4052
stevep 0:04a9f72bbca7 4053 return s;
stevep 0:04a9f72bbca7 4054 }
stevep 0:04a9f72bbca7 4055
stevep 0:04a9f72bbca7 4056 public:
stevep 0:04a9f72bbca7 4057
stevep 0:04a9f72bbca7 4058
stevep 0:04a9f72bbca7 4059 /*!
stevep 0:04a9f72bbca7 4060 input from standard streams
stevep 0:04a9f72bbca7 4061 */
stevep 0:04a9f72bbca7 4062 friend std::istream & operator>>(std::istream & s, UInt<value_size> & l)
stevep 0:04a9f72bbca7 4063 {
stevep 0:04a9f72bbca7 4064 return InputFromStream<std::istream, std::string, char>(s, l);
stevep 0:04a9f72bbca7 4065 }
stevep 0:04a9f72bbca7 4066
stevep 0:04a9f72bbca7 4067
stevep 0:04a9f72bbca7 4068 #ifndef TTMATH_DONT_USE_WCHAR
stevep 0:04a9f72bbca7 4069
stevep 0:04a9f72bbca7 4070 /*!
stevep 0:04a9f72bbca7 4071 input from standard streams
stevep 0:04a9f72bbca7 4072 */
stevep 0:04a9f72bbca7 4073 friend std::wistream & operator>>(std::wistream & s, UInt<value_size> & l)
stevep 0:04a9f72bbca7 4074 {
stevep 0:04a9f72bbca7 4075 return InputFromStream<std::wistream, std::wstring, wchar_t>(s, l);
stevep 0:04a9f72bbca7 4076 }
stevep 0:04a9f72bbca7 4077
stevep 0:04a9f72bbca7 4078 #endif
stevep 0:04a9f72bbca7 4079
stevep 0:04a9f72bbca7 4080
stevep 0:04a9f72bbca7 4081 /*
stevep 0:04a9f72bbca7 4082 Following methods are defined in:
stevep 0:04a9f72bbca7 4083 ttmathuint_x86.h
stevep 0:04a9f72bbca7 4084 ttmathuint_x86_64.h
stevep 0:04a9f72bbca7 4085 ttmathuint_noasm.h
stevep 0:04a9f72bbca7 4086 */
stevep 0:04a9f72bbca7 4087
stevep 0:04a9f72bbca7 4088 #ifdef TTMATH_NOASM
stevep 0:04a9f72bbca7 4089 static uint AddTwoWords(uint a, uint b, uint carry, uint * result);
stevep 0:04a9f72bbca7 4090 static uint SubTwoWords(uint a, uint b, uint carry, uint * result);
stevep 0:04a9f72bbca7 4091
stevep 0:04a9f72bbca7 4092 #ifdef TTMATH_PLATFORM64
stevep 0:04a9f72bbca7 4093
stevep 0:04a9f72bbca7 4094 union uint_
stevep 0:04a9f72bbca7 4095 {
stevep 0:04a9f72bbca7 4096 struct
stevep 0:04a9f72bbca7 4097 {
stevep 0:04a9f72bbca7 4098 unsigned int low; // 32 bit
stevep 0:04a9f72bbca7 4099 unsigned int high; // 32 bit
stevep 0:04a9f72bbca7 4100 } u_;
stevep 0:04a9f72bbca7 4101
stevep 0:04a9f72bbca7 4102 uint u; // 64 bit
stevep 0:04a9f72bbca7 4103 };
stevep 0:04a9f72bbca7 4104
stevep 0:04a9f72bbca7 4105
stevep 0:04a9f72bbca7 4106 static void DivTwoWords2(uint a,uint b, uint c, uint * r, uint * rest);
stevep 0:04a9f72bbca7 4107 static uint DivTwoWordsNormalize(uint_ & a_, uint_ & b_, uint_ & c_);
stevep 0:04a9f72bbca7 4108 static uint DivTwoWordsUnnormalize(uint u, uint d);
stevep 0:04a9f72bbca7 4109 static unsigned int DivTwoWordsCalculate(uint_ u_, unsigned int u3, uint_ v_);
stevep 0:04a9f72bbca7 4110 static void MultiplySubtract(uint_ & u_, unsigned int & u3, unsigned int & q, uint_ v_);
stevep 0:04a9f72bbca7 4111
stevep 0:04a9f72bbca7 4112 #endif // TTMATH_PLATFORM64
stevep 0:04a9f72bbca7 4113 #endif // TTMATH_NOASM
stevep 0:04a9f72bbca7 4114
stevep 0:04a9f72bbca7 4115
stevep 0:04a9f72bbca7 4116 private:
stevep 0:04a9f72bbca7 4117 uint Rcl2_one(uint c);
stevep 0:04a9f72bbca7 4118 uint Rcr2_one(uint c);
stevep 0:04a9f72bbca7 4119 uint Rcl2(uint bits, uint c);
stevep 0:04a9f72bbca7 4120 uint Rcr2(uint bits, uint c);
stevep 0:04a9f72bbca7 4121
stevep 0:04a9f72bbca7 4122 public:
stevep 0:04a9f72bbca7 4123 static const char * LibTypeStr();
stevep 0:04a9f72bbca7 4124 static LibTypeCode LibType();
stevep 0:04a9f72bbca7 4125 uint Add(const UInt<value_size> & ss2, uint c=0);
stevep 0:04a9f72bbca7 4126 uint AddInt(uint value, uint index = 0);
stevep 0:04a9f72bbca7 4127 uint AddTwoInts(uint x2, uint x1, uint index);
stevep 0:04a9f72bbca7 4128 static uint AddVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
stevep 0:04a9f72bbca7 4129 uint Sub(const UInt<value_size> & ss2, uint c=0);
stevep 0:04a9f72bbca7 4130 uint SubInt(uint value, uint index = 0);
stevep 0:04a9f72bbca7 4131 static uint SubVector(const uint * ss1, const uint * ss2, uint ss1_size, uint ss2_size, uint * result);
stevep 0:04a9f72bbca7 4132 static sint FindLeadingBitInWord(uint x);
stevep 0:04a9f72bbca7 4133 static sint FindLowestBitInWord(uint x);
stevep 0:04a9f72bbca7 4134 static uint SetBitInWord(uint & value, uint bit);
stevep 0:04a9f72bbca7 4135 static void MulTwoWords(uint a, uint b, uint * result_high, uint * result_low);
stevep 0:04a9f72bbca7 4136 static void DivTwoWords(uint a,uint b, uint c, uint * r, uint * rest);
stevep 0:04a9f72bbca7 4137
stevep 0:04a9f72bbca7 4138 };
stevep 0:04a9f72bbca7 4139
stevep 0:04a9f72bbca7 4140
stevep 0:04a9f72bbca7 4141
stevep 0:04a9f72bbca7 4142 /*!
stevep 0:04a9f72bbca7 4143 this specialization is needed in order to not confused the compiler "error: ISO C++ forbids zero-size array"
stevep 0:04a9f72bbca7 4144 when compiling Mul3Big2() method
stevep 0:04a9f72bbca7 4145 */
stevep 0:04a9f72bbca7 4146 template<>
stevep 0:04a9f72bbca7 4147 class UInt<0>
stevep 0:04a9f72bbca7 4148 {
stevep 0:04a9f72bbca7 4149 public:
stevep 0:04a9f72bbca7 4150 uint table[1];
stevep 0:04a9f72bbca7 4151
stevep 0:04a9f72bbca7 4152 void Mul2Big(const UInt<0> &, UInt<0> &) { TTMATH_ASSERT(false) };
stevep 0:04a9f72bbca7 4153 void SetZero() { TTMATH_ASSERT(false) };
stevep 0:04a9f72bbca7 4154 uint AddTwoInts(uint, uint, uint) { TTMATH_ASSERT(false) return 0; };
stevep 0:04a9f72bbca7 4155 };
stevep 0:04a9f72bbca7 4156
stevep 0:04a9f72bbca7 4157
stevep 0:04a9f72bbca7 4158 } //namespace
stevep 0:04a9f72bbca7 4159
stevep 0:04a9f72bbca7 4160
stevep 0:04a9f72bbca7 4161 #include "ttmathuint_x86.h"
stevep 0:04a9f72bbca7 4162 #include "ttmathuint_x86_64.h"
stevep 0:04a9f72bbca7 4163 #include "ttmathuint_noasm.h"
stevep 0:04a9f72bbca7 4164
stevep 0:04a9f72bbca7 4165 #endif
stevep 0:04a9f72bbca7 4166