bloom/detail/fast_multiblock32_neon.hpp

0001 /* Copyright 2025 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See https://www.boost.org/libs/bloom for library home page.
0007  */
0008
0009 #ifndef BOOST_BLOOM_DETAIL_FAST_MULTIBLOCK32_NEON_HPP
0010 #define BOOST_BLOOM_DETAIL_FAST_MULTIBLOCK32_NEON_HPP
0011
0012 #include <boost/bloom/detail/multiblock_fpr_base.hpp>
0013 #include <boost/bloom/detail/mulx64.hpp>
0014 #include <boost/bloom/detail/neon.hpp>
0015 #include <boost/config.hpp>
0016 #include <cstddef>
0017 #include <cstdint>
0018
0019 namespace boost{
0020 namespace bloom{
0021
0022 #if defined(BOOST_MSVC)
0023 #pragma warning(push)
0024 #pragma warning(disable:4714) /* marked as __forceinline not inlined */
0025 #endif
0026
0027 /* https://stackoverflow.com/a/54018882/213114 */
0028
0029 #ifdef _MSC_VER
0030 #define BOOST_BLOOM_INIT_U32X4(w,x,y,z)            \
0031 {(std::uint32_t(w)+(unsigned long long(x)<<32)), \
0032  (std::uint32_t(y)+(unsigned long long(z)<<32))}
0033 #else
0034 #define BOOST_BLOOM_INIT_U32X4(w,x,y,z) \
0035 {std::uint32_t(w),std::uint32_t(x),std::uint32_t(y),std::uint32_t(z)}
0036 #endif
0037
0038 #define BOOST_BLOOM_INIT_U32X4X2(w0,x0,y0,z0,w1,x1,y1,z1) \
0039 {{BOOST_BLOOM_INIT_U32X4(w0,x0,y0,z0),BOOST_BLOOM_INIT_U32X4(w1,x1,y1,z1)}}
0040
0041 template<std::size_t K>
0042 struct fast_multiblock32:detail::multiblock_fpr_base<K>
0043 {
0044   static constexpr std::size_t k=K;
0045   using value_type=uint32x4x2_t[(k+7)/8];
0046   static constexpr std::size_t used_value_size=sizeof(std::uint32_t)*k;
0047
0048   static BOOST_FORCEINLINE void mark(value_type& x,std::uint64_t hash)
0049   {
0050     for(std::size_t i=0;i<k/8;++i){
0051       mark_uint32x4x2_t(x[i],hash,8);
0052       hash=detail::mulx64(hash);
0053     }
0054     if(k%8){
0055       mark_uint32x4x2_t(x[k/8],hash,k%8);
0056     }
0057   }
0058
0059   static BOOST_FORCEINLINE bool check(const value_type& x,std::uint64_t hash)
0060   {
0061     bool res=true;
0062     for(std::size_t i=0;i<k/8;++i){
0063       res&=check_uint32x4x2_t(x[i],hash,8);
0064       hash=detail::mulx64(hash);
0065     }
0066     if(k%8){
0067       res&=check_uint32x4x2_t(x[k/8],hash,k%8);
0068     }
0069     return res;
0070   }
0071
0072 private:
0073   static BOOST_FORCEINLINE uint32x4x2_t make_uint32x4x2_t(
0074     std::uint64_t hash,std::size_t kp)
0075   {
0076     static const uint32x4x2_t ones[8]={
0077       BOOST_BLOOM_INIT_U32X4X2(1,0,0,0,0,0,0,0),
0078       BOOST_BLOOM_INIT_U32X4X2(1,1,0,0,0,0,0,0),
0079       BOOST_BLOOM_INIT_U32X4X2(1,1,1,0,0,0,0,0),
0080       BOOST_BLOOM_INIT_U32X4X2(1,1,1,1,0,0,0,0),
0081       BOOST_BLOOM_INIT_U32X4X2(1,1,1,1,1,0,0,0),
0082       BOOST_BLOOM_INIT_U32X4X2(1,1,1,1,1,1,0,0),
0083       BOOST_BLOOM_INIT_U32X4X2(1,1,1,1,1,1,1,0),
0084       BOOST_BLOOM_INIT_U32X4X2(1,1,1,1,1,1,1,1)
0085     };
0086
0087     uint32x4_t h_lo=vreinterpretq_u32_u64(vdupq_n_u64(hash)),
0088                h_hi=h_lo;
0089
0090     h_lo=vreinterpretq_u32_u64(
0091       vshlq_u64(vreinterpretq_u64_u32(h_lo),(int64x2_t{0,5})));
0092     h_hi=vreinterpretq_u32_u64(
0093       vshlq_u64(vreinterpretq_u64_u32(h_hi),(int64x2_t{10,15})));
0094
0095     h_lo=vshrq_n_u32(h_lo,32-5);
0096     h_hi=vshrq_n_u32(h_hi,32-5);
0097
0098     return {
0099       vshlq_u32(ones[kp-1].val[0],vreinterpretq_s32_u32(h_lo)),
0100       vshlq_u32(ones[kp-1].val[1],vreinterpretq_s32_u32(h_hi))
0101     };
0102   }
0103
0104   static BOOST_FORCEINLINE void mark_uint32x4x2_t(
0105     uint32x4x2_t& x,std::uint64_t hash,std::size_t kp)
0106   {
0107     uint32x4x2_t h=make_uint32x4x2_t(hash,kp);
0108     x.val[0]=vorrq_u32(x.val[0],h.val[0]);
0109     x.val[1]=vorrq_u32(x.val[1],h.val[1]);
0110   }
0111
0112   static BOOST_FORCEINLINE bool check_uint32x4x2_t(
0113     const uint32x4x2_t& x,std::uint64_t hash,std::size_t kp)
0114   {
0115     uint32x4x2_t h=make_uint32x4x2_t(hash,kp);
0116     uint32x4_t   lo=vtstq_u32(x.val[0],h.val[0]);
0117     uint32x4_t   hi=vtstq_u32(x.val[1],h.val[1]);
0118     if(kp!=8){
0119       static const uint32x4x2_t masks[7]={
0120         BOOST_BLOOM_INIT_U32X4X2( 0,-1,-1,-1,-1,-1,-1,-1),
0121         BOOST_BLOOM_INIT_U32X4X2( 0, 0,-1,-1,-1,-1,-1,-1),
0122         BOOST_BLOOM_INIT_U32X4X2( 0, 0, 0,-1,-1,-1,-1,-1),
0123         BOOST_BLOOM_INIT_U32X4X2( 0, 0, 0, 0,-1,-1,-1,-1),
0124         BOOST_BLOOM_INIT_U32X4X2( 0, 0, 0, 0, 0,-1,-1,-1),
0125         BOOST_BLOOM_INIT_U32X4X2( 0, 0, 0, 0, 0, 0,-1,-1),
0126         BOOST_BLOOM_INIT_U32X4X2( 0, 0, 0, 0, 0, 0, 0,-1)
0127       };
0128
0129       lo=vorrq_u32(lo,masks[kp-1].val[0]);
0130       hi=vorrq_u32(hi,masks[kp-1].val[1]);
0131     }
0132     int64x2_t res=vreinterpretq_s64_u32(vandq_u32(lo,hi));
0133     return (vgetq_lane_s64(res,0)&vgetq_lane_s64(res,1))==-1;
0134   }
0135 };
0136
0137 #undef BOOST_BLOOM_INIT_U32X4X2
0138 #undef BOOST_BLOOM_INIT_U32X4
0139
0140 #if defined(BOOST_MSVC)
0141 #pragma warning(pop) /* C4714 */
0142 #endif
0143
0144 } /* namespace bloom */
0145 } /* namespace boost */
0146
0147 #endif