db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kahat...@apache.org
Subject svn commit: r501334 - /db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java
Date Tue, 30 Jan 2007 08:04:27 GMT
Author: kahatlen
Date: Tue Jan 30 00:04:25 2007
New Revision: 501334

URL: http://svn.apache.org/viewvc?view=rev&rev=501334
Log:
DERBY-2191: Cleanup of FormatableBitSet

This patch re-writes the method getNumBitsSet() to do a byte-by-byte
calculation. Contributed by Dyre Tjeldvoll.

Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java

Modified: db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java?view=diff&rev=501334&r1=501333&r2=501334
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java
Tue Jan 30 00:04:25 2007
@@ -829,17 +829,46 @@
 	 */
 	public int getNumBitsSet()
 	{
-		int count = 0;
-
-		for (int index = getLength() - 1; index >= 0; index--)
-		{
-			if (isSet(index))
-			{
-				count++;
-			}
+		if (SanityManager.DEBUG) {
+			SanityManager.ASSERT(invariantHolds(),"broken invariant");
 		}
+		int bitsSet = 0;
+		final int numbytes = getLengthInBytes();
+		for (int i = 0; i < numbytes; ++i) {
+			byte v = value[i];
+
+			// "Truth table", bits set in half-nibble (2 bits):
+			//  A | A>>1 | A-=A>>1 | bits set
+			// ------------------------------
+			// 00 |  00  |    0    |    0
+			// 01 |  00  |    1    |    1
+			// 10 |  01  |    1    |    1
+			// 11 |  01  |    2    |    2
+
+			// Calculate bits set in each half-nibble in parallel
+			//   |ab|cd|ef|gh|
+			// - |>a|&c|&e|&g|>
+			// ----------------
+			// = |ij|kl|mn|op|
+			v -= ((v >> 1) & 0x55);
 
-		return count;
+			// Add the upper and lower half-nibbles together and store
+			// in each nibble
+			//  |&&|kl|&&|op|
+			//+ |>>|ij|&&|mn|>>
+			//-----------------
+			//= |0q|rs|0t|uv|
+			v = (byte)((v & 0x33) + ((v >> 2) & 0x33));
+
+			// Add the nibbles together
+			//  |&&&&|&tuv|
+			//+ |>>>>|0qrs|>>>>
+			//-----------------
+			//= |0000|wxyz|
+			v = (byte)((v & 0x7) + (v >> 4));
+			bitsSet += v;
+		}
+		return bitsSet;
 	}
 
 	/////////////////////////////////////////////////////////



Mime
View raw message