rendered paste body#include <stdio.h>#include <stdlib.h>#include <string.h>#ifdef __MINGW32__#include <fcntl.h>#endif#define DNA_WORK_AREA_SIZE 0x10000000#define RNA_SIZE 0x08000000#define CHAIN_SIZE 0x00100000#define PATTERN_SIZE 0x00100000#define TEMPLATE_SIZE 0x00100000#define ENV_SIZE 0x00100000#define PROTECT_SIZE 0x00100000#define FILENAME "endo_mod4.dna"#define NUM_ITER 100000000#define MAGICNUMBER 100021132//#define __DEBUG__//#define __VERBOSE__unsigned int error = 0;unsigned char* dna_work_area;unsigned int dna_from_base = 0; unsigned char* rna;unsigned int rna_index;unsigned char rna_buffer[10];unsigned int* chain_a;unsigned int* chain_b;unsigned int nextfree;unsigned int* pat;unsigned int* templ;unsigned int* env;unsigned char* prot;unsigned int natcount;unsigned int constscount;unsigned int protectcount;unsigned int realprotectcount;unsigned int asnatcount;unsigned int replacecount;unsigned int searchcount;unsigned int searchsum;unsigned int num_rna;void print_pattern(unsigned int pattern_length){ unsigned int i; printf("P: "); for (i = 0; i < pattern_length; i++) { switch (pat[i]) { case 'C' : case 'F' : case 'I' : case 'P' : case '(' : case ')' : printf("%c", pat[i]); break; case '!' : printf("!%08x", pat[++i]); break; case '?' : printf("?%s", (unsigned char*) &pat[++i]); i += ((strlen((unsigned char*) &pat[i]) + 3) >> 2) - 1; break; } } printf("\n");}void print_template(unsigned int template_length){ unsigned int i; printf("T: "); for (i = 0; i < template_length; i++) { switch (templ[i]) { case 'C' : case 'F' : case 'I' : case 'P' : printf("%c", templ[i]); break; case 'l' : printf("l%08x", templ[++i]); break; case 'n' : printf("n%08x,%08x", templ[i + 1], templ[i + 2]); i += 2; break; } } printf("\n");} unsigned char chain_get_char(unsigned int printflag){ unsigned char b; if (chain_a[1] >= chain_a[0]) { printf("Chain length exceeded\n"); b = 0; error = 1; } else { b = dna_work_area[chain_a[chain_a[2]] + chain_a[3]]; chain_a[1]++; chain_a[3]++; if (chain_a[3] >= chain_a[chain_a[2] + 1]) { chain_a[3] = 0; chain_a[2] += 2; } #ifdef __DEBUG__ if (printflag) printf("%c", b);#endif } return b;}void chain_put_char(unsigned char c){ dna_work_area[chain_b[chain_b[2]] + chain_b[3]++] = c; chain_b[chain_b[2] + 1]++; chain_b[0]++; chain_b[1]++; nextfree++;}unsigned int chain_move_forward(unsigned int dist){ if (chain_a[1] + dist >= chain_a[0]) { // printf("Trying to move forward more than in buffer!\n"); return 0; } else { //printf("Chain moving %d %d %d\n", dist, chain_a[3], chain_a[chain_a[2] + 1]); chain_a[1] += dist; while (chain_a[3] + dist >= chain_a[chain_a[2] + 1]) { //printf("Chain moving %d %d %d\n", dist, chain_a[3], chain_a[chain_a[2] + 1]); dist -= (chain_a[chain_a[2] + 1] - chain_a[3]); chain_a[2] += 2; chain_a[3] = 0; } chain_a[3] += dist; //printf("Chain moving %d %d %d\n", dist, chain_a[3], chain_a[chain_a[2] + 1]); return 1; }}unsigned int chain_move_back(void){ if (chain_a[1] == 0) { printf("Trying to move back more than in buffer!\n"); exit(1); } else { //printf("Chain moving %d %d\n", chain_a[3], chain_a[chain_a[2] + 1]); chain_a[1]--; if (chain_a[3] == 0) { chain_a[2] -= 2; chain_a[3] = chain_a[chain_a[2] + 1] - 1; //printf("Chain moving %d %d\n", chain_a[3], chain_a[chain_a[2] + 1]); } else { chain_a[3]--; } //printf("Chain moving %d %d\n", chain_a[3], chain_a[chain_a[2] + 1]); } return 1;} /* // Setting up initial chain chain_a[0] = size; // total chain length chain_a[1] = 0; // total chain offset chain_a[2] = 4; // current chain link - chain array offset chain_a[3] = 0; // current chain link - offset inside link // the chain starts here chain_a[4] = 0; // offset to chain link chain_a[5] = size; // length of chain link chain_a[6] = 0; chain_a[7] = 0; // size = 0, end of chain marker*/unsigned int chain_search(unsigned char* ptr){ unsigned int chain_state_index, chain_state_link, chain_state_offset, i; unsigned char b, b2; if (*ptr != 0) { // printf("%s\n", ptr); while (b = chain_get_char(0)) { // printf("Read char %c\n", b); if (*ptr == b) { //printf("Characters match %c %c\n", *ptr, b); i = 1; chain_state_index = chain_a[1]; chain_state_link = chain_a[2]; chain_state_offset = chain_a[3]; while(1) { b = chain_get_char(0); b2 = *(ptr + i); if (!b2) { //printf("Match, check chars %d %d\n", b, b2); chain_move_back(); return 1; } if (b == b2) { //printf("More characters match %c %c %d\n", b, b2, chain_a[2]); i++; } else { //printf("Character mismatch!! %c %c\n", b, b2); break; } } chain_a[1] = chain_state_index; chain_a[2] = chain_state_link; chain_a[3] = chain_state_offset; } } return 0; } else return 1;}unsigned int nat(void){ unsigned int n = 0; unsigned int power = 1; natcount++; while (1) { switch(chain_get_char(1)) { case 'P' : return n; case 'I' : case 'F' : break; case 'C' : n += power; break; default : printf("nat(): Invalid char\n"); exit(1); } power <<= 1; }}unsigned int consts(unsigned char* str_ptr){ unsigned int i = 0; constscount++; while (1) { switch(chain_get_char(1)) { case 'C' : *(str_ptr + i++) = 'I'; break; case 'F' : *(str_ptr + i++) = 'C'; break; case 'P' : *(str_ptr + i++) = 'F'; break; case 'I' : switch(chain_get_char(1)) { case 'C' : *(str_ptr + i++) = 'P'; break; case 'F' : case 'P' : case 'I' : chain_move_back(); chain_move_back(); *(str_ptr + i++) = 0; i = (i + 3) >> 2; return i; default : printf("consts(): Invalid char\n"); error = 1; return; } break; default : printf("consts(): Invalid char\n"); error = 1; return; } }}void protect(unsigned int l, unsigned int n){ unsigned int dest_start; unsigned int dest_length; unsigned char* source_start; unsigned char* source_end; unsigned int size, temp, i, flag; unsigned char c; unsigned int chain_state_offset, chain_state_link, chain_state_index; unsigned int protect_length; unsigned int source_offset, destination_offset; if (l == 0) { protectcount++; //printf("%d %d %d %d %d %d %d\n", env[n], env[n + 1], env[n + 2], env[n + 3], env[n + 4], env[n + 5], env[n + 5] - env[n + 2]); //for (i = 0; i < 20; i++) // printf("%d ", chain_b[i]); //printf("\n"); if (chain_b[chain_b[2] + 1] != 0) { chain_b[2] += 2; chain_b[3] = 0; } if (env[n] == env[n + 3]) { //for (i = 0; i < 20; i++) // printf("%d ", chain_b[i]); //printf("\n"); size = env[n + 4] - env[n + 1]; if (size) { chain_b[chain_b[2]] = chain_a[env[n]] + env[n + 1]; chain_b[chain_b[2] + 1] = size; chain_b[0] += size; chain_b[1] += size; chain_b[2] += 2; } //for (i = 0; i < 20; i++) // printf("%d ", chain_b[i]); //printf("\n"); } else { size = chain_a[env[n] + 1] - env[n + 1]; chain_b[chain_b[2]] = chain_a[env[n]] + env[n + 1]; chain_b[chain_b[2] + 1] = size; chain_b[0] += size; chain_b[1] += size; chain_b[2] += 2; temp = env[n] + 2; while (temp < env[n + 3]) { chain_b[chain_b[2]] = chain_a[temp]; chain_b[chain_b[2] + 1] = chain_a[temp + 1]; chain_b[0] += chain_a[temp + 1]; chain_b[1] += chain_a[temp + 1]; chain_b[2] += 2; temp += 2; } if (env[n + 4]) { chain_b[chain_b[2]] = chain_a[temp]; chain_b[chain_b[2] + 1] = env[n + 4]; chain_b[0] += env[n + 4]; chain_b[1] += env[n + 4]; chain_b[2] += 2; } } } else { //printf("Realprotect\n"); realprotectcount++;#ifdef __DEBUG__ printf("protect(): l %d n %d\n", l, n); printf("%d %d %d %d %d %d %d\n", env[n], env[n + 1], env[n + 2], env[n + 3], env[n + 4], env[n + 5], env[n + 5] - env[n + 2]);#endif if (chain_b[chain_b[2] + 1] != 0) { chain_b[2] += 2; chain_b[3] = 0; } flag = 1; chain_state_index = chain_a[1]; chain_state_link = chain_a[2]; chain_state_offset = chain_a[3]; chain_a[1] = env[n + 2]; chain_a[2] = env[n + 0]; chain_a[3] = env[n + 1]; protect_length = env[n + 5] - env[n + 2]; destination_offset = nextfree; //printf("protect_length %d destination_offset %d\n", protect_length, destination_offset); while (l--) { for(i = 0; i < protect_length; i++) { if (flag) c = chain_get_char(1); else c = dna_work_area[source_offset++];#ifdef __DEBUG__ // printf("protect(): char %c\n", c);#endif switch (c) { case 'I' : dna_work_area[destination_offset++] = 'C'; break; case 'C' : dna_work_area[destination_offset++] = 'F'; break; case 'F' : dna_work_area[destination_offset++] = 'P'; break; case 'P' : dna_work_area[destination_offset++] = 'I'; dna_work_area[destination_offset++] = 'C'; break; default : printf("protect(): Invalid char %c\n", c); exit(1); } } source_offset = nextfree; protect_length = destination_offset - nextfree; nextfree = destination_offset; flag = 0; //printf("source_offset %d protect_length %d nextfree %d\n", source_offset, protect_length, nextfree); } chain_b[chain_b[2]] = source_offset; chain_b[chain_b[2] + 1] = protect_length; chain_b[0] += protect_length; chain_b[1] += protect_length; chain_b[2] += 2; chain_a[1] = chain_state_index; chain_a[2] = chain_state_link; chain_a[3] = chain_state_offset; }}void asnat(unsigned int l){ asnatcount++; while (l) { if (l & 1) chain_put_char('C'); else chain_put_char('I'); l >>= 1; } chain_put_char('P');}void replace(unsigned int template_length, unsigned int env_length) { unsigned int templ_index = 0; unsigned char b; unsigned int l, n, i; replacecount++; chain_b[0] = 0; chain_b[1] = 0; chain_b[2] = 4; chain_b[3] = 0; chain_b[4] = nextfree; chain_b[5] = 0; while (templ_index < template_length) { switch(templ[templ_index]) { case 'C' : case 'F' : case 'I' : case 'P' : //printf("replace(): %c\n", templ[templ_index]); //printf("Storing at %d\n", chain_b[chain_b[2]] + chain_b[3]); //dna_work_area[chain_b[chain_b[2]] + chain_b[3]++] = templ[templ_index++]; //chain_b[chain_b[2] + 1]++; //chain_b[0]++; //chain_b[1]++; //nextfree++; chain_put_char(templ[templ_index++]); //printf("replace(): %d\n", chain_b[chain_b[2]]); break; case 'l' : templ_index++; l = templ[templ_index++] * 6; //printf("replace(): l %d env_length %d %d %d %d\n", l, env_length, env[l + 5], env[l + 2], env[l + 5] - env[l + 2]); //for (i = 0; i < 6; i++) // printf("%d ", env[l + i]); //printf("\n"); //for (i = 0; i < 40; i++) // printf("%d ", chain_a[i]); //printf("\n"); if (l < env_length) { l = env[l + 5] - env[l + 2]; asnat(l); } else { chain_put_char('P'); }#ifdef __DEBUG__ printf("replace(): case l = %d\n", l);#endif break; case 'n' : templ_index++; l = templ[templ_index++]; n = templ[templ_index++] * 6;#ifdef __DEBUG__ //printf("replace(): n %08x %08x %08x\n", l, n, env_length);#endif if (n < env_length) protect(l, n); chain_b[chain_b[2]] = nextfree; chain_b[chain_b[2] + 1] = 0; break; default : templ_index++;// exit(1); } // printf("replace(): %08x\n", dna_to_index); }} int pattern(void){ unsigned int pattern_index = 0; unsigned int level = 0; unsigned int i; unsigned char c; while (1) { switch(chain_get_char(1)) { case 'C' : pat[pattern_index++] = 'I'; break; case 'F' : pat[pattern_index++] = 'C'; break; case 'P' : pat[pattern_index++] = 'F'; break; case 'I' : switch(chain_get_char(1)) { case 'C' : pat[pattern_index++] = 'P'; break; case 'P' : pat[pattern_index++] = '!'; pat[pattern_index++] = nat(); if (pat[pattern_index - 1] == MAGICNUMBER) { printf("pattern break\n"); error = 1; return pattern_index; } break; case 'F' : pat[pattern_index++] = '?'; chain_get_char(1); pattern_index += consts((unsigned char*) &pat[pattern_index]); break; case 'I' : switch(chain_get_char(1)) { case 'P' : level++; pat[pattern_index++] = '('; break; case 'C' : case 'F' : if (level == 0) {#ifdef __DEBUG__ printf("\n");#endif return pattern_index; } else { level--; pat[pattern_index++] = ')'; } break; case 'I' : for (i = 0; i < 7; i++) rna[rna_index++] = chain_get_char(1); num_rna++;#ifdef __DEBUG__ //if (rna[rna_index - 7] != 'P') //{ memcpy(rna_buffer, rna + rna_index - 7, 7); rna_buffer[7] = 0; printf("RNA output: %s\n", rna_buffer); //}#endif break; default : error = 1; return pattern_index; } break; default : error = 1; return pattern_index; } break; default : error = 1; return pattern_index; } }}int template(void){ unsigned int templ_index = 0; int i; while (1) { switch(chain_get_char(1)) { case 'C' : templ[templ_index++] = 'I'; break; case 'F' : templ[templ_index++] = 'C'; break; case 'P' : templ[templ_index++] = 'F'; break; case 'I' : switch(chain_get_char(1)) { case 'C' : templ[templ_index++] = 'P'; break; case 'F' : case 'P' : templ[templ_index++] = 'n'; templ[templ_index++] = nat(); templ[templ_index++] = nat(); break; case 'I' : switch(chain_get_char(1)) { case 'C' : case 'F' :#ifdef __DEBUG__ printf("\n");#endif return templ_index; case 'P' : templ[templ_index++] = 'l'; templ[templ_index++] = nat(); break; case 'I' : for (i = 0; i < 7; i++) rna[rna_index++] = chain_get_char(1); num_rna++; #ifdef __DEBUG__ //if (rna[rna_index - 7] != 'P') //{ memcpy(rna_buffer, rna + rna_index - 7, 7); rna_buffer[7] = 0; printf("RNA output: %s\n", rna_buffer); //}#endif break; default : error = 1; return templ_index; } break; default : error = 1; return templ_index; } break; default : error = 1; return templ_index; } }}void matchreplace(unsigned int pattern_length, unsigned int template_length){ unsigned int chain_state_index, chain_state_link, chain_state_offset; unsigned int env_index = 0; unsigned int pattern_index = 0; unsigned char* found; unsigned int r_length; unsigned int i, j, temp, size; unsigned int diff_from, diff_to; unsigned int* tptr; unsigned char* searchptr; unsigned char b, b2; unsigned int chainlength; unsigned int c_index = 0; unsigned int c[1024]; chain_state_index = chain_a[1]; chain_state_link = chain_a[2]; chain_state_offset = chain_a[3]; while (pattern_index < pattern_length) { switch(pat[pattern_index++]) { case 'C' : case 'F' : case 'I' : case 'P' : b = chain_get_char(0); if ((unsigned char) pat[pattern_index - 1] == b) {#ifdef __DEBUG__ //printf("matchreplace(): Letter match %c\n", b);#endif } else {#ifdef __DEBUG__ printf("matchreplace(): Letter mismatch %c %c\n", pat[pattern_index - 1], b);#endif //printf("value %d\n", chain_a[1]); chain_a[1] = chain_state_index; chain_a[2] = chain_state_link; chain_a[3] = chain_state_offset; return; } break; case '!' :#ifdef __DEBUG__ printf("matchreplace(): moving forward %d\n", pat[pattern_index]);#endif if (!chain_move_forward(pat[pattern_index++])) { chain_a[1] = chain_state_index; chain_a[2] = chain_state_link; chain_a[3] = chain_state_offset; return; } break; case '?' : searchcount++; if (!chain_search((unsigned char*) &pat[pattern_index])) { printf("Search failed!\n"); chain_a[1] = chain_state_index; chain_a[2] = chain_state_link; chain_a[3] = chain_state_offset; error = 0; return; } error = 0; j = strlen((unsigned char*) &pat[pattern_index]); pattern_index += (j + 3) >> 2; break; case '(' :#ifdef __DEBUG__ //printf("matchreplace(): (\n");#endif c[c_index++] = chain_a[1]; c[c_index++] = chain_a[3]; c[c_index++] = chain_a[2]; break; case ')' :#ifdef __DEBUG__ //printf("matchreplace(): )\n");#endif env[env_index++] = c[--c_index]; env[env_index++] = c[--c_index]; env[env_index++] = c[--c_index]; env[env_index++] = chain_a[2]; env[env_index++] = chain_a[3]; env[env_index++] = chain_a[1]; break; } }#ifdef __DEBUG__ //printf("matchreplace(): "); //for (j = 0; j < env_index; j++) // printf("%d ", env[j]); //printf("\n");#endif replace(template_length, env_index); if (chain_b[chain_b[2] + 1] != 0) { chain_b[2] += 2; chain_b[3] = 0; } while (chain_a[1] < chain_a[0]) { size = chain_a[chain_a[2] + 1] - chain_a[3]; chain_b[chain_b[2]] = chain_a[chain_a[2]] + chain_a[3]; chain_b[chain_b[2] + 1] = size; chain_a[1] += size; chain_a[2] += 2; chain_a[3] = 0; chain_b[0] += size; chain_b[1] += size; chain_b[2] += 2; chain_b[3] = 0; } chainlength = chain_b[2]; // printf("Chain length: %d\n", chainlength); chain_b[chain_b[2]] = 0; chain_b[chain_b[2] + 1] = 0; chain_b[1] = 0; chain_b[2] = 4; chain_b[3] = 0; tptr = chain_a; chain_a = chain_b; chain_b = tptr; if (chain_b[2] > 2500 || nextfree > 0x04000000) { if (dna_from_base > chain_b[0]) dna_from_base = 0; else dna_from_base = nextfree; temp = dna_from_base; printf("Cleaning up chains, relocating to %d\n", dna_from_base); while(dna_work_area[temp++] = chain_get_char(0)) ; error = 0; chain_a[1] = 0; chain_a[2] = 4; chain_a[3] = 0; chain_a[4] = dna_from_base; chain_a[5] = chain_a[0]; chain_a[6] = 0; chain_a[7] = 0; nextfree = dna_from_base + chain_a[0]; //for(i = 0; i < 8; i++) // printf("%d ", chain_a[i]); //printf("\n"); //exit(1); } //printf("%08x\n", &chain_a); //for (i = 0; i < 100; i++) // printf("%d ", chain_a[i]); //printf("\n"); //for (i = 0; i < 10; i++) // printf("%c", dna_work_area[chain_a[chain_a[2]] + i]); //printf("\n"); }int main(){ #ifdef __MINGW32__ _setmode(_fileno(stdout),_O_BINARY); #endif FILE* f; unsigned int size, pattern_length, template_length, i, j, temp; unsigned char b; dna_work_area = (unsigned char*) malloc(DNA_WORK_AREA_SIZE); rna = (unsigned char*) malloc(RNA_SIZE); rna_index = 0; chain_a = (unsigned int*) malloc(CHAIN_SIZE * 4); chain_b = (unsigned int*) malloc(CHAIN_SIZE * 4); pat = (unsigned int*) malloc(PATTERN_SIZE * 4); templ = (unsigned int*) malloc(TEMPLATE_SIZE * 4); env = (unsigned int*) malloc(ENV_SIZE * 4); prot = (unsigned char*) malloc(PROTECT_SIZE); f = fopen(FILENAME, "rb"); if (f == NULL) return 1; fseek(f, 0, SEEK_END); size = ftell(f); rewind(f); fread(dna_work_area + dna_from_base, 1, size, f); fclose(f); // Setting up initial chain chain_a[0] = size; // total chain length chain_a[1] = 0; // total chain offset chain_a[2] = 4; // current chain link - chain array offset chain_a[3] = 0; // current chain link - offset inside link // the chain starts here chain_a[4] = 0; // offset to chain link chain_a[5] = size; // length of chain link chain_a[6] = 0; chain_a[7] = 0; chain_a[8] = 0; chain_a[9] = 0; nextfree = size; for (j = 0; j < NUM_ITER; j++) {#ifndef __DEBUG__#ifndef __VERBOSE__ if (j % 10000 == 0)#endif#endif printf("main(): Iteration %d %08x %08x\n", j, nextfree, rna_index); num_rna = 0; pattern_length = pattern(); if (error) break; #ifdef __VERBOSE__ print_pattern(pattern_length); printf("Ending offset %08x\n", chain_a[1]); if (num_rna) printf("Extracted RNA %d\n", num_rna);#endif #ifdef __DEBUG__ printf("main(): pattern %d\n", pattern_length); for (i = 0; i < pattern_length; i++) printf("%08x ", pat[i]); printf("\n");#endif num_rna = 0; template_length = template(); if (error) break; #ifdef __VERBOSE__ print_template(template_length); printf("Ending offset %08x\n", chain_a[1]); if (num_rna) printf("Extracted RNA %d\n", num_rna); #endif #ifdef __DEBUG__ printf("main(): template %d\n", template_length); for (i = 0; i < template_length; i++) printf("%08x ", templ[i]); printf("\n");#endif matchreplace(pattern_length, template_length); } chain_a[1] = 0; chain_a[2] = 4; chain_a[3] = 0; printf("%d %d %d %d %d %d %d\n", natcount, constscount, protectcount, realprotectcount, asnatcount, replacecount, searchcount); printf("outputting %d %d %d\n", chain_a[chain_a[2]], nextfree, chain_a[0]); temp = nextfree; while(dna_work_area[temp++] = chain_get_char(0)) ; f = fopen("output.dna", "wb"); if (!f) { printf("File open error\n"); exit(1); } fwrite(dna_work_area + nextfree, chain_a[0], 1, f); fclose(f); f = fopen("output.rna", "wb"); if (!f) { printf("File open error\n"); exit(1); } fwrite(rna, rna_index, 1, f); fclose(f); free(dna_work_area); free(rna); free(pat); free(templ); free(env); return 0;}