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
_ubm_add_u32arr(uint32_t * dst,unsigned dst_len,uint32_t * a,unsigned a_len,uint32_t * b,unsigned b_len)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
_ubm_mul_u32arr(uint32_t * dst,unsigned dst_len,uint32_t * a,unsigned a_len,uint32_t * b,unsigned b_len)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 */
113