Skip to content

Instantly share code, notes, and snippets.

@bgschiller
Created December 13, 2013 04:03
Show Gist options
  • Save bgschiller/7939613 to your computer and use it in GitHub Desktop.
Save bgschiller/7939613 to your computer and use it in GitHub Desktop.
A thread-based pseudorandom number generator, and two adversaries that defeat it. Code for the blog post at http://brianschiller.com/blog/2013/12/12/pthreads-and-prngs-oh-my.html
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>
typedef unsigned int uint;
uint moves = 0;
uint guesses = 0;
uint p1 = 0;
uint c1 = 0;
uint p2 = 0;
uint c2 = 0;
uint last_move = 2; //2 indicates uknown, that we should flip a coin.
uint man_score = 0;
uint mach_score = 0;
uint arr[2][3][2][3][2] = { 0 };
void judge(uint man_ans, uint mach_ans){
if (mach_ans == 2){
//machine won't make a choice -- flip a coin
mach_ans = rand() % 2;
guesses++;
}
if (man_ans == mach_ans) {
mach_score++;
} else {
man_score++;
}
}
void run_move(uint man_ans) {
//Very simple adversary, always guesses whatever the most
//recent bit was
uint mach = last_move;
judge(man_ans, mach);
last_move = man_ans;
moves++;
}
void mach_move(uint man_ans) {
//code from http://www.loper-os.org/bad-at-entropy/manmach.html,
//(translated from the javascript)
uint mach;
if (moves < 3){
mach = 2;
} else {
if (fabs(arr[p1][c1][p2][c2][0] - arr[p1][c1][p2][c2][1]) <= 1.8 * pow(1.01, moves))
mach = 2;
else if(arr[p1][c1][p2][c2][0] < arr[p1][c1][p2][c2][1])
mach = 1;
else mach = 0;
arr[p1][c1][p2][c2][man_ans] += pow(1.1,moves);
}
judge(man_ans, mach);
c1 = c2;
c2 = mach;
p1 = p2;
p2 = man_ans;
moves++;
}
int main (int argc, char* argv[]){
/* initialize random seed
(for when the machine doesn't make a choice,
and we flip a coin )*/
srand (time(NULL));
void (*adversary)(uint); //function ptr for our adversary of choice
if (argc < 2){
adversary = mach_move;
} else {
adversary = strcmp(argv[1],"r") == 0 ? run_move : mach_move;
}
uint next_bit;
while(scanf("%u", &next_bit) == 1){
adversary(next_bit);
}
uint total = man_score + mach_score;
double mach_proportion = 0.0;
if (total > 0){
mach_proportion = mach_score / (double) total;
}
fprintf(stderr,"Total bits: %u\n", moves);
fprintf(stderr,"Wild guesses: %u\n",guesses);
fprintf(stderr,"Number correct: %u\n",mach_score);
fprintf(stderr,"Machine Advantage: %f\n",mach_proportion);
printf("%f\n",mach_proportion);
}
all: thread_prng adversary Makefile advantages
thread_prng: thread_prng.c
gcc --std=c99 -o thread_prng -lpthread thread_prng.c
adversary: adversary.c
gcc --std=c99 -o adversary adversary.c
advantages: adversary thread_prng
for option in r m; do \
number=1 ; while [[ $$number -le 100 ]] ; do \
./thread_prng 100 | ./adversary $$option > "$${option}_advantages"; \
((number = number + 1)) ; \
done \
done
touch advantages
clean:
rm thread_prng adversary advantages
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
long value=0;
int threads_alive=1;
void* set_value(void* thread_id){
long favorite_number = (long) thread_id;
while(threads_alive){
value = favorite_number;
}
return NULL;
}
int main (int argc, char *argv[]){
long num_bits;
if (argc < 2){
printf("usage: %s num_bits\n",argv[0]);
exit(1);
} else {
num_bits = strtol(argv[1], NULL,0);
}
pthread_t threads[2];
for (long t = 0; t < 2; t++){
fprintf(stderr,"In main: creating thread %ld\n", t);
int rc = pthread_create(threads + t, NULL, set_value, (void *) t);
if (rc){
fprintf(stderr,"ERROR; return code from pthread_create() is %d\n", rc);
exit(-1);
}
}
for(long b=0; b < num_bits; b++){
printf("%ld\n",value);
nanosleep((struct timespec[]){{0, 10000000}}, NULL);
}
threads_alive=0;
for (long t=0; t < 2; t++){
pthread_join(threads[t],NULL);
fprintf(stderr,"Joined thread %ld\n",t);
}
pthread_exit(NULL);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment