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 |
This series still needs a review. It still applies cleanly and passes all the tests.
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.
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 */ >
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 --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 */
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