2 * Copyright © 2018 Intel Corporation
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:
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
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
24 #ifndef UTIL_BIGMATH_H
25 #define UTIL_BIGMATH_H
34 _ubm_add_u32arr(uint32_t *dst
, unsigned dst_len
,
35 uint32_t *a
, unsigned a_len
,
36 uint32_t *b
, unsigned b_len
)
39 for (unsigned i
= 0; i
< dst_len
; i
++) {
49 /* Now compute overflow */
51 for (unsigned i
= dst_len
; i
< a_len
; i
++) {
56 for (unsigned i
= dst_len
; i
< b_len
; i
++) {
63 #define ubm_add_u32arr(dst, a, b) \
64 _ubm_add_u32arr(dst, ARRAY_SIZE(dst), a, ARRAY_SIZE(a), b, ARRAY_SIZE(b))
67 _ubm_mul_u32arr(uint32_t *dst
, unsigned dst_len
,
68 uint32_t *a
, unsigned a_len
,
69 uint32_t *b
, unsigned b_len
)
71 memset(dst
, 0, dst_len
* sizeof(*dst
));
73 bool overflow
= false;
75 for (unsigned i
= 0; i
< a_len
; i
++) {
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
82 * UINT64_MAX = UINT32_MAX << 32 + UINT32_MAX
83 * = UINT32_MAX * (UINT32_MAX + 1) + UINT32_MAX
84 * = UINT32_MAX * UINT32_MAX + 2 * UINT32_MAX
86 * so we're guaranteed that we can add in two more 32-bit values
87 * without overflowing tmp.
89 uint64_t tmp
= (uint64_t)a
[i
] * (uint64_t)b
[j
];
91 if (i
+ j
< dst_len
) {
96 /* We're trying to write a value that doesn't fit */
97 overflow
= overflow
|| tmp
> 0;
101 if (i
+ b_len
< dst_len
)
102 dst
[i
+ b_len
] = carry
;
104 overflow
= overflow
|| carry
> 0;
109 #define ubm_mul_u32arr(dst, a, b) \
110 _ubm_mul_u32arr(dst, ARRAY_SIZE(dst), a, ARRAY_SIZE(a), b, ARRAY_SIZE(b))
112 #endif /* UTIL_BIGMATH_H */