Prime sieve and sort (x86 asm)

Question

Your challenge is to write a routine, in x86 assembly, which takes a buffer containing 32-bit signed integers and writes a sorted list of the prime values to another buffer, then returns the number of values written to the output buffer. The winning solution is the one that uses the least instructions.

Here's a pseudo-C example of the process:

int __stdcall SortedPrimes(DWORD* input, DWORD* output)
{
    int ctr_in = 0;
    int ctr_out = 0;
    int val = 0;
    // copy primes to output buffer
    while((val = input[ctr_in]) != 0)
    {
        ctr_in++;
        if(isPrime(val))
            output[ctr_out++] = val;
    }
    // you must implement this sort, too!
    sort(output);
    return ctr_out;
}

// for testing/illustration purposes only
// you don't need to implement this part!
void test()
{
    int count = 0;
    int i = 0;
    int v = 0;

    // allocate buffers
    DWORD* input = (DWORD*)calloc(1024, sizeof(DWORD));
    DWORD* output = (DWORD*)calloc(1024, sizeof(DWORD));

    // fill input buffer with data
    input[0] = 0x12345678;
    input[1] = 0x57AC0F10;
    ...
    input[1022] = 0x13371337;
    input[1023] = 0; // terminating value is zero!

    // invoke your function! :]
    count = SortedPrimes(input, output);

    // dump output
    printf("Found %n primes.\n", count);
    while((v = output[i++]) != 0)
        printf("0x%x\n", v);

    free(input);
    free(output);
}

Rules:

• Assume a modern Intel CPU (e.g. Core i3) running in x86-32 mode.
• Assume __stdcall, i.e. parameters pushed from right to left, esp+4 is a pointer to input, esp+8 is a pointer to output, callee is responsible for cleaning stack.
• You cannot call any APIs or library functions - the solution must be in pure assembly.
• The input buffer consists of 32-bit non-zero signed integers, followed by 0x00000000.
• The output buffer is allocated and zero'd before being passed to the function, and its size is the same as the input buffer.
• Assume there are no negative inputs, i.e. the range is 0x00000001 to 0x7FFFFFFF.
• The sort must be lowest to highest, such that output[0] is the lowest value in the list.
• Must give an empty output buffer when given an empty input buffer.
• Must properly handle cases where all values are prime / no values are prime.
• You may not use compiler macros.
• The code must be able to process 1000 inputs in 60 seconds or less.
• I'll accept answers in AT&T syntax, but I'd prefer Intel syntax for uniformity.
• Winner is the code that has the least number of instructions (i.e. lowest number of lines of code), not the least number of characters.

Assembly is pretty terse, so please add comments to your code where necessary.

Enjoy :)

Answer 1

26 instructions

I found this task for the first time only yesterday. sigh.

I took @Sir_Lagsalot's code and removed one xchg. The changes are too significant for a comment, so I've placed it here for review.

    pushad
    mov     ecx, -1              ; will zero output count and position using next instruction
count_prime:
    inc     ecx                  ; increment output & count if prime
    mov     esi, [esp + 8+32]    ; load output array
find_smallest:
    mov     eax,-3               ; 0xfffffffd is larger than any valid input
    mov     edi, [esp + 4+32]    ; load input array
    db      3dh, 50h             ; mask next instruction on first pass
find_smallest_loop2:
    xchg    eax,[edi-4]          ; swap ecx with values that are smaller, values
                                 ; get replaced with 0xfffffffd as they are used
find_smallest_loop:
    scasd
    jbe     find_smallest_loop
    mov     ebx,1                ; ebx is divisor, will start it at 2 later
                                 ; but we need 1 right now
    cmp     [edi-4],ebx
    je      find_smallest        ; skip inputs of 1
    ja      find_smallest_loop2  ; exit loop if a 0 is reached
    mov     [esi+ecx*4],eax      ; store value in next output position
