diff mbox series

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

Message ID 20190301235448.3168-1-blp@ovn.org
State Superseded
Headers show
Series [ovs-dev,1/3] sat-math: Add functions for saturating arithmetic on "long long int". | expand

Commit Message

Ben Pfaff March 1, 2019, 11:54 p.m. UTC 
The first users will be added in an upcoming commit.

Signed-off-by: Ben Pfaff <blp@ovn.org>
---
 lib/automake.mk |  3 ++-
 lib/sat-math.c  | 31 +++++++++++++++++++++++++++++++
 lib/sat-math.h  | 25 ++++++++++++++++++++++---
 3 files changed, 55 insertions(+), 4 deletions(-)
 create mode 100644 lib/sat-math.c

Comments

Ben Pfaff April 16, 2019, 11:21 p.m. UTC | #1 
This series still needs a review.  It still applies cleanly and passes
all the tests.
Ben Pfaff June 10, 2019, 12:29 a.m. UTC | #2 
On Fri, Mar 01, 2019 at 03:54:46PM -0800, Ben Pfaff wrote:
> The first users will be added in an upcoming commit.
> 
> Signed-off-by: Ben Pfaff <blp@ovn.org>

This series still needs review.
Ilya Maximets June 10, 2019, 2:35 p.m. UTC | #3 
On 02.03.2019 2:54, Ben Pfaff wrote:
> The first users will be added in an upcoming commit.
> 
> Signed-off-by: Ben Pfaff <blp@ovn.org>
> ---
>  lib/automake.mk |  3 ++-
>  lib/sat-math.c  | 31 +++++++++++++++++++++++++++++++
>  lib/sat-math.h  | 25 ++++++++++++++++++++++---
>  3 files changed, 55 insertions(+), 4 deletions(-)
>  create mode 100644 lib/sat-math.c
> 
> diff --git a/lib/automake.mk b/lib/automake.mk
> index bae032bd835e..6df8037a3fd8 100644
> --- a/lib/automake.mk
> +++ b/lib/automake.mk
> @@ -1,4 +1,4 @@
> -# Copyright (C) 2009-2018 Nicira, Inc.
> +# Copyright (C) 2009-2019 Nicira, Inc.
>  #
>  # Copying and distribution of this file, with or without modification,
>  # are permitted in any medium without royalty provided the copyright
> @@ -248,6 +248,7 @@ lib_libopenvswitch_la_SOURCES = \
>  	lib/rstp-common.h \
>  	lib/rstp-state-machines.c \
>  	lib/rstp-state-machines.h \
> +	lib/sat-math.c \
>  	lib/sat-math.h \
>  	lib/seq.c \
>  	lib/seq.h \
> diff --git a/lib/sat-math.c b/lib/sat-math.c
> new file mode 100644
> index 000000000000..24b73af12eb4
> --- /dev/null
> +++ b/lib/sat-math.c
> @@ -0,0 +1,31 @@
> +/*
> + * Copyright (c) 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.
> + * You may obtain a copy of the License at:
> + *
> + *     http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing, software
> + * distributed under the License is distributed on an "AS IS" BASIS,
> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> + * See the License for the specific language governing permissions and
> + * limitations under the License.
> + */
> +#include <config.h>
> +#include "sat-math.h"
> +
> +/* Returns x * y, clamping out-of-range results into the range of the return
> + * type. */
> +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_MIN / y ? LLONG_MAX

Shouldn't there be x < LLONG_MAX / y ?

if (y < 0) --> (LLONG_MIN / y) > 0
--> x always less than (LLONG_MIN / y), because x < 0.


Code become complicated here. Maybe it's time to write some unit tests for
this library?

Have you considered using compiler builtins like __builtin_mul_overflow()
for these functions? Modern clang and gcc supports them.

Best regards, Ilya Maximets.

