[PATCH 01/15] math128: Introduce various 128bit primitives

From: Juri Lelli
Date: Wed May 23 2012 - 17:48:37 EST

Next message: J. Bruce Fields: "Re: [PATCH] NFSd: set nfsd_serv to NULL after service destruction"
Previous message: Juri Lelli: "[PATCH 03/15] sched: add sched_class->task_dead."
In reply to: Juri Lelli: "[PATCH 03/15] sched: add sched_class->task_dead."
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

From: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>

Grow rudimentary u128 support without relying on gcc/libgcc.

Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
Cc: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Cc: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
Link: http://lkml.kernel.org/n/tip-pppjsy9fz2v57x98hsts2cj3@xxxxxxxxxxxxxx
---
arch/alpha/include/asm/Kbuild | 1 +
arch/arm/include/asm/Kbuild | 1 +
arch/avr32/include/asm/Kbuild | 1 +
arch/blackfin/include/asm/Kbuild | 1 +
arch/c6x/include/asm/Kbuild | 1 +
arch/cris/include/asm/Kbuild | 1 +
arch/frv/include/asm/Kbuild | 1 +
arch/h8300/include/asm/Kbuild | 1 +
arch/hexagon/include/asm/Kbuild | 1 +
arch/ia64/include/asm/Kbuild | 1 +
arch/m32r/include/asm/Kbuild | 1 +
arch/m68k/include/asm/Kbuild | 1 +
arch/microblaze/include/asm/Kbuild | 1 +
arch/mips/include/asm/Kbuild | 1 +
arch/mn10300/include/asm/Kbuild | 1 +
arch/openrisc/include/asm/Kbuild | 1 +
arch/parisc/include/asm/Kbuild | 1 +
arch/powerpc/include/asm/Kbuild | 1 +
arch/s390/include/asm/Kbuild | 1 +
arch/score/include/asm/Kbuild | 1 +
arch/sh/include/asm/Kbuild | 1 +
arch/sparc/include/asm/Kbuild | 1 +
arch/tile/include/asm/Kbuild | 1 +
arch/um/include/asm/Kbuild | 1 +
arch/unicore32/include/asm/Kbuild | 1 +
arch/x86/include/asm/Kbuild | 1 +
arch/xtensa/include/asm/Kbuild | 1 +
include/asm-generic/math128.h | 4 +
include/linux/math128.h | 180 ++++++++++++++++++++++++++++++++++++
lib/Makefile | 2 +-
lib/math128.c | 40 ++++++++
31 files changed, 252 insertions(+), 1 deletion(-)
create mode 100644 include/asm-generic/math128.h
create mode 100644 include/linux/math128.h
create mode 100644 lib/math128.c

diff --git a/arch/alpha/include/asm/Kbuild b/arch/alpha/include/asm/Kbuild
index e423def..f8f9bed 100644
--- a/arch/alpha/include/asm/Kbuild
+++ b/arch/alpha/include/asm/Kbuild
@@ -8,3 +8,4 @@ header-y += pal.h
header-y += reg.h
header-y += regdef.h
header-y += sysinfo.h
+generic-y += math128.h
diff --git a/arch/arm/include/asm/Kbuild b/arch/arm/include/asm/Kbuild
index 960abce..a55a259 100644
--- a/arch/arm/include/asm/Kbuild
+++ b/arch/arm/include/asm/Kbuild
@@ -18,3 +18,4 @@ generic-y += resource.h
generic-y += sections.h
generic-y += siginfo.h
generic-y += sizes.h
+generic-y += math128.h
diff --git a/arch/avr32/include/asm/Kbuild b/arch/avr32/include/asm/Kbuild
index 3136628..6c8e565 100644
--- a/arch/avr32/include/asm/Kbuild
+++ b/arch/avr32/include/asm/Kbuild
@@ -1,3 +1,4 @@
include include/asm-generic/Kbuild.asm

