flat assembler
Message board for the users of flat assembler.

 Index > Main > Recursion/Looping Problem
Author
kilobyte

Joined: 07 Jun 2008
Posts: 15
kilobyte
hey guys, i'm finding it hard to figure out how to implement a recursive routine? basically i'm trying to create all the possible combinations of all ascii values starting from 20h to 7Eh, up to 4 characters, so all combinations starting with 1, then 2, then 3 etc. mathematically it should come up to (94^1) + (94^2) + (94^3) + (94^4) = 78 914 410 total combinatons.

The only part i've been able to implement is the initialization of the ascii table that will be used.
Code:
```_hashtable  rb 94

.init:
mov eax,20h
mov esi,_hashtable
@@:
mov [esi],eax
cmp byte [esi],7Eh
je .initfinish
inc esi
inc eax
jmp @b
.initfinish:
xor eax,eax
...
```

I guess the problem that i'm having is figuring out how to implement a code to create the combinations. If you can help me or point me in the right direction, i would greatly appreciate it. Thanks in advance
07 Jun 2009, 17:34
neville

Joined: 13 Jul 2008
Posts: 507
Location: New Zealand
neville
kilobyte, the code you need to write is quite simple, almost trivial. All you need to do is to think the process through logically, and then implement it! Some people on this board just want other people to do their thinking for them - and some people are happy to do so. That's fine, but if this is YOUR project, then you should find YOUR solution, not somebody else's!

I am happy to critique the code you've already written -

In general terms, why do a memory access when the data you're checking is already in a register?
Instead of: cmp byte [esi], 7Eh
you could: cmp eax, 7Eh
or even: cmp al,7Eh

_________________
FAMOS - the first memory operating system
07 Jun 2009, 20:59
pal

Joined: 26 Aug 2008
Posts: 227
pal
Check out permutation generators. Combinations are different.
07 Jun 2009, 21:09
LocoDelAssembly

Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Seems I'm going to be one of those happy persons
Code:
```format pe console 4.0
include 'win32ax.inc'

call    generateStrings

invoke  ExitProcess, 0

generateStrings:
push    ebp
mov     ebp, esp
sub     esp, 8

mov     dword [esp], 0
mov     dword [esp+4], 0

push    0

.loop:
lea     eax, [esp+4]

push    dword [esp]
push    0
push    eax
call    _genStrings

inc     dword [esp]
cmp     dword [esp], 4
jb      .loop

leave
ret

_genStrings: ; [ESP+4] = Buffer;   [ESP+8] = Buffer index; [ESP+12] = Max index
push    ebx
push    esi
push    edi
; [ESP+16] = Buffer; [ESP+20] = Buffer index; [ESP+24] = Max index

mov     bl, \$20
mov     esi, [esp+16]
mov     edi, [esp+20]

cmp     edi, [esp+24]
je      .generateSequence

inc     edi

.recurse:
mov     [esi+edi-1], bl

push    dword [esp+24]
push    edi
push    esi
call    _genStrings

inc     bl
cmp     bl, \$7E
jbe     .recurse

jmp     .exit

.generateSequence:
push    .seqSeparator
call    [printf]

.loop:
mov     [esi+edi], bl

; At this point ESI points to a string containing one of the sequence of all possible strings with the constraints you specified

push    esi
push    .fmt
call    [printf]

inc     bl
cmp     bl, \$7E
jbe     .loop

.exit:
pop     edi
pop     esi
pop     ebx
ret     4*3

.fmt db "%s", 9, 0
.seqSeparator db 10, "-----[NEW SEQUENCE]-----", 10, 0

align 4 ; Just to be safe
data import
library kernel32, 'kernel32.dll',\
msvcrt,'msvcrt.dll'

import kernel32,\
ExitProcess, 'ExitProcess'

import msvcrt,\
printf, 'printf',\
system, 'system'
end data    ```

However, this is far from best, it is just a start point to see "ok, it can be done". I have implemented it recursively but not an strict requirement.

