Golf Acak Hari Ini # 6: Roll a d20

17

Tentang Seri

Pertama, Anda dapat memperlakukan ini seperti tantangan golf kode lainnya, dan menjawabnya tanpa khawatir tentang seri sama sekali. Namun, ada papan peringkat di semua tantangan. Anda dapat menemukan papan peringkat bersama dengan beberapa informasi lebih lanjut tentang seri di posting pertama .

Meskipun saya memiliki banyak ide untuk seri ini, tantangan di masa depan belum ditetapkan. Jika Anda memiliki saran, beri tahu saya di pos kotak pasir yang relevan .

Lubang 6: Gulung d20

Die yang sangat umum dalam RPG table-top adalah die dua sisi ( icosahedron , umumnya dikenal sebagai d20 ). Adalah tugas Anda untuk melempar dadu seperti itu. Namun, jika Anda baru saja mengembalikan angka acak antara 1 dan 20, itu akan sedikit sepele. Jadi tugas Anda adalah menghasilkan jaring acak untuk cetakan tertentu.

Kami akan menggunakan jaring berikut:

masukkan deskripsi gambar di sini

Ini adalah strip segitiga, sehingga dapat dengan mudah direpresentasikan sebagai daftar bilangan bulat. Misal jika Anda diberi input:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Itu akan sesuai dengan mati berikut (fakta menyenangkan: ini adalah jaring yang digunakan oleh Sihir: penghitung hidup Pengumpul / dadu spin-down).

masukkan deskripsi gambar di sini

Namun, ini bukan satu-satunya jaring yang mewakili dadu ini. Tergantung pada bagaimana kita membuka gulungan wajah, ada 60 jaring yang berbeda. Inilah dua lagi:

[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]

Atau secara grafis (saya tidak memutar label wajah untuk kesederhanaan):

masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini

Tantangan

Diberikan daftar bilangan bulat yang mewakili cetakan (seperti dijelaskan di atas) dan bilangan bulat N, keluaran Nsecara mandiri, jaring d20 acak seragam yang sesuai dengan cetakan yang diberikan. (Yaitu, masing-masing dari 60 kemungkinan jaring harus memiliki probabilitas yang sama untuk dihasilkan.)

Tentu saja, karena keterbatasan teknis PRNG, keseragaman yang sempurna tidak mungkin terjadi. Untuk tujuan menilai keseragaman kiriman Anda, operasi berikut akan dianggap menghasilkan distribusi seragam sempurna:

  • Memperoleh nomor dari PRNG (pada rentang berapa pun), yang didokumentasikan sebagai (kurang-lebih) seragam.
  • Memetakan distribusi seragam pada set angka yang lebih besar ke set yang lebih kecil melalui modulo atau multiplikasi (atau operasi lain yang mendistribusikan nilai secara merata). Set yang lebih besar harus mengandung setidaknya 1024 kali lebih banyak nilai yang mungkin dari set yang lebih kecil.

Dengan asumsi ini, algoritma Anda harus menghasilkan distribusi yang seragam sempurna.

Program Anda harus dapat menghasilkan 100 jaring dalam waktu kurang dari satu detik (jadi jangan coba-coba membuat jaring acak sampai ada yang sesuai dengan cetakan yang diberikan di atas).

Anda dapat menulis suatu program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter fungsi (keluar).

Input dan output mungkin dalam format daftar datar yang nyaman, tidak ambigu. Anda dapat mengasumsikan bahwa nilai wajah dari d20 adalah bilangan bulat positif dan berbeda, yang cocok dengan tipe bilangan bulat alami bahasa Anda.

Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang. Dan tentu saja, pengiriman terpendek per pengguna juga akan masuk ke papan peringkat keseluruhan seri.

Output Sampel

Untuk input

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

60 kemungkinan jaring (asalkan saya tidak melakukan kesalahan), tanpa urutan tertentu, adalah:

