发信人: micheal (平凡的世界), 信区: ECE
标  题: A Painless Guide to CRC [8]
发信站: 大红花的国度 (Fri Jun  2 09:55:37 2000), 转信

18. Roll Your Own Table-Driven Implementation
---------------------------------------------
Despite all the fuss I've made about understanding and defining CRC
algorithms, the mechanics of their high-speed implementation remains
trivial. There are really only two forms: normal and reflected. Normal
shifts to the left and covers the case of algorithms with Refin=FALSE
and Refot=FALSE. Reflected shifts to the right and covers algorithms
with both those parameters true. (If you want one parameter true and
the other false, you'll have to figure it out for yourself!) The
polynomial is embedded in the lookup table (to be discussed). The
other parameters, Init and XorOt can be coded as macros. Here is the
32-bit normal form (the 16-bit form is similar).
   unsigned long crc_normal ();
   unsigned long crc_normal (blk_adr,blk_len)
   unsigned char *blk_adr;
   unsigned long  blk_len;
   {
    unsigned long crc = INIT;
    while (blk_len--)
       crc = crctable[((crc>>24) ^ *blk_adr++) & 0xFFL] ^ (crc << 8);
    return crc ^ XOROT;
   }
Here is the reflected form:
   unsigned long crc_reflected ();
   unsigned long crc_reflected (blk_adr,blk_len)
   unsigned char *blk_adr;
   unsigned long  blk_len;
   {
    unsigned long crc = INIT_REFLECTED;
    while (blk_len--)
       crc = crctable[(crc ^ *blk_adr++) & 0xFFL] ^ (crc >> 8));
    return crc ^ XOROT;
   }
