UIntFunc

Files CCore/inc/gadget/UIntFunc.h CCore/src/gadget/UIntFunc.cpp

UIntFunc

UIntFunc is an Algorithm Package, parametrized by an unsigned integral type.

template <class UInt>
struct UIntFunc
 {
  // consts

  static const unsigned Bits = .... ; // the number of bits
  
  static const UInt MaxUnsigned ; // 111...111
  
  static const UInt MSBit ;       // 100...000
  
  static const UInt MaxPositive ; // 011...111
  
  static const UInt MinNegative ; // 100...000

MaxUnsigned is a maximum value, represented by the type. All bits are set.

MSBit is a value with the only most significant bit set.

MaxPositive is a maximum positive value, if we interpret an unsigned as a signed in 2's complement representation. All bits are set, except the most significant.

MinNegative is a minimum negative value, if we interpret an unsigned as a signed in 2's complement representation. Only the most significant bit is set. It is the same value, as MSBit.

  
  // sign
  
  static UInt Neg(UInt value);
  
  static bool IsNegative(UInt value);
    
  static bool NotNegative(UInt value);
  
  static bool IsPositive(UInt value);
  
  static bool NotPositive(UInt value);

Neg() negates the argument.

IsNegative(), NotNegative(), IsPositive(), NotPositive() interpret the argument as a signed in 2's complement representation and return its signed properties.

  // bit count

  static unsigned CountZeroMSB(UInt a);
  
  static unsigned CountZeroLSB(UInt a);

  static unsigned BitsOf(UInt a);

CountZeroMSB() counts the number of zero most significant bits of the given number.

CountZeroLSB() counts the number of zero least significant bits of the given number.

BitsOf() returns the number of bits of the argument. I.e. it is a minimum number n, such that a < 2ⁿ .

  // square root
  
  static UInt SqRoot(UInt S,UInt x); // S,x > 0
  
  static UInt SqRoot(UInt S);

Both of these functions calculate the square root of the argument S, rounded up to the nearest integral value.

The first function requires that S > 0 and x > 0, x is the initial approximation of the result. The better this approximation the faster is function.

  
  // additive
  
  struct Add
   {
    UInt result;
    bool carry;
    
    Add(UInt a,UInt b);
   };
   
  struct Sub
   {
    UInt result;
    bool borrow;
    
    Sub(UInt a,UInt b);
   };
   
  struct Inc
   {
    UInt result;
    bool carry;
    
    explicit Inc(UInt a);
   };
   
  struct Dec
   {
    UInt result;
    bool borrow;
    
    explicit Dec(UInt a);
   };

  // multiplicative

  struct Mul
   {
    UInt hi;
    UInt lo;
    
    Mul(UInt a,UInt b);
   };
  
  static UInt Div(UInt hi,UInt lo,UInt den); // hi < den
  
  static UInt Mod(UInt hi,UInt lo,UInt den); // hi < den
  
  struct DivMod
   {
    UInt div;
    UInt mod;
    
    DivMod(UInt hi,UInt lo,UInt den); // hi < den
   };

  static UInt MulDiv(UInt a,UInt b,UInt den); // (a*b)/den
  
  static UInt ModMul(UInt a,UInt b,UInt mod); // a,b < mod 

  static UInt ModMac(UInt s,UInt a,UInt b,UInt mod); // s,a,b < mod
 };

Add is a Class-function performing the addition of the arguments with carry.

Sub is a Class-function performing the subtraction of the arguments with borrow.

Inc is a Class-function performing the increment of the argument with carry.

Dec is a Class-function performing the decrement of the argument with borrow.

Mul is a Class-function performing the multiplication of the arguments. The result has double length and represented by two fields hi and lo for high part and low part of the result respectively.

Div() performs the division of the double length value by the single length divisor. The value is represented by two arguments hi and lo, den is a divisor. The hi must be less than den, it implies that the result has the single length.

Mod() calculates the reminder of the division of the double length value by the single length divisor. The value is represented by two arguments hi and lo, den is a divisor. The hi must be less than den.

DivMod is a Class-function, it performs the division of the double length value by the single length divisor. The value is represented by two arguments hi and lo, den is a divisor. The div field is the quotient and the mod is the reminder.

MulDiv() multiplies two arguments and divides the double length result by the third argument. It is assumed that the result is represented by a single length value, otherwise the behavior is undefined.

ModMul() performs the modular multiplication. It calculates the reminder of the product of a and b by the module mod. It is assumed, that a and b are less than mod.

ModMac() performs the modular multiplication-and-accumulation. It calculates the reminder of the s+a*b by the module mod. It is assumed, that s, a and b are less than mod.

MaxUInt

MaxUInt is a Meta-constant equals the maximum value of the unsigned integral type.

template <class UInt>
const UInt MaxUInt = UInt(-1) ;

Bit() and UIntBit()

These two functions make a one-bit value of an unsigned integral type.

inline constexpr unsigned Bit(unsigned num) { return 1u<<num; }

template <class UInt>
constexpr UInt UIntBit(unsigned num) { return UInt(1)<<num; }

UInt...()

UInt...() is a family of functions. They do direct calls of the functions from the UIntFunc<UInt>.

template <class UInt>
UInt UIntNeg(UInt a);

template <class UInt>
unsigned UIntBitsOf(UInt a);

template <class UInt>
bool UIntAdd(UInt &a,UInt b);

template <class UInt>
bool UIntSub(UInt &a,UInt b);

template <class UInt> 
bool UIntInc(UInt &a);

template <class UInt> 
bool UIntDec(UInt &a);

template <class UInt> 
UInt UIntMulDiv(UInt a,UInt b,UInt den);

template <class UInt>
UInt UIntDiv(UInt hi,UInt lo,UInt den); // hi < den

template <class UInt>
UInt UIntMod(UInt hi,UInt lo,UInt den); // hi < den

template <class UInt>
UInt UIntModMul(UInt a,UInt b,UInt mod); // a,b < mod 

template <class UInt>
UInt UIntModMac(UInt s,UInt a,UInt b,UInt mod); // s,a,b < mod

template <class UInt>
UInt UIntSqRoot(UInt S);

UIntNeg() calls UIntFunc<UInt>::Neg().

UIntBitsOf() calls UIntFunc<UInt>::BitsOf().

UIntAdd() adds the second argument to the first one.

UIntSub() subtracts the second argument from the first one.

UIntInc() increments the argument.

UIntDec() decrements the argument.

Each of these functions returns the carry/borrow condition flag.

UIntMulDiv() calls UIntFunc<UInt>::UIntMulDiv().

UIntDiv() calls UIntFunc<UInt>::UIntDiv().

UIntMod() calls UIntFunc<UInt>::UIntMod().

UIntModMul() calls UIntFunc<UInt>::UIntModMul().

UIntModMac() calls UIntFunc<UInt>::UIntModMac().

UIntSqRoot() calls UIntFunc<UInt>::UIntSqRoot().