diff options
author | Sven Gothel <[email protected]> | 2015-07-30 02:50:38 +0200 |
---|---|---|
committer | Sven Gothel <[email protected]> | 2015-07-30 02:50:38 +0200 |
commit | e241034942725b7a189cb6186fd331d9defde7bc (patch) | |
tree | 385d8fe50d536a8fecc64aea7da895ca416941a3 /src/java/com/jogamp/common/util | |
parent | cb2c86e887d1ae8a29eab5e3967b6ec99d853218 (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.java | 132 | ||||
-rw-r--r-- | src/java/com/jogamp/common/util/IntBitfield.java | 20 |
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} ≤ 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; } |