PERFORCE change 137066 for review

[Randall R. Stewart]

http://perforce.freebsd.org/chv.cgi?CH=137066

Change 137066 by rrs at rrs-mips2-jnpr on 2008/03/07 09:17:12

	Changing to a table driven lookup seems to improve
	       performance on interrupts a bit. I also add
	       a fls64() as well.

Affected files ...

.. //depot/projects/mips2-jnpr/src/sys/libkern/fls.c#2 edit

Differences ...

==== //depot/projects/mips2-jnpr/src/sys/libkern/fls.c#2 (text+ko) ====

@@ -35,14 +35,84 @@
 /*
  * Find Last Set bit
  */
+
+uint8_t fls_mask[256] = {
+	0x00, 0x01, 0x02, 0x02, 0x03, 0x03, 0x03, 0x03,
+	0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
+	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
+	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
+	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
+	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
+	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
+	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
+	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
+	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
+	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
+	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
+	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
+	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
+	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
+	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
+};
+
 int
-fls(int mask)
+fls(int m)
 {
-	int bit;
+        int val;
+	register uint32_t mask = m;
+	if (mask < 0x00000100) {
+		val = mask & 0x000000ff;
+		return (fls_mask[val]);
+	}
+	if (mask > 0x00ffffff) {
+		val = (mask >> 24) & 0x000000ff;
+		return (fls_mask[val] + 24);
+	}
+	if (mask > 0x0000ffff) {
+		val = (mask >> 16) & 0x000000ff;
+		return (fls_mask[val] + 16);
+	}
+	val = (mask >> 8) & 0x000000ff;
+	return (fls_mask[val] + 8);
+}
 
-	if (mask == 0)
-		return (0);
-	for (bit = 1; mask != 1; bit++)
-		mask = (unsigned int)mask >> 1;
-	return (bit);
+int
+fls64(uint64_t mask)
+{
+        int val;
+	if(mask <= 0x00000000ffffffff) {
+	         val = mask & 0x00000000ffffffff;
+		 return(fls(val));
+	}
+	if(mask > 0x00ffffffffffffff) {
+		val = (mask >> 56) & 0x000000ff;
+		return (fls_mask[val] + 56);
+	}
+	if (mask > 0x0000ffffffffffff) {
+		val = (mask >> 48) & 0x000000ff;
+		return (fls_mask[val] + 48);
+	}
+	if (mask > 0x000000ffffffffff) {
+		val = (mask >> 40) & 0x000000ff;
+		return (fls_mask[val] + 40);
+	}
+	val = (mask >> 32) & 0x000000ff;
+	return (fls_mask[val] + 32);
 }
+