Author Topic: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)  (Read 8178 times)

Offline arkoz

  • Jr. Member
  • *
  • Posts: 4
  • Country: 00
Hello! I have a program in TASM.. please, help me to redo the assignment from TASM (MS-DOS) to NASM (Linux)..

Ask the user for a pair of seed numbers for a Fibonacci sequence.
So instead of starting the sequence with 0,1,…; you start with the pair of numbers given.
If the user provides seeds: 1, 3
the sequence is: 1, 3, 4, 7, 11, 18, 29, 47…
instead of the usual 0,1,1,2,3,5,8,13,21,34…
Ask the user for how many steps to go in the sequence
the program should stop after printing that many numbers from the sequence
The program should stop if there is an overflow (number needing more than 32 bits)


Code: [Select]
.model small
.386

.data
printBuffer db 20
msg db "Go away! I refuse to say 'Hello', World!$"
len equ $ - msg
s dd 1
buf1 db 10,0,10 dup(?)
buf2 db 10,0,10 dup(?)
sym1 db 'Input first symbol: $'
sym2 db 'Input second symbol: $'
steps db 0Ah,0Dh,'Steps: $'
seed0 equ ?
seed1 equ ?
 
.code 
_start: 
mov ax,@data
mov ds,ax

mov ah,09h
lea dx,sym1
int 21h

mov ah,0Ah
lea dx,buf1
int 21h

lea esi,buf1+2
xor ecx,ecx
mov cl,byte ptr [buf1+1]

call _AsciiToSignedInt
 
mov esi,eax

mov ah,02h
mov dl,0Ah
int 21h

mov ah,02h
mov dl,0Dh
int 21h

mov ah,09h
lea dx,sym2
int 21h

mov ah,0Ah
lea dx,buf2
int 21h

push esi

lea esi,buf2+2
xor ecx,ecx
mov cl,byte ptr [buf2+1]

call _AsciiToSignedInt

pop esi
 
mov edi,eax

mov ah,09h
lea dx,steps
int 21h

mov ah,01h
int 21h

and al,0Fh

cbw
cwd

mov ecx,eax
dec ecx

push ecx

call _printEsi
 
call _printEdi

pop ecx

_fibloop:
push ecx
   
add esi,edi
jo _exit_cleanly
     
call _printEsi   
   
add edi,esi   
jo _exit_cleanly
 
call _printEdi 

pop ecx
loop _fibloop     
 
_exit_cleanly:
mov ah,4Ch
mov al,00h
int 21h
 
_printEsi:
mov eax,esi
call _printnum
ret
     
_printEdi:
mov eax,edi
call _printnum
ret 
     
_printnum:       
lea ebx,printBuffer   

call _IntToDecStr

mov ah,02h
mov dl,0Ah
int 21h

mov ah,02h
mov dl,0Dh
int 21h

mov ah,09h
mov edx,ebx
int 21h

mov ah,02h
mov dl,' '
int 21h

ret

_AsciiToSignedInt:
push ebx
push ecx
push edx
push edi

xor eax,eax
mov ebx,10
xor edi,edi

lodsb

cmp al,'-'
jne empty

mov s,-1

dec cx

jmp load

empty:
and al,0Fh

dec cx
je fin

cnv:
mov edi,eax

load:
lodsb

and al,0Fh

xchg eax,edi

mul ebx

add eax,edi
loop cnv

fin:
imul s

mov s,1

pop ebx
pop ecx
pop edx
pop edi

ret
 
_IntToDecStr:
asciiZero equ 30h         
 
add ebx,11
 
mov byte ptr [ebx],'$'

push eax

test eax,80000000h
je _Pos

_Neg:
neg eax

_Pos:

mov ecx,1

_PosIntToDecStr_Loop:
dec ebx
 
mov ebp,10       
 
mov edx,0
div ebp         

add edx,asciiZero

mov [ebx], dl
 
inc ecx

cmp eax,0
jne _PosIntToDecStr_Loop

pop eax

test eax,80000000h
je next

dec ebx

mov byte ptr [ebx],'-'

inc ecx

next:
 
ret
end _start

Offline jordi

  • Jr. Member
  • *
  • Posts: 6
Re: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)
« Reply #1 on: March 09, 2017, 08:34:04 PM »
Hi,

The problem I see using assembly for generating Fibonacci numbers is that you will get an overflow sooner than you suspected. Even beginning with 1, the first 50 Fibonacci numbers are:

 1 1
 2 1
 3 2
 4 3
 5 5
 6 8
 7 13
 8 21
 9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
31 1346269
32 2178309
33 3524578
34 5702887
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 2971215073
48 4807526976
49 7778742049
50 12586269025

and the last two will not fit in a 32 bit word. Even in 64 bit you will not be able to generate the first 100. For example,the Fibonacci number 1000 is:

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

The algorithm is very deceptive. It looks simple: add the last two numbers and that's it. Well, I myself got stuck once writing it in C: negative numbers began to scroll by the screen...

Unless you use a big precision number library only the first small numbers are obtained.

Jordi


Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)
« Reply #2 on: March 10, 2017, 05:01:16 AM »
While it is true that the Fibonacci sequence will overflow fairly soon, this has nothing to do with doing it in assembly language, nor with Tasm vs Nasm, nor with DOS vs Linux. proc3nt indicates that the "customer specification" (assignment) calls for "exit cleanly" in the case of overflow. No problem.

proc3nt has two issues. Converting Tasm syntax to Nasm syntax, and converting DOS i/o to Linux i/o. The arithmetic is pretty much the same. What are you having trouble with, proc3nt? How far can you get with it?

There's a little information in the manual about syntax differences, but it won't get you too far. One problem I see is that "printBuffer" is a single byte. There's some unused text after it that you can scribble over, so it won't do much harm, but it's still an error.

Nasm doesn't use "dup(?)" so you probably want something like:
Code: [Select]
section .bss ; uninitialized data
    printBuffer resb 20  ; reserve 20 bytes
; etc...

Linux doesn't have a "print" function that stops on a dollar sign, so you'll have to calculate the length as you do with the unused "msg" and use SYS_WRITE. Linux doesn't have an input function like int21h/0Ah, so use SYS_READ. You don't say whether you're using 32-bit Linux or 64-bit. They are different! I don't have any experience with 64-bit, so I won't be able to help you much with that.

See how far you can get with it.

Best,
Frank


Offline arkoz

  • Jr. Member
  • *
  • Posts: 4
  • Country: 00
Re: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)
« Reply #3 on: March 13, 2017, 01:39:00 AM »
32 bit.. I want to look whole listing code in Linux.. pls, help me..

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)
« Reply #4 on: March 13, 2017, 04:06:11 AM »
What do you need help with? If you mean "do my homework for me." Sorry.

There's some discussion of Fibonacci here:

https://forum.nasm.us/index.php?topic=1505.0

... but we never get to a working program. Going back to the Asm Community Forum reference might have more...

Best,
Frank


Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)
« Reply #5 on: March 13, 2017, 05:15:57 AM »
Well... the Asm Community doesn't appear to be working, even in archive mode. That's a shame!

I distinctly remember fooling with both a recursive version and using bitRAKE's observation that "xadd" is perfect for this, but couldn't find either. Given the hint that we were using Dr. Paul Carter's i/o routines, I found 'em! Since they are not specific to Linux, they aren't quite what you're looking for. Get the Linux version from http://www.drpaulcarter.com/pcasm if you want to try it out.

Code: [Select]

%include "asm_io.inc"

segment .data
            output db "Enter number to calculate fibonacci number: ",0
    over db "Sorry, numbers over 93 are too big for this humble program!", 10, 0
    linefeed db 10, 0

segment .bss
            userInput      resd    1
    numbuf resb 80 ; nice round number

segment .text
            global asm_main

asm_main:
    enter 0, 0

; prompt, and get user input
    mov eax, output
    call print_string
    call read_int
    mov [userInput], eax ; not used, but won't hurt...

; experimentation proves that 94 is too big!
    cmp eax, 93
    jbe oknum
    mov eax, over
    call print_string
    mov eax, -1 ; indicate an error happened
    jmp exit

oknum:   
    push eax ; count
    call fib64
    pop ecx

; since Dr. Carter's "print_int" won't handle numbers this size
; we do it ourselves...
    mov edi, numbuf
    call u64toda

    mov eax, edi
    call print_string
    mov eax, linefeed
    call print_string
   
    mov eax, 0 ; claim no error
exit:
    leave
    ret           
;-----------------------

;---------------------------------------------
; Thaks bitRAKE!

fib64:
; n only valid on [1,93]
mov ecx, [esp + 4]
; C likes these preserved
push esi
push edi

mov eax, 0
mov edi, 1
mov edx, 0
mov esi, 0
.top: xadd eax, edi
adc esi, 0
xadd edx, esi
dec ecx
jne .top

pop edi
pop esi
ret
;------------------------------------------------

;--------------------------------------------------------------
; u64toda - converts (64 bit) integer in edx:eax
; to (comma delimited) decimal representation in
; zero-terminated string in buffer pointed to by edi
;-----------------------------------------------------------------
u64toda:
                pusha
                mov ebx, edx     ; stash high dword
                mov esi,0Ah      ; prepare to divide by 10
                xor ecx, ecx     ; zero the digit count
                jmp highleft     ; check is high word 0 ?
highword:
                xchg eax,ebx    ; swap high & low words
                xor edx,edx     ; zero edx for the divide!
                div esi         ; divide high word by 10
                xchg eax,ebx    ; swap 'em back
                div esi         ; divide low word including remainder
                push edx        ; remainder is our digit - save it
                inc ecx         ; count digits
highleft:
                or ebx,ebx
                jnz highword
lowleft:
                xor edx,edx          ; zero high word
                div esi              ; divide low word by 10
                push edx             ; our digit
                inc ecx              ; count it
                or eax,eax           ; 0 yet ?
                jne lowleft
                cmp ecx, byte 4      ; commas needed ?
                jl write2buf         ; nope
                xor edx,edx            ; zero high word for divide
                mov eax,ecx            ; number of digits
                mov ebx,3
                div ebx
                mov esi,edx            ; remainder = number digits before comma
                test edx,edx
                jnz write2buf        ; no remainder?
                mov esi,3             ; we can write 3 digits, then.
write2buf:
                pop eax              ; get digit back - in right order
                add al,30H           ; convert to ascii character
                stosb                ; write it to our buffer
                dec esi               ; digits before comma needed
                jnz moredigits       ; no comma needed yet
                cmp ecx,2             ; we at the end?
                jl moredigits        ; don't need comma
                mov al,','           ; write a comma
                stosb
                mov esi,03h           ; we're good for another 3 digits
moredigits:
                loop write2buf       ; write more digits - cx of 'em
                mov al,00h           ; terminate buffer with zero
                stosb
popa
                ret
;-------------------------------------------------------------

That's not quite what you want, but it'll give you something to look at.

Strictly speaking, I think the Fibonacci sequence starts with 1, 1. Starting with arbitrary numbers the user enters will give you a "Fibonacci-like" sequence, No matter, that's what the assignment calls for, that's what you'd better do.

Do you know any Linux at all, or is this your first?

Best,
Frank



Offline arkoz

  • Jr. Member
  • *
  • Posts: 4
  • Country: 00
Re: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)
« Reply #6 on: March 13, 2017, 11:25:57 AM »
first, of course..

Offline arkoz

  • Jr. Member
  • *
  • Posts: 4
  • Country: 00
Re: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)
« Reply #7 on: March 13, 2017, 11:29:28 AM »
Frank Kotler, can you redo concrete precisely my variant of program?

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Fibonacci. Redo the assignment from TASM (MS-DOS) to NASM (Linux)
« Reply #8 on: March 13, 2017, 04:30:15 PM »
Could I? I could possibly come close. It is not my assignment! How far can you get with it?

Best,
Frank