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

Last change on this file since 376 was 376, checked in by gregli@…, 12 years ago

WIDE checkin... Added copyright and license information to sorce files, as per the GPL instructions for usage.

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-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
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.