よく忘れるのでメモとして。ちなみにlong long版は今書きました…
前提
qsort関数には比較関数のポインタを渡す必要がありますが、このポインタ部分には機械語を埋め込むことが可能です。
コードゴルフには必要不可欠となります。
この前提を書くのを忘れていました、すみません(170323)
元祖はshinh氏の資料です(おそらく).
int
- 基本形。
- (例として昇順64bit UTF-8環境の場合)
\u05cb\7+\6Ðを使うと2文字*2バイト削減になります(05cbなる文字 は割り当てがないので気合で入れるしかありませんが)。
昇順
32bit
59 pop %ecx
58 pop %eax
5a pop %edx
51 push %ecx
51 push %ecx
51 push %ecx
8b00 mov (%eax),%eax
2b02 sub (%edx),%eax
c3 ret
"YXZQQQ\x8b\0+\2\xc3"
64bit
8b07 mov (%rdi), %eax
2b06 sub (%rsi), %eax
c3 ret
"\x8b\7+\6\xc3"
降順
32bit
59 pop %ecx
58 pop %edx
5a pop %eax
51 push %ecx
51 push %ecx
51 push %ecx
8b00 mov (%eax),%eax
2b02 sub (%edx),%eax
c3 ret
"YZXQQQ\x8b\0+\2\xc3"
64bit
8b06 mov (%rsi), %eax
2b07 sub (%rdi), %eax
c3 ret
"\x8b\6+\7\xc3"
char
- ビット幅を変えれば良いが、負数の扱いに注意。eaxをクリアするのではなく、符号拡張を行う必要がある。
| op | from | dest |
|---|---|---|
| cbw/cbtw | %al | %ax |
| cwde/cwtl | %ax | %eax |
| cwd/cwtd | %ax | %dx:%ax |
| cdq/cltd | %eax | %edx:%eax |
| cdqe/cltq | %eax | %rax |
| cqo/cqto | %rax | %rdx:%rax |
昇順
32bit
59 pop %ecx
58 pop %eax
5a pop %edx
51 push %ecx
51 push %ecx
51 push %ecx
8a00 mov (%eax),%al
2a02 sub (%edx),%al
6698 cbtw
98 cwtl
c3 ret
"YXZQQQ\x8a\0*\2f\x98\x98\xc3"
64bit
8a07 mov (%rdi), %al
2a06 sub (%rsi), %al
6698 cbtw
98 cwtl
c3 ret
"\x8a\7*\6f\x98\x98\xc3"
降順
32bit
59 pop %ecx
5a pop %edx
58 pop %eax
51 push %ecx
51 push %ecx
51 push %ecx
8a00 mov (%eax),%al
2a02 sub (%edx),%al
6698 cbtw
98 cwtl
c3 ret
"YZXQQQ\x8a\0*\2f\x98\x98\xc3"
64bit
8a06 mov (%rsi), %al
2a07 sub (%rdi), %al
6698 cbtw
98 cwtl
c3 ret
"\x8a\6*\7f\x98\x98\xc3"
short
- short配列の後ろ2バイトを読みだして良ければ、66プレフィックスを削除することで2バイト短縮できます。
- http://qiita.com/cielavenir/items/22e47458dc8beaf8341d#comment-5fbb49f38fa91f58483e
昇順
32bit
59 pop %ecx
58 pop %eax
5a pop %edx
51 push %ecx
51 push %ecx
51 push %ecx
668b00 mov (%eax),%ax
662b02 sub (%edx),%ax
98 cwtl
c3 ret
"YXZQQQf\x8b\0f+\2\x98\xc3"
64bit
668b07 mov (%rdi), %ax
662b06 sub (%rsi), %ax
98 cwtl
c3 ret
"f\x8b\7f+\6\x98\xc3"
降順
32bit
59 pop %ecx
5a pop %edx
58 pop %eax
51 push %ecx
51 push %ecx
51 push %ecx
668b00 mov (%eax),%ax
662b02 sub (%edx),%ax
98 cwtl
c3 ret
"YZXQQQf\x8b\0f+\2\x98\xc3"
64bit
668b06 mov (%rsi), %ax
662b07 sub (%rdi), %ax
98 cwtl
c3 ret
"f\x8b\6f+\7\x98\xc3"
long long
- 実用的に使えるのは64bitのみ
- qsortの比較関数の返し値はintであるため、raxをそのまま使うことはできない。
- 符号を取り出すことにした。1を1に、0を-1に変換する。この変換を使いたいため、rsiとrdiが逆になっている。
- \x08は\bで代用。
昇順
int compare(long long*a,long long*b){
//あくまで昇順です
unsigned long long v=*b-*a;
return v?(v>>63<<1)-1:0;
}
488b06 movq (%rsi), %rax
482b07 subq (%rdi), %rax
7408 je 8
48c1e83f shrq $63, %rax
01c0 addl %eax, %eax
ffc8 decl %eax
c3 ret
"H\x8b\6H+\7t\bH\xc1\xe8?\1\xc0\xff\xc8\xc3"
降順
488b07 movq (%rdi), %rax
482b06 subq (%rsi), %rax
7408 je 8
48c1e83f shrq $63, %rax
01c0 addl %eax, %eax
ffc8 decl %eax
c3 ret
"H\x8b\7H+\6t\bH\xc1\xe8?\1\xc0\xff\xc8\xc3"
42バイトという微妙な数字
30バイトにしていただくことができました。ありがとうございます。
//こういうアルゴリズムのようです。
//とりあえずC++として正しいコードにしてみました。
//ポインタめっためたですがもともとそういう話題だしある意味しょうがない。
#include <algorithm>
unsigned char &lo8(unsigned long long &n){
return *(unsigned char*)&n;
}
unsigned int &lo32(unsigned long long &n){
return *(unsigned int*)&n;
}
int compare(long long*a,long long*b){
unsigned long long rax=*a-*b;
if(rax){
unsigned long long rdx=(long long)rax<0 ? -1LL : 0; //cqoの1命令で実行できる
std::swap(lo32(rax),lo32(rdx)); //xchgの1命令で実行できる
lo8(rax)|=32;
}
return lo32(rax);
}
//#include <cstdio>
//int main(){
// long long a=100000000000LL;
// long long b=20000000000000LL;
// printf("%d\n",compare(&a,&b));
//}