NASM - The Netwide Assembler
NASM Forum => Programming with NASM => Topic started by: muratohyes on July 04, 2014, 10:53:14 AM
-
I have the following code part to find zeroes and digit repetitions in my pointed 4 digit number string:
mov ecx, [count] ; count is array's member count
mov eax, array
l2:
push ecx
mov [pointer], eax ; pointer to start of array
push eax
mov ecx, 4 ; if string contains any 0's it's written 0000 onto it
mov edi, [pointer]
mov al, '0'
cld
repne scasb
jne zero
push edx ; all characters in string are compared to each other
push ecx
push ebx
mov dword [repeat_cnt], 0 ; any digit repeats
; repeat_cnt is incremented, here it's reset
mov edx, dword [pointer] ; pointer set to edx, start of string
mov ecx, 4 ; loop will iterate 4 digits
char_loop:
push ecx
mov ebx, dword [pointer] ; compare string with itself
; get the second pointer to start
mov ecx, 4
char_loop2: ; here I'm doing O(n^2) iteration
push ecx
mov dl, byte [edx] ; get the bytes to dl,cl
mov cl, byte [ebx]
cmp dl, cl ; compare the digits in bytes
jne not_equal ; -> not equal
cmp edx, ebx ; if equal -> compare indexes
je not_equal ; if indexes are equal ->not equal.
; I want repeating characters which are in different indexes
inc dword [repeat_cnt] ; increment repeat count
not_equal:
inc ebx
pop ecx
loop char_loop2
inc edx
pop ecx
loop char_loop
pop ebx
pop ecx
pop edx
cmp [repeat_cnt], dword 0 ; if repeat count isn't zero,
je zero
pop eax ; write 0000 onto it
mov edx, [zeroes]
mov [eax], edx
push eax
zero:
push eax
mov eax, 4
mov ebx, 1
mov ecx, [pointer]
mov edx, 4
int 0x80
pop eax
pop eax
add eax, 4
pop ecx
dec ecx
jnz l2
Finding 0's, it's working well. This code also compiles successfully, but at somewhere I'm misusing something, because digit repeated numbers stay the same after the loop. I wrote what I'm trying to do by comments at important lines. Can you tell me at which I'm writing the incompatible code with the comments?
-
Well... I'm not sure you've got enough comments for that. :) Seriously, I'm losing track of what's in a register when it gets pushed, and more important, what's expected to be in a register when it's popped. I can look at it some more...
I think I understand the "specification" for this, but I'm not sure. At one point, you seemed to be talking about comparing two strings, or I misunderstood you. Anyway, this is an attempt to find what I think are "bad" numbers. I just print out the "bad" numbers. If I understand it, you want to skip the "bad" numbers... or overwrite them with '0's, and "save" (or maybe just print) the "good" numbers. Or maybe I don't understand the specification after all.
This was intended to be "simpler" than what you're doing. By the time I got done with it, I'm not sure it's any "simpler" at all...
; purpose: test of an algorithm to find numbers with duplicate (decimal) digits
; and numbers containing the digit '0'.
;
; nasm -f elf32 prog.asm
; ld -o prog prog.o -m elf_i386
; 32-bit Linux system call numbers
sys_write equ 4
sys_exit equ 1
; misc. equates
stdout equ 1
NL equ 10
global _start
section .data
; a "test" array (is this correct?)
array db "9876", "9875", "9874", "9873", "9872", "9871", "9870"
db "9869", "9868", "9867", "9866", "9865", "9864", "9863"
db "9862", "9861", "9860", "9859", "9858" ; etc...
end_of_array:
; also for "test" purposes
; we'd need a different "array" for a different number!
; eventually, we want to let user specify this(?)
number_of_digits dd 4
section .bss
pointer resd 1 ; pointer to current number in array
section .text
_start:
mov dword [pointer], array ; initialize pointer to start of array
test_dups:
mov edi, [pointer] ; this is the number we're checking
xor ebx, ebx ; this is the index of the character we're checking
outer_loop:
mov al, [edi + ebx] ; this is the character we're checking
xor ecx, ecx ; this is the index of the character(s) we're checking against
inner_loop:
cmp ebx, ecx
je continue ; we don't want to compare a character to itself
cmp [edi + ecx], al
jne continue ; if not equal, keep on
; we have a "bad" number - print it
call print_number
call newline
jmp next_number
continue:
inc ecx ; next character to check against
cmp ecx, [number_of_digits]
jne inner_loop
inc ebx ; next character to check
cmp ebx, [number_of_digits]
jne outer_loop
; this is going to trash eax, ecx, and edi
; so I leave it for last
test_zeros:
mov ecx, [number_of_digits]
mov al, '0'
repne scasb
jne next_number
; else print our "bad" number
call print_number
call newline
; fall through to next_number
next_number:
mov eax, [pointer]
add eax, [number_of_digits]
cmp eax, end_of_array
je exit
; else do next number
mov [pointer], eax
jmp test_dups
exit:
mov eax, sys_exit
mov ebx, 0 ; claim "no error"
int 80h
;----------------
;----------------
print_number:
push eax
push ebx
push ecx
push edx
mov edx, [number_of_digits]
mov ecx, [pointer]
mov ebx, stdout
mov eax, sys_write
int 80h
pop edx
pop ecx
pop ebx
pop eax
ret
;-------------------
;-------------------
newline:
push eax
push ebx
push ecx
push edx
push NL
mov ecx, esp ; the stack is my "buffer"
mov edx, 1
mov ebx, stdout
mov eax, sys_write
int 80h
add esp, 4 ; clean up stack
pop edx
pop ecx
pop ebx
pop eax
ret
;----------------
You'll notice that in my subroutines, I push and pop all the registers used. This is "overkill" for any calling convention I know. Generally, ecx at least is considered "volatile" and can be expected to be trashed. For my own convenience, I prefer to preserve it. Keep this in mind if you use other subroutines - particularly libc!
Maybe you can get some ideas from that. Maybe you're better off to ignore it. Maybe it'll help you straighten me out if I've got the "specification" wrong. Kept me amused for a while, in any case. :)
Best,
Frank
-
This is absolutely professional artwork :) I didn't know you're giving such all-around answers, that's why I asked parts seperately. Yes, I'm a stackoverflow user :) I know I will ask simple and stupid questions again, so I'm giving you my actual specification:
1- I'm trying to implement a program which tries to find a picked number from a human. More game information here: http://en.wikipedia.org/wiki/Bulls_and_cows (http://en.wikipedia.org/wiki/Bulls_and_cows)
2- First I'm taking the digit count from the user and fill an array of numbers which doesn't contain a digit more than once and any zeroes.
3- I guess the first number on the list and get the distance values from the user. This values represent placed and not-placed matches. e.g 1234 - 4289, 1 placed 1 not-placed, or "+1" "-1" for short.
4- Assume I've guessed 1234 and user told me "+1 -1". Now, I will iterate through the list, and rule out the numbers which aren't "+1 -1" to 1234. Because the number we're looking for is that "far" from 1234.
5- Go back to step 3 until there's only one element left in the array. (Guess the first number in the array again. 1234 won't be guessed again, as it's "+4 -0" itself.)
My English isn't bad, but I sometimes use wrong words or long sentences and that makes me misunderstood a lot :) So please ask me any part I couldn't express.
I will now work on your code and take best practises of subroutines, register handling and such. Thanks again :)
-
This is the code I've so far. Everything is ready, but I think there's a logical bug here I cannot see. I have to rule out all the numbers which cannot be the one that the user picked. This ruling out continues until there's only one not-erased number in the array. However, all the numbers are eliminated from the array at the first guess cycle. I will add comments to needed parts, but code is too long and commenting everywhere would make it harder to read. Please ask me to comment the parts that you don't understand.
SYS_READ equ 3
SYS_WRITE equ 4
SYS_EXIT equ 1
STDOUT equ 1
STDIN equ 0
NEWLINE equ 10
global _start
section .data
empty_str dd '----'
counter dd 9877
number_count dd 8643
number_array times 8643 dd '0000'
number_array_end:
digit_count dd 4
msg_placed db " placed: "
msg_placed_len equ $ - msg_placed
msg_nonplaced db " nonplaced: "
msg_nonplaced_len equ $ - msg_nonplaced
msg_guess db " guess: "
msg_guess_len equ $ - msg_guess
msg_number_count db " number_count: "
msg_number_count_len equ $ - msg_number_count
section .bss
buffer resb 10
current_number resd 1
guess resd 1
placed_count resd 1
nonplaced_count resd 1
placed_count_temp resd 1
nonplaced_count_temp resd 1
number_count_temp resd 1
section .text
_start:
;--------------------------------
; filling number_array 9876->1234
;--------------------------------
mov ecx, [number_count]
mov edx, number_array
fill_number_array:
push ecx
push edx
dec dword [counter]
lea esi, [buffer]
mov eax, [counter]
call int_to_string
pop edx
mov eax, [eax]
mov [edx], eax
add edx, 4
pop ecx
loop fill_number_array
;--------------------------------
;--------------------------------
; elimination of zero and same
; digit containing numbers
;--------------------------------
mov dword [current_number], number_array
eliminate_number_array:
mov edi, [current_number]
xor ebx, ebx
eliminate_digit_outer: ; loops are named as :
mov al, [edi + ebx] ; the current operation (eliminate, guess etc.)
xor ecx, ecx ; the iterated object (digit, number)
; a descriptive word (inner/outer here, array a little above)
eliminate_digit_inner:
cmp ebx, ecx
je eliminate_digit_continue
cmp [edi + ecx], al
jne eliminate_digit_continue
call erase_number
call dec_number_count
jmp eliminate_number_next
eliminate_digit_continue:
inc ecx
cmp ecx, [digit_count]
jne eliminate_digit_inner
inc ebx
cmp ebx, [digit_count]
jne eliminate_digit_outer
eliminate_number_zeroes:
mov ecx, [digit_count]
mov al, '0'
repne scasb
jne eliminate_number_next
call erase_number
call dec_number_count
eliminate_number_next:
mov eax, [current_number]
add eax, [digit_count]
cmp eax, number_array_end
je find_number
mov [current_number], eax
jmp eliminate_number_array
;-------------------------------
;-------------------------------
; guess a number, read +-, clear
; array, repeat until found
;-------------------------------
find_number:
call make_guess
call read_placed
call read_nonplaced
mov eax, [digit_count]
cmp eax, [placed_count]
je exit
call clear_wrong_numbers
jmp find_number
;--------------------------------
exit:
mov eax, SYS_EXIT
mov ebx, 0 ; no errors
int 80h
;--------------------------------
;--------------------------------
; chosen number (by user) is
; <placed,nonplaced> far from current guess.
; so numbers which aren't <placed,nonplaced>
; away from current guess is ruled out here
;--------------------------------
clear_wrong_numbers:
push eax
push ebx
push ecx
push edx
push edi
push esi
mov dword [current_number], number_array
clear_number_array:
mov edi, [current_number]
mov esi, empty_str
mov ecx, 5
cld
repe cmpsb
jecxz clear_number_next
mov esi, [guess]
xor ebx, ebx
mov dword [nonplaced_count_temp], 0
mov dword [placed_count_temp], 0
clear_digit_outer:
mov al, [edi + ebx]
xor ecx, ecx
clear_digit_inner:
cmp [esi + ecx], al
jne clear_digit_continue
cmp ebx, ecx
je inc_placed_count_temp
inc dword [nonplaced_count_temp]
jmp clear_digit_continue
inc_placed_count_temp:
inc dword [placed_count_temp]
clear_digit_continue:
inc ecx
cmp ecx, [digit_count]
jne clear_digit_inner
inc ebx
cmp ebx, [digit_count]
jne clear_digit_outer
placed_nonplaced_match:
mov edx, [placed_count_temp]
cmp edx, [placed_count]
jne clear_number_from_array
mov edx, [nonplaced_count_temp]
cmp edx, [nonplaced_count]
jne clear_number_from_array
jmp clear_number_next
clear_number_from_array:
call erase_number
call dec_number_count
clear_number_next:
mov eax, [current_number]
add eax, [digit_count]
cmp eax, number_array_end
je clear_number_array_done
mov [current_number], eax
jmp clear_number_array
clear_number_array_done:
mov edx, msg_guess_len
mov ecx, msg_guess
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
mov edx, [digit_count]
mov ecx, [guess]
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
pop esi
pop edi
pop edx
pop ecx
pop ebx
pop eax
ret
;--------------------------------
;--------------------------------
; assign first appropriate number
; (!= '----') as guess
;--------------------------------
make_guess:
push eax
push ebx
push ecx
push edx
push edi
push esi
mov dword [current_number], number_array
guess_number:
mov edi, [current_number]
mov esi, empty_str
mov ecx, 5
cld
repe cmpsb
jecxz guess_empty
guess_not_empty:
mov eax, guess
mov edx, [current_number]
mov [eax], edx
jmp made_guess
guess_empty:
mov eax, [current_number]
add eax, [digit_count]
cmp eax, number_array_end
je made_guess
mov [current_number], eax
jmp guess_number
made_guess:
mov edx, msg_guess_len
mov ecx, msg_guess
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
mov edx, [digit_count]
mov ecx, [guess]
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
pop esi
pop edi
pop edx
pop ecx
pop ebx
pop eax
ret
;--------------------------------
;--------------------------------
; print '----' over number
;--------------------------------
erase_number:
push eax
push edx
mov eax, [current_number]
mov edx, [empty_str]
mov [eax], edx
pop edx
pop eax
ret
;--------------------------------
;--------------------------------
; print number to screen
;--------------------------------
print_number:
push eax
push ebx
push ecx
push edx
mov edx, [digit_count]
mov ecx, [current_number]
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
pop edx
pop ecx
pop ebx
pop eax
ret
;--------------------------------
;--------------------------------
; print non-erased number count
;--------------------------------
dec_number_count:
push eax
push ebx
push ecx
push edx
push esi
push edi
mov edx, msg_number_count_len
mov ecx, msg_number_count
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
dec dword [number_count]
lea esi, [buffer]
mov eax, [number_count]
call int_to_string
mov [number_count_temp], eax
mov edx, 5
mov ecx, [number_count_temp]
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop eax
ret
;--------------------------------
;--------------------------------
; print newline to screen
;--------------------------------
newline:
push eax
push ebx
push ecx
push edx
push NEWLINE
mov ecx, esp
mov edx, 1
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
add esp, 4
pop edx
pop ecx
pop ebx
pop eax
ret
;--------------------------------
;--------------------------------
; integer-string conversion
; result's in eax
;--------------------------------
int_to_string:
add esi, 9
mov byte [esi], 10
mov ebx, 10
next_digit:
xor edx, edx
div ebx
add dl, '0'
dec esi
mov [esi], dl
test eax, eax
jnz next_digit
mov eax, esi
ret
;--------------------------------
;--------------------------------
; read placed digit count from user
;--------------------------------
read_placed:
push eax
push ebx
push ecx
push edx
mov edx, msg_placed_len
mov ecx, msg_placed
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
mov edx, 4
mov ecx, placed_count
mov ebx, STDIN
mov eax, SYS_READ
int 80h
and dword [placed_count], 0FFh
sub dword [placed_count], '0'
pop edx
pop ecx
pop ebx
pop eax
ret
;--------------------------------
;--------------------------------
; read nonplaced digit count from user
;--------------------------------
read_nonplaced:
push eax
push ebx
push ecx
push edx
mov edx, msg_nonplaced_len
mov ecx, msg_nonplaced
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
mov edx, 4
mov ecx, nonplaced_count
mov ebx, STDIN
mov eax, SYS_READ
int 80h
and dword [nonplaced_count], 0FFh
sub dword [nonplaced_count], '0'
pop edx
pop ecx
pop ebx
pop eax
ret
;--------------------------------
-
Let me make it clear that I'm not a "professional" - strictly a hobbyist. I wouldn't count on "best practices". I've been accused of "teaching sloppy methods to beginners." I try not to be "too" sloppy, but... see my recent reply to "Anonymous"...
Funny, something you said about "right digit wrong place" reminded me of "Mastermind". My daughter used to have the plastic version. In fact, I implemented a version for dos, a long time ago. I took the easy way out and made the computer the "codemaker" and let the human do all the thinking. Making the computer the "codebreaker" is much tougher! I'm concerned that humans are prone to mistakes. What happens if the pesky user tells us "one bull and one cow" and then two guesses later says "Wait! Two cows back there."? Only way I see is to quit the game and start over.
I was puzzled to see that they seem to think that three digits is tougher than four. I was also puzzled in Knuth's algorithm (discussed in the "Mastermind" link) that we sometimes have to make a guess that's "not in the set S". I may have to work through some examples...
In any case, I can see you're going to need routines to "match the score" of bulls and cows as well as kicking out "bad" numbers. And then, I guess, to check "proposed next guesses" against the "matches current guess" list to see how many would be eliminated... Do I understand that? Interesting exercise, anyway...
After you posted: Okay, I'll take a look....
Best,
Frank
-
Yes, you got it right. It takes 7 guesses at most with this method, if I remember it right. But generally finds it within 4-5 guesses.
-
I found a bug: "guess" doesn't stay at its value at the "clear_wrong_numbers" function. It's set to "----", because I'm not holding the actual value but the address of it there. I'm trying to deal with it now.
I dealt with that bug. For that:
1- In "clear_number_array" I changed
mov esi, [guess]
to mov esi, guess
2- In "guess_not_empty" I changed the code to
mov edx, [current_number]
mov eax, guess
mov [guess], eax
As it was copying the address of the "current_number" but not the value of it. But I can't still find the number right. I'm looking for other bugs now.
-
Yes. Also...
clear_number_array_done:
mov edx, msg_guess_len
mov ecx, msg_guess
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
mov edx, [digit_count]
mov ecx, [guess] ; <- ?
mov ebx, STDOUT
mov eax, SYS_WRITE
int 80h
Also I spotted a couple of places where you put 5 into ecx prior to a "repe cmpsb" when I would have expected 4. Nothing definite yet. I've only started to look at it...
Using "meaningful names" for variables and labels makes your code pretty easy to read!
Best,
Frank
-
"placed_count_temp" and "nonplaced_count_temp" aren't calculated correctly. I added some printout lines to see that. I am focusing on this point.
When I try to find placed-nonplaced count search for a number with itself, it gives 4 nonplaced. I feel like guess is circular shifted or reversed. However, reversing it didn't make a difference. I smell some evil things with esi-edi around "clear_number_array".
-
I got the bug.
clear_number_array:
mov edi, [current_number]
mov esi, empty_str
mov ecx, 5
cld
repe cmpsb
jecxz clear_number_next
;<------------------------------------------------ here I added mov edi, [current_number]
mov esi, [guess]
xor ebx, ebx
mov dword [nonplaced_count_temp], 0
mov dword [placed_count_temp], 0
"There" I re-moved current number to edi and I can get the non/placed numbers successfully now. My code finally guesses the number in a few steps. I cannot thank you enough Mr. Kotler :)
For the readers, I advice not to use instructions like repe, jecxz, cld etc. without knowing which registers they use. To have healthy volatile registers and values, always make necessary controls and push values to stack if needed, and if you're a beginner, carefully examine addressing modes. A good reading: http://mark.masmcode.com/
-
At the previous work I wrote "----" to eliminated numbers. Now, I'm told to shift the array so that eliminated number won't be in the array anymore. Copying too much elements just for one elimination doesn't make sense to me. However, it's been ordered, so I will write this. Is there any tips you can give here? I wonder if there's a really easy and effective way to shift the elements, if so what is it?
-
Arrragh! Yuck! Oh, not your code, I just found a rotten potato in the sack. Similar reaction, though. :)
If you've been "told" to shift the array down, perhaps that's the way you ought to do it. It does seem "inefficient". Also, "number_array_end:" isn't going to work properly once we start shortening it. That was just an "easy trick" anyway. We can keep track of either "end" or "number of items" to know when we're done (we do have to know!). I don't know of an easy way... we could move more than four bytes at a time, but we'd have to find a good alignment to start (ideally) and handle any odd leftovers at the end. (even on old 16-bit machines we sometimes used FPU registers to move 8 bytes at a time) Probably simplest - if not fastest - to just shift it down by "brute force". If the "digit_count" isn't always going to be four, that might add another problem.
If we were using a linked list, we could remove a node without shifting everything else around. We'd need "malloc()" and "free()" though. We can cobble together a "poor man's malloc" using sys_brk, but "free()" would be tougher, I think, and if we don't free the removed node that would cause a memory leak. Probably wouldn't run us out of memory - not with 4 digits anyway - but it's not good practice!
If you're "allowed" to use C library routines, this might be a good time to learn how to do it. Definitely easier to use code that somebody else has already written... and tested, and debugged, and maybe even optimized. I like to "do it myself" if I can, but there are limits...
Try a brute force, shift the array down, method. It might not be as slow as you imagine. I'll see if I can think of anything useful...
Best,
Frank
-
I think I can handle the "number_array_end" as I have "alive" number and digit count. I was just wondering if there's a common way of handling deletion of elements from the array in assembly. If not, my daily need of sarcastic replies are fulfilled :) Please don't get me wrong, I even read your answers to posts I don't care, just for your theatrical sentences :) Thanks
-
Ah I got a good algorithm, I guess. Iterating through the array, I will hold a writing pointer and a reading pointer.
number_count_temp = number_count
loop:
if @reading_point is_valid ; is valid: zero & repeat control for the first cycle, distance match for later cycles
write writingPoint @reading_point
writing_point += digit_count
else
dec number_count
if reading_point >= array_start + number_count
exit loop
goto loop
number_count = number_count_temp
Does this look valid&good?
-
I've been accused of "teaching sloppy methods to beginners."
Best,
Frank
Whoever accused you with that deserved a slap in the face. AFAIK, you sir, are the most patient and dedicated teacher attending to beginners on asm forum. There's no comparable 'Frank Kotler' on any asm board.