Note: I have carefully checked the above two code fragments, but I
haven't actually compiled or tested them. This shouldn't matter to
you, as, no matter WHAT you code, you will always be able to tell if
you have got it right by running whatever you have created against the
reference model given earlier. The code fragments above are really
just a rough guide. The reference model is the definitive guide.
Note: If you don't care much about speed, just use the reference model
code!
19. Generating A Lookup Table
-----------------------------
The only component missing from the normal and reversed code fragments
in the previous section is the lookup table. The lookup table can be
computed at run time using the cm_tab function of the model package
given earlier, or can be pre-computed and inserted into the C program.
In either case, it should be noted that the lookup table depends only
on the POLY and RefIn (and RefOt) parameters. Basically, the
polynomial determines the table, but you can generate a reflected
table too if you want to use the reflected form above.
The following program generates any desired 16-bit or 32-bit lookup
table. Skip to the word "Summary" if you want to skip over this code.
/****************************************************************************/
/*                             Start of crctable.c                          */
/****************************************************************************/
/*                                                                          */
/* Author  : Ross Williams (ross@guest.adelaide.edu.au.).                   */
/* Date    : 3 June 1993.                                                   */
/* Version : 1.0.                                                           */
/* Status  : Public domain.                                                 */
/*                                                                          */
/* Description : This program writes a CRC lookup table (suitable for       */
/* inclusion in a C program) to a designated output file. The program can be*/
/* statically configured to produce any table covered by the Rocksoft^tm    */
/* Model CRC Algorithm. For more information on the Rocksoft^tm Model CRC   */
/* Algorithm, see the document titled "A Painless Guide to CRC Error        */
/* Detection Algorithms" by Ross Williams (ross@guest.adelaide.edu.au.).    */
/* This document is likely to be in "ftp.adelaide.edu.au/pub/rocksoft".     */
/*                                                                          */
/* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia.  */
/*                                                                          */
/****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "crcmodel.h"
/****************************************************************************/
/* TABLE PARAMETERS                                                         */
/* ================                                                         */
/* The following parameters entirely determine the table to be generated.   */
/* You should need to modify only the definitions in this section before    */
/* running this program.                                                    */
/*                                                                          */
/*    TB_FILE  is the name of the output file.                              */
/*    TB_WIDTH is the table width in bytes (either 2 or 4).                 */
/*    TB_POLY  is the "polynomial", which must be TB_WIDTH bytes wide.      */
/*    TB_REVER indicates whether the table is to be reversed (reflected).   */
/*                                                                          */
/* Example:                                                                 */
/*                                                                          */
/*    #define TB_FILE   "crctable.out"                                      */
/*    #define TB_WIDTH  2                                                   */
/*    #define TB_POLY   0x8005L                                             */
/*    #define TB_REVER  TRUE                                                */
#define TB_FILE   "crctable.out"
#define TB_WIDTH  4
#define TB_POLY   0x04C11DB7L
#define TB_REVER  TRUE
/****************************************************************************/
/* Miscellaneous definitions.                                               */
#define LOCAL static
FILE *outfile;
#define WR(X) fprintf(outfile,(X))
#define WP(X,Y) fprintf(outfile,(X),(Y))
/****************************************************************************/
LOCAL void chk_err P_((char *));
LOCAL void chk_err (mess)
/* If mess is non-empty, write it out and abort. Otherwise, check the error */
/* status of outfile and abort if an error has occurred.                    */
char *mess;
{
 if (mess[0] != 0   ) {printf("%s\n",mess); exit(EXIT_FAILURE);}
 if (ferror(outfile)) {perror("chk_err");   exit(EXIT_FAILURE);}
}
/****************************************************************************/
LOCAL void chkparam P_((void));
LOCAL void chkparam ()
{
 if ((TB_WIDTH != 2) && (TB_WIDTH != 4))
    chk_err("chkparam: Width parameter is illegal.");
 if ((TB_WIDTH == 2) && (TB_POLY & 0xFFFF0000L))
    chk_err("chkparam: Poly parameter is too wide.");
 if ((TB_REVER != FALSE) && (TB_REVER != TRUE))
    chk_err("chkparam: Reverse parameter is not boolean.");
}
/****************************************************************************/
LOCAL void gentable P_((void));
LOCAL void gentable ()
{
 WR("/*****************************************************************/\n");
 WR("/*                                                               */\n");
 WR("/* CRC LOOKUP TABLE                                              */\n");
 WR("/* ================                                              */\n");
 WR("/* The following CRC lookup table was generated automagically    */\n");
 WR("/* by the Rocksoft^tm Model CRC Algorithm Table Generation       */\n");
 WR("/* Program V1.0 using the following model parameters:            */\n");
 WR("/*                                                               */\n");
 WP("/*    Width   : %1lu bytes.                                         */\n",
    (ulong) TB_WIDTH);
 if (TB_WIDTH == 2)
 WP("/*    Poly    : 0x%04lX                                           */\n",
    (ulong) TB_POLY);
 else
 WP("/*    Poly    : 0x%08lXL                                      */\n",
    (ulong) TB_POLY);
 if (TB_REVER)
 WR("/*    Reverse : TRUE.                                            */\n");
 else
 WR("/*    Reverse : FALSE.                                           */\n");
 WR("/*                                                               */\n");
 WR("/* For more information on the Rocksoft^tm Model CRC Algorithm,  */\n");
 WR("/* see the document titled \"A Painless Guide to CRC Error        */\n");
 WR("/* Detection Algorithms\" by Ross Williams                        */\n");
 WR("/* (ross@guest.adelaide.edu.au.). This document is likely to be  */\n");
 WR("/* in the FTP archive \"ftp.adelaide.edu.au/pub/rocksoft\".        */\n");
 WR("/*                                                               */\n");
 WR("/*****************************************************************/\n");
 WR("\n");
 switch (TB_WIDTH)
   {
    case 2: WR("unsigned short crctable[256] =\n{\n"); break;
    case 4: WR("unsigned long  crctable[256] =\n{\n"); break;
    default: chk_err("gentable: TB_WIDTH is invalid.");
   }
 chk_err("");
 {
  int i;
  cm_t cm;
  char *form    = (TB_WIDTH==2) ? "0x%04lX" : "0x%08lXL";
  int   perline = (TB_WIDTH==2) ? 8 : 4;
  cm.cm_width = TB_WIDTH*8;
  cm.cm_poly  = TB_POLY;
  cm.cm_refin = TB_REVER;
  for (i=0; i<256; i++)
    {
     WR(" ");
     WP(form,(ulong) cm_tab(&cm,i));
     if (i != 255) WR(",");
     if (((i+1) % perline) == 0) WR("\n");
     chk_err("");
    }
 WR("};\n");
 WR("\n");
 WR("/*****************************************************************/\n");
 WR("/*                   End of CRC Lookup Table                     */\n");
 WR("/*****************************************************************/\n");
 WR("");
 chk_err("");
}
}
/****************************************************************************/
main ()
{
 printf("\n");
 printf("Rocksoft^tm Model CRC Algorithm Table Generation Program V1.0\n");
 printf("-------------------------------------------------------------\n");
 printf("Output file is \"%s\".\n",TB_FILE);
 chkparam();
 outfile = fopen(TB_FILE,"w"); chk_err("");
 gentable();
 if (fclose(outfile) != 0)
    chk_err("main: Couldn't close output file.");
 printf("\nSUCCESS: The table has been successfully written.\n");
}
/****************************************************************************/
/*                             End of crctable.c                            */
/****************************************************************************/

--
┌───────────────────────────────────┐
│　Ｃ = Ｗ·㏒﹝1﹢ＳＮＲ﹞　　　　　　▁▄▇█▇▄▁　　　　　　　　　│
│　﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋      　　▅███████▅　　　　　　　　│
│　噪声不是我的错　:)　　　　　　▃███████████▃　　　　　　│
│　﹌﹌﹌﹌﹌﹌﹌﹌﹌  　　　▂▇█████████████▇▂　　　　│
│▁▁▁▁▁▁▁▂▂▂▃▃▅▇█████████████████▇▄▃▂│

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: sillystone.bbs@smth.]