[parisc-linux] backport bitops.h stuff

[parisc-linux] backport bitops.h stuff

[Joel Soete]

Hi pa,

Can somebody help me to ci inot 2.4 this patch which backport ffs() needed
for new devmapper ;)

--- bitops.h.orig	2003-08-01 15:25:02.000000000 +0200
+++ bitops.h	2003-08-01 15:27:38.000000000 +0200
@@ -208,13 +208,34 @@
 
 #ifdef __KERNEL__
 
+/**
+ * __ffs - find first bit in word.
+ * @word: The word to search
+ *
+ * Undefined if no bit exists, so code should check against 0 first.
+ */
+static __inline__ unsigned long __ffs(unsigned long word)
+{
+	unsigned long result = 0;
+
+	while (!(word & 1UL)) {
+		result++;
+		word >>= 1;
+	}
+	return result;
+}
+
 /*
  * ffs: find first bit set. This is defined the same way as
  * the libc and compiler builtin ffs routines, therefore
  * differs in spirit from the above ffz (man ffs).
  */
-
-#define ffs(x) generic_ffs(x)
+static __inline__ int ffs(int x)
+{
+	if (!x)
+		return 0;
+	return __ffs((unsigned long)x);
+}
 
 /*
  * hweightN: returns the hamming weight (i.e. the number

Thanks in advance,
    Joel


------------------------------------------------------
Soldes Tiscali ADSL : 27,50 euros/mois jusque fin 2003.
On s'habitue vite à payer son ADSL moins cher!
Plus d'info? Cliquez ici... http://reg.tiscali.be/default.asp?lg=fr 

RE: [parisc-linux] backport bitops.h stuff

[Joel Soete]

[-- Attachment #1: Type: text/plain, Size: 509 bytes --]

 
Hi pa,

>Can somebody help me to ci inot 2.4 this patch which backport ffs() needed
>for new devmapper ;)

Again I forget to attach the patch file, sorry.

    Joel

PS: Now I have an ADSL connection at home, may be could I now ask an account
to ci those kind of armless stuff

------------------------------------------------------
Soldes Tiscali ADSL : 27,50 euros/mois jusque fin 2003.
On s'habitue vite à payer son ADSL moins cher!
Plus d'info? Cliquez ici... http://reg.tiscali.be/default.asp?lg=fr 



[-- Attachment #2: bitops.h-patch --]
[-- Type: application/octet-stream, Size: 844 bytes --]

--- bitops.h.orig	2003-08-01 15:25:02.000000000 +0200
+++ bitops.h	2003-08-01 15:27:38.000000000 +0200
@@ -208,13 +208,34 @@
 
 #ifdef __KERNEL__
 
+/**
+ * __ffs - find first bit in word.
+ * @word: The word to search
+ *
+ * Undefined if no bit exists, so code should check against 0 first.
+ */
+static __inline__ unsigned long __ffs(unsigned long word)
+{
+	unsigned long result = 0;
+
+	while (!(word & 1UL)) {
+		result++;
+		word >>= 1;
+	}
+	return result;
+}
+
 /*
  * ffs: find first bit set. This is defined the same way as
  * the libc and compiler builtin ffs routines, therefore
  * differs in spirit from the above ffz (man ffs).
  */
-
-#define ffs(x) generic_ffs(x)
+static __inline__ int ffs(int x)
+{
+	if (!x)
+		return 0;
+	return __ffs((unsigned long)x);
+}
 
 /*
  * hweightN: returns the hamming weight (i.e. the number

Re: [parisc-linux] backport bitops.h stuff

[James Bottomley]

On Fri, 2003-08-01 at 10:28, Joel Soete wrote:
> Can somebody help me to ci inot 2.4 this patch which backport ffs() needed
> for new devmapper ;)

Actually, this patch looks decidedly non-optimal.

See include/linux/bitops.h:generic_ffs for how it should be done on
architectures that don't have any machine instruction help.  That's only
four if statements and no loop.

I see we already have the loop thing in 2.5, but should we consider
simply using the generic operations there as well?

even for __ffs, which is just a slight optimisation over ffs, using
generic_ffs would probably be faster

James

Re: [parisc-linux] backport bitops.h stuff

[Joel Soete]

> Actually, this patch looks decidedly non-optimal.

> See include/linux/bitops.h:generic_ffs for how it should be done on
> architectures that don't have any machine instruction help.  That's only
> four if statements and no loop.

Yes it was like this (just a lake of #include <linux/bitops.h>) into 2.4

Why was it is changed in 2.5?

> I see we already have the loop thing in 2.5, but should we consider
> simply using the generic operations there as well?

> even for __ffs, which is just a slight optimisation over ffs, using
> generic_ffs would probably be faster

If I have time next week I can test your idea.

Thanks,
    Joel


------------------------------------------------------
Soldes Tiscali ADSL : 27,50 euros/mois jusque fin 2003.
On s'habitue vite à payer son ADSL moins cher!
Plus d'info? Cliquez ici... http://reg.tiscali.be/default.asp?lg=fr 

Re: [parisc-linux] backport bitops.h stuff

[LaMont Jones]

On Fri, Aug 01, 2003 at 07:09:37PM +0200, Joel Soete wrote:
> > Actually, this patch looks decidedly non-optimal.

Here's a more optimal ffs() routine for hppa, along with the
output from the test program...  Should run in ~15 states on
just about anything [yes, it's that lock-stepped that it'll
take about 15 states on PA-8000's as well.. :-(]

Freshly coded, since the hp-ux version (which I can't find
anymore) looked for most significant set bit, not least.

lamont

#include <stdio.h>

int fastffs(int x)
{
	int ret;
	__asm__(" ldi		31,%1\n"
		" extru,<>	%0,31,16,%%r0\n"
		" extru,TR	%0,15,16,%0\n"
		" addi		-16,%1,%1\n"
		" extru,<>	%0,31,8,%%r0\n"
		" extru,TR	%0,23,8,%0\n"
		" addi		-8,%1,%1\n"
		" extru,<>	%0,31,4,%%r0\n"
		" extru,TR	%0,27,4,%0\n"
		" addi		-4,%1,%1\n"
		" extru,<>	%0,31,2,%%r0\n"
		" extru,TR	%0,29,2,%0\n"
		" addi		-2,%1,%1\n"
		" extru,=	%0,31,1,%%r0\n"
		" addi		-1,%1,%1\n"
		: "=r" (x), "=r" (ret)
		: "0" (x), "1" (ret));
	return ret;
}
doffs(x)
{
	printf("fastffs(%x)==%d\n",x,fastffs(x));
}
main()
{
	int i;
	for (i=0;i<5;i++)
		doffs(i);
	for (;i;i<<=1)
		doffs(i);
}


ffs(0)==31
ffs(1)==0
ffs(2)==1
ffs(3)==0
ffs(4)==2
ffs(5)==0
ffs(a)==1
ffs(14)==2
ffs(28)==3
ffs(50)==4
ffs(a0)==5
ffs(140)==6
ffs(280)==7
ffs(500)==8
ffs(a00)==9
ffs(1400)==10
ffs(2800)==11
ffs(5000)==12
ffs(a000)==13
ffs(14000)==14
ffs(28000)==15
ffs(50000)==16
ffs(a0000)==17
ffs(140000)==18
ffs(280000)==19
ffs(500000)==20
ffs(a00000)==21
ffs(1400000)==22
ffs(2800000)==23
ffs(5000000)==24
ffs(a000000)==25
ffs(14000000)==26
ffs(28000000)==27
ffs(50000000)==28
ffs(a0000000)==29
ffs(40000000)==30
ffs(80000000)==31

Re: [parisc-linux] backport bitops.h stuff

[Joel Soete]

>Here's a more optimal ffs() routine for hppa, along with the
>output from the test program...  Should run in ~15 states on
>just about
> anything [yes, it's that lock-stepped that it'll
>take about 15 states on PA-8000's as well.. :-(]
>
>Freshly coded, since the hp-ux version (which I can't find
>anymore) looked for most significant set bit, not least.

Thanks, I will test it on next week,

Joel


------------------------------------------------------
Soldes Tiscali ADSL : 27,50 euros/mois jusque fin 2003.
On s'habitue vite à payer son ADSL moins cher!
Plus d'info? Cliquez ici... http://reg.tiscali.be/default.asp?lg=fr 

Re: [parisc-linux] backport bitops.h stuff

[James Bottomley]

On Fri, 2003-08-01 at 12:14, LaMont Jones wrote:
> ffs(0)==31
> ffs(1)==0
> ffs(2)==1
> ffs(3)==0
> ffs(4)==2
> ffs(80000000)==31

This is off by one.  The definition should say

ffs(0) == 0
ffs(1) == 1
ffs(2) == 2
ffs(4) == 3
...
ffs(0x80000000) == 32

i.e. it returns the first set bit starting counting at one. (Yes, I know
it's confusing, it's tripped me up, especially as ffz counts bits from
zero.  However, ffs is a BSD standard).

Most arch's start by defining an __ffs which is not defined for the zero
case and then build the real ffs from that.

James

Re: [parisc-linux] backport bitops.h stuff

[Joel Soete]

Hi pa,

Here is a combine test case:

#include <stdio.h>

/**
 * __ffs - find first bit in word.
 * @word: The word to search
 *
 * Undefined if no bit exists, so code should check against 0 first.
 */
