algorithm - Generador pseudoaleatorio en lenguaje ensamblador

assembly prng

Question

Necesito un algoritmo generador de números pseudoaleatorios para un programa ensamblador asignado en un curso, y preferiría un algoritmo simple. Sin embargo, no puedo usar una biblioteca externa.

¿Qué es un buen algoritmo de generador de números pseudoaleatorio para el ensamblaje?

Answer 1

@jjrv
Lo que estás describiendo es en realidad un generador congrencial lineal. Los bits más aleatorios son los bits más altos. Para obtener un número de 0..N-1, multiplique el valor completo por N (32 bits por 32 bits, dando 64 bits) y use los 32 bits altos.

No debe usar cualquier número para a (el multiplicador para pasar de un valor completo al siguiente), los números recomendados en Knuth (Tabla 1, sección 3.3.4, TAOCP vol 2 1981) son 1812433253, 1566083941, 69069 y 1664525.

Puedes simplemente elegir cualquier número impar para b . (la adicion).

Answer 2

El volumen 2 de El arte de la programación de computadoras tiene mucha información sobre la generación de números pseudoaleatorios. Los algoritmos se muestran en ensamblador, por lo que puede ver por usted mismo cuáles son los más simples en ensamblador.

Sin embargo, si puede vincular a una biblioteca externa o archivo de objeto, esa sería su mejor opción. Entonces podrías vincular, por ejemplo, a Mersenne Twister .

Tenga en cuenta que la mayoría de los generadores de números pseudoaleatorios no son seguros para la criptografía, por lo que si necesita una generación segura de números aleatorios, debe mirar más allá de los algoritmos básicos (y probablemente debería recurrir a las API criptográficas específicas del sistema operativo).

Answer 3

Fácil es simplemente elegir dos grandes primos relativos a y b, luego seguir multiplicando su número aleatorio por ay agregar b. Utilice el operador de módulo para mantener los bits bajos como su número aleatorio y mantenga el valor completo para la siguiente iteración.

Este algoritmo se conoce como el generador congruente lineal .

Answer 4

Los PRNG lineales congruentes (X = AX + C mod M) pueden ser buenos para asignarlos a un curso de ensamblador ya que los estudiantes tendrán que lidiar con bits de acarreo para resultados de AX intermedios en 2 ^ 31 y calcular un módulo. Si usted es el alumno, es bastante sencillo de implementar en ensamblador y puede ser lo que el conferenciante tenía en mente.

Answer 5

también es probable que pueda emular el cambio de registro con elementos de suma XOR entre bits separados, lo que le dará una secuencia de números pseudoaleatoria.

Answer 6

Bueno, como no he visto una referencia al viejo y antiguo Registro de desplazamiento lineal, publico un código C intrínseco basado en SSE. Solo para completar. Escribí eso hace un par de meses para mejorar mis habilidades SSE nuevamente.

#include <emmintrin.h>

static __m128i LFSR;

void InitRandom (int Seed)
{
  LFSR = _mm_cvtsi32_si128 (Seed);
}

int GetRandom (int NumBits)
{
  __m128i seed = LFSR;
  __m128i one  = _mm_cvtsi32_si128(1);
  __m128i mask; 
  int i;

  for (i=0; i<NumBits; i++)
  {

    // generate xor of adjecting bits
    __m128i temp = _mm_xor_si128(seed, _mm_srli_epi64(seed,1));

    // generate xor of feedback bits 5,6 and 62,61
    __m128i NewBit = _mm_xor_si128( _mm_srli_epi64(temp,5),
                                    _mm_srli_epi64(temp,61));

    // Mask out single bit: 
    NewBit = _mm_and_si128 (NewBit, one);

    // Shift & insert new result bit:
    seed = _mm_or_si128 (NewBit, _mm_add_epi64 (seed,seed));
  }

  // Write back seed...
  LFSR = seed;

  // generate mask of NumBit ones.
  mask = _mm_srli_epi64 (_mm_cmpeq_epi8(seed, seed), 64-NumBits);

  // return random number:
  return _mm_cvtsi128_si32 (_mm_and_si128(seed,mask));
}

Traducir este código al ensamblador es trivial. Simplemente reemplace las características intrínsecas con las instrucciones SSE reales y agregue un bucle alrededor de ellas.

Por cierto, la secuencia que este código genrea se repite después de 4.61169E + 18 números. Eso es mucho más de lo que obtendrá a través del método principal y la aritmética de 32 bits. Si se desenrolla, es más rápido también.

Answer 7

¿Por qué no usar una biblioteca externa? Esa rueda ha sido inventada cientos de veces, ¿por qué hacerlo de nuevo?

Si necesita implementar un RNG usted mismo, ¿necesita producir números a pedido, es decir, está implementando una función rand () o necesita generar flujos de números aleatorios, por ejemplo, para pruebas de memoria?

¿Necesitas un RNG que sea crypto-strength? ¿Cuánto tiempo tiene que pasar antes de que se repita? ¿Tiene que garantizar absoluta y positivamente la distribución uniforme de todos los bits?

Aquí hay un truco simple que utilicé hace varios años. Estaba trabajando en embedded y necesitaba probar RAM en el encendido y quería un código realmente pequeño, rápido y muy poco estado, y lo hice:

• Comience con una constante arbitraria de 4 bytes para su semilla.
• Calcule el CRC de 32 bits de esos 4 bytes. Eso te da los siguientes 4 bytes
• Retroalimente esos 4 bytes en el algoritmo CRC32, como si hubieran sido añadidos. El CRC32 de esos 8 bytes es el siguiente valor.
• Repite todo el tiempo que quieras.

Esto requiere muy poco código (aunque necesita una tabla para la función crc32) y tiene muy poco estado, pero la secuencia de salida psuedorandom tiene un tiempo de ciclo muy largo antes de que se repita. Además, no requiere SSE en el procesador. Y suponiendo que tenga la función CRC32 a mano, es trivial de implementar.

Answer 8

Usando masm615 para el compilador:

delay_function macro
    mov cx,0ffffh
.repeat
    push cx
    mov cx,0f00h
    .repeat
        dec  cx
        .until cx==0
    pop cx
    dec cx
    .until cx==0
endm

random_num macro
   mov  cx,64    ;assum we want to get 64 random numbers
   mov  si,0

get_num:    
   push cx
   delay_function    ;since cpu clock is fast,so we use delay_function
   mov  ah,2ch  
   int  21h
   mov  ax,dx     ;get clock 1/100 sec
   div  num       ;assume we want to get a number from 0~num-1
   mov  arry[si],ah   ;save to array you set
   inc  si
   pop  cx
   loop get_num   ;here we finish the get_random number 

Answer 9

Código simple para probar, no usar con Crypto

De Prueba de software de computadora, página 138

Con maths de 32 bits, no necesita la operación MOD 2^32

RNG = (69069*RNG + 69069) MOD 2^32