Hilbert Curve :-D

Index > Main > Hilbert Curve :-D

Goto page Previous 1, 2, 3 Next

Author

Thread

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 12 Feb 2008, 19:03

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.

12 Feb 2008, 19:03

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 12 Feb 2008, 19:06

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.

12 Feb 2008, 19:06

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 12 Feb 2008, 19:10

Here, I pasted the new method into the old windows program:

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

12 Feb 2008, 19:10

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 12 Feb 2008, 19:20

Most Lindenmayer System seems to re-define F (forward) and I haven't accounted for that in my code. Confused

12 Feb 2008, 19:20

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 12 Feb 2008, 19:24

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

12 Feb 2008, 19:24

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 12 Feb 2008, 19:29

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
;##########################################################################

12 Feb 2008, 19:29

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 12 Feb 2008, 19:36

Julia set - some kind of fractal. Smile

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

12 Feb 2008, 19:36

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 12 Feb 2008, 19:45

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:	16638 Time(s)

12 Feb 2008, 19:45

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 13 Feb 2008, 00:38

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.

13 Feb 2008, 00:38

rugxulo

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

rugxulo 13 Feb 2008, 08:10

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

13 Feb 2008, 08:10

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 13 Feb 2008, 09:49

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.

13 Feb 2008, 09:49

rugxulo

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

rugxulo 14 Feb 2008, 18:22

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

14 Feb 2008, 18:22

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 14 Feb 2008, 19:11

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

14 Feb 2008, 19:11

rugxulo

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

rugxulo 14 Feb 2008, 19:23

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??

14 Feb 2008, 19:23

rugxulo

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

rugxulo 14 Feb 2008, 19:39

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

14 Feb 2008, 19:39

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 14 Feb 2008, 21:10

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.

14 Feb 2008, 21:10

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 16 Feb 2008, 20:08

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)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

16 Feb 2008, 20:08

DOS386

Joined: 08 Dec 2006
Posts: 1905

DOS386 18 Feb 2008, 04:14

bitRAKE wrote:

Hilbert Curve

COOL

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

18 Feb 2008, 04:14

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 18 Feb 2008, 06:39

DOS386 wrote:

32-bit DOS version ?

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)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

18 Feb 2008, 06:39

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 28 Feb 2008, 06:19

http://www.grogra.de/ - A nice bit of research and interactive software for L-systems and "growth grammars".

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

28 Feb 2008, 06:19

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