/* static __inline__ unsigned long ffs26(unsigned long word) */
unsigned long ffs_hppa26(unsigned long word)
{
        unsigned long result = 0;

        if (word)
/* I add this exception condition */
            while (!(word & 1UL)) {
                    result++;
                    word >>= 1;
            }
        return result;
}
/*
 * ffs: find first bit set. This is defined the same way as
 * the libc and compiler builtin ffs routines, therefore
 * differs in spirit from the above ffz (man ffs).
 */

static inline int generic_ffs(int x)
{
        int r = 1;

        if (!x)
                return 0;
        if (!(x & 0xffff)) {
                x >>= 16;
                r += 16;
        }
        if (!(x & 0xff)) {
                x >>= 8;
                r += 8;
        }
        if (!(x & 0xf)) {
                x >>= 4;
                r += 4;
        }
        if (!(x & 3)) {
                x >>= 2;
                r += 2;
        }
        if (!(x & 1)) {
                x >>= 1;
                r += 1;
        }
        return r;
}

int fastffs(int x)
{
  int ret=0;
  __asm__(" ldi    31,%1\n"
    " extru,<>  %0,31,16,%%r0\n"
    " extru,TR  %0,15,16,%0\n"
    " addi    -16,%1,%1\n"
    " extru,<>  %0,31,8,%%r0\n"
    " extru,TR  %0,23,8,%0\n"
    " addi    -8,%1,%1\n"
    " extru,<>  %0,31,4,%%r0\n"
    " extru,TR  %0,27,4,%0\n"
    " addi    -4,%1,%1\n"
    " extru,<>  %0,31,2,%%r0\n"
    " extru,TR  %0,29,2,%0\n"
    " addi    -2,%1,%1\n"
    " extru,=  %0,31,1,%%r0\n"
    " addi    -1,%1,%1\n"
    : "=r" (x), "=r" (ret)
    : "0" (x), "1" (ret));

  return ret;
}

doffs(x)
{
  printf("fastffs(%d)==%d\n",x,fastffs(x));
  printf("ffs_hppa26(%d)==%d\n",x,ffs_hppa26(x));
  printf("generic_ffs(%d)==%d\n",x,generic_ffs(x));
  printf("\n");
}

main()
{
  int i;
  for (i=0;i<5;i++)
    doffs(i);
  for (;i;i<<=1)
    doffs(i);
}

And I am confused by results:

fastffs(0)==31
ffs_hppa26(0)==0
generic_ffs(0)==0

I presume that we also have to consider an exception for 0?

[...]
fastffs(1)==0
ffs_hppa26(1)==0
generic_ffs(1)==1

fastffs(2)==1
ffs_hppa26(2)==1
generic_ffs(2)==2

fastffs(3)==0
ffs_hppa26(3)==0
generic_ffs(3)==1

fastffs(4)==2
ffs_hppa26(4)==2
generic_ffs(4)==3

[...]

So in all other case fastffs or ffs_hppa26 == generic_ffs - 1.
What is right?

Thanks for additional attention,
    Joel


