aboutsummaryrefslogtreecommitdiffstats
path: root/src/java/com/jogamp/common/util
diff options
context:
space:
mode:
authorSven Gothel <[email protected]>2015-07-30 02:50:38 +0200
committerSven Gothel <[email protected]>2015-07-30 02:50:38 +0200
commite241034942725b7a189cb6186fd331d9defde7bc (patch)
tree385d8fe50d536a8fecc64aea7da895ca416941a3 /src/java/com/jogamp/common/util
parentcb2c86e887d1ae8a29eab5e3967b6ec99d853218 (diff)
Introduce Bitfield interface w/ Int32 and Int32Array impl. deprecating IntBitfield
IntBitfield's 64bit bit-size is exceeding its use-case, making it less efficient and complicated. Bitfield offers a fast path implementation for 32 bits as well as a int[] implementation. TODO: 32 bit Unaligned putInt32(..) and getInt32(..), currently throwing UnsupportedOperationException for int[] impl.
Diffstat (limited to 'src/java/com/jogamp/common/util')
-rw-r--r--src/java/com/jogamp/common/util/Bitfield.java132
-rw-r--r--src/java/com/jogamp/common/util/IntBitfield.java20
2 files changed, 138 insertions, 14 deletions
diff --git a/src/java/com/jogamp/common/util/Bitfield.java b/src/java/com/jogamp/common/util/Bitfield.java
new file mode 100644
index 0000000..9155603
--- /dev/null
+++ b/src/java/com/jogamp/common/util/Bitfield.java
@@ -0,0 +1,132 @@
+/**
+ * Copyright 2015 JogAmp Community. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification, are
+ * permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this list of
+ * conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice, this list
+ * of conditions and the following disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * The views and conclusions contained in the software and documentation are those of the
+ * authors and should not be interpreted as representing official policies, either expressed
+ * or implied, of JogAmp Community.
+ */
+package com.jogamp.common.util;
+
+/**
+ * Simple bitfield interface for efficient storage access in O(1).
+ */
+public interface Bitfield {
+ /**
+ * Bit operation utilities (static).
+ */
+ public static class Util {
+ /**
+ * Returns the number of set bits within given 32bit integer in O(1)
+ * using <i>HAKEM Bit Count</i>:
+ * <pre>
+ * http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
+ * http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169
+ * http://tekpool.wordpress.com/category/bit-count/
+ * </pre>
+ */
+ public static final int getBitCount(final int n) {
+ // Note: Original used 'unsigned int',
+ // hence we use the unsigned right-shift '>>>'
+ int c = n;
+ c -= (n >>> 1) & 033333333333;
+ c -= (n >>> 2) & 011111111111;
+ return ( (c + ( c >>> 3 ) ) & 030707070707 ) % 63;
+ }
+ }
+ /**
+ * Simple {@link Bitfield} factory for returning the efficient implementation.
+ */
+ public static class Factory {
+ /**
+ * Creates am efficient {@link Bitfield} instance based on the requested {@code storageBitSize}.
+ * <p>
+ * Implementation returns a plain 32 bit integer field implementation for
+ * {@code storageBitSize} &le; 32 bits or an 32 bit integer array implementation otherwise.
+ * </p>
+ */
+ public static Bitfield create(final int storageBitSize) {
+ if( 32 >= storageBitSize ) {
+ return new jogamp.common.util.Int32Bitfield();
+ } else {
+ return new jogamp.common.util.Int32ArrayBitfield(storageBitSize);
+ }
+ }
+ }
+
+ /**
+ * Returns the storage size in bit units, e.g. 32 bit for implementations using one {@code int} field.
+ */
+ int getStorageBitSize();
+
+ /**
+ * Returns the 32 bit integer mask w/ its lowest bit at the bit number {@code rightBitnum}.
+ * @param rightBitnum bit number denoting the position of the lowest bit, restricted to [0..{@link #getStorageBitSize()}-32].
+ * @throws ArrayIndexOutOfBoundsException if {@code rightBitnum} is out of bounds
+ */
+ int getInt32(final int rightBitnum) throws ArrayIndexOutOfBoundsException;
+
+ /**
+ * Sets the given 32 bit integer mask w/ its lowest bit at the bit number {@code rightBitnum}.
+ * @param rightBitnum bit number denoting the position of the lowest bit, restricted to [0..{@link #getStorageBitSize()}-32].
+ * @param mask denoting the 32 bit mask value to store
+ * @throws ArrayIndexOutOfBoundsException if {@code rightBitnum} is out of bounds
+ */
+ void putInt32(final int rightBitnum, final int mask) throws ArrayIndexOutOfBoundsException;
+
+ /**
+ * Return <code>true</code> if the bit at position <code>bitnum</code> is set, otherwise <code>false</code>.
+ * @param bitnum bit number, restricted to [0..{@link #getStorageBitSize()}-1].
+ * @throws ArrayIndexOutOfBoundsException if {@code bitnum} is out of bounds
+ */
+ boolean get(final int bitnum) throws ArrayIndexOutOfBoundsException;
+
+ /**
+ * Set or clear the bit at position <code>bitnum</code> according to <code>bit</code>
+ * and return the previous value.
+ * @param bitnum bit number, restricted to [0..{@link #getStorageBitSize()}-1].
+ * @throws ArrayIndexOutOfBoundsException if {@code bitnum} is out of bounds
+ */
+ boolean put(final int bitnum, final boolean bit) throws ArrayIndexOutOfBoundsException;
+
+ /**
+ * Set the bit at position <code>bitnum</code> according to <code>bit</code>.
+ * @param bitnum bit number, restricted to [0..{@link #getStorageBitSize()}-1].
+ * @throws ArrayIndexOutOfBoundsException if {@code bitnum} is out of bounds
+ */
+ void set(final int bitnum) throws ArrayIndexOutOfBoundsException;
+
+ /**
+ * Clear the bit at position <code>bitnum</code> according to <code>bit</code>.
+ * @param bitnum bit number, restricted to [0..{@link #getStorageBitSize()}-1].
+ * @throws ArrayIndexOutOfBoundsException if {@code bitnum} is out of bounds
+ */
+ void clear(final int bitnum) throws ArrayIndexOutOfBoundsException;
+
+ /**
+ * Returns the number of set bits within this bitfield.
+ * <p>
+ * Utilizes {#link {@link Bitfield.Util#getBitCount(int)}}.
+ * </p>
+ */
+ int getBitCount();
+}
diff --git a/src/java/com/jogamp/common/util/IntBitfield.java b/src/java/com/jogamp/common/util/IntBitfield.java
index 74e37ac..3ef5bb7 100644
--- a/src/java/com/jogamp/common/util/IntBitfield.java
+++ b/src/java/com/jogamp/common/util/IntBitfield.java
@@ -28,7 +28,10 @@
package com.jogamp.common.util;
/**
+ * @deprecated Use {@link Bitfield} implementations via {@link Bitfield.Factory#create(int)}.
+ * <p>
* Simple bitfield holder class using an int[] storage.
+ * </p>
* <p>
* IntBitfield allows convenient access of a wide field of transient bits using efficient storage in O(1).
* </p>
@@ -137,21 +140,10 @@ public class IntBitfield {
return prev;
}
/**
- * Returns the number of set bits within given 32bit integer in O(1)
- * using <i>HAKEM Bit Count</i>:
- * <pre>
- * http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
- * http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169
- * http://tekpool.wordpress.com/category/bit-count/
- * </pre>
+ * @deprecated Use {@link Bitfield.Util#getBitCount(int)}.
*/
public static final int getBitCount(final int n) {
- // Note: Original used 'unsigned int',
- // hence we use the unsigned right-shift '>>>'
- int c = n;
- c -= (n >>> 1) & 033333333333;
- c -= (n >>> 2) & 011111111111;
- return ( (c + ( c >>> 3 ) ) & 030707070707 ) % 63;
+ return Bitfield.Util.getBitCount(n);
}
/**
@@ -163,7 +155,7 @@ public class IntBitfield {
public long getBitCount() {
long c = 0;
for(int i = storage.length-1; i>=0; i--) {
- c += getBitCount(storage[i]);
+ c += Bitfield.Util.getBitCount(storage[i]);
}
return c;
}