src/util/bigmath.h

   1 /*
   2  * Copyright © 2018 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  */
  23
  24 #ifndef UTIL_BIGMATH_H
  25 #define UTIL_BIGMATH_H
  26
  27 #include "macros.h"
  28
  29 #include <assert.h>
  30 #include <stdint.h>
  31 #include <string.h>
  32
  33 static inline bool
  34 _ubm_add_u32arr(uint32_t *dst, unsigned dst_len,
  35                 uint32_t *a, unsigned a_len,
  36                 uint32_t *b, unsigned b_len)
  37 {
  38    uint32_t carry = 0;
  39    for (unsigned i = 0; i < dst_len; i++) {
  40       uint64_t sum = carry;
  41       if (i < a_len)
  42          sum += a[i];
  43       if (i < b_len)
  44          sum += b[i];
  45       dst[i] = sum;
  46       carry = sum >> 32;
  47    }
  48
  49    /* Now compute overflow */
  50
  51    for (unsigned i = dst_len; i < a_len; i++) {
  52       if (a[i])
  53          return true;
  54    }
  55
  56    for (unsigned i = dst_len; i < b_len; i++) {
  57       if (b[i])
  58          return true;
  59    }
  60
  61    return carry;
  62 }
  63 #define ubm_add_u32arr(dst, a, b) \
  64    _ubm_add_u32arr(dst, ARRAY_SIZE(dst), a, ARRAY_SIZE(a), b, ARRAY_SIZE(b))
  65
  66 static inline bool
  67 _ubm_mul_u32arr(uint32_t *dst, unsigned dst_len,
  68                 uint32_t *a, unsigned a_len,
  69                 uint32_t *b, unsigned b_len)
  70 {
  71    memset(dst, 0, dst_len * sizeof(*dst));
  72
  73    bool overflow = false;
  74
  75    for (unsigned i = 0; i < a_len; i++) {
  76       uint32_t carry = 0;
  77       for (unsigned j = 0; j < b_len; j++) {
  78          /* The maximum values of a[i] and b[i] are UINT32_MAX so the maximum
  79           * value of tmp is UINT32_MAX * UINT32_MAX.  The maximum value that
  80           * will fit in tmp is
  81           *
  82           *    UINT64_MAX = UINT32_MAX << 32 + UINT32_MAX
  83           *               = UINT32_MAX * (UINT32_MAX + 1) + UINT32_MAX
  84           *               = UINT32_MAX * UINT32_MAX + 2 * UINT32_MAX
  85           *
  86           * so we're guaranteed that we can add in two more 32-bit values
  87           * without overflowing tmp.
  88           */
  89          uint64_t tmp = (uint64_t)a[i] * (uint64_t)b[j];
  90          tmp += carry;
  91          if (i + j < dst_len) {
  92             tmp += dst[i + j];
  93             dst[i + j] = tmp;
  94             carry = tmp >> 32;
  95          } else {
  96             /* We're trying to write a value that doesn't fit */
  97             overflow = overflow || tmp > 0;
  98             break;
  99          }
 100       }
 101       if (i + b_len < dst_len)
 102          dst[i + b_len] = carry;
 103       else
 104          overflow = overflow || carry > 0;
 105    }
 106
 107    return overflow;
 108 }
 109 #define ubm_mul_u32arr(dst, a, b) \
 110    _ubm_mul_u32arr(dst, ARRAY_SIZE(dst), a, ARRAY_SIZE(a), b, ARRAY_SIZE(b))
 111
 112 #endif /* UTIL_BIGMATH_H */