Prime sieve and sort (x86 asm) 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&amp;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 :)
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 &amp; 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