Libguestfs - Nov 2021 - [PATCH nbdkit 2/2] common/include/checked-overflow.h: Provide fallback

On 11/18/21 19:12, Eric Blake wrote:
> Perhaps you can do this with a function signature like:
>
> bool check_op_overflow (uint64_t a, uint64_t b, uint64_t max, uint64_t *r)
>
>>
>> - deduce the actual result limit from ((typeof (*r))-1),
>>
>> - assign the low-order bits in any case -- if either the uintmax_t
>> operation overflows or the actual result limit is exceeded, it all
>> happens in unsigned, so it's well-defined (modular reduction).
Return
>> the overflow status correctly.
>
> and then utilize it something like:
>
> #define CHECK_OP_OVERFLOW(a, b, r) \
>   ({ \
>     bool overflow; uint64_t tmp; \
>     CHECK_UNSIGNED_INT (a); CHECK_UNSIGNED_INT (b); \
>     overflow = check_op_overflow (a, b, (typeof (*(r)))-1, &tmp); \
>     *(r) = tmp; \
>     overflow; \
>   })
>
> and maybe even have CHECK_UNSIGNED_INT() permit signed values >= 0,
> rather than insisting that the underlying type be unsigned.
>
> At any rate, the approach sounds good to me.
How about this:

--------
#include <stdbool.h>
#include <stdint.h>

/* Assert, at compile time, that the expression "x" has some unsigned
integer
 * type.
 *
 * The expression "x" is not evaluated, unless it has variably
modified type.
 */
#define STATIC_ASSERT_UNSIGNED_INT(x)                          \
  do {                                                         \
    typedef char x_has_uint_type[(typeof (x))-1 > 0 ? 1 : -1]; \
  } while (0)

/* Assign the sum (a + b) to (*r), using uintmax_t modular arithmetic.
 *
 * Return true iff the addition overflows or the result exceeds (max).
 */
static inline bool
check_add_overflow (uintmax_t a, uintmax_t b, uintmax_t max, uintmax_t *r)
{
  *r = a + b;
  return a > UINTMAX_MAX - b || *r > max;
}

/* Assign the product (a * b) to (*r), using uintmax_t modular arithmetic.
 *
 * Return true iff the multiplication overflows or the result exceeds (max).
 */
static inline bool
check_mul_overflow (uintmax_t a, uintmax_t b, uintmax_t max, uintmax_t *r)
{
  *r = a * b;
  return b > 0 && (a > UINTMAX_MAX / b || *r > max);
}

/* Add (a) and (b), both of (possibly different) unsigned integer types, and
 * store the sum in (*r), which must also have some unsigned integer type.
 *
 * Each macro argument is evaluated exactly once, as long as it does not have
 * variably modified type.
 *
 * The macro evaluates to (false) if (*r) can represent the mathematical sum.
 * Otherwise, the macro evaluates to (true), and the low order bits of the
 * mathematical sum are stored to (*r).
 */
#define ADD_OVERFLOW(a, b, r)                                          \
  ({                                                                   \
    bool overflow;                                                     \
    uintmax_t tmp;                                                     \
                                                                       \
    STATIC_ASSERT_UNSIGNED_INT (a);                                    \
    STATIC_ASSERT_UNSIGNED_INT (b);                                    \
    STATIC_ASSERT_UNSIGNED_INT (*(r));                                 \
    overflow = check_add_overflow ((a), (b), (typeof (*(r)))-1, &tmp); \
    *(r) = tmp;                                                        \
    overflow;                                                          \
  })

/* Multiply (a) and (b), both of (possibly different) unsigned integer types,
 * and store the product in (*r), which must also have some unsigned integer
 * type.
 *
 * Each macro argument is evaluated exactly once, as long as it does not have
 * variably modified type.
 *
 * The macro evaluates to (false) if (*r) can represent the mathematical
 * product. Otherwise, the macro evaluates to (true), and the low order bits of
 * the mathematical product are stored to (*r).
 */
