Online Programming

Ponteiros em C - Parte 2

2010-10-01T14:18:00.000-07:00

Bem, nesta 2ª parte vamos basicamente aplicar tudo o que aprendemos na primeira parte.

Sumariando:
* Resolver o problema da criação de uma função para a troca de valores entre duas variáveis.
* Aritmética de ponteiros.
* Comparação de ponteiros.

Vamos começar por resolver o segundo problema apresentado na parte 1 deste artigo que é o problema de criar uma função que dados dois argumentos para essa mesma função trocar o valor entre eles.

Vamos primeiro perceber por que razão é que uma solução como passar argumentos "normais" não resulta.
Ora bem, quando nós chamámos uma função é criado, como já disse, o seu stack frame. Nesse stack frame vão estar também as variáveis criadas como argumento. Por exemplo, se tivessemos uma definição assim: void fun (int x, int y). Neste caso seria criada, quando chamada, no stack frame da função fun uma variável x e uma variável y. Quando fossemos a chamar esta função, por exemplo assim: fun (10, 20), estaríamos a passar o quê realmente? Estaríamos a passar o valor 10 para a variável x e o valor 20 para a variável y! Ou seja, chamar a função assim: fun (10, 20) é o mesmo que fazer: x = 10, y = 20. Acontecia exactamente o mesmo se fossemos a fazer:
int k = 10, j = 20;
fun (k,j);

Neste caso nós na função fun não estaríamos a trabalhar realmente com k e j mas sim com os seus valores! Ou seja, era a mesma coisa que fazer: x = k, y = j! É muito importante reter esta ideia: quando chamámos uma função com argumentos é na realidade passado para essa função o valor dos argumentos e não os argumentos em si!
A partir disto a questão continua: como é que então vamos trabalhar com os argumentos em si, visto que é isso mesmo que nós queremos, alterá-los...?
Outra vez, a solução passa por utilizar ponteiros. Se nós arranjássemos maneira de conseguir ter o endereço das variáveis na função que vamos criar e se tivéssemos um ponteiro para as manipular e modificar podíamos alterá-las realmente! Ora, isto é perfeitamente possível de o fazer, basta fazer o seguinte:
* Criar uma função que vai ter como argumentos dois ponteiros (que vão receber os endereços das variáveis de main).
* Passar para essa função os endereços das variáveis.

A partir daqui bastava utilizar o operador * para alterar o valor para onde os ponteiros apontam (variáveis da função main).

Vamos então resolver este problema de uma vez por todas.
Exemplo nº 5

Pus diversos comentários que penso serem importantes para entenderem bem isto!
Então, no programa são passados para a função fun os endereços de k e de j para que nessa função possamos trabalhar com eles directamente, visto que o que vai receber esses valores vão ser dois ponteiros! A partir daí podemos trabalhar com essas variáveis directamente através do operador *. É importante que entendam bem este programa por isso não avancem mais no artigo sem o entender bem!

Vou deixar, já agora uma imagem que relata a situação do nosso programa (com stack frames de main e fun).

Se pensarmos um bocadinho vamos-nos lembrar de outra situação em que é preciso passar o endereço das variáveis para uma função bem conhecida por todos vocês! A função scanf:
int x = 0;
scanf ("%d", &x);

Por que razão é que temos de passar para a função scanf o endereço de x? Simplesmente porque a função scanf vai alterar o valor de x e vai "colocar" nele o valor introduzido pelo usuário. X encontra-se no stack frame de main, por exemplo (podia ser outra função qualquer) e nós estamos a criar outro stack frame para a função scanf! Para alterar o valor de x temos de "invadir" o stack frame da função onde se encontra x e depois alterar o seu valor com o valor introduzido pelo usuário. Se não passássemos o endereço de x e fizéssemos: scanf ("%d", x) estaríamos na realidade a passar para um ponteiro o valor de x, que neste caso é 0, então estaríamos a armazenar na posição 0 o valor introduzido pelo usuário, visto que foi passado para o ponteiro o valor 0, ou seja, ele iria apontar para a posição 0 na memória! Isto resultaria num segmentation fault.

Em construção [...]

Ponteiros em C - Parte 1

2010-09-29T08:35:00.001-07:00

Penso que esta é a maior dor de cabeça de principiantes em C e em C++ também, além de existirem as referências que são muito mais simples de se utilizar. Uma vez dominados os ponteiros podem ser muito mas mesmo muito úteis em todas as vertentes da linguagem.

Nesta primeira parte vamos:
* Compreender o conceito
* Utilizar e compreender os operadores & e *.

Temos muitos exemplos diários que se assemelham à utilização de ponteiros. Vou dar um exemplo que penso ser o melhor. Imaginemos que estamos a escrever manualmente um documento (não muito formal) e que nesse documento existe algum termo técnico ou conceito que nem toda a gente entende. O que fazemos é um referência a essa palavra no final do parágrafo ou até no final do próprio documento.

Exemplo:
"[...] os ponteiros[1] são muito úteis [...]".
[1] Em programação, um ponteiro ou apontador é um tipo de dado de uma linguagem de programação cujo valor se refere diretamente a um outro valor alocado em outra área da memória, através de seu endereço. Um ponteiro é uma simples implementação do tipo referência da ciência da computação. @pt.wikipedia.org

Podemos ver neste exemplo bastante simples que o [1] no texto em si faz referência ao [1] que, neste caso, é a definição da palavra.

Obviamente vocês perguntam o que é que isto tem a ver com a linguagem C e com programação. Este pequeno exemplo permite-nos explicar conceitos bastante importantes nesta matéria.

Agora vou introduzir um problema que é bastante comum para a explicação de ponteiros.

Como vocês sabem quando se chama uma função é criado na stack um stack frame para essa função (podem ver o meu artigo sobre buffer overflow), com todas as variáveis locais, etc. Ou seja, cada função tem o seu próprio stack frame (quando chamadas), logo nenhuma função poderá interferir com a variáveis de outra função visto que estão em regiões de memória diferentes. É aqui que os ponteiros nos vão ser úteis, eles vão permitir-nos realmente alterar o valor das variáveis de outras funções. Isto é apenas um exemplo introdutório, obviamente.

Então vamos já escrever um programa em que vamos poder ver que não podemos realmente alterar o valor de variáveis de funções diferentes.
Exemplo nº 1

Meh, vocês olham para este problema e pensam "este tipo está a fazer as coisas mal", com os conhecimentos que vocês já têm conseguem resolver o problema facilmente! Como? Simples, usando o return. Simples, retornámos o valor de x modificado para a função main. Escrevendo novamente o código.
Exemplo nº 2

E pronto tinhamos o problema resolvido.

Então vamos agora apresentar outro problema. Escrever uma função que dados dois valores x e y troca entre si os valores, ou seja:
* x = 10, y = 20
* fun (x,y)
* x = 20, y = 10

Este problema seria impossível de resolver se não tivessemos os ponteiros para ajudar! Não podemos fazer dois return's, ou seja, nunca vamos poder retornar os dois valores! Temos mesmo de arranjar uma forma de "invadir" o stack frame da função main e alterar lá os valores. Como fazer isto? Simples, ponteiros.
Este problema vai ser resolvido numa próxima parte deste artigo. Primeiro temos de conhecer bem como trabalhar com ponteiros.

Como repararam com certeza eu naquele pequeno "documento" pus uma definição para ponteiro. Basicamente um ponteiro é um tipo de dado que armazena nele um endereço de memória de outra variável ou objecto qualquer. Tudo em memória tem o seu endereço de memória, logo podemos ter o endereço de qualquer coisa e podemos ainda armazenar esse endereço num ponteiro. Com o ponteiro podemos ainda trabalhar directamente na variável para qual o ponteiro aponta, podemos alterar o seu valor, podemos realmente trabalhar com a variável em si através de um "comunicador" que é o ponteiro.

O operador em C que nos retorna o endereço de qualquer coisa é o &. Portanto, imaginemos que temos a variável x, o endereço da variável x pode ser obtido pela expressão &x. Bastante simples, uh?
Agora para termos esse endereço armazenado num ponteiro temos de, adivinhem só, declarar um ponteiro e atribuir &x a esse ponteiro.
Como se declara um ponteiro? Muito simples. Primeiro temos de saber sempre isto: Se temos uma variável int o ponteiro que aponta para essa variável tem de ser do tipo int também, se temos uma variável char o ponteiro que aponta para lá também tem de ser do tipo char e assim por diante!
Portanto, para declarar fazemos: int *pt. É exactamente a mesma coisa que declarar uma variável normal mas põe-se o * antes. Podemos declarar uma variável "normal" e um ponteiro na mesma linha, se forem do mesmo tipo obviamente. P.e. int *pt, x = 0. Neste caso apenas pt é um ponteiro!

Então já sabemos:
* Declarar um ponteiro
* Obter o endereço de uma variável

Sabemos também atribuir algo a algo.
Então vamos lá fazer um pequeno código que nos "põe" dentro de um ponteiro o endereço de uma variável. Pûs no inicio do código algumas notas que achei importantes.
Exemplo nº 3

Como podem ver o conteúdo de pt e o endereço de x são exactamente os mesmos, simplesmente porque atribuímos a pt o endereço de x através de: pt = &x.

A questão agora é o que é que podemos fazer com o endereço de x. Podemos sem dúvida alterar o seu valor e trabalhar com ele com o ponteiro pt. Fazemos isto com o operador *. Quando nos referimos a *pt estamos na verdade a referir-nos ao valor de x e quando nos referimos a pt, somente, estamos na verdade a trabalhar com o endereço de x, ou seja, com o conteúdo de pt.
Portanto, para trabalharmos com o valor de x temos de trabalhar com *pt. Vamos então alterar o valor de x através de pt.
Exemplo nº 4

Como podem ver neste exemplo trabalhamos várias vezes com *pt, pt e até com x e chegámos sempre ao mesmo resultado. Porquê? Simplesmente porque pt aponta para x e podemos trabalhar com x através de pt muito facilmente utilizando os operados que aprendemos até aqui.

Resumindo, o operador & retorna o endereço de alguma variável (e não só mas isso veremos mais para a frente). O operador * permite-nos referir ao valor da variável para qual o ponteiro aponta.

Termino então aqui a primeira parte deste artigo.
Aconselho desde já a pensarem como resolver o problema da troca de valores entre variáveis (criando um função que faz isso) e também a brincarem com todos os códigos que forneci até aqui. É de extrema importância que compreendam estes conceitos iniciais visto que vão ser usados para sempre daqui para a frente!

Espero que tenham gostado e que leiam a parte 2 quando esta for publicada.

Trie

2010-09-15T12:30:00.000-07:00

Finalmente voltei a ter tempo para voltar a escrever algo no blog.
Hoje trago uma estrutura de dados que considero muito útil que é a Trie.
É utilizada para armazenar strings e tem a vantagem de procurá-las muito mas mesmo muito rapidamente!

Adiciona uma string em O(M) em que M é o tamanho de string e o melhor é que procura em O(M) também! Com um típico array de strings teriamos uma tempo de pesquisa O(N) em que N é a quantidade de strings, ainda teríamos mais a comparação da string que queremos procurar com a que estamos a "atravessar" no momento, mas decidi desprezar esse factor.

O código está em C++ mas é facilmente "traduzido" para C (linguagem que costumo usar nestes meus posts aka artigos).

Deixo também mais alguma informação sobre a mesma estrutura de dados:
* Wikipédia
* TopCoder

Trie - Código

Este código lê as strings (1 string por cada linha) de um ficheiro chamado wordlist.in, não esquecer isto!

Resumindo:
* Tempo de inserção: O(M * N), N = Quantidade de strings (tempo total)
* Tempo de pesquisa: O(M)

Boas programações.

Binary Search

2010-05-13T06:30:00.000-07:00

Olá pessoal, hoje estou aqui para falar sobre Binary Search *AKA* Pesquisa Binária.

Primeiro vamos ver em que consiste. Binary Search é um método de pesquisa mais rápido e pode ser utilizado quando temos um array ou outra estrutura de dados ordenada. Imaginemos um array de 5 elementos chamado *array* e este é o conjunto de elementos que ele contém: {1,2,3,4,5}, como podemos ver ele está ordenado. Uma maneira de pesquisar, no entanto, lenta, seria percorrer o array todo e quando o elemento actual fosse igual ao que procurámos acabava a pesquisa. Isto leva O(n) operações, onde *n* é o número de elementos que o array tem. Isto pode levar muito quando o array cresce, no entanto, com binary search podemos reduzir este tempo de pesquisa para metade. O que fazemos é consultar o elemento do meio do array e verificar se este é igual ao elemento que procurámos, se for igual então parámos a pesquisa, se não for, verificámos se é menor, se for menor isso significa que o elemento que procurámos está para a direita (no sentido figurado, como é óbvio) do array (percebem porquê?). Se for maior significa que está para a esquerda do array. Este é o conceito de binary search e vamos agora aplicá-lo já na prática, vamos criar uma função que procura por um dado elemento num array.
Código

Se fossemos medir o tempo de pesquisa iriámos perceber logo que isto é muito mais rápido do que andar a percorrer o array todo.
Não comentei muito código porque acho que deu para perceber bem o conceito que é bastante simples de se entender. Espero que tenham gostado, até à próxima.

Lista Ligada - Exemplo

2010-04-18T07:00:00.000-07:00

Ora bem vou deixar aqui um exemplo de uma lista ligada com algumas funções úteis para quem está a começar a trabalhar com elas e quer exemplos.
Qualquer dia vou fazer um tut sobre elas mas por enquanto deixo este exemplo apenas.

Código da lista ligada

Obvio que podiámos ter funções mais complicadas como ordenar a lista e tal mas esta é simples e só foi mesmo para vocês perceberem. Testem bem as funções, mudem, experimentem, brinquem com elas. Se encontrarem algum bug deixem comentário.
Não comentei muito porque quem leu teoria percebe. Não é baseada em recursividade porque não gosto muito de trabalhar assim com elas. Espero que gostem. Até à próxima (:

Olimpiadas Nacionais da Informática 2010

2010-04-17T12:45:00.000-07:00

Bem, estamos a uma semana das ONI 2010. Esta é a primeira vez que vou participar e espero gostar.
Tenho passado vários dias a treinar na USACO, deixo aqui o link: USACO e vou agora na secção 1.4. Tenho de dizer que é um excelente programa de treinos para quem se quer iniciar em algoritmia e para quem quer treinar bem o racicionio.
Sobre as ONI espero que seja uma experiência muito positiva para mim e que conheça muito pessoal novo.
Deixo aqui um link para o Portugal a Programar que é o maior forúm de programação a nível nacional: P@P e também o link para o site das ONI para que se inscrevam e participem nesta aventura e quem sabe tenham a excelente oportunidade de representar Portugal nas IOI que são as Olimipiadas Internacionais da Informática que este ano vai ocorrer no Canadá.

Links:
Site das ONI 2010
USACO
Portugal A Programar
Site das IOI 2010

Boa sorte e boas programações.

Buffer overflow - Terrível demónio

2010-04-16T16:06:00.001-07:00

O que é o buffer overflow?
Buffer overflow é o facto de se passarem os limites do buffer, o buffer é a região de memória onde são lidos e escritos dados como strings por exemplo. Como vocês sabem as strings não são mais do que vectores de elementos de 1byte, os chamados chars ou caracteres. O que o buffer overflow faz ou é, melhor dizendo, é passar os limites desse buffer atingindo assim outras zonas da memória. Agora a pergunta que fica no ar é, o que é que isso tem de perigoso e que zonas é que são "atingidas"? Vamos ver isso a seguir.

O que é o/a stack?
O ou A, stack é o local da memória onde são guardados dados temporários como as variáveis locais, é também o que o computador utiliza para entradas e saída de dados rápidas. É também na/no stack que são guardadas as strings. O que têm de saber da/do stack é que nele/nela, quando é chamada uma função no vosso programa, é criado um stack frame (imaginem o stack frame como uma divisão do/da stack, quando temos várias funções são criados vários stack frame(s)). Ora bem, nesse stack frame vai ser onde vão ser armazenadas todas as variáveis da função e também um endereço, um endereço muito especial, o chamado, endereço de retorno.

O que é o endereço de retorno?
Quando chamamos uma função então é criado um stack frame, agora imaginem na vossa mente o stack frame, agora imaginem como é que no final da função o programa sabia por onde prosseguir a execução? Então para isso existe o endereço de retorno, ele contêm o endereço da próxima instrução de onde foi chamada a função. Para perceberem melhor, vou pôr aqui um código:
Exemplo 1

Vamos perceber o programa, declaramos uma string de 8bytes, e depois chamamos a função ~~gets~~, ora bem, no stack frame da função gets é criado as suas variáveis locais e também um endereço de retorno que contêm o endereço da próxima instrução do programa que neste caso é a função printf. Tentem imaginar isto como quando vamos fazer uma caminhada, pomos as pedras no caminho para não nos perdermos, digamos que a pedras são o endereço de retorno para o caminho principal.

Então como ocorre o buffer overflow?
Ora bem, quando nós passamos os limites do buffer a verdade é que tudo o que está "ao lado" dele vai entrar em contacto com os dados que passaram fora da string (no caso). Na verdade o buffer overflow é só isso, o "transboradamento", como o nome diz de dados pelo buffer fora. No entanto, ao lado do buffer muitas vezes está o endereço de retorno, e é aí que se tenta explorar, imaginem que se meta lixo até preencher o buffer e depois de se preencher, estando já em contacto com o endereço de retorno se coloque lá outro endereço, por exemplo um endereço para uma função maliciosa. Na verdade eu não estou aqui para vos explicar como explorar mas o que as pessoas mal intencionadas fazem não é meter um endereço mas sim uma coisa chamada de shellcode (procurem sobre isso no google). Para provar que é sobreescrito tudo que estiver ao lado do buffer (se forem passados os limites) compilem e executem este código:
Exemplo 2

E agora passem os limites da segunda string ou da primeira, neste caso não vamos estar em contacto com o endereço de retorno mas sim com a string que está a seguir dependendo da que quiserem, vejam então o output e tentem perceber o que aconteceu. Nota: Se estiverem em Linux vai dar um segmentation fault, não podendo assim verem o output, que é o meu caso.

Como se proteger?
Finalmente chegamos à parte da protecção, como nos podemos proteger disto tudo? É simples, usamos funções que verifiquem se a string do input é maior do que aquela que a vai receber. Vou introduzir uma lista a seguir então de funções vulneráveis e das que não são vulneráveis, relativamente a essas.

Funções - Lista (ex: Função_vulnerável - Função segura)
* gets - fgets;
* strcpy - strncpy;
* strcat - strncat
* scanf(strings) - fgets

Lista - O porquê de serem vulneráveis
* gets - A função gets, recebe um input e presupõe que o input nunca seja maior que o buffer que a vai receber.
* strcpy - A função strcpy presupõe que a string destino tenha capacidade para comportar a string origem.
* strcat - A função strcat presupõe que a string que a vai receber tem ainda capacidade para comportar a string que vai ser copiada
* scanf(se não forem incluídas restrições) - A função scanf tem as mesmas caracteristicas que a gets no caso de estarmos a ler strings. Não confundam com inteiros e outro tipos de dados.

Bem, estas são apenas algumas funções, muito poucas aliás mas já dá para ter uma ideia por isso sempre que utilizarem uma nova função pesquisem sobre ela.

O inicio

2010-04-16T16:02:00.000-07:00

Bem, após várias tentativas falhadas de criar um blog decidi mais uma vez tentar.
Este blog vai cobrir basicamente o mundo da informática, especialmente a parte da programação. Os conteúdos vão ser diversos mas vão estar mais focados na linguagem de C/C++.
Espero que gostem do conteúdo e que o visitem mais vezes.