]>
git.proxmox.com Git - ceph.git/blob - ceph/src/arrow/cpp/src/arrow/util/bitmap_generate.h
1 // Licensed to the Apache Software Foundation (ASF) under one
2 // or more contributor license agreements. See the NOTICE file
3 // distributed with this work for additional information
4 // regarding copyright ownership. The ASF licenses this file
5 // to you under the Apache License, Version 2.0 (the
6 // "License"); you may not use this file except in compliance
7 // with the License. You may obtain a copy of the License at
9 // http://www.apache.org/licenses/LICENSE-2.0
11 // Unless required by applicable law or agreed to in writing,
12 // software distributed under the License is distributed on an
13 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 // KIND, either express or implied. See the License for the
15 // specific language governing permissions and limitations
23 #include "arrow/buffer.h"
24 #include "arrow/memory_pool.h"
25 #include "arrow/result.h"
26 #include "arrow/util/bit_util.h"
27 #include "arrow/util/visibility.h"
32 // A std::generate() like function to write sequential bits into a bitmap area.
33 // Bits preceding the bitmap area are preserved, bits following the bitmap
34 // area may be clobbered.
36 template <class Generator
>
37 void GenerateBits(uint8_t* bitmap
, int64_t start_offset
, int64_t length
, Generator
&& g
) {
41 uint8_t* cur
= bitmap
+ start_offset
/ 8;
42 uint8_t bit_mask
= BitUtil::kBitmask
[start_offset
% 8];
43 uint8_t current_byte
= *cur
& BitUtil::kPrecedingBitmask
[start_offset
% 8];
45 for (int64_t index
= 0; index
< length
; ++index
) {
47 current_byte
= bit
? (current_byte
| bit_mask
) : current_byte
;
48 bit_mask
= static_cast<uint8_t>(bit_mask
<< 1);
51 *cur
++ = current_byte
;
56 *cur
++ = current_byte
;
60 // Like GenerateBits(), but unrolls its main loop for higher performance.
62 template <class Generator
>
63 void GenerateBitsUnrolled(uint8_t* bitmap
, int64_t start_offset
, int64_t length
,
65 static_assert(std::is_same
<decltype(std::declval
<Generator
>()()), bool>::value
,
66 "Functor passed to GenerateBitsUnrolled must return bool");
72 uint8_t* cur
= bitmap
+ start_offset
/ 8;
73 const uint64_t start_bit_offset
= start_offset
% 8;
74 uint8_t bit_mask
= BitUtil::kBitmask
[start_bit_offset
];
75 int64_t remaining
= length
;
77 if (bit_mask
!= 0x01) {
78 current_byte
= *cur
& BitUtil::kPrecedingBitmask
[start_bit_offset
];
79 while (bit_mask
!= 0 && remaining
> 0) {
80 current_byte
|= g() * bit_mask
;
81 bit_mask
= static_cast<uint8_t>(bit_mask
<< 1);
84 *cur
++ = current_byte
;
87 int64_t remaining_bytes
= remaining
/ 8;
88 uint8_t out_results
[8];
89 while (remaining_bytes
-- > 0) {
90 for (int i
= 0; i
< 8; ++i
) {
93 *cur
++ = (out_results
[0] | out_results
[1] << 1 | out_results
[2] << 2 |
94 out_results
[3] << 3 | out_results
[4] << 4 | out_results
[5] << 5 |
95 out_results
[6] << 6 | out_results
[7] << 7);
98 int64_t remaining_bits
= remaining
% 8;
102 while (remaining_bits
-- > 0) {
103 current_byte
|= g() * bit_mask
;
104 bit_mask
= static_cast<uint8_t>(bit_mask
<< 1);
106 *cur
++ = current_byte
;
110 } // namespace internal