172a84bc8402d9fd3d8dad7d31be5be62b40fa33
[olsrd.git] / src / olsr_clock.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 #include <assert.h>
43 #include <ctype.h>
44
45 #include "os_time.h"
46 #include "olsr_logging.h"
47 #include "olsr.h"
48 #include "olsr_clock.h"
49
50 /* Timer data */
51 static uint32_t now_times;             /* relative time compared to startup (in milliseconds */
52 static struct timeval first_tv;        /* timevalue during startup */
53 static struct timeval last_tv;         /* timevalue used for last olsr_times() calculation */
54
55 void
56 olsr_clock_init(void) {
57   /* Grab initial timestamp */
58   if (os_gettimeofday(&first_tv, NULL)) {
59     OLSR_ERROR(LOG_TIMER, "OS clock is not working, have to shut down OLSR (%s)\n", strerror(errno));
60     olsr_exit(1);
61   }
62   last_tv = first_tv;
63   olsr_timer_updateClock();
64 }
65
66 /**
67  * Update the internal clock to current system time
68  */
69 void
70 olsr_timer_updateClock(void)
71 {
72   struct timeval tv;
73   uint32_t t;
74
75   if (os_gettimeofday(&tv, NULL) != 0) {
76     OLSR_ERROR(LOG_SCHEDULER, "OS clock is not working, have to shut down OLSR (%s)\n", strerror(errno));
77     olsr_exit(1);
78   }
79
80   /* test if time jumped backward or more than 60 seconds forward */
81   if (tv.tv_sec < last_tv.tv_sec || (tv.tv_sec == last_tv.tv_sec && tv.tv_usec < last_tv.tv_usec)
82       || tv.tv_sec - last_tv.tv_sec > 60) {
83     OLSR_WARN(LOG_SCHEDULER, "Time jump (%d.%06d to %d.%06d)\n",
84               (int32_t) (last_tv.tv_sec), (int32_t) (last_tv.tv_usec), (int32_t) (tv.tv_sec), (int32_t) (tv.tv_usec));
85
86     t = (last_tv.tv_sec - first_tv.tv_sec) * 1000 + (last_tv.tv_usec - first_tv.tv_usec) / 1000;
87     t++;                        /* advance time by one millisecond */
88
89     first_tv = tv;
90     first_tv.tv_sec -= (t / 1000);
91     first_tv.tv_usec -= ((t % 1000) * 1000);
92
93     if (first_tv.tv_usec < 0) {
94       first_tv.tv_sec--;
95       first_tv.tv_usec += 1000000;
96     }
97     last_tv = tv;
98     now_times =  t;
99   }
100   last_tv = tv;
101   now_times = (tv.tv_sec - first_tv.tv_sec) * 1000 + (tv.tv_usec - first_tv.tv_usec) / 1000;
102 }
103
104 /**
105  * Calculates the current time in the internal OLSR representation
106  * @return current time
107  */
108 uint32_t
109 olsr_timer_getNow(void) {
110   return now_times;
111 }
112
113 /**
114  * Returns the number of milliseconds until the timestamp will happen
115  * @param absolute timestamp
116  * @return milliseconds until event will happen, negative if it already
117  *   happened.
118  */
119 int32_t
120 olsr_timer_getRelative(uint32_t absolute)
121 {
122   uint32_t diff;
123   if (absolute > now_times) {
124     diff = absolute - now_times;
125
126     /* overflow ? */
127     if (diff > (1u << 31)) {
128       return -(int32_t) (0xffffffff - diff);
129     }
130     return (int32_t) (diff);
131   }
132
133   diff = now_times - absolute;
134   /* overflow ? */
135   if (diff > (1u << 31)) {
136     return (int32_t) (0xffffffff - diff);
137   }
138   return -(int32_t) (diff);
139 }
140
141 /**
142  * Checks if a timestamp has already happened
143  * @param absolute timestamp
144  * @return true if the event already happened, false otherwise
145  */
146 bool
147 olsr_timer_isTimedOut(uint32_t absolute)
148 {
149   if (absolute > now_times) {
150     return absolute - now_times > (1u << 31);
151   }
152
153   return now_times - absolute <= (1u << 31);
154 }
155
156 /**
157  *Function that converts a double to a mantissa/exponent
158  *product as described in RFC3626:
159  *
160  * value = C*(1+a/16)*2^b [in seconds]
161  *
162  *  where a is the integer represented by the four highest bits of the
163  *  field and b the integer represented by the four lowest bits of the
164  *  field.
165  *
166  *@param interval the time interval to process
167  *
168  *@return a 8-bit mantissa/exponent product
169  */
170 uint8_t
171 reltime_to_me(const uint32_t interval)
172 {
173   uint8_t a = 0, b = 0;                /* Underflow defaults */
174
175   /* It is sufficent to compare the integer part since we test on >=.
176    * So we have now only a floating point division and the rest of the loop
177    * are only integer operations.
178    *
179    * const unsigned int unscaled_interval = interval / VTIME_SCALE_FACTOR;
180    *
181    * VTIME_SCALE_FACTOR = 1/16
182    *
183    * => unscaled_interval = interval(ms) / 1000 * 16
184    *                      = interval(ms) / 125 * 2
185    */
186
187   unsigned unscaled_interval = interval;
188   while (unscaled_interval >= 62) {
189     unscaled_interval >>= 1;
190     b++;
191   }
192
193   if (0 < b) {
194     if (15 < --b) {
195       a = 15;                   /* Overflow defaults */
196       b = 15;
197     } else {
198       a = (interval >> (b + 2)) - 15;
199     }
200   }
201
202   return (a << 4) + b;
203 }
204
205 /**
206  * Function for converting a mantissa/exponent 8bit value back
207  * to double as described in RFC3626:
208  *
209  * value = C*(1+a/16)*2^b [in seconds]
210  *
211  *  where a is the integer represented by the four highest bits of the
212  *  field and b the integer represented by the four lowest bits of the
213  *  field.
214  *
215  * me is the 8 bit mantissa/exponent value
216  *
217  * To avoid expensive floating maths, we transform the equation:
218  *     value = C * (1 + a / 16) * 2^b
219  * first, we make an int addition from the floating point addition:
220  *     value = C * ((16 + a) / 16) * 2^b
221  * then we get rid of a pair of parentheses
222  *     value = C * (16 + a) / 16 * 2^b
223  * and now we make an int multiplication from the floating point one
224  *     value = C * (16 + a) * 2^b / 16
225  * so that we can make a shift from the multiplication
226  *     value = C * ((16 + a) << b) / 16
227  * and sionce C and 16 are constants
228  *     value = ((16 + a) << b) * C / 16
229  *
230  * VTIME_SCALE_FACTOR = 1/16
231  *
232  * =>  value(ms) = ((16 + a) << b) / 256 * 1000
233  *
234  * 1. case: b >= 8
235  *           = ((16 + a) << (b-8)) * 1000
236  *
237  * 2. case: b <= 8
238  *           = ((16 + a) * 1000) >> (8-b)
239  */
240 uint32_t
241 me_to_reltime(const uint8_t me)
242 {
243   const uint8_t a = me >> 4;
244   const uint8_t b = me & 0x0F;
245
246   if (b >= 8) {
247     return ((16 + a) << (b - 8)) * 1000;
248   }
249   assert(me == reltime_to_me(((16 + a) * 1000) >> (8 - b)));
250   return ((16 + a) * 1000) >> (8 - b);
251 }
252
253 /**
254  * converts an unsigned integer value into a string representation
255  * (divided by 1000)
256  */
257 char *
258 olsr_milli_to_txt(struct millitxt_buf *buffer, uint32_t t) {
259   sprintf(buffer->buf, "%u.%03u", t/1000, t%1000);
260   return buffer->buf;
261 }
262
263 /**
264  * converts a floating point text into a unsigned integer representation
265  * (multiplied by 1000)
266  */
267 uint32_t olsr_txt_to_milli(char *txt) {
268   uint32_t t = 0;
269   int fractionDigits = 0;
270   bool frac = false;
271
272   while (fractionDigits < 3 && *txt) {
273     if (*txt == '.' && !frac) {
274       frac = true;
275       txt++;
276     }
277
278     if (!isdigit(*txt)) {
279       break;
280     }
281
282     t = t * 10 + (*txt++ - '0');
283     if (frac) {
284       fractionDigits++;
285     }
286   }
287
288   while (fractionDigits++ < 3) {
289     t *= 10;
290   }
291   return t;
292 }
293
294 /*
295  * Local Variables:
296  * c-basic-offset: 2
297  * indent-tabs-mode: nil
298  * End:
299  */