Wednesday, April 23, 2014

Telephone Game Simulator using C Language

This post shows the code for simulating game of Telephone using processes and pipes. The initial process will create n – 1 additional processes and n pipes, with the processes in chain, connected by pipes.
Text will be read by the initial processes and then be passed from process to process along the chain, using the pipes, which have been created. Each process will read from its incoming pipe and read from its outgoing pipe.

When the message reaches its last process that process will write the message it receives to (stdout) monitor.

To simulate errors in communication, each process may transmit some characters incorrectly.
The program have two command-line arguments, the number of processes n and a real number 0.0 <= p <= 1.0. p represents the probability that a character will be transferred incorrectly. C library function random() used to generate random numbers which is used to decide whether or not a given character should be transmitted correctly.

Following is the C program listing for the above problem description:

#include <time.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

#define MAX_MESSAGE_LENGTH 2048

struct pipe_t{
  int fd[2];
};


/*
 * returns 0 if user did not pass correct arguments
 * returns 1 if user passed correct arguments and initializes
 * these arguments
 */
int check_args(int argc, char **argv, int *n_processes, double *p)
{
  if (argc < 3) {
    printf("Usage: ./program n_processes error_probability\n");
    return 0;
  }
  *n_processes = atoi(argv[1]);
  *p = atof(argv[2]);
  if (*p < 0 || *p > 1) {
    printf("Error probability must be between 0 and 1\n");
    return 0;
  }
  return 1;
}


/*
 * returns random character
 * from set:
 */
char rand_char()
{
  int printable_characters_num = 127 - 32;
  return 32 + (rand() % printable_characters_num);
}

/*
 * returns 1 with probability @p
 * 0 otherwise
 */
int rand_bool(double p)
{
  return (random() / (double)RAND_MAX) < p;
}

/*
 * @str is initial string
 * p is probability of each character to be transimtted
 * incorrectly
 * returns changed @str
 */
void generate_incorrect_str(char *str, double p)
{
  int i;
  for (i = 0; i < strlen(str); i++) {
    if (rand_bool(p)) { // incorrect
      char ch = rand_char();
      str[i] = ch; // replace character
    }
  }
}

/*
 * last process in chain calls this function
 * @str is char* received from previous process
 * @str_origin is original message
 * this function compares them and displays results
 * on stdout
 */
void display_statistics(char *str, char *str_origin)
{
  int errors = 0;
  int i;
  for (i = 0; i < strlen(str); i++) {
    if (str[i] != str_origin[i]) { // compare 2 strings char by char
      errors++; // count errors
    }
  }
  printf("Received %d characters\n", (int) strlen(str));
  double error_rate = ((double) errors) / strlen(str);
  printf("Error rate is: %f percent\n", error_rate * 100);
  printf("Received string: %s\n", str);
  printf("\n\n");
  //  printf("Original string: %s\n", str_origin);
}

/*
 * child processes start here
 * each process reads from @readfd and writes to @writefd
 * if process is last in the chain, @islast is 1, otherwise 0
 * @originfd is file descriptor, from which the last process
 * reads original message
 */
void run_process(int readfd, int writefd,
               int islast, int originfd, double p)
{
  // each process will have differrent random seed
  srand(time(NULL) + getpid());
  char str[MAX_MESSAGE_LENGTH + 1];
  // read message send from previous process
  int status = read(readfd, str, MAX_MESSAGE_LENGTH + 1);
  // could not read - some error happened
  if (status == -1) {
    perror("read:");
  }
 
  // last process
  if (islast) {
    char str_origin[MAX_MESSAGE_LENGTH + 1];
    // read original message from parent process
       status = read(originfd, str_origin, MAX_MESSAGE_LENGTH + 1);
    if (status == -1) {
      // could not read - some error happened
         perror("read:");
    }
    // to standard output
       display_statistics(str, str_origin); 
  } else {
    generate_incorrect_str(str, p);
    // send message to the next process
       write(writefd, str, strlen(str) + 1);
  }
 
}

/*
 * @p is probability of error on each write
 * @n is number of child processes to be created
 * @pipes is an array of initialized pipe_t structs
 * @pipes length must be at least n + 1
 *
 * this function creates n child processes
 */
int create_processes(int n, double p,
                   struct pipe_t *pipes)
{
  int i;
  for (i = 0; i < n; i++) { // crete n child processes
   
    pid_t pid = fork();

    if (pid == -1) { // could not fork because of error
      perror("fork:");
      exit(-1);
    }

    if (pid == 0) { // child process
      if (i != n - 1) {
       run_process(pipes[i].fd[0], pipes[i + 1].fd[1], 0, -1, p); // one of the middle chain processes
      } else {
       run_process(pipes[i].fd[0], -1, 1, pipes[i + 1].fd[0], p); // last process in the chain
      }
      exit(EXIT_SUCCESS); // child has finished its job. good-bye;
    } else { // parent process
      // nothing to do
    }
  }

  return 1;
}

/*
 * waits until all child processes are finished
 */
int wait_processes()
{
  int status;
  while(1) {
    int res = wait(&status);
    if (res == -1) break; // no more child
  }
  return 1;
}

/*
 * iterateos over @pipes array, which has length of @n_pipes
 * and initializes each pipe;
 * returns 1 on success, 0 otherwise;
 */
int create_pipes(int n_pipes, struct pipe_t *pipes)
{
  int i;
  for (i = 0; i < n_pipes; i++) {
    struct pipe_t *pp = &pipes[i];
    if(pipe(pp->fd) == -1) {
      perror("pipe:"); // some error happened
      return 0;
    }
  }
  return 1;
}

/*
 * only parent process must call this function.
 * this function reads input from stdin and sends to
 * the next child process in chain.
 * and sends to last child process too.
 */
void send_message(struct pipe_t *pipes, int n_pipes)
{
  char str[MAX_MESSAGE_LENGTH + 1];
  fgets(str, MAX_MESSAGE_LENGTH + 1, stdin);
  write(pipes[0].fd[1], str, strlen(str) + 1); // send message to next process in the chain
  write(pipes[n_pipes - 1].fd[1], str, strlen(str) + 1); // send message to the last process
}



int main(int argc, char **argv)
{
  int n_processes; // processes to be created and be in chain
  double p; // probability of each character sending with error
  if(!check_args(argc, argv, &n_processes, &p)) { // initializes p and n_processes
    exit(-1); // if invalid arguments - exit
  }
  int n_pipes = n_processes; // they should be equal
  struct pipe_t pipes[n_pipes]; // create array of pipes
  if (!create_pipes(n_pipes, pipes)) exit(-1); // if could not create pipe - exit
  create_processes(n_processes - 1, p, pipes); // create n-1 process (n-th process is parent himself)
  send_message(pipes, n_pipes); // send initial message from parent to the chain
  wait_processes(); // wait child processes to finish

  return 0; // and return
}