03_ffac

ffac.c

#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

typedef unsigned long long ullong;
typedef struct {
  int count;
  ullong *numbers;
} factorize_arg;

#define abs(x) ((x)>0 ? (x) : -(x))

bool is_prime(ullong number)
{
  ullong root = (int)(sqrt(number) + 0.5);
  for (ullong i = 2; i <= root; i++)
  {
    if ((number % i) == 0)
      return false;
  }

  return true;
}

ullong gcd(ullong a, ullong b)
{
  return b ? gcd(b, (a % b)) : a;
}

ullong rho(ullong number)
{
  ullong divisor = 0;
  ullong  c = rand() % number;
  ullong  x = rand() % number;
  ullong xx = x;

  if ((number % 2) == 0)
  {
    return 2;
  }
  
  do {
    x  = (( (x*x)   % number) + c) % number;
    xx = (( (xx*xx) % number) + c) % number;
    xx = (( (xx*xx) % number) + c) % number;

    divisor = gcd(abs(x - xx), number);
  } 
  while (divisor == 1);

  return divisor;
}

void pollard_rho_factorize(ullong number)
{
  if (number == 1l)
    return;

  if (is_prime(number) == true) {
    printf("%lu ", number);
    return;
  }

  ullong divisor = rho(number);

  pollard_rho_factorize(divisor);
  pollard_rho_factorize(number / divisor);
}

void usage(char *image_name) {
  fprintf(stderr, "\n**Usage** %s [NUMBER]...\n\n",
          image_name != NULL ? image_name : "ffac");
}

factorize_arg *alloc_arg(int max_arg_count) {
  factorize_arg *ret = calloc(1, sizeof(factorize_arg));
  ret->count = 0;
  ret->numbers = calloc(max_arg_count, sizeof(ullong));

  return ret;
}

void free_arg(factorize_arg *arg) {
  if (arg == NULL)
    return;

  if (arg->numbers != NULL)
    free(arg->numbers);

  free(arg);
}

factorize_arg *parse_args(int argc, char **argv) {
  if (argc < 2) 
  {
    usage(argv[0]);
    return NULL;
  }
   
  factorize_arg *ret = alloc_arg(argc - 1);

  for (int i = 1; i < argc; i++) 
  {
    ullong n = strtoll(argv[i], NULL, 10);
    
    if (n == 0) 
    {
      fprintf(stderr, "**Warning** Arg %d is either '0', too large, or not a number, skipping\n", i - 1);
      continue;
    }

    if (n == 1)
    {
      fprintf(stderr, "**Warning** Arg %d is '1', no fact. needed, skipping\n", i - 1);
      continue;
    }

    ret->numbers[ret->count] = n;
    ret->count += 1;
  }

  return ret;
}

void do_parallel_factorize(factorize_arg *arg) {
  assert(arg != NULL);

  for (int i = 0; i < arg->count; i++) {
    pid_t pid = fork();
    
    if (pid < 0) 
    {
      fprintf(stderr, "**Error** Unable to spawn new process, exiting\n");
      exit(1);
    }

    if (pid == 0) 
    {
      ullong number = arg->numbers[i];
      
      printf("Factorizing %10lu: ", number);
      pollard_rho_factorize(number);
      printf("\n");

      return;
    }
  }
}

int main(int argc, char **argv) 
{
  factorize_arg *arg = parse_args(argc, argv);
  do_parallel_factorize(arg);
  free_arg(arg);

  return 0;
}