Arquivos | computação RSS for this section

Opinião: No curso de computação eu uso cheat, no curso de computação eu uso Linux!

Há esses pequenos detalhes que eu percebo na parte da realidade a qual eu tenho acesso e talvez se repita em outros lugares. Após um tempo “martelando a ideia”, resolvi sentar para escrever o relato acompanhado de minha opinião. Nesse texto vou comentar sobre o porquê de eu achar que ter optado pelo Linux me deu vantagem sobre outros programadores do curso que faço.

A linguagem C

A primeira coisa a entender na história é a importância da linguagem C. A linguagem C é uma espécie de “Assembly portável”. Entre o código escrito pelo programador e o código gerado pelo compilador não deveria haver nenhum gargalo desnecessário. O código gerado deveria ser tão ou mais rápido que o código que o programador escreveria manualmente. Uma das formas de alcançar essa eficiência é através de Undefined Behaviour, pois assim, entre outras coisas, o código se adapta ao comportamento do hardware em muitas situações. Em C, até a ordem de avaliação dos operandos não é especificada.

Com sua proposta, a linguagem C tornou-se uma das principais linguagens no mundo da computação. Sistemas operacionais são construídos na linguagem C, sistemas para dispositivos embarcados são construídos na linguagem C, sistemas com restrições de tempo real são construídos na linguagem C, para citar alguns. Devido aos sistemas operacionais serem, principalmente, escritos em C, normalmente a linguagem C possui tratamento privilegiado em relação a comunicação com o sistema operacional e normalmente até os interpretadores de outras linguagens são escritos em C. Devido a sua importância, aprender C ajuda a ter uma visão geral dos diferentes componentes que compõem o sistema. Não só é interessante aprender C por sua importância, mas também porque a linguagem expõe conceitos interessantes que não estão presentes em linguagens que fogem do hardware e se aproximam demais com definições algorítmicas elegantes, como os conceitos de escovar bits, alocação de memória dinâmica, o custo de uma chamada recursiva, o uso de aritmética de ponteiros em estrutura de dados, entre outros.

Um fato bem importante para a história que estou tentando contar é que o processo de compilação de um programa escrito em C é complexo. Não sendo suficiente tal processo ser complexo, há muitos comportamentos que não são padronizados e podem tornar incompatíveis códigos-objeto gerados em compiladores diferentes. Ilustrando o caso, considere a opção -fpack-struct, que melhora o uso de memória, mas quebra a compatibilidade com códigos-objeto compilados sem essa opção (o que pode incluir bibliotecas do sistema). A Boost, por exemplo, lista uma página contendo uma conta simples para estimar que há 3200 variações de ABI (claro que Boost é escrita em C++, onde o problema é maior). Isso é só para exemplificar que variações de ABI existem, mas compiladores diferentes normalmente usam ABIs diferentes.

A falta de uma ABI “para a todos trazer e na escuridão aprisionar” é um problema quando você não controla as APIs que deseja utilizar e suas respectivas disponibilidades são limitadas. Citando APIs open source, tem a Qt, que no momento em que escrevo disponibiliza pacotes compilados com MingW, VS 2010, VS 2012 e VS 2013, enquanto a SDL disponibiliza somente para uma versão não claramente especificada do Visual C++ e do MingW. APIs open source são APIs que você controla, pois você sempre tem a opção de compilar sua própria versão.

Apesar de não haver uma ABI estável, no Linux, grande parte das distribuições adota a ABI padrão do GCC, que é bem estável, mesmo dentre diferentes versões do GCC. Ainda no ambiente Linux, compiladores competidores, como o Clang, também tentam aderir a ABI do GCC. Com isso, podemos usar qualquer biblioteca já instalada em nossos sistemas sem problemas causados por diferentes ABIs e também não ficamos dependentes de uma ou outra versão muito específica do Visual Studio.

Outro problema com o complexo processo de compilação de um programa escrito em C é a questão “onde encontro os arquivos de cabeçalho durante a fase de compilação e as bibliotecas na fase de linkedição?”. O Linux é um sistema que pode respeitar o padrão de sistemas de arquivos hierárquicos, que define um padrão sano para encontrar esses (e outros) arquivos-chave do sistema. O Windows próprio não fornece algo próximo ao padrão FHS, então a configuração para compilar algo fica por responsabilidade do compilador/versão-do-compilador/projeto/usuário, sempre tornando o processo mais complexo.

Todo esse complexo processo é bastante facilitado, não somente através do uso de software livre que você pode controlar, mas também, no Linux, através de gerenciadores de pacotes. Os gerenciadores de pacotes não só facilitam o gerenciamento de um sistema, como também automatizam a maior parte da preparação de um ambiente para programar em C (e muitas outras linguagens também). Há até as distribuições que não precisam de pacotes extras de desenvolvimento, tornando o processo ainda mais fácil. Se você tem o Qt ou algum programa que dependa do Qt instalado, significa que você tem o Qt instalado, em toda sua extensão, e já pode começar a programar software que faça uso do Qt. Usuários iniciantes no Linux costumam manter a mesma abordagem de instalação que usavam em seus sistemas anteriores, procurando o site do produto como o primeiro passo em um processo de instalação NNF. Alguém me salvou dessa filosofia com uma simples pergunta há bastante tempo atrás, “qual o sentido em possuir um gerenciador de pacotes se você não usa ele para gerenciar os pacotes?”.

E é isso! O nível de dificuldade imposto pelo ambiente mais usado no meu curso desencoraja o desenvolvimento, aprendizado e qualquer modificação em projetos escritos na linguagem C, apesar de ela ser uma das mais importantes e expor muitos conceitos importantes.

Existem outras tarefas mais dignas para perder tempo do que ficar aprendendo C, pois algoritmos são mais “puros” e aplicáveis a outras linguagens além de C. Otimizações em algoritmos são universais, mas um fato que os advogados dessa filosofia gostam de ignorar é que você não projeta algoritmos para rodar em máquinas abstratas e se não for possível executá-los em máquinas de verdade, eles perdem sua principal utilidade. Conhecimento de arquitetura de computadores é importante e se otimizações a nível de algoritmo fossem a única coisa a importar, talvez não houvessem tantas bibliotecas de álgebra linear tentando ser a mais rápida, assim como não haveria artigos como o “Why Computer Architecture Matters” ou palestras como “Native Code Performance and Memory: The Elephant in the CPU” ou ainda conceitos como “Cache-oblivious algorithm“.

Abertura do sistema

Outra característica que acho que me favoreceu durante meu aprendizado é a disponibilidade fácil de documentação e discussões de desenvolvimento abertas.

Quando há um padrão disponível, ele precisa estar bem documentado e sem nenhuma ambiguidade, mesmo que ao custo de tornar a leitura mais difícil. Pelo bem da interoperabilidade, padrões já existentes são adotados e a criação de novos padrões é evitada. No outro “lado da batalha”, incentivos são feitos para estratégias de lock-in e DRM. Isso é uma discussão bem maior, que não é do interesse desse texto. A característica interessante para os argumentos que estou construindo nesse texto é que você sempre pode descobrir “o que há por trás de alguma tecnologia” e, quando tiver sorte, vai até poder ler um documento bem detalhado, que é a prática encorajada no “nosso lado”.

Considerando os cenários onde uma boa documentação não está disponível, você ainda terá a possibilidade descobrir o que está acontecendo, pois o código-fonte é livre e você não vai acabar esbarrando em um LPVOID lpReserved. Pode ser até que você receba ajuda de pessoas mais experientes.

