Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754185AbcDNCoo (ORCPT ); Wed, 13 Apr 2016 22:44:44 -0400 Received: from m50-138.163.com ([123.125.50.138]:56490 "EHLO m50-138.163.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751286AbcDNCom (ORCPT ); Wed, 13 Apr 2016 22:44:42 -0400 From: zengzhaoxiu@163.com To: linux-kernel@vger.kernel.org Cc: Zhaoxiu Zeng , Arnd Bergmann , Andrew Morton , Martin Kepplinger , George Spelvin , Yury Norov , Ingo Molnar , Sasha Levin , Denys Vlasenko , linux-arch@vger.kernel.org Subject: [PATCH V3 01/29] bitops: add parity functions Date: Thu, 14 Apr 2016 10:41:24 +0800 Message-Id: <1460601694-4056-1-git-send-email-zengzhaoxiu@163.com> X-Mailer: git-send-email 2.5.0 X-CM-TRANSID: C9GowAAnTLBhAw9XZS_VAg--.54621S2 X-Coremail-Antispam: 1Uf129KBjvJXoW3GF17KFWDWw1DJw1kKr47twb_yoWxZr18pF s5Cr1rtrW8Kw1xZFWSkFnrZF4ftw4fGr1avrWa9r97AFy7Jw4UKrn8WFs8ArnF9w4vqrWj yrZxGFyDWws2yaDanT9S1TB71UUUUUUqnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07bbIDcUUUUU= X-Originating-IP: [112.95.225.98] X-CM-SenderInfo: p2hqw6xkdr5xrx6rljoofrz/1tbiGQZLgFXlSLsthQAAs- Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6355 Lines: 200 From: Zhaoxiu Zeng Add generic odd parity functions, adapted from "https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel" Signed-off-by: Zhaoxiu Zeng --- 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 #include #include +#include #include #include 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 + +/* + * 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 +#include + +#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 + +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-bit numbers + */ +#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.5.0