lib/util.c

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