Files CCore/inc/base/Quick.h CCore/src/base/Quick.cpp CCore/src/base/Quick.s
This part contains some "quick" functions. These functions may use hardware capabilities to accelerate its operations.
#ifndef CCore_inc_base_Quick_h
#define CCore_inc_base_Quick_h
#include <CCore/inc/base/PlatformBase.h>
namespace CCore {
namespace Quick {
/* consts */
const bool ScanLSBitIsFast = false ;
const bool ScanMSBitIsFast = false ;
/* types */
using ScanUInt = .... ; // unsigned integral type
/* functions */
unsigned ScanLSBit(ScanUInt value) noexcept;
unsigned ScanMSBit(ScanUInt value) noexcept;
uint16 ByteSwap16(uint16 value) noexcept;
uint32 ByteSwap32(uint32 value) noexcept;
uint64 ByteSwap64(uint64 value) noexcept;
/* classes */
template <unsigned UIntBits> struct UIntMulSelect;
template <class UInt> struct UIntMulFunc;
/* struct UIntMulSelect<unsigned UIntBits> */
template <>
struct UIntMulSelect<8>
{
using ExtType = uint16 ;
enum { IsDoubleType = true };
};
template <>
struct UIntMulSelect<16>
{
using ExtType = uint32 ;
enum { IsDoubleType = true };
};
template <>
struct UIntMulSelect<32>
{
using ExtType = uint32 ;
enum { IsDoubleType = false };
};
template <>
struct UIntMulSelect<64>
{
using ExtType = uint64 ;
enum { IsDoubleType = false };
};
/* struct UIntMulFunc<uint32> */
template <>
struct UIntMulFunc<uint32>
{
using UInt = uint32 ;
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
static UInt MulDiv(UInt a,UInt b,UInt den); // hi(a*b)<den
struct DivMod
{
UInt div;
UInt mod;
DivMod(UInt hi,UInt lo,UInt den); // hi<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
};
/* struct UIntMulFunc<uint64> */
template <>
struct UIntMulFunc<uint64>
{
using UInt = uint64 ;
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
static UInt MulDiv(UInt a,UInt b,UInt den); // hi(a*b)<den
struct DivMod
{
UInt div;
UInt mod;
DivMod(UInt hi,UInt lo,UInt den); // hi<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
};
} // namespace Quick
} // namespace CCore
#endif
ScanLSBit() scans the argument for the less significant bit equals 1 and returns its number (bits are numbered from LSB to MSB).
ScanMSBit() scans the argument for the most significant bit equals 1 and returns its number (bits are numbered from LSB to MSB).
Both scan functions operate on the argument of the type ScanUInt, which must be an unsigned integral type. If the argument is null, the return value is not specified. Flags ScanLSBitIsFast and ScanMSBitIsFast are set, if the correspondent function has a fast implementation. The type ScanUInt should be a machine word size type, the wider it is the better.
ByteSwap16() swaps the bytes of the argument and returns the result. I.e. if the argument consists of the bytes (b0,b1), then the result is (b1,b0).
ByteSwap32() swaps the bytes of the argument and returns the result. I.e. if the argument consists of the bytes (b0,b1,b2,b3), then the result is (b3,b2,b1,b0).
ByteSwap64() swaps the bytes of the argument and returns the result. I.e. if the argument consists of the bytes (b0,b1,b2,b3,b4,b5,b6,b7), then the result is (b7,b6,b5,b4,b3,b2,b1,b0).
The rest is to support integer multiplicative operations. This is done using the structure templates UIntMulSelect and UIntMulFunc. These structures are not defined itself, but its specializations must be given.
UIntMulSelect must be specialized for the four following values: 8, 16, 32, 64 as following:
template <>
struct UIntMulSelect<N>
{
using ExtType = .... ; // unsigned integral type
enum { IsDoubleType = .... }; // true or false
};
ExtType is some unsigned integral type. Either this type has the bit width greater or equal than 2*N and IsDoubleType is assigned to true, or IsDoubleType is false and ExtType is any unsigned integral type. In the first case extended multiplicative operations for the type uintN are implemented using the operations on the type ExtType. Otherwise the specialization UIntMulFunc<uintN> must be given. Such specialization must provide the following:
template <>
struct UIntMulFunc<uintN>
{
using UInt = uintN ;
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
static UInt MulDiv(UInt a,UInt b,UInt den); // hi(a*b)<den
struct DivMod
{
UInt div;
UInt mod;
DivMod(UInt hi,UInt lo,UInt den); // hi<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
};
Mul() performs the full multiplication of the arguments a and b and returns the result in the pair hi and lo, where hi is the high part of the product and the lo is the lower part of the product.
Div() performs the division of the double-size value, given by the arguments hi and lo, by the third argument den. It is assumed, that hi < den, in such case the result is represented by the single-size value. Otherwise the behavior is unspecified (it may cause hardware trap).
Mod() calculates the remainder of the division of the double-size value, given by the arguments hi and lo, by the third argument den. It is assumed, that hi < den. Otherwise the behavior is unspecified (it may cause hardware trap).
MulDiv() multiplies a and b and divides the full double-size product by den. The high part of the product must be less than den, otherwise the behavior is unspecified (it may cause hardware trap).
DivMod() performs both operations Div() and Mod() and returns the result in the fields div and mod.
ModMul() calculates the product of the a and b by the module mod. It is assumed, that a and b < mod, otherwise the behavior is unspecified (it may cause hardware trap). The result is less than mod.
ModMac() calculates the expression s+a*b by the module mod. It is assumed, that a, b and s < mod, otherwise the behavior is unspecified (it may cause hardware trap). The result is less than mod.