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

Ilya Maximets i.maximets at samsung.com
Mon Jun 10 14:35:43 UTC 2019


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 at 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 */
> 


More information about the dev mailing list