Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4462] branches/QUADS_QUERY_BRANCH/bigdata/src
|
From: <tho...@us...> - 2011-05-07 15:44:34
|
Revision: 4462
http://bigdata.svn.sourceforge.net/bigdata/?rev=4462&view=rev
Author: thompsonbry
Date: 2011-05-07 15:44:27 +0000 (Sat, 07 May 2011)
Log Message:
-----------
Added a getBits(int32,off,len) method and test suite. This is intended for bit slices in a hash tree using native int32 keys rather than unsigned byte[] keys. It seems worth while to support this optimization for the hash tree since most of the applications of the hash tree will have int32 keys and it appears that the optimization can be achieved relatively easily within the implementation.
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/BytesUtil.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestAll.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestBytesUtil.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromByteArray.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromInt32.java
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/BytesUtil.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/BytesUtil.java 2011-05-06 15:55:01 UTC (rev 4461)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/btree/BytesUtil.java 2011-05-07 15:44:27 UTC (rev 4462)
@@ -1138,6 +1138,58 @@
}
/**
+ * Return the n-bit integer corresponding to the inclusive bit range of the
+ * byte[]. Bit ZERO (0) is the Most Significant Bit (MSB). Bit positions
+ * increase from zero up to <code>31</code>. The return value is an int32
+ * and the bit range must not be greater than 32 bits.
+ * <p>
+ * For example, given the following data and the bit range (0,2)
+ *
+ * <pre>
+ * bit index: 01234567
+ * ---------+----------
+ * bit value: 10110000
+ * </pre>
+ *
+ * TWO (2) bits starting at bit offset ZERO (0) would be extracted and
+ * returned as a 2-bit integer. For those data, the return value would be an
+ * int32 value whose binary representation was <code>10</code> (with leading
+ * zeros suppressed).
+ * <p>
+ * Note: This method is design for use in a bigdata hash index having native
+ * int32 keys rather than unsigned byte[] keys.
+ *
+ * @param a
+ * An integer.
+ * @param off
+ * The index of the first bit to be included.
+ * @param len
+ * The number of bits to be returned in [0:32]. However, a bit
+ * length of zero will always return zero.
+ *
+ * @return The integer extracted from the specified bit range.
+ */
+ public static int getBits(final int a, final int off, final int len) {
+ if (off < 0)
+ throw new IllegalArgumentException();
+ if (len < 0 || len > 32)
+ throw new IllegalArgumentException();
+ if (len == 0) // zero length is always a zero.
+ return 0;
+ if (off + len > 32)
+ throw new IllegalArgumentException();
+
+ final int last = off + len - 1; // index of the last bit (inclusive).
+ final int rshift = 31 - last; // right shift to word align.
+ int w = (int) (a >>> rshift); // int32 result.
+ int mask = masks32[32 - len]; // lookup mask with [len] LSB ZEROs.
+ mask = ~mask; // flip bits to get [len] LSB ONEs.
+ w &= mask; // mask off the lower [len] bits (handles sign extension and
+ // starting offset within byte).
+ return w;
+ }
+
+ /**
* Return the binary representation of the unsigned byte[].
*
* @param a
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestAll.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestAll.java 2011-05-06 15:55:01 UTC (rev 4461)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestAll.java 2011-05-07 15:44:27 UTC (rev 4462)
@@ -60,6 +60,8 @@
// test low level variable length byte[] operations.
suite.addTestSuite(TestBytesUtil.class);
+ suite.addTestSuite(TestGetBitsFromByteArray.class);
+ suite.addTestSuite(TestGetBitsFromInt32.class);
// unsigned byte[] key encoding and decoding.
suite.addTest(com.bigdata.btree.keys.TestAll.suite());
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestBytesUtil.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestBytesUtil.java 2011-05-06 15:55:01 UTC (rev 4461)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestBytesUtil.java 2011-05-07 15:44:27 UTC (rev 4462)
@@ -27,8 +27,6 @@
package com.bigdata.btree;
-import java.util.Formatter;
-
import junit.framework.TestCase2;
import com.bigdata.btree.keys.IKeyBuilder;
@@ -999,323 +997,4 @@
}
- public void test_getBitsFromByteArray_correctRejection_nullArg() {
-
- try {
- BytesUtil.getBits(null, 0, 0);
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled())
- log.info("Ignoring expected exception: " + ex);
- }
-
- }
-
- /**
- * offset may be zero, but not negative.
- */
- public void test_getBitsFromByteArray_correctRejection_off_and_len_01() {
-
- BytesUtil.getBits(new byte[1], 0, 0); // ok
- try {
- BytesUtil.getBits(new byte[1], -1, 0); // no good
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled())
- log.info("Ignoring expected exception: " + ex);
- }
-
- }
-
- /**
- * length may be zero, but not negative.
- */
- public void test_getBitsFromByteArray_correctRejection_off_and_len_02() {
-
- BytesUtil.getBits(new byte[1], 0, 0); // ok
- try {
- BytesUtil.getBits(new byte[1], 0, -1); // no good
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled())
- log.info("Ignoring expected exception: " + ex);
- }
-
- }
-
- /**
- * length may address all bits (8) in a single byte, but not the 9th bit.
- */
- public void test_getBitsFromByteArray_correctRejection_off_and_len_03() {
-
- BytesUtil.getBits(new byte[1], 0, 8); // ok
- try {
- BytesUtil.getBits(new byte[1], 0, 8 + 1); // no good
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled())
- log.info("Ignoring expected exception: " + ex);
- }
-
- }
-
- /**
- * length may address all bits (32) in 4 bytes, but not 33 bits since the
- * return value would be larger than an int32.
- */
- public void test_getBitsFromByteArray_correctRejection_off_and_len_04() {
-
- BytesUtil.getBits(new byte[4], 0, 32); // ok
- try {
- BytesUtil.getBits(new byte[4], 0, 33); // no good
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled())
- log.info("Ignoring expected exception: " + ex);
- }
-
- }
-
- /**
- * length may address (32) bits in 5 bytes, but not 33 bits since the return
- * value would be larger than an int32.
- */
- public void test_getBitsFromByteArray_correctRejection_off_and_len_05() {
-
- BytesUtil.getBits(new byte[5], 0, 32); // ok
- try {
- BytesUtil.getBits(new byte[5], 0, 33); // no good
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled())
- log.info("Ignoring expected exception: " + ex);
- }
-
- }
-
- /**
- * You can request a zero length slice starting at bit zero of a zero length
- * byte[].
- */
- public void test_getBitsFromByteArray_zeroLength() {
-
- assertEquals(0, BytesUtil.getBits(new byte[0], 0, 0));
-
- }
-
- /** byte[4] (32-bits) with all bits zero. */
- public void test_getBitsFromByteArray_01() {
-
- final byte[] b = new byte[4];
-
- assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
- assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
- assertEquals(0x00000000, getBits(b, 0/* off */, 31/* len */));
- assertEquals(0x00000000, getBits(b, 0/* off */, 32/* len */));
-
- }
-
- /** byte[4] (32-bits) with LSB ONE. */
- public void test_getBitsFromByteArray_02() {
-
- final byte[] b = new byte[4];
-
- BytesUtil.setBit(b, 31/* off */, true);
-
- assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
- assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
- assertEquals(0x00000000, getBits(b, 0/* off */, 31/* len */));//x
- assertEquals(0x00000001, getBits(b, 0/* off */, 32/* len */));
- assertEquals(0x00000001, getBits(b, 31/* off */, 1/* len */));//x
- assertEquals(0x00000001, getBits(b, 30/* off */, 2/* len */));
-
- }
-
- /**
- * byte[4] (32-bits) with bit ONE (1) set.
- */
- public void test_getBitsFromByteArray_03() {
-
- final byte[] b = new byte[4];
-
- BytesUtil.setBit(b, 1/* off */, true);
-
- assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
- assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
- assertEquals(0x00000001, getBits(b, 0/* off */, 2/* len */));
- assertEquals(0x00000002, getBits(b, 1/* off */, 2/* len */));
- assertEquals(0x00000004, getBits(b, 1/* off */, 3/* len */));
-
- assertEquals(0x00000001, getBits(b, 1/* off */, 1/* len */));
-
- assertEquals(0x40000000, getBits(b, 0/* off */, 32/* len */));
- assertEquals(0x20000000, getBits(b, 0/* off */, 31/* len */));
- assertEquals(0x10000000, getBits(b, 0/* off */, 30/* len */));
- assertEquals(0x08000000, getBits(b, 0/* off */, 29/* len */));
-
- }
-
- /**
- * byte[4] (32-bits) with MSB ONE (this test case is the mostly likely to
- * run a foul of a sign bit extension).
- */
- public void test_getBitsFromByteArray_04() {
-
- final byte[] b = new byte[4];
-
- BytesUtil.setBit(b, 0/* off */, true);
-
- assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
- assertEquals(0x00000001, getBits(b, 0/* off */, 1/* len */));
- assertEquals(0x00000002, getBits(b, 0/* off */, 2/* len */));
- assertEquals(0x00000004, getBits(b, 0/* off */, 3/* len */));
- assertEquals(0x00000008, getBits(b, 0/* off */, 4/* len */));
-
- assertEquals(0x00000000, getBits(b, 1/* off */, 0/* len */));
- assertEquals(0x00000000, getBits(b, 1/* off */, 1/* len */));
- assertEquals(0x00000000, getBits(b, 1/* off */, 2/* len */));
- assertEquals(0x00000000, getBits(b, 1/* off */, 3/* len */));
-
- }
-
- /**
- * byte[4] (32-bits) with slice in the 2nd byte.
- */
- public void test_getBitsFromByteArray_05() {
-
- final byte[] b = new byte[4];
-
- // four bits on starting at bit 11.
- BytesUtil.setBit(b, 11/* offset */, true);
- BytesUtil.setBit(b, 12/* offset */, true);
- BytesUtil.setBit(b, 13/* offset */, true);
- BytesUtil.setBit(b, 14/* offset */, true);
-
- /*
- * Test with a window extending from bit zero with a variety of bit
- * lengths ranging from an end bit index one less than the first ONE bit
- * through an end bit index beyond the last ONE bit.
- */
- assertEquals(0x00000000, getBits(b, 0/* off */, 11/* len */));
- assertEquals(0x00000001, getBits(b, 0/* off */, 12/* len */));
- assertEquals(0x00000003, getBits(b, 0/* off */, 13/* len */));
- assertEquals(0x00000007, getBits(b, 0/* off */, 14/* len */));
- assertEquals(0x0000000f, getBits(b, 0/* off */, 15/* len */));
- assertEquals(0x0000001e, getBits(b, 0/* off */, 16/* len */));
- assertEquals(0x0000003c, getBits(b, 0/* off */, 17/* len */));
- assertEquals(0x00000078, getBits(b, 0/* off */, 18/* len */));
- assertEquals(0x000000f0, getBits(b, 0/* off */, 19/* len */));
-
- /*
- * Test with a 4-bit window that slides over the ONE bits. The initial
- * window is to the left of the first ONE bit. The window slides right
- * by one bit position for each assertion.
- */
- assertEquals(0x00000000, getBits(b, 7/* off */, 4/* len */));
- assertEquals(0x00000001, getBits(b, 8/* off */, 4/* len */));
- assertEquals(0x00000003, getBits(b, 9/* off */, 4/* len */));
- assertEquals(0x00000007, getBits(b,10/* off */, 4/* len */));
- assertEquals(0x0000000f, getBits(b,11/* off */, 4/* len */));
- assertEquals(0x0000000e, getBits(b,12/* off */, 4/* len */));
- assertEquals(0x0000000c, getBits(b,13/* off */, 4/* len */));
- assertEquals(0x00000008, getBits(b,14/* off */, 4/* len */));
- assertEquals(0x00000000, getBits(b,15/* off */, 4/* len */));
-
- }
-
- /**
- * byte[2] (16-bits)
- *
- * @todo test slices from arrays with more than 4 bytes
- */
- public void test_getBitsFromByteArray_06() {
-
- final byte[] b = new byte[2];
-
- // four bits on starting at bit 11.
- BytesUtil.setBit(b, 11/* offset */, true);
- BytesUtil.setBit(b, 12/* offset */, true);
- BytesUtil.setBit(b, 13/* offset */, true);
- BytesUtil.setBit(b, 14/* offset */, true);
-
- /*
- * Test with a window extending from bit zero with a variety of bit
- * lengths ranging from an end bit index one less than the first ONE bit
- * through an end bit index beyond the last ONE bit.
- */
- assertEquals(0x00000000, getBits(b, 0/* off */, 11/* len */));
- assertEquals(0x00000001, getBits(b, 0/* off */, 12/* len */));
- assertEquals(0x00000003, getBits(b, 0/* off */, 13/* len */));
- assertEquals(0x00000007, getBits(b, 0/* off */, 14/* len */));
- assertEquals(0x0000000f, getBits(b, 0/* off */, 15/* len */));
- assertEquals(0x0000001e, getBits(b, 0/* off */, 16/* len */));
-
- /*
- * Now that we have reached the last legal length verify that length 17
- * is rejected.
- */
- try {
- getBits(b, 0/* off */, 17/* len */);
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled())
- log.info("Ignoring expected exception: " + ex);
- }
-
- /*
- * Now increase the offset while decreasing the length and step through
- * a few more slices. These all see the FOUR (4) ON bits plus one
- * trailing ZERO (0) bit.
- */
- assertEquals(0x0000001e, getBits(b, 1/* off */, 15/* len */));
- assertEquals(0x0000001e, getBits(b, 2/* off */, 14/* len */));
- assertEquals(0x0000001e, getBits(b, 3/* off */, 13/* len */));
- assertEquals(0x0000001e, getBits(b, 4/* off */, 12/* len */));
- assertEquals(0x0000001e, getBits(b, 5/* off */, 11/* len */));
- assertEquals(0x0000001e, getBits(b, 6/* off */, 10/* len */));
- assertEquals(0x0000001e, getBits(b, 7/* off */, 9/* len */));
- assertEquals(0x0000001e, getBits(b, 8/* off */, 8/* len */));
- assertEquals(0x0000001e, getBits(b, 9/* off */, 7/* len */));
- assertEquals(0x0000001e, getBits(b,10/* off */, 6/* len */));
- assertEquals(0x0000001e, getBits(b,11/* off */, 5/* len */));
-
- /*
- * Continue to increase the offset while decreasing the length, but now
- * we will start to loose the ONE bits on both sides as the window keeps
- * sliding and shrinking.
- */
- assertEquals(0x0000000e, getBits(b,12/* off */, 4/* len */));
- assertEquals(0x00000006, getBits(b,13/* off */, 3/* len */));
- assertEquals(0x00000002, getBits(b,14/* off */, 2/* len */));
- assertEquals(0x00000000, getBits(b,15/* off */, 1/* len */));
-
- /*
- * This is also illegal (the starting offset is too large).
- */
- try {
- getBits(b,16/* off */, 1/* len */);
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled())
- log.info("Ignoring expected exception: " + ex);
- }
-
- }
-
- private int getBits(final byte[] a,final int off,final int len) {
-
- final int ret = BytesUtil.getBits(a, off, len);
-
- if (log.isInfoEnabled()) {
- final StringBuilder sb = new StringBuilder();
- final Formatter f = new Formatter(sb);
- f.format("[%" + (a.length * 8) + "s] =(%2d:%2d)=> [%32s]",
- BytesUtil.toBitString(a), off, len, Integer.toBinaryString(ret));
- log.info(sb.toString());
- }
-
- return ret;
-
- }
-
}
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromByteArray.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromByteArray.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromByteArray.java 2011-05-07 15:44:27 UTC (rev 4462)
@@ -0,0 +1,367 @@
+/**
+
+Copyright (C) SYSTAP, LLC 2006-2007. All rights reserved.
+
+Contact:
+ SYSTAP, LLC
+ 4501 Tower Road
+ Greensboro, NC 27410
+ lic...@bi...
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+/*
+ * Created on May 7, 2011
+ */
+package com.bigdata.btree;
+
+import java.util.Formatter;
+
+import junit.framework.TestCase2;
+
+/**
+ * Unit tests for {@link BytesUtil#getBits(byte[], int, int)}
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id$
+ */
+public class TestGetBitsFromByteArray extends TestCase2 {
+
+ public TestGetBitsFromByteArray() {
+ }
+
+ public TestGetBitsFromByteArray(String name) {
+ super(name);
+ }
+
+ public void test_getBitsFromByteArray_correctRejection_nullArg() {
+
+ try {
+ BytesUtil.getBits(null, 0, 0);
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * offset may be zero, but not negative.
+ */
+ public void test_getBitsFromByteArray_correctRejection_off_and_len_01() {
+
+ BytesUtil.getBits(new byte[1], 0, 0); // ok
+ try {
+ BytesUtil.getBits(new byte[1], -1, 0); // no good
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * length may be zero, but not negative.
+ */
+ public void test_getBitsFromByteArray_correctRejection_off_and_len_02() {
+
+ BytesUtil.getBits(new byte[1], 0, 0); // ok
+ try {
+ BytesUtil.getBits(new byte[1], 0, -1); // no good
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * length may address all bits (8) in a single byte, but not the 9th bit.
+ */
+ public void test_getBitsFromByteArray_correctRejection_off_and_len_03() {
+
+ BytesUtil.getBits(new byte[1], 0, 8); // ok
+ try {
+ BytesUtil.getBits(new byte[1], 0, 8 + 1); // no good
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * length may address all bits (32) in 4 bytes, but not 33 bits since the
+ * return value would be larger than an int32.
+ */
+ public void test_getBitsFromByteArray_correctRejection_off_and_len_04() {
+
+ BytesUtil.getBits(new byte[4], 0, 32); // ok
+ try {
+ BytesUtil.getBits(new byte[4], 0, 33); // no good
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * length may address (32) bits in 5 bytes, but not 33 bits since the return
+ * value would be larger than an int32.
+ */
+ public void test_getBitsFromByteArray_correctRejection_off_and_len_05() {
+
+ BytesUtil.getBits(new byte[5], 0, 32); // ok
+ try {
+ BytesUtil.getBits(new byte[5], 0, 33); // no good
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * You can request a zero length slice starting at bit zero of a zero length
+ * byte[].
+ */
+ public void test_getBitsFromByteArray_zeroLength() {
+
+ assertEquals(0, BytesUtil.getBits(new byte[0], 0, 0));
+
+ }
+
+ /** byte[4] (32-bits) with all bits zero. */
+ public void test_getBitsFromByteArray_01() {
+
+ final byte[] b = new byte[4];
+
+ assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 31/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 32/* len */));
+
+ }
+
+ /** byte[4] (32-bits) with LSB ONE. */
+ public void test_getBitsFromByteArray_02() {
+
+ final byte[] b = new byte[4];
+
+ BytesUtil.setBit(b, 31/* off */, true);
+
+ assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 31/* len */));//x
+ assertEquals(0x00000001, getBits(b, 0/* off */, 32/* len */));
+ assertEquals(0x00000001, getBits(b, 31/* off */, 1/* len */));//x
+ assertEquals(0x00000001, getBits(b, 30/* off */, 2/* len */));
+
+ }
+
+ /**
+ * byte[4] (32-bits) with bit ONE (1) set.
+ */
+ public void test_getBitsFromByteArray_03() {
+
+ final byte[] b = new byte[4];
+
+ BytesUtil.setBit(b, 1/* off */, true);
+
+ assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
+ assertEquals(0x00000001, getBits(b, 0/* off */, 2/* len */));
+ assertEquals(0x00000002, getBits(b, 1/* off */, 2/* len */));
+ assertEquals(0x00000004, getBits(b, 1/* off */, 3/* len */));
+
+ assertEquals(0x00000001, getBits(b, 1/* off */, 1/* len */));
+
+ assertEquals(0x40000000, getBits(b, 0/* off */, 32/* len */));
+ assertEquals(0x20000000, getBits(b, 0/* off */, 31/* len */));
+ assertEquals(0x10000000, getBits(b, 0/* off */, 30/* len */));
+ assertEquals(0x08000000, getBits(b, 0/* off */, 29/* len */));
+
+ }
+
+ /**
+ * byte[4] (32-bits) with MSB ONE (this test case is the mostly likely to
+ * run a foul of a sign bit extension).
+ */
+ public void test_getBitsFromByteArray_04() {
+
+ final byte[] b = new byte[4];
+
+ BytesUtil.setBit(b, 0/* off */, true);
+
+ assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
+ assertEquals(0x00000001, getBits(b, 0/* off */, 1/* len */));
+ assertEquals(0x00000002, getBits(b, 0/* off */, 2/* len */));
+ assertEquals(0x00000004, getBits(b, 0/* off */, 3/* len */));
+ assertEquals(0x00000008, getBits(b, 0/* off */, 4/* len */));
+
+ assertEquals(0x00000000, getBits(b, 1/* off */, 0/* len */));
+ assertEquals(0x00000000, getBits(b, 1/* off */, 1/* len */));
+ assertEquals(0x00000000, getBits(b, 1/* off */, 2/* len */));
+ assertEquals(0x00000000, getBits(b, 1/* off */, 3/* len */));
+
+ }
+
+ /**
+ * byte[4] (32-bits) with slice in the 2nd byte.
+ */
+ public void test_getBitsFromByteArray_05() {
+
+ final byte[] b = new byte[4];
+
+ // four bits on starting at bit 11.
+ BytesUtil.setBit(b, 11/* offset */, true);
+ BytesUtil.setBit(b, 12/* offset */, true);
+ BytesUtil.setBit(b, 13/* offset */, true);
+ BytesUtil.setBit(b, 14/* offset */, true);
+
+ /*
+ * Test with a window extending from bit zero with a variety of bit
+ * lengths ranging from an end bit index one less than the first ONE bit
+ * through an end bit index beyond the last ONE bit.
+ */
+ assertEquals(0x00000000, getBits(b, 0/* off */, 11/* len */));
+ assertEquals(0x00000001, getBits(b, 0/* off */, 12/* len */));
+ assertEquals(0x00000003, getBits(b, 0/* off */, 13/* len */));
+ assertEquals(0x00000007, getBits(b, 0/* off */, 14/* len */));
+ assertEquals(0x0000000f, getBits(b, 0/* off */, 15/* len */));
+ assertEquals(0x0000001e, getBits(b, 0/* off */, 16/* len */));
+ assertEquals(0x0000003c, getBits(b, 0/* off */, 17/* len */));
+ assertEquals(0x00000078, getBits(b, 0/* off */, 18/* len */));
+ assertEquals(0x000000f0, getBits(b, 0/* off */, 19/* len */));
+
+ /*
+ * Test with a 4-bit window that slides over the ONE bits. The initial
+ * window is to the left of the first ONE bit. The window slides right
+ * by one bit position for each assertion.
+ */
+ assertEquals(0x00000000, getBits(b, 7/* off */, 4/* len */));
+ assertEquals(0x00000001, getBits(b, 8/* off */, 4/* len */));
+ assertEquals(0x00000003, getBits(b, 9/* off */, 4/* len */));
+ assertEquals(0x00000007, getBits(b,10/* off */, 4/* len */));
+ assertEquals(0x0000000f, getBits(b,11/* off */, 4/* len */));
+ assertEquals(0x0000000e, getBits(b,12/* off */, 4/* len */));
+ assertEquals(0x0000000c, getBits(b,13/* off */, 4/* len */));
+ assertEquals(0x00000008, getBits(b,14/* off */, 4/* len */));
+ assertEquals(0x00000000, getBits(b,15/* off */, 4/* len */));
+
+ }
+
+ /**
+ * byte[2] (16-bits)
+ *
+ * @todo test slices from arrays with more than 4 bytes
+ */
+ public void test_getBitsFromByteArray_06() {
+
+ final byte[] b = new byte[2];
+
+ // four bits on starting at bit 11.
+ BytesUtil.setBit(b, 11/* offset */, true);
+ BytesUtil.setBit(b, 12/* offset */, true);
+ BytesUtil.setBit(b, 13/* offset */, true);
+ BytesUtil.setBit(b, 14/* offset */, true);
+
+ /*
+ * Test with a window extending from bit zero with a variety of bit
+ * lengths ranging from an end bit index one less than the first ONE bit
+ * through an end bit index beyond the last ONE bit.
+ */
+ assertEquals(0x00000000, getBits(b, 0/* off */, 11/* len */));
+ assertEquals(0x00000001, getBits(b, 0/* off */, 12/* len */));
+ assertEquals(0x00000003, getBits(b, 0/* off */, 13/* len */));
+ assertEquals(0x00000007, getBits(b, 0/* off */, 14/* len */));
+ assertEquals(0x0000000f, getBits(b, 0/* off */, 15/* len */));
+ assertEquals(0x0000001e, getBits(b, 0/* off */, 16/* len */));
+
+ /*
+ * Now that we have reached the last legal length verify that length 17
+ * is rejected.
+ */
+ try {
+ getBits(b, 0/* off */, 17/* len */);
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ /*
+ * Now increase the offset while decreasing the length and step through
+ * a few more slices. These all see the FOUR (4) ON bits plus one
+ * trailing ZERO (0) bit.
+ */
+ assertEquals(0x0000001e, getBits(b, 1/* off */, 15/* len */));
+ assertEquals(0x0000001e, getBits(b, 2/* off */, 14/* len */));
+ assertEquals(0x0000001e, getBits(b, 3/* off */, 13/* len */));
+ assertEquals(0x0000001e, getBits(b, 4/* off */, 12/* len */));
+ assertEquals(0x0000001e, getBits(b, 5/* off */, 11/* len */));
+ assertEquals(0x0000001e, getBits(b, 6/* off */, 10/* len */));
+ assertEquals(0x0000001e, getBits(b, 7/* off */, 9/* len */));
+ assertEquals(0x0000001e, getBits(b, 8/* off */, 8/* len */));
+ assertEquals(0x0000001e, getBits(b, 9/* off */, 7/* len */));
+ assertEquals(0x0000001e, getBits(b,10/* off */, 6/* len */));
+ assertEquals(0x0000001e, getBits(b,11/* off */, 5/* len */));
+
+ /*
+ * Continue to increase the offset while decreasing the length, but now
+ * we will start to loose the ONE bits on both sides as the window keeps
+ * sliding and shrinking.
+ */
+ assertEquals(0x0000000e, getBits(b,12/* off */, 4/* len */));
+ assertEquals(0x00000006, getBits(b,13/* off */, 3/* len */));
+ assertEquals(0x00000002, getBits(b,14/* off */, 2/* len */));
+ assertEquals(0x00000000, getBits(b,15/* off */, 1/* len */));
+
+ /*
+ * This is also illegal (the starting offset is too large).
+ */
+ try {
+ getBits(b,16/* off */, 1/* len */);
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ private int getBits(final byte[] a,final int off,final int len) {
+
+ final int ret = BytesUtil.getBits(a, off, len);
+
+ if (log.isInfoEnabled()) {
+ final StringBuilder sb = new StringBuilder();
+ final Formatter f = new Formatter(sb);
+ f.format("[%" + (a.length * 8) + "s] =(%2d:%2d)=> [%32s]",
+ BytesUtil.toBitString(a), off, len, Integer.toBinaryString(ret));
+ log.info(sb.toString());
+ }
+
+ return ret;
+
+ }
+
+}
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromInt32.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromInt32.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/btree/TestGetBitsFromInt32.java 2011-05-07 15:44:27 UTC (rev 4462)
@@ -0,0 +1,241 @@
+/**
+
+Copyright (C) SYSTAP, LLC 2006-2007. All rights reserved.
+
+Contact:
+ SYSTAP, LLC
+ 4501 Tower Road
+ Greensboro, NC 27410
+ lic...@bi...
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+/*
+ * Created on May 7, 2011
+ */
+package com.bigdata.btree;
+
+import java.util.Formatter;
+
+import junit.framework.TestCase2;
+
+/**
+ * Unit tests for {@link BytesUtil#getBits(int, int, int)
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id$
+ */
+public class TestGetBitsFromInt32 extends TestCase2 {
+
+ /**
+ *
+ */
+ public TestGetBitsFromInt32() {
+ }
+
+ /**
+ * @param name
+ */
+ public TestGetBitsFromInt32(String name) {
+ super(name);
+ }
+
+ /**
+ * offset may be zero, but not negative.
+ */
+ public void test_getBitsFromInt32_correctRejection_off_and_len_01() {
+
+ BytesUtil.getBits(0x0, 0, 0); // ok
+ try {
+ BytesUtil.getBits(0x0, -1, 0); // no good
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * length may be zero, but not negative.
+ */
+ public void test_getBitsFromInt32_correctRejection_off_and_len_02() {
+
+ BytesUtil.getBits(0x0, 0, 0); // ok
+ try {
+ BytesUtil.getBits(0x0, 0, -1); // no good
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * length may address all bits (32), but not 33 bits.
+ */
+ public void test_getBitsFromByteArray_correctRejection_off_and_len_04() {
+
+ BytesUtil.getBits(0x0, 0, 32); // ok
+ try {
+ BytesUtil.getBits(0x0, 0, 33); // no good
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * You can request a zero length slice starting at bit zero.
+ */
+ public void test_getBitsFromInt32_zeroLength() {
+
+ assertEquals(0, BytesUtil.getBits(0x0, 0, 0));
+
+ }
+
+ /** all bits zero. */
+ public void test_getBitsFromInt32_01() {
+
+ final int b = 0x0;
+
+ assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 31/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 32/* len */));
+
+ }
+
+ /** LSB ONE. */
+ public void test_getBitsFromInt32_02() {
+
+ final int b = 1;
+
+ assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 31/* len */));//x
+ assertEquals(0x00000001, getBits(b, 0/* off */, 32/* len */));
+ assertEquals(0x00000001, getBits(b, 31/* off */, 1/* len */));//x
+ assertEquals(0x00000001, getBits(b, 30/* off */, 2/* len */));
+
+ }
+
+ /**
+ * Bit ONE (1) set (remember, MSB is bit ZERO (0)).
+ */
+ public void test_getBitsFromByteArray_03() {
+
+ final int b = 1<<30;
+
+ assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
+ assertEquals(0x00000000, getBits(b, 0/* off */, 1/* len */));
+ assertEquals(0x00000001, getBits(b, 0/* off */, 2/* len */));
+ assertEquals(0x00000002, getBits(b, 1/* off */, 2/* len */));
+ assertEquals(0x00000004, getBits(b, 1/* off */, 3/* len */));
+
+ assertEquals(0x00000001, getBits(b, 1/* off */, 1/* len */));
+
+ assertEquals(0x40000000, getBits(b, 0/* off */, 32/* len */));
+ assertEquals(0x20000000, getBits(b, 0/* off */, 31/* len */));
+ assertEquals(0x10000000, getBits(b, 0/* off */, 30/* len */));
+ assertEquals(0x08000000, getBits(b, 0/* off */, 29/* len */));
+
+ }
+
+ /**
+ * MSB ONE (this test case is the mostly likely to run a foul of a sign bit
+ * extension).
+ */
+ public void test_getBitsFromByteArray_04() {
+
+ final int b = 1<<31;
+
+ assertEquals(0x00000000, getBits(b, 0/* off */, 0/* len */));
+ assertEquals(0x00000001, getBits(b, 0/* off */, 1/* len */));
+ assertEquals(0x00000002, getBits(b, 0/* off */, 2/* len */));
+ assertEquals(0x00000004, getBits(b, 0/* off */, 3/* len */));
+ assertEquals(0x00000008, getBits(b, 0/* off */, 4/* len */));
+
+ assertEquals(0x00000000, getBits(b, 1/* off */, 0/* len */));
+ assertEquals(0x00000000, getBits(b, 1/* off */, 1/* len */));
+ assertEquals(0x00000000, getBits(b, 1/* off */, 2/* len */));
+ assertEquals(0x00000000, getBits(b, 1/* off */, 3/* len */));
+
+ }
+
+ /**
+ * Slice in the 2nd byte.
+ */
+ public void test_getBitsFromByteArray_05() {
+
+ /*
+ * Four bits on starting at bit 11 (where MSB is bit zero).
+ *
+ * Note: For normal Java bit indexing with MSB 31, this is bit indices
+ * 20,19,18,17.
+ */
+ final int b = (1 << 20) | (1 << 19) | (1 << 18) | (1 << 17);
+
+ /*
+ * Test with a window extending from bit zero with a variety of bit
+ * lengths ranging from an end bit index one less than the first ONE bit
+ * through an end bit index beyond the last ONE bit.
+ */
+ assertEquals(0x00000000, getBits(b, 0/* off */, 11/* len */));
+ assertEquals(0x00000001, getBits(b, 0/* off */, 12/* len */));
+ assertEquals(0x00000003, getBits(b, 0/* off */, 13/* len */));
+ assertEquals(0x00000007, getBits(b, 0/* off */, 14/* len */));
+ assertEquals(0x0000000f, getBits(b, 0/* off */, 15/* len */));
+ assertEquals(0x0000001e, getBits(b, 0/* off */, 16/* len */));
+ assertEquals(0x0000003c, getBits(b, 0/* off */, 17/* len */));
+ assertEquals(0x00000078, getBits(b, 0/* off */, 18/* len */));
+ assertEquals(0x000000f0, getBits(b, 0/* off */, 19/* len */));
+
+ /*
+ * Test with a 4-bit window that slides over the ONE bits. The initial
+ * window is to the left of the first ONE bit. The window slides right
+ * by one bit position for each assertion.
+ */
+ assertEquals(0x00000000, getBits(b, 7/* off */, 4/* len */));
+ assertEquals(0x00000001, getBits(b, 8/* off */, 4/* len */));
+ assertEquals(0x00000003, getBits(b, 9/* off */, 4/* len */));
+ assertEquals(0x00000007, getBits(b,10/* off */, 4/* len */));
+ assertEquals(0x0000000f, getBits(b,11/* off */, 4/* len */));
+ assertEquals(0x0000000e, getBits(b,12/* off */, 4/* len */));
+ assertEquals(0x0000000c, getBits(b,13/* off */, 4/* len */));
+ assertEquals(0x00000008, getBits(b,14/* off */, 4/* len */));
+ assertEquals(0x00000000, getBits(b,15/* off */, 4/* len */));
+
+ }
+
+ private int getBits(final int a, final int off, final int len) {
+
+ final int ret = BytesUtil.getBits(a, off, len);
+
+ if (log.isInfoEnabled()) {
+ final StringBuilder sb = new StringBuilder();
+ final Formatter f = new Formatter(sb);
+ f.format("[%32s] =(%2d:%2d)=> [%32s]", Integer.toBinaryString(a),
+ off, len, Integer.toBinaryString(ret));
+ log.info(sb.toString());
+ }
+
+ return ret;
+
+ }
+
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
