1 /* 2 3 Copyright (c) 2014-2016, Arvid Norberg, Alden Torres 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/config.hpp" 34 #include "libtorrent/aux_/ffs.hpp" 35 #include "libtorrent/aux_/byteswap.hpp" 36 37 #include "libtorrent/aux_/disable_warnings_push.hpp" 38 39 #if (defined _MSC_VER && _MSC_VER >= 1600 && (defined _M_IX86 || defined _M_X64)) 40 #include <nmmintrin.h> 41 #endif 42 43 #include "libtorrent/aux_/disable_warnings_pop.hpp" 44 45 namespace libtorrent { 46 namespace aux { 47 48 // returns the index of the first set bit. 49 // Use std::log2p1 in C++20 log2p1(std::uint32_t v)50 int log2p1(std::uint32_t v) 51 { 52 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn 53 static const int MultiplyDeBruijnBitPosition[32] = 54 { 55 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 56 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 57 }; 58 59 v |= v >> 1; // first round down to one less than a power of 2 60 v |= v >> 2; 61 v |= v >> 4; 62 v |= v >> 8; 63 v |= v >> 16; 64 65 return MultiplyDeBruijnBitPosition[std::uint32_t(v * 0x07C4ACDDU) >> 27]; 66 } 67 count_leading_zeros_sw(span<std::uint32_t const> buf)68 int count_leading_zeros_sw(span<std::uint32_t const> buf) 69 { 70 auto const num = int(buf.size()); 71 std::uint32_t const* ptr = buf.data(); 72 73 TORRENT_ASSERT(num >= 0); 74 TORRENT_ASSERT(ptr != nullptr); 75 76 for (int i = 0; i < num; i++) 77 { 78 if (ptr[i] == 0) continue; 79 return i * 32 + 31 - log2p1(aux::network_to_host(ptr[i])); 80 } 81 82 return num * 32; 83 } 84 count_leading_zeros_hw(span<std::uint32_t const> buf)85 int count_leading_zeros_hw(span<std::uint32_t const> buf) 86 { 87 auto const num = int(buf.size()); 88 std::uint32_t const* ptr = buf.data(); 89 90 TORRENT_ASSERT(num >= 0); 91 TORRENT_ASSERT(ptr != nullptr); 92 93 for (int i = 0; i < num; i++) 94 { 95 if (ptr[i] == 0) continue; 96 97 #if TORRENT_HAS_BUILTIN_CLZ 98 std::uint32_t const v = aux::network_to_host(ptr[i]); 99 return i * 32 + __builtin_clz(v); 100 #elif defined _MSC_VER 101 std::uint32_t const v = aux::network_to_host(ptr[i]); 102 DWORD pos; 103 _BitScanReverse(&pos, v); 104 return i * 32 + 31 - pos; 105 #else 106 TORRENT_ASSERT_FAIL(); 107 return -1; 108 #endif 109 } 110 111 return num * 32; 112 } 113 count_leading_zeros(span<std::uint32_t const> buf)114 int count_leading_zeros(span<std::uint32_t const> buf) 115 { 116 #if TORRENT_HAS_BUILTIN_CLZ || defined _MSC_VER 117 return aux::count_leading_zeros_hw(buf); 118 #else 119 return aux::count_leading_zeros_sw(buf); 120 #endif 121 } 122 count_trailing_ones_sw(span<std::uint32_t const> buf)123 int count_trailing_ones_sw(span<std::uint32_t const> buf) 124 { 125 auto const num = int(buf.size()); 126 std::uint32_t const* ptr = buf.data(); 127 128 TORRENT_ASSERT(num >= 0); 129 TORRENT_ASSERT(ptr != nullptr); 130 131 for (int i = num - 1; i >= 0; i--) 132 { 133 if (ptr[i] == 0xffffffff) continue; 134 std::uint32_t v = ~aux::network_to_host(ptr[i]); 135 136 for (int k = 0; k < 32; ++k, v >>= 1) 137 { 138 if ((v & 1) == 0) continue; 139 return (num - i - 1) * 32 + k; 140 } 141 } 142 143 return num * 32; 144 } 145 count_trailing_ones_hw(span<std::uint32_t const> buf)146 int count_trailing_ones_hw(span<std::uint32_t const> buf) 147 { 148 auto const num = int(buf.size()); 149 std::uint32_t const* ptr = buf.data(); 150 151 TORRENT_ASSERT(num >= 0); 152 TORRENT_ASSERT(ptr != nullptr); 153 154 for (int i = num - 1; i >= 0; i--) 155 { 156 if (ptr[i] == 0xffffffff) continue; 157 158 #if TORRENT_HAS_BUILTIN_CTZ 159 std::uint32_t const v = ~aux::network_to_host(ptr[i]); 160 return (num - i - 1) * 32 + __builtin_ctz(v); 161 #elif defined _MSC_VER 162 std::uint32_t const v = ~aux::network_to_host(ptr[i]); 163 DWORD pos; 164 _BitScanForward(&pos, v); 165 return (num - i - 1) * 32 + pos; 166 #else 167 TORRENT_ASSERT_FAIL(); 168 return -1; 169 #endif 170 } 171 172 return num * 32; 173 } 174 count_trailing_ones(span<std::uint32_t const> buf)175 int count_trailing_ones(span<std::uint32_t const> buf) 176 { 177 #if TORRENT_HAS_BUILTIN_CTZ || defined _MSC_VER 178 return aux::count_trailing_ones_hw(buf); 179 #else 180 return aux::count_trailing_ones_sw(buf); 181 #endif 182 } 183 }} 184