You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2014/05/02 13:30:47 UTC
svn commit: r1591872 - in /subversion/trunk/subversion:
libsvn_subr/bit_array.c tests/libsvn_subr/bit-array-test.c
Author: stefan2
Date: Fri May 2 11:30:47 2014
New Revision: 1591872
URL: http://svn.apache.org/r1591872
Log:
Follow-up to r1590982: Fix an out-of-bounds copy and factor out most
of the address / offset calculations to make the code easier to read.
* subversion/libsvn_subr/bit_array.c
(svn_bit_array__set): When re-allocating the array, copy only data
*previously* allocated. Use explicit variables
for the various stages of address calculation.
Use almost the code for bit set as for reset.
(svn_bit_array__get): Use explicit variables for the various stages
of address calculation.
* subversion/tests/libsvn_subr/bit-array-test.c
(test_sparse): New test checking for proper array growth and
(implicitly) for sparse allocation.
(test_funcs): Register new test.
Found by: ivan
Modified:
subversion/trunk/subversion/libsvn_subr/bit_array.c
subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c
Modified: subversion/trunk/subversion/libsvn_subr/bit_array.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/bit_array.c?rev=1591872&r1=1591871&r2=1591872&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_subr/bit_array.c (original)
+++ subversion/trunk/subversion/libsvn_subr/bit_array.c Fri May 2 11:30:47 2014
@@ -103,12 +103,21 @@ svn_bit_array__set(svn_bit_array__t *arr
{
unsigned char *block;
+ /* Index within ARRAY->BLOCKS for the block containing bit IDX. */
+ apr_size_t block_idx = idx / BLOCK_SIZE_BITS;
+
+ /* Within that block, index of the byte containing IDX. */
+ apr_size_t byte_idx = (idx % BLOCK_SIZE_BITS) / 8;
+
+ /* Within that byte, index of the bit corresponding to IDX. */
+ apr_size_t bit_idx = (idx % BLOCK_SIZE_BITS) % 8;
+
/* If IDX is outside the allocated range, we _may_ have to grow it.
*
* Be sure to use division instead of multiplication as we need to cover
* the full value range of APR_SIZE_T for the bit indexes.
*/
- if (idx / BLOCK_SIZE_BITS >= array->block_count)
+ if (block_idx >= array->block_count)
{
apr_size_t new_count;
unsigned char **new_blocks;
@@ -124,7 +133,8 @@ svn_bit_array__set(svn_bit_array__t *arr
*/
new_count = select_data_size(idx);
new_blocks = apr_pcalloc(array->pool, new_count * sizeof(*new_blocks));
- memcpy(new_blocks, array->blocks, new_count * sizeof(*new_blocks));
+ memcpy(new_blocks, array->blocks,
+ array->block_count * sizeof(*new_blocks));
array->blocks = new_blocks;
array->block_count = new_count;
}
@@ -132,7 +142,7 @@ svn_bit_array__set(svn_bit_array__t *arr
/* IDX is covered by ARRAY->BLOCKS now. */
/* Get the block that contains IDX. Auto-allocate it if missing. */
- block = array->blocks[idx / BLOCK_SIZE_BITS];
+ block = array->blocks[block_idx];
if (block == NULL)
{
/* Unallocated indexes are implicitly 0, so no actual allocation
@@ -144,14 +154,14 @@ svn_bit_array__set(svn_bit_array__t *arr
/* Allocate the previously missing block and clear it for our
* array[idx] == 0 default. */
block = apr_pcalloc(array->pool, BLOCK_SIZE);
- array->blocks[idx / BLOCK_SIZE_BITS] = block;
+ array->blocks[block_idx] = block;
}
/* Set / reset one bit. Be sure to use unsigned shifts. */
if (value)
- block[(idx % BLOCK_SIZE_BITS) / 8] |= (unsigned char)(1u << (idx % 8));
+ block[byte_idx] |= (unsigned char)(1u << bit_idx);
else
- block[(idx % BLOCK_SIZE_BITS) / 8] &= (unsigned char)(255u - (1u << (idx % 8)));
+ block[byte_idx] &= ~(unsigned char)(1u << bit_idx);
}
svn_boolean_t
@@ -160,16 +170,25 @@ svn_bit_array__get(svn_bit_array__t *arr
{
unsigned char *block;
+ /* Index within ARRAY->BLOCKS for the block containing bit IDX. */
+ apr_size_t block_idx = idx / BLOCK_SIZE_BITS;
+
+ /* Within that block, index of the byte containing IDX. */
+ apr_size_t byte_idx = (idx % BLOCK_SIZE_BITS) / 8;
+
+ /* Within that byte, index of the bit corresponding to IDX. */
+ apr_size_t bit_idx = (idx % BLOCK_SIZE_BITS) % 8;
+
/* Indexes outside the allocated range are implicitly 0. */
- if (idx / BLOCK_SIZE_BITS >= array->block_count)
+ if (block_idx >= array->block_count)
return 0;
/* Same if the respective block has not been allocated. */
- block = array->blocks[idx / BLOCK_SIZE_BITS];
+ block = array->blocks[block_idx];
if (block == NULL)
return 0;
/* Extract one bit (get the byte, shift bit to LSB, extract it). */
- return (block[(idx % BLOCK_SIZE_BITS) / 8] >> (idx % 8)) & 1;
+ return (block[byte_idx] >> bit_idx) & 1;
}
Modified: subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c?rev=1591872&r1=1591871&r2=1591872&view=diff
==============================================================================
--- subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c (original)
+++ subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c Fri May 2 11:30:47 2014
@@ -96,6 +96,31 @@ test_get_set(apr_pool_t *pool)
return SVN_NO_ERROR;
}
+static svn_error_t *
+test_sparse(apr_pool_t *pool)
+{
+ svn_bit_array__t *array = svn_bit_array__create(0, pool);
+ apr_size_t i, k, min = 0x7ff00, max = 0x7ff00 + 1025, SCALE = 0x10000000;
+
+ /* All values default to 0. */
+ for (i = 0; i < 15; ++i)
+ for (k = i * SCALE + min; k < i * SCALE + max; ++k)
+ SVN_TEST_ASSERT(svn_bit_array__get(array, k) == 0);
+
+ /* Create a pattern, setting every other bit. Array will also auto-grow. */
+ for (i = 0; i < 15; ++i)
+ for (k = i * SCALE + min; k < i * SCALE + max; ++k)
+ if (k % 2)
+ svn_bit_array__set(array, k, 1);
+
+ /* Verify pattern */
+ for (i = 0; i < 15; ++i)
+ for (k = i * SCALE + min; k < i * SCALE + max; ++k)
+ SVN_TEST_ASSERT(svn_bit_array__get(array, k) == k % 2);
+
+ return SVN_NO_ERROR;
+}
+
/* An array of all test functions */
static int max_threads = 1;
@@ -107,6 +132,8 @@ static struct svn_test_descriptor_t test
"check entries to default to zero"),
SVN_TEST_PASS2(test_get_set,
"get / set entries"),
+ SVN_TEST_PASS2(test_sparse,
+ "get / set sparse entries"),
SVN_TEST_NULL
};