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(__linux__)
303	.section	.note.GNU-stack,"",@progbits
304#endif
305