Laboratório 4 - Deslocamento de Bits e Máscaras

O objetivo desta atividade é colocar em prática o uso de operações de bits e deslocamentos (shifts) presentes na arquitetura RISC-V. Para isso, serão implementados algoritmos de multiplicação e divisão de valores inteiros utilizando essas operações.

Multiplicação no RISC-V (Extensão M)

A arquitetura base RISC-V (RV32I) possui apenas operações inteiras básicas. Para realizar multiplicações e divisões diretamente em hardware, o processador pode implementar a Extensão M (Integer Multiplication and Division).

Essa extensão adiciona instruções para multiplicação e divisão de inteiros. Ela é opcional, pois nem todo processador precisa dessas operações: em aplicações simples, implementá-las em hardware pode aumentar desnecessariamente o consumo de energia e a complexidade do circuito.

A forma mais simples para realizar a multiplicação em processadores que não possuem a Extensão M seria somar ou subtrair repetidamente um valor. Porém, essa abordagem se torna impraticável para valores grandes, pois o número de operações cresce linearmente com o valor do multiplicador ou divisor.

Uma alternativa é utilizar algoritmos que operam diretamente sobre os bits dos valores. Para multiplicação, pode-se utilizar o algoritmo shift-and-add, que utiliza deslocamentos e somas para construir o resultado. Para divisão, pode-se utilizar o algoritmo de divisão por restauração (Restoring Division), que utiliza deslocamentos e subtrações para determinar o quociente.

Multiplicação

O algoritmo shift-and-add utiliza a representação binária do multiplicador para realizar a multiplicação por meio de deslocamentos e somas. A cada posição de bit, o multiplicando é deslocado uma posição para a esquerda, o que equivale a multiplicá-lo por uma potência de dois.

Example

Por exemplo, para multiplicar 13 por 9:

Multiplicando: 13 = 01101
multiplicador: 9 = 01001

Percorremos os bits do multiplicador (9) da direita para a esquerda. Sempre que o bit atual for 1, o valor correspondente do multiplicando (13) é somado ao resultado. Após cada posição, o multiplicando é deslocado uma posição para a esquerda:

01101 << 0 = 0001101 = 13  -> bit = 1 -> soma
01101 << 1 = 0011010 = 26  -> bit = 0 -> ignora
01101 << 2 = 0110100 = 52  -> bit = 0 -> ignora
01101 << 3 = 1101000 = 104 -> bit = 1 -> soma

Assim, 13 × 9 = 13 + 104 = 117.

Dessa forma, a multiplicação é realizada utilizando apenas shifts, testes de bits e somas.

Divisão (e Resto)

O algoritmo de divisão por restauração (Restoring Division) utiliza a representação binária do dividendo e do divisor para realizar a divisão por meio de deslocamentos e subtrações.

O algoritmo de divisão por restauração percorre os bits do dividendo da esquerda para a direita. A cada posição, o bit atual é incorporado ao resto por meio de um deslocamento. Em seguida, se o resto for maior ou igual ao divisor, o bit correspondente do quociente é definido como 1 e o divisor é subtraído do resto. Caso contrário, o bit do quociente é definido como 0.

Example

Por exemplo, para dividir 13 por 3, processando os bits do dividendo da esquerda para a direita:

Dividendo: 13 = 1101
Divisor:   3 = 0011

Inicialmente: quociente = resto = 0000.

Processa o primeiro bit (1):

resto = (0000 << 1) | 1 = 0001
0001 < 0011 -> não subtrai, append 0
quociente = (0000 << 1) | 0 = 0000

Processa o segundo bit (1):

resto = (0001 << 1) | 1 = 0011
0011 >= 0011 -> subtrai, append 1
resto = 0011 - 0011 = 0000
quociente = (0000 << 1) | 1 = 0001

Processa o terceiro bit (0):

resto = (0000 << 1) | 0 = 0000
0000 < 0011 -> não subtrai, append 0
quociente = (0001 << 1) | 0 = 0010

Processa o quarto bit (1):

resto = (0000 << 1) | 1 = 0001
0001 < 0011 -> não subtrai, append 0
quociente = (0010 << 1) | 0 = 0100

Assim, no final do processo, o quociente é 0100 = 4 e o resto é 0001 = 1, portanto 13 ÷ 3 = 4.

Exemplo de Código Implementacao da Adição

A modo de exemplo, também é possível reescrever a operação de soma utilizando operações de deslocamento e operações bit a bit. A seguir, é apresentado um exemplo de implementação.

int add(int a, int b)
{
    int soma;
    int carry;

    // Repete enquanto houver carry

    while (b != 0)
    {
        // Soma os bits (desconsidera carry)

        soma = a ^ b;

        // Atualiza o carry

        carry = (a & b) << 1;

        a = soma;
        b = carry;
    }

    return a;
}

Código Base para o Exercício

Partindo do código fornecido, deve ser implementado um programa em linguagem C capaz de realizar as operações de multiplicação, divisão e resto. Para isso, devem ser utilizadas apenas operações de deslocamento de bits e máscaras para manipular os valores de entrada. O programa deve ler uma string da entrada padrão, interpretar os números e a operação especificados, realizar o cálculo e imprimir o resultado na saída padrão.

#define STDIN_FD  0
#define STDOUT_FD 1

int read(int __fd, const void *__buf, int __n){
    int ret_val;
  __asm__ __volatile__(
    "mv a0, %1           # file descriptor\n"
    "mv a1, %2           # buffer \n"
    "mv a2, %3           # size \n"
    "li a7, 63           # syscall write code (63) \n"
    "ecall               # invoke syscall \n"
    "mv %0, a0           # move return value to ret_val\n"
    : "=r"(ret_val)  // Output list
    : "r"(__fd), "r"(__buf), "r"(__n)    // Input list
    : "a0", "a1", "a2", "a7"
  );
  return ret_val;
}

void write(int __fd, const void *__buf, int __n)
{
  __asm__ __volatile__(
    "mv a0, %0           # file descriptor\n"
    "mv a1, %1           # buffer \n"
    "mv a2, %2           # size \n"
    "li a7, 64           # syscall write (64) \n"
    "ecall"
    :   // Output list
    :"r"(__fd), "r"(__buf), "r"(__n)    // Input list
    : "a0", "a1", "a2", "a7"
  );
}

void exit(int code)
{
  __asm__ __volatile__(
    "mv a0, %0           # return code\n"
    "li a7, 93           # syscall exit (64) \n"
    "ecall"
    :   // Output list
    :"r"(code)    // Input list
    : "a0", "a7"
  );
}

unsigned int multiply(unsigned int a, unsigned int b)
{
  /* multiply logic */

  return result;
}

unsigned int divide(unsigned int dividend, unsigned int divisor)
{
  /* divide logic */

  return quotient;
}

unsigned int remainder(unsigned int dividend, unsigned int divisor)
{
  /* remainder logic */

  return remainder;
}

int main()
{
  int n = read(STDIN_FD, (void*) buffer, 10);

  /* program logic */

  write(STDOUT_FD, (void*) buffer, n);

  return 0;
}

void _start()
{
  int ret_code = main();
  exit(ret_code);
}

Entrada do Programa

O programa deve ler da entrada padrão uma string com o seguinte formato: <a2><a1><a0> <op> <b2><b1><b0>\n. Os símbolos a serem considerados para os dígitos são os caracteres de '0' a '9'. As operações aritméticas são representadas pelos símbolos '*' (multiplicação) e '/' (divisão) e '%' (resto).

Saída do Programa

Os casos de teste devem produzir como saída um valor inteiro sem sinal, representado em decimal com sete dígitos, seguido de um \n.

Exemplos de Entradas e Saídas

`003 * 005`	`015 * 002`	`007 / 007`	`099 * 099`
`0000015`	`0000030`	`0000001`	`0009801`

Material Auxiliar

Slides - Computer Organization & Systems: Bitwise Operators, Stanford University.
Lecture - Effective Programming in C & Unix: Bit Operations, Carnegie Mellon University.

Entrega

Utilize o assistente disponível neste link.

Renomeie o arquivo de relatório para lab4_ra.report antes de submeter no Classroom

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