संकलन-समय में CRC32 लाइनों की गणना

अपनी प्रोग्रामिंग प्रकृति से, मैं वास्तव में कोड में गैर-इष्टतमता और अतिरेक को नापसंद करता हूं। और इसलिए, एक बार फिर से काम पर हमारी परियोजना के स्रोत कोड को पढ़ते हुए, मैं फिर से एक उत्पाद को विभिन्न भाषाओं में अनुवाद करने के तरीके में आया।

यहां स्थानीयकरण काफी सरल है। अनुवाद की आवश्यकता वाली सभी पंक्तियों को _TR() मैक्रो में लपेटा गया है:

 wprintf(L"%s\n", _TR("Some translating string")); 

मैक्रो उपयोग की गई वर्तमान भाषा के आधार पर पाठ का वांछित संस्करण देता है। इसे निम्नानुसार परिभाषित किया गया है:

 #define _TR(x) g_Translator.Translate(x) 

यहां, वैश्विक ऑब्जेक्ट g_Translator कॉल किया जाता है, जो Translate() फ़ंक्शन रनटाइम में निर्दिष्ट स्ट्रिंग से crc32 पर विचार करता है, अपने xml डेटाबेस में एक ही चेकसम के साथ अनुवाद की खोज करता है और इसे वापस करता है।

मैं यह नहीं बताऊंगा कि यह निर्णय कितना न्यायसंगत है, लेकिन समय के अनुसार इसका परीक्षण किया गया है और यह काफी विश्वसनीय साबित हुआ है। और सब ठीक हो जाएगा, लेकिन ऐसा समाधान कमियों के बिना नहीं है: वास्तव में, फ़ंक्शन एक अतिरिक्त काम करता है - चेकसम को एक बार संकलन चरण पर गिना जा सकता है, और भविष्य में, तैयार-किए गए संख्यात्मक मूल्यों का उपयोग किया जा सकता है। यह निष्पादन योग्य छवि में डुप्लिकेट लाइनों को संग्रहीत करने की आवश्यकता को भी समाप्त कर देगा, क्योंकि वे अनुवाद के साथ पहले से बाहरी एक्सएमएल फ़ाइल में हैं।

"संकलन-समय crc32" के अनुरोध पर थोड़ा गुगली करना, मुझे जल्दी से एहसास हुआ कि यह कार्य सबसे तुच्छ नहीं है, लेकिन मैं तैयार समाधान नहीं ढूंढ सका।

दुर्भाग्य से, अपने शुद्ध रूप में टेम्पलेट मेटा-प्रोग्रामिंग का उपयोग करने से काम नहीं चलेगा। टेम्पलेट पैरामीटर के रूप में उपयोग किए जाने वाले स्ट्रिंग के पात्रों का कोई भी संदर्भ कंपाइलर को टेम्पलेट फ़ंक्शन के लिए पुनरावर्ती कॉल को तह करने से रोकता है। उदाहरण के लिए, यह आलेख केवल crc32 गणनाओं के लिए एक तालिका बनाने पर चर्चा करता है। और पूरी तरह से मानक-अनुरूप समाधानों से, केवल एक ही पाया गया था - Boost.MPL । यह सुझाव दिया जाता है कि आप निम्नलिखित प्रवेश फार्म का उपयोग करें:

 meta::hash_cstring< mpl::string<'bunn','ies'> >::value; 

स्ट्रिंग शाब्दिक का उपयोग करने के बजाय, इसे स्ट्रिंग को टुकड़ों में तोड़ने और इसे अलग-अलग टेम्पलेट मापदंडों के साथ देने का प्रस्ताव है। लेकिन उपयोग की गई रिकॉर्डिंग की विचित्रता के अलावा, परियोजना के सभी 2450 लाइनों को इस रूप में परिवर्तित करने के लिए, किसी बाहरी कोड जनरेटर को लिखना होगा और पूरे प्रोजेक्ट टीम को एक नया रिकॉर्डिंग फॉर्म सिखाना होगा।
संदेश भी मंचों के माध्यम से फिसल गए कि नए C ++ 11 में यह विचार क्लासिक टेम्पलेट constexpr और constexpr का उपयोग करके कार्यान्वित किया गया है, लेकिन, दुर्भाग्य से, एक लंबी वंशावली से एक नए मानक पर एक परियोजना को स्थानांतरित करना संभव नहीं है।

