HomeFreeBSD

Fletcher4: Incremental using SIMD

Description

Fletcher4: Incremental using SIMD

Combine incrementally computed fletcher4 checksums. Checksums are combined
a posteriori, allowing for parallel computation on chunks to be implemented if
required. The algorithm is general, and does not add changes in each SIMD
implementation.
New test in ztest verifies incremental fletcher computations.

Checksum combining matrix for two buffers a and b, where Ca and Cb are
respective fletcher4 checksums, Cab is combined checksum, s is size of buffer
b (divided by sizeof(uint32_t)) is:

Cab[A] = Cb[A] + Ca[A]
Cab[B] = Cb[B] + Ca[B] + s * Ca[A]
Cab[C] = Cb[C] + Ca[C] + s * Ca[B] + s(s+1)/2 * Ca[A]
Cab[D] = Cb[D] + Ca[D] + s * Ca[C] + s(s+1)/2 * Ca[B] + s(s+1)(s+2)/6 * Ca[A]

NOTE: this calculation overflows for larger buffers. Thus, internally, the calculation is performed on 8MiB chunks.

Signed-off-by: Gvozden Neskovic <neskovic@gmail.com>

Details

Provenance
Gvozden Neskovic <neskovic@gmail.com>Authored on Sep 23 2016, 1:52 AM
Parents
rGdc03fa309247: Fletcher4: Init in libzfs_init()
Branches
Unknown
Tags
Unknown

Event Timeline

Gvozden Neskovic <neskovic@gmail.com> committed rG37f520db2d19: Fletcher4: Incremental using SIMD (authored by Gvozden Neskovic <neskovic@gmail.com>).Oct 5 2016, 2:41 PM