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 21544 invoked from network); 19 Sep 2023 14:10:46 -0000 Received: from minnie.tuhs.org (2600:3c01:e000:146::1) by inbox.vuxu.org with ESMTPUTF8; 19 Sep 2023 14:10:46 -0000 Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 7135D408F2; Wed, 20 Sep 2023 00:10:41 +1000 (AEST) Received: from ewsoutbound.kpnmail.nl (unknown [195.121.94.168]) by minnie.tuhs.org (Postfix) with ESMTPS id 0931E4027B for ; Wed, 20 Sep 2023 00:10:26 +1000 (AEST) X-KPN-MessageId: 40aebe35-56f6-11ee-af88-005056aba152 Received: from smtp.kpnmail.nl (unknown [10.31.155.40]) by ewsoutbound.so.kpn.org (Halon) with ESMTPS id 40aebe35-56f6-11ee-af88-005056aba152; Tue, 19 Sep 2023 16:10:14 +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=obPB2+ELR40YkCU1dWWeDU9e2Yi+VCpU1+/iPoD+9KQ=; b=fuMc3f2OjwI3sbq1n0bWTBaqEJm1Ns9xLYaEdRMtZpQZXo4rVeX34ee6mLjO/gyfe5jxTgADCO8ng eBM6jgmnffUP9lSfepsocgYOnaTV1+rBzogwjOzOln6DSsnXtgT7VR8XOGAbRgkogsj6ubjdqAAQhW wIfSaVItlVjNyR+s= X-KPN-MID: 33|X5pjykWkAZ1E/dR7IWGjHcn75AsHwFugr1l9GllEqT0mEx3IfNLPL4UOGJ1jQNy bTUSY7+M5JRrNTgsLIGIzjOlSh3MYf3OcwEGAL0/rYio= X-KPN-VerifiedSender: Yes X-CMASSUN: 33|LwgPx/rgjnS6UfcXsVDZJFP0dFrBpJSvJJrXEsv8d/Lbd+1ueZ92uBoC0HaFvYU Pfyr4vwwsWC3j2hTNTG26Iw== 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 40a45ddb-56f6-11ee-9f03-005056ab7584; Tue, 19 Sep 2023 16:10:14 +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 14.0 \(3654.120.0.1.13\)) Message-Id: <3735B8B0-427E-42C6-8343-50B5EE964952@planet.nl> Date: Tue, 19 Sep 2023 16:10:13 +0200 To: "tuhs@tuhs.org" X-Mailer: Apple Mail (2.3654.120.0.1.13) Message-ID-Hash: I2MZSZHZO6ARHYZ23XGZA2FNKQ3J3RWG X-Message-ID-Hash: I2MZSZHZO6ARHYZ23XGZA2FNKQ3J3RWG 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: >> 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? >=20 > Could it have been the per-cpu-second billing that was (fairly?) = common at the time. I was only getting in to Unix in the early 90s but = saw the tail end of that. Good point, but wasn=E2=80=99t per-cpu-second billing mostly used for = big iron? For machines without memory constraint the table method makes = the most sense, also if billing was not a factor. >> 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? >=20 > The CRC algorithm I'm familiar with shows up in Dragon Quest for the = Famicom in 1986[1], written in 6502 assembly. Admittedly though I only = recognized it due to the EOR with 0x1021 on lines 318-323. That I then = only know from a quick and dirty CRC I threw in an XMODEM-CRC client [2] = I did to accommodate for a bug in the JH7100 RISC-V board's recovery ROM = implementation. Not sure if this is along the lines of the approach = you're talking about ... >=20 > [1] - = https://gitlab.com/segaloco/dq1disasm/-/blob/master/src/chr3/start_pw.s > [2] - https://gitlab.com/segaloco/riscv-bits/-/blob/master/util/sxj.c Both of these are what I call the bit-wise method: a loop iterating over = bytes, with an inner loop iterating over bits. An example of the table = method is here: https://github.com/u-boot/u-boot/blob/master/lib/crc16-ccitt.c and an example of the on-the-fly method is here: https://github.com/tio/tio/blob/master/src/xymodem.c#L44-L54 Note how the latter also only has one loop iterating over the bytes, but = effectively calculates the table entry =E2=80=98on the fly=E2=80=99 for = each byte. That is only a handful of instructions more than doing the = table lookup. Maybe it is a =E2=80=9Cstuck in the middle=E2=80=9D = solution that was quickly forgotten.