-.s

2021-08-13

Minulla on kotihakemistossani 484-tavuinen, 27-rivinen tiedosto nimeltään "-.s", viiva piste äs. Sen sisältö on seuraava:

	.file	""
	.text
	.globl	main
	.type	main, @function
main:
	pushq	%rbp
	movq	%rsp, %rbp
	movl	$4096, -4(%rbp)
	movl	-4(%rbp), %ecx
	movl	%ecx, %edx
	movl	$3435973837, %eax
	imulq	%rdx, %rax
	shrq	$32, %rax
	movl	%eax, %edx
	shrl	$3, %edx
	movl	%edx, %eax
	sall	$2, %eax
	addl	%edx, %eax
	addl	%eax, %eax
	subl	%eax, %ecx
	movl	%ecx, %edx
	movl	%edx, %eax
	popq	%rbp
	ret
	.size	main, .-main
	.ident	"GCC: (GNU) 9.2.1 20190827 (Red Hat 9.2.1-1)"
	.section	.note.GNU-stack,"",@progbits

Se on x86_64 -assemblyä, GCC-kääntäjän luomaa. (GCC:hän ei käännä suoraan konekieleksi, vaan ensiksi kääntää assemblyksi ja antaa GAS-assemblerin kääntää konekieleksi.) Greppasin bash-historyäni ja löysin viimeisimmän rivin, joka loi -.s-nimisen tiedoston:

gcc -S -x c -fno-asynchronous-unwind-tables -o a.out - <<<"int main() { unsigned int x = 4096; return x % 10; }" && cat -- -.s && wc -l -- -.s

Mitä tämä koodi siis tekee on, on että se laskee jako­jäännöksen, kun 4096 jaetaan kymmenellä; vastaus on 6, mutta käskin kään­täjää olemaan opti­moi­matta laskua pel­käksi kuto­seksi. Kohtasin tämän, kun halusin nähdä, miltä x86_64:n kokonais­luku­jako­lasku näyttää, ja yllätyin, kun käännös ei sisältänyt yhtään jakolasku­käskyä. Sen sijaan että koodi laskisi 4096 modulo 10, niin se laskeekin 4096 kertaa 3435973837 (yhdennellätoista rivillä, imulq %rdx, %rax), sitten tekee bittimagiaa.

Tuon taikaluvun 3435973837 taika piilee siinä, että 3435973837 on heksadesimaalina 0xCCCCCCCD. Se on myös noin neljä viidesosaa 2³²:sta, jonka tarkka arvo on 3435973836,8. (Kymmenellä jakaminenhan on sama asia kuin viidellä jakaminen ja sitten kahdella jakaminen.) Perusidea tässä on, että n/10 on lähes sama luku kuin (n × 3435973837)÷2³⁵, ja koska 3435973837 on niin lähellä 3435973836,8:aa, niin kaikki virheet ovat vain pienien bittien joukossa, jotka shiftataan pois. Kertolaskut sekä kahden potenssilla jakamiset ovat paljon nopeampia käskyjä kuin jakolaskut, joten jos kääntämisen aikana voidaan päätellä, että nimittäjä ei muutu, niin jakolasku korvataan kertolaskulla.

Lisätietoa tästä tempusta on tässä StackOverflow-kysymyksessä, "Why does GCC use multiplication by a strange number in implementing integer division?", sekä artikkelissa johon siellä linkataan, Labor of Divison (Episode I).