Générateur pseudo-aléatoire en langage d'assemblage

Question

J'ai besoin d'un algorithme générateur de nombres pseudo-aléatoires pour un programme assembleur affecté à un cours, et je préférerais un algorithme simple. Cependant, je ne peux pas utiliser une bibliothèque externe.

Qu'est-ce qu'un bon et simple algorithme générateur de nombres pseudo-aléatoires pour l'assemblage?

Answer 1

Le plus simple est de choisir deux gros nombres premiers relatifs a et b, puis de multiplier votre nombre aléatoire par a et d’ajouter b. Utilisez l'opérateur modulo pour conserver les bits faibles en tant que nombre aléatoire et conserver la valeur complète pour la prochaine itération.

Cet algorithme est appelé générateur de congruences linéaires .

Answer 2

Le volume 2 de L'art de la programmation informatique contient de nombreuses informations sur la génération de nombres pseudo-aléatoires . Les algorithmes sont montrés dans assembleur, vous pouvez donc voir par vous-même quels sont les plus simples assembleurs.

Si vous pouvez créer un lien vers une bibliothèque externe ou un fichier objet, ce serait votre meilleur choix. Vous pouvez ensuite créer un lien vers, par exemple, Mersenne Twister .

Notez que la plupart des générateurs de nombres pseudo-aléatoires ne sont pas sûrs pour la cryptographie. Par conséquent, si vous avez besoin de la génération sécurisée de nombres aléatoires, vous devez regarder au-delà des algorithmes de base (et probablement exploiter les API de chiffrement spécifiques au système d'exploitation). ).

Answer 3

Code simple pour les tests, ne pas utiliser avec Crypto

Dans Test du logiciel, page 138

Avec ses calculs en 32 bits, l'opération MOD 2 ^ 32

n'est pas nécessaire.

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

Answer 4

Bien - Comme je n'ai pas vu de référence au bon vieux registre à décalage à rétroaction linéaire, je publie du code C intrinsèque SSE. Juste pour compléter. J'ai écrit cette chose il y a quelques mois pour améliorer mes compétences en SSE.

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

Traduire ce code en assembleur est trivial. Il suffit de remplacer les éléments intrinsèques par les instructions réelles de SSE et d’ajouter une boucle autour de celle-ci.

Btw - la séquence générée par ce code se répète après 4,61169E + 18 nombres. C'est beaucoup plus que ce que vous obtiendrez via la méthode principale et l'arithmétique 32 bits. Si déroulé c'est aussi plus rapide.

Answer 5

@jjrv
Ce que vous décrivez est en réalité un générateur de congruence linéaire. Les bits les plus aléatoires sont les bits les plus élevés. Pour obtenir un nombre compris entre 0..N-1, multipliez la valeur complète par N (32 bits sur 32 bits donnant 64 bits) et utilisez les 32 bits les plus élevés.

 Vous ne devez pas utiliser n'importe quel nombre pour a (le multiplicateur permettant de passer d'une valeur complète à la suivante), les nombres recommandés dans Knuth (Tableau 1 section 3.3.4 TAOCP vol 2 1981) sont 1812433253. , 1566083941, 69069 et 1664525.

Vous pouvez simplement choisir un nombre impair pour b . (l'ajout).

Answer 6

Pourquoi ne pas utiliser une bibliothèque externe ??? Cette roue a été inventée quelques centaines de fois, alors pourquoi la refaire?

Si vous devez implémenter vous-même un générateur de réseau de récupération, devez-vous générer des nombres à la demande (par exemple, implémentez-vous une fonction rand ()) ou devez-vous générer des flux de nombres aléatoires? pour tester la mémoire?

Avez-vous besoin d’un RNG doté d’une force de cryptage? Combien de temps faut-il avant qu'il ne se répète? Devez-vous absolument et positivement garantir une distribution uniforme de tous les bits?

Voici un hack simple que j'ai utilisé il y a plusieurs années. Je travaillais en mode embarqué et je devais tester la mémoire vive au moment de la mise sous tension. Je voulais un code très petit, rapide et un état très réduit. Je l’ai donc fait:

• Commencez avec une constante arbitraire de 4 octets pour votre graine.
• Calculez le CRC 32 bits de ces 4 octets. Cela vous donne les 4 prochains octets
• Transmettez ces 4 octets dans l'algorithme CRC32, comme s'ils avaient été ajoutés. Le CRC32 de ces 8 octets est la valeur suivante.
• Répétez aussi longtemps que vous le souhaitez.

Cela prend très peu de code (bien que vous ayez besoin d’une table pour la fonction crc32) et a très peu d’état, mais le flux de sortie psuedorandom a un temps de cycle très long avant qu’il ne se répète. En outre, SSE n’a pas besoin du processeur. Et en supposant que vous ayez la fonction CRC32 à portée de main, son implémentation est triviale.

Answer 7

Utilisation de masm615 pour compiler:

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 8

Vous pouvez également probablement émuler un registre à décalage avec des éléments de somme XOR entre des bits séparés, ce qui vous donnera une séquence pseudo-aléatoire de nombres.

Answer 9

congruence linéaire (X = AX + C mod M) Les PRNG peuvent être utiles à assigner pour un cours d'assembleur, car vos étudiants devront traiter des bits de support pour des résultats AX intermédiaires sur 2 ^ 31 et calculer un module. Si vous êtes l’étudiant, ils sont relativement simples à mettre en œuvre dans assembleur et peuvent correspondre à ce que le conférencier avait en tête.