 |
|
| Computers Forum Index » Computer Architecture - Arithmetic » Deriving partial CRCs from full - is it possible?... |
|
Page 1 of 1 |
|
| Author |
Message |
| rwf_20... |
 Posted: Tue Feb 17, 2009 5:08 pm |
|
|
|
Guest
|
I have the CRC of a large dataset, which is arranged as follows:
- Header (512 bytes)
- Payload (~300 MB)
I have the CRC-32 value of the full dataset, and I have the CRC-32 of
the Header.
Is there any way I can derive the CRC-32 value of the Payload from the
information I have? That is, without actually reading the Payload and
computing it? From what I know of CRC, I can't see how, but I thought
I'd pose the question in case I'm missing something.
Thanks,
Ryan |
|
|
| Back to top |
|
|
|
| ... |
| Posted: Tue Feb 17, 2009 5:38 pm |
|
|
|
Guest
|
In article <0db151fd-58be-4cbe-af00-53ff7788c42f at (no spam) f33g2000vbf.googlegroups.com>,
rwf_20 <rfrenz at (no spam) gmail.com> wrote:
Quote: I have the CRC of a large dataset, which is arranged as follows:
- Header (512 bytes)
- Payload (~300 MB)
I have the CRC-32 value of the full dataset, and I have the CRC-32 of
the Header.
Is there any way I can derive the CRC-32 value of the Payload from the
information I have? That is, without actually reading the Payload and
computing it? From what I know of CRC, I can't see how, but I thought
I'd pose the question in case I'm missing something.
Yes, you are, but this is probably the wrong group. It's a pure
mathematics question, though you might call it theoretical computer
science.
I should need to restudy the problem to remind myself how, so can't
tell you the details offhand. The technique is roughly to turn the
operation into a ring, with it as multiplication and exclusive or as
addition. You then work out what the header CRC would be after the
number of passes defined by the payload (O(log(N)) operations) and
exclusive or it out.
I may be misremembering, but don't think so.
Regards,
Nick Maclaren. |
|
|
| Back to top |
|
|
|
| Terje Mathisen... |
| Posted: Wed Feb 18, 2009 2:52 am |
|
|
|
Guest
|
nmm1 at (no spam) cam.ac.uk wrote:
Quote: In article <0db151fd-58be-4cbe-af00-53ff7788c42f at (no spam) f33g2000vbf.googlegroups.com>,
rwf_20 <rfrenz at (no spam) gmail.com> wrote:
I have the CRC of a large dataset, which is arranged as follows:
- Header (512 bytes)
- Payload (~300 MB)
[snip]
I should need to restudy the problem to remind myself how, so can't
tell you the details offhand. The technique is roughly to turn the
operation into a ring, with it as multiplication and exclusive or as
addition. You then work out what the header CRC would be after the
number of passes defined by the payload (O(log(N)) operations) and
exclusive or it out.
I may be misremembering, but don't think so.
I think you're right, it should be possible to run a CRC in reverse.
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching" |
|
|
| Back to top |
|
|
|
| Glen Herrmannsfeldt... |
| Posted: Wed Feb 18, 2009 3:24 am |
|
|
|
Guest
|
nmm1 at (no spam) cam.ac.uk wrote:
(snip)
Quote: Is there any way I can derive the CRC-32 value of the Payload from the
information I have? That is, without actually reading the Payload and
computing it? From what I know of CRC, I can't see how, but I thought
I'd pose the question in case I'm missing something.
Yes, you are, but this is probably the wrong group. It's a pure
mathematics question, though you might call it theoretical computer
science.
The problem might not be as theoretical as you say.
The easy case comes up in IP/NAT routers, since IP uses a checksum
instead of CRC. It is easy to figure out the new checksum from
the values of the bytes changed.
Consider a layer 3 ethernet/IP switch which needs to change the
value of an address of TTL value inside an ethernet frame.
It would be nice to be able to do that without completely
recomputing the CRC.
(as for c.a.arithmetic, some processors do have a CRC instruction.)
Quote: I should need to restudy the problem to remind myself how, so can't
tell you the details offhand. The technique is roughly to turn the
operation into a ring, with it as multiplication and exclusive or as
addition. You then work out what the header CRC would be after the
number of passes defined by the payload (O(log(N)) operations) and
exclusive or it out.
I may be misremembering, but don't think so.
-- glen |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Tue Dec 08, 2009 12:32 pm
|
|