I encourage you to write your own code and share it with us.

BTW, what pal says is true, you are asking for permutations with repeated elements. Combinations don't distinguish between "BABA" and "ABAB".
07 Jun 2009, 21:21
kilobyte

Joined: 07 Jun 2008
Posts: 15
kilobyte
neville wrote:
kilobyte, the code you need to write is quite simple, almost trivial. All you need to do is to think the process through logically, and then implement it! Some people on this board just want other people to do their thinking for them - and some people are happy to do so. That's fine, but if this is YOUR project, then you should find YOUR solution, not somebody else's!

I am happy to critique the code you've already written -

In general terms, why do a memory access when the data you're checking is already in a register?
Instead of: cmp byte [esi], 7Eh
you could: cmp eax, 7Eh
or even: cmp al,7Eh

hey thanks i didn't actually see it that way, tho bare with me as i am new to assembly language programming, it takes me longer to take whats in my head and translate it to asm, i guess it gets easier with more practice. Also incase you're wandering whether this is a school project, it isn't infact i don't know of any schools that teach x86-assembly, this is purely out of my own pursuit, as i only code now in asm for fun. I just needed help with getting my thoughts down correctly, wasn't really looking for code. I do appreciate you code critique as i really didn't see it that way, tho now i see the reasoning behind it as it doesn't make sense reading from memory when it's already in register, reg faster than mem right?. thanks for the heads up neville.

Last edited by kilobyte on 07 Jun 2009, 21:57; edited 1 time in total
07 Jun 2009, 21:49
kilobyte

Joined: 07 Jun 2008
Posts: 15
kilobyte
@Pal: I'll definately lookup permutation generators and the differences between permutations and combinations, thanks for the pointing me in the right direction.

@LocoDelAssembly: Thanks for the code, but i'm going to put off looking at it until i've done my own, and i will definately post it up, when i get the time. Thanks for your help.
07 Jun 2009, 21:56
kilobyte

Joined: 07 Jun 2008
Posts: 15
kilobyte
I keep getting an "error: extra characters on line." when assembling. I've just posted the snippet of code that seems to be offending the compiler and any extra info that may be helpful. If anybody can tell me whats wrong then i would be once again very grateful.

Code:
```;declared variables,
_length  dd 0
_set     rb 96
_obuffer rb 8

;offending section of code

.permutate:
mov [_length],02h
call permutate,_obuffer,_set,_length

;procedure declaration, is this correct...
proc permutate uses esi edi ecx edx,buffer,set,length    ;infamous line 28
```

Error Output from the compiler

Code:
```flat assembler  version 1.67.38  (1895632 kilobytes memory)
X:\Assembly\snippets\PERMUT~1.ASM [29]:
call permutate,_obuffer,_set,_length
error: extra characters on line.
```
12 Jun 2009, 14:52
LocoDelAssembly

Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
call is a CPU instruction, you want to use "stdcall" instead:
Code:
`stdcall permutate,_obuffer,_set,_length     `

If you want to use call then you will need to do the following:
Code:
```push _length
push _set
push _obuffer
call permutate    ```
(This is exactly what stdcall macro does inside)

BTW, do you want permutate receive 2 as length? In that case that parameter should be "[_length]" not "_length" because with the latter you are passing a pointer/reference to the variable _length instead of its value.
12 Jun 2009, 15:10
kilobyte

Joined: 07 Jun 2008
Posts: 15
kilobyte
Thanks guys, i've finally been able to do it, now that i look back at it, it really is simple, though i've been through some headaches and did spend days thinking about it. I know it's probably sloppy/hackish coding in some areas, but hey I am new to asm programming. Would just like to say thanks to everyone that helped me and pointed me in the right direction. Now I better head of to revise for my last maths module on monday eek :/. I really hate pulling all nighters.

