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