loopfinder.c

   1 //#include "List.h"
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <stddef.h>
   6 #include <sys/stat.h>
   7 #include <sys/types.h>
   8 #include <errno.h>
   9 #include <string.h>
  10 #include <assert.h>
  11
  12 #include "stringptr.h"
  13
  14
  15 typedef struct {
  16         char text_RIFF[4];
  17         unsigned int filesize_minus_8;
  18         char text_WAVE[4];
  19         char text_fmt[4];
  20         unsigned int formatheadersize;
  21         unsigned short format;
  22         unsigned short channels;
  23         unsigned int samplerate;
  24         unsigned int bytespersec;
  25         unsigned short blockalign;
  26         unsigned short bitwidth;
  27 } WAVE_HEADER;
  28
  29 size_t getfilesize(char *filename) {
  30         struct stat st;
  31         if(!stat(filename, &st)) {
  32                 return st.st_size;
  33         } else
  34                 return 0;
  35 }
  36
  37 stringptr *readfile(char *filename) {
  38         FILE *f;
  39         stringptr *buf;
  40         size_t size = getfilesize(filename);
  41         size_t bufpos = 0;
  42         size_t bread = 0;
  43         if(!size)
  44                 return NULL;
  45         f = fopen(filename, "r");
  46         if(!f)
  47                 return NULL;
  48         //buf = malloc(size);
  49         buf = new_string(size);
  50
  51         if(!buf)
  52                 goto FEXIT;
  53
  54         while(bufpos < size) {
  55                 bread = fread(buf->ptr + bufpos, 1, 64 * 1024, f);
  56                 bufpos += bread;
  57                 if(!bread) {
  58                         printf(strerror(errno));
  59                         break;
  60                 }
  61         }
  62         FEXIT:
  63         fclose(f);
  64         return buf;
  65 }
  66
  67 void searchBiggestRepeatingBlock(stringptr * buf) {
  68         size_t samplesize = 8;
  69         size_t startpos = 0;
  70         size_t scanpos = 0;
  71         size_t lastfoundoffset = 0;
  72         size_t lastfoundsamplesize = 0;
  73
  74         while(startpos < buf->size - samplesize) {
  75                 printf("approaching startpos %d with samplesize %d\n", startpos, samplesize);
  76                 scanpos = startpos + samplesize;
  77                 while(scanpos < buf->size - samplesize) {
  78                         if(buf->ptr[startpos] == buf->ptr[scanpos] &&
  79                            buf->ptr[startpos + samplesize - 1] == buf->ptr[scanpos + samplesize - 1] &&
  80                            memcmp(buf->ptr + startpos, buf->ptr + scanpos, samplesize) == 0) {
  81                                 lastfoundoffset = scanpos;
  82                                 lastfoundsamplesize = samplesize;
  83                                 samplesize++;
  84                                 while(scanpos + samplesize < buf->size
  85                                       && buf->ptr[startpos + samplesize - 1] == buf->ptr[scanpos + samplesize - 1])
  86                                         samplesize++;
  87                                 scanpos++;
  88                                 printf("#");
  89                         } else {
  90                                 scanpos++;
  91                         }
  92                 }
  93                 startpos++;
  94         }
  95         printf("\nlastfoundoffset: %d, lastfoundsamplesize: %d\n", lastfoundoffset, lastfoundsamplesize);
  96
  97 }
  98
  99 void searchLoop(char *buf, size_t bufsize, size_t startpos, size_t minsize, size_t blocksize) {
 100         size_t samplesize = minsize;
 101         size_t save = 0;
 102         size_t scanpos = 0;
 103
 104         //align startpos to blocksize
 105         startpos += startpos % blocksize;
 106
 107         while(startpos < bufsize - samplesize) {
 108                 if(startpos % 1000 == 0)
 109                         printf("approaching startpos %d with samplesize %d\n", startpos, samplesize);
 110                 assert(startpos % blocksize == 0);
 111                 samplesize = minsize;
 112                 scanpos = startpos + minsize;
 113                 save = 0;
 114                 //scanning the buffer from scanpos till eof, comparing with the junk from startpos.
 115                 while(scanpos < bufsize - samplesize) {
 116                         if(!memcmp(buf + startpos, buf + scanpos, samplesize)) {
 117                                 while(scanpos + samplesize < bufsize && startpos + samplesize < scanpos
 118                                       && !memcmp(buf + startpos + samplesize, buf + scanpos + samplesize, blocksize))
 119                                         samplesize += blocksize;
 120                                 if(startpos + samplesize == scanpos || scanpos + samplesize == bufsize) {
 121                                         printf("(possible) loop found at offset %d, length %d, repeats at %d!\n",
 122                                                startpos, samplesize, scanpos);
 123                                         // lets search for a bigger loop, which includes everything here
 124                                         save = samplesize;
 125                                         samplesize *= 2;
 126                                         scanpos += save;
 127                                 } else {
 128                                         printf("match of length %d found at %d and %d\n", samplesize, startpos,
 129                                                scanpos);
 130                                         save = samplesize;
 131                                         samplesize = scanpos - startpos;
 132                                         scanpos += save;
 133                                 }
 134                         } else
 135                                 scanpos += blocksize;
 136                 }
 137                 if(save)
 138                         startpos += save;
 139                 else
 140                         startpos += blocksize;
 141         }
 142         printf("no loops found :-/\n");
 143 }
 144
 145 int checkWaveValid(WAVE_HEADER * wave) {
 146         if(!memcmp((char *) wave->text_RIFF, "RIFF", 4) &&
 147            !memcmp((char *) wave->text_WAVE, "WAVE", 4) &&
 148            !memcmp((char *) wave->text_fmt, "fmt ", 4) && !memcmp((char *) &wave->format, "\x01\x00", 2))
 149                 return 1;
 150         else
 151                 return 0;
 152 }
 153
 154 size_t findWaveDataStart(WAVE_HEADER * wave) {
 155         if(checkWaveValid(wave)) {
 156                 if(!memcmp
 157                    ((char *) &wave->formatheadersize + sizeof(wave->formatheadersize) + wave->formatheadersize, "data",
 158                     4))
 159                         return ((size_t) & wave->formatheadersize - (size_t) wave) + sizeof(wave->formatheadersize) +
 160                             wave->formatheadersize + sizeof(int);
 161         }
 162         return 0;
 163 }
 164
 165 int main(int argc, char **argv) {
 166         // gcc -Wall -g -Isource loopfinder.c source/stringptr.c -o loopfinder
 167         stringptr *buf;
 168         char *data = NULL;
 169         WAVE_HEADER *wave = NULL;
 170         size_t datasize;
 171         size_t startpos;
 172         size_t minsize;
 173         if(argc < 4) {
 174                 puts("need a valid filename as argv1, scanstartoffset as argv2, minimum matchsize in bytes as argv3");
 175                 return 1;
 176         }
 177
 178         buf = readfile(argv[1]);
 179         startpos = atoi(argv[2]);
 180         minsize = atoi(argv[3]);
 181         if(buf->size > sizeof(WAVE_HEADER)) {
 182                 wave = (WAVE_HEADER *) buf->ptr;
 183                 data = buf->ptr + findWaveDataStart(wave);
 184                 datasize = buf->size - ((size_t) data - (size_t) buf->ptr);
 185                 if(data == buf->ptr)
 186                         printf("no valid WAVE file or compressed format. scanning whole file.\n");
 187                 else
 188                         printf("skipping WAVE header of length %d\n", (size_t) data - (size_t) buf->ptr);
 189         }
 190
 191         if(wave && datasize % wave->blockalign != 0) {
 192                 printf("error, filesize doesnt match blockalign!");
 193                 return 1;
 194         }
 195
 196         searchLoop(data, datasize, startpos, minsize, wave ? wave->blockalign : 1);
 197
 198         free_string(buf);
 199         return 0;
 200 }