src/rrd_rpncalc.c

   1 /****************************************************************************
   2  * RRDtool 1.2.23  Copyright by Tobi Oetiker, 1997-2007
   3  ****************************************************************************
   4  * rrd_rpncalc.c  RPN calculator functions
   5  ****************************************************************************/
   6
   7 #include "rrd_tool.h"
   8 #include "rrd_rpncalc.h"
   9 #include "rrd_graph.h"
  10 #include <limits.h>
  11
  12 short     addop2str(
  13     enum op_en op,
  14     enum op_en op_type,
  15     char *op_str,
  16     char **result_str,
  17     unsigned short *offset);
  18 int       tzoffset(
  19     time_t);            /* used to implement LTIME */
  20
  21 short rpn_compact(
  22     rpnp_t *rpnp,
  23     rpn_cdefds_t **rpnc,
  24     short *count)
  25 {
  26     short     i;
  27
  28     *count = 0;
  29     /* count the number of rpn nodes */
  30     while (rpnp[*count].op != OP_END)
  31         (*count)++;
  32     if (++(*count) > DS_CDEF_MAX_RPN_NODES) {
  33         rrd_set_error("Maximum %d RPN nodes permitted",
  34                       DS_CDEF_MAX_RPN_NODES);
  35         return -1;
  36     }
  37
  38     /* allocate memory */
  39     *rpnc = (rpn_cdefds_t *) calloc(*count, sizeof(rpn_cdefds_t));
  40     for (i = 0; rpnp[i].op != OP_END; i++) {
  41         (*rpnc)[i].op = (char) rpnp[i].op;
  42         if (rpnp[i].op == OP_NUMBER) {
  43             /* rpnp.val is a double, rpnc.val is a short */
  44             double    temp = floor(rpnp[i].val);
  45
  46             if (temp < SHRT_MIN || temp > SHRT_MAX) {
  47                 rrd_set_error
  48                     ("constants must be integers in the interval (%d, %d)",
  49                      SHRT_MIN, SHRT_MAX);
  50                 free(*rpnc);
  51                 return -1;
  52             }
  53             (*rpnc)[i].val = (short) temp;
  54         } else if (rpnp[i].op == OP_VARIABLE || rpnp[i].op == OP_PREV_OTHER) {
  55             (*rpnc)[i].val = (short) rpnp[i].ptr;
  56         }
  57     }
  58     /* terminate the sequence */
  59     (*rpnc)[(*count) - 1].op = OP_END;
  60     return 0;
  61 }
  62
  63 rpnp_t   *rpn_expand(
  64     rpn_cdefds_t *rpnc)
  65 {
  66     short     i;
  67     rpnp_t   *rpnp;
  68
  69     /* DS_CDEF_MAX_RPN_NODES is small, so at the expense of some wasted
  70      * memory we avoid any reallocs */
  71     rpnp = (rpnp_t *) calloc(DS_CDEF_MAX_RPN_NODES, sizeof(rpnp_t));
  72     if (rpnp == NULL)
  73         return NULL;
  74     for (i = 0; rpnc[i].op != OP_END; ++i) {
  75         rpnp[i].op = (long) rpnc[i].op;
  76         if (rpnp[i].op == OP_NUMBER) {
  77             rpnp[i].val = (double) rpnc[i].val;
  78         } else if (rpnp[i].op == OP_VARIABLE || rpnp[i].op == OP_PREV_OTHER) {
  79             rpnp[i].ptr = (long) rpnc[i].val;
  80         }
  81     }
  82     /* terminate the sequence */
  83     rpnp[i].op = OP_END;
  84     return rpnp;
  85 }
  86
  87 /* rpn_compact2str: convert a compact sequence of RPN operator nodes back
  88  * into a CDEF string. This function is used by rrd_dump.
  89  * arguments:
  90  *  rpnc: an array of compact RPN operator nodes
  91  *  ds_def: a pointer to the data source definition section of an RRD header
  92  *   for lookup of data source names by index
  93  *  str: out string, memory is allocated by the function, must be freed by the
  94  *   the caller */
  95 void rpn_compact2str(
  96     rpn_cdefds_t *rpnc,
  97     ds_def_t *ds_def,
  98     char **str)
  99 {
 100     unsigned short i, offset = 0;
 101     char      buffer[7];    /* short as a string */
 102
 103     for (i = 0; rpnc[i].op != OP_END; i++) {
 104         if (i > 0)
 105             (*str)[offset++] = ',';
 106
 107 #define add_op(VV,VVV) \
 108           if (addop2str(rpnc[i].op, VV, VVV, str, &offset) == 1) continue;
 109
 110         if (rpnc[i].op == OP_NUMBER) {
 111             /* convert a short into a string */
 112 #if defined(_WIN32) && !defined(__CYGWIN__) && !defined(__CYGWIN32__)
 113             _itoa(rpnc[i].val, buffer, 10);
 114 #else
 115             sprintf(buffer, "%d", rpnc[i].val);
 116 #endif
 117             add_op(OP_NUMBER, buffer)
 118         }
 119
 120         if (rpnc[i].op == OP_VARIABLE) {
 121             char     *ds_name = ds_def[rpnc[i].val].ds_nam;
 122
 123             add_op(OP_VARIABLE, ds_name)
 124         }
 125
 126         if (rpnc[i].op == OP_PREV_OTHER) {
 127             char     *ds_name = ds_def[rpnc[i].val].ds_nam;
 128
 129             add_op(OP_VARIABLE, ds_name)
 130         }
 131 #undef add_op
 132
 133 #define add_op(VV,VVV) \
 134           if (addop2str(rpnc[i].op, VV, #VVV, str, &offset) == 1) continue;
 135
 136         add_op(OP_ADD, +)
 137             add_op(OP_SUB, -)
 138             add_op(OP_MUL, *)
 139             add_op(OP_DIV, /)
 140             add_op(OP_MOD, %)
 141             add_op(OP_SIN, SIN)
 142             add_op(OP_COS, COS)
 143             add_op(OP_LOG, LOG)
 144             add_op(OP_FLOOR, FLOOR)
 145             add_op(OP_CEIL, CEIL)
 146             add_op(OP_EXP, EXP)
 147             add_op(OP_DUP, DUP)
 148             add_op(OP_EXC, EXC)
 149             add_op(OP_POP, POP)
 150             add_op(OP_LT, LT)
 151             add_op(OP_LE, LE)
 152             add_op(OP_GT, GT)
 153             add_op(OP_GE, GE)
 154             add_op(OP_EQ, EQ)
 155             add_op(OP_IF, IF)
 156             add_op(OP_MIN, MIN)
 157             add_op(OP_MAX, MAX)
 158             add_op(OP_LIMIT, LIMIT)
 159             add_op(OP_UNKN, UNKN)
 160             add_op(OP_UN, UN)
 161             add_op(OP_NEGINF, NEGINF)
 162             add_op(OP_NE, NE)
 163             add_op(OP_PREV, PREV)
 164             add_op(OP_INF, INF)
 165             add_op(OP_ISINF, ISINF)
 166             add_op(OP_NOW, NOW)
 167             add_op(OP_LTIME, LTIME)
 168             add_op(OP_TIME, TIME)
 169             add_op(OP_ATAN2, ATAN2)
 170             add_op(OP_ATAN, ATAN)
 171             add_op(OP_SQRT, SQRT)
 172             add_op(OP_SORT, SORT)
 173             add_op(OP_REV, REV)
 174             add_op(OP_TREND, TREND)
 175             add_op(OP_TRENDNAN, TRENDNAN)
 176             add_op(OP_RAD2DEG, RAD2DEG)
 177             add_op(OP_DEG2RAD, DEG2RAD)
 178             add_op(OP_AVG, AVG)
 179             add_op(OP_ABS, ABS)
 180 #undef add_op
 181     }
 182     (*str)[offset] = '\0';
 183
 184 }
 185
 186 short addop2str(
 187     enum op_en op,
 188     enum op_en op_type,
 189     char *op_str,
 190     char **result_str,
 191     unsigned short *offset)
 192 {
 193     if (op == op_type) {
 194         short     op_len;
 195
 196         op_len = strlen(op_str);
 197         *result_str = (char *) rrd_realloc(*result_str,
 198                                            (op_len + 1 +
 199                                             *offset) * sizeof(char));
 200         if (*result_str == NULL) {
 201             rrd_set_error("failed to alloc memory in addop2str");
 202             return -1;
 203         }
 204         strncpy(&((*result_str)[*offset]), op_str, op_len);
 205         *offset += op_len;
 206         return 1;
 207     }
 208     return 0;
 209 }
 210
 211 void parseCDEF_DS(
 212     const char *def,
 213     rrd_t *rrd,
 214     int ds_idx)
 215 {
 216     rpnp_t   *rpnp = NULL;
 217     rpn_cdefds_t *rpnc = NULL;
 218     short     count, i;
 219
 220     rpnp = rpn_parse((void *) rrd, def, &lookup_DS);
 221     if (rpnp == NULL) {
 222         rrd_set_error("failed to parse computed data source");
 223         return;
 224     }
 225     /* Check for OP nodes not permitted in COMPUTE DS.
 226      * Moved this check from within rpn_compact() because it really is
 227      * COMPUTE DS specific. This is less efficient, but creation doesn't
 228      * occur too often. */
 229     for (i = 0; rpnp[i].op != OP_END; i++) {
 230         if (rpnp[i].op == OP_TIME || rpnp[i].op == OP_LTIME ||
 231             rpnp[i].op == OP_PREV || rpnp[i].op == OP_COUNT) {
 232             rrd_set_error
 233                 ("operators time, ltime, prev and count not supported with DS COMPUTE");
 234             free(rpnp);
 235             return;
 236         }
 237     }
 238     if (rpn_compact(rpnp, &rpnc, &count) == -1) {
 239         free(rpnp);
 240         return;
 241     }
 242     /* copy the compact rpn representation over the ds_def par array */
 243     memcpy((void *) &(rrd->ds_def[ds_idx].par[DS_cdef]),
 244            (void *) rpnc, count * sizeof(rpn_cdefds_t));
 245     free(rpnp);
 246     free(rpnc);
 247 }
 248
 249 /* lookup a data source name in the rrd struct and return the index,
 250  * should use ds_match() here except:
 251  * (1) need a void * pointer to the rrd
 252  * (2) error handling is left to the caller
 253  */
 254 long lookup_DS(
 255     void *rrd_vptr,
 256     char *ds_name)
 257 {
 258     unsigned int i;
 259     rrd_t    *rrd;
 260
 261     rrd = (rrd_t *) rrd_vptr;
 262
 263     for (i = 0; i < rrd->stat_head->ds_cnt; ++i) {
 264         if (strcmp(ds_name, rrd->ds_def[i].ds_nam) == 0)
 265             return i;
 266     }
 267     /* the caller handles a bad data source name in the rpn string */
 268     return -1;
 269 }
 270
 271 /* rpn_parse : parse a string and generate a rpnp array; modified
 272  * str2rpn() originally included in rrd_graph.c
 273  * arguments:
 274  * key_hash: a transparent argument passed to lookup(); conceptually this
 275  *    is a hash object for lookup of a numeric key given a variable name
 276  * expr: the string RPN expression, including variable names
 277  * lookup(): a function that retrieves a numeric key given a variable name
 278  */
 279 rpnp_t   *rpn_parse(
 280     void *key_hash,
 281     const char *const expr_const,
 282     long      (*lookup) (void *,
 283                          char *))
 284 {
 285     int       pos = 0;
 286     char     *expr;
 287     long      steps = -1;
 288     rpnp_t   *rpnp;
 289     char      vname[MAX_VNAME_LEN + 10];
 290
 291     rpnp = NULL;
 292     expr = (char *) expr_const;
 293
 294     while (*expr) {
 295         if ((rpnp = (rpnp_t *) rrd_realloc(rpnp, (++steps + 2) *
 296                                            sizeof(rpnp_t))) == NULL) {
 297             return NULL;
 298         }
 299
 300         else if ((sscanf(expr, "%lf%n", &rpnp[steps].val, &pos) == 1)
 301                  && (expr[pos] == ',')) {
 302             rpnp[steps].op = OP_NUMBER;
 303             expr += pos;
 304         }
 305 #define match_op(VV,VVV) \
 306         else if (strncmp(expr, #VVV, strlen(#VVV))==0 && ( expr[strlen(#VVV)] == ',' || expr[strlen(#VVV)] == '\0' )){ \
 307             rpnp[steps].op = VV; \
 308             expr+=strlen(#VVV); \
 309         }
 310
 311
 312 #define match_op_param(VV,VVV) \
 313         else if (sscanf(expr, #VVV "(" DEF_NAM_FMT ")",vname) == 1) { \
 314           int length = 0; \
 315           if ((length = strlen(#VVV)+strlen(vname)+2, \
 316               expr[length] == ',' || expr[length] == '\0') ) { \
 317              rpnp[steps].op = VV; \
 318              rpnp[steps].ptr = (*lookup)(key_hash,vname); \
 319              if (rpnp[steps].ptr < 0) { \
 320                            free(rpnp); \
 321                            return NULL; \
 322                          } else expr+=length; \
 323           } \
 324         }
 325
 326         match_op(OP_ADD, +)
 327             match_op(OP_SUB, -)
 328             match_op(OP_MUL, *)
 329             match_op(OP_DIV, /)
 330             match_op(OP_MOD, %)
 331             match_op(OP_SIN, SIN)
 332             match_op(OP_COS, COS)
 333             match_op(OP_LOG, LOG)
 334             match_op(OP_FLOOR, FLOOR)
 335             match_op(OP_CEIL, CEIL)
 336             match_op(OP_EXP, EXP)
 337             match_op(OP_DUP, DUP)
 338             match_op(OP_EXC, EXC)
 339             match_op(OP_POP, POP)
 340             match_op(OP_LTIME, LTIME)
 341             match_op(OP_LT, LT)
 342             match_op(OP_LE, LE)
 343             match_op(OP_GT, GT)
 344             match_op(OP_GE, GE)
 345             match_op(OP_EQ, EQ)
 346             match_op(OP_IF, IF)
 347             match_op(OP_MIN, MIN)
 348             match_op(OP_MAX, MAX)
 349             match_op(OP_LIMIT, LIMIT)
 350             /* order is important here ! .. match longest first */
 351             match_op(OP_UNKN, UNKN)
 352             match_op(OP_UN, UN)
 353             match_op(OP_NEGINF, NEGINF)
 354             match_op(OP_NE, NE)
 355             match_op(OP_COUNT, COUNT)
 356             match_op_param(OP_PREV_OTHER, PREV)
 357             match_op(OP_PREV, PREV)
 358             match_op(OP_INF, INF)
 359             match_op(OP_ISINF, ISINF)
 360             match_op(OP_NOW, NOW)
 361             match_op(OP_TIME, TIME)
 362             match_op(OP_ATAN2, ATAN2)
 363             match_op(OP_ATAN, ATAN)
 364             match_op(OP_SQRT, SQRT)
 365             match_op(OP_SORT, SORT)
 366             match_op(OP_REV, REV)
 367             match_op(OP_TREND, TREND)
 368             match_op(OP_TRENDNAN, TRENDNAN)
 369             match_op(OP_RAD2DEG, RAD2DEG)
 370             match_op(OP_DEG2RAD, DEG2RAD)
 371             match_op(OP_AVG, AVG)
 372             match_op(OP_ABS, ABS)
 373 #undef match_op
 374             else if ((sscanf(expr, DEF_NAM_FMT "%n", vname, &pos) == 1)
 375                      && ((rpnp[steps].ptr = (*lookup) (key_hash, vname)) !=
 376                          -1)) {
 377             rpnp[steps].op = OP_VARIABLE;
 378             expr += pos;
 379         }
 380
 381         else {
 382             free(rpnp);
 383             return NULL;
 384         }
 385         if (*expr == 0)
 386             break;
 387         if (*expr == ',')
 388             expr++;
 389         else {
 390             free(rpnp);
 391             return NULL;
 392         }
 393     }
 394     rpnp[steps + 1].op = OP_END;
 395     return rpnp;
 396 }
 397
 398 void rpnstack_init(
 399     rpnstack_t *rpnstack)
 400 {
 401     rpnstack->s = NULL;
 402     rpnstack->dc_stacksize = 0;
 403     rpnstack->dc_stackblock = 100;
 404 }
 405
 406 void rpnstack_free(
 407     rpnstack_t *rpnstack)
 408 {
 409     if (rpnstack->s != NULL)
 410         free(rpnstack->s);
 411     rpnstack->dc_stacksize = 0;
 412 }
 413
 414 static int rpn_compare_double(
 415     const void *x,
 416     const void *y)
 417 {
 418     double    diff = *((const double *) x) - *((const double *) y);
 419
 420     return (diff < 0) ? -1 : (diff > 0) ? 1 : 0;
 421 }
 422
 423 /* rpn_calc: run the RPN calculator; also performs variable substitution;
 424  * moved and modified from data_calc() originally included in rrd_graph.c
 425  * arguments:
 426  * rpnp : an array of RPN operators (including variable references)
 427  * rpnstack : the initialized stack
 428  * data_idx : when data_idx is a multiple of rpnp.step, the rpnp.data pointer
 429  *   is advanced by rpnp.ds_cnt; used only for variable substitution
 430  * output : an array of output values; OP_PREV assumes this array contains
 431  *   the "previous" value at index position output_idx-1; the definition of
 432  *   "previous" depends on the calling environment
 433  * output_idx : an index into the output array in which to store the output
 434  *   of the RPN calculator
 435  * returns: -1 if the computation failed (also calls rrd_set_error)
 436  *           0 on success
 437  */
 438 short rpn_calc(
 439     rpnp_t *rpnp,
 440     rpnstack_t *rpnstack,
 441     long data_idx,
 442     rrd_value_t *output,
 443     int output_idx)
 444 {
 445     int       rpi;
 446     long      stptr = -1;
 447
 448     /* process each op from the rpn in turn */
 449     for (rpi = 0; rpnp[rpi].op != OP_END; rpi++) {
 450         /* allocate or grow the stack */
 451         if (stptr + 5 > rpnstack->dc_stacksize) {
 452             /* could move this to a separate function */
 453             rpnstack->dc_stacksize += rpnstack->dc_stackblock;
 454             rpnstack->s = rrd_realloc(rpnstack->s,
 455                                       (rpnstack->dc_stacksize) *
 456                                       sizeof(*(rpnstack->s)));
 457             if (rpnstack->s == NULL) {
 458                 rrd_set_error("RPN stack overflow");
 459                 return -1;
 460             }
 461         }
 462 #define stackunderflow(MINSIZE)                         \
 463         if(stptr<MINSIZE){                              \
 464             rrd_set_error("RPN stack underflow");       \
 465             return -1;                                  \
 466         }
 467
 468         switch (rpnp[rpi].op) {
 469         case OP_NUMBER:
 470             rpnstack->s[++stptr] = rpnp[rpi].val;
 471             break;
 472         case OP_VARIABLE:
 473         case OP_PREV_OTHER:
 474             /* Sanity check: VDEFs shouldn't make it here */
 475             if (rpnp[rpi].ds_cnt == 0) {
 476                 rrd_set_error("VDEF made it into rpn_calc... aborting");
 477                 return -1;
 478             } else {
 479                 /* make sure we pull the correct value from
 480                  * the *.data array. Adjust the pointer into
 481                  * the array acordingly. Advance the ptr one
 482                  * row in the rra (skip over non-relevant
 483                  * data sources)
 484                  */
 485                 if (rpnp[rpi].op == OP_VARIABLE) {
 486                     rpnstack->s[++stptr] = *(rpnp[rpi].data);
 487                 } else {
 488                     if ((output_idx) <= 0) {
 489                         rpnstack->s[++stptr] = DNAN;
 490                     } else {
 491                         rpnstack->s[++stptr] =
 492                             *(rpnp[rpi].data - rpnp[rpi].ds_cnt);
 493                     }
 494
 495                 }
 496                 if (data_idx % rpnp[rpi].step == 0) {
 497                     rpnp[rpi].data += rpnp[rpi].ds_cnt;
 498                 }
 499             }
 500             break;
 501         case OP_COUNT:
 502             rpnstack->s[++stptr] = (output_idx + 1);    /* Note: Counter starts at 1 */
 503             break;
 504         case OP_PREV:
 505             if ((output_idx) <= 0) {
 506                 rpnstack->s[++stptr] = DNAN;
 507             } else {
 508                 rpnstack->s[++stptr] = output[output_idx - 1];
 509             }
 510             break;
 511         case OP_UNKN:
 512             rpnstack->s[++stptr] = DNAN;
 513             break;
 514         case OP_INF:
 515             rpnstack->s[++stptr] = DINF;
 516             break;
 517         case OP_NEGINF:
 518             rpnstack->s[++stptr] = -DINF;
 519             break;
 520         case OP_NOW:
 521             rpnstack->s[++stptr] = (double) time(NULL);
 522             break;
 523         case OP_TIME:
 524             /* HACK: this relies on the data_idx being the time,
 525              ** which the within-function scope is unaware of */
 526             rpnstack->s[++stptr] = (double) data_idx;
 527             break;
 528         case OP_LTIME:
 529             rpnstack->s[++stptr] =
 530                 (double) tzoffset(data_idx) + (double) data_idx;
 531             break;
 532         case OP_ADD:
 533             stackunderflow(1);
 534             rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1]
 535                 + rpnstack->s[stptr];
 536             stptr--;
 537             break;
 538         case OP_SUB:
 539             stackunderflow(1);
 540             rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1]
 541                 - rpnstack->s[stptr];
 542             stptr--;
 543             break;
 544         case OP_MUL:
 545             stackunderflow(1);
 546             rpnstack->s[stptr - 1] = (rpnstack->s[stptr - 1])
 547                 * (rpnstack->s[stptr]);
 548             stptr--;
 549             break;
 550         case OP_DIV:
 551             stackunderflow(1);
 552             rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1]
 553                 / rpnstack->s[stptr];
 554             stptr--;
 555             break;
 556         case OP_MOD:
 557             stackunderflow(1);
 558             rpnstack->s[stptr - 1] = fmod(rpnstack->s[stptr - 1]
 559                                           , rpnstack->s[stptr]);
 560             stptr--;
 561             break;
 562         case OP_SIN:
 563             stackunderflow(0);
 564             rpnstack->s[stptr] = sin(rpnstack->s[stptr]);
 565             break;
 566         case OP_ATAN:
 567             stackunderflow(0);
 568             rpnstack->s[stptr] = atan(rpnstack->s[stptr]);
 569             break;
 570         case OP_RAD2DEG:
 571             stackunderflow(0);
 572             rpnstack->s[stptr] = 57.29577951 * rpnstack->s[stptr];
 573             break;
 574         case OP_DEG2RAD:
 575             stackunderflow(0);
 576             rpnstack->s[stptr] = 0.0174532952 * rpnstack->s[stptr];
 577             break;
 578         case OP_ATAN2:
 579             stackunderflow(1);
 580             rpnstack->s[stptr - 1] = atan2(rpnstack->s[stptr - 1],
 581                                            rpnstack->s[stptr]);
 582             stptr--;
 583             break;
 584         case OP_COS:
 585             stackunderflow(0);
 586             rpnstack->s[stptr] = cos(rpnstack->s[stptr]);
 587             break;
 588         case OP_CEIL:
 589             stackunderflow(0);
 590             rpnstack->s[stptr] = ceil(rpnstack->s[stptr]);
 591             break;
 592         case OP_FLOOR:
 593             stackunderflow(0);
 594             rpnstack->s[stptr] = floor(rpnstack->s[stptr]);
 595             break;
 596         case OP_LOG:
 597             stackunderflow(0);
 598             rpnstack->s[stptr] = log(rpnstack->s[stptr]);
 599             break;
 600         case OP_DUP:
 601             stackunderflow(0);
 602             rpnstack->s[stptr + 1] = rpnstack->s[stptr];
 603             stptr++;
 604             break;
 605         case OP_POP:
 606             stackunderflow(0);
 607             stptr--;
 608             break;
 609         case OP_EXC:
 610             stackunderflow(1);
 611             {
 612                 double    dummy;
 613
 614                 dummy = rpnstack->s[stptr];
 615                 rpnstack->s[stptr] = rpnstack->s[stptr - 1];
 616                 rpnstack->s[stptr - 1] = dummy;
 617             }
 618             break;
 619         case OP_EXP:
 620             stackunderflow(0);
 621             rpnstack->s[stptr] = exp(rpnstack->s[stptr]);
 622             break;
 623         case OP_LT:
 624             stackunderflow(1);
 625             if (isnan(rpnstack->s[stptr - 1]));
 626             else if (isnan(rpnstack->s[stptr]))
 627                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 628             else
 629                 rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1] <
 630                     rpnstack->s[stptr] ? 1.0 : 0.0;
 631             stptr--;
 632             break;
 633         case OP_LE:
 634             stackunderflow(1);
 635             if (isnan(rpnstack->s[stptr - 1]));
 636             else if (isnan(rpnstack->s[stptr]))
 637                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 638             else
 639                 rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1] <=
 640                     rpnstack->s[stptr] ? 1.0 : 0.0;
 641             stptr--;
 642             break;
 643         case OP_GT:
 644             stackunderflow(1);
 645             if (isnan(rpnstack->s[stptr - 1]));
 646             else if (isnan(rpnstack->s[stptr]))
 647                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 648             else
 649                 rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1] >
 650                     rpnstack->s[stptr] ? 1.0 : 0.0;
 651             stptr--;
 652             break;
 653         case OP_GE:
 654             stackunderflow(1);
 655             if (isnan(rpnstack->s[stptr - 1]));
 656             else if (isnan(rpnstack->s[stptr]))
 657                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 658             else
 659                 rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1] >=
 660                     rpnstack->s[stptr] ? 1.0 : 0.0;
 661             stptr--;
 662             break;
 663         case OP_NE:
 664             stackunderflow(1);
 665             if (isnan(rpnstack->s[stptr - 1]));
 666             else if (isnan(rpnstack->s[stptr]))
 667                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 668             else
 669                 rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1] ==
 670                     rpnstack->s[stptr] ? 0.0 : 1.0;
 671             stptr--;
 672             break;
 673         case OP_EQ:
 674             stackunderflow(1);
 675             if (isnan(rpnstack->s[stptr - 1]));
 676             else if (isnan(rpnstack->s[stptr]))
 677                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 678             else
 679                 rpnstack->s[stptr - 1] = rpnstack->s[stptr - 1] ==
 680                     rpnstack->s[stptr] ? 1.0 : 0.0;
 681             stptr--;
 682             break;
 683         case OP_IF:
 684             stackunderflow(2);
 685             rpnstack->s[stptr - 2] = rpnstack->s[stptr - 2] != 0.0 ?
 686                 rpnstack->s[stptr - 1] : rpnstack->s[stptr];
 687             stptr--;
 688             stptr--;
 689             break;
 690         case OP_MIN:
 691             stackunderflow(1);
 692             if (isnan(rpnstack->s[stptr - 1]));
 693             else if (isnan(rpnstack->s[stptr]))
 694                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 695             else if (rpnstack->s[stptr - 1] > rpnstack->s[stptr])
 696                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 697             stptr--;
 698             break;
 699         case OP_MAX:
 700             stackunderflow(1);
 701             if (isnan(rpnstack->s[stptr - 1]));
 702             else if (isnan(rpnstack->s[stptr]))
 703                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 704             else if (rpnstack->s[stptr - 1] < rpnstack->s[stptr])
 705                 rpnstack->s[stptr - 1] = rpnstack->s[stptr];
 706             stptr--;
 707             break;
 708         case OP_LIMIT:
 709             stackunderflow(2);
 710             if (isnan(rpnstack->s[stptr - 2]));
 711             else if (isnan(rpnstack->s[stptr - 1]))
 712                 rpnstack->s[stptr - 2] = rpnstack->s[stptr - 1];
 713             else if (isnan(rpnstack->s[stptr]))
 714                 rpnstack->s[stptr - 2] = rpnstack->s[stptr];
 715             else if (rpnstack->s[stptr - 2] < rpnstack->s[stptr - 1])
 716                 rpnstack->s[stptr - 2] = DNAN;
 717             else if (rpnstack->s[stptr - 2] > rpnstack->s[stptr])
 718                 rpnstack->s[stptr - 2] = DNAN;
 719             stptr -= 2;
 720             break;
 721         case OP_UN:
 722             stackunderflow(0);
 723             rpnstack->s[stptr] = isnan(rpnstack->s[stptr]) ? 1.0 : 0.0;
 724             break;
 725         case OP_ISINF:
 726             stackunderflow(0);
 727             rpnstack->s[stptr] = isinf(rpnstack->s[stptr]) ? 1.0 : 0.0;
 728             break;
 729         case OP_SQRT:
 730             stackunderflow(0);
 731             rpnstack->s[stptr] = sqrt(rpnstack->s[stptr]);
 732             break;
 733         case OP_SORT:
 734             stackunderflow(0);
 735             {
 736                 int       spn = (int) rpnstack->s[stptr--];
 737
 738                 stackunderflow(spn - 1);
 739                 qsort(rpnstack->s + stptr - spn + 1, spn, sizeof(double),
 740                       rpn_compare_double);
 741             }
 742             break;
 743         case OP_REV:
 744             stackunderflow(0);
 745             {
 746                 int       spn = (int) rpnstack->s[stptr--];
 747                 double   *p, *q;
 748
 749                 stackunderflow(spn - 1);
 750
 751                 p = rpnstack->s + stptr - spn + 1;
 752                 q = rpnstack->s + stptr;
 753                 while (p < q) {
 754                     double    x = *q;
 755
 756                     *q-- = *p;
 757                     *p++ = x;
 758                 }
 759             }
 760             break;
 761         case OP_TREND:
 762         case OP_TRENDNAN:
 763             stackunderflow(1);
 764             if ((rpi < 2) || (rpnp[rpi - 2].op != OP_VARIABLE)) {
 765                 rrd_set_error("malformed trend arguments");
 766                 return -1;
 767             } else {
 768                 time_t    dur = (time_t) rpnstack->s[stptr];
 769                 time_t    step = (time_t) rpnp[rpi - 2].step;
 770
 771                 if (output_idx > (int) ceil((float) dur / (float) step)) {
 772                     int       ignorenan = (rpnp[rpi].op == OP_TREND);
 773                     double    accum = 0.0;
 774                     int       i = 0;
 775                     int       count = 0;
 776
 777                     do {
 778                         double    val =
 779                             rpnp[rpi - 2].data[rpnp[rpi - 2].ds_cnt * i--];
 780                         if (ignorenan || !isnan(val)) {
 781                             accum += val;
 782                             ++count;
 783                         }
 784
 785                         dur -= step;
 786                     } while (dur > 0);
 787
 788                     rpnstack->s[--stptr] =
 789                         (count == 0) ? DNAN : (accum / count);
 790                 } else
 791                     rpnstack->s[--stptr] = DNAN;
 792             }
 793             break;
 794         case OP_AVG:
 795             stackunderflow(0);
 796             {
 797                 int       i = (int) rpnstack->s[stptr--];
 798                 double    sum = 0;
 799                 int       count = 0;
 800
 801                 stackunderflow(i - 1);
 802                 while (i > 0) {
 803                     double    val = rpnstack->s[stptr--];
 804
 805                     i--;
 806                     if (isnan(val)) {
 807                         continue;
 808                     }
 809                     count++;
 810                     sum += val;
 811                 }
 812                 /* now push the result back on stack */
 813                 if (count > 0) {
 814                     rpnstack->s[++stptr] = sum / count;
 815                 } else {
 816                     rpnstack->s[++stptr] = DNAN;
 817                 }
 818             }
 819             break;
 820         case OP_ABS:
 821             stackunderflow(0);
 822             rpnstack->s[stptr] = fabs(rpnstack->s[stptr]);
 823             break;
 824         case OP_END:
 825             break;
 826         }
 827 #undef stackunderflow
 828     }
 829     if (stptr != 0) {
 830         rrd_set_error("RPN final stack size != 1");
 831         return -1;
 832     }
 833
 834     output[output_idx] = rpnstack->s[0];
 835     return 0;
 836 }
 837
 838 /* figure out what the local timezone offset for any point in
 839    time was. Return it in seconds */
 840 int tzoffset(
 841     time_t now)
 842 {
 843     int       gm_sec, gm_min, gm_hour, gm_yday, gm_year,
 844         l_sec, l_min, l_hour, l_yday, l_year;
 845     struct tm t;
 846     int       off;
 847
 848     gmtime_r(&now, &t);
 849     gm_sec = t.tm_sec;
 850     gm_min = t.tm_min;
 851     gm_hour = t.tm_hour;
 852     gm_yday = t.tm_yday;
 853     gm_year = t.tm_year;
 854     localtime_r(&now, &t);
 855     l_sec = t.tm_sec;
 856     l_min = t.tm_min;
 857     l_hour = t.tm_hour;
 858     l_yday = t.tm_yday;
 859     l_year = t.tm_year;
 860     off =
 861         (l_sec - gm_sec) + (l_min - gm_min) * 60 + (l_hour - gm_hour) * 3600;
 862     if (l_yday > gm_yday || l_year > gm_year) {
 863         off += 24 * 3600;
 864     } else if (l_yday < gm_yday || l_year < gm_year) {
 865         off -= 24 * 3600;
 866     }
 867     return off;
 868 }