+
+/* Returns an appropriate delimiter for inserting just before the 0-based item
+ * 'index' in a list that has 'total' items in it. */
+const char *
+english_list_delimiter(size_t index, size_t total)
+{
+ return (index == 0 ? ""
+ : index < total - 1 ? ", "
+ : total > 2 ? ", and "
+ : " and ");
+}
+
+/* Returns the number of trailing 0-bits in 'n'. Undefined if 'n' == 0. */
+#if __GNUC__ >= 4
+/* Defined inline in util.h. */
+#else
+/* Returns the number of trailing 0-bits in 'n'. Undefined if 'n' == 0. */
+int
+raw_ctz(uint64_t n)
+{
+ uint64_t k;
+ int count = 63;
+
+#define CTZ_STEP(X) \
+ k = n << (X); \
+ if (k) { \
+ count -= X; \
+ n = k; \
+ }
+ CTZ_STEP(32);
+ CTZ_STEP(16);
+ CTZ_STEP(8);
+ CTZ_STEP(4);
+ CTZ_STEP(2);
+ CTZ_STEP(1);
+#undef CTZ_STEP
+
+ return count;
+}
+
+/* Returns the number of leading 0-bits in 'n'. Undefined if 'n' == 0. */
+int
+raw_clz64(uint64_t n)
+{
+ uint64_t k;
+ int count = 63;
+
+#define CLZ_STEP(X) \
+ k = n >> (X); \
+ if (k) { \
+ count -= X; \
+ n = k; \
+ }
+ CLZ_STEP(32);
+ CLZ_STEP(16);
+ CLZ_STEP(8);
+ CLZ_STEP(4);
+ CLZ_STEP(2);
+ CLZ_STEP(1);
+#undef CLZ_STEP
+
+ return count;
+}
+#endif
+
+#if NEED_COUNT_1BITS_8
+#define INIT1(X) \
+ ((((X) & (1 << 0)) != 0) + \
+ (((X) & (1 << 1)) != 0) + \
+ (((X) & (1 << 2)) != 0) + \
+ (((X) & (1 << 3)) != 0) + \
+ (((X) & (1 << 4)) != 0) + \
+ (((X) & (1 << 5)) != 0) + \
+ (((X) & (1 << 6)) != 0) + \
+ (((X) & (1 << 7)) != 0))
+#define INIT2(X) INIT1(X), INIT1((X) + 1)
+#define INIT4(X) INIT2(X), INIT2((X) + 2)
+#define INIT8(X) INIT4(X), INIT4((X) + 4)
+#define INIT16(X) INIT8(X), INIT8((X) + 8)
+#define INIT32(X) INIT16(X), INIT16((X) + 16)
+#define INIT64(X) INIT32(X), INIT32((X) + 32)
+
+const uint8_t count_1bits_8[256] = {
+ INIT64(0), INIT64(64), INIT64(128), INIT64(192)
+};
+#endif
+
+/* Returns true if the 'n' bytes starting at 'p' are zeros. */
+bool
+is_all_zeros(const uint8_t *p, size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < n; i++) {
+ if (p[i] != 0x00) {
+ return false;
+ }
+ }
+ return true;
+}
+
+/* Returns true if the 'n' bytes starting at 'p' are 0xff. */
+bool
+is_all_ones(const uint8_t *p, size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < n; i++) {
+ if (p[i] != 0xff) {
+ return false;
+ }
+ }
+ return true;
+}
+
+/* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits'
+ * starting from bit 'dst_ofs' in 'dst'. 'src' is 'src_len' bytes long and
+ * 'dst' is 'dst_len' bytes long.
+ *
+ * If you consider all of 'src' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
+ * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
+ * 2], and so on. Similarly for 'dst'.
+ *
+ * Required invariants:
+ * src_ofs + n_bits <= src_len * 8
+ * dst_ofs + n_bits <= dst_len * 8
+ * 'src' and 'dst' must not overlap.
+ */
+void
+bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs,
+ void *dst_, unsigned int dst_len, unsigned int dst_ofs,
+ unsigned int n_bits)
+{
+ const uint8_t *src = src_;
+ uint8_t *dst = dst_;
+
+ src += src_len - (src_ofs / 8 + 1);
+ src_ofs %= 8;
+
+ dst += dst_len - (dst_ofs / 8 + 1);
+ dst_ofs %= 8;
+
+ if (src_ofs == 0 && dst_ofs == 0) {
+ unsigned int n_bytes = n_bits / 8;
+ if (n_bytes) {
+ dst -= n_bytes - 1;
+ src -= n_bytes - 1;
+ memcpy(dst, src, n_bytes);
+
+ n_bits %= 8;
+ src--;
+ dst--;
+ }
+ if (n_bits) {
+ uint8_t mask = (1 << n_bits) - 1;
+ *dst = (*dst & ~mask) | (*src & mask);
+ }
+ } else {
+ while (n_bits > 0) {
+ unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs);
+ unsigned int chunk = MIN(n_bits, max_copy);
+ uint8_t mask = ((1 << chunk) - 1) << dst_ofs;
+
+ *dst &= ~mask;
+ *dst |= ((*src >> src_ofs) << dst_ofs) & mask;
+
+ src_ofs += chunk;
+ if (src_ofs == 8) {
+ src--;
+ src_ofs = 0;
+ }
+ dst_ofs += chunk;
+ if (dst_ofs == 8) {
+ dst--;
+ dst_ofs = 0;
+ }
+ n_bits -= chunk;
+ }
+ }
+}
+
+/* Zeros the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'. 'dst' is
+ * 'dst_len' bytes long.
+ *
+ * If you consider all of 'dst' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
+ * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
+ * 2], and so on.
+ *
+ * Required invariant:
+ * dst_ofs + n_bits <= dst_len * 8
+ */
+void
+bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
+ unsigned int n_bits)
+{
+ uint8_t *dst = dst_;
+
+ if (!n_bits) {
+ return;
+ }
+
+ dst += dst_len - (dst_ofs / 8 + 1);
+ dst_ofs %= 8;
+
+ if (dst_ofs) {
+ unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
+
+ *dst &= ~(((1 << chunk) - 1) << dst_ofs);
+
+ n_bits -= chunk;
+ if (!n_bits) {
+ return;
+ }
+
+ dst--;
+ }
+
+ while (n_bits >= 8) {
+ *dst-- = 0;
+ n_bits -= 8;
+ }
+
+ if (n_bits) {
+ *dst &= ~((1 << n_bits) - 1);
+ }
+}
+
+/* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.
+ * 'dst' is 'dst_len' bytes long.
+ *
+ * If you consider all of 'dst' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
+ * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
+ * 2], and so on.
+ *
+ * Required invariant:
+ * dst_ofs + n_bits <= dst_len * 8
+ */
+void
+bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
+ unsigned int n_bits)
+{
+ uint8_t *dst = dst_;
+
+ if (!n_bits) {
+ return;
+ }
+
+ dst += dst_len - (dst_ofs / 8 + 1);
+ dst_ofs %= 8;
+
+ if (dst_ofs) {
+ unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
+
+ *dst |= ((1 << chunk) - 1) << dst_ofs;
+
+ n_bits -= chunk;
+ if (!n_bits) {
+ return;
+ }
+
+ dst--;
+ }
+
+ while (n_bits >= 8) {
+ *dst-- = 0xff;
+ n_bits -= 8;
+ }
+
+ if (n_bits) {
+ *dst |= (1 << n_bits) - 1;
+ }
+}
+
+/* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits.
+ * Returns false if any 1-bits are found, otherwise true. 'dst' is 'dst_len'
+ * bytes long.
+ *
+ * If you consider all of 'dst' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
+ * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
+ * 2], and so on.
+ *
+ * Required invariant:
+ * dst_ofs + n_bits <= dst_len * 8
+ */
+bool
+bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
+ unsigned int n_bits)
+{
+ const uint8_t *p = p_;
+
+ if (!n_bits) {
+ return true;
+ }
+
+ p += len - (ofs / 8 + 1);
+ ofs %= 8;
+
+ if (ofs) {
+ unsigned int chunk = MIN(n_bits, 8 - ofs);
+
+ if (*p & (((1 << chunk) - 1) << ofs)) {
+ return false;
+ }
+
+ n_bits -= chunk;
+ if (!n_bits) {
+ return true;
+ }
+
+ p--;
+ }
+
+ while (n_bits >= 8) {
+ if (*p) {
+ return false;
+ }
+ n_bits -= 8;
+ p--;
+ }
+
+ if (n_bits && *p & ((1 << n_bits) - 1)) {
+ return false;
+ }
+
+ return true;
+}
+
+/* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
+ * starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long.
+ *
+ * If you consider all of 'dst' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
+ * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
+ * 2], and so on.
+ *
+ * Required invariants:
+ * dst_ofs + n_bits <= dst_len * 8
+ * n_bits <= 64
+ */
+void
+bitwise_put(uint64_t value,
+ void *dst, unsigned int dst_len, unsigned int dst_ofs,
+ unsigned int n_bits)
+{
+ ovs_be64 n_value = htonll(value);
+ bitwise_copy(&n_value, sizeof n_value, 0,
+ dst, dst_len, dst_ofs,
+ n_bits);
+}
+
+/* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src',
+ * which is 'src_len' bytes long.
+ *
+ * If you consider all of 'src' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
+ * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
+ * 2], and so on.
+ *
+ * Required invariants:
+ * src_ofs + n_bits <= src_len * 8
+ * n_bits <= 64
+ */
+uint64_t
+bitwise_get(const void *src, unsigned int src_len,
+ unsigned int src_ofs, unsigned int n_bits)
+{
+ ovs_be64 value = htonll(0);
+
+ bitwise_copy(src, src_len, src_ofs,
+ &value, sizeof value, 0,
+ n_bits);
+ return ntohll(value);
+}
+\f
+/* ovs_scan */
+
+struct scan_spec {
+ unsigned int width;
+ enum {
+ SCAN_DISCARD,
+ SCAN_CHAR,
+ SCAN_SHORT,
+ SCAN_INT,
+ SCAN_LONG,
+ SCAN_LLONG,
+ SCAN_INTMAX_T,
+ SCAN_PTRDIFF_T,
+ SCAN_SIZE_T
+ } type;
+};
+
+static const char *
+skip_spaces(const char *s)
+{
+ while (isspace((unsigned char) *s)) {
+ s++;
+ }
+ return s;
+}
+
+static const char *
+scan_int(const char *s, const struct scan_spec *spec, int base, va_list *args)
+{
+ const char *start = s;
+ uintmax_t value;
+ bool negative;
+ int n_digits;
+
+ negative = *s == '-';
+ s += *s == '-' || *s == '+';
+
+ if ((!base || base == 16) && *s == '0' && (s[1] == 'x' || s[1] == 'X')) {
+ base = 16;
+ s += 2;
+ } else if (!base) {
+ base = *s == '0' ? 8 : 10;
+ }
+
+ if (s - start >= spec->width) {
+ return NULL;
+ }
+
+ value = 0;
+ n_digits = 0;
+ while (s - start < spec->width) {
+ int digit = hexit_value(*s);
+
+ if (digit < 0 || digit >= base) {
+ break;
+ }
+ value = value * base + digit;
+ n_digits++;
+ s++;
+ }
+ if (!n_digits) {
+ return NULL;
+ }
+
+ if (negative) {
+ value = -value;
+ }
+
+ switch (spec->type) {
+ case SCAN_DISCARD:
+ break;
+ case SCAN_CHAR:
+ *va_arg(*args, char *) = value;
+ break;
+ case SCAN_SHORT:
+ *va_arg(*args, short int *) = value;
+ break;
+ case SCAN_INT:
+ *va_arg(*args, int *) = value;
+ break;
+ case SCAN_LONG:
+ *va_arg(*args, long int *) = value;
+ break;
+ case SCAN_LLONG:
+ *va_arg(*args, long long int *) = value;
+ break;
+ case SCAN_INTMAX_T:
+ *va_arg(*args, intmax_t *) = value;
+ break;
+ case SCAN_PTRDIFF_T:
+ *va_arg(*args, ptrdiff_t *) = value;
+ break;
+ case SCAN_SIZE_T:
+ *va_arg(*args, size_t *) = value;
+ break;
+ }
+ return s;
+}
+
+static const char *
+skip_digits(const char *s)
+{
+ while (*s >= '0' && *s <= '9') {
+ s++;
+ }
+ return s;
+}
+
+static const char *
+scan_float(const char *s, const struct scan_spec *spec, va_list *args)
+{
+ const char *start = s;
+ long double value;
+ char *tail;
+ char *copy;
+ bool ok;
+
+ s += *s == '+' || *s == '-';
+ s = skip_digits(s);
+ if (*s == '.') {
+ s = skip_digits(s + 1);
+ }
+ if (*s == 'e' || *s == 'E') {
+ s++;
+ s += *s == '+' || *s == '-';
+ s = skip_digits(s);
+ }
+
+ if (s - start > spec->width) {
+ s = start + spec->width;
+ }
+
+ copy = xmemdup0(start, s - start);
+ value = strtold(copy, &tail);
+ ok = *tail == '\0';
+ free(copy);
+ if (!ok) {
+ return NULL;
+ }
+
+ switch (spec->type) {
+ case SCAN_DISCARD:
+ break;
+ case SCAN_INT:
+ *va_arg(*args, float *) = value;
+ break;
+ case SCAN_LONG:
+ *va_arg(*args, double *) = value;
+ break;
+ case SCAN_LLONG:
+ *va_arg(*args, long double *) = value;
+ break;
+
+ case SCAN_CHAR:
+ case SCAN_SHORT:
+ case SCAN_INTMAX_T:
+ case SCAN_PTRDIFF_T:
+ case SCAN_SIZE_T:
+ OVS_NOT_REACHED();
+ }
+ return s;
+}
+
+static void
+scan_output_string(const struct scan_spec *spec,
+ const char *s, size_t n,
+ va_list *args)
+{
+ if (spec->type != SCAN_DISCARD) {
+ char *out = va_arg(*args, char *);
+ memcpy(out, s, n);
+ out[n] = '\0';
+ }
+}
+
+static const char *
+scan_string(const char *s, const struct scan_spec *spec, va_list *args)
+{
+ size_t n;
+
+ for (n = 0; n < spec->width; n++) {
+ if (!s[n] || isspace((unsigned char) s[n])) {
+ break;
+ }
+ }
+ if (!n) {
+ return NULL;
+ }
+
+ scan_output_string(spec, s, n, args);
+ return s + n;
+}
+
+static const char *
+parse_scanset(const char *p_, unsigned long *set, bool *complemented)
+{
+ const uint8_t *p = (const uint8_t *) p_;
+
+ *complemented = *p == '^';
+ p += *complemented;
+
+ if (*p == ']') {
+ bitmap_set1(set, ']');
+ p++;
+ }
+
+ while (*p && *p != ']') {
+ if (p[1] == '-' && p[2] != ']' && p[2] > *p) {
+ bitmap_set_multiple(set, *p, p[2] - *p + 1, true);
+ p += 3;
+ } else {
+ bitmap_set1(set, *p++);
+ }
+ }
+ if (*p == ']') {
+ p++;
+ }
+ return (const char *) p;
+}
+
+static const char *
+scan_set(const char *s, const struct scan_spec *spec, const char **pp,
+ va_list *args)
+{
+ unsigned long set[BITMAP_N_LONGS(UCHAR_MAX + 1)];
+ bool complemented;
+ unsigned int n;
+
+ /* Parse the scan set. */
+ memset(set, 0, sizeof set);
+ *pp = parse_scanset(*pp, set, &complemented);
+
+ /* Parse the data. */
+ n = 0;
+ while (s[n]
+ && bitmap_is_set(set, (unsigned char) s[n]) == !complemented
+ && n < spec->width) {
+ n++;
+ }
+ if (!n) {
+ return NULL;
+ }
+ scan_output_string(spec, s, n, args);
+ return s + n;
+}
+
+static const char *
+scan_chars(const char *s, const struct scan_spec *spec, va_list *args)
+{
+ unsigned int n = spec->width == UINT_MAX ? 1 : spec->width;
+
+ if (strlen(s) < n) {
+ return NULL;
+ }
+ if (spec->type != SCAN_DISCARD) {
+ memcpy(va_arg(*args, char *), s, n);
+ }
+ return s + n;
+}
+
+/* This is an implementation of the standard sscanf() function, with the
+ * following exceptions:
+ *
+ * - It returns true if the entire format was successfully scanned and
+ * converted, false if any conversion failed.
+ *
+ * - The standard doesn't define sscanf() behavior when an out-of-range value
+ * is scanned, e.g. if a "%"PRIi8 conversion scans "-1" or "0x1ff". Some
+ * implementations consider this an error and stop scanning. This
+ * implementation never considers an out-of-range value an error; instead,
+ * it stores the least-significant bits of the converted value in the
+ * destination, e.g. the value 255 for both examples earlier.
+ *
+ * - Only single-byte characters are supported, that is, the 'l' modifier
+ * on %s, %[, and %c is not supported. The GNU extension 'a' modifier is
+ * also not supported.
+ *
+ * - %p is not supported.
+ */
+bool
+ovs_scan(const char *s, const char *format, ...)
+{
+ const char *const start = s;
+ bool ok = false;
+ const char *p;
+ va_list args;
+
+ va_start(args, format);
+ p = format;
+ while (*p != '\0') {
+ struct scan_spec spec;
+ unsigned char c = *p++;
+ bool discard;
+
+ if (isspace(c)) {
+ s = skip_spaces(s);
+ continue;
+ } else if (c != '%') {
+ if (*s != c) {
+ goto exit;
+ }
+ s++;
+ continue;
+ } else if (*p == '%') {
+ if (*s++ != '%') {
+ goto exit;
+ }
+ p++;
+ continue;
+ }
+
+ /* Parse '*' flag. */
+ discard = *p == '*';
+ p += discard;
+
+ /* Parse field width. */
+ spec.width = 0;
+ while (*p >= '0' && *p <= '9') {
+ spec.width = spec.width * 10 + (*p++ - '0');
+ }
+ if (spec.width == 0) {
+ spec.width = UINT_MAX;
+ }
+
+ /* Parse type modifier. */
+ switch (*p) {
+ case 'h':
+ if (p[1] == 'h') {
+ spec.type = SCAN_CHAR;
+ p += 2;
+ } else {
+ spec.type = SCAN_SHORT;
+ p++;
+ }
+ break;
+
+ case 'j':
+ spec.type = SCAN_INTMAX_T;
+ p++;
+ break;
+
+ case 'l':
+ if (p[1] == 'l') {
+ spec.type = SCAN_LLONG;
+ p += 2;
+ } else {
+ spec.type = SCAN_LONG;
+ p++;
+ }
+ break;
+
+ case 'L':
+ case 'q':
+ spec.type = SCAN_LLONG;
+ p++;
+ break;
+
+ case 't':
+ spec.type = SCAN_PTRDIFF_T;
+ p++;
+ break;
+
+ case 'z':
+ spec.type = SCAN_SIZE_T;
+ p++;
+ break;
+
+ default:
+ spec.type = SCAN_INT;
+ break;
+ }
+
+ if (discard) {
+ spec.type = SCAN_DISCARD;
+ }
+
+ c = *p++;
+ if (c != 'c' && c != 'n' && c != '[') {
+ s = skip_spaces(s);
+ }
+ switch (c) {
+ case 'd':
+ s = scan_int(s, &spec, 10, &args);
+ break;
+
+ case 'i':
+ s = scan_int(s, &spec, 0, &args);
+ break;
+
+ case 'o':
+ s = scan_int(s, &spec, 8, &args);
+ break;
+
+ case 'u':
+ s = scan_int(s, &spec, 10, &args);
+ break;
+
+ case 'x':
+ case 'X':
+ s = scan_int(s, &spec, 16, &args);
+ break;
+
+ case 'e':
+ case 'f':
+ case 'g':
+ case 'E':
+ case 'G':
+ s = scan_float(s, &spec, &args);
+ break;
+
+ case 's':
+ s = scan_string(s, &spec, &args);
+ break;
+
+ case '[':
+ s = scan_set(s, &spec, &p, &args);
+ break;
+
+ case 'c':
+ s = scan_chars(s, &spec, &args);
+ break;
+
+ case 'n':
+ if (spec.type != SCAN_DISCARD) {
+ *va_arg(args, int *) = s - start;
+ }
+ break;
+ }
+
+ if (!s) {
+ goto exit;
+ }
+ }
+ ok = true;
+
+exit:
+ va_end(args);
+ return ok;
+}
+
+void
+xsleep(unsigned int seconds)
+{
+ ovsrcu_quiesce_start();
+#ifdef _WIN32
+ Sleep(seconds * 1000);
+#else
+ sleep(seconds);
+#endif
+ ovsrcu_quiesce_end();
+}
+
+#ifdef _WIN32
+\f
+char *
+ovs_format_message(int error)
+{
+ enum { BUFSIZE = sizeof strerror_buffer_get()->s };
+ char *buffer = strerror_buffer_get()->s;
+
+ FormatMessage(FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS,
+ NULL, error, 0, buffer, BUFSIZE, NULL);
+ return buffer;
+}
+
+/* Returns a null-terminated string that explains the last error.
+ * Use this function to get the error string for WINAPI calls. */
+char *
+ovs_lasterror_to_string(void)
+{
+ return ovs_format_message(GetLastError());
+}
+
+int
+ftruncate(int fd, off_t length)
+{
+ int error;
+
+ error = _chsize_s(fd, length);
+ if (error) {
+ return -1;
+ }
+ return 0;
+}
+#endif