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 33static 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 66static 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 */ 113