You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by uw...@apache.org on 2018/09/22 15:04:05 UTC
[arrow] branch master updated: ARROW-3143: [C++] CopyBitmap into
existing memory
This is an automated email from the ASF dual-hosted git repository.
uwe pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/arrow.git
The following commit(s) were added to refs/heads/master by this push:
new ba83816 ARROW-3143: [C++] CopyBitmap into existing memory
ba83816 is described below
commit ba838160489723c9cd7fd50ce2b9703f4a060665
Author: Korn, Uwe <Uw...@blue-yonder.com>
AuthorDate: Sat Sep 22 17:03:55 2018 +0200
ARROW-3143: [C++] CopyBitmap into existing memory
Author: Korn, Uwe <Uw...@blue-yonder.com>
Closes #2526 from xhochy/ARROW-3143 and squashes the following commits:
694332b2 <Korn, Uwe> Only restore trailing bits if needed
7669ba2c <Korn, Uwe> Incorporate review comments
6e7178e2 <Korn, Uwe> ARROW-3143: CopyBitmap into existing memory
---
cpp/src/arrow/util/bit-util-test.cc | 86 ++++++++++++++++++++++++++++
cpp/src/arrow/util/bit-util.cc | 111 +++++++++++++++++++++++++++---------
cpp/src/arrow/util/bit-util.h | 24 ++++++++
3 files changed, 194 insertions(+), 27 deletions(-)
diff --git a/cpp/src/arrow/util/bit-util-test.cc b/cpp/src/arrow/util/bit-util-test.cc
index 48b4ff1..29ac2aa 100644
--- a/cpp/src/arrow/util/bit-util-test.cc
+++ b/cpp/src/arrow/util/bit-util-test.cc
@@ -519,6 +519,92 @@ TEST(BitUtilTests, TestCopyBitmap) {
}
}
+TEST(BitUtilTests, TestCopyBitmapPreAllocated) {
+ const int kBufferSize = 1000;
+ std::vector<int64_t> lengths = {kBufferSize * 8 - 4, kBufferSize * 8};
+ std::vector<int64_t> offsets = {0, 12, 16, 32, 37, 63, 64, 128};
+
+ std::shared_ptr<Buffer> buffer;
+ ASSERT_OK(AllocateBuffer(kBufferSize, &buffer));
+ memset(buffer->mutable_data(), 0, kBufferSize);
+ random_bytes(kBufferSize, 0, buffer->mutable_data());
+ const uint8_t* src = buffer->data();
+
+ std::shared_ptr<Buffer> other_buffer;
+ // Add 16 byte padding on both sides
+ ASSERT_OK(AllocateBuffer(kBufferSize + 32, &other_buffer));
+ memset(other_buffer->mutable_data(), 0, kBufferSize + 32);
+ random_bytes(kBufferSize + 32, 0, other_buffer->mutable_data());
+ const uint8_t* other = other_buffer->data();
+
+ for (int64_t num_bits : lengths) {
+ for (int64_t offset : offsets) {
+ for (int64_t dest_offset : offsets) {
+ const int64_t copy_length = num_bits - offset;
+
+ std::shared_ptr<Buffer> copy;
+ ASSERT_OK(AllocateBuffer(other_buffer->size(), ©));
+ memcpy(copy->mutable_data(), other_buffer->data(), other_buffer->size());
+ CopyBitmap(src, offset, copy_length, copy->mutable_data(), dest_offset);
+
+ for (int64_t i = 0; i < dest_offset; ++i) {
+ ASSERT_EQ(BitUtil::GetBit(other, i), BitUtil::GetBit(copy->data(), i));
+ }
+ for (int64_t i = 0; i < copy_length; ++i) {
+ ASSERT_EQ(BitUtil::GetBit(src, i + offset),
+ BitUtil::GetBit(copy->data(), i + dest_offset));
+ }
+ for (int64_t i = dest_offset + copy_length; i < (other_buffer->size() * 8); ++i) {
+ ASSERT_EQ(BitUtil::GetBit(other, i), BitUtil::GetBit(copy->data(), i));
+ }
+ }
+ }
+ }
+}
+
+TEST(BitUtilTests, TestCopyAndInvertBitmapPreAllocated) {
+ const int kBufferSize = 1000;
+ std::vector<int64_t> lengths = {kBufferSize * 8 - 4, kBufferSize * 8};
+ std::vector<int64_t> offsets = {0, 12, 16, 32, 37, 63, 64, 128};
+
+ std::shared_ptr<Buffer> buffer;
+ ASSERT_OK(AllocateBuffer(kBufferSize, &buffer));
+ memset(buffer->mutable_data(), 0, kBufferSize);
+ random_bytes(kBufferSize, 0, buffer->mutable_data());
+ const uint8_t* src = buffer->data();
+
+ std::shared_ptr<Buffer> other_buffer;
+ // Add 16 byte padding on both sides
+ ASSERT_OK(AllocateBuffer(kBufferSize + 32, &other_buffer));
+ memset(other_buffer->mutable_data(), 0, kBufferSize + 32);
+ random_bytes(kBufferSize + 32, 0, other_buffer->mutable_data());
+ const uint8_t* other = other_buffer->data();
+
+ for (int64_t num_bits : lengths) {
+ for (int64_t offset : offsets) {
+ for (int64_t dest_offset : offsets) {
+ const int64_t copy_length = num_bits - offset;
+
+ std::shared_ptr<Buffer> copy;
+ ASSERT_OK(AllocateBuffer(other_buffer->size(), ©));
+ memcpy(copy->mutable_data(), other_buffer->data(), other_buffer->size());
+ InvertBitmap(src, offset, copy_length, copy->mutable_data(), dest_offset);
+
+ for (int64_t i = 0; i < dest_offset; ++i) {
+ ASSERT_EQ(BitUtil::GetBit(other, i), BitUtil::GetBit(copy->data(), i));
+ }
+ for (int64_t i = 0; i < copy_length; ++i) {
+ ASSERT_EQ(BitUtil::GetBit(src, i + offset),
+ !BitUtil::GetBit(copy->data(), i + dest_offset));
+ }
+ for (int64_t i = dest_offset + copy_length; i < (other_buffer->size() * 8); ++i) {
+ ASSERT_EQ(BitUtil::GetBit(other, i), BitUtil::GetBit(copy->data(), i));
+ }
+ }
+ }
+ }
+}
+
TEST(BitUtil, CeilDiv) {
EXPECT_EQ(BitUtil::CeilDiv(0, 1), 0);
EXPECT_EQ(BitUtil::CeilDiv(1, 1), 1);
diff --git a/cpp/src/arrow/util/bit-util.cc b/cpp/src/arrow/util/bit-util.cc
index cd3e6d1..604fba4 100644
--- a/cpp/src/arrow/util/bit-util.cc
+++ b/cpp/src/arrow/util/bit-util.cc
@@ -107,48 +107,95 @@ int64_t CountSetBits(const uint8_t* data, int64_t bit_offset, int64_t length) {
return count;
}
-template <bool invert_bits>
-Status TransferBitmap(MemoryPool* pool, const uint8_t* data, int64_t offset,
- int64_t length, std::shared_ptr<Buffer>* out) {
- std::shared_ptr<Buffer> buffer;
- RETURN_NOT_OK(AllocateEmptyBitmap(pool, length, &buffer));
- uint8_t* dest = buffer->mutable_data();
-
+template <bool invert_bits, bool restore_trailing_bits>
+void TransferBitmap(const uint8_t* data, int64_t offset, int64_t length,
+ int64_t dest_offset, uint8_t* dest) {
int64_t byte_offset = offset / 8;
int64_t bit_offset = offset % 8;
+ int64_t dest_byte_offset = dest_offset / 8;
+ int64_t dest_bit_offset = dest_offset % 8;
int64_t num_bytes = BitUtil::BytesForBits(length);
- int64_t bits_to_zero = num_bytes * 8 - length;
+ // Shift dest by its byte offset
+ dest += dest_byte_offset;
- if (bit_offset > 0) {
- uint32_t carry_mask = BitUtil::kBitmask[bit_offset] - 1U;
- uint32_t carry_shift = 8U - static_cast<uint32_t>(bit_offset);
+ if (dest_bit_offset > 0) {
+ internal::BitmapReader valid_reader(data, offset, length);
+ internal::BitmapWriter valid_writer(dest, dest_bit_offset, length);
- uint32_t carry = 0U;
- if (BitUtil::BytesForBits(length + bit_offset) > num_bytes) {
- carry = (data[byte_offset + num_bytes] & carry_mask) << carry_shift;
+ for (int64_t i = 0; i < length; i++) {
+ if (invert_bits ^ valid_reader.IsSet()) {
+ valid_writer.Set();
+ } else {
+ valid_writer.Clear();
+ }
+ valid_reader.Next();
+ valid_writer.Next();
+ }
+ valid_writer.Finish();
+ } else {
+ // Take care of the trailing bits in the last byte
+ int64_t trailing_bits = num_bytes * 8 - length;
+ uint8_t trail = 0;
+ if (trailing_bits && restore_trailing_bits) {
+ trail = dest[num_bytes - 1];
}
- int64_t i = num_bytes - 1;
- while (i + 1 > 0) {
- uint8_t cur_byte = data[byte_offset + i];
+ if (bit_offset > 0) {
+ uint8_t carry_mask = BitUtil::kPrecedingBitmask[bit_offset];
+ uint8_t carry_shift = static_cast<uint8_t>(8U - static_cast<uint8_t>(bit_offset));
+
+ uint8_t carry = 0U;
+ if (BitUtil::BytesForBits(length + bit_offset) > num_bytes) {
+ carry = static_cast<uint8_t>((data[byte_offset + num_bytes] & carry_mask)
+ << carry_shift);
+ }
+
+ int64_t i = num_bytes - 1;
+ while (i + 1 > 0) {
+ uint8_t cur_byte = data[byte_offset + i];
+ if (invert_bits) {
+ dest[i] = static_cast<uint8_t>(~((cur_byte >> bit_offset) | carry));
+ } else {
+ dest[i] = static_cast<uint8_t>((cur_byte >> bit_offset) | carry);
+ }
+ carry = static_cast<uint8_t>((cur_byte & carry_mask) << carry_shift);
+ --i;
+ }
+ } else {
if (invert_bits) {
- dest[i] = static_cast<uint8_t>(~((cur_byte >> bit_offset) | carry));
+ for (int64_t i = 0; i < num_bytes; i++) {
+ dest[i] = static_cast<uint8_t>(~(data[byte_offset + i]));
+ }
} else {
- dest[i] = static_cast<uint8_t>((cur_byte >> bit_offset) | carry);
+ std::memcpy(dest, data + byte_offset, static_cast<size_t>(num_bytes));
}
- carry = (cur_byte & carry_mask) << carry_shift;
- --i;
}
- } else {
- if (invert_bits) {
- for (int64_t i = 0; i < num_bytes; i++) {
- dest[i] = static_cast<uint8_t>(~(data[byte_offset + i]));
+
+ if (restore_trailing_bits) {
+ for (int i = 0; i < trailing_bits; i++) {
+ if (BitUtil::GetBit(&trail, i + 8 - trailing_bits)) {
+ BitUtil::SetBit(dest, length + i);
+ } else {
+ BitUtil::ClearBit(dest, length + i);
+ }
}
- } else {
- std::memcpy(dest, data + byte_offset, static_cast<size_t>(num_bytes));
}
}
+}
+template <bool invert_bits>
+Status TransferBitmap(MemoryPool* pool, const uint8_t* data, int64_t offset,
+ int64_t length, std::shared_ptr<Buffer>* out) {
+ std::shared_ptr<Buffer> buffer;
+ RETURN_NOT_OK(AllocateEmptyBitmap(pool, length, &buffer));
+ uint8_t* dest = buffer->mutable_data();
+
+ TransferBitmap<invert_bits, false>(data, offset, length, 0, dest);
+
+ // As we have freshly allocated this bitmap, we should take care of zeroing the remaing
+ // bits.
+ int64_t num_bytes = BitUtil::BytesForBits(length);
+ int64_t bits_to_zero = num_bytes * 8 - length;
for (int64_t i = length; i < length + bits_to_zero; ++i) {
// Both branches may copy extra bits - unsetting to match specification.
BitUtil::ClearBit(dest, i);
@@ -158,6 +205,16 @@ Status TransferBitmap(MemoryPool* pool, const uint8_t* data, int64_t offset,
return Status::OK();
}
+void CopyBitmap(const uint8_t* data, int64_t offset, int64_t length, uint8_t* dest,
+ int64_t dest_offset) {
+ TransferBitmap<false, true>(data, offset, length, dest_offset, dest);
+}
+
+void InvertBitmap(const uint8_t* data, int64_t offset, int64_t length, uint8_t* dest,
+ int64_t dest_offset) {
+ TransferBitmap<true, true>(data, offset, length, dest_offset, dest);
+}
+
Status CopyBitmap(MemoryPool* pool, const uint8_t* data, int64_t offset, int64_t length,
std::shared_ptr<Buffer>* out) {
return TransferBitmap<false>(pool, data, offset, length, out);
diff --git a/cpp/src/arrow/util/bit-util.h b/cpp/src/arrow/util/bit-util.h
index 4696a8c..871636f 100644
--- a/cpp/src/arrow/util/bit-util.h
+++ b/cpp/src/arrow/util/bit-util.h
@@ -570,6 +570,30 @@ ARROW_EXPORT
Status CopyBitmap(MemoryPool* pool, const uint8_t* bitmap, int64_t offset, int64_t length,
std::shared_ptr<Buffer>* out);
+/// Copy a bit range of an existing bitmap into an existing bitmap
+///
+/// \param[in] bitmap source data
+/// \param[in] offset bit offset into the source data
+/// \param[in] length number of bits to copy
+/// \param[in] dest_offset bit offset into the destination
+/// \param[out] dest the destination buffer, must have at least space for (offset +
+/// length) bits
+ARROW_EXPORT
+void CopyBitmap(const uint8_t* bitmap, int64_t offset, int64_t length, uint8_t* dest,
+ int64_t dest_offset);
+
+/// Invert a bit range of an existing bitmap into an existing bitmap
+///
+/// \param[in] bitmap source data
+/// \param[in] offset bit offset into the source data
+/// \param[in] length number of bits to copy
+/// \param[in] dest_offset bit offset into the destination
+/// \param[out] dest the destination buffer, must have at least space for (offset +
+/// length) bits
+ARROW_EXPORT
+void InvertBitmap(const uint8_t* bitmap, int64_t offset, int64_t length, uint8_t* dest,
+ int64_t dest_offset);
+
/// Invert a bit range of an existing bitmap
///
/// \param[in] pool memory pool to allocate memory from