Re: [RFC][PATCHES v2] checksum stuff

[Al Viro <viro@zeniv.linux.org.uk>]

On Fri, Dec 08, 2023 at 02:17:12PM +0000, Al Viro wrote:
> On Fri, Dec 08, 2023 at 12:04:24PM +0000, David Laight wrote:
> > I've just read RFC 792 and done some experiments.
> > The kernel ICMP checksum code is just plain broken.
> > 
> > RFC 792 is quite clear that the checksum is the 16-bit ones's
> > complement of the one's complement sum of the ICMP message
> > starting with the ICMP Type.
> > 
> > The one's complement sum of 0xfffe and 0x0001 is zero (not the 0xffff
> 
> It is not.  FYI, N-bit one's complement sum is defined as
> 
> X + Y <= MAX_N_BIT ? X + Y : X + Y - MAX_N_BIT,
> 
> where MAX_N_BIT is 2^N - 1.
> 
> You add them as natural numbers.  If there is no carry and result
> fits into N bits, that's it.  If there is carry, you add it to
> the lower N bits of sum.
> 
> Discussion of properties of that operation is present e.g. in
> RFC1071, titled "Computing the Internet Checksum".
> 
> May I politely suggest that some basic understanding of the
> arithmetics involved might be useful for this discussion?

FWIW, "one's complement" in the name is due to the fact that this
operation is how one normally implements addition of integers in
one's complement representation.

The operation itself is on bit vectors - you take two N-bit vectors,
pad them with 0 on the left, add them as unsigned N+1-bit numbers,
then add the leftmost bit (carry) to the value in the remaining N bits.
Since the sum on the first step is no greater than 2^{N+1} - 2, the
result of the second addition will always fit into N bits.

If bit vectors <A> and <B> represent integers x and y with representable
sum (i.e. if 2^{N-1} > x + y > -2^{N-1}), then applying this operation will
produce a vector representing x + y.  In case when the sum allows
more than one representation (i.e. when x + y is 0), it is biased towards
negative zero - the only way to get positive zero is (+0) + (+0); in
particular, your example is (+1) + (-1) yielding (-0).

Your bit vectors are 1111111111111110 and 0000000000000001; padding gives
01111111111111110 and 00000000000000001; the first addition - 01111111111111111,
so the carry bit is 0 and result is the lower 16 bits, i.e. 1111111111111111.

Had the second argument been 0000000000000011 (+3), you would get
10000000000000001 from adding padded vectors, with carry bit being
1.  So the result would be 1 + 0000000000000001, i.e. 0000000000000010
((+2), from adding (-1) and (+3)).

References to 1's complement integers aside, the operation above is
what is used as basis for checksum calculations.  Reasons and
properties are dealt with in IEN 45 (older than RFC 791/792 - TCP
design is older than IP, and that's where the choice of checksum had
been originally dealt with) and in RFC 1071 (which includes
IEN 45 as appendix, noting that it has not been widely available).