An Algorithm for Error Correcting Cyclic Redundance Checks

/* The following program checks numbers to see if they are valid crc's
 * by counting the number of cycles from 1 to 1.
 */
#include <stdio.h>
#include <string.h>

unsigned long int gp, i, j, s, t, v, hpo2;
FILE *infile, *outfile;

int main()
  {
    char lkgp[100]; /* last known generator polynomial */
    char fn[] = {"crc_li3.in"};

    /* open up the file of already known GPs */
    if ((infile  = fopen(fn,"r")) == NULL)
      {
        printf("%s not found",fn);
        return 1;
      }

    /* put the newly discovered gp's into file x.x */
    if ((outfile = fopen("x.x", "w")) == NULL)
      {
        printf("Error:");
        return 1;
      }

    /* find the last known gp */
    while (fgets(lkgp,100,infile)!=NULL);
    fclose(infile);
    printf("lkgp = <%s>\n",lkgp); 

    /* convert the string to a long int */
    s = 0;
    for (i=0; i < strlen(lkgp); i++)
      {
        if (lkgp[i] != ' ')
        if (lkgp[i] != 13)
        if (lkgp[i] != 10)
          {
            s = s*(long long int)10;
            s = s + lkgp[i] - '0';
          }
        printf("%ld\n",s);
      }

    if (s%2 == 0) s++;  /* all GPs are odd */

    /* check the next 10000 numbers for valid gp's */
    for (gp = s+2; gp <= s+10000; gp+=2)
      {
        printf("testing  %lld\n",gp);
        t  = gp;

        /* determine the highest power of 2 in the gp */
        t = gp;
        hpo2 = 1;
        while ((t >> 1) > 0)
        { hpo2 = hpo2 + hpo2; t = t / 2; }

        /* see how many times v cycles around from 1 to 1 */
        v = 1;
        i = 1;
        do
          {
            v = v + v;
            if (v >= hpo2) v = v ^ gp;
            i = i + 1;
          }
        while (v != 1);

        /* if the number of cycles is == hpo2 then it is an
                acceptable
         * generator polynomial and can be used for error
                correction.
*/
        if (i == hpo2)
          {
            printf("%ld is an error correcting gp\n",gp);
            fprintf(outfile," %ld\n",gp);
          }
      }
  fclose(outfile);
  return 0;
}