Advertisement
Guest User

Untitled

a guest
Dec 6th, 2017
307
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 7.24 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <sys/mman.h>
  5. #include <sys/stat.h>
  6. #include <sys/types.h>
  7. #include <unistd.h>
  8. #include <fcntl.h>
  9.  
  10. #define DATA_FILE "../sequence.dat"
  11. #define INDEX_FILE "sequence.vbsi"
  12. //#define KEY_LEN 11
  13. //#define DICT_SIZE 4194304
  14. //#define KEY_MASK  4194303  /* 4**11 -1 */
  15. #define MAX_LIST_LEN 3000
  16. #define LIST_NO_RECORD 0xFFFFFFFF
  17. #define VERSION 0x01010100
  18.  
  19. int DICT_SIZE;
  20. int KEY_LEN;
  21. u_int32_t KEY_MASK;
  22. int NlistSize;
  23. int srcLen;
  24.  
  25. typedef struct {     // Ячейка словаря
  26.   u_int32_t count;   // Количество вхождений ключа
  27.   u_int32_t point;   // Первый элемент в списке или позиция вхождения
  28. } dictCell;
  29. typedef struct {
  30.   u_int32_t end;     // Последний N элемент
  31.   u_int32_t start;   // Первый N элемент
  32. } NlistCell;
  33. typedef struct {     // Заголовок индексного файла
  34.   int version;       // Версия
  35.   int dictSize;      // Размер словаря
  36.   int NlistSize;     // Размер секции Nlist
  37.   int keyLen;        // Длина ключа
  38. } indexHeader;
  39. void error(const char *);
  40.  
  41. dictCell *dict;
  42. NlistCell *Nlist;
  43. int *List;
  44. unsigned char *src;
  45. int search(unsigned char *sline,int len);
  46. typedef struct {     // Рабочая структура поиска
  47.   dictCell d;        // Запись словаря
  48.   int      offs;     // Смещение ключа в паттерне
  49.   int      current;  // Текущая запись в списке словаря
  50. } searchInfo;
  51. int main() {
  52.   struct stat statbuf;
  53.   indexHeader *header;
  54.   int fdin,fdin1;
  55. //  unsigned char *sline="TTCTCTAGAGCAGACAGATCCGGGTGGAGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCAGAGAGATCCGGGTGGAGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCAGACAGATCCGGGTGGACGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCAGACAGATCCGGGTGGAGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCGGACAGATCCAGGTGGGGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCGGACAGATCCGGGTGGGGGTGGTTTTCTTTTGCACTTGATGTTCTCTAG";
  56.   unsigned char *sline="CAGATCCGGGTGGAGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCGGACAGATCCAGGTGGGGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCGGACAGATCCGGGTGGGGGTGGTTTTCTTTTGCACTTGATGTTCTCTAG";
  57. //  unsigned char *sline="GGATGGCTTAATAGTGCCAATAACACAACTGCCTGCCCACTTATTAGGTAACTGAATGTAGGCTCTGTGCCCACATTTCCAGTATAGGCCAGCGGGAGCTGCCCAGTCCTGATGAGATTCTGGATGAGCCCAGGCAGTTTTTAATTTAGAAAATTTACTAAATGGGTTCTTTTCAGTGTGGTTTAGGCCCCACCAAGTAATTGTCTTTGTTGTGCTGTTGTACAACTTCTGTCCTATACAATTAAGCTTTCCTACAGGGATGATAAATTCTTTTCCTTCTCTAGCTATACAGTATTGTCCAATAATTGAGGTTTTTAGGACCCAGAAGTTGCTAACTTGGGCCTTCTGAACTGGAATTATATTAGGAGCTGGATCAGTAGGCACCAACTCTCAGGCTTCCCAAGGCCATCGGTCTCCGATAGTGGTTTCCCCGCATATATAAGATGTAACATTAAGTGAATGAGCTACATTTCCTGCTAATTGGAGAAACAAATTTTTTGTCTTTTTCGGAAGTTCTGGTGCTGGCAGATTCAGCTCCTCATAAAAGGTTTGAAACACTGGTTTGGGAGAGCGCTTGTGGACTTCCCCTCTAACTAAAATGGCAACTTGGGGGTTTAACCCTGTCCCATCGATCCCCAGGGTTACACATTCTCCCTTTTTCCAAGGAGGATCTAGGGGATTGGTAATTATTAGTTCTAGT";
  58.   void *listData;
  59.   char *idxData;
  60.   if ( (fdin = open(DATA_FILE, O_RDONLY)) < 0 ) error("Error opening data file");
  61.   if ( fstat(fdin, &statbuf) < 0 ) error("fstat error");
  62.   srcLen=statbuf.st_size;
  63.   if ( (src = mmap(0, srcLen, PROT_READ, MAP_SHARED, fdin, 0)) == MAP_FAILED )
  64.     error("data file mmap error");
  65.   if ( (fdin1 = open(INDEX_FILE, O_RDONLY)) < 0 ) error("Error opening index file");
  66.   if ( fstat(fdin1, &statbuf) < 0 ) error("fstat1 error");
  67.   if ( (idxData = (char *)mmap(0, statbuf.st_size, PROT_READ, MAP_SHARED, fdin1, 0)) == MAP_FAILED )
  68.     error("index file mmap error");
  69.   header=(indexHeader *)idxData;
  70.   if(header->version!=VERSION) error("Index file version mismatch");
  71.   DICT_SIZE=header->dictSize;
  72.   KEY_LEN=header->keyLen;
  73.   KEY_MASK=DICT_SIZE-1;
  74.   NlistSize=header->NlistSize;
  75.   dict= (dictCell *)(idxData+sizeof(indexHeader));
  76.   Nlist=(NlistCell *)(idxData+sizeof(indexHeader)+sizeof(dictCell)*DICT_SIZE);
  77.   List=(int *)(((char *)Nlist)+sizeof(NlistCell)*header->NlistSize);
  78.   int i;
  79. //  for(i=0;i<15000;i++) {
  80.     search(sline,strlen(sline));
  81. //  }
  82. }
  83. u_int32_t getKey(unsigned char *data) {
  84.   u_int32_t key=0;
  85.   int i;
  86.   for(i=0;i<KEY_LEN;i++) {
  87.     if(data[i]=='N') return LIST_NO_RECORD;
  88.     key=((key<<2) | ((data[i] >> 1)&3));
  89.   }
  90.   return key & KEY_MASK;
  91. }
  92. int si_comparer(const void *a,const void *b) {
  93.   return (*(searchInfo **)a)->d.count - (*(searchInfo **)b)->d.count;
  94. }
  95. #define MAX_KEYS 20
  96. int search(unsigned char *sline,int len) {
  97.   int i=0,k=0;
  98.   searchInfo SI_STAT[MAX_KEYS];
  99.   searchInfo *SI[MAX_KEYS];
  100.   int o=srcLen+1;
  101.   while(i<len-KEY_LEN && k<MAX_KEYS) {  // Сбор информации о ключах и статистики по ним
  102.     if(sline[i]=='N') { i++; continue; } // Быстрый пропуск N
  103.     u_int32_t key=getKey(sline+i);
  104.     if(key==LIST_NO_RECORD) {
  105.       i++; continue;
  106.     }
  107.     if(dict[key].count==0) {
  108.       printf("key %06X (%11.11s): NOT FOUND\n",key,sline+i);
  109.       return -1;
  110.     }
  111.     SI_STAT[k].d.count=dict[key].count;
  112.     SI_STAT[k].d.point=dict[key].point;
  113.     SI_STAT[k].current=0; SI_STAT[k].offs=i;
  114.     SI[k]=&SI_STAT[k];
  115.     if(o>List[dict[key].point]-i) o=List[dict[key].point]-i;
  116.     printf("key %06X (%11.11s): %d o=%d\n",key,sline+i,dict[key].count,o);
  117.     k++;
  118.     i+=KEY_LEN;
  119.   }
  120.   qsort(SI,k,sizeof(searchInfo *),si_comparer);  // Сортировка списков по размеру
  121.   int nli=0,nlm;  // Текущий и максимальный для текущего окна паттерна элемент N-листа
  122.   int oend,endCnt=0;
  123.   while(endCnt<2) {
  124.     oend=o+len;
  125.     while(nli < NlistSize && Nlist[nli].end < o) nli++; // Подгоняем N-лист к текущей позиции
  126. //    if(nli < NlistSize && Nlist[nli].start >= o) {
  127. //      nlm=nli;
  128. //      while(nlm < NlistSize && Nlist[nlm].start < oend) nlm++;
  129. //    }
  130.     int newO=srcLen+1;
  131.     int matchCnt=0,co;
  132.     endCnt=0;
  133.     printf("Search at %d nli %d nlistEnd %d\n",o,nli,Nlist[nli].end);
  134.     for(i=0;i<10 && i<k;i++) { // Для теста обход только 3х листов
  135.       while(SI[i]->current < SI[i]->d.count
  136.             && List[SI[i]->d.point+SI[i]->current]-SI[i]->offs < o)
  137.         SI[i]->current++; // Подгоняем текущий лист к текущей позиции
  138.       if(SI[i]->current >= SI[i]->d.count) { endCnt++; continue; }
  139.       int co=List[SI[i]->d.point+SI[i]->current]-SI[i]->offs;
  140.       if(co==o) matchCnt++;
  141.       else { // Смещение в текущем списке больше текущего, совпадений не найдено
  142. //        printf("not found in %d %d;",i,Nlist[nli].start);
  143.         if(nli>=NlistSize || Nlist[nli].start > co) { // Смещение не покрывается N-листом
  144.           newO=co; // Искать на меньших позициях нет смысла
  145.           break;
  146.         }
  147.       }
  148.       if(newO>co) newO=co; // Ищем минимальную точку поиска на будущее
  149.     }
  150.     if(matchCnt>=4 || matchCnt==k-1) {
  151.       printf("Found match of %d keys at offset %d\n",matchCnt,o);
  152.       printf("%45.45s\n",src+o);
  153.     }
  154.     printf("matchCnt=%d; endCnt=%d; ",matchCnt,endCnt);
  155.     if(o<newO) o=newO;
  156.     else       o=o+len;
  157.   }
  158. }
  159.  
  160. void error(const char *msg) {
  161.   printf("%s\n",msg);
  162.   _exit(1);
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement