dhesi@bsu-cs.UUCP (Rahul Dhesi) (03/19/89)
I recently posted "brik", a general-purpose CRC-32 program, to
comp.binaries.ibm.pc (includes portable C source) and was amused to
consider the following problem. The command
brik -G * > crc.lst
generates a list of filenames and CRCs in crc.lst, which may be later checked
with
brik -C crc.lst
This always reports a CRC error for "crc.lst" itself, since the CRC
recorded for it was based on its contents before it was closed. What I
would like to do is find a way of having brik generate a CRC list that
includes the corect CRC of the file containing that list. I don't
expect to find a simple solution, but it will be fun seeing people
try.
--
Rahul Dhesi UUCP: <backbones>!{iuvax,pur-ee}!bsu-cs!dhesi
ARPA: dhesi@bsu-cs.bsu.eduleo@philmds.UUCP (Leo de Wit) (03/23/89)
In article <6219@bsu-cs.UUCP> dhesi@bsu-cs.UUCP (Rahul Dhesi) writes: |I recently posted "brik", a general-purpose CRC-32 program, to |comp.binaries.ibm.pc (includes portable C source) and was amused to |consider the following problem. The command | | brik -G * > crc.lst | |generates a list of filenames and CRCs in crc.lst, which may be later checked |with | | brik -C crc.lst | |This always reports a CRC error for "crc.lst" itself, since the CRC |recorded for it was based on its contents before it was closed. What I |would like to do is find a way of having brik generate a CRC list that |includes the corect CRC of the file containing that list. I don't |expect to find a simple solution, but it will be fun seeing people |try. Depending on the exact algorithm you're using, this might / might not be an unsolvable problem. In fact solving it boils down to finding a zero for a integer to integer function; this means that there might even be more than one possible solution (depending on the algorithm). Look at this way: for every possible CRC checksum you put in the file for crc.lst itself (this may be in text format) you calculate the CRC checksum. Clearly this is a function (f) from the domain of possible CRC checksums (you may even take this to be somewhat larger, e.g. the domain of ints) to the domain of possible CRC checksums. Depending on your algorithm and the CRC values for the other files (these determine what f looks like), x = f(x) may have zero, one or more than one solutions. If the domain of possible CRC values is not too big, you could use an exhaustive search to find a correct value, if there is one (this had better been a builtin for your program, e.g. a -o flag to create an output file whose contents must be CRC-ed etc.). This should be easy to implement. Leo.
bagpiper@oxy.edu (Michael Paul Hunter) (03/27/89)
In article <990@philmds.UUCP> leo@philmds.UUCP (Leo de Wit) writes: >In article <6219@bsu-cs.UUCP> dhesi@bsu-cs.UUCP (Rahul Dhesi) writes: >|I recently posted "brik", a general-purpose CRC-32 program, to >|comp.binaries.ibm.pc (includes portable C source) and was amused to >|consider the following problem. The command >| >| brik -G * > crc.lst >| >|generates a list of filenames and CRCs in crc.lst, which may be later checked >|with >| >| brik -C crc.lst >| >|This always reports a CRC error for "crc.lst" itself, since the CRC >|recorded for it was based on its contents before it was closed. What I >|would like to do is find a way of having brik generate a CRC list that >|includes the corect CRC of the file containing that list. I don't >|expect to find a simple solution, but it will be fun seeing people >|try. Quick, obvious fix/hack.... Put it on a different drive and brik it separately to the first drive.... :) m
les@chinet.chi.il.us (Leslie Mikesell) (03/27/89)
In article <6219@bsu-cs.UUCP> dhesi@bsu-cs.UUCP (Rahul Dhesi) writes: >consider the following problem. The command > brik -G * > crc.lst >generates a list of filenames and CRCs in crc.lst, which may be later checked >with > brik -C crc.lst >This always reports a CRC error for "crc.lst" itself, since the CRC >recorded for it was based on its contents before it was closed. What I >would like to do is find a way of having brik generate a CRC list that >includes the corect CRC of the file containing that list. There are actually two problems here: finding the file where the output is directed and making the CRC value correct. Under unix fstat() and stat() should let you check to see which file is your output. If you remember what value you wrote for that file and CRC all of your output you could just keep writing junk at the end of the file until the CRC turned out to be correct. Reminds me of a story I once heard about sales vs. service people: ...the salesmen tell the lies - the customer service people have to make them come true. Les Mikesell
bet@dukeac.UUCP (Bennett Todd) (03/28/89)
[ Asks for suggestions on how to make CRC-computer * >CRC-output contain correct CRC values for all files -- including "CRC-output" ] That's easy, just iterate looking for the fixed point, like so: touch .CRC-output finis=0 while test $finis -eq 0 do CRC-computer * >CRC-output diff CRC-output >/dev/null && finis=1 cp CRC-output .CRC-output done rm .CRC-output But please, not on my machine:-). Seriously, without an in-depth analysis of how CRCs behave (which is way, way beyond my abilities) there is no reason to believe that a fixed point exists; it might fall into a cycle instead (given any finite number of bits in the CRC, it has to do one or the other). Unless some mathematician steps forward and waves her magic wand, I expect the best answer will be to fall back 10 and punt: CRC-computer * | egrep -v CRC-output >CRC-output I really liked the question, though. -Bennett bet@orion.mc.duke.edu