,                ,  
       ||          _    ||  
 _-_, =||= ,._-_  < \, =||= 
||_.   ||   ||    /-||  ||  
 ~ ||  ||   ||   (( ||  ||  
,-_-   \\,  \\,   \/\\  \\,

ASM AVX ChaCha20

git repository

Uses C and Intel ASM

A while ago I wanted to learn more about the specifics of how encryption. While I was doing research, I discovered the chacha20 algorithm and saw that it didn't look terribly difficult to implement. Initially I made a simple C version and it had decent speed but I wanted to make it faster. The obvious way to fill a NIC would be to multithread it but that's a given and even with single threaded hyper-optimizations it would probably be done anyway. Instead, I wanted to make it faster on a single core, so I used SIMD. Specifically, I used the AVX instruction set.

The first AVX version I made was in C with the `immintrin.h` library. It only replaced adding the key and state at the end of the rounds and xoring the stream. This gave decent improvements:

205858816init/s
64B blocks	278.302002MB/s
...
65536B blocks	285.795624MB/s

vs

205843968init/s
64B blocks	434.201508MB/s
...
65536B blocks	458.366730MB/s

The reason I only did such a small amount originally is because I was trying to make sure it would still run on my desktop which doesn't have any of the spicy AVX instructions. The specific instruction/function was `_mm_rol_epi32` which uses the `vprold` instruction, which requires the AVX512F and AVX512VL cpu flags. And since I don't run a modern enterprise-grade server, I do not have those flags. I realised I could work around this though; the instruction is a rol which means it's a shift that takes the left over bits and puts them back on the other end. To mimic this I just used a shift left and shift right with inverse shift amounts ored to each other.

regb = _mm_or_si128(
	_mm_slli_epi32(
		regb,
		12
	),
	_mm_srli_epi32(
		regb,
		32 - 12
	)
);

This was faster but not by much because of the introduced inefficencies of hacking a roll instruction:

205837536init/s
64B blocks	468.137390MB/s
...
65536B blocks	532.582458MB/s

Also, on some hardware, this version was actually slower because of how much heavier these instructions are. Another seemingly hardware related quirk is that sometimes O3 on GCC would be slower than O1, specifically on my personal computer and my laptop. The final C version, with the proper roll instruction, was easy because I just replaced the hack.

regb = _mm_rol_epi32(
	regb,
	12
);

This was a small change, but it yielded quite a decent improvement:

205833856init/s
64B blocks	620.353394MB/s
...
65536B blocks	746.811279MB/s

But that wasn't enough. I was still being held back! By the C compiler!!!

The next step in optimizations (when hindered by your C compiler) is to hand-roll some ultra high quality ASM. The first major improvement was with the init function which essentially just copies a bit of data to a context:

mov    rcx, 0x6b20657479622d32
mov    QWORD PTR [rdi + 8], rcx

vmovdqu xmm0, XMMWORD PTR [rsi]
vmovdqu XMMWORD PTR [rdi + 16], xmm0

308768864init/s

The difference between this code and GCC's version is mainly that I used the XMM registers (and 64 bit for consts) to copy the data in fewer instructions. It was highly effective at about 50% faster. Then I rewrote the actual encryption function. I'm not compiletely sure what the differences between my ASM and GCC's are (the GCC ASM is incomprehensible), but it doesn't seem too much is different anyways because the speed difference is only anout 1.4%, which I mean yeah at least I did something, but still, it's not a large improvement, especially considering the amount of time required to get to that point.

Moral of the story: I'm better than GCC, but it's still (usually) not worth the time.