From owner-freebsd-net Thu Nov 16 6:47:58 2000 Delivered-To: freebsd-net@freebsd.org Received: from whizzo.transsys.com (whizzo.TransSys.COM [144.202.42.10]) by hub.freebsd.org (Postfix) with ESMTP id 79FB137B4C5; Thu, 16 Nov 2000 06:47:54 -0800 (PST) Received: from whizzo.transsys.com (localhost.transsys.com [127.0.0.1]) by whizzo.transsys.com (8.11.0/8.11.0) with ESMTP id eAGElrG98811; Thu, 16 Nov 2000 09:47:53 -0500 (EST) (envelope-from louie@whizzo.transsys.com) Message-Id: <200011161447.eAGElrG98811@whizzo.transsys.com> X-Mailer: exmh version 2.1.1 10/15/1999 X-Exmh-Isig-CompType: repl X-Exmh-Isig-Folder: inbox/freebsd To: Ruslan Ermilov Cc: Charles Mott , Archie Cobbs , net@FreeBSD.ORG, Ari Suutari , jdp@FreeBSD.ORG X-Image-URL: http://www.transsys.com/louie/images/louie-mail.jpg From: "Louis A. Mamakos" Subject: Re: libalias: Incremental Update of Internet Checksum References: <200011150315.eAF3FIG60231@whizzo.transsys.com> <20001115100407.D36400@sunbay.com> <200011151436.eAFEaHG65417@whizzo.transsys.com> <20001115172435.A9724@sunbay.com> <200011151548.eAFFmJG66031@whizzo.transsys.com> <20001115180842.A11913@sunbay.com> <200011152043.eAFKhMG68318@whizzo.transsys.com> <20001116110029.A38288@sunbay.com> In-reply-to: Your message of "Thu, 16 Nov 2000 11:00:29 +0200." <20001116110029.A38288@sunbay.com> Mime-Version: 1.0 Content-Type: text/plain Date: Thu, 16 Nov 2000 09:47:53 -0500 Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.org > Read this carefully, word by word: > > RFC768> If the computed checksum is zero, it is transmitted as all ones > RFC768> (the equivalent in one's complement arithmetic). An all zero > RFC768> transmitted checksum value means that the transmitter generated > RFC768> no checksum. > > "If the computed checksum is zero" above means that CHECKSUM can be 0x0000, > i.e. the one's complement SUM could have a value of 0xFFFF. And if this > is the case, the CHECKSUM IS TRANSMITTED as all ones. > > This also means that the one's complement SUM (for IP purposes) can not > have a value of 0x0000, because if there was such a case, then computed > checksum value would be all ones by itself, and the UDP receiver would > not be able to distinguish this "normal" case from the "no checksum" > case above. > > So, to make a conclusion: > > 1. The ONE'S COMPLEMENT SUM CAN NEVER HAVE A VALUE OF ALL ZEROES, unless > all words are zeroes, which is not the case for IP family protocols, > because at least Protocol field is guaranteed to be non-zero, and is > participating in all known checksums (e.g. IP, UDP, TCP, ICMP). > Hereby, the CHECKSUM value, which is the one's complement of the sum, > CAN NEVER HAVE A VALUE OF ALL ONES. I disagree. You are arguing that the only possible implementation that YOU can think of, which is a particular imperfect emulation of 1's complement arithemtic operations on 2's complement hardware will never produce a zero result after summing a bunch of values. I am arguing that if you have a physical implementation of a 1's complement ALU in your CPU (because you machine architecture is 1's complement) that you will never produce an all 1's result from a simple arithmetic ADD operation on quantities of data. On the particular CPU hardware architecure I have written an IP stack from scratch on, I know this to be ABSOLUTELY TRUE. It has been the case for UNIVAC/Sperry/Unisys 1100/2200 series architectures for more than 30 years. And if you think about it a while, it's important that one's compelement architecture systems produce normalized results (e.g., no negative zero results) so that bitwise tests against +0 are only necessary in code, rather than having to test for both possible result values. The statement you quoted above describes a particular circumstance which may happen as a result of a particular implementation approach, not the only result that could ever possibly appear. For instance, even given a 1's complement CPU ALU, if the arithmetic sum operation is done on e.g., 16 bit quantities on a machine with a native word size of e.g., 36 bits, then the low-order 16 bit sum might appear to be 0xffff, but that's because of the word-size mismatch. (A clever implementation would OR a mask of all 1 bits in the high-order part of the word to automatically "fix" this situation). > 2. UDP uses all zero value in the checksum field to indicate that no > checksum have been computed. For this to work, it does the following > substituion. If the computed checksum is all zeroes (the could happen > only if the one's complement sum is all ones), it is transmitted as > all ones. I would mostly agree. I think the other problem I have is that you're embedding particular architectural assumptions in what is likely machine-architecture independent code. There's a reash in_chksum() is in the machine specific part of the kernel source tree, and performance optimization is only part of it. In the mid 80's, I was on a project which mostly ported the BSD IP stack to the UNIVAC 1100 series machines (1100/90 at the time) when a C compiler appeared. Remarkably, the BSD network stack moved over pretty easily because the architecture specific assumptions were mostly hidden away. There was one particular problem, in fact in netinet/udp_usrreq.c where the UDP checksum field was set to -1 rather than ~0 that I had Mike Karels fix (go look at the ancient SCCS logs..) We never fielded the BSD-based code in production because the machine went away. While it's very unlikely that that 1's complement CPU architectures will become wildly popular again, it's not impossible that the Pentium-13 or some other CPU might add 1's complement ALU capability or acceleration to speed up Internet checksum computation operations. If that's the case, we'll be happy if we've isolated botht he code and the assumptions on how one of two "equivilent" results are computed in well defined places. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message