This is an LLVM-based implementation of the n-gram branch coverage proposed in the paper “Be Sensitive and Collaborative: Analzying Impact of Coverage Metrics in Greybox Fuzzing”, by Jinghan Wang, et. al.
Note that the original implementation (available here) is built on top of AFL's QEMU mode. This is essentially a port that uses LLVM vectorized instructions to achieve the same results when compiling source code.
In math the branch coverage is performed as follows: map[current_location ^ prev_location[0] >> 1 ^ prev_location[1] >> 1 ^ ... up to n-1] += 1`
The size of n (i.e., the number of branches to remember) is an option that is specified either in the AFL_LLVM_INSTRUMENT=NGRAM-{value} or the AFL_LLVM_NGRAM_SIZE environment variable. Good values are 2, 4 or 8, valid are 2-16.
It is highly recommended to increase the MAP_SIZE_POW2 definition in config.h to at least 18 and maybe up to 20 for this as otherwise too many map collisions occur.