Um hábito da comunidade que apoio que me ajudou é o hábito de manter as discussões abertas. O ato de declarar derrota quando sua solução não é a melhor. As discussões que ajudam a entender como decisões de projeto afetam um produto, discussões de levantamento e análise de problemas e suas soluções, discussões sobre abordagens alternativas. São essas discussões que ajudaram a moldar a forma como encaro os meus próprios problemas. Alguns exemplos de tecnologias que geram discussões, para efeito de ilustração:

Ainda para efeito de ilustração, um assunto sobre o qual eu estava lendo recentemente é programação assíncrona e, graças ao fato de eu estar participando de várias listas de discussões, acabei encontrando esse texto sobre programação assíncrona e, especialmente, o gargalo que as interfaces podem criar no sistema operacional. Esse nível de detalhamento dos problemas não é algo que eu encontro em sistemas fechados, até porque manter seus detalhes disponíveis publicamente é um acontecimento que eles evitam.

Resultado

O resultado que observo é um monte de programadores incapazes de programar em C, reclamando de projetos que tenham muitas dependência (ou somente considerando bibliotecas header-only), incapazes de compilar outros projetos, optando por linguagens e ambientes inchados para ter certeza que todas suas necessidades são supridas, para citar alguns.

Outro resultado que observo é que você ganha o título de “usuário ninja do Linux” só por ler a documentação e conseguir fazer um programa mal feito funcionar e, para um curso de computação, essa é uma tarefa broxante.

E por essas e outras é que considero que estou “cheatando” por estar usando Linux. Não é que é impossível você conseguir tanto e até mais conhecimento fugindo da sua zona de conforto e usando um sistema operacional alternativo, mas é que eu acho que a jornada é muito facilitada a partir do momento que você adota o Linux.

Showtime: library to be proposed as Boost.Http!

It’s been two months already since my last post on this blog. All this time (and more), I’ve been (among other tasks) working on my 2014 GSoC project, an HTTP server proposal to Boost. I’ve finally reached a point where I feel it’s ready for major review/feedback.

If you’re a C++ programmer, a native speaker or an HTTP researcher (or just a little of everything) and you want to help, I’d like to ask you to review the project (interface-wise) and give me feedback.

You can find all the documentation and code at github.

Experience

This isn’t my first time on GSoC, but the experience was very different. The communities, development model, targeted audience, knowledge domain, to name a few, were completely different. Also, this year’s project wasn’t as challenging as the last one (although this is very subjective).

I improved as a programmer, but this is limiting. Once you become able to write algorithms for turing-machine compatible devices, there isn’t much room for improvement and you need to hunt other skills to continue improving (e.g. security, parallelism…). Coding for the sake of coding solves no problems. I decided to take a break (not exactly now, but in a few weeks) to make a shift and start to increase the efforts I dedicate to my academic skills.

Next step

I aim to integrate this library into Boost, so I still want to invest effort in this project.

Meu ambiente Emacs

Há alguns anos que o editor de texto Emacs me serve durante minha principal atividade, que é programar, e resolvi dedicar um post nesse blog para o Emacs e, em especial, meu uso com o Emacs.

Arquivos incovenientes

O Emacs tenta arduamente impedir que você perca qualquer modificação em qualquer de seus arquivos e um efeito colateral de tal funcionalidade é que vários arquivos de backup são criados por todos os lugares que você edita. Minha primeira modificação no Emacs foi evitar que tais arquivos fossem criados.

Visão “conservadora”

Antes do Emacs eu estava habituado a ferramentas com paradigmas muito diferentes (intuitivo, mouse, treinamento zero, customização no máximo de cores, …) e o Emacs me fez aceitar novos (na verdade velhos, considerando a idade do Emacs) paradigmas, tais como “se esforce o possível para manter sua posição de digitação padrão”, “tudo que você deleta é copiado”, “buffers no lugar de abas”, “janelas & frames”. Apesar de eu ter aceitado vários dos conceitos do Emacs com o objetivo de alcançar um maior nível de produtividade, há elementos que simplesmente iriam me confundir quando eu alternasse para uma janela não-Emacs e não eram exclusividades que iriam melhorar minha produtividade. Logo, eu me mantive “conservador” em relação a alguns elementos:

Suporte para manter estilo/consistência

Mudanças que acabei fazendo nesse sentido:

Outras ajudas para programadores

Mudanças:

Meus truques

Além de configurar o Emacs, existe a forma como eu o uso, minhas funcionalidades favoritas. Algumas dessas funcionalidades são ligeiramente mais obscuras (não são bem conhecidas) e achei que seria legal documentar elas.

Pacotes extras

A lista de pacotes extras que eu tenho instalados é:

Fim

Acho que esse é o primeiro post no qual fiz uso pesado da ferramenta asciinema, desde a fase de planejamento. E para quem quiser como referência, o meu arquivo de configuração do Emacs. Façam um post sobre a ferramenta de vocês e postem aí nos comentários, para que eu talvez migre para um workflow melhor, após uma nova epifania.

Por que eu migrei o projeto Tufão para o github?

Há um projeto de software livre que eu iniciei chamado Tufão. O objetivo do projeto era tornar a linguagem C++ amigável para desenvolvimento web. A diferença é que por muito tempo desenvolvimento web fazia o contrário de me atrair e isso só mudou depois que conheci o Node.js, que acabou influenciando na arquitetura do Tufão. Há muitos e muitos meses atrás, o Tufão era hospedado no Google Code, mas devido a alguns motivos eu acabei migrando para o github.

Motivos da mudança

Eu migrei o Tufão para o github pelo simples motivo de que a linguagem de marcação usada para customizar a página inicial do projeto no Google Code não suporta listas aninhadas muito bem.

  • Listas
    • Profundamente
      • Aninhadas

O motivo da migração pode parecer decepcionante, então eu vou dizer que outro motivo da migração é que eu finalmente pude deixar a documentação do projeto online, pois o Github gera um site online para você a partir do branch especial gh-pages e uma documentação online é algo que eu queria muito. A tentativa de converter a documentação gerada pelo Doxygen para a wiki do Google Code foi um resultado bem ruim. E na época que eu usava o Google Code acabava oferecendo a documentação gerada como uma opção download, uma tarefa bem inconveniente. E essa gambiarra nem funcionaria hoje em dia, pois “devido a mal uso da funcionalidade”, a Google desativou a funcionalidade.

Experiência pós-github

O primeiro impacto que o github trouxe para o projeto, é que antigamente você não tinha um jeito fácil de oferecer o download dos binários do projeto, então eu parei de oferecer binários para a plataforma Windows (que a partir de agora você tem que gerar por sua conta), assim como os usuários pararam de encher meu saco com essa tarefa que pode ter uma explosão combinatória, pois o ambiente de desenvolvimento pode variar muito entre sistemas diferentes.

O segundo impacto que o github trouxe, é que ele mapeia muito bem a natureza distribuída do git e tornou-se muito fácil contribuir para o projeto. Você pode conferir no próprio github que há pessoas modificando cópias próprias do projeto, assim como houveram outros contribuidores além de mim.

O terceiro impacto que o GitHub trouxe foi me deixar viciado em MarkDown. É o requisito #1 para caixas de textos de qualquer serviço na web. Eu uso gists secretos para manter minhas listas de tarefas, pois há suporte a MarkDown, eu escrevo minhas propostas usando MarkDown, eu faço slides para apresentações usando MarkDown, eu uso e abuso do MarkDown…

Uma característica que eu notei é que o bug tracker do Google Code aparentava ser mais completo, mas para um projeto do tamanho do Tufão, isso ainda não impactou negativamente o projeto. Só para citar como exemplo, eu podia anexar arquivos arbitrários a comentários que eu fizesse aos bugs registrados, no Google Code. No GitHub eu só aprendi a anexar imagens. Acho que até o bugtracker do serviço launchpad é mais completo e acho que o github não vai mudar, pois essa simplicidade torna o serviço dele mais “user-friendly”, que é a mesma desculpa para eles ignorarem as reclamações do Linus Torvalds.

Arquivos portáveis, protocolos portáveis… em C!

Um hábito que me faz desprezar imediatamente TODAS as habilidades que um programador afirme ter, é ele fazer um formato de arquivo ou protocolo binário que não é portável, então resolvi fazer esse artigo para ajudar a diminuir essa prática, expondo os seus perigos.

Mas antes, lembro que na época que eu usava Flash Player, eu era um usuário burro e aceitava cegamente a desculpa das versões de diferentes sistemas operacionais serem dessincronizadas (sistema operacional X recebe versão nova antes de Y e Z, em vez de lançamento simultâneo). Isso é um ato que eu até consigo entender tendo em mente os objetivos da empresa, mas outro lugar onde a dessincronização de versões ocorria era em arquiteturas diferentes (32bit e 64bit). E o único fator para justificar isso é pura incompetência dos programadores, que ganharam para sempre o meu desprezo. Dito isso, não acompanho ou uso mais o Flash Player e não sei se esse problema já foi corrigido.

Para não comentarem que sou extremista e só exponho os erros técnicos de softwares proprietários, aqui e aqui você vai encontrar um erro que pode ocasionar o mesmo problema, no futuro, mas é completamente ignorado, no projeto Enlightenment, que é software livre. Aliás, eu nem posso afirmar que expus erros técnicos do software Flash Player, pois é assim que funciona com software proprietário, você simplesmente não sabe.

Citando, para motivos de reflexão, antes do começar a parte séria do texto, a frase de alguns padrões da IETF, em tradução livre: “seja liberal no que você aceita, mas conservador no que você produz”.

Fluxos de bytes binários

O computador trabalha usando binários, mas esse fato é abstraído na linguagem de programação e esquecemos isso enquanto estamos focando no problema que queremos resolver de verdade, em vez de ficarmos nos preocupando com o opcode da instrução da arquitetura do processador que é necessária para implementar várias camadas de algoritmos até chegar no problema que realmente queremos resolver. Entretanto, quando é hora de fazer o programa se comunicar com o mundo externo, através de arquivos ou sockets, é hora de nos preocuparmos com a representação interna das estruturas do programa, pois nesse momento elas importam.

<stdint.h> e <inttypes.h>

Começando pelo mais simples, C não exige/garante que os tipos short, int, long, long long tenham a mesma quantidade de bits para todas implementações, ou mesmo que o tipo char tenha sinal. Isso significa que se você fizer um programa que leia um long de um arquivo ou da rede, você está errado. Quando você compilar o seu programa em uma implementação que usa um long de 32 bits, ele não se comunicará adequadamente com o mesmo programa compilado em uma implementação que usa um long de 64 bits, pois a estrutura de fluxo de bytes que ele gera não é definida e varia de implementação para implementação.

A solução para esse problema é você usar tipos para os quais existe a garantia de tamanho específico, independente de implementação. Se um compilador não cumprir com esse requisito, ele não é um compilador da linguagem C, pois ele não cumpre com a especificação da linguagem. Esses inteiros estão disponíveis nos cabeçalhos <stdint.h> e <inttypes.h>. O cabeçalho <stdint.h> possui todos os nomes necessário para declarar inteiros de tamanho fixo, enquanto o <inttypes.h>, além dos nomes introduzidos pelo <stdint.h>, introduz nomes para ajudar a trabalhar com printf, scanf e conversões entre strings e inteiros de tamanho fixo.

Mais uma coisa a aprender é que o padrão mais comum para representar números negativos usando binários é o complemento de 2, mas a especificação da linguagem não exige/garante o padrão por trás do mesmo e, inclusive, define integer overflow como undefined behaviour. Mas nada tema, pois o padrão exige que os inteiros com sinal declarados no cabeçalho <stdint.h> sejam armazenados usando complemento de dois. Então se você está seguindo as soluções até aqui, você já se livrou do problema.

Uma última nota que tenho a adicionar é: só use inteiros de tamanho fixo quando eles forem necessários.

Ordem dos bytes

Outro problema que atinge a portabilidade do fluxo de bytes é que não há garantias em relação a ordem dos bytes que compõem um mesmo inteiro. Isto é, em 16 bits, é legal representar 16 bits como 0000’0001’0000’0000 ou 0000’0000’0000’0001. As duas ordenações que costumamos encontrar são Little Endian e Big Endian (também conhecido com Network Byte Order).

Não há solução embutida na especificação da linguagem C para esse problema, então você vai ter que implementar suas funções ou usar alguma biblioteca externa como essa ou essa.

EBML/Matroska

Um formato que eu quero citar brevemente, pois possui uma característica que eu acho bem legal, é o EBML. O EBML é binário e possui uma representação eficiente, sendo usado, por exemplo, no formato de arquivo Matroska. Mas o EBML é também extensível, o que me dá confiança para acreditar que não seria surpresa continuarmos a utilizar esse formato por, sei lá, mais 20 anos.

Imagine que lhe seja dada a tarefa de criar uma representação binária para datas. Você decide especificar a quantidade de bits necessários para dias (que variam entre 1 e 31) e meses, mas chega então no problema de especificar a representação para armazenar o ano. Você sente a vontade de especificar um tamanho fixo grande o suficiente para que o problema não seja exposto enquanto você estiver vivo, mas algo dentro de você grita para que você lute e acabe com o problema. Esse algo dentro de você, gritando para que você resolva o problema, se chama competência. Você decide usar caracteres ASCII no topo do formato binário, para usar texto e ter uma quantidade infinita de caracteres, que pode ser usada para representar qualquer data, mas surge a questão de como definir o tamanho para armazenar essa cadeia de caracteres. Se você especificar um inteiro de 32 bits ou qualquer outro tamanho no começo da sequência, a representação continuará limitada.

A linguagem C define cadeias de caracteres de tamanho arbitrários (na verdade, ainda limitados pelo intervalo enumerável dos ponteiros) através de um delimitador no final da sequência. A mesma solução de usar um delimitador pode ser trazida ao universo dos inteiros binários e, de fato, é usada no formato EBML. Vale ressaltar que o EBML não sofre o gargalo e ineficiência de usar caracteres ASCII convertidos lexicalmente (no sentido do lexical_cast existente na Boost) para inteiros em sua representação.

Baseado em texto puro (legível por humanos)

Não, seus problemas não acabam com você indo para texto puro! Mas nada tema, pois você usa uma linguagem que requer a presença de acentos, está usando um locale diferente do padrão e já possui vantagem sobre outros programadores, detectando mais cedo qualquer quebra de internacionalização!

Se o fluxo de bytes que você está definindo é baseado em texto puro, você deve responder algumas perguntas como “o conjunto de caracteres ASCII é suficiente?”, “como adicionar estrutura de uma forma extensível?” e “dados binários serão suficientes?”.

O primeiro problema a resolver é que, caso abra um arquivo em modo de texto, em C, o final de linha será interceptado e convertido, a depender do sistema operacional (“\n” no sistema pai, o Unix, “\r\n” no Windows e “\r” no sistema da empresa que gosta de quebrar padrões para eventualmente causar dependência). Então, ou você escolhe e usa apenas uma dessas opções (como acontece com o HTTP), ou se prepara para tratar todas elas (como acontece com o gcc e editores de texto decentes). Mas um comportamento deve ser definido (assim como suas consequências refletidas) e a implementação deve cumprir com tal.

Se eventualmente for necessário adicionar suporte a dados binários, pesquise pelos padrões base64 e base91 e faça preparativos para que não haja conflitos de caracteres especiais sendo utilizados em áreas diferentes das planejadas.

Se o conjunto de caracteres ASCII não for suficiente, use Unicode. Vou apenas lhe informar para começar por aqui.

Problemas em XML e arquivos estruturados em geral

O XML é um formato de arquivo que carrega a palavra extensibilidade em seu nome (eXtensible Markup Language) e ele é bastante usado em alguns locais onde manter interoperabilidade é um requisito importante. Os problemas que podem aparecer aqui não são de baixo nível, específicos de arquitetura de computadores ou da linguagem C, mas já que comecei a comentar sobre interoperabilidade, decidi estender o texto e fugir do escopo inicial só um pouco.

Um problema que costuma afetar o XML e formatos estruturados como um todo, é que algumas implementações, não-conformantes, costumam usar a estratégia ingênua de mapear o arquivo para suas próprias estruturas e trabalhar daí, em vez de manipular o arquivo original. Acontece que normalmente essa estratégia ingênua irá descartar todos os atributos, tags, elementos e por aí vai do arquivo original, que não forem reconhecidas pela implementação. Isso aconteceu com algumas implementações do ODF e houve até a teoria conspiratória que a infratora tentava minar o padrão.

Mesmo que você argumente em optar pela abordagem ingênua, por sua implementação suportar todos os nomes definidos na especificação, você deve ter em mente que formatos evoluem e extensões são adicionadas no topo do formato original (isso acontece com o OpenGL, com o XML SVG do Inkscape e em tantos outros por aí).

Uma abordagem mais legal do que criar abstrações que retornam o elemento processado (que só contém as propriedades que a implementação conhece), é criar abstrações que realizem operações em cima da representação original, como acontece com a API do MongoDB, onde você só especifica os atributos que devem ser modificados, mas os atributos não-especificados continuam a existir.

Caso você não seja um guerreiro incorruptível e se desvie do caminho correto, pelo menos tenha a decência de explicitamente proibir, na especificação do padrão, o uso de propriedades adicionais. Tal exigência pode ser especificada como “additionalProperties: false” em JSON Schema.

Final

No final do texto eu fiquei com preguiça e passei a só explicar quais deveriam ser suas preocupações, adicionando referências para você pesquisar mais. Foi diferente do começo do texto, onde eu estava com paciência até para explicar os problemas com detalhes.

Se eu esqueci de alguma coisa ou você tem alguma informação relevante a acrescentar, comente!

GSoC 2014/Boost

I was accepted for GSoC 2014 and I’ll be working on the Boost project.

I created a new category on this blog to track the progress, so you’ll be able to have a separate rss feed for these posts. The new category URL is http://vinipsmaker.wordpress.com/category/computacao/gsoc2014-boost/.

Another libdepixelize update

Evil patterns

I’ve invested some effort to improve libdepixelize response to evil patterns. Because libdepixelize won’t discard color information, the connections of the similarity graph aren’t a transitivity relation and extra topological patterns can happen. I refer to the extra patterns as evil patterns. The name comes from the fact that I enjoy to play Zelda and defeat the evil from the Hyrule land. Same happened in the last libdepixelize’s commits, where I overcame some patterns to improve the output quality. Quality can be something subjective sometimes, then I was a little conservative and limited my changes to things that I could reason about. The effort end up in new samples to the libdepixelize documentation, new rules for the algorithm and its related documentation and lines of code in libdepixelize itself.

The new rules are added as an extra step on the process. They are not treated like the Kopf-Lischinski’s heuristics to resolve crossing connections. I think maybe would be possible to get some of the new rules and describe versions that are more general and can be added to the “container” that holds the old heuristics. To make this happen, I’d need to define the concept of “similar color” as a set and operations on top of the set, the notion of interval and other things and logical reasoning on top of all that. A bit of mathematical work to improve the quality a little more, but I wanna to investigate the use of La*b* colors (an old suggestion by Nathan) to replace the current concept of “similar colors”. I didn’t replaced the current space color until now, because YUV and La*b* behave differently and I couldn’t just convert the YUV constants that define the boundary between dissimilar colors to La*b* to achieve better results. The current YUV constants were taken from HQx filter and I need to define a methodology to find new constants.

The advantage of a rule that is more general and unifies behaviour is just the beauty of a simpler rule that handles the real problem, as opposed to several branches that are consequence of the real problem. It’d abstract the nature of the problem better. It’d make the code simpler. It’d handle more branches. Being a single rule that affect more branches, it’d be easier to test and better at convincing me that the improvement is real and there will be no loss of quality in other images.

It’d be interesting to investigate the range of voting in all heuristics and try to come up with “fair” multipliers/strength.

New idea to represent splines

Previously I used a technique to carefully insert new nodes to obey the technique “adjust splines” from the Kopf-Lischinski paper while being limited by the old splines representation. This technique has caused troubles to several later steps.

The first problem was to remove the extra invisible nodes that are present in the output SVG. These extra node not only make the output larger and make rendering consume more CPU time, but also can be troublesome for artists wanting to manurally edit the generated image. I’ve made several unsuccessful attempts to remove these nodes and I’m sure it’s possible, but I’ll try to move away from this problem trying a completely different approach to the problem.

The second problem is similar, in essence, to the first one, described in the paragraph above. When I originally disabled the optimization step in the Inkscape GUI and marked it as experimental, one of the reasons was because it required “extra preprocessing steps” (it was a pretty vague explanation, but I should try to improve my communication skills). With no extra invisible points, the optimization step will be way simpler. The step related to optimization that avoid overlapping shapes and holes will partly go away and the approach I mentioned previously (“A new idea to keep the shape of optimized splines correct“) will be affected.

The idea is to split splines. I was previously using a list of points. The new idea is to use a list of splines, where spline itself is a list of points. I hope that the new representation will allow a representation closer to “arbitrary”, just enough to apply the operation “adjust splines”. The new representation should do without extra points and easy the last processing steps (in terms of processing power and my productivity). Of course this change requires a lot of refactoring and will take a bit of time to be finished. Also, the “hope” word used previously means that I haven’t thought about all implications and I’m sharing this idea very early. I’m trying to improve my communication skills and this means that you’ll see some “flood” on this blog. The “flood” might include ideas that eventually prove to be bad at a later point and doesn’t hit the libdepixelize code.

Beta testers

After I shared some images on Google+ related to libdepixelize improvements, some people demonstrated interest in helping me with beta testing.

First, the software is free software, then anyone can use it (even the development versions). So, if you find a crash or something that obviously is a bug, fill a bug report and I’ll fix it.

Second, I still want to improve the quality of the algorithm, then a good pixel art database can help me a lot. Currently the algorithm behaves bad at images with too many gradients, but this doesn’t mean that a lot of images with gradients will help me to improve the quality of the algorithm. I need to publish a page explaining what kind of image can help me to improve the quality of the algorithm.

Third, you can help me with profiling info to improve the performance of the algorithm. I’ll probably send a message to the Inkscape mailing list with the title “request for beta testers/profiling data on libdepixelize”. I’ll probably (re-)share the message through Google+, this blog and maybe more. If you follow any of  these communication channels, you’ll know when I need help.

Thanks for the support.

New logo

The project doesn’t have a logo and uses an ugly icon in the Inkscape GUI dialog. I was thinking about use the character introduced by Jabier on the Inkscape mailing list to represent libdepixelize project:

boof

This image already is highlighted on the algorithmic documentation report anyway and is unique enough.

Timesharing

I’ll have a test at the end of the week and later I’ll share more of my time to play with POWER and LLVM. Then libdepixelize will have to wait a little until I can do more commits.

Target

I’m aiming to deliver all the improvements related to the original Kopf-Lischinski algorithm before Inkscape 0.91. Later I’ll try to improve performance. “Beyond Kopf-Lischinski” extensions have no timeline and depend on creativity.

%d blogueiros gostam disto: