//Copyright Michael Niedermayer GPL

#include <stdio.h>
#include <string.h>

#define BLOCK_SIZE (1<<12) // MAX is 1<<16
#define TRYS 5000
#define G 0x00210801
unsigned int crctab[BLOCK_SIZE][2];

static int cmp (int *a, int *b){
    return (a[0] > b[0]) - (a[0] < b[0]);
}

static int get_error(unsigned int crc, unsigned int len, int error[2]){
    int i;

    for(i=0; i<len; i++){
        int *result= bsearch(&crc, crctab, BLOCK_SIZE, 2*sizeof(int), cmp);
        if(result){
            error[0]= i;
            error[1]= result[1] + i;
            return 1 + (result != crctab[0]);
        }
        crc= (crc>>1) ^ (((G>>1)|0x80000000) & (-(crc&1)));
    }
    return -1;
}

static int get_crc(char *val, int len){
    int j, v=0;
    for(j=0; j<len; j++){
        if(val[j] & ~1) fprintf(stderr, "error3\n");
        v= ((v<<1) + val[j]) ^ (G & (v>>31));
    }
    return v;
}

main(){
    unsigned int i,j,k,v,crc;
    char val[BLOCK_SIZE];

    v=1;
    for(i=0; i<BLOCK_SIZE; i++){
        crctab[i][0]= i ? (v^1) : v;
        crctab[i][1]= i;
        v= (v<<1) ^ (G & (((int)v)>>31));
    }

    qsort(crctab, BLOCK_SIZE, 2*sizeof(int), cmp);

    for(i=0; i<TRYS; i++){
        int error[2];

        memset(val, 0, sizeof(val));
        for(j=0; j<BLOCK_SIZE-32; j++){
            val[j]= rand()&1;
        }
        v= get_crc(val, BLOCK_SIZE);
        crc= v;
        for(j=BLOCK_SIZE-32; j<BLOCK_SIZE; j++){
            val[j]= v>>31;
            v<<=1;
        }
        v= get_crc(val, BLOCK_SIZE);
        if(v) fprintf(stderr, "error\n");

        j= rand() % BLOCK_SIZE;
        k= rand() % (j+1);
        val[BLOCK_SIZE - j - 1] ^= 1;
        if(j!=k)
            val[BLOCK_SIZE - k - 1] ^= 1;
        v= get_crc(val, BLOCK_SIZE);

        get_error(v, BLOCK_SIZE, error);
        if(error[0] != k || error[1] != j) 
            fprintf(stderr, "error2 %d %d %d %d %X %X\n", j, k, error[0], error[1], v, crc);
        fprintf(stderr, ".");
    }
    fprintf(stderr, "\n");
}