itfd.c (7529B)
1 #include <assert.h> 2 #include <stdbool.h> 3 #include <stddef.h> 4 #include <stdint.h> 5 #include <stdlib.h> 6 #include <sys/mman.h> 7 #include <sys/stat.h> 8 #include <sys/types.h> 9 10 #include "itfd.h" 11 #include "tampex.h" 12 #include "tfd.h" 13 14 /* Lire du tampon tp au décalage dec 16 ou 32 bits. */ 15 #define LIRE_16(tp, dec) (*(uint16_t *)((tp) + (dec))) 16 #define LIRE_32(tp, dec) (*(uint32_t *)((tp) + (dec))) 17 18 struct option { 19 size_t icse; /* Indice dans la liste de symboles d’entrée. */ 20 size_t icss; /* Indice dans la liste de symboles de sortie. */ 21 uint32_t pos; /* Position dans le transducteur. */ 22 }; 23 24 /* Empiler l’option initialisatrice d’interp. 25 * Renvoie 0, ou -1 en cas d’erreur. */ 26 static int interp_init_empl(struct interp *interp); 27 28 /* Empiler l’option formée apr icse, icss et pos dans interp. 29 * Renvoie 0, ou -1 en cas d’erreur. */ 30 static int empiler(struct interp *interp, size_t icse, size_t icss, 31 uint32_t pos); 32 33 struct itfd * 34 itfd_ouvrir(int df) 35 { 36 struct itfd *itfd; 37 struct stat stat; 38 uint32_t n; 39 40 assert(df > 0); 41 42 if ((itfd = malloc(sizeof(struct itfd))) == NULL) 43 return NULL; 44 45 if (fstat(df, &stat) < 0) 46 goto erreur1; 47 48 if ((itfd->f = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, df, 0)) 49 == MAP_FAILED) 50 goto erreur1; 51 52 itfd->df = df; 53 itfd->lngr = stat.st_size; 54 55 /* Vérifier le nombre magique. */ 56 n = itfd->f[0x00]; 57 n <<= 8; 58 n |= itfd->f[0x01]; 59 60 if (n != TFD_MAGIQUE) 61 goto erreur2; 62 63 /* Vérifier la version. */ 64 n = itfd->f[0x02]; 65 n <<= 8; 66 n |= itfd->f[0x03]; 67 if (n != 0) 68 goto erreur2; 69 itfd->version = n; 70 71 /* Vérifier le boutisme. */ 72 if ((n = LIRE_16(itfd->f, 0x04)) != TFD_TEMOIN) 73 goto erreur2; 74 75 /* Lire les informations sur les segments. */ 76 itfd->symbs = itfd->f + LIRE_32(itfd->f, 0x06); 77 itfd->symbs_lngr = LIRE_32(itfd->f, 0x0A); 78 79 itfd->se = itfd->f + LIRE_32(itfd->f, 0x0E); 80 itfd->se_lngr = LIRE_32(itfd->f, 0x12); 81 82 itfd->ss = itfd->f + LIRE_32(itfd->f, 0x16); 83 itfd->ss_lngr = LIRE_32(itfd->f, 0x1A); 84 85 itfd->segm = itfd->f + LIRE_32(itfd->f, 0x1E); 86 itfd->segm_lngr = LIRE_32(itfd->f, 0x22); 87 88 itfd->trans = itfd->f + LIRE_32(itfd->f, 0x26); 89 itfd->trans_lngr = LIRE_32(itfd->f, 0x2A); 90 91 return itfd; 92 93 erreur2: 94 itfd_fermer(itfd); 95 return NULL; 96 erreur1: 97 free(itfd); 98 return NULL; 99 } 100 101 int 102 itfd_fermer(struct itfd *itfd) 103 { 104 assert(itfd); 105 assert(itfd->f); 106 107 if (munmap(itfd->f, itfd->lngr) < 0) 108 return -1; 109 110 free(itfd); 111 112 return 0; 113 } 114 115 size_t 116 segmenter(struct itfd *itfd, uint8_t *cc, size_t lngrcc, uint16_t *symbs) 117 { 118 size_t i, pi; /* Indice et prochain indice dans le segmenteur. */ 119 uint16_t base, orig; 120 uint16_t (*segm)[2]; 121 uint8_t *prch; /* Fin du dernier symbole trouvé. */ 122 uint8_t *fin; /* Fin de cc. */ 123 int symb; /* Identifiant du dernier symbole trouvé. */ 124 size_t nsymbs; /* Nombre de symboles. */ 125 126 assert(itfd); 127 assert(cc); 128 129 fin = cc + lngrcc; 130 segm = (uint16_t (*)[2])itfd->segm; 131 nsymbs = 0; 132 133 while (cc < fin) { 134 symb = (*cc << 1) | 0x00; 135 prch = cc + 1; 136 137 for (i = 0; cc < fin; cc++) { 138 pi = (segm[i][0] >> 1) + *cc; 139 140 base = segm[pi][0]; 141 orig = segm[pi][1]; 142 143 /* Vérifier. */ 144 if (orig & 0x01 || orig >> 0x01 != i) { 145 cc = prch; 146 break; 147 } 148 149 i = pi; 150 151 /* Si état final. */ 152 if (base & 0x01) { 153 i = base >> 1; 154 orig = segm[i][1]; 155 symb = ((orig >> 1) << 1) | 0x01; 156 prch = cc + 1; 157 } 158 } 159 160 cc = prch; 161 *symbs++ = symb; 162 nsymbs++; 163 } 164 165 assert(nsymbs <= lngrcc); 166 return nsymbs; 167 } 168 169 struct interp * 170 interp_init(struct itfd *itfd) 171 { 172 struct interp *interp; 173 174 assert(itfd); 175 176 if ((interp = malloc(sizeof(struct interp))) == NULL) 177 return NULL; 178 if ((interp->opt = tampex_init(64, sizeof(struct option))) == NULL) 179 goto erreur1; 180 if ((interp->css = tampex_init(64, sizeof(uint16_t))) == NULL) 181 goto erreur2; 182 interp->itfd = itfd; 183 184 if (interp_init_empl(interp) < 0) 185 goto erreur3; 186 187 return interp; 188 189 erreur3: 190 tampex_libr(interp->css); 191 erreur2: 192 tampex_libr(interp->opt); 193 erreur1: 194 free(interp); 195 return NULL; 196 } 197 198 void 199 interp_libr(struct interp *interp) 200 { 201 assert(interp); 202 assert(interp->opt); 203 assert(interp->css); 204 205 tampex_libr(interp->opt); 206 tampex_libr(interp->css); 207 free(interp); 208 } 209 210 int 211 interp_reinit(struct interp *interp, struct itfd *itfd) 212 { 213 assert(interp); 214 assert(interp->opt); 215 assert(interp->css); 216 assert(itfd); 217 218 tampex_reinit(interp->opt); 219 tampex_reinit(interp->css); 220 interp->itfd = itfd; 221 222 if (interp_init_empl(interp) < 0) 223 return -1; 224 225 return 0; 226 } 227 228 static int 229 interp_init_empl(struct interp *interp) 230 { 231 assert(interp); 232 233 return empiler(interp, 0, 0, 4); 234 } 235 236 ssize_t 237 interpreter(struct interp *interp, uint16_t *cse, size_t nsymbs) 238 { 239 uint16_t *tf; /* Adresse du début du transducteur. */ 240 uint16_t ntrans; /* Nombre de transitions. */ 241 uint16_t se, ss; /* Symboles d’entrée et de sortie. */ 242 size_t pos; /* Position dans le transducteur. */ 243 size_t ipile; /* Indice dans la pile. */ 244 size_t icse, icss; /* Indices dans les chaînes d’entrée et de 245 sortie. */ 246 bool trouve; /* Si une transition exacte a été trouvée. */ 247 bool final; /* Si un état est final. */ 248 249 assert(interp); 250 assert(cse); 251 252 tf = (uint16_t *)interp->itfd->trans; 253 254 while (tampex_nelem(interp->opt)) { 255 /* Dépiler une transition. */ 256 ipile = tampex_dpl(interp->opt); 257 icse = interp->opt[ipile].icse; 258 icss = interp->opt[ipile].icss; 259 pos = interp->opt[ipile].pos; 260 261 /* Ajouter le symbole à la chaîne de sortie. */ 262 ss = tf[pos + 1]; 263 if (tampex_minim((void **)&interp->css, icss + 1) < 0) 264 return -1; 265 switch (ss) { 266 case TFD_SYMB_EPSILON: break; /* Ignorer. */ 267 case TFD_SYMB_IDENTITE: 268 se = tf[pos + 0]; 269 if (se == TFD_SYMB_EPSILON) break; 270 assert(icse > 0); 271 interp->css[icss++] = cse[icse - 1]; 272 break; 273 case TFD_SYMB_AUTRE: 274 ss = ITFD_SYMB_AUTRE; 275 /* ON TOMBE! */ 276 default: /* Ajouter le symbole à la sortie. */ 277 if ((ss & 0x01) != TFD_SNORMAL) 278 break; 279 interp->css[icss++] = ss; 280 } 281 282 /* Sauter au prochain état. */ 283 pos = LIRE_32(tf, pos + 2) << 2; 284 ntrans = tf[pos + 0]; 285 /* Si l’état est final et qu’on est à la fin de cse. */ 286 final = (icse == nsymbs) && (tf[pos + 1] & 0x1); 287 pos += 4; 288 trouve = 0; 289 /* Parcourir les transitions. */ 290 for (; ntrans--; pos += 4) { 291 if ((icse >= nsymbs) && (tf[pos + 0] != TFM_SYMB_EPSILON)) 292 continue; 293 switch (tf[pos + 0]) { 294 case TFM_SYMB_AUTRE: 295 if (!trouve) { 296 if (empiler(interp, icse + 1, icss, pos) < 0) 297 return -1; 298 } 299 break; 300 case TFM_SYMB_EPSILON: 301 if (empiler(interp, icse, icss, pos) < 0) 302 return -1; 303 break; 304 case TFM_SYMB_IDENTITE: 305 if (empiler(interp, icse + 1, icss, pos) < 0) 306 return -1; 307 break; 308 default: 309 se = cse[icse]; 310 if ((tf[pos + 0] >> 1) != (se >> 1)) 311 break; 312 if ((tf[pos + 0] & 0x01) != TFD_SNORMAL) 313 break; 314 if ((se & 0x01) != ITFD_SYMB_REC) 315 break; 316 if (empiler(interp, icse + 1, icss, pos) < 0) 317 return -1; 318 trouve = 1; 319 } 320 } 321 if (final) 322 return icss + 1; 323 } 324 325 return 0; 326 } 327 328 static int 329 empiler(struct interp *interp, size_t icse, size_t icss, uint32_t pos) 330 { 331 ssize_t ipile; 332 333 if ((ipile = tampex_empl((void **)&interp->opt)) < 0) 334 return -1; 335 interp->opt[ipile].icse = icse; 336 interp->opt[ipile].icss = icss; 337 interp->opt[ipile].pos = pos; 338 339 return 0; 340 }