1988 Uluslararası Gizlenmiş C Kodu Yarışması’nın Kazananı: Xmas.c

 (udel.edu)
3 puan yazan GN⁺ 2023-12-24 | 1 yorum | WhatsApp'ta paylaş
  • 1988 International Obfuscated C Code Contest kazananı xmas.c, rastgele yazılmış gibi görünen C koduyla The Twelve Days of Christmas şarkısının sözlerini çıktılar
  • Çıktıdan daha küçük bir kodun içine şifrelenmiş dizgeler yerleştirir; yerine koyma şifresi ve özyinelemeli çağrılarla sözcükleri ve ifadeleri çözer
  • Üçlü operatörleri if-then-else bloklarına açıp words ve shift için adlandırma yapınca, t değerinin özyineleme akışını değiştiren yapı ortaya çıkar
  • shift, baştaki karakterleri 31 konum sonraki karakterlerle eşler; words ise eğik çizgiyle (/) ayrılmış şifrelenmiş şarkı sözü parçalarını içerir
  • Basit bir şarkı sözü yazdırma programı olsa da, yerine koyma şifresi, çift yönlü özyineleme, gereksiz kodlar ve kullanılmayan argümanlar üst üste gelerek yaratıcı bir C gizleme örneği olarak kalmıştır

xmas.c’nin ürettiği çıktı

  • xmas.c, 1988 International Obfuscated C Code Contest’te kazanan C programıdır
  • Analizi yapan kişi bu programı ilk kez 2000 civarında gördükten sonra, Kasım 2008’de kodu parçalara ayırarak nasıl çalıştığını anlamıştır
  • Parametresiz derlenip çalıştırıldığında Noel ilahisi The Twelve Days of Christmas’ın 1. günden 12. güne kadar sözlerini yazdırır
  • Orijinal kod yorumlarında, programın çıktının “sıkıştırılmış” biçiminden bile küçük olduğu ve jüri üyelerinin bunun “eski bir daktiloya rastgele basılmasının sonucu” gibi göründüğünü düşündüğü yazıyordu

Okunabilir hale getirilen iç yapı

  • Analizin ilk adımı, tüm a ? b : c biçimlerini açık if-then-else bloklarına dönüştürmektir
  • Anlamı anlaşılması zor iki dizgeye rollerine uygun adlar verilmiştir
    • words: Noel ilahisi sözlerini oluşturmak için kullanılan şifrelenmiş sözcük ve ifade kümesi
    • shift: şifrelenmiş karakterleri gerçek çıktı karakterlerine dönüştüren yerine koyma dizgesi
  • main(), xmas(1, 0, '\0') ile başlar; ardından tek bir xmas() fonksiyonu tüm çıktıyı özyinelemeli olarak işler
  • t değişkeni, özyinelemenin yönünü ve dallanma davranışını kontrol eden temel değerdir

Yerine koyma şifresi ve şarkı sözü verisi

  • shift dizgesi, gerçekte iki dizgenin birbirine eklenmiş hali gibi çalışır
  • Ön yarıda bulunan karakter, 31 konum sonrasındaki karaktere çözülür
    • Örneğin dizgenin ilk karakteri !, 31 konum sonraki satır sonu karakteriyle eşleşir
  • t < -50 dalı, giriş karakteri _ shift içinde bulunana kadar a dizgesinde birer karakter ilerler
    • Eşleşen karakteri bulunca a[31] değerini yazdırır ve döner
  • words dizgesi, yerine koyma şifresiyle çözülen şifrelenmiş şarkı sözü verisidir
    • Sıra sayısı ifadeleri ve her kıtanın söz parçaları eğik çizgi (/) karakteriyle ayrılmıştır

Özyineleme dallarının üstlendiği roller

  • t < -72 dalı, ilk iki argümanı değiştirip üçüncü argüman olarak words vererek tekrar çağırır
    • Ana amacı kafa karıştırmaktır ve üçüncü argümanı yok sayan iç içe özyinelemeyi mümkün kılar
  • t < 0 dalı, dizge içinde |t|’inci eğik çizgiyi (/) bulur ve sonraki karakterden başlayan dizgeyi geçirir
  • t == 0 dalı, sonraki eğik çizgi gelene kadar dizgeyi çözüp yazdırır, ardından 1 döndürür
  • t == 1 dalı başlangıçta yalnızca bir kez çağrılır ve xmas(2, 2, "%s") ile asıl özyinelemeyi başlatır
  • t == 2 dalı, "On the [ordinal] day of Christmas my true love gave to me\n" biçimindeki ilk satırı yazdırır
  • Son iki koşul bloğu özyinelemeyi iki yönde sürdürür
    • Geçerli günden aşağı doğru inerek ilgili kıtanın sözlerini ters sırada yazdırır
      1. güne kadar günleri artırarak tüm kıtaları tekrarlar

Basitleştirildiğinde görünen yürütme akışı

  • Çalışma biçimi anlaşıldıktan sonra kod, döngüler ve C dizge kütüphanesi rutinleriyle daha basit hale getirilebilir
  • Basitleştirilmiş sürümde de temel veriler olan words ve shift aynen korunur
  • t < 0 dalı, index(a, '/') kullanarak eğik çizgi ayırıcısını bulur ve istenen şarkı sözü parçasının konumuna ilerler
  • t == 0 dalı, index(shift, *a++)[31] ile karakterleri çözüp yazdırır
  • t == 2 dalı, bir kıtanın başlangıcını şu sırayla yazdırır
    • "On the "
    • ilgili günün sıra sayısı
    • " my true love gave to me\n"

Gizlemenin ilginç olmasının nedeni

  • Bu program sonuna kadar basitleştirildiğinde, şarkı sözlerini yazdıran bir koda indirgenebilir
  • Orijinal sürüm, yerine koyma şifresi ile özyinelemeyi birlikte kullanarak basit çıktıdan çok daha karmaşık bir yapı kurar
  • Küçük gereksiz kod parçaları ve gerçekte kullanılmayan rastgele argümanlar eklenince kodu anlamak daha da zorlaşır
  • Anlamak ile doğrudan yazmak ayrı meselelerdir; xmas.c yaratıcı bir C kodu örneği olarak değerlendirilir

İlgili okumalar

