flat assembler
Message board for the users of flat assembler.

Index > Main > Hilbert Curve :-D

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



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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
Post 10 Feb 2008, 20:28
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
How about writing a 32bit version. Wink
Post 10 Feb 2008, 22:16
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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.
Post 10 Feb 2008, 22:20
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
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.
Post 10 Feb 2008, 22:31
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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: 9548 Time(s)

Hilbert2.PNG


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

Hilbert.PNG


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

Post 11 Feb 2008, 02:35
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
How about some controls to change the various parameters and see the changes in real time. Wink
Post 11 Feb 2008, 03:37
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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.)
Post 11 Feb 2008, 04:11
View user's profile Send private message Visit poster's website Reply with quote
DJ Mauretto



Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto
Bravo !
Very very good Wink
Post 11 Feb 2008, 10:18
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
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).
Post 11 Feb 2008, 11:30
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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
Post 11 Feb 2008, 14:58
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
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.
Post 11 Feb 2008, 15:21
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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
Post 11 Feb 2008, 20:58
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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'
Post 12 Feb 2008, 03:38
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
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
Post 12 Feb 2008, 09:39
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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    
Post 12 Feb 2008, 16:25
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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
Post 12 Feb 2008, 17:10
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Hehe. Very Happy 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]
Post 12 Feb 2008, 17:22
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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.
Post 12 Feb 2008, 17:35
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
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
Post 12 Feb 2008, 17:59
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2895
Location: [RSP+8*5]
bitRAKE
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.
Post 12 Feb 2008, 18:27
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 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.