Tác phẩm đoạt giải cuộc thi mã C làm rối quốc tế năm 1988, Xmas.c

 (udel.edu)
3 điểm bởi GN⁺ 2023-12-24 | 1 bình luận | Chia sẻ qua WhatsApp
  • xmas.c, tác phẩm đoạt giải International Obfuscated C Code Contest năm 1988, là đoạn mã C trông như gõ ngẫu nhiên nhưng lại in ra lời bài The Twelve Days of Christmas
  • Chương trình nhúng các chuỗi đã mã hóa vào phần mã nhỏ hơn cả phần đầu ra, rồi giải mã từ và cụm từ bằng mật mã thay thế và gọi đệ quy
  • Khi tách toán tử ba ngôi thành các khối if-then-else và đặt tên words, shift, cấu trúc trong đó giá trị t thay đổi luồng đệ quy bắt đầu lộ ra
  • shift ánh xạ ký tự ở phần đầu với ký tự nằm sau 31 vị trí, còn words chứa các mảnh lời bài hát đã mã hóa được ngăn cách bằng dấu gạch chéo (/)
  • Dù chỉ là chương trình in lời bài hát đơn giản, sự kết hợp của mật mã thay thế, đệ quy hai chiều, mã thừa và tham số không dùng đến khiến nó vẫn là một ví dụ sáng tạo về mã C làm rối

xmas.c in ra gì

  • xmas.c là một chương trình C đoạt giải tại International Obfuscated C Code Contest năm 1988
  • Người phân tích lần đầu nhìn thấy chương trình này vào khoảng năm 2000, rồi đến tháng 11 năm 2008 mới tách mã để hiểu cách nó hoạt động
  • Khi biên dịch và chạy không có tham số, nó in ra lời bài hát mừng Giáng sinh The Twelve Days of Christmas từ ngày thứ 1 đến ngày thứ 12
  • Chú thích trong mã gốc có nói rằng chương trình còn nhỏ hơn cả dạng “nén” của phần đầu ra, và các giám khảo cho rằng nó trông như “kết quả của việc gõ ngẫu nhiên trên một máy đánh chữ cũ”

Cấu trúc bên trong sau khi được viết lại cho dễ đọc

  • Bước đầu tiên của quá trình phân tích là chuyển mọi biểu thức dạng a ? b : c thành các khối if-then-else tường minh
  • Hai chuỗi khó hiểu được đặt tên theo đúng vai trò của chúng
    • words: tập hợp các từ và cụm từ đã mã hóa để tạo ra lời bài hát mừng Giáng sinh
    • shift: chuỗi dùng cho phép thay thế để biến ký tự đã mã hóa thành ký tự thực sự được in ra
  • main() bắt đầu bằng xmas(1, 0, '\0'), sau đó chỉ một hàm xmas() xử lý toàn bộ đầu ra bằng đệ quy
  • Biến t là giá trị then chốt điều khiển hướng đệ quy và hành vi phân nhánh

Mật mã thay thế và dữ liệu lời bài hát

  • Chuỗi shift thực tế hoạt động như thể là hai chuỗi được nối lại với nhau
  • Ký tự tìm thấy ở nửa đầu sẽ được giải mã thành ký tự nằm sau nó 31 vị trí
    • Ví dụ, ký tự đầu tiên ! trong chuỗi tương ứng với ký tự xuống dòng nằm sau 31 vị trí
  • Nhánh t < -50 dịch chuyển chuỗi a từng ký tự một cho đến khi ký tự đầu vào _ xuất hiện trong shift
    • Khi tìm được ký tự khớp, nó in a[31] rồi trả về
  • Chuỗi words là dữ liệu lời bài hát đã mã hóa sẽ được giải bằng mật mã thay thế
    • Cách viết thứ tự và các mảnh lời của từng khổ được ngăn cách bằng ký tự gạch chéo (/)

