khtml/svg/SVGParserUtilities.cpp

   1 /* This file is part of the KDE project
   2    Copyright (C) 2002, 2003 The Karbon Developers
   3                  2006       Alexander Kellett <lypanov@kde.org>
   4                  2006, 2007 Rob Buis <buis@kde.org>
   5                  2007       Apple, Inc.  All rights reserved.
   6
   7    This library is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU Library General Public
   9    License as published by the Free Software Foundation; either
  10    version 2 of the License, or (at your option) any later version.
  11
  12    This library is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    Library General Public License for more details.
  16
  17    You should have received a copy of the GNU Library General Public License
  18    along with this library; see the file COPYING.LIB.  If not, write to
  19    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20    Boston, MA 02110-1301, USA.
  21 */
  22
  23 #include "config.h"
  24 #include "wtf/Platform.h"
  25 #if ENABLE(SVG)
  26 #include "xml/Document.h"
  27 #include "SVGParserUtilities.h"
  28
  29 #include "ExceptionCode.h"
  30 #include "FloatConversion.h"
  31 #include "FloatPoint.h"
  32 #include "Path.h"
  33 #include "PlatformString.h"
  34 #include "SVGPathSegList.h"
  35 #include "SVGPathSegArc.h"
  36 #include "SVGPathSegClosePath.h"
  37 #include "SVGPathSegCurvetoCubic.h"
  38 #include "SVGPathSegCurvetoCubicSmooth.h"
  39 #include "SVGPathSegCurvetoQuadratic.h"
  40 #include "SVGPathSegCurvetoQuadraticSmooth.h"
  41 #include "SVGPathSegLineto.h"
  42 #include "SVGPathSegLinetoHorizontal.h"
  43 #include "SVGPathSegLinetoVertical.h"
  44 #include "SVGPathSegList.h"
  45 #include "SVGPathSegMoveto.h"
  46 #include "SVGPointList.h"
  47 #include "SVGPathElement.h"
  48 #include <math.h>
  49 #include <wtf/MathExtras.h>
  50
  51 namespace WebCore {
  52
  53 /* We use this generic _parseNumber function to allow the Path parsing code to work
  54  * at a higher precision internally, without any unnecessary runtime cost or code
  55  * complexity
  56  */
  57 template <typename FloatType> static bool _parseNumber(const UChar*& ptr, const UChar* end, FloatType& number, bool skip)
  58 {
  59     int integer, exponent;
  60     FloatType decimal, frac;
  61     int sign, expsign;
  62     const UChar* start = ptr;
  63
  64     exponent = 0;
  65     integer = 0;
  66     frac = 1;
  67     decimal = 0;
  68     sign = 1;
  69     expsign = 1;
  70
  71     // read the sign
  72     if (ptr < end && *ptr == '+')
  73         ptr++;
  74     else if (ptr < end && *ptr == '-') {
  75         ptr++;
  76         sign = -1;
  77     }
  78
  79     if (ptr == end || ((*ptr < '0' || *ptr > '9') && *ptr != '.'))
  80         // The first character of a number must be one of [0-9+-.]
  81         return false;
  82
  83     // read the integer part
  84     while (ptr < end && *ptr >= '0' && *ptr <= '9')
  85         integer = (integer * 10) + (ptr++)->unicode() - '0';
  86
  87     if (ptr < end && *ptr == '.') { // read the decimals
  88         ptr++;
  89
  90         // There must be a least one digit following the .
  91         if (ptr >= end || *ptr < '0' || *ptr > '9')
  92             return false;
  93
  94         while (ptr < end && *ptr >= '0' && *ptr <= '9')
  95             decimal += ((ptr++)->unicode() - '0') * (frac *= static_cast<FloatType>(0.1));
  96     }
  97
  98     // read the exponent part
  99     if (ptr != start && ptr + 1 < end && (*ptr == 'e' || *ptr == 'E')
 100         && (ptr[1] != 'x' && ptr[1] != 'm')) {
 101         ptr++;
 102
 103         // read the sign of the exponent
 104         if (*ptr == '+')
 105             ptr++;
 106         else if (*ptr == '-') {
 107             ptr++;
 108             expsign = -1;
 109         }
 110
 111         // There must be an exponent
 112         if (ptr >= end || *ptr < '0' || *ptr > '9')
 113             return false;
 114
 115         while (ptr < end && *ptr >= '0' && *ptr <= '9') {
 116             exponent *= 10;
 117             exponent += ptr->unicode() - '0';
 118             ptr++;
 119         }
 120     }
 121
 122     number = integer + decimal;
 123     number *= sign * static_cast<FloatType>(pow(10.0, expsign * exponent));
 124
 125     if (start == ptr)
 126         return false;
 127
 128     if (skip)
 129         skipOptionalSpacesOrDelimiter(ptr, end);
 130
 131     return true;
 132 }
 133
 134 bool parseNumber(const UChar*& ptr, const UChar* end, float& number, bool skip)
 135 {
 136     return _parseNumber(ptr, end, number, skip);
 137 }
 138
 139 // Only used for parsing Paths
 140 static bool parseNumber(const UChar*& ptr, const UChar* end, double& number, bool skip = true)
 141 {
 142     return _parseNumber(ptr, end, number, skip);
 143 }
 144
 145 bool parseNumberOptionalNumber(const String& s, float& x, float& y)
 146 {
 147     if (s.isEmpty())
 148         return false;
 149     const UChar* cur = s.characters();
 150     const UChar* end = cur + s.length();
 151
 152     if (!parseNumber(cur, end, x))
 153         return false;
 154
 155     if (cur == end)
 156         y = x;
 157     else if (!parseNumber(cur, end, y, false))
 158         return false;
 159
 160     return cur == end;
 161 }
 162
 163 bool pointsListFromSVGData(SVGPointList* pointsList, const String& points)
 164 {
 165     if (points.isEmpty())
 166         return true;
 167     const UChar* cur = points.characters();
 168     const UChar* end = cur + points.length();
 169
 170     skipOptionalSpaces(cur, end);
 171
 172     bool delimParsed = false;
 173     while (cur < end) {
 174         delimParsed = false;
 175         float xPos = 0.0f;
 176         if (!parseNumber(cur, end, xPos))
 177            return false;
 178
 179         float yPos = 0.0f;
 180         if (!parseNumber(cur, end, yPos, false))
 181             return false;
 182
 183         skipOptionalSpaces(cur, end);
 184
 185         if (cur < end && *cur == ',') {
 186             delimParsed = true;
 187             cur++;
 188         }
 189         skipOptionalSpaces(cur, end);
 190
 191         ExceptionCode ec = 0;
 192         pointsList->appendItem(FloatPoint(xPos, yPos), ec);
 193     }
 194     return cur == end && !delimParsed;
 195 }
 196
 197     /**
 198      * Parser for svg path data, contained in the d attribute.
 199      *
 200      * The parser delivers encountered commands and parameters by calling
 201      * methods that correspond to those commands. Clients have to derive
 202      * from this class and implement the abstract command methods.
 203      *
 204      * There are two operating modes. By default the parser just delivers unaltered
 205      * svg path data commands and parameters. In the second mode, it will convert all
 206      * relative coordinates to absolute ones, and convert all curves to cubic beziers.
 207      */
 208     class SVGPathParser
 209     {
 210     public:
 211         virtual ~SVGPathParser() { }
 212         bool parseSVG(const String& d, bool process = false);
 213
 214     protected:
 215         virtual void svgMoveTo(double x1, double y1, bool closed, bool abs = true) = 0;
 216         virtual void svgLineTo(double x1, double y1, bool abs = true) = 0;
 217         virtual void svgLineToHorizontal(double x, bool abs = true) {}
 218         virtual void svgLineToVertical(double y, bool abs = true) {}
 219         virtual void svgCurveToCubic(double x1, double y1, double x2, double y2, double x, double y, bool abs = true) = 0;
 220         virtual void svgCurveToCubicSmooth(double x, double y, double x2, double y2, bool abs = true) {}
 221         virtual void svgCurveToQuadratic(double x, double y, double x1, double y1, bool abs = true) {}
 222         virtual void svgCurveToQuadraticSmooth(double x, double y, bool abs = true) {}
 223         virtual void svgArcTo(double x, double y, double r1, double r2, double angle, bool largeArcFlag, bool sweepFlag, bool abs = true) {}
 224         virtual void svgClosePath() = 0;
 225     private:
 226         void calculateArc(bool relative, double& curx, double& cury, double angle, double x, double y, double r1, double r2, bool largeArcFlag, bool sweepFlag);
 227     };
 228
 229 bool SVGPathParser::parseSVG(const String& s, bool process)
 230 {
 231     if (s.isEmpty())
 232         return false;
 233
 234     const UChar* ptr = s.characters();
 235     const UChar* end = ptr + s.length();
 236
 237     double contrlx, contrly, curx, cury, subpathx, subpathy, tox, toy, x1, y1, x2, y2, xc, yc;
 238     double px1, py1, px2, py2, px3, py3;
 239     bool closed = true;
 240
 241     if (!skipOptionalSpaces(ptr, end)) // skip any leading spaces
 242         return false;
 243
 244     char command = (ptr++)->unicode(), lastCommand = ' ';// or toLatin1() instead of unicode()???
 245     if (command != 'm' && command != 'M') // path must start with moveto
 246         return false;
 247
 248     subpathx = subpathy = curx = cury = contrlx = contrly = 0.0;
 249     while (1) {
 250         skipOptionalSpaces(ptr, end); // skip spaces between command and first coord
 251
 252         bool relative = false;
 253
 254         switch(command)
 255         {
 256             case 'm':
 257                 relative = true;
 258             case 'M':
 259             {
 260                 if (!parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy))
 261                     return false;
 262
 263                 if (process) {
 264                     subpathx = curx = relative ? curx + tox : tox;
 265                     subpathy = cury = relative ? cury + toy : toy;
 266
 267                     svgMoveTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury), closed);
 268                 } else
 269                     svgMoveTo(narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), closed, !relative);
 270                 closed = false;
 271                 break;
 272             }
 273             case 'l':
 274                 relative = true;
 275             case 'L':
 276             {
 277                 if (!parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy))
 278                     return false;
 279
 280                 if (process) {
 281                     curx = relative ? curx + tox : tox;
 282                     cury = relative ? cury + toy : toy;
 283
 284                     svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
 285                 }
 286                 else
 287                     svgLineTo(narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
 288                 break;
 289             }
 290             case 'h':
 291             {
 292                 if (!parseNumber(ptr, end, tox))
 293                     return false;
 294                 if (process) {
 295                     curx = curx + tox;
 296                     svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
 297                 }
 298                 else
 299                     svgLineToHorizontal(narrowPrecisionToFloat(tox), false);
 300                 break;
 301             }
 302             case 'H':
 303             {
 304                 if (!parseNumber(ptr, end, tox))
 305                     return false;
 306                 if (process) {
 307                     curx = tox;
 308                     svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
 309                 }
 310                 else
 311                     svgLineToHorizontal(narrowPrecisionToFloat(tox));
 312                 break;
 313             }
 314             case 'v':
 315             {
 316                 if (!parseNumber(ptr, end, toy))
 317                     return false;
 318                 if (process) {
 319                     cury = cury + toy;
 320                     svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
 321                 }
 322                 else
 323                     svgLineToVertical(narrowPrecisionToFloat(toy), false);
 324                 break;
 325             }
 326             case 'V':
 327             {
 328                 if (!parseNumber(ptr, end, toy))
 329                     return false;
 330                 if (process) {
 331                     cury = toy;
 332                     svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
 333                 }
 334                 else
 335                     svgLineToVertical(narrowPrecisionToFloat(toy));
 336                 break;
 337             }
 338             case 'z':
 339             case 'Z':
 340             {
 341                 // reset curx, cury for next path
 342                 if (process) {
 343                     curx = subpathx;
 344                     cury = subpathy;
 345                 }
 346                 closed = true;
 347                 svgClosePath();
 348                 break;
 349             }
 350             case 'c':
 351                 relative = true;
 352             case 'C':
 353             {
 354                 if (!parseNumber(ptr, end, x1)  || !parseNumber(ptr, end, y1) ||
 355                     !parseNumber(ptr, end, x2)  || !parseNumber(ptr, end, y2) ||
 356                     !parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy))
 357                     return false;
 358
 359                 if (process) {
 360                     px1 = relative ? curx + x1 : x1;
 361                     py1 = relative ? cury + y1 : y1;
 362                     px2 = relative ? curx + x2 : x2;
 363                     py2 = relative ? cury + y2 : y2;
 364                     px3 = relative ? curx + tox : tox;
 365                     py3 = relative ? cury + toy : toy;
 366
 367                     svgCurveToCubic(narrowPrecisionToFloat(px1), narrowPrecisionToFloat(py1), narrowPrecisionToFloat(px2),
 368                                     narrowPrecisionToFloat(py2), narrowPrecisionToFloat(px3), narrowPrecisionToFloat(py3));
 369
 370                     contrlx = relative ? curx + x2 : x2;
 371                     contrly = relative ? cury + y2 : y2;
 372                     curx = relative ? curx + tox : tox;
 373                     cury = relative ? cury + toy : toy;
 374                 }
 375                 else
 376                     svgCurveToCubic(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1), narrowPrecisionToFloat(x2),
 377                                     narrowPrecisionToFloat(y2), narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
 378
 379                 break;
 380             }
 381             case 's':
 382                 relative = true;
 383             case 'S':
 384             {
 385                 if (!parseNumber(ptr, end, x2)  || !parseNumber(ptr, end, y2) ||
 386                     !parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy))
 387                     return false;
 388
 389                 if (!(lastCommand == 'c' || lastCommand == 'C' ||
 390                      lastCommand == 's' || lastCommand == 'S')) {
 391                     contrlx = curx;
 392                     contrly = cury;
 393                 }
 394
 395                 if (process) {
 396                     px1 = 2 * curx - contrlx;
 397                     py1 = 2 * cury - contrly;
 398                     px2 = relative ? curx + x2 : x2;
 399                     py2 = relative ? cury + y2 : y2;
 400                     px3 = relative ? curx + tox : tox;
 401                     py3 = relative ? cury + toy : toy;
 402
 403                     svgCurveToCubic(narrowPrecisionToFloat(px1), narrowPrecisionToFloat(py1), narrowPrecisionToFloat(px2),
 404                                     narrowPrecisionToFloat(py2), narrowPrecisionToFloat(px3), narrowPrecisionToFloat(py3));
 405
 406                     contrlx = relative ? curx + x2 : x2;
 407                     contrly = relative ? cury + y2 : y2;
 408                     curx = relative ? curx + tox : tox;
 409                     cury = relative ? cury + toy : toy;
 410                 }
 411                 else
 412                     svgCurveToCubicSmooth(narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2),
 413                                           narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
 414                 break;
 415             }
 416             case 'q':
 417                 relative = true;
 418             case 'Q':
 419             {
 420                 if (!parseNumber(ptr, end, x1)  || !parseNumber(ptr, end, y1) ||
 421                     !parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy))
 422                     return false;
 423
 424                 if (process) {
 425                     px1 = relative ? (curx + 2 * (x1 + curx)) * (1.0 / 3.0) : (curx + 2 * x1) * (1.0 / 3.0);
 426                     py1 = relative ? (cury + 2 * (y1 + cury)) * (1.0 / 3.0) : (cury + 2 * y1) * (1.0 / 3.0);
 427                     px2 = relative ? ((curx + tox) + 2 * (x1 + curx)) * (1.0 / 3.0) : (tox + 2 * x1) * (1.0 / 3.0);
 428                     py2 = relative ? ((cury + toy) + 2 * (y1 + cury)) * (1.0 / 3.0) : (toy + 2 * y1) * (1.0 / 3.0);
 429                     px3 = relative ? curx + tox : tox;
 430                     py3 = relative ? cury + toy : toy;
 431
 432                     svgCurveToCubic(narrowPrecisionToFloat(px1), narrowPrecisionToFloat(py1), narrowPrecisionToFloat(px2),
 433                                     narrowPrecisionToFloat(py2), narrowPrecisionToFloat(px3), narrowPrecisionToFloat(py3));
 434
 435                     contrlx = relative ? curx + x1 : x1;
 436                     contrly = relative ? cury + y1 : y1;
 437                     curx = relative ? curx + tox : tox;
 438                     cury = relative ? cury + toy : toy;
 439                 }
 440                 else
 441                     svgCurveToQuadratic(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
 442                                         narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
 443                 break;
 444             }
 445             case 't':
 446                 relative = true;
 447             case 'T':
 448             {
 449                 if (!parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy))
 450                     return false;
 451                 if (!(lastCommand == 'q' || lastCommand == 'Q' ||
 452                      lastCommand == 't' || lastCommand == 'T')) {
 453                     contrlx = curx;
 454                     contrly = cury;
 455                 }
 456
 457                 if (process) {
 458                     xc = 2 * curx - contrlx;
 459                     yc = 2 * cury - contrly;
 460
 461                     px1 = relative ? (curx + 2 * xc) * (1.0 / 3.0) : (curx + 2 * xc) * (1.0 / 3.0);
 462                     py1 = relative ? (cury + 2 * yc) * (1.0 / 3.0) : (cury + 2 * yc) * (1.0 / 3.0);
 463                     px2 = relative ? ((curx + tox) + 2 * xc) * (1.0 / 3.0) : (tox + 2 * xc) * (1.0 / 3.0);
 464                     py2 = relative ? ((cury + toy) + 2 * yc) * (1.0 / 3.0) : (toy + 2 * yc) * (1.0 / 3.0);
 465                     px3 = relative ? curx + tox : tox;
 466                     py3 = relative ? cury + toy : toy;
 467
 468                     svgCurveToCubic(narrowPrecisionToFloat(px1), narrowPrecisionToFloat(py1), narrowPrecisionToFloat(px2),
 469                                     narrowPrecisionToFloat(py2), narrowPrecisionToFloat(px3), narrowPrecisionToFloat(py3));
 470
 471                     contrlx = xc;
 472                     contrly = yc;
 473                     curx = relative ? curx + tox : tox;
 474                     cury = relative ? cury + toy : toy;
 475                 }
 476                 else
 477                     svgCurveToQuadraticSmooth(narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
 478                 break;
 479             }
 480             case 'a':
 481                 relative = true;
 482             case 'A':
 483             {
 484                 bool largeArc, sweep;
 485                 double angle, rx, ry;
 486                 if (!parseNumber(ptr, end, rx)    || !parseNumber(ptr, end, ry) ||
 487                     !parseNumber(ptr, end, angle) || !parseNumber(ptr, end, tox))
 488                     return false;
 489                 largeArc = tox == 1;
 490                 if (!parseNumber(ptr, end, tox))
 491                     return false;
 492                 sweep = tox == 1;
 493                 if (!parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy))
 494                     return false;
 495
 496                 // Spec: radii are nonnegative numbers
 497                 rx = fabs(rx);
 498                 ry = fabs(ry);
 499
 500                 if (process)
 501                     calculateArc(relative, curx, cury, angle, tox, toy, rx, ry, largeArc, sweep);
 502                 else
 503                     svgArcTo(narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), narrowPrecisionToFloat(rx), narrowPrecisionToFloat(ry),
 504                              narrowPrecisionToFloat(angle), largeArc, sweep, !relative);
 505                 break;
 506             }
 507             default:
 508                 // FIXME: An error should go to the JavaScript console, or the like.
 509                 return false;
 510         }
 511         lastCommand = command;
 512
 513         if (ptr >= end)
 514             return true;
 515
 516         // Check for remaining coordinates in the current command.
 517         if ((*ptr == '+' || *ptr == '-' || (*ptr >= '0' && *ptr <= '9')) &&
 518             (command != 'z' && command != 'Z')) {
 519             if (command == 'M')
 520                 command = 'L';
 521             else if (command == 'm')
 522                 command = 'l';
 523         } else
 524             command = (ptr++)->unicode(); // or toLatin1() instead of unicode()???
 525
 526         if (lastCommand != 'C' && lastCommand != 'c' &&
 527             lastCommand != 'S' && lastCommand != 's' &&
 528             lastCommand != 'Q' && lastCommand != 'q' &&
 529             lastCommand != 'T' && lastCommand != 't') {
 530             contrlx = curx;
 531             contrly = cury;
 532         }
 533     }
 534
 535     return false;
 536 }
 537
 538 // This works by converting the SVG arc to "simple" beziers.
 539 // For each bezier found a svgToCurve call is done.
 540 // Adapted from Niko's code in kdelibs/kdecore/svgicons.
 541 // Maybe this can serve in some shared lib? (Rob)
 542 void SVGPathParser::calculateArc(bool relative, double& curx, double& cury, double angle, double x, double y, double r1, double r2, bool largeArcFlag, bool sweepFlag)
 543 {
 544     double sin_th, cos_th;
 545     double a00, a01, a10, a11;
 546     double x0, y0, x1, y1, xc, yc;
 547     double d, sfactor, sfactor_sq;
 548     double th0, th1, th_arc;
 549     int i, n_segs;
 550
 551     sin_th = sin(angle * (piDouble / 180.0));
 552     cos_th = cos(angle * (piDouble / 180.0));
 553
 554     double dx;
 555
 556     if (!relative)
 557         dx = (curx - x) / 2.0;
 558     else
 559         dx = -x / 2.0;
 560
 561     double dy;
 562
 563     if (!relative)
 564         dy = (cury - y) / 2.0;
 565     else
 566         dy = -y / 2.0;
 567
 568     double _x1 =  cos_th * dx + sin_th * dy;
 569     double _y1 = -sin_th * dx + cos_th * dy;
 570     double Pr1 = r1 * r1;
 571     double Pr2 = r2 * r2;
 572     double Px = _x1 * _x1;
 573     double Py = _y1 * _y1;
 574
 575     // Spec : check if radii are large enough
 576     double check = Px / Pr1 + Py / Pr2;
 577     if (check > 1) {
 578         r1 = r1 * sqrt(check);
 579         r2 = r2 * sqrt(check);
 580     }
 581
 582     a00 = cos_th / r1;
 583     a01 = sin_th / r1;
 584     a10 = -sin_th / r2;
 585     a11 = cos_th / r2;
 586
 587     x0 = a00 * curx + a01 * cury;
 588     y0 = a10 * curx + a11 * cury;
 589
 590     if (!relative)
 591         x1 = a00 * x + a01 * y;
 592     else
 593         x1 = a00 * (curx + x) + a01 * (cury + y);
 594
 595     if (!relative)
 596         y1 = a10 * x + a11 * y;
 597     else
 598         y1 = a10 * (curx + x) + a11 * (cury + y);
 599
 600     /* (x0, y0) is current point in transformed coordinate space.
 601        (x1, y1) is new point in transformed coordinate space.
 602
 603        The arc fits a unit-radius circle in this space.
 604     */
 605
 606     d = (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0);
 607
 608     sfactor_sq = 1.0 / d - 0.25;
 609
 610     if (sfactor_sq < 0)
 611         sfactor_sq = 0;
 612
 613     sfactor = sqrt(sfactor_sq);
 614
 615     if (sweepFlag == largeArcFlag)
 616         sfactor = -sfactor;
 617
 618     xc = 0.5 * (x0 + x1) - sfactor * (y1 - y0);
 619     yc = 0.5 * (y0 + y1) + sfactor * (x1 - x0);
 620
 621     /* (xc, yc) is center of the circle. */
 622     th0 = atan2(y0 - yc, x0 - xc);
 623     th1 = atan2(y1 - yc, x1 - xc);
 624
 625     th_arc = th1 - th0;
 626     if (th_arc < 0 && sweepFlag)
 627         th_arc += 2 * piDouble;
 628     else if (th_arc > 0 && !sweepFlag)
 629         th_arc -= 2 * piDouble;
 630
 631     n_segs = (int) (int) ceil(fabs(th_arc / (piDouble * 0.5 + 0.001)));
 632
 633     for(i = 0; i < n_segs; i++) {
 634         double sin_th, cos_th;
 635         double a00, a01, a10, a11;
 636         double x1, y1, x2, y2, x3, y3;
 637         double t;
 638         double th_half;
 639
 640         double _th0 = th0 + i * th_arc / n_segs;
 641         double _th1 = th0 + (i + 1) * th_arc / n_segs;
 642
 643         sin_th = sin(angle * (piDouble / 180.0));
 644         cos_th = cos(angle * (piDouble / 180.0));
 645
 646         /* inverse transform compared with rsvg_path_arc */
 647         a00 = cos_th * r1;
 648         a01 = -sin_th * r2;
 649         a10 = sin_th * r1;
 650         a11 = cos_th * r2;
 651
 652         th_half = 0.5 * (_th1 - _th0);
 653         t = (8.0 / 3.0) * sin(th_half * 0.5) * sin(th_half * 0.5) / sin(th_half);
 654         x1 = xc + cos(_th0) - t * sin(_th0);
 655         y1 = yc + sin(_th0) + t * cos(_th0);
 656         x3 = xc + cos(_th1);
 657         y3 = yc + sin(_th1);
 658         x2 = x3 + t * sin(_th1);
 659         y2 = y3 - t * cos(_th1);
 660
 661         svgCurveToCubic(narrowPrecisionToFloat(a00 * x1 + a01 * y1), narrowPrecisionToFloat(a10 * x1 + a11 * y1),
 662                         narrowPrecisionToFloat(a00 * x2 + a01 * y2), narrowPrecisionToFloat(a10 * x2 + a11 * y2),
 663                         narrowPrecisionToFloat(a00 * x3 + a01 * y3), narrowPrecisionToFloat(a10 * x3 + a11 * y3));
 664     }
 665
 666     if (!relative)
 667         curx = x;
 668     else
 669         curx += x;
 670
 671     if (!relative)
 672         cury = y;
 673     else
 674         cury += y;
 675 }
 676
 677 class PathBuilder : public SVGPathParser
 678 {
 679 public:
 680     bool build(Path* path, const String& d)
 681     {
 682         m_path = path;
 683         return parseSVG(d, true);
 684     }
 685
 686 private:
 687     virtual void svgMoveTo(double x1, double y1, bool closed, bool abs = true)
 688     {
 689         current.setX(narrowPrecisionToFloat(abs ? x1 : current.x() + x1));
 690         current.setY(narrowPrecisionToFloat(abs ? y1 : current.y() + y1));
 691         if (closed)
 692             m_path->closeSubpath();
 693         m_path->moveTo(current);
 694     }
 695     virtual void svgLineTo(double x1, double y1, bool abs = true)
 696     {
 697         current.setX(narrowPrecisionToFloat(abs ? x1 : current.x() + x1));
 698         current.setY(narrowPrecisionToFloat(abs ? y1 : current.y() + y1));
 699         m_path->addLineTo(current);
 700     }
 701     virtual void svgCurveToCubic(double x1, double y1, double x2, double y2, double x, double y, bool abs = true)
 702     {
 703         if (!abs) {
 704             x1 += current.x();
 705             y1 += current.y();
 706             x2 += current.x();
 707             y2 += current.y();
 708         }
 709         current.setX(narrowPrecisionToFloat(abs ? x : current.x() + x));
 710         current.setY(narrowPrecisionToFloat(abs ? y : current.y() + y));
 711         m_path->addBezierCurveTo(FloatPoint::narrowPrecision(x1, y1), FloatPoint::narrowPrecision(x2, y2), current);
 712     }
 713     virtual void svgClosePath()
 714     {
 715         m_path->closeSubpath();
 716     }
 717     Path* m_path;
 718     FloatPoint current;
 719 };
 720
 721 bool pathFromSVGData(Path& path, const String& d)
 722 {
 723     PathBuilder builder;
 724     return builder.build(&path, d);
 725 }
 726
 727 class SVGPathSegListBuilder : public SVGPathParser
 728 {
 729 public:
 730     bool build(SVGPathSegList* segList, const String& d, bool process)
 731     {
 732         m_pathSegList = segList;
 733         return parseSVG(d, process);
 734     }
 735
 736 private:
 737     virtual void svgMoveTo(double x1, double y1, bool, bool abs = true)
 738     {
 739         ExceptionCode ec = 0;
 740
 741         if (abs)
 742             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegMovetoAbs(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1)), ec);
 743         else
 744             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegMovetoRel(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1)), ec);
 745     }
 746     virtual void svgLineTo(double x1, double y1, bool abs = true)
 747     {
 748         ExceptionCode ec = 0;
 749
 750         if (abs)
 751             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoAbs(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1)), ec);
 752         else
 753             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoRel(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1)), ec);
 754     }
 755     virtual void svgLineToHorizontal(double x, bool abs)
 756     {
 757         ExceptionCode ec = 0;
 758
 759         if (abs)
 760             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoHorizontalAbs(narrowPrecisionToFloat(x)), ec);
 761         else
 762             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoHorizontalRel(narrowPrecisionToFloat(x)), ec);
 763     }
 764     virtual void svgLineToVertical(double y, bool abs)
 765     {
 766         ExceptionCode ec = 0;
 767
 768         if (abs)
 769             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoVerticalAbs(narrowPrecisionToFloat(y)), ec);
 770         else
 771             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoVerticalRel(narrowPrecisionToFloat(y)), ec);
 772     }
 773     virtual void svgCurveToCubic(double x1, double y1, double x2, double y2, double x, double y, bool abs = true)
 774     {
 775         ExceptionCode ec = 0;
 776
 777         if (abs)
 778             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoCubicAbs(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y),
 779                                                                                       narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
 780                                                                                       narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2)), ec);
 781         else
 782             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoCubicRel(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y),
 783                                                                                       narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
 784                                                                                       narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2)), ec);
 785     }
 786     virtual void svgCurveToCubicSmooth(double x, double y, double x2, double y2, bool abs)
 787     {
 788         ExceptionCode ec = 0;
 789
 790         if (abs)
 791             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoCubicSmoothAbs(narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2),
 792                                                                                             narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
 793         else
 794             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoCubicSmoothRel(narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2),
 795                                                                                             narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
 796     }
 797     virtual void svgCurveToQuadratic(double x, double y, double x1, double y1, bool abs)
 798     {
 799         ExceptionCode ec = 0;
 800
 801         if (abs)
 802             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoQuadraticAbs(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
 803                                                                                           narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
 804         else
 805             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoQuadraticRel(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
 806                                                                                           narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
 807     }
 808     virtual void svgCurveToQuadraticSmooth(double x, double y, bool abs)
 809     {
 810         ExceptionCode ec = 0;
 811
 812         if (abs)
 813             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoQuadraticSmoothAbs(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
 814         else
 815             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoQuadraticSmoothRel(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
 816     }
 817     virtual void svgArcTo(double x, double y, double r1, double r2, double angle, bool largeArcFlag, bool sweepFlag, bool abs)
 818     {
 819         ExceptionCode ec = 0;
 820
 821         if (abs)
 822             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegArcAbs(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y),
 823                                                                              narrowPrecisionToFloat(r1), narrowPrecisionToFloat(r2),
 824                                                                              narrowPrecisionToFloat(angle), largeArcFlag, sweepFlag), ec);
 825         else
 826             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegArcRel(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y),
 827                                                                              narrowPrecisionToFloat(r1), narrowPrecisionToFloat(r2),
 828                                                                              narrowPrecisionToFloat(angle), largeArcFlag, sweepFlag), ec);
 829     }
 830     virtual void svgClosePath()
 831     {
 832         ExceptionCode ec = 0;
 833         m_pathSegList->appendItem(SVGPathElement::createSVGPathSegClosePath(), ec);
 834     }
 835     SVGPathSegList* m_pathSegList;
 836 };
 837
 838 bool pathSegListFromSVGData(SVGPathSegList* path , const String& d, bool process)
 839 {
 840     SVGPathSegListBuilder builder;
 841     return builder.build(path, d, process);
 842 }
 843
 844 Vector<String> parseDelimitedString(const String& input, const char seperator)
 845 {
 846     Vector<String> values;
 847
 848     const UChar* ptr = input.characters();
 849     const UChar* end = ptr + input.length();
 850     skipOptionalSpaces(ptr, end);
 851
 852     while (ptr < end) {
 853         // Leading and trailing white space, and white space before and after semicolon separators, will be ignored.
 854         const UChar* inputStart = ptr;
 855         while (ptr < end && *ptr != seperator) // careful not to ignore whitespace inside inputs
 856             ptr++;
 857
 858         if (ptr == inputStart)
 859             break;
 860
 861         // walk backwards from the ; to ignore any whitespace
 862         const UChar* inputEnd = ptr - 1;
 863         while (inputStart < inputEnd && isWhitespace(*inputEnd))
 864             inputEnd--;
 865
 866         values.append(String(inputStart, inputEnd - inputStart + 1));
 867         skipOptionalSpacesOrDelimiter(ptr, end, seperator);
 868     }
 869
 870     return values;
 871 }
 872
 873 }
 874
 875 #endif // ENABLE(SVG)