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

Last change on this file since 351 was 209, checked in by gregli@…, 13 years ago

Initial checkin for the Serial Server code, to be run on a host computer with a hard disk image file. Connected via a serial line, this provides the I/O for the serial port support in the XTIDE bios. At present, this is a Win32 command line program, run without parameters for usage information.

File size: 8.9 KB
Line 
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
26unsigned 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
65unsigned char bit[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
66
67class algorithm
68{
69public:
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
85algorithm::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
104static unsigned short crc16_table[256];
105
106class crc16_algorithm : public algorithm
107{
108public:
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
134private:
135 static const unsigned short crc16_polynomial = 0xA001;
136};
137
138unsigned 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
157class basic_algorithm : public algorithm
158{
159public:
160 unsigned short checksum( unsigned char *data, int len );
161 basic_algorithm( algorithm *last ) : algorithm( last, (char *) "basic" ) { };
162};
163
164unsigned 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
175class fletcher16_algorithm : public algorithm
176{
177public:
178 unsigned short checksum( unsigned char *data, int len );
179 fletcher16_algorithm( algorithm *last ) : algorithm( last, (char *) "f-16" ) { }
180};
181
182unsigned 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
202class folded_fletcher32_algorithm : public algorithm
203{
204public:
205 unsigned short checksum( unsigned char *data, int len );
206 folded_fletcher32_algorithm( algorithm *last ) : algorithm( last, (char *) "fold-f-32" ) { }
207};
208
209unsigned 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
219void 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
228unsigned char bbuff[ BBUFF_LENGTH ];
229
230int 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
Note: See TracBrowser for help on using the repository browser.