------------------------------------------------------
Soldes Tiscali ADSL : 27,50 euros/mois jusque fin 2003.
On s'habitue vite à payer son ADSL moins cher!
Plus d'info? Cliquez ici... http://reg.tiscali.be/default.asp?lg=fr 

Re: [parisc-linux] backport bitops.h stuff

[LaMont Jones]

On Mon, Aug 04, 2003 at 12:43:10PM +0200, Joel Soete wrote:
>   int ret=0;
>   __asm__(" ldi    31,%1\n"

Make it say 32,%1...  Mistake in understanding things on my part...

> And I am confused by results:
> fastffs(0)==31
> ffs_hppa26(0)==0
> generic_ffs(0)==0
> 
> I presume that we also have to consider an exception for 0?

yes.

lamont

Re: [parisc-linux] backport bitops.h stuff

[James Bottomley]

Let me try to clarify, since there are two differently defined macros in
the kernel (off by one) that would appear to have the same interface,
but which in fact have different semantics (I know, recipe for
disaster):  ffs and ffz (meaning find first set and find first zero).

Both tend to have machine code implementations for architectures that
support them.  The difference is that ffz counts bit zero as zero, but
ffz counts bit zero as one.

They also have different requirements for the error case (no bit set for
ffs and no bit zero for ffz).  For ffs, this is defined to be 32.  For
ffz, this is undefined.

The reason for all of this is that on x86 there is an instruction bsfl
that actually finds first set bit (but counting from zero, not one), but
the O(1) scheduler needed to find clear bits for the arrays, so ffz was
implemented as the complement of this.

ffs has been around a long time (inherited from BSD).  The differing
semantics are because "damnit, computers count from zero not one for
fast operations".

i.e.

ffs(0) == 0
ffz(0) == 0

ffs(1) == 1
ffz(~1) == 0  (same as above ffz, bit zero clear)

ffs(2) == 2
ffz(~3) == 1

[...]

ffs(0x8000000) == 32
ffz(0x7ffffff) == 31

ffz(0xffffffff) == could be anything

Some machine architectures have an __ffs() (usually mirroring a machine
instruction) whose semantics are identical to ffs() except that it also
is undefined in the error case (so ffs can simply be implemented as if
not error case, do __ffs()).

James

Re: [parisc-linux] backport bitops.h stuff

[Joel Soete]

>>   int ret=0;
>>   __asm__(" ldi    31,%1\n"
>
>Make it say 32,%1...  Mistake in understanding things on my part...


Yes,

the following code:

int fastffs(int x)
{
  int ret=0;
  if (x)
    __asm__(" ldi    32,%1\n"
      " extru,<>  %0,31,16,%%r0\n"
      " extru,TR  %0,15,16,%0\n"
      " addi    -16,%1,%1\n"
      " extru,<>  %0,31,8,%%r0\n"
      " extru,TR  %0,23,8,%0\n"
      " addi    -8,%1,%1\n"
      " extru,<>  %0,31,4,%%r0\n"
      " extru,TR  %0,27,4,%0\n"
      " addi    -4,%1,%1\n"
      " extru,<>  %0,31,2,%%r0\n"
      " extru,TR  %0,29,2,%0\n"
      " addi    -2,%1,%1\n"
      " extru,=  %0,31,1,%%r0\n"
      " addi    -1,%1,%1\n"
      : "=r" (x), "=r" (ret)
      : "0" (x), "1" (ret));

  return ret;
}

give now the same results as generic_ffs:

fastffs(0)==0
generic_ffs(0)==0

fastffs(1)==1
generic_ffs(1)==1

fastffs(2)==2
generic_ffs(2)==2

fastffs(3)==1
generic_ffs(3)==1

fastffs(4)==3
generic_ffs(4)==3

fastffs(5)==1
generic_ffs(5)==1

fastffs(10)==2
generic_ffs(10)==2

fastffs(20)==3
generic_ffs(20)==3

fastffs(40)==4
generic_ffs(40)==4

fastffs(80)==5
generic_ffs(80)==5

fastffs(160)==6
generic_ffs(160)==6

fastffs(320)==7
generic_ffs(320)==7

fastffs(640)==8
generic_ffs(640)==8

fastffs(1280)==9
generic_ffs(1280)==9

fastffs(2560)==10
generic_ffs(2560)==10

fastffs(5120)==11
generic_ffs(5120)==11

fastffs(10240)==12
generic_ffs(10240)==12

fastffs(20480)==13
generic_ffs(20480)==13

fastffs(40960)==14
generic_ffs(40960)==14

fastffs(81920)==15
generic_ffs(81920)==15

fastffs(163840)==16
generic_ffs(163840)==16

fastffs(327680)==17
generic_ffs(327680)==17

fastffs(655360)==18
generic_ffs(655360)==18

fastffs(1310720)==19
generic_ffs(1310720)==19

fastffs(2621440)==20
generic_ffs(2621440)==20

fastffs(5242880)==21
generic_ffs(5242880)==21

fastffs(10485760)==22
generic_ffs(10485760)==22

fastffs(20971520)==23
generic_ffs(20971520)==23

fastffs(41943040)==24
generic_ffs(41943040)==24

fastffs(83886080)==25
generic_ffs(83886080)==25

fastffs(167772160)==26
generic_ffs(167772160)==26

fastffs(335544320)==27
generic_ffs(335544320)==27

fastffs(671088640)==28
generic_ffs(671088640)==28

fastffs(1342177280)==29
generic_ffs(1342177280)==29

fastffs(-1610612736)==30
generic_ffs(-1610612736)==30

fastffs(1073741824)==31
generic_ffs(1073741824)==31

fastffs(-2147483648)==32
generic_ffs(-2147483648)==32


Great job. If everybody agreed could you ci (I have no cvs ci access).
Or do you need a more accurate patch?

Thanks,
    Joel


------------------------------------------------------
Soldes Tiscali ADSL : 27,50 euros/mois jusque fin 2003.
On s'habitue vite à payer son ADSL moins cher!
Plus d'info? Cliquez ici... http://reg.tiscali.be/default.asp?lg=fr 

Re: [parisc-linux] backport bitops.h stuff

[Joel Soete]

James,

Many thanks for those clear explanation,

Joel

> -- Original Message --
> From: James Bottomley <James.Bottomley@steeleye.com>
> To: LaMont Jones <lamont@hp.com>
> Cc: Joel Soete <jsoe0708@tiscali.be>, parisc-linux@parisc-linux.org
> Date: 04 Aug 2003 11:08:01 -0500
> Subject: Re: [parisc-linux] backport bitops.h stuff
> 
> 
> Let me try to clarify, since there are two differently defined macros in
the kernel (off by one) that would appear to have the same interface,
but which in fact have different semantics (I know, recipe for
disaster):  ffs and ffz (meaning find first
> set and find first zero).

Both tend to have machine code implementations for architectures that
support them.  The difference is that ffz counts bit zero as zero, but
ffz counts bit zero as one.

They also have different requirements for the err
> r case (no bit set for
ffs and no bit zero for ffz).  For ffs, this is defined to be 32.  For
ffz, this is undefined.

The reason for all of this is that on x86 there is an instruction bsfl
that actually finds first set bit (but counting from zero
>  not one), but
the O(1) scheduler needed to find clear bits for the arrays, so ffz was
implemented as the complement of this.

ffs has been around a long time (inherited from BSD).  The differing
semantics are because "damnit, computers count from
> zero not one for
fast operations".

i.e.

ffs(0) == 0
ffz(0) == 0

ffs(1) == 1
ffz(~1) == 0  (same as above ffz, bit zero clear)

ffs(2) == 2
ffz(~3) == 1

[...]

ffs(0x8000000) == 32
ffz(0x7ffffff) == 31

ffz(0xffffffff) == could be
> anything

Some machine architectures have an __ffs() (usually mirroring a machine
instruction) whose semantics are identical to ffs() except that it also
is undefined in the error case (so ffs can simply be implemented as if
not error case, do __f
> s()).

James


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux



------------------------------------------------------
Soldes Tiscali ADSL : 27,50 euros/mois jusque fin 2003.
On s'habitue vite à payer son ADSL moins cher!
Plus d'info? Cliquez ici... http://reg.tiscali.be/default.asp?lg=fr