x86 32-bitowa funkcja kodu maszynowego, 42 41 bajtów
Obecnie najkrótsza odpowiedź w języku innym niż golf, 1B krótsza niż q / kdb + streetstera .
Zerem dla prawdy i niezerowym dla fałszu: 41 40 bajtów. (generalnie zapisuje 1 bajt dla wersji 32-bitowej, 2 bajty dla wersji 64-bitowej).
Z ciągami o niejawnej długości (w stylu C zakończonym 0): 45 44 bajtów
kod maszynowy x86-64 (z 32-bitowymi wskaźnikami, takimi jak x32 ABI): 44 43 bajty .
x86-64 z ciągami o niejawnej długości, wciąż 46 bajtów (strategia bitmapy shift / mask jest teraz na progu rentowności).
Jest to funkcja z C podpisu _Bool dennis_like(size_t ecx, const char *esi). Konwencja wywoływania jest nieco niestandardowa, zbliżona do MS wektorcall / fastcall, ale z różnymi rejestrami arg: ciąg znaków w ESI i długość w ECX. Blokuje tylko arg-regy i EDX. AL przechowuje wartość zwracaną, przy czym wysokie bajty przechowują śmieci (zgodnie z ABI SysV x86 i x32. IDK to, co ABI MS mówią o wysokich śmieciach podczas zwracania wartości bool lub wąskich liczb całkowitych.)
Objaśnienie algorytmu :
Pętla nad ciągiem wejściowym, filtrując i klasyfikując do tablicy boolowskiej na stosie: Dla każdego bajtu sprawdź, czy jest to znak alfabetyczny (jeśli nie, przejdź do następnego znaku) i przekształć go na liczbę całkowitą od 0-25 (AZ) . Użyj tej liczby całkowitej 0-25, aby sprawdzić bitmapę samogłoski = 0 / spółgłoska = 1. (Mapa bitowa jest ładowana do rejestru jako 32-bitowa stała natychmiastowa). Wciśnij 0 lub 0xFF na stos zgodnie z wynikiem bitmapy (w rzeczywistości w niskim bajcie elementu 32-bitowego, który może zawierać śmieci w pierwszych 3 bajtach).
Pierwsza pętla tworzy tablicę 0 lub 0xFF (w elementach dword wypełnionych śmieciami). Wykonaj zwykłe sprawdzanie palindromu za pomocą drugiej pętli, która zatrzymuje się, gdy wskaźniki przecinają się na środku (lub gdy oba wskazują na ten sam element, jeśli występuje nieparzysta liczba znaków alfabetycznych). Wskaźnik w górę jest wskaźnikiem stosu i używamy POP do ładowania + przyrostu. Zamiast porównywać / ustawiać w tej pętli, możemy po prostu użyć XOR do wykrycia tego samego / innego, ponieważ istnieją tylko dwie możliwe wartości. Możemy kumulować (za pomocą OR), czy znaleźliśmy jakieś niepasujące elementy, ale wczesna gałąź na flagach ustawionych przez XOR jest co najmniej tak dobra.
Zauważ, że druga pętla używa bytewielkości operandu, więc nie ma znaczenia, jakie śmieci pozostawia pierwsza pętla poza niskim bajtem każdego elementu tablicy.
Używa nieudokumentowanej salcinstrukcji, aby ustawić AL z CF w taki sam sposób, jak sbb al,alby to zrobił. Jest obsługiwany na każdym procesorze Intel (z wyjątkiem trybu 64-bitowego), nawet w Knight's Landing! Agner Fog podaje również czasy dla wszystkich procesorów AMD (w tym Ryzen), więc jeśli dostawcy x86 nalegają na ograniczenie tego bajtu przestrzeni opcode od 8086, równie dobrze moglibyśmy z niego skorzystać.
Ciekawe sztuczki:
- trick bez porównania porównuje kombinację isalpha () i toupper (), a zero-wydłuża bajt, aby wypełnić eax, ustawiając dla:
- natychmiastowa mapa bitowa w rejestrze dla
bt, zainspirowana jakimś ładnym wyjściem kompilatora dlaswitch .
- Tworzenie tablicy o zmiennej wielkości na stosie za pomocą pętli push. (Standard dla asm, ale nie jest to coś, co można zrobić z C dla wersji ciągu o niejawnej długości). Wykorzystuje 4 bajty miejsca na stosie na każdy znak wejściowy, ale oszczędza co najmniej 1 bajt w porównaniu do optymalnej gry w golfa
stosb.
- Zamiast cmp / setne na tablicy boolowskiej, boolany XOR razem uzyskują bezpośrednio wartość prawdy. (
cmp/ salcnie jest opcją, ponieważ salcdziała tylko dla CF, a 0xFF-0 nie ustawia CF. setema 3 bajty, ale uniknie inczewnętrznej pętli, koszt netto 2 bajtów (1 w trybie 64-bitowym )) vs. xor w pętli i ustalanie jej za pomocą inc.
; explicit-length version: input string in ESI, byte count in ECX
08048060 <dennis_like>:
8048060: 55 push ebp
8048061: 89 e5 mov ebp,esp ; a stack frame lets us restore esp with LEAVE (1B)
8048063: ba ee be ef 03 mov edx,0x3efbeee ; consonant bitmap
08048068 <dennis_like.filter_loop>:
8048068: ac lods al,BYTE PTR ds:[esi]
8048069: 24 5f and al,0x5f ; uppercase
804806b: 2c 41 sub al,0x41 ; range-shift to 0..25
804806d: 3c 19 cmp al,0x19 ; reject non-letters
804806f: 77 05 ja 8048076 <dennis_like.non_alpha>
8048071: 0f a3 c2 bt edx,eax # AL = 0..25 = position in alphabet
8048074: d6 SALC ; set AL=0 or 0xFF from carry. Undocumented insn, but widely supported
8048075: 50 push eax
08048076 <dennis_like.non_alpha>:
8048076: e2 f0 loop 8048068 <dennis_like.filter_loop> # ecx = remaining string bytes
; end of first loop
8048078: 89 ee mov esi,ebp ; ebp = one-past-the-top of the bool array
0804807a <dennis_like.palindrome_loop>:
804807a: 58 pop eax ; read from the bottom
804807b: 83 ee 04 sub esi,0x4
804807e: 32 06 xor al,BYTE PTR [esi]
8048080: 75 04 jne 8048086 <dennis_like.non_palindrome>
8048082: 39 e6 cmp esi,esp ; until the pointers meet or cross in the middle
8048084: 77 f4 ja 804807a <dennis_like.palindrome_loop>
08048086 <dennis_like.non_palindrome>:
; jump or fall-through to here with al holding an inverted boolean
8048086: 40 inc eax
8048087: c9 leave
8048088: c3 ret
;; 0x89 - 0x60 = 41 bytes
Jest to prawdopodobnie jedna z najszybszych odpowiedzi, ponieważ żadna gra w golfa nie boli tak bardzo, przynajmniej dla łańcuchów poniżej kilku tysięcy znaków, w których użycie pamięci 4x nie powoduje wielu braków pamięci podręcznej. (Może również stracić odpowiedzi, które wymagają wcześniejszego wypuszczenia ciągów niepochodzących od Dennisa przed zapętleniem wszystkich znaków.) salcJest wolniejsze niż setccna wielu procesorach (np. 3 ulepszenia vs. 1 na Skylake), ale sprawdzenie bitmapy z bt/salcjest nadal szybszy niż wyszukiwanie ciągów lub dopasowanie do wyrażenia regularnego. I nie ma narzutu związanego z uruchamianiem, więc jest wyjątkowo tani w przypadku krótkich ciągów.
Wykonanie tego w jednym przejściu w locie oznaczałoby powtórzenie kodu klasyfikacji dla kierunków w górę i w dół. Byłoby to szybsze, ale większy rozmiar kodu. (Oczywiście, jeśli chcesz szybko, możesz robić 16 lub 32 znaki jednocześnie za pomocą SSE2 lub AVX2, wciąż używając sztuczki porównywania, przesuwając zakres na dół podpisanego zakresu).
Program testowy (dla systemu Linux ia32 lub x32), aby wywołać tę funkcję za pomocą argumentu cmdline i wyjść ze statusu = zwracana wartość. strlenwdrożenie z int80h.org .
; build with the same %define macros as the source below (so this uses 32-bit regs in 32-bit mode)
global _start
_start:
;%define PTRSIZE 4 ; true for x32 and 32-bit mode.
mov esi, [rsp+4 + 4*1] ; esi = argv[1]
;mov rsi, [rsp+8 + 8*1] ; rsi = argv[1] ; For regular x86-64 (not x32)
%if IMPLICIT_LENGTH == 0
; strlen(esi)
mov rdi, rsi
mov rcx, -1
xor eax, eax
repne scasb ; rcx = -strlen - 2
not rcx
dec rcx
%endif
mov eax, 0xFFFFAEBB ; make sure the function works with garbage in EAX
call dennis_like
;; use the 32-bit ABI _exit syscall, even in x32 code for simplicity
mov ebx, eax
mov eax, 1
int 0x80 ; _exit( dennis_like(argv[1]) )
;; movzx edi, al ; actually mov edi,eax is fine here, too
;; mov eax,231 ; 64-bit ABI exit_group( same thing )
;; syscall
Można użyć 64-bitowej wersji tej funkcji sbb eax,eax, dla której są tylko 2 bajty zamiast 3 setc al. Potrzebowałby także dodatkowego bajtu na końcu declub notna końcu (ponieważ tylko 32-bit ma 1 bajt inc / dec r32). Używając x32 ABI (32-bitowe wskaźniki w trybie długim), nadal możemy uniknąć prefiksów REX, nawet jeśli kopiujemy i porównujemy wskaźniki.
setc [rdi]może zapisywać bezpośrednio do pamięci, ale rezerwowanie bajtów ECX miejsca na stosie kosztuje więcej kodu niż to oszczędza. (I musimy przechodzić przez tablicę wyjściową. [rdi+rcx]Zajmuje jeden dodatkowy bajt dla trybu adresowania, ale tak naprawdę potrzebujemy licznika, który nie aktualizuje filtrowanych znaków, więc będzie gorzej.)
To jest źródło YASM / NASM z parametrami %ifwarunkowymi. Może być zbudowany z -felf32(kod 32-bitowy) lub -felfx32( kod 64-bit z ABI x32) oraz z niejawną lub jawną długością . Przetestowałem wszystkie 4 wersje. Zobacz tę odpowiedź dotyczącą skryptu do tworzenia statycznego pliku binarnego ze źródła NASM / YASM.
Aby przetestować wersję 64-bitową na komputerze bez obsługi ABI x32, możesz zmienić rejestr wskaźnika na 64-bit. (Następnie wystarczy odjąć liczbę prefiksów REX.W = 1 (0x48 bajtów) od liczby. W takim przypadku 4 instrukcje wymagają prefiksów REX do działania na 64-bitowych rejestrach). Lub po prostu nazwij to wskaźnikiem rspi wskaźnikiem wejściowym w niskim 4G przestrzeni adresowej.
%define IMPLICIT_LENGTH 0
; This source can be built as x32, or as plain old 32-bit mode
; x32 needs to push 64-bit regs, and using them in addressing modes avoids address-size prefixes
; 32-bit code needs to use the 32-bit names everywhere
;%if __BITS__ != 32 ; NASM-only
%ifidn __OUTPUT_FORMAT__, elfx32
%define CPUMODE 64
%define STACKWIDTH 8 ; push / pop 8 bytes
%else
%define CPUMODE 32
%define STACKWIDTH 4 ; push / pop 4 bytes
%define rax eax
%define rcx ecx
%define rsi esi
%define rdi edi
%define rbp ebp
%define rsp esp
%endif
; A regular x86-64 version needs 4 REX prefixes to handle 64-bit pointers
; I haven't cluttered the source with that, but I guess stuff like %define ebp rbp would do the trick.
;; Calling convention similar to SysV x32, or to MS vectorcall, but with different arg regs
;; _Bool dennis_like_implicit(const char *esi)
;; _Bool dennis_like_explicit(size_t ecx, const char *esi)
global dennis_like
dennis_like:
; We want to restore esp later, so make a stack frame for LEAVE
push rbp
mov ebp, esp ; enter 0,0 is 4 bytes. Only saves bytes if we had a fixed-size allocation to do.
; ZYXWVUTSRQPONMLKJIHGFEDCBA
mov edx, 11111011111011111011101110b ; consonant/vowel bitmap for use with bt
;;; assume that len >= 1
%if IMPLICIT_LENGTH
lodsb ; pipelining the loop is 1B shorter than jmp .non_alpha
.filter_loop:
%else
.filter_loop:
lodsb
%endif
and al, 0x7F ^ 0x20 ; force ASCII to uppercase.
sub al, 'A' ; range-shift to 'A' = 0
cmp al, 'Z'-'A' ; if al was less than 'A', it will be a large unsigned number
ja .non_alpha
;; AL = position in alphabet (0-25)
bt edx, eax ; 3B
%if CPUMODE == 32
salc ; 1B only sets AL = 0 or 0xFF. Not available in 64-bit mode
%else
sbb eax, eax ; 2B eax = 0 or -1, according to CF.
%endif
push rax
.non_alpha:
%if IMPLICIT_LENGTH
lodsb
test al,al
jnz .filter_loop
%else
loop .filter_loop
%endif
; al = potentially garbage if the last char was non-alpha
; esp = bottom of bool array
mov esi, ebp ; ebp = one-past-the-top of the bool array
.palindrome_loop:
pop rax
sub esi, STACKWIDTH
xor al, [rsi] ; al = (arr[up] != arr[--down]). 8-bit operand-size so flags are set from the non-garbage
jnz .non_palindrome
cmp esi, esp
ja .palindrome_loop
.non_palindrome: ; we jump here with al=1 if we found a difference, or drop out of the loop with al=0 for no diff
inc eax ;; AL transforms 0 -> 1 or 0xFF -> 0.
leave
ret ; return value in AL. high bytes of EAX are allowed to contain garbage.
Patrzyłem na bałagan z DF (flagą kierunkową, która kontroluje lodsd/ scasdi tak dalej), ale nie wydawało się to zwycięstwem. Zwykłe ABI wymagają wyczyszczenia DF przy wejściu i wyjściu funkcji. Zakładając, że wyczyszczone przy wjeździe, ale pozostawienie go ustawionego przy wyjściu byłoby oszustwem, IMO. Byłoby miło użyć LODSD / SCASD, aby uniknąć 3-bajtów sub esi, 4, szczególnie w przypadku braku śmieci.
Alternatywna strategia bitmapowa (dla ciągów o niejawnej długości x86-64)
Okazuje się, że nie zapisuje to żadnych bajtów, ponieważ bt r32,r32nadal działa z dużymi śmieciami w indeksie bitów. Po prostu nie jest to udokumentowane shr.
Zamiast bt / sbbwprowadzić bit do / z CF, użyj shift / mask, aby odizolować bit, który chcemy od bitmapy.
%if IMPLICIT_LENGTH && CPUMODE == 64
; incompatible with LOOP for explicit-length, both need ECX. In that case, bt/sbb is best
xchg eax, ecx
mov eax, 11111011111011111011101110b ; not hoisted out of the loop
shr eax, cl
and al, 1
%else
bt edx, eax
sbb eax, eax
%endif
push rax
Ponieważ daje to 0/1 w AL na końcu (zamiast 0 / 0xFF), możemy wykonać niezbędną inwersję wartości zwracanej na końcu funkcji za pomocą xor al, 1(2B) zamiast dec eax(również 2B w x86-64), aby nadal generuje poprawną bool/_Bool zwracaną wartość.
W ten sposób zapisywano 1B dla x86-64 z ciągami o niejawnej długości, unikając konieczności zerowania wysokich bajtów EAX. (Używałem and eax, 0x7F ^ 0x20do wymuszania wielkich liter i zerowania reszty eax za pomocą 3-bajtowego and r32,imm8. Ale teraz używam 2-bajtowego kodowania natychmiastowego z AL, które ma większość instrukcji 8086, tak jak już to robiłem dla subi cmp.)
Traci do bt/ salcw trybie 32-bitowym, a ciągi o jawnej długości potrzebują ECX do zliczania, więc to też tam nie działa.
Ale potem zdałem sobie sprawę, że się myliłem: bt edx, eaxnadal działa z wysokimi śmieciami w eax. To widocznie maski Shift liczyć tak samo shr r32, clma (patrząc tylko na niskich 5 bitów CL). Różni się to od tego bt [mem], reg, który może uzyskiwać dostęp poza pamięcią, do której odnosi się tryb / rozmiar adresowania, traktując to jako ciąg bitów. (Crazy CISC ...)
Instrukcja odnawiania wewnętrznego zestawu Intela nie dokumentuje maskowania, więc może to nieudokumentowane zachowanie, które Intel na razie zachowuje. (Takie rzeczy nie są rzadkie. bsf dst, srcPrzy src = 0 zawsze pozostawia dst niezmodyfikowane, nawet jeśli udokumentowano, że dst ma w tym przypadku niezdefiniowaną wartość. AMD faktycznie dokumentuje zachowanie src = 0). Testowałem na Skylake i Core2, a btwersja działa z niezerowymi śmieciami w EAX poza AL.
Dobrą sztuczką jest użycie xchg eax,ecx(1 bajtu), aby uzyskać licznik w CL. Niestety BMI2 shrx eax, edx, eaxma 5 bajtów, a tylko 2 bajty shr eax, cl. Korzystanie bextrwymaga 2 bajtów mov ah,1(do liczby bitów do wyodrębnienia), więc znów jest to 5 + 2 bajtów, takich jak SHRX + AND.
Kod źródłowy stał się dość niechlujny po dodaniu %ifwarunkowych. Oto demontaż ciągów o niejawnej długości x32 (przy użyciu alternatywnej strategii dla mapy bitowej, więc nadal jest to 46 bajtów).
Główną różnicą w stosunku do wersji o jawnej długości jest pierwsza pętla. Zauważ, że jest lodsprzed nim i na dole, zamiast tylko jednego na górze pętli.
; 64-bit implicit-length version using the alternate bitmap strategy
00400060 <dennis_like>:
400060: 55 push rbp
400061: 89 e5 mov ebp,esp
400063: ac lods al,BYTE PTR ds:[rsi]
00400064 <dennis_like.filter_loop>:
400064: 24 5f and al,0x5f
400066: 2c 41 sub al,0x41
400068: 3c 19 cmp al,0x19
40006a: 77 0b ja 400077 <dennis_like.non_alpha>
40006c: 91 xchg ecx,eax
40006d: b8 ee be ef 03 mov eax,0x3efbeee ; inside the loop since SHR destroys it
400072: d3 e8 shr eax,cl
400074: 24 01 and al,0x1
400076: 50 push rax
00400077 <dennis_like.non_alpha>:
400077: ac lods al,BYTE PTR ds:[rsi]
400078: 84 c0 test al,al
40007a: 75 e8 jne 400064 <dennis_like.filter_loop>
40007c: 89 ee mov esi,ebp
0040007e <dennis_like.palindrome_loop>:
40007e: 58 pop rax
40007f: 83 ee 08 sub esi,0x8
400082: 32 06 xor al,BYTE PTR [rsi]
400084: 75 04 jne 40008a <dennis_like.non_palindrome>
400086: 39 e6 cmp esi,esp
400088: 77 f4 ja 40007e <dennis_like.palindrome_loop>
0040008a <dennis_like.non_palindrome>:
40008a: ff c8 dec eax ; invert the 0 / non-zero status of AL. xor al,1 works too, and produces a proper bool.
40008c: c9 leave
40008d: c3 ret
0x8e - 0x60 = 0x2e = 46 bytes