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