contrib/ntp/include/ntp_fp.h

   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  */
  30 typedef 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  */
  64 typedef int32 s_fp;
  65 typedef 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  */
 347 extern  char *  dofptoa         (u_fp, int, short, int);
 348 extern  char *  dolfptoa        (u_int32, u_int32, int, short, int);
 349
 350 extern  int     atolfp          (const char *, l_fp *);
 351 extern  int     buftvtots       (const char *, l_fp *);
 352 extern  char *  fptoa           (s_fp, short);
 353 extern  char *  fptoms          (s_fp, short);
 354 extern  int     hextolfp        (const char *, l_fp *);
 355 extern  void    gpstolfp        (u_int, u_int, unsigned long, l_fp *);
 356 extern  int     mstolfp         (const char *, l_fp *);
 357 extern  char *  prettydate      (l_fp *);
 358 extern  char *  gmprettydate    (l_fp *);
 359 extern  char *  uglydate        (l_fp *);
 360 extern  void    mfp_mul         (int32 *, u_int32 *, int32, u_int32, int32, u_int32);
 361
 362 extern  void    set_sys_fuzz    (double);
 363 extern  void    init_systime    (void);
 364 extern  void    get_systime     (l_fp *);
 365 extern  int     step_systime    (double);
 366 extern  int     adj_systime     (double);
 367 extern  int     clamp_systime   (void);
 368
 369 extern  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  */
 389 typedef void (*time_stepped_callback)(void);
 390 extern 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
 404 extern 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 */