Project

General

Profile

« Previous | Next » 

Revision 92782e4a

Added by David Sorber over 4 years ago

Additional improvements to the fixed type. Also added a few good test
cases.

View differences:

software/fixed/fixed.h
#ifndef __FIXED_H_
#define __FIXED_H_
#define __STDC_FORMAT_MACROS
#include <cctype>
#include <cmath>
#include <cinttypes>
#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <iomanip>
......
#include <sstream>
#include <stdexcept>
#include <type_traits>
#include <map>
#ifdef USE_INT128
#include "int128.h"
#endif
#if __GNUC__ >= 3
#define __unlikely(cond) __builtin_expect((cond), 0)
......
static constexpr FractionalType MIN_FRACTIONAL_VALUE = 0;
static const uint64_t SCALE_VALUES[20];
static const std::map<uint64_t, uint32_t> DIGIT_LOOKUP_TABLE;
// Constructors
fixed()
......
m_fractional(__checkFracOverflow(fractionalVal))
{
// Scale the fractional value appropriately
uint32_t idx = 0;
for (; idx < fractional_decimal_digits; ++idx)
{
if (SCALE_VALUES[idx] > m_fractional)
{
break;
}
}
m_fractional = __checkFracOverflow(
m_fractional * SCALE_VALUES[fractional_decimal_digits - idx]);
m_fractional = __checkFracOverflow(m_fractional *
getFracScaleValue(m_fractional));
}
fixed(IntegerType integerVal, FractionalType fractionalVal, uint32_t leadingZeros)
: m_integer(__checkIntOverflow(integerVal)),
m_fractional(__checkFracOverflow(fractionalVal))
{
// Scale the fractional value appropriately
m_fractional = __checkFracOverflow(m_fractional *
getFracScaleValue(m_fractional,
leadingZeros));
}
// Default copy constructor, and assignment operator
fixed(const fixed&) = default;
fixed& operator=(const fixed&) = default;
// Reassign value to type
// Reassign value to type with a prescaled fractional value.
void assign(IntegerType integerVal, FractionalType fractionalVal)
{
m_integer = __checkIntOverflow(integerVal);
// Scale the fractional value appropriately
uint32_t idx = 0;
for (; idx < fractional_decimal_digits; ++idx)
{
if (SCALE_VALUES[idx] > fractionalVal)
{
break;
}
}
// Fractional value is prescaled to fractional type precision
m_fractional = __checkFracOverflow(fractionalVal);
}
m_fractional = __checkFracOverflow(
fractionalVal * SCALE_VALUES[fractional_decimal_digits - idx]);
// Assign a new value with an *unscaled* fractional part (NOTE: use the
// "leadingZeros" parameter to represent the number of leading zeros in the
// unscaled fractional part.
void assignUnscaledFrac(
IntegerType integerVal,
FractionalType fractionalVal,
uint32_t leadingZeros=0)
{
m_integer = __checkIntOverflow(integerVal);
// Scale the fractional value appropriately
m_fractional = __checkFracOverflow(fractionalVal *
getFracScaleValue(fractionalVal,
leadingZeros));
}
// Parse value from string input
uint32_t parse(const char* input)
{
char* endPtr = nullptr;
//~ m_integer = __checkIntOverflow(strtoll(input, &endPtr, 10));
m_integer = __checkIntOverflow(strto_inttype(input, &endPtr, 10));
m_fractional = 0;
......
{
char* fracEndPtr = nullptr;
FractionalType fracTemp =
//~ __checkFracOverflow(strtoull(endPtr + 1, &fracEndPtr, 10));
__checkFracOverflow(strto_fractype(endPtr + 1, &fracEndPtr, 10));
uint32_t fracLen = (fracEndPtr - endPtr) - 1;
fracLen = fractional_decimal_digits - fracLen;
m_fractional = __checkFracOverflow(fracTemp * SCALE_VALUES[fracLen]);
......
return (endPtr - input);
}
void absval()
{
m_integer = abs(m_integer);
}
constexpr inline fixed operator-() const noexcept = delete;
constexpr inline fixed operator!() const noexcept = delete;
constexpr inline fixed operator~() const noexcept = delete;
......
friend constexpr inline bool operator>=(
const fixed<I, F, STI, STF>& x, const fixed<I, F, STI, STF>& y) noexcept;
// Divide by unsigned int
template<typename I, typename F, typename STI, typename STF>
friend constexpr inline fixed<I, F, STI, STF> operator/(
const fixed<I, F, STI, STF>& x, const uint64_t& y);
// Output stream operator
template<typename I, typename F, typename STI, typename STF>
friend inline std::ostream& operator<<(
std::ostream& os, const fixed<I, F, STI, STF>& rhs);
private:
static StrToIntegerTypeFunc strto_inttype;
......
}
return fractionalVal;
}
public:
// Helper function to get the approprate scale value for an unscaled input
// value of the fractional type
static inline FractionalType getFracScaleValue(
FractionalType value,
uint32_t leadingZeros=0)
{
uint32_t index = fractional_decimal_digits -
(DIGIT_LOOKUP_TABLE.upper_bound(value)->second +
leadingZeros);
return SCALE_VALUES[index];
}
public:
IntegerType m_integer;
FractionalType m_fractional;
};
......
}
};
#ifdef USE_INT128
// Functor for calling strtoll_128()
struct strtoll_128_ftor {
inline int64_t operator()(const char* str, char** str_end, int base)
{
//~ return strtoll_128(str, str_end, base);
return strtoll_128_b10opt(str, str_end, base);
}
};
// Functor for calling strtoull_128()
struct strtoull_128_ftor {
inline uint64_t operator()(const char* str, char** str_end, int base)
{
//~ return strtoull_128(str, str_end, base);
return strtoull_128_b10opt(str, str_end, base);
}
};
#endif
// Predefined types
using fixed_8_8 = fixed<int8_t, uint8_t, strtoll_ftor, strtoull_ftor>;
using fixed_8_16 = fixed<int8_t, uint16_t, strtoll_ftor, strtoull_ftor>;
......
using fixed_64_32 = fixed<int64_t, uint32_t, strtoll_ftor, strtoull_ftor>;
using fixed_64_64 = fixed<int64_t, uint64_t, strtoll_ftor, strtoull_ftor>;
#ifdef USE_INT128
using fixed_128_128 = fixed<int128_t, uint128_t, strtoll_128_ftor, strtoull_128_ftor>;
#endif
// Precomputed scale value constants
template<typename I, typename F, typename STI, typename STF>
const uint64_t fixed<I, F, STI, STF>::SCALE_VALUES[20] =
......
/* 19 */ 10000000000000000000ULL
};
template<typename I, typename F, typename STI, typename STF>
const std::map<uint64_t, uint32_t> fixed<I, F, STI, STF>::DIGIT_LOOKUP_TABLE{
{1ULL, 0},
{10ULL, 1},
{100ULL, 2},
{1000ULL, 3},
{10000ULL, 4},
{100000ULL, 5},
{1000000ULL, 6},
{10000000ULL, 7},
{100000000ULL, 8},
{1000000000ULL, 9},
{10000000000ULL, 10},
{100000000000ULL, 11},
{1000000000000ULL, 12},
{10000000000000ULL, 13},
{100000000000000ULL, 14},
{1000000000000000ULL, 15},
{10000000000000000ULL, 16},
{100000000000000000ULL, 17},
{1000000000000000000ULL, 18},
{std::numeric_limits<uint64_t>::max(), 19} // Special case for uint64_t max value
};
template<typename I, typename F, typename STI, typename STF>
constexpr inline bool operator==(
const fixed<I, F, STI, STF>& x, const fixed<I, F, STI, STF>& y) noexcept
......
constexpr inline fixed<I, F, STI, STF> operator-(
const fixed<I, F, STI, STF>& x, const fixed<I, F, STI, STF>& y) noexcept = delete;
// Multiplication
// Multiplication -- not yet supported
template<typename I, typename F, typename STI, typename STF>
constexpr inline fixed<I, F, STI, STF> operator*(
const fixed<I, F, STI, STF>& x, const fixed<I, F, STI, STF>& y) noexcept = delete;
......
constexpr inline fixed<I, F, STI, STF> operator/(
const fixed<I, F, STI, STF>& x, const fixed<I, F, STI, STF>& y) noexcept = delete;
// Division by unsigned int
template<typename I, typename F, typename STI, typename STF>
constexpr inline fixed<I, F, STI, STF> operator/(
const fixed<I, F, STI, STF>& x, const uint64_t& y)
{
fixed<I, F, STI, STF> newVal;
newVal.m_integer = x.m_integer / y;
newVal.m_fractional = x.m_integer % y;
newVal.m_fractional *= x.getFracScaleValue(newVal.m_fractional);
newVal.m_fractional += x.m_fractional / y;
return newVal;
}
// Stream output
template<typename I, typename F, typename STI, typename STF>
inline std::ostream& operator<<(std::ostream& os, const fixed<I, F, STI, STF>& rhs)
{
#if 0
// Print full fractional precision always (even with trailing zeros)
return os << std::fixed << rhs.m_integer << "."
<< std::setw(fixed<I, F, STI, STF>::fractional_decimal_digits)
<< std::setfill('0') << rhs.m_fractional;
#else
// Print fractional part without trailing zeros
char buffer[fixed<I, F, STI, STF>::fractional_decimal_digits + 1]{};
std::snprintf(buffer, fixed<I, F, STI, STF>::fractional_decimal_digits + 1,
"%" PRIu64, rhs.m_fractional);
// NOTE: if fractional part is zero always print at least one zero
int idx = fixed<I, F, STI, STF>::fractional_decimal_digits;
bool found = false;
for (; idx >= 0; --idx)
{
if (std::isdigit(buffer[idx]) && buffer[idx] != '0')
{
found = true;
break;
}
}
if (found)
{
buffer[idx + 1] = '\0';
}
uint32_t leadingZeros =
fixed<I, F, STI, STF>::fractional_decimal_digits -
fixed<I, F, STI, STF>::DIGIT_LOOKUP_TABLE.upper_bound(rhs.m_fractional)->second;
// Output any leading zeros
os << std::fixed << rhs.m_integer << ".";
for (uint32_t idx = 0; idx < leadingZeros; ++idx)
{
os << "0";
}
return os << buffer;
#endif
}
#endif // FIXED_H_
software/fixed/fixed_test.cc
#include <cstdint>
#include <limits>
#include <random>
#include <sstream>
#include <string>
#include <vector>
#define BOOST_TEST_MAIN 1
#include <boost/test/unit_test.hpp>
......
BOOST_AUTO_TEST_CASE(t0)
{
// Check overall type sizes
/* TEST CASE 0: Check storage sizes (in bytes) of all predefined fixed
* point types.
*/
fixed_8_8 f_8_8;
fixed_8_32 f_8_32;
fixed_8_16 f_8_16;
......
BOOST_CHECK(sizeof(f_64_32) == 16);
BOOST_CHECK(sizeof(f_64_64) == 16);
}
BOOST_AUTO_TEST_CASE(t1)
{
/* TEST CASE 1: Test basic comparisons
*/
fixed_64_64 val1(100, 1, 0);
fixed_64_64 val2(100, 1);
BOOST_CHECK( (val1 == val2));
BOOST_CHECK(! (val1 != val2));
BOOST_CHECK(! (val1 > val2));
BOOST_CHECK(! (val1 < val2));
BOOST_CHECK( (val1 >= val2));
BOOST_CHECK( (val1 <= val2));
val2.assignUnscaledFrac(100, 1, 18);
BOOST_CHECK(! (val1 == val2));
BOOST_CHECK( (val1 != val2));
BOOST_CHECK( (val1 > val2));
BOOST_CHECK(! (val1 < val2));
BOOST_CHECK( (val1 >= val2));
BOOST_CHECK(! (val1 <= val2));
}
BOOST_AUTO_TEST_CASE(t2)
{
/* TEST CASE 2: Test parsing with leading zeros.
*/
fixed_64_64 val1;
fixed_64_64 val2;
// 1
val1.assign(1, 2000000000000000000);
val2.parse("1.2");
BOOST_CHECK(val1 == val2);
// 2
val1.assign(1, 200000000000000000);
val2.parse("1.02");
BOOST_CHECK(val1 == val2);
// 3
val1.assign(1, 20000000000000000);
val2.parse("1.002");
BOOST_CHECK(val1 == val2);
// 4
val1.assign(1, 2000000000000000);
val2.parse("1.0002");
BOOST_CHECK(val1 == val2);
// 5
val1.assign(1, 200000000000000);
val2.parse("1.00002");
BOOST_CHECK(val1 == val2);
// 6
val1.assign(1, 20000000000000);
val2.parse("1.000002");
BOOST_CHECK(val1 == val2);
// 7
val1.assign(1, 2000000000000);
val2.parse("1.0000002");
BOOST_CHECK(val1 == val2);
// 8
val1.assign(1, 200000000000);
val2.parse("1.00000002");
BOOST_CHECK(val1 == val2);
// 9
val1.assign(1, 20000000000);
val2.parse("1.000000002");
BOOST_CHECK(val1 == val2);
// 10
val1.assign(1, 2000000000);
val2.parse("1.0000000002");
BOOST_CHECK(val1 == val2);
// 11
val1.assign(1, 200000000);
val2.parse("1.00000000002");
BOOST_CHECK(val1 == val2);
// 12
val1.assign(1, 20000000);
val2.parse("1.000000000002");
BOOST_CHECK(val1 == val2);
// 13
val1.assign(1, 2000000);
val2.parse("1.0000000000002");
BOOST_CHECK(val1 == val2);
// 14
val1.assign(1, 200000);
val2.parse("1.00000000000002");
BOOST_CHECK(val1 == val2);
// 15
val1.assign(1, 20000);
val2.parse("1.000000000000002");
BOOST_CHECK(val1 == val2);
// 16
val1.assign(1, 2000);
val2.parse("1.0000000000000002");
BOOST_CHECK(val1 == val2);
// 17
val1.assign(1, 200);
val2.parse("1.00000000000000002");
BOOST_CHECK(val1 == val2);
// 18
val1.assign(1, 20);
val2.parse("1.000000000000000002");
BOOST_CHECK(val1 == val2);
// 19
val1.assign(1, 2);
val2.parse("1.0000000000000000002");
BOOST_CHECK(val1 == val2);
}
BOOST_AUTO_TEST_CASE(t3)
{
/* TEST CASE 3: Test parsing and printing randomly generated values
*/
using theType = fixed_64_64;
uint32_t NUMBER = 1000000;
uint64_t SEED = 0xDEADBEEF123;
std::random_device dev;
std::mt19937 rng;
rng.seed(SEED);
std::uniform_int_distribution<std::mt19937::result_type> intDigits(1, theType::integer_decimal_digits);
std::uniform_int_distribution<std::mt19937::result_type> fracDigits(1, theType::fractional_decimal_digits);
std::uniform_int_distribution<std::mt19937::result_type> digits(0, 9);
// Generate NUMBER worth of parsable decimal number strings
std::vector<std::string> values;
for (uint32_t idx = 0; idx < NUMBER; ++idx)
{
std::ostringstream output;
// Generate random integer number digits
for (uint32_t integerIdx = 0; integerIdx < intDigits(rng); ++integerIdx)
{
int digit = digits(rng);
// Integer part cannot start with a zero
if (integerIdx == 0)
{
while (digit == 0)
{
digit = digits(rng);
}
}
output << digit;
}
output << ".";
// Generate random fractional number digits
int numFracDigits = fracDigits(rng);
for (uint32_t fracIdx = 0; fracIdx < numFracDigits; ++fracIdx)
{
int digit = digits(rng);
// Fractional part cannot end with a zero
if (fracIdx == (numFracDigits - 1))
{
while (digit == 0)
{
digit = digits(rng);
}
}
output << digit;
}
values.emplace_back(output.str());
//~ std::cout << "VAL: " << values.back() << std::endl;
}
// Now validate that the output of the parsed
theType fixedValue;
std::ostringstream output;
for (auto& value : values)
{
fixedValue.parse(value.c_str());
output << fixedValue;
//~ std::cout << "TEST: " << output.str() << " -- " << value << std::endl;
BOOST_CHECK(output.str() == value);
output.str("");
}
}
BOOST_AUTO_TEST_CASE(t4)
{
/* TEST CASE 4: Basic test division by unsigned integer
*/
fixed_64_64 val1(18, 55, 0);
fixed_64_64 val2(0, 1855, 0);
fixed_64_64 answer = val1 / 100;
BOOST_CHECK(answer == val2);
}
software/fixed/parse_test.cc
long double value = 0.0;
fixed_64_64 fvalue;
//~ fixed_128_128 f128value;
// 0) strtold()
if (parseType == 0)
......
<< " ms" << std::endl;
}
#endif
#if 0
// 5)
else if (parseType == 5)
{
......
auto start = std::chrono::system_clock::now();
for (auto& strValue : values)
{
fvalue.parse(strValue.c_str());
//~ std::cout << "In: " << strValue << " -- Out: " << fvalue << std::endl;
f128value.parse(strValue.c_str());
std::cout << "In: " << strValue << " -- Out: " << f128value << std::endl;
}
auto end = std::chrono::system_clock::now();
auto diff = end - start;
......
<< " ms" << std::endl;
}
#endif
else
{
std::cerr << "ERROR: invalid parse type: " << parseType << std::endl;
software/fixed/util.py
#!/usr/bin/python3
import sys
def generate_t1():
""" Generate test case t1.
"""
num = 18
int_digit = '1'
frac_digit = '2'
for idx in range(num + 1):
print(f' // {idx + 1}')
frac_val = f"{frac_digit}{'0' * (num - idx)}"
print(f" val1.assign({int_digit}, {frac_val});")
frac_val = f"{'0' * idx}{frac_digit}"
print(f" val2.parse(\"{int_digit}.{frac_val}\");")
print(' BOOST_CHECK(val1 == val2);\n')
def main():
print('Gen Util')
if __name__ == '__main__':
sys.exit(main())

Also available in: Unified diff