lib/util.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "util.h"
  19 #include <assert.h>
  20 #include <errno.h>
  21 #include <limits.h>
  22 #include <stdarg.h>
  23 #include <stdint.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <unistd.h>
  28 #include "byte-order.h"
  29 #include "coverage.h"
  30 #include "openvswitch/types.h"
  31 #include "vlog.h"
  32
  33 VLOG_DEFINE_THIS_MODULE(util);
  34
  35 COVERAGE_DEFINE(util_xalloc);
  36
  37 /* argv[0] without directory names. */
  38 const char *program_name;
  39
  40 /* Ordinarily "" but set to "monitor" for a monitor process or "worker" for a
  41  * worker process. */
  42 const char *subprogram_name = "";
  43
  44 /* --version option output. */
  45 static char *program_version;
  46
  47 void
  48 out_of_memory(void)
  49 {
  50     ovs_abort(0, "virtual memory exhausted");
  51 }
  52
  53 void *
  54 xcalloc(size_t count, size_t size)
  55 {
  56     void *p = count && size ? calloc(count, size) : malloc(1);
  57     COVERAGE_INC(util_xalloc);
  58     if (p == NULL) {
  59         out_of_memory();
  60     }
  61     return p;
  62 }
  63
  64 void *
  65 xzalloc(size_t size)
  66 {
  67     return xcalloc(1, size);
  68 }
  69
  70 void *
  71 xmalloc(size_t size)
  72 {
  73     void *p = malloc(size ? size : 1);
  74     COVERAGE_INC(util_xalloc);
  75     if (p == NULL) {
  76         out_of_memory();
  77     }
  78     return p;
  79 }
  80
  81 void *
  82 xrealloc(void *p, size_t size)
  83 {
  84     p = realloc(p, size ? size : 1);
  85     COVERAGE_INC(util_xalloc);
  86     if (p == NULL) {
  87         out_of_memory();
  88     }
  89     return p;
  90 }
  91
  92 void *
  93 xmemdup(const void *p_, size_t size)
  94 {
  95     void *p = xmalloc(size);
  96     memcpy(p, p_, size);
  97     return p;
  98 }
  99
 100 char *
 101 xmemdup0(const char *p_, size_t length)
 102 {
 103     char *p = xmalloc(length + 1);
 104     memcpy(p, p_, length);
 105     p[length] = '\0';
 106     return p;
 107 }
 108
 109 char *
 110 xstrdup(const char *s)
 111 {
 112     return xmemdup0(s, strlen(s));
 113 }
 114
 115 char *
 116 xvasprintf(const char *format, va_list args)
 117 {
 118     va_list args2;
 119     size_t needed;
 120     char *s;
 121
 122     va_copy(args2, args);
 123     needed = vsnprintf(NULL, 0, format, args);
 124
 125     s = xmalloc(needed + 1);
 126
 127     vsnprintf(s, needed + 1, format, args2);
 128     va_end(args2);
 129
 130     return s;
 131 }
 132
 133 void *
 134 x2nrealloc(void *p, size_t *n, size_t s)
 135 {
 136     *n = *n == 0 ? 1 : 2 * *n;
 137     return xrealloc(p, *n * s);
 138 }
 139
 140 char *
 141 xasprintf(const char *format, ...)
 142 {
 143     va_list args;
 144     char *s;
 145
 146     va_start(args, format);
 147     s = xvasprintf(format, args);
 148     va_end(args);
 149
 150     return s;
 151 }
 152
 153 /* Similar to strlcpy() from OpenBSD, but it never reads more than 'size - 1'
 154  * bytes from 'src' and doesn't return anything. */
 155 void
 156 ovs_strlcpy(char *dst, const char *src, size_t size)
 157 {
 158     if (size > 0) {
 159         size_t len = strnlen(src, size - 1);
 160         memcpy(dst, src, len);
 161         dst[len] = '\0';
 162     }
 163 }
 164
 165 /* Copies 'src' to 'dst'.  Reads no more than 'size - 1' bytes from 'src'.
 166  * Always null-terminates 'dst' (if 'size' is nonzero), and writes a zero byte
 167  * to every otherwise unused byte in 'dst'.
 168  *
 169  * Except for performance, the following call:
 170  *     ovs_strzcpy(dst, src, size);
 171  * is equivalent to these two calls:
 172  *     memset(dst, '\0', size);
 173  *     ovs_strlcpy(dst, src, size);
 174  *
 175  * (Thus, ovs_strzcpy() is similar to strncpy() without some of the pitfalls.)
 176  */
 177 void
 178 ovs_strzcpy(char *dst, const char *src, size_t size)
 179 {
 180     if (size > 0) {
 181         size_t len = strnlen(src, size - 1);
 182         memcpy(dst, src, len);
 183         memset(dst + len, '\0', size - len);
 184     }
 185 }
 186
 187 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 188  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 189  * the message inside parentheses.  Then, terminates with abort().
 190  *
 191  * This function is preferred to ovs_fatal() in a situation where it would make
 192  * sense for a monitoring process to restart the daemon.
 193  *
 194  * 'format' should not end with a new-line, because this function will add one
 195  * itself. */
 196 void
 197 ovs_abort(int err_no, const char *format, ...)
 198 {
 199     va_list args;
 200
 201     va_start(args, format);
 202     ovs_error_valist(err_no, format, args);
 203     va_end(args);
 204
 205     abort();
 206 }
 207
 208 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 209  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 210  * the message inside parentheses.  Then, terminates with EXIT_FAILURE.
 211  *
 212  * 'format' should not end with a new-line, because this function will add one
 213  * itself. */
 214 void
 215 ovs_fatal(int err_no, const char *format, ...)
 216 {
 217     va_list args;
 218
 219     va_start(args, format);
 220     ovs_fatal_valist(err_no, format, args);
 221 }
 222
 223 /* Same as ovs_fatal() except that the arguments are supplied as a va_list. */
 224 void
 225 ovs_fatal_valist(int err_no, const char *format, va_list args)
 226 {
 227     ovs_error_valist(err_no, format, args);
 228     exit(EXIT_FAILURE);
 229 }
 230
 231 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 232  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 233  * the message inside parentheses.
 234  *
 235  * 'format' should not end with a new-line, because this function will add one
 236  * itself. */
 237 void
 238 ovs_error(int err_no, const char *format, ...)
 239 {
 240     va_list args;
 241
 242     va_start(args, format);
 243     ovs_error_valist(err_no, format, args);
 244     va_end(args);
 245 }
 246
 247 /* Same as ovs_error() except that the arguments are supplied as a va_list. */
 248 void
 249 ovs_error_valist(int err_no, const char *format, va_list args)
 250 {
 251     int save_errno = errno;
 252
 253     if (subprogram_name[0]) {
 254         fprintf(stderr, "%s(%s): ", program_name, subprogram_name);
 255     } else {
 256         fprintf(stderr, "%s: ", program_name);
 257     }
 258
 259     vfprintf(stderr, format, args);
 260     if (err_no != 0) {
 261         fprintf(stderr, " (%s)", ovs_retval_to_string(err_no));
 262     }
 263     putc('\n', stderr);
 264
 265     errno = save_errno;
 266 }
 267
 268 /* Many OVS functions return an int which is one of:
 269  * - 0: no error yet
 270  * - >0: errno value
 271  * - EOF: end of file (not necessarily an error; depends on the function called)
 272  *
 273  * Returns the appropriate human-readable string. The caller must copy the
 274  * string if it wants to hold onto it, as the storage may be overwritten on
 275  * subsequent function calls.
 276  */
 277 const char *
 278 ovs_retval_to_string(int retval)
 279 {
 280     static char unknown[48];
 281
 282     if (!retval) {
 283         return "";
 284     }
 285     if (retval > 0) {
 286         return strerror(retval);
 287     }
 288     if (retval == EOF) {
 289         return "End of file";
 290     }
 291     snprintf(unknown, sizeof unknown, "***unknown return value: %d***", retval);
 292     return unknown;
 293 }
 294
 295 /* Sets global "program_name" and "program_version" variables.  Should
 296  * be called at the beginning of main() with "argv[0]" as the argument
 297  * to 'argv0'.
 298  *
 299  * 'version' should contain the version of the caller's program.  If 'version'
 300  * is the same as the VERSION #define, the caller is assumed to be part of Open
 301  * vSwitch.  Otherwise, it is assumed to be an external program linking against
 302  * the Open vSwitch libraries.
 303  *
 304  * The 'date' and 'time' arguments should likely be called with
 305  * "__DATE__" and "__TIME__" to use the time the binary was built.
 306  * Alternatively, the "set_program_name" macro may be called to do this
 307  * automatically.
 308  */
 309 void
 310 set_program_name__(const char *argv0, const char *version, const char *date,
 311                    const char *time)
 312 {
 313     const char *slash = strrchr(argv0, '/');
 314     program_name = slash ? slash + 1 : argv0;
 315
 316     free(program_version);
 317
 318     if (!strcmp(version, VERSION)) {
 319         program_version = xasprintf("%s (Open vSwitch) "VERSION"\n"
 320                                     "Compiled %s %s\n",
 321                                     program_name, date, time);
 322     } else {
 323         program_version = xasprintf("%s %s\n"
 324                                     "Open vSwitch Library "VERSION"\n"
 325                                     "Compiled %s %s\n",
 326                                     program_name, version, date, time);
 327     }
 328 }
 329
 330 /* Returns a pointer to a string describing the program version.  The
 331  * caller must not modify or free the returned string.
 332  */
 333 const char *
 334 get_program_version(void)
 335 {
 336     return program_version;
 337 }
 338
 339 /* Print the version information for the program.  */
 340 void
 341 ovs_print_version(uint8_t min_ofp, uint8_t max_ofp)
 342 {
 343     printf("%s", program_version);
 344     if (min_ofp || max_ofp) {
 345         printf("OpenFlow versions %#x:%#x\n", min_ofp, max_ofp);
 346     }
 347 }
 348
 349 /* Writes the 'size' bytes in 'buf' to 'stream' as hex bytes arranged 16 per
 350  * line.  Numeric offsets are also included, starting at 'ofs' for the first
 351  * byte in 'buf'.  If 'ascii' is true then the corresponding ASCII characters
 352  * are also rendered alongside. */
 353 void
 354 ovs_hex_dump(FILE *stream, const void *buf_, size_t size,
 355              uintptr_t ofs, bool ascii)
 356 {
 357   const uint8_t *buf = buf_;
 358   const size_t per_line = 16; /* Maximum bytes per line. */
 359
 360   while (size > 0)
 361     {
 362       size_t start, end, n;
 363       size_t i;
 364
 365       /* Number of bytes on this line. */
 366       start = ofs % per_line;
 367       end = per_line;
 368       if (end - start > size)
 369         end = start + size;
 370       n = end - start;
 371
 372       /* Print line. */
 373       fprintf(stream, "%08jx  ", (uintmax_t) ROUND_DOWN(ofs, per_line));
 374       for (i = 0; i < start; i++)
 375         fprintf(stream, "   ");
 376       for (; i < end; i++)
 377         fprintf(stream, "%02hhx%c",
 378                 buf[i - start], i == per_line / 2 - 1? '-' : ' ');
 379       if (ascii)
 380         {
 381           for (; i < per_line; i++)
 382             fprintf(stream, "   ");
 383           fprintf(stream, "|");
 384           for (i = 0; i < start; i++)
 385             fprintf(stream, " ");
 386           for (; i < end; i++) {
 387               int c = buf[i - start];
 388               putc(c >= 32 && c < 127 ? c : '.', stream);
 389           }
 390           for (; i < per_line; i++)
 391             fprintf(stream, " ");
 392           fprintf(stream, "|");
 393         }
 394       fprintf(stream, "\n");
 395
 396       ofs += n;
 397       buf += n;
 398       size -= n;
 399     }
 400 }
 401
 402 bool
 403 str_to_int(const char *s, int base, int *i)
 404 {
 405     long long ll;
 406     bool ok = str_to_llong(s, base, &ll);
 407     *i = ll;
 408     return ok;
 409 }
 410
 411 bool
 412 str_to_long(const char *s, int base, long *li)
 413 {
 414     long long ll;
 415     bool ok = str_to_llong(s, base, &ll);
 416     *li = ll;
 417     return ok;
 418 }
 419
 420 bool
 421 str_to_llong(const char *s, int base, long long *x)
 422 {
 423     int save_errno = errno;
 424     char *tail;
 425     errno = 0;
 426     *x = strtoll(s, &tail, base);
 427     if (errno == EINVAL || errno == ERANGE || tail == s || *tail != '\0') {
 428         errno = save_errno;
 429         *x = 0;
 430         return false;
 431     } else {
 432         errno = save_errno;
 433         return true;
 434     }
 435 }
 436
 437 bool
 438 str_to_uint(const char *s, int base, unsigned int *u)
 439 {
 440     return str_to_int(s, base, (int *) u);
 441 }
 442
 443 bool
 444 str_to_ulong(const char *s, int base, unsigned long *ul)
 445 {
 446     return str_to_long(s, base, (long *) ul);
 447 }
 448
 449 bool
 450 str_to_ullong(const char *s, int base, unsigned long long *ull)
 451 {
 452     return str_to_llong(s, base, (long long *) ull);
 453 }
 454
 455 /* Converts floating-point string 's' into a double.  If successful, stores
 456  * the double in '*d' and returns true; on failure, stores 0 in '*d' and
 457  * returns false.
 458  *
 459  * Underflow (e.g. "1e-9999") is not considered an error, but overflow
 460  * (e.g. "1e9999)" is. */
 461 bool
 462 str_to_double(const char *s, double *d)
 463 {
 464     int save_errno = errno;
 465     char *tail;
 466     errno = 0;
 467     *d = strtod(s, &tail);
 468     if (errno == EINVAL || (errno == ERANGE && *d != 0)
 469         || tail == s || *tail != '\0') {
 470         errno = save_errno;
 471         *d = 0;
 472         return false;
 473     } else {
 474         errno = save_errno;
 475         return true;
 476     }
 477 }
 478
 479 /* Returns the value of 'c' as a hexadecimal digit. */
 480 int
 481 hexit_value(int c)
 482 {
 483     switch (c) {
 484     case '0': case '1': case '2': case '3': case '4':
 485     case '5': case '6': case '7': case '8': case '9':
 486         return c - '0';
 487
 488     case 'a': case 'A':
 489         return 0xa;
 490
 491     case 'b': case 'B':
 492         return 0xb;
 493
 494     case 'c': case 'C':
 495         return 0xc;
 496
 497     case 'd': case 'D':
 498         return 0xd;
 499
 500     case 'e': case 'E':
 501         return 0xe;
 502
 503     case 'f': case 'F':
 504         return 0xf;
 505
 506     default:
 507         return -1;
 508     }
 509 }
 510
 511 /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or
 512  * UINT_MAX if one of those "digits" is not really a hex digit.  If 'ok' is
 513  * nonnull, '*ok' is set to true if the conversion succeeds or to false if a
 514  * non-hex digit is detected. */
 515 unsigned int
 516 hexits_value(const char *s, size_t n, bool *ok)
 517 {
 518     unsigned int value;
 519     size_t i;
 520
 521     value = 0;
 522     for (i = 0; i < n; i++) {
 523         int hexit = hexit_value(s[i]);
 524         if (hexit < 0) {
 525             if (ok) {
 526                 *ok = false;
 527             }
 528             return UINT_MAX;
 529         }
 530         value = (value << 4) + hexit;
 531     }
 532     if (ok) {
 533         *ok = true;
 534     }
 535     return value;
 536 }
 537
 538 /* Returns the current working directory as a malloc()'d string, or a null
 539  * pointer if the current working directory cannot be determined. */
 540 char *
 541 get_cwd(void)
 542 {
 543     long int path_max;
 544     size_t size;
 545
 546     /* Get maximum path length or at least a reasonable estimate. */
 547     path_max = pathconf(".", _PC_PATH_MAX);
 548     size = (path_max < 0 ? 1024
 549             : path_max > 10240 ? 10240
 550             : path_max);
 551
 552     /* Get current working directory. */
 553     for (;;) {
 554         char *buf = xmalloc(size);
 555         if (getcwd(buf, size)) {
 556             return xrealloc(buf, strlen(buf) + 1);
 557         } else {
 558             int error = errno;
 559             free(buf);
 560             if (error != ERANGE) {
 561                 VLOG_WARN("getcwd failed (%s)", strerror(error));
 562                 return NULL;
 563             }
 564             size *= 2;
 565         }
 566     }
 567 }
 568
 569 static char *
 570 all_slashes_name(const char *s)
 571 {
 572     return xstrdup(s[0] == '/' && s[1] == '/' && s[2] != '/' ? "//"
 573                    : s[0] == '/' ? "/"
 574                    : ".");
 575 }
 576
 577 /* Returns the directory name portion of 'file_name' as a malloc()'d string,
 578  * similar to the POSIX dirname() function but thread-safe. */
 579 char *
 580 dir_name(const char *file_name)
 581 {
 582     size_t len = strlen(file_name);
 583     while (len > 0 && file_name[len - 1] == '/') {
 584         len--;
 585     }
 586     while (len > 0 && file_name[len - 1] != '/') {
 587         len--;
 588     }
 589     while (len > 0 && file_name[len - 1] == '/') {
 590         len--;
 591     }
 592     return len ? xmemdup0(file_name, len) : all_slashes_name(file_name);
 593 }
 594
 595 /* Returns the file name portion of 'file_name' as a malloc()'d string,
 596  * similar to the POSIX basename() function but thread-safe. */
 597 char *
 598 base_name(const char *file_name)
 599 {
 600     size_t end, start;
 601
 602     end = strlen(file_name);
 603     while (end > 0 && file_name[end - 1] == '/') {
 604         end--;
 605     }
 606
 607     if (!end) {
 608         return all_slashes_name(file_name);
 609     }
 610
 611     start = end;
 612     while (start > 0 && file_name[start - 1] != '/') {
 613         start--;
 614     }
 615
 616     return xmemdup0(file_name + start, end - start);
 617 }
 618
 619 /* If 'file_name' starts with '/', returns a copy of 'file_name'.  Otherwise,
 620  * returns an absolute path to 'file_name' considering it relative to 'dir',
 621  * which itself must be absolute.  'dir' may be null or the empty string, in
 622  * which case the current working directory is used.
 623  *
 624  * Returns a null pointer if 'dir' is null and getcwd() fails. */
 625 char *
 626 abs_file_name(const char *dir, const char *file_name)
 627 {
 628     if (file_name[0] == '/') {
 629         return xstrdup(file_name);
 630     } else if (dir && dir[0]) {
 631         char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/";
 632         return xasprintf("%s%s%s", dir, separator, file_name);
 633     } else {
 634         char *cwd = get_cwd();
 635         if (cwd) {
 636             char *abs_name = xasprintf("%s/%s", cwd, file_name);
 637             free(cwd);
 638             return abs_name;
 639         } else {
 640             return NULL;
 641         }
 642     }
 643 }
 644
 645
 646 /* Pass a value to this function if it is marked with
 647  * __attribute__((warn_unused_result)) and you genuinely want to ignore
 648  * its return value.  (Note that every scalar type can be implicitly
 649  * converted to bool.) */
 650 void ignore(bool x OVS_UNUSED) { }
 651
 652 /* Returns an appropriate delimiter for inserting just before the 0-based item
 653  * 'index' in a list that has 'total' items in it. */
 654 const char *
 655 english_list_delimiter(size_t index, size_t total)
 656 {
 657     return (index == 0 ? ""
 658             : index < total - 1 ? ", "
 659             : total > 2 ? ", and "
 660             : " and ");
 661 }
 662
 663 /* Given a 32 bit word 'n', calculates floor(log_2('n')).  This is equivalent
 664  * to finding the bit position of the most significant one bit in 'n'.  It is
 665  * an error to call this function with 'n' == 0. */
 666 int
 667 log_2_floor(uint32_t n)
 668 {
 669     assert(n);
 670
 671 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 672 #error "Someone screwed up the #includes."
 673 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
 674     return 31 - __builtin_clz(n);
 675 #else
 676     {
 677         int log = 0;
 678
 679 #define BIN_SEARCH_STEP(BITS)                   \
 680         if (n >= (1 << BITS)) {                 \
 681             log += BITS;                        \
 682             n >>= BITS;                         \
 683         }
 684         BIN_SEARCH_STEP(16);
 685         BIN_SEARCH_STEP(8);
 686         BIN_SEARCH_STEP(4);
 687         BIN_SEARCH_STEP(2);
 688         BIN_SEARCH_STEP(1);
 689 #undef BIN_SEARCH_STEP
 690         return log;
 691     }
 692 #endif
 693 }
 694
 695 /* Given a 32 bit word 'n', calculates ceil(log_2('n')).  It is an error to
 696  * call this function with 'n' == 0. */
 697 int
 698 log_2_ceil(uint32_t n)
 699 {
 700     return log_2_floor(n) + !IS_POW2(n);
 701 }
 702
 703 /* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
 704 int
 705 ctz(uint32_t n)
 706 {
 707     if (!n) {
 708         return 32;
 709     } else {
 710 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 711 #error "Someone screwed up the #includes."
 712 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
 713         return __builtin_ctz(n);
 714 #else
 715         unsigned int k;
 716         int count = 31;
 717
 718 #define CTZ_STEP(X)                             \
 719         k = n << (X);                           \
 720         if (k) {                                \
 721             count -= X;                         \
 722             n = k;                              \
 723         }
 724         CTZ_STEP(16);
 725         CTZ_STEP(8);
 726         CTZ_STEP(4);
 727         CTZ_STEP(2);
 728         CTZ_STEP(1);
 729 #undef CTZ_STEP
 730
 731         return count;
 732 #endif
 733     }
 734 }
 735
 736 /* Returns true if the 'n' bytes starting at 'p' are zeros. */
 737 bool
 738 is_all_zeros(const uint8_t *p, size_t n)
 739 {
 740     size_t i;
 741
 742     for (i = 0; i < n; i++) {
 743         if (p[i] != 0x00) {
 744             return false;
 745         }
 746     }
 747     return true;
 748 }
 749
 750 /* Returns true if the 'n' bytes starting at 'p' are 0xff. */
 751 bool
 752 is_all_ones(const uint8_t *p, size_t n)
 753 {
 754     size_t i;
 755
 756     for (i = 0; i < n; i++) {
 757         if (p[i] != 0xff) {
 758             return false;
 759         }
 760     }
 761     return true;
 762 }
 763
 764 /* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits'
 765  * starting from bit 'dst_ofs' in 'dst'.  'src' is 'src_len' bytes long and
 766  * 'dst' is 'dst_len' bytes long.
 767  *
 768  * If you consider all of 'src' to be a single unsigned integer in network byte
 769  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 770  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
 771  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
 772  * 2], and so on.  Similarly for 'dst'.
 773  *
 774  * Required invariants:
 775  *   src_ofs + n_bits <= src_len * 8
 776  *   dst_ofs + n_bits <= dst_len * 8
 777  *   'src' and 'dst' must not overlap.
 778  */
 779 void
 780 bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs,
 781              void *dst_, unsigned int dst_len, unsigned int dst_ofs,
 782              unsigned int n_bits)
 783 {
 784     const uint8_t *src = src_;
 785     uint8_t *dst = dst_;
 786
 787     src += src_len - (src_ofs / 8 + 1);
 788     src_ofs %= 8;
 789
 790     dst += dst_len - (dst_ofs / 8 + 1);
 791     dst_ofs %= 8;
 792
 793     if (src_ofs == 0 && dst_ofs == 0) {
 794         unsigned int n_bytes = n_bits / 8;
 795         if (n_bytes) {
 796             dst -= n_bytes - 1;
 797             src -= n_bytes - 1;
 798             memcpy(dst, src, n_bytes);
 799
 800             n_bits %= 8;
 801             src--;
 802             dst--;
 803         }
 804         if (n_bits) {
 805             uint8_t mask = (1 << n_bits) - 1;
 806             *dst = (*dst & ~mask) | (*src & mask);
 807         }
 808     } else {
 809         while (n_bits > 0) {
 810             unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs);
 811             unsigned int chunk = MIN(n_bits, max_copy);
 812             uint8_t mask = ((1 << chunk) - 1) << dst_ofs;
 813
 814             *dst &= ~mask;
 815             *dst |= ((*src >> src_ofs) << dst_ofs) & mask;
 816
 817             src_ofs += chunk;
 818             if (src_ofs == 8) {
 819                 src--;
 820                 src_ofs = 0;
 821             }
 822             dst_ofs += chunk;
 823             if (dst_ofs == 8) {
 824                 dst--;
 825                 dst_ofs = 0;
 826             }
 827             n_bits -= chunk;
 828         }
 829     }
 830 }
 831
 832 /* Zeros the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.  'dst' is
 833  * 'dst_len' bytes long.
 834  *
 835  * If you consider all of 'dst' to be a single unsigned integer in network byte
 836  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 837  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
 838  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
 839  * 2], and so on.
 840  *
 841  * Required invariant:
 842  *   dst_ofs + n_bits <= dst_len * 8
 843  */
 844 void
 845 bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
 846              unsigned int n_bits)
 847 {
 848     uint8_t *dst = dst_;
 849
 850     if (!n_bits) {
 851         return;
 852     }
 853
 854     dst += dst_len - (dst_ofs / 8 + 1);
 855     dst_ofs %= 8;
 856
 857     if (dst_ofs) {
 858         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
 859
 860         *dst &= ~(((1 << chunk) - 1) << dst_ofs);
 861
 862         n_bits -= chunk;
 863         if (!n_bits) {
 864             return;
 865         }
 866
 867         dst--;
 868     }
 869
 870     while (n_bits >= 8) {
 871         *dst-- = 0;
 872         n_bits -= 8;
 873     }
 874
 875     if (n_bits) {
 876         *dst &= ~((1 << n_bits) - 1);
 877     }
 878 }
 879
 880 /* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.
 881  * 'dst' is 'dst_len' bytes long.
 882  *
 883  * If you consider all of 'dst' to be a single unsigned integer in network byte
 884  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 885  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
 886  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
 887  * 2], and so on.
 888  *
 889  * Required invariant:
 890  *   dst_ofs + n_bits <= dst_len * 8
 891  */
 892 void
 893 bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
 894             unsigned int n_bits)
 895 {
 896     uint8_t *dst = dst_;
 897
 898     if (!n_bits) {
 899         return;
 900     }
 901
 902     dst += dst_len - (dst_ofs / 8 + 1);
 903     dst_ofs %= 8;
 904
 905     if (dst_ofs) {
 906         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
 907
 908         *dst |= ((1 << chunk) - 1) << dst_ofs;
 909
 910         n_bits -= chunk;
 911         if (!n_bits) {
 912             return;
 913         }
 914
 915         dst--;
 916     }
 917
 918     while (n_bits >= 8) {
 919         *dst-- = 0xff;
 920         n_bits -= 8;
 921     }
 922
 923     if (n_bits) {
 924         *dst |= (1 << n_bits) - 1;
 925     }
 926 }
 927
 928 /* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits.
 929  * Returns false if any 1-bits are found, otherwise true.  'dst' is 'dst_len'
 930  * bytes long.
 931  *
 932  * If you consider all of 'dst' to be a single unsigned integer in network byte
 933  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 934  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
 935  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
 936  * 2], and so on.
 937  *
 938  * Required invariant:
 939  *   dst_ofs + n_bits <= dst_len * 8
 940  */
 941 bool
 942 bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
 943                      unsigned int n_bits)
 944 {
 945     const uint8_t *p = p_;
 946
 947     if (!n_bits) {
 948         return true;
 949     }
 950
 951     p += len - (ofs / 8 + 1);
 952     ofs %= 8;
 953
 954     if (ofs) {
 955         unsigned int chunk = MIN(n_bits, 8 - ofs);
 956
 957         if (*p & (((1 << chunk) - 1) << ofs)) {
 958             return false;
 959         }
 960
 961         n_bits -= chunk;
 962         if (!n_bits) {
 963             return true;
 964         }
 965
 966         p--;
 967     }
 968
 969     while (n_bits >= 8) {
 970         if (*p) {
 971             return false;
 972         }
 973         n_bits -= 8;
 974         p--;
 975     }
 976
 977     if (n_bits && *p & ((1 << n_bits) - 1)) {
 978         return false;
 979     }
 980
 981     return true;
 982 }
 983
 984 /* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
 985  * starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long.
 986  *
 987  * If you consider all of 'dst' to be a single unsigned integer in network byte
 988  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 989  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
 990  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
 991  * 2], and so on.
 992  *
 993  * Required invariants:
 994  *   dst_ofs + n_bits <= dst_len * 8
 995  *   n_bits <= 64
 996  */
 997 void
 998 bitwise_put(uint64_t value,
 999             void *dst, unsigned int dst_len, unsigned int dst_ofs,
1000             unsigned int n_bits)
1001 {
1002     ovs_be64 n_value = htonll(value);
1003     bitwise_copy(&n_value, sizeof n_value, 0,
1004                  dst, dst_len, dst_ofs,
1005                  n_bits);
1006 }
1007
1008 /* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src',
1009  * which is 'src_len' bytes long.
1010  *
1011  * If you consider all of 'src' to be a single unsigned integer in network byte
1012  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1013  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
1014  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
1015  * 2], and so on.
1016  *
1017  * Required invariants:
1018  *   src_ofs + n_bits <= src_len * 8
1019  *   n_bits <= 64
1020  */
1021 uint64_t
1022 bitwise_get(const void *src, unsigned int src_len,
1023             unsigned int src_ofs, unsigned int n_bits)
1024 {
1025     ovs_be64 value = htonll(0);
1026
1027     bitwise_copy(src, src_len, src_ofs,
1028                  &value, sizeof value, 0,
1029                  n_bits);
1030     return ntohll(value);
1031 }