* [patch V4 00/31] bitops: add parity functions
@ 2016-05-11 8:25 zengzhaoxiu
2016-05-11 8:25 ` zengzhaoxiu
2016-05-11 8:47 ` [patch V4 01/31] " zengzhaoxiu
0 siblings, 2 replies; 4+ messages in thread
From: zengzhaoxiu @ 2016-05-11 8:25 UTC (permalink / raw)
To: akpm, linux, bp, ulrik.debie-os, sam, davem, ddaney.cavm, joe,
computersforpeace
Cc: linux-kernel, linux-arch, linux-alpha, adi-buildroot-devel,
linux-ia64, linux-mips, linux-am33-list, linuxppc-dev, sparclinux,
qat-linux, linux-crypto, linux-edac, linux-media, linux-mtd,
netdev, linux-scsi, linux-nfs, linux-mediatek, Zhaoxiu Zeng
From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
When I do "grep parity -r linux", I found many parity calculations
distributed in many drivers.
This patch series does:
1. provide generic and architecture-specific parity calculations
2. remove drivers' local parity calculations, use bitops' parity
functions instead
3. replace "hweightN(x) & 1" with "parityN(x)" to improve readability,
and improve performance on some CPUs that without popcount support
I did not use GCC's __builtin_parity* functions, based on the following reasons:
1. I don't know where to identify which version of GCC from the beginning
supported __builtin_parity for the architecture.
2. For the architecture that doesn't has popcount instruction, GCC instead use
"call __paritysi2" (__paritydi2 for 64-bits). So if use __builtin_parity, we must
provide __paritysi2 and __paritydi2 functions for these architectures.
Additionally, parity4,8,16 might be "__builtin_parity(x & mask)", but the "& mask"
operation is totally unnecessary.
3. For the architecture that has popcount instruction, we do the same things as GCC.
4. For powerpc, sparc, and x86, we do runtime patching to use popcount instruction
if the CPU support.
I have compiled successfully with x86_64_defconfig, i386_defconfig, pseries_defconfig
and sparc64_defconfig.
Changes to V3:
- Remove "odd" and "even" from documents. The function parityN returns whether an odd
or even number of bits are on in a N-bit word, does not involve the definition of
odd/even parity. Is it an odd or even parity checking, depends on the caller's context.
- Replace "hweightN(x) % 2" with "parityN(x)" in crypto/sahara.c and edac/amd64_edac.c
- Use PARITY_MAGIC instead of 0x6996 in powerpc's parity_64.S
- Use PARITY_MAGIC instead of 0x6996 in sparc's parity.S
- Pick up ACKs
Changes to v2:
- X86, remove custom calling convention, use inline asm
- Add constant PARITY_MAGIC (proposals by Sam Ravnborg)
- Add include/asm-generic/bitops/popc-parity.h (proposals by Chris Metcalf)
- Tile uses popc-parity.h directly
- Mips uses popc-parity.h if has usable __builtin_popcount
- Add few comments in powerpc's and sparc's parity.S
Changes to v1:
- Add runtime patching for powerpc, sparc, and x86
- Avr32 use grenric parity too
- Fix error in ssfdc's patch, and add commit message
- Don't change the original code composition of adxrs450.c
- Directly assignement to phy_cap.parity in drivers/scsi/isci/phy.c
Regards,
=== diffstat ===
Zhaoxiu Zeng (31):
bitops: add parity functions
bitops: Include generic parity.h in some architectures' bitops.h
bitops: Add alpha-specific parity functions
bitops: Add blackfin-specific parity functions
bitops: Add ia-specific parity functions
bitops: Tile and MIPS (if has usable __builtin_popcount) use popcount
parity functions
bitops: Add powerpc-specific parity functions
bitops: Add sparc-specific parity functions
bitops: Add x86-specific parity functions
sunrpc: use parity8
mips: use parity functions in cerr-sb1.c
lib: bch: use parity32
media: use parity8 in vivid-vbi-gen.c
media: use parity functions in saa7115
input: use parity32 in grip_mp
input: use parity64 in sidewinder
input: use parity16 in ams_delta_serio
scsi: use parity32 in isci's phy
mtd: use parity16 in ssfdc
mtd: use parity functions in inftlcore
crypto: use parity functions in qat_hal
mtd: use parity16 in sm_ftl
ethernet: use parity8 in sun/niu.c
input: use parity8 in pcips2
input: use parity8 in sa1111ps2
iio: use parity32 in adxrs450
serial: use parity32 in max3100
input: use parity8 in elantech
ethernet: use parity8 in broadcom/tg3.c
crypto: use parity_long is sahara.c
edac: use parity8 in amd64_edac.c
arch/alpha/include/asm/bitops.h | 27 +++++
arch/arc/include/asm/bitops.h | 1 +
arch/arm/include/asm/bitops.h | 1 +
arch/arm64/include/asm/bitops.h | 1 +
arch/avr32/include/asm/bitops.h | 1 +
arch/blackfin/include/asm/bitops.h | 31 ++++++
arch/c6x/include/asm/bitops.h | 1 +
arch/cris/include/asm/bitops.h | 1 +
arch/frv/include/asm/bitops.h | 1 +
arch/h8300/include/asm/bitops.h | 1 +
arch/hexagon/include/asm/bitops.h | 1 +
arch/ia64/include/asm/bitops.h | 31 ++++++
arch/m32r/include/asm/bitops.h | 1 +
arch/m68k/include/asm/bitops.h | 1 +
arch/metag/include/asm/bitops.h | 1 +
arch/mips/include/asm/bitops.h | 7 ++
arch/mips/mm/cerr-sb1.c | 67 ++++---------
arch/mn10300/include/asm/bitops.h | 1 +
arch/openrisc/include/asm/bitops.h | 1 +
arch/parisc/include/asm/bitops.h | 1 +
arch/powerpc/include/asm/bitops.h | 11 +++
arch/powerpc/lib/Makefile | 2 +-
arch/powerpc/lib/parity_64.S | 143 +++++++++++++++++++++++++++
arch/powerpc/lib/ppc_ksyms.c | 5 +
arch/s390/include/asm/bitops.h | 1 +
arch/sh/include/asm/bitops.h | 1 +
arch/sparc/include/asm/bitops_32.h | 1 +
arch/sparc/include/asm/bitops_64.h | 18 ++++
arch/sparc/kernel/sparc_ksyms_64.c | 6 ++
arch/sparc/lib/Makefile | 2 +-
arch/sparc/lib/parity.S | 129 ++++++++++++++++++++++++
arch/tile/include/asm/bitops.h | 2 +
arch/x86/include/asm/arch_hweight.h | 5 +
arch/x86/include/asm/arch_parity.h | 117 ++++++++++++++++++++++
arch/x86/include/asm/bitops.h | 4 +-
arch/xtensa/include/asm/bitops.h | 1 +
drivers/crypto/qat/qat_common/qat_hal.c | 32 ++----
drivers/crypto/sahara.c | 2 +-
drivers/edac/amd64_edac.c | 2 +-
drivers/iio/gyro/adxrs450.c | 4 +-
drivers/input/joystick/grip_mp.c | 16 +--
drivers/input/joystick/sidewinder.c | 24 +----
drivers/input/mouse/elantech.c | 10 +-
drivers/input/mouse/elantech.h | 1 -
drivers/input/serio/ams_delta_serio.c | 8 +-
drivers/input/serio/pcips2.c | 2 +-
drivers/input/serio/sa1111ps2.c | 2 +-
drivers/media/i2c/saa7115.c | 17 +---
drivers/media/platform/vivid/vivid-vbi-gen.c | 9 +-
drivers/mtd/inftlcore.c | 17 +---
drivers/mtd/sm_ftl.c | 5 +-
drivers/mtd/ssfdc.c | 31 ++----
drivers/net/ethernet/broadcom/tg3.c | 6 +-
drivers/net/ethernet/sun/niu.c | 10 +-
drivers/scsi/isci/phy.c | 15 +--
drivers/tty/serial/max3100.c | 2 +-
include/asm-generic/bitops.h | 1 +
include/asm-generic/bitops/arch_parity.h | 39 ++++++++
include/asm-generic/bitops/const_parity.h | 36 +++++++
include/asm-generic/bitops/parity.h | 7 ++
include/asm-generic/bitops/popc-parity.h | 32 ++++++
include/linux/bitops.h | 10 ++
lib/bch.c | 14 +--
net/sunrpc/auth_gss/gss_krb5_keys.c | 6 +-
64 files changed, 749 insertions(+), 237 deletions(-)
create mode 100644 arch/powerpc/lib/parity_64.S
create mode 100644 arch/sparc/lib/parity.S
create mode 100644 arch/x86/include/asm/arch_parity.h
create mode 100644 include/asm-generic/bitops/arch_parity.h
create mode 100644 include/asm-generic/bitops/const_parity.h
create mode 100644 include/asm-generic/bitops/parity.h
create mode 100644 include/asm-generic/bitops/popc-parity.h
--
2.7.4
^ permalink raw reply [flat|nested] 4+ messages in thread
* [patch V4 00/31] bitops: add parity functions
2016-05-11 8:25 [patch V4 00/31] bitops: add parity functions zengzhaoxiu
@ 2016-05-11 8:25 ` zengzhaoxiu
2016-05-11 8:47 ` [patch V4 01/31] " zengzhaoxiu
1 sibling, 0 replies; 4+ messages in thread
From: zengzhaoxiu @ 2016-05-11 8:25 UTC (permalink / raw)
To: akpm, linux, bp, ulrik.debie-os, sam, davem, ddaney.cavm, joe,
computersforpeace
Cc: linux-kernel, linux-arch, linux-alpha, adi-buildroot-devel,
linux-ia64, linux-mips, linux-am33-list, linuxppc-dev, sparclinux,
qat-linux, linux-crypto, linux-edac, linux-media, linux-mtd,
netdev, linux-scsi, linux-nfs, linux-mediatek, Zhaoxiu Zeng
From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
When I do "grep parity -r linux", I found many parity calculations
distributed in many drivers.
This patch series does:
1. provide generic and architecture-specific parity calculations
2. remove drivers' local parity calculations, use bitops' parity
functions instead
3. replace "hweightN(x) & 1" with "parityN(x)" to improve readability,
and improve performance on some CPUs that without popcount support
I did not use GCC's __builtin_parity* functions, based on the following reasons:
1. I don't know where to identify which version of GCC from the beginning
supported __builtin_parity for the architecture.
2. For the architecture that doesn't has popcount instruction, GCC instead use
"call __paritysi2" (__paritydi2 for 64-bits). So if use __builtin_parity, we must
provide __paritysi2 and __paritydi2 functions for these architectures.
Additionally, parity4,8,16 might be "__builtin_parity(x & mask)", but the "& mask"
operation is totally unnecessary.
3. For the architecture that has popcount instruction, we do the same things as GCC.
4. For powerpc, sparc, and x86, we do runtime patching to use popcount instruction
if the CPU support.
I have compiled successfully with x86_64_defconfig, i386_defconfig, pseries_defconfig
and sparc64_defconfig.
Changes to V3:
- Remove "odd" and "even" from documents. The function parityN returns whether an odd
or even number of bits are on in a N-bit word, does not involve the definition of
odd/even parity. Is it an odd or even parity checking, depends on the caller's context.
- Replace "hweightN(x) % 2" with "parityN(x)" in crypto/sahara.c and edac/amd64_edac.c
- Use PARITY_MAGIC instead of 0x6996 in powerpc's parity_64.S
- Use PARITY_MAGIC instead of 0x6996 in sparc's parity.S
- Pick up ACKs
Changes to v2:
- X86, remove custom calling convention, use inline asm
- Add constant PARITY_MAGIC (proposals by Sam Ravnborg)
- Add include/asm-generic/bitops/popc-parity.h (proposals by Chris Metcalf)
- Tile uses popc-parity.h directly
- Mips uses popc-parity.h if has usable __builtin_popcount
- Add few comments in powerpc's and sparc's parity.S
Changes to v1:
- Add runtime patching for powerpc, sparc, and x86
- Avr32 use grenric parity too
- Fix error in ssfdc's patch, and add commit message
- Don't change the original code composition of adxrs450.c
- Directly assignement to phy_cap.parity in drivers/scsi/isci/phy.c
Regards,
=== diffstat ===
Zhaoxiu Zeng (31):
bitops: add parity functions
bitops: Include generic parity.h in some architectures' bitops.h
bitops: Add alpha-specific parity functions
bitops: Add blackfin-specific parity functions
bitops: Add ia-specific parity functions
bitops: Tile and MIPS (if has usable __builtin_popcount) use popcount
parity functions
bitops: Add powerpc-specific parity functions
bitops: Add sparc-specific parity functions
bitops: Add x86-specific parity functions
sunrpc: use parity8
mips: use parity functions in cerr-sb1.c
lib: bch: use parity32
media: use parity8 in vivid-vbi-gen.c
media: use parity functions in saa7115
input: use parity32 in grip_mp
input: use parity64 in sidewinder
input: use parity16 in ams_delta_serio
scsi: use parity32 in isci's phy
mtd: use parity16 in ssfdc
mtd: use parity functions in inftlcore
crypto: use parity functions in qat_hal
mtd: use parity16 in sm_ftl
ethernet: use parity8 in sun/niu.c
input: use parity8 in pcips2
input: use parity8 in sa1111ps2
iio: use parity32 in adxrs450
serial: use parity32 in max3100
input: use parity8 in elantech
ethernet: use parity8 in broadcom/tg3.c
crypto: use parity_long is sahara.c
edac: use parity8 in amd64_edac.c
arch/alpha/include/asm/bitops.h | 27 +++++
arch/arc/include/asm/bitops.h | 1 +
arch/arm/include/asm/bitops.h | 1 +
arch/arm64/include/asm/bitops.h | 1 +
arch/avr32/include/asm/bitops.h | 1 +
arch/blackfin/include/asm/bitops.h | 31 ++++++
arch/c6x/include/asm/bitops.h | 1 +
arch/cris/include/asm/bitops.h | 1 +
arch/frv/include/asm/bitops.h | 1 +
arch/h8300/include/asm/bitops.h | 1 +
arch/hexagon/include/asm/bitops.h | 1 +
arch/ia64/include/asm/bitops.h | 31 ++++++
arch/m32r/include/asm/bitops.h | 1 +
arch/m68k/include/asm/bitops.h | 1 +
arch/metag/include/asm/bitops.h | 1 +
arch/mips/include/asm/bitops.h | 7 ++
arch/mips/mm/cerr-sb1.c | 67 ++++---------
arch/mn10300/include/asm/bitops.h | 1 +
arch/openrisc/include/asm/bitops.h | 1 +
arch/parisc/include/asm/bitops.h | 1 +
arch/powerpc/include/asm/bitops.h | 11 +++
arch/powerpc/lib/Makefile | 2 +-
arch/powerpc/lib/parity_64.S | 143 +++++++++++++++++++++++++++
arch/powerpc/lib/ppc_ksyms.c | 5 +
arch/s390/include/asm/bitops.h | 1 +
arch/sh/include/asm/bitops.h | 1 +
arch/sparc/include/asm/bitops_32.h | 1 +
arch/sparc/include/asm/bitops_64.h | 18 ++++
arch/sparc/kernel/sparc_ksyms_64.c | 6 ++
arch/sparc/lib/Makefile | 2 +-
arch/sparc/lib/parity.S | 129 ++++++++++++++++++++++++
arch/tile/include/asm/bitops.h | 2 +
arch/x86/include/asm/arch_hweight.h | 5 +
arch/x86/include/asm/arch_parity.h | 117 ++++++++++++++++++++++
arch/x86/include/asm/bitops.h | 4 +-
arch/xtensa/include/asm/bitops.h | 1 +
drivers/crypto/qat/qat_common/qat_hal.c | 32 ++----
drivers/crypto/sahara.c | 2 +-
drivers/edac/amd64_edac.c | 2 +-
drivers/iio/gyro/adxrs450.c | 4 +-
drivers/input/joystick/grip_mp.c | 16 +--
drivers/input/joystick/sidewinder.c | 24 +----
drivers/input/mouse/elantech.c | 10 +-
drivers/input/mouse/elantech.h | 1 -
drivers/input/serio/ams_delta_serio.c | 8 +-
drivers/input/serio/pcips2.c | 2 +-
drivers/input/serio/sa1111ps2.c | 2 +-
drivers/media/i2c/saa7115.c | 17 +---
drivers/media/platform/vivid/vivid-vbi-gen.c | 9 +-
drivers/mtd/inftlcore.c | 17 +---
drivers/mtd/sm_ftl.c | 5 +-
drivers/mtd/ssfdc.c | 31 ++----
drivers/net/ethernet/broadcom/tg3.c | 6 +-
drivers/net/ethernet/sun/niu.c | 10 +-
drivers/scsi/isci/phy.c | 15 +--
drivers/tty/serial/max3100.c | 2 +-
include/asm-generic/bitops.h | 1 +
include/asm-generic/bitops/arch_parity.h | 39 ++++++++
include/asm-generic/bitops/const_parity.h | 36 +++++++
include/asm-generic/bitops/parity.h | 7 ++
include/asm-generic/bitops/popc-parity.h | 32 ++++++
include/linux/bitops.h | 10 ++
lib/bch.c | 14 +--
net/sunrpc/auth_gss/gss_krb5_keys.c | 6 +-
64 files changed, 749 insertions(+), 237 deletions(-)
create mode 100644 arch/powerpc/lib/parity_64.S
create mode 100644 arch/sparc/lib/parity.S
create mode 100644 arch/x86/include/asm/arch_parity.h
create mode 100644 include/asm-generic/bitops/arch_parity.h
create mode 100644 include/asm-generic/bitops/const_parity.h
create mode 100644 include/asm-generic/bitops/parity.h
create mode 100644 include/asm-generic/bitops/popc-parity.h
--
2.7.4
^ permalink raw reply [flat|nested] 4+ messages in thread
* [patch V4 01/31] bitops: add parity functions
2016-05-11 8:25 [patch V4 00/31] bitops: add parity functions zengzhaoxiu
2016-05-11 8:25 ` zengzhaoxiu
@ 2016-05-11 8:47 ` zengzhaoxiu
2016-05-11 14:32 ` Martin Kepplinger
1 sibling, 1 reply; 4+ messages in thread
From: zengzhaoxiu @ 2016-05-11 8:47 UTC (permalink / raw)
To: linux-kernel, linux, ulrik.debie-os
Cc: Zhaoxiu Zeng, Arnd Bergmann, Martin Kepplinger, Andrew Morton,
Sasha Levin, Ingo Molnar, Denys Vlasenko, linux-arch
From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
Add generic parity functions, adapted from
"https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel".
The function parityN returns whether an odd or even number of bits are on
in a N-bit word.
Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
---
include/asm-generic/bitops.h | 1 +
include/asm-generic/bitops/arch_parity.h | 39 +++++++++++++++++++++++++++++++
include/asm-generic/bitops/const_parity.h | 36 ++++++++++++++++++++++++++++
include/asm-generic/bitops/parity.h | 7 ++++++
include/asm-generic/bitops/popc-parity.h | 32 +++++++++++++++++++++++++
include/linux/bitops.h | 10 ++++++++
6 files changed, 125 insertions(+)
create mode 100644 include/asm-generic/bitops/arch_parity.h
create mode 100644 include/asm-generic/bitops/const_parity.h
create mode 100644 include/asm-generic/bitops/parity.h
create mode 100644 include/asm-generic/bitops/popc-parity.h
diff --git a/include/asm-generic/bitops.h b/include/asm-generic/bitops.h
index dcdcacf..d85722f 100644
--- a/include/asm-generic/bitops.h
+++ b/include/asm-generic/bitops.h
@@ -27,6 +27,7 @@
#include <asm-generic/bitops/sched.h>
#include <asm-generic/bitops/ffs.h>
#include <asm-generic/bitops/hweight.h>
+#include <asm-generic/bitops/parity.h>
#include <asm-generic/bitops/lock.h>
#include <asm-generic/bitops/atomic.h>
diff --git a/include/asm-generic/bitops/arch_parity.h b/include/asm-generic/bitops/arch_parity.h
new file mode 100644
index 0000000..813e152
--- /dev/null
+++ b/include/asm-generic/bitops/arch_parity.h
@@ -0,0 +1,39 @@
+#ifndef _ASM_GENERIC_BITOPS_ARCH_PARITY_H_
+#define _ASM_GENERIC_BITOPS_ARCH_PARITY_H_
+
+#include <asm/types.h>
+
+/*
+ * Refrence to 'https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel'.
+ */
+
+static inline unsigned int __arch_parity4(unsigned int w)
+{
+ w &= 0xf;
+ return ((PARITY_MAGIC) >> w) & 1;
+}
+
+static inline unsigned int __arch_parity8(unsigned int w)
+{
+ w ^= w >> 4;
+ return __arch_parity4(w);
+}
+
+static inline unsigned int __arch_parity16(unsigned int w)
+{
+ w ^= w >> 8;
+ return __arch_parity8(w);
+}
+
+static inline unsigned int __arch_parity32(unsigned int w)
+{
+ w ^= w >> 16;
+ return __arch_parity16(w);
+}
+
+static inline unsigned int __arch_parity64(__u64 w)
+{
+ return __arch_parity32((unsigned int)(w >> 32) ^ (unsigned int)w);
+}
+
+#endif /* _ASM_GENERIC_BITOPS_ARCH_PARITY_H_ */
diff --git a/include/asm-generic/bitops/const_parity.h b/include/asm-generic/bitops/const_parity.h
new file mode 100644
index 0000000..3970546
--- /dev/null
+++ b/include/asm-generic/bitops/const_parity.h
@@ -0,0 +1,36 @@
+#ifndef _ASM_GENERIC_BITOPS_CONST_PARITY_H_
+#define _ASM_GENERIC_BITOPS_CONST_PARITY_H_
+
+/*
+ * Compile time versions of __arch_parityN()
+ */
+#define __const_parity4(w) (((PARITY_MAGIC) >> ((w) & 0xf)) & 1)
+#define __const_parity8(w) (__const_parity4((w) ^ ((w) >> 4)))
+#define __const_parity16(w) (__const_parity8((w) ^ ((w) >> 8)))
+#define __const_parity32(w) (__const_parity16((w) ^ ((w) >> 16)))
+#define __const_parity64(w) (__const_parity32((w) ^ ((w) >> 32)))
+
+/*
+ * Generic interface.
+ */
+#define parity4(w) (__builtin_constant_p(w) ? __const_parity4(w) : __arch_parity4(w))
+#define parity8(w) (__builtin_constant_p(w) ? __const_parity8(w) : __arch_parity8(w))
+#define parity16(w) (__builtin_constant_p(w) ? __const_parity16(w) : __arch_parity16(w))
+#define parity32(w) (__builtin_constant_p(w) ? __const_parity32(w) : __arch_parity32(w))
+#define parity64(w) (__builtin_constant_p(w) ? __const_parity64(w) : __arch_parity64(w))
+
+/*
+ * Interface for known constant arguments
+ */
+#define PARITY4(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity4(w))
+#define PARITY8(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity8(w))
+#define PARITY16(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity16(w))
+#define PARITY32(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity32(w))
+#define PARITY64(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity64(w))
+
+/*
+ * Type invariant interface to the compile time constant parity functions.
+ */
+#define PARITY(w) PARITY64((u64)(w))
+
+#endif /* _ASM_GENERIC_BITOPS_CONST_PARITY_H_ */
diff --git a/include/asm-generic/bitops/parity.h b/include/asm-generic/bitops/parity.h
new file mode 100644
index 0000000..a91dce7
--- /dev/null
+++ b/include/asm-generic/bitops/parity.h
@@ -0,0 +1,7 @@
+#ifndef _ASM_GENERIC_BITOPS_PARITY_H_
+#define _ASM_GENERIC_BITOPS_PARITY_H_
+
+#include <asm-generic/bitops/arch_parity.h>
+#include <asm-generic/bitops/const_parity.h>
+
+#endif /* _ASM_GENERIC_BITOPS_PARITY_H_ */
diff --git a/include/asm-generic/bitops/popc-parity.h b/include/asm-generic/bitops/popc-parity.h
new file mode 100644
index 0000000..bf05999
--- /dev/null
+++ b/include/asm-generic/bitops/popc-parity.h
@@ -0,0 +1,32 @@
+#ifndef _ASM_GENERIC_BITOPS_POPC_PARITY_H_
+#define _ASM_GENERIC_BITOPS_POPC_PARITY_H_
+
+#include <asm/types.h>
+
+static inline unsigned int __arch_parity32(unsigned int w)
+{
+ return __builtin_popcount(w) & 1;
+}
+
+static inline unsigned int __arch_parity16(unsigned int w)
+{
+ return __arch_parity32(w & 0xffff);
+}
+
+static inline unsigned int __arch_parity8(unsigned int w)
+{
+ return __arch_parity32(w & 0xff);
+}
+
+static inline unsigned int __arch_parity4(unsigned int w)
+{
+ return __arch_parity32(w & 0xf);
+}
+
+static inline unsigned int __arch_parity64(__u64 w)
+{
+ return (unsigned int)__builtin_popcountll(w) & 1;
+}
+
+#endif
+
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index defeaac..c3ea19e 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -30,6 +30,11 @@ extern unsigned int __sw_hweight32(unsigned int w);
extern unsigned long __sw_hweight64(__u64 w);
/*
+ * a miniature 16-bit parity-table of 4-bits number
+ */
+#define PARITY_MAGIC 0x6996
+
+/*
* Include this here because some architectures need generic_ffs/fls in
* scope
*/
@@ -80,6 +85,11 @@ static __always_inline unsigned long hweight_long(unsigned long w)
return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
}
+static __always_inline unsigned int parity_long(unsigned long w)
+{
+ return sizeof(w) == 4 ? parity32(w) : parity64(w);
+}
+
/**
* rol64 - rotate a 64-bit value left
* @word: value to rotate
--
2.7.4
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [patch V4 01/31] bitops: add parity functions
2016-05-11 8:47 ` [patch V4 01/31] " zengzhaoxiu
@ 2016-05-11 14:32 ` Martin Kepplinger
0 siblings, 0 replies; 4+ messages in thread
From: Martin Kepplinger @ 2016-05-11 14:32 UTC (permalink / raw)
To: zengzhaoxiu, linux-kernel, linux, ulrik.debie-os
Cc: Zhaoxiu Zeng, Arnd Bergmann, Andrew Morton, Sasha Levin,
Ingo Molnar, Denys Vlasenko, linux-arch
Am 2016-05-11 um 10:47 schrieb zengzhaoxiu@163.com:
> From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
>
> Add generic parity functions, adapted from
> "https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel".
>
> The function parityN returns whether an odd or even number of bits are on
> in a N-bit word.
>
> Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
> ---
This won't be up to me, but I'd appreciate to see all 31 patches
together without having to look for them; I guess I'm not alone.
thanks
martin
> include/asm-generic/bitops.h | 1 +
> include/asm-generic/bitops/arch_parity.h | 39 +++++++++++++++++++++++++++++++
> include/asm-generic/bitops/const_parity.h | 36 ++++++++++++++++++++++++++++
> include/asm-generic/bitops/parity.h | 7 ++++++
> include/asm-generic/bitops/popc-parity.h | 32 +++++++++++++++++++++++++
> include/linux/bitops.h | 10 ++++++++
> 6 files changed, 125 insertions(+)
> create mode 100644 include/asm-generic/bitops/arch_parity.h
> create mode 100644 include/asm-generic/bitops/const_parity.h
> create mode 100644 include/asm-generic/bitops/parity.h
> create mode 100644 include/asm-generic/bitops/popc-parity.h
>
> diff --git a/include/asm-generic/bitops.h b/include/asm-generic/bitops.h
> index dcdcacf..d85722f 100644
> --- a/include/asm-generic/bitops.h
> +++ b/include/asm-generic/bitops.h
> @@ -27,6 +27,7 @@
> #include <asm-generic/bitops/sched.h>
> #include <asm-generic/bitops/ffs.h>
> #include <asm-generic/bitops/hweight.h>
> +#include <asm-generic/bitops/parity.h>
> #include <asm-generic/bitops/lock.h>
>
> #include <asm-generic/bitops/atomic.h>
> diff --git a/include/asm-generic/bitops/arch_parity.h b/include/asm-generic/bitops/arch_parity.h
> new file mode 100644
> index 0000000..813e152
> --- /dev/null
> +++ b/include/asm-generic/bitops/arch_parity.h
> @@ -0,0 +1,39 @@
> +#ifndef _ASM_GENERIC_BITOPS_ARCH_PARITY_H_
> +#define _ASM_GENERIC_BITOPS_ARCH_PARITY_H_
> +
> +#include <asm/types.h>
> +
> +/*
> + * Refrence to 'https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel'.
> + */
> +
> +static inline unsigned int __arch_parity4(unsigned int w)
> +{
> + w &= 0xf;
> + return ((PARITY_MAGIC) >> w) & 1;
> +}
> +
> +static inline unsigned int __arch_parity8(unsigned int w)
> +{
> + w ^= w >> 4;
> + return __arch_parity4(w);
> +}
> +
> +static inline unsigned int __arch_parity16(unsigned int w)
> +{
> + w ^= w >> 8;
> + return __arch_parity8(w);
> +}
> +
> +static inline unsigned int __arch_parity32(unsigned int w)
> +{
> + w ^= w >> 16;
> + return __arch_parity16(w);
> +}
> +
> +static inline unsigned int __arch_parity64(__u64 w)
> +{
> + return __arch_parity32((unsigned int)(w >> 32) ^ (unsigned int)w);
> +}
> +
> +#endif /* _ASM_GENERIC_BITOPS_ARCH_PARITY_H_ */
> diff --git a/include/asm-generic/bitops/const_parity.h b/include/asm-generic/bitops/const_parity.h
> new file mode 100644
> index 0000000..3970546
> --- /dev/null
> +++ b/include/asm-generic/bitops/const_parity.h
> @@ -0,0 +1,36 @@
> +#ifndef _ASM_GENERIC_BITOPS_CONST_PARITY_H_
> +#define _ASM_GENERIC_BITOPS_CONST_PARITY_H_
> +
> +/*
> + * Compile time versions of __arch_parityN()
> + */
> +#define __const_parity4(w) (((PARITY_MAGIC) >> ((w) & 0xf)) & 1)
> +#define __const_parity8(w) (__const_parity4((w) ^ ((w) >> 4)))
> +#define __const_parity16(w) (__const_parity8((w) ^ ((w) >> 8)))
> +#define __const_parity32(w) (__const_parity16((w) ^ ((w) >> 16)))
> +#define __const_parity64(w) (__const_parity32((w) ^ ((w) >> 32)))
> +
> +/*
> + * Generic interface.
> + */
> +#define parity4(w) (__builtin_constant_p(w) ? __const_parity4(w) : __arch_parity4(w))
> +#define parity8(w) (__builtin_constant_p(w) ? __const_parity8(w) : __arch_parity8(w))
> +#define parity16(w) (__builtin_constant_p(w) ? __const_parity16(w) : __arch_parity16(w))
> +#define parity32(w) (__builtin_constant_p(w) ? __const_parity32(w) : __arch_parity32(w))
> +#define parity64(w) (__builtin_constant_p(w) ? __const_parity64(w) : __arch_parity64(w))
> +
> +/*
> + * Interface for known constant arguments
> + */
> +#define PARITY4(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity4(w))
> +#define PARITY8(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity8(w))
> +#define PARITY16(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity16(w))
> +#define PARITY32(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity32(w))
> +#define PARITY64(w) (BUILD_BUG_ON_ZERO(!__builtin_constant_p(w)) + __const_parity64(w))
> +
> +/*
> + * Type invariant interface to the compile time constant parity functions.
> + */
> +#define PARITY(w) PARITY64((u64)(w))
> +
> +#endif /* _ASM_GENERIC_BITOPS_CONST_PARITY_H_ */
> diff --git a/include/asm-generic/bitops/parity.h b/include/asm-generic/bitops/parity.h
> new file mode 100644
> index 0000000..a91dce7
> --- /dev/null
> +++ b/include/asm-generic/bitops/parity.h
> @@ -0,0 +1,7 @@
> +#ifndef _ASM_GENERIC_BITOPS_PARITY_H_
> +#define _ASM_GENERIC_BITOPS_PARITY_H_
> +
> +#include <asm-generic/bitops/arch_parity.h>
> +#include <asm-generic/bitops/const_parity.h>
> +
> +#endif /* _ASM_GENERIC_BITOPS_PARITY_H_ */
> diff --git a/include/asm-generic/bitops/popc-parity.h b/include/asm-generic/bitops/popc-parity.h
> new file mode 100644
> index 0000000..bf05999
> --- /dev/null
> +++ b/include/asm-generic/bitops/popc-parity.h
> @@ -0,0 +1,32 @@
> +#ifndef _ASM_GENERIC_BITOPS_POPC_PARITY_H_
> +#define _ASM_GENERIC_BITOPS_POPC_PARITY_H_
> +
> +#include <asm/types.h>
> +
> +static inline unsigned int __arch_parity32(unsigned int w)
> +{
> + return __builtin_popcount(w) & 1;
> +}
> +
> +static inline unsigned int __arch_parity16(unsigned int w)
> +{
> + return __arch_parity32(w & 0xffff);
> +}
> +
> +static inline unsigned int __arch_parity8(unsigned int w)
> +{
> + return __arch_parity32(w & 0xff);
> +}
> +
> +static inline unsigned int __arch_parity4(unsigned int w)
> +{
> + return __arch_parity32(w & 0xf);
> +}
> +
> +static inline unsigned int __arch_parity64(__u64 w)
> +{
> + return (unsigned int)__builtin_popcountll(w) & 1;
> +}
> +
> +#endif
> +
> diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> index defeaac..c3ea19e 100644
> --- a/include/linux/bitops.h
> +++ b/include/linux/bitops.h
> @@ -30,6 +30,11 @@ extern unsigned int __sw_hweight32(unsigned int w);
> extern unsigned long __sw_hweight64(__u64 w);
>
> /*
> + * a miniature 16-bit parity-table of 4-bits number
> + */
> +#define PARITY_MAGIC 0x6996
> +
> +/*
> * Include this here because some architectures need generic_ffs/fls in
> * scope
> */
> @@ -80,6 +85,11 @@ static __always_inline unsigned long hweight_long(unsigned long w)
> return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
> }
>
> +static __always_inline unsigned int parity_long(unsigned long w)
> +{
> + return sizeof(w) == 4 ? parity32(w) : parity64(w);
> +}
> +
> /**
> * rol64 - rotate a 64-bit value left
> * @word: value to rotate
>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2016-05-11 14:32 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2016-05-11 8:25 [patch V4 00/31] bitops: add parity functions zengzhaoxiu
2016-05-11 8:25 ` zengzhaoxiu
2016-05-11 8:47 ` [patch V4 01/31] " zengzhaoxiu
2016-05-11 14:32 ` Martin Kepplinger
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).