arrow/util/bitmap_visit.h

0001 // Licensed to the Apache Software Foundation (ASF) under one
0002 // or more contributor license agreements.  See the NOTICE file
0003 // distributed with this work for additional information
0004 // regarding copyright ownership.  The ASF licenses this file
0005 // to you under the Apache License, Version 2.0 (the
0006 // "License"); you may not use this file except in compliance
0007 // with the License.  You may obtain a copy of the License at
0008 //
0009 //   http://www.apache.org/licenses/LICENSE-2.0
0010 //
0011 // Unless required by applicable law or agreed to in writing,
0012 // software distributed under the License is distributed on an
0013 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
0014 // KIND, either express or implied.  See the License for the
0015 // specific language governing permissions and limitations
0016 // under the License.
0017
0018 #pragma once
0019
0020 #include <cstdint>
0021
0022 #include "arrow/util/bit_util.h"
0023 #include "arrow/util/bitmap_reader.h"
0024
0025 namespace arrow {
0026 namespace internal {
0027
0028 // A function that visits each bit in a bitmap and calls a visitor function with a
0029 // boolean representation of that bit. This is intended to be analogous to
0030 // GenerateBits.
0031 template <class Visitor>
0032 void VisitBits(const uint8_t* bitmap, int64_t start_offset, int64_t length,
0033                Visitor&& visit) {
0034   BitmapReader reader(bitmap, start_offset, length);
0035   for (int64_t index = 0; index < length; ++index) {
0036     visit(reader.IsSet());
0037     reader.Next();
0038   }
0039 }
0040
0041 // Like VisitBits(), but unrolls its main loop for better performance.
0042 template <class Visitor>
0043 void VisitBitsUnrolled(const uint8_t* bitmap, int64_t start_offset, int64_t length,
0044                        Visitor&& visit) {
0045   if (length == 0) {
0046     return;
0047   }
0048
0049   // Start by visiting any bits preceding the first full byte.
0050   int64_t num_bits_before_full_bytes =
0051       bit_util::RoundUpToMultipleOf8(start_offset) - start_offset;
0052   // Truncate num_bits_before_full_bytes if it is greater than length.
0053   if (num_bits_before_full_bytes > length) {
0054     num_bits_before_full_bytes = length;
0055   }
0056   // Use the non loop-unrolled VisitBits since we don't want to add branches
0057   VisitBits<Visitor>(bitmap, start_offset, num_bits_before_full_bytes, visit);
0058
0059   // Shift the start pointer to the first full byte and compute the
0060   // number of full bytes to be read.
0061   const uint8_t* first_full_byte = bitmap + bit_util::CeilDiv(start_offset, 8);
0062   const int64_t num_full_bytes = (length - num_bits_before_full_bytes) / 8;
0063
0064   // Iterate over each full byte of the input bitmap and call the visitor in
0065   // a loop-unrolled manner.
0066   for (int64_t byte_index = 0; byte_index < num_full_bytes; ++byte_index) {
0067     // Get the current bit-packed byte value from the bitmap.
0068     const uint8_t byte = *(first_full_byte + byte_index);
0069
0070     // Execute the visitor function on each bit of the current byte.
0071     visit(bit_util::GetBitFromByte(byte, 0));
0072     visit(bit_util::GetBitFromByte(byte, 1));
0073     visit(bit_util::GetBitFromByte(byte, 2));
0074     visit(bit_util::GetBitFromByte(byte, 3));
0075     visit(bit_util::GetBitFromByte(byte, 4));
0076     visit(bit_util::GetBitFromByte(byte, 5));
0077     visit(bit_util::GetBitFromByte(byte, 6));
0078     visit(bit_util::GetBitFromByte(byte, 7));
0079   }
0080
0081   // Write any leftover bits in the last byte.
0082   const int64_t num_bits_after_full_bytes = (length - num_bits_before_full_bytes) % 8;
0083   VisitBits<Visitor>(first_full_byte + num_full_bytes, 0, num_bits_after_full_bytes,
0084                      visit);
0085 }
0086
0087 }  // namespace internal
0088 }  // namespace arrow