[11, 10, 9, 18, 19, 20, 13, 12, 3, 2, 1, 8, 7, 17, 16, 15, 14, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[8, 7, 17, 18, 9, 10, 2, 1, 5, 6, 15, 16, 20, 19, 11, 12, 3, 4, 14, 13]
[3, 12, 13, 14, 4, 5, 1, 2, 10, 11, 19, 20, 16, 15, 6, 7, 8, 9, 18, 17]
[3, 4, 5, 1, 2, 10, 11, 12, 13, 14, 15, 6, 7, 8, 9, 18, 19, 20, 16, 17]
[11, 19, 20, 13, 12, 3, 2, 10, 9, 18, 17, 16, 15, 14, 4, 5, 1, 8, 7, 6]
[4, 14, 15, 6, 5, 1, 2, 3, 12, 13, 20, 16, 17, 7, 8, 9, 10, 11, 19, 18]
[2, 10, 11, 12, 3, 4, 5, 1, 8, 9, 18, 19, 20, 13, 14, 15, 6, 7, 17, 16]
[4, 5, 1, 2, 3, 12, 13, 14, 15, 6, 7, 8, 9, 10, 11, 19, 20, 16, 17, 18]
[10, 2, 1, 8, 9, 18, 19, 11, 12, 3, 4, 5, 6, 7, 17, 16, 20, 13, 14, 15]
[3, 2, 10, 11, 12, 13, 14, 4, 5, 1, 8, 9, 18, 19, 20, 16, 15, 6, 7, 17]
[7, 8, 1, 5, 6, 15, 16, 17, 18, 9, 10, 2, 3, 4, 14, 13, 20, 19, 11, 12]
[13, 12, 11, 19, 20, 16, 15, 14, 4, 3, 2, 10, 9, 18, 17, 7, 6, 5, 1, 8]
[16, 15, 14, 13, 20, 19, 18, 17, 7, 6, 5, 4, 3, 12, 11, 10, 9, 8, 1, 2]
[15, 16, 17, 7, 6, 5, 4, 14, 13, 20, 19, 18, 9, 8, 1, 2, 3, 12, 11, 10]
[20, 13, 12, 11, 19, 18, 17, 16, 15, 14, 4, 3, 2, 10, 9, 8, 7, 6, 5, 1]
[5, 4, 14, 15, 6, 7, 8, 1, 2, 3, 12, 13, 20, 16, 17, 18, 9, 10, 11, 19]
[10, 11, 12, 3, 2, 1, 8, 9, 18, 19, 20, 13, 14, 4, 5, 6, 7, 17, 16, 15]
[4, 3, 12, 13, 14, 15, 6, 5, 1, 2, 10, 11, 19, 20, 16, 17, 7, 8, 9, 18]
[19, 20, 13, 12, 11, 10, 9, 18, 17, 16, 15, 14, 4, 3, 2, 1, 8, 7, 6, 5]
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[8, 1, 5, 6, 7, 17, 18, 9, 10, 2, 3, 4, 14, 15, 16, 20, 19, 11, 12, 13]
[18, 9, 8, 7, 17, 16, 20, 19, 11, 10, 2, 1, 5, 6, 15, 14, 13, 12, 3, 4]
[12, 3, 2, 10, 11, 19, 20, 13, 14, 4, 5, 1, 8, 9, 18, 17, 16, 15, 6, 7]
[2, 3, 4, 5, 1, 8, 9, 10, 11, 12, 13, 14, 15, 6, 7, 17, 18, 19, 20, 16]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
[9, 8, 7, 17, 18, 19, 11, 10, 2, 1, 5, 6, 15, 16, 20, 13, 12, 3, 4, 14]
[16, 17, 7, 6, 15, 14, 13, 20, 19, 18, 9, 8, 1, 5, 4, 3, 12, 11, 10, 2]
[17, 7, 6, 15, 16, 20, 19, 18, 9, 8, 1, 5, 4, 14, 13, 12, 11, 10, 2, 3]
[1, 5, 6, 7, 8, 9, 10, 2, 3, 4, 14, 15, 16, 17, 18, 19, 11, 12, 13, 20]
[9, 18, 19, 11, 10, 2, 1, 8, 7, 17, 16, 20, 13, 12, 3, 4, 5, 6, 15, 14]
[16, 20, 19, 18, 17, 7, 6, 15, 14, 13, 12, 11, 10, 9, 8, 1, 5, 4, 3, 2]
[5, 1, 2, 3, 4, 14, 15, 6, 7, 8, 9, 10, 11, 12, 13, 20, 16, 17, 18, 19]
[8, 9, 10, 2, 1, 5, 6, 7, 17, 18, 19, 11, 12, 3, 4, 14, 15, 16, 20, 13]
[13, 20, 16, 15, 14, 4, 3, 12, 11, 19, 18, 17, 7, 6, 5, 1, 2, 10, 9, 8]
[6, 15, 16, 17, 7, 8, 1, 5, 4, 14, 13, 20, 19, 18, 9, 10, 2, 3, 12, 11]
[6, 5, 4, 14, 15, 16, 17, 7, 8, 1, 2, 3, 12, 13, 20, 19, 18, 9, 10, 11]
[7, 6, 15, 16, 17, 18, 9, 8, 1, 5, 4, 14, 13, 20, 19, 11, 10, 2, 3, 12]
[19, 18, 17, 16, 20, 13, 12, 11, 10, 9, 8, 7, 6, 15, 14, 4, 3, 2, 1, 5]
[14, 15, 6, 5, 4, 3, 12, 13, 20, 16, 17, 7, 8, 1, 2, 10, 11, 19, 18, 9]
[17, 18, 9, 8, 7, 6, 15, 16, 20, 19, 11, 10, 2, 1, 5, 4, 14, 13, 12, 3]
[6, 7, 8, 1, 5, 4, 14, 15, 16, 17, 18, 9, 10, 2, 3, 12, 13, 20, 19, 11]
[14, 13, 20, 16, 15, 6, 5, 4, 3, 12, 11, 19, 18, 17, 7, 8, 1, 2, 10, 9]
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[7, 17, 18, 9, 8, 1, 5, 6, 15, 16, 20, 19, 11, 10, 2, 3, 4, 14, 13, 12]
[15, 6, 5, 4, 14, 13, 20, 16, 17, 7, 8, 1, 2, 3, 12, 11, 19, 18, 9, 10]
[9, 10, 2, 1, 8, 7, 17, 18, 19, 11, 12, 3, 4, 5, 6, 15, 16, 20, 13, 14]
[2, 1, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 17, 18, 19, 20, 13, 14, 15, 16]
[12, 13, 14, 4, 3, 2, 10, 11, 19, 20, 16, 15, 6, 5, 1, 8, 9, 18, 17, 7]
[17, 16, 20, 19, 18, 9, 8, 7, 6, 15, 14, 13, 12, 11, 10, 2, 1, 5, 4, 3]
[18, 17, 16, 20, 19, 11, 10, 9, 8, 7, 6, 15, 14, 13, 12, 3, 2, 1, 5, 4]
[18, 19, 11, 10, 9, 8, 7, 17, 16, 20, 13, 12, 3, 2, 1, 5, 6, 15, 14, 4]
[11, 12, 3, 2, 10, 9, 18, 19, 20, 13, 14, 4, 5, 1, 8, 7, 17, 16, 15, 6]
[15, 14, 13, 20, 16, 17, 7, 6, 5, 4, 3, 12, 11, 19, 18, 9, 8, 1, 2, 10]
[19, 11, 10, 9, 18, 17, 16, 20, 13, 12, 3, 2, 1, 8, 7, 6, 15, 14, 4, 5]
[12, 11, 19, 20, 13, 14, 4, 3, 2, 10, 9, 18, 17, 16, 15, 6, 5, 1, 8, 7]
[20, 16, 15, 14, 13, 12, 11, 19, 18, 17, 7, 6, 5, 4, 3, 2, 10, 9, 8, 1]
[13, 14, 4, 3, 12, 11, 19, 20, 16, 15, 6, 5, 1, 2, 10, 9, 18, 17, 7, 8]
[5, 6, 7, 8, 1, 2, 3, 4, 14, 15, 16, 17, 18, 9, 10, 11, 12, 13, 20, 19]
[14, 4, 3, 12, 13, 20, 16, 15, 6, 5, 1, 2, 10, 11, 19, 18, 17, 7, 8, 9]

Untuk ijaringan lain, cukup ganti setiap kemunculan dengan inomor ke-dalam input (di mana iberbasis 1).

Tantangan Terkait

Papan peringkat

Posting pertama dari seri menghasilkan leaderboard.

Untuk memastikan jawaban Anda muncul, mulailah setiap jawaban dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

## Ruby, <s>104</s> <s>101</s> 96 bytes

(Bahasa saat ini tidak ditampilkan, tetapi cuplikan memang membutuhkan dan menguraikannya, dan saya dapat menambahkan leaderboard berdasarkan bahasa di masa mendatang.)

Martin Ender
sumber
Mengenai diskusi kami, saya telah menambahkan kata "harus" untuk membuatnya lebih jelas. Saya pikir itu menutup celah yang telah saya manfaatkan. Namun, saya pikir pendekatan yang saya gunakan (meskipun tidak valid) menarik.
Level River St
Ini hampir persis seperti pos kotak pasir saya!
Rɪᴋᴇʀ
@RikerW Itulah yang saya pikirkan ketika Anda memasukkannya ke dalam kotak pasir. ;) (Pada saat itu, milik saya langsung di bawah Anda. Saya pikir yang ini mengilhami Anda.) Anda jelas jauh lebih sederhana (yang mungkin merupakan hal yang baik).
Martin Ender
Tidak pernah melihat milikmu. Aneh, saya pikir saya sudah membaca semua yang ada di halaman pertama. Tapi tidak, saya membuat sendiri.
Rɪᴋᴇʀ
Bukankah seharusnya itu berjudul "buka d20"?
Titus

