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.

4 files changed, 381 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;
     }
diff --git a/src/java/jogamp/common/util/Int32ArrayBitfield.java b/src/java/jogamp/common/util/Int32ArrayBitfield.java
new file mode 100644
index 0000000..d0ce669
--- /dev/null
+++ b/src/java/jogamp/common/util/Int32ArrayBitfield.java
@@ -0,0 +1,136 @@
+/**
+ * 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 jogamp.common.util;
+
+import com.jogamp.common.util.Bitfield;
+
+/**
+ * Simple bitfield interface for efficient storage access in O(1).
+ * <p>
+ * Implementation uses a 32bit integer array for storage.
+ * </p>
+ */
+public class Int32ArrayBitfield implements Bitfield {
+    private static final int UNIT_SHIFT = 5;
+    private final int[] storage;
+    private final int bitSize;
+
+    /**
+     * @param storageBitSize
+     */
+    public Int32ArrayBitfield(final int storageBitSize) {
+        final int units = Math.max(1, ( storageBitSize + 7 ) >>> UNIT_SHIFT);
+        this.storage = new int[units];
+        this.bitSize = units << UNIT_SHIFT;
+    }
+
+    @Override
+    public int getStorageBitSize() {
+        return bitSize;
+    }
+
+    private final void check(final int limit, final int bitnum) throws ArrayIndexOutOfBoundsException {
+        if( 0 > bitnum || bitnum >= limit ) {
+            throw new ArrayIndexOutOfBoundsException("Bitnum should be within [0.."+(limit-1)+"], but is "+bitnum);
+        }
+    }
+
+    @Override
+    public final int getInt32(final int rightBitnum) throws ArrayIndexOutOfBoundsException {
+        check(bitSize-31, rightBitnum);
+        if( 0 == rightBitnum % 32 ) {
+            // fast path
+            return storage[rightBitnum >>> UNIT_SHIFT];
+        } else {
+            // slow path
+            throw new UnsupportedOperationException("todo: non-32bit alignment");
+        }
+    }
+
+    @Override
+    public final void putInt32(final int rightBitnum, final int mask) throws ArrayIndexOutOfBoundsException {
+        check(bitSize-31, rightBitnum);
+        if( 0 == rightBitnum % 32 ) {
+            // fast path
+            storage[rightBitnum >>> UNIT_SHIFT] = mask;
+        } else {
+            // slow path
+            throw new UnsupportedOperationException("todo: non-32bit alignment");
+        }
+    }
+
+    @Override
+    public final boolean get(final int bitnum) throws ArrayIndexOutOfBoundsException {
+        check(bitSize, bitnum);
+        final int u = bitnum >>> UNIT_SHIFT;
+        final int b = bitnum - ( u << UNIT_SHIFT );
+        return 0 != ( storage[u] & ( 1 << b ) ) ;
+    }
+
+    @Override
+    public final boolean put(final int bitnum, final boolean bit) throws ArrayIndexOutOfBoundsException {
+        check(bitSize, bitnum);
+        final int u = bitnum >>> UNIT_SHIFT;
+        final int b = bitnum - ( u << UNIT_SHIFT );
+        final int m = 1 << b;
+        final boolean prev = 0 != ( storage[u] & m ) ;
+        if( prev != bit ) {
+            if( bit ) {
+                storage[u] |=  m;
+            } else {
+                storage[u] &= ~m;
+            }
+        }
+        return prev;
+    }
+    @Override
+    public final void set(final int bitnum) throws ArrayIndexOutOfBoundsException {
+        check(bitSize, bitnum);
+        final int u = bitnum >>> UNIT_SHIFT;
+        final int b = bitnum - ( u << UNIT_SHIFT );
+        final int m = 1 << b;
+        storage[u] |=  m;
+    }
+    @Override
+    public final void clear (final int bitnum) throws ArrayIndexOutOfBoundsException {
+        check(bitSize, bitnum);
+        final int u = bitnum >>> UNIT_SHIFT;
+        final int b = bitnum - ( u << UNIT_SHIFT );
+        final int m = 1 << b;
+        storage[u] &= ~m;
+    }
+
+    @Override
+    public int getBitCount() {
+        int c = 0;
+        for(int i = storage.length-1; i>=0; i--) {
+            c += Bitfield.Util.getBitCount(storage[i]);
+        }
+        return c;
+    }
+}
diff --git a/src/java/jogamp/common/util/Int32Bitfield.java b/src/java/jogamp/common/util/Int32Bitfield.java
new file mode 100644
index 0000000..28faf2c
--- /dev/null
+++ b/src/java/jogamp/common/util/Int32Bitfield.java
@@ -0,0 +1,107 @@
+/**
+ * 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 jogamp.common.util;
+
+import com.jogamp.common.util.Bitfield;
+
+/**
+ * Simple bitfield interface for efficient storage access in O(1).
+ * <p>
+ * Implementation uses one 32bit integer field for storage.
+ * </p>
+ */
+public class Int32Bitfield implements Bitfield {
+    /** Unit size in bits, here 32 bits for one int unit. */
+    private static final int UNIT_SIZE = 32;
+    private int storage;
+
+    public Int32Bitfield() {
+        this.storage = 0;
+    }
+
+    @Override
+    public int getStorageBitSize() {
+        return UNIT_SIZE;
+    }
+
+    private final void check(final int limit, final int bitnum) throws ArrayIndexOutOfBoundsException {
+        if( 0 > bitnum || bitnum >= limit ) {
+            throw new ArrayIndexOutOfBoundsException("Bitnum should be within [0.."+(limit-1)+"], but is "+bitnum);
+        }
+    }
+
+    @Override
+    public final int getInt32(final int rightBitnum) throws ArrayIndexOutOfBoundsException {
+        check(UNIT_SIZE-31, rightBitnum);
+        return storage;
+    }
+
+    @Override
+    public final void putInt32(final int rightBitnum, final int mask) throws ArrayIndexOutOfBoundsException {
+        check(UNIT_SIZE-31, rightBitnum);
+        storage = mask;
+    }
+
+    @Override
+    public final boolean get(final int bitnum) throws ArrayIndexOutOfBoundsException {
+        check(UNIT_SIZE, bitnum);
+        return 0 != ( storage & ( 1 << bitnum ) ) ;
+    }
+
+    @Override
+    public final boolean put(final int bitnum, final boolean bit) throws ArrayIndexOutOfBoundsException {
+        check(UNIT_SIZE, bitnum);
+        final int m = 1 << bitnum;
+        final boolean prev = 0 != ( storage & m ) ;
+        if( prev != bit ) {
+            if( bit ) {
+                storage |=  m;
+            } else {
+                storage &= ~m;
+            }
+        }
+        return prev;
+    }
+    @Override
+    public final void set(final int bitnum) throws ArrayIndexOutOfBoundsException {
+        check(UNIT_SIZE, bitnum);
+        final int m = 1 << bitnum;
+        storage |=  m;
+    }
+    @Override
+    public final void clear (final int bitnum) throws ArrayIndexOutOfBoundsException {
+        check(UNIT_SIZE, bitnum);
+        final int m = 1 << bitnum;
+        storage &= ~m;
+    }
+
+    @Override
+    public int getBitCount() {
+        return Bitfield.Util.getBitCount(storage);
+    }
+}