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 #include "libtorrent/bitfield.hpp" 34 #include "libtorrent/aux_/numeric_cast.hpp" 35 #include "libtorrent/aux_/cpuid.hpp" 36 37 #ifdef _MSC_VER 38 #include <intrin.h> 39 #endif 40 41 namespace libtorrent { 42 all_set() const43 bool bitfield::all_set() const noexcept 44 { 45 if(size() == 0) return false; 46 47 int const words = size() / 32; 48 for (int i = 1; i < words + 1; ++i) 49 { 50 if (m_buf[i] != 0xffffffff) return false; 51 } 52 int const rest = size() & 31; 53 if (rest > 0) 54 { 55 std::uint32_t const mask = aux::host_to_network(0xffffffff << (32 - rest)); 56 if ((m_buf[words + 1] & mask) != mask) return false; 57 } 58 return true; 59 } 60 count() const61 int bitfield::count() const noexcept 62 { 63 int ret = 0; 64 int const words = num_words(); 65 #if TORRENT_HAS_SSE 66 if (aux::mmx_support) 67 { 68 for (int i = 1; i < words + 1; ++i) 69 { 70 #ifdef __GNUC__ 71 std::uint32_t cnt = 0; 72 __asm__("popcnt %1, %0" 73 : "=r"(cnt) 74 : "r"(m_buf[i])); 75 ret += cnt; 76 #else 77 ret += _mm_popcnt_u32(m_buf[i]); 78 #endif 79 } 80 81 TORRENT_ASSERT(ret <= size()); 82 TORRENT_ASSERT(ret >= 0); 83 return ret; 84 } 85 #endif // TORRENT_HAS_SSE 86 87 #if TORRENT_HAS_ARM_NEON && defined __arm__ 88 if (aux::arm_neon_support) 89 { 90 for (int i = 1; i < words + 1; ++i) 91 { 92 std::uint32_t cnt; 93 __asm__( 94 "vld1.u32 d0[0], [%1] \n" 95 "vcnt.u8 d0, d0 \n" 96 "vpaddl.u8 d0, d0 \n" 97 "vpaddl.u16 d0, d0 \n" 98 "vst1.u32 d0[0], [%0]" 99 :: "r"(&cnt), "r"(&m_buf[i]) 100 : "d0", "memory"); 101 ret += cnt; 102 } 103 104 TORRENT_ASSERT(ret <= size()); 105 TORRENT_ASSERT(ret >= 0); 106 return ret; 107 } 108 #endif // TORRENT_HAS_ARM_NEON 109 110 for (int i = 1; i < words + 1; ++i) 111 { 112 #if defined __GNUC__ || defined __clang__ 113 ret += __builtin_popcountl(m_buf[i]); 114 #else 115 std::uint32_t const v = m_buf[i]; 116 // from: 117 // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 118 static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers 119 static const std::uint32_t B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF}; 120 121 std::uint32_t c = v - ((v >> 1) & B[0]); 122 c = ((c >> S[1]) & B[1]) + (c & B[1]); 123 c = ((c >> S[2]) + c) & B[2]; 124 c = ((c >> S[3]) + c) & B[3]; 125 c = ((c >> S[4]) + c) & B[4]; 126 ret += c; 127 TORRENT_ASSERT(ret <= size()); 128 #endif 129 } 130 131 TORRENT_ASSERT(ret <= size()); 132 TORRENT_ASSERT(ret >= 0); 133 return ret; 134 } 135 resize(int const bits,bool const val)136 void bitfield::resize(int const bits, bool const val) 137 { 138 if (bits == size()) return; 139 140 int const s = size(); 141 int const b = size() & 31; 142 resize(bits); 143 if (s >= size()) return; 144 int const old_size_words = (s + 31) / 32; 145 int const new_size_words = num_words(); 146 if (val) 147 { 148 if (old_size_words && b) buf()[old_size_words - 1] |= aux::host_to_network(0xffffffff >> b); 149 if (old_size_words < new_size_words) 150 std::memset(buf() + old_size_words, 0xff 151 , static_cast<std::size_t>(new_size_words - old_size_words) * 4); 152 clear_trailing_bits(); 153 } 154 else 155 { 156 if (old_size_words < new_size_words) 157 std::memset(buf() + old_size_words, 0x00 158 , static_cast<std::size_t>(new_size_words - old_size_words) * 4); 159 } 160 TORRENT_ASSERT(size() == bits); 161 } 162 resize(int const bits)163 void bitfield::resize(int const bits) 164 { 165 if (bits == size()) return; 166 167 TORRENT_ASSERT(bits >= 0); 168 if (bits == 0) 169 { 170 m_buf.reset(); 171 return; 172 } 173 int const new_size_words = (bits + 31) / 32; 174 int const cur_size_words = num_words(); 175 if (cur_size_words != new_size_words) 176 { 177 aux::unique_ptr<std::uint32_t[]> b(new std::uint32_t[std::size_t(new_size_words + 1)]); 178 #ifdef BOOST_NO_EXCEPTIONS 179 if (b == nullptr) std::terminate(); 180 #endif 181 b[0] = aux::numeric_cast<std::uint32_t>(bits); 182 if (m_buf) std::memcpy(&b[1], buf() 183 , aux::numeric_cast<std::size_t>(std::min(new_size_words, cur_size_words) * 4)); 184 if (new_size_words > cur_size_words) 185 { 186 std::memset(&b[1 + cur_size_words], 0 187 , aux::numeric_cast<std::size_t>((new_size_words - cur_size_words) * 4)); 188 } 189 m_buf = std::move(b); 190 } 191 else 192 { 193 m_buf[0] = aux::numeric_cast<std::uint32_t>(bits); 194 } 195 196 clear_trailing_bits(); 197 TORRENT_ASSERT(size() == bits); 198 } 199 find_first_set() const200 int bitfield::find_first_set() const noexcept 201 { 202 int const num = num_words(); 203 if (num == 0) return -1; 204 int const count = aux::count_leading_zeros({&m_buf[1], num}); 205 return count != num * 32 ? count : -1; 206 } 207 find_last_clear() const208 int bitfield::find_last_clear() const noexcept 209 { 210 int const num = num_words(); 211 if (num == 0) return - 1; 212 int const size = this->size(); 213 std::uint32_t const mask = 0xffffffff << (32 - (size & 31)); 214 std::uint32_t const last = m_buf[num] ^ aux::host_to_network(mask); 215 int const ext = aux::count_trailing_ones(~last) - (31 - (size % 32)); 216 return last != 0 217 ? (num - 1) * 32 + ext 218 : size - (aux::count_trailing_ones({&m_buf[1], num - 1}) + ext); 219 } 220 221 static_assert(std::is_nothrow_move_constructible<bitfield>::value 222 , "should be nothrow move constructible"); 223 static_assert(std::is_nothrow_move_assignable<bitfield>::value 224 , "should be nothrow move assignable"); 225 static_assert(std::is_nothrow_default_constructible<bitfield>::value 226 , "should be nothrow default constructible"); 227 228 static_assert(std::is_nothrow_move_constructible<typed_bitfield<int>>::value 229 , "should be nothrow move constructible"); 230 static_assert(std::is_nothrow_move_assignable<typed_bitfield<int>>::value 231 , "should be nothrow move assignable"); 232 static_assert(std::is_nothrow_default_constructible<typed_bitfield<int>>::value 233 , "should be nothrow default constructible"); 234 } 235