diff options
| -rw-r--r-- | src/java/com/jogamp/common/util/Bitfield.java | 132 | ||||
| -rw-r--r-- | src/java/com/jogamp/common/util/IntBitfield.java | 20 | ||||
| -rw-r--r-- | src/java/jogamp/common/util/Int32ArrayBitfield.java | 136 | ||||
| -rw-r--r-- | src/java/jogamp/common/util/Int32Bitfield.java | 107 |
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} ≤ 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); + } +} |