2 * Speed-optimized CRC32 using slicing-by-eight algorithm
4 * This uses only i386 instructions, but it is optimized for i686 and later
5 * (including e.g. Pentium II/III/IV, Athlon XP, and Core 2). For i586
6 * (e.g. Pentium), slicing-by-four would be better, and even the C version
7 * of slicing-by-eight built with gcc -march=i586 tends to be a little bit
8 * better than this. Very few probably run this code on i586 or older x86
9 * so this shouldn't be a problem in practice.
11 * Authors: Igor Pavlov (original version)
12 * Lasse Collin (AT&T syntax, PIC support, better portability)
14 * This file has been put into the public domain.
15 * You can do whatever you want with this file.
17 * This code needs lzma_crc32_table, which can be created using the
20 uint32_t lzma_crc32_table[8][256];
26 static const uint32_t poly32 = UINT32_C(0xEDB88320);
29 // static const uint32_t poly32 = UINT32_C(0x82F63B78);
32 // static const uint32_t poly32 = UINT32_C(0xEB31D82E);
34 for (size_t s = 0; s < 8; ++s) {
35 for (size_t b = 0; b < 256; ++b) {
36 uint32_t r = s == 0 ? b : lzma_crc32_table[s - 1][b];
38 for (size_t i = 0; i < 8; ++i) {
40 r = (r >> 1) ^ poly32;
45 lzma_crc32_table[s][b] = r;
50 * The prototype of the CRC32 function:
51 * extern uint32_t lzma_crc32(const uint8_t *buf, size_t size, uint32_t crc);
55 * On some systems, the functions need to be prefixed. The prefix is
56 * usually an underscore.
58 #ifndef __USER_LABEL_PREFIX__
59 # define __USER_LABEL_PREFIX__
61 #define MAKE_SYM_CAT(prefix, sym) prefix ## sym
62 #define MAKE_SYM(prefix, sym) MAKE_SYM_CAT(prefix, sym)
63 #define LZMA_CRC32 MAKE_SYM(__USER_LABEL_PREFIX__, lzma_crc32)
64 #define LZMA_CRC32_TABLE MAKE_SYM(__USER_LABEL_PREFIX__, lzma_crc32_table)
67 * Solaris assembler doesn't have .p2align, and Darwin uses .align
68 * differently than GNU/Linux and Solaris.
70 #if defined(__MACH__) || defined(__MSDOS__)
71 # define ALIGN(pow2, abs) .align pow2
73 # define ALIGN(pow2, abs) .align abs
79 #if !defined(__MACH__) && !defined(_WIN32) && !defined(__CYGWIN__) \
80 && !defined(__MSDOS__)
81 .type LZMA_CRC32, @function
90 * %edi size or buf + size
91 * %ebx lzma_crc32_table
100 movl 0x14(%esp), %esi /* buf */
101 movl 0x18(%esp), %edi /* size */
102 movl 0x1C(%esp), %eax /* crc */
105 * Store the address of lzma_crc32_table to %ebx. This is needed to
106 * get position-independent code (PIC).
108 * The PIC macro is defined by libtool, while __PIC__ is defined
109 * by GCC but only on some systems. Testing for both makes it simpler
110 * to test this code without libtool, and keeps the code working also
111 * when built with libtool but using something else than GCC.
113 #if !defined(PIC) && !defined(__PIC__)
115 movl $LZMA_CRC32_TABLE, %ebx
116 #elif defined(__MACH__)
120 leal .L_lzma_crc32_table$non_lazy_ptr-.L_pic(%ebx), %ebx
125 addl $_GLOBAL_OFFSET_TABLE_, %ebx
126 movl LZMA_CRC32_TABLE@GOT(%ebx), %ebx
129 /* Complement the initial value. */
135 * Check if there is enough input to use slicing-by-eight.
136 * We need 16 bytes, because the loop pre-reads eight bytes.
141 /* Check if we have reached alignment of eight bytes. */
145 /* Calculate CRC of the next input byte. */
151 xorl (%ebx, %ebp, 4), %eax
158 * If we get here, there's at least 16 bytes of aligned input
159 * available. Make %edi multiple of eight bytes. Store the possible
160 * remainder over the "size" variable in the argument stack.
162 movl %edi, 0x18(%esp)
164 subl %edi, 0x18(%esp)
167 * Let %edi be buf + size - 8 while running the main loop. This way
168 * we can compare for equality to determine when exit the loop.
173 /* Read in the first eight aligned bytes. */
179 movl 0x0C00(%ebx, %ebp, 4), %edx
181 xorl 0x0800(%ebx, %ebp, 4), %edx
185 xorl 0x0400(%ebx, %ebp, 4), %edx
187 xorl (%ebx, %ebp, 4), %edx
191 * Read the next four bytes, for which the CRC is calculated
192 * on the next interation of the loop.
196 xorl 0x1C00(%ebx, %ebp, 4), %edx
199 xorl 0x1800(%ebx, %ebp, 4), %edx
202 movl 0x1400(%ebx, %eax, 4), %eax
205 xorl 0x1000(%ebx, %ebp, 4), %eax
207 /* Check for end of aligned input. */
213 * Process the remaining eight bytes, which we have already
214 * copied to %ecx and %edx.
216 movl 0x0C00(%ebx, %ebp, 4), %edx
218 xorl 0x0800(%ebx, %ebp, 4), %edx
221 xorl 0x0400(%ebx, %ebp, 4), %edx
223 xorl (%ebx, %ebp, 4), %edx
226 xorl 0x1C00(%ebx, %ebp, 4), %edx
229 xorl 0x1800(%ebx, %ebp, 4), %edx
232 movl 0x1400(%ebx, %eax, 4), %eax
235 xorl 0x1000(%ebx, %ebp, 4), %eax
237 /* Copy the number of remaining bytes to %edi. */
238 movl 0x18(%esp), %edi
241 /* Check for end of input. */
245 /* Calculate CRC of the next input byte. */
251 xorl (%ebx, %ebp, 4), %eax
256 /* Complement the final value. */
265 #if defined(PIC) || defined(__PIC__)
272 #if defined(__MACH__) && (defined(PIC) || defined(__PIC__))
274 .section __IMPORT,__pointers,non_lazy_symbol_pointers
275 .L_lzma_crc32_table$non_lazy_ptr:
276 .indirect_symbol LZMA_CRC32_TABLE
279 #elif defined(_WIN32) || defined(__CYGWIN__)
281 /* This is equivalent of __declspec(dllexport). */
283 .ascii " -export:lzma_crc32"
286 #elif !defined(__MSDOS__)
288 .size LZMA_CRC32, .-LZMA_CRC32
292 * This is needed to support non-executable stack. It's ugly to
293 * use __linux__ here, but I don't know a way to detect when
294 * we are using GNU assembler.
296 #if defined(__ELF__) && defined(__linux__)
297 .section .note.GNU-stack,"",@progbits