1 /* 2 3 Copyright (c) 2008-2018, Arvid Norberg 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with or without 7 modification, are permitted provided that the following conditions 8 are met: 9 10 * Redistributions of source code must retain the above copyright 11 notice, this list of conditions and the following disclaimer. 12 * Redistributions in binary form must reproduce the above copyright 13 notice, this list of conditions and the following disclaimer in 14 the documentation and/or other materials provided with the distribution. 15 * Neither the name of the author nor the names of its 16 contributors may be used to endorse or promote products derived 17 from this software without specific prior written permission. 18 19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 23 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 POSSIBILITY OF SUCH DAMAGE. 30 31 */ 32 33 #ifndef TORRENT_BITFIELD_HPP_INCLUDED 34 #define TORRENT_BITFIELD_HPP_INCLUDED 35 36 #include "libtorrent/assert.hpp" 37 #include "libtorrent/config.hpp" 38 #include "libtorrent/index_range.hpp" 39 #include "libtorrent/aux_/unique_ptr.hpp" 40 #include "libtorrent/aux_/byteswap.hpp" 41 #include "libtorrent/aux_/ffs.hpp" 42 43 #include <cstring> // for memset and memcpy 44 #include <cstdint> // uint32_t 45 46 namespace libtorrent { 47 48 // The bitfield type stores any number of bits as a bitfield 49 // in a heap allocated array. 50 struct TORRENT_EXPORT bitfield 51 { 52 // constructs a new bitfield. The default constructor creates an empty 53 // bitfield. ``bits`` is the size of the bitfield (specified in bits). 54 // ``val`` is the value to initialize the bits to. If not specified 55 // all bits are initialized to 0. 56 // 57 // The constructor taking a pointer ``b`` and ``bits`` copies a bitfield 58 // from the specified buffer, and ``bits`` number of bits (rounded up to 59 // the nearest byte boundary). 60 bitfield() noexcept = default; bitfieldlibtorrent::bitfield61 explicit bitfield(int bits) { resize(bits); } bitfieldlibtorrent::bitfield62 bitfield(int bits, bool val) { resize(bits, val); } bitfieldlibtorrent::bitfield63 bitfield(char const* b, int bits) { assign(b, bits); } bitfieldlibtorrent::bitfield64 bitfield(bitfield const& rhs) { assign(rhs.data(), rhs.size()); } 65 bitfield(bitfield&& rhs) noexcept = default; 66 67 // copy bitfield from buffer ``b`` of ``bits`` number of bits, rounded up to 68 // the nearest byte boundary. assignlibtorrent::bitfield69 void assign(char const* b, int const bits) 70 { 71 resize(bits); 72 if (bits > 0) 73 { 74 std::memcpy(buf(), b, std::size_t((bits + 7) / 8)); 75 clear_trailing_bits(); 76 } 77 } 78 79 // query bit at ``index``. Returns true if bit is 1, otherwise false. operator []libtorrent::bitfield80 bool operator[](int index) const noexcept 81 { return get_bit(index); } get_bitlibtorrent::bitfield82 bool get_bit(int index) const noexcept 83 { 84 TORRENT_ASSERT(index >= 0); 85 TORRENT_ASSERT(index < size()); 86 return (buf()[index / 32] & aux::host_to_network(0x80000000 >> (index & 31))) != 0; 87 } 88 89 // set bit at ``index`` to 0 (clear_bit) or 1 (set_bit). clear_bitlibtorrent::bitfield90 void clear_bit(int index) noexcept 91 { 92 TORRENT_ASSERT(index >= 0); 93 TORRENT_ASSERT(index < size()); 94 buf()[index / 32] &= aux::host_to_network(~(0x80000000 >> (index & 31))); 95 } set_bitlibtorrent::bitfield96 void set_bit(int index) noexcept 97 { 98 TORRENT_ASSERT(index >= 0); 99 TORRENT_ASSERT(index < size()); 100 buf()[index / 32] |= aux::host_to_network(0x80000000 >> (index & 31)); 101 } 102 103 // returns true if all bits in the bitfield are set 104 bool all_set() const noexcept; 105 106 // returns true if no bit in the bitfield is set none_setlibtorrent::bitfield107 bool none_set() const noexcept 108 { 109 if(size() == 0) return true; 110 111 const int words = num_words(); 112 std::uint32_t const* b = buf(); 113 for (int i = 0; i < words; ++i) 114 { 115 if (b[i] != 0) return false; 116 } 117 return true; 118 } 119 120 // returns the size of the bitfield in bits. sizelibtorrent::bitfield121 int size() const noexcept 122 { 123 int const bits = m_buf == nullptr ? 0 : int(m_buf[0]); 124 TORRENT_ASSERT(bits >= 0); 125 return bits; 126 } 127 128 // returns the number of 32 bit words are needed to represent all bits in 129 // this bitfield. num_wordslibtorrent::bitfield130 int num_words() const noexcept 131 { 132 return (size() + 31) / 32; 133 } 134 135 // returns true if the bitfield has zero size. emptylibtorrent::bitfield136 bool empty() const noexcept { return size() == 0; } 137 138 // returns a pointer to the internal buffer of the bitfield, or 139 // ``nullptr`` if it's empty. datalibtorrent::bitfield140 char const* data() const noexcept { return m_buf ? reinterpret_cast<char const*>(&m_buf[1]) : nullptr; } datalibtorrent::bitfield141 char* data() noexcept { return m_buf ? reinterpret_cast<char*>(&m_buf[1]) : nullptr; } 142 143 #if TORRENT_ABI_VERSION == 1 144 TORRENT_DEPRECATED byteslibtorrent::bitfield145 char const* bytes() const { return data(); } 146 #endif 147 148 // hidden operator =libtorrent::bitfield149 bitfield& operator=(bitfield const& rhs) 150 { 151 if (&rhs == this) return *this; 152 assign(rhs.data(), rhs.size()); 153 return *this; 154 } 155 bitfield& operator=(bitfield&& rhs) noexcept = default; 156 157 // swaps the bit-fields two variables refer to swaplibtorrent::bitfield158 void swap(bitfield& rhs) noexcept 159 { 160 std::swap(m_buf, rhs.m_buf); 161 } 162 163 // count the number of bits in the bitfield that are set to 1. 164 int count() const noexcept; 165 166 // returns the index of the first set bit in the bitfield, i.e. 1 bit. 167 int find_first_set() const noexcept; 168 169 // returns the index to the last cleared bit in the bitfield, i.e. 0 bit. 170 int find_last_clear() const noexcept; 171 172 // internal 173 struct const_iterator 174 { 175 friend struct bitfield; 176 177 using value_type = bool; 178 using difference_type = ptrdiff_t; 179 using pointer = bool const*; 180 using reference = bool&; 181 using iterator_category = std::forward_iterator_tag; 182 operator *libtorrent::bitfield::const_iterator183 bool operator*() noexcept { return (*buf & aux::host_to_network(bit)) != 0; } operator ++libtorrent::bitfield::const_iterator184 const_iterator& operator++() noexcept { inc(); return *this; } operator ++libtorrent::bitfield::const_iterator185 const_iterator operator++(int) noexcept 186 { const_iterator ret(*this); inc(); return ret; } operator --libtorrent::bitfield::const_iterator187 const_iterator& operator--() noexcept { dec(); return *this; } operator --libtorrent::bitfield::const_iterator188 const_iterator operator--(int) noexcept 189 { const_iterator ret(*this); dec(); return ret; } 190 const_iteratorlibtorrent::bitfield::const_iterator191 const_iterator() noexcept {} operator ==libtorrent::bitfield::const_iterator192 bool operator==(const_iterator const& rhs) const noexcept 193 { return buf == rhs.buf && bit == rhs.bit; } 194 operator !=libtorrent::bitfield::const_iterator195 bool operator!=(const_iterator const& rhs) const noexcept 196 { return buf != rhs.buf || bit != rhs.bit; } 197 198 private: inclibtorrent::bitfield::const_iterator199 void inc() 200 { 201 TORRENT_ASSERT(buf); 202 if (bit == 0x01) 203 { 204 bit = 0x80000000; 205 ++buf; 206 } 207 else 208 { 209 bit >>= 1; 210 } 211 } declibtorrent::bitfield::const_iterator212 void dec() 213 { 214 TORRENT_ASSERT(buf); 215 if (bit == 0x80000000) 216 { 217 bit = 0x01; 218 --buf; 219 } 220 else 221 { 222 bit <<= 1; 223 } 224 } const_iteratorlibtorrent::bitfield::const_iterator225 const_iterator(std::uint32_t const* ptr, int offset) 226 : buf(ptr), bit(0x80000000 >> offset) {} 227 std::uint32_t const* buf = nullptr; 228 std::uint32_t bit = 0x80000000; 229 }; 230 231 // internal beginlibtorrent::bitfield232 const_iterator begin() const noexcept { return const_iterator(m_buf ? buf() : nullptr, 0); } endlibtorrent::bitfield233 const_iterator end() const noexcept 234 { 235 if (m_buf) 236 return const_iterator(buf() + num_words() - (((size() & 31) == 0) ? 0 : 1), size() & 31); 237 else 238 return const_iterator(nullptr, size() & 31); 239 } 240 241 // set the size of the bitfield to ``bits`` length. If the bitfield is extended, 242 // the new bits are initialized to ``val``. 243 void resize(int bits, bool val); 244 void resize(int bits); 245 246 // set all bits in the bitfield to 1 (set_all) or 0 (clear_all). set_alllibtorrent::bitfield247 void set_all() noexcept 248 { 249 if (size() == 0) return; 250 std::memset(buf(), 0xff, std::size_t(num_words()) * 4); 251 clear_trailing_bits(); 252 } clear_alllibtorrent::bitfield253 void clear_all() noexcept 254 { 255 if (size() == 0) return; 256 std::memset(buf(), 0x00, std::size_t(num_words()) * 4); 257 } 258 259 // make the bitfield empty, of zero size. clearlibtorrent::bitfield260 void clear() noexcept { m_buf.reset(); } 261 262 private: 263 buflibtorrent::bitfield264 std::uint32_t const* buf() const noexcept { TORRENT_ASSERT(m_buf); return &m_buf[1]; } buflibtorrent::bitfield265 std::uint32_t* buf() noexcept { TORRENT_ASSERT(m_buf); return &m_buf[1]; } clear_trailing_bitslibtorrent::bitfield266 void clear_trailing_bits() noexcept 267 { 268 // clear the tail bits in the last byte 269 if (size() & 31) buf()[num_words() - 1] &= aux::host_to_network(0xffffffff << (32 - (size() & 31))); 270 } 271 272 // the first element is not part of the bitfield, it's the 273 // number of bits. 274 aux::unique_ptr<std::uint32_t[]> m_buf; 275 }; 276 277 template <typename IndexType> 278 struct typed_bitfield : bitfield 279 { typed_bitfieldlibtorrent::typed_bitfield280 typed_bitfield() noexcept {} typed_bitfieldlibtorrent::typed_bitfield281 typed_bitfield(typed_bitfield&& rhs) noexcept 282 : bitfield(std::forward<bitfield>(rhs)) 283 {} typed_bitfieldlibtorrent::typed_bitfield284 typed_bitfield(typed_bitfield const& rhs) 285 : bitfield(static_cast<bitfield const&>(rhs)) 286 {} typed_bitfieldlibtorrent::typed_bitfield287 typed_bitfield(bitfield&& rhs) noexcept : bitfield(std::forward<bitfield>(rhs)) {} // NOLINT typed_bitfieldlibtorrent::typed_bitfield288 typed_bitfield(bitfield const& rhs) : bitfield(rhs) {} // NOLINT operator =libtorrent::typed_bitfield289 typed_bitfield& operator=(typed_bitfield&& rhs) noexcept 290 { 291 this->bitfield::operator=(std::forward<bitfield>(rhs)); 292 return *this; 293 } operator =libtorrent::typed_bitfield294 typed_bitfield& operator=(typed_bitfield const& rhs) 295 { 296 this->bitfield::operator=(rhs); 297 return *this; 298 } 299 using bitfield::bitfield; 300 301 // returns an object that can be used in a range-for to iterate over all 302 // indices in the bitfield rangelibtorrent::typed_bitfield303 index_range<IndexType> range() const noexcept 304 { 305 return {IndexType{0}, end_index()}; 306 } 307 operator []libtorrent::typed_bitfield308 bool operator[](IndexType const index) const 309 { return this->bitfield::get_bit(static_cast<int>(index)); } 310 get_bitlibtorrent::typed_bitfield311 bool get_bit(IndexType const index) const 312 { return this->bitfield::get_bit(static_cast<int>(index)); } 313 clear_bitlibtorrent::typed_bitfield314 void clear_bit(IndexType const index) 315 { this->bitfield::clear_bit(static_cast<int>(index)); } 316 set_bitlibtorrent::typed_bitfield317 void set_bit(IndexType const index) 318 { this->bitfield::set_bit(static_cast<int>(index)); } 319 end_indexlibtorrent::typed_bitfield320 IndexType end_index() const noexcept { return IndexType(this->size()); } 321 }; 322 } 323 324 #endif // TORRENT_BITFIELD_HPP_INCLUDED 325