← Back to context

Comment by kragen

1 year ago

That's not quicksort, though, because it's not in place; the actual quicksort on that page is in https://stackoverflow.com/a/7833043, which is 11 lines of code. That's still pretty concise. My own preferred concise, or at least terse, presentation of quicksort is http://canonical.org/~kragen/sw/dev3/paperalgo#addtoc_20.

How long would a quicksort (say, of integers) be in 68000 assembly? Maybe 20 lines? My 68000 isn't very good. The real advantage of writing it in Haskell is that it's automatically applicable to anything that's Ord, that is, ordered.

4 comments

kragen

Reply
duskwuff  1 year ago

> How long would a quicksort (say, of integers) be in 68000 assembly?

About 70 lines, once you strip out the comments and blank lines.

https://github.com/historicalsource/supermario/blob/9dd3c4be...

  • kragen  1 year ago

    This is great, thanks! I was thinking it could be much simpler, but it looks like I was mistaken.

    I'm trying to code up a version in ARM assembly to compare, and it looks like it'll be about 30 lines; when I get that working I can compare to see why the difference. In some ways the 68000 is more expressive than ARM, like being able to reference memory directly, even twice in one instruction.

    (Am I misunderstanding this, or is this the source code to Apple System 7.1? There seems to have been a mailing list about this codebase from 02018 to 02021: https://lists.ucc.gu.uwa.edu.au/pipermail/cdg5/)

    • kragen  1 year ago

      Here's a quicksort in 20 lines of ARM assembly, sorting an array of integers in memory starting at [r0] and ending at [r1] (i.e., inclusive bounds):

          quirks: push {r4, r5, r6, lr}
        4:  subs r2, r0, r1
            bhs 3f                  @ Exit if carry set (no borrow).
            mov r5, r1              @ This frees up r1 as a temp.

            mov r6, r0
            ldr r3, [r5]

        1:  ldr r4, [r5, r2]
            cmp r4, r3         @ Is element at r2 ≤ pivot?
            bgt 2f             @ If so, swap elements at r2 and r6,
            ldr r1, [r6]       @ Load previously first element in > side,
            str r4, [r6], #4   @ and postincrement r6,
            str r1, [r5, r2]   @ and save previous element at end of > side.
        2:  adds r2, #4        @ Increment offset.  Reached the end (>0)?
            ble 1b   @ Loop if ≤ 0 (either N && !V && !C, or !N && V && C)

            subs r1, r6, #8
            bl quirks               @ Recursively sort left partition.

            mov r0, r6
            mov r1, r5
            b 4b                  @ Tail-recursively sort right partition.

        3:  pop {r4, r5, r6, pc}

      Fully commented source with Makefile and test C program at http://canonical.org/~kragen/sw/dev3/quicksort.S.

    • duskwuff  1 year ago

      > Am I misunderstanding this, or is this the source code to Apple System 7.1?

      More or less, yes. It only encompasses the system (i.e. not applications like the Finder) and isn't entirely complete, but it's still a great window into the world of Apple pre-OS X.

      > There seems to have been a mailing list about this codebase from 02018 to 02021: https://lists.ucc.gu.uwa.edu.au/pipermail/cdg5/

      This mailing list was for a set of projects which focused on taking this code dump (among other things) and making it compile, ideally to reproduce released binaries.

      https://github.com/elliotnunn/cdg5