---
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',
--
2.19.0
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
