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