Ressu versio 1

Tässä oikeastaan ensimmäinen “virallinen” julkaisu Ressu-satunnaislukugenetaattorin versiosta 1.0.

Edit: muokattu julkaisun jälkeisten viikkojen aikana.

Satunnaislukugeneraattorihan koostuu kahdesta funktiosta, clockbyte(), joka palauttaa kellojonon seuraavan merkin, ja ressu_genbytes(), joka on varsinainen generaattori.

Ensimmäinen kierros genbytes() rutiinista vaihtaa jokaisen merkin bittien järjestystä ja summaa merkkiin seuraavan kellojonon merkin. Ajatuksena on että jokainen tuloksena tulevan puskurin bitti koskee kaikkia kellojonon merkin bittejä.

Toinen kierros sekoittaa tulokseksi saadun kellojonon kuin korttipakan käyden koko jonon läpi, ja vaihtaen kunkin merkin satunnaisen merkin kanssa. Satunnainen merkki valitaan kellojonon merkkien perusteella.

Näitä kahta kierrosta suoritetaan b kertaa, jossa b on kierrosten lukumäärä ja määritellään genbytes() kutsussa.

Eli siis kellon tarkin bitti koskettaa merkin tarkinta bittiä, sen jälkeen merkkiä siirretään satunnaisesti toiseen kohtaan puskurissa, tämän jälkeen toinen tarkin bitti kellojonosta koskettaa merkin seuraavaa tarkinta bittiä ja merkki siirretään taas. Eli merkin bitit tulevat täysin satunnaisista kellon kohdista ja kaikkien kellon bittien vaikutuskohdat leviävät tasaisesti puskurissa. Jos kierroksia on kahdeksan, tämä tehdään kahdeksan kertaa, ja puskurin kaikki bitit koskettavat kahdeksan kertaa satunnaista kellosignaalin tarkinta bittiä ja vaihtavat kosketusten välillä paikkojaan.

OWN_CLOCK #define muuttujalla voidaan määritellä oma clock rutiini. Sitä voisi teoriassa käyttää näppäimistölle tai valokuville.

Vielä kerran: ethän käytä tätä generaattoria ainoana generaattorina kriittisiin tarkoituksiin, vaan summaat aina useampia generaattoreita..

/*      
 * Ressu−satunnaislukugeneraattori versio 1.0 (ressugen.c)
 *
 * (c)2013−2018 Jari Kuivaniemi, Kaikki oikeudet pidätetään!
 */
#include <stdio.h>
#include <sys/time.h>

unsigned char *ressu_name = "Ressu 1.0";

#ifndef OWN_CLOCK

unsigned char clockbyte() /* JariK 2013 */
{
  struct timeval tv;

  gettimeofday(&tv,NULL);

  return(tv.tv_usec & 0xff);
}

#endif

void ressu_genbytes(int size, unsigned char *buffer, int b) /* JariK 2013 */
{
  int c,d,e,f;

  f=0;
  for(c=0;c<8*b;c++) {
    for(d=0;d<size;d++) {
      e=buffer[d];
      e=((e&0x80)>>7) | ((e&0x7f)<<1);
      buffer[d]=e^clockbyte();
    }
    for(d=0;d<size;d++) {
      f=(f+buffer[d])%size;
      e=buffer[d];
      buffer[d]=buffer[f];
      buffer[f]=e;
    }
  }
}

Clockbyte() palauttaa yksinkertaisesti alimmat bitit järjestelmän kellosta.

Ressu_genbytes() saa parametreinaan puskurin koon, osoitteen siihen ja kierrosten lukumäärän. Se generoi puskuriin satunnaisbittijonon. Rutiini sisältää kolme kierrosrakennetta, joista c luuppi laskee kierroksia, d laskee puskurin merkkejä (alusta loppuun), e:tä käytetään välimuuttujana, ja f laskee vaihdettavan merkin paikkaa. F:ään lisätään aina puskurin sisältö, eli näin myös kellojono, se vastaa siitä että kun yksikin bitti kellojonossa muuttuu, tulos muuttuu. Tästä tulee periaatteessa mahdollinen ongelma, eli jos kellojono on samanlainen, generaattori generoi samoja bittijonoja uudestaan. Näyttää kuitenkin siltä että kellojonossa on samanlaisia vain noin kilojen kokoisia jaksoja. Tämän perusteella voisi ehkä laskea puskurin pituutta. Jatkossa puskurin pituus on määritelty 65535 merkiksi.

Tässä vielä muutama apurutiini:

Ressu_genbyte() palauttaa yhden ressu generaattorin arpoman merkin. Ressu_genbyte_limit(int limit) palauttaa yhden haluttua rajaa pienemmän merkin (raja on parametrissa limit). ressu_genshort() palauttaa 16 bittisen intin ja ressu_genshort_limit(int limit) palauttaa rajaa pienemmän 16 bittisen luvun. ressu_clear() tyhjentää apurutiinitn ressu_bytes puskurin.

Jättämällä määrittelemättä #define muuttuja RESSU_CLEAR:in voimme estää puskurin tyhjentämisen uuden puskurin luonnin yhteydessä. Jos puskuria ei ole tyhjennetty, voimme alkaa riidellä siitä, kuinka paljon edellisistä biteistä voidaan arvata uuden puskurin bittejä. (todellisuudessahan yhteyttä edelliseen puskuriin ei ole, puolet biteistä vaihtuvat vähintään rounds kertaa).. Toisaalta jos puskuria ei tyhjennetä, satunnaisuus “kertyy” useampien kutsukertojen välillä.

B muuttuja seuraavan koodin alussa kertoo kuinka monta kierrosta generaattoria ajetaan. Se on nyt 45 ja olen ajatellut sen olevan riittävän suuri ettei ongelmia kriittistenkään satunnaisbittien generoinnissa tule. Samoin tuo puskurin pituus on arvaus, jolla ei pitäisi tulla ongelmia. Jos esimerkiksi haluat satunnaislukuja shakki peliin tai sudokujen laatimiseen voit ilman muuta valita pienemmät luvut. (Esimerkiksi kilon puskuri ja pari kierrosta riittävät hyvin perus pelin generaattoriin.) Olen itse tutkinut generaattoria ja tuohon tietoon voi tulla muutoksia. Toisaalta jos noudatat neuvoani ja et käytä tätä generaattoria pelkästään, ei tietenkään haittaa siirtyä pienempiin lukuihin.

#define RESSUBUFLEN 2048
unsigned char ressu_bytes[RESSUBUFLEN];

int ressu_byte=999999;
int ressu_b = 45;
#define aRESSU_CLEAR 2
unsigned char *file_b = "libressu1.b";

int ressu_genbyte()
{
  if(ressu_byte>=ressu_bytes) {
    if(ressu_buffer==NULL)
      ressu_buffersize(ressu_bytes);
#ifdef RESSU_CLEAR
    ressu_clear();
#endif
    ressu_genbytes(ressu_bytes, ressu_buffer,
        ressu_b);
    ressu_byte=0;
  }
  return(ressu_buffer[ressu_byte++]);
}

void ressu_genbytes_xor(unsigned char *buffer,int size)
{
  int c,d;

  for(c=0;c<size;c++)
    buffer[c]^=ressu_genbyte();;
}

int ressu_genbyte_limit(int limit)
{
  int c;

  while((c=ressu_genbyte())>(256/limit)*limit);
  return(c%limit);
}

int ressu_genshort()
{
  return(ressu_genbyte()+256*ressu_genbyte());
}

int ressu_genshort_limit(int limit)
{
  int c;

  while((c=ressu_genshort())>
          (65536/limit)*limit);
  return(c%limit);
}

void ressu_clear()
{
  memset(ressu_bytes,0,sizeof(ressu_bytes));
  ressu_byte=999999;
}

Yksi ongelma on määritellä, miten pitkä kellojonoo tarvitaan, että siinä on riittävästi satunnaisbittejä puskuriin. Yksi tapa tarkastella sitä on päättää että yhdessä kellon vaihdoksessa on yksi bitti, eli jos yhden vaihdoksen pituus on 20 merkkiä ja tarvittavien satunnaismerkkien määrä olisi 2048, kaava olisi 2048*8*20. Tulokseksi saataisiin että b:n arvo olisi sama kuin kellojakson pituus eli 20.

Tässä ohjelma, joka hakee kellojonon pituuden ja palauttaa sen (lisäten 2).

int ressu_calculate_b()
{
  int c,d,ed,count,first,statmax,statlength,b,b2;
  unsigned char stats[512];

  while(clockbyte()!=0);
  while(clockbyte()==0);
  while(clockbyte()!=0);

  for(c=0;c<sizeof(stats);c++)
    stats[c]=0;
  first=1;
  for(c=0;c<65535;c++) {
    d=clockbyte();
    if(first==1) {
      ed=d;
      count=1;
      first=0;
    } else if(ed!=d) {
      ed=d;
      stats[count]++;
      count=1;
    } else {
      count++;
    }
  }

  for(c=0;c<512;c++)
    if(stats[c]>0)
      fprintf(stdout," %d:%2d",c,stats[c]);

  fprintf(stdout,"\n");

  statmax=0;
  statlength=-1;
  for(c=0;c<sizeof(stats);c++) {
    if(stats[c]>=statmax) {
      statmax=stats[c];
      statlength=c;
    }
  }
  fprintf(stdout,"most frequend clockchain size: %d",statlength);
  b2=int_read(file_b);
  fprintf(stdout,", b from file: %d",b2);
  if(b2>=statlength) {
    b=b2;
  } else {
    b=statlength;
    int_write(b,file_b);
    fprintf(stdout,", b written to file: %d",b);
  }
  fprintf(stdout,", returned b: %d\n",b+2);
  fflush(stdout);
  
  return(b+2);
}

int int_read(char *filename)
{
  int i;
  unsigned char buffer[10];
  FILE *fp1;

  i=0;
  
  if((fp1=fopen(filename,"r"))!=NULL) {
    fgets(buffer,sizeof(buffer),fp1);
    i=atoi(buffer);
    fclose(fp1);
  }
  return(i);
}

void int_write(int i, unsigned char *filename)
{
  FILE *fp1;

  if((fp1=fopen(filename,"w"))!=NULL) {
    fprintf(fp1,"%d\n",i);
    fclose(fp1);
  }
}

Jos haluat itse pongata pitkiä duplikaattimerkkijonoja voit aloittaa sen seuraavalla ohjelmalla:

#include <stdio.h>
#include <string.h>
#include <time.h>

#include "ressugen.c"

#define RESSUBYTES 16384*8
//#define RESSUBYTES 16384*48
unsigned char ressu_bytes[RESSUBYTES];

#define VERBOSE 2
#define aFAST 2

time_t now;
#define HTMLTIMEFORMAT "%a, %d %b %Y %H:%M:%S GMT"
unsigned char datestr[128];
char procname[] = "Ressutest v0.01";

void main(int argc,char *argv[])
{
  int c,d,e,limit,dup,first0;
  int low,high,middle;
  time_t now2,now3;

  
  now = time(NULL);
  strftime(datestr, sizeof(datestr),
       HTMLTIMEFORMAT, gmtime(&now));

  fprintf(stdout,"\n");
  fflush(stdout);
  
  fprintf(stdout,"%s\n%s\n\n",procname,datestr);
  fflush(stdout);

  for(;;) {
    for(c=0;c<sizeof(ressu_bytes);c++) {
      ressu_bytes[c]=clockbyte();
    }
    
    now2 = time(NULL);
    
    limit=sizeof(ressu_bytes);;
    low=1;
    high=10000;

    fprintf(stdout,"limit: %d",limit);
    fflush(stdout);

    while(low<=high) {
      middle=(low+high)/2;
#ifdef VERBOSE
      fprintf(stdout,"\nlimit: %d",limit);
      fprintf(stdout,", low:%d",low);
      fprintf(stdout,", high: %d",high);
      fprintf(stdout,", middle: %d",middle);
      fflush(stdout);
#endif
      dup=0;
      for(d=0; d<limit-middle; d++) {
    for(e=d+1; e<limit-middle; e++) {
      if(!memcmp(&ressu_bytes[d],
             &ressu_bytes[e],middle)) {
        dup++;
        e+=middle;
#ifdef FAST
        break;
#endif
      }
    }
#ifdef FAST
      if(dup)
    break;
#endif
      }
#ifdef VERBOSE
      fprintf(stdout,", dup: %d",dup);
      fflush(stdout);
#endif
      if(dup) {
    low=middle+1;
      } else {
    high=middle-1;
      }
    }
#ifdef VERBOSE
    fflush(stdout);
    fprintf(stdout,", middle: %d",middle-1);
#endif
    first0=middle-1;
    dup=0;
    for(d=0;d<limit-(middle-1);d++) {
      for(e=d+1;e<limit-(middle-1);e++) {
    if(!memcmp(&ressu_bytes[d],
           &ressu_bytes[e],middle-1)) {
      dup++;
      e+=middle;
#ifdef FAST
      break;
#endif      
    }
      }
#ifdef FAST
      if(dup)
    break;
#endif
    }
    if(dup!=0)
      first0++;
#ifdef VERBOSE
    fprintf(stdout,", dup: %d",dup);  
    fflush(stdout);
#endif
#ifdef VERBOSE
    fprintf(stdout,", middle: %d",middle);
    fflush(stdout);
#endif
    dup=0;
    for(d=0;d<limit-middle;d++) {
      for(e=d+1;e<limit-middle;e++) {
    if(!memcmp(&ressu_bytes[d],
           &ressu_bytes[e],middle)) {
      dup++;
      e+=middle;
#ifdef FAST
      break;
#endif
    }
      }
#ifdef FAST
      if(dup)
    break;
#endif
    }
    if(dup!=0)
      first0++;
#ifdef VERBOSE
    fprintf(stdout,", dup2: %d",dup);
    fflush(stdout);
#endif
#ifdef VERBOSE
    fprintf(stdout,", middle: %d",middle+1);
    fflush(stdout);
#endif
    dup=0;
    for(d=0;d<limit-(middle+1);d++) {
      for(e=d+1;e<limit-(middle+1);e++) {
    if(!memcmp(&ressu_bytes[d],
           &ressu_bytes[e],middle+1)) {
      dup++;
      e+=middle;
#ifdef FAST
      break;
#endif
    }
      }
#ifdef FAST
      if(dup)
    break;
#endif
    }
    if(dup!=0)
      first0++;
    now3 = time(NULL);
#ifdef VERBOSE
    fprintf(stdout,", dup3: %d",dup);
    fflush(stdout);
#endif
    fprintf(stdout,", first0: %d",first0);

    int time;

    time=now3-now2;

    fprintf(stdout,", took ");
    if((time/60)>0) {
      fprintf(stdout,"%d minutes, ",time/60);
      time%=60;
    }
    fprintf(stdout,"%d seconds.\n",time);
    fflush(stdout);
  }
}

Seuraavassa mallitulokset edellisestä ohjelmasta: ensimmäisessä listassa VERBOSE ei ole määritelty. Toisessa ja kolmannessa VERBOSE on määritelty. Toisessa listassa FAST on määritelty, kolmannessa FAST ei ole määritelty. Limit on puskurin koko. Low, high ja middle ovat binäärihaun muuttujat. Dup kertoo onko duplikaatteja. Dup on 0 tai 1, jos FAST on määritelty, muuten tuplamerkkijonojen lukumäärä. First0  on ensimmäinen pituus, jolla ei ole tuplamerkkijonoja.

limit: 131072, first0: 1818, took 17 minutes, 10 seconds.
limit: 131072, first0: 1618, took 13 minutes, 23 seconds.
limit: 131072, first0: 2790, took 15 minutes, 16 seconds.
limit: 131072, first0: 2616, took 11 minutes, 21 seconds.
limit: 131072, first0: 2598, took 16 minutes, 35 seconds.