> +            : x * y);
> +}
> diff --git a/lib/sat-math.h b/lib/sat-math.h
> index beeff8b2b429..79757726ead5 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,43 @@
>  #include <limits.h>
>  #include "openvswitch/util.h"
>  
> -/* Saturating addition: overflow yields UINT_MAX. */
> +/* 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);
> +}
>  
> -/* 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);
> +}
>  
> +/* 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);
>  }
> +long long int llsat_mul(long long int x, long long int y);
>  
>  #endif /* sat-math.h */
>
Ben Pfaff June 11, 2019, 4:49 p.m. UTC | #4 
On Mon, Jun 10, 2019 at 05:35:43PM +0300, Ilya Maximets wrote:
> On 02.03.2019 2:54, Ben Pfaff wrote:
> > The first users will be added in an upcoming commit.
> > 
> > Signed-off-by: Ben Pfaff <blp@ovn.org>
> > ---
> >  lib/automake.mk |  3 ++-
> >  lib/sat-math.c  | 31 +++++++++++++++++++++++++++++++
> >  lib/sat-math.h  | 25 ++++++++++++++++++++++---
> >  3 files changed, 55 insertions(+), 4 deletions(-)
> >  create mode 100644 lib/sat-math.c
> > 
> > diff --git a/lib/automake.mk b/lib/automake.mk
> > index bae032bd835e..6df8037a3fd8 100644
> > --- a/lib/automake.mk
> > +++ b/lib/automake.mk
> > @@ -1,4 +1,4 @@
> > -# Copyright (C) 2009-2018 Nicira, Inc.
> > +# Copyright (C) 2009-2019 Nicira, Inc.
> >  #
> >  # Copying and distribution of this file, with or without modification,
> >  # are permitted in any medium without royalty provided the copyright
> > @@ -248,6 +248,7 @@ lib_libopenvswitch_la_SOURCES = \
> >  	lib/rstp-common.h \
> >  	lib/rstp-state-machines.c \
> >  	lib/rstp-state-machines.h \
> > +	lib/sat-math.c \
> >  	lib/sat-math.h \
> >  	lib/seq.c \
> >  	lib/seq.h \
> > diff --git a/lib/sat-math.c b/lib/sat-math.c
> > new file mode 100644
> > index 000000000000..24b73af12eb4
> > --- /dev/null
> > +++ b/lib/sat-math.c
> > @@ -0,0 +1,31 @@
> > +/*
> > + * Copyright (c) 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.
> > + * You may obtain a copy of the License at:
> > + *
> > + *     http://www.apache.org/licenses/LICENSE-2.0
> > + *
> > + * Unless required by applicable law or agreed to in writing, software
> > + * distributed under the License is distributed on an "AS IS" BASIS,
> > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> > + * See the License for the specific language governing permissions and
> > + * limitations under the License.
> > + */
> > +#include <config.h>
> > +#include "sat-math.h"
> > +
> > +/* Returns x * y, clamping out-of-range results into the range of the return
> > + * type. */
> > +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_MIN / y ? LLONG_MAX
> 
> Shouldn't there be x < LLONG_MAX / y ?
> 
> if (y < 0) --> (LLONG_MIN / y) > 0
> --> x always less than (LLONG_MIN / y), because x < 0.
> 
> 
> Code become complicated here. Maybe it's time to write some unit tests for
> this library?

Maybe that was your polite way of saying "all your math is wrong" ;-)
I wrote some tests and I'll post v2 in a minute.

> Have you considered using compiler builtins like __builtin_mul_overflow()
> for these functions? Modern clang and gcc supports them.

Yes, those functions are awesome but OVS also supports MSVC so we can't
rely solely on them.
diff mbox series

Patch

diff --git a/lib/automake.mk b/lib/automake.mk
index bae032bd835e..6df8037a3fd8 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -1,4 +1,4 @@ 
-# Copyright (C) 2009-2018 Nicira, Inc.
+# Copyright (C) 2009-2019 Nicira, Inc.
 #
 # Copying and distribution of this file, with or without modification,
 # are permitted in any medium without royalty provided the copyright
@@ -248,6 +248,7 @@  lib_libopenvswitch_la_SOURCES = \
 	lib/rstp-common.h \
 	lib/rstp-state-machines.c \
 	lib/rstp-state-machines.h \
+	lib/sat-math.c \
 	lib/sat-math.h \
 	lib/seq.c \
 	lib/seq.h \
diff --git a/lib/sat-math.c b/lib/sat-math.c
new file mode 100644
index 000000000000..24b73af12eb4
--- /dev/null
+++ b/lib/sat-math.c
@@ -0,0 +1,31 @@ 
+/*
+ * Copyright (c) 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.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <config.h>
+#include "sat-math.h"
+
+/* Returns x * y, clamping out-of-range results into the range of the return
+ * type. */
+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_MIN / y ? LLONG_MAX
+            : x * y);
+}
diff --git a/lib/sat-math.h b/lib/sat-math.h
index beeff8b2b429..79757726ead5 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,43 @@ 
 #include <limits.h>
 #include "openvswitch/util.h"
 
-/* Saturating addition: overflow yields UINT_MAX. */
+/* 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);
+}
 
-/* 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);
+}
 
+/* 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);
 }
+long long int llsat_mul(long long int x, long long int y);
 
 #endif /* sat-math.h */