flat assembler
Message board for the users of flat assembler.

Index > Main > Hilbert Curve :-D

Goto page Previous  1, 2, 3  Next
Author
Thread Post new topic Reply to topic
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Shouldn't there be
Code:
Do_Rule:
        dec ecx
        lodsd
        test eax, eax
        je .x 

        (...)
    
('test eax, eax' after first 'lodsd')? If I know correctly 'lodsX' doesn't affect flags.
Post 12 Feb 2008, 19:03
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Need to use a direct CALL EAX instead of CALL [EAX]. Confused I started out using a table based method then switched to using LODS to reduce the size.

Do_Rule always has one parameter at ESI - it must be the address of a rule array - can never be zero. Also a rule: RULE_X dd 0 - is not allowed.
Post 12 Feb 2008, 19:06
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Here, I pasted the new method into the old windows program:


Description: General rule plotter
Download
Filename: hilbertW2.asm
Filesize: 3.5 KB
Downloaded: 183 Time(s)

Post 12 Feb 2008, 19:10
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Most Lindenmayer System seems to re-define F (forward) and I haven't accounted for that in my code. Confused
Post 12 Feb 2008, 19:20
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Works fine. Smile

I think, that it would be ideal to put out the rules from the program body and create some kind of rules interpreter. Now it's built-in. There should be some automaton which interprets some kind of byte code of virtual machine. Smile
Post 12 Feb 2008, 19:24
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Enter the Dragon!
Code:
;##########################################################################
; . => FX
; X => X+YF+
; Y => -FX-Y

macro Dragon {
        DIRECTION equ edx
        COLOR = $00FF00 ; green

        pushad
        mov edi,[pvBits]
        lea edi,[edi+4*(MAX_X*(2*MAX_Y/3)+MAX_X/2)]
        push RULE_DRAGON
        mov esi,esp
        mov ecx,15
        mov DIRECTION,0
        mov dword [edi],COLOR
        call Do_Rule
        pop esi
        popad
}

RULE_DRAGON dd \
        Forward,\
        Do_Rule,RULE_X,\
        0

RULE_X dd \
        Do_Rule,RULE_X,\
        Right,\
        Do_Rule,RULE_Y,\
        Forward,\
        Right,\
        0
RULE_Y dd \
        Left,\
        Forward,\
        Do_Rule,RULE_X,\
        Left,\
        Do_Rule,RULE_Y,\
        0
;##########################################################################    
Post 12 Feb 2008, 19:29
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Julia set - some kind of fractal. Smile


Description: "Dragon" vel Julia set.
Filesize: 5.7 KB
Viewed: 5255 Time(s)

Dragon.png


Post 12 Feb 2008, 19:36
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Forward advances two pixels when normally only one is used - this was done to see the path of the space filling curve.


Description:
Filesize: 5.38 KB
Viewed: 5252 Time(s)

dragon.GIF


Post 12 Feb 2008, 19:45
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Well, since this is the DOS section:
Code:
; LSYS - L-system or Lindenmayer system
; -------------------------------------
;
; Command line:
;    LSYS # {rule} {rule} ...
;
;        # - depth of recursion
;   {rule} - {letter}:{def}
;    {def} - {rule letter},+,-,F
;
; Examples:
;
;    Hilbert Curve:
;       LSYS.COM 6 R:-LF+RFR+FL- L:+RF-LFL-FR+
;
; separate parameters with space
; last rule gets executed
; no error checking

org $100
MAX_X = 320
MAX_Y = 200 
COLOR = 4 ; red 

    mov si,$81
    lodsb
    sub al,"0"
    mov cl,al       ; depth count
    jmp .0
.new:
    xor ax,ax
    stosw
.0: lodsb
    sub al," "
    jc .end         ; end of string
    je .0

    shl ax,8
    mov di,ax       ; rule pointer

    lodsb
    cmp al,":"
    jne ERROR

.1: lodsb
    sub al," "
    jc .end
    je .new

.2: cmp al,"+" - " "
    mov bx,Right
    je .terminal

    cmp al,"-" - " "
    mov bx,Left
    je .terminal

    cmp al,"F" - " "
    mov bx,Forward
    je .terminal

    mov bl,al
    shl bx,8
    mov ax,Do_Rule
    stosw
.terminal:
    mov [di],bx
    scasw
    jmp .1

.end:
    xor ax,ax
    stosw           ; insure terminate on last rule

    mov ax,$13
    int $10

    mov ax,di
    mov si,di
    mov al,0
    stosw

    push $A000
    pop es
    mov di,0
    cwd ; mov dx,0
    mov byte[es:di],COLOR
    push DONE

Do_Rule:
    dec cx
    lodsw
    js .x
    push si
    mov si,ax
    lodsw
.0: call ax
.1: lodsw
    test ax,ax
    jne .0
    pop si
.x: inc cx
    retn

Right:
    inc dx
    retn

Left:
    dec dx
    retn

Forward:
    ror dx,2
    sbb bx,bx         ; dir&&2 ? -1 : 0
    rol dx,2
    sbb bp,bp         ; dir&&1 ? -1 : 0

    and bp,MAX_X-1    ; dir&&1 ? MAX_X-1 : 0
    inc bp            ; dir&&1 ? MAX_X : 1

    xor bp,bx         ; conditional negate
    sub bp,bx         ; based on dir&&2

    mov byte[es:di+bp],COLOR
    add di,bp
    retn

DONE: ; graceful exit
    xor ax,ax
    int $16

    mov ax,3
    int $10
ERROR:
    mov ax,$4C00
    int $21    
Works in the debugger, but Windows is screwing with the commandline! Confused
It can be made much smaller...currently 166 bytes.

Dragon curve:
Code:
LSYS ? A:-FB-A B:B+AF+ C:DD D:EE E:GG G:HH H:FF I:+CCC-CCCC+B    
Maybe, make a lowercase "F" result in forward movement without drawing.
Post 13 Feb 2008, 00:38
View user's profile Send private message Visit poster's website Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
Code:
    mov byte[es:di+bp],COLOR 
    add di,bp
    


Why not just do this? (just a tired thought ...):

Code:
    add di,bp
    mov byte [es:di],COLOR
    


... and this:

Code:
    mov al,3        ; AL instead of AX saves a byte
    int $10
    


(EDIT) ... and this:

Code:
;    mov bl,al 
;    shl bx,8
    mov bh,al      ; saves a byte
    xor bl,bl 
    


Very interesting project (even if theoretically way beyond me). Very Happy
Post 13 Feb 2008, 08:10
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Thank you for taking a look at the code. With your help it's down to 150 bytes. I believe ~128 bytes should be possible, but would require some serious effort/restrictions. For example, $150 + ('+' or '-') is equal to the routine offset. Could place the Forward routine at offset $150 and then add the +/- character if they match. Change the 'F' to a 'P' ($50) and we're closing in. Introduce some branching in the Forward routine should save a couple. Shoot, a lookup table would be smaller.
Post 13 Feb 2008, 09:49
View user's profile Send private message Visit poster's website Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
Oops, "mov al,3" doesn't work because AH is modified by int 16h (EDIT: if you care what it returns). But here's some other changes (which you probably already caught if you're at 150 bytes already):

Code:
***** lsys.old
    xor ax,ax
    stosw
    mov ax,$13
    int $10
***** LSYS.ASM
    xor ax,ax
    stosw
    mov al,$13         ; AH is already 0, so this saves a byte
    int $10
*****

***** lsys.old
    pop es
    mov di,0
    cwd ; mov dx,0
***** LSYS.ASM
    pop es
    xor di,di            ; saves a byte, plus two more for "jne ERROR" !
    cwd ; mov dx,0  ; (FASM previously made it a near "0Fh" jump!)
*****

***** lsys.old
    push si
    mov si,ax
    lodsw
***** LSYS.ASM
    push si
    xchg si,ax         ; saves a byte (since AX is overwritten anyways)
    lodsw
*****
    


Last edited by rugxulo on 14 Feb 2008, 19:25; edited 1 time in total
Post 14 Feb 2008, 18:22
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
hard to believe I missed that last one - good work

Here is the current incarnation - it's 159 bytes, but I added the lowercase "f" feature:
Code:
; LSYS - L-system or Lindenmayer system
; -------------------------------------
;
; Command line:
;    LSYS # {rule} {rule} ...
;
;        # - depth of recursion
;   {rule} - {letter}:{def}
;    {def} - {rule letter},+,-,F
;            F - draw forward
;            f - step forward w/o drawing
;
; Examples:
;
;    Hilbert Curve:
;       LSYS.COM 6 R:-LFF+RFFR+FFL- L:+RFF-LFFL-FFR+
;
;    Dragon Curve:
;       LSYS.COM ? A:-FB-A B:B+AF+ C:DD D:EE E:GG G:HH H:ff I:+CCC-CCCC+B
;
; separate parameters with space
; last rule gets executed
; no error checking

org $100
MAX_X = 320
MAX_Y = 200 
COLOR = 4 ; red 

    mov si,$81
    lodsb
    sub al,"0"
    mov cl,al       ; depth count
    jmp .0
.new:
    xor ax,ax
    stosw
.0: lodsb
    sub al," "
    jc .end         ; end of string
    je .0

    imul di,ax,256  ; rule pointer
    lodsb
    cmp al,":"
    jne ERROR

.1: lodsb
    sub al," "
    jc .end
    je .new

.2: cmp al,"+" - " "
    mov bx,Right
    je .terminal

    cmp al,"-" - " "
    mov bl,Left and $FF
    je .terminal

    cmp al,"F" - " "
    mov bl,Draw and $FF
    je .terminal

    cmp al,"f" - " "
    mov bl,Step and $FF
    je .terminal

    mov bl,Do_Rule and $FF
    shl ax,8
    xchg ax,bx
    stosw
.terminal:
    mov [di],bx
    scasw
    jmp .1

.end:
    xor ax,ax
    stosw           ; insure terminate on last rule

    mov si,di
    mov [di],di
    stosb
    mov di,ax

    mov al,$13
    int $10

    push $A000
    pop es
    cwd ; mov dx,0
    mov byte[es:di],COLOR
    call Do_Rule
; graceful exit
    xor ax,ax
    int $16
    mov al,3
    int $10
ERROR:
    retn
;    mov ax,$4C00
;    int $21




Do_Rule:
    dec cx
    lodsw
    js .x
    push si
    xchg ax,si
    lodsw
.0: call ax
.1: lodsw
    test ax,ax
    jne .0
    pop si
.x: inc cx
    retn

Right:
    inc dx
    retn

Left:
    dec dx
    retn

Draw:
    call Step
    mov byte[es:di],COLOR
    retn

Step:
    ror dx,2
    sbb bx,bx         ; dir&&2 ? -1 : 0
    rol dx,2
    sbb bp,bp         ; dir&&1 ? -1 : 0
    and bp,MAX_X-1    ; dir&&1 ? MAX_X-1 : 0
    inc bp            ; dir&&1 ? MAX_X : 1

    xor bp,bx         ; conditional negate
    sub bp,bx         ; based on dir&&2

    add di,bp
    retn    
Post 14 Feb 2008, 19:11
View user's profile Send private message Visit poster's website Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
Code:
    mov bl,Do_Rule and $FF
    shl ax,8             ; 3 bytes while "XCHG AH,AL" is 2
    xchg ax,bx 
    


Code:
    mov si,di
    mov [di],di         ; store a word?
    stosb                 ; overwrite a byte of previous word written??
    
Post 14 Feb 2008, 19:23
View user's profile Send private message Visit poster's website Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
Quote:

Works in the debugger, but Windows is screwing with the commandline!


Did you fix this? It may be incorrectly assumed that AH=0 at startup. (Just a guess.)

BTW, this only occurs once, so you could probably "inline" it:

Code:
    call Step
    
Post 14 Feb 2008, 19:39
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
rugxulo wrote:
Code:
    mov bl,Do_Rule and $FF
    shl ax,8             ; 3 bytes while "XCHG AH,AL" is 2
    xchg ax,bx 
    


Code:
    mov si,di
    mov [di],di         ; store a word?
    stosb                 ; overwrite a byte of previous word written??
    
On that first one, the address of the rule needs to be stored after the pointer to Do_Rule. Currently, AX is setup with rule pointer - which starts on a $100 boundary for simplicity. Then this exchanged with BX which is the pointer to Do_Rule. This makes the fall through possible and doesn't rely on AH being zero. Your suggestion only works if AH is zero - which it might be the first time through, but definitely not the second time.

Yeah, little tricky there: remember that rule pointers are $100 aligned and DI points to somewhere in the last rule $AAxx. By zeroing the low byte the pointer points to the rule head. Do_Rule requires [SI] to be a rule to execute.

Alternately, if AX can be loaded with the rule head and count+1 is okay then jumping into Do_Rule (at the PUSH SI) would work. But I'm not happy with command line interface like that. It is bad enough depth 15 requires putting "?" for the count. Maybe it makes more sense though because depth 0 seems lame, and I'd like to remove the single pixel (mov byte[es:di],COLOR) write to save more bytes. Smile

No, it still doesn't work in windows. If I just print the command line nothing is there - I don't know wtf windows is doing. Using the Insight debugger works perfect. I'll save you the rant, but it did cost me some wasted time and stirred doubts about the functionality of the code - damn, I hate that.

Oh, "Step" can't be inlined because it's needed for the rule construction. If we remap the symbols: F=>SD and f=>S (S for Step and D for Draw); then the call could just be removed and all the rules adjusted. But this severely obfuscates the L-System. revolution, is right about needing a real-time generator to gain an intuitive understanding of the language.
Post 14 Feb 2008, 21:10
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
The more L-Systems example I look at it becomes clear that F/f need to be redefinable. So, the easy solution is to set F/f to RET and when they are used Do_Rule still calls their Draw/Step functions. But the functions are changed to call F/f rule first and only step or draw on return. It keeps the current functionality while adding flexiblity for all published L-Systems that I'm aware of.

_________________
¯\(°_o)/¯ unlicense.org
Post 16 Feb 2008, 20:08
View user's profile Send private message Visit poster's website Reply with quote
DOS386



Joined: 08 Dec 2006
Posts: 1901
DOS386
bitRAKE wrote:
Hilbert Curve


COOL Shocked

Quote:
How about writing a 32bit version.


32-bit DOS version ? Wink

_________________
Bug Nr.: 12345

Title: Hello World program compiles to 100 KB !!!

Status: Closed: NOT a Bug
Post 18 Feb 2008, 04:14
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
DOS386 wrote:
32-bit DOS version ? Wink
If you have a plotter app template I'll gladly shoe-horn the code in - nothing you couldn't do yourself. I've putting a little thought into creating a really lazy (ie minimal effort) realtime generator. It's tricky to provide functionality without coding a bunch of safety clauses.

Currently, I think it's best to store the coordinates and then automatically center/size them to the screen. Putting clipping code within the L-System plotter would be horribly restrictive and slow. Storing a massive number of points could really slow down, too.

_________________
¯\(°_o)/¯ unlicense.org
Post 18 Feb 2008, 06:39
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
http://www.grogra.de/ - A nice bit of research and interactive software for L-systems and "growth grammars".

_________________
¯\(°_o)/¯ unlicense.org
Post 28 Feb 2008, 06:19
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3  Next

< 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


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.