/* sieve.c - Crivo de Eratostenes
 *
 * Estudante: Cesar Eduardo Barros (991.302.397)
 * Data: 22 de Maio de 1999
 *
 * Feito num AMD K6 rodando Linux */

#define _GNU_SOURCE
/* define funcoes seguras para threads */
#define _REENTRANT
#define _THREAD_SAFE

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>

/* Note: ao mudar algo no codigo, cuidado para nao confudir N's com I's e
 * esquecer a conversao */

typedef unsigned unit;
typedef unsigned bitpos;

#define UNIT_SIZE_BYTES (sizeof (unit))
#define UNIT_SIZE_BITS (UNIT_SIZE_BYTES * 8)
#define UNIT_FORMAT "%u"
#define BITPOS_FORMAT "%u"

/* forces rounding up */
#define NUM_UNITS(n) (((n) + (UNIT_SIZE_BITS - 1)) / UNIT_SIZE_BITS)
#define NUM_BYTES(n) (NUM_UNITS(n) * UNIT_SIZE_BYTES)

#define BIT_MASK(b) ((unit)0x1 << ((b) % UNIT_SIZE_BITS))
#define BIT_MASK_ALL (~ (unit)0x0)
#define BIT_MASK_NONE ((unit)0x0)
/* WARNING! These macros evaluate b twice on non-GNU compilers */
#ifndef __GNUC__
#define GET_BIT(v,b) ((v) [(b) / UNIT_SIZE_BITS] & BIT_MASK ((b)))
#define SET_BIT(v,b) ((v) [(b) / UNIT_SIZE_BITS] |= BIT_MASK ((b)))
#define CLEAR_BIT(v,b) ((v) [(b) / UNIT_SIZE_BITS] &= ~ BIT_MASK ((b)))
#else
#define GET_BIT(v,b) ( __extension__ ({ bitpos _b = (b); \
			(v) [_b / UNIT_SIZE_BITS] & BIT_MASK (_b); }))
#define SET_BIT(v,b) ( __extension__ ({ bitpos _b = (b); \
			(v) [_b / UNIT_SIZE_BITS] |= BIT_MASK (_b); ; }))
#define CLEAR_BIT(v,b) ( __extension__ ({ bitpos _b = (b); \
			(v) [_b / UNIT_SIZE_BITS] &= ~ BIT_MASK (_b); ; }))
#endif

/* nota: arrays em C comecam por 0, arrays de bits tambem */
#define I2N(i) (2 * (i) + 3)
#define N2I(n) (((n) - 3) / 2)

static bitpos printf_i, printf_N2I_limit;
static pthread_mutex_t printf_mutex;

static void * printf_thread (void * p)
{
	bitpos temp_printf_i;
	bitpos N2I_limit;
	struct timespec timer;

	timer.tv_sec = 0;
	timer.tv_nsec = 100000;

	N2I_limit = printf_N2I_limit;

	while (1)
	{
		pthread_mutex_lock (&printf_mutex);
		temp_printf_i = printf_i;
		pthread_mutex_unlock (&printf_mutex);
	
		fprintf (stderr, "\r%3f%%",
				temp_printf_i * 100. / N2I_limit);
		fflush (stderr);

		nanosleep (&timer, NULL);
	}
}

int main (int argc, char * argv[])
{
	unit * sieve;
	bitpos limit;
	bitpos i, j;
	bitpos count;
	/* threading (for printf) */
	pthread_t t;
	bitpos N2I_limit;

	fprintf (stderr, "Maximum: ");
	fflush (stderr);
	scanf (BITPOS_FORMAT, &limit);

	if (limit <= 2)
		goto out_small_limit;

	N2I_limit = N2I (limit);

	sieve = malloc (NUM_BYTES (N2I_limit + 1));
	if (sieve == NULL)
		goto out_no_mem;

	for (i = 0; i < NUM_UNITS (N2I_limit); ++i)
		sieve [i] = BIT_MASK_NONE;

	printf_i = 0;
	printf_N2I_limit = N2I_limit;
	pthread_mutex_init (&printf_mutex, NULL);
	pthread_create (&t, NULL, printf_thread, NULL);

	for (i = 0; i <= N2I_limit; ++i)
	{
		/* meus testes mostraram que printf() estava reduzindo muito a
		 * velocidade neste ponto quando i tendia a N2I (limit).
		 * Portanto dividi o programa em dois threads para reduzir a
		 * taxa de chamadas a printf sem complicar muito o codigo */
		/* note que o loop ainda para neste ponto durante chamadas a
		 * printf, se printf_thread travar o mutex enquanto tenta-se
		 * trava-lo aqui. Isso nao faz muita diferenca uma vez que o
		 * mutex e travado pelo menor tempo possivel */
		/* O calculo da percentagem tambem foi movido para
		 * printf_thread; agora esta thread nao usa ponto flutuante no
		 * loop (evitando as computacoes caras de ponto flutuante) */
		pthread_mutex_lock (&printf_mutex);
		printf_i = i;
		pthread_mutex_unlock (&printf_mutex);

		if (!GET_BIT (sieve, i))
			for (j = i + I2N (i); j <= N2I_limit; j += I2N (i))
				SET_BIT (sieve, j);
	}

	pthread_cancel (t);
	pthread_join (t, NULL);
	pthread_mutex_destroy (&printf_mutex);

	fprintf (stderr, "\n");

	printf ("%u ", 2);
	count = 1; /* 2 included here */
	for (i = 0; i <= N2I_limit; ++i)
		if (!GET_BIT (sieve, i))
		{
			printf ("%u ", I2N (i));
			++count;
		}

	printf ("\nPrimes found: " BITPOS_FORMAT "\n", count);

	free (sieve);

	return EXIT_SUCCESS;

out_small_limit:
	fprintf (stderr, "%s: Maximum too small\n", argv [0]);
	return EXIT_FAILURE;

out_no_mem:
	perror (argv[0]);
	return EXIT_FAILURE;
}