- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <ctype.h>
- char table [100][10]; /* the table of random digits */
- /* max: 100 numbers of 10 digits each */
- void DisplayUsage();
- void LoadTableRandom ( char * );
- int GetChecksum ( char *, int, int );
- int main( int argc, char *argv[] )
- {
- int i, j, size, method;
- char *pmax;
- char buffer[10];
- char *p= (char *) table; /* start of table */
- pmax = p + 1000; /* end of table */
- if ( argc != 2 )
- {
- DisplayUsage();
- return EXIT_FAILURE;
- }
- else
- method = atoi ( argv[1] );
- switch ( method )
- {
- case 1:
- printf ( "Using 7 mod 11\\n\\n");
- break;
- case 2:
- printf ( "Using 9 mod 11\\n\\n");
- break;
- case 3:
- printf ( "Using 7 mod 26\\n\\n");
- break;
- case 4:
- printf ( "Using 7 mod 10\\n\\n");
- break;
- case 5:
- printf ( "Using 9 mod 10\\n\\n");
- break; default:
- DisplayUsage();
- return EXIT_FAILURE;
- }
- /*we loop through for every size from 10 to 2.
- We don't handle 1-digit numbers since they
- offer no possibility of transpositions.*/
- for ( size = 10; size > 1; size-- )
- {
- int collisions = 0;
- /* Load the table with random digits */
- LoadTableRandom ( pmax );
- /* main test loop: we process 100 numbers
- of length size. For each number, we do every
- possible transposition and get its checksum. */
- for ( i = 0, p = (char *)table; i < 100;i++, p += size )
- {
- int k, l, orig_cksum;
- /* get the original number's checksum */
- orig_cksum = GetChecksum ( p, size, method );
- /* now copy the number to buffer, where we'll do the transpositions.*/
- memcpy ( buffer, p, size );
- /* do the transpositions and checksums */
- for ( k = 0; k < size - 1; k++ )
- {
- /* is there a transposition possible?
- if both digits are the same, they cannot
- be transposed; so skip these, otherwise
- they will generate bogus collisions.
- */
- if ( buffer[k] == buffer[k + 1] )
- continue;
- /* otherwise, do the transposition */
- l = buffer[k + 1];
- buffer[k + 1] = buffer[k];
- buffer[k] = (char) l;
- /* get the checksum */
- j = GetChecksum ( buffer, size, method );
- if ( j == orig_cksum )
- collisions++;
- /* now undo this transposition */
- l = buffer[k + 1];
- buffer[k +1] = buffer[k];
- buffer[k] = (char) l;
- }
- } /* end of loop processing numbers of one size */
- printf ( "%2d digits avg. %1.2f collisions\\n",size,(float) ( collisions / 100.0 ));
- collisions = 0;
- }
- return EXIT_SUCCESS;
- }
- void LoadTableRandom ( char *table_end )
- {
- int i;
- unsigned short int j;
- char *p, *p2;
- /* 200 random ints will get us close to 1000 digits
- we presume it gets us at least 500 digits, which is
- a safe bet, but will not always be the case.
- */
- p = (char *) table;
- for ( i = 0; i < 200; i++ )
- {
- j = (short int) rand();
- sprintf ( p, "%u", j );
- p += strlen ( p );
- }
- /* how many digits left to fill out? */
- i = table_end - p;
- p2 = p - 1;
- /* go backwards from p and copy digits into the
- remaining table space. This will copy i digits
- prior to p and place them in reverse order after p. */
- while ( i )
- {
- *p++ = *p2--;
- i--;
- }
- }
- int GetChecksum ( char *data, int length, int which_test )
- {
- int i, j;
- int position;
- unsigned long int sum;
- long int *powers;
- static long int powers_of_7 [10] = { 1, 7, 49, 343, 2401, 16807, 117649, 823543, 5764801, 40353607 };
- static long int powers_of_9 [10] = { 1, 9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489 };
- if ( which_test == 2 || which_test == 5 )
- powers = powers_of_9;
- else
- powers = powers_of_7;
- /* make sure all digits can be looked up */
- if ( length > 10 )
- return -1;
- sum = 0L;
- position =0; /* what digit in the data are we at? */
- for ( i = length; i > 0; i--, position++ )
- {
- /* do we have a digit ? */
- if ( ! isdigit ( data[i-1] ))
- return -2;
- /* convert digit character to a number */
- j = data[i-1] - '0';
- /* look up power, multiply by j, add to sum */
- sum += powers [position] * j;
- }
- /* get the sum modulus depending on method */
- switch ( which_test )
- {
- case 1:
- case 2:
- i = (int) ( sum % 11L );
- if ( i == 10 )
- i = 0;
- break;
- case 3:
- i = (int) ( sum % 26L );
- break;
- case 4:
- case 5:
- i = (int) ( sum % 10L );
- break;
- default:
- DisplayUsage();
- exit (EXIT_FAILURE);
- }
- return ( i );
- }
- void DisplayUsage()
- {
- fprintf ( stderr,"Error: need to specify checksum method to test\\n"
- "1. Powers of 7 Mod 11\\n"
- "2. Powers of 9 Mod 11\\n"
- "3. Powers of 7 Mod 26\\n"
- "4. Powers of 7 Mod 10\\n"
- "5. Powers of 9 Mod 10\\n" );
- }
- //该片段来自于http://www.codesnippet.cn/detail/250720134811.html
来源: http://www.codesnippet.cn/detail/250720134811.html