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

2019-06-11 Thread Ben Pfaff 
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 
> > ---
> >  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 ..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 
> > +#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.
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

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

2019-06-10 Thread Ilya Maximets 
On 02.03.2019 2:54, Ben Pfaff wrote:
> The first users will be added in an upcoming commit.
> 
> Signed-off-by: Ben Pfaff 
> ---
>  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 ..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 
> +#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 
>  #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 */
> 
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

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

2019-06-09 Thread Ben Pfaff 
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 

This series still needs review.
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

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

2019-04-16 Thread Ben Pfaff 
This series still needs a review.  It still applies cleanly and passes
all the tests.
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

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

2019-03-01 Thread Ben Pfaff 
The first users will be added in an upcoming commit.

Signed-off-by: Ben Pfaff 
---
 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 ..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 
+#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 
 #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 */
-- 
2.20.1

___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev