ntp_fp.h revision 330106
1/* 2 * ntp_fp.h - definitions for NTP fixed/floating-point arithmetic 3 */ 4 5#ifndef NTP_FP_H 6#define NTP_FP_H 7 8#include "ntp_types.h" 9 10/* 11 * NTP uses two fixed point formats. The first (l_fp) is the "long" 12 * format and is 64 bits long with the decimal between bits 31 and 32. 13 * This is used for time stamps in the NTP packet header (in network 14 * byte order) and for internal computations of offsets (in local host 15 * byte order). We use the same structure for both signed and unsigned 16 * values, which is a big hack but saves rewriting all the operators 17 * twice. Just to confuse this, we also sometimes just carry the 18 * fractional part in calculations, in both signed and unsigned forms. 19 * Anyway, an l_fp looks like: 20 * 21 * 0 1 2 3 22 * 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 23 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 24 * | Integral Part | 25 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 26 * | Fractional Part | 27 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 28 * 29 */ 30typedef struct { 31 union { 32 u_int32 Xl_ui; 33 int32 Xl_i; 34 } Ul_i; 35 u_int32 l_uf; 36} l_fp; 37 38#define l_ui Ul_i.Xl_ui /* unsigned integral part */ 39#define l_i Ul_i.Xl_i /* signed integral part */ 40 41/* 42 * Fractional precision (of an l_fp) is actually the number of 43 * bits in a long. 44 */ 45#define FRACTION_PREC (32) 46 47 48/* 49 * The second fixed point format is 32 bits, with the decimal between 50 * bits 15 and 16. There is a signed version (s_fp) and an unsigned 51 * version (u_fp). This is used to represent synchronizing distance 52 * and synchronizing dispersion in the NTP packet header (again, in 53 * network byte order) and internally to hold both distance and 54 * dispersion values (in local byte order). In network byte order 55 * it looks like: 56 * 57 * 0 1 2 3 58 * 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 59 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 60 * | Integer Part | Fraction Part | 61 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 62 * 63 */ 64typedef int32 s_fp; 65typedef u_int32 u_fp; 66 67/* 68 * A unit second in fp format. Actually 2**(half_the_bits_in_a_long) 69 */ 70#define FP_SECOND (0x10000) 71 72/* 73 * Byte order conversions 74 */ 75#define HTONS_FP(x) (htonl(x)) 76#define NTOHS_FP(x) (ntohl(x)) 77 78#define NTOHL_MFP(ni, nf, hi, hf) \ 79 do { \ 80 (hi) = ntohl(ni); \ 81 (hf) = ntohl(nf); \ 82 } while (FALSE) 83 84#define HTONL_MFP(hi, hf, ni, nf) \ 85 do { \ 86 (ni) = htonl(hi); \ 87 (nf) = htonl(hf); \ 88 } while (FALSE) 89 90#define HTONL_FP(h, n) \ 91 HTONL_MFP((h)->l_ui, (h)->l_uf, (n)->l_ui, (n)->l_uf) 92 93#define NTOHL_FP(n, h) \ 94 NTOHL_MFP((n)->l_ui, (n)->l_uf, (h)->l_ui, (h)->l_uf) 95 96/* Convert unsigned ts fraction to net order ts */ 97#define HTONL_UF(uf, nts) \ 98 do { \ 99 (nts)->l_ui = 0; \ 100 (nts)->l_uf = htonl(uf); \ 101 } while (FALSE) 102 103/* 104 * Conversions between the two fixed point types 105 */ 106#define MFPTOFP(x_i, x_f) (((x_i) >= 0x00010000) ? 0x7fffffff : \ 107 (((x_i) <= -0x00010000) ? 0x80000000 : \ 108 (((x_i)<<16) | (((x_f)>>16)&0xffff)))) 109#define LFPTOFP(v) MFPTOFP((v)->l_i, (v)->l_uf) 110 111#define UFPTOLFP(x, v) ((v)->l_ui = (u_fp)(x)>>16, (v)->l_uf = (x)<<16) 112#define FPTOLFP(x, v) (UFPTOLFP((x), (v)), (x) < 0 ? (v)->l_ui -= 0x10000 : 0) 113 114#define MAXLFP(v) ((v)->l_ui = 0x7fffffffu, (v)->l_uf = 0xffffffffu) 115#define MINLFP(v) ((v)->l_ui = 0x80000000u, (v)->l_uf = 0u) 116 117/* 118 * Primitive operations on long fixed point values. If these are 119 * reminiscent of assembler op codes it's only because some may 120 * be replaced by inline assembler for particular machines someday. 121 * These are the (kind of inefficient) run-anywhere versions. 122 */ 123#define M_NEG(v_i, v_f) /* v = -v */ \ 124 do { \ 125 (v_f) = ~(v_f) + 1u; \ 126 (v_i) = ~(v_i) + ((v_f) == 0); \ 127 } while (FALSE) 128 129#define M_NEGM(r_i, r_f, a_i, a_f) /* r = -a */ \ 130 do { \ 131 (r_f) = ~(a_f) + 1u; \ 132 (r_i) = ~(a_i) + ((r_f) == 0); \ 133 } while (FALSE) 134 135#define M_ADD(r_i, r_f, a_i, a_f) /* r += a */ \ 136 do { \ 137 u_int32 add_t = (r_f); \ 138 (r_f) += (a_f); \ 139 (r_i) += (a_i) + ((u_int32)(r_f) < add_t); \ 140 } while (FALSE) 141 142#define M_ADD3(r_o, r_i, r_f, a_o, a_i, a_f) /* r += a, three word */ \ 143 do { \ 144 u_int32 add_t, add_c; \ 145 add_t = (r_f); \ 146 (r_f) += (a_f); \ 147 add_c = ((u_int32)(r_f) < add_t); \ 148 (r_i) += add_c; \ 149 add_c = ((u_int32)(r_i) < add_c); \ 150 add_t = (r_i); \ 151 (r_i) += (a_i); \ 152 add_c |= ((u_int32)(r_i) < add_t); \ 153 (r_o) += (a_o) + add_c; \ 154 } while (FALSE) 155 156#define M_SUB(r_i, r_f, a_i, a_f) /* r -= a */ \ 157 do { \ 158 u_int32 sub_t = (r_f); \ 159 (r_f) -= (a_f); \ 160 (r_i) -= (a_i) + ((u_int32)(r_f) > sub_t); \ 161 } while (FALSE) 162 163#define M_RSHIFTU(v_i, v_f) /* v >>= 1, v is unsigned */ \ 164 do { \ 165 (v_f) = ((u_int32)(v_f) >> 1) | ((u_int32)(v_i) << 31); \ 166 (v_i) = ((u_int32)(v_i) >> 1); \ 167 } while (FALSE) 168 169#define M_RSHIFT(v_i, v_f) /* v >>= 1, v is signed */ \ 170 do { \ 171 (v_f) = ((u_int32)(v_f) >> 1) | ((u_int32)(v_i) << 31); \ 172 (v_i) = ((u_int32)(v_i) >> 1) | ((u_int32)(v_i) & 0x80000000); \ 173 } while (FALSE) 174 175#define M_LSHIFT(v_i, v_f) /* v <<= 1 */ \ 176 do { \ 177 (v_i) = ((u_int32)(v_i) << 1) | ((u_int32)(v_f) >> 31); \ 178 (v_f) = ((u_int32)(v_f) << 1); \ 179 } while (FALSE) 180 181#define M_LSHIFT3(v_o, v_i, v_f) /* v <<= 1, with overflow */ \ 182 do { \ 183 (v_o) = ((u_int32)(v_o) << 1) | ((u_int32)(v_i) >> 31); \ 184 (v_i) = ((u_int32)(v_i) << 1) | ((u_int32)(v_f) >> 31); \ 185 (v_f) = ((u_int32)(v_f) << 1); \ 186 } while (FALSE) 187 188#define M_ADDUF(r_i, r_f, uf) /* r += uf, uf is u_int32 fraction */ \ 189 M_ADD((r_i), (r_f), 0, (uf)) /* let optimizer worry about it */ 190 191#define M_SUBUF(r_i, r_f, uf) /* r -= uf, uf is u_int32 fraction */ \ 192 M_SUB((r_i), (r_f), 0, (uf)) /* let optimizer worry about it */ 193 194#define M_ADDF(r_i, r_f, f) /* r += f, f is a int32 fraction */ \ 195 do { \ 196 int32 add_f = (int32)(f); \ 197 if (add_f >= 0) \ 198 M_ADD((r_i), (r_f), 0, (uint32)( add_f)); \ 199 else \ 200 M_SUB((r_i), (r_f), 0, (uint32)(-add_f)); \ 201 } while(0) 202 203#define M_ISNEG(v_i) /* v < 0 */ \ 204 (((v_i) & 0x80000000) != 0) 205 206#define M_ISGT(a_i, a_f, b_i, b_f) /* a > b signed */ \ 207 (((u_int32)((a_i) ^ 0x80000000) > (u_int32)((b_i) ^ 0x80000000)) || \ 208 ((a_i) == (b_i) && ((u_int32)(a_f)) > ((u_int32)(b_f)))) 209 210#define M_ISGTU(a_i, a_f, b_i, b_f) /* a > b unsigned */ \ 211 (((u_int32)(a_i)) > ((u_int32)(b_i)) || \ 212 ((a_i) == (b_i) && ((u_int32)(a_f)) > ((u_int32)(b_f)))) 213 214#define M_ISHIS(a_i, a_f, b_i, b_f) /* a >= b unsigned */ \ 215 (((u_int32)(a_i)) > ((u_int32)(b_i)) || \ 216 ((a_i) == (b_i) && ((u_int32)(a_f)) >= ((u_int32)(b_f)))) 217 218#define M_ISGEQ(a_i, a_f, b_i, b_f) /* a >= b signed */ \ 219 (((u_int32)((a_i) ^ 0x80000000) > (u_int32)((b_i) ^ 0x80000000)) || \ 220 ((a_i) == (b_i) && (u_int32)(a_f) >= (u_int32)(b_f))) 221 222#define M_ISEQU(a_i, a_f, b_i, b_f) /* a == b unsigned */ \ 223 ((u_int32)(a_i) == (u_int32)(b_i) && (u_int32)(a_f) == (u_int32)(b_f)) 224 225/* 226 * Operations on the long fp format 227 */ 228#define L_ADD(r, a) M_ADD((r)->l_ui, (r)->l_uf, (a)->l_ui, (a)->l_uf) 229#define L_SUB(r, a) M_SUB((r)->l_ui, (r)->l_uf, (a)->l_ui, (a)->l_uf) 230#define L_NEG(v) M_NEG((v)->l_ui, (v)->l_uf) 231#define L_ADDUF(r, uf) M_ADDUF((r)->l_ui, (r)->l_uf, (uf)) 232#define L_SUBUF(r, uf) M_SUBUF((r)->l_ui, (r)->l_uf, (uf)) 233#define L_ADDF(r, f) M_ADDF((r)->l_ui, (r)->l_uf, (f)) 234#define L_RSHIFT(v) M_RSHIFT((v)->l_i, (v)->l_uf) 235#define L_RSHIFTU(v) M_RSHIFTU((v)->l_ui, (v)->l_uf) 236#define L_LSHIFT(v) M_LSHIFT((v)->l_ui, (v)->l_uf) 237#define L_CLR(v) ((v)->l_ui = (v)->l_uf = 0) 238 239#define L_ISNEG(v) M_ISNEG((v)->l_ui) 240#define L_ISZERO(v) (((v)->l_ui | (v)->l_uf) == 0) 241#define L_ISGT(a, b) M_ISGT((a)->l_i, (a)->l_uf, (b)->l_i, (b)->l_uf) 242#define L_ISGTU(a, b) M_ISGTU((a)->l_ui, (a)->l_uf, (b)->l_ui, (b)->l_uf) 243#define L_ISHIS(a, b) M_ISHIS((a)->l_ui, (a)->l_uf, (b)->l_ui, (b)->l_uf) 244#define L_ISGEQ(a, b) M_ISGEQ((a)->l_ui, (a)->l_uf, (b)->l_ui, (b)->l_uf) 245#define L_ISEQU(a, b) M_ISEQU((a)->l_ui, (a)->l_uf, (b)->l_ui, (b)->l_uf) 246 247/* 248 * s_fp/double and u_fp/double conversions 249 */ 250#define FRIC 65536.0 /* 2^16 as a double */ 251#define DTOFP(r) ((s_fp)((r) * FRIC)) 252#define DTOUFP(r) ((u_fp)((r) * FRIC)) 253#define FPTOD(r) ((double)(r) / FRIC) 254 255/* 256 * l_fp/double conversions 257 */ 258#define FRAC 4294967296.0 /* 2^32 as a double */ 259 260/* 261 * Use 64 bit integers if available. Solaris on SPARC has a problem 262 * compiling parsesolaris.c if ntp_fp.h includes math.h, due to 263 * archaic gets() and printf() prototypes used in Solaris kernel 264 * headers. So far the problem has only been seen with gcc, but it 265 * may also affect Sun compilers, in which case the defined(__GNUC__) 266 * term should be removed. 267 * XSCALE also generates bad code for these, at least with GCC 3.3.5. 268 * This is unrelated to math.h, but the same solution applies. 269 */ 270#if defined(HAVE_U_INT64) && \ 271 !(defined(__SVR4) && defined(__sun) && \ 272 defined(sparc) && defined(__GNUC__) || \ 273 defined(__arm__) && defined(__XSCALE__) && defined(__GNUC__)) 274 275#include <math.h> /* ldexp() */ 276 277#define M_DTOLFP(d, r_ui, r_uf) /* double to l_fp */ \ 278 do { \ 279 double d_tmp; \ 280 u_int64 q_tmp; \ 281 int M_isneg; \ 282 \ 283 d_tmp = (d); \ 284 M_isneg = (d_tmp < 0.); \ 285 if (M_isneg) { \ 286 d_tmp = -d_tmp; \ 287 } \ 288 q_tmp = (u_int64)ldexp(d_tmp, 32); \ 289 if (M_isneg) { \ 290 q_tmp = ~q_tmp + 1; \ 291 } \ 292 (r_uf) = (u_int32)q_tmp; \ 293 (r_ui) = (u_int32)(q_tmp >> 32); \ 294 } while (FALSE) 295 296#define M_LFPTOD(r_ui, r_uf, d) /* l_fp to double */ \ 297 do { \ 298 double d_tmp; \ 299 u_int64 q_tmp; \ 300 int M_isneg; \ 301 \ 302 q_tmp = ((u_int64)(r_ui) << 32) + (r_uf); \ 303 M_isneg = M_ISNEG(r_ui); \ 304 if (M_isneg) { \ 305 q_tmp = ~q_tmp + 1; \ 306 } \ 307 d_tmp = ldexp((double)q_tmp, -32); \ 308 if (M_isneg) { \ 309 d_tmp = -d_tmp; \ 310 } \ 311 (d) = d_tmp; \ 312 } while (FALSE) 313 314#else /* use only 32 bit unsigned values */ 315 316#define M_DTOLFP(d, r_ui, r_uf) /* double to l_fp */ \ 317 do { \ 318 double d_tmp; \ 319 if ((d_tmp = (d)) < 0) { \ 320 (r_ui) = (u_int32)(-d_tmp); \ 321 (r_uf) = (u_int32)(-(d_tmp + (double)(r_ui)) * FRAC); \ 322 M_NEG((r_ui), (r_uf)); \ 323 } else { \ 324 (r_ui) = (u_int32)d_tmp; \ 325 (r_uf) = (u_int32)((d_tmp - (double)(r_ui)) * FRAC); \ 326 } \ 327 } while (0) 328#define M_LFPTOD(r_ui, r_uf, d) /* l_fp to double */ \ 329 do { \ 330 u_int32 l_thi, l_tlo; \ 331 l_thi = (r_ui); l_tlo = (r_uf); \ 332 if (M_ISNEG(l_thi)) { \ 333 M_NEG(l_thi, l_tlo); \ 334 (d) = -((double)l_thi + (double)l_tlo / FRAC); \ 335 } else { \ 336 (d) = (double)l_thi + (double)l_tlo / FRAC; \ 337 } \ 338 } while (0) 339#endif 340 341#define DTOLFP(d, v) M_DTOLFP((d), (v)->l_ui, (v)->l_uf) 342#define LFPTOD(v, d) M_LFPTOD((v)->l_ui, (v)->l_uf, (d)) 343 344/* 345 * Prototypes 346 */ 347extern char * dofptoa (u_fp, int, short, int); 348extern char * dolfptoa (u_int32, u_int32, int, short, int); 349 350extern int atolfp (const char *, l_fp *); 351extern int buftvtots (const char *, l_fp *); 352extern char * fptoa (s_fp, short); 353extern char * fptoms (s_fp, short); 354extern int hextolfp (const char *, l_fp *); 355extern void gpstolfp (u_int, u_int, unsigned long, l_fp *); 356extern int mstolfp (const char *, l_fp *); 357extern char * prettydate (l_fp *); 358extern char * gmprettydate (l_fp *); 359extern char * uglydate (l_fp *); 360extern void mfp_mul (int32 *, u_int32 *, int32, u_int32, int32, u_int32); 361 362extern void set_sys_fuzz (double); 363extern void init_systime (void); 364extern void get_systime (l_fp *); 365extern int step_systime (double); 366extern int adj_systime (double); 367extern int clamp_systime (void); 368 369extern struct tm * ntp2unix_tm (u_int32 ntp, int local); 370 371#define lfptoa(fpv, ndec) mfptoa((fpv)->l_ui, (fpv)->l_uf, (ndec)) 372#define lfptoms(fpv, ndec) mfptoms((fpv)->l_ui, (fpv)->l_uf, (ndec)) 373 374#define stoa(addr) socktoa(addr) 375#define ntoa(addr) stoa(addr) 376#define sptoa(addr) sockporttoa(addr) 377#define stohost(addr) socktohost(addr) 378 379#define ufptoa(fpv, ndec) dofptoa((fpv), 0, (ndec), 0) 380#define ufptoms(fpv, ndec) dofptoa((fpv), 0, (ndec), 1) 381#define ulfptoa(fpv, ndec) dolfptoa((fpv)->l_ui, (fpv)->l_uf, 0, (ndec), 0) 382#define ulfptoms(fpv, ndec) dolfptoa((fpv)->l_ui, (fpv)->l_uf, 0, (ndec), 1) 383#define umfptoa(fpi, fpf, ndec) dolfptoa((fpi), (fpf), 0, (ndec), 0) 384 385/* 386 * Optional callback from libntp step_systime() to ntpd. Optional 387* because other libntp clients like ntpdate don't use it. 388 */ 389typedef void (*time_stepped_callback)(void); 390extern time_stepped_callback step_callback; 391 392/* 393 * Multi-thread locking for get_systime() 394 * 395 * On most systems, get_systime() is used solely by the main ntpd 396 * thread, but on Windows it's also used by the dedicated I/O thread. 397 * The [Bug 2037] changes to get_systime() have it keep state between 398 * calls to ensure time moves in only one direction, which means its 399 * use on Windows needs to be protected against simultaneous execution 400 * to avoid falsely detecting Lamport violations by ensuring only one 401 * thread at a time is in get_systime(). 402 */ 403#ifdef SYS_WINNT 404extern CRITICAL_SECTION get_systime_cs; 405# define INIT_GET_SYSTIME_CRITSEC() \ 406 InitializeCriticalSection(&get_systime_cs) 407# define ENTER_GET_SYSTIME_CRITSEC() \ 408 EnterCriticalSection(&get_systime_cs) 409# define LEAVE_GET_SYSTIME_CRITSEC() \ 410 LeaveCriticalSection(&get_systime_cs) 411# define INIT_WIN_PRECISE_TIME() \ 412 init_win_precise_time() 413#else /* !SYS_WINNT follows */ 414# define INIT_GET_SYSTIME_CRITSEC() \ 415 do {} while (FALSE) 416# define ENTER_GET_SYSTIME_CRITSEC() \ 417 do {} while (FALSE) 418# define LEAVE_GET_SYSTIME_CRITSEC() \ 419 do {} while (FALSE) 420# define INIT_WIN_PRECISE_TIME() \ 421 do {} while (FALSE) 422#endif 423 424#endif /* NTP_FP_H */ 425