Vai trò của các nhánh đệ quy

  • Nhánh t < -72 gọi lại hàm với hai đối số đầu bị hoán đổi và truyền words làm đối số thứ ba
    • Mục đích chính là gây nhiễu, đồng thời cho phép đệ quy lồng nhau bỏ qua đối số thứ ba
  • Nhánh t < 0 tìm dấu gạch chéo (/) thứ |t| trong chuỗi rồi truyền tiếp chuỗi bắt đầu từ ký tự ngay sau đó
  • Nhánh t == 0 giải mã và in chuỗi cho đến khi gặp dấu gạch chéo tiếp theo, rồi trả về 1
  • Nhánh t == 1 chỉ được gọi một lần lúc bắt đầu để khởi động phần đệ quy chính bằng xmas(2, 2, "%s")
  • Nhánh t == 2 in dòng đầu tiên theo mẫu "On the [ordinal] day of Christmas my true love gave to me\n"
  • Hai khối điều kiện cuối cùng duy trì đệ quy theo hai hướng
    • Đi xuống từ ngày hiện tại để in lời của khổ tương ứng theo thứ tự ngược
    • Tăng ngày lên cho đến ngày thứ 12 để lặp lại toàn bộ các khổ

Luồng thực thi hiện rõ sau khi đơn giản hóa

  • Sau khi hiểu cách hoạt động, có thể chuyển nó thành mã đơn giản hơn bằng vòng lặp và các hàm thư viện chuỗi của C
  • Ngay cả trong phiên bản đơn giản hóa, hai dữ liệu cốt lõi là words và shift vẫn được giữ nguyên
  • Nhánh t < 0 dùng index(a, '/') để tìm dấu phân cách gạch chéo và di chuyển tới vị trí của mảnh lời mong muốn
  • Nhánh t == 0 giải mã và in ký tự bằng index(shift, *a++)[31]
  • Nhánh t == 2 in phần mở đầu của một khổ theo thứ tự sau
    • "On the "
    • số thứ tự của ngày tương ứng
    • " my true love gave to me\n"

