debian: Synchronize debian/changelog with downstream Debian changelog.
[openvswitch] / 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 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  * 'version' should contain the version of the caller's program.  If 'version'
288  * is the same as the VERSION #define, the caller is assumed to be part of Open
289  * vSwitch.  Otherwise, it is assumed to be an external program linking against
290  * the Open vSwitch libraries.
291  *
292  * The 'date' and 'time' arguments should likely be called with
293  * "__DATE__" and "__TIME__" to use the time the binary was built.
294  * Alternatively, the "set_program_name" macro may be called to do this
295  * automatically.
296  */
297 void
298 set_program_name__(const char *argv0, const char *version, const char *date,
299                    const char *time)
300 {
301     const char *slash = strrchr(argv0, '/');
302     program_name = slash ? slash + 1 : argv0;
303
304     free(program_version);
305
306     if (!strcmp(version, VERSION)) {
307         program_version = xasprintf("%s (Open vSwitch) "VERSION"\n"
308                                     "Compiled %s %s\n",
309                                     program_name, date, time);
310     } else {
311         program_version = xasprintf("%s %s\n"
312                                     "Open vSwitch Library "VERSION"\n"
313                                     "Compiled %s %s\n",
314                                     program_name, version, date, time);
315     }
316 }
317
318 /* Returns a pointer to a string describing the program version.  The
319  * caller must not modify or free the returned string.
320  */
321 const char *
322 get_program_version(void)
323 {
324     return program_version;
325 }
326
327 /* Print the version information for the program.  */
328 void
329 ovs_print_version(uint8_t min_ofp, uint8_t max_ofp)
330 {
331     printf("%s", program_version);
332     if (min_ofp || max_ofp) {
333         printf("OpenFlow versions %#x:%#x\n", min_ofp, max_ofp);
334     }
335 }
336
337 /* Writes the 'size' bytes in 'buf' to 'stream' as hex bytes arranged 16 per
338  * line.  Numeric offsets are also included, starting at 'ofs' for the first
339  * byte in 'buf'.  If 'ascii' is true then the corresponding ASCII characters
340  * are also rendered alongside. */
341 void
342 ovs_hex_dump(FILE *stream, const void *buf_, size_t size,
343              uintptr_t ofs, bool ascii)
344 {
345   const uint8_t *buf = buf_;
346   const size_t per_line = 16; /* Maximum bytes per line. */
347
348   while (size > 0)
349     {
350       size_t start, end, n;
351       size_t i;
352
353       /* Number of bytes on this line. */
354       start = ofs % per_line;
355       end = per_line;
356       if (end - start > size)
357         end = start + size;
358       n = end - start;
359
360       /* Print line. */
361       fprintf(stream, "%08jx  ", (uintmax_t) ROUND_DOWN(ofs, per_line));
362       for (i = 0; i < start; i++)
363         fprintf(stream, "   ");
364       for (; i < end; i++)
365         fprintf(stream, "%02hhx%c",
366                 buf[i - start], i == per_line / 2 - 1? '-' : ' ');
367       if (ascii)
368         {
369           for (; i < per_line; i++)
370             fprintf(stream, "   ");
371           fprintf(stream, "|");
372           for (i = 0; i < start; i++)
373             fprintf(stream, " ");
374           for (; i < end; i++) {
375               int c = buf[i - start];
376               putc(c >= 32 && c < 127 ? c : '.', stream);
377           }
378           for (; i < per_line; i++)
379             fprintf(stream, " ");
380           fprintf(stream, "|");
381         }
382       fprintf(stream, "\n");
383
384       ofs += n;
385       buf += n;
386       size -= n;
387     }
388 }
389
390 bool
391 str_to_int(const char *s, int base, int *i)
392 {
393     long long ll;
394     bool ok = str_to_llong(s, base, &ll);
395     *i = ll;
396     return ok;
397 }
398
399 bool
400 str_to_long(const char *s, int base, long *li)
401 {
402     long long ll;
403     bool ok = str_to_llong(s, base, &ll);
404     *li = ll;
405     return ok;
406 }
407
408 bool
409 str_to_llong(const char *s, int base, long long *x)
410 {
411     int save_errno = errno;
412     char *tail;
413     errno = 0;
414     *x = strtoll(s, &tail, base);
415     if (errno == EINVAL || errno == ERANGE || tail == s || *tail != '\0') {
416         errno = save_errno;
417         *x = 0;
418         return false;
419     } else {
420         errno = save_errno;
421         return true;
422     }
423 }
424
425 bool
426 str_to_uint(const char *s, int base, unsigned int *u)
427 {
428     return str_to_int(s, base, (int *) u);
429 }
430
431 bool
432 str_to_ulong(const char *s, int base, unsigned long *ul)
433 {
434     return str_to_long(s, base, (long *) ul);
435 }
436
437 bool
438 str_to_ullong(const char *s, int base, unsigned long long *ull)
439 {
440     return str_to_llong(s, base, (long long *) ull);
441 }
442
443 /* Converts floating-point string 's' into a double.  If successful, stores
444  * the double in '*d' and returns true; on failure, stores 0 in '*d' and
445  * returns false.
446  *
447  * Underflow (e.g. "1e-9999") is not considered an error, but overflow
448  * (e.g. "1e9999)" is. */
449 bool
450 str_to_double(const char *s, double *d)
451 {
452     int save_errno = errno;
453     char *tail;
454     errno = 0;
455     *d = strtod(s, &tail);
456     if (errno == EINVAL || (errno == ERANGE && *d != 0)
457         || tail == s || *tail != '\0') {
458         errno = save_errno;
459         *d = 0;
460         return false;
461     } else {
462         errno = save_errno;
463         return true;
464     }
465 }
466
467 /* Returns the value of 'c' as a hexadecimal digit. */
468 int
469 hexit_value(int c)
470 {
471     switch (c) {
472     case '0': case '1': case '2': case '3': case '4':
473     case '5': case '6': case '7': case '8': case '9':
474         return c - '0';
475
476     case 'a': case 'A':
477         return 0xa;
478
479     case 'b': case 'B':
480         return 0xb;
481
482     case 'c': case 'C':
483         return 0xc;
484
485     case 'd': case 'D':
486         return 0xd;
487
488     case 'e': case 'E':
489         return 0xe;
490
491     case 'f': case 'F':
492         return 0xf;
493
494     default:
495         return -1;
496     }
497 }
498
499 /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or
500  * UINT_MAX if one of those "digits" is not really a hex digit.  If 'ok' is
501  * nonnull, '*ok' is set to true if the conversion succeeds or to false if a
502  * non-hex digit is detected. */
503 unsigned int
504 hexits_value(const char *s, size_t n, bool *ok)
505 {
506     unsigned int value;
507     size_t i;
508
509     value = 0;
510     for (i = 0; i < n; i++) {
511         int hexit = hexit_value(s[i]);
512         if (hexit < 0) {
513             if (ok) {
514                 *ok = false;
515             }
516             return UINT_MAX;
517         }
518         value = (value << 4) + hexit;
519     }
520     if (ok) {
521         *ok = true;
522     }
523     return value;
524 }
525
526 /* Returns the current working directory as a malloc()'d string, or a null
527  * pointer if the current working directory cannot be determined. */
528 char *
529 get_cwd(void)
530 {
531     long int path_max;
532     size_t size;
533
534     /* Get maximum path length or at least a reasonable estimate. */
535     path_max = pathconf(".", _PC_PATH_MAX);
536     size = (path_max < 0 ? 1024
537             : path_max > 10240 ? 10240
538             : path_max);
539
540     /* Get current working directory. */
541     for (;;) {
542         char *buf = xmalloc(size);
543         if (getcwd(buf, size)) {
544             return xrealloc(buf, strlen(buf) + 1);
545         } else {
546             int error = errno;
547             free(buf);
548             if (error != ERANGE) {
549                 VLOG_WARN("getcwd failed (%s)", strerror(error));
550                 return NULL;
551             }
552             size *= 2;
553         }
554     }
555 }
556
557 static char *
558 all_slashes_name(const char *s)
559 {
560     return xstrdup(s[0] == '/' && s[1] == '/' && s[2] != '/' ? "//"
561                    : s[0] == '/' ? "/"
562                    : ".");
563 }
564
565 /* Returns the directory name portion of 'file_name' as a malloc()'d string,
566  * similar to the POSIX dirname() function but thread-safe. */
567 char *
568 dir_name(const char *file_name)
569 {
570     size_t len = strlen(file_name);
571     while (len > 0 && file_name[len - 1] == '/') {
572         len--;
573     }
574     while (len > 0 && file_name[len - 1] != '/') {
575         len--;
576     }
577     while (len > 0 && file_name[len - 1] == '/') {
578         len--;
579     }
580     return len ? xmemdup0(file_name, len) : all_slashes_name(file_name);
581 }
582
583 /* Returns the file name portion of 'file_name' as a malloc()'d string,
584  * similar to the POSIX basename() function but thread-safe. */
585 char *
586 base_name(const char *file_name)
587 {
588     size_t end, start;
589
590     end = strlen(file_name);
591     while (end > 0 && file_name[end - 1] == '/') {
592         end--;
593     }
594
595     if (!end) {
596         return all_slashes_name(file_name);
597     }
598
599     start = end;
600     while (start > 0 && file_name[start - 1] != '/') {
601         start--;
602     }
603
604     return xmemdup0(file_name + start, end - start);
605 }
606
607 /* If 'file_name' starts with '/', returns a copy of 'file_name'.  Otherwise,
608  * returns an absolute path to 'file_name' considering it relative to 'dir',
609  * which itself must be absolute.  'dir' may be null or the empty string, in
610  * which case the current working directory is used.
611  *
612  * Returns a null pointer if 'dir' is null and getcwd() fails. */
613 char *
614 abs_file_name(const char *dir, const char *file_name)
615 {
616     if (file_name[0] == '/') {
617         return xstrdup(file_name);
618     } else if (dir && dir[0]) {
619         char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/";
620         return xasprintf("%s%s%s", dir, separator, file_name);
621     } else {
622         char *cwd = get_cwd();
623         if (cwd) {
624             char *abs_name = xasprintf("%s/%s", cwd, file_name);
625             free(cwd);
626             return abs_name;
627         } else {
628             return NULL;
629         }
630     }
631 }
632
633
634 /* Pass a value to this function if it is marked with
635  * __attribute__((warn_unused_result)) and you genuinely want to ignore
636  * its return value.  (Note that every scalar type can be implicitly
637  * converted to bool.) */
638 void ignore(bool x OVS_UNUSED) { }
639
640 /* Returns an appropriate delimiter for inserting just before the 0-based item
641  * 'index' in a list that has 'total' items in it. */
642 const char *
643 english_list_delimiter(size_t index, size_t total)
644 {
645     return (index == 0 ? ""
646             : index < total - 1 ? ", "
647             : total > 2 ? ", and "
648             : " and ");
649 }
650
651 /* Given a 32 bit word 'n', calculates floor(log_2('n')).  This is equivalent
652  * to finding the bit position of the most significant one bit in 'n'.  It is
653  * an error to call this function with 'n' == 0. */
654 int
655 log_2_floor(uint32_t n)
656 {
657     assert(n);
658
659 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
660 #error "Someone screwed up the #includes."
661 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
662     return 31 - __builtin_clz(n);
663 #else
664     {
665         int log = 0;
666
667 #define BIN_SEARCH_STEP(BITS)                   \
668         if (n >= (1 << BITS)) {                 \
669             log += BITS;                        \
670             n >>= BITS;                         \
671         }
672         BIN_SEARCH_STEP(16);
673         BIN_SEARCH_STEP(8);
674         BIN_SEARCH_STEP(4);
675         BIN_SEARCH_STEP(2);
676         BIN_SEARCH_STEP(1);
677 #undef BIN_SEARCH_STEP
678         return log;
679     }
680 #endif
681 }
682
683 /* Given a 32 bit word 'n', calculates ceil(log_2('n')).  It is an error to
684  * call this function with 'n' == 0. */
685 int
686 log_2_ceil(uint32_t n)
687 {
688     return log_2_floor(n) + !IS_POW2(n);
689 }
690
691 /* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
692 int
693 ctz(uint32_t n)
694 {
695     if (!n) {
696         return 32;
697     } else {
698 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
699 #error "Someone screwed up the #includes."
700 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
701         return __builtin_ctz(n);
702 #else
703         unsigned int k;
704         int count = 31;
705
706 #define CTZ_STEP(X)                             \
707         k = n << (X);                           \
708         if (k) {                                \
709             count -= X;                         \
710             n = k;                              \
711         }
712         CTZ_STEP(16);
713         CTZ_STEP(8);
714         CTZ_STEP(4);
715         CTZ_STEP(2);
716         CTZ_STEP(1);
717 #undef CTZ_STEP
718
719         return count;
720 #endif
721     }
722 }
723
724 /* Returns true if the 'n' bytes starting at 'p' are zeros. */
725 bool
726 is_all_zeros(const uint8_t *p, size_t n)
727 {
728     size_t i;
729
730     for (i = 0; i < n; i++) {
731         if (p[i] != 0x00) {
732             return false;
733         }
734     }
735     return true;
736 }
737
738 /* Returns true if the 'n' bytes starting at 'p' are 0xff. */
739 bool
740 is_all_ones(const uint8_t *p, size_t n)
741 {
742     size_t i;
743
744     for (i = 0; i < n; i++) {
745         if (p[i] != 0xff) {
746             return false;
747         }
748     }
749     return true;
750 }
751
752 /* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits'
753  * starting from bit 'dst_ofs' in 'dst'.  'src' is 'src_len' bytes long and
754  * 'dst' is 'dst_len' bytes long.
755  *
756  * If you consider all of 'src' to be a single unsigned integer in network byte
757  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
758  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
759  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
760  * 2], and so on.  Similarly for 'dst'.
761  *
762  * Required invariants:
763  *   src_ofs + n_bits <= src_len * 8
764  *   dst_ofs + n_bits <= dst_len * 8
765  *   'src' and 'dst' must not overlap.
766  */
767 void
768 bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs,
769              void *dst_, unsigned int dst_len, unsigned int dst_ofs,
770              unsigned int n_bits)
771 {
772     const uint8_t *src = src_;
773     uint8_t *dst = dst_;
774
775     src += src_len - (src_ofs / 8 + 1);
776     src_ofs %= 8;
777
778     dst += dst_len - (dst_ofs / 8 + 1);
779     dst_ofs %= 8;
780
781     if (src_ofs == 0 && dst_ofs == 0) {
782         unsigned int n_bytes = n_bits / 8;
783         if (n_bytes) {
784             dst -= n_bytes - 1;
785             src -= n_bytes - 1;
786             memcpy(dst, src, n_bytes);
787
788             n_bits %= 8;
789             src--;
790             dst--;
791         }
792         if (n_bits) {
793             uint8_t mask = (1 << n_bits) - 1;
794             *dst = (*dst & ~mask) | (*src & mask);
795         }
796     } else {
797         while (n_bits > 0) {
798             unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs);
799             unsigned int chunk = MIN(n_bits, max_copy);
800             uint8_t mask = ((1 << chunk) - 1) << dst_ofs;
801
802             *dst &= ~mask;
803             *dst |= ((*src >> src_ofs) << dst_ofs) & mask;
804
805             src_ofs += chunk;
806             if (src_ofs == 8) {
807                 src--;
808                 src_ofs = 0;
809             }
810             dst_ofs += chunk;
811             if (dst_ofs == 8) {
812                 dst--;
813                 dst_ofs = 0;
814             }
815             n_bits -= chunk;
816         }
817     }
818 }
819
820 /* Zeros the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.  'dst' is
821  * 'dst_len' bytes long.
822  *
823  * If you consider all of 'dst' to be a single unsigned integer in network byte
824  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
825  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
826  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
827  * 2], and so on.
828  *
829  * Required invariant:
830  *   dst_ofs + n_bits <= dst_len * 8
831  */
832 void
833 bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
834              unsigned int n_bits)
835 {
836     uint8_t *dst = dst_;
837
838     if (!n_bits) {
839         return;
840     }
841
842     dst += dst_len - (dst_ofs / 8 + 1);
843     dst_ofs %= 8;
844
845     if (dst_ofs) {
846         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
847
848         *dst &= ~(((1 << chunk) - 1) << dst_ofs);
849
850         n_bits -= chunk;
851         if (!n_bits) {
852             return;
853         }
854
855         dst--;
856     }
857
858     while (n_bits >= 8) {
859         *dst-- = 0;
860         n_bits -= 8;
861     }
862
863     if (n_bits) {
864         *dst &= ~((1 << n_bits) - 1);
865     }
866 }
867
868 /* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.
869  * 'dst' is 'dst_len' bytes long.
870  *
871  * If you consider all of 'dst' to be a single unsigned integer in network byte
872  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
873  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
874  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
875  * 2], and so on.
876  *
877  * Required invariant:
878  *   dst_ofs + n_bits <= dst_len * 8
879  */
880 void
881 bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
882             unsigned int n_bits)
883 {
884     uint8_t *dst = dst_;
885
886     if (!n_bits) {
887         return;
888     }
889
890     dst += dst_len - (dst_ofs / 8 + 1);
891     dst_ofs %= 8;
892
893     if (dst_ofs) {
894         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
895
896         *dst |= ((1 << chunk) - 1) << dst_ofs;
897
898         n_bits -= chunk;
899         if (!n_bits) {
900             return;
901         }
902
903         dst--;
904     }
905
906     while (n_bits >= 8) {
907         *dst-- = 0xff;
908         n_bits -= 8;
909     }
910
911     if (n_bits) {
912         *dst |= (1 << n_bits) - 1;
913     }
914 }
915
916 /* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits.
917  * Returns false if any 1-bits are found, otherwise true.  'dst' is 'dst_len'
918  * bytes long.
919  *
920  * If you consider all of 'dst' to be a single unsigned integer in network byte
921  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
922  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
923  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
924  * 2], and so on.
925  *
926  * Required invariant:
927  *   dst_ofs + n_bits <= dst_len * 8
928  */
929 bool
930 bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
931                      unsigned int n_bits)
932 {
933     const uint8_t *p = p_;
934
935     if (!n_bits) {
936         return true;
937     }
938
939     p += len - (ofs / 8 + 1);
940     ofs %= 8;
941
942     if (ofs) {
943         unsigned int chunk = MIN(n_bits, 8 - ofs);
944
945         if (*p & (((1 << chunk) - 1) << ofs)) {
946             return false;
947         }
948
949         n_bits -= chunk;
950         if (!n_bits) {
951             return true;
952         }
953
954         p--;
955     }
956
957     while (n_bits >= 8) {
958         if (*p) {
959             return false;
960         }
961         n_bits -= 8;
962         p--;
963     }
964
965     if (n_bits && *p & ((1 << n_bits) - 1)) {
966         return false;
967     }
968
969     return true;
970 }
971
972 /* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
973  * starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long.
974  *
975  * If you consider all of 'dst' to be a single unsigned integer in network byte
976  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
977  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
978  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
979  * 2], and so on.
980  *
981  * Required invariants:
982  *   dst_ofs + n_bits <= dst_len * 8
983  *   n_bits <= 64
984  */
985 void
986 bitwise_put(uint64_t value,
987             void *dst, unsigned int dst_len, unsigned int dst_ofs,
988             unsigned int n_bits)
989 {
990     ovs_be64 n_value = htonll(value);
991     bitwise_copy(&n_value, sizeof n_value, 0,
992                  dst, dst_len, dst_ofs,
993                  n_bits);
994 }
995
996 /* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src',
997  * which is 'src_len' bytes long.
998  *
999  * If you consider all of 'src' to be a single unsigned integer in network byte
1000  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1001  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
1002  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
1003  * 2], and so on.
1004  *
1005  * Required invariants:
1006  *   src_ofs + n_bits <= src_len * 8
1007  *   n_bits <= 64
1008  */
1009 uint64_t
1010 bitwise_get(const void *src, unsigned int src_len,
1011             unsigned int src_ofs, unsigned int n_bits)
1012 {
1013     ovs_be64 value = htonll(0);
1014
1015     bitwise_copy(src, src_len, src_ofs,
1016                  &value, sizeof value, 0,
1017                  n_bits);
1018     return ntohll(value);
1019 }