INF1018 - Software Básico - 2013.2

Primeiro Trabalho

Manipulação de inteiros grandes

O objetivo deste trabalho é construir uma biblioteca para manipulação de inteiros grandes de 128 bits. A biblioteca deverá prover as operações aritméticas básicas (somar, subtrair, multiplicar), comparação e operações de deslocamento de bits.

A biblioteca deve ser implementada em C, usando a seguinte definição para o tipo do inteiro grande:

	
#define NUM_BYTES 16
typedef unsigned char BigInt[NUM_BYTES];

Ou seja, uma variável do tipo BigInt é representada por este array, que deve ser interpretado como um único inteiro de 128 bits, seguindo a ordem little-endian. Dependendo do tipo de operação, o valor armazenado deve ser interpretado como um valor sem sinal (unsigned) ou como um valor com sinal, representado em complemento a dois.

Por exemplo, o array {0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}, se interpretado como um valor inteiro com sinal, representa o inteiro 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE (-2). Este mesmo array, se interpretado como um valor inteiro sem sinal, representa o inteiro 2¹²⁸-2.

Especificação da Biblioteca

A implementação das funções da biblioteca deve obedecer os protótipos a seguir:

/* Atribuição */

/* res = val (extensão com sinal) */
void big_val (BigInt res, int val);

/* res = uval (extensão sem sinal) */
void big_uval (BigInt res, unsigned int uval);

/* Operacoes aritméticas */

/* res = a + b */
void big_sum (BigInt res, BigInt a, BigInt b);

/* res = a - b */
void big_sub (BigInt res, BigInt a, BigInt b);

/* res = a * b (com sinal) */
void big_mul (BigInt res, BigInt a, BigInt b);

/* res = a * b (sem sinal) */
void big_umul (BigInt res, BigInt a, BigInt b);

/* Operacoes de deslocamento */

/* res = a << n */
void big_shl (BigInt res, BigInt a, int n);

/* res = a >> n (lógico) */
void big_shr (BigInt res, BigInt a, int n);

/* Comparação: retorna -1 (a < b), 0 (a == b), 1 (a > b) */

/* comparação com sinal */
int big_cmp(BigInt a, BigInt b);

/* comparação sem sinal */
int big_ucmp(BigInt a, BigInt b);

Sua biblioteca deve ser implementada como um arquivo C com nome "bigint.c". Este arquivo deve conter apenas a implementação das funções acima (e, eventualmente, funções auxiliares). Ele deve incluir a linha

#include "bigint.h"

(arquivo de cabeçalho com os protótipos das funções da biblioteca, que pode ser obtido aqui)

Testando as funções

Para testar as suas funções, crie um outro arquivo, teste.c, contendo uma função main. Este arquivo também deverá conter a linha

#include "bigint.h"

Crie seu programa executável teste com a linha:

   gcc -Wall -o teste bigint.c teste.c

Recomendações:

Construa suas funções uma a uma e vá testando-as aos poucos, em vez de escrever o código todo de uma vez sem testar as funções individualmente. É receita de desgraça deixar para testar tudo no final!
Não se esqueça de testar bem seu programa antes de entregá-lo! Em cada operação implementada, pense nos diferentes casos (números positivos, negativos, muito grandes, etc) e teste-os todos.
Não serão considerados trabalhos com erros de compilação!
Algumas das operações possuem uma implementação evidente, enquanto que outras requerem um pouco mais de investigação. Por este motivo, os trabalhos também serão julgados pela sua eficiência.

Prazo: 25/09 (até a meia noite)

Os trabalhos perderão um ponto por cada dia de atraso, incluindo dias de final de semana.

Entrega

Devem ser entregue dois arquivos:
1. um arquivo bigint.c, contendo a implementação das funções pedidas (e, eventualmente, funções auxiliares). Esse arquivo * não * deve conter uma função main!
2. um arquivo texto rel.txt contendo um pequeno relatório explicando como seu trabalho foi testado (cite explicitamente os casos de teste utilizados), o que está funcionando e o que não está funcionando. Se seu programa tem bugs, você saber disto é um atenuante para o julgamento do trabalho...
O trabalho deve ser enviado por email para o professor da turma, com subject/assunto "Trabalho 1 - Software Basico". Indique claramente os integrantes do grupo no corpo do email e inclua, como anexo, apenas os arquivos "bigint.c" e "rel.txt".
Coloque no início dos dois arquivos, como comentário, os nomes dos integrantes do grupo, da seguinte forma:
```
/* Nome_do_Aluno1 Matricula */
/* Nome_do_Aluno2 Matricula */
```

Observações

O trabalho pode ser feito em grupo de dois alunos.

Implemente uma função de cada vez, e teste bem sua implementação. É melhor entregar um trabalho com apenas algumas funções funcionando corretamente do que com todas as funções funcionando incorretamente.
Se você não implementar alguma das funções, crie uma função dummy com o nome da função que faltou com corpo '{ return; }', para que o programa de teste usado para correção do trabalho possa ser gerado sem problemas.

Alguns grupos poderão ser chamados para explicar ao professor, no laboratório, o código do trabalho entregue. Será marcada uma data específica para essa avaliação.

Em caso de dúvidas, não invente. Pergunte!