1988 के International Obfuscated C Code Contest की विजेता रचना, Xmas.c

• 1988 की International Obfuscated C Code Contest की विजेता xmas.c एक ऐसे C कोड की तरह दिखती है जिसे मानो किसी ने बेतरतीब टाइप किया हो, लेकिन यह The Twelve Days of Christmas के बोल प्रिंट करती है
• आउटपुट से भी छोटे कोड में एन्क्रिप्टेड स्ट्रिंग्स रखी गई हैं, और substitution cipher तथा recursive calls से शब्दों और वाक्यांशों को डिक्रिप्ट किया जाता है
• ternary operator को if-then-else ब्लॉक्स में खोलने और words, shift नाम देने पर यह संरचना साफ दिखती है कि t का मान recursive flow को बदलता है
• shift आगे के अक्षरों को 31 स्थान बाद के अक्षरों से मैप करता है, और words में स्लैश(/) से अलग किए गए एन्क्रिप्टेड गीत-अंश हैं
• यह एक साधारण lyrics-printing प्रोग्राम है, लेकिन substitution cipher, bidirectional recursion, अनावश्यक कोड और इस्तेमाल न होने वाले arguments मिलकर इसे C obfuscation का एक रचनात्मक उदाहरण बनाते हैं

---

xmas.c क्या प्रिंट करता है

• xmas.c 1988 International Obfuscated C Code Contest का विजेता C प्रोग्राम है
• विश्लेषक ने यह प्रोग्राम पहली बार लगभग 2000 में देखा और नवंबर 2008 में कोड को तोड़कर इसकी कार्यप्रणाली समझी
• बिना किसी parameter के compile और run करने पर यह Christmas carol The Twelve Days of Christmas के दिन 1 से दिन 12 तक के बोल प्रिंट करता है
• मूल कोड की टिप्पणियों में लिखा है कि यह प्रोग्राम अपने आउटपुट के “compressed” रूप से भी छोटा है, और निर्णायकों ने सोचा कि यह “पुरानी typewriter को बेतरतीब ठोकने” का नतीजा लगता है

आसान पढ़ाई के लिए खोली गई आंतरिक संरचना

• विश्लेषण का पहला कदम सभी a ? b : c रूपों को स्पष्ट if-then-else ब्लॉक्स में बदलना था
• जिन दो स्ट्रिंग्स का अर्थ समझना कठिन था, उन्हें उनकी भूमिका के अनुसार नाम दिए गए
  • words: Christmas carol के बोल बनाने वाले एन्क्रिप्टेड शब्दों और वाक्यांशों का सेट
  • shift: एन्क्रिप्टेड अक्षरों को वास्तविक आउटपुट अक्षरों में बदलने वाली substitution स्ट्रिंग
• main() की शुरुआत xmas(1, 0, '\0') से होती है, और उसके बाद एक ही xmas() फ़ंक्शन recursion के ज़रिए पूरा आउटपुट संभालता है
• वेरिएबल t recursion की दिशा और branching behavior को नियंत्रित करने वाला मुख्य मान है

substitution cipher और lyrics data

• shift स्ट्रिंग व्यवहार में दो स्ट्रिंग्स को जोड़कर बनाई गई रचना की तरह काम करती है
• पहले आधे में मिला कोई अक्षर 31 स्थान बाद वाले अक्षर में डिक्रिप्ट होता है
  • उदाहरण के लिए, स्ट्रिंग का पहला अक्षर ! 31 स्थान बाद के newline character से मेल खाता है
• t < -50 branch स्ट्रिंग a को एक-एक अक्षर आगे बढ़ाती है, जब तक input character _ shift में नहीं मिल जाता
  • मिलान होने पर यह a[31] प्रिंट करती है और लौट जाती है
• words स्ट्रिंग substitution cipher से खुलने वाला एन्क्रिप्टेड lyrics data है
  • ordinal expressions और हर verse के lyrics fragments स्लैश(/) character से अलग किए गए हैं

recursive branches की भूमिकाएँ

• t < -72 branch पहले दो arguments को बदलकर तीसरे argument के रूप में words डालते हुए फिर कॉल करती है
  • इसका मुख्य उद्देश्य भ्रम पैदा करना है, और यह nested recursion को संभव बनाती है जिसमें तीसरा argument अनदेखा किया जाता है
• t < 0 branch स्ट्रिंग में |t|वाँ स्लैश(/) ढूँढती है और उसके बाद के अक्षर से शुरू होने वाली स्ट्रिंग पास करती है
• t == 0 branch अगला स्लैश आने तक स्ट्रिंग को डिक्रिप्ट करके प्रिंट करती है और फिर 1 लौटाती है
• t == 1 branch शुरुआत में सिर्फ एक बार कॉल होती है और xmas(2, 2, "%s") के साथ वास्तविक recursion शुरू करती है
• t == 2 branch "On the [ordinal] day of Christmas my true love gave to me\n" फ़ॉर्मैट की पहली पंक्ति प्रिंट करती है
• आख़िरी दो condition blocks recursion को दो दिशाओं में बनाए रखते हैं
  • वर्तमान दिन से नीचे जाते हुए उस verse के बोल उल्टे क्रम में प्रिंट करना
  • दिन बढ़ाते हुए 12वें दिन तक पूरे verses दोहराना

सरल करने पर दिखने वाला execution flow

• कामकाज समझ लेने के बाद इसे loops और C string library routines की मदद से अधिक सरल कोड में बदला जा सकता है
• simplified version में भी मुख्य data words और shift वैसे ही रहते हैं
• t < 0 branch index(a, '/') का उपयोग करके स्लैश delimiter ढूँढती है और इच्छित lyrics fragment की जगह तक जाती है
• t == 0 branch index(shift, *a++)[31] से अक्षरों को डिक्रिप्ट करके प्रिंट करती है
• t == 2 branch एक verse की शुरुआत इस क्रम में प्रिंट करती है
  • "On the "
  • उस दिन का ordinal
  • " my true love gave to me\n"

obfuscation दिलचस्प क्यों है

• इस प्रोग्राम को अंत तक सरल करने पर यह lyrics प्रिंट करने वाले कोड के रूप में समझा जा सकता है
• मूल रूप substitution cipher और recursion को साथ इस्तेमाल करके साधारण आउटपुट से कहीं अधिक जटिल संरचना बनाता है
• छोटे-छोटे अनावश्यक कोड और वास्तव में उपयोग न होने वाले मनमाने arguments इसे समझना और कठिन बना देते हैं
• इसे समझ लेना और ऐसा कोड खुद लिख पाना अलग-अलग बातें हैं, और xmas.c को रचनात्मक C कोड के उदाहरण के रूप में देखा जाता है

[GN⁺]

Hacker News की राय

• TeX की तरफ भी ऐसा ही एक उदाहरण xii.tex है
  इस सामग्री को .tex फ़ाइल में डालकर pdftex चलाने के बाद बने PDF को देखें तो यह ऐसा दिखता है: https://shreevatsa.net/post/xii/

  • यह obfuscation से ज़्यादा खास तौर पर logical compression का एक रूप लगता है

• जब यह मूल रूप से रिलीज़ हुआ था, तब मैंने इसे डाउनलोड कर रखा था, लेकिन इस पोस्ट के फ़ाइलनाम से अलग, मेरी फ़ाइल carol.c थी
  आधुनिक सिस्टम पर compile करके चलाया तो gcc -o carol carol.c में return type defaults to ‘int’, type of ‘t’ defaults to ‘int’, type of ‘_’ defaults to ‘int’ जैसी warnings आईं

  • GCC 14 से implicit int को अब अनुमति नहीं दी जाएगी: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
  • समस्या यह है कि main के अंदर xmas() को define होने से पहले call किया गया है
    macOS के GCC से compile करने पर ISO C99 and later do not support implicit function declarations error आता है, और main() को नीचे ले जाने पर यह सही से compile होता है और सही output देता है
  • यह हैरानी की बात है कि warnings अप्रत्याशित रूप से कम हैं, और सब एक ही लाइन से आती हैं

• इसे देखकर Kolmogorov complexity याद आती है
  यहां program बकवास-सा दिखता है, लेकिन desired output बनाता है, इसलिए जिज्ञासा होती है कि क्या उसी output को देने वाला इससे छोटा और इससे भी ज़्यादा अटपटा program हो सकता है
  ऐसा program कैसे ढूंढा जा सकता है?

  • 12 Days of Christmas के lyrics print करने वाले सबसे छोटे C program का मौजूदा record 431 bytes है: https://code.golf/12-days-of-christmas#c
  • और छोटे programs के होने की संभावना आम तौर पर काफी है
    लेकिन brute-force search बहुत inefficient है, इसलिए व्यावहारिक जवाब mathematical अर्थ में “smart तरीके से करो” के करीब है
    सामान्य तौर पर Kolmogorov complexity computable नहीं है, इसलिए ऐसा कोई program मौजूद नहीं है जो किसी string को लेकर उस string को compute करने वाला shortest program वापस दे
    हालांकि किसी specific string की Kolmogorov complexity X है, यह कोई व्यक्ति सिद्ध कर सके—यह सिद्धांततः संभव है
  • ज़्यादातर मामलों में Kolmogorov complexity को सीधे compute करना practically impossible है, और मेरे हिसाब से हम सिर्फ possibility के नजरिये से तुलना कर सकते हैं, जैसे कि यह किसी version या value से धीमा है
    इसलिए यह long-running contests और competition के लिए अच्छा बैठता है, और log जैसी growth curve की वजह से बहुत आखिरी हिस्सों में दिलचस्प discoveries भी निकल आती हैं
    अभी मैं अगले मार्च तक pi के digits सबसे ज़्यादा याद रखने वाले LLMs की एक mini contest चला रहा हूं, मौजूदा prize $100 है और इसे log space में contribution ratio के हिसाब से distribute करने का इरादा है
    pi theoretically काफी compressible है, इसलिए यह देखना रोचक होगा कि क्या model data से high-compression algorithm recover करने वाली minimum description length (MDL) के करीब weights का set सीख सकता है
    हालांकि off-the-shelf models से यह संभव है या नहीं, यह अभी साफ नहीं है, इसलिए फिलहाल इसे digits memorization contest के रूप में रखकर देखूंगा

• explanation अच्छी है, और IOCCC 2023 में भी जीवित लग रहा है: https://www.ioccc.org/years.html

  • उस page को देखें तो आखिरी IOCCC 2020 के रूप में दिखता है
    लेकिन homepage पर May 2023 update में लिखा है कि “28th IOCCC आयोजित करने की योजना” है
    Nethack release जैसी कुछ चीजें इंतज़ार के लायक होती हैं

• हाल ही में The Twelve Days of Christmas के बारे में एक मज़ेदार बात पता चली: सारे gifts किसी न किसी तरह के birds हैं
  leaping ladies और lords तक सब ऐसे ही हैं, ऐसा कहा जाता है

  • पूरा यकीन नहीं है
    Wikipedia के मुताबिक lyrics का सबसे पुराना ज्ञात publication 1780 में London से निकली illustrated children’s book Mirth Without Mischief है: https://en.wikipedia.org/wiki/The_Twelve_Days_of_Christmas_(...
    यह site सबको birds से जोड़ने की कोशिश करती है https://www.birdspot.co.uk/culture/the-birds-of-the-twelve-d... खासकर Five Gold Rings पर बात काफी खिंच जाती है
    Mirth and Mischief में rings को साफ तौर पर jewellery की तरह दिखाने वाली illustration है, और Archive.org पर scan भी है: https://archive.org/details/mirth_without_mischief/page/n7/m...
  • यह मैंने The Office से सीखा था :D

• 20 साल से भी ज़्यादा पहले मैंने खुद जो research की थी, वह भी है: http://michaeldnahas.com/xmassong/index.html

• warnings बंद कर दें तो यह अभी भी trunk पर चलता है: https://compiler-explorer.com/z/hGvs1e9jo

• 2022 में, जब university के मेरे आखिरी दो semesters थे, professor ने lecture शुरू होते ही यह code snippet दिखाया था—यह अच्छी याद ताज़ा हो गई

  • “university के आखिरी दो semesters, यानी बस पिछले साल!” जैसा पढ़ने पर ऐसा भी लगता है जैसे बहुत पुरानी बात होने से याद धुंधली होने वाला joke हो
    समझ नहीं आ रहा कि यह genuine है या restrained comedy

• college में professor ने C language के printed course material में इसे शामिल किया था, इसलिए याद है कि मैंने एक बार इसे हाथ से type किया था

• Rosetta Code पर भी ऐसा ही एक task है
  यह repeatedly बढ़ते जाने वाले song Old Lady Swallowed a Fly को print करने वाला program है: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly

  • Tcl version मुझे पसंद है, क्योंकि उसमें lyrics को बस compress करके रखा गया है
    puts [zlib inflate [binary decode base64 "7VRNa8MwDL3nV2(...)"]]
    https://rosettacode.org/wiki/Old_lady_swallowed_a_fly#Tcl
    Python, Nim, Julia वगैरह में भी ऐसे versions होने की संभावना काफी है