src/math.c

   1 /* math.c - Mathematics functions for chanserv.calc
   2  *
   3  * This program is free software; you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation; either version 2 of the License, or
   6  * (at your option) any later version.  Important limitations are
   7  * listed in the COPYING file that accompanies this software.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, email srvx-maintainers@srvx.net.
  16  *
  17  * $Id$
  18  */
  19
  20 #include "conf.h"
  21 #include "helpfile.h"
  22 #include "nickserv.h"
  23 #include "modcmd.h"
  24 #include "saxdb.h"
  25 #include "timeq.h"
  26 #include <stdio.h>
  27 #include <ctype.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <math.h>
  31 #include <time.h>
  32
  33 #ifdef WIN32
  34 #define strcasecmp stricmp
  35 #endif
  36
  37 enum MathType {
  38         mEnd,
  39         mPlus,
  40         mMinus,
  41         mMult,
  42         mDiv,
  43         mPower,
  44         mLt,
  45         mRt,
  46         mOp,
  47         mOpEnd,
  48         mNumber
  49 };
  50
  51 enum MathOpType {
  52         otExp,
  53         otLog,
  54         otSin,
  55         otASin,
  56         otSinH,
  57         otCos,
  58         otACos,
  59         otCosH,
  60         otTan,
  61         otATan,
  62         otTanH,
  63         otSqrt,
  64         otAbs,
  65         otCeil,
  66         otFloor
  67 };
  68
  69 /* This table is needed for the translation from infix to postfix.      */
  70 static const int TranslateTable[][10] = {
  71 /*List:  _  +  -  *  /  ^  (  )  [  ]                                   */
  72 /*Stack:                                                                */
  73 /* _ */ {4, 1, 1, 1, 1, 1, 1, 5, 1, 5},
  74 /* + */ {2, 2, 2, 1, 1, 1, 1, 2, 1, 2},
  75                 {2, 2, 2, 1, 1, 1, 1, 2, 1, 2},
  76                 {2, 2, 2, 2, 2, 1, 1, 2, 1, 2},
  77                 {2, 2, 2, 2, 2, 1, 1, 2, 1, 2},
  78                 {2, 2, 2, 2, 2, 2, 1, 2, 1, 2},
  79                 {5, 1, 1, 1, 1, 1, 1, 3, 1, 5},
  80                 {5, 5, 5, 5, 5, 5, 5, 5, 5, 5},
  81                 {5, 1, 1, 1, 1, 1, 1, 5, 1, 6},
  82                 {5, 5, 5, 5, 5, 5, 5, 5, 5, 5}
  83 };
  84
  85 typedef struct MathToken {
  86         enum MathType Type;
  87         double Value;
  88         enum MathOpType OpType;
  89         struct MathToken *Next;
  90         struct MathToken *Previous;             /* Previous is used in the stack */
  91 } *MathList;
  92
  93 typedef struct Values {
  94         double Value;
  95         struct Values *Next;
  96         struct Values *Previous;
  97 } *ValueList;
  98
  99 void do_math(char *Buffer, char *Math)
 100 {
 101         int HasDot;
 102         double Value = 0.0;
 103         double Floating;        /* = 10^number of digits after the dot */
 104         int ValueExpected = 1;
 105         char Identifier[512];
 106
 107         MathList ListFirst = NULL;
 108         MathList StackFirst = NULL;
 109         MathList PostFixFirst = NULL;
 110         ValueList TheValuesFirst = NULL;
 111         MathList List;
 112         MathList Stack;
 113         MathList PostFix;
 114         ValueList TheValues;
 115         int Minus = 0;
 116
 117         void *Temp;
 118         int Index;
 119         int OEndExpected;
 120
 121         if (!(List = ListFirst = malloc(sizeof(struct MathToken)))) goto MemError;
 122         if (!(Stack = StackFirst = malloc(sizeof(struct MathToken)))) goto MemError;
 123         if (!(PostFix = PostFixFirst = malloc(sizeof(struct MathToken)))) goto MemError;
 124         if (!(TheValues = TheValuesFirst = malloc(sizeof(struct Values)))) goto MemError;
 125
 126         List->Next = NULL;
 127         Stack->Next = NULL;
 128         PostFix->Next = NULL;
 129         TheValues->Next = NULL;
 130
 131         StackFirst->Type = mEnd;
 132
 133         /* First tokenize the buffer */
 134
 135         while (*Math) {
 136                 if (isdigit(*Math) || *Math == '.') {
 137                         if (!ValueExpected) {
 138                                 strcpy(Buffer, "Unexpected value");
 139                                 goto End;
 140                         }
 141                         HasDot = 0;
 142                         Value = 0;
 143                         Floating = 1;
 144                         while (isdigit(*Math) || *Math == '.') {
 145                                 if (*Math == '.')
 146                                         if (HasDot) {
 147                                                 strcpy(Buffer, "Error in constant");
 148                                                 goto End;
 149                                         }
 150                                         else
 151                                                 HasDot = 1;
 152                                 else
 153                                         if (!HasDot)
 154                                                 Value = Value * 10 + *Math - '0';
 155                                         else {
 156                                                 Floating = Floating * 10;
 157                                                 Value = Value + (*Math - '0') / Floating;
 158                                         }
 159                                 ++Math;
 160                         }
 161                         if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 162                         List->Next = NULL;
 163                         List->Type = mNumber;
 164                         List->Value = Value;
 165                         if (Minus) {
 166                                 List->Value = -Value;
 167                                 Minus = 0;
 168                         }
 169                         ValueExpected = 0;
 170                 }
 171                 else switch (*Math) {
 172                         case ' ': case '\t':
 173                                 ++Math;
 174                                 break;
 175                         case '+':       case '-':
 176                         case '*':       case '/':
 177                         case '^':       case '(':
 178                         case ')':       case ']':
 179                                 if (*Math == '-' && ValueExpected) {
 180                                         Minus = !Minus;
 181                                         ++Math;
 182                                         break;
 183                                 }
 184                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto End;
 185                                 List->Next = NULL;
 186                                 switch (*Math) {
 187                                         case '+':       List->Type = mPlus;             break;
 188                                         case '-':       List->Type = mMinus;    break;
 189                                         case '*':       List->Type = mMult;             break;
 190                                         case '/':       List->Type = mDiv;              break;
 191                                         case '^':       List->Type = mPower;    break;
 192                                         case '(':       List->Type = mLt;               break;
 193                                         case ')':       List->Type = mRt;               break;
 194                                         case ']':       List->Type = mOpEnd;    break;
 195                                 }
 196                                 if (*Math != '(' && ValueExpected) {
 197                                         strcpy(Buffer, "Value expected");
 198                                         goto End;
 199                                 }
 200                                 if (*Math != ')' && *Math != ']')
 201                                         ValueExpected = 1;
 202                                 ++Math;
 203                                 break;
 204                         default:
 205                                 if (isalpha(*Math)) {
 206                                         Index = 0;
 207                                         while (isalpha(*Math))
 208                                                 Identifier[Index++] = *Math++;
 209                                         Identifier[Index] = '\0';
 210                                         OEndExpected = 0;
 211                                         if (!ValueExpected) {
 212                                                 strcpy(Buffer, "Unexpected value");
 213                                                 goto End;
 214                                         }
 215                                         if (!strcasecmp(Identifier, "e")) {
 216                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 217                                                 List->Next = NULL;
 218                                                 List->Type = mNumber;
 219                                                 List->Value = exp(1);
 220                                                 ValueExpected = 0;
 221                                         }
 222                                         else if (!strcasecmp(Identifier, "pi")) {
 223                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 224                                                 List->Next = NULL;
 225                                                 List->Type = mNumber;
 226                                                 List->Value = 4 * atan(1);
 227                                                 ValueExpected = 0;
 228                                         }
 229                                         else if (!strcasecmp(Identifier, "rand")) {
 230                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 231                                                 List->Next = NULL;
 232                                                 List->Type = mNumber;
 233                                                 List->Value = (double)rand() / (double)RAND_MAX;
 234                                                 ValueExpected = 0;
 235                                         }
 236                                         else if (!strcasecmp(Identifier, "exp")) {
 237                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 238                                                 List->Next = NULL;
 239                                                 List->Type = mOp;
 240                                                 List->OpType = otExp;
 241                                                 OEndExpected = 1;
 242                                         }
 243                                         else if (!strcasecmp(Identifier, "log")) {
 244                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 245                                                 List->Next = NULL;
 246                                                 List->Type = mOp;
 247                                                 List->OpType = otLog;
 248                                                 OEndExpected = 1;
 249                                         }
 250                                         else if (!strcasecmp(Identifier, "sin")) {
 251                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 252                                                 List->Next = NULL;
 253                                                 List->Type = mOp;
 254                                                 List->OpType = otSin;
 255                                                 OEndExpected = 1;
 256                                         }
 257                                         else if (!strcasecmp(Identifier, "asin")) {
 258                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 259                                                 List->Next = NULL;
 260                                                 List->Type = mOp;
 261                                                 List->OpType = otASin;
 262                                                 OEndExpected = 1;
 263                                         }
 264                                         else if (!strcasecmp(Identifier, "sinh")) {
 265                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 266                                                 List->Next = NULL;
 267                                                 List->Type = mOp;
 268                                                 List->OpType = otSinH;
 269                                                 OEndExpected = 1;
 270                                         }
 271                                         else if (!strcasecmp(Identifier, "cos")) {
 272                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 273                                                 List->Next = NULL;
 274                                                 List->Type = mOp;
 275                                                 List->OpType = otCos;
 276                                                 OEndExpected = 1;
 277                                         }
 278                                         else if (!strcasecmp(Identifier, "acos")) {
 279                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 280                                                 List->Next = NULL;
 281                                                 List->Type = mOp;
 282                                                 List->OpType = otACos;
 283                                                 OEndExpected = 1;
 284                                         }
 285                                         else if (!strcasecmp(Identifier, "cosh")) {
 286                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 287                                                 List->Next = NULL;
 288                                                 List->Type = mOp;
 289                                                 List->OpType = otCosH;
 290                                                 OEndExpected = 1;
 291                                         }
 292                                         else if (!strcasecmp(Identifier, "tan")) {
 293                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 294                                                 List->Next = NULL;
 295                                                 List->Type = mOp;
 296                                                 List->OpType = otTan;
 297                                                 OEndExpected = 1;
 298                                         }
 299                                         else if (!strcasecmp(Identifier, "atan")) {
 300                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 301                                                 List->Next = NULL;
 302                                                 List->Type = mOp;
 303                                                 List->OpType = otATan;
 304                                                 OEndExpected = 1;
 305                                         }
 306                                         else if (!strcasecmp(Identifier, "tanh")) {
 307                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 308                                                 List->Next = NULL;
 309                                                 List->Type = mOp;
 310                                                 List->OpType = otTanH;
 311                                                 OEndExpected = 1;
 312                                         }
 313                                         else if (!strcasecmp(Identifier, "sqrt")) {
 314                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 315                                                 List->Next = NULL;
 316                                                 List->Type = mOp;
 317                                                 List->OpType = otSqrt;
 318                                                 OEndExpected = 1;
 319                                         }
 320                                         else if (!strcasecmp(Identifier, "abs")) {
 321                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 322                                                 List->Next = NULL;
 323                                                 List->Type = mOp;
 324                                                 List->OpType = otAbs;
 325                                                 OEndExpected = 1;
 326                                         }
 327                                         else if (!strcasecmp(Identifier, "ceil")) {
 328                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 329                                                 List->Next = NULL;
 330                                                 List->Type = mOp;
 331                                                 List->OpType = otCeil;
 332                                                 OEndExpected = 1;
 333                                         }
 334                                         else if (!strcasecmp(Identifier, "floor")) {
 335                                                 if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 336                                                 List->Next = NULL;
 337                                                 List->Type = mOp;
 338                                                 List->OpType = otFloor;
 339                                                 OEndExpected = 1;
 340                                         }
 341                                         else {
 342                                                 strcpy(Buffer, "Unexpected Identifier");
 343                                                 goto End;
 344                                         }
 345                                         if (OEndExpected) {
 346                                                 while (*Math == ' ' || *Math == '\t')
 347                                                         ++Math;
 348                                                 if (*Math != '[') {
 349                                                         strcpy(Buffer, "'[' expected");
 350                                                         goto End;
 351                                                 }
 352                                                 ++Math;
 353                                         }
 354                                 }
 355                                 else {
 356                                         strcpy(Buffer, "Unknown character in expression");
 357                                         goto End;
 358                                 }
 359                 }
 360         }
 361         if (ValueExpected) {
 362                 strcpy(Buffer, "Value expected");
 363                 goto End;
 364         }
 365         if (!(List = List->Next = malloc(sizeof(struct MathToken)))) goto MemError;
 366         List->Next = NULL;
 367         List->Type = mEnd;
 368
 369         /* We've got them tokenized now... now convert it
 370                 from infix notation to postfix notation */
 371
 372         List = ListFirst->Next;
 373         while (List) {
 374                 if (List->Type == mNumber) {
 375                         PostFix = PostFix->Next = List;
 376                         ListFirst = List = List->Next;
 377                         PostFix->Next = NULL;
 378                 }
 379                 else switch (TranslateTable[Stack->Type][List->Type]) {
 380                         case 1:
 381                                 List->Previous = Stack;
 382                                 Stack = Stack->Next = List;
 383                                 ListFirst = List = List->Next;
 384                                 Stack->Next = NULL;
 385                                 break;
 386                         case 2:
 387                                 PostFix = PostFix->Next = Stack;
 388                                 Stack = Stack->Previous;
 389                                 Stack->Next = NULL;
 390                                 break;
 391                         case 3:
 392                                 Stack = Stack->Previous;
 393                                 free(Stack->Next);
 394                                 Stack->Next = NULL;
 395                                 Temp = List;
 396                                 ListFirst = List = List->Next;
 397                                 free(Temp);
 398                                 break;
 399                         case 4:
 400                                 PostFix = PostFix->Next = List;
 401                                 ListFirst = List = List->Next;
 402                                 break;
 403                         case 5:
 404                                 strcpy(Buffer, "Error in expression");
 405                                 goto End;
 406                         case 6:
 407                                 PostFix = PostFix->Next = Stack;
 408                                 Stack = Stack->Previous;
 409                                 Stack->Next = NULL;
 410                                 Temp = List;
 411                                 ListFirst = List = List->Next;
 412                                 free(Temp);
 413                                 break;
 414                         default:
 415                                 strcpy(Buffer, "Internal error");
 416                                 goto End;
 417                 }
 418         }
 419
 420         /* Now we've got everything in Postfix notation... calculate it now */
 421
 422         PostFix = PostFixFirst->Next;
 423         while (PostFix) {
 424                 switch (PostFix->Type) {
 425                         case mNumber:
 426                                 if (!(TheValues->Next = malloc(sizeof(struct Values)))) goto MemError;
 427                                 TheValues->Next->Previous = TheValues;
 428                                 TheValues = TheValues->Next;
 429                                 TheValues->Next = NULL;
 430                                 TheValues->Value = PostFix->Value;
 431                                 break;
 432                         case mPlus:
 433                                 TheValues->Previous->Value += TheValues->Value;
 434                                 TheValues = TheValues->Previous;
 435                                 free(TheValues->Next);
 436                                 TheValues->Next = NULL;
 437                                 break;
 438                         case mMinus:
 439                                 TheValues->Previous->Value -= TheValues->Value;
 440                                 TheValues = TheValues->Previous;
 441                                 free(TheValues->Next);
 442                                 TheValues->Next = NULL;
 443                                 break;
 444                         case mMult:
 445                                 TheValues->Previous->Value *= TheValues->Value;
 446                                 TheValues = TheValues->Previous;
 447                                 free(TheValues->Next);
 448                                 TheValues->Next = NULL;
 449                                 break;
 450                         case mDiv:
 451                                 if (TheValues->Value == 0) {
 452                                         strcpy(Buffer, "Division by zero error!");
 453                                         goto End;
 454                                 }
 455                                 TheValues->Previous->Value /= TheValues->Value;
 456                                 TheValues = TheValues->Previous;
 457                                 free(TheValues->Next);
 458                                 TheValues->Next = NULL;
 459                                 break;
 460                         case mPower:
 461                                 TheValues->Previous->Value = pow(TheValues->Previous->Value, TheValues->Value);
 462                                 TheValues = TheValues->Previous;
 463                                 free(TheValues->Next);
 464                                 TheValues->Next = NULL;
 465                                 break;
 466                         case mEnd:
 467                                 Value = TheValues->Value;
 468                                 break;
 469                         case mOp:
 470                                 switch (PostFix->OpType) {
 471                     case otExp:
 472                         TheValues->Value = exp(TheValues->Value);
 473                         break;
 474                                         case otLog:
 475                                                 if (TheValues->Value <= 0) {
 476                                                         strcpy(Buffer, "Log of non-positive value error");
 477                                                         goto End;
 478                                                 }
 479                                                 TheValues->Value = log(TheValues->Value);
 480                                                 break;
 481                                         case otSin:
 482                                                 TheValues->Value = sin(TheValues->Value);
 483                                                 break;
 484                                         case otASin:
 485                                                 if (TheValues->Value < -1 || TheValues->Value > 1) {
 486                                                         strcpy(Buffer, "Domain error");
 487                                                         goto End;
 488                                                 }
 489                                                 TheValues->Value = asin(TheValues->Value);
 490                                                 break;
 491                                         case otSinH:
 492                                                 TheValues->Value = sinh(TheValues->Value);
 493                                         case otCos:
 494                                                 TheValues->Value = cos(TheValues->Value);
 495                                                 break;
 496                                         case otACos:
 497                                                 if (TheValues->Value < -1 || TheValues->Value > 1) {
 498                                                         strcpy(Buffer, "Domain error");
 499                                                         goto End;
 500                                                 }
 501                                                 TheValues->Value = acos(TheValues->Value);
 502                                                 break;
 503                                         case otCosH:
 504                                                 TheValues->Value = cosh(TheValues->Value);
 505                                                 break;
 506                                         case otTan:
 507                                                 TheValues->Value = tan(TheValues->Value);
 508                                                 break;
 509                                         case otATan:
 510                                                 TheValues->Value = atan(TheValues->Value);
 511                                                 break;
 512                                         case otTanH:
 513                                                 TheValues->Value = tanh(TheValues->Value);
 514                                                 break;
 515                                         case otSqrt:
 516                                                 if (TheValues->Value < 0) {
 517                                                         strcpy(Buffer, "Sqrt from number < 0");
 518                                                         goto End;
 519                                                 }
 520                                                 TheValues->Value = sqrt(TheValues->Value);
 521                                                 break;
 522                                         case otAbs:
 523                                                 TheValues->Value = fabs(TheValues->Value);
 524                                                 break;
 525                                         case otCeil:
 526                                                 TheValues->Value = ceil(TheValues->Value);
 527                                                 break;
 528                                         case otFloor:
 529                                                 TheValues->Value = floor(TheValues->Value);
 530                                                 break;
 531                                 }
 532                                 break;
 533                         /* The following three do not occur. They are here to prevent compiler warnings */
 534                         case mLt:
 535                         case mRt:
 536                         case mOpEnd:
 537                                 break;
 538                 }
 539                 PostFix = PostFix->Next;
 540         }
 541
 542         if (fabs(Value) < 1000000 && (fabs(Value) > 0.001 || Value == 0.0))
 543         {
 544                 if (fabs(Value - floor(Value + 0.5)) < 0.00001) {
 545                         sprintf(Buffer, "%.0f", Value);
 546                 }
 547                 else {
 548                         sprintf(Buffer, "%f", Value);
 549                 }
 550         }
 551         else {
 552                 sprintf(Buffer, "%E", Value);
 553         }
 554 End:
 555         /* Free up memory here */
 556
 557         List = ListFirst;
 558         while (List) {
 559                 Temp = List;
 560                 List = List->Next;
 561                 free(Temp);
 562         }
 563
 564         Stack = StackFirst;
 565         while (Stack) {
 566                 Temp = Stack;
 567                 Stack = Stack->Next;
 568                 free(Temp);
 569         }
 570
 571         PostFix = PostFixFirst;
 572         while (PostFix) {
 573                 Temp = PostFix;
 574                 PostFix = PostFix->Next;
 575                 free(Temp);
 576         }
 577
 578         TheValues = TheValuesFirst;
 579         while (TheValues) {
 580                 Temp = TheValues;
 581                 TheValues = TheValues->Next;
 582                 free(Temp);
 583         }
 584
 585         return;
 586
 587 MemError:
 588         strcpy(Buffer, "Couldn't allocate enough memory");
 589         goto End;
 590 }