header-y += cachectl.h
+generic-y += math128.h
diff --git a/arch/blackfin/include/asm/Kbuild b/arch/blackfin/include/asm/Kbuild
index 5a0625a..6836e68 100644
--- a/arch/blackfin/include/asm/Kbuild
+++ b/arch/blackfin/include/asm/Kbuild
@@ -47,3 +47,4 @@ generic-y += xor.h
header-y += bfin_sport.h
header-y += cachectl.h
header-y += fixed_code.h
+generic-y += math128.h
diff --git a/arch/c6x/include/asm/Kbuild b/arch/c6x/include/asm/Kbuild
index 3af601e..0f84f29 100644
--- a/arch/c6x/include/asm/Kbuild
+++ b/arch/c6x/include/asm/Kbuild
@@ -51,3 +51,4 @@ generic-y += types.h
generic-y += ucontext.h
generic-y += user.h
generic-y += vga.h
+generic-y += math128.h
diff --git a/arch/cris/include/asm/Kbuild b/arch/cris/include/asm/Kbuild
index 956eea2..6f7f36c 100644
--- a/arch/cris/include/asm/Kbuild
+++ b/arch/cris/include/asm/Kbuild
@@ -8,3 +8,4 @@ header-y += etraxgpio.h
header-y += rs485.h
header-y += rtc.h
header-y += sync_serial.h
+generic-y += math128.h
diff --git a/arch/frv/include/asm/Kbuild b/arch/frv/include/asm/Kbuild
index 5be6663..8430351 100644
--- a/arch/frv/include/asm/Kbuild
+++ b/arch/frv/include/asm/Kbuild
@@ -2,3 +2,4 @@ include include/asm-generic/Kbuild.asm

header-y += registers.h
header-y += termios.h
+generic-y += math128.h
diff --git a/arch/h8300/include/asm/Kbuild b/arch/h8300/include/asm/Kbuild
index c68e168..a58a669 100644
--- a/arch/h8300/include/asm/Kbuild
+++ b/arch/h8300/include/asm/Kbuild
@@ -1 +1,2 @@
include include/asm-generic/Kbuild.asm
+generic-y += math128.h
diff --git a/arch/hexagon/include/asm/Kbuild b/arch/hexagon/include/asm/Kbuild
index 9aa17f1..df1203f 100644
--- a/arch/hexagon/include/asm/Kbuild
+++ b/arch/hexagon/include/asm/Kbuild
@@ -56,3 +56,4 @@ generic-y += types.h
generic-y += ucontext.h
generic-y += unaligned.h
generic-y += xor.h
+generic-y += math128.h
diff --git a/arch/ia64/include/asm/Kbuild b/arch/ia64/include/asm/Kbuild
index 241d1c5..e95a5dc 100644
--- a/arch/ia64/include/asm/Kbuild
+++ b/arch/ia64/include/asm/Kbuild
@@ -12,3 +12,4 @@ header-y += ptrace_offsets.h
header-y += rse.h
header-y += ucontext.h
header-y += ustack.h
+generic-y += math128.h
diff --git a/arch/m32r/include/asm/Kbuild b/arch/m32r/include/asm/Kbuild
index c68e168..a58a669 100644
--- a/arch/m32r/include/asm/Kbuild
+++ b/arch/m32r/include/asm/Kbuild
@@ -1 +1,2 @@
include include/asm-generic/Kbuild.asm
+generic-y += math128.h
diff --git a/arch/m68k/include/asm/Kbuild b/arch/m68k/include/asm/Kbuild
index 1a922fa..1c2a318 100644
--- a/arch/m68k/include/asm/Kbuild
+++ b/arch/m68k/include/asm/Kbuild
@@ -1,2 +1,3 @@
include include/asm-generic/Kbuild.asm
header-y += cachectl.h
+generic-y += math128.h
diff --git a/arch/microblaze/include/asm/Kbuild b/arch/microblaze/include/asm/Kbuild
index db5294c..6faf1fe 100644
--- a/arch/microblaze/include/asm/Kbuild
+++ b/arch/microblaze/include/asm/Kbuild
@@ -1,3 +1,4 @@
include include/asm-generic/Kbuild.asm

