/*************************************** * * * Copyright (c) 1998 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /*------------------------------------------------------------------- * Matrices.c Jean-Eric Pin 07/12/96 *------------------------------------------------------------------- */ #include <ctype.h> #include <stdlib.h> #include <stdio.h> #include <limits.h> #include <errno.h> #include "Erreurs.h" #include "Globales.h" #include "Main.h" #include "InitiauxFinaux.h" #include "Matrices.h" #include "Memoire.h" #include "Utilitaires.h" #ifdef DEBUG extern long ElementsAlloues; #endif /* DEBUG */ extern unsigned short NbEtats, NbLettres, PartiePointee, InitiauxDejaSpecifies, FinauxDejaSpecifies; extern unsigned long Periode, Seuil; extern unsigned long TailleElement; extern element *Generateurs, *TableDesValeurs; extern unsigned long TailleTableDeHachage, TailleTableDeHachageMoinsUn; extern unsigned long TailleMaxi; extern char **Messages; /************************************************************************ * * CopieMatrices : copie x dans y * ************************************************************************/ void CopieMatrices(element x, element y) { register short i, j; for (i = 0; i < NbEtats; i++) for (j = 0; j < NbEtats; j++) ((Matrice)y)[i][j] = ((Matrice)x)[i][j]; } /************************************************************************ * * EstEgalMatrice : Teste l'egalite de deux matrices. * ************************************************************************/ short EstEgalMatrices(element x, element y) { register short i, j; for (i = 0; i < NbEtats; i++) for (j = 0; j < NbEtats; j++) if (((Matrice)x)[i][j] != ((Matrice)y)[i][j]) return(0); return(1); } /***************** * * SeuilPeriode. OK * ******************/ long SeuilPeriode(long x) { if (Periode && (x > Seuil)) x = Seuil + (x - Seuil) % Periode; return(x); } /**************************************************** * * EntreeSeuil. OK * ****************************************************/ void EntreeSeuil(void) { printf("%s ", Messages[M_Threshold_semiring]); /* printf("Seuil du semianneau ? "); */ if (scanf("%lud", &Seuil) != 1) { printf("scanf error\n"); exit(1); } } /**************************************************** * * EntreePeriode. OK * ****************************************************/ void EntreePeriode(void) { printf("%s ", Messages[M_Period_semiring]); /* printf("Periode du semianneau ? "); */ if (scanf("%lud", &Periode) != 1) { printf("scanf error\n"); exit(1); } } /**************************************************** * * EntreeSemiAnneauZst. OK * ****************************************************/ void EntreeSemiAnneauZst(void) { printf("%s\n", Messages[M_Z_st]); /* printf("Semianneau Z_{s,t} ou s est le seuil et t la periode\n"); */ EntreeSeuil(); EntreePeriode(); } /**************************************************** * * SauvegardeMatrices. OK * ****************************************************/ void SauvegardeMatrices(FILE *MyFile) { short p, q; lettre a; long c; int erreur; if (fprintf(MyFile, "%8hu %% Taille des matrices\n", NbEtats) < 0) { erreur = errno; printf("fprintf %8hu %% Taille des matrices failed!\n", NbEtats); Erreur_printf(erreur); return; } if (fprintf(MyFile, "%8lu %% Seuil\n", Seuil) < 0) { erreur = errno; printf("fprintf %8lu %% Seuil failed!\n", Seuil); Erreur_printf(erreur); return; } if (fprintf(MyFile, "%8lu %% Periode\n", Periode) < 0) { erreur = errno; printf("fprintf %8lu %% Periode failed!\n", Periode); Erreur_printf(erreur); return; } for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) { c = ((Matrice)Generateurs[a])[p][q]; if (c == LONG_MAX) { if (fprintf(MyFile, "+%% ") < 0) { erreur = errno; printf("fprintf +%% failed!\n"); Erreur_printf(erreur); return; } } else if (c == LONG_MIN) { if (fprintf(MyFile, "-%% ") < 0) { erreur = errno; printf("fprintf -%% failed!\n"); Erreur_printf(erreur); return; } } else { if (fprintf(MyFile, "%ld ", c) < 0) { erreur = errno; printf("fprintf %ld failed!\n", c); Erreur_printf(erreur); return; } } } if (fprintf(MyFile, "\n") < 0) { erreur = errno; printf("fprintf \\n failed!\n"); Erreur_printf(erreur); return; } } if (fprintf(MyFile, "\n") < 0) { erreur = errno; printf("fprintf \\n failed!\n"); Erreur_printf(erreur); return; } } if (PartiePointee && InitiauxDejaSpecifies) SauvegardeInitiaux(MyFile); if (PartiePointee && FinauxDejaSpecifies) SauvegardeFinaux(MyFile); } /**************************************************** * * LectureMatrices. OK * ****************************************************/ void LectureMatrices(FILE *MyFile) { short p, q; lettre a; int c, d; if (fscanf(MyFile, "%hu %% Taille des matrices", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } if (fscanf(MyFile, "%lu %% Seuil", &Seuil) != 1) { printf("scanf error\n"); exit(1); } if (fscanf(MyFile, "%lu %% Periode", &Periode) != 1) { printf("scanf error\n"); exit(1); } AlloueMemoireGenerateurs(); for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) { while (isspace(c = getc(MyFile))) ; if (isdigit(c)) { ungetc(c, MyFile); if (fscanf(MyFile, "%ld", &((Matrice)Generateurs[a])[p][q]) != 1) { printf("scanf error\n"); exit(1); } } else if (c == '+') /* +% code +infini */ { getc(MyFile); /* Pour absorber le % */ ((Matrice)Generateurs[a])[p][q] = LONG_MAX; } else if (c == '-') /* -% code -infini */ { d = getc(MyFile); if (d == '%') /* Il faut tester si le caractere suivant est un % */ ((Matrice)Generateurs[a])[p][q] = LONG_MIN; else { ungetc(d, MyFile); ungetc(c, MyFile); if (fscanf(MyFile, "%ld", &((Matrice)Generateurs[a])[p][q]) != 1) /* et pas "%lu" !! */ { printf("scanf error\n"); exit(1); } } } } } } if (!InitiauxDejaSpecifies) LectureInitiaux(MyFile); if (!FinauxDejaSpecifies) LectureFinaux(MyFile); } /**************************************************** * * EntreeMatricesEntieres. OK * ****************************************************/ void EntreeMatricesEntieres(void) { short p, q; lettre a; static char s[] = " "; EntreeSemiAnneauZst(); printf("%s ", Messages[M_Size_matrices_question_mark]); /* printf("Taille des matrices ? "); */ if (scanf("%hu", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } printf("\n"); TailleElement = NbEtats * NbEtats * sizeof(short); AlloueMemoireGenerateurs(); for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { printf("%c[%d,%d] = ", a + 97, p + 1, q + 1); if (scanf("%s", s) != 1) { printf("scanf error\n"); exit(1); } ((Matrice)Generateurs[a])[p][q] = atol(s); } printf("\n"); } if (PartiePointee && (!FinauxDejaSpecifies)) EntreeEtatsInitiauxFinaux(); } /************************************ * * ProduitMatricesEntieres * ************************************/ void ProduitMatricesEntieres(element x, element y, element xy) { register short p, q, r; long v; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { v = 0; for (r = 0; r < NbEtats; r++) v = v + ((Matrice)x)[p][r] * ((Matrice)y)[r][q]; ((Matrice)xy)[p][q] = SeuilPeriode(v) ; } } /************************************************************ * * HachageMatrices * ************************************************************/ unsigned long HachageMatrices(element x) { register short i, j; register unsigned long h; h = 0; for (i = 0; i < NbEtats; i++) for (j = 0; j < NbEtats; j++) h = ((h << 4) + ((Matrice)x)[i][j]) % TailleTableDeHachage; /* (h << 4) : Le 4 est un peu arbitraire */ h = abs(h) % TailleTableDeHachage; return(h); } /************************************************************ * * HachageSecondaireMatrices * ************************************************************/ unsigned long HachageSecondaireMatrices(element x) { register short i, j; register unsigned long h; h = 0; for (i = 0; i < NbEtats; i++) for (j = 0; j < NbEtats; j++) h = ((h << 4) + ((Matrice)x)[i][j]) % TailleTableDeHachageMoinsUn; /* Le 4 est un peu arbitraire */ return(1+h); } /******************************************************** * * FaireIdentiteMatricesEntieres : Initialisation de l'identite * ********************************************************/ void FaireIdentiteMatricesEntieres(element x) { short p, q; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) ((Matrice)x)[p][q] = 0; for (p = 0; p < NbEtats; p++) ((Matrice)x)[p][p] = 1; } /**************************************************** * * MatricesEntieres : Sortie d'un element. OK * ****************************************************/ void SortieMatricesEntieres(element x) { short p, q, NbDeChiffresSeuil; NbDeChiffresSeuil = NombreDeChiffres(Seuil); for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) printf("%*ld ", NbDeChiffresSeuil, ((Matrice)x)[p][q]); printf("|"); } printf("\n"); } /**************************************************** * * MatricesEntieres : Sortie LaTeX d'un element. OK * ****************************************************/ void SortieLaTeXMatricesEntieres(element x, FILE *MyFile) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]); } fprintf(MyFile, "\n"); } /**************************************************** * * AlloueMemoireMatrice. OK * ****************************************************/ element AlloueMemoireMatrice(void) { element Element; short j; Element = (void *)ALLOC(long *, NbEtats); if (Element == NULL) { printf("%s %s\n", Messages[M_Pb_memory], Messages[M_Pb_matrix]); /* Probleme lors de l'allocation memoire d'une matrice ! */ exit(1); } for (j = 0; j < NbEtats; j++) { ((Matrice)Element)[j] = (long *)ALLOC(long, NbEtats); if (((Matrice)Element)[j] == NULL) { printf("%s %s\n", Messages[M_Pb_memory], Messages[M_Pb_matrix]); /* Probleme lors de l'allocation memoire d'une matrice ! */ exit(1); } } #ifdef DEBUG ElementsAlloues++; #endif /* DEBUG */ return Element; } /**************************************************** * * LibereMemoireMatrice. OK * ****************************************************/ void LibereMemoireMatrice(element Element) { short j; for (j = 0; j < NbEtats; j++) free(((Matrice)Element)[j]); free(Element); #ifdef DEBUG ElementsAlloues--; #endif /* DEBUG */ }