This patch is
Reviewed-by: Ian Romanick <ian.d.roman...@intel.com>
On 10/05/2018 09:10 PM, Jason Ekstrand wrote:
> ---
> src/util/Makefile.am | 1 +
> src/util/Makefile.sources | 1 +
> src/util/bigmath.h | 112 ++++++++++++++++++++++++++++++++++++++
> src/util/meson.build | 1 +
> 4 files changed, 115 insertions(+)
> create mode 100644 src/util/bigmath.h
>
> diff --git a/src/util/Makefile.am b/src/util/Makefile.am
> index efb94caff71..d79f2b320be 100644
> --- a/src/util/Makefile.am
> +++ b/src/util/Makefile.am
> @@ -21,6 +21,7 @@
>
> SUBDIRS = . \
> xmlpool \
> + tests/fast_idiv_by_const \
> tests/hash_table \
> tests/string_buffer \
> tests/set
> diff --git a/src/util/Makefile.sources b/src/util/Makefile.sources
> index b562d6cd6f4..5b1548c733c 100644
> --- a/src/util/Makefile.sources
> +++ b/src/util/Makefile.sources
> @@ -1,4 +1,5 @@
> MESA_UTIL_FILES := \
> + bigmath.h \
> bitscan.c \
> bitscan.h \
> bitset.h \
> diff --git a/src/util/bigmath.h b/src/util/bigmath.h
> new file mode 100644
> index 00000000000..6339bb6f6ca
> --- /dev/null
> +++ b/src/util/bigmath.h
> @@ -0,0 +1,112 @@
> +/*
> + * Copyright © 2018 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
> DEALINGS
> + * IN THE SOFTWARE.
> + */
> +
> +#ifndef UTIL_BIGMATH_H
> +#define UTIL_BIGMATH_H
> +
> +#include "macros.h"
> +
> +#include <assert.h>
> +#include <stdint.h>
> +#include <string.h>
> +
> +static inline bool
> +_ubm_add_u32arr(uint32_t *dst, unsigned dst_len,
> + uint32_t *a, unsigned a_len,
> + uint32_t *b, unsigned b_len)
> +{
> + uint32_t carry = 0;
> + for (unsigned i = 0; i < dst_len; i++) {
> + uint64_t sum = carry;
> + if (i < a_len)
> + sum += a[i];
> + if (i < b_len)
> + sum += b[i];
> + dst[i] = sum;
> + carry = sum >> 32;
> + }
> +
> + /* Now compute overflow */
> +
> + for (unsigned i = dst_len; i < a_len; i++) {
> + if (a[i])
> + return true;
> + }
> +
> + for (unsigned i = dst_len; i < b_len; i++) {
> + if (b[i])
> + return true;
> + }
> +
> + return carry;
> +}
> +#define ubm_add_u32arr(dst, a, b) \
> + _ubm_add_u32arr(dst, ARRAY_SIZE(dst), a, ARRAY_SIZE(a), b, ARRAY_SIZE(b))
> +
> +static inline bool
> +_ubm_mul_u32arr(uint32_t *dst, unsigned dst_len,
> + uint32_t *a, unsigned a_len,
> + uint32_t *b, unsigned b_len)
> +{
> + memset(dst, 0, dst_len * sizeof(*dst));
> +
> + bool overflow = false;
> +
> + for (unsigned i = 0; i < a_len; i++) {
> + uint32_t carry = 0;
> + for (unsigned j = 0; j < b_len; j++) {
> + /* The maximum values of a[i] and b[i] are UINT32_MAX so the maximum
> + * value of tmp is UINT32_MAX * UINT32_MAX. The maximum value that
> + * will fit in tmp is
> + *
> + * UINT64_MAX = UINT32_MAX << 32 + UINT32_MAX
> + * = UINT32_MAX * (UINT32_MAX + 1) + UINT32_MAX
> + * = UINT32_MAX * UINT32_MAX + 2 * UINT32_MAX
> + *
> + * so we're guaranteed that we can add in two more 32-bit values
> + * without overflowing tmp.
> + */
> + uint64_t tmp = (uint64_t)a[i] * (uint64_t)b[j];
> + tmp += carry;
> + if (i + j < dst_len) {
> + tmp += dst[i + j];
> + dst[i + j] = tmp;
> + carry = tmp >> 32;
> + } else {
> + /* We're trying to write a value that doesn't fit */
> + overflow = overflow || tmp > 0;
> + break;
> + }
> + }
> + if (i + b_len < dst_len)
> + dst[i + b_len] = carry;
> + else
> + overflow = overflow || carry > 0;
> + }
> +
> + return overflow;
> +}
> +#define ubm_mul_u32arr(dst, a, b) \
> + _ubm_mul_u32arr(dst, ARRAY_SIZE(dst), a, ARRAY_SIZE(a), b, ARRAY_SIZE(b))
> +
> +#endif /* UTIL_BIGMATH_H */
> diff --git a/src/util/meson.build b/src/util/meson.build
> index 027bc5b9d0d..9a99d60c158 100644
> --- a/src/util/meson.build
> +++ b/src/util/meson.build
> @@ -23,6 +23,7 @@ inc_util = include_directories('.')
> subdir('xmlpool')
>
> files_mesa_util = files(
> + 'bigmath.h',
> 'bitscan.c',
> 'bitscan.h',
> 'bitset.h',
>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
