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