0

I'm on this textbook, Randal E. Bryant, David R. O’Hallaron - Computer Systems. A Programmer’s Perspective [3rd ed.] (2016, Pearson)
and I am stuck at figuring out how the author is able to work out the case number for the switch table, as shown below~

What I am unsure about is how they obtain the case numbers like Case A is Case 5: and how Case 2/7 is Case C and Case D , and so on for the rest of the cases in this example

Any help is appreciated thank you!!

switch stmt

assembly code

Answer given

Megan Darcy
  • 530
  • 5
  • 15
  • 1
    In the jump table, the cases start at 0. So case 0 jumps to `.L3`. Cases 2 and 7 jump to `.L5`. Case 4 jumps to `.L6`. Case 5 jumps to `.L7`. Cases 1,3,6 and any number above 7, or below 0, jump to the `default` label, which is `.L2`. – user3386109 Sep 20 '21 at 06:14
  • 2
    The third image you posted contains an explanation for how they worked out the case numbers. So I'm not sure I understand your question. What did you find unclear about the explanation? – Michael Sep 20 '21 at 06:17
  • 2
    Is that perhaps CS:APP 3e global edition? If so, that would explain the bugs in the practice problems like the mixed up calling convention mentioned in Daniel's answer. See [CS:APP example uses idivq with two operands?](https://stackoverflow.com/q/57998998) for details. If not, then it's hopefully listed in the errata for the non-global edition. https://csapp.cs.cmu.edu/3e/errata.html. Oh, yes, that problem is listed there, so probably you have a good edition and this is one of the small number of errata in that edition. – Peter Cordes Sep 20 '21 at 08:20
  • **DO NOT post images of code, data, error messages, etc.** - copy or type the text into the question. [ask] – Rob Sep 24 '21 at 09:43

1 Answers1

11

First of all, your book has a mistake - it says that "a in %rsi, b in %rdi" - but this is not the standard x64 calling convention and it is inconsistent with the rest of the assembly.

What the book meant:

  • %rdi -> a, %rsi -> b, %rdx -> c, and %rcx -> dest

Moving on, let's understand what happens:

Default Code Block

The first two opcodes are:

cmpq $7, %rdi
ja .L2

ja is jump if above, i.e. if a > 7 then go to .L2 - which is at the end of the assembly. We can deduce that this is the default code block (it continues immediately to the end of the function) - and under .L2 we have:

movq %rsi, %rdi
movq %rdi, %(rcx) ; this corresponds to *dest = val in C

so we can conclude that %(rcx) gets %rsi's value in this case - in other words, in the default code block, val = b.

Switch Code Blocks

If our first ja above did not excute, then we jmp *.L4(,%rdi,8). Since a is not above 7, we have eight possibilities - we can see in the .L4 table that:

  • If a == 0 then we jump to .L3
  • If a == 1, a == 3, or a == 6, we jump to .L2 (our default code block, described above)
  • If a == 2 or a == 7 we jump to .L5
  • If a == 4 we jump to .L6
  • If a == 5 we jump to .L7

.L3, or case 0

This block runs leaq 112(%rdx), %rdi, which simply has the effect of setting %rdi to %rdx + 112 - which is c + 112. We then jump to the end of the function - we can conclude that val = c + 112 in the case 0 code block.

.L7, or case 5

This block runs leaq (%rdx, %rsi), %rdi, which sets %rdi to %rdx + %rsi (which is c + b) - and then calls salq $2, %rdi, which just shifts this value left by 2 bits - for a total value of (c + b) << 2. We then jump to the end of the function - we can conclude that val = (c + b) << 2 in the case 5 code block.

.L6, or case 4

Here we have jumped immediately to the end of the function, just calling the movq %rdi, (%rcx) opcode - which is effectively equivalent to setting *dest = a. We can conclude that in this case, val = a.

.L7, or case 5

This block runs xorq $15, %rsi - which is equivalent to b ^= 15. It then runs movq %rsi, %rdx - setting c to this value. We then continue straight into .L3 described above - which sets val = c + 112. We can conclude that .L7 is our fall-through switch case.

In general, reversing switch cases can be very straightforward - it mostly involves understanding how the jump table corresponds to different values in the compared register (notice here how several possible values of a mapped to the same jump in the table) - and understanding the fall-throughs between different switch cases.

Daniel Kleinstein
  • 5,262
  • 1
  • 22
  • 39
  • 2
    That calling-convention register mixup in this one problem is listed in the errata, https://csapp.cs.cmu.edu/3e/errata.html. So hopefully that's not a sign of the CS:APP 3e global edition which is [a disaster](https://stackoverflow.com/questions/57998998/csapp-example-uses-idivq-with-two-operands) – Peter Cordes Sep 20 '21 at 08:21
  • 2
    Let's also note for the readers that `ja` is an unsigned compare, so negative long values will be "above" 7 and take the default. – Erik Eidt Sep 20 '21 at 20:41