1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file       crc32.c
4 /// \brief      CRC32 calculation
5 ///
6 /// Calculate the CRC32 using the slice-by-eight algorithm.
7 /// It is explained in this document:
8 /// http://www.intel.com/technology/comms/perfnet/download/CRC_generators.pdf
9 /// The code in this file is not the same as in Intel's paper, but
10 /// the basic principle is identical.
11 //
12 //  Author:     Lasse Collin
13 //
14 //  This file has been put into the public domain.
15 //  You can do whatever you want with this file.
16 //
17 ///////////////////////////////////////////////////////////////////////////////
18 
19 #include "check.h"
20 #include "crc_macros.h"
21 
22 
23 // If you make any changes, do some benchmarking! Seemingly unrelated
24 // changes can very easily ruin the performance (and very probably is
25 // very compiler dependent).
26 extern LZMA_API(uint32_t)
27 lzma_crc32(const uint8_t *buf, size_t size, uint32_t crc)
28 {
29 	crc = ~crc;
30 
31 #ifdef WORDS_BIGENDIAN
32 	crc = bswap32(crc);
33 #endif
34 
35 	if (size > 8) {
36 		// Fix the alignment, if needed. The if statement above
37 		// ensures that this won't read past the end of buf[].
38 		while ((uintptr_t)(buf) & 7) {
39 			crc = lzma_crc32_table[0][*buf++ ^ A(crc)] ^ S8(crc);
40 			--size;
41 		}
42 
43 		// Calculate the position where to stop.
44 		const uint8_t *const limit = buf + (size & ~(size_t)(7));
45 
46 		// Calculate how many bytes must be calculated separately
47 		// before returning the result.
48 		size &= (size_t)(7);
49 
50 		// Calculate the CRC32 using the slice-by-eight algorithm.
51 		while (buf < limit) {
52 			crc ^= aligned_read32ne(buf);
53 			buf += 4;
54 
55 			crc = lzma_crc32_table[7][A(crc)]
56 			    ^ lzma_crc32_table[6][B(crc)]
57 			    ^ lzma_crc32_table[5][C(crc)]
58 			    ^ lzma_crc32_table[4][D(crc)];
59 
60 			const uint32_t tmp = aligned_read32ne(buf);
61 			buf += 4;
62 
63 			// At least with some compilers, it is critical for
64 			// performance, that the crc variable is XORed
65 			// between the two table-lookup pairs.
66 			crc = lzma_crc32_table[3][A(tmp)]
67 			    ^ lzma_crc32_table[2][B(tmp)]
68 			    ^ crc
69 			    ^ lzma_crc32_table[1][C(tmp)]
70 			    ^ lzma_crc32_table[0][D(tmp)];
71 		}
72 	}
73 
74 	while (size-- != 0)
75 		crc = lzma_crc32_table[0][*buf++ ^ A(crc)] ^ S8(crc);
76 
77 #ifdef WORDS_BIGENDIAN
78 	crc = bswap32(crc);
79 #endif
80 
81 	return ~crc;
82 }
83