Aula 4

Hexadecimal

  • Na semana 0, aprendemos sobre binário, um sistema de contagem com 0s e 1s.
  • Na semana 2, falamos sobre a memória e como cada byte tem um endereço ou identificador, então podemos nos referir a onde nossas variáveis são armazenadas.
  • Acontece que, por convenção, os endereços da memória usam o sistema de contagem hexadecimal, onde existem 16 dígitos, de 0 a 9 e de A a F.

  • Lembre-se que, em binário, cada dígito representava uma potência de 2:

      128 64 32 16  8  4  2  1
    1  1  1  1  1  1  1  1
    • Com 8 bits, podemos contar até 255.

  • Acontece que, em hexadecimal, podemos contar perfeitamente até 8 bits binários com apenas 2 dígitos:

      16^1 16^0
     F    F
    • Aqui, F é um valor de 15 em decimal, e cada lugar é uma potência de 16, então o primeiro F é 16^1 * 15 = 240, mais o segundo F com o valor de 16^0 * 15 = 15, para um total de 255.

  • E 0A é o mesmo que 10 em decimal, e 0F o mesmo que 15. Em hexadecimal, 10 seria 16, e nós diríamos "um zero em hexadecimal" ao invés de "dez", se quiséssemos evitar confusão.

  • O sistema de cores RGB também usa hexadecimal por convenção para descrever a quantidade de cada cor. Por exemplo, 000000 em hexadecimal significa 0 de cada vermelho, verde e azul, para uma cor preta. E FF0000 seria 255, ou a quantidade máxima possível de vermelho. Com diferentes valores para cada cor, podemos representar milhões de cores diferentes.
  • Na escrita, podemos também indicar que um valor está em hexadecimal ao prefixar com 0x, como em 0x10, onde o valor é igual a 16 em decimal, diferentemente de 10.

Ponteiros

  • Podemos criar um valor n e imprimi-lo:

```

include

int main(void) { int n = 50; printf("%i\n", n); } ```

  • Na memória do nosso computador, existem agora 4 bytes em algum lugar que têm o valor binário de 50, etiquetados n: grade representando bytes, com quatro caixas juntas contendo 50 com um pequeno n embaixo
  • Acontece que, com bilhões de bytes na memória, esses bytes para a variável n começam em algum endereço exclusivo que pode parecer como 0x12345678.
  • Em C, podemos realmente ver o endereço com o operador &, que significa "obter o endereço desta variável":

```

include

int main(void) { int n = 50; printf("%p\n", &n); } ```

  • E no CS50 IDE, podemos ver um endereço como 0x7ffe00b3adbc, onde este é um local específico na memória do servidor.

  • O endereço de uma variável é chamado de ponteiro, que podemos considerar como um valor que "aponta" para um local na memória. O operador * nos permite "ir para" o local para o qual um ponteiro está apontando.

  • Por exemplo, podemos imprimir *&n, onde "vamos" para o endereço de n, e isso imprimirá o valor de n, 50, já que esse é o valor no endereço de n:

```

include

int main(void) { int n = 50; printf("%i\n", *&n); } ```

  • Também temos que usar o operador * (de uma forma infelizmente confusa) para declarar uma variável que queremos que seja um ponteiro:

```

include

int main(void) { int n = 50; int *p = &n; printf("%p\n", p); } ```

  • Aqui, usamos int *p para declarar uma variável, p, que tem o tipo *, um ponteiro, para um valor do tipo int, um inteiro. Então, podemos imprimir seu valor (algo como 0x12345678), ou imprimir o valor em seu local com printf("%n\n", *p);.

  • Na memória do nosso computador, as variáveis podem ser semelhantes a isto: grade representando bytes, com quatro caixas juntas contendo 50 com um pequeno 0x12345678 embaixo, e oito caixas juntas contendo 0x12345678 com um pequeno p embaixo

  • Temos um ponteiro, p, com o endereço de alguma variável.
  • Podemos abstrair o valor real dos endereços agora, já que eles serão diferentes conforme declaramos variáveis em nossos programas, e simplesmente pensar em p como "apontando" para algum valor: uma caixa contendo p apontando para uma caixa menor contendo 50
  • Digamos que temos uma caixa de correio rotulada "123", com o número "50" dentro dela. A caixa de correio seria int n, pois armazena um inteiro. Podemos ter outra caixa de correio com o endereço "456", dentro da qual está o valor "123", que é o endereço da nossa outra caixa de correio. Isso seria int *p, já que é um ponteiro para um inteiro.
  • Com a capacidade de usar ponteiros, podemos criar diferentes estruturas de dados, ou diferentes maneiras de organizar dados na memória que veremos na próxima semana.
  • Muitos sistemas de computador modernos são "64 bits", o que significa que usam 64 bits para endereçar a memória, portanto um ponteiro terá 8 bytes, o dobro do tamanho de um inteiro de 4 bytes.

string

  • Poderíamos ter uma variável string s para um nome como "EMMA" e poder acessar cada caractere com s[0] e assim por diante: Caixas lado a lado, contendo: E rotulado s[0], M rotulado s[1], M rotulado s[2], A rotulado s[3], \0 rotulado s[4]
  • Mas acontece que cada caractere é armazenado na memória em um byte com algum endereço, e s é na verdade apenas um ponteiro com o endereço do primeiro caractere: Caixa contendo 0x123 rotulado s, caixas lado a lado contendo E rotulado 0x123, M rotulado 0x124, M rotulado 0x125, A rotulado 0x126, \0 rotulado 0x127
  • E como s é apenas um ponteiro para o começo, somente o \0 indica o fim da string.
  • De fato, a biblioteca CS50 define uma string com typedef char *string, que simplesmente diz que queremos nomear um novo tipo, string, como char *, ou um ponteiro para um caractere.

  • Vamos imprimir uma string:

      #include <cs50.h>
  #include <stdio.h>

  int main(void)
  {
      string s = "EMMA";
      printf("%s\n", s);
  }

  • Isso é familiar, mas podemos simplesmente dizer:

      #include <stdio.h>

  int main(void)
  {
      char *s = "EMMA";
      printf("%s\n", s);
  }
    • Isso também imprimirá EMMA.

  • Com printf("%p\n", s);, podemos imprimir s como seu valor como um ponteiro, como 0x42ab52. (printf sabe ir para o endereço e imprimir a string inteira quando usamos %s e passamos s, mesmo que s aponte apenas para o primeiro caractere.)

  • Podemos também tentar printf("%p\n", &s[0]);, que é o endereço do primeiro caractere de s, e é exatamente o mesmo que imprimir s. E imprimir &s[1], &s[2], e &s[3] nos dá os endereços que são os próximos caracteres na memória depois de &s[0], como 0x42ab53, 0x42ab54, e 0x42ab55, exatamente um byte após o outro.
  • E finalmente, se tentarmos printf("%c\n", *s);, obteremos um único caractere E, já que iremos para o endereço contido em s, que tem o primeiro caractere na string.
  • De fato, s[0], s[1], e s[2] na verdade são mapeados diretamente para *s, *(s+1), e *(s+2), já que cada um dos próximos caracteres está exatamente no endereço do próximo byte.

Comparar e copiar

  • Vamos olhar para compare0:

      #include <cs50.h>
  #include <stdio.h>

  int main(void)
  {
      // Obter dois inteiros
      int i = get_int("i: ");
      int j = get_int("j: ");

      // Comparar inteiros
      if (i == j)
      {
          printf("Igual\n");
      }
      else
      {
          printf("Diferente\n");
      }
  }
    • Podemos compilar e executar isso, e nosso programa funciona como esperado, com os mesmos valores dos dois inteiros nos dando "Igual" e valores diferentes "Diferente".

  • Em compare1, vemos que os mesmos valores de string estão fazendo nosso programa imprimir "Diferente":

      #include <cs50.h>
  #include <stdio.h>

  int main(void)
  {
      // Obter duas strings
      string s = get_string("s: ");
      string t = get_string("t: ");

      // Comparar endereços das strings
      if (s == t)
      {
          printf("Igual\n");
      }
      else
      {
          printf("Diferente\n");
      }
  }
    • Dado o que sabemos agora sobre strings, isso faz sentido porque cada variável de "string" está apontando para um local diferente na memória, onde o primeiro caractere de cada string é armazenado. Portanto, mesmo que os valores das strings sejam iguais, isso sempre imprimirá "Diferente".
    • Por exemplo, nossa primeira string pode estar no endereço 0x123, a segunda pode estar no 0x456, e s será 0x123 e t será 0x456, então esses valores serão diferentes.
    • E get_string, o tempo todo, tem retornado apenas um char *, ou um ponteiro para o primeiro caractere de uma string do usuário.

  • Agora vamos tentar copiar uma string:

      #include <cs50.h>
  #include <ctype.h>
  #include <stdio.h>

  int main(void)
  {
      string s = get_string("s: ");

      string t = s;

      t[0] = toupper(t[0]);

      // Imprimir a string duas vezes
      printf("s: %s\n", s);
      printf("t: %s\n", t);
  }
    • Obtemos uma string s e copiamos o valor de s para t. Em seguida, capitalizamos a primeira letra em t.
    • Mas quando executamos nosso programa, vemos que tanto s quanto t agora estão capitalizados.
    • Como definimos s e t para os mesmos valores, eles são na verdade ponteiros para o mesmo caractere, e assim capitalizamos o mesmo caractere!

  • Para realmente fazer uma cópia de uma string, precisamos fazer um pouco mais de trabalho:

      #include <cs50.h>
  #include <ctype.h>
  #include <stdio.h>
  #include <string.h>

  int main(void)
  {
      char *s = get_string("s: ");

      char *t = malloc(strlen(s) + 1);

      for (int i = 0, n = strlen(s); i < n + 1; i++)
      {
          t[i] = s[i];
      }

      t[0] = toupper(t[0]);

      printf("s: %s\n", s);
      printf("t: %s\n", t);
  }
    • Criamos uma nova variável, t, do tipo char *, com char *t. Agora, queremos apontá-la para um novo bloco de memória grande o suficiente para armazenar a cópia da string. Com malloc, podemos alocar alguns bytes na memória (que não estão sendo usados para armazenar outros valores), e passamos o número de bytes que desejamos. Já sabemos o comprimento de s, então adicionamos 1 para o caractere nulo de terminação. Portanto, nossa linha final de código é char *t = malloc(strlen(s) + 1);.
    • Em seguida, copiamos cada caractere, um de cada vez, e agora podemos capitalizar apenas a primeira letra de t. E usamos i < n + 1, já que realmente queremos ir até n, para garantir que copiamos o caractere de terminação na string.
    • Na verdade, também podemos usar a função da biblioteca strcpy com strcpy(t, s) em vez do nosso loop, para copiar a string s para t. Para ser claro, o conceito de uma “string” é da linguagem C e bem suportado; as únicas rodinhas de treinamento do CS50 são o tipo string em vez de char *, e a função get_string.

  • Se não copiarmos o caractere nulo de terminação, \0, e tentarmos imprimir nossa string t, printf continuará e imprimirá os valores desconhecidos ou lixo que temos na memória, até que eventualmente encontre um \0, ou até mesmo possa travar completamente, já que nosso programa pode acabar tentando ler uma memória que não lhe pertence!

valgrind

  • Acontece que, após concluirmos de usar uma memória que alocamos com malloc, devemos chamar free (como em free(t)), que informa ao nosso computador que aqueles bytes não são mais úteis ao programa, então os bytes na memória podem ser reutilizados novamente.
  • Se continuássemos a executar o programa e alocar memória com malloc, mas nunca liberar a memória após o uso, teríamos um vazamento de memória, o que tornará o computador mais lento e usará cada vez mais memória até que o computador fique sem.
  • valgrind é uma ferramenta de linha de comando que podemos usar para executar o programa e ver se ele tem algum vazamento de memória. Podemos executar o valgrind no programa acima com help50 valgrind ./copy e ver, a partir da mensagem de erro, que na linha 10, alocamos memória que nunca liberamos (ou “perdemos”).
  • Portanto, no final, podemos adicionar uma linha free(t), que não mudará a execução do programa, mas sem erros do valgrind.

  • Vamos dar uma olhada em memory.c:

      // http://valgrind.org/docs/manual/quick-start.html#quick-start.prepare

  #include <stdlib.h>

  void f(void)
  {
      int *x = malloc(10 * sizeof(int));
      x[10] = 0;
  }

  int main(void)
  {
      f();
      return 0;
  }
    • Este é um exemplo da documentação do valgrind (valgrind é uma ferramenta real, enquanto o help50 foi escrito especificamente para nos ajudar neste curso).
    • A função f aloca memória suficiente para armazenar 10 números inteiros e armazena o endereço em um ponteiro chamado x. Então, tentamos definir o 11º valor de x com x[10] como 0, que vai além do array de memória que alocamos para o programa. Isso é chamado de estouro de buffer, em que vamos além dos limites do buffer ou array e para uma memória desconhecida.

  • O valgrind também nos informará que há uma “Gravação inválida de tamanho 4” para a linha 8, onde estamos realmente tentando alterar o valor de um inteiro (de tamanho 4 bytes).

  • E durante todo esse tempo, a Biblioteca CS50 tem liberado memória que foi alocada em get_string, quando o programa termina!

Troca

  • Temos duas bebidas coloridas, roxa e verde, cada uma delas em um copo. Queremos trocar as bebidas entre os dois copos, mas não podemos fazer isso sem um terceiro copo para despejar uma das bebidas primeiro.

  • Agora, digamos que queremos trocar os valores de dois números inteiros.

      void swap(int a, int b)
  {
      int tmp = a;
      a = b;
      b = tmp;
  }
    • Com uma terceira variável para usar como espaço de armazenamento temporário, podemos fazer isso facilmente, colocando a em tmp, e então b em a, e finalmente o valor original de a, agora em tmp, em b.

  • Mas, se tentarmos usar essa função em um programa, não vemos nenhuma alteração:

      #include <stdio.h>

  void swap(int a, int b);

  int main(void)
  {
      int x = 1;
      int y = 2;

      printf("x é %i, y é %i\n", x, y);
      swap(x, y);
      printf("x é %i, y é %i\n", x, y);
  }

  void swap(int a, int b)
  {
      int tmp = a;
      a = b;
      b = tmp;
  }
    • Acontece que a função swap recebe suas próprias variáveis, a e b quando elas são passadas, que são cópias de x e y, e portanto, alterar esses valores não altera x e y na função main.

Layout da memória

  • Dentro da memória do nosso computador, os diferentes tipos de dados que precisam ser armazenados para o nosso programa são organizados em diferentes seções: Grade com seções, de cima para baixo: código da máquina, globais, heap (com seta apontando para baixo), pilha (com seta apontando para cima)
    • A seção código da máquina é o código binário do nosso programa compilado. Quando executamos nosso programa, esse código é carregado na "parte superior" da memória.
    • Globais são variáveis globais declaramos em nosso programa ou outras variáveis compartilhadas que todo o nosso programa pode acessar.
    • A seção heap é uma área vazia onde o malloc pode obter memória livre, para que nosso programa use.
    • A seção pilha é usada por funções em nosso programa conforme elas são chamadas. Por exemplo, nossa função main está na parte inferior da pilha e tem as variáveis locais x e y. A função swap, quando chamada, tem seu próprio quadro ou fatia de memória que está no topo da memória de main, com as variáveis locais a, b e tmp: Seção da pilha com (a, b, tmp) acima de (x, y)
      • Depois que a função swap retorna, a memória que ela estava usando é liberada para a próxima chamada de função, e nós perdemos tudo o que fizemos, além dos valores de retorno, e nosso programa volta para a função que chamou swap.
      • Portanto, passando os endereços de x e y de main para swap, podemos realmente alterar os valores de x e y: Seção da pilha com (a, b, tmp) acima de (x, y), e um apontando para x e b apontando para y
  • Ao passar o endereço de x e y, nossa função swap pode realmente funcionar:

``` #include 

void swap(int *a, int *b);

int main(void)
{
    int x = 1;
    int y = 2;

    printf("x is %i, y is %i\n", x, y);
    swap(&x, &y);
    printf("x is %i, y is %i\n", x, y);
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

```

  • Os endereços de x e y são passados de main para swap, e usamos a sintaxe int *a para declarar que nossa função swap recebe ponteiros. Salvamos o valor de x para tmp seguindo o ponteiro a e, em seguida, pegamos o valor de y seguindo o ponteiro b e o armazenamos no local para o qual a está apontando (x). Finalmente, armazenamos o valor de tmp no local apontado por b (y), e pronto.

  • Se chamarmos malloc muitas vezes, teremos um overflow de heap, no qual acabamos passando do nosso heap. Ou, se tivermos muitas funções sendo chamadas, teremos um overflow de pilha, no qual nossa pilha também tem muitos quadros de memória alocados. E esses dois tipos de estouro são geralmente conhecidos como estouros de buffer, após os quais nosso programa (ou computador inteiro) pode travar.

get_int

  • Podemos implementar get_int nós mesmos com uma função de biblioteca em C, scanf:

      #include <stdio.h>

  int main(void)
  {
      int x;
      printf("x: ");
      scanf("%i", &x);
      printf("x: %i\n", x);
  }
    • scanf recebe um formato, %i, portanto, a entrada é "escaneada" para esse formato e o endereço na memória para onde queremos que essa entrada vá. Mas scanf não tem muita verificação de erros, então podemos não obter um inteiro.

  • Podemos tentar obter uma string da mesma maneira:

      #include <stdio.h>

  int main(void)
  {
      char *s = NULL;
      printf("s: ");
      scanf("%s", s);
      printf("s: %s\n", s);
  }
    • Mas, na verdade, não alocamos nenhuma memória para s (s é NULL ou não aponta para nada), então, podemos querer chamar char s[5] para alocar uma matriz de 5 caracteres para nossa string. Então, s será tratado como um ponteiro em scanf e printf.
    • Agora, se o usuário digitar uma string de comprimento 4 ou menor, nosso programa funcionará com segurança. Mas se o usuário digitar uma string maior, scanf poderá tentar escrever além do final da nossa matriz na memória desconhecida, fazendo com que nosso programa trave.

Arquivos

  • Com a habilidade de usar ponteiros, também podemos abrir arquivos:

```c

include

include

include

int main(void) { // Abre arquivo FILE *file = fopen("phonebook.csv", "a");

  // Recebe texto do usuário
  char *name = get_string("Name: ");
  char *number = get_string("Number: ");

  // Imprime (escreve) texto no arquivo
  fprintf(file, "%s,%s\n", name, number);

  // Fecha arquivo
  fclose(file);

} ```

  • fopen é uma nova função que podemos usar para abrir um arquivo. Ela retornará um ponteiro para um novo tipo, FILE, que podemos ler e escrever. O primeiro argumento é o nome do arquivo, e o segundo é o modo que queremos abrir o arquivo (r para leitura, w para escrita, e a para anexar, ou adicionar).
  • Após obter algum texto, podemos usar fprintf para imprimir em um arquivo.

  • Finalmente, fechamos o arquivo com fclose.

  • Agora podemos criar nossos próprios arquivos CSV, arquivos de valores separados por vírgulas (como uma mini-planilha), programaticamente.

JPEG

  • Também podemos escrever um programa que abre um arquivo e nos diz se é um arquivo JPEG (imagem):

      #include <stdio.h>

  int main(int argc, char *argv[])
  {
      // Verifica o uso
      if (argc != 2)
      {
          retornar 1;
      }

      // Abrir o arquivo
      FILE *file = fopen(argv[1], "r");
      if (!arquivo)
      {
          retornar 1;
      }

      // Ler os três primeiros bytes
      unsigned char bytes[3];
      fread(bytes, 3, 1, file);

      // Verificar os três primeiros bytes
      if (bytes[0] == 0xff && bytes[1] == 0xd8 && bytes[2] == 0xff)
      {
          printf("Talvez\n");
      }
      mais
      {
          printf("Não\n");
      }

      // Fechar o arquivo
      fclose(file);
  }
    • Agora, se executarmos este programa com ./jpeg brian.jpg, nosso programa tentará abrir o arquivo que especificamos (verificando se realmente obtemos um arquivo não nulo) e ler os três primeiros bytes do arquivo com ler.
    • Podemos comparar os três primeiros bytes (em hexadecimal) com os três bytes necessários para iniciar um arquivo JPEG. Se eles forem iguais, então nosso arquivo provavelmente será um arquivo JPEG (embora outros tipos de arquivo ainda possam começar com esses bytes). Mas se eles não forem iguais, sabemos que definitivamente não é um arquivo JPEG.

  • Podemos usar essas habilidades para ler e escrever arquivos, em particular imagens, e modificá-los alterando os bytes neles, no conjunto de problemas desta semana!