qsortの比較関数

よく忘れるのでメモとして。ちなみにlong long版は今書きました…

## 前提

qsort関数には比較関数のポインタを渡す必要がありますが、このポインタ部分には機械語を埋め込むことが可能です。
コードゴルフには必要不可欠となります。
この前提を書くのを忘れていました、すみません(170323)

元祖は[shinh氏の資料](http://shinh.skr.jp/dat_dir/golf_prosym.pdf)です(おそらく).

## int

- 基本形。
- (例として昇順64bit UTF-8環境の場合)`\u05cb\7+\6Ð`を使うと2文字*2バイト削減になります(05cbなる文字 &#x05cb; は割り当てがないので気合で入れるしかありませんが)。
    - 解説：http://qiita.com/akinomyoga/items/abffbc6ea1657d01014b#qsort-cmp-asc32-x64-utf8 http://qiita.com/akinomyoga/items/abffbc6ea1657d01014b#comment-2eb8e2cf8eea3f19ff96

### 昇順

#### 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をクリアするのではなく、符号拡張を行う必要がある。

https://sourceware.org/binutils/docs/as/i386_002dMnemonics.html

|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"
```

<del>42バイトという微妙な数字</del>
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));
//}
```

http://qiita.com/cielavenir/items/22e47458dc8beaf8341d#comment-e83e5ea2231500d97c5b