source: xtideuniversalbios/trunk/Serial_Server/library/Checksum.cpp@ 582

Last change on this file since 582 was 526, checked in by krille_n_@…, 12 years ago

Changes:

  • Update of the copyright notices to include the year 2013.
File size: 9.6 KB
Line 
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-2013 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
43unsigned 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
82unsigned char bit[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
83
84class algorithm
85{
86public:
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
102algorithm::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
121static unsigned short crc16_table[256];
122
123class crc16_algorithm : public algorithm
124{
125public:
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
151private:
152 static const unsigned short crc16_polynomial = 0xA001;
153};
154
155unsigned 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
174class basic_algorithm : public algorithm
175{
176public:
177 unsigned short checksum( unsigned char *data, int len );
178 basic_algorithm( algorithm *last ) : algorithm( last, (char *) "basic" ) { };
179};
180
181unsigned 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
192class fletcher16_algorithm : public algorithm
193{
194public:
195 unsigned short checksum( unsigned char *data, int len );
196 fletcher16_algorithm( algorithm *last ) : algorithm( last, (char *) "f-16" ) { }
197};
198
199unsigned 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
219class folded_fletcher32_algorithm : public algorithm
220{
221public:
222 unsigned short checksum( unsigned char *data, int len );
223 folded_fletcher32_algorithm( algorithm *last ) : algorithm( last, (char *) "fold-f-32" ) { }
224};
225
226unsigned 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
236void 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
245unsigned char bbuff[ BBUFF_LENGTH ];
246
247int 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
Note: See TracBrowser for help on using the repository browser.