发信人: micheal (平凡的世界), 信区: ECE
标 题: A Painless Guide to CRC [7]
发信站: 大红花的国度 (Fri Jun 2 09:55:12 2000), 转信
16. A Catalog of Parameter Sets for Standards
---------------------------------------------
At this point, I would like to give a list of the specifications for
commonly used CRC algorithms. However, most of the algorithms that I
have come into contact with so far are specified in such a vague way
that this has not been possible. What I can provide is a list of polys
for various CRC standards I have heard of:
X25 standard : 1021 [CRC-CCITT, ADCCP, SDLC/HDLC]
X25 reversed : 0811
CRC16 standard : 8005
CRC16 reversed : 4003 [LHA]
CRC32 : 04C11DB7 [PKZIP, AUTODIN II, Ethernet, FDDI]
I would be interested in hearing from anyone out there who can tie
down the complete set of model parameters for any of these standards.
However, a program that was kicking around seemed to imply the
following specifications. Can anyone confirm or deny them (or provide
the check values (which I couldn't be bothered coding up and
calculating)).
Name : "CRC-16/CITT"
Width : 16
Poly : 1021
Init : FFFF
RefIn : False
RefOut : False
XorOut : 0000
Check : ?
Name : "XMODEM"
Width : 16
Poly : 8408
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : ?
Name : "ARC"
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : ?
Here is the specification for the CRC-32 algorithm which is reportedly
used in PKZip, AUTODIN II, Ethernet, and FDDI.
Name : "CRC-32"
Width : 32
Poly : 04C11DB7
Init : FFFFFFFF
RefIn : True
RefOut : True
XorOut : FFFFFFFF
Check : CBF43926
17. An Implementation of the Model Algorithm
--------------------------------------------
Here is an implementation of the model algorithm in the C programming
language. The implementation consists of a header file (.h) and an
implementation file (.c). If you're reading this document in a
sequential scroller, you can skip this code by searching for the
string "Roll Your Own".
To ensure that the following code is working, configure it for the
CRC-16 and CRC-32 algorithms given above and ensure that they produce
the specified "check" checksum when fed the test string "123456789"
(see earlier).
/****************************************************************************/
/* Start of crcmodel.h */
/****************************************************************************/
/* */
/* Author : Ross Williams (ross@guest.adelaide.edu.au.). */
/* Date : 3 June 1993. */
/* Status : Public domain. */
/* */
/* Description : This is the header (.h) file for the reference */
/* implementation of 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. */
/* */
/****************************************************************************/
/* */
/* How to Use This Package */
/* ----------------------- */
/* Step 1: Declare a variable of type cm_t. Declare another variable */
/* (p_cm say) of type p_cm_t and initialize it to point to the first*/
/* variable (e.g. p_cm_t p_cm = &cm_t). */
/* */
/* Step 2: Assign values to the parameter fields of the structure. */
/* If you don't know what to assign, see the document cited earlier.*/
/* For example: */
/* p_cm->cm_width = 16; */
/* p_cm->cm_poly = 0x8005L; */
/* p_cm->cm_init = 0L; */
/* p_cm->cm_refin = TRUE; */
/* p_cm->cm_refot = TRUE; */
/* p_cm->cm_xorot = 0L; */
/* Note: Poly is specified without its top bit (18005 becomes 8005).*/
/* Note: Width is one bit less than the raw poly width. */
/* */
/* Step 3: Initialize the instance with a call cm_ini(p_cm); */
/* */
/* Step 4: Process zero or more message bytes by placing zero or more */
/* successive calls to cm_nxt. Example: cm_nxt(p_cm,ch); */
/* */
/* Step 5: Extract the CRC value at any time by calling crc = cm_crc(p_cm); */
/* If the CRC is a 16-bit value, it will be in the bottom 16 bits. */
/* */
/****************************************************************************/
/* */
/* Design Notes */
/* ------------ */
/* PORTABILITY: This package has been coded very conservatively so that */
/* it will run on as many machines as possible. For example, all external */
/* identifiers have been restricted to 6 characters and all internal ones to*/
/* 8 characters. The prefix cm (for Crc Model) is used as an attempt to */
/* avoid namespace collisions. This package is endian independent. */
/* */
/* EFFICIENCY: This package (and its interface) is not designed for */
/* speed. The purpose of this package is to act as a well-defined reference */
/* model for the specification of CRC algorithms. If you want speed, cook up*/
/* a specific table-driven implementation as described in the document cited*/
/* above. This package is designed for validation only; if you have found or*/
/* implemented a CRC algorithm and wish to describe it as a set of para- */
/* meters to the Rocksoft^tm Model CRC Algorithm, your CRC algorithm imple- */
/* mentation should behave identically to this package under those para- */
/* meters. */
/* */
/****************************************************************************/
/* The following #ifndef encloses this entire */
/* header file, rendering it indempotent. */
#ifndef CM_DONE
#define CM_DONE
/****************************************************************************/
/* The following definitions are extracted from my style header file which */
/* would be cumbersome to distribute with this package. The DONE_STYLE is */
/* the idempotence symbol used in my style header file. */
#ifndef DONE_STYLE
typedef unsigned long ulong;
typedef unsigned bool;
typedef unsigned char * p_ubyte_;
#ifndef TRUE
#define FALSE 0
#define TRUE 1
#endif
/* Change to the second definition if you don't have prototypes. */
#define P_(A) A
/* #define P_(A) () */
/* Uncomment this definition if you don't have void. */
/* typedef int void; */
#endif
/****************************************************************************/
/* CRC Model Abstract Type */
/* ----------------------- */
/* The following type stores the context of an executing instance of the */
/* model algorithm. Most of the fields are model parameters which must be */
/* set before the first initializing call to cm_ini. */
typedef struct
{
int cm_width; /* Parameter: Width in bits [8,32]. */
ulong cm_poly; /* Parameter: The algorithm's polynomial. */
ulong cm_init; /* Parameter: Initial register value. */
bool cm_refin; /* Parameter: Reflect input bytes? */
bool cm_refot; /* Parameter: Reflect output CRC? */
ulong cm_xorot; /* Parameter: XOR this to output CRC. */
ulong cm_reg; /* Context: Context during execution. */
} cm_t;
typedef cm_t *p_cm_t;
/****************************************************************************/
/* Functions That Implement The Model */
/* ---------------------------------- */
/* The following functions animate the cm_t abstraction. */
void cm_ini P_((p_cm_t p_cm));
/* Initializes the argument CRC model instance. */
/* All parameter fields must be set before calling this. */
void cm_nxt P_((p_cm_t p_cm,int ch));
/* Processes a single message byte [0,255]. */
void cm_blk P_((p_cm_t p_cm,p_ubyte_ blk_adr,ulong blk_len));
/* Processes a block of message bytes. */
ulong cm_crc P_((p_cm_t p_cm));
/* Returns the CRC value for the message bytes processed so far. */
/****************************************************************************/
/* Functions For Table Calculation */
/* ------------------------------- */
/* The following function can be used to calculate a CRC lookup table. */
/* It can also be used at run-time to create or check static tables. */
ulong cm_tab P_((p_cm_t p_cm,int index));
/* Returns the i'th entry for the lookup table for the specified algorithm. */
/* The function examines the fields cm_width, cm_poly, cm_refin, and the */
/* argument table index in the range [0,255] and returns the table entry in */
/* the bottom cm_width bytes of the return value. */
/****************************************************************************/
/* End of the header file idempotence #ifndef */
#endif
/****************************************************************************/
/* End of crcmodel.h */
/****************************************************************************/
/****************************************************************************/
/* Start of crcmodel.c */
/****************************************************************************/
/* */
/* Author : Ross Williams (ross@guest.adelaide.edu.au.). */
/* Date : 3 June 1993. */
/* Status : Public domain. */
/* */
/* Description : This is the implementation (.c) file for the reference */
/* implementation of 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. */
/* */
/****************************************************************************/
/* */
/* Implementation Notes */
/* -------------------- */
/* To avoid inconsistencies, the specification of each function is not */
/* echoed here. See the header file for a description of these functions. */
/* This package is light on checking because I want to keep it short and */
/* simple and portable (i.e. it would be too messy to distribute my entire */
/* C culture (e.g. assertions package) with this package. */
/* */
/****************************************************************************/
#include "crcmodel.h"
/****************************************************************************/
/* The following definitions make the code more readable. */
#define BITMASK(X) (1L << (X))
#define MASK32 0xFFFFFFFFL
#define LOCAL static
/****************************************************************************/
LOCAL ulong reflect P_((ulong v,int b));
LOCAL ulong reflect (v,b)
/* Returns the value v with the bottom b [0,32] bits reflected. */
/* Example: reflect(0x3e23L,3) == 0x3e26 */
ulong v;
int b;
{
int i;
ulong t = v;
for (i=0; i<b; i++)
{
if (t & 1L)
v|= BITMASK((b-1)-i);
else
v&= ~BITMASK((b-1)-i);
t>>=1;
}
return v;
}
/****************************************************************************/
LOCAL ulong widmask P_((p_cm_t));
LOCAL ulong widmask (p_cm)
/* Returns a longword whose value is (2^p_cm->cm_width)-1. */
/* The trick is to do this portably (e.g. without doing <<32). */
p_cm_t p_cm;
{
return (((1L<<(p_cm->cm_width-1))-1L)<<1)|1L;
}
/****************************************************************************/
void cm_ini (p_cm)
p_cm_t p_cm;
{
p_cm->cm_reg = p_cm->cm_init;
}
/****************************************************************************/
void cm_nxt (p_cm,ch)
p_cm_t p_cm;
int ch;
{
int i;
ulong uch = (ulong) ch;
ulong topbit = BITMASK(p_cm->cm_width-1);
if (p_cm->cm_refin) uch = reflect(uch,8);
p_cm->cm_reg ^= (uch << (p_cm->cm_width-8));
for (i=0; i<8; i++)
{
if (p_cm->cm_reg & topbit)
p_cm->cm_reg = (p_cm->cm_reg << 1) ^ p_cm->cm_poly;
else
p_cm->cm_reg <<= 1;
p_cm->cm_reg &= widmask(p_cm);
}
}
/****************************************************************************/
void cm_blk (p_cm,blk_adr,blk_len)
p_cm_t p_cm;
p_ubyte_ blk_adr;
ulong blk_len;
{
while (blk_len--) cm_nxt(p_cm,*blk_adr++);
}
/****************************************************************************/
ulong cm_crc (p_cm)
p_cm_t p_cm;
{
if (p_cm->cm_refot)
return p_cm->cm_xorot ^ reflect(p_cm->cm_reg,p_cm->cm_width);
else
return p_cm->cm_xorot ^ p_cm->cm_reg;
}
/****************************************************************************/
ulong cm_tab (p_cm,index)
p_cm_t p_cm;
int index;
{
int i;
ulong r;
ulong topbit = BITMASK(p_cm->cm_width-1);
ulong inbyte = (ulong) index;
if (p_cm->cm_refin) inbyte = reflect(inbyte,8);
r = inbyte << (p_cm->cm_width-8);
for (i=0; i<8; i++)
if (r & topbit)
r = (r << 1) ^ p_cm->cm_poly;
else
r<<=1;
if (p_cm->cm_refin) r = reflect(r,p_cm->cm_width);
return r & widmask(p_cm);
}
/****************************************************************************/
/* End of crcmodel.c */
/****************************************************************************/
--
┌───────────────────────────────────┐
│ Ｃ = Ｗ·㏒﹝1﹢ＳＮＲ﹞ ▁▄▇█▇▄▁ │
│ ﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋ ▅███████▅ │
│ 噪声不是我的错 :) ▃███████████▃ │
│ ﹌﹌﹌﹌﹌﹌﹌﹌﹌ ▂▇█████████████▇▂ │
│▁▁▁▁▁▁▁▂▂▂▃▃▅▇█████████████████▇▄▃▂│
--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: sillystone.bbs@smth.]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：213.655毫秒