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+4is a pointer toinput,esp+8is a pointer tooutput, 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
0x00000001to0x7FFFFFFF. - 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 :)
