tfd.c (17429B)
1 #include <assert.h> 2 #include <stdbool.h> 3 #include <stdint.h> 4 #include <stdio.h> 5 #include <string.h> 6 7 #include "tampex.h" 8 #include "tfd.h" 9 #include "tfm.h" 10 11 #define TAMPON_LNGR_DEF 64 12 13 /* Renvoie le maximum de deux nombres. */ 14 #define MAX(n1, n2) ((n1) > (n2) ? (n1) : (n2)) 15 16 /* Aligner un pointeur p sur n octets. */ 17 #define ALIGNER(p, n) (((p) + ((n) - 1)) & -(n)) 18 19 /* Écrire la valeur val dans le tampon tp, en préservant le boutisme de 20 * l’hôte. ecrire_16() écrit deux octets et ecrire_32() en écrit 4. 21 * Renvoie un pointer vers l’octet suivant le dernier écrit. */ 22 static void *ecrire_16(void *tp, uint16_t val); 23 static void *ecrire_32(void *tp, uint32_t val); 24 25 /* Créer le segmenteur de symboles. 26 * Renvoie un pointeur vers un tampex, ou NULL en cas d’erreur. */ 27 static void *segmenteur(struct tfm *tfm, uint16_t *se); 28 29 /* Trouver une paire libre dans le segmenteur. 30 * Renvoie l’indice de la paire trouvée, ou -1 en cas d’erreur. */ 31 static ssize_t segmenteur_libre(uint16_t (**segm)[2]); 32 33 /* Trouver la paire de base dans le segmenteur segm de l’état ietat dans 34 * l’automate tfm. 35 * Renvoie l’indice de la base, ou -1 en cas d’erreur. */ 36 static ssize_t segmenteur_base(uint16_t (**segm)[2], struct tfm *tfm, 37 size_t ietat); 38 39 /* Tester si la paire à l’indice i dans le segmenteur segm est libre. 40 * Renvoie 1 si elle est libre et 0 si elle ne l’est pas, ou -1 en cas 41 * d’erreur. */ 42 static int segmenteur_tlibre(uint16_t (**segm)[2], size_t i); 43 44 /* Créer un automate au format tfm à partir d’une liste de symboles d’entrée. 45 * Renvoie un pointeur vers un tfm, ou NULL en cas d’erreur. */ 46 static struct tfm *automate_symbs(struct tfm *tfm, uint16_t *se, 47 uint32_t **finaux); 48 49 /* Obtenir la liste des identifiants de symbole d’entrée (se) et de sortie (ss) 50 * du tranducteur tfm. 51 * Renvoie 0, ou -1 en cas d’erreur. */ 52 static int symboles_id(struct tfm *tfm, uint16_t **se, uint16_t **ss); 53 54 /* Afficher un segmenteur en sortie standard. */ 55 static void segmenteur_afficher(struct tfm *tfm, uint16_t *se); 56 57 /* Créer le transducteur à parir d’un tfm. 58 * Renvoie un pointeur vers un tampex, ou NULL en cas d’erreur. */ 59 static void *transducteur(struct tfm *tfm); 60 61 int 62 tfd_ecrire(FILE *f, struct tfm *tfm) 63 { 64 uint8_t ent[TFD_ENTETE_TLL]; /* Contenu de l’entête. */ 65 uint8_t *pent; /* Pointeur vers l’entête. */ 66 size_t dec; /* Décalage courant dans le fichier. */ 67 void *te; /* Pointeur réutilisable vers un tampon extensible. */ 68 void *se; /* Liste d’identifiants de symboles d’entrée. */ 69 size_t lngr; /* Longueur d’un tampon. */ 70 71 assert(f); 72 assert(tfm); 73 74 dec = ALIGNER(TFD_ENTETE_TLL, 8); 75 if (fseek(f, dec, SEEK_SET) != 0) 76 return -1; 77 78 pent = ent; 79 80 /* Écrire le nombre magique. */ 81 *pent++ = (TFD_MAGIQUE >> 8) & 0xFF; 82 *pent++ = (TFD_MAGIQUE >> 0) & 0xFF; 83 84 /* Écrire la version. */ 85 *pent++ = (TFD_VERSION >> 8) & 0xFF; 86 *pent++ = (TFD_VERSION >> 0) & 0xFF; 87 88 /* Écrire le témoin de boutisme. */ 89 pent = ecrire_16(pent, TFD_TEMOIN); 90 91 /* Écrire la liste de symboles. 92 * Le format de la liste des symboles du tfd et du tfm est le même. */ 93 lngr = tampex_esp(tfm->symbs); 94 if (fwrite(tfm->symbs, 1, lngr, f) != lngr) 95 return -1; 96 pent = ecrire_32(pent, dec); 97 pent = ecrire_32(pent, lngr); 98 99 dec += lngr; 100 dec = ALIGNER(dec, 2); 101 if (fseek(f, dec, SEEK_SET) != 0) 102 return -1; 103 104 /* Écrire la liste d’identifiants de symbole d’entrée. */ 105 if (symboles_id(tfm, (uint16_t **)&se, (uint16_t **)&te) < 0) 106 return -1; 107 lngr = tampex_esp(se); 108 if (fwrite(se, 1, lngr, f) != lngr) { 109 tampex_libr(se); 110 tampex_libr(te); 111 return -1; 112 } 113 pent = ecrire_32(pent, dec); 114 pent = ecrire_32(pent, lngr); 115 116 dec += lngr; 117 dec = ALIGNER(dec, 2); 118 if (fseek(f, dec, SEEK_SET) != 0) { 119 tampex_libr(se); 120 tampex_libr(te); 121 return -1; 122 } 123 124 /* Écrire la liste d’identifiants de symbole de sortie. */ 125 lngr = tampex_esp(te); 126 if (fwrite(te, 1, lngr, f) != lngr) { 127 tampex_libr(se); 128 tampex_libr(te); 129 return -1; 130 } 131 tampex_libr(te); 132 pent = ecrire_32(pent, dec); 133 pent = ecrire_32(pent, lngr); 134 135 dec += lngr; 136 dec = ALIGNER(dec, 2); 137 if (fseek(f, dec, SEEK_SET) != 0) { 138 tampex_libr(se); 139 return -1; 140 } 141 142 /* Écrire le segmenteur. */ 143 if ((te = segmenteur(tfm, se)) == NULL) { 144 tampex_libr(se); 145 return -1; 146 } 147 lngr = tampex_esp(te); 148 if (fwrite(te, 1, lngr, f) != lngr) { 149 tampex_libr(te); 150 tampex_libr(se); 151 return -1; 152 } 153 tampex_libr(te); 154 tampex_libr(se); 155 pent = ecrire_32(pent, dec); 156 pent = ecrire_32(pent, lngr); 157 158 dec += lngr; 159 dec = ALIGNER(dec, 4); 160 if (fseek(f, dec, SEEK_SET) != 0) 161 return -1; 162 163 /* Écrire le transducteur. */ 164 if ((te = transducteur(tfm)) == NULL) 165 return -1; 166 lngr = tampex_esp(te); 167 if (fwrite(te, 1, lngr, f) != lngr) { 168 tampex_libr(te); 169 return -1; 170 } 171 pent = ecrire_32(pent, dec); 172 pent = ecrire_32(pent, lngr); 173 tampex_libr(te); 174 175 /* Écrire l’entête. */ 176 if (fseek(f, 0, SEEK_SET) != 0) 177 return -1; 178 if (fwrite(ent, 1, TFD_ENTETE_TLL, f) != TFD_ENTETE_TLL) 179 return -1; 180 181 return 0; 182 } 183 184 static void * 185 ecrire_16(void *tp, uint16_t val) 186 { 187 assert(tp); 188 189 *(uint16_t *)tp = val; 190 191 return ((uint16_t *)tp) + 1; 192 } 193 194 static void * 195 ecrire_32(void *tp, uint32_t val) 196 { 197 assert(tp); 198 199 *(uint32_t *)tp = val; 200 201 return ((uint32_t *)tp) + 1; 202 } 203 204 static void * 205 segmenteur(struct tfm *tfm, uint16_t *se) 206 { 207 uint16_t (*segm)[2]; /* Segmenteur (base, origine). */ 208 struct tfm *symbs; /* Automate des symboles. */ 209 uint32_t *finaux; /* Symboles correspondants aux états finaux. */ 210 size_t (*pile)[2]; /* Pile: (indice dans segm, état). */ 211 ssize_t ipile; /* Indice dans la pile. */ 212 size_t isegm; /* Indice dans le segmenteur. */ 213 size_t ietat, ntrans, itrans; 214 ssize_t base; 215 size_t bmax; /* Base maximale. */ 216 unsigned char c; 217 218 assert(tfm); 219 220 /* Initialiser le segmenteur et la pile. */ 221 if ((segm = tampex_init(TAMPON_LNGR_DEF, sizeof *segm)) == NULL) 222 return NULL; 223 if ((pile = tampex_init(TAMPON_LNGR_DEF, sizeof *pile)) == NULL) 224 goto erreur1; 225 226 /* Créer l’automate de symboles. */ 227 if ((symbs = automate_symbs(tfm, se, &finaux)) == NULL) 228 goto erreur2; 229 230 /* Le premier état ne peut être final; car un symbole doit avoir une 231 * longueur supérieure à 0. */ 232 assert(!symbs->etats[0].final); 233 234 /* Empiler le premier état. */ 235 if ((ipile = tampex_empl((void **)&pile)) < 0) 236 goto erreur3; 237 assert(ipile == 0); 238 pile[ipile][0] = 0; 239 pile[ipile][1] = 0; 240 241 bmax = 1; 242 243 do { 244 /* Dépiler. */ 245 ipile = tampex_dpl(pile); 246 isegm = pile[ipile][0]; 247 ietat = pile[ipile][1]; 248 249 /* Si ietat est un état final. */ 250 if (tfm_tfinal(symbs, ietat)) { 251 if ((base = segmenteur_libre(&segm)) < 0) 252 goto erreur3; 253 segm[isegm][0] = (base << 1) | 0x01; 254 isegm = base; 255 segm[isegm][1] = (finaux[ietat] << 1) | 0x01; 256 /* Marquer comme sans descendant. Sera réécrit s’il en a. A 257 * aussi pour effet de réserver la paire. */ 258 segm[isegm][0] = (0 << 1) | 0x01; 259 } 260 261 /* S’il y a des transitions sortantes. */ 262 if ((ntrans = symbs->etats[ietat].ntrans) > 0) { 263 if ((base = segmenteur_base(&segm, symbs, ietat)) < 0) 264 goto erreur3; 265 segm[isegm][0] = (base << 1) | 0x00; 266 for (itrans = symbs->etats[ietat].trans; 267 ntrans--; 268 itrans = symbs->trans[itrans].prch) { 269 assert((symbs->trans[itrans].se & 0x01) == 270 TFM_SNORMAL); 271 if (tfm_symb_obt(symbs, symbs->trans[itrans].se, 272 (char *)&c, 1) != 1) 273 goto erreur3; 274 segm[base + c][0] = 1; /* Réserver la paire. */ 275 segm[base + c][1] = (isegm << 1) | 0x00; 276 bmax = MAX(isegm, bmax); 277 if ((ipile = tampex_empl((void **)&pile)) < 0) 278 goto erreur3; 279 pile[ipile][0] = base + c; 280 pile[ipile][1] = symbs->trans[itrans].ed; 281 } 282 } 283 } while (tampex_nelem(pile)); 284 285 tfm_libr(symbs); 286 tampex_libr(finaux); 287 tampex_libr(pile); 288 289 /* Faire que les données du transducteur ne puissent interférer avec 290 * l’interprétation du segmenteur en assurant que la base la plus haute 291 * soit suivie par au moins 255 paires dans le segmenteur. */ 292 tampex_minim((void **)&segm, bmax + 255); 293 294 /* Désactiver les paires vides. */ 295 for (isegm = 0; tampex_dedans(segm, isegm); isegm++) 296 if (segm[isegm][0] == 0) 297 segm[isegm][1] = (0 << 1) | 0x01; 298 299 return segm; 300 301 erreur3: 302 tfm_libr(symbs); 303 tampex_libr(finaux); 304 erreur2: 305 tampex_libr(pile); 306 erreur1: 307 tampex_libr(segm); 308 return NULL; 309 } 310 311 static ssize_t 312 segmenteur_libre(uint16_t (**segm)[2]) 313 { 314 size_t i; 315 316 assert(segm); 317 assert(*segm); 318 319 for (i = 1;; i++) { 320 switch (segmenteur_tlibre(segm, i)) { 321 case 0: continue; 322 case 1: return i; 323 default: return -1; 324 } 325 } 326 327 assert(0); 328 } 329 330 static ssize_t 331 segmenteur_base(uint16_t (**segm)[2], struct tfm *tfm, size_t ietat) 332 { 333 size_t i; 334 size_t itrans, ntrans; 335 char c; 336 337 assert(segm); 338 assert(*segm); 339 assert(tfm); 340 341 for (i = 1;; i++) { 342 for (itrans = tfm->etats[ietat].trans, 343 ntrans = tfm->etats[ietat].ntrans; 344 ntrans--; itrans = tfm->trans[itrans].prch) { 345 assert((tfm->trans[itrans].se & 0x01) == TFM_SNORMAL); 346 347 if (tfm_symb_obt(tfm, tfm->trans[itrans].se, &c, 1) != 1) 348 return -1; 349 switch (segmenteur_tlibre(segm, i + (unsigned char)c)) { 350 case 0: goto encore; 351 case 1: continue; 352 default: return -1; 353 } 354 } 355 return i; 356 encore:; 357 } 358 359 assert(0); 360 } 361 362 static int 363 segmenteur_tlibre(uint16_t (**segm)[2], size_t i) 364 { 365 assert(segm); 366 assert(*segm); 367 368 if (tampex_minim((void **)segm, i) < 0) 369 return -1; 370 if ((*segm)[i][0] == 0) 371 return 1; 372 else 373 return 0; 374 } 375 376 static void 377 segmenteur_afficher(struct tfm *tfm, uint16_t *se) 378 { 379 size_t i; 380 uint16_t (*segm)[2]; 381 382 assert(tfm); 383 assert(se); 384 385 segm = segmenteur(tfm, se); 386 387 for (i = 0; tampex_dedans(segm, i); i++) { 388 printf("%lu\t%s%u\t%s%u", 389 i, 390 segm[i][0] & 0x01 ? "*" : "", 391 segm[i][0] >> 1, 392 segm[i][1] & 0x01 ? "*" : "", 393 segm[i][1] >> 1); 394 if (segm[i][1] & 0x01 && segm[i][1] != ((0 << 1) | 0x01)) { 395 fputc('\t', stdout); 396 fwrite(tfm->symbs + (segm[i][1] >> 1) + 1, 397 1, 398 *(uint8_t *)(tfm->symbs + (segm[i][1] >> 1)), 399 stdout); 400 } 401 fputc('\n', stdout); 402 } 403 } 404 405 /* La routine fonctionne en parcourant tous les symboles d’un transducteur. À 406 * chaque nouveau symbole, il parcourt l’automate de symboles à partir de son 407 * premier état et passe d’état en état en suivant les caractères du symbole et 408 * en ajoutant les transitions manquantes. */ 409 static struct tfm * 410 automate_symbs(struct tfm *tfm, uint16_t *se, uint32_t **finaux) 411 { 412 struct tfm *symbs; 413 size_t pos; /* Position courante dans la liste de symboles. */ 414 uint16_t isymb; /* Indice d’un symbole. */ 415 ssize_t id; /* Identifiant de symbole. */ 416 size_t ietat, ietatp; /* Identifiants des états courant et 417 précédent. */ 418 unsigned char lngr; /* Longueur d’un symbole. */ 419 size_t ntrans, itrans; 420 char c; 421 422 assert(tfm); 423 assert(finaux); 424 425 /* Initialiser l’automate de symboles. */ 426 if ((symbs = tfm_init()) == NULL) 427 return NULL; 428 429 /* Initialiser *finaux. */ 430 if ((*finaux = tampex_init(TAMPON_LNGR_DEF, sizeof(uint32_t))) == NULL) 431 goto erreur1; 432 433 /* Créer le premier état. */ 434 if (tampex_minim((void **)&symbs->etats, 0) < 0) 435 goto erreur2; 436 437 /* Parcourir les symboles. */ 438 for (isymb = 0; tampex_dedans(se, isymb); isymb++) { 439 pos = se[isymb]; /* Position courante. */ 440 441 /* Obtenir la longueur du symbole. */ 442 lngr = tfm->symbs[pos++]; 443 444 /* Parcourir les caractères du symbole. */ 445 for (ietat = 0; lngr--; pos++) { 446 447 /* Chercher une transition sortante pour liste[pos]. */ 448 for (ntrans = symbs->etats[ietat].ntrans, 449 itrans = symbs->etats[ietat].trans; 450 ntrans--; 451 itrans = symbs->trans[itrans].prch) { 452 if (tfm_symb_obt(symbs, symbs->trans[itrans].se, 453 &c, 1) != 1) 454 goto erreur2; 455 if (c == tfm->symbs[pos]) { 456 /* La bonne transition a été trouvée. Passer au 457 * prochain caractère et au prochain état. */ 458 ietat = symbs->trans[itrans].ed; 459 goto pcar; 460 } 461 } 462 463 /* Aucune transition adéquate n’a été trouvée. En ajouter 464 * une. */ 465 ietatp = ietat; 466 ietat = tampex_nelem(symbs->etats); 467 if (tampex_minim((void **)&symbs->etats, ietat) < 0) 468 goto erreur2; 469 if ((id = tfm_symb_id(symbs, tfm->symbs + pos, 1)) < 0) 470 goto erreur2; 471 if (tfm_ajt(symbs, ietatp, ietat, id, id) < 0) 472 goto erreur2; 473 474 pcar:; 475 } 476 477 /* Marquer le dernier état d’un symbole comme final. */ 478 if (tfm_mfinal(symbs, ietat) < 0) 479 goto erreur2; 480 if (tampex_minim((void **)finaux, ietat) < 0) 481 goto erreur2; 482 (*finaux)[ietat] = se[isymb]; 483 } 484 485 return symbs; 486 487 erreur2: 488 tampex_libr(*finaux); 489 erreur1: 490 tfm_libr(symbs); 491 return NULL; 492 } 493 494 static int 495 symboles_id(struct tfm *tfm, uint16_t **se, uint16_t **ss) 496 { 497 size_t ise, iss; /* Indices dans se et ss. */ 498 char *dejala; /* Indique si l’identifiant est déjà dans se (& 0x01) ou 499 dans ss (& 0x02). */ 500 size_t ietat, ntrans, itrans; 501 size_t isymb; /* Identifiant de symbole. */ 502 503 assert(tfm); 504 assert(se); 505 assert(ss); 506 507 /* Initialiser se, ss et dejala. */ 508 if ((*se = tampex_init(TAMPON_LNGR_DEF, sizeof(uint16_t))) == NULL) 509 return -1; 510 if ((*ss = tampex_init(TAMPON_LNGR_DEF, sizeof(uint16_t))) == NULL) 511 goto erreur1; 512 if ((dejala = tampex_init(TAMPON_LNGR_DEF, sizeof *dejala)) == NULL) 513 goto erreur2; 514 515 ise = iss = 0; 516 517 /* Parcourir les états. */ 518 for (ietat = 0; tampex_dedans(tfm->etats, ietat); ietat++) { 519 /* Parcourir les transitions. */ 520 for (itrans = tfm->etats[ietat].trans, 521 ntrans = tfm->etats[ietat].ntrans; 522 ntrans--; itrans = tfm->trans[itrans].prch) { 523 524 /* Symbole d’entrée. */ 525 /* Ignorer les symboles spéciaux. */ 526 if (((isymb = tfm->trans[itrans].se) & 0x01) == 527 TFM_SSPECIAL) 528 continue; 529 isymb >>= 1; 530 /* Ne pas ajouter le symbole s’il est déjà la. */ 531 if (tampex_minim((void **)&dejala, isymb) < 0) 532 goto erreur3; 533 if (dejala[isymb] & 0x01) 534 continue; 535 /* Ajouter le symbole. */ 536 if (tampex_minim((void **)se, ise) < 0) 537 goto erreur3; 538 (*se)[ise++] = isymb; 539 dejala[isymb] |= 0x01; 540 541 /* Symbole de sortie. */ 542 /* Ignorer les symboles spéciaux. */ 543 if (((isymb = tfm->trans[itrans].ss) & 0x01) == 544 TFM_SSPECIAL) 545 continue; 546 isymb >>= 1; 547 /* Ne pas ajouter le symbole s’il est déjà la. */ 548 if (tampex_minim((void **)&dejala, isymb) < 0) 549 goto erreur3; 550 if (dejala[isymb] & 0x02) 551 continue; 552 /* Ajouter le symbole. */ 553 if (tampex_minim((void **)ss, iss) < 0) 554 goto erreur3; 555 (*ss)[iss++] = isymb; 556 dejala[isymb] |= 0x02; 557 } 558 } 559 560 tampex_libr(dejala); 561 return 0; 562 563 erreur3: 564 tampex_libr(dejala); 565 erreur2: 566 tampex_libr(*ss); 567 erreur1: 568 tampex_libr(*se); 569 return -1; 570 } 571 572 static void * 573 transducteur(struct tfm *tfm) 574 { 575 uint16_t *t; 576 size_t pos; 577 uint32_t *corr; /* Correspondances entre ietat et la position dans le 578 tampon. */ 579 size_t ietat; 580 ssize_t itrans; 581 582 assert(tfm); 583 584 /* Initialiser le transducteur et le tampon corr. */ 585 if ((t = tampex_init(TAMPON_LNGR_DEF, sizeof(uint16_t))) == NULL) 586 return NULL; 587 if ((corr = tampex_init(TAMPON_LNGR_DEF, sizeof(uint32_t))) == NULL) 588 goto erreur1; 589 590 /* Les transitions du tfm doivent être triées. */ 591 tfm_trier(tfm); 592 593 pos = 0; 594 595 /* Ajouter un état initial standard. Il permet de simplifier 596 * l’interprétation. */ 597 assert(TAMPON_LNGR_DEF >= 8); 598 t[pos] = 1; /* L’état contient une transition et n’est pas final. */ 599 pos += 4; 600 t[pos] = TFD_SYMB_EPSILON; /* Symbole d’entrée. */ 601 t[pos + 1] = TFD_SYMB_EPSILON; /* Symbole de sortie. */ 602 ecrire_32(t + pos + 2, 2); /* Mène au véritable état initial. */ 603 pos += 4; 604 605 /* Parcourir les états. */ 606 for (ietat = 0; tampex_dedans(tfm->etats, ietat); ietat++) { 607 /* Ajouter l’état à la correspondance. */ 608 if (tampex_minim((void **)&corr, ietat) < 0) 609 goto erreur2; 610 assert(pos % 4 == 0); 611 corr[ietat] = pos >> 2; 612 613 /* Écrire l’entête de l’état. */ 614 if (tampex_minim((void **)&t, pos + 3) < 0) 615 goto erreur2; 616 /* Nombre d’éléments. */ 617 t[pos] = tfm->etats[ietat].ntrans; 618 pos += 1; 619 /* Si l’état est final. */ 620 if (tfm_tfinal(tfm, ietat)) 621 t[pos] |= 0x01; 622 pos += 3; 623 624 /* Réserver de l’espace pour les transitions. */ 625 tampex_minim((void **)&t, pos - 1 + tfm->etats[ietat].ntrans * 4); 626 /* Parcourir les transitions. */ 627 for (itrans = tfm->etats[ietat].trans; itrans != -1; 628 itrans = tfm->trans[itrans].prch) { 629 t[pos++] = tfm->trans[itrans].se; 630 t[pos++] = tfm->trans[itrans].ss; 631 pos += 2; 632 } 633 } 634 635 /* Écrire les références vers les états. Commencer après l’état 636 * initial. */ 637 for (pos = 8, ietat = 0; tampex_dedans(t, pos); ietat++) { 638 pos += 4; /* Sauter l’entête. */ 639 for (itrans = tfm->etats[ietat].trans; itrans != -1; 640 itrans = tfm->trans[itrans].prch) { 641 pos += 2; 642 ecrire_32(t + pos, corr[tfm->trans[itrans].ed]); 643 pos += 2; 644 } 645 } 646 647 tampex_libr(corr); 648 return t; 649 650 erreur2: 651 tampex_libr(corr); 652 erreur1: 653 tampex_libr(t); 654 return NULL; 655 }