[209] | 1 | //====================================================================== |
---|
| 2 | // |
---|
| 3 | // Project: XTIDE Universal BIOS, Serial Port Server |
---|
| 4 | // |
---|
[589] | 5 | // File: Checksum.cpp - Checksum function and test routines |
---|
[376] | 6 | |
---|
[209] | 7 | // |
---|
[526] | 8 | // XTIDE Universal BIOS and Associated Tools |
---|
| 9 | // Copyright (C) 2009-2010 by Tomi Tilli, 2011-2013 by XTIDE Universal BIOS Team. |
---|
[376] | 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. |
---|
[526] | 15 | // |
---|
[376] | 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 |
---|
[526] | 19 | // GNU General Public License for more details. |
---|
[376] | 20 | // Visit http://www.gnu.org/licenses/old-licenses/gpl-2.0.html |
---|
| 21 | // |
---|
| 22 | |
---|
| 23 | // |
---|
[526] | 24 | // This file implements Fletcher's Checksum. The serial code uses this checksum, as it is very quick |
---|
[209] | 25 | // to calculate in assembly and offers reasonable error detection. |
---|
| 26 | // For more information, see http://en.wikipedia.org/wiki/Fletcher%27s_checksum. |
---|
| 27 | // |
---|
[526] | 28 | // Since it is faster in 8088 assembly code to deal with 16-bit quantities than 8-bit quantities, |
---|
[209] | 29 | // Fletcher's Checksum has been modified to calculate the 32-bit checksum, and then "fold" the result into a |
---|
[526] | 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 |
---|
[209] | 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 |
---|
[526] | 37 | // some statistical tests comparing various checksum algorithms with random 512-byte sectors and various |
---|
[209] | 38 | // levels of errors introduced. |
---|
| 39 | // |
---|
| 40 | |
---|
[589] | 41 | #include "Library.h" |
---|
[209] | 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 | |
---|
[526] | 60 | // Although tempting to use, for its simplicity and size/speed in assembly, the following folding |
---|
[209] | 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 | //==================================================================================================== |
---|
[526] | 70 | // |
---|
[209] | 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 | |
---|
[526] | 84 | class algorithm |
---|
[209] | 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 | //---------------------------------------------------------------------------------------------------- |
---|
[526] | 115 | // |
---|
[209] | 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 | |
---|
[526] | 133 | for(i = 0; i < 256; ++i) |
---|
[209] | 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 | |
---|
[526] | 149 | unsigned short checksum( unsigned char *data, int len ); |
---|
[209] | 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 | |
---|
[526] | 160 | for(i = 0; i < len; ++i) |
---|
[209] | 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 | //---------------------------------------------------------------------------------------------------- |
---|
[526] | 170 | // |
---|
[209] | 171 | // Basic checksum (just add up the bytes) |
---|
| 172 | // |
---|
| 173 | |
---|
| 174 | class basic_algorithm : public algorithm |
---|
| 175 | { |
---|
| 176 | public: |
---|
[526] | 177 | unsigned short checksum( unsigned char *data, int len ); |
---|
[209] | 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: |
---|
[526] | 195 | unsigned short checksum( unsigned char *data, int len ); |
---|
[209] | 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 | //---------------------------------------------------------------------------------------------------- |
---|
[526] | 215 | // |
---|
[209] | 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: |
---|
[526] | 222 | unsigned short checksum( unsigned char *data, int len ); |
---|
[209] | 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 | //---------------------------------------------------------------------------------------------------- |
---|
[526] | 232 | // |
---|
[209] | 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) ); |
---|
[526] | 285 | |
---|
[209] | 286 | a->zero = (unsigned long) a->checksum( bbuff, BBUFF_LENGTH ); |
---|
| 287 | |
---|
| 288 | a->min = iterations+1; |
---|
| 289 | } |
---|
[526] | 290 | |
---|
[209] | 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 | |
---|
[592] | 345 | bbuff[ rand() & 511 ] ^= bit[ rand() & 7 ]; |
---|
[526] | 346 | |
---|
[209] | 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 | } |
---|
[526] | 356 | } |
---|
[209] | 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 | |
---|