1 yorum

 
GN⁺ 2023-12-24
Hacker News yorumları

  • TeX tarafında da benzer bir örnek olarak xii.tex var.
    Bu içeriği bir .tex dosyasına koyup pdftex çalıştırdıktan sonra çıkan PDF’ye bakınca şöyle görünüyor: https://shreevatsa.net/post/xii/

    • Gizlemeden çok özellikle bir mantıksal sıkıştırma biçimi gibi görünüyor.

  • İlk yayımlandığında indirmiştim; bu yazıdaki dosya adından farklı olarak bendeki dosya carol.c idi.
    Modern sistemlerde derleyip çalıştırmayı deneyince gcc -o carol carol.c komutunda return type defaults to ‘int’, type of ‘t’ defaults to ‘int’, type of ‘_’ defaults to ‘int’ gibi uyarılar çıktı.

    • GCC 14’ten itibaren örtük int artık kabul edilmeyecek: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • Sorun, main içinde xmas()’ın tanımlanmadan önce çağrılmasında.
      macOS’taki GCC ile derleyince ISO C99 and later do not support implicit function declarations hatası veriyor; main() aşağı taşınırsa düzgün derleniyor ve doğru çıktı üretiliyor.
    • Uyarıların beklenenden az olması ve hepsinin yalnızca aynı satırdan gelmesi şaşırtıcı.

  • Bunu görünce aklıma Kolmogorov karmaşıklığı geliyor.
    Buradaki program saçmalık gibi görünse de istenen çıktıyı ürettiği için, aynı çıktıyı veren daha kısa ve daha da anlamsız görünen bir program var mı diye merak ediyorum.
    Böyle bir program nasıl bulunabilir?

    • 12 Days of Christmas sözlerini yazdıran en kısa C programı için güncel rekor 431 bayt: https://code.golf/12-days-of-christmas#c
    • Daha kısa bir programın olma olasılığı genel olarak yüksek.
      Ancak kaba kuvvetle arama çok verimsiz olduğundan, pratik cevap matematiksel anlamda “akıllıca yap” demeye yakın.
      Genel olarak Kolmogorov karmaşıklığı hesaplanamaz; bu yüzden herhangi bir dizgeyi alıp o dizgeyi hesaplayan en kısa programı döndüren bir program yoktur.
      Yine de belirli bir dizgenin Kolmogorov karmaşıklığının X olduğunu birinin kanıtlaması ilke olarak mümkündür.
    • Çoğu durumda Kolmogorov karmaşıklığını doğrudan hesaplamak fiilen imkânsız; ancak herhangi bir sürümden ya da değerden daha yavaş olduğu türünden olasılık temelli karşılaştırmalar yapılabilir diye düşünüyorum.
      Bu yüzden uzun soluklu yarışmalara ve rekabete çok uygun; logaritmik büyüme eğrileri nedeniyle en uç noktalarda ilginç keşifler de çıkabiliyor.
      Şu anda gelecek yıl mart ayına kadar pi sayısının basamaklarını en çok ezberleyen LLM’i karşılaştıran mini bir yarışma düzenliyorum; mevcut ödül 100 dolar ve katkı oranına göre logaritmik uzayda dağıtmayı planlıyorum.
      Pi teorik olarak epey sıkıştırılabilir olduğundan, modelin veriden yüksek sıkıştırmalı algoritmayı yeniden oluşturan minimum açıklama uzunluğuna (MDL) yakın bir ağırlık kümesi öğrenip öğrenemeyeceğini görmek ilginç olabilir.
      Ancak hazır modellerle bunun mümkün olup olmadığı henüz net değil; bu yüzden şimdilik bunu bir sayı ezberleme yarışması olarak tutup izlemeyi düşünüyorum.

  • Açıklama iyi ve IOCCC 2023’te de yaşamaya devam ediyor gibi görünüyor: https://www.ioccc.org/years.html

    • O sayfaya bakınca son IOCCC 2020 olarak gösteriliyor.
      Ama ana sayfada Mayıs 2023 güncellemesiyle “28. IOCCC’yi düzenleme planı” olduğu yazıyor.
      Nethack sürümleri gibi beklemeye değer şeyler var.

  • Yakın zamanda The Twelve Days of Christmas hakkında ilginç bir şey öğrendim: bütün hediyeler bir tür kuşmuş.
    Sıçrayan hanımlar, lordlar bile hepsi öyleymiş.

  • 20 yıldan fazla önce bizzat araştırdığım şeyler de var: http://michaeldnahas.com/xmassong/index.html

  • Uyarıları kapatırsanız hâlâ trunk üzerinde de çalışıyor: https://compiler-explorer.com/z/hGvs1e9jo

  • Üniversitenin son iki döneminde, 2022’de, hocanın derse başlar başlamaz bu kod parçasını gösterdiği güzel anı aklıma geldi.

    • “Üniversitenin son iki dönemi, yani ta geçen yıl!” der gibi, o kadar eskiymiş de hatırası bulanıklaşmış şakası olarak da okunuyor.
      Ciddi mi, ölçülü bir komedi mi ayırt edemiyorum.

  • Üniversitede hocam C dili için basılı ders materyaline bunu koymuştu; bir keresinde elle baştan sona yazdığımı hatırlıyorum.

  • Rosetta Code’da da benzer bir görev var.
    Tekrarlayarak uzayan bir şarkı olan Old Lady Swallowed a Fly’ı yazdıran bir program: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly