String to double without std::stod

Question

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)

Answer 1

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.

Answer 2

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).

Answer 3

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.

Answer 4

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;
 }

Answer 5

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.