# Projet LEPL1503 - Prime factorization

"Prime factorization" est un programme écrit en langage C. Il prend en entrée un fichier texte de nombres et renvoie un nouveau fichier texte avec, à chaque ligne, le nombre à factoriser et la liste de ses diviseurs premiers. Le programme fonctionne en "muli-threading" et le nombre de threads est paramétrable.


## Objectif du projet
Convertir et optimiser un programme python en langage C et retourner les diviseurs premiers de chaque entier d'une liste de nombres.

## Fichiers
* **Makefile** : Permet l'exécution de commandes (compilation du code, exécution des tests).
* **run.c** : Contient le corps du code de l'algorithme
* **run.h** : Contient les signatures des fonctions de run.c.
* **main.c** : Contient la fonction main du programme principal (run.c).
* **test.c** : Contient des tests en CUnit permettant de tester les fonctions de run.c. 
* **Test_files** : Dossier contenant différents input et output pour divers exemples de nombres (entiers,petits,grands).

## Librairies utilisées
- Librairies standards en C
- Librairie pthreads et semaphores: exécution des threads et des semaphores
- Librairie Cunit: utilisée pour les tests unitaires
- Librairie time: calcule le temps d'exécution du programme


## Installation

Les packages suivants doivent être installés :

* [CUnit](https://sites.uclouvain.be/SystInfo/notes/Outils/html/cunit.html) 
* Valgrind : sudo apt-get install valgrind
* Cppcheck : sudo apt-get install cppcheck

## Utilisation

* Pour compiler le programme : make fact

* Pour exécuter le fichier exécutable "fact" : ./fact [-N nombre_de_threads] input output

* Pour compiler et tester (suite de tests unitaires) le programme : make test 

* Pour compiler et effectuer une analyse avec "Valgrind" : make val

* Pour compiler, et obtenir le rapport d'analyse .xml de "Valgrind" : make val_xml

* Pour effectuer une analyse avec "cppcheck" : make cpp

* Pour compiler et obtenir le rapport d'analyse .xml  de "cppcheck" : make cpp_xml

* Pour nettoyer les fichiers auxiliaires générés et l'exécutable : make clean


## Architecture du programme:

Le travail est décomposé en 3 sections coordonnées via un double problème du producteur-consommateur :

* 1 thread s'occupe de:
    * lire le fichier input 

    * stocker chacune des lignes sous forme de chaine de charactère dans un 1er tableau

* N threads s'occupent de :
    * récupérer les chaines de caractères dans le premier tableau

    * les convertir en 'unsigned long long' et calculer leur liste de diviseurs premiers grâce au test de primalité de Fermat

    * Stocker ces listes dans un 2e tableau
    
* 1 thread s'occupe de :
    * récupérer les listes de diviseurs dans le 2e tableau

    * Retranscrire dans le bon format le nombre à factoriser et ses diviseurs premiers dans le fichier output

Note : 
* Les accès aux tableaux sont coordonnés par des mutex (1 par tableau) et des sémaphores

* Les diviseurs premiers d'un même nombre sont stockés dans une circular linked list

* Le nombre de threads de calcul par défaut est 8


## Architecture des tests :

10 tests sont réalisés afin de vérifier:

* "is_div" (2 tests)
* "is_prime" (2 tests)
* "mod_pow"
* "randomiser"
* Le fonctionnement complet pour un fichier vide (N = 4)
* Le fonctionnement complet pour un fichier d'une ligne : check du format et des diviseurs (N = 4)
* Le fonctionnement complet pour un fichier de 100 lignes : check du nombre de lignes (réalisé avec N = 4 puis N = 1)

# lepl1503-2020-groupe-M2