test_next_divisor:               ; primality test
    mov     eax,[esi+ecx*4]
    cdq                            
    inc     ebx                  ; 2+
    idiv    ebx                  ; use signed division
    cmp     eax,ebx
    jb      count_prime
    test    edx,edx
    jz      find_smallest   
    jns     test_next_divisor    ; exit if remainder is negative
exit_function:
    mov     [esp+28],ecx         ; move count to eax position
    popad
    ret 8

Answer 2

32 30 29 28 27 Instructions

Changed my algorithm so we're not all trying to implement the same thing, and it's a little smaller than my earlier attempt. The code repeatedly searches through the input array, finding the smallest value, and replacing it with 0xfffffffd. It then tests if the found value is prime and outputs it if so. The code exits when the input has been completely replaced with 0xfffffffd.

    pushad
    mov     ecx, 0              ; zero output count and position
    mov     esi, [esp + 8+32]   ; load output array
find_smallest:
    mov     eax,-3              ; 0xfffffffd is larger than any valid input
    mov     edi, [esp + 4+32]   ; load input array
find_smallest_loop:
    scasd
    jbe     find_smallest_loop
    xchg    eax,[edi-4]          ; swap ecx with values that are smaller, values
                                 ; get replaced with 0xfffffffd as they are used
    cmp     eax,1                 
    je      find_smallest        ; skip inputs of 1
    ja      find_smallest_loop   ; exit loop if a 0 is reached
    xchg    eax,[edi-4]          ; swap 0 with lowest value found
    mov     [esi+ecx*4],eax      ; store value in next output position
    mov     ebx,2                ; ebx is divisor, start it at 2
test_next_divisor:               ; primality test
    mov     eax,[esi+ecx*4]
    cdq                            
    idiv    ebx                  ; use signed division
    cmp     eax,ebx
    cmovb   edx,[edi-4]          ; zero edx if prime to exit loop later on
    adc     ecx,0                ; increment output & count if prime
    inc     ebx
    test    edx,edx
    jz      find_smallest   
    jns     test_next_divisor    ; exit if remainder is negative
exit_function:
    mov     [esp+28],ecx         ; move count to eax position
    popad
    ret 8

Answer 3

41 29 instructions

The code itself, NASM syntax:

global primes
    section .code
primes:
    pushad
    mov     esi, [esp + 32 + 4]
    mov     dword [esp + 28], 0 ; primes counter
read:
    add     esi, 4
    mov     ecx, [esi - 4]
    jecxz   return          ; zero terminator
    cmp     ecx, 1
    je      read            ; omit 1
    mov     ebx, 2          ; initial divisor
try_divisor:
    mov     eax, ecx        ; get original number from ecx
    mov     edx, 0
    div     ebx             ; divide
    cmp     ebx, eax
    jg      save            ; divisor exceeds sqrt(n), so n is prime
    cmp     edx, 0
    je      read            ; not prime
    inc     ebx             ; next divisor
    jmp     try_divisor
save:                        ; prime number to store is in ecx
    inc     dword [esp + 28] ; increase prime counter
    mov     edi, [esp + 32 + 8]
bubble:                     ; insert prime into output array
    add     edi, 4
    xchg    ecx, [edi - 4]
    jecxz   read
    cmp     ecx, [edi - 4]
    jge     bubble
    xchg    ecx, [edi - 4]
    jmp     bubble
return: 
    popad
    ret     8

I borrowed a lot from Keith Randall's solution, but improved prime saving code. So, I guess, my code should be out of competition since it's not completely mine.

Answer 4

35 31 instructions

        .globl  _primesort
_primesort:
        pushal
        mov     36(%esp),%esi           # load input ptr
        mov     40(%esp),%edi           # load output ptr
        movl    $0,28(%esp)             # count primes in saved eax slot
inputloop:
        add     $4,%esi
        cmp     $1,-4(%esi)
        jl      return                  # 0 = input end marker
        je      inputloop               # special case for 1
        mov     $2,%ecx                 # trial divisor
