6
\$\begingroup\$

I encountered a pesky error in Code::Blocks: the conversions functions (stod, stof, stoi, ...) are not linked correctly.

I wanted to learn how to convert double or floats starting from a string. I started writing down a version of it, but I couldn't get it right even if I had understood the concept. Then I came upon this well explained algorithm.

The algorithm is in C style, so I tried to transform it into a C++ stylish format. I basically copied the algorithm and added a class for integer96 operations. Yet I would like to improve my C++ coding style, so I could use advices!


StringToDouble.h

This is composed of a prepNumber, Parser, converter and stod functions

prepNumber is a structure used by Parser and converter. Parser parses the string into a prepNumber, converter converts it to double.

#ifndef STRINGTODOUBLE_H
#define STRINGTODOUBLE_H

#include <string>
#include <inttypes.h>
#include "int_96.h"

/*prepNumber: helper class storing the x * 10 ^ (y) number*/

class prepNumber{
public:

    prepNumber();

    bool negative; // negative flag for the negative
    int32_t exponent; // store the exponent of the numnber v= 10^e * x  e (-327:308)
    uint64_t mantissa; // x in the above form

};

/*Parser: parses the string into prepNumber*/

class Parser{
public:
    Parser();

    prepNumber run(std::string init_string);

    int get_machine_state();
    int get_parser_state();

    static int const PARSER_OK = 0;
    // parser states...

private:
/*state machine states*/
    static int const FSM_A = 0;
    //...

    int state;
    int parser_state;
};

/*converter:  converts the number into the double*/

double converter(prepNumber pn);

/*stod: wrapping function dealing with parse errors*/

double stod(std::string init_string);

#endif // STRINGTODOUBLE_H

StringToDouble.cpp

Constants and helpers:

#include "StringtoDouble.h"

/* Constants*/

#define DPOINT '.'
#define DIGITS 18 //significant digits of the number (mantissa)

#ifndef INT_MAX
#define INT_MAX 2147483647
#endif // INT_MAX

#define DOUBLE_PLUS_ZERO          0x0000000000000000ULL
#define DOUBLE_MINUS_ZERO         0x8000000000000000ULL
#define DOUBLE_PLUS_INFINITY      0x7FF0000000000000ULL
#define DOUBLE_MINUS_INFINITY     0xFFF0000000000000ULL

/* Helper functions */

// spaces are: 0x09 : 0x13 \t\n\r... 0x20= ' '
inline bool is_space(const char& x){
    return (x >= 0x09 && x <= 0x13) || x == 0x20;
}

inline bool is_digit(const char& x){
    return x >= '0' && x <= '9';
}

inline bool is_exp(const char& x){
    return (x == 'e') || (x == 'E');
}

// scrolls the string pointer
inline char GETC(std::string::iterator& s){ return *s++; }

/* prepNumber */

prepNumber::prepNumber() : negative(false), exponent(0), mantissa(0) {}

Parser implementation

/* Parser */

Parser::Parser(){}

Parser::get_machine_state(){return state;}
Parser::get_parser_state() {return parser_state;}

prepNumber Parser::run(std::string init_string){
    std::string::iterator s = init_string.begin();

    parser_state = PARSER_OK; // reset the result
    state = FSM_A; // set the state to A to enter the cycle
    int c = ' '; // set c to ' ' to trigger getc.
    int digx  = 0;
    bool expneg = false;
    int32_t expexp = 0;
    prepNumber pn;

    while(state != FSM_STOP){
        // state machine... see github or orginal code
    }

    if(expneg) {expexp = -expexp;}
    pn.exponent += expexp;

    // if mantissa is 0 or result < 10e-328 (double limit)
    if(pn.mantissa == 0 || pn.exponent < -328){
        parser_state = ((pn.negative)? PARSER_MZERO : PARSER_PZERO);
    }

    if(pn.exponent > 309){
        parser_state = ((pn.negative)? PARSER_MINF : PARSER_PINF);
    }

    return pn;
}

Converter implementation

/* converter */

// helps conversion between uint64 and double
class HexDouble{
public:

    HexDouble(){u = 0;}

    void set(uint64_t n){u = n;}

    double get(){return d;}

private:
    union{
        double d;
        uint64_t u;
    };
};


double converter(prepNumber pn){

    int bin_exp = 92;
    int_96 r;
    int_96 s((uint64_t)pn.mantissa);

    // multiply by 10 till significand get to the left most bit
    while(pn.exponent > 0){

        // multiplication by 10 (2^2 * 2^8) = (n<<1 + n<<3)
        int_96 q = (s << 1) + (s << 3);
        pn.exponent--;

        //if the multiplication overflows in the last 4 of the 96 bits
        // then increase the binary exponent
        while(q.get_last_bits()){
            q >>= 1;
            bin_exp++;
        }
    }

    // divide by 10 to get the significand to the left most bit
    while(pn.exponent < 0){
        while(!s.get_last_bit()){
            s <<= 1;
            bin_exp--;
        }

        // divide by 10
        s.divide_by_10();
        pn.exponent++;
    }

    // correct for the last 4 bits;
    if(s != 0){
        while(!s.get_last_bits()){
            s<<=1;
            bin_exp--;
        }
    }

    // prepare the number <uint64 to double>
    HexDouble hd;

    //boundary checking
    bin_exp += 1023; // addin bias

    if(bin_exp > 2046){
        hd.set((pn.negative)? DOUBLE_MINUS_INFINITY : DOUBLE_PLUS_INFINITY);
    }
    else if(bin_exp < 1){
        hd.set((pn.negative)? DOUBLE_MINUS_ZERO : DOUBLE_PLUS_ZERO);
    }
    else if(s != 0){
        uint64_t binexs2 = (uint64_t) bin_exp;
        binexs2 <<= 52;

        // construct complete mantissa
        uint64_t signbit = (pn.negative)? (1ULL << 63) : 0;
        uint64_t q = signbit | binexs2 | s.get_mantissa();
        hd.set(q);
    }

    return hd.get();
}

I would appreciate any comment about style, clarity and exposition. I deleted some parts of the code in order to spare space and reading time yet the code is available at (https://github.com/Pella86/string_to_double)

\$\endgroup\$
  • \$\begingroup\$ Are the "last" bits of int_96 the 4 most significant bits or the least? (s)(MMMm)bbb....bbbb(llll). I suspect it is the most significant. Then is that sMMM or MMMm bits? Is the result signed? Maybe a ref to int_96.h would help. \$\endgroup\$ – chux May 1 '18 at 13:35
10
\$\begingroup\$

Don't use #define!!!

There are much better techniques for all use cases of #define in C++.

#define DPOINT '.'
// Why not
char constexpr dPoint = '.';

#define DIGITS 18 //significant digits of the number (mantissa)
// Why not
int constexpr digits = 18;

Not sure this is allowed (pretty sure its illegal).

#ifndef INT_MAX
#define INT_MAX 2147483647
#endif // INT_MAX

Also this value in C++ is retieved from std::numerical_limits<int>

You are making a whole bunch of assumptions about the shape of a floating point number here. None of this is guaranteed by the standard.

#define DOUBLE_PLUS_ZERO          0x0000000000000000ULL
#define DOUBLE_MINUS_ZERO         0x8000000000000000ULL
#define DOUBLE_PLUS_INFINITY      0x7FF0000000000000ULL
#define DOUBLE_MINUS_INFINITY     0xFFF0000000000000ULL

Your helper function all have standard version.
I would also put money on the standard version being faster than your implementation. You chose the slowest way to implement these functions.

// spaces are: 0x09 : 0x13 \t\n\r... 0x20= ' '
inline bool is_space(const char& x){
    return (x >= 0x09 && x <= 0x13) || x == 0x20;
}

inline bool is_digit(const char& x){
    return x >= '0' && x <= '9';
}

inline bool is_exp(const char& x){
    return (x == 'e') || (x == 'E');
}

I can see where you are going to go with these functions. But it looks like you are only going to support the American English way to represent floating point numbers. Not all locals will write floating point numbers the same way.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the constexpr, I will use it, I wanted to avoid including too many libraries, this is why the redefinitions. With the complete std library at hand this code could be refactored greatly. This the reason of INT_MAX definition, which if I understood correctly will take any definition defined somewhere else, yet for the stand alone cpp file it will need a definition somewhere. I maybe should put the number explicitly in the code, since maybe is more dependent of 32 bits then intmax. \$\endgroup\$ – Pella86 Apr 25 '18 at 19:54
  • \$\begingroup\$ "There are much better techniques for all use cases of #define in C++." That's a bit hyperbolic. I would say "for most use cases", or maybe even "nearly all", but not "all". An assert macro comes to mind. \$\endgroup\$ – Cris Luengo Apr 29 '18 at 1:53
  • \$\begingroup\$ @CrisLuengo We have static_assert. Which is even better than assert (as its compile time) and for things that are detected at runtime we have throw. The macro assert() is basically useless (even before C++) because it causes different behaviors in debug and production code. But we can implement assert() in modern C++ using normal inline functions. \$\endgroup\$ – Martin York Apr 30 '18 at 1:55
  • \$\begingroup\$ The preprocessor is good for conditional compilation associated with OS/Compiler/Platform specific situation. But that should not affect the average programmer as these use cases are best defined below the standard API layer of most libraries. \$\endgroup\$ – Martin York Apr 30 '18 at 1:59
  • \$\begingroup\$ Normal inline functions cannot use __LINE__ or __func__ to tell you where the problem is. I'm sure there are alternatives, but I find these so very handy. \$\endgroup\$ – Cris Luengo Apr 30 '18 at 5:13
8
\$\begingroup\$

I'm not sure you're allowed to define your own INT_MAX like this:

#ifndef INT_MAX
#define INT_MAX 2147483647
#endif // INT_MAX

I recommend you just include <climits> rather than trying to adapt to your implementation's choice whether or not to pull it in with another standard header.

Other improvements to headers:

  • You should prefer <cinttypes> over <inttypes.h> for new code. Use the C-compatibility headers only in contexts that might be parsed by a C compiler.
  • What's "int_96.h", and why does StringtoDouble.h need it? In fact, why does the header need anything more than a declaration of strtod()?

Your is_space() function seems to assume ASCII encoding of input. It's probably better to write:

inline constexpr bool is_space(const char c)
{
     switch (c) {
     case ' ':
     case '\t':
     case '\n':
     case '\r':
     case '\f':
     case '\v':
         return true;
     default:
         return false;
}

Note pass-by-value - const ref is a poor choice in this case (though if inlined, likely to compile to the same code anyway).

\$\endgroup\$
  • \$\begingroup\$ Thanks for the comment, int_96.h is the implementation of the int_96 type that is just 3 integers bound together, in order to not lose mantissa precision. \$\endgroup\$ – Pella86 Apr 25 '18 at 15:38
  • 2
    \$\begingroup\$ The point is that it's needed only by the implementation, not by the users of the function, so it shouldn't be included from the public header. \$\endgroup\$ – Toby Speight Apr 25 '18 at 15:42
6
\$\begingroup\$

You are passing the string by value.

prepNumber run(std::string init_string);

there is no reason to copy the string.

    std::string::iterator s = init_string.begin();

In fact, since you are just using iterators to look through the input, you can use the new std::string_view and support std::string and low-level string literals with the same function without having to convert.

In the above line, you should be using auto.

using std::begin;
  ⋮
auto s = begin(init_string);

and get in the habit of using the non-member versions. These are to be called unqualified, so you need to import into your scope first (known as the "two step"). That is not needed here, but that will be needed for generic code, and also to keep your code from breaking when other parts of the program change.


double get(){return d;}

you are missing const. Member functions that are accessors should always be declared const.

This HexDouble class seems like a lot of work over just using the union in your code. Since it’s a local class used in one place, just use the union.

But, technically this is undefined behavior. There is a long history of using unions and casts in just this way, and real compilers go to some trouble to recognize this and not optimize it away to nonsense. But really, the compiler is allowed to see that you’re reading from a variant of the union that was never set, and assume that this path in the code is never taken.


uint64_t binexs2 = (uint64_t) bin_exp;

Why do you need a cast at all? If you do, don’t use an old C-style cast.


int_96 s((uint64_t)pn.mantissa);

Again, that’s odd… why do you explicitly cast the value to a different type before giving it to the constructor? I would expect

int_96 s { pn.mantissa };

(note the modern initialization syntax) to work without complaint and do the same thing. Any integral type that is a subset of int64_t should just work without warnings. If your class does something different for int64_t and int32_t then there is something wonky about the class.

\$\endgroup\$
  • \$\begingroup\$ you actually hit the knife in the wound. I had a problem of ambiguity. MyClass::MyClass(const uint32_t& t); MyClass::MyClass(const uint64_t& t); >>>>>>>> uint64_t n; MyClass(n); gave an ambiguity error. Even when I explicitly casted the already uint64_t mantissa. I will try with the new initialization, thanks for the suggestions. \$\endgroup\$ – Pella86 Apr 27 '18 at 9:35
  • \$\begingroup\$ I see. Why does it take a simple integer type by const reference? That just doesn't make sence. Why the 2 constructors? (might be worth a new post just for that) \$\endgroup\$ – JDługosz Apr 27 '18 at 12:51
2
\$\begingroup\$

The iostream libraries know how to parse floats.
So you can write your own lexical_cast() very easily.

 #include <sstream>

 // Lexical Cast:
 // Converts any input type to a specified output type.
 template<typename R, template T>
 R lexical_cast(T const& input)
 {
     std::stringstream  stream;
     R    result;

     stream << input;
     stream >> result;
     return result;
 }

Usage:

 #include <iostream>
 int main()
 {
     double d = lexical_cast<double>("12345.456e6");
     std::cout << d << "\n";
 }

If you want to go and do some extra validation:

 // Lexical Cast:
 // Converts any input type to a specified output type.
 template<typename R, typename T, typename F = decltype(std::skipws)>
 R lexical_cast(T const& input, bool mustUseAllInput = true, F filter = std::skipws)
 {
     std::stringstream  stream;
     R    result;

     bool succ = false;
     if ((stream << input) && (stream >> result)) {
         succ = true;
     }

     char x;
     if (succ && mustUseAllInput && (stream >> filter >> x)) {
         succ = false; // Unused data on input
     }

     if (!succ) {
        throw std::runtime_error("Parse Failure");
     }
     return result;
 }
\$\endgroup\$
  • 1
    \$\begingroup\$ The whole point of the code in question is too understand how dtoa and atod work in detail. Therefore, suggesting to use the high-level interface misses the point. \$\endgroup\$ – Roland Illig Apr 25 '18 at 20:47
  • \$\begingroup\$ @RolandIllig: That's not what the OP is about. This code shows the futility of attempting to do it. \$\endgroup\$ – Martin York Apr 25 '18 at 21:41
  • \$\begingroup\$ "I wanted to learn how to convert double or floats starting from a string". It was meant as I want to learn how to do the process low-level. I could have used many hacks to actually get a double back. Yet thanks for the solution because that should be portable and doesn't lose precision! Seems pretty useful. \$\endgroup\$ – Pella86 Apr 27 '18 at 9:28
2
\$\begingroup\$

Bug: s not updated.

while(pn.exponent > 0){
    int_96 q = (s << 1) + (s << 3);
    pn.exponent--;

    while(q.get_last_bits()){
        q >>= 1;
        bin_exp++;
    }
    s = q;  // missing , add this
}

Weakness: unnecessary loss of accuracy.

The above q >>= 1; simply throws away the least significant bit of q. To improve accuracy, this division would benefit with a "round to nearest even". About 1/2 the time when a bit is shifted out, the quotient is incremented.

Example code to demo improvement.

        // q >>= 1;
        if (q & 1) {
          q >>= 1;
          if (q & 1) q++;
        } else {
          q >= 1;
        }

Bug

Code does not form sub-normals correctly.

else if(bin_exp < 1){
  // Add code to form sub-normals.
  ...
  // Then if truly too small return 0
  hd.set((pn.negative)? DOUBLE_MINUS_ZERO : DOUBLE_PLUS_ZERO);
}

Weakness

Unnecessary loss of accuracy.

The unposted .get_mantissa() is unclear, yet it certainly is returning a truncated result. Instead of truncating the 96 bit values to 52(53), a better answer can be formed, like above by using "round to nearest even". This implies a potential increase in exponent. And an increase in exponent can lead to infinity.

// needs work
uint64_t q = signbit | binexs2 | s.get_mantissa();

These bugs imply insuffcient testing.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the thorough comment! What would you suggest to improve testing? Unit test? (github.com/grzegorz-kraszewski/stringtofloat#limitations) I think the algorithm actually works as the original guy intended with the rounding. The other comments I think are on point. \$\endgroup\$ – Pella86 May 3 '18 at 12:43
  • \$\begingroup\$ @Pella86 Yes testing with select strings and comparing results against your function and strtod(). Also form random strings in exponential notation of at least DBL_DECIMAL_DIG + 3 significant digits too. A good test may match the coding effort for the function-under-test. Concerning "original guy intended with the rounding" --> not quite as the algorithm doubles double, triple, and more rounding, so it is not proper round toward zero either. \$\endgroup\$ – chux May 3 '18 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.