Laboratório 7 - Posicionamento de GPS
Objetivo
Praticar o uso de instruções aritméticas e lógicas na arquitetura Assembly RISC-V, aplicando-as para resolver um problema real de geometria e cinemática: descobrir sua localização no mapa usando sinais de satélites (semelhante ao funcionamento básico de um GPS).
Motivação
Nesta atividade, você deve escrever um programa em linguagem assembly RISC-V que calcula suas coordenadas geográficas em um plano bidimensional, com base no tempo atual e nas mensagens recebidas de 3 satélites
Para simplificar o exercício, assumiremos que:
- O satélite A está posicionado na origem do plano cartesiano (0, 0),
- O satélite B está posicionado em (0, YB) e,
- O satélite C está posicionado em (XC, 0).
Os satélites enviam continuamente mensagens com um carimbo de tempo através de ondas que se propagam em todas as direções a uma velocidade de 3 x \(10^8\) m/s. Em um determinado momento TR, você recebe uma mensagem de cada satélite contendo os carimbos de tempo TA, TB e TC. Supondo que todos os relógios estão perfeitamente sincronizados, o seu desafio é escrever um programa em Assembly RISC-V que processe esses dados e descubra a sua posição exata \((x, y)\) (note que a formulação utilizada neste exercício não é realista).
Para chegar nas coordenadas, você deve quebrar o problema em duas etapas lógicas no seu código:
Passo 1: Converter Tempo em Distância
O tempo que o sinal levou para chegar até você é a diferença entre o tempo de recepção e o tempo de envio (\(\Delta t = T_R - T_{origem}\)). Sabendo a velocidade do sinal, calculamos as distâncias \(d_A\), \(d_B\) e \(d_C\) até os satélites.
Tip
É melhor trabalhar com distâncias em metros e tempo em nanossegundos, para que os valores de entrada fornecidos não causem overflow ao usar o método proposto e uma boa precisão possa ser alcançada
Passo 2: Calcular as Coordenadas (Interseção de Círculos)
A sua posição \((x, y)\) é o ponto onde os raios de alcance dos três satélites se cruzam. Isso gera as seguintes equações de círculo:
- \(x^2 + y^2 = d_A^2 \quad (Eq. 1 - Círculo do Satélite A)\)
- \(x^2 + (y - Y_B)^2 = d_B^2 \quad (Eq. 2 - Círculo do Satélite B)\)
- \((x - X_C)^2 + y^2 = d_C^2 \quad (Eq. 3 - Círculo do Satélite C)\)
Ao manipularmos algebricamente as Eq. 1 e Eq. 2, podemos isolar a coordenada Y (Eq 4.):
Com o valor de Y em mãos, usamos a Eq. 1 para encontrar X:
Tip
A Eq. 5 gera dois valores possíveis de \(X\), um positivo e um negativo. Você pode usar a Eq. 3 para testar e descobrir qual dos dois sinais de \(X\) é o correto, ou manipular a Eq. 1 e Eq. 3 de forma semelhante à Eq. 4 para calcular \(X\) sem precisar extrair raízes quadradas!
Entradas e Saídas
A entrada é composta por duas linhas: a primeira contém as coordenadas XC e YB em metros, representadas por números inteiros de quatro dígitos na base decimal precedidos por um sinal (+ ou -) e separados por espaço, e a segunda contém os tempos TR, TA, TB e TC em nanossegundos, representados por números inteiros de quatro dígitos na base decimal e separados por espaço. Cada linha termina com um caractere de nova linha (\n).
A saída consiste em uma única linha contendo as coordenadas x e y em metros, representadas por números inteiros de quatro dígitos na base decimal e precedidos por um sinal (+ ou -), separados por espaço. Para este exercício, soluções aproximadas são aceitas com um erro absoluto menor que 10.
Código Base
Como o conjunto base de instruções do RISC-V não possui uma instrução nativa para calcular raízes quadradas, nós já fornecemos uma função sqrt pronta no Código Base! Assim, você não precisa se preocupar em implementar algoritmos de cálculo numérico e pode focar na manipulação de dados e nas equações principais.
.data
# Buffers na memória para ler a entrada e gravar a saída
input_buffer: .skip 32
output_buffer: .skip 12
.text
.globl _start
_start:
# TODO: Ler a entrada do usuário (coordenadas e tempos)
j read
# TODO: Implementar o cálculo das distâncias
j calculate_distances
# TODO: Converter os resultados de X e Y (inteiros) de volta
j write
li a0, 0
li a7, 93 # syscall de exit (93)
ecall
# ============================================================
# Método auxiliar: Raiz Quadrada (Método Babilônico)
# ============================================================
# Entrada: a0 (Valor que você deseja calcular a raiz)
# Saída: a0 (Resultado inteiro da raiz quadrada)
# ============================================================
sqrt:
li t2, 1
ble a0, t2, sqrt_end
li t2, 21 # t2 = Contador de iterações (precisão)
mv t0, a0 # Copia o valor de entrada para t0
srli t0, t0, 1 # t0 = Chute inicial (Entrada / 2)
loop_sqrt:
div t1, a0, t0 # t1 = Entrada / Chute
add t1, t1, t0 # t1 = Chute + (Entrada / Chute)
srli t0, t1, 1 # t0 = Novo Chute (Divide tudo por 2)
addi t2, t2, -1 # Diminui o contador de iterações
bnez t2, loop_sqrt # Se não chegou a zero, repete o loop
mv a0, t0 # Coloca o resultado final em a0
sqrt_end:
ret
Exemplos
Test Case 01
-0100 +0700
2300 2000 0000 2240
-------------------
-0088 +0016
Test Case 02
-2042 +1042
9913 6823 4756 6047
-------------------
-0902 -0215
Test Case 03
+0280 -2168
9550 3207 5791 3638
-------------------
+0989 -1626
Test Case 04
+0965 -2491
9357 2884 7511 2033
-------------------
-0065 -1941
Test Case 05
+1337 -0656
9133 0162 2023 1192
-------------------
+1255 -2381
Entrega
O report gerado pelo simulador deve ser submetido no Classroom da disciplina, renomeado para {RA}_lab7.report.
Warning
- Qualquer alteração no arquivo de report será considerado fraude
- O uso de ferramentas de IA deve ser reportado, indicando como foi utilizado e em quais partes do código.
- Está é uma atividade individual, o qual deve ser desenvolvido individualmente, qualquer forma de cópia ou plágio será penalizada. Portanto, atividades que apresentarem semelhanças injustificadas serão atribuídas nota zero para todos os envolvidos