/*************************************** * * * Copyright (c) 1998 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /*------------------------------------------------------------------- * MatricesBooleennes.c Jean-Eric Pin 07/12/96 *------------------------------------------------------------------- */ #include <stdlib.h> #include <stdio.h> #include <limits.h> #include "Globales.h" #include "Main.h" #include "InitiauxFinaux.h" #include "MatricesBooleennes.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, NbElements; extern char **Messages; extern unsigned short *EtatsInitiaux, *EtatsFinaux; extern info *Table; /* La table contenant les informations sur les elements */ /************************************************************************ * * CopieMatricesBooleennes : copie x dans y * ************************************************************************/ void CopieMatricesBooleennes(element x, element y) { register short i, j; for (i = 0; i < NbEtats; i++) for (j = 0; j < NbEtats; j++) ((MatriceBooleenne)y)[i][j] = ((MatriceBooleenne)x)[i][j]; } /************************************************************************ * * EstEgalMatricesBooleennes : Teste l'egalite de deux matrices booleennes * ************************************************************************/ short EstEgalMatricesBooleennes(element x, element y) { register short i, j; for (i = 0; i < NbEtats; i++) for (j = 0; j < NbEtats; j++) if (((MatriceBooleenne)x)[i][j] != ((MatriceBooleenne)y)[i][j]) return(0); return(1); } /************************************ * * ProduitMatricesBooleennes * ************************************/ void ProduitMatricesBooleennes(element x, element y, element xy) { register short p, q, r; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { for (r = 0; r < NbEtats; r++) if (((MatriceBooleenne)x)[p][r] && ((MatriceBooleenne)y)[r][q]) break; ((MatriceBooleenne)xy)[p][q] = (boolean)(r < NbEtats) ; } } /************************************************************ * * HachageMatricesBooleennes * ************************************************************/ unsigned long HachageMatricesBooleennes(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 << 1) + ((MatriceBooleenne)x)[i][j]) % TailleTableDeHachage; return(h); } /************************************************************ * * HachageSecondaireMatricesBooleennes * ************************************************************/ unsigned long HachageSecondaireMatricesBooleennes(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 << 1) + ((MatriceBooleenne)x)[i][j]) % TailleTableDeHachageMoinsUn; return(1+h); /* Il faut eviter la valeur 0 ! */ } /******************************************************** * * FaireIdentiteMatricesBooleennes : Initialisation de l'identite * ********************************************************/ void FaireIdentiteMatricesBooleennes(element x) { short p, q; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) ((MatriceBooleenne)x)[p][q] = (p != q) ? '\0' : '\1'; } /**************************************************** * * SauvegardeMatricesBooleennes. OK * ****************************************************/ void SauvegardeMatricesBooleennes(FILE *MyFile) { short p, q; lettre a; fprintf(MyFile, "%8hu %% Taille des matrices\n", NbEtats); fprintf(MyFile, "%8lu %% Seuil\n", 0UL); fprintf(MyFile, "%8lu %% Periode\n", 1UL); for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) fprintf(MyFile, "%u ", ((MatriceBooleenne)Generateurs[a])[p][q]); fprintf(MyFile, "\n"); } fprintf(MyFile, "\n"); } if (PartiePointee && InitiauxDejaSpecifies) SauvegardeInitiaux(MyFile); if (PartiePointee && FinauxDejaSpecifies) SauvegardeFinaux(MyFile); } /**************************************************** * * LectureMatricesBooleennes. OK * ****************************************************/ void LectureMatricesBooleennes(FILE *MyFile) { short p, q; lettre a; 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++) { if (fscanf(MyFile, "%1s", &((MatriceBooleenne)Generateurs[a])[p][q]) != 1) { printf("scanf error\n"); exit(1); } ((MatriceBooleenne)Generateurs[a])[p][q] -= '0'; } if (!InitiauxDejaSpecifies) LectureInitiaux(MyFile); if (!FinauxDejaSpecifies) LectureFinaux(MyFile); } /**************************************************** * * EntreeMatricesBooleennes. Les matrices booleennes sont * des matrices ayant NbEtats lignes et NbEtats colonnes, * on comprimera peut etre un jour les booleens... * ****************************************************/ void EntreeMatricesBooleennes(void) { short p, q, n; lettre a; printf("%s ", Messages[M_Size_Boolean_matrices]); if (scanf("%hu", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } printf("\n"); TailleElement = NbEtats * NbEtats * sizeof(boolean); AlloueMemoireGenerateurs(); for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) { do { printf("%c[%d,%d] = ", a + 97, p + 1, q + 1); if (scanf("%hd", &n) != 1) { printf("scanf error\n"); exit(1); } } while (!((n == 0) || (n == 1))); ((MatriceBooleenne)Generateurs[a])[p][q] = (boolean)n; } } printf("\n"); } if (PartiePointee && (!FinauxDejaSpecifies)) EntreeEtatsInitiauxFinaux(); } /**************************************************** * * SortieMatricesBooleennes. Sortie d'un element. OK * ****************************************************/ void SortieMatricesBooleennes(element x) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) printf("%2c ", ((MatriceBooleenne)x)[p][q] + '0'); printf("|"); } printf("\n"); } /**************************************************** * * SortieLaTeXMatricesBooleennes. Sortie d'un element. OK * ****************************************************/ void SortieLaTeXMatricesBooleennes(element x, FILE *MyFile) { short p, q; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) fprintf(MyFile, "&%d ", ((MatriceBooleenne)x)[p][q]); fprintf(MyFile, "\n"); } /**************************************************** * * AlloueMemoireMatricesBooleennes. OK * ****************************************************/ element AlloueMemoireMatricesBooleennes(void) { element Element; short j; Element = (void *)ALLOC(boolean *, 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++) { ((MatriceBooleenne)Element)[j] = (boolean *)ALLOC(boolean, NbEtats); if (((MatriceBooleenne)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; } /**************************************************** * * LibereMemoireMatricesBooleennes. OK * ****************************************************/ void LibereMemoireMatricesBooleennes(element Element) { short j; for (j = 0; j < NbEtats; j++) free(((MatriceBooleenne)Element)[j]); free(Element); #ifdef DEBUG ElementsAlloues--; #endif /* DEBUG */ } /**************************************************************************** * * EntreePartieMatricesBooleennes. OK * Definit la partie pointee P a partir des ensembles I (etats initiaux) et F * (etats finaux). * P = { u | il existe i dans I et f dans F tels que u_{i,f} = 1 } * ****************************************************************************/ void EntreePartieMatricesBooleennes(void) { unsigned long u; short i, j = 0; if (InitiauxDejaSpecifies && FinauxDejaSpecifies) /* Etat initiaux et finaux specifies */ { for (u = IDENTITE; u <= NbElements; u++) { for (i = 0; i < NbEtats; i++) { if (EtatsInitiaux[i]) /* i etat initial */ for (j = 0; j < NbEtats; j++) if ((EtatsFinaux[j]) && (((MatriceBooleenne)TableDesValeurs[u])[i][j])) break; /* j etat final et M_{i,j} = 1 */ if (j != NbEtats) /* x est dans P, inutile de poursuivre. */ break; } if (i != NbEtats) Table[u].Statut |= EST_DANS_P; else Table[u].Statut &= ~EST_DANS_P; } } else /* Pas d'etats initiaux ni finaux specifies */ EntreePartieStandard(); }