FizzBuzz в сборке - ошибка сегментации
Я пытаюсь написать FizzBuzz на ассемблере и постоянно вижу ошибку сегментации. До сих пор я определил, что это не мои процедуры печати (потому что я удалил их содержимое и проблема сохраняется), и ошибка скрывается где-то в основной функции.
Я получил этот вывод, когда я запускаю программу:
fizzSegmentation fault
Приводит меня к мысли, что проблема не в использовании деления и поиске остатков. Но я могу ошибаться, я не собирался в течение двух лет...
SECTION .data
global _start
fizz: db "fizz", 4
buzz: db "buzz", 4
SECTION .bss
counter: resb 1
SECTION .text
_start:
mov ax,0
mov [counter],ax
main_loop:
cmp ax,100 ;from 0 to 100
je exit ;
mov bl,3 ;divisor
mov ah,0 ;here will be a remainder
div bl ;divide
cmp ah,0 ;compare the remainder with 0
je print_fizz ;print fizz if they equal
mov bl,5 ;new divisor
mov ah,0 ;do I have to do it every time?
div bl ;divide
cmp ah,0 ;compare the remainder with 0
je print_buzz ;print buzz if they equal
jmp print_ax ;print contents of ax if not
inc ax ;increment ax
jmp main_loop ;jump to label
print_ax:
ret
print_fizz:
ret
print_buzz:
ret
exit:
mov rax,1
mov rbx,0
int 80h
ret
Я компилирую, используя:
yasm -f elf64 -o fizzbuzz.o fizzbuzz.asm
ld -d -o fizzbuzz fizzbuzz.o
3 ответа
Это вызывает ошибку сегментации:
...
je print_fizz ;print fizz if they equal
...
je print_buzz ;print buzz if they equal
jmp print_ax ;print contents of ax if not
...
print_ax:
ret
print_fizz:
ret
print_buzz:
ret
...
Поскольку вы переходите к функциям, ret не получает обратный адрес и вернется куда угодно. Измените это на call/ret-пара:
...
; je print_fizz ;print fizz if they equal
jne .1 ;skip if not equal
call print_fizz
.1:
...
; je print_buzz ;print buzz if they equal
jne .2 ;skip if not equal
call print_buzz
.2:
; jmp print_ax ;print contents of ax if not
call print_ax
...
Это вызовет бесконечный цикл:
mov ax,0
mov [counter],ax
main_loop:
cmp ax,100 ;from 0 to 100
je exit
...
mov ah,0 ;here will be a remainder
div bl ;divide
...
mov ah,0 ;do I have to do it every time?
div bl ;divide
...
inc ax ;increment ax
jmp main_loop ;jump to label
AX изменяет свои значения и не может держать счетчик цикла. Я предлагаю:
...
main_loop:
; cmp ax,100 ;from 0 to 100
cmp byte [counter], 100
...
; inc ax ;increment ax
inc byte [counter]
jmp main_loop ;jump to label
...
Этот ответ закончился намного дольше, чем я планировал, что-то вроде учебника по написанию эффективного asm. т.е. как сделать простую задачу сложной.
На случай, если кто-то заинтересован в проверке кода попытавшейся реализации и в версии с большим количеством трюков asm:
Есть так много маленьких способов, которые могут быть лучше, например, сохранить 5 в bh а также 3 в bl, Вы не всегда должны использовать div bl, AMD64 имеет 20 однобайтовых регистров. (al/ah, bl/bh, cl/ch, dl/dh (без REX) и sil, dil, ... r15b (требуется REX)).
Использование 16-битного счетчика является как минимум пустой тратой байтов (префиксы размера операнда) и может привести к замедлению работы. С помощью mov reg,0 это плохо Поместите условную ветвь внизу цикла, когда это возможно.
mov rax, 1 это пустая трата байтов инструкции по сравнению с mov eax, 1 и это помечено yasm, что не оптимизирует это для вас во время сборки. (nasm сам делает.) Настройка 64-битных регистров, а затем с помощью int 0x80 32-битная совместимость ABI еще глупее.
Во-первых, глупо хранить 16-битный счетчик в памяти, но хранить его по адресу, где вы зарезервировали только один байт, вызывает проблемы.
Помимо мелочей, FizzBuzz(3,5) достаточно мал, чтобы развернуть и избежать некоторых div целиком С помощью макросов на ассемблере вы могли бы легко создать полностью развернутый цикл с выводами LCM(fizz,buzz) на цикл (т.е. 15 в данном случае); достаточно для повторения шаблона, поэтому вам не нужны никакие условия.
Вы можете избежать div без развертывания с помощью счетчиков вниз, чтобы обнаружить count%5==0 а также count%3==0, 16-битный DOS код-гольф @ anatolyg FizzBuzz делает это. Это действительно распространенная техника - делать что-то каждый раз, когда происходит что-то еще. например, события счетчика производительности работают таким образом.
Вот моя попытка создать эффективный FizzBuzz (для AMD64 Linux) без использования библиотек. только write(2) а также exit_group(2)
Там нет компилятора, поэтому, если вы хотите хороший код, вы должны написать его самостоятельно. Вы не можете просто надеяться, что компилятор сделает что-то хорошее с i%3 в цикле (чего не происходит, для большинства компиляторов).
Код развивался во время написания. Как обычно, начало реализации одного способа дает вам лучшие идеи, когда вы видите, что ваша первая идея требует большего или меньшего количества инструкций, чем вы ожидали.
Я развернул 3 (Fizz), чтобы удалить все проверки counter%3, Я занимался counter%5 чеки с обратным отсчетом от 5 вместо деления. Это по-прежнему требует немалой логики, которая могла бы исчезнуть при полном развороте до точки, где шаблон повторяется (LCM(3,5)). Код целых чисел в коде ASCII может быть в функции или встроен в развернутый цикл для очень раздутого кода.
Я держу все в регистрах (включая константы fizz\n а также buzz\n). Там нет загрузок, и хранит только в буфер. Многие из регистров устанавливаются вне цикла, а не с mov Непосредственно перед использованием. Это требует хороших комментариев, чтобы отслеживать, что вы положили куда.
Я добавляю символы в буфер, который мы write(2) после каждого fizzbuzz\n линия. Это самый длинный цикл, который происходит естественным образом в логике программы, и означает, что нам нужно только syscall код в одном месте.
В реальной программе, которая может записывать в файл или канал, было бы лучше использовать стратегию C stdio по использованию гораздо большего буфера в этом случае. (Многие ~100-байтовые записи намного хуже, чем записи 4096B.) Тем не менее, я подумал, что это был интересный выбор между традиционным printf на каждой итерации или накоплением всей строки в один большой буфер. Я использовал статический буфер вместо того, чтобы резервировать пространство стека, потому что я пишу целую программу, а не функцию, которая должна избежать потери памяти после возврата. Кроме того, он позволил мне использовать 32-битный размер операнда для приращения указателя, чтобы сохранить байты кода (префиксы REX).
Было бы довольно легко накапливать несколько блоков, пока вы не дойдете до точки, где следующая группа может пройти за конец буфера. т.е. сравнить текущую позицию с buffer_end - BUZZMOD*FIZZMOD*9, Оптимизация системных вызовов ввода / вывода - это, очевидно, широкая тема, и этой версии достаточно для демонстрации накопления строки в буфере.
; for (count=1..100):
; if(count%3 == 0) { print_fizz(); }
; if(count%5 == 0) { print_buzz(); } else {
; if(count%3 && count%5) print(count);
;; }
; print(newline)
; We don't need pointers to these strings at all; The strings are immediate data for a couple mov instructions
;SECTION .rodata ; put constants in .rodata.
; fizz: db "fizz" ; No idea what the trailing 4 was for
; buzz: db "buzz"
FIZZMOD equ 3 ; only 3 works, but it would be easy to use a loop
BUZZMOD equ 5 ; any value works
LASTCOUNT equ 100 ; max 100: we only handle two decimal digits.
; TODO: cleanup that can handle LASTCOUNT%FIZZMOD != 1 and LASTCOUNT%BUZZMOD != 0
SECTION .bss
;;; generate a string in this buffer. (flush it with write(2) on "fizzbuzz" lines)
; buf: resb 4096
buf: resb FIZZMOD * BUZZMOD * 9 ; (worst case: every line is "fizzbuzz\n")
SECTION .text
global _start
_start:
; args for write(2). (syscall clobbers rcx/r11, and rax with the return value)
mov edi, 1 ; STDOUT_FILENO. also happens to be __NR_write in the AMD64 Linux ABI
mov esi, buf ; static data lives in the low 2G of address space, so we don't need a 64bit mov
;; edx = count. ; calculated each iteration
;; mov eax, edi ; also needed every time. saves 3B vs mov eax, imm32
; 'fizz' is only used once, so we could just store with an immediate there. That wouldn't micro-fuse, and we'd have to do the newline separately
mov r10b, 10 ; base 10
;;mov r14d, BUZZMOD ; not needed, we don't div for this
mov r12, 'fizz' | 10<<32 ; `fizz\n`, but YASM doesn't support NASM's backquotes for \-escapes
mov r13, 'buzz' | 10<<32 ; `buzz\n`. When buzz appears, it's always the end of a line
;;;;;;;; Set up for first iteration
mov ebp, BUZZMOD ; detect count%BUZZMOD == 0 with a down-counter instead of dividing
mov ebx, 1 ; counter starts at 1
mov edx, esi ; current output position = front of buf
ALIGN 16
main_loop:
;; TODO: loop FIZZMOD-1 times inside buzz_or_number, or here
;; It doesn't make much sense to unroll this loop but not inline buzz_or_number :/
call buzz_or_number
inc ebx
call buzz_or_number
add ebx, 2 ; counter is never printed on Fizz iterations, so just set up for next main_loop
;; Fizz, and maybe also Buzz
mov qword [rdx], r12 ; Fizz with a newline
add edx, 5 ; TODO: move this after the branch; adjust the offsets in .fizzbuzz
dec ebp
jz .fizzbuzz
;;.done_buzz: ; .fizzbuzz duplicates the main_loop branch instead of jumping back here
cmp ebx, LASTCOUNT-FIZZMOD
jbe main_loop
;;;;;;;;;; END OF main_loop
.cleanup:
;;;;;;;;;;;;;;;;;;;;; Cleanup after the loop
; hard-code the fact that 100 % FIZZMOD = 1 more line to print,
; and that 100 % BUZZMOD = 0, so the line is "buzz\n"
mov eax, edi ; __NR_write
mov [rdx], r13 ; the final "buzz\n".
sub edx, buf - 5 ; write_count = current_pos+5 - buf.
syscall ; write(1, buf, p - buf).
;; if buf isn't static, then use add edx, 5 / sub edx, esi
xor edi, edi
mov eax, 231 ; exit_group(0). same as eax=60: exit() for a single-threaded program
syscall
;;;;; The fizzbuzz case from the loop
.fizzbuzz:
;; count%BUZZMOD == 0: rdx points after the \n at the end of fizz\n, which we need to overwrite
;; this is a macro so we can use it in buzz_or_number, too, where we don't need to back up and overwrite a \n
%macro BUZZ_HIT 1
mov [rdx - %1], r13 ; buzz\n. Next line will overwrite the last 3 bytes of the 64b store.
add edx, 5 - %1
mov ebp, BUZZMOD ; reset the count%BUZZMOD down-counter
%endmacro
BUZZ_HIT 1 ; arg=1 to back up and overwrite the \n from "fizz\n"
sub edx, esi ; write_count = current_pos - buf
mov eax, edi ; __NR_write
syscall ; write(1, buf, p - buf). clobbers only rax (return value), and rcx,r11
mov edx, esi ; restart at the front of the buffer
;;; tail-duplication of the main loop, instead of jmp back to the cmp/jbe
;;; could just be a jmp main_loop, if we check at assemble time that LASTCOUNT % FIZZMOD != 0 || LASTCOUNT % BUZZMOD != 0
cmp ebx, LASTCOUNT-FIZZMOD
jbe main_loop
jmp .cleanup
;;;;;;;;;;;;;;;;;;;;;;; buzz_or_number: called for non-fizz cases
; special calling convention: uses (without clobbering) the same regs as the loop
;; modifies: BUZZMOD down-counter, output position pointer
;; clobbers: rax, rcx
ALIGN 32
buzz_or_number:
dec ebp
jnz .no_buzz ; could make this part of the macro, but flow-control inside macros is probably worse than duplication
;; count%BUZZMOD == 0: append "buzz\n" to the buffer and reset the down-counter
BUZZ_HIT 0 ; back up 0 bytes before appending
ret
.no_buzz: ;; get count as a 1 or 2-digit ASCII number
;; assert(ebx < 10); We don't handle 3-digit numbers
mov eax, ebx
div r10b ; al = count/10 (first (high) decimal digit), ah = count%10 (second (low) decimal digit).
;; x86 is little-endian, so this is in printing-order already for storing eax
;movzx eax, ax ; avoid partial-reg stalls on pre-Haswell
;; convert integer digits to ASCII by adding '0' to al and ah at the same time, and set the 3rd byte to `\n`.
cmp ebx, 9 ; compare against the original counter instead of the div result, for more ILP and earlier detection of branch misprediction
jbe .1digit ; most numbers from 1..100 are 2-digit, so make this the not-taken case
add eax, 0x0a3030 ;; `00\n`: converts 2 integer digits -> ASCII
;; eax now holds the number + newline as a 3-byte ASCII string
mov [rdx], eax
add edx, 3
ret
.1digit:
;; Could use a 16bit operand-size here to avoid partial-reg stalls, but an imm16 would LCP-stall on Intel.
shr eax, 8 ; Shift out the leading 0
add eax, 0x000a30 ;; 1-digit numbers
;; eax now holds the number + newline as a 2-byte ASCII string
mov [rdx], ax
add edx, 2
ret
Вот как это работает:
$ strace ./fizzbuzz > /dev/null
execve("./fizzbuzz", ["./fizzbuzz"], [/* 69 vars */]) = 0
write(1, "1\n2\nfizz\n4\nbuzz\nfizz\n7\n8\nfizz\nbu"..., 58) = 58
write(1, "16\n17\nfizz\n19\nbuzz\nfizz\n22\n23\nfi"..., 63) = 63
write(1, "31\n32\nfizz\n34\nbuzz\nfizz\n37\n38\nfi"..., 63) = 63
write(1, "46\n47\nfizz\n49\nbuzz\nfizz\n52\n53\nfi"..., 63) = 63
write(1, "61\n62\nfizz\n64\nbuzz\nfizz\n67\n68\nfi"..., 63) = 63
write(1, "76\n77\nfizz\n79\nbuzz\nfizz\n82\n83\nfi"..., 63) = 63
write(1, "91\n92\nfizz\n94\nbuzz\nfizz\n97\n98\nfi"..., 40) = 40
exit_group(0) = ?
./fizzbuzz | diff - <(perl -E'say((fizz)[$_%3].(buzz)[$_%5]or$_)for+1..100')
# no output = no difference
Развертывание над Buzz (5) и использование обратного счетчика для Fizz, вероятно, будет хуже. Моя версия имеет 64-битный магазин fizz\n\0\0\0 а затем ветка, чтобы решить, следует ли хранить buzz\n\0\0\0 перекрытие для производства fizzbuzz\n, Другой способ будет иметь ветку, чтобы решить, хранить ли fizz (перевод строки не требуется, так что это может быть 32-битный магазин). Тогда это будет безусловно хранить buzz\n\0\0\0, Однако, поскольку FIZZMOD меньше, чем BUZZMOD, это означает более частые сбросы обратного счетчика и больше проверок, чтобы увидеть, нужно ли нам печатать число вместо строки на этой итерации. Известно, что каждая третья строка fizz\n или же fizzbuzz\n означает, что более простой код для этого выполняется чаще.
Если пересекающиеся хранилища являются проблемой, весь этот алгоритм облажался, и это только один из многих. Кроме того, мы могли бы просто ветвиться перед сохранением fizz\n и добавление 5. Затем в fizzbuzz\n случай, мы делаем два магазина и добавляем 9. Это также отделяет dec/jcc от cmp/jcc внизу main_loop Таким образом, они могут надеяться, что оба макро-предохранителя на предварительном Haswell. IIRC, у некоторых процессоров есть предикторы ветвлений, которым действительно не нравятся множественные ветви, действительно близкие друг к другу.
Дальнейшие улучшения, оставленные в качестве упражнения для читателя:
В соответствии
buzz_or_numberи, возможно, превратить его в цикл (итерации FIZZMOD-1)Кроме того, он может, вероятно, меньше переходить, и другие незначительные улучшения. Это своего рода версия 1.1: работающая, протестированная, с некоторыми комментариями и наблюдениями, добавленными во время написания этого ответа, но на самом деле не улучшающими код, в отличие от того, что я изначально решил, было достаточно хорошо, чтобы увидеть, работает ли он.
Сделайте его более гибким, написав цикл очистки (или макросы ассемблера) для последнего
LASTCOUNT % FIZZMODлиний, вместо того, чтобы предполагать, что это 1 строка. Код очистки является обратной стороной для развертывания.Я использовал
divна 10, чтобы преобразовать счетчик в строку. Лучшая реализация будет использовать мультипликативный обратный, как компиляторы генерируют для небольших константных делителей (реализовано в этом случае с LEA).Еще одна стратегия, на которую стоит обратить внимание, - это уменьшение силы приращения последовательности цифр ASCII (хранящихся в регистре). Эту технику будет сложнее распространить на числа с большим количеством цифр. Хранение их в порядке печати (самая значимая цифра в младшем байте) делает перенос между цифрами против нас, а не против нас. (например, если бы они были в естественном порядке, вы могли бы
add eax, 256-10для исправления младшего разряда и увеличения старшего разряда с помощью переноса.) Возможно, стоит сохранить его таким образом, но BSWAP следует сохранить. Держать\nвстроенный в реестр, поэтому он занимает только один магазин, может не стоить того. Обнаружение и обработка 1-значного числа, превращающегося в 2-значное число, достаточно плохо.В 32-битном режиме мы могли бы использовать
AAAинструкция делать десятичный перенос после увеличения. Однако, несмотря на мнемонику, он работает на BCD (0-9), не ASCII ('0'-'9'), и, кажется, не облегчает распространение переноса на 3-ю цифру. Неудивительно, что AMD удалила его для AMD64. Это проверяетAFфлаг для определения выполнения младших 4 битов, но это полезно только дляDAAгде у вас есть две цифры BCD, упакованные в один байт, и когда вы добавляете неизвестные значения, не увеличивается. В этом случае вы просто проверяетеal >= 10,
Моя первая версия почти сработала в первый раз (после исправления нескольких синтаксических ошибок, чтобы он собирался, и глупого сбоя, который потребовал пару минут для отладки IIRC): fizz\nbuzz\n в fizzbuzz\n случай, и он поменял цифры. Я постоянно забываю, что сначала нужно хранить строки цифр с самой старшей цифрой, а не байтами в двоичном порядке с прямым порядком байтов.
Альтернативные способы сделать вещи
Я решил не использовать версию без разветвления кода преобразования ASCII, состоящего из 1 цифры и 2 цифр, поскольку потребовалось много инструкций. Также ветка должна очень хорошо прогнозировать.
;; Untested
buzz_or_number:
...
.no_buzz:
...
div r10b
DECIMAL_TO_ASCII_NEWLINE_2DIGIT equ 0x0a3030 ; add '0' to two unpacked decimal digits, and a newline
DECIMAL_TO_ASCII_NEWLINE_1DIGIT equ 0x000a30
;; hoist this out of the loop: mov r15d, DECIMAL_TO_ASCII_NEWLINE_2DIGIT - DECIMAL_TO_ASCII_NEWLINE_1DIGIT
xor ecx,ecx
cmp ah, 1 ; set CF if ah=0 (1 digit number), otherwise clear it. This allows sbb for a conditional add, instead of setcc
cmovae ecx, r15d ; 0 or the difference from 1digit to 2digit
lea eax, [rax+rcx + DECIMAL_TO_ASCII_NEWLINE_1DIGIT] ; rax+=0x0a3030 or 0x000a30, without clobbering flags
mov [rdx], eax
sbb edx, -3 ; add 2 (-(-3) - 1) or 3.
ret
В 32-битном (и 16-битном) режиме есть div инструкция, которая принимает непосредственный операнд и использует AL в качестве дивиденда, а не AX, Это называется AAM и был удален для AMD64 вместе с другими инструкциями BCD/ASCII. Это удобно для проверки делимости на 5 без привязки регистра для делителя или траты инструкции внутри цикла. Это немного быстрее, чем div r/m8 и устанавливает флаги в соответствии с остатком (в al: его результаты обращены вспять, по сравнению с div).
Гольф Анатолий FizzBuzz использует AAM в петле с shr ax, 8 генерировать одну цифру за раз в обратном порядке, сохраняя и уменьшая указатель.
Эта версия намного сложнее, потому что она использует AAM проверить счетчик%5 и затем обработать его в счетчик%10 вместо отдельного деления для получения цифр ASCII.
;; Untested
buzz_or_number_div:
mov eax, ebx
aam 5 ; al = al%5 ah = al/5. (opposite locations from div), and sets flags according to the remainder.
jz print_buzz ; tailcall
; fall through into print_counter
;print_counter:
; maybe use the result of div by 5 to get division by 10?
; shifting the low bit of the quotient into bit 4 of the remainder should be faster than dividing again.
;; after AAM: ah = 5bit quotient (qqqqQ), al = 3bit remainder(RRR)
;; starting point: ; AX = [ 000qqqqQ 00000RRR ]
;; desired = byte swapped as well: [ 0000QRRR 0000qqqq ]
shl al, 5 ; AX = [ 000qqqqQ RRR00000 ]
shr ax, 1 ; AX = [ 0000qqqq QRRR0000 ]
ror ax, 8 ; AX = [ QRRR0000 0000qqqq ] ; simple byte-swap
shr ah, 4 ; AX = [ 0000QRRR 0000qqqq ]
add eax, ...; convert to ascii
...
ret
; those instructions are all single-uop 1c latency on SnB-family, but pre-Haswell will insert extra merging uops. (And stall while doing so, on pre-SnB).
; and there's another partial-reg stall when we read eax
; It might be possible to do this bit manipulation with fewer operations, or maybe different ones. (maybe copy ax to cx, so we can move from cl or ch to al or ah?)
; shr ah, 1 ; AX = [ 0000qqqq 00000RRR ] CF=Q ; then what? setc/shift/or? rcl is slow, too.
; rorx eax, eax, 32-4 ; AX = [ qqqq0000 0RRR0000 ] CF=Q
; nope, seems a dead end
; shl ah, 3 ; AX = [ qqqqQ000 00000RRR ]
; ror ax, 7 ; AX = [ 0000RRRq qqqQ0000 ]
; shr al, 4 ; AX = [ 0000RRRq 0000qqqQ ]
; oops, no, shifts the wrong way.
; shl ah, 3 ; AX = [ qqqqQ000 00000RRR ]
; or ah, al ; AX = [ qqqqQRRR 00000RRR ]
; xor al,al ; AX = [ qqqqQRRR 00000000 ]
; rol ax, 4 ; AX = [ QRRR0000 0000qqqq ]
; shr ah, 4 ; AX = [ QRRR0000 qqqq0000 ]
; only 3 shifts, but still partial-reg heavy. Interesting on Haswell
; ror ax, 9 ; AX = [ Q00000RR R000qqqq ] CF=Q
Используйте отладчик, чтобы пошагово выполнить свой код и посмотреть, где он идет не так.
С первого взгляда уже очевидно, что ты уничтожаешь ax (может быть, вы не знаете, что ax изготовлена из ah а также al?). Также вы переходите к функциям, а не вызываете их, это, вероятно, является причиной неисправностей.