[U-Boot-Users] [PATCH] ppc: Add u64 versions of fls64 and __ilog bitops
Signed-off-by: Kumar Gala galak@kernel.crashing.org --- include/asm-ppc/bitops.h | 58 ++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 58 insertions(+), 0 deletions(-)
diff --git a/include/asm-ppc/bitops.h b/include/asm-ppc/bitops.h index 4e9c608..ea73027 100644 --- a/include/asm-ppc/bitops.h +++ b/include/asm-ppc/bitops.h @@ -167,6 +167,64 @@ extern __inline__ int ffz(unsigned int x) return __ilog2(x & -x); }
+/* + * fls: find last (most-significant) bit set. + * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. + */ +static __inline__ int fls(unsigned int x) +{ + int lz; + + asm ("cntlzw %0,%1" : "=r" (lz) : "r" (x)); + return 32 - lz; +} + +static __inline__ unsigned long __fls(unsigned long x) +{ + return __ilog2(x); +} + +/** + * fls64 - find last set bit in a 64-bit word + * @x: the word to search + * + * This is defined in a similar way as the libc and compiler builtin + * ffsll, but returns the position of the most significant set bit. + * + * fls64(value) returns 0 if value is 0 or the position of the last + * set bit if value is nonzero. The last (most significant) bit is + * at position 64. + */ +#if BITS_PER_LONG == 32 +static inline int fls64(__u64 x) +{ + __u32 h = x >> 32; + if (h) + return fls(h) + 32; + return fls(x); +} +#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{ + if (x == 0) + return 0; + return __fls(x) + 1; +} +#else +#error BITS_PER_LONG not 32 or 64 +#endif + +static inline +int __ilog2_u64(u64 n) +{ + return fls64(n) - 1; +} + +static inline int ffs64(u64 x) +{ + return __ilog2_u64(x & -x) + 1ull; +} + #ifdef __KERNEL__
/*
In message Pine.LNX.4.64.0806101618470.3027@blarg.am.freescale.net you wrote:
Signed-off-by: Kumar Gala galak@kernel.crashing.org
Comments and code do not match; you'r actually adding much more code.
+/*
- fls: find last (most-significant) bit set.
- Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
- */
+static __inline__ int fls(unsigned int x)
This is not a u64 version of fls64, or is it? ;-)
+static __inline__ unsigned long __fls(unsigned long x)
Neither is this...
Also: is fls() vs. __fls() a good way to differentiate between int and ulong?
- fls64(value) returns 0 if value is 0 or the position of the last
- set bit if value is nonzero. The last (most significant) bit is
Sorry, I can't parse this.
+#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{
- if (x == 0)
return 0;- return __fls(x) + 1;
Do I have to understand where the "+1" is coming from?
+static inline int ffs64(u64 x) +{
- return __ilog2_u64(x & -x) + 1ull;
Isn't there an easier way to do this?
Best regards,
Wolfgang Denk
On Jun 10, 2008, at 4:58 PM, Wolfgang Denk wrote:
In message Pine.LNX.4.64.0806101618470.3027@blarg.am.freescale.net you wrote:
Signed-off-by: Kumar Gala galak@kernel.crashing.org
Comments and code do not match; you'r actually adding much more code.
I was just needing the u64 versions and the other stuff came along to make it work :)
+/*
- fls: find last (most-significant) bit set.
- Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
- */
+static __inline__ int fls(unsigned int x)
This is not a u64 version of fls64, or is it? ;-)
+static __inline__ unsigned long __fls(unsigned long x)
Neither is this...
Also: is fls() vs. __fls() a good way to differentiate between int and ulong?
I took this from the kernel source tree and didn't really pay much attention to it.
- fls64(value) returns 0 if value is 0 or the position of the last
- set bit if value is nonzero. The last (most significant) bit is
Sorry, I can't parse this.
again taken from kernel land.
+#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{
- if (x == 0)
return 0;- return __fls(x) + 1;
Do I have to understand where the "+1" is coming from?
Nope, you can just accept it. I can drop this for now since I don't believe we support any ppc64 machines.
+static inline int ffs64(u64 x) +{
- return __ilog2_u64(x & -x) + 1ull;
Isn't there an easier way to do this?
Not aware of one.
So, I've stolen this from the kernel and am not sure what you'd like for me to change at this point.
- k
Dear Kumar,
in message 3F2661BD-8C86-410F-984D-B887242A8AA2@kernel.crashing.org you wrote:
Comments and code do not match; you'r actually adding much more code.
I was just needing the u64 versions and the other stuff came along to make it work :)
Please make the comment match the code.
Also: is fls() vs. __fls() a good way to differentiate between int and ulong?
I took this from the kernel source tree and didn't really pay much attention to it.
Maybe we can do better?
- fls64(value) returns 0 if value is 0 or the position of the last
- set bit if value is nonzero. The last (most significant) bit is
Sorry, I can't parse this.
again taken from kernel land.
No reason not to fix it.
+#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{
- if (x == 0)
return 0;- return __fls(x) + 1;
Do I have to understand where the "+1" is coming from?
Nope, you can just accept it. I can drop this for now since I don't believe we support any ppc64 machines.
I guess we might see support for the PA6T soon. SO please leave it here.
And I'd appreciate if somebody could explain the code to me...
+static inline int ffs64(u64 x) +{
- return __ilog2_u64(x & -x) + 1ull;
Isn't there an easier way to do this?
Not aware of one.
So, I've stolen this from the kernel and am not sure what you'd like for me to change at this point.
Please clean it up and fix at least the obvious issues.
Best regards,
Wolfgang Denk
On Jun 10, 2008, at 6:51 PM, Wolfgang Denk wrote:
Dear Kumar,
in message <3F2661BD-8C86-410F-984D- B887242A8AA2@kernel.crashing.org> you wrote:
Comments and code do not match; you'r actually adding much more code.
I was just needing the u64 versions and the other stuff came along to make it work :)
Please make the comment match the code.
will do.
Also: is fls() vs. __fls() a good way to differentiate between int and ulong?
I took this from the kernel source tree and didn't really pay much attention to it.
Maybe we can do better?
going to drop __fls()
- fls64(value) returns 0 if value is 0 or the position of the
last
- set bit if value is nonzero. The last (most significant) bit is
Sorry, I can't parse this.
again taken from kernel land.
No reason not to fix it.
I'm not clear on what the confusion is.
+#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{
- if (x == 0)
return 0;- return __fls(x) + 1;
Do I have to understand where the "+1" is coming from?
It has to do w/how __fls(x) is implemented. It might be clear in v2.
Nope, you can just accept it. I can drop this for now since I don't believe we support any ppc64 machines.
I guess we might see support for the PA6T soon. SO please leave it here.
And I'd appreciate if somebody could explain the code to me...
+static inline int ffs64(u64 x) +{
- return __ilog2_u64(x & -x) + 1ull;
Isn't there an easier way to do this?
Not aware of one.
So, I've stolen this from the kernel and am not sure what you'd like for me to change at this point.
Please clean it up and fix at least the obvious issues.
Best regards,
take a look at v2 and see what issues you have with it :)
- k
fls64, __ilog2_u64, ffs64 are variants that work on an u64 and fls is used to implement them.
Signed-off-by: Kumar Gala galak@kernel.crashing.org ---
Dropped __fls and cleaned up things a bit based on feedback (commit message is more explicit).
- k
include/asm-ppc/bitops.h | 49 ++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 49 insertions(+), 0 deletions(-)
diff --git a/include/asm-ppc/bitops.h b/include/asm-ppc/bitops.h index 4e9c608..957b3d4 100644 --- a/include/asm-ppc/bitops.h +++ b/include/asm-ppc/bitops.h @@ -167,6 +167,55 @@ extern __inline__ int ffz(unsigned int x) return __ilog2(x & -x); }
+/* + * fls: find last (most-significant) bit set. + * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. + */ +static __inline__ int fls(unsigned int x) +{ + return __ilog2(x) + 1; +} + +/** + * fls64 - find last set bit in a 64-bit word + * @x: the word to search + * + * This is defined in a similar way as the libc and compiler builtin + * ffsll, but returns the position of the most significant set bit. + * + * fls64(value) returns 0 if value is 0 or the position of the last + * set bit if value is nonzero. The last (most significant) bit is + * at position 64. + */ +#if BITS_PER_LONG == 32 +static inline int fls64(__u64 x) +{ + __u32 h = x >> 32; + if (h) + return fls(h) + 32; + return fls(x); +} +#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{ + if (x == 0) + return 0; + return __ilog2(x) + 1; +} +#else +#error BITS_PER_LONG not 32 or 64 +#endif + +static inline int __ilog2_u64(u64 n) +{ + return fls64(n) - 1; +} + +static inline int ffs64(u64 x) +{ + return __ilog2_u64(x & -x) + 1ull; +} + #ifdef __KERNEL__
/*
Kumar Gala galak@kernel.crashing.org wrote:
+/*
- fls: find last (most-significant) bit set.
- Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
- */
+static __inline__ int fls(unsigned int x) +{
- return __ilog2(x) + 1;
+}
__ilog2(0) returns -1?
Haavard
On Jun 11, 2008, at 5:54 AM, Haavard Skinnemoen wrote:
Kumar Gala galak@kernel.crashing.org wrote:
+/*
- fls: find last (most-significant) bit set.
- Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
- */
+static __inline__ int fls(unsigned int x) +{
- return __ilog2(x) + 1;
+}
__ilog2(0) returns -1?
it does.
- k
Kumar Gala galak@kernel.crashing.org wrote:
On Jun 11, 2008, at 5:54 AM, Haavard Skinnemoen wrote:
Kumar Gala galak@kernel.crashing.org wrote:
+/*
- fls: find last (most-significant) bit set.
- Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
- */
+static __inline__ int fls(unsigned int x) +{
- return __ilog2(x) + 1;
+}
__ilog2(0) returns -1?
it does.
In general, or just on powerpc? If it's the latter, could you add a comment so that people won't blindly copy it into their architecture's bitops.h?
Haavard
On Jun 11, 2008, at 9:03 AM, Haavard Skinnemoen wrote:
Kumar Gala galak@kernel.crashing.org wrote:
On Jun 11, 2008, at 5:54 AM, Haavard Skinnemoen wrote:
Kumar Gala galak@kernel.crashing.org wrote:
+/*
- fls: find last (most-significant) bit set.
- Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
- */
+static __inline__ int fls(unsigned int x) +{
- return __ilog2(x) + 1;
+}
__ilog2(0) returns -1?
it does.
In general, or just on powerpc? If it's the latter, could you add a comment so that people won't blindly copy it into their architecture's bitops.h?
I'm guessing on PPC (thus the __ilog2 rather than ilog2()).
From the kernel headers:
/* * non-constant log of base 2 calculators * - the arch may override these in asm/bitops.h if they can be implemented * more efficiently than using fls() and fls64() * - the arch is not required to handle n==0 if implementing the fallback */ #ifndef CONFIG_ARCH_HAS_ILOG2_U32 static inline __attribute__((const)) int __ilog2_u32(u32 n) { return fls(n) - 1; } #endif
I'll add a comment.
- k
fls64, __ilog2_u64, ffs64 are variants that work on an u64 and fls is used to implement them.
Signed-off-by: Kumar Gala galak@kernel.crashing.org ---
added comment about __ilog2() x == 0 being undefined.
include/asm-ppc/bitops.h | 50 ++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 50 insertions(+), 0 deletions(-)
diff --git a/include/asm-ppc/bitops.h b/include/asm-ppc/bitops.h index 4e9c608..23f5449 100644 --- a/include/asm-ppc/bitops.h +++ b/include/asm-ppc/bitops.h @@ -152,6 +152,7 @@ extern __inline__ int test_bit(int nr, __const__ volatile void *addr) }
/* Return the bit position of the most significant 1 bit in a word */ +/* - the result is undefined when x == 0 */ extern __inline__ int __ilog2(unsigned int x) { int lz; @@ -167,6 +168,55 @@ extern __inline__ int ffz(unsigned int x) return __ilog2(x & -x); }
+/* + * fls: find last (most-significant) bit set. + * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. + */ +static __inline__ int fls(unsigned int x) +{ + return __ilog2(x) + 1; +} + +/** + * fls64 - find last set bit in a 64-bit word + * @x: the word to search + * + * This is defined in a similar way as the libc and compiler builtin + * ffsll, but returns the position of the most significant set bit. + * + * fls64(value) returns 0 if value is 0 or the position of the last + * set bit if value is nonzero. The last (most significant) bit is + * at position 64. + */ +#if BITS_PER_LONG == 32 +static inline int fls64(__u64 x) +{ + __u32 h = x >> 32; + if (h) + return fls(h) + 32; + return fls(x); +} +#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{ + if (x == 0) + return 0; + return __ilog2(x) + 1; +} +#else +#error BITS_PER_LONG not 32 or 64 +#endif + +static inline int __ilog2_u64(u64 n) +{ + return fls64(n) - 1; +} + +static inline int ffs64(u64 x) +{ + return __ilog2_u64(x & -x) + 1ull; +} + #ifdef __KERNEL__
/*
Kumar Gala galak@kernel.crashing.org wrote:
+/*
- fls: find last (most-significant) bit set.
- Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
- */
+static __inline__ int fls(unsigned int x) +{
- return __ilog2(x) + 1;
I was sort of hoping you'd add a comment here explaining why it's safe to rely on undefined behaviour in this particular case. Something like
/* On powerpc, __ilog2(0) returns -1, but this is not safe in general */
Haavard
fls64, __ilog2_u64, ffs64 are variants that work on an u64 and fls is used to implement them.
Signed-off-by: Kumar Gala galak@kernel.crashing.org ---
Added comment about __ilog2(0) not being generally safe from Haavard Skinnemoen
- k
include/asm-ppc/bitops.h | 52 ++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 52 insertions(+), 0 deletions(-)
diff --git a/include/asm-ppc/bitops.h b/include/asm-ppc/bitops.h index 4e9c608..daa66cf 100644 --- a/include/asm-ppc/bitops.h +++ b/include/asm-ppc/bitops.h @@ -152,6 +152,7 @@ extern __inline__ int test_bit(int nr, __const__ volatile void *addr) }
/* Return the bit position of the most significant 1 bit in a word */ +/* - the result is undefined when x == 0 */ extern __inline__ int __ilog2(unsigned int x) { int lz; @@ -167,6 +168,57 @@ extern __inline__ int ffz(unsigned int x) return __ilog2(x & -x); }
+/* + * fls: find last (most-significant) bit set. + * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. + * + * On powerpc, __ilog2(0) returns -1, but this is not safe in general + */ +static __inline__ int fls(unsigned int x) +{ + return __ilog2(x) + 1; +} + +/** + * fls64 - find last set bit in a 64-bit word + * @x: the word to search + * + * This is defined in a similar way as the libc and compiler builtin + * ffsll, but returns the position of the most significant set bit. + * + * fls64(value) returns 0 if value is 0 or the position of the last + * set bit if value is nonzero. The last (most significant) bit is + * at position 64. + */ +#if BITS_PER_LONG == 32 +static inline int fls64(__u64 x) +{ + __u32 h = x >> 32; + if (h) + return fls(h) + 32; + return fls(x); +} +#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{ + if (x == 0) + return 0; + return __ilog2(x) + 1; +} +#else +#error BITS_PER_LONG not 32 or 64 +#endif + +static inline int __ilog2_u64(u64 n) +{ + return fls64(n) - 1; +} + +static inline int ffs64(u64 x) +{ + return __ilog2_u64(x & -x) + 1ull; +} + #ifdef __KERNEL__
/*
Kumar Gala galak@kernel.crashing.org wrote:
fls64, __ilog2_u64, ffs64 are variants that work on an u64 and fls is used to implement them.
Signed-off-by: Kumar Gala galak@kernel.crashing.org
Added comment about __ilog2(0) not being generally safe from Haavard Skinnemoen
Looks good. Thanks!
Haavard
In message Pine.LNX.4.64.0806111013470.18478@blarg.am.freescale.net you wrote:
fls64, __ilog2_u64, ffs64 are variants that work on an u64 and fls is used to implement them.
Signed-off-by: Kumar Gala galak@kernel.crashing.org
Added comment about __ilog2(0) not being generally safe from Haavard Skinnemoen
- k
include/asm-ppc/bitops.h | 52 ++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 52 insertions(+), 0 deletions(-)
Applied, thanks.
Best regards,
Wolfgang Denk
participants (3)
-
Haavard Skinnemoen -
Kumar Gala -
Wolfgang Denk