From: Peter Zijlstra <a.p.zijlstra@chello.nl>
To: linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org
Cc: Linus Torvalds <torvalds@linux-foundation.org>,
Andrew Morton <akpm@linux-foundation.org>,
Juri Lelli <juri.lelli@gmail.com>, Ingo Molnar <mingo@kernel.org>,
Thomas Gleixner <tglx@linutronix.de>,
Peter Zijlstra <a.p.zijlstra@chello.nl>
Subject: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128
Date: Tue, 24 Apr 2012 18:10:41 +0200 [thread overview]
Message-ID: <20120424162224.526249106@chello.nl> (raw)
In-Reply-To: 20120424161039.293018424@chello.nl
[-- Attachment #1: math128.patch --]
[-- Type: text/plain, Size: 7794 bytes --]
Grow rudimentary u128 support without relying on gcc/libgcc.
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
arch/alpha/include/asm/math128.h | 4 ++
arch/arm/include/asm/math128.h | 4 ++
arch/avr32/include/asm/math128.h | 4 ++
arch/blackfin/include/asm/math128.h | 4 ++
arch/c6x/include/asm/math128.h | 4 ++
arch/cris/include/asm/math128.h | 4 ++
arch/frv/include/asm/math128.h | 4 ++
arch/h8300/include/asm/math128.h | 4 ++
arch/hexagon/include/asm/math128.h | 4 ++
arch/ia64/include/asm/math128.h | 4 ++
arch/m32r/include/asm/math128.h | 4 ++
arch/m68k/include/asm/math128.h | 4 ++
arch/microblaze/include/asm/math128.h | 4 ++
arch/mips/include/asm/math128.h | 4 ++
arch/mn10300/include/asm/math128.h | 4 ++
arch/openrisc/include/asm/math128.h | 4 ++
arch/parisc/include/asm/math128.h | 4 ++
arch/powerpc/include/asm/math128.h | 4 ++
arch/s390/include/asm/math128.h | 4 ++
arch/score/include/asm/math128.h | 4 ++
arch/sh/include/asm/math128.h | 4 ++
arch/sparc/include/asm/math128.h | 4 ++
arch/tile/include/asm/math128.h | 4 ++
arch/um/include/asm/math128.h | 4 ++
arch/unicore32/include/asm/math128.h | 4 ++
arch/x86/include/asm/math128.h | 4 ++
arch/xtensa/include/asm/math128.h | 4 ++
include/linux/math128.h | 47 ++++++++++++++++++++++++++++++++++
lib/Makefile | 2 -
lib/math128.c | 42 ++++++++++++++++++++++++++++++
30 files changed, 198 insertions(+), 1 deletion(-)
--- /dev/null
+++ b/arch/alpha/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/arm/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/avr32/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/blackfin/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/c6x/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/cris/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/frv/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/h8300/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/hexagon/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/ia64/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/m32r/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/m68k/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/microblaze/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/mips/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/mn10300/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/openrisc/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/parisc/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/powerpc/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/s390/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/score/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/sh/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/sparc/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/tile/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/um/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/unicore32/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/x86/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/arch/xtensa/include/asm/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_MATH128_H
+#define _ASM_MATH128_H
+
+#endif /* _ASM_MATH128_H */
--- /dev/null
+++ b/include/linux/math128.h
@@ -0,0 +1,47 @@
+#ifndef _LINUX_MATH128_H
+#define _LINUX_MATH128_H
+
+#include <linux/types.h>
+
+typedef struct {
+ u64 hi, lo;
+} u128;
+
+#include <asm/math128.h>
+
+#ifndef add_u128
+static inline u128 add_u128(u128 a, u128 b)
+{
+ u128 res;
+
+ res.hi = a.hi + b.hi;
+ res.lo = a.lo + b.lo;
+
+ if (res.lo < a.lo || res.lo < b.lo)
+ res.hi++;
+
+ return res;
+}
+#endif /* add_u128 */
+
+#ifndef mult_u128
+extern int u128 mult_u128(u64 a, u64 b);
+#endif
+
+#ifndef cmp_u128
+static inline int cmp_u128(u128 a, u128 b)
+{
+ if (a.hi > b.hi)
+ return 1;
+ if (a.hi < b.hi)
+ return -1;
+ if (a.lo > b.lo)
+ return 1;
+ if (a.lo < b.lo)
+ return -1;
+
+ return 0;
+}
+#endif /* cmp_u128 */
+
+#endif /* _LINUX_MATH128_H */
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmd
idr.o int_sqrt.o extable.o prio_tree.o \
sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
proportions.o prio_heap.o ratelimit.o show_mem.o \
- is_single_threaded.o plist.o decompress.o
+ is_single_threaded.o plist.o decompress.o math128.o
lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
--- /dev/null
+++ b/lib/math128.c
@@ -0,0 +1,42 @@
+#include <linux/math128.h>
+
+#ifndef mult_u128
+/*
+ * a * b = (ah * 2^32 + al) * (bh * 2^32 + bl) =
+ * ah*bh * 2^64 + (ah*bl + bh*al) * 2^32 + al*bl
+ */
+u128 mult_u128(u64 a, u64 b)
+{
+ u128 res;
+ u64 ah, al;
+ u64 bh, bl;
+ u128 t1, t2, t3, t4;
+
+ ah = a >> 32;
+ al = a & ((1ULL << 32) - 1);
+
+ bh = b >> 32;
+ bl = b & ((1ULL << 32) - 1);
+
+ t1.lo = 0;
+ t1.hi = ah * bh;
+
+ t2.lo = ah * bl;
+ t2.hi = t2.lo >> 32;
+ t2.lo <<= 32;
+
+ t3.lo = al * bh;
+ t3.hi = t3.lo >> 32;
+ t3.lo <<= 32;
+
+ t4.lo = al * bl;
+ t4.hi = 0;
+
+ res = add_u128(t1, t2);
+ res = add_u128(res, t3);
+ res = add_u128(res, t4);
+
+ return res;
+}
+#endif /* mult_u128 */
+
next prev parent reply other threads:[~2012-04-24 16:25 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-04-24 16:10 [RFC][PATCH 0/3] gcc work-around and math128 Peter Zijlstra
2012-04-24 16:10 ` [RFC][PATCH 1/3] kernel,sched,time: Clean up gcc work-arounds Peter Zijlstra
2012-04-24 19:39 ` Linus Torvalds
2012-04-25 0:14 ` Stephen Rothwell
2012-04-24 16:10 ` Peter Zijlstra [this message]
2012-04-24 19:37 ` [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128 Linus Torvalds
2012-04-24 19:43 ` Peter Zijlstra
2012-04-24 20:12 ` Måns Rullgård
2012-04-24 21:54 ` Peter Zijlstra
2012-04-25 0:09 ` H. Peter Anvin
2012-04-25 1:46 ` Linus Torvalds
2012-04-25 8:35 ` Peter Zijlstra
2012-04-25 10:13 ` Peter Zijlstra
2012-04-25 0:23 ` Stephen Rothwell
2012-04-25 8:11 ` Peter Zijlstra
2012-04-25 11:23 ` Geert Uytterhoeven
2012-04-25 11:58 ` Peter Zijlstra
2012-04-25 14:35 ` Geert Uytterhoeven
2012-04-25 15:09 ` Peter Zijlstra
2012-04-24 16:10 ` [RFC][PATCH 3/3] math128, x86_64: Implement {mult,add}_u128 in 64bit asm Peter Zijlstra
2012-04-24 16:34 ` H. Peter Anvin
2012-04-24 16:36 ` Peter Zijlstra
2012-04-24 17:17 ` H. Peter Anvin
2012-04-24 17:19 ` Peter Zijlstra
2012-04-24 17:20 ` H. Peter Anvin
2012-04-24 22:00 ` Peter Zijlstra
2012-04-24 22:03 ` H. Peter Anvin
2012-04-24 17:22 ` [RFC][PATCH 0/3] gcc work-around and math128 H. Peter Anvin
2012-04-24 17:27 ` H. Peter Anvin
2012-04-24 21:15 ` Andy Lutomirski
2012-04-24 21:18 ` Linus Torvalds
2012-04-24 21:32 ` Peter Zijlstra
2012-04-24 21:35 ` Andy Lutomirski
2012-04-24 21:51 ` Peter Zijlstra
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20120424162224.526249106@chello.nl \
--to=a.p.zijlstra@chello.nl \
--cc=akpm@linux-foundation.org \
--cc=juri.lelli@gmail.com \
--cc=linux-arch@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox