PHP’s sort functions are bad designed

Everyone knows that is possible to sort an array in O(N log N) where N is the array’s length.

We know also, that Quicksort has expected complexity of O(N log N) but in worst case its complextity is O(N^2), and Quicksort is used more than Mergesort (worst case O(N log N)) because constants are smaller and it requires no extra memory and is easy to avoid Quicksort running on the worst case.

The easiest way to avoid bad inputs for Quicksort is choosing the pivot randomly, which means that a malicious user cannot guess a permutation for cracking it.

What I found at the PHP source is that the pivot choosing is done by picking the element at middle of array.

Here is the code (link line 76):

ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
{
	void           *begin_stack[QSORT_STACK_SIZE];
	void           *end_stack[QSORT_STACK_SIZE];
	register char  *begin;
	register char  *end;
	register char  *seg1;
	register char  *seg2;
	register char  *seg2p;
	register int    loop;
	uint            offset;

	begin_stack[0] = (char *) base;
	end_stack[0]   = (char *) base + ((nmemb - 1) * siz);

	for (loop = 0; loop >= 0; --loop) {
		begin = begin_stack[loop];
		end   = end_stack[loop];

		while (begin < end) {
			offset = (end - begin) >> 1; // HERE: choosing the current subarray's middle element 
			_zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);

			seg1 = begin + siz;
			seg2 = end;

			while (1) {
				for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
				     seg1 += siz);

				for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
				     seg2 -= siz);

				if (seg1 >= seg2)
					break;

				_zend_qsort_swap(seg1, seg2, siz);

				seg1 += siz;
				seg2 -= siz;
			}

			_zend_qsort_swap(begin, seg2, siz);

			seg2p = seg2;

			if ((seg2p - begin) <= (end - seg2p)) {
				if ((seg2p + siz) < end) {
					begin_stack[loop] = seg2p + siz;
					end_stack[loop++] = end;
				}
				end = seg2p - siz;
			}
			else {
				if ((seg2p - siz) > begin) {
					begin_stack[loop] = begin;
					end_stack[loop++] = seg2p - siz;
				}
				begin = seg2p + siz;
			}
		}
	}
}

The pivot is named offset here.

Tests

I used the usort() function for counting how many comparisons was needed to sort the array in my cmp() function.
So, lets see the tests:

<?php

$counter = 0; // counts how many comparisons
function cmp($a, $b)
{
	global $counter;
	++$counter;
	return $a - $b;
}

$normal = array();
for ($i = 0; $i < 15; ++$i) {
	$normal[] = $i;
}
shuffle($normal);

$counter = 0;
print "<pre>Normal array:\n";
usort($normal, 'cmp');
print $counter . " comparisons\n\n";

$malicious = array(2, 9, 4, 12, 6, 11, 8, 1, 3, 5, 7, 9, 10, 14, 12);

$counter = 0;
print "Malicious array:\n";
usort($malicious, 'cmp');
print $counter . " comparisons\n</pre>";

?>

And the results:
Normal array:
64 comparisons // variable because of the shuffle

Malicious array:
208 comparisons // constant


It means that the PHP’s sort() family depends on the input array’s length and content while a Randomized Quicksort depends only on the input array’s length.

As we can see, usort() sorted the randomly generated array of length 20 very fast with a few number of comparisons, but in the case of a manipulated array of length 20, the number of comparisons are much more.

In the same way, taking an array of length 10.000, these functions do around 50.000.000 comparisons when the expected is around 132.000. This can be a problem if some “bad” guy inserts manipulated data which your script will sort.

Solution

The naive solution is shuffle()‘n the array before sorting.

<?php

$malicious = array(11, 3, 20, 5, 13, 7, 17, 9, 15, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 19);
shuffle($malicious);

$counter = 0;
print "No longer malicious:\n";
usort($malicious, 'cmp');
print $counter . " coparisons\n</pre>";

?>

Output:
No longer malicious:
76 comparisons


References

zend_qsort source
PHP: sort() function
PHP: usort() function
PHP: shuffle() function
Quicksort – Wikipedia
Mergesort – Wikipedia

Fast and Easy Levenshtein distance using a Trie (in C++)

I implemented this clever algorithm described on Steven Hanov’s blog in C++. Actually this algorithm is a bit different from the original because I wanted to know what is the least Levenshtein distance given a word.

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

/*
 * Algorithm: Edit distance using a trie-tree (Dynamic Programming)
 * Author: Murilo Adriano Vasconcelos <muriloufg@gmail.com>
 */

using namespace std;

// Trie's node
struct trie
{
	typedef map<char, trie*> next_t;

	// The set with all the letters which this node is prefix
	next_t next;

	// If word is equal to "" is because there is no word in the
	//	dictionary which ends here.
	string word;

	trie() : next(map<char, trie*>()) {}

	void insert(string w)
	{
		w = string("$") + w;
		
		int sz = w.size();
		
		trie* n = this;
		for (int i = 0; i < sz; ++i) {
			if (n->next.find(w[i]) == n->next.end()) {
				n->next[w[i]] = new trie();
			}

			n = n->next[w[i]];
		}

		n->word = w;
	}
};

// The tree
trie tree;

// The minimum cost of a given word to be changed to a word of the dictionary
int min_cost;

//
void search_impl(trie* tree, char ch, vector<int> last_row, const string& word)
{
	int sz = last_row.size();

	vector<int> current_row(sz);
	current_row[0] = last_row[0] + 1;

	// Calculate the min cost of insertion, deletion, match or substution
	int insert_or_del, replace;
	for (int i = 1; i < sz; ++i) {
		insert_or_del = min(current_row[i-1] + 1, last_row[i] + 1);
		replace = (word[i-1] == ch) ? last_row[i-1] : (last_row[i-1] + 1);

		current_row[i] = min(insert_or_del, replace);
	}

	// When we find a cost that is less than the min_cost, is because
	// it is the minimum until the current row, so we update
	if ((current_row[sz-1] < min_cost) && (tree->word != "")) {
		min_cost = current_row[sz-1];
	}

	// If there is an element wich is smaller than the current minimum cost,
	// 	we can have another cost smaller than the current minimum cost
	if (*min_element(current_row.begin(), current_row.end()) < min_cost) {
		for (trie::next_t::iterator it = tree->next.begin(); it != tree->next.end(); ++it) {
			search_impl(it->second, it->first, current_row, word);
		}
	}
}

int search(string word)
{
	word = string("$") + word;
	
	int sz = word.size();
	min_cost = 0x3f3f3f3f;

	vector<int> current_row(sz + 1);

	// Naive DP initialization
	for (int i = 0; i < sz; ++i) current_row[i] = i;
	current_row[sz] = sz;
	
	
	
	// For each letter in the root map wich matches with a
	// 	letter in word, we must call the search
	for (int i = 0 ; i < sz; ++i) {
		if (tree.next.find(word[i]) != tree.next.end()) {
			search_impl(tree.next[word[i]], word[i], current_row, word);
		}
	}

	return min_cost;
}

The modification for match all words within a given Leveshtein distance and returning that set is trivial. Just modify the line 72 for storing that word if its Leveshtein distance is less than or equal to a given distance.

For more details, read this: Fast and Easy Levenshtein distance using a Trie
See ya!

Nunca retorne ponteiros para atributos de uma classe nem deixem atributos com acesso ‘public’

Esse post surgiu de uma dúvida que tive:

Como será que é feita a “proteção” dos atributos e funções-membro de classes em C++?

Com isso resolvi fazer  alguns testes e eis a classe de teste:

#include <iostream>
#include <string>

class security
{
private:
	std::string name;
	std::string password;
	int id;
	/* more stuff */
public:
	security() : name("John"), password("s3cr3t"), id(10) {}

	std::string* name_ptr() { return &name; }

	void print_pass()
	{
		std::cout << "The current password is: " << password << std::endl;
	}
};

A pergunta é: aonde pode estar o perigo nesse código (obviamente além de ter uma função-membro que imprime a senha na tela)?

Onde mora o perigo

O perigo maior reside na função-membro name_ptr(). Essa função por algum motivo (talvez o desenvolvedor queria fazer de name_ptr() um getter/setter por exemplo) delega um ponteiro para o atributo name.
Por ela retornar um ponteiro para um atributo da classe, acabamos com o sistema de proteção de acesso a atributos/funções-membro do C++:

int main()
{
	security obj;

	std::string* name = obj.name_ptr();
	std::cout << "Name: " << *name << std::endl;

	std::string* password = (std::string*)(name + 1);
	std::cout << "Password was: " << *password << std::endl;

	// Changing password
	*password = "l33t";

	obj.print_pass(); // whoa!!

	// For other data types
	int* id = (int*)(password + 1);
	std::cout << "ID: " << *id << std::endl;

	return 0;
}

Ou seja, a partir do ponteiro retornado por obj.name_ptr(), através de aritmética de ponteiros[0], podemos acessar qualquer outro atributo de um objeto da classe security, mesmo que estes não sejam public. Como podemos ver no exemplo acima, a partir do atributo name, podemos facilmente obter acesso aos outros atributos.

Outra falha é quando deixamos algum atributo como public:

#include <iostream>
#include <string>

class security
{
public:
	std::string name;
private:
	std::string password;
	int id;

	/* more stuff */

public:

	security() : name("John"), password("s3cr3t"), id(10) {}

	void print_pass()
	{
		std::cout << "The current password is: " << password << std::endl;
	}
};

Dessa maneira podemos também obter o endereço de name, agora apenas usando o operador & unário:

int main()
{
	security obj;

	std::string* name = &(obj.name);
	std::cout << "Name: " << *name << std::endl;

	std::string* password = (std::string*)(name + 1);
	std::cout << "Password was: " << *password << std::endl;

	// Changing password
	*password = "l33t";

	obj.print_pass(); // whoa!!

	// For other data types
	int* id = (int*)(password + 1);
	std::cout << "ID: " << *id << std::endl;

	return 0;
}

Observem que na linha 5, peguei o endereço do atributo name e fiz a mesma coisa do exemplo anterior.

Para os dois exemplos a saída é a mesma:

Name: John
Password was: s3cr3t
The current password is: l33t
ID: 10

Voltando à minha dúvida inicial…

Conclusão: pelo menos no compilador g++, a proteção é feita apenas pelo compilador (compile-time) e nenhum outro tipo de impedimento é usado. Ou seja, se você “adivinhar” o endereço de memória de um atributo de um objeto, você poderá ter acesso total à ele e aos outros atributos desse objeto.

Então, na hora de desenvolvermos nossas classes em C++, nada de retornar ponteiros para atributos de um objeto, nem de deixar atributos public quando se tem outros atributos não-public.

Update

Logo depois de eu fazer esse post, o WP automaticamente postou em meu Twitter e Facebook o link para este post. No Facebook recebi um comentário de um excelente programador o Maurício Collares (ou MauricioC no TopCoder[1]). Acho pertinente colar o comentário e também minha reposta aqui uma vez que estou vendo que esse post está tendo uma grande quantidade de leituras.

Maurício Collares Neto: Não sei se entendi qual o problema de alguém que já tem acesso de leitura à posicao “secreta” de memória (no sentido de não tomar um SIGSEGV) acessar tal posicao. Private e public são anotacoes existentes por motivos de Engenharia de Software, para evitar quebra de abstracoes; a grande maioria das linguagens oferece um jeito “fácil” de quebrar tal abstracao caso você precise fazê-lo (vide instrospeccao em Java).

Além disso, se você tem o endereco da da instäncia da classe (que pode ser obtido mesmo que vocë náo tenha nenhum membro público), você já tem acesso ao endereco de memória de todas as outras variáveis, do mesmo jeito; membros de classes são só syntactic sugar pra aritmética de ponteiros.

Murilo Adriano Vasconcelos: Interessante, eu não tinha pensado no fato de através do endereço do objeto podemos facilmente acessar qualquer atributo do objeto. E pensando melhor, mesmo que não houvesse esse tipo de facilidade no ponto de vista de objetos, teríamos acesso de alguma forma no no ponto de vista de processos, já que os processos tem total acesso às àreas de memória alocadas por ele.

Assim, e com o que você disse, fica totalmente anula o sentido do título do post (já que, por exemplo, seria o mesmo que dizer “Nunca instancie objetos”, um absurdo), porém poderei fazer uma atualização no post no sentido de apenas expor essa “feature” adicionando essa idéia de através de uma instância da classe acessar os outros atributos.

De qualquer forma, valeu pelo comentário, pena que foi só aqui no FB e não no blog, onde mais pessoas poderiam ter acesso à essa conversa.

Referências

[0] - Aritmética de ponteiros em C e C++ (Wikipedia)

[1] – TopCoder

Políticas de Controle de Comportamento em C++

Trabalhando no meu projeto na Boost, fui requisitado a implementar uma função para calcular o logaritmo na base 2 de números inteiros. De prontidão pesquisei qual a melhor forma e implementei-a da maneira mais otimizada possível. Fiz um Request For Comments (RFC) na mail list da Boost para saber opiniões sobre qual deveria ser o nome de tal função. Bom, depois de alguma conversa ficou (ao menos por enquanto) decidido que o melhor nome é ilog2.

Bom mas havia um problema logaritmo de 0 é indefinido. E na documentação eu coloquei:

If `value` is equal to 0, the value returned is undefined

Foi aí que um contribuidor da Boost chamado Paul Bristow recomendou a mim que fizesse com que esse comportamento (ilog2(0)) pudesse ser controlável através de políticas, mais especificamente usando boost::math::policies. Resisti um pouco no começo mas cedi e achei bastante interessante.

O que são políticas de tratamento de comportamento?

Basicamente são meios de controlar o comportamento de um algoritmo em certas situações (como o ilog2(0) por exemplo).

Um exemplo de política muito utilizada na biblioteca padrão são as classes que usam std::allocator.

Em C++ podemos implementar políticas facilmente em tempo de compilação.

Implementando Políticas

Vamos então implementar um modelo de política bem simples. Tomei por base as Policies da biblioteca Math da Boost, porém muito mais simplificada por questão de didática.

#ifndef POLICIES_HPP_INCLUDED
#define POLICIES_HPP_INCLUDED

#include <cerrno>      // errno
#include <stdexcept> // std::domain_error

namespace policies
{

// Nossa política
enum error_policy_type
{
	ignore_error = 0,
	errno_on_error,
	throw_on_error,
	user_error
};

// continua

Esse enum define a regra que queremos utilizar em nossa política.

• ignore_error: ignora o erro e retorna um valor padrão.
• errno_on_error: seta errno e retorna um valor padrão.
• throw_on_error: dispara uma exceção.
• user_error: executa uma função customizada definida pelo usuário, note que a declaração dessa função já existe, tendo apenas que ser feita a definição dessa função.

No caso defini 4 tipos de erros mas pode-se ter mais coisas como “dialog_on_error” se seu projeto utiliza GUI e você quer que apareça uma dialog box informando algo, de qualquer maneira pode-se também usar o user_error se for aplicável.

// continuação

template <int P>
struct domain_error
{
	const static int policy = P;
};

template <int P>
struct overflow_error
{
	const static int policy = P;
};

Aqui declaramos nossos tipos de erro. É basicamente um wrapper para nossas constantes declaradas no enum anterior. P é a política que queremos aplicar. Por exemplo typedef overflow_error<errno_on_error> my_pol;, my_pol é uma política que para tratar overflow_error seguindo a regra errno_on_error. Novamente podemos ter vários tipos de erros que queiramos tratar, coloquei esses dois como exemplo. Notemos também que para simplicidade não tratei os possíveis valores que P pode assumir.

typedef domain_error<ignore_error> default_domain_policy; typedef overflow_error<errno_on_error> default_overflow_policy;

Aqui definimos quais as políticas padrões para cada tipo de erro. No caso definimos que a política padrão que deve ser seguida quando um domain_error for lançado é a ignore_error. Veremos mais para frente sugestões de como tratar cada política.

// Only the declaration, must be defined somewhere
template <typename T>
T user_domain_error(const char* function, const char* message, const T& val);

template <typename T>
T user_overflow_error(const char* function, const char* message, const T& val);

Aqui nós apenas declaramos os protótipos das funções que serão chamadas quando um user_error for lançado. Se alguém usar a política user_error, este deverá codificar essas funções em algum outro lugar.

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<ignore_error>&)
{
	// Simply ignoring the error
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<errno_on_error>&)
{
	// Sets errno to Error DOMain
	errno = EDOM;
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<throw_on_error>&)
{
	throw std::domain_error(message);
	
	// This will never be returned
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<user_error>&)
{
	return user_domain_error(function, message, val);
}

}

Essas são as funções chamadas para lançar um domain_error. Note que para cada política definimos uma função para tratá-la. Por questão de simplicidade, defini apenas as funções que tratam as políticas de domain_error, para overflow_error por exemplo, precisaríamos definir raise_overflow_error() com sobrecargas para cada política diferente.

O protótipo das funções pode ser modificado de acordo com o que você necessitar. Aqui defini quatro parâmetros:

• function – o nome da função que causou o comportamento (erro)
• message – a descrição do que causou o comportamento.
• val – o valor que essa função deve retornar (quando aplicável)
• const policies::domain_error& – utilizado para fazer a sobrecarga de função, onde X é a política a ser tratada.

Pode paracer meio desgastante porém depois de pronto, seu sistema complexo pode se beneficiar com transparência das políticas que não devem ser tantas.

A Boost Math por exemplo define apenas 6 tipos de erros e as mesmas 4 políticas que estou usando como exemplo.

Exemplo de uso

Agora suponhamos que tenhamos que implementar uma função que faz a divisão de dois elementos a e b (ohhh divisão!). Essa função, chamada divide, está sendo representada abaixo.

Como sabemos, divisão por zero não existe, então para uma solução elegante para nossa função super complexa, iremos utilizar as nossas políticas.

#include "policies.hpp"

template <typename T, typename Policy>
T divide(T a, T b, const Policy& pol)
{
	if (b == 0) {
		return policies::raise_domain_error("divide(a, b)", 
			"Cannot divide by zero", 
			T(0),   // Value to be returned  
			pol  // Our policy
		);
	}
	
	return a / b;
}

template <typename T>
inline T divide(T a, T b)
{
	return divide(a, b, policies::default_policy());
}

Como pudemos notar, declarei duas funções divide, uma aceitando dois parâmetros que serão computados e a outra aceitando um parâmetro a mais que é a política a ser utilizada. A versão de dois parâmetros na verdade é somente um forwarder para a outra passando a política padrão para ser utilizada. O valor padrão a ser retornado é 0, como podemos notar em T(0).

O “mau” comportamento ocorre quando b == 0, então, se essa condição for satisfeita, simplesmente lançamos um domain_error utilizando a função raise_domain_error.

Para o usuário da função isso é transparente se ele não quiser trabalhar com as políticas, já que uma política padrão é adotada e um valor padrão é retornado.

int main()
{	
	using namespace policies;
	
        // Default policy, zero is returned
	assert((divide(1, 0) == 0));

	typedef domain_error<errno_on_error> errno_pol;
	typedef domain_error<ignore_error>   ignore_pol;
	typedef domain_error<throw_on_error> throw_pol;
	
	// Testing errno_on_error policy, errno is set equal EDOM
	errno = 0;
	divide(1, 0, errno_pol());
	assert((errno == EDOM));
	
	// Testing ignore_error policy, zero is returned
	assert((divide(1, 0, ignore_pol()) == 0));
	
	// Testing throw_on_error policy, a std::domain_error is threw
	try {
		divide(1, 0, throw_pol());
		
		// Never is threw
		throw "error 0";
	}
	catch (std::domain_error&) {
		// FINE!!!
        // Sucessfully caught!
	}
	catch (...) {
                // Bad!
		throw "error 1";
	}
	
	return 0;
}

Se estiver tudo certo, programa acima deve (após ser compilado) ser executado sem nenhuma saída e com nenhuma exceção.

Ficou agora faltando demonstrar apenas como usar as políticas com user_error.

#include <iostream>
#include "policies.hpp"
#include "divide.hpp"

namespace policies {
template <typename T>
T user_domain_error(const char* function, const char* message, const T& val)
{
	std::cout << "Problem on calling function "<< function << std::endl;
	std::cout << "Value " << val << " will be returned " << std::endl;
	
	// DialogBox db(message); or anything you want
	
	return val;
}
}

int main()
{
	policies::domain_error<policies::user_error> usr_err;
	divide(1, 0, usr_err);
        /*  Saída:
  	     Problem on calling function divide(a, b)
             Value 0 will be returned 
         */

	return 0;
}

Como pudemos ver, basta apenas definirmos a função user_domain_error do modo que quisermos para que possamos usar essa política. No caso acima apenas imprimimos uma mensagem com duas linhas e retornamos val.

Arquivos

policies.hpp
divide.hpp
policies_example.cpp
user_error.cpp

Referências

Boost Math Policies
ilog2 implementation
Policy Classes On Generic Programming Techniques from Boost

C++ Idioms: SFINAE

Introdução

Nesse post falarei sobre uma técnica (ou recurso) utilizada em  C++ que estou utilizando muito no meu projeto[0][1] na Boost Libraries[2] no GSoC, essa técnica é o SFINAE.

SFINAE[3] é uma sigla para “Substitution failure is not an error” que em uma tradução livre quer dizer “Falha na substituição não é um erro”. Segundo[3]:

SFINAE se refere a uma situação em C++ que uma substituição inválida de templates não é um erro.

Especificamente, na criação de um conjunto candidato para a resolução de sobrecarga, alguns (talvez todos) os candidatos deste conjunto pode ser resultante da substituição de argumentos templates deduzidos para os parâmetros de template. Se um erro ocorre durante a substituição, o compilador remove essa potencial sobrecarga do conjunto candidato ao invés de parar com um erro de compilação. Se restam um ou mais candidatos (i.é: pelo menos uma sobrecarga é válida), a resolução é feita e a invocação é bem formada.

Como funciona

Para entender melhor vejamos esse trecho de código:

template <typename T>
struct A
{
	typedef T type;
	T value;
};

template <>
struct A<bool>
{
};

template<typename T>
typename A<T>::type func(const A<T>& param)
{
	std::cout << param.value << std::endl;
}

Esse código compila sem warnings. A função template func() é sobrecarregada e retorna o tipo T. Mas você deve estar se perguntando, o que acontece quando T = bool? Esse é justo o ponto do SFINAE!
Para T = bool, typename A::type seria uma declaração inválida já que A não contém o tipo type declarado, porém, com SFINAE, essa sobrecarga é simplesmente descartada e para qualquer outro T que não bool, func(A) é uma chamada legal porque sua sobrecarga é gerada.

Aplicações

Como eu disse no começo deste post eu estou utilizando bastante SFINAE no meu projeto do Google Summer of Code com uma utilidade chamada enable_if[4] encontrado na Boost.

Enable_if é uma classe (ou struct) que “ativa” a declaração de algo (classe, função, etc) se uma condição for satisfeita por meio do SFINAE. Vou mostrar aqui uma maneira de fazer um enable_if like, e quem quiser saber mais sobre o enable_if da Boost é encorajado a ler[4][5].

Vamos ao código:

/* Cond é a condição de ativação
 * Type é o tipo que será declarado pelo membro type.
 */
template <bool Cond, typename Type = void>
struct enable_if_c
{
	typedef Type type;
};

/*
 * Especialização, quando Cond for false,
 * 	esse template vazio é invocado.
 */
template <typename Type>
struct enable_if_c<false, Type>
{
	// empty
};

Ou seja, sempre quando Cond for true, existirá um membro type declarado em enable_if_c, quando Cond for false o membro type não existirá.

Um exemplo de uso:

/*
 * Nossa função pega o bit mais significativo de value e retorna um bool.
 * 	***Note que nesse exemplo estamos assumindo que T é um tipo inteiro.***
 */

/*
 * Para retornar o bit mais significativo de um T com 4bytes (32 bits),
 * 	deslocamos 31 bits para a direita e fazemos um & com 1.
 */
template <typename T>
typename enable_if_c<sizeof(T) == 4, bool>::type msb(T value)
{
	std::cout << "Value have 4 bytes.\n";
	return (value >> 31) & T(1);
}

/*
 * Porém se T é um tipo de 1byte (8 bits) o deslocamento deve ser de
 * 	7 bits para pegarmos o bit mais significativo.
 */
template <typename T>
typename enable_if_c<sizeof(T) == 1, bool>::type msb(T value)
{
	std::cout << "Value have 1 byte.\n";
	return (value >> 7) & T(1);
}

Ou seja, a função de cima, é sobrecarregada para todos os tipos que tenham 32 bits (sizeof(T) == 4) e a de baixo é sobrecarregada para todos os tipos que tenham 8 bits (sizeof(T) == 1). Assim, no processo de resolução de sobrecarga, os outros tipos que não tem nem 8 nem 32 bits, são descartadas pois cairá na especialização enable_if_c que não possui um membro type (usado como retorno da função msb), comportamento citado anteriormente.

Para testar:

int main()
{
	int a = -3;
	unsigned b = 190000;
	char c = 129;
	uint16_t d = 10;
	uint64_t e = 10000000;
	
	std::cout << "Retorno int: " << msb(a) << std::endl;
	std::cout << "Retorno unsigned: " << msb(b) << std::endl;
	std::cout << "Retorno char: " << msb(c) << std::endl;
}

Se tentarmos executar com uma condição que não é true, teremos um erro em tempo de compilação, como podemos ver abaixo:

...
uint16_t d = 10;
uint64_t e = 10000000;

std::cout << "Ret: uint16_t: " << msb(d) << std::endl
std::cout << "Ret: uint64_t: " << msb(e) << std::endl;
...

/*
/Users/murilo/Documents/programming/blog/sfinae.cpp: In function ‘int main()’: /Users/murilo/Documents/programming/blog/sfinae.cpp:61: error: no matching function for call to ‘msb(uint16_t&)’ 
/Users/murilo/Documents/programming/blog/sfinae.cpp:62: error: no matching function for call to ‘msb(uint64_t&)’
*/

Alguns outros exemplos usando o enable_if da Boost você pode encontrar no meu projeto[1] na Boost onde utilizo enable_if aos montes.

Nesse post exemplifiquei SFINAE com funções, mas também é aplicável para classes. Um exemplo você pode ver aqui [6].

Até a próxima!

Referências

[0] – Estou no Google Summer of Code 2010 – http://murilo.wordpress.com/2010/05/03/estou-no-google-summer-of-code-2010
[1] – Source of Bits and Ints project – https://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boost/integer
[2] – Boost C++ Libraries – http://www.boost.org/
[3] – Artigo “Substitution failure is not an error” na Wikipedia – http://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
[4] – Boost enable_if – http://www.boost.org/doc/libs/1_43_0/libs/utility/enable_if.html
[5] – enable_if.hpp – http://www.boost.org/doc/libs/1_35_0/boost/utility/enable_if.hpp
[6] – static_sign_extend.hpp at Boost Trac – https://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boost/integer/static_sign_extend.hpp

Estou no Google Summer of Code 2010

Olá pessoal.

Esse ano fui um dos (2^10 + 4) selecionados para passar alguns meses programando nesse evento.

O que é o Google Summer of Code?

O Google Summer of Code (GS0C) é um programa realizado pela Google que consiste em incentivar o e divulgar o software livre entre os estudantes. A filosofia do GSoC é “flip bits not burgers” que é a de incentivar os estudantes em seu período de férias de verão (as nossas férias são no inverno) a programarem, não trabalhar por exemplo em fast-foods como é comum principalmente nos Estados Unidos.

Neste programa, a Google paga aproximadamente 5000 dólares para cada estudante que ao final do programa tenha completado seu projeto.

Funciona assim: os estudantes escolhem uma ou mais organizações de software livre que foram aceitas pelo programa para trabalhar com elas. Aí o estudante tem que propor um projeto para essa organização que pode ser algo do tipo:

• Implementar uma nova ferramenta
• Corrigir bugs
• Documentar código
• Melhorar o desempenho de alguma ferramenta
• Portabilizar para alguma(s) plataforma(s)
• Adicionar features à alguma ferramenta
• etc.

Feito isso, há uma seleção interna e logo é divulgado no site do GSoC a lista de aceitos.

Em seguida você tem uma pessoa alocada pela organização para te ajudar que chamamos de mentor.

Ao final do programa, além dos dólares a mais, o participante ganhará uma camiseta do programa e, no meu ver o mais importante, o certificado emitido pela Google atestando a sua participação.

Eu no GSoC 2010

Eu escolhi a Boost que é um conjunto de bibliotecas para C++ (com bindings para Python) amplamente utilizada no mundo inteiro. Algumas bibliotecas Boost já foram inseridas no padrão C++ através do TR1 (e algumas outras serão inseridas no próximo padrão) e por isso as bibliotecas Boost sejam talvez as mais respeitadas, digamos assim, bibliotecas para C++.

Minha proposta é implementar algoritmos rápidos para manipulação de dados binários em inteiros. Se você quiser saber como é a “cara” das coisas que terei que fazer, aqui você encontra alguns dos algoritmos que implementarei.

Meu mentor chama-se Vicente J. Botet Escribá que parece ser uma bastante pró-ativa e que saca bastante e que tem um blog com conteúdo bem interessante.

Ah, e parabéns ao Marcos Roriz meu colega de universidade que também teve seu projeto aprovado.

O abstract do meu projeto e do Marcos podem ser acessados aqui.

Até mais!

Meta-Programação por Templates

Ultimamente estou me aventurando por essas terras misteriosas e estou fascinado.

Segundo o Wikipedia[1] Meta-programação por templates (TMP ou Template metaprogramming) é:

Template metaprogramming is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates include compile-time constants, data structures, and complete function

Ou seja TMP é uma técnica usada para gerar código-fonte em tempo de compilação. Isso quer dizer que, no momento da compilação, as chamadas à esse tipo de código são avaliadas, o código correspondente é gerado e o resultado já é conhecido, antes mesmo do programa ser executado!

Uau!! Isso é perfeito! Resolverá todos meus problemas…

Não é bem assim, como tudo é feito em tempo de compilação, os valores de entrada para esses algoritmos também devem ser conhecidos em tempo de compilação. Isso quer dizer que os valores de entrada devem ser constantes.

Eis um exemplo de código C++ usando essa abordagem:

#include <iostream>

template<int V>
struct Int { enum { value = V }; }; // representa um valor inteiro

template<int V>
struct bin : Int<(V % 10) + 2 * (bin<V / 10>::value)> {}; // algoritmo recursivo

template<> struct bin<0> : Int<0> {}; // base da recursão

int main()
{
	std::cout << "1000b == " << bin<1000>::value << "d\n";
	std::cout << "10001b == " << bin<10001>::value << "d\n";
	std::cout << "111b == " << bin<111>::value << "d\n";
	std::cout << "10b == " << bin<10>::value << "d\n";
	
	return 0;
}

Como ainda estou aprendendo a respeito, vou finalizar esse post nesse código. Caso queiram discutir o tema em questão, sintam-se a vontade!

Links:

[1] Template Metaprogramming no Wikipedia
Outro material sobre TMP
Boost MPL – biblioteca Boost que provê frameworks para meta-programação

A importância de declarar os destrutores como virtual em C++

Funções Virtuais

Depois de muito tempo sem postar algo aqui vou falar sobre um especificador do C++ que muitas vezes é esquecido: a keyword virtual.

Essa keyword é utilizada para dizer que queremos que faça a avaliação da chamada dessa função em run-time, não em compile-time como é feito por padrão.

Mas no que isso pode ajudar?

#include <iostream>

struct base
{
	void funcao()
	{
		std::cout << "chamada da base\n";
	} 
	
	virtual void vfuncao()
	{
		std::cout << "chamada da base\n";
	}
};

struct derivada: public base
{
	void funcao()
	{
		std::cout << "chamada da derivada\n";
	} 
	
	void vfuncao()
	{
		std::cout << "chamada da derivada\n";
	}
};

int main()
{
	base* pt = new derivada;
	
	//nao virtual
	pt->funcao();
	
	//virtual
	pt->vfuncao();
	
	delete pt;
	
	return 0;
}

Saída:

chamada da base
chamada da derivada

Ou seja, quando uma função-membro (aka. método) é declarada como virtual na classe base, a checagem em run-time é feita e é possível encontrar a vfuncao() na classe

derivada

, assim chamando a função correta, o que não acontece com funcao(): apesar de ter uma função-membro com mesmo nome na classe derivada, é chamada a funcao() da classe base porque o ponteiro que a referencia é do tipo da classe base. Pra isso serve a keyword virtual (êba, vamos usá-la daqui pra frente!).

Mas e os destrutores virtuais?

Segue a mesma idéia e com um agrave de risco eminente de memory leaks!
Se na classe base não temos o destrutor declarado como virtual, temos um grande problema. Vejamos o exemplo:

#include <iostream>

class base 
{
	int* ptr;
public:
	base()
	{
		ptr = new int;
	}
	
	~base() 
	{
		delete ptr;
		std::cout << "'destruindo' base\n";	
	}
};

class derivada: public base
{
	int* dptr;
public:
	derivada() {
		dptr = new int;
	}
	~derivada()
	{
		delete dptr;
		std::cout << "'destruindo' derivada\n";
	}
};

int main()
{
	base* pt = new derivada;
	delete pt;
}

Saída:

'destruindo' base

Como podemos ver, apenas o destrutor da classe base é chamado, deletando o ponteiro ptr. Mas e o dptr declarado em derivada e alocado em seu construtor? Leaked! Se perdeu!

A solução é declarar o destrutor da classe base como virtual e a mágica acontece.

#include <iostream>

class base 
{
	int* ptr;
public:
	base()
	{
		ptr = new int;
	}
	
	virtual ~base() 
	{
		delete ptr;
		std::cout << "'destruindo' base\n";	
	}
};

class derivada: public base
{
	int* dptr;
public:
	derivada() {
		dptr = new int;
	}
	~derivada()
	{
		delete dptr;
		std::cout << "'destruindo' derivada\n";
	}
};

int main()
{
	base* pt = new derivada;
	delete pt;
}

Saída:

'destruindo' derivada
'destruindo' base

Conclusão

É aconselhável que seus destrutores sejam virtuais e que pondere nas outras funções, pois tudo que deixa de ser feito em compile-time e passa a ser feito em run-time, gera overhead na sua aplicação (é… nem tudo é maravilha). Até a próxima!

Static Template Matrix – uma abordagem diferente

Static Template Matrix?

De fato eu nunca vi esse nome em outro lugar, mas foi o nome que eu pensei que se aproxima mais da implementação que veremos nesse post.

Trata-se template de uma matriz (matrix) de duas dimensões de tamanho constante (static). Uma das diferenças dessa matriz é que ao invés de se usar o convencional operator[] para acessar os elementos, nessa abordagem iremos utilizar o operator().

Motivações

Na realidade, não tem muito mais utilidades práticas do que matrizes normais. Pode ser que pode servir em algo para você. Então minha motivação é puramente de aprendizagem, principalmente da linguagem.

matrix.h

#ifndef _CLASS_MATRIX_H__
#define _CLASS_MATRIX_H__

/**
 * matrix.h
 * Defines a template type 'matrix' wich is a constant-sized 2-dimensioned
 * 	matrix and generic typed elements.
 *
 * author: Murilo Adriano Vasconcelos
 * website: http://murilo.wordpress.com
 */

/**
 * T = value type
 * R = number of rows
 * C = number of columns
 */
template <typename T, unsigned R, unsigned C>
class matrix
{
    //data matrix
    T data[R][C];

public:
    //type of the current matrix
    typedef matrix<T, R, C> type;
    typedef T            value_type;

    //quantity of rows
    const unsigned rows;
    //quantity of columns
    const unsigned columns;

    //default ctor
    matrix(): rows(R), columns(C) {};

    /*ctor wich initializes the matrix filled
      with 'value' elements */
    matrix(const T& value);

    //copy ctor: copies the matrix 'tocopy'
    matrix(const type& tocopy);

    /*gets and/or set the value of the element
      in the row 'i', column 'j' */
    T& operator()(unsigned i, unsigned j);

    /*gets the value of the element in the
      row 'i', column 'j' */
    const T& operator()(unsigned i, unsigned j) const;

    //copy operator
    type& operator=(const type& tocopy);
};

/* class functions definition */

template <typename T, unsigned R, unsigned C>
matrix<T, R, C>::matrix(const matrix& tocopy): rows(R), columns(C)
{
    for (unsigned i = 0; i < R; i++)
        for (unsigned j = 0; j < C; j++)
            data[i][j] = tocopy(i, j);
}

template <typename T, unsigned R, unsigned C>
matrix<T, R, C>::matrix(const T& value): rows(R), columns(C)
{
    for (unsigned i = 0; i < R; i++)
        for (unsigned j = 0; j < C; j++)
            data[i][j] = value;
}

template <typename T, unsigned R, unsigned C>
matrix<T, R, C>& matrix<T, R, C>::operator=(const matrix& tocopy)
{
    for (unsigned i = 0; i < R; i++)
        for (unsigned j = 0; j < C; j++)
            data[i][j] = tocopy(i, j);

    return *this;
}

template <typename T, unsigned R, unsigned C>
T& matrix<T, R, C>::operator()(unsigned i, unsigned j)
{
    return data[i][j];
}

template <typename T, unsigned R, unsigned C>
const T& matrix<T, R, C>::operator()(unsigned i, unsigned j) const
{
    return data[i][j];
}

#endif

main.cpp

#include "matrix.h" //our matrix
#include <iostream>  //cout'ing
#include <string>   //for strings

int main()
{
        //declares a 3x3 matrix filled with "nil"
        matrix<std::string, 5, 5> mat("nil");

        //modifies the value in the position (1, 1) to C++
        mat(1, 1) = "C++";

        //we can use the const atribbutes rows and columns
        //to check our limits
        for (unsigned i = 0; i < mat.rows; i++) {
                for (unsigned j = 0; j < mat.columns; j++) {
                        //getting, setting the value of matrix elements
                        //is the same way
                        std::cout << mat(i, j) << ' ';
                }

                std::cout << '\n';
        }

        std::cout << '\n';

        matrix<int, 3, 3> ones(1), identity;
        //copy
        identity = ones;

        //so silly
        for (unsigned i = 0; i < identity.rows; i++) {
                for (unsigned j = i; j < identity.columns; j++) {
                        if (i != j) {
                                identity(i, j) = identity(j, i) = 0;
                        }
                }
        }

        for (unsigned i = 0; i < identity.rows; i++) {
                for (unsigned j = 0; j < identity.columns; j++) {
                        std::cout << identity(i, j) << ' ';
                }

                std::cout << '\n';
        }

        return 0;
}

Como vocês puderam notar, a forma de acesso e modificação (get, set) dos elementos da matriz é da mesma forma. Outra coisa que podemos notar é que passamos o tipo e a quantidade de linhas e colunas direto no template. A quantidade de linha e colunas passada deve ser uma constante.

Bom, até mais.

obs.: Eu odeio profundamente o source highlight bugado do WordPress que converte todos os meus < e > e etc. para &lt; &gt;. Por isso os fontes acima não estão com hl.

Fixed!

Agora sim, até mais.

Regional da Maratona de Programação 2009

Considerações

Bem, eu ainda não tinha escrito nada sobre a fase regional da XIV Maratona de Programação que ocorreu dia 19 de setembro por falta de tempo e porque não havia recebido as fotos do evento.

O primeiro ponto que quero destacar é a estrutura da regional aqui de Goiânia. Não deixou nada a desejar! Ambiente ótimo, infra-estrutura boa, máquinas, espaço, equipamento, organização. Tenho que parabenizar os professores que organizaram o evento, principalmente os professores Humberto Longo e Cláudio Nogueira do INF-UFG.

Esse ano (2º da regional de Goiânia) participaram 11 equipes de 5 instituições: ALFA (1), IFG-Morrinhos (2), UEG (2), PUC-GO (3) e INF-UFG (3).

Local da competição

Antes…

Na chegada das equipes, pude reencontrar vários amigos, principalmente da PUC-GO e aí os assuntos ficaram em dia (conversamos sobre computação, lógico). O clima estava típico de uma decisão mesmo: em um segunto estávamos conversando e rindo, no outro estávamos tensos e pensativos.

Galera no corredor

Antes de começar o warm-up, tivemos uma “mini-palestra” sobre as regras da maratona e de como usar o sistema BOCA e entregas de credenciais, logins/senhas e das plaquinhas que identificam as equipes.

Pré-warm-up

O warm-up foi tranquilo, só pra testes mesmo. Parece que houve um problema no julgamento do problema “Bolhas e Baldes” que posteriormente foi solucionado.

Fim de warm-up, fomos almoçar. Como o campus é uma cidade a parte, quase todo mundo almoçou no mesmo lugar, tendo calculado o menor caminho ou não .

Começa a maratona e aí vira tensão…

Começa a competição e com 6 minutos, minha equipe (UFG – Monkeys) recebe o primeiro AC da competição: problema B – “Alarme”, Carlitos na implementação. Não sei dizer mas acho que esse foi um dos balões mais rápidos do Brasil.

Não demorou e nossa principal rival, a PUC-GO – Mother Focas, e a UFG – Sobrevientes do RU conseguiram também seus balões amarelos.

Os Focas: Jackie, Divinera e Marciano

Até os 3 primeiros balões nós lideramos com uma certa vantagem no tempo. O problema foi quando os Focas conseguiram o quarto balão e nós não. Aí bateu aquele “caramba, agora fodeo!”. Aí focamos no problema (que por sinal era muito simples) e mandamos… Recebemos um NO bem grande e aí bateu o desespero. Consegui achar a lógica, conferi com meus colegas a corretude e, finalmente YES! Na hora olhamos para o Score que estava num telão na nossa frente e vimos que tinhamos passado os Focas (na verdade olhei o score mesmo assim deu um branco não saquei nada e tive que perguntar a nossa posição pra minha equipe [sic]).

Alguns balões

Ficamos focados no problema G – “Registrador” e perdemos tempo, muito tempo [sic²]. Quando vimos, tinham 6 equipes com 4 balões, aí de novo bateu o pensamento “fodeo”…

No freeze, conseguimos formular um algoritmo pro E – “Dragster” mas aí já era tarde… Estávamos exaustos e não conseguimos codificá-lo. Enquanto isso, eu estava tentando ter a sacada do F – “Torres de Celular” (pô, tava na cara e eu não enxerguei). E o freeze-time foi isso: Diego e Carlos no Dragster (esse dava hein) e eu tentando algo no Torres de Celular.

Nosso quarto balão. Monkeys: Murilo, Carlos e Diego

A cada vez que nós víamos alguem teclando algo no freeze, dava um frio na barriga. Tentamos fazer uns “cortes” no registrador e mandamos várias outras vezes.

Score Final

Por um problema na rede (ou de juízes engraçadinhos), o score final demorou uma eternidade após a competição a ser apresentado a nós (aproximadamente 4min e 30seg). Anunciado o vencedor, só alegria.

Comemoração

Mais algumas fotos

PUC-GO Bit a bit: Douttor, Mauricinho e Loos

UFG - Sons of a Bit: Nemo, Will e PC

UFG - Sobreviventes do RU: Everton, Will e Lup

A única competidora, o japa e o barba

Os melança

Premiação

É… teve premiação com direito a reitor e tudo mais. Auditório cheio e prêmios para os vencedores

As três primeiras equipes ganharam camisetas geeks, medalhas e trófeus além de um livro (alguns dos prêmios concedidos pela SistemasAbertos).

Nós da Monkeys ganhamos uma camiseta personalizada da Maratona de Programação, como essa abaixo do Longo branca.

3º Lugar - UFG - Sons of a Bit e o coach Humberto Longo

2º Lugar - PUC-GO - MotherFocas, pró-reitora de graduação e o coach Alexandre

1º Lugar - UFG - Monkeys, coach: Humberto Longo e o reitor

MONKEYS

E agora…

Final Nacional em Campinas

Rumo a Tóquio, ops, Harbin na China!!

O scoreboard, clarifications e etc podem ser visualizados aqui.