|
NCBI Home IEB Home C++ Toolkit docs C Toolkit source browser C Toolkit source browser (2) |
NCBI C++ Toolkit Cross ReferenceC++/src/util/checksum.cpp |
source navigation diff markup identifier search freetext search file search |
1 /* $Id: checksum.cpp 103491 2007-05-04 17:18:18Z kazimird $
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government have not placed any restriction on its use or reproduction.
13 *
14 * Although all reasonable efforts have been taken to ensure the accuracy
15 * and reliability of the software and data, the NLM and the U.S.
16 * Government do not and cannot warrant the performance or results that
17 * may be obtained by using this software or data. The NLM and the U.S.
18 * Government disclaim all warranties, express or implied, including
19 * warranties of performance, merchantability or fitness for any particular
20 * purpose.
21 *
22 * Please cite the author in any work or product based on this material.
23 *
24 * ===========================================================================
25 *
26 * Author: Eugene Vasilchenko
27 *
28 * File Description: Checksum (CRC32 or MD5) calculation class
29 *
30 */
31
32 #include <ncbi_pch.hpp>
33 #include <corelib/ncbistd.hpp>
34 #include <util/checksum.hpp>
35 #include <util/md5.hpp>
36
37
38 BEGIN_NCBI_SCOPE
39
40 #define NCBI_USE_PRECOMPILED_CRC32_TABLES 1
41
42 // sx_Start must begin with "/* O" (see ValidChecksumLine() in checksum.inl)
43 static const char sx_Start[] = "/* Original file checksum: ";
44 static const char sx_End[] = " */";
45 static const char sx_LineCount[] = "lines: ";
46 static const char sx_CharCount[] = "chars: ";
47
48 #ifdef NCBI_USE_PRECOMPILED_CRC32_TABLES
49 inline void s_InitTableCRC32() {}
50 inline void s_InitTableCRC32ZIP() {}
51 #else
52 static Uint4 s_CalcByteCRC32(size_t byte);
53 static Uint4 s_CalcByteCRC32ZIP(size_t byte);
54 static void s_FillMultiBitsCRC(Uint4* table, size_t size);
55 static void s_InitTableCRC32();
56 static void s_InitTableCRC32ZIP();
57 #endif
58 static Uint4 s_UpdateCRC32(Uint4 checksum, const char* str, size_t length);
59 static Uint4 s_UpdateCRC32ZIP(Uint4 checksum, const char* str, size_t length);
60 static Uint4 s_UpdateAdler32(Uint4 sum, const char* data, size_t len);
61 static void s_PrintTable(CNcbiOstream& out, const char* name,
62 const Uint4* table, size_t size);
63
64 CChecksum::CChecksum(EMethod method)
65 : m_LineCount(0), m_CharCount(0), m_Method(method)
66 {
67 switch ( GetMethod() ) {
68 case eCRC32:
69 s_InitTableCRC32();
70 m_Checksum.m_CRC32 = 0;
71 break;
72 case eCRC32ZIP:
73 s_InitTableCRC32ZIP();
74 m_Checksum.m_CRC32 = ~0;
75 break;
76 case eMD5:
77 m_Checksum.m_MD5 = new CMD5;
78 break;
79 case eAdler32:
80 m_Checksum.m_CRC32 = 1;
81 break;
82 default:
83 break;
84 }
85 }
86
87
88 CChecksum::CChecksum(const CChecksum& cks)
89 : m_LineCount(cks.m_LineCount), m_CharCount(cks.m_CharCount),
90 m_Method(cks.m_Method)
91 {
92 switch ( GetMethod() ) {
93 case eCRC32:
94 case eCRC32ZIP:
95 case eAdler32:
96 m_Checksum.m_CRC32 = cks.m_Checksum.m_CRC32;
97 break;
98 case eMD5:
99 m_Checksum.m_MD5 = new CMD5(*cks.m_Checksum.m_MD5);
100 break;
101 default:
102 break;
103 }
104 }
105
106
107 CChecksum::~CChecksum()
108 {
109 x_Free();
110 }
111
112
113 void CChecksum::x_Free()
114 {
115 switch ( GetMethod() ) {
116 case eMD5:
117 delete m_Checksum.m_MD5;
118 m_Checksum.m_MD5 = 0;
119 break;
120 default:
121 break;
122 }
123 }
124
125
126 CChecksum& CChecksum::operator= (const CChecksum& cks)
127 {
128 x_Free();
129
130 m_LineCount = cks.m_LineCount;
131 m_CharCount = cks.m_CharCount;
132 m_Method = cks.m_Method;
133
134 switch ( GetMethod() ) {
135 case eCRC32:
136 case eCRC32ZIP:
137 case eAdler32:
138 m_Checksum.m_CRC32 = cks.m_Checksum.m_CRC32;
139 break;
140 case eMD5:
141 m_Checksum.m_MD5 = new CMD5(*cks.m_Checksum.m_MD5);
142 break;
143 default:
144 break;
145 }
146 return *this;
147 }
148
149
150 void CChecksum::Reset()
151 {
152 m_LineCount = 0;
153 m_CharCount = 0;
154 switch ( GetMethod() ) {
155 case eCRC32:
156 m_Checksum.m_CRC32 = 0;
157 break;
158 case eCRC32ZIP:
159 m_Checksum.m_CRC32 = ~0;
160 break;
161 case eMD5:
162 delete m_Checksum.m_MD5;
163 m_Checksum.m_MD5 = new CMD5();
164 break;
165 case eAdler32:
166 m_Checksum.m_CRC32 = 1;
167 break;
168 default:
169 break;
170 }
171 }
172
173
174 Uint4 CChecksum::GetChecksum() const
175 {
176 switch ( GetMethod() ) {
177 case eCRC32:
178 return m_Checksum.m_CRC32;
179 case eCRC32ZIP:
180 return ~m_Checksum.m_CRC32;
181 case eAdler32:
182 return m_Checksum.m_CRC32;
183 default:
184 _ASSERT(0);
185 return 0;
186 }
187 }
188
189 void CChecksum::GetMD5Digest(unsigned char digest[16]) const
190 {
191 _ASSERT(GetMethod() == eMD5);
192 m_Checksum.m_MD5->Finalize(digest);
193 }
194
195 CNcbiOstream& CChecksum::WriteChecksum(CNcbiOstream& out) const
196 {
197 if ( !Valid() ) {
198 return out;
199 }
200 out << sx_Start <<
201 sx_LineCount << m_LineCount << ", " <<
202 sx_CharCount << m_CharCount << ", ";
203 WriteChecksumData(out);
204 return out << sx_End << '\n';
205 }
206
207
208 bool CChecksum::ValidChecksumLineLong(const char* line, size_t length) const
209 {
210 if ( !Valid() ) {
211 return false;
212 }
213 CNcbiOstrstream buffer;
214 WriteChecksum(buffer);
215 size_t bufferLength = buffer.pcount() - 1; // do not include '\n'
216 if ( bufferLength != length ) {
217 return false;
218 }
219 const char* bufferPtr = buffer.str();
220 buffer.freeze(false);
221 return memcmp(line, bufferPtr, length) == 0;
222 }
223
224
225 CNcbiOstream& CChecksum::WriteChecksumData(CNcbiOstream& out) const
226 {
227 switch ( GetMethod() ) {
228 case eCRC32:
229 case eCRC32ZIP:
230 return out << "CRC32: " << hex << setprecision(8)
231 << GetChecksum();
232 case eMD5:
233 return out << "MD5: " << m_Checksum.m_MD5->GetHexSum();
234 case eAdler32:
235 return out << "Adler32: " << hex << setprecision(8)
236 << GetChecksum();
237 default:
238 return out << "none";
239 }
240 }
241
242
243 void CChecksum::x_Update(const char* str, size_t count)
244 {
245 switch ( GetMethod() ) {
246 case eCRC32:
247 m_Checksum.m_CRC32 = s_UpdateCRC32(m_Checksum.m_CRC32, str, count);
248 break;
249 case eCRC32ZIP:
250 m_Checksum.m_CRC32 = s_UpdateCRC32ZIP(m_Checksum.m_CRC32, str, count);
251 break;
252 case eAdler32:
253 m_Checksum.m_CRC32 = s_UpdateAdler32(m_Checksum.m_CRC32, str, count);
254 break;
255 case eMD5:
256 m_Checksum.m_MD5->Update(str, count);
257 break;
258 default:
259 break;
260 }
261 }
262
263
264 void CChecksum::NextLine(void)
265 {
266 char eol = '\n';
267 x_Update(&eol, 1);
268 ++m_LineCount;
269 }
270
271
272 CChecksum ComputeFileChecksum(const string& path, CChecksum::EMethod method)
273 {
274 CNcbiIfstream input(path.c_str(), IOS_BASE::in | IOS_BASE::binary);
275 CChecksum cks(method);
276
277 return ComputeFileChecksum(path, cks);
278 }
279
280
281 CChecksum& ComputeFileChecksum(const string& path,
282 CChecksum& checksum)
283 {
284 CNcbiIfstream input(path.c_str(), IOS_BASE::in | IOS_BASE::binary);
285 if ( !input.is_open() ) {
286 return checksum;
287 }
288
289 while ( !input.eof() ) {
290 char buf[1024*4];
291 input.read(buf, sizeof(buf));
292 size_t count = input.gcount();
293 if ( count ) {
294 checksum.AddChars(buf, count);
295 }
296 }
297 input.close();
298 return checksum;
299
300 }
301
302
303 void CChecksum::InitTables(void)
304 {
305 s_InitTableCRC32();
306 s_InitTableCRC32ZIP();
307 }
308
309
310 static void s_PrintTable(CNcbiOstream& out, const char* name,
311 const Uint4* table, size_t size)
312 {
313 const size_t kLineSize = 4;
314 out << "static Uint4 " << name << "[" << size << "] = {";
315 for ( size_t i = 0; i < size; ++i ) {
316 if ( i != 0 ) {
317 out << ',';
318 }
319 if ( i % kLineSize == 0 ) {
320 out << "\n ";
321 }
322 else {
323 out << ' ';
324 }
325 out << "0x" << hex << setw(8) << setfill('0') << table[i];
326 }
327 out << dec << "\n};\n" << endl;
328 }
329
330
331 static const size_t kCRC32Size = 256;
332 #ifdef NCBI_USE_PRECOMPILED_CRC32_TABLES
333 static Uint4 s_CRC32Table[256] = {
334 0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,
335 0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,
336 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
337 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
338 0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9,
339 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
340 0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011,
341 0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd,
342 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
343 0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,
344 0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81,
345 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
346 0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49,
347 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
348 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
349 0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d,
350 0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae,
351 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
352 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
353 0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,
354 0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
355 0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02,
356 0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066,
357 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
358 0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e,
359 0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692,
360 0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
361 0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a,
362 0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
363 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
364 0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686,
365 0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a,
366 0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
367 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
368 0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f,
369 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
370 0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47,
371 0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b,
372 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
373 0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,
374 0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7,
375 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
376 0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f,
377 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
378 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
379 0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b,
380 0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f,
381 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
382 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
383 0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,
384 0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
385 0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24,
386 0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30,
387 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
388 0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088,
389 0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654,
390 0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
391 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c,
392 0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
393 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
394 0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0,
395 0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c,
396 0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
397 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
398 };
399
400 static Uint4 s_CRC32ZIPTable[256] = {
401 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
402 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
403 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
404 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
405 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
406 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
407 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
408 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
409 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
410 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
411 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
412 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
413 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
414 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
415 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
416 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
417 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
418 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
419 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
420 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
421 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
422 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
423 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
424 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
425 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
426 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
427 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
428 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
429 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
430 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
431 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
432 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
433 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
434 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
435 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
436 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
437 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
438 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
439 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
440 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
441 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
442 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
443 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
444 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
445 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
446 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
447 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
448 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
449 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
450 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
451 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
452 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
453 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
454 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
455 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
456 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
457 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
458 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
459 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
460 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
461 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
462 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
463 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
464 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
465 };
466
467 #else
468 static Uint4 s_CRC32Table[kCRC32Size];
469 static Uint4 s_CRC32ZIPTable[kCRC32Size];
470
471 /////////////////////////////////////////////////////////////////////////////
472 // Implementation of CRC32 algorithm.
473 /////////////////////////////////////////////////////////////////////////////
474 //
475 // This code assumes that an unsigned is at least 32 bits wide and
476 // that the predefined type char occupies one 8-bit byte of storage.
477
478 // The polynomial used is
479 // x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+x^0
480 #define CRC32_POLYNOM 0x04c11db7
481 #define CRC32ZIP_POLYNOM 0xedb88320
482
483 // CRC32 is linear meaning that for any texts t1 & t2:
484 // CRC32[t1 XOR t2] = CRC32[t1] XOR CRC32[t2].
485 // This allows to speed up calculation of CRC32 tables by first
486 // calculating CRC32 for bytes with only one bit set,
487 // and then xoring all CRC32 of lowest bit and CRC32 of remaining bits
488 // to get CRC32 of whole number.
489 // First part is done by calling s_CalcByteCRC32 or s_CalcByteCRC32ZIP for
490 // each bit.
491 // Second pass is universal for any CRC32 and is performed by function
492 // s_FillMultiBitsCRC().
493
494 Uint4 s_CalcByteCRC32(size_t byte)
495 {
496 Uint4 byteCRC = byte << 24;
497 for ( int j = 0; j < 8; ++j ) {
498 if ( byteCRC & 0x80000000L )
499 byteCRC = (byteCRC << 1) ^ CRC32_POLYNOM;
500 else
501 byteCRC = (byteCRC << 1);
502 }
503 return byteCRC;
504 }
505
506 Uint4 s_CalcByteCRC32ZIP(size_t byte)
507 {
508 Uint4 byteCRC = byte;
509 for ( int j = 0; j < 8; ++j ) {
510 if ( byteCRC & 1 )
511 byteCRC = (byteCRC >> 1) ^ CRC32ZIP_POLYNOM;
512 else
513 byteCRC = (byteCRC >> 1);
514 }
515 return byteCRC;
516 }
517
518 void s_FillMultiBitsCRC(Uint4* table, size_t size)
519 {
520 // Preconditions:
521 // Entries at one-bit indexes (1<<k), are calculated.
522 for ( size_t i = 0; i < size; ++i ) { // order is significant
523 // Split bits of i into two parts:
524 // lobit contains lowest bit set, or zero if no bits are set,
525 // hibits contains all other bits.
526 size_t hibits = i & (i-1);
527 size_t lobit = i & ~(i-1);
528 // Because of:
529 // 1. i = lobit ^ hibits
530 // 2. lobit <= i
531 // 3. hibits <= i
532 // we can calculate entry at i by xoring entries at lobit and hibits
533 // There are 3 possible cases:
534 // A. i = 0
535 // In this case lobit = 0 and hibits = 0.
536 // As a result table[0] will become 0, which is correct for CRC.
537 // B. i = 1<<k
538 // In this case lobit = i, and hibits = 0.
539 // table[i] will become table[i] ^ table[0].
540 // Because table[0] is 0 (see case A above),
541 // table[i] will not change and will preserve precalculated value
542 // (see Preconditions above).
543 // C. all other i
544 // In this case lobit < i, and hibits < i
545 // It means the entries at lobit and hibits are calculated already
546 // because of the order of iteration by i.
547 table[i] = table[lobit] ^ table[hibits];
548 }
549 }
550
551 void s_InitTableCRC32(void)
552 {
553 // check the last element to make sure we minimize chances of races
554 // in MT programs.
555 if ( s_CRC32Table[kCRC32Size-1] == 0 ) {
556 // Initialize CRC32 for bytes with only one bit set
557 for ( size_t i = 1; i < kCRC32Size; i <<= 1 ) {
558 s_CRC32Table[i] = s_CalcByteCRC32(i);
559 }
560 // Fill the rest of table
561 s_FillMultiBitsCRC(s_CRC32Table, kCRC32Size);
562 }
563 }
564
565
566 void s_InitTableCRC32ZIP(void)
567 {
568 // check the last element to make sure we minimize chances of races
569 // in MT programs.
570 if ( s_CRC32ZIPTable[kCRC32Size-1] == 0 ) {
571 // Initialize CRC32 for bytes with only one bit set
572 for ( size_t i = 1; i < kCRC32Size; i <<= 1 ) {
573 s_CRC32ZIPTable[i] = s_CalcByteCRC32ZIP(i);
574 }
575 // Fill the rest of table
576 s_FillMultiBitsCRC(s_CRC32ZIPTable, kCRC32Size);
577 }
578 }
579 #endif
580
581 Uint4 s_UpdateCRC32(Uint4 checksum, const char *str, size_t count)
582 {
583 for ( size_t j = 0; j < count; ++j ) {
584 size_t tableIndex = ((checksum >> 24) ^ *str++) & 0xff;
585 checksum = (checksum << 8) ^ s_CRC32Table[tableIndex];
586 }
587 return checksum;
588 }
589
590
591 Uint4 s_UpdateCRC32ZIP(Uint4 checksum, const char *str, size_t count)
592 {
593 for ( size_t j = 0; j < count; ++j ) {
594 size_t tableIndex = (checksum ^ *str++) & 0xff;
595 checksum = (checksum >> 8) ^ s_CRC32ZIPTable[tableIndex];
596 }
597 return checksum;
598 }
599
600
601 Uint4 s_UpdateAdler32(Uint4 sum, const char* data, size_t len)
602 {
603 const Uint4 MOD_ADLER = 65521;
604
605 Uint4 a = sum & 0xffff, b = sum >> 16;
606
607 while (len) {
608 size_t tlen = len > 5550u ? 5550u : len;
609 len -= tlen;
610 do {
611 a += Uint1(*data++);
612 b += a;
613 } while (--tlen);
614 a = (a & 0xffff) + (a >> 16) * (65536-MOD_ADLER);
615 b = (b & 0xffff) + (b >> 16) * (65536-MOD_ADLER);
616 }
617 // It can be shown that a <= 0x1013a here, so a single subtract will do.
618 if (a >= MOD_ADLER)
619 a -= MOD_ADLER;
620 // It can be shown that b can reach 0xffef1 here.
621 b = (b & 0xffff) + (b >> 16) * (65536-MOD_ADLER);
622 if (b >= MOD_ADLER)
623 b -= MOD_ADLER;
624 return (b << 16) | a;
625 }
626
627 void CChecksum::PrintTables(CNcbiOstream& out)
628 {
629 InitTables();
630 s_PrintTable(out, "s_CRC32Table", s_CRC32Table, kCRC32Size);
631 s_PrintTable(out, "s_CRC32ZIPTable", s_CRC32ZIPTable, kCRC32Size);
632 }
633
634
635 END_NCBI_SCOPE
636 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |