xmas.c ผลงานชนะเลิศการประกวดโค้ด C แบบทำให้อ่านยากระดับนานาชาติปี 1988

 (udel.edu)
3 คะแนน โดย GN⁺ 2023-12-24 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • xmas.c ผลงานชนะเลิศจาก International Obfuscated C Code Contest ปี 1988 เป็นโค้ด C ที่ดูเหมือนการพิมพ์มั่ว ๆ และพิมพ์เนื้อเพลง The Twelve Days of Christmas ออกมา
  • มันเก็บสตริงที่เข้ารหัสไว้ในโค้ดซึ่งมีขนาดเล็กกว่าผลลัพธ์ที่พิมพ์ออกมา แล้วถอดรหัสคำและวลีด้วย substitution cipher และการเรียกซ้ำแบบ recursive
  • เมื่อลองคลี่ ternary operator ออกเป็นบล็อก if-then-else และตั้งชื่อให้ words, shift ก็จะเห็นโครงสร้างที่ค่า t ใช้เปลี่ยนทิศทางของการไหลแบบ recursive
  • shift จับคู่ตัวอักษรด้านหน้ากับตัวอักษรที่อยู่ถัดไป 31 ตำแหน่ง และ words เก็บ ชิ้นส่วนเนื้อเพลงที่เข้ารหัสไว้ โดยคั่นด้วยเครื่องหมายทับ (/)
  • แม้จะเป็นเพียงโปรแกรมพิมพ์เนื้อเพลงธรรมดา แต่การซ้อนกันของ substitution cipher, recursion สองทิศทาง, โค้ดที่ไม่จำเป็น และอาร์กิวเมนต์ที่ไม่ได้ใช้ ทำให้มันยังคงเป็นตัวอย่างการทำให้โค้ด C อ่านยากอย่างสร้างสรรค์

สิ่งที่ xmas.c พิมพ์ออกมา

  • xmas.c เป็นโปรแกรมภาษา C ที่ชนะ International Obfuscated C Code Contest ในปี 1988
  • ผู้วิเคราะห์พบโปรแกรมนี้ครั้งแรกประมาณปี 2000 และแยกโครงสร้างโค้ดเพื่อทำความเข้าใจการทำงานในเดือนพฤศจิกายน 2008
  • เมื่อคอมไพล์และรันโดยไม่ส่งอาร์กิวเมนต์ มันจะพิมพ์เนื้อเพลงคริสต์มาสแครอล The Twelve Days of Christmas ตั้งแต่วันแรกจนถึงวันที่สิบสอง
  • ในคอมเมนต์ของโค้ดต้นฉบับมีข้อความว่าโปรแกรมมีขนาดเล็กกว่ารูปแบบที่ “บีบอัด” ของผลลัพธ์เสียอีก และกรรมการคิดว่ามันดูเหมือน “ผลลัพธ์จากการเคาะเครื่องพิมพ์ดีดเก่าแบบสุ่มเป็นเวลานาน”

โครงสร้างภายในเมื่อคลี่ให้อ่านง่าย

  • ขั้นแรกของการวิเคราะห์คือเปลี่ยนทุกโครงสร้าง a ? b : c ให้เป็นบล็อก if-then-else แบบชัดเจน
  • สตริงสองชุดที่เดาความหมายได้ยากถูกตั้งชื่อใหม่ตามหน้าที่
    • words: ชุดคำและวลีที่เข้ารหัสไว้เพื่อประกอบเป็นเนื้อเพลงคริสต์มาสแครอล
    • shift: สตริงสำหรับแทนที่อักขระที่เข้ารหัสให้กลายเป็นอักขระจริงที่ต้องพิมพ์
  • main() เริ่มด้วย xmas(1, 0, '\0') และหลังจากนั้นฟังก์ชัน xmas() เพียงตัวเดียวจะจัดการการพิมพ์ทั้งหมดแบบ recursive
  • ตัวแปร t คือค่าหลักที่ควบคุมทิศทางของ recursion และพฤติกรรมการแตกแขนง

substitution cipher และข้อมูลเนื้อเพลง

  • สตริง shift ทำงานราวกับเป็นการนำสองสตริงมาต่อกัน
  • อักขระที่พบในครึ่งแรกจะถูกถอดรหัสเป็นอักขระที่อยู่ถัดไป 31 ตำแหน่ง
    • ตัวอย่างเช่น อักขระแรกของสตริงคือ ! จะตรงกับอักขระขึ้นบรรทัดใหม่ที่อยู่ถัดไป 31 ตำแหน่ง
  • กิ่ง t < -50 จะเลื่อนผ่านสตริง a ทีละตัวอักษรจนกว่าจะพบอักขระอินพุต _ อยู่ใน shift
    • เมื่อพบอักขระที่ตรงกัน มันจะพิมพ์ a[31] แล้วคืนค่า
  • สตริง words คือ ข้อมูลเนื้อเพลงที่เข้ารหัสไว้ ซึ่งจะถูกคลี่ด้วย substitution cipher
    • รูปคำลำดับที่และชิ้นส่วนเนื้อเพลงของแต่ละท่อนถูกคั่นด้วยเครื่องหมายทับ (/)

หน้าที่ของแต่ละกิ่ง recursive

  • กิ่ง t < -72 จะสลับอาร์กิวเมนต์สองตัวแรก แล้วเรียกซ้ำอีกครั้งโดยใส่ words เป็นอาร์กิวเมนต์ตัวที่สาม
    • จุดประสงค์หลักคือทำให้สับสน และเปิดทางให้เกิด recursion ซ้อนที่ไม่สนใจอาร์กิวเมนต์ตัวที่สาม
  • กิ่ง t < 0 จะค้นหาเครื่องหมายทับ (/) ลำดับที่ |t| ภายในสตริง แล้วส่งต่อสตริงที่เริ่มจากตัวอักษรถัดไป
  • กิ่ง t == 0 จะถอดรหัสและพิมพ์สตริงออกมาจนกว่าจะเจอเครื่องหมายทับถัดไป แล้วคืนค่า 1
  • กิ่ง t == 1 ถูกเรียกเพียงครั้งเดียวตอนเริ่มต้น เพื่อเริ่ม recursion จริงด้วย xmas(2, 2, "%s")
  • กิ่ง t == 2 จะพิมพ์บรรทัดแรกในรูปแบบ "On the [ordinal] day of Christmas my true love gave to me\n"
  • บล็อกเงื่อนไขสองส่วนสุดท้ายทำหน้าที่คง recursion ไว้สองทิศทาง
    • ไล่ลงจากวันที่ปัจจุบันเพื่อพิมพ์เนื้อเพลงของท่อนนั้นในลำดับย้อนกลับ
    • เพิ่มวันไปเรื่อย ๆ จนถึงวันที่สิบสองเพื่อวนพิมพ์ครบทุกท่อน

ลำดับการทำงานเมื่อทำให้เรียบง่าย

  • เมื่อเข้าใจการทำงานแล้ว ก็สามารถเขียนใหม่เป็นโค้ดที่ง่ายขึ้นด้วยลูปและรูทีนไลบรารีสตริงของ C
  • แม้ในเวอร์ชันที่ลดรูปแล้ว ข้อมูลหลักอย่าง words และ shift ก็ยังคงเดิม
  • กิ่ง t < 0 ใช้ index(a, '/') เพื่อหาเครื่องหมายทับที่ใช้คั่น แล้วเลื่อนไปยังตำแหน่งของชิ้นส่วนเนื้อเพลงที่ต้องการ
  • กิ่ง t == 0 ใช้ index(shift, *a++)[31] เพื่อถอดรหัสอักขระแล้วพิมพ์ออกมา
  • กิ่ง t == 2 จะพิมพ์ช่วงต้นของแต่ละท่อนตามลำดับต่อไปนี้
    • "On the "
    • คำลำดับของวันนั้น
    • " my true love gave to me\n"

ทำไมความอ่านยากนี้จึงน่าสนใจ

  • หากลดรูปจนสุด โปรแกรมนี้สามารถสรุปได้ว่าเป็นโค้ดสำหรับพิมพ์เนื้อเพลง
  • แต่ต้นฉบับใช้ substitution cipher ร่วมกับ recursion เพื่อสร้างโครงสร้างที่ซับซ้อนกว่าการพิมพ์ธรรมดามาก
  • โค้ดส่วนเกินขนาดเล็กและอาร์กิวเมนต์สุ่มที่จริง ๆ แล้วไม่ถูกใช้งาน ยิ่งทำให้ความเข้าใจโค้ดยากขึ้น
  • การเข้าใจโค้ดกับการเขียนโค้ดแบบนี้ได้เองเป็นคนละเรื่องกัน และ xmas.c ก็ยังถูกมองว่าเป็นตัวอย่างโค้ด C ที่สร้างสรรค์

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-12-24
ความคิดเห็นจาก Hacker News

  • ฝั่ง TeX ก็มีตัวอย่างคล้าย ๆ กันคือ xii.tex
    ถ้าใส่เนื้อหานี้ลงในไฟล์ .tex แล้วรัน pdftex จากนั้นดู PDF ที่ได้ จะออกมาแบบนี้: https://shreevatsa.net/post/xii/

    • ดูเหมือนเป็นรูปแบบหนึ่งของ การบีบอัดเชิงตรรกะ โดยเฉพาะ มากกว่าจะเป็นการทำให้โค้ดอ่านยาก

  • ตอนที่เผยแพร่ครั้งแรกผมดาวน์โหลดเก็บไว้ แต่ต่างจากชื่อไฟล์ในบทความนี้ ไฟล์ของผมชื่อ carol.c
    ลองคอมไพล์และรันบนระบบสมัยใหม่แล้ว ที่ gcc -o carol carol.c มีคำเตือนอย่าง return type defaults to ‘int’, type of ‘t’ defaults to ‘int’, type of ‘_’ defaults to ‘int’

    • ตั้งแต่ GCC 14 เป็นต้นไป จะไม่อนุญาต implicit int อีกแล้ว: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • ปัญหาอยู่ที่ใน main มีการเรียก xmas() ก่อนที่จะนิยาม
      ถ้าคอมไพล์ด้วย GCC บน macOS จะเกิดข้อผิดพลาด ISO C99 and later do not support implicit function declarations และถ้าย้าย main() ลงไปข้างล่าง ก็จะคอมไพล์ได้ถูกต้องและให้เอาต์พุตที่ถูกต้อง
    • น่าทึ่งที่มีคำเตือนน้อยกว่าที่คิด และทั้งหมดออกมาจากบรรทัดเดียวกันเท่านั้น

  • เห็นสิ่งนี้แล้วนึกถึง Kolmogorov complexity
    โปรแกรมนี้ดูเหมือนพูดจาไม่เป็นเรื่อง แต่ก็สร้างเอาต์พุตที่ต้องการได้ เลยสงสัยว่าจะมีโปรแกรมที่สั้นกว่าและดูไร้เหตุผลยิ่งกว่านี้ แต่ให้เอาต์พุตเดียวกันได้ไหม
    แล้วจะหาโปรแกรมแบบนั้นได้อย่างไร?

    • สถิติปัจจุบันของโปรแกรม C ที่สั้นที่สุดสำหรับพิมพ์เนื้อเพลง 12 Days of Christmas คือ 431 ไบต์: https://code.golf/12-days-of-christmas#c
    • โดยมากแล้วมีความเป็นไปได้สูงว่าจะมีโปรแกรมที่สั้นกว่านั้น
      แต่การค้นหาแบบ brute force ไม่มีประสิทธิภาพอย่างยิ่ง คำตอบที่ทำได้จริงจึงใกล้เคียงกับคำว่า “ทำอย่างชาญฉลาด” ในเชิงคณิตศาสตร์
      โดยทั่วไป Kolmogorov complexity เป็นสิ่งที่คำนวณไม่ได้ ดังนั้นจึงไม่มีโปรแกรมที่รับสตริงใด ๆ แล้วส่งคืนโปรแกรมที่สั้นที่สุดซึ่งคำนวณสตริงนั้นได้
      อย่างไรก็ตาม โดยหลักการแล้วเป็นไปได้ที่ใครสักคนจะพิสูจน์ว่า Kolmogorov complexity ของสตริงเฉพาะบางตัวมีค่า X
    • ในกรณีส่วนใหญ่ แทบเป็นไปไม่ได้ที่จะคำนวณ Kolmogorov complexity โดยตรง และผมมองว่าทำได้แค่เปรียบเทียบในเชิงความเป็นไปได้ เช่น ช้ากว่าเวอร์ชันหรือค่าบางอย่าง
      เพราะอย่างนั้นมันจึงเหมาะกับการแข่งขันระยะยาว และด้วยเส้นโค้งการเติบโตแบบลอการิทึม ก็มักมีการค้นพบที่น่าสนใจตรงช่วงท้าย ๆ
      ตอนนี้ผมกำลังจัดมินิคอมเพทิชันแข่ง LLM ที่ท่องจำ ตัวเลขของค่า pi ได้มากที่สุดจนถึงเดือนมีนาคมปีหน้า เงินรางวัลปัจจุบันคือ 100 ดอลลาร์ และจะแบ่งตามสัดส่วนการมีส่วนร่วมในสเกล log
      ค่า pi ในเชิงทฤษฎีบีบอัดได้ค่อนข้างมาก ดังนั้นน่าจะน่าสนใจหากดูว่าโมเดลสามารถเรียนรู้ชุดน้ำหนักที่ใกล้กับ minimum description length (MDL) ซึ่งกู้คืนอัลกอริทึมการบีบอัดสูงจากข้อมูลได้หรือไม่
      แต่ยังไม่ชัดเจนว่าโมเดลสำเร็จรูปทำได้หรือเปล่า ตอนนี้เลยตั้งใจปล่อยไว้เป็นการแข่งขันท่องจำตัวเลขแล้วรอดูไปก่อน

  • คำอธิบายดี และ IOCCC ก็ดูเหมือนยังมีชีวิตอยู่ต่อในปี 2023: https://www.ioccc.org/years.html

    • ถ้าดูหน้านั้น IOCCC ครั้งล่าสุดแสดงไว้ว่าเป็นปี 2020
      แต่หน้าแรกมีอัปเดตเมื่อเดือนพฤษภาคม 2023 ว่า “มีแผนจะจัด IOCCC ครั้งที่ 28”
      มีอะไรบางอย่างที่คุ้มค่ากับการรอ เหมือนกับรีลีสของ Nethack

  • ช่วงหลังมานี้ผมเพิ่งรู้เรื่องน่าสนใจเกี่ยวกับ The Twelve Days of Christmas คือของขวัญทั้งหมดเป็นนกชนิดหนึ่ง
    แม้แต่บรรดาหญิงสาวที่กระโดดและเหล่าขุนนางก็ว่ากันว่าเป็นนกทั้งหมด

    • ไม่แน่ใจนัก
      ตาม Wikipedia สิ่งพิมพ์เนื้อเพลงที่เก่าแก่ที่สุดเท่าที่รู้จักคือหนังสือเด็กมีภาพประกอบชื่อ Mirth Without Mischief ที่ตีพิมพ์ในลอนดอนเมื่อปี 1780: https://en.wikipedia.org/wiki/The_Twelve_Days_of_Christmas_(...
      เว็บไซต์นี้พยายามเชื่อมโยงทุกอย่างเข้ากับนก https://www.birdspot.co.uk/culture/the-birds-of-the-twelve-d... แต่โดยเฉพาะตรง Five Gold Rings นั้นฝืนมาก
      ใน Mirth and Mischief มีภาพประกอบที่วาดแหวนไว้อย่างชัดเจนว่าเป็นเครื่องประดับ และ Archive.org ก็มีสแกนไว้ด้วย: https://archive.org/details/mirth_without_mischief/page/n7/m...
    • ผมเรียนรู้เรื่องนั้นจาก The Office :D

  • มีสิ่งที่ผมเคยค้นคว้าเองเมื่อกว่า 20 ปีก่อนด้วย: http://michaeldnahas.com/xmassong/index.html

  • ถ้าปิดคำเตือน ก็ยังทำงานได้แม้บน trunk: https://compiler-explorer.com/z/hGvs1e9jo

  • ทำให้นึกถึงความทรงจำดี ๆ ตอนปี 2022 ซึ่งเป็นสองเทอมสุดท้ายในมหาวิทยาลัย อาจารย์เอาโค้ดชิ้นนี้มาให้ดูทันทีที่เริ่มคาบ

    • อ่านแล้วเหมือนมุกว่า “สองเทอมสุดท้ายในมหาวิทยาลัย นั่นมันตั้งแต่ปีก่อนเลยนะ!” ราวกับนานจนจำเลือน ๆ
      แยกไม่ออกว่าเขาพูดจริงหรือเป็นตลกแบบสุขุม

  • ตอนเรียนมหาวิทยาลัย อาจารย์ใส่มันไว้ในเอกสารประกอบการสอนภาษา C แบบพิมพ์ออกมา จำได้ว่าครั้งหนึ่งเคยพิมพ์ตามด้วยมือเอง

  • ใน Rosetta Code ก็มีโจทย์คล้ายกัน
    เป็นโปรแกรมที่พิมพ์เพลง Old Lady Swallowed a Fly ซึ่งเป็นเพลงที่ท่อนร้องยาวขึ้นเรื่อย ๆ: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly

    • เวอร์ชัน Tcl ถูกใจผม เพราะเป็นรูปแบบที่แค่บีบอัดเนื้อเพลงไว้
      puts [zlib inflate [binary decode base64 "7VRNa8MwDL3nV2(...)"]]
      https://rosettacode.org/wiki/Old_lady_swallowed_a_fly#Tcl
      Python, Nim, Julia ฯลฯ ก็น่าจะมีเวอร์ชันคล้าย ๆ กัน