Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!unmvax!pprg.unm.edu!hc!lll-winken!uunet!mcvax!hp4nl!philmds!leo
From: leo@philmds.UUCP (Leo de Wit)
Newsgroups: comp.lang.c
Subject: Re: A self-referential challenge
Message-ID: <990@philmds.UUCP>
Date: 23 Mar 89 09:35:07 GMT
References: <6219@bsu-cs.UUCP>
Reply-To: leo@philmds.UUCP (Leo de Wit)
Organization: Philips I&E DTS Eindhoven
Lines: 40

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.