You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2015/04/13 09:13:59 UTC
svn commit: r1673123 - in /lucene/dev/trunk/lucene: CHANGES.txt
core/src/java/org/apache/lucene/util/FixedBitSet.java
core/src/java/org/apache/lucene/util/LongBitSet.java
core/src/test/org/apache/lucene/util/TestLongBitSet.java
Author: jpountz
Date: Mon Apr 13 07:13:59 2015
New Revision: 1673123
URL: http://svn.apache.org/r1673123
Log:
LUCENE-6409: Fixed integer overflow in LongBitSet.ensureCapacity.
Modified:
lucene/dev/trunk/lucene/CHANGES.txt
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java
Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1673123&r1=1673122&r2=1673123&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Mon Apr 13 07:13:59 2015
@@ -88,6 +88,9 @@ Bug Fixes
* LUCENE-6416: BooleanQuery.extractTerms now only extracts terms from scoring
clauses. (Adrien Grand)
+* LUCENE-6409: Fixed integer overflow in LongBitSet.ensureCapacity.
+ (Luc Vanlerberghe via Adrien Grand)
+
API Changes
* LUCENE-6377: SearcherFactory#newSearcher now accepts the previous reader
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java?rev=1673123&r1=1673122&r2=1673123&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java Mon Apr 13 07:13:59 2015
@@ -60,11 +60,7 @@ public final class FixedBitSet extends B
/** returns the number of 64 bit words it would take to hold numBits */
public static int bits2words(int numBits) {
- int numLong = numBits >>> 6;
- if ((numBits & 63) != 0) {
- numLong++;
- }
- return numLong;
+ return ((numBits - 1) >> 6) + 1; // I.e.: get the word-offset of the last bit and add one (make sure to use >> so 0 returns 0!)
}
/**
@@ -334,7 +330,7 @@ public final class FixedBitSet extends B
int startWord = startIndex >> 6;
int endWord = (endIndex-1) >> 6;
- /*** Grrr, java shifting wraps around so -1L>>>64 == -1
+ /*** Grrr, java shifting uses only the lower 6 bits of the count so -1L>>>64 == -1
* for that reason, make sure not to use endmask if the bits to flip will
* be zero in the last word (redefine endWord to be the last changed...)
long startmask = -1L << (startIndex & 0x3f); // example: 11111...111000
@@ -342,7 +338,7 @@ public final class FixedBitSet extends B
***/
long startmask = -1L << startIndex;
- long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
+ long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex since only the lowest 6 bits are used
if (startWord == endWord) {
bits[startWord] ^= (startmask & endmask);
@@ -383,7 +379,7 @@ public final class FixedBitSet extends B
int endWord = (endIndex-1) >> 6;
long startmask = -1L << startIndex;
- long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
+ long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex since only the lowest 6 bits are used
if (startWord == endWord) {
bits[startWord] |= (startmask & endmask);
@@ -407,7 +403,7 @@ public final class FixedBitSet extends B
int endWord = (endIndex-1) >> 6;
long startmask = -1L << startIndex;
- long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
+ long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex since only the lowest 6 bits are used
// invert masks since we are clearing
startmask = ~startmask;
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java?rev=1673123&r1=1673122&r2=1673123&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java Mon Apr 13 07:13:59 2015
@@ -51,19 +51,15 @@ public final class LongBitSet {
if (numWords >= arr.length) {
arr = ArrayUtil.grow(arr, numWords + 1);
}
- return new LongBitSet(arr, arr.length << 6);
+ return new LongBitSet(arr, (long)arr.length << 6);
}
}
/** returns the number of 64 bit words it would take to hold numBits */
public static int bits2words(long numBits) {
- int numLong = (int) (numBits >>> 6);
- if ((numBits & 63) != 0) {
- numLong++;
- }
- return numLong;
+ return (int)((numBits - 1) >> 6) + 1; // I.e.: get the word-offset of the last bit and add one (make sure to use >> so 0 returns 0!)
}
-
+
public LongBitSet(long numBits) {
this.numBits = numBits;
bits = new long[bits2words(numBits)];
@@ -247,7 +243,7 @@ public final class LongBitSet {
int startWord = (int) (startIndex >> 6);
int endWord = (int) ((endIndex-1) >> 6);
- /*** Grrr, java shifting wraps around so -1L>>>64 == -1
+ /*** Grrr, java shifting uses only the lower 6 bits of the count so -1L>>>64 == -1
* for that reason, make sure not to use endmask if the bits to flip will
* be zero in the last word (redefine endWord to be the last changed...)
long startmask = -1L << (startIndex & 0x3f); // example: 11111...111000
@@ -255,7 +251,7 @@ public final class LongBitSet {
***/
long startmask = -1L << startIndex;
- long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
+ long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex since only the lowest 6 bits are used
if (startWord == endWord) {
bits[startWord] ^= (startmask & endmask);
@@ -287,7 +283,7 @@ public final class LongBitSet {
int endWord = (int) ((endIndex-1) >> 6);
long startmask = -1L << startIndex;
- long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
+ long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex since only the lowest 6 bits are used
if (startWord == endWord) {
bits[startWord] |= (startmask & endmask);
@@ -315,7 +311,7 @@ public final class LongBitSet {
int endWord = (int) ((endIndex-1) >> 6);
long startmask = -1L << startIndex;
- long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
+ long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex since only the lowest 6 bits are used
// invert masks since we are clearing
startmask = ~startmask;
Modified: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java?rev=1673123&r1=1673122&r2=1673123&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java Mon Apr 13 07:13:59 2015
@@ -317,4 +317,34 @@ public class TestLongBitSet extends Luce
assertFalse(newBits.get(1));
}
+ public void testHugeCapacity() {
+ long moreThanMaxInt = (long)Integer.MAX_VALUE + 5;
+
+ LongBitSet bits = new LongBitSet(42);
+
+ assertEquals(42, bits.length());
+
+ LongBitSet hugeBits = LongBitSet.ensureCapacity(bits, moreThanMaxInt);
+
+ assertTrue(hugeBits.length() >= moreThanMaxInt);
+ }
+
+ public void testBits2Words() {
+ assertEquals(0, LongBitSet.bits2words(0));
+ assertEquals(1, LongBitSet.bits2words(1));
+ // ...
+ assertEquals(1, LongBitSet.bits2words(64));
+ assertEquals(2, LongBitSet.bits2words(65));
+ // ...
+ assertEquals(2, LongBitSet.bits2words(128));
+ assertEquals(3, LongBitSet.bits2words(129));
+ // ...
+ assertEquals(1 << (31-6), LongBitSet.bits2words(1L << 31));
+ assertEquals((1 << (31-6)) + 1, LongBitSet.bits2words((1L << 31)) + 1);
+ // ...
+ assertEquals(1 << (32-6), LongBitSet.bits2words(1L << 32));
+ assertEquals((1 << (32-6)) + 1, LongBitSet.bits2words((1L << 32)) + 1);
+ // ...
+ assertEquals(Integer.MAX_VALUE, LongBitSet.bits2words((1L << 37) - 64));
+ }
}