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