Statistics
| Branch: | Revision:

napa-baselibs / tests / Broadcaster / crc.c @ 507372bb

History | View | Annotate | Download (5.67 KB)

1
/**********************************************************************
2
 *
3
 * Filename:    crc.c
4
 *
5
 * Description: Slow and fast implementations of the CRC standards.
6
 *
7
 * Notes:       The parameters for each supported CRC standard are
8
 *                                defined in the header file crc.h.  The implementations
9
 *                                here should stand up to further additions to that list.
10
 *
11
 *
12
 * Copyright (c) 2000 by Michael Barr.  This software is placed into
13
 * the public domain and may be used for any purpose.  However, this
14
 * notice must not be changed or removed and no warranty is either
15
 * expressed or implied by its publication or distribution.
16
 **********************************************************************/
17

    
18
#include "crc.h"
19

    
20

    
21
/*
22
 * Derive parameters from the standard-specific parameters in crc.h.
23
 */
24
#define WIDTH    (8 * sizeof(crc))
25
#define TOPBIT   (1 << (WIDTH - 1))
26

    
27
#if (REFLECT_DATA == TRUE)
28
#undef  REFLECT_DATA
29
#define REFLECT_DATA(X)                        ((unsigned char) reflect((X), 8))
30
#else
31
#undef  REFLECT_DATA
32
#define REFLECT_DATA(X)                        (X)
33
#endif
34

    
35
#if (REFLECT_REMAINDER == TRUE)
36
#undef  REFLECT_REMAINDER
37
#define REFLECT_REMAINDER(X)        ((crc) reflect((X), WIDTH))
38
#else
39
#undef  REFLECT_REMAINDER
40
#define REFLECT_REMAINDER(X)        (X)
41
#endif
42

    
43

    
44
/*********************************************************************
45
 *
46
 * Function:    reflect()
47
 *
48
 * Description: Reorder the bits of a binary sequence, by reflecting
49
 *                                them about the middle position.
50
 *
51
 * Notes:                No checking is done that nBits <= 32.
52
 *
53
 * Returns:                The reflection of the original data.
54
 *
55
 *********************************************************************/
56
static unsigned long
57
reflect(unsigned long data, unsigned char nBits)
58
{
59
        unsigned long  reflection = 0x00000000;
60
        unsigned char  bit;
61

    
62
        /*
63
         * Reflect the data about the center bit.
64
         */
65
        for (bit = 0; bit < nBits; ++bit)
66
        {
67
                /*
68
                 * If the LSB bit is set, set the reflection of it.
69
                 */
70
                if (data & 0x01)
71
                {
72
                        reflection |= (1 << ((nBits - 1) - bit));
73
                }
74

    
75
                data = (data >> 1);
76
        }
77

    
78
        return (reflection);
79

    
80
}        /* reflect() */
81

    
82

    
83
/*********************************************************************
84
 *
85
 * Function:    crcSlow()
86
 *
87
 * Description: Compute the CRC of a given message.
88
 *
89
 * Notes:
90
 *
91
 * Returns:                The CRC of the message.
92
 *
93
 *********************************************************************/
94
crc
95
crcSlow(unsigned char const message[], int nBytes)
96
{
97
    crc            remainder = INITIAL_REMAINDER;
98
        int            byte;
99
        unsigned char  bit;
100

    
101

    
102
    /*
103
     * Perform modulo-2 division, a byte at a time.
104
     */
105
    for (byte = 0; byte < nBytes; ++byte)
106
    {
107
        /*
108
         * Bring the next byte into the remainder.
109
         */
110
        remainder ^= (REFLECT_DATA(message[byte]) << (WIDTH - 8));
111

    
112
        /*
113
         * Perform modulo-2 division, a bit at a time.
114
         */
115
        for (bit = 8; bit > 0; --bit)
116
        {
117
            /*
118
             * Try to divide the current data bit.
119
             */
120
            if (remainder & TOPBIT)
121
            {
122
                remainder = (remainder << 1) ^ POLYNOMIAL;
123
            }
124
            else
125
            {
126
                remainder = (remainder << 1);
127
            }
128
        }
129
    }
130

    
131
    /*
132
     * The final remainder is the CRC result.
133
     */
134
    return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);
135

    
136
}   /* crcSlow() */
137

    
138

    
139
crc  crcTable[256];
140

    
141

    
142
/*********************************************************************
143
 *
144
 * Function:    crcInit()
145
 *
146
 * Description: Populate the partial CRC lookup table.
147
 *
148
 * Notes:                This function must be rerun any time the CRC standard
149
 *                                is changed.  If desired, it can be run "offline" and
150
 *                                the table results stored in an embedded system's ROM.
151
 *
152
 * Returns:                None defined.
153
 *
154
 *********************************************************************/
155
void
156
crcInit(void)
157
{
158
    crc                           remainder;
159
        int                           dividend;
160
        unsigned char  bit;
161

    
162

    
163
    /*
164
     * Compute the remainder of each possible dividend.
165
     */
166
    for (dividend = 0; dividend < 256; ++dividend)
167
    {
168
        /*
169
         * Start with the dividend followed by zeros.
170
         */
171
        remainder = dividend << (WIDTH - 8);
172

    
173
        /*
174
         * Perform modulo-2 division, a bit at a time.
175
         */
176
        for (bit = 8; bit > 0; --bit)
177
        {
178
            /*
179
             * Try to divide the current data bit.
180
             */
181
            if (remainder & TOPBIT)
182
            {
183
                remainder = (remainder << 1) ^ POLYNOMIAL;
184
            }
185
            else
186
            {
187
                remainder = (remainder << 1);
188
            }
189
        }
190

    
191
        /*
192
         * Store the result into the table.
193
         */
194
        crcTable[dividend] = remainder;
195
    }
196

    
197
}   /* crcInit() */
198

    
199

    
200
/*********************************************************************
201
 *
202
 * Function:    crcFast()
203
 *
204
 * Description: Compute the CRC of a given message.
205
 *
206
 * Notes:                crcInit() must be called first.
207
 *
208
 * Returns:                The CRC of the message.
209
 *
210
 *********************************************************************/
211
crc
212
crcFast(unsigned char const message[], int nBytes)
213
{
214
    crc                   remainder = INITIAL_REMAINDER;
215
    unsigned char  data;
216
        int            byte;
217

    
218

    
219
    /*
220
     * Divide the message by the polynomial, a byte at a time.
221
     */
222
    for (byte = 0; byte < nBytes; ++byte)
223
    {
224
        data = REFLECT_DATA(message[byte]) ^ (remainder >> (WIDTH - 8));
225
                  remainder = crcTable[data] ^ (remainder << 8);
226
    }
227

    
228
    /*
229
     * The final remainder is the CRC.
230
     */
231
    return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);
232

    
233
}   /* crcFast() */