[vorbis-dev] OGG header

[Segher Boessenkool]

> Err.  Except I begin to doubt my own words.  The algorithm
> I described above would be
> 
> for(i=0;i<og->header_len;i++)
>   crc_reg=(crc_reg<<8)^crc_lookup[((crc_reg >> 24)&0xff)]^og->header[i];
> 
> whereas in framing.c we find
>   crc_reg=(crc_reg<<8)^crc_lookup[((crc_reg >> 24)&0xff)^og->header[i]];
> 
> (note change in position of left bracket of subscript.)
> 
> That is, if you have a 32-bit shift register shifting in one bit at
> a time into the low order, then the new bits shifted in do not
> affect the addition of the generator "polynomial" until they
> have been shifted through the intervening 24 bits, while the
> Ogg algorithm makes the new data byte affect the XORed generator
> immediately.

Sorry for taking so long to answer this one...

Say your CRC polynomial P(X) has deg N (in our case, N is 32); P(X) is
irreducible over F_2[X], so there is a natural mapping
p : F_2[X] -> F_2[X]/(P(X))
p : q -> coset q

[
        You can view F_2[X] as an infinitely long string of input bits, while
        F_2[X]/(P(X)) is a string of N output bits; and you can view the mapping
        p as the action of the CRC shift register, taking all "cast out" bits
        and mixing them back in.
]

View the original data as a polynomial b(X) in F_2[X], then your algo calculates
p(b(X)), while Ogg's algo calculates p(X^N b(X)).

Your algo always has the last few bytes added in "unchanged", i.e. not
mixed with
the generator poly; if you generate the CRC of a *very* short ( <= N
bits) sequence
like this, the CRC will be equal to the original data; that's why it
isn't done
like that.

On the other hand, some extra shifting (i.e., adding a few (namely, N)
zero bits)
after applying your algo will have it generate exactly the same CRC as
the usual (i.e.,
Ogg's) algo.  Also note that your algo is typically faster on modern
computers ;)

Cheers,

<p>Segher

p.s. Yes I know I'm off-topic :)

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'vorbis-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.