1/* 2 * Speed-optimized CRC32 using slicing-by-eight algorithm 3 * 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. 10 * 11 * Authors: Igor Pavlov (original version) 12 * Lasse Collin (AT&T syntax, PIC support, better portability) 13 * 14 * This file has been put into the public domain. 15 * You can do whatever you want with this file. 16 * 17 * This code needs lzma_crc32_table, which can be created using the 18 * following C code: 19 20uint32_t lzma_crc32_table[8][256]; 21 22void 23init_table(void) 24{ 25 // IEEE-802.3 26 static const uint32_t poly32 = UINT32_C(0xEDB88320); 27 28 // Castagnoli 29 // static const uint32_t poly32 = UINT32_C(0x82F63B78); 30 31 // Koopman 32 // static const uint32_t poly32 = UINT32_C(0xEB31D82E); 33 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]; 37 38 for (size_t i = 0; i < 8; ++i) { 39 if (r & 1) 40 r = (r >> 1) ^ poly32; 41 else 42 r >>= 1; 43 } 44 45 lzma_crc32_table[s][b] = r; 46 } 47 } 48} 49 50 * The prototype of the CRC32 function: 51 * extern uint32_t lzma_crc32(const uint8_t *buf, size_t size, uint32_t crc); 52 */ 53 54/* 55 * On some systems, the functions need to be prefixed. The prefix is 56 * usually an underscore. 57 */ 58#ifndef __USER_LABEL_PREFIX__ 59# define __USER_LABEL_PREFIX__ 60#endif 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) 65 66/* 67 * Solaris assembler doesn't have .p2align, and Darwin uses .align 68 * differently than GNU/Linux and Solaris. 69 */ 70#if defined(__APPLE__) || defined(__MSDOS__) 71# define ALIGN(pow2, abs) .align pow2 72#else 73# define ALIGN(pow2, abs) .align abs 74#endif 75 76 .text 77 .globl LZMA_CRC32 78 79#if !defined(__APPLE__) && !defined(_WIN32) && !defined(__CYGWIN__) \ 80 && !defined(__MSDOS__) 81 .type LZMA_CRC32, @function 82#endif 83 84 ALIGN(4, 16) 85LZMA_CRC32: 86 /* 87 * Register usage: 88 * %eax crc 89 * %esi buf 90 * %edi size or buf + size 91 * %ebx lzma_crc32_table 92 * %ebp Table index 93 * %ecx Temporary 94 * %edx Temporary 95 */ 96 pushl %ebx 97 pushl %esi 98 pushl %edi 99 pushl %ebp 100 movl 0x14(%esp), %esi /* buf */ 101 movl 0x18(%esp), %edi /* size */ 102 movl 0x1C(%esp), %eax /* crc */ 103 104 /* 105 * Store the address of lzma_crc32_table to %ebx. This is needed to 106 * get position-independent code (PIC). 107 * 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. 112 * 113 * I understood that libtool may define PIC on Windows even though 114 * the code in Windows DLLs is not PIC in sense that it is in ELF 115 * binaries, so we need a separate check to always use the non-PIC 116 * code on Windows. 117 */ 118#if (!defined(PIC) && !defined(__PIC__)) \ 119 || (defined(_WIN32) || defined(__CYGWIN__)) 120 /* Not PIC */ 121 movl $ LZMA_CRC32_TABLE, %ebx 122#elif defined(__APPLE__) 123 /* Mach-O */ 124 call .L_get_pc 125.L_pic: 126 leal .L_lzma_crc32_table$non_lazy_ptr-.L_pic(%ebx), %ebx 127 movl (%ebx), %ebx 128#else 129 /* ELF */ 130 call .L_get_pc 131 addl $_GLOBAL_OFFSET_TABLE_, %ebx 132 movl LZMA_CRC32_TABLE@GOT(%ebx), %ebx 133#endif 134 135 /* Complement the initial value. */ 136 notl %eax 137 138 ALIGN(4, 16) 139.L_align: 140 /* 141 * Check if there is enough input to use slicing-by-eight. 142 * We need 16 bytes, because the loop pre-reads eight bytes. 143 */ 144 cmpl $16, %edi 145 jb .L_rest 146 147 /* Check if we have reached alignment of eight bytes. */ 148 testl $7, %esi 149 jz .L_slice 150 151 /* Calculate CRC of the next input byte. */ 152 movzbl (%esi), %ebp 153 incl %esi 154 movzbl %al, %ecx 155 xorl %ecx, %ebp 156 shrl $8, %eax 157 xorl (%ebx, %ebp, 4), %eax 158 decl %edi 159 jmp .L_align 160 161 ALIGN(2, 4) 162.L_slice: 163 /* 164 * If we get here, there's at least 16 bytes of aligned input 165 * available. Make %edi multiple of eight bytes. Store the possible 166 * remainder over the "size" variable in the argument stack. 167 */ 168 movl %edi, 0x18(%esp) 169 andl $-8, %edi 170 subl %edi, 0x18(%esp) 171 172 /* 173 * Let %edi be buf + size - 8 while running the main loop. This way 174 * we can compare for equality to determine when exit the loop. 175 */ 176 addl %esi, %edi 177 subl $8, %edi 178 179 /* Read in the first eight aligned bytes. */ 180 xorl (%esi), %eax 181 movl 4(%esi), %ecx 182 movzbl %cl, %ebp 183 184.L_loop: 185 movl 0x0C00(%ebx, %ebp, 4), %edx 186 movzbl %ch, %ebp 187 xorl 0x0800(%ebx, %ebp, 4), %edx 188 shrl $16, %ecx 189 xorl 8(%esi), %edx 190 movzbl %cl, %ebp 191 xorl 0x0400(%ebx, %ebp, 4), %edx 192 movzbl %ch, %ebp 193 xorl (%ebx, %ebp, 4), %edx 194 movzbl %al, %ebp 195 196 /* 197 * Read the next four bytes, for which the CRC is calculated 198 * on the next interation of the loop. 199 */ 200 movl 12(%esi), %ecx 201 202 xorl 0x1C00(%ebx, %ebp, 4), %edx 203 movzbl %ah, %ebp 204 shrl $16, %eax 205 xorl 0x1800(%ebx, %ebp, 4), %edx 206 movzbl %ah, %ebp 207 movzbl %al, %eax 208 movl 0x1400(%ebx, %eax, 4), %eax 209 addl $8, %esi 210 xorl %edx, %eax 211 xorl 0x1000(%ebx, %ebp, 4), %eax 212 213 /* Check for end of aligned input. */ 214 cmpl %edi, %esi 215 movzbl %cl, %ebp 216 jne .L_loop 217 218 /* 219 * Process the remaining eight bytes, which we have already 220 * copied to %ecx and %edx. 221 */ 222 movl 0x0C00(%ebx, %ebp, 4), %edx 223 movzbl %ch, %ebp 224 xorl 0x0800(%ebx, %ebp, 4), %edx 225 shrl $16, %ecx 226 movzbl %cl, %ebp 227 xorl 0x0400(%ebx, %ebp, 4), %edx 228 movzbl %ch, %ebp 229 xorl (%ebx, %ebp, 4), %edx 230 movzbl %al, %ebp 231 232 xorl 0x1C00(%ebx, %ebp, 4), %edx 233 movzbl %ah, %ebp 234 shrl $16, %eax 235 xorl 0x1800(%ebx, %ebp, 4), %edx 236 movzbl %ah, %ebp 237 movzbl %al, %eax 238 movl 0x1400(%ebx, %eax, 4), %eax 239 addl $8, %esi 240 xorl %edx, %eax 241 xorl 0x1000(%ebx, %ebp, 4), %eax 242 243 /* Copy the number of remaining bytes to %edi. */ 244 movl 0x18(%esp), %edi 245 246.L_rest: 247 /* Check for end of input. */ 248 testl %edi, %edi 249 jz .L_return 250 251 /* Calculate CRC of the next input byte. */ 252 movzbl (%esi), %ebp 253 incl %esi 254 movzbl %al, %ecx 255 xorl %ecx, %ebp 256 shrl $8, %eax 257 xorl (%ebx, %ebp, 4), %eax 258 decl %edi 259 jmp .L_rest 260 261.L_return: 262 /* Complement the final value. */ 263 notl %eax 264 265 popl %ebp 266 popl %edi 267 popl %esi 268 popl %ebx 269 ret 270 271#if defined(PIC) || defined(__PIC__) 272 ALIGN(4, 16) 273.L_get_pc: 274 movl (%esp), %ebx 275 ret 276#endif 277 278#if defined(__APPLE__) && (defined(PIC) || defined(__PIC__)) 279 /* Mach-O PIC */ 280 .section __IMPORT,__pointers,non_lazy_symbol_pointers 281.L_lzma_crc32_table$non_lazy_ptr: 282 .indirect_symbol LZMA_CRC32_TABLE 283 .long 0 284 285#elif defined(_WIN32) || defined(__CYGWIN__) 286# ifdef DLL_EXPORT 287 /* This is equivalent of __declspec(dllexport). */ 288 .section .drectve 289 .ascii " -export:lzma_crc32" 290# endif 291 292#elif !defined(__MSDOS__) 293 /* ELF */ 294 .size LZMA_CRC32, .-LZMA_CRC32 295#endif 296 297/* 298 * This is needed to support non-executable stack. It's ugly to 299 * use __linux__ here, but I don't know a way to detect when 300 * we are using GNU assembler. 301 */ 302#if defined(__ELF__) && (defined(__FreeBSD__) || defined(__linux__)) 303 .section .note.GNU-stack,"",@progbits 304#endif 305