Vì sao kiểu làm rối này thú vị

  • Khi được đơn giản hóa đến cùng, chương trình này có thể được rút gọn thành đoạn mã chỉ để in lời bài hát
  • Bản gốc kết hợp mật mã thay thế với đệ quy để tạo ra cấu trúc phức tạp hơn rất nhiều so với việc in đơn thuần
  • Những đoạn mã thừa nhỏ và các đối số ngẫu nhiên thực tế không được dùng đến khiến việc hiểu mã càng khó hơn
  • Hiểu được nó và tự tay viết ra thứ tương tự là hai việc khác nhau; xmas.c được xem là một ví dụ sáng tạo về mã C

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-12-24
Ý kiến trên Hacker News

  • Phía TeX cũng có một ví dụ tương tự là xii.tex
    Đặt nội dung này vào một tệp .tex, chạy pdftex, rồi xem PDF kết quả thì sẽ hiện ra thế này: https://shreevatsa.net/post/xii/

    • Có vẻ đây không hẳn là obfuscation mà giống một dạng nén logic hơn

  • Tôi đã tải về khi nó được công bố lần đầu, và khác với tên tệp trong bài này, tệp của tôi là carol.c
    Khi biên dịch và chạy thử trên hệ thống hiện đại bằng gcc -o carol carol.c, tôi gặp các cảnh báo như return type defaults to ‘int’, type of ‘t’ defaults to ‘int’, type of ‘_’ defaults to ‘int’

    • Từ GCC 14, int ngầm định sẽ không còn được cho phép nữa: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • Vấn đề là trong main, hàm xmas() được gọi trước khi được định nghĩa
      Nếu biên dịch bằng GCC trên macOS thì sẽ báo lỗi ISO C99 and later do not support implicit function declarations; nếu chuyển main() xuống dưới thì nó biên dịch bình thường và cho ra đúng kết quả
    • Điều đáng ngạc nhiên là số cảnh báo lại ít hơn tưởng tượng, và tất cả đều chỉ xuất hiện trên cùng một dòng

  • Nhìn cái này làm tôi nghĩ đến độ phức tạp Kolmogorov
    Chương trình này trông như lảm nhảm nhưng lại tạo ra đúng đầu ra mong muốn, nên tôi tự hỏi liệu có chương trình nào còn ngắn hơn, còn vô nghĩa hơn mà vẫn cho ra cùng kết quả không
    Làm sao có thể tìm được những chương trình như vậy?

    • Kỷ lục hiện tại cho chương trình C ngắn nhất in ra lời bài 12 Days of Christmas là 431 byte: https://code.golf/12-days-of-christmas#c
    • Rất có thể vẫn tồn tại chương trình ngắn hơn
      Nhưng tìm kiếm vét cạn là cực kỳ kém hiệu quả, nên câu trả lời thực tế gần với kiểu “hãy làm thật thông minh” theo nghĩa toán học
      Nói chung, độ phức tạp Kolmogorov là không thể tính được, nên không thể tồn tại một chương trình nhận vào một chuỗi rồi trả về chương trình ngắn nhất tạo ra chuỗi đó
      Tuy vậy, về nguyên tắc vẫn có thể chứng minh rằng độ phức tạp Kolmogorov của một chuỗi cụ thể là X
    • Trong hầu hết trường hợp, việc tính trực tiếp độ phức tạp Kolmogorov về thực tế là bất khả thi, và chỉ có thể so sánh theo nghĩa khả dĩ rằng nó nhỏ hơn một phiên bản hay giá trị nào đó
      Vì thế nó rất hợp với các cuộc thi và cạnh tranh dài hạn, và do đường cong tăng trưởng theo log nên đôi khi có những phát hiện thú vị ở giai đoạn rất muộn
      Hiện tôi đang tổ chức một mini contest kéo dài đến tháng 3 năm sau để xem LLM nào có thể thuộc được nhiều chữ số của số pi nhất; giải thưởng hiện là 100 USD và sẽ được chia theo tỷ lệ đóng góp trong không gian log
      Về mặt lý thuyết, số pi có thể nén khá tốt, nên sẽ rất thú vị nếu xem liệu mô hình có thể học được một bộ trọng số gần với độ dài mô tả tối thiểu (MDL) để khôi phục một thuật toán nén mạnh từ dữ liệu hay không
      Dù vậy, vẫn chưa rõ liệu các mô hình hiện có có làm được không, nên trước mắt cứ xem đây là một cuộc thi ghi nhớ chữ số rồi chờ xem

  • Phần giải thích rất hay, và có vẻ IOCCC vẫn còn sống tới tận năm 2023: https://www.ioccc.org/years.html

    • Nhưng trang đó cho thấy IOCCC gần nhất là vào năm 2020
      Tuy nhiên, trang chủ lại ghi trong bản cập nhật tháng 5/2023 rằng họ “dự định tổ chức IOCCC lần thứ 28”
      Cũng có những thứ đáng để chờ như một bản phát hành Nethack vậy

  • Gần đây tôi mới biết một điều thú vị về The Twelve Days of Christmas: tất cả các món quà đều là một loại chim
    Kể cả các quý cô đang nhảy hay các lãnh chúa cũng vậy

  • Đây là một nghiên cứu tôi tự làm từ hơn 20 năm trước: http://michaeldnahas.com/xmassong/index.html

  • Nếu tắt cảnh báo đi thì nó vẫn chạy cả trên trunk: https://compiler-explorer.com/z/hGvs1e9jo

  • Điều này gợi lại cho tôi một ký ức đẹp: vào năm 2022, trong hai học kỳ cuối ở đại học, giáo sư đã cho xem đoạn mã này ngay khi bắt đầu buổi giảng

    • Cũng có thể đọc nó như một câu đùa kiểu “hai học kỳ cuối đại học, tức là tận năm ngoái rồi đấy!” như thể đã quá lâu nên ký ức mờ nhạt
      Khó phân biệt là nói thật hay là kiểu hài tiết chế

  • Hồi đại học, giáo sư đã đưa cái này vào tài liệu in môn C, và tôi nhớ có lần đã tự tay gõ lại toàn bộ

  • Rosetta Code cũng có một bài tương tự
    Đó là chương trình in ra bài hát lặp dần Old Lady Swallowed a Fly: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly

    • Tôi thích bản Tcl vì nó đơn giản là lời bài hát đã được nén lại
      puts [zlib inflate [binary decode base64 "7VRNa8MwDL3nV2(...)"]]
      https://rosettacode.org/wiki/Old_lady_swallowed_a_fly#Tcl
      Có lẽ Python, Nim, Julia v.v. cũng có những phiên bản tương tự