src/lib/misc.c

   1 /*
   2  * misc.c       Various miscellaneous functions.
   3  *
   4  * Version:     $Id$
   5  *
   6  *   This library is free software; you can redistribute it and/or
   7  *   modify it under the terms of the GNU Lesser General Public
   8  *   License as published by the Free Software Foundation; either
   9  *   version 2.1 of the License, or (at your option) any later version.
  10  *
  11  *   This library is distributed in the hope that it will be useful,
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14  *   Lesser General Public License for more details.
  15  *
  16  *   You should have received a copy of the GNU Lesser General Public
  17  *   License along with this library; if not, write to the Free Software
  18  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  *
  20  * Copyright 2000,2006  The FreeRADIUS server project
  21  */
  22
  23 RCSID("$Id$")
  24
  25 #include        <freeradius-devel/libradius.h>
  26
  27 #include        <ctype.h>
  28 #include        <sys/file.h>
  29 #include        <fcntl.h>
  30
  31 #define FR_PUT_LE16(a, val)\
  32         do {\
  33                 a[1] = ((uint16_t) (val)) >> 8;\
  34                 a[0] = ((uint16_t) (val)) & 0xff;\
  35         } while (0)
  36
  37 #ifdef HAVE_PTHREAD_H
  38 static pthread_mutex_t autofree_context = PTHREAD_MUTEX_INITIALIZER;
  39 #  define PTHREAD_MUTEX_LOCK pthread_mutex_lock
  40 #  define PTHREAD_MUTEX_UNLOCK pthread_mutex_unlock
  41 #else
  42 #  define PTHREAD_MUTEX_LOCK(_x)
  43 #  define PTHREAD_MUTEX_UNLOCK(_x)
  44 #endif
  45
  46 bool    fr_dns_lookups = false;     /* IP -> hostname lookups? */
  47 bool    fr_hostname_lookups = true; /* hostname -> IP lookups? */
  48 int     fr_debug_flag = 0;
  49
  50 static char const *months[] = {
  51         "jan", "feb", "mar", "apr", "may", "jun",
  52         "jul", "aug", "sep", "oct", "nov", "dec" };
  53
  54 fr_thread_local_setup(char *, fr_inet_ntop_buffer);     /* macro */
  55
  56 /** Sets a signal handler using sigaction if available, else signal
  57  *
  58  * @param sig to set handler for.
  59  * @param func handler to set.
  60  */
  61 int fr_set_signal(int sig, sig_t func)
  62 {
  63 #ifdef HAVE_SIGACTION
  64         struct sigaction act;
  65
  66         memset(&act, 0, sizeof(act));
  67         act.sa_flags = 0;
  68         sigemptyset(&act.sa_mask);
  69         act.sa_handler = func;
  70
  71         if (sigaction(sig, &act, NULL) < 0) {
  72                 fr_strerror_printf("Failed setting signal %i handler via sigaction(): %s", sig, fr_syserror(errno));
  73                 return -1;
  74         }
  75 #else
  76         if (signal(sig, func) < 0) {
  77                 fr_strerror_printf("Failed setting signal %i handler via signal(): %s", sig, fr_syserror(errno));
  78                 return -1;
  79         }
  80 #endif
  81         return 0;
  82 }
  83
  84 /** Allocates a new talloc context from the root autofree context
  85  *
  86  * This function is threadsafe, whereas using the NULL context is not.
  87  *
  88  * @note The returned context must be freed by the caller.
  89  * @returns a new talloc context parented by the root autofree context.
  90  */
  91 TALLOC_CTX *fr_autofree_ctx(void)
  92 {
  93         static TALLOC_CTX *ctx = NULL, *child;
  94         PTHREAD_MUTEX_LOCK(&autofree_context);
  95         if (!ctx) {
  96                 ctx = talloc_autofree_context();
  97         }
  98
  99         child = talloc_new(ctx);
 100         PTHREAD_MUTEX_UNLOCK(&autofree_context);
 101
 102         return child;
 103 }
 104
 105 /*
 106  *      Explicitly cleanup the memory allocated to the error inet_ntop
 107  *      buffer.
 108  */
 109 static void _fr_inet_ntop_free(void *arg)
 110 {
 111         free(arg);
 112 }
 113
 114 /** Wrapper around inet_ntop, prints IPv4/IPv6 addresses
 115  *
 116  * inet_ntop requires the caller pass in a buffer for the address.
 117  * This would be annoying and cumbersome, seeing as quite often the ASCII
 118  * address is only used for logging output.
 119  *
 120  * So as with lib/log.c use TLS to allocate thread specific buffers, and
 121  * write the IP address there instead.
 122  *
 123  * @param af address family, either AF_INET or AF_INET6.
 124  * @param src pointer to network address structure.
 125  * @return NULL on error, else pointer to ASCII buffer containing text version of address.
 126  */
 127 char const *fr_inet_ntop(int af, void const *src)
 128 {
 129         char *buffer;
 130
 131         if (!src) {
 132                 return NULL;
 133         }
 134
 135         buffer = fr_thread_local_init(fr_inet_ntop_buffer, _fr_inet_ntop_free);
 136         if (!buffer) {
 137                 int ret;
 138
 139                 /*
 140                  *      malloc is thread safe, talloc is not
 141                  */
 142                 buffer = malloc(sizeof(char) * INET6_ADDRSTRLEN);
 143                 if (!buffer) {
 144                         fr_perror("Failed allocating memory for inet_ntop buffer");
 145                         return NULL;
 146                 }
 147
 148                 ret = fr_thread_local_set(fr_inet_ntop_buffer, buffer);
 149                 if (ret != 0) {
 150                         fr_perror("Failed setting up TLS for inet_ntop buffer: %s", fr_syserror(ret));
 151                         free(buffer);
 152                         return NULL;
 153                 }
 154         }
 155         buffer[0] = '\0';
 156
 157         return inet_ntop(af, src, buffer, INET6_ADDRSTRLEN);
 158 }
 159
 160 /*
 161  *      Return an IP address in standard dot notation
 162  *
 163  *      FIXME: DELETE THIS
 164  */
 165 char const *ip_ntoa(char *buffer, uint32_t ipaddr)
 166 {
 167         ipaddr = ntohl(ipaddr);
 168
 169         sprintf(buffer, "%d.%d.%d.%d",
 170                 (ipaddr >> 24) & 0xff,
 171                 (ipaddr >> 16) & 0xff,
 172                 (ipaddr >>  8) & 0xff,
 173                 (ipaddr      ) & 0xff);
 174         return buffer;
 175 }
 176
 177 /** Parse an IPv4 address or IPv4 prefix in presentation format (and others)
 178  *
 179  * @param out Where to write the ip address value.
 180  * @param value to parse, may be dotted quad [+ prefix], or integer, or octal number, or '*' (INADDR_ANY).
 181  * @param inlen Length of value, if value is \0 terminated inlen may be 0.
 182  * @param resolve If true and value doesn't look like an IP address, try and resolve value as a hostname.
 183  * @param fallback to IPv4 resolution if no A records can be found.
 184  * @return 0 if ip address was parsed successfully, else -1 on error.
 185  */
 186 int fr_pton4(fr_ipaddr_t *out, char const *value, size_t inlen, bool resolve, bool fallback)
 187 {
 188         char *p;
 189         unsigned int prefix;
 190         char *eptr;
 191
 192         /* Dotted quad + / + [0-9]{1,2} */
 193         char buffer[INET_ADDRSTRLEN + 3];
 194
 195         /*
 196          *      Copy to intermediary buffer if we were given a length
 197          */
 198         if (inlen > 0) {
 199                 if (inlen >= sizeof(buffer)) {
 200                         fr_strerror_printf("Invalid IPv4 address string \"%s\"", value);
 201                         return -1;
 202                 }
 203                 memcpy(buffer, value, inlen);
 204                 buffer[inlen] = '\0';
 205         }
 206
 207         p = strchr(value, '/');
 208         /*
 209          *      192.0.2.2 is parsed as if it was /32
 210          */
 211         if (!p) {
 212                 /*
 213                  *      Allow '*' as the wildcard address usually 0.0.0.0
 214                  */
 215                 if ((value[0] == '*') && (value[1] == '\0')) {
 216                         out->ipaddr.ip4addr.s_addr = htonl(INADDR_ANY);
 217                 /*
 218                  *      Convert things which are obviously integers to IP addresses
 219                  *
 220                  *      We assume the number is the bigendian representation of the
 221                  *      IP address.
 222                  */
 223                 } else if (is_integer(value) || ((value[0] == '0') && (value[1] == 'x'))) {
 224                         out->ipaddr.ip4addr.s_addr = htonl(strtoul(value, NULL, 0));
 225                 } else if (!resolve) {
 226                         if (inet_pton(AF_INET, value, &(out->ipaddr.ip4addr.s_addr)) <= 0) {
 227                                 fr_strerror_printf("Failed to parse IPv4 address string \"%s\"", value);
 228                                 return -1;
 229                         }
 230                 } else if (ip_hton(out, AF_INET, value, fallback) < 0) return -1;
 231
 232                 out->prefix = 32;
 233                 out->af = AF_INET;
 234
 235                 return 0;
 236         }
 237
 238         /*
 239          *      Otherwise parse the prefix
 240          */
 241         if ((size_t)(p - value) >= INET_ADDRSTRLEN) {
 242                 fr_strerror_printf("Invalid IPv4 address string \"%s\"", value);
 243                 return -1;
 244         }
 245
 246         /*
 247          *      Copy the IP portion into a temporary buffer if we haven't already.
 248          */
 249         if (inlen == 0) memcpy(buffer, value, p - value);
 250         buffer[p - value] = '\0';
 251
 252         if (!resolve) {
 253                 if (inet_pton(AF_INET, buffer, &(out->ipaddr.ip4addr.s_addr)) <= 0) {
 254                         fr_strerror_printf("Failed to parse IPv4 address string \"%s\"", value);
 255                         return -1;
 256                 }
 257         } else if (ip_hton(out, AF_INET, buffer, fallback) < 0) return -1;
 258
 259         prefix = strtoul(p + 1, &eptr, 10);
 260         if (prefix > 32) {
 261                 fr_strerror_printf("Invalid IPv4 mask length \"%s\".  Should be between 0-32", p);
 262                 return -1;
 263         }
 264         if (eptr[0] != '\0') {
 265                 fr_strerror_printf("Failed to parse IPv4 address string \"%s\", "
 266                                    "got garbage after mask length \"%s\"", value, eptr);
 267                 return -1;
 268         }
 269
 270         if (prefix < 32) {
 271                 out->ipaddr.ip4addr = fr_inaddr_mask(&(out->ipaddr.ip4addr), prefix);
 272         }
 273
 274         out->prefix = (uint8_t) prefix;
 275         out->af = AF_INET;
 276
 277         return 0;
 278 }
 279
 280 /** Parse an IPv6 address or IPv6 prefix in presentation format (and others)
 281  *
 282  * @param out Where to write the ip address value.
 283  * @param value to parse.
 284  * @param inlen Length of value, if value is \0 terminated inlen may be 0.
 285  * @param resolve If true and value doesn't look like an IP address, try and resolve value as a hostname.
 286  * @param fallback to IPv4 resolution if no AAAA records can be found.
 287  * @return 0 if ip address was parsed successfully, else -1 on error.
 288  */
 289 int fr_pton6(fr_ipaddr_t *out, char const *value, size_t inlen, bool resolve, bool fallback)
 290 {
 291         char const *p;
 292         unsigned int prefix;
 293         char *eptr;
 294
 295         /* IPv6  + / + [0-9]{1,3} */
 296         char buffer[INET6_ADDRSTRLEN + 4];
 297
 298         /*
 299          *      Copy to intermediary buffer if we were given a length
 300          */
 301         if (inlen > 0) {
 302                 if (inlen >= sizeof(buffer)) {
 303                         fr_strerror_printf("Invalid IPv6 address string \"%s\"", value);
 304                         return -1;
 305                 }
 306                 memcpy(buffer, value, inlen);
 307                 buffer[inlen] = '\0';
 308         }
 309
 310         p = strchr(value, '/');
 311         if (!p) {
 312                 /*
 313                  *      Allow '*' as the wildcard address
 314                  */
 315                 if ((value[0] == '*') && (value[1] == '\0')) {
 316                         memset(&out->ipaddr.ip6addr.s6_addr, 0, sizeof(out->ipaddr.ip6addr.s6_addr));
 317                 } else if (!resolve) {
 318                         if (inet_pton(AF_INET6, value, &(out->ipaddr.ip6addr.s6_addr)) <= 0) {
 319                                 fr_strerror_printf("Failed to parse IPv6 address string \"%s\"", value);
 320                                 return -1;
 321                         }
 322                 } else if (ip_hton(out, AF_INET6, value, fallback) < 0) return -1;
 323
 324                 out->prefix = 128;
 325                 out->af = AF_INET6;
 326
 327                 return 0;
 328         }
 329
 330         if ((p - value) >= INET6_ADDRSTRLEN) {
 331                 fr_strerror_printf("Invalid IPv6 address string \"%s\"", value);
 332                 return -1;
 333         }
 334
 335         /*
 336          *      Copy string to temporary buffer if we didn't do it earlier
 337          */
 338         if (inlen == 0) memcpy(buffer, value, p - value);
 339         buffer[p - value] = '\0';
 340
 341         if (!resolve) {
 342                 if (inet_pton(AF_INET6, buffer, &(out->ipaddr.ip6addr.s6_addr)) <= 0) {
 343                         fr_strerror_printf("Failed to parse IPv6 address string \"%s\"", value);
 344                         return -1;
 345                 }
 346         } else if (ip_hton(out, AF_INET6, buffer, fallback) < 0) return -1;
 347
 348         prefix = strtoul(p + 1, &eptr, 10);
 349         if (prefix > 128) {
 350                 fr_strerror_printf("Invalid IPv6 mask length \"%s\".  Should be between 0-128", p);
 351                 return -1;
 352         }
 353         if (eptr[0] != '\0') {
 354                 fr_strerror_printf("Failed to parse IPv6 address string \"%s\", "
 355                                    "got garbage after mask length \"%s\"", value, eptr);
 356                 return -1;
 357         }
 358
 359         if (prefix < 128) {
 360                 struct in6_addr addr;
 361
 362                 addr = fr_in6addr_mask(&(out->ipaddr.ip6addr), prefix);
 363                 memcpy(&(out->ipaddr.ip6addr.s6_addr), &addr, sizeof(addr));
 364         }
 365
 366         out->prefix = (uint8_t) prefix;
 367         out->af = AF_INET6;
 368
 369         return 0;
 370 }
 371
 372 /** Simple wrapper to decide whether an IP value is v4 or v6 and call the appropriate parser.
 373  *
 374  * @param out Where to write the ip address value.
 375  * @param value to parse.
 376  * @param inlen Length of value, if value is \0 terminated inlen may be 0.
 377  * @param resolve If true and value doesn't look like an IP address, try and resolve value as a hostname.
 378  * @return 0 if ip address was parsed successfully, else -1 on error.
 379  */
 380 int fr_pton(fr_ipaddr_t *out, char const *value, size_t inlen, bool resolve)
 381 {
 382         size_t len, i;
 383
 384         len = (inlen == 0) ? strlen(value) : inlen;
 385         for (i = 0; i < len; i++) switch (value[i]) {
 386         /*
 387          *      Chars illegal in domain names and IPv4 addresses.
 388          *      Must be v6 and cannot be a domain.
 389          */
 390         case ':':
 391         case '[':
 392         case ']':
 393                 return fr_pton6(out, value, inlen, false, false);
 394
 395         /*
 396          *      Chars which don't really tell us anything
 397          */
 398         case '.':
 399         case '/':
 400                 continue;
 401
 402         default:
 403                 /*
 404                  *      Outside the range of IPv4 chars, must be a domain
 405                  *      Use A record in preference to AAAA record.
 406                  */
 407                 if ((value[i] < '0') || (value[i] > '9')) {
 408                         if (!resolve) return -1;
 409                         return fr_pton4(out, value, inlen, true, true);
 410                 }
 411                 break;
 412         }
 413
 414         /*
 415          *      All chars were in the IPv4 set [0-9/.], must be an IPv4
 416          *      address.
 417          */
 418         return fr_pton4(out, value, inlen, false, false);
 419 }
 420
 421 /** Check if the IP address is equivalent to INADDR_ANY
 422  *
 423  * @param addr to chec.
 424  * @return true if IP address matches INADDR_ANY or INADDR6_ANY (assumed to be 0), else false.
 425  */
 426 bool is_wildcard(fr_ipaddr_t *addr)
 427 {
 428         static struct in6_addr in6_addr;
 429
 430         switch (addr->af) {
 431         case AF_INET:
 432                 return (addr->ipaddr.ip4addr.s_addr == htons(INADDR_ANY));
 433
 434         case AF_INET6:
 435                 return (memcmp(addr->ipaddr.ip6addr.s6_addr, in6_addr.s6_addr, sizeof(in6_addr.s6_addr)) == 0) ? true :false;
 436
 437         default:
 438                 fr_assert(0);
 439                 return false;
 440         }
 441 }
 442
 443 int fr_ntop(char *out, size_t outlen, fr_ipaddr_t *addr)
 444 {
 445         char buffer[INET6_ADDRSTRLEN];
 446
 447         if (inet_ntop(addr->af, &(addr->ipaddr), buffer, sizeof(buffer)) == NULL) return -1;
 448
 449         return snprintf(out, outlen, "%s/%i", buffer, addr->prefix);
 450 }
 451
 452 /*
 453  *      Internal wrapper for locking, to minimize the number of ifdef's
 454  *
 455  *      Use fcntl or error
 456  */
 457 int rad_lockfd(int fd, int lock_len)
 458 {
 459 #ifdef F_WRLCK
 460         struct flock fl;
 461
 462         fl.l_start = 0;
 463         fl.l_len = lock_len;
 464         fl.l_pid = getpid();
 465         fl.l_type = F_WRLCK;
 466         fl.l_whence = SEEK_CUR;
 467
 468         return fcntl(fd, F_SETLKW, (void *)&fl);
 469 #else
 470 #error "missing definition for F_WRLCK, all file locks will fail"
 471
 472         return -1;
 473 #endif
 474 }
 475
 476 /*
 477  *      Internal wrapper for locking, to minimize the number of ifdef's
 478  *
 479  *      Lock an fd, prefer lockf() over flock()
 480  *      Nonblocking version.
 481  */
 482 int rad_lockfd_nonblock(int fd, int lock_len)
 483 {
 484 #ifdef F_WRLCK
 485         struct flock fl;
 486
 487         fl.l_start = 0;
 488         fl.l_len = lock_len;
 489         fl.l_pid = getpid();
 490         fl.l_type = F_WRLCK;
 491         fl.l_whence = SEEK_CUR;
 492
 493         return fcntl(fd, F_SETLK, (void *)&fl);
 494 #else
 495 #error "missing definition for F_WRLCK, all file locks will fail"
 496
 497         return -1;
 498 #endif
 499 }
 500
 501 /*
 502  *      Internal wrapper for unlocking, to minimize the number of ifdef's
 503  *      in the source.
 504  *
 505  *      Unlock an fd, prefer lockf() over flock()
 506  */
 507 int rad_unlockfd(int fd, int lock_len)
 508 {
 509 #ifdef F_WRLCK
 510         struct flock fl;
 511
 512         fl.l_start = 0;
 513         fl.l_len = lock_len;
 514         fl.l_pid = getpid();
 515         fl.l_type = F_WRLCK;
 516         fl.l_whence = SEEK_CUR;
 517
 518         return fcntl(fd, F_UNLCK, (void *)&fl);
 519 #else
 520 #error "missing definition for F_WRLCK, all file locks will fail"
 521
 522         return -1;
 523 #endif
 524 }
 525
 526 /*
 527  *      Return an interface-id in standard colon notation
 528  */
 529 char *ifid_ntoa(char *buffer, size_t size, uint8_t const *ifid)
 530 {
 531         snprintf(buffer, size, "%x:%x:%x:%x",
 532                  (ifid[0] << 8) + ifid[1], (ifid[2] << 8) + ifid[3],
 533                  (ifid[4] << 8) + ifid[5], (ifid[6] << 8) + ifid[7]);
 534         return buffer;
 535 }
 536
 537
 538 /*
 539  *      Return an interface-id from
 540  *      one supplied in standard colon notation.
 541  */
 542 uint8_t *ifid_aton(char const *ifid_str, uint8_t *ifid)
 543 {
 544         static char const xdigits[] = "0123456789abcdef";
 545         char const *p, *pch;
 546         int num_id = 0, val = 0, idx = 0;
 547
 548         for (p = ifid_str; ; ++p) {
 549                 if (*p == ':' || *p == '\0') {
 550                         if (num_id <= 0)
 551                                 return NULL;
 552
 553                         /*
 554                          *      Drop 'val' into the array.
 555                          */
 556                         ifid[idx] = (val >> 8) & 0xff;
 557                         ifid[idx + 1] = val & 0xff;
 558                         if (*p == '\0') {
 559                                 /*
 560                                  *      Must have all entries before
 561                                  *      end of the string.
 562                                  */
 563                                 if (idx != 6)
 564                                         return NULL;
 565                                 break;
 566                         }
 567                         val = 0;
 568                         num_id = 0;
 569                         if ((idx += 2) > 6)
 570                                 return NULL;
 571                 } else if ((pch = strchr(xdigits, tolower(*p))) != NULL) {
 572                         if (++num_id > 4)
 573                                 return NULL;
 574                         /*
 575                          *      Dumb version of 'scanf'
 576                          */
 577                         val <<= 4;
 578                         val |= (pch - xdigits);
 579                 } else
 580                         return NULL;
 581         }
 582         return ifid;
 583 }
 584
 585
 586 #ifndef HAVE_INET_PTON
 587 static int inet_pton4(char const *src, struct in_addr *dst)
 588 {
 589         int octet;
 590         unsigned int num;
 591         char const *p, *off;
 592         uint8_t tmp[4];
 593         static char const digits[] = "0123456789";
 594
 595         octet = 0;
 596         p = src;
 597         while (1) {
 598                 num = 0;
 599                 while (*p && ((off = strchr(digits, *p)) != NULL)) {
 600                         num *= 10;
 601                         num += (off - digits);
 602
 603                         if (num > 255) return 0;
 604
 605                         p++;
 606                 }
 607                 if (!*p) break;
 608
 609                 /*
 610                  *      Not a digit, MUST be a dot, else we
 611                  *      die.
 612                  */
 613                 if (*p != '.') {
 614                         return 0;
 615                 }
 616
 617                 tmp[octet++] = num;
 618                 p++;
 619         }
 620
 621         /*
 622          *      End of the string.  At the fourth
 623          *      octet is OK, anything else is an
 624          *      error.
 625          */
 626         if (octet != 3) {
 627                 return 0;
 628         }
 629         tmp[3] = num;
 630
 631         memcpy(dst, &tmp, sizeof(tmp));
 632         return 1;
 633 }
 634
 635
 636 #ifdef HAVE_STRUCT_SOCKADDR_IN6
 637 /* int
 638  * inet_pton6(src, dst)
 639  *      convert presentation level address to network order binary form.
 640  * return:
 641  *      1 if `src' is a valid [RFC1884 2.2] address, else 0.
 642  * notice:
 643  *      (1) does not touch `dst' unless it's returning 1.
 644  *      (2) :: in a full address is silently ignored.
 645  * credit:
 646  *      inspired by Mark Andrews.
 647  * author:
 648  *      Paul Vixie, 1996.
 649  */
 650 static int inet_pton6(char const *src, unsigned char *dst)
 651 {
 652         static char const xdigits_l[] = "0123456789abcdef",
 653                           xdigits_u[] = "0123456789ABCDEF";
 654         u_char tmp[IN6ADDRSZ], *tp, *endp, *colonp;
 655         char const *xdigits, *curtok;
 656         int ch, saw_xdigit;
 657         u_int val;
 658
 659         memset((tp = tmp), 0, IN6ADDRSZ);
 660         endp = tp + IN6ADDRSZ;
 661         colonp = NULL;
 662         /* Leading :: requires some special handling. */
 663         if (*src == ':')
 664                 if (*++src != ':')
 665                         return (0);
 666         curtok = src;
 667         saw_xdigit = 0;
 668         val = 0;
 669         while ((ch = *src++) != '\0') {
 670                 char const *pch;
 671
 672                 if ((pch = strchr((xdigits = xdigits_l), ch)) == NULL)
 673                         pch = strchr((xdigits = xdigits_u), ch);
 674                 if (pch != NULL) {
 675                         val <<= 4;
 676                         val |= (pch - xdigits);
 677                         if (val > 0xffff)
 678                                 return (0);
 679                         saw_xdigit = 1;
 680                         continue;
 681                 }
 682                 if (ch == ':') {
 683                         curtok = src;
 684                         if (!saw_xdigit) {
 685                                 if (colonp)
 686                                         return (0);
 687                                 colonp = tp;
 688                                 continue;
 689                         }
 690                         if (tp + INT16SZ > endp)
 691                                 return (0);
 692                         *tp++ = (u_char) (val >> 8) & 0xff;
 693                         *tp++ = (u_char) val & 0xff;
 694                         saw_xdigit = 0;
 695                         val = 0;
 696                         continue;
 697                 }
 698                 if (ch == '.' && ((tp + INADDRSZ) <= endp) &&
 699                     inet_pton4(curtok, (struct in_addr *) tp) > 0) {
 700                         tp += INADDRSZ;
 701                         saw_xdigit = 0;
 702                         break;  /* '\0' was seen by inet_pton4(). */
 703                 }
 704                 return (0);
 705         }
 706         if (saw_xdigit) {
 707                 if (tp + INT16SZ > endp)
 708                         return (0);
 709                 *tp++ = (u_char) (val >> 8) & 0xff;
 710                 *tp++ = (u_char) val & 0xff;
 711         }
 712         if (colonp != NULL) {
 713                 /*
 714                  * Since some memmove()'s erroneously fail to handle
 715                  * overlapping regions, we'll do the shift by hand.
 716                  */
 717                 int const n = tp - colonp;
 718                 int i;
 719
 720                 for (i = 1; i <= n; i++) {
 721                         endp[- i] = colonp[n - i];
 722                         colonp[n - i] = 0;
 723                 }
 724                 tp = endp;
 725         }
 726         if (tp != endp)
 727                 return (0);
 728         /* bcopy(tmp, dst, IN6ADDRSZ); */
 729         memcpy(dst, tmp, IN6ADDRSZ);
 730         return (1);
 731 }
 732 #endif
 733
 734 /*
 735  *      Utility function, so that the rest of the server doesn't
 736  *      have ifdef's around IPv6 support
 737  */
 738 int inet_pton(int af, char const *src, void *dst)
 739 {
 740         if (af == AF_INET) {
 741                 return inet_pton4(src, dst);
 742         }
 743 #ifdef HAVE_STRUCT_SOCKADDR_IN6
 744
 745         if (af == AF_INET6) {
 746                 return inet_pton6(src, dst);
 747         }
 748 #endif
 749
 750         return -1;
 751 }
 752 #endif
 753
 754 #ifndef HAVE_INET_NTOP
 755 /*
 756  *      Utility function, so that the rest of the server doesn't
 757  *      have ifdef's around IPv6 support
 758  */
 759 char const *inet_ntop(int af, void const *src, char *dst, size_t cnt)
 760 {
 761         if (af == AF_INET) {
 762                 uint8_t const *ipaddr = src;
 763
 764                 if (cnt <= INET_ADDRSTRLEN) return NULL;
 765
 766                 snprintf(dst, cnt, "%d.%d.%d.%d",
 767                          ipaddr[0], ipaddr[1],
 768                          ipaddr[2], ipaddr[3]);
 769                 return dst;
 770         }
 771
 772         /*
 773          *      If the system doesn't define this, we define it
 774          *      in missing.h
 775          */
 776         if (af == AF_INET6) {
 777                 struct in6_addr const *ipaddr = src;
 778
 779                 if (cnt <= INET6_ADDRSTRLEN) return NULL;
 780
 781                 snprintf(dst, cnt, "%x:%x:%x:%x:%x:%x:%x:%x",
 782                          (ipaddr->s6_addr[0] << 8) | ipaddr->s6_addr[1],
 783                          (ipaddr->s6_addr[2] << 8) | ipaddr->s6_addr[3],
 784                          (ipaddr->s6_addr[4] << 8) | ipaddr->s6_addr[5],
 785                          (ipaddr->s6_addr[6] << 8) | ipaddr->s6_addr[7],
 786                          (ipaddr->s6_addr[8] << 8) | ipaddr->s6_addr[9],
 787                          (ipaddr->s6_addr[10] << 8) | ipaddr->s6_addr[11],
 788                          (ipaddr->s6_addr[12] << 8) | ipaddr->s6_addr[13],
 789                          (ipaddr->s6_addr[14] << 8) | ipaddr->s6_addr[15]);
 790                 return dst;
 791         }
 792
 793         return NULL;            /* don't support IPv6 */
 794 }
 795 #endif
 796
 797 /** Wrappers for IPv4/IPv6 host to IP address lookup
 798  *
 799  * This function returns only one IP address, of the specified address family,
 800  * or the first address (of whatever family), if AF_UNSPEC is used.
 801  *
 802  * If fallback is specified and af is AF_INET, but no AF_INET records were
 803  * found and a record for AF_INET6 exists that record will be returned.
 804  *
 805  * If fallback is specified and af is AF_INET6, and a record with AF_INET4 exists
 806  * that record will be returned instead.
 807  *
 808  * @param out Where to write result.
 809  * @param af To search for in preference.
 810  * @param hostname to search for.
 811  * @param fallback to the other adress family, if no records matching af, found.
 812  * @return 0 on success, else -1 on failure.
 813  */
 814 int ip_hton(fr_ipaddr_t *out, int af, char const *hostname, bool fallback)
 815 {
 816         int rcode;
 817         struct addrinfo hints, *ai = NULL, *alt = NULL, *res = NULL;
 818
 819         if (!fr_hostname_lookups) {
 820 #ifdef HAVE_STRUCT_SOCKADDR_IN6
 821                 if (af == AF_UNSPEC) {
 822                         char const *p;
 823
 824                         for (p = hostname; *p != '\0'; p++) {
 825                                 if ((*p == ':') ||
 826                                     (*p == '[') ||
 827                                     (*p == ']')) {
 828                                         af = AF_INET6;
 829                                         break;
 830                                 }
 831                         }
 832                 }
 833 #endif
 834
 835                 if (af == AF_UNSPEC) af = AF_INET;
 836
 837                 if (!inet_pton(af, hostname, &(out->ipaddr))) {
 838                         return -1;
 839                 }
 840
 841                 out->af = af;
 842                 return 0;
 843         }
 844
 845         memset(&hints, 0, sizeof(hints));
 846         hints.ai_family = af;
 847
 848 #ifdef TALLOC_DEBUG
 849         /*
 850          *      Avoid malloc for IP addresses.  This helps us debug
 851          *      memory errors when using talloc.
 852          */
 853         if (af == AF_INET) {
 854                 /*
 855                  *      If it's all numeric, avoid getaddrinfo()
 856                  */
 857                 if (inet_pton(af, hostname, &out->ipaddr.ip4addr) == 1) {
 858                         return 0;
 859                 }
 860         }
 861 #endif
 862
 863         if ((rcode = getaddrinfo(hostname, NULL, &hints, &res)) != 0) {
 864                 fr_strerror_printf("ip_hton: %s", gai_strerror(rcode));
 865                 return -1;
 866         }
 867
 868         for (ai = res; ai; ai = ai->ai_next) {
 869                 if ((af == ai->ai_family) || (af == AF_UNSPEC)) break;
 870                 if (!alt && fallback && ((ai->ai_family == AF_INET) || (ai->ai_family == AF_INET6))) alt = ai;
 871         }
 872
 873         if (!ai) ai = alt;
 874         if (!ai) {
 875                 fr_strerror_printf("ip_hton failed to find requested information for host %.100s", hostname);
 876                 freeaddrinfo(ai);
 877                 return -1;
 878         }
 879
 880         rcode = fr_sockaddr2ipaddr((struct sockaddr_storage *)ai->ai_addr,
 881                                    ai->ai_addrlen, out, NULL);
 882         freeaddrinfo(ai);
 883         if (!rcode) return -1;
 884
 885         return 0;
 886 }
 887
 888 /*
 889  *      Look IP addresses up, and print names (depending on DNS config)
 890  */
 891 char const *ip_ntoh(fr_ipaddr_t const *src, char *dst, size_t cnt)
 892 {
 893         struct sockaddr_storage ss;
 894         int error;
 895         socklen_t salen;
 896
 897         /*
 898          *      No DNS lookups
 899          */
 900         if (!fr_dns_lookups) {
 901                 return inet_ntop(src->af, &(src->ipaddr), dst, cnt);
 902         }
 903
 904         if (!fr_ipaddr2sockaddr(src, 0, &ss, &salen)) {
 905                 return NULL;
 906         }
 907
 908         if ((error = getnameinfo((struct sockaddr *)&ss, salen, dst, cnt, NULL, 0,
 909                                  NI_NUMERICHOST | NI_NUMERICSERV)) != 0) {
 910                 fr_strerror_printf("ip_ntoh: %s", gai_strerror(error));
 911                 return NULL;
 912         }
 913         return dst;
 914 }
 915
 916 /** Mask off a portion of an IPv4 address
 917  *
 918  * @param ipaddr to mask.
 919  * @param prefix Number of contiguous bits to mask.
 920  * @return an ipv6 address with the host portion zeroed out.
 921  */
 922 struct in_addr fr_inaddr_mask(struct in_addr const *ipaddr, uint8_t prefix)
 923 {
 924         uint32_t ret;
 925
 926         if (prefix > 32) {
 927                 prefix = 32;
 928         }
 929
 930         /* Short circuit */
 931         if (prefix == 32) {
 932                 return *ipaddr;
 933         }
 934
 935         ret = htonl(~((0x00000001UL << (32 - prefix)) - 1)) & ipaddr->s_addr;
 936         return (*(struct in_addr *)&ret);
 937 }
 938
 939 /** Mask off a portion of an IPv6 address
 940  *
 941  * @param ipaddr to mask.
 942  * @param prefix Number of contiguous bits to mask.
 943  * @return an ipv6 address with the host portion zeroed out.
 944  */
 945 struct in6_addr fr_in6addr_mask(struct in6_addr const *ipaddr, uint8_t prefix)
 946 {
 947         uint64_t const *p = (uint64_t const *) ipaddr;
 948         uint64_t ret[2], *o = ret;
 949
 950         if (prefix > 128) {
 951                 prefix = 128;
 952         }
 953
 954         /* Short circuit */
 955         if (prefix == 128) {
 956                 return *ipaddr;
 957         }
 958
 959         if (prefix >= 64) {
 960                 prefix -= 64;
 961                 *o++ = 0xffffffffffffffffULL & *p++;
 962         } else {
 963                 ret[1] = 0;
 964         }
 965
 966         *o = htonll(~((0x0000000000000001ULL << (64 - prefix)) - 1)) & *p;
 967
 968         return *(struct in6_addr *) &ret;
 969 }
 970
 971 /** Zeroes out the host portion of an fr_ipaddr_t
 972  *
 973  * @param[in,out] addr to mask
 974  * @param[in] prefix Length of the network portion.
 975  */
 976 void fr_ipaddr_mask(fr_ipaddr_t *addr, uint8_t prefix)
 977 {
 978
 979         switch (addr->af) {
 980         case AF_INET:
 981                 addr->ipaddr.ip4addr = fr_inaddr_mask(&addr->ipaddr.ip4addr, prefix);
 982                 break;
 983
 984         case AF_INET6:
 985                 addr->ipaddr.ip6addr = fr_in6addr_mask(&addr->ipaddr.ip6addr, prefix);
 986                 break;
 987
 988         default:
 989                 return;
 990         }
 991         addr->prefix = prefix;
 992 }
 993
 994 static char const hextab[] = "0123456789abcdef";
 995
 996 /** Convert hex strings to binary data
 997  *
 998  * @param bin Buffer to write output to.
 999  * @param outlen length of output buffer (or length of input string / 2).
1000  * @param hex input string.
1001  * @param inlen length of the input string
1002  * @return length of data written to buffer.
1003  */
1004 size_t fr_hex2bin(uint8_t *bin, size_t outlen, char const *hex, size_t inlen)
1005 {
1006         size_t i;
1007         size_t len;
1008         char *c1, *c2;
1009
1010         /*
1011          *      Smartly truncate output, caller should check number of bytes
1012          *      written.
1013          */
1014         len = inlen >> 1;
1015         if (len > outlen) len = outlen;
1016
1017         for (i = 0; i < len; i++) {
1018                 if(!(c1 = memchr(hextab, tolower((int) hex[i << 1]), sizeof(hextab))) ||
1019                    !(c2 = memchr(hextab, tolower((int) hex[(i << 1) + 1]), sizeof(hextab))))
1020                         break;
1021                 bin[i] = ((c1-hextab)<<4) + (c2-hextab);
1022         }
1023
1024         return i;
1025 }
1026
1027
1028 /** Convert binary data to a hex string
1029  *
1030  * Ascii encoded hex string will not be prefixed with '0x'
1031  *
1032  * @warning If the output buffer isn't long enough, we have a buffer overflow.
1033  *
1034  * @param[out] hex Buffer to write hex output.
1035  * @param[in] bin input.
1036  * @param[in] inlen of bin input.
1037  * @return length of data written to buffer.
1038  */
1039 size_t fr_bin2hex(char *hex, uint8_t const *bin, size_t inlen)
1040 {
1041         size_t i;
1042
1043         for (i = 0; i < inlen; i++) {
1044                 hex[0] = hextab[((*bin) >> 4) & 0x0f];
1045                 hex[1] = hextab[*bin & 0x0f];
1046                 hex += 2;
1047                 bin++;
1048         }
1049
1050         *hex = '\0';
1051         return inlen * 2;
1052 }
1053
1054
1055
1056 /** Consume the integer (or hex) portion of a value string
1057  *
1058  * @param value string to parse.
1059  * @param end pointer to the first non numeric char.
1060  * @return integer value.
1061  */
1062 uint32_t fr_strtoul(char const *value, char **end)
1063 {
1064         if ((value[0] == '0') && (value[1] == 'x')) {
1065                 return strtoul(value, end, 16);
1066         }
1067
1068         return strtoul(value, end, 10);
1069 }
1070
1071 /** Check whether the string is all whitespace
1072  *
1073  * @return true if the entirety of the string is whitespace, else false.
1074  */
1075 bool is_whitespace(char const *value)
1076 {
1077         do {
1078                 if (!isspace(*value)) return false;
1079         } while (*++value);
1080
1081         return true;
1082 }
1083
1084 /** Check whether the string is all numbers
1085  *
1086  * @return true if the entirety of the string is are numebrs, else false.
1087  */
1088 bool is_integer(char const *value)
1089 {
1090         do {
1091                 if (!isdigit(*value)) return false;
1092         } while (*++value);
1093
1094         return true;
1095 }
1096
1097 /** Check whether the string is allzeros
1098  *
1099  * @return true if the entirety of the string is are numebrs, else false.
1100  */
1101 bool is_zero(char const *value)
1102 {
1103         do {
1104                 if (*value != '0') return false;
1105         } while (*++value);
1106
1107         return true;
1108 }
1109
1110 /*
1111  *      So we don't have ifdef's in the rest of the code
1112  */
1113 #ifndef HAVE_CLOSEFROM
1114 int closefrom(int fd)
1115 {
1116         int i;
1117         int maxfd = 256;
1118
1119 #ifdef _SC_OPEN_MAX
1120         maxfd = sysconf(_SC_OPEN_MAX);
1121         if (maxfd < 0) {
1122           maxfd = 256;
1123         }
1124 #endif
1125
1126         if (fd > maxfd) return 0;
1127
1128         /*
1129          *      FIXME: return EINTR?
1130          *
1131          *      Use F_CLOSEM?
1132          */
1133         for (i = fd; i < maxfd; i++) {
1134                 close(i);
1135         }
1136
1137         return 0;
1138 }
1139 #endif
1140
1141 int fr_ipaddr_cmp(fr_ipaddr_t const *a, fr_ipaddr_t const *b)
1142 {
1143         if (a->af < b->af) return -1;
1144         if (a->af > b->af) return +1;
1145
1146         switch (a->af) {
1147         case AF_INET:
1148                 return memcmp(&a->ipaddr.ip4addr,
1149                               &b->ipaddr.ip4addr,
1150                               sizeof(a->ipaddr.ip4addr));
1151                 break;
1152
1153 #ifdef HAVE_STRUCT_SOCKADDR_IN6
1154         case AF_INET6:
1155                 if (a->scope < b->scope) return -1;
1156                 if (a->scope > b->scope) return +1;
1157
1158                 return memcmp(&a->ipaddr.ip6addr,
1159                               &b->ipaddr.ip6addr,
1160                               sizeof(a->ipaddr.ip6addr));
1161                 break;
1162 #endif
1163
1164         default:
1165                 break;
1166         }
1167
1168         return -1;
1169 }
1170
1171 int fr_ipaddr2sockaddr(fr_ipaddr_t const *ipaddr, uint16_t port,
1172                        struct sockaddr_storage *sa, socklen_t *salen)
1173 {
1174         if (ipaddr->af == AF_INET) {
1175                 struct sockaddr_in s4;
1176
1177                 *salen = sizeof(s4);
1178
1179                 memset(&s4, 0, sizeof(s4));
1180                 s4.sin_family = AF_INET;
1181                 s4.sin_addr = ipaddr->ipaddr.ip4addr;
1182                 s4.sin_port = htons(port);
1183                 memset(sa, 0, sizeof(*sa));
1184                 memcpy(sa, &s4, sizeof(s4));
1185
1186 #ifdef HAVE_STRUCT_SOCKADDR_IN6
1187         } else if (ipaddr->af == AF_INET6) {
1188                 struct sockaddr_in6 s6;
1189
1190                 *salen = sizeof(s6);
1191
1192                 memset(&s6, 0, sizeof(s6));
1193                 s6.sin6_family = AF_INET6;
1194                 s6.sin6_addr = ipaddr->ipaddr.ip6addr;
1195                 s6.sin6_port = htons(port);
1196                 s6.sin6_scope_id = ipaddr->scope;
1197                 memset(sa, 0, sizeof(*sa));
1198                 memcpy(sa, &s6, sizeof(s6));
1199 #endif
1200         } else {
1201                 return 0;
1202         }
1203
1204         return 1;
1205 }
1206
1207
1208 int fr_sockaddr2ipaddr(struct sockaddr_storage const *sa, socklen_t salen,
1209                        fr_ipaddr_t *ipaddr, uint16_t *port)
1210 {
1211         if (sa->ss_family == AF_INET) {
1212                 struct sockaddr_in      s4;
1213
1214                 if (salen < sizeof(s4)) {
1215                         fr_strerror_printf("IPv4 address is too small");
1216                         return 0;
1217                 }
1218
1219                 memcpy(&s4, sa, sizeof(s4));
1220                 ipaddr->af = AF_INET;
1221                 ipaddr->prefix = 32;
1222                 ipaddr->ipaddr.ip4addr = s4.sin_addr;
1223                 if (port) *port = ntohs(s4.sin_port);
1224
1225 #ifdef HAVE_STRUCT_SOCKADDR_IN6
1226         } else if (sa->ss_family == AF_INET6) {
1227                 struct sockaddr_in6     s6;
1228
1229                 if (salen < sizeof(s6)) {
1230                         fr_strerror_printf("IPv6 address is too small");
1231                         return 0;
1232                 }
1233
1234                 memcpy(&s6, sa, sizeof(s6));
1235                 ipaddr->af = AF_INET6;
1236                 ipaddr->prefix = 128;
1237                 ipaddr->ipaddr.ip6addr = s6.sin6_addr;
1238                 if (port) *port = ntohs(s6.sin6_port);
1239                 ipaddr->scope = s6.sin6_scope_id;
1240 #endif
1241
1242         } else {
1243                 fr_strerror_printf("Unsupported address famility %d",
1244                                    sa->ss_family);
1245                 return 0;
1246         }
1247
1248         return 1;
1249 }
1250
1251 /** Convert UTF8 string to UCS2 encoding
1252  *
1253  * @note Borrowed from src/crypto/ms_funcs.c of wpa_supplicant project (http://hostap.epitest.fi/wpa_supplicant/)
1254  *
1255  * @param[out] out Where to write the ucs2 string.
1256  * @param[in] outlen Size of output buffer.
1257  * @param[in] in UTF8 string to convert.
1258  * @param[in] inlen length of UTF8 string.
1259  * @return the size of the UCS2 string written to the output buffer (in bytes).
1260  */
1261 ssize_t fr_utf8_to_ucs2(uint8_t *out, size_t outlen, char const *in, size_t inlen)
1262 {
1263         size_t i;
1264         uint8_t *start = out;
1265
1266         for (i = 0; i < inlen; i++) {
1267                 uint8_t c, c2, c3;
1268
1269                 c = in[i];
1270                 if ((size_t)(out - start) >= outlen) {
1271                         /* input too long */
1272                         return -1;
1273                 }
1274
1275                 /* One-byte encoding */
1276                 if (c <= 0x7f) {
1277                         FR_PUT_LE16(out, c);
1278                         out += 2;
1279                         continue;
1280                 } else if ((i == (inlen - 1)) || ((size_t)(out - start) >= (outlen - 1))) {
1281                         /* Incomplete surrogate */
1282                         return -1;
1283                 }
1284
1285                 c2 = in[++i];
1286                 /* Two-byte encoding */
1287                 if ((c & 0xe0) == 0xc0) {
1288                         FR_PUT_LE16(out, ((c & 0x1f) << 6) | (c2 & 0x3f));
1289                         out += 2;
1290                         continue;
1291                 }
1292                 if ((i == inlen) || ((size_t)(out - start) >= (outlen - 1))) {
1293                         /* Incomplete surrogate */
1294                         return -1;
1295                 }
1296
1297                 /* Three-byte encoding */
1298                 c3 = in[++i];
1299                 FR_PUT_LE16(out, ((c & 0xf) << 12) | ((c2 & 0x3f) << 6) | (c3 & 0x3f));
1300                 out += 2;
1301         }
1302
1303         return out - start;
1304 }
1305
1306 /** Write 128bit unsigned integer to buffer
1307  *
1308  * @author Alexey Frunze
1309  *
1310  * @param out where to write result to.
1311  * @param outlen size of out.
1312  * @param num 128 bit integer.
1313  */
1314 size_t fr_prints_uint128(char *out, size_t outlen, uint128_t const num)
1315 {
1316         char buff[128 / 3 + 1 + 1];
1317         uint64_t n[2];
1318         char *p = buff;
1319         int i;
1320
1321         memset(buff, '0', sizeof(buff) - 1);
1322         buff[sizeof(buff) - 1] = '\0';
1323
1324         memcpy(n, &num, sizeof(n));
1325
1326         for (i = 0; i < 128; i++) {
1327                 ssize_t j;
1328                 int carry;
1329
1330                 carry = (n[1] >= 0x8000000000000000);
1331
1332                 // Shift n[] left, doubling it
1333                 n[1] = ((n[1] << 1) & 0xffffffffffffffff) + (n[0] >= 0x8000000000000000);
1334                 n[0] = ((n[0] << 1) & 0xffffffffffffffff);
1335
1336                 // Add s[] to itself in decimal, doubling it
1337                 for (j = sizeof(buff) - 2; j >= 0; j--) {
1338                         buff[j] += buff[j] - '0' + carry;
1339                         carry = (buff[j] > '9');
1340                         if (carry) {
1341                                 buff[j] -= 10;
1342                         }
1343                 }
1344         }
1345
1346         while ((*p == '0') && (p < &buff[sizeof(buff) - 2])) {
1347                 p++;
1348         }
1349
1350         return strlcpy(out, p, outlen);
1351 }
1352
1353 /** Calculate powers
1354  *
1355  * @author Orson Peters
1356  * @note Borrowed from the gist here: https://gist.github.com/nightcracker/3551590.
1357  *
1358  * @param base a 32bit signed integer.
1359  * @param exp amount to raise base by.
1360  * @return base ^ pow, or 0 on underflow/overflow.
1361  */
1362 int64_t fr_pow(int32_t base, uint8_t exp) {
1363         static const uint8_t highest_bit_set[] = {
1364                 0, 1, 2, 2, 3, 3, 3, 3,
1365                 4, 4, 4, 4, 4, 4, 4, 4,
1366                 5, 5, 5, 5, 5, 5, 5, 5,
1367                 5, 5, 5, 5, 5, 5, 5, 5,
1368                 6, 6, 6, 6, 6, 6, 6, 6,
1369                 6, 6, 6, 6, 6, 6, 6, 6,
1370                 6, 6, 6, 6, 6, 6, 6, 6,
1371                 6, 6, 6, 6, 6, 6, 6, 255, // anything past 63 is a guaranteed overflow with base > 1
1372                 255, 255, 255, 255, 255, 255, 255, 255,
1373                 255, 255, 255, 255, 255, 255, 255, 255,
1374                 255, 255, 255, 255, 255, 255, 255, 255,
1375                 255, 255, 255, 255, 255, 255, 255, 255,
1376                 255, 255, 255, 255, 255, 255, 255, 255,
1377                 255, 255, 255, 255, 255, 255, 255, 255,
1378                 255, 255, 255, 255, 255, 255, 255, 255,
1379                 255, 255, 255, 255, 255, 255, 255, 255,
1380                 255, 255, 255, 255, 255, 255, 255, 255,
1381                 255, 255, 255, 255, 255, 255, 255, 255,
1382                 255, 255, 255, 255, 255, 255, 255, 255,
1383                 255, 255, 255, 255, 255, 255, 255, 255,
1384                 255, 255, 255, 255, 255, 255, 255, 255,
1385                 255, 255, 255, 255, 255, 255, 255, 255,
1386                 255, 255, 255, 255, 255, 255, 255, 255,
1387                 255, 255, 255, 255, 255, 255, 255, 255,
1388                 255, 255, 255, 255, 255, 255, 255, 255,
1389                 255, 255, 255, 255, 255, 255, 255, 255,
1390                 255, 255, 255, 255, 255, 255, 255, 255,
1391                 255, 255, 255, 255, 255, 255, 255, 255,
1392                 255, 255, 255, 255, 255, 255, 255, 255,
1393                 255, 255, 255, 255, 255, 255, 255, 255,
1394                 255, 255, 255, 255, 255, 255, 255, 255,
1395                 255, 255, 255, 255, 255, 255, 255, 255,
1396         };
1397
1398         uint64_t result = 1;
1399
1400         switch (highest_bit_set[exp]) {
1401         case 255: // we use 255 as an overflow marker and return 0 on overflow/underflow
1402                 if (base == 1) {
1403                         return 1;
1404                 }
1405
1406                 if (base == -1) {
1407                         return 1 - 2 * (exp & 1);
1408                 }
1409                 return 0;
1410         case 6:
1411                 if (exp & 1) result *= base;
1412                 exp >>= 1;
1413                 base *= base;
1414         case 5:
1415                 if (exp & 1) result *= base;
1416                 exp >>= 1;
1417                 base *= base;
1418         case 4:
1419                 if (exp & 1) result *= base;
1420                 exp >>= 1;
1421                 base *= base;
1422         case 3:
1423                 if (exp & 1) result *= base;
1424                 exp >>= 1;
1425                 base *= base;
1426         case 2:
1427                 if (exp & 1) result *= base;
1428                 exp >>= 1;
1429                 base *= base;
1430         case 1:
1431                 if (exp & 1) result *= base;
1432         default:
1433                 return result;
1434         }
1435 }
1436
1437 /*
1438  *      Sort of strtok/strsep function.
1439  */
1440 static char *mystrtok(char **ptr, char const *sep)
1441 {
1442         char    *res;
1443
1444         if (**ptr == 0) {
1445                 return NULL;
1446         }
1447
1448         while (**ptr && strchr(sep, **ptr)) {
1449                 (*ptr)++;
1450         }
1451         if (**ptr == 0) {
1452                 return NULL;
1453         }
1454
1455         res = *ptr;
1456         while (**ptr && strchr(sep, **ptr) == NULL) {
1457                 (*ptr)++;
1458         }
1459
1460         if (**ptr != 0) {
1461                 *(*ptr)++ = 0;
1462         }
1463         return res;
1464 }
1465
1466 /** Convert string in various formats to a time_t
1467  *
1468  * @param date_str input date string.
1469  * @param date time_t to write result to.
1470  * @return 0 on success or -1 on error.
1471  */
1472 int fr_get_time(char const *date_str, time_t *date)
1473 {
1474         int             i;
1475         time_t          t;
1476         struct tm       *tm, s_tm;
1477         char            buf[64];
1478         char            *p;
1479         char            *f[4];
1480         char            *tail = NULL;
1481
1482         /*
1483          * Test for unix timestamp date
1484          */
1485         *date = strtoul(date_str, &tail, 10);
1486         if (*tail == '\0') {
1487                 return 0;
1488         }
1489
1490         tm = &s_tm;
1491         memset(tm, 0, sizeof(*tm));
1492         tm->tm_isdst = -1;      /* don't know, and don't care about DST */
1493
1494         strlcpy(buf, date_str, sizeof(buf));
1495
1496         p = buf;
1497         f[0] = mystrtok(&p, " \t");
1498         f[1] = mystrtok(&p, " \t");
1499         f[2] = mystrtok(&p, " \t");
1500         f[3] = mystrtok(&p, " \t"); /* may, or may not, be present */
1501         if (!f[0] || !f[1] || !f[2]) return -1;
1502
1503         /*
1504          *      The time has a colon, where nothing else does.
1505          *      So if we find it, bubble it to the back of the list.
1506          */
1507         if (f[3]) {
1508                 for (i = 0; i < 3; i++) {
1509                         if (strchr(f[i], ':')) {
1510                                 p = f[3];
1511                                 f[3] = f[i];
1512                                 f[i] = p;
1513                                 break;
1514                         }
1515                 }
1516         }
1517
1518         /*
1519          *  The month is text, which allows us to find it easily.
1520          */
1521         tm->tm_mon = 12;
1522         for (i = 0; i < 3; i++) {
1523                 if (isalpha( (int) *f[i])) {
1524                         /*
1525                          *  Bubble the month to the front of the list
1526                          */
1527                         p = f[0];
1528                         f[0] = f[i];
1529                         f[i] = p;
1530
1531                         for (i = 0; i < 12; i++) {
1532                                 if (strncasecmp(months[i], f[0], 3) == 0) {
1533                                         tm->tm_mon = i;
1534                                         break;
1535                                 }
1536                         }
1537                 }
1538         }
1539
1540         /* month not found? */
1541         if (tm->tm_mon == 12) return -1;
1542
1543         /*
1544          *  The year may be in f[1], or in f[2]
1545          */
1546         tm->tm_year = atoi(f[1]);
1547         tm->tm_mday = atoi(f[2]);
1548
1549         if (tm->tm_year >= 1900) {
1550                 tm->tm_year -= 1900;
1551
1552         } else {
1553                 /*
1554                  *  We can't use 2-digit years any more, they make it
1555                  *  impossible to tell what's the day, and what's the year.
1556                  */
1557                 if (tm->tm_mday < 1900) return -1;
1558
1559                 /*
1560                  *  Swap the year and the day.
1561                  */
1562                 i = tm->tm_year;
1563                 tm->tm_year = tm->tm_mday - 1900;
1564                 tm->tm_mday = i;
1565         }
1566
1567         /*
1568          *  If the day is out of range, die.
1569          */
1570         if ((tm->tm_mday < 1) || (tm->tm_mday > 31)) {
1571                 return -1;
1572         }
1573
1574         /*
1575          *      There may be %H:%M:%S.  Parse it in a hacky way.
1576          */
1577         if (f[3]) {
1578                 f[0] = f[3];    /* HH */
1579                 f[1] = strchr(f[0], ':'); /* find : separator */
1580                 if (!f[1]) return -1;
1581
1582                 *(f[1]++) = '\0'; /* nuke it, and point to MM:SS */
1583
1584                 f[2] = strchr(f[1], ':'); /* find : separator */
1585                 if (f[2]) {
1586                   *(f[2]++) = '\0';     /* nuke it, and point to SS */
1587                   tm->tm_sec = atoi(f[2]);
1588                 }                       /* else leave it as zero */
1589
1590                 tm->tm_hour = atoi(f[0]);
1591                 tm->tm_min = atoi(f[1]);
1592         }
1593
1594         /*
1595          *  Returns -1 on error.
1596          */
1597         t = mktime(tm);
1598         if (t == (time_t) -1) return -1;
1599
1600         *date = t;
1601
1602         return 0;
1603 }
1604
1605 /** Compares two pointers
1606  *
1607  * @param a first pointer to compare.
1608  * @param b second pointer to compare.
1609  * @return -1 if a < b, +1 if b > a, or 0 if both equal.
1610  */
1611 int8_t fr_pointer_cmp(void const *a, void const *b)
1612 {
1613         if (a < b) return -1;
1614         if (a == b) return 0;
1615
1616         return 1;
1617 }
1618
1619 static int _quick_partition(void const *to_sort[], int min, int max, fr_cmp_t cmp) {
1620         void const *pivot = to_sort[min];
1621         int i = min;
1622         int j = max + 1;
1623         void const *tmp;
1624
1625         for (;;) {
1626                 do ++i; while((cmp(to_sort[i], pivot) <= 0) && i <= max);
1627                 do --j; while(cmp(to_sort[j], pivot) > 0);
1628
1629                 if (i >= j) break;
1630
1631                 tmp = to_sort[i];
1632                 to_sort[i] = to_sort[j];
1633                 to_sort[j] = tmp;
1634         }
1635
1636         tmp = to_sort[min];
1637         to_sort[min] = to_sort[j];
1638         to_sort[j] = tmp;
1639
1640         return j;
1641 }
1642
1643 /** Quick sort an array of pointers using a comparator
1644  *
1645  * @param to_sort array of pointers to sort.
1646  * @param min_idx the lowest index (usually 0).
1647  * @param max_idx the highest index (usually length of array - 1).
1648  * @param cmp the comparison function to use to sort the array elements.
1649  */
1650 void fr_quick_sort(void const *to_sort[], int min_idx, int max_idx, fr_cmp_t cmp)
1651 {
1652         int part;
1653
1654         if (min_idx >= max_idx) return;
1655
1656         part = _quick_partition(to_sort, min_idx, max_idx, cmp);
1657         fr_quick_sort(to_sort, min_idx, part - 1, cmp);
1658         fr_quick_sort(to_sort, part + 1, max_idx, cmp);
1659 }
1660
1661 #ifdef TALLOC_DEBUG
1662 void fr_talloc_verify_cb(UNUSED const void *ptr, UNUSED int depth,
1663                          UNUSED int max_depth, UNUSED int is_ref,
1664                          UNUSED void *private_data)
1665 {
1666         /* do nothing */
1667 }
1668 #endif