common/include/test-checked-overflow.c

   1 /* nbdkit
   2  * Copyright Red Hat
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #include <stddef.h>
  34 #include <stdint.h>
  35 #undef NDEBUG /* Keep test strong even for nbdkit built without assertions */
  36 #include <assert.h>
  37
  38 #include "checked-overflow.h"
  39
  40 #define TEST_ADD(a, b, result, expected_overflow, expected_result)      \
  41   do {                                                                  \
  42     bool actual_overflow;                                               \
  43                                                                         \
  44     actual_overflow = ADD_OVERFLOW_FALLBACK ((a), (b), (result));       \
  45     assert (actual_overflow == (expected_overflow));                    \
  46     assert (*(result) == (expected_result));                            \
  47     actual_overflow = ADD_OVERFLOW_FALLBACK ((b), (a), (result));       \
  48     assert (actual_overflow == (expected_overflow));                    \
  49     assert (*(result) == (expected_result));                            \
  50   } while (0)
  51
  52 #define TEST_MUL(a, b, result, expected_overflow, expected_result)      \
  53   do {                                                                  \
  54     bool actual_overflow;                                               \
  55                                                                         \
  56     actual_overflow = MUL_OVERFLOW_FALLBACK ((a), (b), (result));       \
  57     assert (actual_overflow == (expected_overflow));                    \
  58     assert (*(result) == (expected_result));                            \
  59     actual_overflow = MUL_OVERFLOW_FALLBACK ((b), (a), (result));       \
  60     assert (actual_overflow == (expected_overflow));                    \
  61     assert (*(result) == (expected_result));                            \
  62   } while (0)
  63
  64 /* Define these const-qualified objects because the UINTN_MAX object-like
  65  * macros in <stdint.h> have "post integer promotion" types. Therefore,
  66  * UINT16_MAX and UINT8_MAX most commonly have type "int". And that trips the
  67  * signedness check in ADD_OVERFLOW_FALLBACK().
  68  */
  69 static const uintmax_t umax_max = UINTMAX_MAX;
  70 static const uint64_t  u64_max  = UINT64_MAX;
  71 static const uint32_t  u32_max  = UINT32_MAX;
  72 static const uint16_t  u16_max  = UINT16_MAX;
  73 static const uint8_t   u8_max   = UINT8_MAX;
  74 static const size_t    size_max = SIZE_MAX;
  75
  76 int
  77 main (void)
  78 {
  79   union {
  80     uintmax_t umax;
  81     uint64_t  u64;
  82     uint32_t  u32;
  83     uint16_t  u16;
  84     uint8_t   u8;
  85     size_t    sz;
  86   } result;
  87   bool overflow;
  88
  89   /* "max + 0" and "0 + max" evaluate to "max", without overflow. */
  90   TEST_ADD (umax_max, 0u, &result.umax, false, umax_max);
  91   TEST_ADD (u64_max,  0u, &result.u64,  false, u64_max);
  92   TEST_ADD (u32_max,  0u, &result.u32,  false, u32_max);
  93   TEST_ADD (u16_max,  0u, &result.u16,  false, u16_max);
  94   TEST_ADD (u8_max,   0u, &result.u8,   false, u8_max);
  95   TEST_ADD (size_max, 0u, &result.sz,   false, size_max);
  96
  97   /* "max + 1" and "1 + max" overflow to zero. */
  98   TEST_ADD (umax_max, 1u, &result.umax, true, 0);
  99   TEST_ADD (u64_max,  1u, &result.u64,  true, 0);
 100   TEST_ADD (u32_max,  1u, &result.u32,  true, 0);
 101   TEST_ADD (u16_max,  1u, &result.u16,  true, 0);
 102   TEST_ADD (u8_max,   1u, &result.u8,   true, 0);
 103   TEST_ADD (size_max, 1u, &result.sz,   true, 0);
 104
 105   /* Adding umax_max (i.e., all-bits-one) amounts (with overflow) to
 106    * subtracting one.
 107    */
 108   TEST_ADD (umax_max, umax_max, &result.umax, true, umax_max - 1);
 109   TEST_ADD (u64_max,  umax_max, &result.u64,  true, u64_max  - 1);
 110   TEST_ADD (u32_max,  umax_max, &result.u32,  true, u32_max  - 1);
 111   TEST_ADD (u16_max,  umax_max, &result.u16,  true, u16_max  - 1);
 112   TEST_ADD (u8_max,   umax_max, &result.u8,   true, u8_max   - 1);
 113   TEST_ADD (size_max, umax_max, &result.sz,   true, size_max - 1);
 114
 115   /* "max * 0" and "0 * max" evaluate to 0, without overflow. */
 116   TEST_MUL (umax_max, 0u, &result.umax, false, 0);
 117   TEST_MUL (u64_max,  0u, &result.u64,  false, 0);
 118   TEST_MUL (u32_max,  0u, &result.u32,  false, 0);
 119   TEST_MUL (u16_max,  0u, &result.u16,  false, 0);
 120   TEST_MUL (u8_max,   0u, &result.u8,   false, 0);
 121   TEST_MUL (size_max, 0u, &result.sz,   false, 0);
 122
 123   /* "max * 1" and "1 * max" evaluate to "max", without overflow. */
 124   TEST_MUL (umax_max, 1u, &result.umax, false, umax_max);
 125   TEST_MUL (u64_max,  1u, &result.u64,  false, u64_max);
 126   TEST_MUL (u32_max,  1u, &result.u32,  false, u32_max);
 127   TEST_MUL (u16_max,  1u, &result.u16,  false, u16_max);
 128   TEST_MUL (u8_max,   1u, &result.u8,   false, u8_max);
 129   TEST_MUL (size_max, 1u, &result.sz,   false, size_max);
 130
 131   /* "max * 2" and "2 * max" evaluate (with overflow) to "max - 1". */
 132   TEST_MUL (umax_max, 2u, &result.umax, true, umax_max - 1);
 133   TEST_MUL (u64_max,  2u, &result.u64,  true, u64_max  - 1);
 134   TEST_MUL (u32_max,  2u, &result.u32,  true, u32_max  - 1);
 135   TEST_MUL (u16_max,  2u, &result.u16,  true, u16_max  - 1);
 136   TEST_MUL (u8_max,   2u, &result.u8,   true, u8_max   - 1);
 137   TEST_MUL (size_max, 2u, &result.sz,   true, size_max - 1);
 138
 139   /* factor                  255 -> 3 5 17
 140    * factor                65535 -> 3 5 17 257
 141    * factor           4294967295 -> 3 5 17 257     65537
 142    * factor 18446744073709551615 -> 3 5 17 257 641 65537 6700417
 143    *
 144    * Note: every time we double the width, we multiply the previous maximum
 145    * 0xF...F with 0x10...01:
 146    *
 147    *        0xF (= 3 * 5) *        0x11 (=            17) =               0xFF
 148    *       0xFF           *       0x101 (=           257) =             0xFFFF
 149    *     0xFFFF           *     0x10001 (=         65537) =         0xFFFFFFFF
 150    * 0xFFFFFFFF           * 0x100000001 (= 641 * 6700417) = 0xFFFFFFFFFFFFFFFF
 151    *
 152    * Perform the above multiplications, advacing with prime factors.
 153    */
 154   overflow = MUL_OVERFLOW_FALLBACK (3u, 5u, &result.u8);
 155   assert (!overflow);
 156   assert (result.u8 == 0xF);
 157
 158   overflow = MUL_OVERFLOW_FALLBACK (result.u8, 17u, &result.u8);
 159   assert (!overflow);
 160   assert (result.u8 == UINT8_MAX);
 161
 162   overflow = MUL_OVERFLOW_FALLBACK (result.u8, 257u, &result.u16);
 163   assert (!overflow);
 164   assert (result.u16 == UINT16_MAX);
 165
 166   overflow = MUL_OVERFLOW_FALLBACK (result.u16, 65537ul, &result.u32);
 167   assert (!overflow);
 168   assert (result.u32 == UINT32_MAX);
 169
 170   overflow = MUL_OVERFLOW_FALLBACK (result.u32, 641u, &result.u64);
 171   assert (!overflow);
 172   overflow = MUL_OVERFLOW_FALLBACK (result.u64, 6700417ul, &result.u64);
 173   assert (!overflow);
 174   assert (result.u64 == UINT64_MAX);
 175
 176   return 0;
 177 }