[Mesa-dev] [PATCH 1/6] util: Add a simple big math library

[Jason Ekstrand]

---
 src/util/Makefile.sources |  1 +
 src/util/bigmath.h        | 95 +++++++++++++++++++++++++++++++++++++++
 src/util/meson.build      |  1 +
 3 files changed, 97 insertions(+)
 create mode 100644 src/util/bigmath.h

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..1887ea423d6
--- /dev/null
+++ b/src/util/bigmath.h
@@ -0,0 +1,95 @@
+/*
+ * 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_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++) {
+         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))
+
+static inline int
+_ubm_cmp_u32arr(uint32_t *a, unsigned a_len, uint32_t *b, unsigned b_len)
+{
+   if (a_len < b_len) {
+      for (int i = a_len; i < b_len; i++) {
+         if (0 < b[i])
+            return -1;
+      }
+   } else if (a_len > b_len) {
+      for (int i = b_len; i < a_len; i++) {
+         if (a[i] > 0)
+            return 1;
+      }
+   }
+
+   for (int i = MIN2(a_len, b_len) - 1; i >= 0; i--) {
+      if (a[i] < b[i])
+         return -1;
+      else if (a[i] > b[i])
+         return 1;
+   }
+
+   return 0;
+}
+#define ubm_cmp_u32arr(a, b) \
+   _ubm_cmp_u32arr(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.17.1