मैं एक ASCII-string से 32 बिट संख्या बनाना चाहता हूं। सीआरसी 32 एल्गोरिदम ठीक वही है जो मैं ढूंढ रहा हूं लेकिन मैं इसका उपयोग नहीं कर सकता क्योंकि इसकी आवश्यकता वाली तालिका बहुत बड़ी है (यह एक एम्बेडेड सिस्टम के लिए है जहां संसाधन बहुत दुर्लभ हैं)।फास्ट सीआरसी एल्गोरिदम?
तो: एक तेज और पतला सीआरसी एल्गोरिदम के लिए कोई सुझाव? इससे कोई फर्क नहीं पड़ता कि मूल CRC32 के मुकाबले टक्कर थोड़ी अधिक संभावना है।
धन्यवाद!
सीआरसी कार्यान्वयन गति के लिए टेबल का उपयोग करें। वे आवश्यक नहीं हैं।
यहां कास्टगोनोली बहुपद (या इंटेल क्रैक 32 निर्देश द्वारा उपयोग किए जाने वाले समान) या ईथरनेट बहुपद (जैसे ज़िप, gzip, आदि में उपयोग किया जाता है) का उपयोग कर एक छोटा सीआरसी 32 है।
#include <stddef.h>
#include <stdint.h>
/* CRC-32C (iSCSI) polynomial in reversed bit order. */
#define POLY 0x82f63b78
/* CRC-32 (Ethernet, ZIP, etc.) polynomial in reversed bit order. */
/* #define POLY 0xedb88320 */
uint32_t crc32c(uint32_t crc, const unsigned char *buf, size_t len)
{
int k;
crc = ~crc;
while (len--) {
crc ^= *buf++;
for (k = 0; k < 8; k++)
crc = crc & 1 ? (crc >> 1)^POLY : crc >> 1;
}
return ~crc;
}
प्रारंभिक crc मान शून्य होना चाहिए। नियमित रूप से सीआरसी को अद्यतन करने के लिए डेटा के हिस्सों के साथ नियमित रूप से कहा जा सकता है। आप गति के लिए आंतरिक पाश को अनलोल कर सकते हैं, हालांकि आपका कंपाइलर वैसे भी आपके लिए ऐसा कर सकता है।
@ होलीब्लैक कैट: क्यों? सीआरसी की गणना के लिए यह सामान्य मुहावरे है: सीआरसी में अब तक गणना की गई है और अद्यतन सीआरसी मूल्य वापस कर दें। –
यह भी तर्कसंगत रूप से संकलित होता है, तर्क आने के साथ और मूल्य में लौटाया जा रहा है और कभी भी एक ही रजिस्टर को छोड़ नहीं रहा है। –
@MichaelBurr मुझे नहीं पता कि मुझे 3 साल पहले क्यों पुराना कहा गया था। :/ – HolyBlackCat
स्पष्ट रूप से सबसे बड़ी लुकअप तालिका सर्वश्रेष्ठ प्रदर्शन लाएगी, लेकिन आप 16,8 या 4 बिट लुकअप के लिए किसी भी (छोटी) तालिका का उपयोग कर सकते हैं।
तो तालिका आकार CRC32 के लिए कर रहे हैं:
16bit-lookup: 4*2^16=256k
8bit-lookup: 4*2^8=1k
4bit-lookup: 4*2^4=64byte
4bit तालिका में चार बार 16bit तालिका की तुलना में धीमी है।
आपको क्या उपयोग करना चाहिए अपनी गति आवश्यकताओं पर निर्भर करता है।
चूंकि लूका राहने का उल्लेख है कि फ्लैश मेमोरी में टेबल डालना अच्छा विचार है, लेकिन कई प्लेटफ़ॉर्म पर const कीवर्ड का उपयोग करने के लिए पर्याप्त नहीं है।
अधिकतर आपको अपनी लिंकर कमांड फ़ाइल को संशोधित करके, फ्लैश में रखे गए अनुभाग में तालिका को रखने की आवश्यकता होती है।
सीआरसी 32 को 256k लुकअप टेबल संस्करण की तुलना में कोई बड़ी गति जुर्माना के बिना, यदि आप को बिना किसी लुकअप टेबल के साथ लागू किया जा सकता है, या 1k-byte लुकअप टेबल के साथ लागू किया जा सकता है। Http://wiki.osdev.org/CRC32 पर उदाहरण। यदि आपको वास्तव में बाइट्स को सहेजना है, तो adler32 का उपयोग करें। – dascandy
'संसाधनों के साथ आपका क्या मतलब है बहुत दुर्लभ'? 64 एमबी से कम, 8 केबी से कम या 512byte से कम? – jeb
जेब: बहुत दुर्लभ माध्यमों में वर्तमान में मेरे पास http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/libkern/crc32.c में दिखाए गए तालिका को जोड़ने के लिए पर्याप्त स्थान नहीं है। – Elmi