🗝️ 👌🏾 🌤️ Pengantar rekayasa terbalik: meretas format data game 🤸🏻 👨‍🏫 🤽🏾

Pendahuluan

Rekayasa terbalik dari file data yang tidak dikenal dapat digambarkan sebagai proses pemahaman bertahap. Dalam banyak hal, itu menyerupai metode ilmiah, hanya diterapkan pada benda-benda abstrak yang diciptakan oleh manusia, dan bukan pada dunia alami. Kami mulai dengan mengumpulkan data, dan kemudian menggunakan informasi ini untuk mengajukan satu atau lebih hipotesis. Kami menguji hipotesis dan menerapkan hasil tes ini untuk memperjelasnya. Jika perlu, ulangi prosesnya.

Mengembangkan keterampilan rekayasa terbalik pada dasarnya adalah masalah praktik. Dengan mendapatkan pengalaman, Anda membangun pemahaman intuitif tentang apa yang perlu Anda jelajahi terlebih dahulu, pola apa yang perlu Anda cari, dan alat mana yang lebih nyaman digunakan.

Pada artikel ini, saya akan berbicara secara rinci tentang proses file data rekayasa balik dari sebuah game komputer lama untuk menunjukkan bagaimana hal ini dilakukan.

Sedikit latar belakang

Semuanya berawal ketika saya mencoba menciptakan kembali Tantangan Chip di Linux.

Tantangan Chip awalnya dirilis pada tahun 1989 untuk konsol portabel Atari Lynx yang sekarang terlupakan. Untuk saat itu, Atari Lynx adalah mobil yang mengesankan, tetapi keluar bersamaan dengan Nintendo Game Boy, yang akhirnya merebut pasar.

Chip's Challenge adalah game puzzle dengan tampilan atas dan peta ubin. Seperti kebanyakan gim semacam itu, tujuan setiap level adalah mencapai pintu keluar. Di sebagian besar level, output dilindungi oleh konektor untuk chip, yang dapat dilewati hanya dengan mengumpulkan sejumlah chip komputer.

Video: Atari Lynx beraksi , penelusuran tingkat satu .

Gim baru dimulai dari tingkat pertama dengan nama "PELAJARAN 1". Selain chip dan slot untuk chip, kunci dan pintu muncul di sana. Di tingkat lain, hambatan seperti perangkap, bom, air dan makhluk muncul yang (paling sering) bergerak di sepanjang rute yang dapat diprediksi. Berbagai objek dan perangkat memungkinkan Anda membuat banyak teka-teki dan batas waktu. Untuk menyelesaikan permainan, Anda harus melewati lebih dari 140 level.

Meskipun Lynx akhirnya gagal, Tantangan Chip terbukti cukup populer dan porting ke banyak platform lain, akhirnya muncul di Microsoft Windows, di mana ia menjadi luas. Sekitar permainan, basis kecil tapi berdedikasi penggemar terbentuk, dan seiring waktu, editor level ditulis yang memungkinkan pemain untuk membuat level yang tak terhitung jumlahnya.

Dan di sinilah kisah saya dimulai. Saya memutuskan bahwa saya ingin membuat versi mesin game open source dasar sehingga saya bisa memainkan Chip's Challenge di Linux dan Windows, dan membuatnya lebih mudah untuk menjalankan semua level yang dibuat oleh penggemar.

Keberadaan editor level ternyata menjadi keajaiban bagi saya, karena saya bisa menjelajahi fitur tersembunyi dari logika game, membuat level saya sendiri dan melakukan tes. Sayangnya, tidak ada editor level untuk gim Lynx asli, hanya muncul di port yang lebih terkenal di Windows.

Port Windows tidak dibuat oleh pengembang asli, sehingga banyak perubahan pada logika game muncul di dalamnya (dan tidak semua dari mereka disengaja). Ketika saya mulai menulis mesin saya, saya ingin membuat ulang logika game asli di Lynx, dan versi yang lebih terkenal untuk Windows. Tetapi kurangnya editor level di Lynx secara serius membatasi kemampuan saya untuk mempelajari game asli secara detail. Port Windows memiliki keuntungan: level disimpan dalam file data terpisah, yang menyederhanakan deteksi dan rekayasa balik. Gim untuk Lynx didistribusikan pada kartrid ROM yang berisi gambar sprite, efek suara, dan kode mesin, serta data level yang dieksekusi bersama-sama. Tidak ada petunjuk tentang di mana data berada dalam dump ROM 128-kilobyte ini, atau bagaimana tampilannya, dan tanpa sepengetahuan ini saya tidak dapat membuat editor level untuk versi Lynx.

Suatu kali, dalam proses penelitian yang santai, saya menemukan salinan port Tantangan Chip di bawah MS-DOS. Seperti sebagian besar port awal game, logikanya lebih dekat ke aslinya daripada di versi Windows. Ketika saya melihat data program untuk mengetahui bagaimana itu disimpan, saya terkejut menemukan bahwa data level dialokasikan dalam direktori yang terpisah, dan setiap level disimpan dalam file sendiri. Setelah dengan mudah memisahkan data level, saya menyarankan agar tidak terlalu sulit untuk merekayasa balik file data level. Dan ini akan memungkinkan Anda untuk menulis editor level untuk versi gim di bawah MS-DOS. Saya memutuskan bahwa ini adalah kesempatan yang menarik.

Tetapi kemudian anggota lain dari komunitas Chip's Challenge memperingatkan saya tentang fakta yang menarik. Isi file level untuk MS-DOS ternyata merupakan byte byte ROM Lynx. Ini berarti bahwa jika saya dapat mendekode file MS-DOS, maka saya kemudian dapat menggunakan pengetahuan ini untuk membaca dan mengubah level di dalam dump ROM Lynx. Kemudian Anda bisa membuat editor level langsung untuk gim asli di Lynx.

Tiba-tiba, prioritas utama saya adalah membalikkan level level engineering untuk MS-DOS.

File data

Berikut ini tautan ke direktori tarball yang berisi semua file data. Saya memberikannya jika Anda ingin mengulangi setelah saya semua langkah yang dijelaskan dalam artikel ini, atau mencoba untuk memecahkan kode file data sendiri.

Apakah ini legal? Pertanyaan yang bagus Karena file-file ini hanya sebagian kecil dari program untuk MS-DOS, dan dengan sendirinya mereka tidak berguna, dan karena saya mempostingnya untuk tujuan pendidikan saja, saya percaya bahwa ini termasuk dalam persyaratan penggunaan yang adil. Saya harap semua pihak yang berkepentingan setuju dengan saya. (Jika saya tetap menerima surat ancaman dari pengacara, saya dapat mengubah artikel sehingga menyajikan file data dengan cara yang lucu, dan kemudian menyatakan bahwa itu adalah parodi.)

Prasyarat

Saya akan berasumsi bahwa Anda tahu kalkulus heksadesimal, bahkan jika Anda tidak tahu decoding dari nilai heksadesimal, dan juga bahwa Anda sedikit akrab dengan shell Unix. Sesi shell yang ditunjukkan dalam artikel ini berjalan pada sistem Linux standar, tetapi perintah yang hampir sering digunakan adalah utilitas Unix yang umum, dan didistribusikan secara luas pada sistem mirip Unix lainnya.

Penampilan pertama

Berikut adalah daftar direktori yang berisi file data dari port di bawah MS-DOS:

  tingkat $ ls
 all_full.pak cake_wal.pak eeny_min.pak iceberg.pak lesson_5.pak mulligan.pak playtime.pak southpol.pak totally_.pak
 alphabet.pak castle_m.pak elementa.pak ice_cube.pak lesson_6.pak nice_day.pak potpourr.pak special.pak traffic_.pak
 amsterda.pak catacomb.pak fireflie.pak icedeath.pak lesson_7.pak nightmar.pak masalah.pak spirals.pak trinity.pak
 apartmen.pak cellbloc.pak firetrap.pak icehouse.pak lesson_8.pak now_you_.pak refracti.pak spooks.pak trust_me.pak
 arcticfl.pak chchchip.pak floorgas.pak invincib.pak lobster_.pak nuts_and.pak reverse_.pak steam.pakalami.pak
 balls_o_.pak chiller.pak forced_e.pak i.pak lock_blo.pak on_the_r.pak rink.pak stripes.pak up_the_b.pak
 beware_o.pak chipmine.pak force_fi.pak i_slide.pak loop_aro.pak oorto_ge.pak roadsign.pak suicide.pak vanishin.pak
 blink.pak citybloc.pak force_sq.pak jailer.pak memory.pak open_que.pak sampler.pak telebloc.pak korban.pak
 blobdanc.pak colony.pak fortune_.pak jumping_.pak metastab.pak oversea_.pak mencari-cari.pak telenet.pak vortex.pak
 blobnet.pak corridor.pak four_ple.pak kablam.pak mind_blo.pak pain.pak scoundre.pak t_fair.pak wars.pak
 block_fa.pak cypher.pak four_squ.pak knot.pak mishmesh.pak paranoia.pak seeing_s.pak the_last.pak penulis_.pak
 block_ii.pak deceptio.pak glut.pak ladder.pak miss_dir.pak partial_.pak short_ci.pak the_mars.pak yorkhous.pak
 block_n_.pak deepfree.pak goldkey.pak lemmings.pak mixed_nu.pak pentagra.pak shrinkin.pak the_pris.pak
 block_ou.pak digdirt.pak go_with_.pak lesson_1.pak mix_up.pak perfect_.pak skelzie.pak three_do.pak
 block.pak digger.pak grail.pak lesson_2.pak monster_.pak pier_sev.pak slide_st.pak time_lap.pak
 bounce_c.pak doublema.pak hidden_d.pak lesson_3.pak morton.pak ping_pon.pak slo_mo.pak torturec.pak
 brushfir.pakrawn_an.pak hunt.pak lesson_4.pak mugger_s.pak playhous.pak socialis.pak tossed_s.pak

Seperti yang Anda lihat, semua file diakhiri dengan .pak . .pak adalah izin standar untuk file data aplikasi, dan ini, sayangnya, tidak memberi kami informasi apa pun tentang struktur internalnya. Nama file adalah delapan karakter pertama dari nama level, dengan beberapa pengecualian. (Misalnya, dalam nama file level "BLOCK BUSTER" dan "BLOCK BUSTER II" kata "buster" dihilangkan sehingga tidak cocok.)

  Tingkat $ ls |  wc
      17 148 1974

Ada 148 file data dalam direktori, dan game ini sebenarnya memiliki 148 level, jadi semuanya sama di sini.

Sekarang mari kita periksa apa file-file ini. xxd adalah utilitas standar untuk membuang data heksadesimal (hexdump). Mari kita lihat seperti apa di dalam PELAJARAN 1.

  $ xxd level / lesson_1.pak
 00000000: 1100 cb00 0200 0004 0202 0504 0407 0505 ................
 00000010: 0807 0709 0001 0a01 010b 0808 0d0a 0a11 ................
 00000020: 0023 1509 0718 0200 2209 0d26 0911 270b. # ...... ".. & .. '.
 00000030: 0b28 0705 291e 0127 2705 020d 0122 0704. (..) ..''.... "..
 00000040: 0902 090a 0215 0426 0925 0111 1502 221d ....... &.% .... ".
 00000050: 0124 011d 0d01 0709 0020 001b 0400 1a00. $ ....... ......
 00000060: 2015 2609 1f00 3300 2911 1522 2302 110d. & ... 3.) .. "# ...
 00000070: 0107 2609 1f18 2911 1509 181a 0223 021b .. & ...) ...... # ..
 00000080: 0215 2201 1c01 1c0d 0a07 0409 0201 0201 .. ".............
 00000090: 2826 0123 1505 0902 0121 1505 220a 2727 (&. # .....! .. ". ''
 000000a0: 0b05 0400 060b 0828 0418 780b 0828 0418 ....... (.. x .. (..
 000000b0: 700b 0828 0418 6400 1710 1e1e 1a19 0103 p .. (.. d .........
 000000c0: 000e 1a17 1710 0e1f 010e 1314 1b29 1f1a .............) ..
 000000d0: 0012 101f 011b 0c1e 1f01 1f13 1001 0e13 ................
 000000e0: 141b 001e 1a0e 1610 1f2d 0020 1e10 0116 .........-.  ....
 000000f0: 1024 291f 1a01 1a1b 1019 000f 1a1a 1d1e. $) .............
 00000100: 2d02

Apa itu utilitas hexdump? Dump heksadesimal adalah cara standar untuk menampilkan byte yang tepat dari file biner. Sebagian besar nilai byte tidak dapat dikaitkan dengan karakter ASCII yang dapat dicetak, atau mereka memiliki penampilan yang tidak dapat dipahami (seperti karakter tab). Dalam dump heksadesimal, byte individu adalah output sebagai nilai numerik. Nilai ditampilkan dalam heksadesimal, karenanya namanya. Dalam contoh di atas, 16 byte ditampilkan pada satu baris output. Kolom paling kiri menunjukkan posisi baris dalam file, juga dalam heksadesimal, sehingga jumlah di setiap baris meningkat sebesar 16. Bytes ditampilkan dalam delapan kolom, dan dua byte ditampilkan di setiap kolom. Hexdump di sebelah kanan menunjukkan bagaimana byte akan terlihat ketika ditampilkan oleh karakter, hanya semua nilai ASCII yang tidak dapat dicetak diganti oleh titik. Ini membuatnya mudah untuk menemukan string yang dapat disematkan dalam file biner.

Jelas, rekayasa balik dari file-file ini tidak akan mendidih menjadi hanya browsing konten dan menjelajahi apa yang terlihat di sana. Sejauh ini, tidak ada yang memberi tahu kami apa fungsi data melakukan.

Apa yang kita harapkan untuk dilihat?

Mari kita mundur selangkah dan memperjelas situasinya: data spesifik apa yang kita harapkan akan ditemukan dalam file data ini?

Yang paling jelas adalah "peta" tingkat tertentu: data yang menunjukkan posisi dinding dan pintu, serta segala sesuatu yang lain, yang membuat tingkat tersebut unik.

(Untungnya bagi kami, penggemar game melakukan pekerjaan yang melelahkan dan mengumpulkan peta lengkap untuk semua 148 level, sehingga kami dapat menggunakannya untuk mengetahui apa yang seharusnya ada di setiap peta.)

Selain peta, setiap level harus memiliki beberapa atribut lainnya. Misalnya, Anda mungkin memperhatikan bahwa setiap level memiliki nama, misalnya, "PELAJARAN 1", "PERTANDINGAN SEMPURNA", "DRAWN DAN PERIODE KUARTALAN", dan sebagainya. Level yang berbeda juga memiliki batas waktu yang berbeda, sehingga kita dapat mengasumsikan bahwa informasi ini juga terkandung dalam data. Selain itu, setiap level memiliki jumlah chip rakitan sendiri. (Kita dapat mengasumsikan bahwa jumlah ini hanya sesuai dengan jumlah chip pada level, tetapi ternyata pada beberapa level ada lebih banyak chip daripada yang diperlukan untuk membuka slot chip. Setidaknya untuk level ini, jumlah minimum harus ditunjukkan dalam bentuk eksplisit.)

Sepotong data lain yang kami harapkan akan ditemukan dalam data level adalah teks petunjuk. Di beberapa tingkat ada "tombol petunjuk" - tanda tanya besar tergeletak di tanah. Ketika Chip bangun di atasnya, teks tooltip ditampilkan. Tombol petunjuk ada di sekitar 20 level.

Akhirnya, setiap level memiliki kata sandi - urutan empat huruf yang memungkinkan pemain untuk melanjutkan permainan dari level ini. (Kata sandi ini diperlukan karena Lynx tidak memiliki penyimpanan data. Tidak mungkin menyimpan game di konsol, sehingga Anda dapat terus memainkan game setelah menyalakan konsol menggunakan kata sandi.)

Jadi di sini adalah daftar data relevan kami:

Tingkat peta
Nama tingkat
Tingkat kata sandi
Batas waktu
Jumlah chip
Teks tooltip

Mari secara kasar memperkirakan ukuran total data. Cara termudah untuk menentukan batas waktu dan jumlah chip. Kedua parameter ini dapat memiliki nilai dalam rentang dari 0 hingga 999, sehingga kemungkinan besar disimpan sebagai nilai integer dengan ukuran total 4 byte. Kata sandi selalu terdiri dari empat huruf, sehingga kemungkinan besar disimpan sebagai empat byte lagi, yaitu hanya 8 byte. Panjang nama level bervariasi dari empat hingga sembilan belas karakter. Jika kita berasumsi bahwa kita memerlukan byte lain untuk menyelesaikan baris, maka ini adalah dua puluh byte, yaitu, subtotalnya adalah 28 byte. Teks tooltip terpanjang berukuran lebih dari 80 byte; jika kami membulatkan nilai ini menjadi 90, kami akan mendapatkan total 118 byte.

Bagaimana dengan skema level? Sebagian besar level memiliki ukuran 32 × 32 ubin. Level yang lebih besar tidak ada. Beberapa level lebih rendah, tetapi akan logis untuk mengasumsikan bahwa mereka hanya tertanam dalam kartu 32 × 32. Jika kita mengasumsikan bahwa satu byte diperlukan untuk satu ubin, maka diperlukan 1024 byte untuk rangkaian lengkap. Artinya, secara umum, kami mendapatkan perkiraan kasar 1142 byte per level. Tentu saja, ini hanya perkiraan awal yang kasar. Ada kemungkinan bahwa beberapa elemen ini disimpan secara berbeda, atau sama sekali tidak disimpan di dalam file level. Atau mungkin berisi data lain yang tidak kami perhatikan atau tidak ketahui tentang mereka. Namun sejauh ini kami telah meletakkan dasar yang baik.

Setelah memutuskan apa yang ingin kita lihat dalam file data, mari kita kembali mempelajari apa yang sebenarnya terkandung di dalamnya.

Apa yang ada dan apa yang tidak

Meskipun sekilas file data terlihat sangat tidak bisa dipahami, Anda masih bisa melihat beberapa poin di dalamnya. Pertama, ini yang tidak kita lihat. Sebagai contoh, kita tidak melihat nama level atau teks dari tips. Anda dapat memahami bahwa ini bukan kebetulan, setelah mempelajari file lain:

  $ strings levels / * |  kurang
 : !!; #
 &> '' :: 4 #
 . ,,!
 -54 ";
 / & 67
 !) 60
 <171
 * (0 *
 82> '= /
 8> <171 &&
 9> # 2 ') (
 ,) 9
  0hX
 `@PX
 ) "" *
 24 ** 5
 ;)) <
 B777: .. 22C1
 E ,, F
 -DI
 EGFF16G ;; H <
 IECJ
 9K444
 = MBBB >> N9 "O" 9P3? Q
 baris 1-24 / 1544 (selengkapnya)

Tidak ada yang terlihat di sini kecuali fragmen sewenang-wenang dari sampah ASCII.

Agaknya, di suatu tempat di file-file ini ada nama level dan petunjuk, tetapi mereka tidak disimpan di ASCII, atau telah mengalami beberapa transformasi (misalnya, karena kompresi).

Ini juga perlu diperhatikan sebagai berikut: ukuran file hampir mencapai 256 byte. Ini cukup kecil, mengingat pada awalnya kami memperkirakan ukurannya lebih dari 1140 byte.

Opsi -S mengurutkan file dalam urutan ukuran yang menurun.

  $ ls -lS level |  kepala
 total 592
 -rw-r - r-- 1 kotak roti kotak roti 680 23 Juni 2015 mulligan.pak
 -rw-r - r-- 1 kotak roti kotak roti 675 Jun 23 2015 shrinkin.pak
 -rw-r - r-- 1 kotak roti kotak roti 671 23 Juni 2015 balls_o_.pak
 -rw-r - r-- 1 kotak roti kotak roti 648 23 Juni 2015 cake_wal.pak
 -rw-r - r-- 1 kotak roti kotak roti 647 Jun 23 2015 citybloc.pak
 -rw-r - r-- 1 kotak roti kotak roti 639 23 Juni 2015 four_ple.pak
 -rw-r - r-- 1 kotak roti kotak roti 636 Jun 23 2015 trust_me.pak
 -rw-r - r-- 1 kotak roti kotak roti 625 Jun 23 2015 block_n_.pak
 -rw-r - r-- 1 kotak roti kotak roti 622 Jun 23 2015 mix_up.pak

File terbesar hanya membutuhkan 680 byte, dan ini tidak terlalu banyak. Dan apa yang akan menjadi yang terkecil?

Opsi -r memberi tahu ls untuk membalik urutan.

  $ ls -lSr level |  kepala
 total 592
 -rw-r - r-- 1 breadbox breadbox 206 Jun 23 2015 kablam.pak
 -rw-r - r-- 1 kotak roti kotak roti 214 Juni 23 2015 fortune_.pak
 -rw-r - r-- 1 breadbox breadbox 219 Jun 23 2015 digdirt.pak
 -rw-r - r-- 1 kotak roti kotak roti 226 Juni 23 2015 lesson_2.pak
 -rw-r - r-- 1 kotak roti kotak roti 229 Juni 23 2015 lesson_8.pak
 -rw-r - r-- 1 kotak roti kotak roti 237 Jun 23 2015 partial_.pak
 -rw-r - r-- 1 kotak roti kotak roti 239 Jun 23 2015 knot.pak
 -rw-r - r-- 1 kotak roti kotak roti 247 Jun 23 2015 cellbloc.pak
 -rw-r - r-- 1 kotak roti kotak roti 248 Jun 23 2015 torturec.pak

File terkecil hanya membutuhkan 206 byte, yang lebih dari tiga kali lebih kecil dari yang terbesar. Ini adalah kisaran yang cukup luas, dengan mempertimbangkan fakta bahwa kami mengharapkan ukuran level yang kira-kira sama.

Dalam penilaian awal kami, kami mengasumsikan bahwa kartu akan membutuhkan satu byte per ubin, dan hanya 1024 byte. Jika kita memotong estimasi ini menjadi setengahnya, yaitu, setiap ubin hanya akan membutuhkan 4 bit (atau dua ubin per byte), maka kartu akan tetap menempati 512 byte. 512 lebih kecil dari 680, tetapi masih lebih besar dari kebanyakan level. Dan dalam hal apa pun - 4 bit hanya akan memberikan 16 nilai yang berbeda, dan dalam permainan ada banyak objek yang jauh lebih berbeda.

Artinya, jelas bahwa kartu tidak disimpan dalam file-file ini dalam bentuk terbuka. Mereka menggunakan pengkodean yang lebih kompleks, memberikan deskripsi yang lebih efisien, dan / atau mereka terkompresi. Misalnya, pada level "PELAJARAN 1", kita dapat melihat bagaimana entri yang hilang untuk ubin "kosong" akan secara signifikan mengurangi ukuran keseluruhan data peta.

Kita dapat melihat peta file terbesar:

Level 57 Peta: STRANGE MAZE

Kartu Level 98: SHRINKING

dan kemudian membandingkannya dengan peta file terkecil:

Kartu Level 106: KABLAM

Level 112 Card: SELAMAT MENDAPATKAN THE

Perbandingan ini mendukung gagasan kami bahwa file data kecil sesuai dengan tingkat yang lebih sederhana, atau mengandung lebih banyak redundansi. Misalnya, jika data dikompresi oleh beberapa jenis pengkodean run-length, ini dapat dengan mudah menjelaskan interval ukuran file yang berbeda.

Jika file benar-benar dienkripsi, maka kemungkinan besar kita harus mendekripsi kompresi sebelum melanjutkan untuk mendekripsi data kartu.

Kami mempelajari beberapa file secara bersamaan

Studi singkat kami tentang file data pertama memungkinkan kami untuk membuat beberapa asumsi, tetapi tidak menemukan apa pun yang konkret. Sebagai langkah selanjutnya, kita akan mulai mengeksplorasi pola beberapa file data. Untuk saat ini, kami mengasumsikan bahwa semua 148 file menggunakan skema pemesanan yang sama untuk menyandikan data, jadi mencari pola duplikat dalam file-file ini akan membantu kami memulai.

Mari kita mulai dari awal ubin. Bagian atas file kemungkinan besar digunakan untuk menyimpan "metadata" yang memberi tahu kita tentang isi file. Dengan hanya melihat baris pertama dari dump heksadesimal, kita dapat melakukan perbandingan sederhana dan cepat dari 16 byte pertama dan mencari pola yang menonjol di dalamnya:

  $ untuk f di level / *;  lakukan xxd $ f |  sed -n 1p;  selesai |  kurang
 00000000: 2300 dc01 0300 0004 0101 0a03 030b 2323 # ............. ##
 00000000: 2d00 bf01 0300 0015 0101 2203 0329 2222 -... "..)"
 00000000: 2b00 a101 0301 0105 0000 0601 0207 0505 + ...............
 00000000: 1d00 d300 0200 0003 0101 0402 0205 0102 ................
 00000000: 2d00 7a01 0300 0006 1414 0701 0109 0303 -.z .............
 00000000: 3100 0802 0200 0003 0101 0502 0206 1313 1 ...............
 00000000: 1a00 b700 0200 0003 0100 0502 0206 0101 ................
 00000000: 1a00 0601 0300 0005 0001 0601 0107 0303 ................
 00000000: 2000 7a01 0200 0003 0202 0401 0105 0028 .z ............ (
 00000000: 3a00 a400 0200 0003 2828 0428 0205 0303: ....... ((.... (....
 00000000: 2600 da00 0300 0004 0507 0901 010a 0303 & ...............
 00000000: 2400 f000 0300 0004 0303 0504 0407 0101 $ ...............
 00000000: 2a00 ef01 0300 0005 0101 0614 0007 0303 * ...............
 00000000: 2c00 8c01 0300 0004 0303 0500 0107 0101, ...............
 00000000: 2a00 0001 0300 0004 0303 0501 0107 0404 * ...............
 00000000: 1b00 6d01 0200 0003 0101 0502 0206 0003 ..m .............
 00000000: 1e00 1701 0200 0003 0202 0401 0105 0013 ................
 00000000: 3200 ee01 0f00 0015 0101 270f 0f29 1414 2 ......... '..) ..
 00000000: 2a00 5b01 0300 0005 0303 0601 0107 1414 *. [.............
 00000000: 2c00 8a01 0200 0003 0202 0401 0105 0303, ...............
 00000000: 1d00 9c00 0216 1604 0000 0516 0107 0205 ................
 00000000: 2000 e100 0200 0003 0101 0402 0205 0303 ...............
 00000000: 2000 2601 0300 0004 0303 0502 0207 0101. & .............
 00000000: 1f00 f600 0132 0403 0000 0532 3206 0404 ..... 2 ..... 22 ...
 baris 1-24 / 148 (selengkapnya)

Melihat dump ini, Anda dapat melihat bahwa di setiap kolom ada beberapa nilai yang sama.

Dimulai dengan byte pertama, kami segera menyadari bahwa nilainya berada dalam kisaran nilai yang sangat terbatas, dalam kisaran heksadesimal 40 (atau sekitar 20–60 dalam desimal). Ini adalah fitur yang cukup spesifik.

Yang lebih menarik adalah byte kedua dari setiap file selalu nol, tanpa pengecualian. Byte kedua mungkin tidak digunakan, atau merupakan placeholder. Namun, ada kemungkinan lain - dua byte pertama ini bersama-sama mewakili nilai 16-bit yang disimpan dalam urutan little-endian.

Apa itu little-endian? Saat menyimpan nilai numerik yang lebih dari satu byte, Anda harus terlebih dahulu memilih urutan penyimpanan byte. Jika Anda pertama kali menyimpan byte yang mewakili bagian yang lebih kecil dari angka tersebut, maka ini disebut direct-order ( little-endian ); jika Anda pertama kali menyimpan byte yang menunjukkan sebagian besar angka, maka ini adalah urutan terbalik ( big-endian ). Sebagai contoh, kita menulis nilai desimal dalam urutan terbalik (big-endian): baris "42" berarti "empat puluh dua," bukan "empat dan dua puluh." Little-endian adalah tatanan alami bagi banyak keluarga mikroprosesor, sehingga biasanya lebih populer, dengan pengecualian protokol jaringan, yang biasanya memerlukan big-endian.

Jika kita melanjutkan analisis, kita akan segera melihat bahwa byte ketiga dalam file tidak sama dengan dua sebelumnya: nilainya bervariasi pada rentang yang luas. Namun, byte keempat selalu 00 , 01 atau 02 , dan 01 paling umum. Ini juga mengisyaratkan kepada kita bahwa dua byte ini merupakan nilai 16-bit lain, yang kira-kira berada dalam kisaran nilai desimal 0-700. Hipotesis ini juga dapat dikonfirmasikan oleh fakta bahwa nilai byte ketiga biasanya rendah jika nilai byte keempat adalah 02 , dan biasanya besar jika byte keempat adalah 00 .

By the way, perlu dicatat bahwa ini adalah sebagian alasan bahwa format dump heksadesimal menampilkan byte secara berpasangan secara default - ini membuatnya lebih mudah untuk membaca urutan angka integer 16-bit. Format hex dump distandarisasi ketika komputer 16-bit digunakan. Coba ganti xxd dengan xxd -g1 untuk sepenuhnya menonaktifkan pengelompokan, dan Anda akan melihat bahwa mengenali pasangan byte di tengah-tengah baris adalah banyak pekerjaan. Ini adalah contoh sederhana tentang bagaimana alat yang digunakan untuk mempelajari data yang tidak dikenal cenderung membuat kita memperhatikan jenis pola tertentu. Adalah baik bahwa xxd menyoroti pola ini secara default karena sangat umum (bahkan hari ini, ketika komputer 64-bit digunakan di mana-mana). Namun bermanfaat untuk mengetahui cara mengubah parameter ini jika tidak membantu.

Mari kita lanjutkan eksplorasi visual, dan lihat apakah pola ini dipertahankan dari nilai integer 16-bit. Byte kelima biasanya memiliki nilai yang sangat rendah: 02 dan 03 paling sering dijumpai, dan nilai maksimumnya adalah 05 . Byte keenam file sangat sering sama dengan nol - tetapi kadang-kadang berisi nilai yang jauh lebih besar, misalnya 32 atau 2C . Dalam pasangan ini, asumsi kami tentang nilai yang didistribusikan dalam interval tidak dikonfirmasi secara khusus.

Kami dengan cermat mempelajari nilai awal

Kita bisa menguji tebakan kita dengan menggunakan od untuk menghasilkan hex dump. Utilitas od mirip dengan xxd , tetapi menyediakan pilihan format output yang jauh lebih besar. Kita dapat menggunakannya untuk membuang output sebagai bilangan bulat desimal 16-bit:

Opsi -t untuk utilitas od menentukan format output. Dalam hal ini, u berarti angka desimal yang tidak ditandai, dan 2 berarti dua byte per rekaman. (Anda juga dapat menentukan format ini menggunakan opsi -d .)

  $ untuk f di level / *;  lakukan od -tu2 $ f |  sed -n 1p;  selesai |  kurang
 0000000 35 476 3 1024 257 778 2819 8995
 0000000 45 447 3 5376 257 802 10499 8738
 0000000 43 417 259 1281 0 262 1794 1285
 0000000 29 211 2 768 257 516 1282 513
 0000000 45 378 3 1536 5140 263 2305 771
 0000000 49 520 2 768 257 517 1538 4883
 0000000 26 183 2 768 1 517 1538 257
 0000000 26 262 3 1280 256 262 1793 771
 0000000 32 378 2 768 514 260 1281 10240
 0000000 58 164 2 768 10280 10244 1282 771
 0000000 38 218 3 1024 1797 265 2561 771
 0000000 36 240 3 1024 771 1029 1796 257
 0000000 42 495 3 1280 257 5126 1792 771
 0000000 44 396 3 1024 771 5 1793 257
 0000000 42 256 3 1024 771 261 1793 1028
 0000000 27 365 2 768 257 517 1538 768
 0000000 30 279 2 768 514 260 1281 4864
 0000000 50 494 15 5376 257 3879 10511 5140
 0000000 42 347 3 1280 771 262 1793 5140
 0000000 44 394 2 768 514 260 1281 771
 0000000 29 156 5634 1046 0 5637 1793 1282
 0000000 32 225 2 768 257 516 1282 771
 0000000 32 294 3 1024 771 517 1794 257
 0000000 31 246 12801 772 0 12805 1586 1028
 baris 1-24 / 148 (selengkapnya)

Output ini menunjukkan bahwa dugaan kami tentang beberapa byte pertama benar. Kita melihat bahwa nilai 16-bit pertama berada dalam kisaran desimal 20-70, dan nilai 16-bit kedua berada dalam kisaran desimal 100-600. Namun, nilai-nilai selanjutnya tidak berperilaku baik. Pola tertentu muncul di dalamnya (misalnya, di posisi keempat, mengejutkan sering 1024), tetapi mereka tidak memiliki keterulangan yang melekat pada nilai pertama file.

Oleh karena itu, mari kita asumsikan bahwa empat byte pertama dari file tersebut spesial dan terdiri dari dua nilai 16-bit. Karena mereka berada di bagian paling awal file, mereka kemungkinan besar adalah metadata dan membantu menentukan cara membaca sisa file.

Bahkan, interval nilai kedua (100-600) cukup dekat dengan interval ukuran file yang kita perhatikan sebelumnya (208-680). Mungkin ini bukan kebetulan? Mari kita mengajukan hipotesis: nilai 16-bit yang disimpan dalam byte ketiga dan keempat file berkorelasi dengan ukuran file total. Sekarang kita memiliki hipotesis, kita dapat mengujinya. Mari kita lihat apakah file besar di tempat ini benar-benar memiliki nilai besar setiap saat, dan file kecil memiliki nilai kecil.

Untuk menampilkan ukuran file dalam byte tanpa informasi lain, Anda dapat menggunakan wc dengan opsi -c . Demikian pula, Anda dapat menambahkan opsi ke od yang memungkinkan Anda untuk hanya menampilkan nilai yang menarik bagi kami. Kemudian kita bisa menggunakan substitusi perintah untuk menulis nilai-nilai ini ke variabel shell dan menampilkannya bersama-sama:

Opsi -An dari utilitas od menonaktifkan kolom paling kiri, yang menampilkan offset dalam file, dan -N4 memberitahu od berhenti setelah 4 byte pertama file.

  $ untuk f di level / *;  do size = $ (wc -c <$ f);  data = $ (od -tuS -An -N4 $ f);  gema "$ size: $ data";  selesai |  kurang
 585: 35 476
 586: 45 447
 550: 43,417
 302: 29.211
 517: 45 378
 671: 49 520
 265: 26 183
 344: 26.262
 478: 32.378
 342: 58 164
 336: 38 218
 352: 36.240
 625: 42 495
 532: 44.396
 386: 42.256
 450: 27 365
 373: 30 279
 648: 50 494
 477: 42 347
 530: 44.394
 247: 29 156
 325: 32.225
 394: 32.294
 343: 31.246

Melihat output ini, Anda dapat melihat bahwa nilainya hampir berkorelasi. File yang lebih kecil biasanya memiliki nilai lebih rendah di posisi kedua, dan file besar memiliki nilai lebih besar. Namun, korelasinya tidak akurat, dan perlu dicatat bahwa ukuran file selalu jauh lebih besar daripada nilai yang tersimpan di dalamnya.

Selain itu, nilai 16-bit pertama juga biasanya lebih besar dengan ukuran file besar, tetapi kecocokannya juga tidak cukup lengkap, dan Anda dapat dengan mudah menemukan contoh file berukuran sedang dengan nilai yang relatif besar di posisi pertama. Tetapi mungkin jika kita menambahkan kedua nilai ini bersama-sama, jumlah mereka akan lebih baik berkorelasi dengan ukuran file?

Kita dapat menggunakan readuntuk mengekstraksi dua angka dari output odke variabel yang terpisah, dan kemudian menggunakan aritmatika shell untuk menemukan jumlah mereka:

perintah Shellreadtidak dapat digunakan di sisi kanan bilah vertikal, karena perintah yang ditransfer ke pipa dieksekusi dalam prosesor perintah anak (subkulit), yang, ketika keluar, membawa variabel lingkungannya ke penerima bit. Oleh karena itu, sebagai gantinya, kita perlu menggunakan fungsi substitusi proses bashdan mengarahkan output odke file sementara, yang kemudian dapat diarahkan ke perintah read.

$ untuk f di level / *; do size = $ (wc -c <$ f); baca v1 v2 << (od -tuS -An -N4 $ f); jumlah = $ (($ v1 + $ v2));
    echo "$ size: $ v1 + $ v2 = $ sum"; selesai | kurang
585: 35 + 476 = 511
586: 45 + 447 = 492
550: 43 + 417 = 460
302: 29 + 211 = 240
517: 45 + 378 = 423
671: 49 + 520 = 569
265: 26 + 183 = 209
344: 26 + 262 = 288
478: 32 + 378 = 410
342: 58 + 164 = 222
336: 38 + 218 = 256
352: 36 + 240 = 276
625: 42 + 495 = 537
532: 44 + 396 = 440
386: 42 + 256 = 298
450: 27 + 365 = 392
373: 30 + 279 = 309
648: 50 + 494 = 544
477: 42 + 347 = 389
530: 44 + 394 = 438
247: 29 + 156 = 185
325: 32 + 225 = 257
394: 32 + 294 = 326
343: 31 + 246 = 277
baris 1-24 / 148 (selengkapnya)

Jumlah dari dua angka juga kira-kira berkorelasi dengan ukuran file, tetapi mereka masih kurang cocok. Seberapa berbeda mereka? Mari kita tunjukkan perbedaannya:

$ untuk f di level / *; do size = $ (wc -c <$ f); baca v1 v2 << (od -tuS -An -N4 $ f); diff = $ (($ size - $ v1 - $ v2));
    echo "$ size = $ v1 + $ v2 + $ diff"; selesai | kurang
585 = 35 + 476 + 74
586 = 45 + 447 + 94
550 = 43 + 417 + 90
302 = 29 + 211 + 62
517 = 45 + 378 + 94
671 = 49 + 520 + 102
265 = 26 + 183 + 56
344 = 26 + 262 + 56
478 = 32 + 378 + 68
342 = 58 + 164 + 120
336 = 38 + 218 + 80
352 = 36 + 240 + 76
625 = 42 + 495 + 88
532 = 44 + 396 + 92
386 = 42 + 256 + 88
450 = 27 + 365 + 58
373 = 30 + 279 + 64
648 = 50 + 494 + 104
477 = 42 + 347 + 88
530 = 44 + 394 + 92
247 = 29 + 156 + 62
325 = 32 + 225 + 68
394 = 32 + 294 + 68
343 = 31 + 246 + 66
lines 1-24/148 (more)

Perbedaan, atau nilai "sisa", ditampilkan di sisi paling kanan dari output. Nilai ini tidak cukup jatuh ke dalam pola konstan, tetapi tampaknya tetap sekitar dalam kisaran terbatas 40-120. Dan lagi, semakin besar file, biasanya lebih banyak dari nilai residu mereka. Tetapi terkadang file kecil juga memiliki nilai residu yang besar, jadi ini tidak konstan seperti yang kita inginkan.

Namun, perlu dicatat bahwa nilai residu tidak pernah negatif. Oleh karena itu, gagasan bahwa kedua nilai metadata ini menunjukkan subbagian file tetap menarik.

(Jika Anda cukup berhati-hati, Anda telah melihat sesuatu yang memberi petunjuk tentang koneksi yang belum diketahui. Jika Anda belum, maka lanjutkan membaca; rahasia akan segera terungkap.)

Perbandingan Lintas-File Lebih Besar

Pada titik ini, akan lebih baik untuk dapat membandingkan lebih dari 16 byte sekaligus. Untuk ini kita memerlukan jenis visualisasi yang berbeda. Salah satu pendekatan yang baik adalah membuat gambar di mana setiap piksel menunjukkan byte terpisah dari salah satu file, dan warna menunjukkan nilai byte ini. Suatu gambar dapat memperlihatkan sepotong dari 148 file sekaligus jika setiap file data ditunjukkan oleh satu baris piksel gambar. Karena semua file memiliki ukuran yang berbeda, kami mengambil 200 byte pertama masing-masing untuk membangun gambar persegi panjang.

Cara termudah adalah membangun gambar dalam skala abu-abu, di mana nilai setiap byte sesuai dengan tingkat abu-abu yang berbeda. Sangat mudah untuk membuat file PGM dengan data kami, karena header PGM hanya terdiri dari teks ASCII:

 $ echo P5 200 148 255 >hdr.pgm

PGM? PGM, «portable graymap» (« ») — , : ASCII, . — PBM («portable bitmap», « »), 8 , PPM («portable pixmap», « »), 3 .

P5Apakah tanda tangan awal untuk format file PGM. Dua angka berikutnya, 200dan 148, tentukan lebar dan tinggi gambar, dan yang terakhir 255,, menunjukkan nilai maksimum per piksel. Header PGM berakhir dengan baris baru diikuti oleh data piksel. (Perlu dicatat bahwa header PGM paling sering dibagi menjadi tiga baris teks yang terpisah, tetapi standar PGM hanya mengharuskan elemen-elemen dipisahkan oleh beberapa karakter spasi putih.)

Kita dapat menggunakan utilitas headuntuk mengekstrak 200 byte pertama dari setiap file:

$ untuk f di level / *; lakukan head -c200 $ f; selesai> out.pgm

Kemudian kita dapat menggabungkannya dengan tajuk dan membuat gambar yang ditampilkan:

xview- ini adalah program X lama untuk menampilkan gambar di jendela. Anda dapat menggantinya dengan penampil gambar favorit Anda, misalnya, utilitas displaydari ImageMagick, tetapi perlu diingat bahwa ada banyak pemirsa gambar yang tidak menerima file gambar yang dialihkan ke input standar.

$ cat hdr.pgm out.pgm | xview / dev / stdin

Jika sulit bagi Anda untuk mempertimbangkan detail dalam gambar gelap, maka Anda dapat memilih skema warna yang berbeda. Gunakan utilitas pgmtoppmdari ImageMagick untuk mengonversi piksel ke rentang warna yang berbeda. Versi ini akan membuat gambar "negatif":

$ cat hdr.pgm out.pgm | pgmtoppm putih-hitam | xview / dev / stdin

Dan versi ini membuat nilai rendah menjadi kuning dan nilai tinggi menjadi biru:

$ cat hdr.pgm out.pgm | pgmtoppm kuning-biru | xview / dev / stdin

Visibilitas warna adalah pertanyaan yang sangat subyektif, sehingga Anda dapat bereksperimen dan memilih mana yang terbaik untuk Anda. Meskipun demikian, gambar 200 × 148 ini cukup kecil, jadi yang terbaik adalah meningkatkan visibilitas dengan meningkatkan ukurannya:

$ cat hdr.pgm out.pgm | xview -zoom 300 / dev / stdin

Gambar gelap, dan ini berarti bahwa sebagian besar byte mengandung nilai kecil. Strip nyata piksel yang paling terang lebih dekat ke tepi kiri kontras dengan itu. Strip ini terletak di byte ketiga file, yang, seperti yang kami katakan di atas, bervariasi dalam kisaran nilai penuh.

Dan meskipun tidak ada banyak nilai tinggi di luar byte ketiga, ketika mereka muncul, mereka sering terdiri dari seri, menciptakan garis-garis terang pendek pada gambar. Beberapa seri ini terputus secara berkala, menciptakan efek garis putus-putus. (Mungkin, dengan pemilihan warna yang tepat, akan mungkin untuk melihat urutan seperti itu dalam warna yang lebih gelap.)

Dengan studi yang cermat terhadap gambar, dapat dipahami bahwa sebagian besar di bagian kiri mendominasi garis-garis vertikal kecil. Band-band ini memberi tahu kami tentang beberapa pengulangan di sebagian besar file. Tetapi tidak di semua file - dari waktu ke waktu ada garis piksel di mana band terputus - tetapi ini lebih dari cukup untuk menentukan keberadaan pola nyata. Pola ini menghilang di sisi kanan gambar, latar belakang gelap dari garis-garis memberi jalan ke sesuatu yang lebih berisik dan tidak terbatas. (Tampaknya garis-garis itu juga hilang di bagian paling kiri gambar, tetapi, saya ulangi, ada kemungkinan bahwa ketika menggunakan skema warna yang berbeda, Anda dapat melihat bahwa garis-garis itu mulai lebih dekat ke tepi kiri daripada yang terlihat di sini.)

Garis-garis ini terdiri dari garis tipis piksel yang sedikit lebih terang dengan latar belakang piksel yang sedikit lebih gelap. Oleh karena itu, pola grafik ini harus berkorelasi dengan pola file data di mana nilai yang sedikit lebih besar tersebar merata di antara nilai byte yang sedikit lebih kecil. Tampaknya garis-garis tersebut habis kira-kira di tengah-tengah gambar. Karena ini menunjukkan 200 byte file pertama, Anda harus berharap bahwa pola byte berakhir setelah sekitar 100 byte.

Fakta bahwa pola-pola ini berubah dalam file data yang berbeda harus mengarahkan kita pada pertanyaan: seperti apa file tersebut setelah 200 byte pertama. Kita dapat dengan mudah mengganti utilitas dengan headutilitas taildan melihat seperti apa 200 byte terakhir itu:

$ untuk f di level / *; lakukan tail -c200 $ f; selesai> out.pgm; cat hdr.pgm out.pgm | xview -zoom 300 / dev / stdin

Kami segera melihat bahwa area file data ini sangat berbeda. Di sini, byte jauh lebih umum, terutama menjelang akhir file. (Namun, seperti sebelumnya, mereka lebih suka mengelompokkan bersama, menutupi gambar dengan garis-garis horizontal yang cerah.) Tampaknya frekuensi nilai byte tinggi meningkat hampir sampai akhir, di mana ia tiba-tiba rusak dan digantikan oleh nilai-nilai rendah sekitar sepuluh hingga dua belas byte terakhir. Dan pola di sini juga tidak universal, tetapi terlalu standar untuk menjadi kebetulan.

Mungkin di tengah file mungkin ada area lain yang belum kita pertimbangkan. Hal berikutnya yang ingin kita lakukan adalah memeriksa seluruh file dengan cara ini. Tetapi karena semua file memiliki ukuran yang berbeda, mereka tidak dapat ditempatkan dalam array piksel persegi panjang yang indah. Kita dapat mengisi akhir setiap baris dengan piksel hitam, tetapi akan lebih baik jika kita mengubah ukurannya sehingga semua garis memiliki lebar yang sama dan area proporsional dari file yang berbeda lebih atau kurang cocok.

Dan kita sebenarnya bisa melakukan ini dengan sedikit usaha. Anda dapat menggunakan Python dan perpustakaannya untuk bekerja dengan gambar PIL("Bantal"):

File showbytes.py:

 import sys from PIL import Image # Retrieve the full list of data files. filenames = sys.argv[1:] # Create a grayscale image, its height equal to the number of data files. width = 750 height = len(filenames) image = Image.new('L', (width, height)) # Fill in the image, one row at a time. for y in range(height): # Retrieve the contents of one data file. data = open(filenames[y]).read() linewidth = len(data) # Turn the data into a pixel-high image, each byte becoming one pixel. line = Image.new(image.mode, (linewidth, 1)) linepixels = line.load() for x in range(linewidth): linepixels[x,0] = ord(data[x]) # Stretch the line out to fit the final image, and paste it into place. line = line.resize((width, 1)) image.paste(line, (0, y)) # Magnify the final image and display it. image = image.resize((width, 3 * height)) image.show()

Saat kami memanggil skrip ini, menggunakan daftar lengkap file data sebagai argumen, skrip ini akan membuat gambar lengkap dan menampilkannya di jendela terpisah:

 $ python showbytes.py levels / *

Sayangnya, meskipun gambar ini selesai, tidak menunjukkan kepada kami sesuatu yang baru. (Tapi sebenarnya itu menunjukkan lebih sedikit, karena mengubah ukuran menghancurkan pola dari garis-garis.) Mungkin, untuk mempelajari seluruh rangkaian data, kita memerlukan proses visualisasi yang lebih baik.

Mengkarakterisasi data

Dengan mengingat hal ini, mari kita berhenti sejenak dan menyelesaikan sensus data yang lengkap. Kita perlu tahu apakah file data memberikan preferensi ke nilai byte tertentu. Misalnya, jika setiap nilai biasanya sama duplikatnya, maka ini akan menjadi bukti kuat bahwa file-file tersebut benar-benar dikompres.

Untuk benar-benar

menulis ulang nilai, cukup beberapa baris dalam Python yang cukup: File census.py:

 import sys data = sys.stdin.read() for c in range(256): print c, data.count(chr(c))

Setelah memasukkan semua data ke dalam satu variabel, kita dapat menghitung frekuensi kemunculan setiap nilai byte.

$ level kucing / * | python ./census.py | kurang
0 2458
1 2525
2 1626
3 1768
4 1042
5 1491
6 1081
7 1445
8 958
9 1541
10 1279
11 1224
12.845
13 908
14 859
15 1022
16 679
17 1087
18.881
19 1116
20 1007
21 1189
22 1029
23.733
baris 1-24 / 256 (selengkapnya)

Kita melihat bahwa paling sering ada nilai byte 0 dan 1, frekuensi berikutnya adalah 2 dan 3, setelah itu angkanya terus menurun (walaupun dengan lebih sedikit keteguhan). Untuk memvisualisasikan data ini dengan lebih baik, kami dapat mentransfer output ke gnuplotdan mengubah sensus ini menjadi histogram:

Opsi -putilitas gnuplotmemerintahkan untuk tidak menutup jendela dengan grafik setelah pekerjaan selesai gnuplot.

$ level kucing / * | python ./census.py | gnuplot -p -e 'plot "-" with boxes'

Sangat terlihat bahwa nilai byte pertama jauh lebih umum daripada yang lainnya. Beberapa dari nilai-nilai berikut juga cukup umum, dan kemudian frekuensi nilai-nilai dari sekitar 50 mulai menurun di sepanjang kurva probabilitas yang mulus. Namun, ada himpunan bagian dari nilai-nilai tinggi yang terpisah satu sama lain, yang frekuensinya agak stabil. Dengan melihat output asli, kita dapat memastikan bahwa subset ini terdiri dari nilai-nilai yang dapat dibagi delapan.

Perbedaan-perbedaan dalam jumlah nilai ini mengisyaratkan bahwa ada beberapa "kelas" nilai byte yang berbeda, jadi akan logis untuk melihat bagaimana kelas-kelas ini didistribusikan. Grup nilai byte pertama akan menjadi nilai terendah: 0, 1, 2, dan 3. Kemudian grup kedua dapat berupa nilai dari 4 hingga 64. Dan grup ketiga adalah nilai di atas 64, yang dapat dibagi dengan 8. Tanpa jejak, semua yang lain, termasuk non-habis dibagi 8 nilai lebih besar dari 64 akan menjadi kelompok keempat dan terakhir.

Dengan semua ini dalam pikiran, kita dapat mengubah skrip generasi gambar tertulis terakhir. Alih-alih menampilkan nilai aktual dari setiap byte dalam warna yang terpisah, mari kita perlihatkan saja kelompok dari masing-masing byte. Anda dapat menetapkan warna unik untuk masing-masing dari empat grup, dan ini akan membantu kami melihat apakah nilai-nilai tertentu benar-benar muncul di tempat-tempat tertentu.

File showbytes2.py:

 import sys from PIL import Image # Retrieve the full list of data files. filenames = sys.argv[1:] # Create a color image, its height equal to the number of data files. width = 750 height = len(filenames) image = Image.new('RGB', (width, height)) # Fill in the image, one row at a time. for y in range(height): # Retrieve the contents of one data file. data = open(filenames[y]).read() linewidth = len(data) # Turn the data into a pixel-high image, each byte becoming one pixel. line = Image.new(image.mode, (linewidth, 1)) linepixels = line.load() # Determine which group each byte belongs to and assign it a color. for x in range(linewidth): byte = ord(data[x]) if byte < 0x04: linepixels[x,0] = (255, 0, 0) elif byte < 0x40: linepixels[x,0] = (0, 255, 0) elif byte % 8 == 0: linepixels[x,0] = (0, 0, 255) else: linepixels[x,0] = (255, 255, 255) # Paste the line of pixels into the final image, stretching to fit. line = line.resize((width, 1)) image.paste(line, (0, y)) # Magnify the final image and display it. image = image.resize((width, 3 * height)) image.show()

Kami menugaskan empat kelompok merah, hijau, biru dan putih. (Sekali lagi, Anda dapat mencoba memilih warna lain yang sesuai dengan preferensi Anda.)

 $ python showbytes2.py levels / *

Berkat gambar ini, kami dapat mengkonfirmasi sebelumnya pemisahan file data menjadi lima bagian:

Header empat byte yang kami temukan sebelumnya.
, , (.. ).
, (. 64).
, .
, .

Berkat warna-warna ini, jelaslah bahwa di bagian keempat, di mana nilai byte tinggi berlaku, seperti yang dapat dilihat pada gambar skala abu-abu, nilai byte tinggi, membaginya dengan 8, terutama yang berlaku.

Dari gambar sebelumnya kita tahu bahwa bagian kedua, yaitu, bagian dengan garis-garis membentang di area yang hampir sepenuhnya merah. Bahkan, dalam salah satu gambar pertama kita melihat bahwa bagian dengan garis-garis, pergi dari kiri ke kanan, perlahan-lahan menjadi cerah.

Kita melihat lagi bahwa piksel hijau dari bagian ketiga utama membentuk pola bertitik dari piksel hijau dan merah berselang (baik biru atau putih) dari waktu ke waktu. Namun, pola ini tidak terlalu teratur, dan mungkin imajiner.

Tentu saja, pembagian file ini menjadi lima bagian sangat sewenang-wenang. Bagian keempat dengan nilai byte tinggi yang dapat dibagi delapan mungkin menjadi akhir dari bagian ketiga. Atau mungkin ternyata yang terbaik adalah membagi sepertiga bagian besar menjadi beberapa bagian yang belum kita tentukan. Pada tahap ini, penemuan bagian membantu kita lebih banyak menemukan tempat untuk penelitian lebih lanjut. Untuk saat ini, cukup bagi kami untuk mengetahui bahwa ada bagian di mana komposisi umum nilai byte berubah, dan perkiraan ukurannya akan membantu kami melanjutkan penelitian kami.

Pencarian struktur

Apa yang harus kita cari selanjutnya? Nah, seperti sebelumnya, cara termudah untuk memulai adalah dari atas file. Atau lebih tepatnya, di dekat bagian atas. Karena kita sudah cukup percaya diri mengidentifikasi bagian pertama sebagai header empat byte, mari kita lihat lebih dekat apa yang terjadi selanjutnya - area yang kita sebut bagian kedua, atau bagian dari band. Pita-pita ini adalah isyarat terkuat dari keberadaan struktur, oleh karena itu lebih baik mencari bukti baru dari keberadaan pola di sini.

(Untuk saat ini, kami mengasumsikan bahwa pola strip dimulai segera setelah empat byte pertama. Secara visual, ini tidak jelas, tetapi tampaknya mungkin, dan memeriksa nilai byte harus dengan cepat menunjukkan kepada kita kebenarannya.)

Mari kita kembali ke hex dump, kali ini fokus pada bagian kedua. Ingatlah bahwa kami berharap menemukan pola berulang dengan nilai yang sedikit lebih tinggi yang terdistribusi secara merata di antara nilai yang sedikit lebih rendah.

Opsi -s4memerintahkan untuk xxdmelewati 4 byte pertama file.

$ untuk f di level / *; lakukan xxd -s4 $ f | sed -n 1p; selesai | kurang
00000004: 0200 0003 0202 0401 0105 0303 0700 0108 ................
00000004: 0201 0104 0000 0504 0407 0202 0902 010a ................
00000004: 0300 0004 0303 0504 0407 0505 0801 0109 ................
00000004: 0300 0009 0202 1203 0313 0909 1401 0115 ................
00000004: 0203 0305 0000 0602 0207 0505 0901 010a ................
00000004: 0203 0304 0000 0502 0206 0404 0901 010a ................
00000004: 0300 0005 022a 0602 2907 0303 0902 000a ..... * ..) .......
00000004: 0203 0305 0000 0605 0507 0101 0802 0209 ................
00000004: 0300 0007 0303 0901 010a 0707 0b09 090c ................
00000004: 0300 0004 0101 0903 030e 0404 1609 0920 ...............
00000004: 0200 0003 1313 0402 0205 0013 0701 0109 ................
00000004: 0500 0006 0505 0701 0109 0606 0e07 070f ................
00000004: 0100 0003 0101 0a03 030b 0a0a 0e32 3216 .............22.
00000004: 0300 0004 0705 0903 030a 0606 0b08 080c ................
00000004: 0200 0003 0701 0402 0209 0501 0a08 080b ................
00000004: 0200 0003 0202 0901 010a 0303 0b05 010d ................
00000004: 0200 0003 0202 0403 0305 0101 0904 040a ................
00000004: 0300 0007 0303 0f01 0115 0707 2114 1422 ............!.."
00000004: 0200 0003 0202 0403 0309 0101 0a04 040b ................
00000004: 0231 3103 0202 0500 0006 0303 0701 0109 .11.............
00000004: 0200 0003 0202 0b32 320c 0303 0e08 0811 .......22.......
00000004: 0201 0103 0000 0902 020a 0303 0b09 090c ................
00000004: 0200 0003 0202 0a01 010b 0303 0d0b 0b0f ................
00000004: 0300 0005 0303 0701 0109 0001 0b05 051b ................
lines 27-50/148 (more)

Dengan hati-hati melihat urutan byte dalam string, kita dapat melihat pola di mana byte pertama, keempat, ketujuh dan kesepuluh lebih besar dari tetangga terdekatnya. Pola ini tidak sempurna, memiliki pengecualian, tetapi pasti cukup stabil untuk membuat pengulangan visual dari band yang terlihat pada semua gambar. (Dan itu cukup untuk mengonfirmasi asumsi kami bahwa pola garis dimulai segera setelah header empat byte.)

Keteguhan pola ini jelas menyiratkan bahwa bagian file ini adalah array atau tabel, dan setiap catatan dalam array memiliki panjang tiga byte.

Anda dapat mengonfigurasi format hex dump untuk membuatnya lebih mudah untuk melihat output sebagai serangkaian kembar tiga:

Opsi -g3mengatur pengelompokan dengan tiga byte, bukan dua. Opsi-c18 menetapkan 18 byte (kelipatan 3) per baris, bukan 16.

$ untuk f di level / *; lakukan xxd -s4 -g3 -c18 $ f | sed -n 1p; selesai | kurang
00000004: 050000 060505 070101 090606 0e0707 0f0001 ..................
00000004: 010000 030101 0a0303 0b0a0a 0e3232 161414 ............. 22 ...
00000004: 030000 040705 090303 0a0606 0b0808 0c0101 ..................
00000004: 020000 030701 040202 090501 0a0808 0b0101 ..................
00000004: 020000 030202 090101 0a0303 0b0501 0d0302 ..................
00000004: 020000 030202 040303 050101 090404 0a0302 ..................
00000004: 030000 070303 0f0101 150707 211414 221313 ............! .. "..
00000004: 020000 030202 040303 090101 0a0404 0b0001 ..................
00000004: 023131 030202 050000 060303 070101 090505 .11 ...............
00000004: 020000 030202 0b3232 0c0303 0e0808 110b0b ....... 22 .........
00000004: 020101 030000 090202 0a0303 0b0909 0c0a0a ..................
00000004: 020000 030202 0a0101 0b0303 0d0b0b 0f2323 ................##
00000004: 030000 050303 070101 090001 0b0505 1b0707 ..................
00000004: 022323 030000 040202 050303 030101 070505 .##...............
00000004: 031414 050000 060303 070505 080101 090707 ..................
00000004: 030000 050202 060303 070505 080101 090606 ..................
00000004: 030202 040000 050303 070404 080005 090101 ..................
00000004: 030202 040000 050303 090404 1d0101 1f0909 ..................
00000004: 020000 050303 060101 070202 0f0300 110505 ..................
00000004: 050000 070101 0c0505 0d0007 110c0c 120707 ..................
00000004: 030202 050000 060303 070505 080101 090606 ..................
00000004: 020000 030101 050202 060505 070100 080303 ..................
00000004: 020000 030202 050303 090101 0a0505 0b0302 ..................
00000004: 022c2c 030000 040202 020303 050101 060202 .,,...............
lines 38-61/148 (more)

Dalam dump yang diformat dengan cara ini, beberapa fitur lain dari pola ini mulai muncul. Seperti sebelumnya, byte pertama dari setiap triplet biasanya lebih besar dari byte yang mengelilinginya. Anda juga dapat memperhatikan bahwa byte kedua dan ketiga dari setiap triplet sering digandakan. Turun kolom pertama, kita akan melihat bahwa sebagian besar nilai byte kedua dan ketiga sama 0000. Tetapi nilai-nilai bukan nol juga sering ditemukan berpasangan, misalnya, 0101atau 2323. Pola ini juga tidak sempurna, tetapi memiliki banyak kesamaan untuk menjadi kebetulan. Dan melihat kolom ASCII di sebelah kanan, kita akan melihat bahwa ketika kita memiliki nilai byte yang sesuai dengan karakter ASCII yang dapat dicetak, mereka sering ditemukan berpasangan.

Pola lain yang layak disebutkan yang tidak segera terlihat: byte pertama dari setiap triple meningkat dari kiri ke kanan. Meskipun pola ini kurang terlihat, stabilitasnya tinggi; kita perlu melihat banyak baris sebelum kita menemukan ketidakcocokan pertama. Dan byte biasanya meningkat dengan nilai kecil, tetapi mereka tidak mewakili pola reguler.

Ketika mempelajari gambar asli, kami perhatikan bahwa bagian dengan garis-garis berakhir di setiap file tidak di tempat yang sama. Ada transisi dari membuat strip pola di sebelah kiri ke derau acak di sebelah kanan, tetapi transisi ini terjadi untuk setiap baris piksel pada titik yang berbeda. Ini menyiratkan bahwa harus ada beberapa penanda sehingga program membaca file data dapat memahami di mana array berakhir dan set data lain dimulai.

Mari kita kembali ke dump hanya level pertama untuk memeriksa seluruh file:

 $ xxd -s4 -g3 -c18 level / lesson_1.pak
00000004: 020000 040202 050404 070505 080707 090001 ..................
00000016: 0a0101 0b0808 0d0a0a 110023 150907 180200 ........... # ......
00000028: 22090d 260911 270b0b 280705 291e01 272705 ".. & .. '.. (..) ..' '.
0000003a: 020d01 220704 090209 0a0215 042609 250111 ... "......... &.% ..
0000004c: 150222 1d0124 011d0d 010709 002000 1b0400 .. ".. $ ....... ....
0000005e: 1a0020 152609 1f0033 002911 152223 02110d ... & ... 3.) .. "# ...
00000070: 010726 091f18 291115 09181a 022302 1b0215 .. & ...) ...... # ....
00000082: 22011c 011c0d 0a0704 090201 020128 260123 "............. (&. #
00000094: 150509 020121 150522 0a2727 0b0504 00060b .....! .. ".''......
000000a6: 082804 18780b 082804 18700b 082804 186400 .(..x..(..p..(..d.
000000b8: 17101e 1e1a19 010300 0e1a17 17100e 1f010e ..................
000000ca: 13141b 291f1a 001210 1f011b 0c1e1f 011f13 ...)..............
000000dc: 10010e 13141b 001e1a 0e1610 1f2d00 201e10 .............-. ..
000000ee: 011610 24291f 1a011a 1b1019 000f1a 1a1d1e ...$).............
00000100: 2d02

Mempelajari urutan kembar tiga, kita dapat mengasumsikan bahwa bagian dengan pita-pita dalam data ini berakhir setelah 17 kembar tiga, dengan offset 00000036. Ini tidak akurat, tetapi byte pertama dari setiap triplet terus-menerus meningkatkan nilainya, dan kemudian menurun pada triplet kedelapan belas. Satu lagi bukti: pada triplet kedelapan belas, byte kedua memiliki arti yang sama dengan byte pertama. Kami belum melihat ini, tetapi jika kita kembali dan melihat, kita akan melihat bahwa byte pertama tidak pernah sama dengan byte kedua atau ketiga.

Jika teori penanda kita benar, maka ada dua kemungkinan. Pertama, adalah mungkin bahwa setelah bagian strip ada beberapa nilai byte khusus (tepat setelah triplet ketujuh belas). Kedua, mungkin ada nilai yang disimpan di suatu tempat yang sama dengan ukuran bagian dengan garis-garis. Ukuran ini bisa sama dengan 17 (yaitu, ini menunjukkan jumlah kembar tiga), atau 51 (ini menunjukkan jumlah total byte dalam suatu bagian), atau 55 (51 ditambah 4, yaitu, offset file di mana bagian ini berakhir).

Untuk opsi pertama, nilai byte ganda dapat menjadi penanda untuk bagian akhir (mengingat bahwa urutan seperti itu tidak pernah terjadi di bagian kedua). Namun, studi yang cermat terhadap beberapa file data lain bertentangan dengan ide ini, karena pola seperti itu tidak muncul di tempat lain.

Untuk opsi kedua, jelas akan mencari indikator ukuran di bagian pertama. Lihatlah - nilai 16-bit pertama dalam header file empat byte adalah 17:

 $ od -An -tuS -N4 level / lesson_1.pak
    17 203

Jika teori kita benar, maka nilai ini tidak menentukan ukuran bagian dengan garis, tetapi jumlah rekaman tiga byte. Untuk menguji ide ini, mari kita kembali ke komputasi, di mana kita membandingkan jumlah dua nilai integer 16-bit dengan ukuran file. Kali ini kita mengalikan angka pertama dengan tiga untuk mendapatkan ukuran sebenarnya dalam byte:

$ untuk f di level / *; do size = $ (wc -c <$ f); baca v1 v2 << (od -tuS -An -N4 $ f); diff = $ (($ size - 3 * $ v1 - $ v2));
    echo "$ size = 3 * $ v1 + $ v2 + $ diff"; selesai | kurang
585 = 3 * 35 + 476 + 4
586 = 3 * 45 + 447 + 4
550 = 3 * 43 + 417 + 4
302 = 3 * 29 + 211 + 4
517 = 3 * 45 + 378 + 4
671 = 3 * 49 + 520 + 4
265 = 3 * 26 + 183 + 4
344 = 3 * 26 + 262 + 4
478 = 3 * 32 + 378 + 4
342 = 3 * 58 + 164 + 4
336 = 3 * 38 + 218 + 4
352 = 3 * 36 + 240 + 4
625 = 3 * 42 + 495 + 4
532 = 3 * 44 + 396 + 4
386 = 3 * 42 + 256 + 4
450 = 3 * 27 + 365 + 4
373 = 3 * 30 + 279 + 4
648 = 3 * 50 + 494 + 4
477 = 3 * 42 + 347 + 4
530 = 3 * 44 + 394 + 4
247 = 3 * 29 + 156 + 4
325 = 3 * 32 + 225 + 4
394 = 3 * 32 + 294 + 4
343 = 3 * 31 + 246 + 4
lines 1-24/148 (more)

Ya! Setelah perubahan ini, jumlah total dari header selalu tepat empat kurang dari ukuran seluruh file data. Dan karena empat juga merupakan jumlah byte di header, jelas bahwa ini bukan kebetulan. Angka pertama memberi kita jumlah entri tiga byte dalam tabel, dan angka kedua memberi kita jumlah byte yang merupakan sisa dari file data.

Kami menemukan rumus konstan, yang berarti bahwa kami sekarang sepenuhnya memahami apa arti angka-angka di bagian pertama.

(Ngomong-ngomong, ini adalah pola yang sangat rahasia yang bisa dilihat oleh pembaca yang penuh perhatian. Sebuah penelitian yang cermat tentang persamaan menjelaskan bahwa ketika file memiliki angka pertama yang sama, mereka mendapatkan perbedaan residu yang sama. Ini terjadi karena perbedaan selalu dua kali nilainya. nomor pertama. Ini adalah pola yang tidak terlihat, tetapi pengamat yang telaten atau sukses dapat menyadarinya.)

Jadi, kita dapat mengatakan bahwa file tersebut memiliki tiga bagian utama:

header empat byte;
tabel catatan tiga byte; dan
sisa file, yang seharusnya berisi sebagian besar data.

(Konsekuensinya, bagian lain yang telah kita tentukan sebelumnya harus menjadi subbagian dari bagian ketiga.)

Menafsirkan Metadata

Dengan skema ini, akan masuk akal untuk mengasumsikan bahwa entri dalam tabel bagian kedua adalah beberapa metadata yang diperlukan untuk menafsirkan data bagian ketiga.

Tetapi metadata macam apa yang terkandung dalam tabel ini?

Kami perhatikan di atas bahwa ada beberapa tanda bahwa file data dapat dikompresi. (Sekarang ini tampaknya bahkan lebih masuk akal, karena kita tahu bahwa bagian ketiga dari setiap file, yang seharusnya berisi data dari setiap level, hanya berukuran 100-600 byte.) Jika demikian, maka sangat mungkin bahwa tabel yang mendahului data utama berisi metadata kompresi - kamus yang digunakan saat membongkar. Misalnya, sebelum data dikodekan oleh algoritma Huffman, biasanya ada kamus yang memetakan nilai byte asli ke urutan bit. Meskipun kami tidak berharap file-file ini dikodekan oleh algoritma Huffman (karena data menunjukkan pola yang jelas pada tingkat byte, yaitu, mereka hampir tidak bitstream), akan lebih bijaksana untuk mencoba menafsirkan tabel ini sebagai kamus dekompresi.

(Tentu saja, tidak setiap jenis kompresi menggunakan kamus yang tersimpan. Misalnya, algoritma deflate digunakan gzipdan zlibmemungkinkan Anda untuk membuat ulang kamus langsung dari aliran data. Namun, kasus seperti itu merupakan pengecualian daripada aturan.)

Biasanya, entri kamus terdiri dari dua bagian: kunci dan nilai-nilai. Tentu saja, kadang-kadang kunci tersirat, misalnya, ketika diperintahkan bukan ke dalam tabel pencarian, tetapi ke dalam array. Namun, kami sudah memperhatikan bahwa rekaman tiga byte tampaknya terdiri dari dua bagian - khususnya, byte pertama dari setiap catatan mengikuti pola yang jelas berbeda dari pola byte kedua dan ketiga. Dengan mengingat hal ini, hipotesis pertama yang masuk akal adalah menganggap byte pertama sebagai kunci, dan dua byte sisanya sebagai nilai.

Jika demikian, maka salah satu cara paling sederhana untuk menginterpretasikan bagian strip adalah bahwa byte pertama adalah nilai byte yang perlu diganti dalam data terkompresi, dan byte kedua dan ketiga adalah nilai yang perlu diganti. Hasil yang dibuat oleh skema ini pasti akan lebih besar, meskipun tidak jelas berapa banyak. Bagaimanapun, ini adalah hipotesis logis, dan cukup mudah untuk diverifikasi. Kita dapat menulis sebuah program pendek dengan Python yang mengimplementasikan skema dekompresi ini:

File decompress.py:

 import struct import sys # Read the compressed data file. data = sys.stdin.read() # Extract the two integers of the four-byte header. tablesize, datasize = struct.unpack('HH', data[0:4]) data = data[4:] # Separate the dictionary table and the compressed data. tablesize *= 3 table = data[0:tablesize] data = data[tablesize:datasize] # Apply the dictionary entries to the data section. for n in range(0, len(table), 3): key = table[n] val = table[n+1:n+3] data = data.replace(key, val) # Output the expanded result. sys.stdout.write(data)

Sekarang kita dapat memeriksa skrip ini menggunakan contoh file data:

$ python ./decompress.py <levels/lesson_1.pak | xxd 00000000: 0b0b 0b0b 0404 0000 0a0a 0109 0d05 0502 ................ 00000010: 0200 0100 0000 0101 0100 0009 0702 0209 ................ 00000020: 1100 0125 0100 2309 0700 0009 0d1d 0124 ...%..#........$ 00000030: 011d 0a0a 0105 0500 0100 2000 1b02 0200 .......... ..... 00000040: 1a00 2009 0709 1100 011f 0033 001e 0100 .. ........3.... 00000050: 2309 0709 0d23 0000 0023 0a0a 0105 0509 #....#...#...... 00000060: 1100 011f 0200 1e01 0023 0907 0001 0200 .........#...... 00000070: 1a00 0023 0000 1b00 0009 0709 0d01 1c01 ...#............ 00000080: 1c0a 0a01 0105 0502 0200 0100 0001 0000 ................ 00000090: 0107 0509 1101 2309 0704 0400 0100 0001 ......#......... 000000a0: 2109 0704 0409 0d01 010b 0b0b 0b08 0804 !............... 000000b0: 0402 0200 0608 0807 0707 0502 0202 0078 ...............x 000000c0: 0808 0707 0705 0202 0200 7008 0807 0707 ..........p..... 000000d0: 0502 0202 0064 0017 101e 1e1a 1901 0300 .....d.......... 000000e0: 0e1a 1717 100e 1f01 0e13 141b 1e01 1f1a ................ 000000f0: 0012 101f 011b 0c1e 1f01 1f13 1001 0e13 ................ 00000100: 141b 001e 1a0e 1610 1f2d 0020 1e10 0116 .........-. .... 00000110: 1024 1e01 1f1a 011a 1b10 1900 0f1a 1a1d .$.............. 00000120: 1e2d 0000

Namun, hasilnya tidak luar biasa. Tentu saja, aliran data yang dihasilkan menjadi lebih banyak digunakan daripada yang asli, tetapi tidak banyak. Jelas tidak cukup untuk memuat semua data yang kami harapkan akan ditemukan. Jelas, skema pembongkaran ini sedikit lebih sederhana dari yang diperlukan.

Jika kita hati-hati memeriksa output yang dihasilkan, kita akan segera melihat bahwa itu dimulai dengan banyak byte berulang. 0b, 04, 00, 0a- mereka semua terjadi pada pasangan. Melihat dokumen asli yang dikompresi, kita akan melihat bahwa semua pasangan ini muncul karena penggantian kamus. Namun dalam prosesnya, kami segera melihat bahwa semua makna duplikat ini juga sesuai dengan entri dalam kamus. Artinya, jika kita kembali menerapkan kamus, maka data akan berkembang lagi. Mungkin kita tidak cukup membongkar?

Tebakan pertama kami mungkin untuk melakukan pass kedua, menerapkan setiap entri kamus untuk kedua kalinya untuk memperluas data lebih banyak lagi. Tebakan kedua adalah melakukan beberapa lintasan dengan kamus, mengulangi prosesnya sampai semua byte yang mirip dengan kunci kamus diganti. Namun, jika kita melihat lebih dekat pada struktur kamus, kami menyadari bahwa kami hanya menerapkan entri kamus dari kanan ke kiri , dan bukan dari kiri ke kanan, ketika semua nilai kami diperluas dalam satu pass.

Mengambil hipotesis ini, kita dapat melihat struktur algoritma kompresi yang lebih masuk akal. Program mengambil sumber data dan memindainya, mencari urutan bita ganda yang paling umum. Kemudian menggantikan urutan dua byte dengan nilai satu byte yang tidak ditemukan dalam data. Kemudian ia mengulangi prosesnya, melanjutkannya hingga data berisi lebih dari dua pengulangan urutan bita-ganda. Faktanya, algoritma kompresi semacam itu memiliki nama: dikenal sebagai kompresi "pasang ulang", yang merupakan kependekan dari "pasangan rekursif".

(Dan ini dapat menjelaskan beberapa pola yang kita lihat dalam kamus. Selama kompresi, kamus dibangun dari kiri ke kanan, jadi ketika membongkar itu harus diterapkan dari kanan ke kiri. Karena entri kamus sering merujuk ke entri sebelumnya, logis bahwa byte kedua dan ketiga akan sering lebih kecil dari yang pertama.)

Meskipun kompresi pasangan-ulang tidak menghasilkan hasil yang sangat mengesankan, ia memiliki keuntungan: dekompresor dapat diimplementasikan dengan kode minimum. Saya sendiri menggunakan re-pair dalam beberapa situasi ketika saya perlu meminimalkan ukuran total data terkompresi dan kode dekompresi.

Jadi, kita dapat membuat perubahan dalam satu baris program Python untuk menerapkan kamus dari kanan ke kiri:

File decompress2.py:

 import struct import sys # Read the compressed data file. data = sys.stdin.read() # Extract the two integers of the four-byte header. tablesize, datasize = struct.unpack('HH', data[0:4]) data = data[4:] # Separate the dictionary table and the compressed data. tablesize *= 3 table = data[0:tablesize] data = data[tablesize:datasize] # Apply the dictionary entries to the data section in reverse order. for n in range(len(table) - 3, -3, -3): key = table[n] val = table[n+1:n+3] data = data.replace(key, val) # Output the expanded result. sys.stdout.write(data)

Jika kami mencoba versi ini, hasilnya akan jauh lebih besar:

 $ python ./decompress2.py <levels/lesson_1.pak | xxd | less
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000010: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000050: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000070: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000090: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000100: 0000 0000 0000 0000 0000 0101 0101 0100 ................
00000110: 0101 0101 0100 0000 0000 0000 0000 0000 ................
00000120: 0000 0000 0000 0000 0000 0100 0000 0101 ................
00000130: 0100 0000 0100 0000 0000 0000 0000 0000 ................
00000140: 0000 0000 0000 0000 0000 0100 2300 0125 ............#..%
00000150: 0100 2300 0100 0000 0000 0000 0000 0000 ..#.............
00000160: 0000 0000 0000 0000 0101 0101 011d 0124 ...............$
00000170: 011d 0101 0101 0100 0000 0000 0000 0000 ................
baris 1-24 / 93 (selengkapnya)

Kami melihat banyak byte nol dalam output ini, tetapi ini mungkin berhubungan dengan kartu yang hampir kosong. Bytes bukan nol tampaknya dikelompokkan berdampingan. Karena kami berharap dapat menemukan kartu 32 × 32, mari kita format ulang output menjadi 32 byte per baris:

$ python ./decompress2.py <levels / lesson_1.pak | xxd -c32 | kurang
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ....................................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ....................................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ....................................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000e0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000100: 0000 0000 0000 0000 0000 0101 0101 0100 0101 0101 0100 0000 0000 0000 0000 0000 ................................
00000120: 0000 0000 0000 0000 0000 0100 0000 0101 0100 0000 0100 0000 0000 0000 0000 0000 ................................
00000140: 0000 0000 0000 0000 0000 0100 2300 0125 0100 2300 0100 0000 0000 0000 0000 0000 ............#..%..#.............
00000160: 0000 0000 0000 0000 0101 0101 011d 0124 011d 0101 0101 0100 0000 0000 0000 0000 ...............$................
00000180: 0000 0000 0000 0000 0100 2000 1b00 0000 0000 1a00 2000 0100 0000 0000 0000 0000 .......... ......... ...........
000001a0: 0000 0000 0000 0000 0100 2300 011f 0033 001e 0100 2300 0100 0000 0000 0000 0000 ..........#....3....#...........
000001c0: 0000 0000 0000 0000 0101 0101 0123 0000 0023 0101 0101 0100 0000 0000 0000 0000 .............#...#..............
000001e0: 0000 0000 0000 0000 0100 2300 011f 0000 001e 0100 2300 0100 0000 0000 0000 0000 ..........#.........#...........
00000200: 0000 0000 0000 0000 0100 0000 1a00 0023 0000 1b00 0000 0100 0000 0000 0000 0000 ...............#................
00000220: 0000 0000 0000 0000 0101 0101 0101 1c01 1c01 0101 0101 0100 0000 0000 0000 0000 ................................
00000240: 0000 0000 0000 0000 0000 0000 0100 0001 0000 0100 0000 0000 0000 0000 0000 0000 ................................
00000260: 0000 0000 0000 0000 0000 0000 0100 2301 2300 0100 0000 0000 0000 0000 0000 0000 ..............#.#...............
00000280: 0000 0000 0000 0000 0000 0000 0100 0001 2100 0100 0000 0000 0000 0000 0000 0000 ................!...............
000002a0: 0000 0000 0000 0000 0000 0000 0101 0101 0101 0100 0000 0000 0000 0000 0000 0000 ................................
000002c0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000002e0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
lines 1-24/47 (more)

Setelah dengan cermat melihat pola nilai bukan nol, kita akan melihat bahwa peta terlihat jelas di output. Faktanya, kita dapat membuat pola ini lebih terlihat dengan menggunakan alat dump “berwarna”, yang memberikan warna pada setiap nilai byte, menyederhanakan pencarian pola nilai berulang: itu

xcdadalah alat yang tidak standar, tetapi Anda dapat mengunduhnya dari sini . Perhatikan opsi -rutilitas less, yang memberitahu Anda untuk menghapus urutan kontrol.

Bandingkan ini dengan peta tingkat pertama yang digambar penggemar:

Tanpa ragu, kami melihat data peta level. Anda dapat yakin bahwa kami telah menentukan algoritma pembongkaran dengan benar.

Interpretasi data

Dengan membandingkan nilai byte dengan gambar peta, kita dapat menentukan apa yang 00mengkodekan petak kosong, 01mengkodekan dinding, dan 23menunjukkan sebuah chip. 1Amenunjukkan pintu merah, 1B- pintu biru, dan sebagainya. Kami dapat menetapkan nilai tepat untuk chip, kunci, pintu, dan semua ubin lain yang membentuk seluruh peta level.

Sekarang kita bisa pergi ke level berikutnya dan menemukan nilai byte untuk objek yang muncul di sana. Dan lanjutkan ke level berikutnya sampai kita mendapatkan daftar lengkap nilai byte dan objek game yang mereka encode.

Seperti yang kami sarankan pada awalnya, kartu berakhir tepat setelah 1024 byte (pada offset 000003FF).

Kali ini, untuk menghapus 32 baris pertama dari dump, kami gunakansed. Karena kita memiliki 32 byte per baris, kita akan melewati 1024 byte pertama.

Segera setelah data peta adalah urutan 384 byte (yang nilainya dalam interval 00000400- 0000057F), hampir semuanya sama dengan nol, tetapi nilai bukan nol juga jatuh di antara mereka. Setelah ini muncul pola byte yang sama sekali berbeda, jadi akan logis untuk mengasumsikan bahwa urutan 384 byte ini adalah bagian yang terpisah.

Jika kita melihat beberapa level lagi, kita dengan cepat memperhatikan polanya. Bagian 384-byte sebenarnya terdiri dari tiga subbagian, masing-masing panjangnya 128 byte. Setiap subbagian dimulai dengan beberapa byte non-nol diikuti oleh nol yang mengisi sisa subbagian.

Beberapa level berisi banyak data; untuk orang lain (misalnya, untuk tingkat pertama) hanya sangat minimum. Membandingkan level dengan kartu mereka, kami akan segera melihat bahwa jumlah data di bagian file ini terkait langsung dengan jumlah "massa" per level. Dalam hal ini, jumlah "gerombolan" termasuk semua makhluk di tingkat, blok tanah (yang tidak bergerak secara independen, tetapi mereka dapat didorong) dan karakter utama Chip (pemain). Artinya, massa tidak ditunjukkan pada peta itu sendiri, tetapi dikodekan dalam tiga buffer ini.

Setelah kami mengetahui bahwa ketiga subbagian ini berisi data pada massa di tingkat, tidak akan terlalu sulit untuk mengetahui apa yang terkandung dalam masing-masing subbagian.

Subbagian 128 byte pertama adalah daftar nilai byte yang menentukan tipe mob. Misalnya, buffer tingkat kedua terlihat seperti ini:

 $ python ./decompress2.py <levels/lesson_2.pak | xxd | less
00000400: 0608 1c1c 0808 0000 0000 0000 0000 0000 ................
00000410: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000420: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000430: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000450: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000460: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000470: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000480: a870 98a0 6868 0000 0000 0000 0000 0000 .p..hh..........
00000490: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000500: 6060 6060 5868 0000 0000 0000 0000 0000 ````Xh..........
00000510: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000520: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000530: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000540: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000550: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000560: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000570: 0000 0000 0000 0000 0000 0000 0000 0000 ................
baris 64-87 / 93 (selengkapnya)

Bandingkan ini dengan peta level:

Pada level ini, ada enam gerombolan: tiga bug, dua blok, dan sebuah Chip. Subkey 128-byte pertama berisi satu byte 06, tiga byte, 08dan dua byte 1C. Akan masuk akal untuk menyimpulkan apa 06kepanjangan dari Chip 08- bug, dan 1C- blok.

(Melanjutkan untuk membandingkan file data dari tingkat kartu dan mengisi massa kamus kami, kami dengan cepat menemukan cacat dalam teori ini: Chip dapat disebut empat nilai yang berbeda, yaitu 04, 05, 06atau07. Set notasi ini sebenarnya berisi semua massa. Ketika kita mempelajari dengan hati-hati nilai-nilai yang berbeda, kita akhirnya akan memahami bahwa nilai 0, 1, 2, atau 3 ditambahkan ke nilai byte yang menunjukkan tipe, yang menunjukkan arah awal massa: utara, timur, selatan, atau barat. Misalnya, nilai byte 06menunjukkan Chip yang mencari ke selatan.)

Signifikansi dari dua subbagian lainnya kurang jelas. Tetapi setelah mempelajari nilai berulang dalam subbagian ini dan membandingkan kartu untuk mob ini, kita akan mengerti bahwa byte di subbagian kedua menyimpan koordinat X dari setiap mob, dan byte di subbagian ketiga menyimpan koordinat Y dari masing-masing mob. Memahami keputusan ini terhalang oleh fakta bahwa koordinat yang disimpan dalam subbagian ini sebenarnya bergeser 3 bit ke kiri, mis. dikalikan dengan 8. Fakta kecil ini menjelaskan kelompok "biru", yang kami temukan dalam sensus nilai. (Alasan mengapa pergeseran ini dibuat tidak jelas, tetapi kemungkinan tiga bit yang lebih rendah digunakan untuk mewakili animasi ketika massa bergerak.)

Setelah berurusan dengan bagian ini, kita sekarang dapat melihat berapa banyak file data yang hanya memiliki beberapa byte tersisa setelahnya:

Catatan apaxxdmenerima -snilai heksadesimal untuk opsi .

$ untuk f di level / *; lakukan python ./decompress2.py <$ f | xxd -s 0x580 | sed -n 1p; selesai | kurang
00000580: 9001 0c17 1701 1120 1717 00 ....... ...
00000580: 0000 0c17 1b13 0c0d 101f 011e 1a20 1b00 ............. ..
00000580: f401 0c18 1e1f 101d 0f0c 1800 ............
00000580: 2c01 0c1b 0c1d 1f18 1019 1f00, ...........
00000580: 9001 0c1d 0e1f 140e 1117 1a22 00 ............ "
00000580: 2c01 0d0c 1717 1e01 1a01 1114 1d10 00, ..............
00000580: 2c01 0d10 220c 1d10 011a 1101 0d20 1200, ... "........ ..
00000580: 5802 0d17 1419 1600 X .......
00000580: 0000 0d17 1a0d 0f0c 190e 1000 ............
00000580: f401 0d17 1a0d 1910 1f00 ..........
00000580: f401 0d17 1a0e 1601 110c 0e1f 1a1d 2400 .............. $.
00000580: ee02 0d17 1a0e 1601 0d20 1e1f 101d 0114 ......... ......
00000580: 5802 0d17 1a0e 1601 1901 1d1a 1717 00 X..............
00000580: 5e01 0d17 1a0e 1601 1a20 1f00 ^........ ..
00000580: c201 0d17 1a0e 1601 0d20 1e1f 101d 00 ......... .....
00000580: 2c01 0d1a 2019 0e10 010e 141f 2400 ,... .......$.
00000580: 5000 0d1d 201e 1311 141d 1000 P... .......
00000580: e703 0e0c 1610 0122 0c17 1600 ......."....
00000580: 5802 0e0c 1e1f 1710 0118 1a0c 1f00 X.............
00000580: 8f01 0e0c 1f0c 0e1a 180d 1e00 ............
00000580: 0000 0e10 1717 0d17 1a0e 1610 0f00 1b1d ................
00000580: 2c01 0e13 0e13 0e13 141b 1e00 ,...........
00000580: 8f01 0e13 1417 1710 1d00 ..........
00000580: bc02 0e13 141b 1814 1910 00 ...........
lines 1-24/148 (more)

Memeriksa pasangan byte pertama dalam sisanya dengan cepat mengisyaratkan kepada kita bahwa mereka mengandung nilai integer 16-bit lainnya. Jika kita menganggapnya seperti ini, maka sebagian besar nilai muncul dalam notasi desimal sebagai angka bulat:

Perintah odmenggunakan -jalih - alih untuk pindah ke offset asli -s. Ini juga perlu diperhatikan perintahnya printf: selain menyediakan pemformatan, ini adalah cara yang nyaman untuk menampilkan teks tanpa menggantung baris baru di akhir.

$ untuk f di level / *; lakukan printf "% -20s" $ f; python ./decompress2.py <$ f | od -An -j 0x580 -tuS -N2; selesai | kurang
levels / all_full.pak 400
level / alphabet.pak 0
level / amsterda.pak 500
level / apartmen.pak 300
level / arcticfl.pak 400
levels / balls_o_.pak 300
levels / beware_o.pak 300
level / blink.pak 600
levels / blobdanc.pak 0
levels / blobnet.pak 500
levels / block_fa.pak 500
levels / block_ii.pak 750
level / block_n_.pak 600
levels / block_ou.pak 350
level / block.pak 450
levels / bounce_c.pak 300
level / brushfir.pak 80
levels / cake_wal.pak 999
levels / castle_m.pak 600
level / catacomb.pak 399
level / cellbloc.pak 0
level / chchchip.pak 300
level / chiller.pak 399
level / chipmine.pak 700
baris 1-24 / 148 (selengkapnya)

Jika kita kembali ke daftar, yang semula dibuat dari data yang kita harapkan ditemukan dalam file, maka kita menyadari bahwa angka ini adalah waktu untuk melewati level (jika nilainya nol, maka tidak ada batas waktu pada level).

Setelah dua byte ini, data menjadi lebih tidak stabil. Fakta bahwa untuk sebagian besar level ada sekitar sepuluh byte yang tersisa dalam file dengan serius membatasi isinya:

$ python ./decompress2.py <levels / all_full.pak | xxd -s 0x0582
00000582: 0c17 1701 1120 1717 00 ..... ...

Misalnya, hanya sembilan byte yang tersisa pada level ini. Kami memperhitungkan ukuran terbatas ini, serta fakta bahwa sembilan byte ini mengandung empat kemunculan nilai 17, dikumpulkan dalam dua pasangan. Kami akan segera melihat bahwa pola angka 17sesuai dengan pola huruf Latas nama level "ALL FULL". Namanya adalah delapan karakter, jadi byte nol di akhir kemungkinan besar adalah karakter baris terakhir. Setelah menemukan ini, Anda dapat dengan mudah melihat semua level lain dan menggunakan nama mereka untuk membuat daftar karakter lengkap:

`00`	ujung garis
`01`	bilah ruang
`02` - `0B`	digit 0-9
`0C` - `25`	huruf AZ
`26` - `30`	tanda baca

Untuk sebagian besar level, file data berakhir di sini. Namun, beberapa lusin nama masih memiliki data. Jika kita melihat daftar, kita akan melihat bahwa ada level dengan tombol petunjuk, dan data yang tersisa ini berisi teks dari garis petunjuk level yang dikodekan dengan karakter yang sama yang ditetapkan sebagai nama level.

Setelah itu, kami mencapai akhir semua file. Sekarang kami memiliki deskripsi lengkap tentang skema level-level ini. Tugas kita selesai.

Bisnis yang belum selesai

Pembaca yang penuh perhatian mungkin memperhatikan bahwa awalnya kami berharap menemukan dua elemen lagi dalam file-file ini yang tidak pernah kami temui. Kami akan menjelaskan ketiadaan keduanya:

Elemen pertama adalah jumlah chip, mis. Jumlah total chip yang harus dikumpulkan pemain untuk bisa melewati konektor chip. Seperti yang kami katakan pada awalnya, seringkali itu sama dengan jumlah total chip pada suatu level, tetapi ini tidak selalu terjadi. Karena itu, data ini harus diperoleh dengan cara tertentu. Jawabannya dapat ditemukan dengan mempelajari kartu dari level tersebut di mana ada chip tambahan. Ternyata dua nilai berbeda digunakan untuk menunjukkan chip. Nilai yang 23kami temukan awalnya, tetapi nilainya juga digunakan.31menunjukkan suatu chip yang tidak mempengaruhi jumlah total yang diperlukan untuk membuka konektor chip. (Namun, dari sudut pandang gameplay, kedua jenis chip itu sama. Jika ada satu jenis chip 31di level, maka pada level tersebut Anda tidak dapat mengumpulkan jumlah chip apa pun.)

Elemen kedua adalah kata sandi tingkat empat huruf. Itu tidak tersembunyi di mana pun di data level. Sayangnya, masalah ini tidak dapat diselesaikan dengan penyelidikan lebih lanjut dari file data. Kami terpaksa menyimpulkan bahwa kata sandi disimpan di tempat lain. Penjelasan yang paling mungkin: mereka di-kode di suatu tempat dalam program itu sendiri. Namun, kemudian menjadi jelas bahwa kata sandi tidak disimpan secara langsung. Dari orang-orang yang mengenal kode itu sendiri, saya mengetahui bahwa kata sandi dihasilkan secara dinamis menggunakan generator nomor pseudo-acak yang diinisialisasi dengan urutan tertentu. Oleh karena itu, kata sandi ke level tidak dapat diubah secara langsung, ini hanya dapat dilakukan dengan mengubah kode assembler.

Kata penutup

Dengan melakukan reverse engineering lengkap dari data dalam file level, saya bisa mulai menulis sebuah program yang dapat menyandikan dan mendekode data level. Berkat dia, saya dapat membuat editor level yang lama ditunggu-tunggu untuk versi Chip's Challenge for Lynx, dan kehadiran alat ini sangat meningkatkan kemampuan saya untuk mempelajari logika permainan, dan juga meningkatkan kualitas emulasi.

Tapi ... Saya harus mengakui bahwa saya pribadi melakukan pengembangan terbalik dari file data dengan cara yang tidak dijelaskan di atas. Saya mulai dari ujung yang lain - dengan mendefinisikan data string. Saya mulai mempelajari file-file dari delapan level pertama. Karena mereka dipanggil dari "PELAJARAN 1" ke "PELAJARAN 8", saya mencari data substring identik di dalamnya. Dan saya beruntung: tidak ada nama level ini yang dikompresi, jadi kedelapan nama tersebut disimpan dalam file data dalam bentuk aslinya. Tentu saja, saya merasa malu bahwa baris-baris ini tidak disimpan dalam karakter ASCII, tetapi double S dalam namanya membantu saya mendeteksi pola yang berulang dalam delapan file data. Dan setelah menemukan namanya, saya mengenali pengkodean karakter huruf, angka, dan karakter spasi. Kemudian saya menerapkan pengkodean ini ke seluruh file, dan tepat setelah nama saya melihat baris prompt, dan mulai mengamati anomali:

Utilitas yang hebat trmembuatnya mudah untuk mengkonversi set karakter Anda sendiri dari file data ke ASCII.

$ tr '\ 001- \ 045' '0-9A-Z' <level / lesson_1.pak | xxd
00000000: 4600 cb00 3000 0032 3030 3332 3235 3333 F ... 0..200322533
00000010: 3635 3537 0020 3820 2039 3636 4238 3846 6557. 8 966B88F
00000020: 0058 4a37 354d 3000 5737 4226 3746 2739 .XJ75M0.W7B & 7F'9
00000030: 3928 3533 2953 2027 2733 3042 2057 3532 9 (53) S '' 30B W52
00000040: 3730 3738 304a 3226 375a 2046 4a30 5752 70780J2 & 7Z FJ0WR
00000050: 2059 2052 4220 3537 0055 0050 3200 4f00 Y RB 57.U.P2.O.
00000060: 554a 2637 5400 3300 2946 4a57 5830 4642 UJ & 7T.3.) FJWX0FB
00000070: 2035 2637 544d 2946 4a37 4d4f 3058 3050 5 & 7TM) FJ7MO0X0P
00000080: 304a 5720 5120 5142 3835 3237 3020 3020 0JW Q QB85270 0
00000090: 2826 2058 4a33 3730 2056 4a33 5738 2727 (& XJ370 VJ3W8''
000000a0: 3933 3200 3439 3628 324d 7839 3628 324d 932.496(2Mx96(2M
000000b0: 7039 3628 324d 6400 4c45 5353 4f4e 2031 p96(2Md.LESSON 1
000000c0: 0043 4f4c 4c45 4354 2043 4849 5029 544f .COLLECT CHIP)TO
000000d0: 0047 4554 2050 4153 5420 5448 4520 4348 .GET PAST THE CH
000000e0: 4950 0053 4f43 4b45 542d 0055 5345 204b IP.SOCKET-.USE K
000000f0: 4559 2954 4f20 4f50 454e 0044 4f4f 5253 EY)TO OPEN.DOORS
00000100: 2d30 -0

Misalnya, dalam teks bantuan ada dua tempat di mana urutan S dan spasi diganti oleh braket kanan. Anomali ini memberi saya cukup bukti untuk secara deduktif menghitung keberadaan kompresi dan mendapatkan beberapa informasi tentang sifatnya. Kemudian saya mengaitkan nilai byte abnormal dengan kemunculannya lebih dekat ke awal file data. (Misalnya, dalam dump offset heksadesimal yang ditunjukkan di atas 00000035ada braket yang tepat, diikuti oleh huruf kapital S dan spasi.) Dari sini, saya menghitung skema kompresi yang serupa dengan proses yang dijelaskan dalam artikel. Yang lainnya cukup sederhana.

Tampak bagi saya bahwa seseorang dapat mengambil pelajaran dari ini: tidak ada cara unik untuk memeriksa file data yang tidak dikenal. Setiap alat yang sesuai dengan Anda adalah alat yang tepat untuk rekayasa terbalik.

Pengantar rekayasa terbalik: meretas format data game