limit: 131072, low:1, high: 10000, middle: 5000, dup: 0
limit: 131072, low:1, high: 4999, middle: 2500, dup: 0
limit: 131072, low:1, high: 2499, middle: 1250, dup: 1
limit: 131072, low:1251, high: 2499, middle: 1875, dup: 1
limit: 131072, low:1876, high: 2499, middle: 2187, dup: 0
limit: 131072, low:1876, high: 2186, middle: 2031, dup: 1
limit: 131072, low:2032, high: 2186, middle: 2109, dup: 1
limit: 131072, low:2110, high: 2186, middle: 2148, dup: 0
limit: 131072, low:2110, high: 2147, middle: 2128, dup: 1
limit: 131072, low:2129, high: 2147, middle: 2138, dup: 1
limit: 131072, low:2139, high: 2147, middle: 2143, dup: 1
limit: 131072, low:2144, high: 2147, middle: 2145, dup: 0
limit: 131072, low:2144, high: 2144, middle: 2144, dup: 1, middle: 2143, dup: 1, middle: 2144, dup2: 1, middle: 2145, dup3: 0, first0: 2145, took 13 minutes, 54 seconds.
limit: 131072
limit: 131072, low:1, high: 10000, middle: 5000, dup: 0
limit: 131072, low:1, high: 4999, middle: 2500, dup: 0
limit: 131072, low:1, high: 2499, middle: 1250, dup: 1
limit: 131072, low:1251, high: 2499, middle: 1875, dup: 0
limit: 131072, low:1251, high: 1874, middle: 1562, dup: 1
limit: 131072, low:1563, high: 1874, middle: 1718, dup: 0
limit: 131072, low:1563, high: 1717, middle: 1640, dup: 1
limit: 131072, low:1641, high: 1717, middle: 1679, dup: 0
limit: 131072, low:1641, high: 1678, middle: 1659, dup: 1
limit: 131072, low:1660, high: 1678, middle: 1669, dup: 0
limit: 131072, low:1660, high: 1668, middle: 1664, dup: 0
limit: 131072, low:1660, high: 1663, middle: 1661, dup: 1
limit: 131072, low:1662, high: 1663, middle: 1662, dup: 1
limit: 131072, low:1663, high: 1663, middle: 1663, dup: 1, middle: 1662, dup: 1, middle: 1663, dup2: 1, middle: 1664, dup3: 0, first0: 1664, took 16 minutes, 0 seconds.

limit: 131072, low:1, high: 10000, middle: 5000, dup: 0
limit: 131072, low:1, high: 4999, middle: 2500, dup: 0
limit: 131072, low:1, high: 2499, middle: 1250, dup: 666
limit: 131072, low:1251, high: 2499, middle: 1875, dup: 0
limit: 131072, low:1251, high: 1874, middle: 1562, dup: 0
limit: 131072, low:1251, high: 1561, middle: 1406, dup: 252
limit: 131072, low:1407, high: 1561, middle: 1484, dup: 96
limit: 131072, low:1485, high: 1561, middle: 1523, dup: 34
limit: 131072, low:1524, high: 1561, middle: 1542, dup: 15
limit: 131072, low:1543, high: 1561, middle: 1552, dup: 5
limit: 131072, low:1553, high: 1561, middle: 1557, dup: 0
limit: 131072, low:1553, high: 1556, middle: 1554, dup: 3
limit: 131072, low:1555, high: 1556, middle: 1555, dup: 2
limit: 131072, low:1556, high: 1556, middle: 1556, dup: 1, middle: 1555, dup: 2, middle: 1556, dup2: 1, middle: 1557, dup3: 0, first0: 1557, took 25 minutes, 46 seconds.
limit: 131072
limit: 131072, low:1, high: 10000, middle: 5000, dup: 0
limit: 131072, low:1, high: 4999, middle: 2500, dup: 469
limit: 131072, low:2501, high: 4999, middle: 3750, dup: 0
limit: 131072, low:2501, high: 3749, middle: 3125, dup: 0
limit: 131072, low:2501, high: 3124, middle: 2812, dup: 102
limit: 131072, low:2813, high: 3124, middle: 2968, dup: 0
limit: 131072, low:2813, high: 2967, middle: 2890, dup: 24
limit: 131072, low:2891, high: 2967, middle: 2929, dup: 0
limit: 131072, low:2891, high: 2928, middle: 2909, dup: 5
limit: 131072, low:2910, high: 2928, middle: 2919, dup: 0
limit: 131072, low:2910, high: 2918, middle: 2914, dup: 0
limit: 131072, low:2910, high: 2913, middle: 2911, dup: 3
limit: 131072, low:2912, high: 2913, middle: 2912, dup: 2
limit: 131072, low:2913, high: 2913, middle: 2913, dup: 1, middle: 2912, dup: 2, middle: 2913, dup2: 1, middle: 2914, dup3: 0, first0: 2914, took 29 minutes, 26 seconds.