[ovs-dev] [PATCH v2 1/3] sat-math: Add functions for saturating arithmetic on "long long int".

Ben Pfaff blp at ovn.org
Tue Jun 11 16:55:14 UTC 2019


The first users will be added in an upcoming commit.

Also add tests.

Signed-off-by: Ben Pfaff <blp at ovn.org>
---
 lib/sat-math.h    | 72 +++++++++++++++++++++++++++++++++++++++++++++--
 tests/library.at  |  5 ++++
 tests/test-util.c | 42 ++++++++++++++++++++++++++-
 3 files changed, 115 insertions(+), 4 deletions(-)

diff --git a/lib/sat-math.h b/lib/sat-math.h
index beeff8b2b429..8dda1515fdd0 100644
--- a/lib/sat-math.h
+++ b/lib/sat-math.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2012 Nicira, Inc.
+ * Copyright (c) 2008, 2012, 2019 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -20,24 +20,90 @@
 #include <limits.h>
 #include "openvswitch/util.h"
 
-/* Saturating addition: overflow yields UINT_MAX. */
+#ifndef __has_builtin
+#define __has_builtin(x) 0
+#endif
+
+/* Returns x + y, clamping out-of-range results into the range of the return
+ * type. */
 static inline unsigned int
 sat_add(unsigned int x, unsigned int y)
 {
     return x + y >= x ? x + y : UINT_MAX;
 }
+static inline long long int
+llsat_add__(long long int x, long long int y)
+{
+    return (x >= 0 && y >= 0 && x > LLONG_MAX - y ? LLONG_MAX
+            : x < 0 && y < 0 && x < LLONG_MIN - y ? LLONG_MIN
+            : x + y);
+}
+static inline long long int
+llsat_add(long long int x, long long int y)
+{
+#if __GNUC__ >= 5 || __has_builtin(__builtin_saddll_overflow)
+    long long int sum;
+    return (!__builtin_saddll_overflow(x, y, &sum) ? sum
+            : x > 0 ? LLONG_MAX : LLONG_MIN);
+#else
+    return llsat_add__(x, y);
+#endif
+}
 
-/* Saturating subtraction: underflow yields 0. */
+/* Returns x - y, clamping out-of-range results into the range of the return
+ * type. */
 static inline unsigned int
 sat_sub(unsigned int x, unsigned int y)
 {
     return x >= y ? x - y : 0;
 }
+static inline long long int
+llsat_sub__(long long int x, long long int y)
+{
+    return (x >= 0 && y < 0 && x > LLONG_MAX + y ? LLONG_MAX
+            : x < 0 && y >= 0 && x < LLONG_MIN + y ? LLONG_MIN
+            : x - y);
+}
+static inline long long int
+llsat_sub(long long int x, long long int y)
+{
+#if __GNUC__ >= 5 || __has_builtin(__builtin_ssubll_overflow)
+    long long int difference;
+    return (!__builtin_ssubll_overflow(x, y, &difference) ? difference
+            : x >= 0 ? LLONG_MAX : LLONG_MIN);
+#else
+    return llsat_sub__(x, y);
+#endif
+}
 
+/* Returns x * y, clamping out-of-range results into the range of the return
+ * type. */
 static inline unsigned int
 sat_mul(unsigned int x, unsigned int y)
 {
     return OVS_SAT_MUL(x, y);
 }
+static inline long long int
+llsat_mul__(long long int x, long long int y)
+{
+    return (  x > 0 && y > 0 && x > LLONG_MAX / y ? LLONG_MAX
+            : x < 0 && y > 0 && x < LLONG_MIN / y ? LLONG_MIN
+            : x > 0 && y < 0 && y < LLONG_MIN / x ? LLONG_MIN
+            /* Special case because -LLONG_MIN / -1 overflows: */
+            : x == LLONG_MIN && y == -1 ? LLONG_MAX
+            : x < 0 && y < 0 && x < LLONG_MAX / y ? LLONG_MAX
+            : x * y);
+}
+static inline long long int
+llsat_mul(long long int x, long long int y)
+{
+#if __GNUC__ >= 5 || __has_builtin(__builtin_smulll_overflow)
+    long long int product;
+    return (!__builtin_smulll_overflow(x, y, &product) ? product
+            : (x > 0) == (y > 0) ? LLONG_MAX : LLONG_MIN);
+#else
+    return llsat_mul__(x, y);
+#endif
+}
 
 #endif /* sat-math.h */
diff --git a/tests/library.at b/tests/library.at
index a30d362e34bf..ecb9268d40df 100644
--- a/tests/library.at
+++ b/tests/library.at
@@ -231,6 +231,11 @@ AT_CHECK([sed 's/.*: //
 
 AT_CLEANUP
 
+AT_SETUP([saturating arithmetic])
+AT_KEYWORDS([sat math sat_math])
+AT_CHECK([ovstest test-util sat_math])
+AT_CLEANUP
+
 AT_SETUP([snprintf])
 AT_CHECK([ovstest test-util snprintf])
 AT_CLEANUP
diff --git a/tests/test-util.c b/tests/test-util.c
index 9222355ec1b0..f0fd0421086b 100644
--- a/tests/test-util.c
+++ b/tests/test-util.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, 2012, 2013, 2014, 2015, 2016 Nicira, Inc.
+ * Copyright (c) 2011, 2012, 2013, 2014, 2015, 2016, 2019 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -27,6 +27,7 @@
 #include "command-line.h"
 #include "ovstest.h"
 #include "random.h"
+#include "sat-math.h"
 #include "openvswitch/vlog.h"
 
 static void
@@ -1138,6 +1139,44 @@ test_snprintf(struct ovs_cmdl_context *ctx OVS_UNUSED)
     ovs_assert(snprintf(NULL, 0, "abcde") == 5);
 }
 
+static void
+check_sat(long long int x, long long int y, const char *op,
+          long long int r_a, long long int r_b)
+{
+    if (r_a != r_b) {
+        fprintf(stderr, "%lld %s %lld saturates differently: %lld vs %lld\n",
+                x, op, y, r_a, r_b);
+        abort();
+    }
+}
+
+static void
+test_sat_math(struct ovs_cmdl_context *ctx OVS_UNUSED)
+{
+    long long int values[] = {
+        LLONG_MIN, LLONG_MIN + 1, LLONG_MIN + 2, LLONG_MIN + 3,
+        LLONG_MIN + 4, LLONG_MIN + 5, LLONG_MIN + 6, LLONG_MIN + 7,
+        LLONG_MIN / 2, LLONG_MIN / 3, LLONG_MIN / 4, LLONG_MIN / 5,
+        -1000, -50, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0,
+        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 50, 1000,
+        LLONG_MAX / 5, LLONG_MAX / 4, LLONG_MAX / 3, LLONG_MAX / 2,
+        LLONG_MAX - 7, LLONG_MAX - 6, LLONG_MAX - 5, LLONG_MAX - 4,
+        LLONG_MAX - 3, LLONG_MAX - 2, LLONG_MAX - 1, LLONG_MAX,
+    };
+
+    /* Compare the behavior of our local implementation of these functions
+     * against the compiler implementation or its fallback.  (If the fallback
+     * is in use then this is comparing the fallback to itself, so this test is
+     * only really useful if the compiler has an implementation.) */
+    for (long long int *x = values; x < values + ARRAY_SIZE(values); x++) {
+        for (long long int *y = values; y < values + ARRAY_SIZE(values); y++) {
+            check_sat(*x, *y, "+", llsat_add(*x, *y), llsat_add__(*x, *y));
+            check_sat(*x, *y, "-", llsat_sub(*x, *y), llsat_sub__(*x, *y));
+            check_sat(*x, *y, "*", llsat_mul(*x, *y), llsat_mul__(*x, *y));
+        }
+    }
+}
+
 #ifndef _WIN32
 static void
 test_file_name(struct ovs_cmdl_context *ctx)
@@ -1174,6 +1213,7 @@ static const struct ovs_cmdl_command commands[] = {
     {"assert", NULL, 0, 0, test_assert, OVS_RO},
     {"ovs_scan", NULL, 0, 0, test_ovs_scan, OVS_RO},
     {"snprintf", NULL, 0, 0, test_snprintf, OVS_RO},
+    {"sat_math", NULL, 0, 0, test_sat_math, OVS_RO},
 #ifndef _WIN32
     {"file_name", NULL, 1, INT_MAX, test_file_name, OVS_RO},
 #endif
-- 
2.20.1



More information about the dev mailing list