1

In C I have the following struct:

typedef struct _Node{
    int data;
    struct _Node *left;
    struct _Node *right;
} Node;

and the following assembly code:

.section .text
.global _start

_start:
    mov $8, %esi
    mov $A, %rdi
    call func
    movq $60, %rax
    movq $0, %rdi
    syscall
    
func:
    pushq %rbp
    movq %rsp, %rbp
    cmp (%rdi), %esi
    jne continue
    mov $1, %eax
    jmp finish
    
continue:
    cmpq $0, 4(%rdi)
    je next
    pushq %rdi
    mov 4(%rdi), %rdi
    call func
    pop %rdi
    cmp $1, %eax
    je finish

next:
    cmpq $0, 12(%rdi)
    je fail
    pushq %rid
    mov 12(%rdi), %rdi
    call func
    pop %rdi
    cmp $1, %eax
    je finish
   
fail:
    mov $0, %rax

finish:
    leave
    ret

Now trying to write it in C I have a question:

__long__ func ( Node *root, __int__ x){
            if (root->data == __x__ )
                return 1;

            if (root->left != null)
               if (_____??_____)
                   return ___ func(root->left, x)____;

            if (root->right != null)
                return ____func(root->right, x)____;
}

Why we have 2 if-if inside each other? If left isn't null the assembly code calls the function with the left son and doesn't do another condition check (ie cmp call).

  • Why did you delete your prior question? This seems to be the same content? – ecm May 02 '21 at 15:18
  • it contained images which was really bad and caused it to lose attention @ecm plus changed a little –  May 02 '21 at 15:24
  • 7
    @stacker Editing your [old question](https://stackoverflow.com/questions/67357154/how-to-translate-this-assembly-into-c-code?noredirect=1#comment119057067_67357154) was the right solution. Do not delete and repost. – fuz May 02 '21 at 15:28
  • 2
    To be fair, this question is somewhat reasonable in its current state. It probably shouldn't be downvoted as punishment / retribution for doing the wrong thing with the previous question. All we really lost were comments that the struct is missing `__attribute__((packed))`, and about the return type. Although now we can see it checking the return value from child calls we can see it's a 32-bit type, so `int` or `unsigned`, not `bool` or `long`. (Or if it's `long`, then it's doing `(int)func(root->left, x) == 1` or something!) – Peter Cordes May 02 '21 at 15:43

1 Answers1

2

The second if is the one that returns if func was successfull.

bool func(Node *nd, int x)
{
    if (nd->data == x)
        return true;

    if (nd->left)
    {
        if (func(nd->left, x) == true)
            return true;
    }

    if (nd->right)
        return func(nd->right, x);
    
    return false;
}

I choose bool because it makes sense in the context of this function, even though int or long or others may also be valid.

Devolus
  • 21,661
  • 13
  • 66
  • 113
  • 1
    We can see from `cmp $1, %eax` that the return type is a 32-bit integer. (Or `long` and it's doing `if ((int)func(...) == 1)`.) In x86-64 System V (and Windows x64), return registers are allowed to have high garbage in bits of the register outside the actual return value. (Same for arg-passing, [except unofficially narrow integers are sign- or zero- extended to 32-bit](https://stackoverflow.com/questions/36706721/is-a-sign-or-zero-extension-required-when-adding-a-32bit-offset-to-a-pointer-for); clang relies on this in callees, GCC and clang both do it in callers. ICC doesn't...) – Peter Cordes May 02 '21 at 15:47
  • still I don't understand why we need that extra condition... –  May 02 '21 at 15:50
  • 2
    The extra condition is used, when the left path found the value, so it shouldn't also look in the right path. Might be a binary tree implementation. – Devolus May 02 '21 at 15:52
  • @stacker: Note that the `next:` block, doing the nd->right call, is only logically equivalent to a tailcall. It's actually checking if the return value is `== 1`, and If so returning that, otherwise returning a `0`. So it pointlessly branches on the `func(nd->right, x)` return value. If you're trying to literally represent the logic in C, you need inside the `if (nd->right)` block, something like `{ int rv = func();` / `if (rv == 1) return rv; }` (otherwise fall through to `return false;`) – Peter Cordes May 03 '21 at 04:24
  • This is of course super pointless because the function can only return 0 or 1. So the asm for the `next:` block could have been much more efficient: `mov 12(%rdi), %rdi` / `leave` (clean up the stack) / `test %rdi, %rdi` / `jnz func` (optimized tailcall), otherwise fall through to `xor %eax, %eax` / `ret`. Of course, an actual compiler with full optimization will turn the tail-recursion into a loop and do the check, only recursing down the left-hand side. If you only enable partial optimization (gcc -O1), then you don't get an optimized tailcall either. https://godbolt.org/z/jPYYrn4d3 – Peter Cordes May 03 '21 at 04:40
  • Also note that the asm recursion depends on `func` not modifying ESI. Compilers won't take advantage of this, and copy the search key `x` to a call-preserved register to preserve it across the first recursive call, too. So the asm is doing better than compilers in that respect alone. – Peter Cordes May 03 '21 at 04:42