Re: CRC32 Question

NvrBst <nvrbst@xxxxxxxxx> writes:

I just started trying to figure out how CRC32 is generated but can't
seem to get it *been thinking about it for almost 5 hours now*.
Basically I understand CRC from the examples on wikipedia. From wiki
I gathered that I could add or remove 0's from the beginning of the
source string and still get the same CRC. It didn't work with the
CRC32 generators and I found out CRC32 is a little different which I
don't fully understand what makes it different than CRC other than the
polynomial used.

Quite simple: CRC32 inverts its register before and after processing.

A CRC computation is simply taking the remainder after division (with
the minor wrinkle that we're doing arithmetic with binary polynomials
rather than integers). For added fun, we do the computation
incrementally: at each stage, we have a remainder in a register, and we
read a symbol from the input, and we update the register: if the
register initially contains r, we're reducing modulo p, and we introduce
a new radix-B symbol x, then we update the register to contain r B + x
(mod p).

The downside is that if r = x = 0 then this won't change the register:
it's not sensitive to leading zeros. The fix that CRC32 uses is to
invert the register before and afterwards; so rather than starting with
r = 0, we start with r = 0xffffffff, and XOR the final value with
0xffffffff when we're done.

Let's write t for the indeterminate in the polynomials, and assume we're
working with bytes. Then a `symbol' is a polynomial in t with degree at
most 7 and coefficients in F_2 (i.e., either 0 or 1, with arithmetic
performed mod 2). The register r contains a polynomial with degree at
most 31. And B = t^8.

Basically the end result that I'm looking to archive is this. I have
a small byte sequence "hidden" in a larger byte sequence. I know the
CRC32 and size of the small byte sequence and wish to calculate the
CRC32 by removing 1 byte from the beginning and adding 1 byte to the
end, and recalculating; like a catipillar all the way down. The way
CRC works I should be able to add 1 byte to the end and recalculate
very easily, however, if it is possible to remove 1 byte from the
beginning for CRC32 is tripping me up.

This shouldn't be very tricky. If you know the value of the byte (y),
and how many bytes ago (n) it was, you can remove its effect from the
register by subtracting y t^{8n} from the register. (Though addition
and subtraction are the same thing.)

1. Is it possible to remove 1 byte from the beginning(or close to
beginning) of a CRC32 and be able recalculate the CRC, using the CRC
that I just calculated, if I know what the byte I want to remove is?

Yes. See above.

Or even in the case where I know the byte is "0x00" or "0x00000000"?

In this case, if you really want the CRC to be insensitive to leading
zeros, you can just skip the initial inversion.

2. I haven't looked at MD5 or SHA-1, but I also have these for the
small byte sequence I wish to find. Would using these help my cause
worst/better/same as CRC32?

They'd be much, much worse.

-- [mdw]
.

Relevant Pages

  • Re: Shorter checksum than MD5
    ... CRC algorithms were ... within that arithmetic, the CRC of a string is ... def crc(s, salt): ... 'The probability of the changed dada having the same CRC32 is 1/2**32' ...
    (comp.lang.python)
  • Re: CRC and checksum
    ... - Serial hardware CRC: Starting with a zero register, ... register is XORed with the generator. ... the register are then the CRC to be added. ... an imaginary four-bit CRC, whose generator is 10011. ...
    (comp.compression)
  • Re: dealing with hex values in c# vs VB
    ... The resulting CRC must match up against a CRC generated by someone elses ... Public Function AdDDNc32(ByVal Item As String, ByVal Crc32 As Long) As Long ... Dim bCharValue As Byte, iCounter As Integer, lIndex As Long ... Dim lAccValue As Long, lTableValue As Long ...
    (microsoft.public.dotnet.languages.csharp)
  • Calculate CRC in Virtex-Spartan II bitstream
    ... I want calculate the CRC of a standard bitstream ... Write the CMD Register: RCRC ... Write the FDRI Register: DATA ... cycle of 910 time ...
    (comp.arch.fpga)
  • [PATCH 2/6] crc32: replace bitreverse by bitrev32
    ... The only users of bitreverse() are crc32 itself and via-velocity. ... crc1 = crc32_le; ...
    (Linux-Kernel)