Talk:CRC-32
Task goal
Hi, What do you want the task to be about? --Paddy3118 17:45, 29 November 2011 (UTC)
- The questions that come to my mind...Which polynominal? Is this in pursuit of a particular protocol's check? (i.e. ethernet frame checksums, ZIP file stream checksums, etc). "CRC" isn't any more specific than, say, "draw a shape".--Michael Mol 18:02, 29 November 2011 (UTC)
- I would like a task that calculates the ubiquitous CRC-32 as in RFC 1952 for GZIP. (The RFC contains an algorithm in C code, and refers to section 8.1.1.6.2 "32-bit frame check sequence" from ITU-T Rec. V.42.) However, I am not author of this draft task. --Kernigh 21:13, 29 November 2011 (UTC)
- Given that there are language (and even CPU) accelerators for different common cases of CRC32, I'd say go ahead and create a separate task for each form of interest. Probably use a naming scheme of "CRC32/$name", where $name would be the common name for the CRC32 variant. CRC32/CRC32c, for example. I realize this would lead to a small explosion in tasks which would be mundane and uninteresting after the second or so variation, but that leaves low-hanging fruit for whoever comes along later. --Michael Mol 15:27, 30 November 2011 (UTC)
- Isn't it possible to write a program that calculates an N-bit CRC of a string with polynomial P ? --Spekkio 21:14, 29 November 2011 (UTC)
- I would like a task that calculates the ubiquitous CRC-32 as in RFC 1952 for GZIP. (The RFC contains an algorithm in C code, and refers to section 8.1.1.6.2 "32-bit frame check sequence" from ITU-T Rec. V.42.) However, I am not author of this draft task. --Kernigh 21:13, 29 November 2011 (UTC)
Hmm, ok I see. There are many types of algoritms that can be called a CRC. I think the most common CRC algoritm would be the CRC-32 used by IEEE 802.3, also mentioned by Kernigh. But it would also be interesting to make CRC-8,CRC-16 etc... --Spekkio 07:47, 30 November 2011 (UTC)
- Maybe (I don't know), and perhaps its of theoretical interest, but who wants to use a generic algorithm? CRC is used specifically because it's a fast, low-cost way to generate a reasonable checksum. --Michael Mol 15:27, 30 November 2011 (UTC)
- I'm not really sure what you mean? Why use a different kind of CRC algoritm that is not a standard? I have seen different kinds of CRC algoritms, like in Modbus, though Modbus is old.--Spekkio 16:09, 30 November 2011 (UTC)
- I didn't mean to suggest that you'd want to use a CEC algorithm that wasn't either de facto or de jure standard. --Michael Mol 18:15, 30 November 2011 (UTC)
- Why use a standard CRC algoritm, I think to reduce confusion :) --Spekkio 16:09, 30 November 2011 (UTC)
- Certainly, but there are many meaningful, standard CRC algorithms. I noted above that it might be reasonable to implement several of them as different tasks. --Michael Mol 18:15, 30 November 2011 (UTC)
- Or do you mean why make a function that can calculate N bit CRC for poly P? Maybe it would be interesting to have such a function if an MCU is communicating with several devices that uses different polynomials and different bit length CRC, maybe it could save space, but it would be slower --Spekkio 16:09, 30 November 2011 (UTC)
- A generic function, while theoretically interesting (and
probablycertainly worthwhile as a generic, illustrative case) is not something you'd see in a practical setting. Practical settings tend to call for a great deal of speed, and thus rely on optimized or specially-provided forms. As a consequence, languages like PHP provide a crc32 function, and Intel is even including a CPU instruction for accelerating CRC32 with their Nehalem architecture. These aren't likely to be able to be illustrated with a good generic function, but they're going to be the best way forward for some CRC32s. That's why I noted different tasks above. --Michael Mol 18:15, 30 November 2011 (UTC)- That would have been the basic argument behind the splitting of the MD5 and MD5/Implementation tasks. --Dgamey 13:22, 7 December 2011 (UTC)
- A generic function, while theoretically interesting (and
- I'm not really sure what you mean? Why use a different kind of CRC algoritm that is not a standard? I have seen different kinds of CRC algoritms, like in Modbus, though Modbus is old.--Spekkio 16:09, 30 November 2011 (UTC)
We still don't have an answer to the question "What do we need to do to fulfill this task?". How about stating:
- "Implement the CRC commonly known as ... whose equation is ... . Use it to generate a checksum for the following bytes ..."
--Paddy3118 05:39, 1 December 2011 (UTC)
- All the language examples have to work with the same input leading to greater uniformity of purpose and hopefully comparability in resultant code. As soon as one example gives a checksum, other examples can compare their checksums. --Paddy3118 10:55, 2 December 2011 (UTC)
- Yes I understand, but what is meant was it is not in the task description of MD5 for example, or is it just implied? --Spekkio 13:25, 2 December 2011 (UTC)
- I can't answer that. But it is in the MD5/Implementation which is closer in principle to this task. MD5 frequently just calls libraries that have been validated elsewhere. --Dgamey 13:18, 7 December 2011 (UTC)
- Yes I understand, but what is meant was it is not in the task description of MD5 for example, or is it just implied? --Spekkio 13:25, 2 December 2011 (UTC)
- All the language examples have to work with the same input leading to greater uniformity of purpose and hopefully comparability in resultant code. As soon as one example gives a checksum, other examples can compare their checksums. --Paddy3118 10:55, 2 December 2011 (UTC)
Is using a built-in implementation acceptable? Or a library? –Donal Fellows 15:17, 6 December 2011 (UTC)
- Given some of the above discussion (for example: "A generic function, while theoretically interesting...") I assumed that using a built-in was desirable. --Rdm 15:38, 6 December 2011 (UTC)