Computer Assembly/Architecture. Explain which two programs work with prime numbers and which two programs work with square numbers looking at the program assembly code below and explaining why.

Question

Computer Assembly/Architecture. Explain which two programs work with prime numbers and which two programs work with square numbers looking at the program assembly code below and explaining why.

There are two programs that work with prime numbers, and two programs that work with square numbers. For each number sequence, one of the programs will fill in an array of 100 quadword integers with the first 100 numbers in the sequence; the other program will fill in an array of 100 bytes with booleans indicating which of the numbers up to 100 is a member of the sequence. For example, the first-100-primes program will fill in an array of quadwords with 2, 3, 5, 7, …, while the primes-up-to-100 program will fill in an array of bytes with 0, 0, 1, 1, 0, 1, 0, 1, … (notice that the 1s are at indices 2, 3, 5, 7, …).

The task is to figure out which program is which, using the debugger. Don’t care a lot that you tell me which is which correctly; what is important is that you show the steps you went through in the debugger and your reasoning about which is which. These programs were compiled from C programs; I have taken care that the names of the files and the names of symbols won’t be a giveaway, but I have neither stripped the symbol tables (which would make it harder) nor added debugging symbols (which would make it easier).

Use the script program to record your debugging sessions. First, within the Environment, run script. It will say something like “Script started, file is typescript”. Proceed to run gdb and explore one of the programs. When you are done and have exited gdb, also exit the shell with exit or by pressing control-d. You should see “Script done, file is typescript”. There should now be a file named typescript that has a complete log of your debugging session.

Put together a document that explains your belief about which program is which, and why, with supporting evidence from typescripts recorded from debugging. You will not get credit for an answer that says which programs are which correctly but does not include evidence from the debugger. You can use the disas command (e.g. disas main) in the debugger to see the machine code as assembly code, as well as the other debugging techniques we discussed for previous assignments.

If in the disassembly you encounter instructions you are not familiar with, stop and look them up and figure out what the code is doing. You could probably figure out which program is which just by looking at how each one fills in its array, but it’s worth even more credit if you can reverse engineer how the programs are doing their work and sketch the algorithms in your document.

ProgC:

Dump of assembler code for function main:

  0x00000000000005fa <+0>: push %rbp

  0x00000000000005fb <+1>: mov %rsp,%rbp

  0x00000000000005fe <+4>: movq $0x0,-0x8(%rbp)

  0x0000000000000606 <+12>: jmp 0x630

  0x0000000000000608 <+14>: mov -0x8(%rbp),%rax

  0x000000000000060c <+18>: imul -0x8(%rbp),%rax

  0x0000000000000611 <+23>: mov %rax,%rdx

  0x0000000000000614 <+26>: mov -0x8(%rbp),%rax

  0x0000000000000618 <+30>: lea 0x0(,%rax,8),%rcx

  0x0000000000000620 <+38>: lea 0x200a19(%rip),%rax # 0x201040

  0x0000000000000627 <+45>: mov %rdx,(%rcx,%rax,1)

  0x000000000000062b <+49>: addq $0x1,-0x8(%rbp)

  0x0000000000000630 <+54>: cmpq $0x63,-0x8(%rbp)

  0x0000000000000635 <+59>: jbe 0x608

  0x0000000000000637 <+61>: mov $0x0,%eax

  0x000000000000063c <+66>: pop %rbp

  0x000000000000063d <+67>: retq

End of assembler dump.

ProgD:

Dump of assembler code for function main:

  0x00000000000005fa <+0>: push %rbp

  0x00000000000005fb <+1>: mov %rsp,%rbp

  0x00000000000005fe <+4>: movb $0x0,0x200a3b(%rip) # 0x201040

  0x0000000000000605 <+11>: movb $0x0,0x200a35(%rip) # 0x201041

  0x000000000000060c <+18>: movq $0x2,-0x10(%rbp)

  0x0000000000000614 <+26>: jmp 0x62c

  0x0000000000000616 <+28>: lea 0x200a23(%rip),%rdx # 0x201040

  0x000000000000061d <+35>: mov -0x10(%rbp),%rax

  0x0000000000000621 <+39>: add %rdx,%rax

  0x0000000000000624 <+42>: movb $0x1,(%rax)

  0x0000000000000627 <+45>: addq $0x1,-0x10(%rbp)

  0x000000000000062c <+50>: cmpq $0x63,-0x10(%rbp)

  0x0000000000000631 <+55>: jbe 0x616

  0x0000000000000633 <+57>: movq $0x2,-0x8(%rbp)

  0x000000000000063b <+65>: jmp 0x66f

  0x000000000000063d <+67>: mov -0x8(%rbp),%rax

  0x0000000000000641 <+71>: add %rax,%rax

  0x0000000000000644 <+74>: mov %rax,-0x10(%rbp)

  0x0000000000000648 <+78>: jmp 0x663

Answer 1

Based on the assembly code provided, we can tell that both programs are filling in an array of numbers, but one program is filling in quadword integers and the other is filling in bytes. We need to figure out which program is filling in an array of primes and which program is filling in an array of squares.

ProgC appears to be filling in an array of squares. The instruction at address 0x000000000000060c loads the value 2 into a register, and the instruction at address 0x0000000000000618 calculates the address in the array to store the square. The instruction at address 0x0000000000000620 loads the address of the array into a register, and the instruction at address 0x0000000000000627 stores the calculated square at the calculated address. Therefore, ProgC is storing the first 100 squares in an array of quadword integers.

On the other hand, ProgD appears to be filling in an array of primes. The instruction at address 0x000000000000060c loads the value 2 into a register, which is the first prime number. The instruction at address 0x00000000000005fe initializes the first element of the array to 0, and the instruction at address 0x0000000000000605 initializes the second element of the array to 0. Then, the loop starting at address 0x0000000000000614 repeatedly checks if the current number is prime and, if so, sets the corresponding element of the array to 1. Therefore, ProgD is storing a boolean array indicating which numbers up to 100 are prime.

In conclusion, ProgC fills in an array of squares, and ProgD fills in an array of primes.