[PATCH bpf-next] bpf, docs: Define signed modulo as using truncated division

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



From: Dave Thaler <dthaler@xxxxxxxxxxxxx>

There's different mathematical definitions (truncated, floored,
rounded, etc.) and different languages have chosen different
definitions [0][1].  E.g., languages/libraries that follow Knuth
use a different mathematical definition than C uses.  This
patch specifies which definition BPF uses, as verified by
Eduard [2] and others.

[0]: https://en.wikipedia.org/wiki/Modulo#Variants_of_the_definition
[1]: https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/
[2]: https://lore.kernel.org/bpf/57e6fefadaf3b2995bb259fa8e711c7220ce5290.camel@xxxxxxxxx/

Signed-off-by: Dave Thaler <dthaler@xxxxxxxxxxxxx>
---
 Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/Documentation/bpf/standardization/instruction-set.rst b/Documentation/bpf/standardization/instruction-set.rst
index c5d53a6e8c7..245b6defc29 100644
--- a/Documentation/bpf/standardization/instruction-set.rst
+++ b/Documentation/bpf/standardization/instruction-set.rst
@@ -283,6 +283,14 @@ For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``,
 is first :term:`sign extended<Sign Extend>` from 32 to 64 bits, and then
 interpreted as a 64-bit signed value.
 
+Note that there are varying definitions of the signed modulo operation
+when the dividend or divisor are negative, where implementations often
+vary by language such that Python, Ruby, etc.  differ from C, Go, Java,
+etc. This specification requires that signed modulo use truncated division
+(where -13 % 3 == -1) as implemented in C, Go, etc.:
+
+   a % n = a - n * trunc(a / n)
+
 The ``BPF_MOVSX`` instruction does a move operation with sign extension.
 ``BPF_ALU | BPF_MOVSX`` :term:`sign extends<Sign Extend>` 8-bit and 16-bit operands into 32
 bit operands, and zeroes the remaining upper 32 bits.
-- 
2.33.4





[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux