Hilbert Curve :-D

Index > Main > Hilbert Curve :-D

Goto page 1, 2, 3 Next

Author

Thread

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 10 Feb 2008, 20:28

Code:

MAX_X = 320
MAX_Y = 200
COLOR = 4 ; red

org $100
mov ax,$13
int $10

push $A000
pop es
mov di,0
mov ax,00b
mov dx,1
mov cx,6
call Hilbert

xor ax,ax
int $16

mov ax,3
int $10

mov ax,$4C00
int $21



; Hilbert curve
Hilbert:
    .order equ cx
    .direction equ ax
    ; 00 right
    ; 01 up
    ; 10 left
    ; 11 down
    .rotation equ dx
    ; 1 clockwise
    ;-1 counterclockwise
    mov byte[es:di],COLOR
.recursion:
    dec .order
    js .exit
    call .corner
    call .corner
    call .recursion
    sub .direction,.rotation
    call .step
    neg .rotation
    call .recursion
    ; preserve original values
    sub .direction,.rotation
    neg .rotation
.exit:
    inc .order
    retn

.corner:
    neg .rotation
    sub .direction,.rotation
    call .recursion
.step:
    ror .direction,2
    sbb bx,bx           ; dir&&2 ? -1 : 0
    rol .direction,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:bp+di],COLOR
    add di,bp
    mov byte[es:bp+di],COLOR
    add di,bp
    retn

Hope everyone is having a great weekend. Very Happy

10 Feb 2008, 20:28

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 10 Feb 2008, 22:16

How about writing a 32bit version. Wink

10 Feb 2008, 22:16

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 10 Feb 2008, 22:20

That is the reason for the register naming - a 32-bit version is basically the same, lol. I'm cleaning house ATM, but will post a windows version later. Had some fun playing with buggy versions - all kind of neat designs are possible.

10 Feb 2008, 22:20

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 10 Feb 2008, 22:31

bitRAKE wrote:

... a 32-bit version is basically the same ...

The windowing will make a big difference. You can't just go "int 0x10" and start plotting. Use a back buffer for redrawing, it is a lot faster that way.

10 Feb 2008, 22:31

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 11 Feb 2008, 02:35

Yeah, but I've got a library of templates for this kind of thing - plotting to a DIBSection. Just a little cut-n-paste.

Here are some colorful variations:

Description:
Filesize:	414.29 KB
Viewed:	20599 Time(s)

Description:
Filesize:	20.75 KB
Viewed:	20603 Time(s)

Description:	Windows Version	Download
Filename:	hilbertW.asm
Filesize:	3.24 KB
Downloaded:	744 Time(s)

11 Feb 2008, 02:35

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 11 Feb 2008, 03:37

How about some controls to change the various parameters and see the changes in real time. Wink

11 Feb 2008, 03:37

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 11 Feb 2008, 04:11

That would be good - can't wait to see your implementation. Laughing

(I have controls - edit code and push F9.
Hard to complete with that kind of flexiblity.)

11 Feb 2008, 04:11

DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy

DJ Mauretto 11 Feb 2008, 10:18

Bravo !
Very very good Wink

11 Feb 2008, 10:18

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 11 Feb 2008, 11:30

bitRAKE
very nice program. Smile

What about Koch snowflake? Wink

BTW, I'm curious why in the Windows version you have "mixed" procedure calling conventions ("raw" push, push, ..., push, call and invoke in the other places).

11 Feb 2008, 11:30

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 11 Feb 2008, 14:58

MHajduk wrote:

BTW, I'm curious why in the Windows version you have "mixed" procedure calling conventions ("raw" push, push, ..., push, call and invoke in the other places).

I didn't want to scroll to the data section so I did the work on the stack in the code. Ideally, I'd put all the temporary windows structures on the stack for more effective use of memory. This is what results from cut-n-paste.

Quote:

What about Koch snowflake?

I've been looking at techniques for better cache utilization and the Hilbert curve is useful in that regard, and scaleable, too.

http://www.cs.umd.edu/class/fall2005/cmsc714/Lectures/alaei-reordering.pdf
http://math.uni-graz.at/reports/archive-2005/IMA03-05.pdf

Last edited by bitRAKE on 12 Feb 2008, 01:40; edited 2 times in total

11 Feb 2008, 14:58

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 11 Feb 2008, 15:21

I think, that you are very close to write simple LOGO-like language interpreter (implementation of "turtle geometry" Wink

). Seems, that DOS version of such interpreter could be smaller than 200 bytes.

11 Feb 2008, 15:21

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 11 Feb 2008, 20:58

I'm intrigued enough to maybe do a FASM macro version. It would basically stack commands to build the recursive routine while tracking the change in variables to preserve them without saving on the stack. Hugi compo already had a similar challenge.

The color versions are not as complex as them seem. First one adds two different prime offsets to different color components (notice how little it compresses - would look good animated). While the second only rotates a constant bit pattern. Cool

11 Feb 2008, 20:58

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 12 Feb 2008, 03:38

Typically, the Hilbert curve is defined as:

Code:

L => +RF-LFL-FR+
R => -LF+RFR+FL-

Where F stands for move forward, +/- are rotation by 90 degrees.[1][2]

L and R are mirror images of each other - which leads to a simplier definition.

I've mapped the function to: L => *.LF*.LFL.F*L.*

Where * means change direction of rotation and (.) period means to rotate. L needs to be rotation & direction neutral, or fixups would be required after each L. Spliting the rotate operator allowed further optimization because the first four symbols repeat. Leading to:

Code:

L => RRL.F*L.*
R => *.LF

I still wonder if the two "L." can be combined, or a trick to execute the "F" only first time through a "L.F*" block? Resulting in L => RRSS'

12 Feb 2008, 03:38

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 12 Feb 2008, 09:39

bitRAKE wrote:

Typically, the Hilbert curve is defined as:
Code:
L => +RF-LFL-FR+
R => -LF+RFR+FL-    

I have some idea: to write simple Finite Automaton (http://board.flatassembler.net/topic.php?t=5735) interpreting strings encoded in Lindenmayer System (grammar of some formal language used to describe growth processes of plants and other organisms) given as an argument of program. It shouldn't be very complicated. Smile

12 Feb 2008, 09:39

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 12 Feb 2008, 16:25

Code:

        mov edx,NODES
        stc
.load:  lodsd
        dec ecx
        js .end
.next:  adc eax,eax
        je .load
        jc .state1
.state0:
        mov edx,[edx]
        jmp .next
.state1:
        mov edx,[edx+4]
        jmp .next

.end:   jmp [edx+8]


NODES:

Start dd S0,     S1,     EmptyLine
S0    dd S0,     S1,     Accept
S1    dd S10,    S11,    NotAccept
S10   dd S100,   S0,     NotAccept
S11   dd S1,     S10,    NotAccept
S100  dd S11,    S100,   NotAccept

12 Feb 2008, 16:25

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 12 Feb 2008, 17:10

Code:

Rule:   call [eax]
  .0:   lodsd
        test eax,eax
        jne Rule
        retn

Do_Rule:
        lodsd
        push esi
        dec [DEPTH] ; don't recurse indefinitely!
        je .0
        mov esi,eax
        call Rule.0
   .0:  pop esi
        inc [DEPTH]
        retn


RULE_L dd \
        Right,\
        Do_Rule,RULE_R,\
        Forward,\
        Left,\
        Do_Rule,RULE_L,\
        Forward,\
        Do_Rule,RULE_L,\
        Left,\
        Forward,\
        Do_Rule,RULE_R,\
        Right,\
        0

RULE_R dd \
        Left,\
        Do_Rule,RULE_L,\
        Forward,\
        Right,\
        Do_Rule,RULE_R,\
        Forward,\
        Do_Rule,RULE_R,\
        Right,\
        Forward,\
        Do_Rule,RULE_L,\
        Left,\
        0

Each rule becomes a simple data structure. Any number of rules/functions (forward/right/left) can be supported this way. Just parse the string and create the data structure. Very Happy

Last edited by bitRAKE on 12 Feb 2008, 17:26; edited 1 time in total

12 Feb 2008, 17:10

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 12 Feb 2008, 17:22

Hehe.

You were still editing your message when I was reading it. I wanted to ask if ecx contains recursion depth when you changed it to 'DEPTH' variable. Laughing

[EDIT]Yes, zero dword is necessary to stop executing 'Rule'. BTW, seems that you write (sketch) your programs directly on PC with any indirect steps (paper + pencil). Wink

Am I right?[/EDIT]

12 Feb 2008, 17:22

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 12 Feb 2008, 17:35

Yeah, I use the message board like a chat channel - very bad, sorry Tomasz.

Keeping everything is registers is best because many functions would just update common state space (works like cache in a processor, oh it is, lol). More complex functions (forward) should save what they use (or, use free registers in the minimal case).

Additional, each rule could have a different depth parameter.

Quote:

BTW, seems that you write (sketch) your programs directly on PC with any indirect steps (paper + pencil). Am I right?

I have a white board here to draw on, but usually direct coding is best. I'd rather have a broken algorithm typed in than notes on paper. Language is very flexible, but code can be like a blueprint with little doubt about what will take place.

That said, I do re-code algorithms many times: once from the data driven perpective and then from minimal data perspective; and then find a happy point somewhere in the middle.

12 Feb 2008, 17:35

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 12 Feb 2008, 17:59

bitRAKE wrote:

I have a white board here to draw on, but usually direct coding is best. I'd rather have a broken algorithm typed in than notes on paper. Language is very flexible, but code can be like a blueprint with little doubt about what will take place.

Are you an academic teacher? I don't criticize your work methods, everybody has own way of coding, of course. Smile

12 Feb 2008, 17:59

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 12 Feb 2008, 18:27

No, I'm not a teacher. I understand that more complex algorithms require a deeper level of knowledge - just jumping to the code level can have detrimental effects on the final product - some avenues for optimization might never be seen or make days of work superfluous. Sometimes I prototype in Mathematica, but often the high-level analysis has already been done.

Code:

Do_Rule:
        dec ecx
        lodsd
        je .x
        push esi
        mov esi,eax

        lodsd
  .0:   call [eax]
        lodsd
        test eax,eax
        jne .0

        pop esi
  .x:   inc ecx
        retn

...assuming a zero rule is not allowed, and ECX is depth counter.

12 Feb 2008, 18:27

Goto page 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