AtCoder でも colun 法を

AtCoder でも colun 法が使えたというだけの話。

colun 法とは

およそ6年前のこと。 TopCoder SRM 620 Div1 Easy で、再帰の引数を増やしすぎるとスタックオーバーフローする問題が出たらしい。

これを、「自分で確保したヒープ領域に rsp ポインタを移動させる」という類稀なる方法によって colun 氏が解決したらしい。 方法は簡単で、プログラムのはじめに

lint esp_org,esp_new;
const int size=128*1024*1024;
void* p=malloc(size);
esp_new=(lint)p+size-1;
void * stack_extend_memory_ = malloc(size);
void * stack_extend_origin_memory_;
char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);
*stack_extend_dummy_memory_ = 0;
asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));

を、おわりに

asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));
free(stack_extend_memory_);

をつけるだけ。 アセンブリで rsp ポインタを退避させるコードを書いている。

これで、権限の必要なコマンドの実行なしでもスタック領域（に見えるヒープ領域）を好きに使える！（最悪）

競プロテクニックの中で kaage 法に並ぶ黒魔術だと思う。

ABC168-F . (Single Dot)

座圧して走査するだけの問題なのだが、再帰で書いたらどうやらスタックオーバーフローするらしい。

スタックオーバーフローした提出はこちら。

スタックオーバーフローで RE する

ここで、黒魔術が使える。 先ほどのコードを最初と最後に付け加えて、提出ッ！

colun 法の威力

通った…!?!?!?

これが colun 法の威力。 AtCoder でも colun 法が使えるよというお話でした。

ちなみに、もっと言うと最後の free をサボってメモリリークしても、main でやればだいたい通る。
流石にこれは行儀が悪すぎるが