1988年の国際難読化Cコードコンテスト優勝作、Xmas.c

 (udel.edu)
3 ポイント 投稿者 GN⁺ 2023-12-24 | 1件のコメント | WhatsAppで共有
  • 1988年のInternational Obfuscated C Code Contest優勝作 xmas.c は、ランダムにタイプしたように見えるCコードで The Twelve Days of Christmas の歌詞を出力する
  • 出力より小さなコードの中に暗号化された文字列を入れ、換字式暗号と再帰呼び出しで単語やフレーズを復号する
  • 三項演算子を if-then-else ブロックに展開し、words、shift に名前を付けると、t の値が再帰の流れを変える構造が見えてくる
  • shift は前方の文字と31文字後の文字を対応させ、words はスラッシュ（/）で区切られた暗号化された歌詞の断片を保持する
  • 単純な歌詞出力プログラムだが、換字式暗号・双方向再帰・不要なコード・使われない引数が重なり、創造的なC難読化の例として残っている

xmas.cが出力するもの

  • xmas.c は1988年のInternational Obfuscated C Code Contestで優勝したCプログラム
  • 分析者はこのプログラムを2000年ごろに初めて見た後、2008年11月にコードを分解して動作を把握した
  • 引数なしでコンパイルして実行すると、クリスマスキャロル The Twelve Days of Christmas の1日目から12日目までの歌詞を出力する
  • 元コードのコメントには、プログラムが出力の「圧縮された」形よりも小さく、審査員たちが「古いタイプライターをランダムに叩いた結果」のように見えると思った、という文が含まれている

読みやすく展開した内部構造

  • 分析の第一段階は、すべての a ? b : c 形式を明示的な if-then-else ブロックに置き換える作業
  • 意味を把握しにくい2つの文字列には、役割に合った名前を付ける
    • words: クリスマスキャロルの歌詞を作るための、暗号化された単語とフレーズの集合
    • shift: 暗号化された文字を実際に出力する文字へ変換するための換字用文字列
  • main() は xmas(1, 0, '\0') で始まり、その後は xmas() 関数1つが再帰的に全体の出力を処理する
  • 変数 t は、再帰の方向と分岐動作を制御する中心的な値

換字式暗号と歌詞データ

  • shift 文字列は、実際には2つの文字列を連結した形のように動作する
  • 前半で見つかった文字は、31文字後にある文字へ復号される
    • 例えば文字列の最初の文字 ! は、31文字後の改行文字に対応する
  • t < -50 分岐は、入力文字 _ が shift 内に現れるまで文字列 a を1文字ずつ移動する
    • 一致する文字を見つけると a[31] を出力して戻る
  • words 文字列は、換字式暗号で解かれる暗号化された歌詞データ
    • 序数表現と各節の歌詞断片は、スラッシュ（/）文字で区切られている

再帰分岐が担う役割

  • t < -72 分岐は、最初の2つの引数を入れ替え、3番目の引数として words を入れて再度呼び出す
    • 主な目的は混乱を招くことであり、3番目の引数を無視する入れ子の再帰を可能にする
  • t < 0 分岐は、文字列内で |t| 番目のスラッシュ（/）を探し、その次の文字から始まる文字列を渡す
  • t == 0 分岐は、次のスラッシュが現れるまで文字列を復号して出力した後、1 を返す
  • t == 1 分岐は開始時に一度だけ呼び出され、xmas(2, 2, "%s") で本格的な再帰を開始する
  • t == 2 分岐は "On the [ordinal] day of Christmas my true love gave to me\n" 形式の最初の行を出力する
  • 最後の2つの条件ブロックは、再帰を2方向に維持する
    • 現在の日付から下へ降りながら、該当する節の歌詞を逆順に出力する
    • 12日目まで日付を上げながら、節全体を繰り返す

単純化すると見える実行フロー

  • 動作を理解した後は、ループとC文字列ライブラリのルーチンで、より単純なコードに置き換えられる
  • 単純化版でも、中核データである words と shift はそのまま維持される
  • t < 0 分岐は index(a, '/') を使ってスラッシュ区切りを探し、目的の歌詞断片の位置へ移動する
  • t == 0 分岐は index(shift, *a++)[31] で文字を復号して出力する
  • t == 2 分岐は、1節の冒頭部分を次の順に出力する
    • "On the "
    • 該当する日の序数
    • " my true love gave to me\n"

