Announcement

Collapse

Forum Rules and Etiquette

Our mission ...

This forum is part of our mission to promote the preservation of vintage computers through education and outreach. (In real life we also run events and have a museum.) We encourage you to join us, participate, share your knowledge, and enjoy.

This forum has been around in this format for over 15 years. These rules and guidelines help us maintain a healthy and active community, and we moderate the forum to keep things on track. Please familiarize yourself with these rules and guidelines.


Rule 1: Remain civil and respectful

There are several hundred people who actively participate here. People come from all different backgrounds and will have different ways of seeing things. You will not agree with everything you read here. Back-and-forth discussions are fine but do not cross the line into rude or disrespectful behavior.

Conduct yourself as you would at any other place where people come together in person to discuss their hobby. If you wouldn't say something to somebody in person, then you probably should not be writing it here.

This should be obvious but, just in case: profanity, threats, slurs against any group (sexual, racial, gender, etc.) will not be tolerated.


Rule 2: Stay close to the original topic being discussed
  • If you are starting a new thread choose a reasonable sub-forum to start your thread. (If you choose incorrectly don't worry, we can fix that.)
  • If you are responding to a thread, stay on topic - the original poster was trying to achieve something. You can always start a new thread instead of potentially "hijacking" an existing thread.



Rule 3: Contribute something meaningful

To put things in engineering terms, we value a high signal to noise ratio. Coming here should not be a waste of time.
  • This is not a chat room. If you are taking less than 30 seconds to make a post then you are probably doing something wrong. A post should be on topic, clear, and contribute something meaningful to the discussion. If people read your posts and feel that their time as been wasted, they will stop reading your posts. Worse yet, they will stop visiting and we'll lose their experience and contributions.
  • Do not bump threads.
  • Do not "necro-post" unless you are following up to a specific person on a specific thread. And even then, that person may have moved on. Just start a new thread for your related topic.
  • Use the Private Message system for posts that are targeted at a specific person.


Rule 4: "PM Sent!" messages (or, how to use the Private Message system)

This forum has a private message feature that we want people to use for messages that are not of general interest to other members.

In short, if you are going to reply to a thread and that reply is targeted to a specific individual and not of interest to anybody else (either now or in the future) then send a private message instead.

Here are some obvious examples of when you should not reply to a thread and use the PM system instead:
  • "PM Sent!": Do not tell the rest of us that you sent a PM ... the forum software will tell the other person that they have a PM waiting.
  • "How much is shipping to ....": This is a very specific and directed question that is not of interest to anybody else.


Why do we have this policy? Sending a "PM Sent!" type message basically wastes everybody else's time by making them having to scroll past a post in a thread that looks to be updated, when the update is not meaningful. And the person you are sending the PM to will be notified by the forum software that they have a message waiting for them. Look up at the top near the right edge where it says 'Notifications' ... if you have a PM waiting, it will tell you there.

Rule 5: Copyright and other legal issues

We are here to discuss vintage computing, so discussing software, books, and other intellectual property that is on-topic is fine. We don't want people using these forums to discuss or enable copyright violations or other things that are against the law; whether you agree with the law or not is irrelevant. Do not use our resources for something that is legally or morally questionable.

Our discussions here generally fall under "fair use." Telling people how to pirate a software title is an example of something that is not allowable here.


Reporting problematic posts

If you see spam, a wildly off-topic post, or something abusive or illegal please report the thread by clicking on the "Report Post" icon. (It looks like an exclamation point in a triangle and it is available under every post.) This send a notification to all of the moderators, so somebody will see it and deal with it.

If you are unsure you may consider sending a private message to a moderator instead.


New user moderation

New users are directly moderated so that we can weed spammers out early. This means that for your first 10 posts you will have some delay before they are seen. We understand this can be disruptive to the flow of conversation and we try to keep up with our new user moderation duties to avoid undue inconvenience. Please do not make duplicate posts, extra posts to bump your post count, or ask the moderators to expedite this process; 10 moderated posts will go by quickly.

New users also have a smaller personal message inbox limit and are rate limited when sending PMs to other users.


Other suggestions
  • Use Google, books, or other definitive sources. There is a lot of information out there.
  • Don't make people guess at what you are trying to say; we are not mind readers. Be clear and concise.
  • Spelling and grammar are not rated, but they do make a post easier to read.
See more
See less

QuickSort in 6502 assembler

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    QuickSort in 6502 assembler

    Originally posted by carlsson View Post
    The first attempt failed, but after changing to a different algorithm, I got QuickSort working
    Kind of. I was about to post the code, but I just found if the data to be sorted is too versatile (too big interval between smallest and largest) and at the same time already sorted, my algorithm recurses so many steps I run out of stack space and computer crashes.

    I tried to come up with a hackery solution, but so far I came up with no real good workaround. One way would be to take a copy of the whole stack elsewhere, and start a new one, but it is a bit clumsy. I tried to store only the low byte of the return address as long as I stay within the same memory page. It helped a bit, but not fully. Since the recursive calls come from only two places, maybe I can store some counter how many times the return address is valid instead of storing each return address:

    Now: ret1 ret1 ret1 ret1 ret2 ret2 ret2 ret1 ret2 ret2 ret1 end (12 bytes)
    Idea: 4 ret1 3 ret2 1 ret1 2 ret2 1 ret1 end (11 bytes)

    I could probably align the code in a way so I can smart-code the counter into the return address or at least distinguish between the two, but I'd look for a general solution. This is nothing I need to use right now, so it is far from priority, just annoying.

    Anyway, this is what I have for now. It would assemble with DASM and execute on a Commodore 64. Address $0400 equals screen matrix, so you can see the data being sorted.

    Code:
    #processor 6502
    #seg main
     
    array eqm $0400 ; $c100
    larec eqm $c200
    rarec eqm $c300
    crec eqm $fa
    ktmp eqm $fb
    lval eqm $fc
    left eqm $fd
    right eqm $fe
     
              org $0900
     
              lda #$00
              sta crec
              tax
              sta larec,x
              lda #$ff
              sta rarec,x
              jsr quick
              rts
     
    quick:    ldx crec
              lda rarec,x
              sta right 
              lda larec,x
              sta left
              inc crec
     
              tax                 ; left
              cpx right
              bcs qout$           ; if left >= right exit
              ldy right           
              lda array,y
              cmp array,x         ; if d[left] > d[right]
              bcs bprep$
              jsr swap
    bprep$:   lda array,x         ; repeat
              sta lval
    prep$:    lda lval
    loop$:    cpx right
              beq loop2$
              inx
              cmp array,x         ;   repeat j=j+1 until d[left] <= d[j]
              beq loop2$
              bcs loop$
    loop2$:   cpy left
              beq uloop2$
              dey
              cmp array,y         ;   repeat k=k-1 until d[left] >= d[k]
              bcc loop2$
    uloop2$:  sty ktmp
              cpx ktmp            ;   if k >= j
              php
              bcs uloop1$
              jsr swap
    uloop1$:  plp
              beq prep$
              bcc prep$
    uprep$:   ldx left
              jsr swap
     
              ldx crec
              lda left
              sta larec,x
              cpy left
              php
              dey
              tya
              sta rarec,x
              plp
              bcc no1st$
              beq no1st$
              jsr quick           ; jsr
    no1st$:   ldx crec
              ldy rarec,x
              iny
              iny
              tya
              sta larec,x
              lda rarec-1,x       ; lda right
              sta rarec,x
              jsr quick
    qout$:    dec crec
              rts
     
    ;; swap takes x/y as index to the two values to swap
    swap:     lda array,x
              pha
              lda array,y
              sta array,x
              pla
              sta array,y
              rts
    To make it worse (?), I have another code written by someone else that is about the same in size, but functions better. It overcomes the recursive calls, which is something I'd like to do as well. I have some iterative implementation of QuickSort in a C book, but I never was successful to convert it into 6502. Maybe that's the desired approach anyway; stay away from recursion on small platforms.
    Anders Carlsson
Working...
X