On 8/22/25 3:47 AM, Nandakumar Edamana wrote:
This commit addresses a challenge explained in an open question ("How
can we incorporate correlation in unknown bits across partial
products?") left by Harishankar et al. in their paper:
https://arxiv.org/abs/2105.05398
When LSB(a) is uncertain, we know for sure that it is either 0 or 1,
from which we could find two possible partial products and take a
union. Experiment shows that applying this technique in long
multiplication improves the precision in a significant number of cases
(at the cost of losing precision in a relatively lower number of
cases).
This commit also removes the value-mask decomposition technique
employed by Harishankar et al., as its direct incorporation did not
result in any improvements for the new algorithm.
Signed-off-by: Nandakumar Edamana <nandakumar@xxxxxxxxxxxxxxxx>
---
include/linux/tnum.h | 3 +
kernel/bpf/tnum.c | 47 ++++++++----
.../selftests/bpf/prog_tests/verifier.c | 2 +
.../selftests/bpf/progs/verifier_mul.c | 74 +++++++++++++++++++
4 files changed, 113 insertions(+), 13 deletions(-)
create mode 100644 tools/testing/selftests/bpf/progs/verifier_mul.c
Nandakumar, please split this patch into 2, one for the core change and then
a second patch for the selftest code, and also keep the previous reviewers in
Cc (e.g. harishankar.vishwanathan@xxxxxxxxx was not copied).
Thanks,
Daniel