Jawaban:

7

Ruby, 160 byte (rev B)

17 byte disimpan berkat saran dari Martin Büttner.

->a,n{n.times{k=rand 60
%w{ABCD@GHIJKLMNEFPQRSO PFENOSRQHG@DCMLKJIAB GFPQHIA@DENOSRJKBCML}.map{|b|k.times{a=b.chars.map{|i|a[i.ord-64]}}}
k>29&&a.reverse!
p a}}

Ruby, 177 byte (rev A)

->n,a{n.times{k=rand(60)
h=->b{k.times{|j|a=(0..19).map{|i|a[b[i].ord-64]}}}
h['ABCD@GHIJKLMNEFPQRSO']
h['PFENOSRQHG@DCMLKJIAB']
h['GFPQHIA@DENOSRJKBCML']
k>29&&a.reverse!
p a}}

Penjelasan

Dimungkinkan untuk menghasilkan semua orientasi yang mungkin dengan rotasi sekitar satu wajah (3 kali lipat), satu simpul (5 kali lipat) dan dua tepi (2 kali lipat). Tapi bukan sembarang wajah dan ujungnya. Kapak harus memiliki hubungan yang benar dan rotasi harus dilakukan dalam urutan yang benar, atau hal-hal aneh dapat terjadi.

Ini adalah cara saya melakukannya (walaupun saya mengerti Martin melakukannya secara berbeda.)

Semua orientasi tetrahedron dapat dihasilkan oleh kombinasi dari tiga operasi simetri berikut:

a) Rotasi sekitar dua sumbu 2 kali lipat di kanan melalui titik tengah tepi (ini adalah sudut kanan satu sama lain. Jika kita mengalikannya bersama-sama, kita menemukan sumbu 2 kali lipat ketiga melalui sepasang tepi yang tersisa.)

b) Rotasi sekitar sumbu 3 kali lipat diagonal ke sumbu 2 kali lipat, melewati titik dan wajah.

Simetri icosahedron adalah superset dari tetrahedron. Pada gambar di bawah ini dari https://en.wikipedia.org/wiki/Icosahedron , wajah kuning dan wajah merah menentukan dua tetrahedra yang berbeda (atau sebagai alternatif satu oktahedron tunggal), sedangkan tepi yang umum untuk dua wajah biru berada dalam tiga pasangan pada sudut kanan (dan berbaring di wajah kubus.)

Semua orientasi icosahedron dapat dihasilkan oleh operasi simetri yang disebutkan di atas ditambah operasi 5 kali lipat tambahan.

masukkan deskripsi gambar di sini

Rotasi sekitar tiga dari empat sumbu yang disebutkan di atas diwakili oleh string sihir antara '' tanda. Rotasi tentang sumbu 2 kali lipat kedua berbeda, dan dapat dilakukan hanya dengan membalikkan array a[].

Tidak tergabung dalam program uji:

f=->a,n{
  n.times{                     #Iterate n times, using the result from the previous iteration to generate the next
    k=rand(60)                 #pick a random number

    h=->b{                     #helper function taking a string representing a transformation
      k.times{|j|              #which is performed on a using the number of times according to k
        a=(0..19).map{|i|a[b[i].ord-64]}
      }
    }

    #Rotate about axes k times (one 5-fold, one 3-fold, two 2-fold)
    #The first three axes have coprime rotation orders
    #And the rotations themselves take care of the modulus operation so no need to add it.
    #The second 2-fold rotation is equivalent to reversing the order
    #And is applied to the last 30 numbers as it is not coprime with the first 2-fold rotation.

    h['ABCD@GHIJKLMNEFPQRSO']  #rotate k times about 5-fold axis
    h['PFENOSRQHG@DCMLKJIAB']  #rotate k times about 3-fold axis
    h['GFPQHIA@DENOSRJKBCML']  #rotate k times about 2-fold axis
    k>29&&a.reverse!
    p a
  }
}

z=(1..20).map{|i|i} 
f[z,50]

Solusi alternatif 131 byte (Tidak valid karena pendekatan biner acak berjalan, hanya memberikan distribusi yang kira-kira benar.)

->a,n{(n*99).times{|i|s=['@DEFGHIABCMNOPQRJKLS','ABCD@GHIJKLMNEFPQRSO'][rand(2)] 
a=(0..19).map{|i|a[s[i].ord-64]}
i%99==98&&p(a)}}

Ini adalah perebutan (sangat mirip dengan program yang digunakan untuk mengacak kubus rubik.)

Rotasi spesifik yang saya gunakan adalah dua yang paling jelas:

-Sebuah rotasi 120 derajat (sekitar wajah 1 dan 20 per diagram pertama)

-Sebuah rotasi 72 derajat (tentang simpul-simpulnya yang umum hingga 1,2,3,4,5 dan 16,17,18,19,20 per diagram pertama.)

kita membalik koin 99 kali, dan setiap kali kita melakukan salah satu dari dua rotasi ini tergantung apakah itu kepala atau ekor.

Perhatikan bahwa bergantian secara deterministik mengarah ke urutan yang cukup singkat. Misalnya, dengan indra rotasi yang benar, rotasi 180 derajat dapat diproduksi dengan periode hanya 2.

Level River St
sumber
Sepertinya membalik koin untuk memilih operasi akan menghasilkan sesuatu yang lebih dekat ke distribusi binomial daripada distribusi seragam.
Sparr
@ Parr itu yang akan terjadi jika ruang negara lebih besar dari jalan acak. Tetapi dalam kasus ini jalan acak hanya 6 langkah dapat membuka sebanyak 2 ^ 6 = 64 kemungkinan (saya belum menghitungnya), dan ruang keadaan kita hanya 60. Setelah 99 langkah (2 ^ 99 jalur yang berbeda) semuanya harus sekurang-kurangnya sama terdistribusi dengan sampel tunggal PRNG yang digunakan untuk menghasilkan angka-angka.
Level River St
@ MartinBüttner Terima kasih atas tipsnya, saya sudah menerapkan yang berfungsi. b.maptidak bekerja secara langsung, saya harus b.chars.mapmembuatnya bekerja (BTW yang tidak bekerja di mesin saya karena saya memiliki Ruby 1.9.3 tetapi bekerja pada Ideone.) Ini adalah penghematan yang adil. Saya tidak berpikir mengubah string ajaib untuk karakter yang tidak dapat dicetak untuk menyimpan surat -64wasiat akan berfungsi: %w{}interprets \n(dan juga spasi) sebagai pemisah antara string dalam array yang dihasilkan. Saya tidak tahu apa yang akan dilakukan dengan karakter ASCII lainnya yang tidak dapat dicetak.
Level River St
@ Martin, ini lebih sulit daripada yang saya harapkan - pada awalnya saya bingung ketika kode saya tidak berfungsi dengan baik, kemudian saya beristirahat dan tiba-tiba menyadari bahwa simetri 2 kali lipat dan 3 kali lipat harus memiliki hubungan timbal balik yang sama seperti pada tetrahedron (saya harus mengubah wajah segitiga yang saya putar untuk wajah segitiga yang berbeda).
Level River St
1
Selamat menjadi pengguna pertama dengan lencana geometri yang baru dibuka . :)
Martin Ender
2

Kode mesin IA-32, 118 byte

Hexdump:

60 33 c0 51 8b 74 24 28 8b fa 6a 05 59 f3 a5 e8
21 00 00 00 20 c4 61 cd 6a 33 00 84 80 ad a8 33
32 00 46 20 44 8e 48 61 2d 2c 33 32 4a 00 21 20
a7 a2 90 8c 00 5b b1 04 51 0f c7 f1 83 e1 1f 49
7e f7 51 8b f2 56 8d 7c 24 e0 b1 14 f3 a4 5f 8b
f3 ac 8b ee d4 20 86 cc e3 0a 56 8d 74 04 e0 f3
a4 5e eb ed 59 e2 db 8b dd 59 e2 cc 59 83 c2 14
e2 91 61 c2 04 00

Agak panjang, jadi beberapa penjelasan masuk dulu. Aku digunakan hampir algoritma yang sama seperti yang ada jawaban dengan Tingkat Sungai St . Untuk membuat jawaban saya berbeda, saya mengambil permutasi dasar lainnya, yang tidak selalu memiliki makna geometris intuitif, tetapi entah bagaimana lebih nyaman.

Kode pada dasarnya harus menghasilkan permutasi, yang merupakan aplikasi berurutan dari yang berikut:

  1. Permutasi order 3, yang saya sebut p3, diterapkan 0 ... 2 kali
  2. Permutasi pesanan 2, yang saya sebut q2, diterapkan 0 atau 1 kali
  3. Permutasi pesanan 5, yang saya sebut p5, diterapkan 0 ... 4 kali
  4. Permutasi pesanan 2 lainnya, yang saya sebut p2, diterapkan 0 atau 1 kali

Ada banyak pilihan yang memungkinkan untuk permutasi ini. Salah satunya adalah sebagai berikut:

p3 = [0   4   5   6   7   8   9   1   2   3  13  14  15  16  17  18  10  11  12  19]
q2 = [4   5   6   7   0   1   2   3  13  14  15  16  17   8   9  10  11  12  19  18]
p5 = [6   7   0   4   5  14  15  16  17   8   9   1   2   3  13  12  19  18  10  11]
p2 = [1   0   7   8   9  10  11   2   3   4   5   6  16  17  18  19  12  13  14  15]

Pilihan ini lebih baik daripada yang lain karena permutasi di sini memiliki jangka panjang indeks berurutan, yang dapat dikompresi dengan pengkodean run-length - hanya 29 byte untuk 4 permutasi.

Untuk menyederhanakan generasi bilangan acak, saya memilih kekuatan (berapa kali setiap permutasi diterapkan) dalam kisaran 1 ... 30 untuk semuanya. Hal ini menyebabkan banyak pekerjaan tambahan dalam kode, karena misalnya p3menjadi permutasi identitas setiap kali dikalikan dengan sendirinya 3 kali. Namun, kode lebih kecil seperti itu, dan selama rentang dibagi 30, output akan memiliki distribusi yang seragam.

Juga, kekuatan harus positif sehingga operasi pendekodean run-length dilakukan setidaknya sekali.

Kode ini memiliki 4 loop bersarang; garis besarnya seperti ini:

void doit(int n, uint8_t* output, const uint8_t input[20])
{    
    uint8_t temp[20];

    n_loop: for i_n = 0 ... n
    {
        memcpy(output, input, 20);
        expr_loop: for i_expr = 0 ... 3
        {
            power = rand(1 ... 30);
            power_loop: for i_power = 0 ... power
            {
                memcpy(temp, output, 20);
                output_index = 0;
                perm_loop: do while length > 0
                {
                    index = ...; // decode it
                    length = ...; // decode it
                    memcpy(output + output_index, temp + index, length);
                    output_index += length;
                }
            }
        }
        output += 20;
    }
}

Saya harap kode semu ini lebih jelas daripada kode inline-assembly di bawah ini.

_declspec(naked) void __fastcall doit(int n, uint8_t* output, const uint8_t* input)
{
    _asm {
        pushad
        xor eax, eax

        n_loop:
            push ecx

            ; copy from input to output
            mov esi, [esp + 0x28]
            mov edi, edx
            push 5
            pop ecx
            rep movsd

            call end_of_data
#define rl(index, length) _emit(length * 32 + index)
            rl(0, 1)
            rl(4, 6)
            rl(1, 3)
            rl(13, 6)
            rl(10, 3)
            rl(19, 1)
            _emit(0)

            rl(4, 4)
            rl(0, 4)
            rl(13, 5)
            rl(8, 5)
            rl(19, 1)
            rl(18, 1)
            _emit(0)

            rl(6, 2)
            rl(0, 1)
            rl(4, 2)
            rl(14, 4)
            rl(8, 2)
            rl(1, 3)
            rl(13, 1)
            rl(12, 1)
            rl(19, 1)
            rl(18, 1)
            rl(10, 2)
            _emit(0)

            rl(1, 1)
            rl(0, 1)
            rl(7, 5)
            rl(2, 5)
            rl(16, 4)
            rl(12, 4)
            _emit(0)

            end_of_data:
            pop ebx ; load the address of the encoded data
            mov cl, 4

            expr_loop:
                push ecx

                make_rand:
                rdrand ecx
                and ecx, 31
                dec ecx
                jle make_rand

                ; input: ebx => encoding of permutation
                ; output: ebp => encoding of next permutation
                power_loop:
                    push ecx

                    ; copy from output to temp
                    mov esi, edx
                    push esi
                    lea edi, [esp - 0x20]
                    mov cl, 20
                    rep movsb
                    pop edi

                    ; ebx => encoding of permutation
                    ; edi => output
                    mov esi, ebx
                    perm_loop:
                        ; read a run-length
                        lodsb
                        mov ebp, esi

                        _emit(0xd4)             ; divide by 32, that is, split into
                        _emit(32)               ; index (al) and length (ah)
                        xchg cl, ah             ; set ecx = length; also makes eax = al
                        jecxz perm_loop_done    ; zero length => done decoding
                        push esi
                        lea esi, [esp + eax - 0x20]
                        rep movsb
                        pop esi
                        jmp perm_loop

                    perm_loop_done:
                    pop ecx
                    loop power_loop

                mov ebx, ebp
                pop ecx
                loop expr_loop

            pop ecx
            add edx, 20
            loop n_loop

        popad
        ret 4
    }
}

Beberapa detail implementasi yang menyenangkan:

  • Saya menggunakan perakitan indentasi, seperti dalam bahasa tingkat tinggi; jika tidak kode akan berantakan
  • Saya menggunakan calldan selanjutnya popuntuk mengakses data (permutasi yang dikodekan) yang disimpan dalam kode
  • The jecxzinstruksi nyaman memungkinkan saya menggunakan byte nol sebagai terminasi untuk proses decoding run-length
  • Untungnya, angka 30 (2 * 3 * 5) hampir merupakan kekuatan 2. Ini memungkinkan saya menggunakan kode pendek untuk menghasilkan angka dalam kisaran 1 ... 30:

            and ecx, 31
            dec ecx
            jle make_rand
    
  • Saya menggunakan instruksi "pembagian tujuan umum" ( aam) untuk memisahkan byte ke dalam bidang bit (panjang 3-bit dan indeks 5-bit); oleh keberuntungan, pada posisi itu dalam kode cl = 0,, jadi saya mendapat manfaat dari kedua "sisi" darixchg

anatolyg
sumber