Enquanto navegava no twitter, me deparei com este tweet:
Continua após a publicidade..
Desafio aceito
Algumas regras básicas
A tarefa é inverter uma árvore binária. Um nó de árvore binária é definido da seguinte forma:
struct TreeNode{
int
val;
estrutura
TreeNode
* deixei; estrutura Treenode
* certo; };
Esta definição é de Leetcode 226. Depois que terminarmos, podemos enviar nosso código para lá para ver se funciona.
Estarei usando o assembly x64 com a sintaxe AT&T como está objetivamente superior à sintaxe da Intel.
Tecnicamente, o tweet pede para inverter uma árvore merkle, no entanto, você pode facilmente estender o código final para recalcular o hash em cada nó após suas duas subárvores serem invertidas.
“A pilha precisa ter 16 byte alinhado imediatamente antes de qualquer instrução de chamada ser executada.”
Caso base
A função aceita um único ponteiro como entrada, portanto conforme a convenção de chamada, estaremos recebendo como valor de 64 bits no registrador %rdi.
Para retornar um ponteiro da nossa função, temos que armazená-lo no registrador %rax antes de nós ret da nossa função.
invert_tree : #Função prólogo push %rbp mov %rsp , %rbp sub$32, %rsp # --------- Base caso --------- # %rdi contém o inp parâmetro ut (ponteiro de 8 bytes para a raiz) cmp$0, %rdi # Root not NULL, continue com a execução jne Prosseguir# Root é NULL, armazene NULL em %rax e retorne xor %rax, %rax jmpfeitoProsseguir: feito: # Função epílogo sairret
Em x64, NULL é o valor 0. Comparamos %rdi com 0 e se for bem sucedido, colocamos 0 dentro %rax e retornar da nossa função. Para fazer isso, usando xor é mais rápido que mov ou sub.
Alinhamento da estrutura
Na maioria dos ISAs, cada tipo de dado em uma estrutura tem um requisito de alinhamento. O que isso significa é que o endereço de um tipo deve começar em um endereço que seja múltiplo de seu tamanho. (Existem algumas exceções, mas esta é a regra geral)
Então int devem começar em um endereço que seja múltiplo de 4, e os ponteiros devem começar em um endereço que seja um múltiplo de 8.
Dado isso, nossa estrutura original é disposta na memória mais ou menos assim:
struct TreeNode{ int val; Caracteres tecla[
4]; // 4 bytes extras para alinhar o próximo ponteiro struct TreeNode
* esquerda; estrutura Treenode
* certo; };
Isso desperdiça 4 bytes para cada struct na memória. Podemos economizar esse espaço declarando os ponteiros primeiro, porém continuaremos a usar a declaração struct original, pois queremos enviar isso para o Leetcode.
Armazenando variáveis locais na pilha
Assim que soubermos os deslocamentos de endereço em nossa estrutura, podemos armazená-los na pilha. Vamos armazenar local_root, ponteiros esquerdo e direito na pilha. Cada um deles tem um tamanho de 8 bytes. Nós os armazenamos da seguinte maneira
invert_tree: # ... Prosseguir: # --------- Salvar variáveis locais na pilha --------- # Salve o parâmetro raiz como local_root na pilha movq %rdi, local_root(%rbp) # Avance 8 bytes da raiz, para obter o ponteiro esquerdo na estrutura. movq8(%rdi), %rdx # Armazene isso como local_left para empilhar movq %rdx, local_left(% rbp) # Avance 16 bytes da raiz, para chegar ao ponteiro certo em struct. movq16(%rdi), %rdx # Armazene isso como local_right para empilhar movq %rdx, local_right(% rbp) feito: # ...
Faça as chamadas recursivas
Neste ponto, olhando o pseudocódigo, basta realizar 2 chamadas recursivas.
Para isso, armazenamos o parâmetro correto em %rdi e use a chamada instrução.
# --------- Salvar variáveis locais na pilha --------- # Salve o parâmetro raiz como local_root na pilha movq %rdi, local_root(%rbp ) # Avance 8 bytes da raiz, para obter o ponteiro esquerdo em struct. movq8(%rdi), %rdx # Armazene isso como local_left para empilhar movq %rdx,
local_left(% rbp) # Avance 16 bytes da raiz, para chegar ao ponteiro certo em struct. movq16(%rdi), %rdx # Armazene isso como local_right para empilhar movq %rdx,
local_right(% rbp) # --------- Chamadas recursivas --------- # Recursivo y chame invert_tree em local_right movqlocal_right(%rbp), %rdi ligarinvert_tree# Calcula o endereço de root.left movqlocal_root(%rbp), %rdx addq$8, %rdx # Atribui root.left ao valor retornado da chamada recursiva movq %rax, (%rdx) #Chamada recursivamente inverter_tree em local_left movqlocal_left (%rbp), %rdi ligarinvert_tree# Calcular endereço de root.right movqlocal_root(%rbp), %rdx addq$16, %rdx # Atribui root.right ao valor retornado da chamada recursiva movq %rax, (%rdx) # Return root movqlocal_root(%rbp), %rax feito: # Função epílogo sairret
Para atribuir os resultados das chamadas recursivas, usamos o %rdx registre-se para calcular os endereços corretos de root.left e root. certo. A maior parte disso é uma tradução direta do pseudocódigo.
Enviando para leetcode
Não podemos enviar montagem para Leetcode, então usaremos C em seu lugar. Leetcode usa o gcc para compilar nosso código, então podemos usar o __asm__ para adicionar nosso assembly.
O desempenho e a memória do leetcode os números não são muito confiáveis, então não sabemos realmente o quanto nosso programa é mais rápido em comparação com outros envios, mas suspeito que seja bem rápido.
Conclusão
Esta foi uma excursão divertida para aprimorar minhas habilidades de montagem. Não foi difícil, mas definitivamente foi tedioso (geralmente é assim que me sinto sobre a maioria das questões de estilo leetcode).
Pelo menos agora posso me relacionar com mais memes em
