From 77fd5ff29861c6c87bcc9fc466d330b17a978c8a Mon Sep 17 00:00:00 2001 From: jaspervdg Date: Fri, 18 Jul 2008 19:10:58 +0000 Subject: [PATCH] Fix for PathString to prevent it from getting into a very, very long copying run and make it use minimumexponent. Plus some extra tests. --- src/streq.h | 6 ++ src/svg/path-string.cpp | 127 ++++++++++++------------- src/svg/path-string.h | 50 +++++++--- src/svg/svg-affine-test.h | 30 +++--- src/svg/svg-affine.cpp | 32 +++---- src/svg/svg-length.cpp | 88 ++++++++++------- src/svg/svg-path-test.h | 16 ++++ src/svg/svg.h | 2 +- src/trace/potrace/inkscape-potrace.cpp | 2 +- src/xml/quote-test.h | 14 +-- 10 files changed, 211 insertions(+), 156 deletions(-) diff --git a/src/streq.h b/src/streq.h index c790db9e8..06f78e1e5 100644 --- a/src/streq.h +++ b/src/streq.h @@ -11,6 +11,12 @@ streq(char const *a, char const *b) return std::strcmp(a, b) == 0; } +struct streq_rel { + bool operator()(char const *a, char const *b) const + { + return (std::strcmp(a, b) == 0); + } +}; #endif /* !INKSCAPE_STREQ_H */ diff --git a/src/svg/path-string.cpp b/src/svg/path-string.cpp index 68fcb26d8..6f6a1f20f 100644 --- a/src/svg/path-string.cpp +++ b/src/svg/path-string.cpp @@ -18,10 +18,21 @@ #include "prefs-utils.h" #include +// 1<=numericprecision<=16, doubles are only accurate upto (slightly less than) 16 digits (and less than one digit doesn't make sense) +// Please note that these constants are used to allocate sufficient space to hold serialized numbers +static int const minprec = 1; +static int const maxprec = 16; + +int Inkscape::SVG::PathString::numericprecision; +int Inkscape::SVG::PathString::minimumexponent; + Inkscape::SVG::PathString::PathString() : allow_relative_coordinates(0 != prefs_get_int_attribute("options.svgoutput", "allowrelativecoordinates", 1)), force_repeat_commands(0 != prefs_get_int_attribute("options.svgoutput", "forcerepeatcommands", 0)) -{} +{ + numericprecision = std::max(minprec,std::min(maxprec,prefs_get_int_attribute("options.svgoutput", "numericprecision", 8))); + minimumexponent = prefs_get_int_attribute("options.svgoutput", "minimumexponent", -8); +} void Inkscape::SVG::PathString::_appendOp(char abs_op, char rel_op) { bool abs_op_repeated = _abs_state.prevop == abs_op && !force_repeat_commands; @@ -29,6 +40,9 @@ void Inkscape::SVG::PathString::_appendOp(char abs_op, char rel_op) { unsigned int const abs_added_size = abs_op_repeated ? 0 : 2; unsigned int const rel_added_size = rel_op_repeated ? 0 : 2; if ( _rel_state.str.size()+2 < _abs_state.str.size()+abs_added_size && allow_relative_coordinates ) { + // Store common prefix + commonbase += _rel_state.str; + _rel_state.str.clear(); // Copy rel to abs _abs_state = _rel_state; _abs_state.switches++; @@ -38,6 +52,9 @@ void Inkscape::SVG::PathString::_appendOp(char abs_op, char rel_op) { // _rel_state.str.size()+rel_added_size < _abs_state.str.size()+2 // _abs_state.str.size()+2 > _rel_state.str.size()+rel_added_size } else if ( _abs_state.str.size()+2 < _rel_state.str.size()+rel_added_size ) { + // Store common prefix + commonbase += _abs_state.str; + _abs_state.str.clear(); // Copy abs to rel _rel_state = _abs_state; _abs_state.switches++; @@ -48,104 +65,78 @@ void Inkscape::SVG::PathString::_appendOp(char abs_op, char rel_op) { } void Inkscape::SVG::PathString::State::append(NR::Coord v) { - SVGOStringStream os; - os << ' ' << v; - str.append(os.str()); + str += ' '; + appendNumber(v); } void Inkscape::SVG::PathString::State::append(NR::Point p) { - SVGOStringStream os; - os << ' ' << p[NR::X] << ',' << p[NR::Y]; - str.append(os.str()); + str += ' '; + appendNumber(p[NR::X]); + str += ','; + appendNumber(p[NR::Y]); } -static void appendCoord(Glib::ustring& str, NR::Coord v, NR::Coord &rv) { - Inkscape::SVGOStringStream os; - os << v; - str += os.str(); - double c; - sp_svg_number_read_d(os.str().c_str(), &c); - rv = c; - /*{ - Inkscape::SVGOStringStream ost; - ost << rv; - if (ost.str()!=os.str()) { - FILE* file = fopen("pathstring log.txt","at"); - fprintf(file, "v: %g, rv: %g\n", v, rv); - fclose(file); - } - }*/ +void Inkscape::SVG::PathString::State::append(NR::Coord v, NR::Coord& rv) { + str += ' '; + appendNumber(v, rv); } void Inkscape::SVG::PathString::State::append(NR::Point p, NR::Point &rp) { str += ' '; - appendCoord(str, p[NR::X], rp[NR::X]); + appendNumber(p[NR::X], rp[NR::X]); str += ','; - appendCoord(str, p[NR::Y], rp[NR::Y]); + appendNumber(p[NR::Y], rp[NR::Y]); } -void Inkscape::SVG::PathString::State::append(NR::Coord v, NR::Coord& rv) { - str += ' '; - appendCoord(str, v, rv); -} - -// NOTE: The following two appendRelative methods will not be exact if the total number of digits needed +// NOTE: The following appendRelativeCoord function will not be exact if the total number of digits needed // to represent the difference exceeds the precision of a double. This is not very likely though, and if // it does happen the imprecise value is not likely to be chosen (because it will probably be a lot longer // than the absolute value). -static void appendRelativeCoord(Glib::ustring& str, NR::Coord v, NR::Coord r) { - Inkscape::SVGOStringStream os; - int precision = (int)os.precision(); - int digitsEnd = (int)floor(log10(std::min(fabs(v),fabs(r)))) - precision; // Position just beyond the last significant digit of the smallest (in absolute sense) number - double roundeddiff = floor((v-r)*pow(10.,-digitsEnd-1)+.5); - int numDigits = (int)floor(log10(fabs(roundeddiff)))+1; // Number of digits in roundeddiff +// NOTE: This assumes v and r are already rounded (this includes flushing to zero if they are < 10^minexp) +void Inkscape::SVG::PathString::State::appendRelativeCoord(NR::Coord v, NR::Coord r) { + int const minexp = minimumexponent-numericprecision+1; + int const digitsEnd = (int)floor(log10(std::min(fabs(v),fabs(r)))) - numericprecision; // Position just beyond the last significant digit of the smallest (in absolute sense) number + double const roundeddiff = floor((v-r)*pow(10.,-digitsEnd-1)+.5); + int const numDigits = (int)floor(log10(fabs(roundeddiff)))+1; // Number of digits in roundeddiff if (r == 0) { - os.precision(precision); - os << v; + appendNumber(v, numericprecision, minexp); } else if (v == 0) { - os.precision(precision); - os << -r; + appendNumber(-r, numericprecision, minexp); } else if (numDigits>0) { - os.precision(numDigits); - os << (v-r); + appendNumber(v-r, numDigits, minexp); } else { // This assumes the input numbers are already rounded to 'precision' digits - os << '0'; - } - str.append(os.str()); - { - /*double c; - sp_svg_number_read_d(os.str().c_str(), &c); - if (fabs((v-r)-c)>5.*pow(10.,digitsEnd)) { - FILE* file = fopen("pathstring log.txt","at"); - fprintf(file, "bad, v: %.9g, r: %.9g, os: %s, c: %.12g, roundeddiff: %.12g, precision: %d, digitsEnd: %d, numDigits: %d\n", v, r, os.str().c_str(), c, roundeddiff, precision, digitsEnd, numDigits); - fclose(file); - } - Inkscape::SVGOStringStream ostr1, ostr2; - ostr1 << v; - ostr2 << (r+c); - if (ostr1.str() != ostr2.str()) { - FILE* file = fopen("pathstring log.txt","at"); - fprintf(file, "bad, v: %.9g, r: %.9g, os: %s, c: %.12g, ostr1: %s, ostr2: %s, roundeddiff: %.12g\n", v, r, os.str().c_str(), c, ostr1.str().c_str(), ostr2.str().c_str(), roundeddiff); - fclose(file); - }*/ - /*FILE* file = fopen("pathstring log.txt","at"); - fprintf(file, "good, v: %.9g, r: %.9g, os: %s, c: %.12g, roundeddiff: %.12g, precision: %d, digitsEnd: %d, numDigits: %d\n", v, r, os.str().c_str(), c, roundeddiff, precision, digitsEnd, numDigits); - fclose(file);*/ + str += '0'; } } void Inkscape::SVG::PathString::State::appendRelative(NR::Point p, NR::Point r) { str += ' '; - appendRelativeCoord(str, p[NR::X], r[NR::X]); + appendRelativeCoord(p[NR::X], r[NR::X]); str += ','; - appendRelativeCoord(str, p[NR::Y], r[NR::Y]); + appendRelativeCoord(p[NR::Y], r[NR::Y]); } void Inkscape::SVG::PathString::State::appendRelative(NR::Coord v, NR::Coord r) { str += ' '; - appendRelativeCoord(str, v, r); + appendRelativeCoord(v, r); +} + +void Inkscape::SVG::PathString::State::appendNumber(double v, int precision, int minexp) { + size_t const reserve = precision+1+1+1+1+3; // Just large enough to hold the maximum number of digits plus a sign, a period, the letter 'e', another sign and three digits for the exponent + size_t const oldsize = str.size(); + str.append(reserve, (char)0); + char* begin_of_num = const_cast(str.data()+oldsize); // Slightly evil, I know (but std::string should be storing its data in one big block of memory, so...) + size_t added = sp_svg_number_write_de(begin_of_num, v, precision, minexp); + str.resize(oldsize+added); // remove any trailing characters +} + +void Inkscape::SVG::PathString::State::appendNumber(double v, double &rv, int precision, int minexp) { + size_t const oldsize = str.size(); + appendNumber(v, precision, minexp); + char* begin_of_num = const_cast(str.data()+oldsize); // Slightly evil, I know (but std::string should be storing its data in one big block of memory, so...) + sp_svg_number_read_d(begin_of_num, &rv); } /* diff --git a/src/svg/path-string.h b/src/svg/path-string.h index bba4c8473..d09d43b9d 100644 --- a/src/svg/path-string.h +++ b/src/svg/path-string.h @@ -17,6 +17,8 @@ #define SEEN_INKSCAPE_SVG_PATH_STRING_H #include +#include +#include #include "libnr/nr-point.h" #include "libnr/nr-point-ops.h" @@ -31,16 +33,24 @@ public: // default copy // default assign - Glib::ustring const &ustring() const { - return (_abs_state <= _rel_state || !allow_relative_coordinates) ? _abs_state.str : _rel_state.str; + std::string const &string() { + std::string const &t = tail(); + final.reserve(commonbase.size()+t.size()); + final = commonbase; + final += tail(); + return final; } - operator Glib::ustring const &() const { - return ustring(); + operator std::string const &() { + return string(); } - char const *c_str() const { - return ustring().c_str(); + operator Glib::ustring const () const { + return commonbase + tail(); + } + + char const *c_str() { + return string().c_str(); } PathString &moveTo(NR::Coord x, NR::Coord y) { @@ -167,14 +177,14 @@ private: State() { prevop = 0; switches = 0; } void appendOp(char op) { - if (!str.empty()) str.append(1, ' '); - str.append(1, op); - prevop = op == 'M' ? 'L' : op == 'm' ? 'l' : op; + if (prevop != 0) str += ' '; + str += op; + prevop = ( op == 'M' ? 'L' : op == 'm' ? 'l' : op ); } void append(bool flag) { - str.append(1, ' '); - str.append(1, ( flag ? '1' : '0' )); + str += ' '; + str += ( flag ? '1' : '0' ); } void append(NR::Coord v); @@ -192,16 +202,32 @@ private: return true; } - Glib::ustring str; + // Note: changing this to Glib::ustring might cause problems in path-string.cpp because it assumes that + // size() returns the size of the string in BYTES (and Glib::ustring::resize is terribly slow) + std::string str; unsigned int switches; char prevop; + + private: + void appendNumber(double v, int precision=numericprecision, int minexp=minimumexponent); + void appendNumber(double v, double &rv, int precision=numericprecision, int minexp=minimumexponent); + void appendRelativeCoord(NR::Coord v, NR::Coord r); } _abs_state, _rel_state; // State with the last operator being an absolute/relative operator NR::Point _initial_point; NR::Point _current_point; + // If both states have a common prefix it is stored here. + // Separating out the common prefix prevents repeated copying between the states + // to cause a quadratic time complexity (in the number of characters/operators) + std::string commonbase; + std::string final; + std::string const &tail() const { return ((_abs_state <= _rel_state || !allow_relative_coordinates) ? _abs_state.str : _rel_state.str); } + bool const allow_relative_coordinates; bool const force_repeat_commands; + static int numericprecision; + static int minimumexponent; }; } diff --git a/src/svg/svg-affine-test.h b/src/svg/svg-affine-test.h index 0284402ed..7a4c27fb3 100644 --- a/src/svg/svg-affine-test.h +++ b/src/svg/svg-affine-test.h @@ -1,6 +1,7 @@ #include #include "svg/svg.h" +#include "streq.h" #include <2geom/matrix.h> #include #include @@ -8,15 +9,6 @@ #include #include -struct streq_free2 { - bool operator()(char const *exp, char const *got) const - { - bool const ret = (strcmp(exp, got) == 0); - g_free((void*)got); - return ret; - } -}; - struct approx_equal { bool operator()(Geom::Matrix const &ref, Geom::Matrix const &cm) const { @@ -122,35 +114,45 @@ public: void testWriteMatrix() { for(size_t i=0; i 0u); + + memcpy(buf, &c[16u - i], i); + buf[i] = 0; + + return i; +} + static unsigned int sp_svg_number_write_i(gchar *buf, int val) { int p = 0; + unsigned int uval; if (val < 0) { buf[p++] = '-'; - val = -val; + uval = (unsigned int)-val; + } else { + uval = (unsigned int)val; } - - int i = 0; - char c[32]; - do { - c[32 - (++i)] = '0' + (val % 10); - val /= 10; - } while (val > 0); - - memcpy(buf + p, &c[32 - i], i); - p += i; - buf[p] = 0; + + p += sp_svg_number_write_ui(buf+p, uval); return p; } -static unsigned sp_svg_number_write_d(gchar *buf, double val, unsigned int tprec, unsigned int fprec, unsigned int padf) +static unsigned sp_svg_number_write_d(gchar *buf, double val, unsigned int tprec, unsigned int fprec) { /* Process sign */ int i = 0; @@ -98,23 +107,30 @@ static unsigned sp_svg_number_write_d(gchar *buf, double val, unsigned int tprec /* Determine number of integral digits */ int idigits = 0; if (val >= 1.0) { - idigits = (int) floor(log10(val)); + idigits = (int) floor(log10(val)) + 1; } /* Determine the actual number of fractional digits */ - fprec = MAX(fprec, tprec - idigits - 1); + fprec = MAX(fprec, tprec - idigits); /* Round value */ - val += 0.5 * pow(10.0, - ((double) fprec)); + val += 0.5 / pow(10.0, fprec); /* Extract integral and fractional parts */ double dival = floor(val); - int ival = (int) dival; double fval = val - dival; /* Write integra */ - i += sp_svg_number_write_i(buf + i, ival); + if (idigits > (int)tprec) { + i += sp_svg_number_write_ui(buf + i, (unsigned int)floor(dival/pow(10.0, idigits-tprec) + .5)); + for(unsigned int j=0; j<(unsigned int)idigits-tprec; j++) { + buf[i+j] = '0'; + } + i += idigits-tprec; + } else { + i += sp_svg_number_write_ui(buf + i, (unsigned int)dival); + } int end_i = i; - if (fprec > 0 && (padf || fval > 0.0)) { + if (fprec > 0 && fval > 0.0) { buf[i++] = '.'; - while ((fprec > 0) && (padf || (fval > 0.0))) { + do { fval *= 10.0; dival = floor(fval); fval -= dival; @@ -124,27 +140,31 @@ static unsigned sp_svg_number_write_d(gchar *buf, double val, unsigned int tprec end_i = i; } fprec -= 1; - } + } while(fprec > 0 && fval > 0.0); } buf[end_i] = 0; return end_i; } -unsigned int sp_svg_number_write_de(gchar *buf, double val, unsigned int tprec, int min_exp, unsigned int padf) +unsigned int sp_svg_number_write_de(gchar *buf, double val, unsigned int tprec, int min_exp) { - if (val == 0.0 || (fabs(val) >= 0.1 && fabs(val) < 10000000)) { - return sp_svg_number_write_d(buf, val, tprec, 0, padf); + int eval = (int)floor(log10(fabs(val))); + if (val == 0.0 || eval < min_exp) { + return sp_svg_number_write_ui(buf, 0); + } + unsigned int maxnumdigitsWithoutExp = // This doesn't include the sign because it is included in either representation + eval<0?tprec+(unsigned int)-eval+1: + eval+1<(int)tprec?tprec+1: + (unsigned int)eval+1; + unsigned int maxnumdigitsWithExp = tprec + ( eval<0 ? 4 : 3 ); // It's not necessary to take larger exponents into account, because then maxnumdigitsWithoutExp is DEFINITELY larger + if (maxnumdigitsWithoutExp <= maxnumdigitsWithExp) { + return sp_svg_number_write_d(buf, val, tprec, 0); } else { - double eval = floor(log10(fabs(val))); - if ((int) eval < min_exp) { - return sp_svg_number_write_d(buf, 0, tprec, 0, padf); - } else { - val = val / pow(10.0, eval); - int p = sp_svg_number_write_d(buf, val, tprec, 0, padf); - buf[p++] = 'e'; - p += sp_svg_number_write_i(buf + p, (int) eval); - return p; - } + val = eval < 0 ? val * pow(10.0, -eval) : val / pow(10.0, eval); + int p = sp_svg_number_write_d(buf, val, tprec, 0); + buf[p++] = 'e'; + p += sp_svg_number_write_i(buf + p, eval); + return p; } } diff --git a/src/svg/svg-path-test.h b/src/svg/svg-path-test.h index 5e2038527..0f58d6627 100644 --- a/src/svg/svg-path-test.h +++ b/src/svg/svg-path-test.h @@ -2,6 +2,8 @@ #include "libnr/n-art-bpath.h" #include "svg/svg.h" #include "2geom/coord.h" +#include "prefs-utils.h" +#include "streq.h" #include #include #include @@ -435,6 +437,20 @@ public: g_free(bpath); g_free(path_str); g_free(new_bpath); } + void testMinexpPrecision() { + NArtBpath * bpath; + char * path_str; + // Default values + prefs_set_int_attribute("options.svgoutput", "allowrelativecoordinates", 1); + prefs_set_int_attribute("options.svgoutput", "forcerepeatcommands", 0); + prefs_set_int_attribute("options.svgoutput", "numericprecision", 8); + prefs_set_int_attribute("options.svgoutput", "minimumexponent", -8); + bpath = sp_svg_read_path("M 123456781,1.23456781e-8 L 123456782,1.23456782e-8 L 123456785,1.23456785e-8 L 10123456400,1.23456785e-8 L 123456789,1.23456789e-8 L 123456789,101.234564e-8 L 123456789,1.23456789e-8"); + path_str = sp_svg_write_path(bpath); + TS_ASSERT_RELATION( streq_rel , "m 123456780,1.2345678e-8 0,0 10,1e-15 9999999210,0 -9999999210,0 0,9.99999921e-7 0,-9.99999921e-7" , path_str ); + g_free(bpath); g_free(path_str); + } + private: bool bpathEqual(NArtBpath const * a, NArtBpath const * b, double eps = 1e-16) { while(a->code != NR_END && b->code == a->code) { diff --git a/src/svg/svg.h b/src/svg/svg.h index a273ceddc..7c9ac5a91 100644 --- a/src/svg/svg.h +++ b/src/svg/svg.h @@ -35,7 +35,7 @@ unsigned int sp_svg_number_read_d (const gchar *str, double *val); /* * No buffer overflow checking is done, so better wrap them if needed */ -unsigned int sp_svg_number_write_de (gchar *buf, double val, unsigned int tprec, int min_exp, unsigned int padf); +unsigned int sp_svg_number_write_de (gchar *buf, double val, unsigned int tprec, int min_exp); /* Length */ diff --git a/src/trace/potrace/inkscape-potrace.cpp b/src/trace/potrace/inkscape-potrace.cpp index 296d88c63..2f4dc7a6f 100644 --- a/src/trace/potrace/inkscape-potrace.cpp +++ b/src/trace/potrace/inkscape-potrace.cpp @@ -406,7 +406,7 @@ PotraceTracingEngine::grayMapToPath(GrayMap *grayMap, long *nodeCount) if ( nodeCount) *nodeCount = thisNodeCount; - return data.ustring(); + return data.string(); } diff --git a/src/xml/quote-test.h b/src/xml/quote-test.h index 7f5372844..cfcb3bef2 100644 --- a/src/xml/quote-test.h +++ b/src/xml/quote-test.h @@ -1,4 +1,5 @@ #include +#include "streq.h" /* Initial author: Peter Moulder. Hereby released into the Public Domain. */ @@ -11,15 +12,6 @@ #define's and `using' directives of the included file. */ #include "quote.cpp" -struct streq_free2 { - bool operator()(char const *exp, char *got) const - { - bool const ret = (strcmp(exp, got) == 0); - g_free(got); - return ret; - } -}; - class XmlQuoteTest : public CxxTest::TestSuite { public: @@ -71,7 +63,9 @@ public: {"a\"bd;!@#$%^*(\\)?", "a"b<c>d;!@#$%^*(\\)?"} }; for(size_t i=0; i