RZ

001: /****** AlgoBytewiseGF.hh / GF(2**32) Finite Field Arithmetic ******/
002: 
003: #ifndef _AlgoBytewiseGF_HH
004: #define _AlgoBytewiseGF_HH 1
005: 
006: #include "AlgoGF.hh"
007: 
008: /****** ******* ******* ******* ******* ******* ******* ******* ******* ******/ 
009: 
010: namespace Bytewise {
011:     struct Checksum32 {
012:         unsigned int const buflen;
013:         unsigned int checkroll[256]; // << 32 ( modulo m )
014: 
015:         Checksum32(int mod32, unsigned int nbits)
016:         : buflen(nbits >> 3)
017:         {
018:             for (unsigned int b = 0; b < 256; ++b) {
019:                 int acc = b << 24;
020:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
021:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
022:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
023:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
024:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
025:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
026:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
027:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
028:                 checkroll[b] = acc;
029:             }
030:         }
031: 
032:         unsigned int checksum32(char const buffer[])
033:         const {
034:             unsigned int acc = 0;
035:             for (unsigned int i = 0; i < buflen; ++i)
036:                 acc = checkroll[acc>>24] ^ acc<<8 ^ (unsigned char)buffer[i];
037:             return acc;
038:         }
039: 
040:         unsigned int checksum32(
041:             char const buffer0[], unsigned int buflen0, char const buffer1[])
042:         const {
043:             if (buflen <= buflen0) return checksum32(buffer0);
044:             unsigned int acc = 0;
045:             for (unsigned int i = 0; i < buflen0; ++i)
046:                 acc = checkroll[acc>>24] ^ acc<<8 ^ (unsigned char)buffer0[i];
047:             for (unsigned int i = 0, iend = buflen - buflen0; i < iend; ++i)
048:                 acc = checkroll[acc>>24] ^ acc<<8 ^ (unsigned char)buffer1[i];
049:             return acc;
050:         }
051: 
052:         void accumulate(
053:             char const buffer[], unsigned int buflen, unsigned int &acc)
054:         const {
055:             for (unsigned int i = 0; i < buflen; ++i)
056:                 acc = checkroll[acc>>24] ^ acc<<8 ^ (unsigned char)buffer[i];
057:         }
058:     };
059: 
060:     struct Rollingsum : Checksum32 {
061:         unsigned int checkouts[256];
062: 
063:         Rollingsum(int mod32, unsigned int nbits)
064:         : Checksum32(mod32, nbits)
065:         {
066:             int advance = GF::GFbinary32(mod32).exponentiate(2, nbits);
067:             for (unsigned int b = 0; b < 256; ++b) {
068:                 signed char out = b;
069:                 int acc = 0;
070:                 if (out < 0) acc ^= advance; out <<= 1;
071:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
072:                 if (out < 0) acc ^= advance; out <<= 1;       
073:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
074:                 if (out < 0) acc ^= advance; out <<= 1;       
075:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
076:                 if (out < 0) acc ^= advance; out <<= 1;       
077:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
078:                 if (out < 0) acc ^= advance; out <<= 1;       
079:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
080:                 if (out < 0) acc ^= advance; out <<= 1;       
081:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
082:                 if (out < 0) acc ^= advance; out <<= 1;       
083:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
084:                 if (out < 0) acc ^= advance; out <<= 1;       
085:                 checkouts[b] = acc;
086:             }
087:         }
088: 
089:         unsigned int rollingsum(unsigned int chk, char out, char in)
090:         const {
091:             return checkroll[chk>>24]
092:                 ^ chk<<8 ^ checkouts[(unsigned char)out] ^ (unsigned char)in;
093:         }
094:     };
095: 
096:     // Checksum32 const a(555777555, 65536);
097:     // Checksum32 const b(777222777, 65536);
098:     // Rollingsum const c(999555999, 65536);
099:     
100:     // Bytewise::a.checksum32(buf);
101:     // Bytewise::b.checksum32(buf);
102:     // Bytewise::c.checksum32(buf);
103:     // Bytewise::c.rollingsum(chk, out, in);
104: }
105: 
106: #endif /****** AlgoBytewiseGF.hh / GF(2**32) Finite Field Arithmetic ******/