2 * Copyright (c) Meta Platforms, Inc. and affiliates.
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
11 #include "../common/portability_macros.h"
13 #if defined(__ELF__) && defined(__GNUC__)
15 * ref: https://wiki.gentoo.org/wiki/Hardened/GNU_stack_quickstart
17 .section .note.GNU-stack,"",%progbits
19 #if defined(__aarch64__)
20 /* Mark that this assembly supports BTI & PAC, because it is empty for aarch64.
21 * See: https://github.com/facebook/zstd/issues/3841
22 * See: https://gcc.godbolt.org/z/sqr5T4ffK
23 * See: https://lore.kernel.org/linux-arm-kernel/20200429211641.9279-8-broonie@kernel.org/
24 * See: https://reviews.llvm.org/D62609
26 .pushsection .note.gnu.property, "a"
28 .long 4 /* size of the name - "GNU\0" */
29 .long 0x10 /* size of descriptor */
30 .long 0x5 /* NT_GNU_PROPERTY_TYPE_0 */
32 .long 0xc0000000 /* pr_type - GNU_PROPERTY_AARCH64_FEATURE_1_AND */
33 .long 4 /* pr_datasz - 4 bytes */
34 .long 3 /* pr_data - GNU_PROPERTY_AARCH64_FEATURE_1_BTI | GNU_PROPERTY_AARCH64_FEATURE_1_PAC */
35 .p2align 3 /* pr_padding - bring everything to 8 byte alignment */
41 #if ZSTD_ENABLE_ASM_X86_64_BMI2
43 /* Calling convention:
45 * %rdi contains the first argument: HUF_DecompressAsmArgs*.
46 * %rbp isn't maintained (no frame pointer).
47 * %rsp contains the stack pointer that grows down.
48 * No red-zone is assumed, only addresses >= %rsp are used.
49 * All register contents are preserved.
51 * TODO: Support Windows calling convention.
54 ZSTD_HIDE_ASM_FUNCTION(HUF_decompress4X1_usingDTable_internal_fast_asm_loop)
55 ZSTD_HIDE_ASM_FUNCTION(HUF_decompress4X2_usingDTable_internal_fast_asm_loop)
56 ZSTD_HIDE_ASM_FUNCTION(_HUF_decompress4X2_usingDTable_internal_fast_asm_loop)
57 ZSTD_HIDE_ASM_FUNCTION(_HUF_decompress4X1_usingDTable_internal_fast_asm_loop)
58 .global HUF_decompress4X1_usingDTable_internal_fast_asm_loop
59 .global HUF_decompress4X2_usingDTable_internal_fast_asm_loop
60 .global _HUF_decompress4X1_usingDTable_internal_fast_asm_loop
61 .global _HUF_decompress4X2_usingDTable_internal_fast_asm_loop
64 /* Sets up register mappings for clarity.
65 * op[], bits[], dtable & ip[0] each get their own register.
66 * ip[1,2,3] & olimit alias var[].
67 * %rax is a scratch register.
87 /* var[] aliases ip[1,2,3] & olimit
88 * ip[1,2,3] are saved every iteration.
89 * olimit is only used in compute_olimit.
96 /* 32-bit var registers */
102 /* Calls X(N) for each stream 0, 1, 2, 3. */
103 #define FOR_EACH_STREAM(X) \
109 /* Calls X(N, idx) for each stream 0, 1, 2, 3. */
110 #define FOR_EACH_STREAM_WITH_INDEX(X, idx) \
116 /* Define both _HUF_* & HUF_* symbols because MacOS
117 * C symbols are prefixed with '_' & Linux symbols aren't.
119 _HUF_decompress4X1_usingDTable_internal_fast_asm_loop:
120 HUF_decompress4X1_usingDTable_internal_fast_asm_loop:
122 /* Save all registers - even if they are callee saved for simplicity. */
139 /* Read HUF_DecompressAsmArgs* args from %rax */
149 movq 64(%rax), %bits0
150 movq 72(%rax), %bits1
151 movq 80(%rax), %bits2
152 movq 88(%rax), %bits3
153 movq 96(%rax), %dtable
154 push %rax /* argument */
155 push 104(%rax) /* ilowest */
156 push 112(%rax) /* oend */
157 push %olimit /* olimit space */
161 .L_4X1_compute_olimit:
162 /* Computes how many iterations we can do safely
163 * %r15, %rax may be clobbered
164 * rbx, rdx must be saved
165 * op3 & ip0 mustn't be clobbered
170 movq 32(%rsp), %rax /* rax = oend */
171 subq %op3, %rax /* rax = oend - op3 */
173 /* r15 = (oend - op3) / 5 */
174 movabsq $-3689348814741910323, %rdx
179 movq %ip0, %rax /* rax = ip0 */
180 movq 40(%rsp), %rdx /* rdx = ilowest */
181 subq %rdx, %rax /* rax = ip0 - ilowest */
182 movq %rax, %rbx /* rbx = ip0 - ilowest */
184 /* rdx = (ip0 - ilowest) / 7 */
185 movabsq $2635249153387078803, %rdx
192 /* r15 = min(%rdx, %r15) */
197 leaq (%r15, %r15, 4), %r15
199 /* olimit = op3 + r15 */
205 /* If (op3 + 20 > olimit) */
206 movq %op3, %rax /* rax = op3 */
207 cmpq %rax, %olimit /* op3 == olimit */
210 /* If (ip1 < ip0) go to exit */
214 /* If (ip2 < ip1) go to exit */
218 /* If (ip3 < ip2) go to exit */
222 /* Reads top 11 bits from bits[n]
223 * Loads dt[bits[n]] into var[n]
225 #define GET_NEXT_DELT(n) \
227 shrxq %var##n, %bits##n, %var##n; \
228 movzwl (%dtable,%var##n,2),%vard##n
230 /* var[n] must contain the DTable entry computed with GET_NEXT_DELT
231 * Moves var[n] to %rax
232 * bits[n] <<= var[n] & 63
233 * op[n][idx] = %rax >> 8
234 * %ah is a way to access bits [8, 16) of %rax
236 #define DECODE_FROM_DELT(n, idx) \
237 movq %var##n, %rax; \
238 shlxq %var##n, %bits##n, %bits##n; \
239 movb %ah, idx(%op##n)
241 /* Assumes GET_NEXT_DELT has been called.
242 * Calls DECODE_FROM_DELT then GET_NEXT_DELT
244 #define DECODE_AND_GET_NEXT(n, idx) \
245 DECODE_FROM_DELT(n, idx); \
248 /* // ctz & nbBytes is stored in bits[n]
249 * // nbBits is stored in %rax
255 * // Note: x86-64 is little-endian ==> no bswap
256 * bits[n] = MEM_readST(ip[n]) | 1
259 #define RELOAD_BITS(n) \
260 bsfq %bits##n, %bits##n; \
261 movq %bits##n, %rax; \
264 leaq 5(%op##n), %op##n; \
265 subq %bits##n, %ip##n; \
266 movq (%ip##n), %bits##n; \
268 shlx %rax, %bits##n, %bits##n
270 /* Store clobbered variables on the stack */
271 movq %olimit, 24(%rsp)
276 /* Call GET_NEXT_DELT for each stream */
277 FOR_EACH_STREAM(GET_NEXT_DELT)
282 /* Decode 5 symbols in each of the 4 streams (20 total)
283 * Must have called GET_NEXT_DELT for each stream
285 FOR_EACH_STREAM_WITH_INDEX(DECODE_AND_GET_NEXT, 0)
286 FOR_EACH_STREAM_WITH_INDEX(DECODE_AND_GET_NEXT, 1)
287 FOR_EACH_STREAM_WITH_INDEX(DECODE_AND_GET_NEXT, 2)
288 FOR_EACH_STREAM_WITH_INDEX(DECODE_AND_GET_NEXT, 3)
289 FOR_EACH_STREAM_WITH_INDEX(DECODE_FROM_DELT, 4)
291 /* Load ip[1,2,3] from stack (var[] aliases them)
292 * ip[] is needed for RELOAD_BITS
293 * Each will be stored back to the stack after RELOAD
299 /* Reload each stream & fetch the next table entry
300 * to prepare for the next iteration
317 /* If op3 < olimit: continue the loop */
321 /* Reload ip[1,2,3] from stack */
326 /* Re-compute olimit */
327 jmp .L_4X1_compute_olimit
330 #undef DECODE_FROM_DELT
336 /* Restore stack (oend & olimit) */
337 pop %rax /* olimit */
339 pop %rax /* ilowest */
342 /* Save ip / op / bits */
351 movq %bits0, 64(%rax)
352 movq %bits1, 72(%rax)
353 movq %bits2, 80(%rax)
354 movq %bits3, 88(%rax)
356 /* Restore registers */
374 _HUF_decompress4X2_usingDTable_internal_fast_asm_loop:
375 HUF_decompress4X2_usingDTable_internal_fast_asm_loop:
377 /* Save all registers - even if they are callee saved for simplicity. */
403 movq 64(%rax), %bits0
404 movq 72(%rax), %bits1
405 movq 80(%rax), %bits2
406 movq 88(%rax), %bits3
407 movq 96(%rax), %dtable
408 push %rax /* argument */
409 push %rax /* olimit */
410 push 104(%rax) /* ilowest */
413 push %rax /* oend3 */
416 push %rax /* oend2 */
419 push %rax /* oend1 */
422 push %rax /* oend0 */
427 .L_4X2_compute_olimit:
428 /* Computes how many iterations we can do safely
429 * %r15, %rax may be clobbered
431 * op[1,2,3,4] & ip0 mustn't be clobbered
435 /* We can consume up to 7 input bytes each iteration. */
436 movq %ip0, %rax /* rax = ip0 */
437 movq 40(%rsp), %rdx /* rdx = ilowest */
438 subq %rdx, %rax /* rax = ip0 - ilowest */
439 movq %rax, %r15 /* r15 = ip0 - ilowest */
442 movabsq $2635249153387078803, %rdx
449 /* r15 = (ip0 - ilowest) / 7 */
452 /* r15 = min(r15, min(oend0 - op0, oend1 - op1, oend2 - op2, oend3 - op3) / 10) */
453 movq 8(%rsp), %rax /* rax = oend0 */
454 subq %op0, %rax /* rax = oend0 - op0 */
455 movq 16(%rsp), %rdx /* rdx = oend1 */
456 subq %op1, %rdx /* rdx = oend1 - op1 */
459 cmova %rax, %rdx /* rdx = min(%rdx, %rax) */
461 movq 24(%rsp), %rax /* rax = oend2 */
462 subq %op2, %rax /* rax = oend2 - op2 */
465 cmova %rax, %rdx /* rdx = min(%rdx, %rax) */
467 movq 32(%rsp), %rax /* rax = oend3 */
468 subq %op3, %rax /* rax = oend3 - op3 */
471 cmova %rax, %rdx /* rdx = min(%rdx, %rax) */
473 movabsq $-3689348814741910323, %rax
475 shrq $3, %rdx /* rdx = rdx / 10 */
477 /* r15 = min(%rdx, %r15) */
481 /* olimit = op3 + 5 * r15 */
483 leaq (%op3, %rax, 4), %olimit
488 /* If (op3 + 10 > olimit) */
489 movq %op3, %rax /* rax = op3 */
490 cmpq %rax, %olimit /* op3 == olimit */
493 /* If (ip1 < ip0) go to exit */
497 /* If (ip2 < ip1) go to exit */
501 /* If (ip3 < ip2) go to exit */
505 #define DECODE(n, idx) \
506 movq %bits##n, %rax; \
508 movzwl 0(%dtable,%rax,4),%r8d; \
509 movzbl 2(%dtable,%rax,4),%r15d; \
510 movzbl 3(%dtable,%rax,4),%eax; \
511 movw %r8w, (%op##n); \
512 shlxq %r15, %bits##n, %bits##n; \
515 #define RELOAD_BITS(n) \
516 bsfq %bits##n, %bits##n; \
517 movq %bits##n, %rax; \
520 subq %bits##n, %ip##n; \
521 movq (%ip##n), %bits##n; \
523 shlxq %rax, %bits##n, %bits##n
526 movq %olimit, 48(%rsp)
531 /* We clobber r8, so store it on the stack */
534 /* Decode 5 symbols from each of the 4 streams (20 symbols total). */
535 FOR_EACH_STREAM_WITH_INDEX(DECODE, 0)
536 FOR_EACH_STREAM_WITH_INDEX(DECODE, 1)
537 FOR_EACH_STREAM_WITH_INDEX(DECODE, 2)
538 FOR_EACH_STREAM_WITH_INDEX(DECODE, 3)
539 FOR_EACH_STREAM_WITH_INDEX(DECODE, 4)
544 FOR_EACH_STREAM(RELOAD_BITS)
548 jmp .L_4X2_compute_olimit
554 /* Restore stack (oend & olimit) */
559 pop %rax /* ilowest */
560 pop %rax /* olimit */
563 /* Save ip / op / bits */
572 movq %bits0, 64(%rax)
573 movq %bits1, 72(%rax)
574 movq %bits2, 80(%rax)
575 movq %bits3, 88(%rax)
577 /* Restore registers */