poly.cpp

非常好用的五子棋游戏源码

// Created:11-01-98
// By Jeff Connelly

// Chosing a good CRC polynomial (refered to hereinafter as "poly")

// ERRORS AND SOLUTIONS
// --------------------
// (Note: "E" refers to the corrupted error-containing number)

// SINGLE BIT ERRORS: Means E=1000...0000, poly should have at least 2 bits
// set to 1.

// TWO-BIT ERRORS: Errors in form: 100...000100...000 where E contains two
// one bits.  Choose a poly that does not have the multibles: 11, 101, 1001,
// 10001, 100001, 1000001, ect.

// ERRORS WITH ODD NUMBER OF BITS: Choose a poly that has an even number of
// bits, such as 16 or 32.

// BURST ERRORS: Look like E=000...000111...11110000...00, E consists of all
// zeros except for a run of 1's somewhere.  Set lowest bit of poly to 1.

// Some good polys are:
// 16, 12, 5, 0                                             [X25 Standard]
// 16, 15, 2, 0                                             [CRC-16]
// 32, 26, 23, 22, 16, 12, 11, 10, 8, 7, 5, 4, 2, 1, 0      [Ethernet]

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

// Structure to repersent the results of a poly checking
typedef struct
{
    bool singlebit : 1;     // Single-bit error
    bool twobit : 1;        // Two-bit error
    bool oddbit : 1;        // Errors with an odd number of bits
    bool burst : 1;         // Burst error
} POLYINFO;
    
// Checks the polynomial 'poly' and returns results
POLYINFO CheckPoly(unsigned long poly)
{
    POLYINFO ret = { 0, 0, 0, 0 };
    register int i;
    int j = 0;

    // Test 1: Single bit error, should have at least two bits set to 1
    for (i = 1; i < sizeof(poly); i <<= 1)
    {
        if (poly & i)
            ++j;        // 'j' is number of bits set to 1
    }
    if (j >= 2)         // Has at least two bits set to 1
        ret.singlebit = 1;

    // Test 2: Two-bit error, should not have multibles 11, 101, 1001, ect.
    // I don't know how to do this
    ret.twobit = 0;

    // Test 3: Errors with odd number of bits, polynomial should have even
    // number of bits.  Since this is always a 32-bit polynomial, we don't
    // have to worry about it.
    ret.oddbit = 1;

    // Test 4: Burst errors, prevented by setting lowest bit to 1.
    if (poly & 1)   // Lowest bit is set
        ret.burst = 1;

    return ret;
}

// Print the information stored in 'poly'
void PrintInfo(POLYINFO poly)
{
    printf ("%c%c%c%c",
            (poly.singlebit ? '*' : ' '),
            (poly.twobit ? '*' : ' '),
            (poly.oddbit ? '*' : ' '),
            (poly.burst ? '*' : ' '));

/*
    printf ("Single Bit Errors: %s\n"
            "Two-bit Errors: %s\n"
            "Odd Number of Bits Errors: %s\n"
            "Burst Errorsd: %s\n",
            (poly.singlebit ? "Detected" : "NOT DETECTED"),
            (poly.twobit ? "Detected" : "NOT DETECTED"),
            (poly.oddbit ? "Detected" : "NOT DETECTED"),
            (poly.burst ? "Detected" : "NOT DETECTED"));
*/
}

void CheckRange(int begin, int end, int incr)
{
    register int i;
    register POLYINFO info = { 0, 0, 0, 0 };

    for (i = begin; i < end; i += incr)
    {
        printf ("\nPoly %x", i); 
        info = CheckPoly(i);
        PrintInfo(info);
    }
}


int main(int argc, char* argv[])
{
    unsigned long poly = 0;
    unsigned long begin, end, incr;
    POLYINFO info = { 0, 0, 0, 0 };

    if (argc == 1)
    {
        printf ("Checks to see if a CRC polynomial is good.\n"
                "\tPOLY p     -> Check polynomial P to see if good.\n"
                "\tPOLY b e i -> Check all polynomials from B to E, adding\n"
                "                I each time.\n"
                "\tPOLY a > f -> A is P or B, E, I (above), redirect to F\n"
                "The polynomial checks are reported in this format: \n"
                "Single-Bit Two-Bit Odd-Bit Burst\n"
                "A * is displayed if the specified polynomial passes that test, \n"
                "instead a space will be there.  For example, if a polynomial\n"
                "passed all the tests: ****\n"
                "\n");
        exit (0);
    }

    if (argc == 2)
    {
        poly = atol(argv[1]);
        printf ("Checking polynomial %U...\n", poly);
        info = CheckPoly (poly);
        PrintInfo(info);
    } else if (argc == 4) {
        begin = atol(argv[1]);
        end = atol(argv[2]);
        incr = atol(argv[3]);
        printf ("Checking polynomials from %U to %U, incrmenting by %U...\n",
                begin, end, incr);
        CheckRange(begin, end, incr);
    }
    return 0;
}