Software Básico

Representação de tipos estruturados (cont)

Estruturas heterogêneas: structs

componentes alocados na memória na ordem em que são declarados
- mas não necessariamente contíguos!!!!!
- restrições de alinhamento!

O layout de structs na memória depende da questão de alinhamento. Cada campo da estrutura que corresponde a uma palavra deve necessariamente começar em um endereço múltiplo de 4. Assim, se tivermos uma declaração como:

struct s{
  char c[2];
  float b;
};

onde um campo ocupando dois bytes precede um campo que corresponde a uma palavra, o compilador terá que deixar dois bytes não utilizados entre o array de caracteres e o float.

struct s s1;

memória alocada para s1:

    início de s1
    ----------------------------------------------------------------------
    |s1.c[0]|s1.c[1]| xxxxx | xxxxx | s1.b  | s1.b   | s1.b    | s1.b    |
    ----------------------------------------------------------------------

Os bytes não usados na memória alocada a um struct são chamados de padding.

Observe que o início de cada estrutura tem que ser sempre alinhado, senão não saberemos quantos bytes devem ser "pulados" para chegar a um endereço múltiplo de 4. Isso é especialmente relevante na hora em que montamos um array de structs, já que os elementos de um array são alocados contiguamente na memória.

O tamanho total da struct tem que já ser calculado para o caso da struct ser usada dentro de um array e respeitar a regra de cálculo do tamanho total do array, usando sizeof (sizeof(array)=num_elem*sizeof(elem)). Por isso, o padding pode às vezes ocorrer no final. Por exemplo, a declaração:

struct s {
  float b;
  char c[2];
};

indica que o campo b deve estar sempre alinhado em um múltiplo de 4 bytes. Como a estrutura pode vir a ser usada em um array, o compilador irá automaticamente colocar um padding de 2 bytes ao final da estrutura, ou seja, o sizeof de s será 8.

Para a declaração:

struct s bobo[2];

a alocação de memória ficaria:

                              --------------------
    início de bobo  --->      | bobo[0].b        |
                              --------------------
                              | bobo[0].b        |
                              --------------------
                              | bobo[0].b        |
                              --------------------
                              | bobo[0].b        |
                              --------------------
                              | bobo[0].c[0]     |
                              --------------------
                              | bobo[0].c[1]     |
                              --------------------
                              |     XXX          |
                              --------------------
                              |     XXX          |
                              --------------------
                              | bobo[1].b        |
                              --------------------
                              | bobo[1].b        |
                              --------------------
                              | bobo[1].b        |
                              --------------------
                              | bobo[1].b        |
                              --------------------
                              | bobo[1].c[0]     |
                              --------------------
                              | bobo[1].c[1]     |
                              --------------------
                              |     XXX          |
                              --------------------
                              |     XXX          |
                              --------------------

Outros exemplos:

O que será gerado por sizeof para as seguintes structs?

struct X
{
   char c;
   int a,b;
}

struct X
{
   char c,d;
   int a,b;
}

se palavra da máquina for 2 bytes (16 bits), temos um inteiro em C de 2 bytes, qual é o tamanho de:
```
struct X
{
   char c,d;
   int a;
   char e;
}
```

Referência

CS:APP, 3.9, 3.10 (por enquanto ignorando a parte de código assembly).
referência: C Programming Notes. Steve Summit.

Representação de números inteiros negativos

com 4 bits, 2⁴ valores distintos e positivos
pensando só em inteiros não negativos, podemos então representar números de 0..15.
e de que forma podemos acrescentar um sinal usando esses mesmos 4 bits? de qualquer forma continuam sendo 2⁴ valores distintos.
- uma forma é usar o bit mais significativo (chamada de representação por sinal e magnitude):
```
ex 4 bits: 0000 ... 0111 : 0 a 7 decimal
           1001 ... 1111: -1 a -7 decimal
	   1000 -> ? (2 representações para o zero??)
```
- mas a forma mais usual é o complemento a dois

Complemento a 2

ex 3 bits

binário		comp. a 2
000		0
001		1
010		2
011		3
100		-4 *
101		-3
110		-2
111		-1

na realidade, estamos usando representação módulo 2^k, onde k é o número de bits usado na representação. Podemos pensar de forma circular:

                  0
               * 000 *
         -1  * 111 001 *  1
            *           *
       -2  * 110     010 *  2
           *             *
            *           *
         -3  * 101 011 *  3
               * 100 *
                 -4

com n bits, que valores distintos podem ser representados? : 2ⁿ : -(2^n-1) ... 2^n-1 - 1
representação de x em complemento a 2 em n bits:
```
se x >= 0, rep(x) = x
se x < 0, rep(x) = 2ⁿ+x
```
Para encontrar a representação em complemento a 2, podemos seguir essa regra.
- Por exemplo, rep(-5) em 8 bits:
```
rep(-5) = 2⁸ + (-5) = 251 = FB₁₆
```
- Pode se tornar muito trabalhoso quando o número de bits é muito grande...
outro método: encontrar a representação de (-x), inverter bit a bit e adicionar 1:
```
2^k+x = (2^k-1) - (-x) + 1
       ************
       complemento bit a bit de (-x)
```

Limites

Qual o maior número inteiro que podemos representar usando unsigned e 8 bits?
Qual o maior número inteiro que podemos representar usando signed e 8 bits?
E qual o menor?
Qual o maior número inteiro que podemos representar usando unsigned e 16 bits?
Qual o maior número inteiro que podemos representar usando signed e 16 bits?
E qual o menor?
Qual o maior número inteiro que podemos representar usando unsigned e 32 bits?
Qual o maior número inteiro que podemos representar usando signed e 32 bits?
E qual o menor?

extensão de representação

como fazer para estender o mesmo número originalmente em 8 bits para 16 bits? e 32 bits?
- depende se número é representação com sinal, em complemento a 2 (nesse caso repetimos o bit mais significativo até preencher todos os bits à esquerda) ou se é unsigned (nesse caso preenchemos à esquerda com zero)
- essa diferença tipicamente vai se refletir em algumas instruções da linguagem de máquina
e o contrário?

perguntas:
- qual número é representado por 1100 0001?
- quantos bits são necessários para representar o valor decimal 3025?

Operadores Relacionais

As operações de comparação têm que levar em conta se os valores comparados são unsigned ou em complemento a dois!
Em assembler, o programador tem que usar operações diferentes em cada caso.
O compilador C gera código com a operação correta dependendo da declaração dos tipos envolvidos.
CUIDADO: Em C, em expressões que envolvem valores signed e unsigned, todos os valores são tratados como unsigned!

Soma e Subtração

uma enorme vantagem da representação em complemento a 2 é que todas as somas e subtrações são resolvidas com um mesmo algoritmo de adição;
a aritmética módulo 2ⁿ garante que o resultado da soma é sempre correto, mesmo que estejamos somando números de sinais diferentes.
- ex: rep[1-2 (modulo 8)] = rep[1+(-2) modulo 8] = (1 modulo 8) + (-2 modulo 8) = 1+6 = 7 = rep(-1 modulo 8)
- a menos de situações de overflow!

Overflow

ocorre quando o resultado (x+y) não é representável em n bits;
como é detectado em complemento a 2?
- se números têm sinais diferentes, nunca ocorre;
- se ambos são positivos, ocorre quando há carry do penúltimo bit para o último (e nesse caso nunca há carry do último bit para fora)
- se ambos são negativos, ocorre quando não há carry do penúltimo bit para o último (e nesse caso sempre há carry do último bit para fora)
- ... quando os dois carrys são diferentes o hardware marca uma condição de overflow!
- essa condição é marcada em qualquer soma, mas só faz sentido se os números estão em complemento a 2!
- para unsigned, o overflow é indicado por uma outra condição, que simplesmente indica se houve carry do último bit para fora!

Referência:

CSPP, seção 2.2