Code:
```; Permutation Snippet by kilobyte
; 13/06/09 - 00:34
; about the code: I only need it do it to length 4, but if you wanted to include permutations
; up to length w.e say 7, then
; all you would have to do is call permutate from a loop incrementing eax after every call.
; you would also have to remove the mov eax,01h line

format PE Console 4.0
entry start

include 'X:\fasmw\include\win32a.inc'

_fmt     db '%s',13,10,0
_obuffer rb 8

start:
.init:
clc
call permutate
.exit:
stdcall [ExitProcess],0

proc permutate
jc .infunc
push ebx
push edx
xor ebx,ebx
cmp ebx,23h
ja exit
mov eax,01h         ;0h-01h is 2, for demonstration purposes, doing 4 will take
xor edx,edx         ;a considerable amount of time.
mov edi,_obuffer
; push ebx
; push edx
.infunc:
mov ebx,20h
@@:
cmp bl,7Eh
ja .inret
mov [edi+edx],bl
cmp edx,eax
jne .next
call print
inc bl
jmp @b
.next:
push ebx
push edx
inc edx
stc
call permutate
pop edx
pop ebx
inc bl
jmp @b
.inret:
mov cl,bl
dec cl
cmp cl,7Eh
je exit
ret
print:
cinvoke printf,_fmt,_obuffer
ret
exit:
pop edx
pop ebx
ret

endp

library KERNEL, 'KERNEL32.DLL',\
MSVCRT, 'MSVCRT.DLL'

import KERNEL,\
ExitProcess, 'ExitProcess'

import MSVCRT,\
printf, 'printf'
```

also, i know this code could be improved in many ways; so if you have the time please critique the code and wrong habits, anything that could make me a better programmer. Thanks in advance.
12 Jun 2009, 23:50

Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
First I will give you some hints:
1) Its always nice to read code, when it fits on screen (about 80 chars wide)
2) When your environment is set, you can easily just include 'win32a.inc'
3) invoke ExitProcess is cleaner than stdcall [ExitProcess]
4) Sleep at the end of process lets you see what it printed out
5) pushad/popad are very constraining. FASM knows how to handle just pusha/popa
6) Use tabs between mnemonics and parameters
7) Data suits best at the end of the file (maybe its just my habit)

Code:
```; Permutation Snippet by kilobyte                                            80
; 13/06/09 - 00:34                                                           80
; about the code: I only need it do it to length 4, but if you wanted to     80
; include permutations up to length w.e say 7, then all you would have to    80
; do is call permutate from a loop incrementing eax after every call.        80
; you would also have to remove the mov eax,01h line                         80
;     /\
format PE Console 4.0                                                  ; see
entry start

include 'win32a.inc' ; FASM allows you this and its shorter
; This is possible if environment is set up though
start:
.init:
clc
call permutate
.exit:
invoke  Sleep,2000    ;Invoke is easier, no need to ][]][][[]]
;and make a pause for easier F9-use
invoke  ExitProcess,0

proc permutate
jc      .infunc
push    ebx
push    edx                             ;                            80
xor     ebx,ebx                         ; also comments so that I don't
cmp     ebx,23h                         ; need to scroll sideways
ja      exit                            ;                            80
mov     eax,01h     ;0h-01h is 2, for demonstration purposes,
;doing 4 will take
xor     edx,edx     ;a considerable amount of time.
mov     edi,_obuffer
;push    ebx
;push    edx
.infunc:
mov     ebx,20h
@@:
cmp     bl,7Eh
ja      .inret
mov     [edi+edx],bl
cmp     edx,eax
jne     .next
call    print
inc     bl
jmp     @b
.next:
push    ebx
push    edx
inc     edx
stc
call    permutate
pop     edx
pop     ebx
inc     bl
jmp     @b
.inret:
mov     cl,bl
dec     cl
cmp     cl,7Eh
je      exit
ret
print:
pusha                         ;pusha/popa will do fine
cinvoke printf,_fmt,_obuffer
popa                          ;assembler knows what it needs to do
ret
exit:
pop edx
pop ebx
ret

endp

section '.data' data readable writeable ;I put my data at the end of code
_fmt     db '%s',32,32,0 ;Spaces fit better on the console
_obuffer rb 8

library KERNEL, 'KERNEL32.DLL',\
MSVCRT, 'MSVCRT.DLL'

import KERNEL,\
ExitProcess, 'ExitProcess',\
Sleep,'Sleep'

import MSVCRT,\
printf, 'printf'
```