testloop:
        mov     -4(%esi),%eax
        mov     $0,%edx
        div     %ecx
        cmp     %ecx,%eax
        jl      saveprime               # n/d < d => d > sqrt(n) => no more trial division
        cmp     $0,%edx
        je      inputloop               # found a divisor
        inc     %ecx                    # next trial divisor
        jmp     testloop
saveprime:
        mov     -4(%esi),%eax           # prime
        mov     28(%esp),%ecx           # index of new last element
        jecxz   storeprime              # at start of output array, just store it
bubbledown:
        cmp     %eax,-4(%edi,%ecx,4)
        jl      storeprime              # found spot to store it
        mov     -4(%edi,%ecx,4),%edx
        mov     %edx,(%edi,%ecx,4)      # move larger element up one
        loop    bubbledown              # repeat until start of output array
storeprime:
        mov     %eax,(%edi,%ecx,4)
        incl    28(%esp)
        jmp     inputloop
return:
        popal
        ret

This code is AT&T syntax, and it uses cdecl instead of stdcall, but I think the only difference for the latter would be to replace the ret with ret 0x8.

Answer 5

28 instructions

Build with nasm -f elf32:

BITS 32
GLOBAL sortedprimes

;; int sortedprimes(int const *input, int *output)
;; Read a zero-terminated list of numbers from input. Copy only the prime
;; numbers to the buffer output, returning the count of numbers so
;; copied. The numbers in output are returned in sorted order.

sortedprimes:

;; Within this function:
;; eax = the number currently being tested for primality;
;; ecx = the potential divisor being tested;
;; esi = the pointer to the next number to test for primality;
;; edi = a pointer into the output buffer; and
;; (eax on the stack) = how many numbers are in the output buffer.

;; Initialize the return value to zero, and point esi at the input buffer.

                xor     eax, eax
                pusha
                mov     esi, [byte esp + 36]

;; Retrieve the next number to be tested. If the number is one, it is
;; skipped. If the number is zero, the program has reached the end of
;; the buffer and exits. Otherwise the program starts testing
;; potential divisors, starting with 2.

.nextnumber:    lodsd
                mov     ecx, 2
                cmp     eax, byte 1
                jz      .nextnumber
                jns     .divloop
                popa
                ret     8


;; Divide the number by a candidate divisor. If the quotient is less
;; than the candidate, the list of; potential divisors has been
;; exhausted, and the program jumps forward. If the remainder is
;; zero, however, then the number is composite, and it is discarded
;; and the program jumps back to get the next number. If neither is
;; true, then ecx is incremented and the next candidate is tested.

.divloop:       xor     edx, edx
                div     ecx
                cmp     eax, ecx
                mov     eax, [byte esi - 4]
                jl      .prime
                inc     ecx
                or      edx, edx
                jnz     .divloop
                jmp     short .nextnumber

;; eax contains a prime. The count of primes is incremented, and eax
;; is temporarily placed into the output buffer at the initial position,
;; displacing whatever number was already there. This number is then
;; restored, edi is advanced and eax displaces the number at at the
;; next position. Thus continues until (a) a number higher than eax
;; is reached, in which case it is left there and the displaced
;; number is left in eax, to become the displacing number going
;; forward, or (b) the end of the list is reached, in which case the
;; last number displaced is just zero-padding, and it is discarded as
;; the program jumps back to test the next input number.

.prime:         inc     dword [byte esp + 28]
                mov     edi, [byte esp + 40]
.insertloop:    xchg    eax, [edi]
                or      eax, eax
                jz      .nextnumber
                scasd
                jg      .insertloop
                xchg    eax, [byte edi - 4]
                jmp     short .insertloop

@Sir_Lagsalot is right that all of our solutions are starting to look the same. I was actually a bit dismayed when I finally read Alexander Bakulin's solution at how closely it resembled my own. I guess that's a side effect of targeting the challenge to a single language/platform.