# 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!

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.

Enjoy :)

• If there are two or more input values that are equal and prime, should the value be output once or repeated for each occurrence in the input? e.g. if input = {3, 3, 3, 3, 3} should output be: {3} or {3, 3, 3, 3, 3} – Skizz May 30 '12 at 15:07
• Keith Randall brought up a good point in the comments, do we need to preserve the values of ebx,esi,edi at return to comply with the stdcall convention? I'll assume we do unless you want to relax that requirement. – Sir_Lagsalot May 30 '12 at 17:05
• Skizz - either way is fine. Sir_Lagsalot - Yes, they have to be preserved by the callee, as per stdcall. – Polynomial May 30 '12 at 17:18
• @Polynomial Is the program permitted to alter the input buffer? The function signature suggests that it is. – breadbox Jun 4 '12 at 3:00
• @breadbox Sure, why not? :) – Polynomial Jun 4 '12 at 10:16

## 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
ret 8
• Nice optimisation there :) – Polynomial Nov 25 '17 at 17:41

# 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
ret 8

• ebx,esi,edi are callee-save. (I'm assuming we have to adhere to stdcall in this regard.) – Keith Randall May 30 '12 at 16:35
• Good point, I've updated the code to fix that. – Sir_Lagsalot May 30 '12 at 16:48

## 41 29 instructions

The code itself, NASM syntax:

global primes
section .code
primes:
mov     esi, [esp + 32 + 4]
mov     dword [esp + 28], 0 ; primes counter
mov     ecx, [esi - 4]
jecxz   return          ; zero terminator
cmp     ecx, 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
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
xchg    ecx, [edi - 4]
cmp     ecx, [edi - 4]
jge     bubble
xchg    ecx, [edi - 4]
jmp     bubble
return:
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.

• ebx,esi,edi are callee-save. (I'm assuming we have to adhere to stdcall in this regard.) – Keith Randall May 30 '12 at 16:26
• @KeithRandall That's correct. All general purpose registers, stack registers, etc. must be preserved by the callee, as per stdcall spec. – Polynomial May 30 '12 at 17:20
• The value '9' passes your prime check. – Sir_Lagsalot May 30 '12 at 18:28
• You're right, guys, thanks. Will fix tomorrow. – Alexander Bakulin May 30 '12 at 19:55
• Fixed. Actually, improved Keith Randall's solution. – Alexander Bakulin May 31 '12 at 8:40

## 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.

• With 1000 inputs it runs much longer than 60 seconds on my Core 2 Duo. – Alexander Bakulin May 30 '12 at 10:28
• Ok, fixed. I now only test up to sqrt(n) before declaring a value prime. Takes 1/2 second for 1000 instances of 0x7fffffff. – Keith Randall May 30 '12 at 16:17

## 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.

• I think lodsd/scasd require direction flag to be cleared. – Alexander Bakulin Jun 1 '12 at 7:02
• And it's no wonder that our solutions are converging. I guess this challenge has become rather a collective hacking session than a competition. – Alexander Bakulin Jun 1 '12 at 7:04
• @AlexanderBakulin, the standard C calling convention explicitly requires functions to leave the direction flag cleared. – breadbox Jun 1 '12 at 7:09
• I would appreciate if you point me to the documentation stating it. The only mention of this requirement I could find is in some MASM Guide dated 1992. Neither Wikipedia, nor MSDN don't say a word on it. – Alexander Bakulin Jun 1 '12 at 7:50
• It's not just targeting a single language, it's also the stated problem lends itself to one solution with no neat tricks available. – Skizz Jun 1 '12 at 8:26