header-y += elf.h
+generic-y += math128.h
diff --git a/arch/mips/include/asm/Kbuild b/arch/mips/include/asm/Kbuild
index f53f9ca..c1e9992 100644
--- a/arch/mips/include/asm/Kbuild
+++ b/arch/mips/include/asm/Kbuild
@@ -3,3 +3,4 @@ include include/asm-generic/Kbuild.asm
header-y += cachectl.h
header-y += sgidefs.h
header-y += sysmips.h
+generic-y += math128.h
diff --git a/arch/mn10300/include/asm/Kbuild b/arch/mn10300/include/asm/Kbuild
index c68e168..a58a669 100644
--- a/arch/mn10300/include/asm/Kbuild
+++ b/arch/mn10300/include/asm/Kbuild
@@ -1 +1,2 @@
include include/asm-generic/Kbuild.asm
+generic-y += math128.h
diff --git a/arch/openrisc/include/asm/Kbuild b/arch/openrisc/include/asm/Kbuild
index c936483..c707d4b 100644
--- a/arch/openrisc/include/asm/Kbuild
+++ b/arch/openrisc/include/asm/Kbuild
@@ -66,3 +66,4 @@ generic-y += topology.h
generic-y += types.h
generic-y += ucontext.h
generic-y += user.h
+generic-y += math128.h
diff --git a/arch/parisc/include/asm/Kbuild b/arch/parisc/include/asm/Kbuild
index 19a434f..0663c2b 100644
--- a/arch/parisc/include/asm/Kbuild
+++ b/arch/parisc/include/asm/Kbuild
@@ -1,3 +1,4 @@
include include/asm-generic/Kbuild.asm

header-y += pdc.h
+generic-y += math128.h
diff --git a/arch/powerpc/include/asm/Kbuild b/arch/powerpc/include/asm/Kbuild
index 7e313f1..8565e89 100644
--- a/arch/powerpc/include/asm/Kbuild
+++ b/arch/powerpc/include/asm/Kbuild
@@ -36,3 +36,4 @@ header-y += ucontext.h
header-y += unistd.h

generic-y += rwsem.h
+generic-y += math128.h
diff --git a/arch/s390/include/asm/Kbuild b/arch/s390/include/asm/Kbuild
index 287d7bb..7947b7a 100644
--- a/arch/s390/include/asm/Kbuild
+++ b/arch/s390/include/asm/Kbuild
@@ -13,3 +13,4 @@ header-y += tape390.h
header-y += ucontext.h
header-y += vtoc.h
header-y += zcrypt.h
+generic-y += math128.h
diff --git a/arch/score/include/asm/Kbuild b/arch/score/include/asm/Kbuild
index b367abd..dba713d 100644
--- a/arch/score/include/asm/Kbuild
+++ b/arch/score/include/asm/Kbuild
@@ -1,3 +1,4 @@
include include/asm-generic/Kbuild.asm

