पुनरावर्ती ज़िप संग्रह

कई हाबरा उपयोगकर्ता संभवतः क्वेंस - कार्यक्रमों से परिचित हैं जो अपने स्वयं के स्रोत कोड प्रदर्शित करते हैं। आज मैं दिखाना चाहता हूं कि क्वीन का एक दिलचस्प संस्करण कैसे बनाया जाए - एक ज़िप संग्रह जो स्वयं में अनपैक्ड है ।

लेम्पेल-ज़िव एलगोरिदम

ज़िप फ़ाइलों ( Lempel-Ziv ) में इस्तेमाल किया एल्गोरिथ्म वास्तव में काफी सरल है। इसके दो प्रकार के निर्देश हैं: literal(n) , इसके बाद डेटा की एक धारा है जो आउटपुट के रूप में होना चाहिए, और repeat(d, n) , जो d बाइट्स द्वारा वापस जाता है और इस स्थिति से n बाइट्स आउटपुट करता है।

तदनुसार, हमारा कार्य इस प्रकार है: स्टार्टअप पर अपना कोड प्रदर्शित करने वाले प्रोग्राम को लिखने के लिए इस एल्गोरिदम का उपयोग करना। दूसरे शब्दों में, एक संपीड़ित डेटा स्ट्रीम लिखें जो अपने आप को दर्शाती है। अधिकतम कार्यक्रम: शुरुआत और अंत में मनमाना डेटा के साथ खुद को फैलाने वाली एक धारा लिखें (ताकि इसका उपयोग वास्तविक ज़िप या गज़िप फ़ाइल के रूप में किया जा सके, हेडर और अन्य आवश्यक डेटा के साथ)।

चलो Ln और Rn को literal(n) और repeat(n, n) लिए संक्षिप्त रूप में उपयोग करने के लिए सहमत हैं, और प्रोग्राम मानता है कि प्रत्येक कोड एक बाइट है। L0, क्रमशः, Lempel-Ziv में NOP का एक एनालॉग है, L5 hello , L5 hello को आउटपुट करेगा; वही L3 hel R1 L1 o ।

एक साधारण रानी इस तरह दिखाई देगी:

		कोड		निष्कर्ष
कोई-op		L0
कोई-op		L0
कोई-op		L0
4 बाइट्स प्रिंट करें		L4 L0 L0 L0 L4		L0 L0 L0 L4
पिछले 4 बाइट्स दोहराएं		R4		L0 L0 L0 L4
4 बाइट्स प्रिंट करें		L4 R4 L4 R4 L4		R4 L4 R4 L4
पिछले 4 बाइट्स दोहराएं		R4		R4 L4 R4 L4
4 बाइट्स प्रिंट करें		L4 L0 L0 L0 L0		L0 L0 L0 L0

(यह देखा जा सकता है कि "कोड" और "आउटपुट" कॉलम की सामग्री समान हैं)

कार्यक्रम का एक दिलचस्प हिस्सा 6 बाइट्स L4 R4 L4 R4 L4 R4 का एक अनुक्रम है, जो 8 बाइट्स को आउटपुट करता है: R4 L4 R4 L4 R4 L4 R4 । यही है, यह एक बाइट से पहले और एक के बाद खुद को प्रदर्शित करता है।

यदि हम पाइथन में क्वीन लिखते हैं, तो आमतौर पर समस्या यह होती है कि print स्टेटमेंट हमेशा प्रिंट की तुलना में अधिक लंबा होता है। हम पुनरावृत्ति के साथ इस समस्या को हल करते हैं, अपने आप में मुद्रण के लिए लाइन को प्रतिस्थापित करते हैं। यहां हम एक अलग दृष्टिकोण का उपयोग कर सकते हैं। लेम्पेल-ज़िव पर कार्यक्रम आंशिक रूप से दोहराया जाता है, ताकि बार-बार प्रतिस्थापन में संपूर्ण मूल टुकड़ा हो। यहाँ पुनरावृत्ति कार्यक्रम की बहुत ही प्रस्तुति में है, निष्पादन में नहीं। किसी भी मामले में, यह टुकड़ा महत्वपूर्ण है। अंतिम R4 तक, प्रोग्राम आउटपुट इनपुट के पीछे रहता है। निष्पादन के बाद, आउटपुट इनपुट के आगे एक बाइट है।

डमी ऑपरेटर L0 उपयोग कार्यक्रम के अधिक सामान्य संस्करण में भी किया जा सकता है, जो खुद को मनमाने ढंग से तीन-बाइट उपसर्ग और प्रत्यय के साथ पूरक कर सकता है:

		कोड		निष्कर्ष
4 बाइट्स प्रिंट करें		L4 aa bb cc L4		aa bb cc L4
पिछले 4 बाइट्स दोहराएं		R4		aa bb cc L4
4 बाइट्स प्रिंट करें		L4 R4 L4 R4 L4		R4 L4 R4 L4
पिछले 4 बाइट्स दोहराएं		R4		R4 L4 R4 L4
4 बाइट्स प्रिंट करें		L4 R4 xx yy zz		R4 xx yy zz
पिछले 4 बाइट्स दोहराएं		R4		R4 xx yy zz

(आउटपुट शुरुआत में जोड़े गए कोड प्लस ए aa bb cc बराबर है और xx yy zz अंत में जोड़ा गया)

मुझे इस मुकाम पर पहुंचने के लिए ज्यादातर रविवार बिताने पड़े, लेकिन जब मैंने ऐसा किया, तो मुझे पहले से ही पता था कि मैं जीत चुका हूं। अपने प्रयोगों से, मुझे पता चला कि यह एक प्रोग्राम बनाना काफी आसान है जो कुछ निर्देशों के बिना खुद को प्रदर्शित करता है, या एक भी जो उपसर्ग के साथ खुद को प्रदर्शित करता है, कुछ निर्देशों को घटाता है। आउटपुट में अतिरिक्त बाइट्स aa bb cc आप कार्यक्रम में वांछित टुकड़ा जोड़ने के लिए अनुमति देते हैं। यह कोड लिखना भी आसान है जो खुद को एक अतिरिक्त तीन बाइट्स xx yy zz आउटपुट करता है। इन दोनों ट्रिक्स का उपयोग हेडर और अतिरिक्त डेटा को अंत में आर्काइव में जोड़ने के लिए किया जा सकता है।

यह कैसे मनमाना उपसर्ग और प्रत्यय के साथ एक कार्यक्रम है:

		कोड		निष्कर्ष
प्रिंट उपसर्ग		[P]		P
प्रिंट पी + 1 बाइट		L p +1 [P] L p +1		[P] L पी १
अंतिम p +1 बाइट्स दोहराएं		R पी +1		[P] L पी १
1 बाइट प्रिंट करें		L1 R पी +1		R पी +1
1 बाइट प्रिंट करें		L1 L1		L1
4 बाइट्स प्रिंट करें		L4 R पी +1 L1 L1 L4		R पी +1 L1 L1 L4
अंतिम 4 बाइट्स दोहराएं		R4		R पी +1 L1 L1 L4
4 बाइट्स प्रिंट करें		L4 R4 L4 R4 L4		R4 L4 R4 L4
अंतिम 4 बाइट्स दोहराएं		R4		R4 L4 R4 L4
4 बाइट्स प्रिंट करें		L4 R4 L0 L0 L s +1		R4 L0 L0 L s +1
अंतिम 4 बाइट्स दोहराएं		R4		R4 L0 L0 L s +1
कोई-op		L0
कोई-op		L0
आउटपुट s +1 बाइट्स		L s +1 R s +1 [S]		R s +1 [S]
अंतिम s +1 बाइट्स दोहराएं		R s +1		R s +1 [S]
प्रिंट प्रत्यय		[S]		S

(आउटपुट पी है, फिर "कोड" कॉलम से बाइट्स, फिर एस।)

अनज़िप्ड ज़िप फ़ाइल

अब हम वास्तविक क्रियाओं को पास करते हैं। हमने एक पुनरावर्ती ज़िप फ़ाइल बनाने की मुख्य तकनीकी समस्या को हल किया, लेकिन कुछ और विवरण बने रहे।

पहली समस्या: सरलीकृत opcodes में दर्ज की गई हमारी क्वीन को वास्तविक लेम्पेल-ज़िव ऑपकोड में अनुवाद करें। RFC 1951 , gzip और zip में प्रयुक्त DEFLATE प्रारूप को परिभाषित करता है; ब्लॉकों का एक क्रम, जिनमें से प्रत्येक में हफमैन कोडिंग द्वारा एन्कोड किए गए ओपकोड का एक अनुक्रम होता है। हफ़मैन कोडिंग अलग-अलग लंबाई के तार को अलग-अलग opcodes को असाइन करता है, जो हमारी धारणा के साथ मेल नहीं खाता है कि opcodes की लंबाई समान है। लेकिन एक पल रुकिए! यदि हम कोशिश करते हैं, तो एक निश्चित लंबाई वाले एन्कोडिंग का उपयोग कर सकते हैं।

DEFLATE में शाब्दिक ब्लॉक और opcode ब्लॉक हैं। शाब्दिक ब्लॉक हेडर 5 बाइट्स है:



यदि हमारा opcodes L 5 बाइट्स पर कब्जा करता है, तो opcodes R को 5 बाइट्स पर भी कब्जा करना चाहिए, और ऊपर दिए गए प्रत्येक बाइट को पांच बार दोहराया जाएगा (उदाहरण के लिए, L4 के लिए तर्क में अब 20 बाइट्स लगते हैं, और R4 आउटपुट के अंतिम 20 बाइट्स को दोहराता है)। एक repeat(20,20) का ब्लॉक 5 बाइट्स से थोड़ा कम होता है:



सौभाग्य से, एक repeat(20,10) ब्लॉक जिसमें दो repeat(20,10) निर्देश हैं, वही करता है और ठीक 5 बाइट्स लेता है:



एक अलग तर्क लंबाई के साथ repeat कुछ और जटिल चाल की आवश्यकता है, लेकिन ऐसा लगता है कि हम 5-बाइट कोड विकसित कर सकते हैं जो एक स्ट्रिंग को 9 से 64 बाइट्स लंबाई में दोहराते हैं। उदाहरण के लिए, यहां 10 और 40 बाइट्स को दोहराने वाले ब्लॉक हैं:





पिछले 10 बाइट्स को दोहराने वाला एक ब्लॉक आवश्यक से 2 बिट कम है, लेकिन पुनरावृत्ति के प्रत्येक ब्लॉक का पालन शाब्दिकों के एक ब्लॉक द्वारा किया जाता है जो तीन शून्य बिट्स से शुरू होता है और निकटतम बाइट की सीमा तक पूरा होता है। यदि सीमा से पहले रिपीट ब्लॉक 2 बिट्स समाप्त हो जाता है और उसके बाद शाब्दिक ब्लॉक होता है, तो पैडिंग लापता दो बिट्स को सम्मिलित करेगा। उसी तरह, 40 बाइट्स को दोहराने वाला एक ब्लॉक 5 बिट्स द्वारा विदेश जाता है, लेकिन ये बिट्स शून्य हैं। 5 बिट्स बाद में ब्लॉक करना शुरू करें, हम इन बिट्स को फिनिश से दूर ले जाते हैं। ये दोनों तरकीबें काम करती हैं क्योंकि किसी भी रिपीट ब्लॉक के अंतिम 7 बिट्स शून्य हैं, और शाब्दिक ब्लॉक के पहले बाइट में बिट्स भी शून्य हैं, इसलिए सीमा दिखाई नहीं देती है। अगर शाब्दिकों का एक खंड एक बिट के साथ शुरू हुआ, तो यह मुश्किल चाल काम नहीं करेगी।

दूसरी बाधा यह है कि ज़िप अभिलेखागार (और gzip भी) असम्पीडित डेटा का एक चेकसम स्टोर करते हैं। चूंकि असंपीड़ित डेटा समान ज़िप संग्रह है, चेकसम भी गणना में भाग लेता है। इसलिए, हमें x का मान ज्ञात करने की आवश्यकता है जिस पर चेकसम x बराबर हो जाता है। पुनरावृत्ति वापस आ रही है।

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

यदि आप यह सब अपने आप को दोहराना चाहते हैं, तो आपके पास अभी भी कुछ सरल समस्याएं होंगी, उदाहरण के लिए, टार-फाइल को बिना बचे 512 से विभाजित करना और ज़िप हैडर को 59 बाइट्स में संपीड़ित करना ताकि Rs+1 R64 से अधिक न हो। लेकिन यह सिर्फ एक प्रोग्रामिंग मुद्दा है।

तो, मुझे r.gz (gzip संग्रह), r.tar.gz (टार फ़ाइल, संपीड़ित gzip), और r.zip (ज़िप संग्रह) फ़ाइलें मिलीं । यह एक अफ़सोस की बात है, लेकिन मुझे ऐसा प्रोग्राम नहीं मिला, जो इन फ़ाइलों को अनिश्चित काल के लिए अनपैक कर सके। यह देखना मजेदार होगा, लेकिन ऐसा लगता है कि बहुत कम परिष्कृत जिप बमों ने पहले से ही हमें सभी मज़ा खराब कर दिया है।

यदि आप फिट महसूस करते हैं, तो यहां rgzip.go है , जो एक गो कार्यक्रम है जो इन फ़ाइलों को उत्पन्न करता है। मुझे आश्चर्य है कि यदि आप एक ज़िप फ़ाइल बना सकते हैं जिसमें एक gzip फ़ाइल हो, जिसमें मूल ज़िप फ़ाइल हो)। केन थॉम्पसन ने सुझाव दिया कि एक ज़िप संग्रह बनाने की कोशिश की जाए जो थोड़े बड़े आकार की एक प्रति को हटाता है ताकि पुनरावर्ती रूप से अनपैक करते समय, संग्रह आकार अनिश्चित काल तक बढ़ता रहे (यदि आप एक या दूसरे में सफल होते हैं, तो कृपया एक टिप्पणी छोड़ दें)।