1 | //====================================================================== |
---|
2 | // |
---|
3 | // Project: XTIDE Universal BIOS, Serial Port Server |
---|
4 | // |
---|
5 | // File: checksum.cpp - Checksum function and test routines |
---|
6 | // |
---|
7 | // This file implements Fletcher's Checksum. The serial code uses this checksum, as it is very quick |
---|
8 | // to calculate in assembly and offers reasonable error detection. |
---|
9 | // For more information, see http://en.wikipedia.org/wiki/Fletcher%27s_checksum. |
---|
10 | // |
---|
11 | // Since it is faster in 8088 assembly code to deal with 16-bit quantities than 8-bit quantities, |
---|
12 | // Fletcher's Checksum has been modified to calculate the 32-bit checksum, and then "fold" the result into a |
---|
13 | // 16-bit quantity. Fletcher's 32-bit Checksum consists of two parts: concatenated 16-bit accumulators. |
---|
14 | // To "fold" to 16-bits, The upper and lower 8-bits of each of these accumulators is XOR'd independently, and then |
---|
15 | // the two results concatenated together, resulting in 16-bits. Although simpler, an early attempt to XOR the |
---|
16 | // 16-bit accumulators results in poorer error detection behavior. Folding as described here results in error |
---|
17 | // detection on par with Fletcher's 16-bit Checksum. |
---|
18 | // |
---|
19 | // With #define CHECKSUM_TEST, this file becomes a self-contained command line program that runs |
---|
20 | // some statistical tests comparing various checksum algorithms with random 512-byte sectors and various |
---|
21 | // levels of errors introduced. |
---|
22 | // |
---|
23 | |
---|
24 | #include "library.h" |
---|
25 | |
---|
26 | unsigned short checksum( unsigned short *wbuff, int wlen ) |
---|
27 | { |
---|
28 | unsigned long a = 0xffff; |
---|
29 | unsigned long b = 0xffff; |
---|
30 | int t; |
---|
31 | |
---|
32 | for( t = 0; t < wlen; t++ ) |
---|
33 | { |
---|
34 | a += wbuff[t]; |
---|
35 | b += a; |
---|
36 | } |
---|
37 | |
---|
38 | a = (a & 0xffff) + (a >> 16); |
---|
39 | b = (b & 0xffff) + (b >> 16); |
---|
40 | a = (a & 0xffff) + (a >> 16); |
---|
41 | b = (b & 0xffff) + (b >> 16); |
---|
42 | |
---|
43 | // Although tempting to use, for its simplicity and size/speed in assembly, the following folding |
---|
44 | // algorithm results in many undetected single bit errors and therefore should not be used. |
---|
45 | // return( (unsigned short) (a ^ b) ); |
---|
46 | |
---|
47 | return( (unsigned short) (((a & 0xff) << 8) ^ (a & 0xff00)) + (((b & 0xff00) >> 8) ^ (b & 0xff)) ); |
---|
48 | } |
---|
49 | |
---|
50 | #ifdef CHECKSUM_TEST |
---|
51 | |
---|
52 | //==================================================================================================== |
---|
53 | // |
---|
54 | // Test Code |
---|
55 | // |
---|
56 | |
---|
57 | #include <stdlib.h> |
---|
58 | #include <stdio.h> |
---|
59 | #include <time.h> |
---|
60 | #include <math.h> |
---|
61 | |
---|
62 | #define BUCKETS 65536 |
---|
63 | #define BITTEST 16 |
---|
64 | |
---|
65 | unsigned char bit[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; |
---|
66 | |
---|
67 | class algorithm |
---|
68 | { |
---|
69 | public: |
---|
70 | virtual unsigned short checksum( unsigned char *data, int len ) = 0; |
---|
71 | char *title; |
---|
72 | unsigned long *found; |
---|
73 | unsigned long zero; |
---|
74 | unsigned long total; |
---|
75 | unsigned long empty; |
---|
76 | unsigned long min; |
---|
77 | unsigned long max; |
---|
78 | double stdev; |
---|
79 | unsigned long bittest[ BITTEST ]; |
---|
80 | unsigned long missed[ BITTEST ]; |
---|
81 | algorithm *next; |
---|
82 | algorithm( algorithm *last, char *new_title ); |
---|
83 | }; |
---|
84 | |
---|
85 | algorithm::algorithm( algorithm *last, char *new_title ) |
---|
86 | { |
---|
87 | zero = total = empty = min = max = 0; |
---|
88 | stdev = 0.0; |
---|
89 | for( int t = 0; t < BITTEST; t++ ) |
---|
90 | { |
---|
91 | bittest[t] = missed[t] = 0; |
---|
92 | } |
---|
93 | title = new_title; |
---|
94 | next = last; |
---|
95 | } |
---|
96 | |
---|
97 | //---------------------------------------------------------------------------------------------------- |
---|
98 | // |
---|
99 | // Standard CRC-16 |
---|
100 | // |
---|
101 | // http://sanity-free.org/134/standard_crc_16_in_csharp.html |
---|
102 | // |
---|
103 | |
---|
104 | static unsigned short crc16_table[256]; |
---|
105 | |
---|
106 | class crc16_algorithm : public algorithm |
---|
107 | { |
---|
108 | public: |
---|
109 | crc16_algorithm( algorithm *last ) : algorithm( last, (char *) "crc-16" ) |
---|
110 | { |
---|
111 | unsigned short value; |
---|
112 | unsigned short temp; |
---|
113 | unsigned short i; |
---|
114 | unsigned short j; |
---|
115 | |
---|
116 | for(i = 0; i < 256; ++i) |
---|
117 | { |
---|
118 | value = 0; |
---|
119 | temp = i; |
---|
120 | for(j = 0; j < 8; ++j) { |
---|
121 | if(((value ^ temp) & 0x0001) != 0) { |
---|
122 | value = (unsigned short)((value >> 1) ^ this->crc16_polynomial); |
---|
123 | }else { |
---|
124 | value >>= 1; |
---|
125 | } |
---|
126 | temp >>= 1; |
---|
127 | } |
---|
128 | crc16_table[i] = value; |
---|
129 | } |
---|
130 | } |
---|
131 | |
---|
132 | unsigned short checksum( unsigned char *data, int len ); |
---|
133 | |
---|
134 | private: |
---|
135 | static const unsigned short crc16_polynomial = 0xA001; |
---|
136 | }; |
---|
137 | |
---|
138 | unsigned short crc16_algorithm::checksum( unsigned char *data, int len ) |
---|
139 | { |
---|
140 | unsigned short crc = 0; |
---|
141 | int i; |
---|
142 | |
---|
143 | for(i = 0; i < len; ++i) |
---|
144 | { |
---|
145 | unsigned char index = (unsigned char)(crc ^ data[i]); |
---|
146 | crc = (unsigned short)((crc >> 8) ^ crc16_table[index]); |
---|
147 | } |
---|
148 | |
---|
149 | return( crc ); |
---|
150 | } |
---|
151 | |
---|
152 | //---------------------------------------------------------------------------------------------------- |
---|
153 | // |
---|
154 | // Basic checksum (just add up the bytes) |
---|
155 | // |
---|
156 | |
---|
157 | class basic_algorithm : public algorithm |
---|
158 | { |
---|
159 | public: |
---|
160 | unsigned short checksum( unsigned char *data, int len ); |
---|
161 | basic_algorithm( algorithm *last ) : algorithm( last, (char *) "basic" ) { }; |
---|
162 | }; |
---|
163 | |
---|
164 | unsigned short basic_algorithm::checksum( unsigned char *bbuff, int blen ) |
---|
165 | { |
---|
166 | unsigned short sum = 0; |
---|
167 | int i; |
---|
168 | for( i = 0; i < blen; i++ ) |
---|
169 | { |
---|
170 | sum += bbuff[ i ]; |
---|
171 | } |
---|
172 | return( sum ); |
---|
173 | } |
---|
174 | |
---|
175 | class fletcher16_algorithm : public algorithm |
---|
176 | { |
---|
177 | public: |
---|
178 | unsigned short checksum( unsigned char *data, int len ); |
---|
179 | fletcher16_algorithm( algorithm *last ) : algorithm( last, (char *) "f-16" ) { } |
---|
180 | }; |
---|
181 | |
---|
182 | unsigned short fletcher16_algorithm::checksum( unsigned char* data, int count ) |
---|
183 | { |
---|
184 | unsigned short sum1 = 0; |
---|
185 | unsigned short sum2 = 0; |
---|
186 | int index; |
---|
187 | |
---|
188 | for( index = 0; index < count; ++index ) |
---|
189 | { |
---|
190 | sum1 = (sum1 + data[index]) % 255; |
---|
191 | sum2 = (sum2 + sum1) % 255; |
---|
192 | } |
---|
193 | |
---|
194 | return (sum2 << 8) | sum1; |
---|
195 | } |
---|
196 | |
---|
197 | //---------------------------------------------------------------------------------------------------- |
---|
198 | // |
---|
199 | // Folded Fletcher's Checksum (what we use in the serial code, from the top of this file) |
---|
200 | // |
---|
201 | |
---|
202 | class folded_fletcher32_algorithm : public algorithm |
---|
203 | { |
---|
204 | public: |
---|
205 | unsigned short checksum( unsigned char *data, int len ); |
---|
206 | folded_fletcher32_algorithm( algorithm *last ) : algorithm( last, (char *) "fold-f-32" ) { } |
---|
207 | }; |
---|
208 | |
---|
209 | unsigned short folded_fletcher32_algorithm::checksum( unsigned char* data, int count ) |
---|
210 | { |
---|
211 | return( ::checksum( (unsigned short *) data, count/2 ) ); |
---|
212 | } |
---|
213 | |
---|
214 | //---------------------------------------------------------------------------------------------------- |
---|
215 | // |
---|
216 | // Test Driver and Support routines |
---|
217 | // |
---|
218 | |
---|
219 | void randomize_buff( unsigned char *bbuff, int blen ) |
---|
220 | { |
---|
221 | int i; |
---|
222 | for( i = 0; i < blen; i++ ) |
---|
223 | bbuff[i] = rand() % 255; |
---|
224 | } |
---|
225 | |
---|
226 | #define BBUFF_LENGTH 512 |
---|
227 | |
---|
228 | unsigned char bbuff[ BBUFF_LENGTH ]; |
---|
229 | |
---|
230 | int main( int argc, char *argv[] ) |
---|
231 | { |
---|
232 | algorithm *a, *algorithms; |
---|
233 | |
---|
234 | unsigned short c; |
---|
235 | |
---|
236 | double p; |
---|
237 | double average; |
---|
238 | |
---|
239 | unsigned long iterations; |
---|
240 | |
---|
241 | time_t now; |
---|
242 | |
---|
243 | algorithms = new folded_fletcher32_algorithm( NULL ); |
---|
244 | algorithms = new fletcher16_algorithm( algorithms ); |
---|
245 | algorithms = new crc16_algorithm( algorithms ); |
---|
246 | algorithms = new basic_algorithm( algorithms ); |
---|
247 | |
---|
248 | time( &now ); |
---|
249 | srand((unsigned int)now); |
---|
250 | |
---|
251 | if( argc != 2 ) |
---|
252 | { |
---|
253 | fprintf( stderr, "usage: checksum number_of_iterations\n" ); |
---|
254 | exit( 1 ); |
---|
255 | } |
---|
256 | else |
---|
257 | iterations = atol( argv[1] ); |
---|
258 | |
---|
259 | #define PRINTROW( E, F, G ) { printf( E ); for( a = algorithms; a; a = a->next ) printf( F, G ); printf( "\n" ); } |
---|
260 | |
---|
261 | printf( "\nnumber of iterations: %d\n\n", iterations ); |
---|
262 | PRINTROW( " ", "%10s ", a->title ); |
---|
263 | PRINTROW( "=======", "============", NULL ); |
---|
264 | |
---|
265 | for( a = algorithms; a; a = a->next ) |
---|
266 | { |
---|
267 | a->found = (unsigned long *) calloc( BUCKETS, sizeof(long) ); |
---|
268 | |
---|
269 | a->zero = (unsigned long) a->checksum( bbuff, BBUFF_LENGTH ); |
---|
270 | |
---|
271 | a->min = iterations+1; |
---|
272 | } |
---|
273 | |
---|
274 | printf( "\n" ); |
---|
275 | PRINTROW( "zero ", "%10d ", a->zero ); |
---|
276 | |
---|
277 | for( int t = 0; t < iterations; t++ ) |
---|
278 | { |
---|
279 | randomize_buff( bbuff, BBUFF_LENGTH ); |
---|
280 | |
---|
281 | for( a = algorithms; a; a = a->next ) |
---|
282 | a->found[ a->checksum( bbuff, BBUFF_LENGTH ) ]++; |
---|
283 | } |
---|
284 | |
---|
285 | average = iterations / 65536.0; |
---|
286 | |
---|
287 | for( int t = 0; t < 65536; t++ ) |
---|
288 | { |
---|
289 | for( a = algorithms; a; a = a->next ) |
---|
290 | { |
---|
291 | a->total += a->found[ t ]; |
---|
292 | if( !a->found[ t ] ) |
---|
293 | a->empty++; |
---|
294 | if( a->found[ t ] > a->max ) |
---|
295 | a->max = a->found[ t ]; |
---|
296 | if( a->found[ t ] < a->min ) |
---|
297 | a->min = a->found[ t ]; |
---|
298 | p = a->found[ t ] - average; |
---|
299 | a->stdev += p*p; |
---|
300 | } |
---|
301 | } |
---|
302 | |
---|
303 | p = 1.0 / (65536.0-1.0); |
---|
304 | for( a = algorithms; a; a = a->next ) |
---|
305 | { |
---|
306 | a->stdev = sqrt( p * a->stdev ); |
---|
307 | if( a->total != iterations ) |
---|
308 | fprintf( stderr, "Bad %s\n", a->title ); |
---|
309 | } |
---|
310 | |
---|
311 | printf( "\nchecksum distribution test:\n" ); |
---|
312 | PRINTROW( "empty ", "%10d ", a->empty ); |
---|
313 | PRINTROW( "min ", "%10d ", a->min ); |
---|
314 | PRINTROW( "max ", "%10d ", a->max ); |
---|
315 | PRINTROW( "stdev ", "%10.4lf ", a->stdev ); |
---|
316 | |
---|
317 | for( int t = 0; t < iterations; t++ ) |
---|
318 | { |
---|
319 | randomize_buff( bbuff, BBUFF_LENGTH ); |
---|
320 | |
---|
321 | for( int b = 0; b < BITTEST; b++ ) |
---|
322 | { |
---|
323 | for( a = algorithms; a; a = a->next ) |
---|
324 | { |
---|
325 | a->bittest[ b ] = (a->checksum)( bbuff, BBUFF_LENGTH ); |
---|
326 | } |
---|
327 | |
---|
328 | bbuff[ rand() % 512 ] ^= bit[ rand() % 8 ]; |
---|
329 | |
---|
330 | if( b > 0 ) |
---|
331 | { |
---|
332 | for( a = algorithms; a; a = a->next ) |
---|
333 | { |
---|
334 | if( a->bittest[ 0 ] == a->bittest[ b ] ) |
---|
335 | a->missed[ b ]++; |
---|
336 | } |
---|
337 | } |
---|
338 | } |
---|
339 | } |
---|
340 | |
---|
341 | printf( "\nbit change test:\n" ); |
---|
342 | for( int t = 1; t < BITTEST; t++ ) |
---|
343 | { |
---|
344 | printf( "%2d ", t ); |
---|
345 | for( a = algorithms; a; a = a->next ) |
---|
346 | printf( "%7d ", a->missed[ t ] ); |
---|
347 | printf( "\n" ); |
---|
348 | } |
---|
349 | } |
---|
350 | |
---|
351 | #endif |
---|
352 | |
---|
353 | |
---|
354 | |
---|
355 | |
---|