#define MUL_OVERFLOW(a, b, r)                                          \
  ({                                                                   \
    bool overflow;                                                     \
    uintmax_t tmp;                                                     \
                                                                       \
    STATIC_ASSERT_UNSIGNED_INT (a);                                    \
    STATIC_ASSERT_UNSIGNED_INT (b);                                    \
    STATIC_ASSERT_UNSIGNED_INT (*(r));                                 \
    overflow = check_mul_overflow ((a), (b), (typeof (*(r)))-1, &tmp); \
    *(r) = tmp;                                                        \
    overflow;                                                          \
  })
--------

Questions:

(1) What is the usual style in nbdkit to highlight parameters of
functions and function-like macros in documentation (comments)? Here I
used parentheses. Normally I use quotes "".

(2) In the actual functions, we return "true" for
"overflow". My
original conditions expressed "no overflow". In this source code, I
*open-coded* the negations of my original conditions, using De Morgan's
laws. That's because I dislike expressions with an outermost "!"
operator -- whenever I face such an expression, I always work the
outermost negation *into* the formula, as deeply as I can.

However, I realize the resultant conditions may not be easy to read this
way. Here's an alternative for the body of check_add_overflow(), based
on the original formulation:

  register bool in_range;

  *r = a + b;
  in_range = a <= UINTMAX_MAX - b && *r <= max;
  return !in_range;

(3) In the overflow conditions, I used parentheses as sparingly as
possible; only when needed. I could also use as many as possible.

- Compare, for the addition:

  return ((a > UINTMAX_MAX - b) || (*r > max));

or

  in_range = ((a <= UINTMAX_MAX - b) && (*r <= max));
  return !in_range;

- Compare, for the multiplication:

  return ((b > 0) && ((a > UINTMAX_MAX / b) || (*r > max)));

or

  in_range = ((b == 0) || ((a <= UINTMAX_MAX / b) && (*r <=
max)));
  return !in_range;

What's the preferred form?

Thanks,
Laszlo

On Fri, Nov 19, 2021 at 03:35:48PM +0100, Laszlo Ersek
wrote:
> (1) What is the usual style in nbdkit to highlight parameters of
> functions and function-like macros in documentation (comments)? Here I
> used parentheses. Normally I use quotes "".
We don't have one, so quotes are fine.
> (2) In the actual functions, we return "true" for
"overflow". My
> original conditions expressed "no overflow". In this source code,
I
> *open-coded* the negations of my original conditions, using De Morgan's
> laws. That's because I dislike expressions with an outermost
"!"
> operator -- whenever I face such an expression, I always work the
> outermost negation *into* the formula, as deeply as I can.
> 
> However, I realize the resultant conditions may not be easy to read this
> way. Here's an alternative for the body of check_add_overflow(), based
> on the original formulation:
> 
>   register bool in_range;
> 
>   *r = a + b;
>   in_range = a <= UINTMAX_MAX - b && *r <= max;
>   return !in_range;
Seems reasonable.
> (3) In the overflow conditions, I used parentheses as sparingly as
> possible; only when needed. I could also use as many as possible.
> 
> - Compare, for the addition:
> 
>   return ((a > UINTMAX_MAX - b) || (*r > max));
> 
> or
> 
>   in_range = ((a <= UINTMAX_MAX - b) && (*r <= max));
>   return !in_range;
> 
> - Compare, for the multiplication:
> 
>   return ((b > 0) && ((a > UINTMAX_MAX / b) || (*r >
max)));
> 
> or
> 
>   in_range = ((b == 0) || ((a <= UINTMAX_MAX / b) && (*r <=
max)));
>   return !in_range;
> 
> What's the preferred form?
Personally I use fewest parens, but indicate precedence by dropping
whitespace, but I guess whatever works.  However you definitely don't
need the parens around the entire return value, C doesn't require
that.

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
Read my programming and virtualization blog: http://rwmj.wordpress.com
virt-builder quickly builds VMs from scratch
http://libguestfs.org/virt-builder.1.html