Now I give you the MOST interesting part of assembly language --- its MAGIC
Code:
```; Permutation v2 by Madis Kalme
; 13 July 2009
;
; Purpose:
; Call to permute_v2 will display permutations of length ecx to stdout

format PE Console 4.0
entry start

include 'win32a.inc'

start:
.init:
mov  ecx,3
call permute_v2
.exit:
invoke  Sleep,2000    ;Invoke is easier, no need to ][]][][[]]
;and make a pause for easier F9-use
invoke  ExitProcess,0

;IN: ECX=length of permutation
;OUT:All permutations to stdout
;Consider all registers trashed
proc permute_v2
mov     ebx,20202020h ;20h-7Eh
mov     edx,7E7E7E7Eh
shl     ecx,3
mov     eax,32
sub     eax,ecx
mov     ecx,eax
shr     ebx,cl
shr     edx,cl        ;Initialize boundaries ebx and edx
.loop:

bswap   ebx           ;Reformat ebx for buffer
shr     ebx,cl
mov     dword[_obuffer],ebx
shl     ebx,cl
bswap   ebx
push    eax ecx edx
cinvoke printf,_fmt,_obuffer
pop     edx ecx eax

mov     eax,ebx
mov     esi,eax
not     eax
sub     esi,0x01010101
and     eax,0x80808080
and     eax,esi
shr     eax,7
imul    eax,20h+81h

sub     ebx,81818181h
cmp     ebx,edx

jbe     .loop

ret

endp

section '.idata' import data readable writable
library KERNEL, 'KERNEL32.DLL',\
MSVCRT, 'MSVCRT.DLL'

import KERNEL,\
ExitProcess, 'ExitProcess',\
Sleep,'Sleep'

import MSVCRT,\
printf, 'printf'

_fmt     db '%s',32,32,0
_obuffer rb 8
```

_________________
My updated idol http://www.agner.org/optimize/
13 Jun 2009, 10:08
kilobyte

Joined: 07 Jun 2008
Posts: 15
kilobyte
Thanks for the critque,
1) really i do code 80 chars wide, it's only because i edited the code inside of the "post reply" input box
2) I tried setting the environment but i'm using ultraedit as texteditor, well something is broken somewhere, i guess i just need to look over it.
3) by cleaner do you mean, appealing to the eyes? because i do like the use of the brackets as it signfies getting the address of the function held at location Exitprocess, if you get what i mean, i guess it's just really based on how the import table works. It really does look cleaner tho.
4) thanks for that.
5) ok i'll keep that in mind
6) isn't that a matter of preference, but i guess it does look cleaner that way, now that i think about it, definately take that onboard.
7) yes agreed.

Thanks for your critque, all taken onboard.
13 Jun 2009, 11:04
Borsuc

Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
4) Sleep at the end of process lets you see what it printed out
Not necessarily you can put "& pause" at the end of the command line when launching it.

Code:
`someapp argument1 argument2 "argument3" & pause    `
That is, if you're using DOS/Windows, not sure about *nix.

_________________
Previously known as The_Grey_Beast
13 Jun 2009, 23:45
pal

Joined: 26 Aug 2008
Posts: 227
pal
Or you could just run it via command prompt and there will be no need for it at all.
14 Jun 2009, 10:45

Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
@Borsuc, @pal: You're talking about the same thing. Both need an extra step to open a command prompt and then execute your assembled file.

With the 4th suggestion I was easing the execution under FASMW, where you just press F9 and see the result. That is how I usually code. Much faster way to the result.
14 Jun 2009, 15:17
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum