1 // We want C99 functionality if it is available (it gives us long doubles) 2 #define _ISOC9X_SOURCE 3 4 #include <string.h> 5 #include <ctype.h> 6 #include <stdlib.h> 7 #include <stdio.h> 8 #include <string.h> 9 #include <limits.h> 10 #include <math.h> 11 #include <float.h> 12 #include <errno.h> 13 #include "rpn.h" 14 15 #define VERSION "RPN version 0.1" 16 17 // ------------------------------------------------------------------------- 18 // Misc. macros 19 // ------------------------------------------------------------------------- 20 21 // A macro to make sure we have enough parameters on the stack 22 #define STACK_CHECK(n) \ 23 if(ssize < n) { \ 24 STRNCPY(output, "Not enough parameters", out_len); \ 25 return RPN_BAD_PARAM; \ 26 } 27 28 // This should be a large enough stack size for most operations 29 #define MAX_STACK_SIZE 20 30 #define MAX_TOKEN_SIZE 512 31 32 // FLOAT is the best floating-point type we can get 33 // (hopefully, HUGE_VALL should only be defined on C99 platforms, which should 34 // have all the functions listed below) 35 #ifdef HUGE_VALL 36 # define FLOAT long double 37 # define FLOOR floorl 38 # define CEIL ceill 39 # define FMOD fmodl 40 # define POW powl 41 # define SQRT sqrtl 42 # define ABS fabsl 43 # define FMA(x, y, z) ((x) * (y) + (z)) 44 # define FREXP frexpl 45 # define LOG logl 46 # define MODF modfl 47 # define FLOAT_DIG LDBL_DIG 48 #else 49 # define FLOAT double 50 # define FLOOR floor 51 # define CEIL ceil 52 # define FMOD fmod 53 # define POW pow 54 # define SQRT sqrt 55 # define ABS fabs 56 # define FMA(x, y, z) ((x) * (y) + (z)) 57 # define FREXP frexp 58 # define LOG log 59 # define MODF modf 60 # define FLOAT_DIG DBL_DIG 61 #endif 62 63 # define TRUNC(x) (((x) >= 0.0) ? (FLOOR(x)) : (CEIL(x))) 64 65 // strncpy does not null-terminate 66 #define STRNCPY(dest, src, n) \ 67 do { \ 68 strncpy(dest, src, n); \ 69 dest[n] = '\0'; \ 70 } while(0) 71 72 // Check errno, and set buf to an error string and return if set 73 #define CHECK_ERRNO(buf, len, retval) \ 74 if(errno) { \ 75 STRNCPY(buf, strerror(errno), len); \ 76 return retval; \ 77 } 78 79 // ------------------------------------------------------------------------- 80 // Utility functions 81 // ------------------------------------------------------------------------- 82 83 // A modified verison of dave2548's power() function. 84 static FLOAT ipow(FLOAT number, int power) { 85 FLOAT temp; 86 87 if(power == 0.0) { 88 return 1.0; 89 } else if(power == 1.0) { 90 return number; 91 } else if(power < 0.0) { 92 return 1.0/(ipow(number, -power)); 93 } else if(power % 2 == 0) { 94 temp = ipow(number, power / 2); 95 return(temp * temp); 96 } else { 97 temp = ipow(number, power / 2); 98 return(temp * temp * number); 99 } 100 } 101 102 // A helper macro for my_atof; take a digit, do error checking, and add it 103 // on to the mantissa 104 #define ADD_DIGIT(fl, dig, mult, coeff) \ 105 if((dig) <= (base)) { \ 106 mantissa = FMA(mantissa, (mult), (dig) * (coeff)); \ 107 } else { \ 108 errno = EINVAL; \ 109 return 0.0; \ 110 } 111 112 // Given a string, create a FLOAT from it, using the given base. We assume 113 // ASCII. Sets errno on error. 114 static FLOAT my_atof(char * input, int base) { 115 FLOAT mantissa = 0.0; 116 long int exponent = 0; 117 FLOAT multiplier = base; 118 FLOAT coeff = 1.0; 119 char c; 120 121 // Loop through the string 122 errno = 0; 123 while(*input != '\0') { 124 c = toupper(*input); 125 if(isdigit(c)) { 126 ADD_DIGIT(mantissa, c - '0', multiplier, 1.0/coeff); 127 } else if(isupper(c)) { 128 // Check for exponent 129 if(c == 'E' && base < 'E' - 'A' + 10) { 130 exponent = strtoul(input+1, NULL, base); 131 if(errno) return 0.0; 132 break; 133 } else { 134 ADD_DIGIT(mantissa, c - 'A' + 10, multiplier, 1.0/coeff); 135 } 136 } else if(c == '-') { 137 mantissa = -mantissa; 138 } else if(c == '.') { 139 multiplier = 1.0; 140 } else { 141 errno = EINVAL; 142 return 0.0; 143 } 144 ++input; 145 if(multiplier == 1.0) coeff *= base; 146 } 147 148 // There's probably a better way to do this 149 return mantissa * ipow(base, exponent); 150 } 151 152 // A helper macro for my_ftoa; convert an integer into a digit (char), 153 // returning 0 if the value is invalid 154 #define INT_TO_DIGIT(x) \ 155 (((x) < 10) ? ((x) + '0') : (((x) < 36) ? ((x) + 'A' - 10) : (0))) 156 157 // A helper macro for my_ftoa; do error checking and put ch into buf 158 #define BUF_ADD(buf, end, ch) \ 159 if(buf < end) *buf++ = ch 160 161 // A helper macro for my_ftoa; given a digit, put it into buf 162 #define DO_DIGIT(buf, end, x) \ 163 do { \ 164 char c = INT_TO_DIGIT(x); \ 165 if(c) {\ 166 BUF_ADD(buf, end, c); \ 167 } else { \ 168 errno = EINVAL; \ 169 return; \ 170 } \ 171 } while(0) 172 173 // A helper macro for my_ftoa; terminate a string safely. 174 #define DO_TERMINATE(buf, end) \ 175 if(buf < end) { \ 176 *buf = 0; \ 177 } else { \ 178 *(buf-1) = 0; \ 179 } 180 181 // Given a FLOAT as input, create a string that contains the digits of the 182 // input value as they would appear in the given base. Puts the exponent 183 // into exp as an integer. 184 static void my_ftoa(FLOAT input, int base, char *buf, size_t buflen, int *exp) { 185 char *end = buf + buflen; 186 char *start = buf; 187 FLOAT frac; 188 FLOAT whole; 189 int j; 190 int max_digits; 191 192 // Check for negative value 193 if(input < 0.0) { 194 BUF_ADD(buf, end, '-'); 195 input = -input; 196 } 197 198 // Extract the exponent 199 input = FREXP(input, exp); 200 frac = *exp * LOG(2)/LOG(base); 201 frac = MODF(frac, &whole); 202 *exp = TRUNC(whole); 203 input *= POW(base, frac); 204 (*exp)++; 205 206 // Find the number of digits we want 207 max_digits = LOG(10)/LOG(base) * FLOAT_DIG; 208 209 // Don't put a leading zero on the string 210 input = MODF(input, &whole); 211 if(TRUNC(whole) != 0) { 212 DO_DIGIT(buf, end, TRUNC(whole)); 213 } else { 214 --(*exp); 215 } 216 input *= base; 217 218 // Iterate through the string and generate the digits 219 for(j = 1; j < max_digits-1 && input > 0.0; ++j) { 220 input = MODF(input, &whole); 221 DO_DIGIT(buf, end, TRUNC(whole)); 222 input *= base; 223 } 224 DO_TERMINATE(buf, end); 225 226 // Perform some special checks if the string is larger than we have 227 // precision for 228 if(j >= max_digits-1) { 229 int i, j; 230 char *ptr; 231 char mbase; 232 FLOAT x, y; 233 234 // We want to round the last digit 235 input = MODF(input, &whole); 236 x = MODF(input*base, &y); 237 if(y >= base/2 && whole < base-1) ++whole; 238 DO_DIGIT(buf, end, TRUNC(whole)); 239 input *= base; 240 DO_TERMINATE(buf, end); 241 242 --buf; 243 244 // Check for a number that can be rounded down 245 for(j = 0; j < 2; ++j) { 246 for(i = 0, ptr = buf-j; *ptr == '0' && ptr > start; --ptr) ++i; 247 if(i >= 5) { 248 for(ptr = buf-j; *ptr == '0' && ptr > start; --ptr) *ptr = '\0'; 249 } 250 } 251 252 // Find the max digit for this base (in ascii); we'll use this below 253 mbase = INT_TO_DIGIT(base - 1); 254 255 // Check for a number that can be rounded up 256 for(j = 0; j < 5; ++j) { 257 for(i = 0, ptr = buf-j; *ptr == mbase && ptr > start; --ptr) ++i; 258 if(i >= 5) { 259 for(ptr = buf-j; *ptr == mbase && ptr > start; --ptr) { 260 *ptr = '\0'; 261 } 262 ++(*ptr); 263 if(ptr == start) { 264 if(*ptr > '9') { 265 *ptr = *ptr - '0' + 'A' - 10; 266 if(*exp >= 0) ++(*exp); 267 } 268 if(*ptr > mbase) *ptr = '1'; 269 } 270 } 271 } 272 } 273 } 274 275 // Move memory from src to dest, being sure not to pass outside of buf. 276 static void rpn_mem_move(char * dest, char * src, int len, char * buf, int buf_len) { 277 char *end = buf + buf_len; 278 279 while(len > 0 && (dest < buf || src < buf)) { 280 dest++; src++; len--; 281 } 282 283 while(dest + len > end || src + len > end) len--; // TODO: This is SLOW! 284 285 if(len >= 0) memmove(dest, src, len); 286 } 287 288 // Insert a decimal at position loc 289 static void rpn_insert_decimal(char *str, int len, int str_len, int loc) { 290 rpn_mem_move(str+loc+1, str+loc, str_len-loc+1, str, len); 291 if(loc < len) str[loc] = '.'; 292 } 293 294 // Convert a string to exponent notation 295 static void rpn_exponent_notation(char *str, int len, long int exponent, int str_len) { 296 // We can't fit the whole string, so use exponent notation 297 int loc = str_len + 1; 298 if(loc < len && len > 2 && str[1] == '\0') { 299 // Add a zero to the end of the number 300 str[1] = '0'; 301 loc++; 302 } 303 if(loc > len-17) loc = len-17; 304 rpn_insert_decimal(str, len, str_len, 1); 305 snprintf(str+loc, 16, "e%ld", exponent-1); 306 } 307 308 // Create human-readable output from a floating-point number. 309 // Returns 0 on success, -1 on failure. 310 static int rpn_make_string(FLOAT input, char *str, int len, int base) { 311 int exponent; 312 int str_len, j; 313 314 if(input < 0.0) len--; 315 316 // Get the string in mantissa-exponent form 317 my_ftoa(input, base, str, len, &exponent); 318 CHECK_ERRNO(str, len, -1); 319 320 // printf("%s %d\n", str, (int)exponent); 321 str_len = strlen(str); 322 if(len > 0 && str[0] == '-') { 323 str++; 324 str_len--; 325 } 326 327 // zero is a special case 328 if(*str == '\0') { 329 STRNCPY(str, "0", len); 330 return 0; 331 } 332 333 if(exponent < str_len) { 334 // The number includes all the information we need. 335 if(exponent > 0) { 336 // We must add a decimal point, since 337 rpn_insert_decimal(str, len, str_len, exponent); 338 } else { 339 // The number is much less than zero. 340 if(str_len - exponent + 3 > len) { 341 // We can't fit the whole string, so use exponent notation 342 rpn_exponent_notation(str, len, exponent, str_len); 343 } else { 344 // We can just add zero's to the beginning of the string 345 rpn_mem_move(str-exponent+2, str, str_len+1, str, len); 346 if(0 < len) str[0] = '0'; 347 if(1 < len) str[1] = '.'; 348 for(j = 2; j < 2-exponent; ++j) { 349 if(j < len) str[j] = '0'; 350 } 351 } 352 } 353 } else /* if(exponent > str_len) */ { 354 // The number is bigger than what the string represents 355 if(exponent >= len) { 356 // We can't fit the whole string, so use exponent notation 357 rpn_exponent_notation(str, len, exponent, str_len); 358 } else { 359 // We can just add zero's to the end of the string 360 for(j = str_len; j < exponent; ++j) { 361 if(j < len) str[j] = '0'; 362 } 363 if(exponent < len) str[exponent] = '\0'; 364 } 365 } 366 367 if(len-1 > 0) str[len-1] = '\0'; // just in case 368 return 0; 369 } 370 371 // ------------------------------------------------------------------------- 372 // Initialization and destruction 373 // ------------------------------------------------------------------------- 374 375 void rpn_calc_close(void) { 376 } 377 378 void rpn_calc_init(void) { 379 } 380 381 // ------------------------------------------------------------------------- 382 // The calculator 383 // ------------------------------------------------------------------------- 384 385 static int rpn_calc_internal( 386 const char *input, 387 char *output, 388 size_t out_len, 389 FLOAT *stack) { 390 391 char real_token[MAX_TOKEN_SIZE+1] = "0"; 392 char * const token = real_token + 1; 393 char * new_token; 394 int ssize = 0; 395 int token_len = 0; 396 int ibase = 10, obase = 10; 397 int have_exponent = 0; 398 399 for(;; ++input) { 400 if(isdigit(*input) || *input == '.' || 401 (ibase > 10 && ibase <= 16 && 402 toupper(*input) >= 'A' && toupper(*input) <= 'F') || 403 (ibase > 16 && isupper(*input))) { 404 // Still processing this token 405 token[token_len++] = *input; 406 if(*input != 0) continue; 407 } 408 409 if(*input == 'e' || *input == 'E') { 410 // exponent 411 token[token_len++] = *input; 412 have_exponent = 1; 413 continue; 414 } 415 416 if(have_exponent && *input == '-') { 417 // negative exponent 418 token[token_len++] = *input; 419 continue; 420 } 421 422 if(token_len != 0) { 423 // End of token 424 if(ssize >= MAX_STACK_SIZE) { 425 STRNCPY(output, "Stack full", out_len); 426 return RPN_STACK_FULL; 427 } 428 token[token_len] = 0; 429 430 // my_atof might not accept numbers that begin with a period. 431 new_token = (token[0] == '.') ? real_token : token; 432 433 stack[ssize++] = my_atof(new_token, ibase); 434 CHECK_ERRNO(output, out_len, RPN_UNKNOWN); 435 token_len = 0; 436 have_exponent = 0; 437 } 438 439 // Check for end of string 440 if(*input == 0) break; 441 442 // Operation 443 switch(*input) { 444 case '+': 445 // Add 446 STACK_CHECK(2); 447 stack[ssize-2] += stack[ssize-1]; 448 ssize--; 449 break; 450 451 case '-': 452 // Subtract 453 STACK_CHECK(2); 454 stack[ssize-2] -= stack[ssize-1]; 455 ssize--; 456 break; 457 458 case '*': 459 // Multiply 460 STACK_CHECK(2); 461 stack[ssize-2] *= stack[ssize-1]; 462 ssize--; 463 break; 464 465 case '/': 466 // Divide 467 STACK_CHECK(2); 468 if(stack[ssize-1] == 0.0) { 469 STRNCPY(output, "Divide by zero", out_len); 470 return RPN_DIVIDE_BY_ZERO; 471 } 472 stack[ssize-2] /= stack[ssize-1]; 473 ssize--; 474 break; 475 476 case '%': 477 // Modulus 478 STACK_CHECK(2); 479 if(stack[ssize-1] == 0.0) { 480 STRNCPY(output, "Divide by zero", out_len); 481 return RPN_DIVIDE_BY_ZERO; 482 } 483 stack[ssize-2] = FMOD(stack[ssize-2], stack[ssize-1]); 484 ssize--; 485 break; 486 487 case '~': 488 // Negate 489 STACK_CHECK(1); 490 stack[ssize-1] = -stack[ssize-1]; 491 break; 492 493 case '^': 494 STACK_CHECK(2); 495 stack[ssize-2] = POW(stack[ssize-2], stack[ssize-1]); 496 ssize--; 497 break; 498 499 case 'r': 500 // Swap 501 STACK_CHECK(2); 502 { 503 FLOAT temp = stack[ssize-1]; 504 stack[ssize-1] = stack[ssize-2]; 505 stack[ssize-2] = temp; 506 } 507 break; 508 509 case 'v': 510 // Square root 511 STACK_CHECK(1); 512 if(stack[ssize-1] < 0.0) { 513 STRNCPY(output, "Cannot take sqrt of a negative", 514 out_len); 515 return RPN_ILLEGAL; 516 } 517 stack[ssize-1] = SQRT(stack[ssize-1]); 518 break; 519 520 case '|': 521 // Absolute value 522 STACK_CHECK(1); 523 stack[ssize-1] = ABS(stack[ssize-1]); 524 break; 525 526 case 'i': 527 // Set input base 528 STACK_CHECK(1); 529 ibase = FLOOR(stack[--ssize]); 530 if(ibase < 2 || ibase > 36) { 531 STRNCPY(output, "Invalid base", out_len); 532 return RPN_ILLEGAL; 533 } 534 break; 535 536 case 'o': 537 // Set output base 538 STACK_CHECK(1); 539 obase = FLOOR(stack[--ssize]); 540 if(obase < 2 || obase > 36) { 541 STRNCPY(output, "Invalid base", out_len); 542 return RPN_ILLEGAL; 543 } 544 break; 545 546 case ' ': 547 case '\t': 548 case '\r': 549 case '\n': 550 // Ignore whitespace 551 break; 552 553 default: 554 STRNCPY(output, "Illegal operation", out_len); 555 return RPN_ILLEGAL; 556 } 557 } 558 559 // Copy out the answer 560 if(ssize == 0) { 561 STRNCPY(output, "Empty stack", out_len); 562 return RPN_EMPTY_STACK; 563 } else if(ssize == 1) { 564 if(rpn_make_string(stack[0], output, out_len, obase) == -1) { 565 return RPN_UNKNOWN; 566 } 567 } else { 568 STRNCPY(output, "Stack not empty", out_len); 569 return RPN_NONEMPTY_STACK; 570 } 571 572 return RPN_OK; 573 } 574 575 int rpn_calc(const char *input, char *output, size_t out_len) { 576 FLOAT stack[MAX_STACK_SIZE]; 577 578 // strcasecmp won't work right with _ISOC9X_SOURCE defined. 579 if(!strcmp(input, "lag")) { 580 STRNCPY(output, "This is Efnet. What do you expect?", out_len); 581 return RPN_OK; 582 } else if(!strcmp(input, "help")) { 583 STRNCPY(output, 584 "Valid operations: " 585 "+ (add), " 586 "- (subtract), " 587 "* (multiply), " 588 "/ (divide), " 589 "~ (negate), " 590 "% (modulus), " 591 "^ (exponent), " 592 "r (swap), " 593 "v (sqrt), " 594 "| (abs), " 595 "i (set input base), " 596 "o (set output base); " 597 "bases higher than 16 require upper-case input", 598 out_len); 599 return RPN_OK; 600 } else if(!strcmp(input, "version")) { 601 STRNCPY(output, VERSION, out_len); 602 return RPN_OK; 603 } 604 605 // Do the calculation 606 return rpn_calc_internal(input, output, out_len, stack); 607 } |