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 20529 invoked from network); 18 Sep 2023 23:02:39 -0000 Received: from minnie.tuhs.org (50.116.15.146) by inbox.vuxu.org with ESMTPUTF8; 18 Sep 2023 23:02:39 -0000 Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 9AF714028E; Tue, 19 Sep 2023 09:02:34 +1000 (AEST) Received: from ewsoutbound.kpnmail.nl (ewsoutbound.kpnmail.nl [195.121.94.170]) by minnie.tuhs.org (Postfix) with ESMTPS id B5C694027A for ; Tue, 19 Sep 2023 09:02:23 +1000 (AEST) X-KPN-MessageId: 69735d3f-5677-11ee-88e9-005056ab378f Received: from smtp.kpnmail.nl (unknown [10.31.155.38]) by ewsoutbound.so.kpn.org (Halon) with ESMTPS id 69735d3f-5677-11ee-88e9-005056ab378f; Tue, 19 Sep 2023 01:02:16 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=planet.nl; s=planet01; h=to:date:message-id:subject:mime-version:content-type:from; bh=LzxZXYa6n0ar1ojikd1mRExApnKBq7o8vvvLYFMtJzI=; b=Sn0s51/AyAFVWxn85ySpGM4ZVlOBx1vrfZDQxc+I/q5HuJmE78t53ueQoWMRoCNChKF/t3BYaFG1a 2Z+IrqAE7fGLXbOIDe+VcAXlfeV7gybgo8EjeRZW8pxKmh6n1PiCH5ItV02gcFZaZ0518l0NDtF1ar ZojubjSRjoBXOETk= X-KPN-MID: 33|lGzYyXXr3Nf4xc847Tbr19V2exrp3+VuVqFljvdvt4tbvZZaEgL+s089SC8b4AM eShwbLfkVTWp/3mqy2DXqlQ04ITHtwDwn9oxQ8h4x7Rw= X-KPN-VerifiedSender: Yes X-CMASSUN: 33|dIG5r0yfGIFqJERofiBq27R8yM0zCIu/GUhx1sX18wS1r2dJYvT8zDzb6Kx0teG 2p3SNUPIu0Gsux77VCl78fQ== X-Originating-IP: 77.172.38.96 Received: from mba1.fritz.box (77-172-38-96.fixed.kpn.net [77.172.38.96]) by smtp.kpnmail.nl (Halon) with ESMTPSA id 6c97cdba-5677-11ee-b96b-005056abf0db; Tue, 19 Sep 2023 01:02:22 +0200 (CEST) From: Paul Ruizendaal Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.7\)) Message-Id: <87246EC9-0AC8-404E-A8DD-508AB046018B@planet.nl> Date: Tue, 19 Sep 2023 01:02:21 +0200 To: "tuhs@tuhs.org" X-Mailer: Apple Mail (2.3445.9.7) Message-ID-Hash: LZLBVIBNDK6EAP3KPJMUUBQJAYWDJ6VL X-Message-ID-Hash: LZLBVIBNDK6EAP3KPJMUUBQJAYWDJ6VL 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 X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] 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: When looking at old xmodem code I noticed that it calculated its CRC = bit-by-bit, switching to byte-wise using a table in the late 80=E2=80=99s.= It never seems to have used the byte-wise, =E2=80=9Con-the-fly=E2=80=9D = algorithm. This seems to match a pattern: I often come across bit-wise = and table implementations, but rarely on-the-fly implementations if any. = The on-the-fly algorithm was known at least since 1983, following a = paper by Perez: = http://www.bitsavers.org/components/fairchild/_appNotes/Byte-wise_CRC_Jun8= 3.pdf The paper was noted, for example it is on the citation list of RFC1134, = describing the PPP protocol. Today, a wikipedia page gives = implementations for various polynomials: = https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks#Para= llel_computation_without_table Now, it would seem to me that on memory constrained personal computers = and PDP-11=E2=80=99s the =E2=80=9Con-the-fly=E2=80=9D algorithm would = have been a good choice, being just a few lines of code and maybe 30-50% = slower than table lookup. The tables aren=E2=80=99t big, but a kilobyte = is a lot when you only have 64. Any suggestions as to why the on-the-fly algorithm did not catch on more = in the 1980=E2=80=99s? Maybe it was simply less well known than I think?