कोड जनरेटर का उपयोग करने का एक और विचार था। एक पूर्व-निर्माण कार्यक्रम बनाना संभव होगा, जिस पर अनुवादित स्ट्रिंग्स का इस रूप में अनुवाद करना है:

 _TR(0x12345678/*"Some hashing string"*/); 

लेकिन फिर, मैं कुछ सार्वभौमिक चाहता था ... मैं ऐसा जादुई _TR() चाहता था जो बिना अनावश्यक इशारों के एक साफ crc32 को पीछे छोड़ दे। और फिर मैंने अपनी बाइक को फिर से बनाना शुरू कर दिया।

प्रयास नंबर 1। स्वच्छ मैक्रोज़

इस स्तर पर, मेरे दिमाग में केवल एक विचार गर्म हो रहा था: टेम्पलेट्स के अलावा, मैक्रो को गणना से पहले गणना की जाती है - आपको उनका उपयोग करने की आवश्यकता है!

मैंने विज़ुअल स्टूडियो में एक नई परियोजना बनाई, अधिकतम सीमा रेखा और अधिकतम गति के लिए अनुकूलन सेटिंग्स की स्थापना की। मैंने जाने-माने उपयोगकर्ता-मोड डीबगर OllyDbg में हैश को तह पंक्तियों की सफलता / विफलता का विश्लेषण करने का निर्णय लिया, इसलिए मैं प्रति कोड में केवल एक छोटे से भाग को देखना चाहता हूं और अनावश्यक कचरे के बिना डेटा। ऐसा करने के लिए, मैंने सी-रनटाइम को बंद कर दिया, जिसने कई अन्य रिसीवरों के साथ मिलकर मुझे एक खाली एक्सई प्राप्त करने की अनुमति दी जो आकार में केवल 2 KB थी।

कई प्रयोगों के बाद, मैंने 3 वर्णों से अधिक के तार के लिए crc32 गणना का सरलतम कार्यान्वयन किया:

 static const unsigned int Crc32Table[256] = { 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, /* ... ,*/ 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D }; template <typename T, int N> char (&array_length(T (&)[N]))[N]; //       #define lengthof(x) (sizeof(array_length(x))) //    crc32 #define TR_CRC(crc,i,s) (crc >> 8)^Crc32Table[(crc^s[i])&0xFF] //            #define TR_CRC_COND(crc,i,s) (i<lengthof(s)-1 ? TR_CRC(crc,i,s):crc) //   CRC     ( 3 ) #define _TR(s) TR_CRC_COND(TR_CRC_COND(TR_CRC_COND(TR_CRC_COND(0xFFFFFFFF,0,s),1,s),2,s),3,s)^0xFFFFFFFF int main(int argc, char *argv[]) { //     ,    - DWORD, //             Olly Sleep(_TR("123")); } 

मैक्रोज़ के कार्यान्वयन में, मुख्य समस्या यह है कि हम crc गणना चक्र को लाइन की लंबाई के साथ पुनरावृत्तियों की आवश्यक संख्या तक नहीं ला सकते हैं, जैसा कि टेम्पलेट मेटाप्रोग्रामिंग में है। एक मैक्रो हमेशा शुरुआत के रूप में कई पुनरावृत्तियों के रूप में होगा। उदाहरण के लिए, उपरोक्त उदाहरण में, स्ट्रिंग "1" की गणना अभी भी 4 पुनरावृत्तियों (अधिकतम 3 वर्णों + '\ 0') में की जाएगी, इस तथ्य के बावजूद कि इसकी लंबाई केवल एक वर्ण है। यह एक सशर्त ऑपरेशन द्वारा बाईपास किया जाता है, जो पिछले पुनरावृत्ति से सीआरसी मूल्य को हथेली पर ले जाता है, यदि स्ट्रिंग पहले से ही अंतिम चरित्र की गणना की गई है।

डिबगर में परिणामी exe चलाने के बाद, मैंने क़ीमती PUSH 884863D2 देखा, जिसकी सही गणना पहले crc32 ऑनलाइन कैलकुलेटर द्वारा आसानी से पुष्टि की जाती है जो सामने आया था।



यह देखने का समय आ गया है कि यदि आप मैक्रो को लाइन की लंबाई से दोहराते हैं, तो संकलन की गति कितनी कम हो जाती है, जिससे आप प्रोजेक्ट की आवश्यकताओं को पूरा कर सकते हैं। अनुवाद डेटाबेस में सबसे लंबी लाइन 350 अक्षरों से थोड़ी कम थी, इसलिए मैं कम से कम 500 अक्षरों की सीमा में फिट होना चाहता था।

इस प्रकार, मैंने एक स्थूल निकाय उत्पन्न किया जो संक्षिप्त रूप में कुछ इस तरह से दिखता है:

 #define _TR(s) TR_CRC_COND(TR_CRC_COND(/*...*/TR_CRC_COND(TR_CRC_COND(0xFFFFFFFF,0,s),1,s),2,s),3,s)/*...*/,448,s),449,s)^0xFFFFFFFF 

लेकिन यहाँ मैं निराश था जब कंपाइलर ने अपनी ठंड जारी की: "घातक त्रुटि C1009: कंपाइलर सीमा: मैक्रोज़ ने बहुत गहराई से घोंसला बनाया" । स्वाभाविक रूप से, यह पता लगाना संभव था कि घोंसले के शिकार की सीमा कहीं 300 के क्षेत्र में है।

प्रयास नंबर 2। __Forceinline फ़ंक्शन

तब नेस्टेड मैक्रोज़ के बजाय इनलाइन-फ़ंक्शंस का उपयोग करने के लिए कई प्रयास किए गए थे, लेकिन अंत में सब कुछ या तो एक समान त्रुटि में बदल गया (मुझे बिल्कुल याद नहीं है, लेकिन कंपाइलर ने एक जटिल व्याकरण को शाप दिया) या एक अतिरिक्त लंबे संकलन के लिए।

सभी पीड़ा के बाद, मैं इस विचार को छोड़ने के लिए लगभग तैयार था, लेकिन फिर भी अनुक्रमिक गणनाओं और स्ट्रिंग लंबाई की जाँच के एक समूह के साथ एक बड़ा __forceinline फ़ंक्शन लिखने का प्रयास करने का फैसला किया (किसी कारण से मुझे यकीन था कि ऐसा कंपाइलर जीवन में कभी भी नहीं बदलेगा):

 //  ,       #define CRC_STUB_(i) if (i<N-1) { crc = (crc>>8) ^ Crc32Table[(crc^s[i])&0xFF] } template <int N> static __forceinline DWORD CRC_ARR_CALC_(const char (&s)[N]) { static const unsigned int Crc32Table[256] = { 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, /* ... ,*/ 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D }; DWORD crc = 0; CRC_STUB_(0);CRC_STUB_(1);CRC_STUB_(2);CRC_STUB_(3);CRC_STUB_(4);CRC_STUB_(5);CRC_STUB_(6);CRC_STUB_(7);CRC_STUB_(8);CRC_STUB_(9);CRC_STUB_(10);CRC_STUB_(11);CRC_STUB_(12);CRC_STUB_(13);CRC_STUB_(14);CRC_STUB_(15);CRC_STUB_(16);CRC_STUB_(17); /* ... */ CRC_STUB_(498);CRC_STUB_(499); return crc; } 

और यह काम किया! संकलक बहुत जल्दी सभी कोड को एक ही संख्या में ढह गया, जिससे न तो लाइनें खुद को Crc32Table हैं, न ही परिणामी बाइनरी में Crc32Table तालिका। इस तरह के कार्यान्वयन को सही ढंग से संकलित करने के लिए, केवल / O2 स्विच पर्याप्त है। जो कुछ बचा था वह एक पैरामीटर के रूप में crc32 के साथ g_Translator.Translate() विधि के एक अधिभार संस्करण को जोड़ना था, और बिंदु टोपी में है।

कोड को परियोजना में पेश करने के बाद, रिलीज़ बिल्ड का संकलन 1-2 मिनट लंबा हो गया, लेकिन बाइनरी 200 Kb से आसान हो गया, और अब यह उपयोगकर्ताओं को अनावश्यक काम करने के लिए मजबूर नहीं करता है, जिससे उनके लैपटॉप बैटरी पर थोड़ी देर चल सकते हैं :)

परीक्षण परियोजना के लिए पूर्ण स्रोत कोड यहां लिया जा सकता है: 7z , tar.gz