常见的取模优化有 Montgomery multiplication、Barrett reduction 等。当模数固定时，编译器会帮我们进行 Barrett reduction 的优化，而当模数不固定时，这两种都需要手动实现。而手动实现的速度总会比编译器慢（比如模数啥的必须占一个寄存器位置）。
那么能不能在程序中内置编译器呢？即使能，也多半超过了码长限制。但是我们可以白嫖编译器的成果，让编译器对着某个模数优化，我们之后再改掉代码里的模数。
实现如下：
const int P=1000000007;
#ifdef _WIN32
#include<windows.h>
bool set_rwx(void*addr)
{
char tmp[8];
return VirtualProtect(addr, 0x1000, PAGE_EXECUTE_READWRITE, (PDWORD)tmp);
}
#else
#include<sys/mman.h>
bool set_rwx(void*addr)
{
return !mprotect(addr, 0x1000, PROT_READ | PROT_WRITE | PROT_EXEC);
}
#endif
namespace mod_jit
{
struct pointer{
union{uint64_t*ul;uint32_t*ui;uint16_t*us;uint64_t v;};
pointer(){}
template<typename T>pointer(T x){ul=(uint64_t*)x;}
};
pointer range_l,range_r;
bool add_segment(uint64_t addr,uint64_t elfsz,uint64_t memsz)
{
if(elfsz+0x10000<memsz)return 1; // skip global arrays
uint64_t tmp=range_l.v+addr+elfsz;
if(range_r.v<tmp)range_r.v=tmp;
return 0;
}
#ifdef _WIN32
void get_range()
{
pointer t=get_range;
t.v&=~0xfffull;
while(*t.ui!=0x905a4d)t.v-=0x1000;
range_l=t;
t.v+=*(t.ui+15);
int num=*(t.us+3);
t.v+=0x18+*(t.us+10);
for(;num--;t.v+=0x28){
if(*(t.ui+9)>>25&1)continue;
if(add_segment(*(t.ui+3),*(t.ui+4),*(t.ui+2)))break;
}
}
#else
void get_range()
{
pointer t=get_range;
t.v&=~0xfffull;
while(*t.ui!=0x464c457f)t.v-=0x1000;
int num=*(t.us+28);
range_l=t;
t.v+=*(t.ul+4);
for(;num--;t.v+=0x38){
if(add_segment(*(t.ul+2),*(t.ul+4),*(t.ul+5)))break;
}
}
#endif
void get_change(int P,std::function<void(uint32_t)>add_int,std::function<void(uint64_t)>add_ll)
{
assert(P>(1<<29)&&P<(1<<30));
auto tint=[&](uint32_t x){add_int(x);add_int(-x);};
auto tll=[&](uint64_t x){add_ll(x);add_ll(-x);};
for(int i=-3;i<=3;i++)tint(P+i);
tint(((((1ull<<30)-P)<<32)+P-1)/P);
for(int i=59;i<=61;i++)tint(((1ull<<i)+P-1)/P);
for(int i=91;i<=93;i++)tll(((__uint128_t(1)<<i)+P-1)/P);
}
int vc,tc,pl;
std::vector<std::pair<int,pointer>>p;
void record_int(uint32_t x)
{
pointer a=range_l,b=range_r;
b.v-=3;
while(a.v!=b.v)
{
if(*a.ui==x)p.push_back(std::make_pair(vc,a));
a.v++;
}
vc++;
}
void record_ll(uint64_t x)
{
pointer a=range_l,b=range_r;
b.v-=7;
while(a.v!=b.v)
{
if(*a.ul==x)p.push_back(std::make_pair(vc,a));
a.v++;
}
vc++;
}
void change_int(uint32_t x)
{
for(;pl<p.size()&&p[pl].first==tc;pl++)
*p[pl].second.ui=x;
tc++;
}
void change_ll(uint64_t x)
{
for(;pl<p.size()&&p[pl].first==tc;pl++)
*p[pl].second.ul=x;
tc++;
}
uint64_t anti_optimize_zero()
{
uint64_t res=0;
for(int i=0;i<0x100;i++){
res=res+55555^114514;
res^=res<<9;
}
return res^11608655508041216768ull;
}
struct init{init()
{
get_range();
get_change(P+anti_optimize_zero(),record_int,record_ll);
std::set<uint64_t>map_area;
for(auto&a:p)map_area.insert(a.second.v&~0xfffull);
for(uint64_t x:map_area)assert(set_rwx(*(void**)&x));
}}init_;
void change_mod(int P)
{
tc=pl=0;
get_change(P,change_int,change_ll);
}
}用法：粘上这坨，然后用这个固定模数 P 写代码。要改模数的时候调用 mod_jit::change_mod。
速度参考：https://loj.ac/s/1233497 （原始提交：https://loj.ac/s/1233405 https://loj.ac/s/1170461 ）
这坨代码的主要流程是，先找到程序基地址，然后读取每个段，得到整个程序的地址区间，接下来在程序中找到编译器可能优化出来的常数，把对应内存设为可修改的，每次 change_mod 时就修改他们。
然而这份代码也只是个概念验证，想粘个板子直接用，目前还不太现实。
有一个主要问题，这个找常数的过程找到的不一定真的是常数，他有可能是指令的一部分恰好和常数相同（虽然概率非常小）。为了解决这个问题，就需要把程序按指令划分开，虽然能做到（比如参考这个），但是成本会高得多。
另一个问题是，编译器优化出的常数，可能性非常多，很难枚举完。在 get_change 函数里面可以看到许多带 P 的表达式，他们勉强能覆盖大多数情况，但是显然不能覆盖所有情况。另外这里还要求 $2^{29}< P < 2^{30}$，这是因为编译器根据模数不同，生成的移位指令也不同，而想要写代码找出这些移位指令是比较困难的。（另一种解决方法是，对于每个 $2^k\sim 2^{k+1}$ 之间的 $P$ 都生成一份代码，这倒也许还不错）
鄂公网安备 42010202000505 号