Golf aleatorio del día # 6: Tira un d20

17

Sobre la serie

En primer lugar, puede tratar esto como cualquier otro desafío de golf de código y responderlo sin preocuparse por la serie. Sin embargo, hay una tabla de clasificación en todos los desafíos. Puede encontrar la tabla de clasificación junto con más información sobre la serie en la primera publicación .

Aunque tengo un montón de ideas alineadas para la serie, los desafíos futuros aún no están establecidos en piedra. Si tiene alguna sugerencia, hágamelo saber en la publicación de sandbox relevante .

Hoyo 6: Tira un d20

Un dado muy común en los juegos de rol de mesa es el dado de veinte lados (un icosaedro , comúnmente conocido como d20 ). Es tu tarea tirar un dado. Sin embargo, si solo estuviera devolviendo un número aleatorio entre 1 y 20, eso sería un poco trivial. Entonces su tarea es generar una red aleatoria para un dado dado.

Utilizaremos la siguiente red:

ingrese la descripción de la imagen aquí

Es una franja triangular, por lo que se puede representar fácilmente como una lista de enteros. Por ejemplo, si le dan la entrada:

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

Eso correspondería al siguiente dado (hecho divertido: esta es la red utilizada por Magic: the Gathering contadores de vida / dados de spin-down).

ingrese la descripción de la imagen aquí

Sin embargo, esta no es la única red que representa este dado. Dependiendo de cómo desenrollemos las caras, hay 60 redes diferentes. Aquí hay dos más:

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

O gráficamente (no roté las etiquetas de la cara por simplicidad):

ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

El reto

Dada una lista de enteros que representan un dado (como se describió anteriormente) y un entero N, se obtienen de forma Nindependiente, redes d20 uniformemente aleatorias correspondientes al dado dado. (Es decir, cada una de las 60 redes posibles debería tener la misma probabilidad de ser generada).

Por supuesto, debido a las limitaciones técnicas de los PRNG, será imposible una uniformidad perfecta. Para evaluar la uniformidad de su envío, se considerará que las siguientes operaciones producen distribuciones perfectamente uniformes:

  • Obtener un número de un PRNG (sobre cualquier rango), que está documentado como (aproximadamente) uniforme.
  • Mapear una distribución uniforme sobre un conjunto más grande de números en un conjunto más pequeño mediante módulo o multiplicación (o alguna otra operación que distribuya valores de manera uniforme). El conjunto más grande tiene que contener al menos 1024 veces tantos valores posibles como el conjunto más pequeño.

Dados estos supuestos, su algoritmo debe producir una distribución perfectamente uniforme.

Su programa debería ser capaz de generar 100 redes en menos de un segundo (por lo tanto, no intente generar redes aleatorias hasta que una corresponda con el dado indicado anteriormente).

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

La entrada y salida pueden estar en cualquier formato de lista plana conveniente, inequívoco. Puede suponer que los valores faciales de d20 son enteros distintos y positivos, que se ajustan al tipo de entero natural de su idioma.

Este es el código de golf, por lo que gana el envío más corto (en bytes). Y, por supuesto, la presentación más corta por usuario también entrará en la tabla de clasificación general de la serie.

Resultados de muestra

Para la entrada

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

Las 60 redes posibles (siempre que no haya cometido un error), sin ningún orden en particular, son:

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

Para cualquier otra red, simplemente reemplace cada aparición de icon el inúmero th en la entrada (donde iestá basado en 1).

Desafíos relacionados

Tabla de clasificación

La primera publicación de la serie genera una tabla de clasificación.

Para asegurarse de que sus respuestas aparezcan, comience cada respuesta con un título, utilizando la siguiente plantilla de Markdown:

## Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

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

(El idioma no se muestra actualmente, pero el fragmento sí lo requiere y analiza, y puedo agregar una tabla de clasificación por idioma en el futuro).

code-golf geometry random permutations abstract-algebra Martin Ender
fuente
Con respecto a nuestra discusión, he agregado la palabra "must" para hacerlo más claro. Creo que eso cierra el vacío que he estado aprovechando. Aún así, creo que el enfoque que utilicé (aunque no válido) es interesante.
Level River St
¡Esto es casi exactamente como mi publicación de sandbox!
Rɪᴋᴇʀ
@RikerW Eso es lo que pensé cuando lo protegiste. ;) (En ese momento, el mío estaba directamente debajo del tuyo. Pensé que este inspiró el tuyo). Sin embargo, el tuyo es obviamente mucho más simple (lo que probablemente sea algo bueno).
Martin Ender
Nunca vi el tuyo. Eso es raro, pensé que leí todos los de la primera página. Pero no, hice el mío independientemente.
Rɪᴋᴇʀ
¿No debería titularse "desplegar un d20"?
Tito el

Respuestas:

7

Ruby, 160 bytes (rev B)

17 bytes guardados gracias a las sugerencias 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 bytes (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}}

Explicación

Es posible generar todas las orientaciones posibles mediante rotaciones alrededor de una cara (3 veces), un vértice (5 veces) y dos bordes (2 veces). Pero no solo cualquier cara y bordes. Los ejes deben tener la relación correcta y las rotaciones deben hacerse en el orden correcto, o pueden suceder cosas extrañas.

Así es como lo hice (aunque entiendo que Martin lo hizo de manera diferente).

Todas las orientaciones de un tetraedro se pueden generar mediante combinaciones de las siguientes tres operaciones de simetría:

a) Rotación alrededor de dos ejes de 2 pliegues a la derecha a través de los puntos medios de los bordes (estos están en ángulo recto entre sí. Si los multiplicamos juntos descubrimos un tercer eje de 2 pliegues a través del par de bordes restante).

b) Rotación sobre un eje de 3 pliegues diagonal a los ejes de 2 pliegues, pasando a través de un vértice y una cara.

La simetría del icosaedro es un superconjunto de la del tetraedro. En la imagen a continuación de https://en.wikipedia.org/wiki/Icosahedron , las caras amarillas y rojas definen dos tetraedros diferentes (o, alternativamente, un solo octaedro), mientras que los bordes comunes a dos caras azules están en tres pares en ángulos rectos (y recostarse sobre las caras de un cubo).

Todas las orientaciones del icosaedro pueden generarse mediante las operaciones de simetría mencionadas anteriormente más una operación adicional de 5 veces.

ingrese la descripción de la imagen aquí

Las rotaciones alrededor de tres de los cuatro ejes mencionados anteriormente están representadas por las cadenas mágicas entre las ''marcas. La rotación sobre el segundo eje doble es diferente, y se puede hacer simplemente invirtiendo la matriza[] .

Sin golf en el programa de prueba:

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]

Solución alternativa 131 bytes (inválida debido al enfoque de paseo aleatorio binario, solo da una distribución aproximadamente correcta).

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

Esta es una codificación (al igual que los programas utilizados para codificar el cubo de Rubik).

Las rotaciones específicas que uso son dos de las más obvias:

-Una rotación de 120 grados (alrededor de las caras 1 y 20 según el primer diagrama)

-Una rotación de 72 grados (sobre los vértices comunes a 1,2,3,4,5 y 16,17,18,19,20 según el primer diagrama).

Lanzamos una moneda 99 veces, y cada vez que realizamos una de estas dos rotaciones dependiendo de si es cara o cruz.

Tenga en cuenta que alternar estos determinísticamente conduce a secuencias bastante cortas. Por ejemplo, con los sentidos de rotación correctos, se puede producir una rotación de 180 grados con un período de solo 2.

Level River St
fuente
Parece que lanzar una moneda para elegir una operación va a producir algo más cercano a una distribución binomial que a una distribución uniforme.
Sparr
@Sparr ese sería el caso si el espacio de estado fuera más grande que la caminata aleatoria. Pero en este caso, una caminata aleatoria de solo 6 pasos puede abrir hasta 2 ^ 6 = 64 posibilidades (no las he contado), y nuestro espacio de estado es solo 60. Después de 99 pasos (2 ^ 99 caminos diferentes) todo debería estar al menos tan uniformemente distribuido como una sola muestra de PRNG utilizada para generar los números.
Level River St
@ MartinBüttner Gracias por los consejos, he aplicado los que funcionan. b.mapno funciona directamente, necesito b.chars.maphacerlo funcionar (por cierto que no funciona en mi máquina ya que tengo Ruby 1.9.3 pero funciona en Ideone). Es un ahorro justo. No creo que cambiar las cadenas mágicas de los caracteres no imprimibles para guardar -64funcionará: %w{}interpreta \n(así como el espacio) como un separador entre las cadenas en la matriz generada. No tengo idea de lo que hará con otros caracteres ASCII no imprimibles.
Level River St
@Martin esto fue más difícil de lo que esperaba: al principio me desconcerté cuando mi código no funcionó correctamente, luego me tomé un descanso y de repente me di cuenta de que las simetrías doble y triple tenían que tener la misma relación mutua que en un tetraedro (tuve que cambiar la cara triangular que estaba rotando por una cara triangular diferente.)
Level River St
1
Felicidades por ser el primer usuario con la insignia de geometría recién desbloqueada . :)
Martin Ender
2

Código de máquina IA-32, 118 bytes

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

Es un poco largo, por lo que algunas explicaciones van primero. Solía casi el mismo algoritmo que el vigente respuesta según el nivel del río St . Para que mi respuesta sea diferente, tomé otras permutaciones básicas, que no necesariamente tienen un significado geométrico intuitivo, pero de alguna manera son más convenientes.

El código básicamente tiene que generar una permutación, que es una aplicación secuencial de lo siguiente:

  1. Una permutación de orden 3, que llamo p3, aplicada 0 ... 2 veces
  2. Una permutación de orden 2, que llamo q2, aplicada 0 o 1 veces
  3. Una permutación de orden 5, que llamo p5, se aplica 0 ... 4 veces
  4. Otra permutación de orden 2, que llamo p2, se aplica 0 o 1 veces

Hay muchas opciones posibles para estas permutaciones. Uno de ellos es el siguiente:

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]

Esta opción es mejor que otras porque las permutaciones aquí tienen largas series de índices secuenciales, que se pueden comprimir mediante codificación de longitud de ejecución: solo 29 bytes para las 4 permutaciones.

Para simplificar la generación de números aleatorios, elegí los poderes (cuántas veces se aplica cada permutación) en el rango 1 ... 30 para todos ellos. Esto lleva a mucho trabajo adicional en el código, porque, por ejemplo, se p3convierte en una permutación de identidad cada vez que se multiplica por sí mismo 3 veces. Sin embargo, el código es más pequeño de esa manera, y siempre que el rango sea divisible por 30, la salida tendrá una distribución uniforme.

Además, las potencias deben ser positivas para que la operación de decodificación de longitud de ejecución se realice al menos una vez.

El código tiene 4 bucles anidados; El esquema es así:

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

Espero que este pseudocódigo sea más claro que el código de ensamblaje en línea a continuación.

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

Algunos detalles divertidos de implementación:

  • Usé ensamblaje sangrado, como en lenguajes de alto nivel; de lo contrario, el código sería un desastre incomprensible
  • Yo uso cally luego poppara acceder a los datos (permutaciones codificadas) almacenados en el código
  • La jecxzinstrucción convenientemente me permite usar un byte cero como terminación para el proceso de decodificación de longitud de ejecución

  • Por suerte, el número 30 (2 * 3 * 5) es casi una potencia de 2. Esto me permite usar un código corto para generar un número en el rango 1 ... 30:

            and ecx, 31
        dec ecx
        jle make_rand

  • Utilizo una instrucción de "división de propósito general" ( aam) para separar un byte en campos de bits (longitud de 3 bits e índice de 5 bits); por suerte, en esa posición en el código cl = 0, así que me beneficio de ambos "lados" dexchg

anatolyg
fuente