Recursion/Looping Problem

Index > Main > Recursion/Looping Problem

Author

Thread

kilobyte

Joined: 07 Jun 2008
Posts: 15

kilobyte 07 Jun 2009, 17:34

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 07 Jun 2009, 20:59

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! Wink

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 07 Jun 2009, 21:09

Check out permutation generators. Combinations are different.

07 Jun 2009, 21:09

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 07 Jun 2009, 21:21

Seems I'm going to be one of those happy persons Razz

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]
      add     esp, 4

.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]
      add     esp, 4*2

      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 07 Jun 2009, 21:49

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 07 Jun 2009, 21:56

@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 12 Jun 2009, 14:52

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
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 12 Jun 2009, 15:10

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 12 Jun 2009, 23:50

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'

section '.data' data readable writeable
_fmt     db '%s',13,10,0
_obuffer rb 8

section '.code' code readable executable
  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
        add cl,dl
        cmp cl,7Eh
        je exit
        ret
    print:
        pushad
        cinvoke printf,_fmt,_obuffer
        popad
        ret
    exit:
        pop edx
        pop ebx
        ret  
     
  endp

section '.idata' import data readable
 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

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 13 Jun 2009, 10:08

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
section '.code' code readable executable
  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
        add     cl,dl
        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

section '.idata' import data readable
 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 Very Happy

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'

section '.code' code readable executable
  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

        add     ebx,81818181h ;The "magic"!
        add     ebx,1
        mov     eax,ebx
        mov     esi,eax
        not     eax
        sub     esi,0x01010101
        and     eax,0x80808080
        and     eax,esi
        shr     eax,7
        imul    eax,20h+81h
        add     ebx,eax

        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 Very Happy

http://www.agner.org/optimize/

13 Jun 2009, 10:08

kilobyte

Joined: 07 Jun 2008
Posts: 15

kilobyte 13 Jun 2009, 11:04

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: 2465
Location: Bucharest, Romania

Borsuc 13 Jun 2009, 23:45

Madis731 wrote:

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 14 Jun 2009, 10:45

Or you could just run it via command prompt and there will be no need for it at all.

14 Jun 2009, 10:45

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 14 Jun 2009, 15:17

@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

< Last Thread | Next Thread >

Forum Rules:

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