From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 26298 invoked from network); 19 Sep 2023 16:01:07 -0000 Received: from minnie.tuhs.org (2600:3c01:e000:146::1) by inbox.vuxu.org with ESMTPUTF8; 19 Sep 2023 16:01:07 -0000 Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 6BF2240967; Wed, 20 Sep 2023 02:01:02 +1000 (AEST) Received: from ewsoutbound.kpnmail.nl (ewsoutbound.kpnmail.nl [195.121.94.168]) by minnie.tuhs.org (Postfix) with ESMTPS id 78E2640966 for ; Wed, 20 Sep 2023 02:00:48 +1000 (AEST) X-KPN-MessageId: aecb787c-5705-11ee-af88-005056aba152 Received: from smtp.kpnmail.nl (unknown [10.31.155.40]) by ewsoutbound.so.kpn.org (Halon) with ESMTPS id aecb787c-5705-11ee-af88-005056aba152; Tue, 19 Sep 2023 18:00:41 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=planet.nl; s=planet01; h=to:message-id:date:from:subject:mime-version:content-type; bh=7xM2efyroB0ZUy+zYYGUK7G1/f40UQvnrIlpo3Uurwo=; b=Z6V924YWDrTd0+6jVG1h3bkEDVef8R90y6HnAY8N2aGPGo6os5h5jvAiDyrwlD2v82Go0NQhuE+vf nu/S2/sAxUZxlFM+UyPyNjb6d9sLVpZTZM/vaAgBjXRXGBTTjYxSlEdXFvI4nipY+aYM45OmkgFrz7 E59cOHog3q20dr/g= X-KPN-MID: 33|Kg2GIRq8MBfwM8h2FBrD+l+79PUKuhe1Ajadjmp3tEyAolX2Q945SpznaqAGebT sh77/2CYMB7XgGKcm+pfipQ== X-KPN-VerifiedSender: Yes X-CMASSUN: 33|OlfndRzuF7oFFpvL0kF52xf/uyGrl0b/9MRAw4pln56o8GUNQYO09R3+ult75zx unVfVQDf6M17Uy0m/y5kLHA== X-Originating-IP: 77.172.38.96 Received: from smtpclient.apple (77-172-38-96.fixed.kpn.net [77.172.38.96]) by smtp.kpnmail.nl (Halon) with ESMTPSA id ae8ad173-5705-11ee-9f03-005056ab7584; Tue, 19 Sep 2023 18:00:41 +0200 (CEST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) From: Paul Ruizendaal In-Reply-To: <20230919114229.55D3418C084@mercury.lcs.mit.edu> Date: Tue, 19 Sep 2023 18:00:40 +0200 Content-Transfer-Encoding: quoted-printable Message-Id: <789D4FAC-B6FD-4019-AF7B-C3EAA02E49FC@planet.nl> References: <20230919114229.55D3418C084@mercury.lcs.mit.edu> To: Noel Chiappa X-Mailer: Apple Mail (2.3654.120.0.1.13) Message-ID-Hash: DHBRJWW2EKJNBCIEKMKLUACFSSUPMMQV X-Message-ID-Hash: DHBRJWW2EKJNBCIEKMKLUACFSSUPMMQV X-MailFrom: pnr@planet.nl X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: "tuhs@tuhs.org" X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] Re: CRC calculation in the 1980s List-Id: The Unix Heritage Society mailing list Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: > On 19 Sep 2023, at 13:42, Noel Chiappa = wrote: >=20 >> From: Paul Ruizendaal >=20 >> Any suggestions as to why the on-the-fly algorithm did not catch on >> more in the 1980's? Maybe it was simply less well known than I think? >=20 > I can't answer that directly, but I will point you at IEN-56, "CRC = Checksum > Calculation", by Dave Reed (11-Sep-78): >=20 > https://www.rfc-editor.org/ien/ien56.pdf >=20 > Dave wanted the INWG to use a more powerful (in terms of detecting = errors) > CRC, instead of the simple summation eventually adopted, in TCP and = IP. So he > produced code to implement a particular CRC, to show people that it = would not > be particularly expensive (whether in time, or space, I don't alas = recall > definitively; speed would have been an important consideration, when > competing with the summation, though). >=20 > This would have been close to the leading edge of our knowledge at the = time; > Dave liked playing around with math, and at about that time he did a = very > fast DES implementation. >=20 > Noel That is a very interesting paper and it uses the same polynomial. The = algorithm seems different from the one that Perez published in 1983, but = in the same general direction. So it would seem that this = =E2=80=9Con-the-fly=E2=80=9D method was not (well) known prior to 1983. = By the looks of it, it was not well known afterwards either. You were part of the group that invented it and I=E2=80=99m telling you = stuff you know better than I do, but the adopted summation in TCP/IP had = a lot of advantages: it could be efficiently calculated on 36, 32 and 16 = bit machines, it did not care about endianness and was efficient on both = two=E2=80=99s and one=E2=80=99s complement machines. I don=E2=80=99t = think CRC had all those properties. I don=E2=80=99t think in 1978 the IEN group was aiming for the LAN use = case, but as it turned out a few years later the simple summation = consumed 25% of a VAX-750 CPU to saturate 3 Mbps ethernet. Even a 30% = slowdown in checksumming would have been costly -- but you already = pointed out that speed was an important consideration.