header-y +=
+generic-y += math128.h
diff --git a/arch/sh/include/asm/Kbuild b/arch/sh/include/asm/Kbuild
index 7beb423..84af798 100644
--- a/arch/sh/include/asm/Kbuild
+++ b/arch/sh/include/asm/Kbuild
@@ -9,3 +9,4 @@ header-y += ptrace_32.h
header-y += ptrace_64.h
header-y += unistd_32.h
header-y += unistd_64.h
+generic-y += math128.h
diff --git a/arch/sparc/include/asm/Kbuild b/arch/sparc/include/asm/Kbuild
index 2c2e388..e153f78 100644
--- a/arch/sparc/include/asm/Kbuild
+++ b/arch/sparc/include/asm/Kbuild
@@ -21,3 +21,4 @@ generic-y += div64.h
generic-y += local64.h
generic-y += irq_regs.h
generic-y += local.h
+generic-y += math128.h
diff --git a/arch/tile/include/asm/Kbuild b/arch/tile/include/asm/Kbuild
index 0bb4264..0c1257f 100644
--- a/arch/tile/include/asm/Kbuild
+++ b/arch/tile/include/asm/Kbuild
@@ -42,3 +42,4 @@ generic-y += termios.h
generic-y += types.h
generic-y += ucontext.h
generic-y += xor.h
+generic-y += math128.h
diff --git a/arch/um/include/asm/Kbuild b/arch/um/include/asm/Kbuild
index fff2435..7644899 100644
--- a/arch/um/include/asm/Kbuild
+++ b/arch/um/include/asm/Kbuild
@@ -2,3 +2,4 @@ generic-y += bug.h cputime.h device.h emergency-restart.h futex.h hardirq.h
generic-y += hw_irq.h irq_regs.h kdebug.h percpu.h sections.h topology.h xor.h
generic-y += ftrace.h pci.h io.h param.h delay.h mutex.h current.h exec.h
generic-y += switch_to.h
+generic-y += math128.h
diff --git a/arch/unicore32/include/asm/Kbuild b/arch/unicore32/include/asm/Kbuild
index 34b789b..56e1880 100644
--- a/arch/unicore32/include/asm/Kbuild
+++ b/arch/unicore32/include/asm/Kbuild
@@ -58,3 +58,4 @@ generic-y += unaligned.h
generic-y += user.h
generic-y += vga.h
generic-y += xor.h
+generic-y += math128.h
diff --git a/arch/x86/include/asm/Kbuild b/arch/x86/include/asm/Kbuild
index f9c0d3b..86441b9 100644
--- a/arch/x86/include/asm/Kbuild
+++ b/arch/x86/include/asm/Kbuild
@@ -26,3 +26,4 @@ header-y += vsyscall.h
genhdr-y += unistd_32.h
genhdr-y += unistd_64.h
genhdr-y += unistd_x32.h
+generic-y += math128.h
diff --git a/arch/xtensa/include/asm/Kbuild b/arch/xtensa/include/asm/Kbuild
index c68e168..a58a669 100644
--- a/arch/xtensa/include/asm/Kbuild
+++ b/arch/xtensa/include/asm/Kbuild
@@ -1 +1,2 @@
include include/asm-generic/Kbuild.asm
+generic-y += math128.h
diff --git a/include/asm-generic/math128.h b/include/asm-generic/math128.h
new file mode 100644
index 0000000..3582691
--- /dev/null
+++ b/include/asm-generic/math128.h
@@ -0,0 +1,4 @@
+#ifndef _ASM_GENERIC_MATH128_H
+#define _ASM_GENERIC_MATH128_H
+
+#endif /*_ASM_GENERIC_MATH128_H */
diff --git a/include/linux/math128.h b/include/linux/math128.h
new file mode 100644
index 0000000..5b0eef6
--- /dev/null
+++ b/include/linux/math128.h
@@ -0,0 +1,180 @@
+#ifndef _LINUX_MATH128_H
+#define _LINUX_MATH128_H
+
+#include <linux/types.h>
+
+typedef union {
+ struct {
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+ u64 lo, hi;
+#else
+ u64 hi, lo;
+#endif
+ };
+#ifdef __SIZEOF_INT128__ /* gcc-4.6+ */
+ unsigned __int128 val;
+#endif
+} u128;
+
+#define U128_INIT(_hi, _lo) (u128){{ .hi = (_hi), .lo = (_lo) }}
+
+#include <asm/math128.h>
+
+/*
+ * Make usage of __int128 dependent on arch code so they can
+ * judge if gcc is doing the right thing for them and can over-ride
+ * any funnies.
+ */
+
+#ifndef ARCH_HAS_INT128
+
+#ifndef add_u128
+static inline u128 add_u128(u128 a, u128 b)
+{
+ a.hi += b.hi;
+ a.lo += b.lo;
+ if (a.lo < b.lo)
+ a.hi++;
+
+ return a;
+}
+#endif /* add_u128 */
+
+#ifndef mul_u64_u64
+extern u128 mul_u64_u64(u64 a, u64 b);
+#endif
+
+#ifndef mul_u64_u32_shr
+static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
+{
+ u32 ah, al;
+ u64 t1, t2;
+
+ ah = a >> 32;
+ al = a;
+
+ t1 = ((u64)al * mul) >> shift;
+ t2 = ((u64)ah * mul) << (32 - shift);
+
+ return t1 + t2;
+}
+#endif /* mul_u64_u32_shr */
+
+#ifndef shl_u128
+static inline u128 shl_u128(u128 x, unsigned int n)
+{
+ u128 res;
+
+ if (!n)
+ return x;
+
+ if (n < 64) {
+ res.hi = x.hi << n;
+ res.hi |= x.lo >> (64 - n);
+ res.lo = x.lo << n;
+ } else {
+ res.lo = 0;
+ res.hi = x.lo << (n - 64);
+ }
+
+ return res;
+}
+#endif /* shl_u128 */
+
+#ifndef shr_u128
+static inline u128 shr_u128(u128 x, unsigned int n)
+{
+ u128 res;
+
+ if (!n)
+ return x;
+
+ if (n < 64) {
+ res.lo = x.lo >> n;
+ res.lo |= x.hi << (64 - n);
+ res.hi = x.hi >> n;
+ } else {
+ res.hi = 0;
+ res.lo = x.hi >> (n - 64);
+ }
+
+ return res;
+}
+#endif /* shr_u128 */
+
+#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 */
+
+#else /* ARCH_HAS_INT128 */
+
+#ifndef add_u128
+static inline u128 add_u128(u128 a, u128 b)
+{
+ a.val += b.val;
+ return a;
+}
+#endif /* add_u128 */
+
+#ifndef mul_u64_u64
+static inline u128 mul_u64_u64(u64 a, u64 b)
+{
+ u128 res;
+
+ res.val = a;
+ res.val *= b;
+
+ return res;
+}
+#define mul_u64_u64 mul_u64_u64
+#endif
+
+#ifndef mul_u64_u32_shr
+static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
+{
+ return (u64)(((unsigned __int128)a * mul) >> shift);
+}
+#endif /* mul_u64_u32_shr */
+
+#ifndef shl_u128
+static inline u128 shl_u128(u128 x, unsigned int n)
+{
+ x.val <<= n;
+ return x;
+}
+#endif /* shl_u128 */
+
+#ifndef shr_u128
+static inline u128 shr_u128(u128 x, unsigned int n)
+{
+ x.val >>= n;
+ return x;
+}
+#endif /* shr_u128 */
+
+#ifndef cmp_u128
+static inline int cmp_u128(u128 a, u128 b)
+{
+ if (a.val < b.val)
+ return -1;
+ if (a.val > b.val)
+ return 1;
+ return 0;
+}
+#endif /* cmp_u128 */
+
+#endif /* ARCH_HAS_INT128 */
+
+#endif /* _LINUX_MATH128_H */
diff --git a/lib/Makefile b/lib/Makefile
index 74290c9..08014b4 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
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
diff --git a/lib/math128.c b/lib/math128.c
new file mode 100644
index 0000000..55b123a
--- /dev/null
+++ b/lib/math128.c
@@ -0,0 +1,40 @@
+#include <linux/math128.h>
+
+#ifndef mul_u64_u64
+/*
+ * a * b = (ah * 2^32 + al) * (bh * 2^32 + bl) =
+ * ah*bh * 2^64 + (ah*bl + bh*al) * 2^32 + al*bl
+ */
+u128 mul_u64_u64(u64 a, u64 b)
+{
+ u128 t1, t2, t3, t4;
+ u32 ah, al;
+ u32 bh, bl;
+
+ ah = a >> 32;
+ al = a;
+
+ bh = b >> 32;
+ bl = b;
+
+ t1.lo = 0;
+ t1.hi = (u64)ah * bh;
+
+ t2.lo = (u64)ah * bl;
+ t2.hi = t2.lo >> 32;
+ t2.lo <<= 32;
+
+ t3.lo = (u64)al * bh;
+ t3.hi = t3.lo >> 32;
+ t3.lo <<= 32;
+
+ t4.lo = (u64)al * bl;
+ t4.hi = 0;
+
+ t1 = add_u128(t1, t2);
+ t1 = add_u128(t1, t3);
+ t1 = add_u128(t1, t4);
+
+ return t1;
+}
+#endif /* mul_u64_u64 */
--
1.7.9.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Next message: J. Bruce Fields: "Re: [PATCH] NFSd: set nfsd_serv to NULL after service destruction"
Previous message: Juri Lelli: "[PATCH 03/15] sched: add sched_class->task_dead."
In reply to: Juri Lelli: "[PATCH 03/15] sched: add sched_class->task_dead."
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]