From: liqiang <liqiang64@xxxxxxxxxx> Dear all, Thank you for taking the precious time to read this email! Let me introduce the implementation ideas of my code here. In the process of using the compression library libz, I found that the adler32 checksum always occupies a higher hot spot, so I paid attention to this algorithm. After getting in touch with the SVE instruction set of armv8, I realized that SVE can effectively accelerate adler32, so I made some attempts and got correct and better performance results. I very much hope that this modification can be applied to the kernel. Below is my analysis process: Adler32 algorithm ================= Reference: https://en.wikipedia.org/wiki/Adler-32 Assume that the buf of the Adler32 checksum to be calculated is D and the length is n: A = 1 + D1 + D2 + ... + Dn (mod 65521) B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521) = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521) Adler-32(D) = B × 65536 + A In C, an inefficient but straightforward implementation is: const uint32_t MOD_ADLER = 65521; uint32_t adler32(unsigned char *data, size_t len) { uint32_t a = 1, b = 0; size_t index; // Process each byte of the data in order for (index = 0; index < len; ++index) { a = (a + data[index]) % MOD_ADLER; b = (b + a) % MOD_ADLER; } return (b << 16) | a; } SVE vector method ================= Step 1. Determine the block size: Use addvl instruction to get SVE bit width. Assuming the SVE bit width is x here. Step 2. Start to calculate the first block: The calculation formula is: A1 = 1 + D1 + D2 + ... + Dx (mod 65521) B1 = x*D1 + (x-1)*D2 + ... + Dx + x (mod 65521) Step 3. Calculate the follow block: The calculation formula of A2 is very simple, just add up: A2 = A1 + Dx+1 + Dx+2 + ... + D2x (mod 65521) The calculation formula of B2 is more complicated, because the result is related to the length of buf. When calculating the B1 block, it is actually assumed that the length is the block length x. Now when calculating B2, the length is expanded to 2x, so B2 becomes: B2 = 2x*D1 + (2x-1)*D2 + ... + (x+1)*Dx + x*D(x+1) + ... + D2x + 2x = x*D1 + x*D1 + x*D2 + (x-1)*D2 + ... + x*Dx + Dx + x*1 + x + [x*D(x+1) + (x-1)*D(x+2) + ... + D2x] ^^^^ ~~~~ ^^^^ ~~~~~~~~ ^^^^ ~~ ^^^ ~ +++++++++++++++++++++++++++++++++++++ Through the above polynomial transformation: Symbol "^" represents the <x * A1>; Symbol "~" represents the <B1>; Symbol "+" represents the next block. So we can get the method of calculating the next block from the previous block(Assume that the first byte number of the new block starts from 1): An+1 = An + D1 + D2 + ... + Dx (mod 65521) Bn+1 = Bn + x*An + x*D1 + (x-1)*D2 + ... + Dx (mod 65521) Step 4. Implement and test with SVE instruction set: Implement the above ideas with the SVE instruction set (Please refer to the patch for details), and conduct correctness and performance tests. The following are three sets of test data, the test objects are random data of 1M, 10M, 100M: [root@xxx adler32]# ./benchmark 1000000 Libz alg: Time used: 615 us, 1626.0 Mb/s. SVE alg: Time used: 163 us, 6135.0 Mb/s. Libz result: 0x7a6a200 Sve result: 0x7a6a200 Equal [root@xxx adler32]# ./benchmark 10000000 Libz alg: Time used: 6486 us, 1541.8 Mb/s. SVE alg: Time used: 2077 us, 4814.6 Mb/s. Libz result: 0xf92a8b92 Sve result: 0xf92a8b92 Equal [root@xxx adler32]# ./benchmark 100000000 Libz alg: Time used: 64352 us, 1554.0 Mb/s. SVE alg: Time used: 20697 us, 4831.6 Mb/s. Libz result: 0x295bf401 Sve result: 0x295bf401 Equal Test environment: Taishan 1951. The test results show that on Taishan 1951, the speed of SVE is generally about 3 to 4 times that of the C algorithm. liqiang (1): Accelerate Adler32 using arm64 SVE instructions. arch/arm64/crypto/Kconfig | 5 ++ arch/arm64/crypto/Makefile | 3 + arch/arm64/crypto/adler32-sve-glue.c | 93 ++++++++++++++++++++ arch/arm64/crypto/adler32-sve.S | 127 +++++++++++++++++++++++++++ crypto/testmgr.c | 8 +- crypto/testmgr.h | 13 +++ 6 files changed, 248 insertions(+), 1 deletion(-) create mode 100644 arch/arm64/crypto/adler32-sve-glue.c create mode 100644 arch/arm64/crypto/adler32-sve.S -- 2.19.1
