summaryrefslogtreecommitdiff
path: root/cesar/lib/crc.h
blob: 7f3b3574be593b0992773d3e030088243ad056b5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#ifndef lib_crc_h
#define lib_crc_h
/* Cesar project {{{
 *
 * Copyright (C) 2007 Spidcom
 *
 * <<<Licence>>>
 *
 * }}} */
/**
 * \file    lib/crc.h
 * \brief   General Cyclic Redundancy Code utilities.
 * \ingroup lib
 *
 * General CRC utilities
 * =====================
 *
 * This module follows the Rocksoft^tm Model CRC Algorithm, introduced in "A
 * painless guide to CRC error detection algorithms" by Ross N. Williams.  You
 * can get it at http://www.ross.net/crc/.  This model defines a nomenclature
 * of existing CRC implementations in order to fully specify a CRC algorithm.
 * This module takes parameters from this model as input to generate the
 * requested CRC generator.
 *
 * Once you got a functional CRC algorithm, you also have to take care of
 * details such as:
 *
 *  - bit and byte order of the CRC digest,
 *  - whether extra zeros must be added to the message (this could be
 *    precomputed in crc_init),
 *  - what is the expected CRC result if feeding the algorithms with the
 *    message along with the appended CRC digest.
 *
 * Usage
 * =====
 *
 * To use this module, you should first call \c crc_init with your CRC
 * algorithm description and some extra memory.  This will construct a lookup
 * table to speed-up future computations.
 *
 * Example:
 *
 * \code
 *   static u32 crc32_tab[256];
 *   static crc_t crc32;
 *   crc32.width = 32;
 *   crc32.generator = 0x04c11db7;
 *   crc32.init = 0xffffffff;
 *   crc32.refin = true;
 *   crc32.refout = true;
 *   crc32.xorout = 0xffffffff;
 *   crc32.table.t32 = crc32_tab;
 *   crc_init (&crc32);
 * \endcode
 *
 * The table should be a 256 wide table of u32, u16 or u8, depending on the
 * CRC width.  You should store a pointer to it in \c table.t32, \c table.t16
 * or \c table.t8.
 *
 * CRC tables might be shared between several algorithms but this is an
 * unsupported feature, use at your own risk (basically, any parameters used
 * to initialise the table must be the same between the sharing algorithms).
 * If you play this game, remember that there is more than the table to
 * contain precomputed values.
 *
 * Once your CRC description is initialised, you can use it to compute CRC.
 * Initialisation should be done only once in your program life as the table
 * construction is expensive.
 *
 * You have two options to compute your CRC.  If the whole buffer is available
 * and linear, you can use \c crc_compute_block to compute the CRC in one
 * pass.  If the whole input buffer is not available yet or is sliced in
 * several non linear buffers, you should use \c crc_compute_begin to
 * initialise the CRC computation, \c crc_compute_continue_block for each
 * input blocks, and finally \c crc_compute_end to stop the computation and
 * retrieve the final CRC value.
 *
 * There is also a \c ..._le version of \c crc_compute_block and
 * \c crc_compute_continue_block which read input buffer using word access and
 * process read data as little endian.
 *
 * There is no big endian version as there is no demand for it for the moment.
 */

/** CRC description structure. */
struct crc_t
{
    /** \name client
     * Client filled values. */
    /*@{*/
    /** Width of the CRC register. */
    uint width;
    /** Generator polynomial, with the top bit left of. */
    u32 generator;
    /** Initial value of the CRC register. */
    u32 init;
    /** Whether to reflect input bytes. */
    bool refin;
    /** Whether to reflect the generated CRC. */
    bool refout;
    /** Value XOR'd with the final CRC register value. */
    u32 xorout;
    /*@}*/
    /** \name precomputed
     * Precomputed values, filled by crc_init(). */
    /*@{*/
    /** Precomputed initial register value. */
    u32 reg_init;
    /** Precomputed table, client should initialise table pointer. */
    union {
        /** Access by bytes. */
        u8 *t8;
        /** Access by halfwords. */
        u16 *t16;
        /** Access by words. */
        u32 *t32;
    } table;
    /*@}*/
};
typedef struct crc_t crc_t;

BEGIN_DECLS

/**
 * Compute precomputed values for the given CRC characteristics.
 * \param  ctx  filled CRC description
 */
void
crc_init (crc_t *ctx);

/**
 * Compute a CRC on a data block in one go.
 * \param  ctx  initialised CRC description
 * \param  block  data block
 * \param  block_size  data block size
 * \return  computed CRC
 */
u32
crc_compute_block (const crc_t *ctx, const u8 *block, uint block_size);

/**
 * Compute a CRC on a data block in one go, read little endian words,
 * handle unaligned data.
 * \param  ctx  initialised CRC description
 * \param  block  data block
 * \param  block_size  data block size
 * \return  computed CRC
 */
u32
crc_compute_block_le (const crc_t *ctx, const u8 *block, uint block_size);

/**
 * Begin a CRC computation.
 * \param  ctx  initialised CRC description
 * \return  initialised CRC register
 */
u32
crc_compute_begin (const crc_t *ctx);

/**
 * Continue a CRC computation on a data block.
 * \param  ctx  initialised CRC description
 * \param  reg  previously used or initialised CRC register
 * \param  block  data block
 * \param  block_size  data block size
 * \return  CRC register
 */
u32
crc_compute_continue_block (const crc_t *ctx, u32 reg, const u8 *block,
                            uint block_size);

/**
 * Continue a CRC computation on a data block, read little endian words,
 * handle unaligned data.
 * \param  ctx  initialised CRC description
 * \param  reg  previously used or initialised CRC register
 * \param  block  data block
 * \param  block_size  data block size
 * \return  CRC register
 */
u32
crc_compute_continue_block_le (const crc_t *ctx, u32 reg, const u8 *block,
                               uint block_size);

/**
 * End a CRC computation.
 * \param  ctx  initialised CRC description
 * \param  reg  previously used CRC register
 * \return  computed CRC
 */
u32
crc_compute_end (const crc_t *ctx, u32 reg);

END_DECLS

#endif /* lib_crc_h */