fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. #define D_LEFT		-1
  6. #define D_RIGHT		1
  7.  
  8. #define MAX_STATE	(100*1000)
  9.  
  10. typedef struct tree_t{
  11. 	int state;
  12. 	int zero;
  13. 	int one;
  14. } tree;
  15.  
  16. typedef struct rule_t{
  17. 	int state1;
  18. 	unsigned char read;
  19.  
  20. 	int state2;
  21. 	unsigned char write;
  22. 	int direction;
  23. } rule;
  24.  
  25. rule rules[1024];
  26. int nrules;
  27.  
  28. rule converted[1024*128];
  29. int nconverted;
  30.  
  31. int used_state[1024*128];
  32. int nuseds;
  33.  
  34. int fused_symbol[256];
  35.  
  36. int bits = 1;
  37.  
  38. tree trees[1024*128];
  39. int ntrees;
  40.  
  41. unsigned char symbit[256][8];
  42.  
  43. int isused( int state )
  44. {
  45. 	int i;
  46.  
  47. 	for( i = 0 ; i < nuseds ; i++ ) {
  48. 		if( used_state[i] == state ) {
  49. 			return 1;
  50. 		}
  51. 	}
  52.  
  53. 	return 0;
  54. }
  55.  
  56. int find_unused( void )
  57. {
  58. 	int i;
  59.  
  60. 	for( i = 1 ; i < MAX_STATE ; i++ ) {
  61. 		if( isused(i) == 0 ) {
  62. 			return i;
  63. 		}
  64. 	}
  65.  
  66. 	return -1;
  67. }
  68.  
  69. void init( void )
  70. {
  71. 	int i;
  72. 	int cnt;
  73. 	int n;
  74. 	int k;
  75.  
  76. 	nconverted = 0;
  77. 	nuseds = 0;
  78. 	ntrees = 0;
  79.  
  80. 	for( i = 0 ; i < nrules ; i++ ) {
  81. 		if( rules[i].state1 != -1 && isused( rules[i].state1 ) == 0 ) {
  82. 			used_state[nuseds++] = rules[i].state1;
  83. 		}
  84. 		if( rules[i].state2 != -1 && isused( rules[i].state2 ) == 0 ) {
  85. 			used_state[nuseds++] = rules[i].state2;
  86. 		}
  87. 	}
  88.  
  89. 	for( i = 0 ; i < 256 ; i++ ) {
  90. 		fused_symbol[i] = 0;
  91. 	}
  92.  
  93. 	for( i = 0 ; i < nrules ; i++ ) {
  94. 		fused_symbol[rules[i].read] = 1;
  95. 		fused_symbol[rules[i].write] = 1;
  96. 	}
  97.  
  98. 	cnt = 0;
  99. 	for( i = 0 ; i < 256 ; i++ ) {
  100. 		if( fused_symbol[i] ) cnt++;
  101. 	}
  102.  
  103. 	n = 1;
  104. 	for( i = 2 ; i <= 256 ; i *= 2 ) {
  105. 		if( cnt <= i ) break;
  106. 		n++;
  107. 	}
  108. 	bits = n;
  109.  
  110. 	n = 0;
  111. 	k = 1;
  112. 	for( i = 0 ; i < bits-1 ; i++ ) {
  113. 		k *= 2;
  114. 	}
  115. 	for( i = 0 ; i < 256 ; i++ ) {
  116. 		if( fused_symbol[i] ) {
  117. 			int j = 0;
  118. 			int m = k;
  119.  
  120. 			for( j = 0 ; j < bits ; j++ ) {
  121. 				if( n & m ) symbit[i][j] = 1;
  122. 				else symbit[i][j] = 0;
  123.  
  124. 				m /= 2;
  125. 			}
  126.  
  127. 			n++;
  128. 		}
  129. 	}
  130. }
  131.  
  132. int find_tree( int state )
  133. {
  134. 	int i;
  135.  
  136. 	for( i = 0 ; i < ntrees ; i++ ) {
  137. 		if( trees[i].state == state ) {
  138. 			return i;
  139. 		}
  140. 	}
  141.  
  142. 	return -1;
  143. }
  144.  
  145. /* change and move right */
  146. void case2( int i , int n )
  147. {
  148. 	int j;
  149. 	int n2;
  150. 	int s;
  151. 	int b,b2;
  152.  
  153. 	converted[n].direction = D_LEFT;
  154.  
  155. 	b = symbit[rules[i].write][bits-1];
  156. 	converted[n].write = b ? '1' : '0';
  157.  
  158. 	s = find_unused();
  159. 	used_state[nuseds++] = s;
  160. 	converted[n].state2 = s;
  161.  
  162. 	for( j = 0 ; j < bits-1 ; j++ ) {
  163. 		b = symbit[rules[i].write][bits-j-2];
  164. 		b2 = symbit[rules[i].read][bits-j-2];
  165. 		n2 = nconverted++;
  166. 		converted[n2].direction = ( j == bits-2 ) ? D_RIGHT : D_LEFT;
  167. 		converted[n2].state1 = s;
  168. 		converted[n2].read = b2 ? '1' : '0';
  169. 		converted[n2].write = b ? '1' : '0';
  170.  
  171. 		s = find_unused();
  172. 		used_state[nuseds++] = s;
  173. 		converted[n2].state2 = s;
  174. 	}
  175.  
  176. 	for( j = 0 ; j < bits-1 ; j++ ) {
  177. 		b = symbit[rules[i].write][j+1];
  178. 		n2 = nconverted++;
  179. 		converted[n2].direction = D_RIGHT;
  180. 		converted[n2].state1 = s;
  181. 		converted[n2].read = b ? '1' : '0';
  182. 		converted[n2].write = b ? '1' : '0';
  183.  
  184. 		if( j != bits-2 ) {
  185. 			s = find_unused();
  186. 			used_state[nuseds++] = s;
  187. 			converted[n2].state2 = s;
  188. 		} else {
  189. 			converted[n2].state2 = rules[i].state2;
  190. 		}
  191. 	}
  192. }
  193.  
  194. /* not change and move left */
  195. void case3( int i , int n )
  196. {
  197. 	int j;
  198. 	int n2,n3;
  199. 	int s;
  200. 	int b;
  201.  
  202. 	converted[n].direction = D_LEFT;
  203.  
  204. 	s = find_unused();
  205. 	used_state[nuseds++] = s;
  206. 	converted[n].state2 = s;
  207.  
  208. 	for( j = 0 ; j < bits-1 ; j++ ) {
  209. 		b = symbit[rules[i].read][bits-j-2];
  210. 		n2 = nconverted++;
  211. 		converted[n2].direction = D_LEFT;
  212. 		converted[n2].state1 = s;
  213. 		converted[n2].read = b ? '1' : '0';
  214. 		converted[n2].write = b ? '1' : '0';
  215.  
  216. 		s = find_unused();
  217. 		used_state[nuseds++] = s;
  218. 		converted[n2].state2 = s;
  219. 	}
  220.  
  221. 	for( j = 0 ; j < bits-1 ; j++ ) {
  222. 		n2 = nconverted++;
  223. 		n3 = nconverted++;
  224. 		converted[n2].direction = D_LEFT;
  225. 		converted[n2].state1 = s;
  226. 		converted[n2].read = '0';
  227. 		converted[n2].write = '0';
  228. 		converted[n3].direction = D_LEFT;
  229. 		converted[n3].state1 = s;
  230. 		converted[n3].read = '1';
  231. 		converted[n3].write = '1';
  232.  
  233. 		if( j != bits-2 ) {
  234. 			s = find_unused();
  235. 			used_state[nuseds++] = s;
  236. 			converted[n2].state2 = s;
  237. 			converted[n3].state2 = s;
  238. 		} else {
  239. 			converted[n2].state2 = rules[i].state2;
  240. 			converted[n3].state2 = rules[i].state2;
  241. 		}
  242. 	}
  243. }
  244.  
  245. /* change and move left */
  246. void case4( int i , int n )
  247. {
  248. 	int j;
  249. 	int n2,n3;
  250. 	int s;
  251. 	int b,b2;
  252.  
  253. 	converted[n].direction = D_LEFT;
  254.  
  255. 	b = symbit[rules[i].write][bits-1];
  256. 	converted[n].write = b ? '1' : '0';
  257.  
  258. 	s = find_unused();
  259. 	used_state[nuseds++] = s;
  260. 	converted[n].state2 = s;
  261.  
  262. 	for( j = 0 ; j < bits-1 ; j++ ) {
  263. 		b = symbit[rules[i].write][bits-j-2];
  264. 		b2 = symbit[rules[i].read][bits-j-2];
  265. 		n2 = nconverted++;
  266. 		converted[n2].direction = D_LEFT;
  267. 		converted[n2].state1 = s;
  268. 		converted[n2].read = b2 ? '1' : '0';
  269. 		converted[n2].write = b ? '1' : '0';
  270.  
  271. 		s = find_unused();
  272. 		used_state[nuseds++] = s;
  273. 		converted[n2].state2 = s;
  274. 	}
  275.  
  276. 	for( j = 0 ; j < bits-1 ; j++ ) {
  277. 		n2 = nconverted++;
  278. 		n3 = nconverted++;
  279. 		converted[n2].direction = D_LEFT;
  280. 		converted[n2].state1 = s;
  281. 		converted[n2].read = '0';
  282. 		converted[n2].write = '0';
  283. 		converted[n3].direction = D_LEFT;
  284. 		converted[n3].state1 = s;
  285. 		converted[n3].read = '1';
  286. 		converted[n3].write = '1';
  287.  
  288. 		if( j != bits-2 ) {
  289. 			s = find_unused();
  290. 			used_state[nuseds++] = s;
  291. 			converted[n2].state2 = s;
  292. 			converted[n3].state2 = s;
  293. 		} else {
  294. 			converted[n2].state2 = rules[i].state2;
  295. 			converted[n3].state2 = rules[i].state2;
  296. 		}
  297. 	}
  298. }
  299.  
  300. void convert( void )
  301. {
  302. 	int i,j;
  303. 	int n;
  304. 	int b;
  305. 	int t,t2;
  306. 	int s;
  307.  
  308. 	for( i = 0 ; i < nrules ; i++ ) {
  309. 		s = rules[i].state1;
  310. 		n = -1;
  311. 		for( j = 0 ; j < bits ; j++ ) {
  312. 			t = find_tree( s );
  313. 			b = symbit[rules[i].read][j];
  314. 			if( t == -1 ||
  315. 			    ( trees[t].one == -1 && b ) ||
  316. 			    ( trees[t].zero == -1 && b == 0 ) ) {
  317. 				n = nconverted++;
  318.  
  319. 				converted[n].state1 = s;
  320. 				converted[n].direction = D_RIGHT;
  321.  
  322. 				if( b == 0 ) {
  323. 					converted[n].read = '0';
  324. 					converted[n].write = '0';
  325. 				} else {
  326. 					converted[n].read = '1';
  327. 					converted[n].write = '1';
  328. 				}
  329.  
  330. 				if( t == -1 ) {
  331. 					t = ntrees++;
  332. 					trees[t].state = s;
  333. 					trees[t].zero = -1;
  334. 					trees[t].one = -1;
  335. 				}
  336.  
  337. 				if( j != bits-1 ) {
  338. 					t2 = ntrees++;
  339.  
  340. 					s = find_unused();
  341. 					used_state[nuseds++] = s;
  342. 					trees[t2].state = s;
  343.  
  344. 					if( b ) {
  345. 						trees[t].one = t2;
  346. 					} else {
  347. 						trees[t].zero = t2;
  348. 					}
  349. 					trees[t2].zero = -1;
  350. 					trees[t2].one = -1;
  351.  
  352. 					converted[n].state2 = s;
  353. 				}
  354. 			} else {
  355. 				if( b && trees[t].one != -1 ) {
  356. 					int t3 = trees[t].one;
  357. 					s = trees[t3].state;
  358. 				}
  359. 				if( b == 0 && trees[t].zero != -1 ) {
  360. 					int t3 = trees[t].zero;
  361. 					s = trees[t3].state;
  362. 				}
  363. 			}
  364. 		}
  365. 		/* not change and move right */
  366. 		if( rules[i].direction == D_RIGHT &&
  367. 		    ( rules[i].read == rules[i].write ) ) {
  368. 			if( n != -1 ) {
  369. 				converted[n].state2 = rules[i].state2;
  370. 			}
  371. 		}
  372. 		/* change and move right */
  373. 		if( rules[i].direction == D_RIGHT &&
  374. 		    ( rules[i].read != rules[i].write ) ) {
  375. 			if( n != -1 ) {
  376. 				case2( i , n );
  377. 			}
  378. 		}
  379. 		/* not change and move left */
  380. 		if( rules[i].direction == D_LEFT &&
  381. 		    ( rules[i].read == rules[i].write ) ) {
  382. 			if( n != -1 ) {
  383. 				case3( i , n );
  384. 			}
  385. 		}
  386. 		/* change and move left */
  387. 		if( rules[i].direction == D_LEFT &&
  388. 		    ( rules[i].read != rules[i].write ) ) {
  389. 			if( n != -1 ) {
  390. 				case4( i , n );
  391. 			}
  392. 		}
  393. 	}
  394. }
  395.  
  396. void ReadRule( char *filename )
  397. {
  398. 	FILE *fp;
  399. 	char buf[1024];
  400.  
  401. 	fp = fopen_s( &fp , filename , "r" );
  402.  
  403. 	if( fp == NULL ) {
  404. 		return;
  405. 	}
  406.  
  407. 	nrules = 0;
  408.  
  409. 	for(;;) {
  410. 		char *p = fgets( buf , sizeof(buf) , fp );
  411. 		char *pa[5];
  412. 		int i,l,i2,f;
  413.  
  414. 		if( p == NULL ) break;
  415.  
  416. 		l = strlen( buf );
  417. 		if( buf[l-1] == '\n' ) {
  418. 			buf[l-1] = '\0';
  419. 			l -= 1;
  420. 		}
  421.  
  422. 		i2 = 0;
  423. 		f = 0;
  424. 		for( i = 0 ; i < l ; i++ ) {
  425. 			if( !( buf[i] == ' ' || buf[i] == ',' ) && f == 0 ) {
  426. 				if( i2 == 5 ) {
  427. 					i2 = -1;
  428. 					break;
  429. 				}
  430. 				pa[i2++] = &buf[i];
  431. 				f = 1;
  432. 				continue;
  433. 			}
  434. 			if( buf[i] == ' ' || buf[i] == ',' ) {
  435. 				buf[i] = '\0';
  436. 				f = 0;
  437. 			}
  438. 		}
  439.  
  440. 		if( i2 != 5 ) break;
  441.  
  442. 		rules[nrules].state1 = atoi( pa[0] );
  443.  
  444. 		if( strlen( pa[1] ) != 1 ) {
  445. 			break;
  446. 		}
  447.  
  448. 		if( pa[1][0] == '_' ) pa[1][0] = ' ';
  449. 		rules[nrules].read = pa[1][0];
  450.  
  451. 		if( strcmp( pa[2] , "H" ) == 0 ) {
  452. 			rules[nrules].state2 = -1;
  453. 		} else {
  454. 			rules[nrules].state2 = atoi( pa[2] );
  455. 		}
  456.  
  457. 		if( strlen( pa[3] ) != 1 ) {
  458. 			break;
  459. 		}
  460.  
  461. 		if( pa[3][0] == '_' ) pa[3][0] = ' ';
  462. 		rules[nrules].write = pa[3][0];
  463.  
  464. 		if( strlen( pa[4] ) != 1 ) {
  465. 			break;
  466. 		}
  467.  
  468. 		if( pa[4][0] == '<' ) {
  469. 			rules[nrules].direction = D_LEFT;
  470. 		} else if( pa[4][0] == '>' ) {
  471. 			rules[nrules].direction = D_RIGHT;
  472. 		} else {
  473. 			break;
  474. 		}
  475.  
  476. 		nrules++;
  477. 	}
  478.  
  479. 	fclose( fp );
  480. }
  481.  
  482. void print( void )
  483. {
  484. 	int i,j;
  485.  
  486. 	for( i = 0 ; i < nconverted ; i++ ) {
  487. 		printf( "%d,%c " ,
  488. 			converted[i].state1 ,
  489. 			converted[i].read );
  490. 		if( converted[i].state2 == -1 ) {
  491. 			printf( "H" );
  492. 		} else {
  493. 			printf( "%d" , converted[i].state2 );
  494. 		}
  495. 		printf( ",%c,%c\n" ,
  496. 			converted[i].write ,
  497. 			( converted[i].direction == D_RIGHT ) ? '>' : '<' );
  498. 	}
  499.  
  500. 	printf( "\n" );
  501.  
  502. 	for( i = 0 ; i < 256 ; i++ ) {
  503. 		if( fused_symbol[i] ) {
  504. 			printf( "%c : " , (unsigned char)i == ' ' ? '_' : (unsigned char) i );
  505. 			for( j = 0 ; j < bits ; j++ ) {
  506. 				printf( "%d" , symbit[i][j] );
  507. 			}
  508. 			printf( "\n" );
  509. 		}
  510. 	}
  511. }
  512.  
  513. int main( int argc , char *argv[] )
  514. {
  515. 	if( argc != 2 ) {
  516. 		printf( "argc != 2\n" );
  517. 		return 0;
  518. 	}
  519.  
  520. 	ReadRule( argv[1] );
  521. 	init();
  522. 	if( bits == 1 ) {
  523. 		printf( "no more work for this rule list\n" );
  524. 		return 0;
  525. 	}
  526. 	convert();
  527. 	print();
  528.  
  529. 	return 0;
  530. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c: In function ‘ReadRule’:
prog.c:401:7: warning: implicit declaration of function ‘fopen_s’; did you mean ‘fopen’? [-Wimplicit-function-declaration]
  fp = fopen_s( &fp , filename , "r" );
       ^~~~~~~
       fopen
prog.c:401:5: warning: assignment to ‘FILE *’ {aka ‘struct _IO_FILE *’} from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
  fp = fopen_s( &fp , filename , "r" );
     ^
/usr/bin/ld: /home/Td9lbs/cckdIbqH.o: in function `ReadRule':
prog.c:(.text+0x11a4): undefined reference to `fopen_s'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/JY7nPI
language:
C (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!