Golf aléatoire du jour # 6: lancez un d20

17

À propos de la série

Tout d'abord, vous pouvez traiter cela comme n'importe quel autre défi de golf de code et y répondre sans vous soucier de la série. Cependant, il existe un classement pour tous les défis. Vous pouvez trouver le classement avec plus d'informations sur la série dans le premier post .

Bien que j'ai un tas d'idées alignées pour la série, les défis futurs ne sont pas encore gravés dans le marbre. Si vous avez des suggestions, faites-le moi savoir sur le post sandbox correspondant .

Trou 6: Rouler un d20

Un dé très courant dans les RPG de table est le dé à vingt faces (un icosaèdre , communément appelé d20 ). C'est votre tâche de lancer un tel dé. Cependant, si vous retourniez simplement un nombre aléatoire entre 1 et 20, ce serait un peu trivial. Votre tâche consiste donc à générer un filet aléatoire pour un dé donné.

Nous utiliserons le filet suivant:

entrez la description de l'image ici

C'est une bande triangulaire, elle peut donc être facilement représentée sous forme de liste d'entiers. Par exemple, si vous recevez l'entrée:

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

Cela correspondrait au dé suivant (fait amusant: il s'agit du filet utilisé par Magic: les compteurs de vie Gathering / dés dés).

entrez la description de l'image ici

Cependant, ce n'est pas le seul filet représentant ce dé. Selon la façon dont nous déroulons les visages, il existe 60 filets différents. En voici deux autres:

[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]

Ou graphiquement (je n'ai pas fait pivoter les étiquettes des visages pour plus de simplicité):

entrez la description de l'image ici entrez la description de l'image ici

Le défi

Etant donné une liste d'entiers représentant un dé (comme décrit ci-dessus) et un entier N, sortir Nindépendamment, des réseaux d20 uniformément aléatoires correspondant au dé donné. (Autrement dit, chacun des 60 réseaux possibles devrait avoir la même probabilité d'être généré.)

Bien sûr, en raison des limites techniques des PRNG, une parfaite uniformité sera impossible. Aux fins d'évaluer l'uniformité de votre soumission, les opérations suivantes seront considérées comme produisant des distributions parfaitement uniformes:

  • Obtention d'un numéro d'un PRNG (sur n'importe quelle plage), qui est documenté comme étant (approximativement) uniforme.
  • Mapper une distribution uniforme sur un ensemble de nombres plus grand sur un ensemble plus petit via modulo ou multiplication (ou une autre opération qui distribue les valeurs uniformément). L'ensemble plus grand doit contenir au moins 1024 fois autant de valeurs possibles que l'ensemble plus petit.

Compte tenu de ces hypothèses, votre algorithme doit produire une distribution parfaitement uniforme.

Votre programme devrait être capable de générer 100 réseaux en moins d'une seconde (alors n'essayez pas de générer des réseaux aléatoires jusqu'à ce qu'un corresponde au dé donné ci-dessus).

Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), la valeur de retour de la fonction ou le paramètre de la fonction (out).

L'entrée et la sortie peuvent être dans n'importe quel format de liste plat pratique et sans ambiguïté. Vous pouvez supposer que les valeurs faciales du d20 sont des entiers positifs distincts, qui correspondent au type d'entier naturel de votre langue.

Il s'agit du code golf, donc la soumission la plus courte (en octets) l'emporte. Et bien sûr, la soumission la plus courte par utilisateur entrera également dans le classement général de la série.

Exemples de sorties

Pour l'entrée

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

Les 60 filets possibles (à condition que je ne me sois pas trompé), sans ordre particulier, sont:

[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]

Pour tout autre réseau, remplacez simplement chaque occurrence de ipar le inuméro e dans l'entrée (où iest basé sur 1).

Défis liés

Classement

Le premier post de la série génère un classement.

Pour vous assurer que vos réponses s'affichent, veuillez commencer chaque réponse par un titre, en utilisant le modèle Markdown suivant:

## Language Name, N bytes

Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les barrant. Par exemple:

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

(La langue n'est pas actuellement affichée, mais l'extrait de code l'exige et l'analyse, et je pourrai ajouter un classement par langue à l'avenir.)

Martin Ender
la source
Concernant notre discussion, j'ai ajouté le mot "must" pour le rendre plus clair. Je pense que cela comble la faille dont je profite. Pourtant, je pense que l'approche que j'ai utilisée (bien que non valide) est intéressante.
Level River St
C'est presque exactement comme mon post sandbox!
Rɪᴋᴇʀ
@RikerW C'est ce que je pensais quand tu l'as mis en sandbox. ;) (À l'époque, le mien était directement en dessous du vôtre. Je pensais que celui-ci vous inspirait.) Le vôtre est évidemment beaucoup plus simple (ce qui est probablement une bonne chose).
Martin Ender
Je n'ai jamais vu le vôtre. C'est bizarre, je pensais avoir lu tous ceux de la première page. Mais non, j'ai fait le mien indépendamment.
Rɪᴋᴇʀ
Cela ne devrait-il pas être intitulé "déplier un d20"?
Titus

Réponses:

7

Ruby, 160 octets (rév B)

17 octets économisés grâce aux suggestions de 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 octets (rév 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}}

Explication

Il est possible de générer toutes les orientations possibles par des rotations autour d'une face (3 fois), d'un sommet (5 fois) et de deux bords (2 fois). Mais pas n'importe quel visage et bords. Les axes doivent avoir la bonne relation et les rotations doivent être effectuées dans le bon ordre, sinon des choses étranges peuvent se produire.

C'est ainsi que je l'ai fait (même si je comprends que Martin l'a fait différemment.)

Toutes les orientations d'un tétraèdre peuvent être générées par des combinaisons des trois opérations de symétrie suivantes:

a) Rotation autour de deux axes 2 fois à droite à travers les points médians des bords (ceux-ci sont à angle droit l'un par rapport à l'autre. Si nous les multiplions ensemble, nous découvrons un troisième axe 2 fois à travers la paire restante d'arêtes.)

b) Rotation autour d'un axe 3 fois diagonal aux axes 2 fois, passant par un sommet et une face.

La symétrie de l'icosaèdre est un sur-ensemble de celle du tétraèdre. Dans l'image ci-dessous de https://en.wikipedia.org/wiki/Icosaèdre , les faces jaunes et rouges définissent deux tétraèdres différents (ou alternativement un seul octaèdre), tandis que les bords communs à deux faces bleues sont en trois paires à angles droits (et se trouvent sur les faces d'un cube.)

Toutes les orientations de l'icosaèdre peuvent être générées par les opérations de symétrie mentionnées ci-dessus plus une opération supplémentaire de 5 fois.

entrez la description de l'image ici

Les rotations d'environ trois des quatre axes mentionnés ci-dessus sont représentées par les cordes magiques entre les ''marques. La rotation autour du deuxième axe double est différente et peut être effectuée simplement en inversant le réseau a[].

Non testé dans le programme de test:

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]

Solution alternative 131 octets (invalide en raison de l'approche de marche aléatoire binaire, ne donne qu'une distribution approximativement correcte.)

->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)}}

Ceci est un brouillage (un peu comme les programmes utilisés pour brouiller le cube de rubik.)

Les rotations spécifiques que j'utilise sont deux des plus évidentes:

-Une rotation de 120 degrés (autour des faces 1 et 20 selon le premier diagramme)

-Une rotation de 72 degrés (autour des sommets communs à 1,2,3,4,5 et 16,17,18,19,20 selon le premier diagramme.)

nous retournons une pièce 99 fois, et chaque fois que nous effectuons l'une de ces deux rotations selon qu'il s'agit de têtes ou de queues.

Notez que l'alternance de ces éléments conduit à des séquences assez courtes. Par exemple, avec les bons sens de rotation, une rotation de 180 degrés peut être produite avec une période de seulement 2.

Level River St
la source
Il semble que lancer une pièce pour choisir une opération va produire quelque chose de plus proche d'une distribution binomiale qu'une distribution uniforme.
Sparr
@Sparr ce serait le cas si l'espace d'état était plus grand que la marche aléatoire. Mais dans ce cas, une marche aléatoire de seulement 6 étapes peut ouvrir jusqu'à 2 ^ 6 = 64 possibilités (je ne les ai pas comptées), et notre espace d'état n'est que de 60. Après 99 étapes (2 ^ 99 chemins différents) tout doit être au moins aussi uniformément distribué qu'un seul échantillon du PRNG utilisé pour générer les nombres.
Level River St
@ MartinBüttner Merci pour les conseils, j'ai appliqué ceux qui fonctionnent. b.mapne fonctionne pas directement, je dois b.chars.maple faire fonctionner (BTW qui ne fonctionne pas sur ma machine car j'ai Ruby 1.9.3 mais il fonctionne sur Ideone.) C'est une bonne économie. Je ne pense pas que changer les chaînes magiques pour les caractères non imprimables pour enregistrer la -64volonté fonctionnera: %w{}interprète \n(ainsi que l'espace) comme séparateur entre les chaînes dans le tableau généré. Je n'ai aucune idée de ce qu'il fera avec les autres caractères ASCII non imprimables.
Level River St
@Martin, c'était plus difficile que ce à quoi je m'attendais - au début, j'étais déconcerté quand mon code ne fonctionnait pas correctement, puis j'ai pris une pause et j'ai soudainement réalisé que les symétries 2 et 3 fois devaient avoir la même relation mutuelle que sur un tétraèdre (j'ai dû changer la face triangulaire autour de laquelle je tournais pour une autre face triangulaire.)
Level River St
1
Félicitations d'être le premier utilisateur avec le badge de géométrie nouvellement déverrouillé . :)
Martin Ender
2

Code machine IA-32, 118 octets

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

C'est un peu long, donc certaines explications vont d'abord. Je presque le même algorithme que l'actuel réponse par niveau de la rivière St . Pour rendre ma réponse différente, j'ai pris d'autres permutations de base, qui n'ont pas nécessairement une signification géométrique intuitive, mais qui sont en quelque sorte plus pratiques.

Le code doit essentiellement générer une permutation, qui est une application séquentielle des éléments suivants:

  1. Une permutation d'ordre 3, que j'appelle p3, appliquée 0 ... 2 fois
  2. Une permutation d'ordre 2, que j'appelle q2, appliquée 0 ou 1 fois
  3. Une permutation d'ordre 5, que j'appelle p5, appliquée 0 ... 4 fois
  4. Une autre permutation d'ordre 2, que j'appelle p2, appliquée 0 ou 1 fois

Il existe de nombreux choix possibles pour ces permutations. L'un d'eux est le suivant:

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]

Ce choix est meilleur que d'autres parce que les permutations ici ont de longues séries d'index séquentiels, qui peuvent être compressées par un codage de longueur d'exécution - seulement 29 octets pour les 4 permutations.

Pour simplifier la génération de nombres aléatoires, j'ai choisi les puissances (combien de fois chaque permutation est appliquée) dans la plage 1 ... 30 pour chacune d'elles. Cela entraîne beaucoup de travail supplémentaire dans le code, car par exemple p3devient une permutation d'identité à chaque fois qu'il est multiplié par lui-même 3 fois. Cependant, le code est plus petit de cette façon et tant que la plage est divisible par 30, la sortie aura une distribution uniforme.

De plus, les puissances doivent être positives pour que l'opération de décodage de longueur soit effectuée au moins une fois.

Le code a 4 boucles imbriquées; le contour est comme ceci:

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;
    }
}

J'espère que ce pseudo-code est plus clair que le code d'assemblage en ligne ci-dessous.

_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
    }
}

Quelques détails d'implémentation amusants:

  • J'ai utilisé l'assemblage en retrait, comme dans les langages de haut niveau; sinon le code serait un gâchis incompréhensible
  • J'utilise callet ensuite poppour accéder aux données (permutations codées) stockées dans le code
  • L' jecxzinstruction me permet commodément d'utiliser un octet zéro comme terminaison pour le processus de décodage de longueur
  • Par chance, le nombre 30 (2 * 3 * 5) est presque une puissance de 2. Cela me permet d'utiliser un code court pour générer un nombre compris entre 1 et 30:

            and ecx, 31
            dec ecx
            jle make_rand
    
  • J'utilise une instruction "division à usage général" ( aam) pour séparer un octet en champs de bits (longueur 3 bits et index 5 bits); par chance, à cette position dans le code cl = 0, donc je profite des deux "côtés" dexchg

anatolyg
la source