難読化が興味深い理由

  • このプログラムは最後まで単純化すると、歌詞を出力するコードとして整理できる
  • 原本は換字式暗号と再帰を組み合わせ、単純な出力よりもはるかに複雑な構造を作っている
  • 小さな不要コードや、実際には使われない任意の引数が加わることで、コード理解はさらに難しくなる
  • 理解することと自分で書くことは別問題であり、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 からは暗黙の int はもう許可されない予定: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • 問題は main の中で xmas() を定義前に呼んでいることにある
      macOSのGCCでコンパイルすると ISO C99 and later do not support implicit function declarations というエラーが出るが、main() を下に移せば正しくコンパイルでき、期待どおりの出力になる
    • 警告が意外なほど少なく、しかも全部同じ行からしか出ていないのが驚き

  • これを見ると コルモゴロフ複雑性 を思い出す
    このプログラムは支離滅裂に見えるのに欲しい出力を生成しているので、同じ出力を出しつつもっと短く、もっと意味不明に見えるプログラムがあるのか気になる
    そういうプログラムはどうやって見つければいいのだろう？

    • 12 Days of Christmas の歌詞を出力する最短のCプログラムの現在の記録は431バイト: https://code.golf/12-days-of-christmas#c
    • もっと短いプログラムはたいてい存在する可能性が高い
      ただし総当たり探索は非常に非効率なので、現実的な答えは数学的な意味で「うまくやる」に近い
      一般にコルモゴロフ複雑性は計算不可能なので、ある文字列を受け取ってその文字列を計算する最短プログラムを返すプログラムは存在しない
      ただし、特定の文字列のコルモゴロフ複雑性がXであることを誰かが証明すること自体は原理的には可能
    • ほとんどの場合、コルモゴロフ複雑性を直接計算するのは事実上不可能で、ある版や値より遅い／小さいといった可能性の観点でしか比較できないと思う
      なので長期コンテストや競争と相性がよく、対数的な成長曲線のため終盤に面白い発見が出ることもある
      今は来年3月まで 円周率の桁 を最も多く暗記するLLMを競うミニコンテストを開いており、現在の賞金は100ドル、対数空間での寄与率に応じて分配する予定
      円周率は理論上かなり圧縮可能なので、モデルがデータから高圧縮アルゴリズムを復元する最小記述長（MDL）に近い重み集合を学習できるかを見るのは面白そう
      ただ、既存モデルで可能かどうかはまだはっきりしていないので、今のところは単なる数字暗記コンテストとして様子を見るつもり

  • 説明が良いし、IOCCC は2023年にもまだ続いているように見える: https://www.ioccc.org/years.html

    • そのページを見ると最後のIOCCCは2020年と表示されている
      ただしホームページには2023年5月の更新として「第28回IOCCCを開催する予定」と書かれている
      Nethackのリリースのように、待つ価値のあるものもある

  • 最近 The Twelve Days of Christmas について面白いことを知ったのだが、贈り物はすべて鳥の一種だという話だ
    跳ねる貴婦人たちや領主たちまで全部そうだという

  • 20年以上前に自分で調べた内容もある: http://michaeldnahas.com/xmassong/index.html

  • 警告を無効にすればまだ trunk でも動く: https://compiler-explorer.com/z/hGvs1e9jo

  • 大学最後の2学期だった2022年に、教授が講義の冒頭でこのコード片を見せてくれた良い思い出がよみがえる

    • 「大学最後の2学期って、つまり去年じゃないか！」という感じの、あまりに最近すぎて記憶が曖昧だという冗談のようにも読める
      本気なのか抑制の効いたコメディなのか判別がつかない

  • 大学時代、教授がC言語の印刷教材にこれを載せてくれて、一度は手で打ち込んだ記憶がある

  • Rosetta Codeにも似た課題がある
    繰り返しでどんどん長くなる歌 Old Lady Swallowed a Fly を出力するプログラムだ: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly