Exercise on Preventive Analysis

Consider a program that is in charge of controlling heavy machinery for analyzing component materials.

It is accessed through a procedure, which takes a set of elements and produces a result based on all the possible unordered pairs that can be formed from them.

For example the following elements

produce the following pairs,

where the rows and the columns are in no particular order.

The relevant part of the source code is shown below.

#include <errno.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>

#include "analyzer.h"

#define COUNT_MAX 2

bool analyze(struct sample const* const elements,
    size_t const count,
    struct result* const result) {
  if (count > COUNT_MAX)
    return errno = EINVAL, false;

  if (result == NULL)
    return true;

  return analyze_for_real(elements, count, result);
}

The publicly visible analyze procedure checks its arguments and delegates the hard work to analyze_for_real, which then writes its result into the result pointer.

The set of interest is represented as an array of unique elements and the element count is stored in a variable of type size_t, as it should. However the amount of pairs may exceed the amount of elements. That is a problem, because size_t may be the largest unsigned integer type available, in which case the amount of pairs will not fit into any kind of variable. The solution is to limit the amount of elements to COUNT_MAX.

The limit is currently set so low that nothing unsafe may happen. Unfortunately nothing useful may happen either.

Your job is to find the highest possible COUNT_MAX that does not cause an overflow during pair formation.

The catch is that COUNT_MAX must be a compile-time constant. Therefore it may only depend on

• SIZE_MAX, the maximum value of size_t;
• sizeof (size_t), the amount of bytes in a size_t;
• CHAR_BIT, the amount of bits in a byte and
• other such compile-time constants

instead of count.