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.

  • “C-t” para transpor caracteres e “M-t” para transpor palavras. Útil quando você tem um “ataque de dislexia”.
  • “Registradores” para rapidamente pular entre pontos específicos em buffers abertos. “C-x r <SPC> [letter]” para salvar um registrador e “C-x r j [letter]” para pular para um registrador. Útil quando você quer, por exemplo, comparar o uso e uma implementação de uma função, mas não quer baguncar a organização de janelas que você criou.
  • Capitalizar (ou o inverso) a palavra seguinte. “M-u” para maiúsculas e “M-l” para minúsculas (só lembrar de Upper e Lower).
  • Trabalhar (substituição/adição e remoção) com retângulos. Retângulos são definidos por dois pontos da sua seleção (começo e final). “C-x r t” substitui retângulo pela nova string e “C-x r k” apaga. É uma “versão generalizada” do ato de identar e mais útil do que aparenta.
  • “M-q” para restruturar o texto de forma que o limite de caracteres por coluna seja respeitado (80 no meu caso).
  • Dired FTW! Emacs não usa abas convencionais, mas uma lista de buffers abertos. Além da inconveniência de várias extensões poluírem sua lista de buffers com mais buffers, a sua ordem não é estável, tornando algo muito chato rapidamente alternar entre arquivos. Para fugir dessa loucura, eu acabo usando uma janela do lado esquerdo com o Dired aberto e uma janela com o conteúdo do lado direito.
    • Ao pressionar “o” em um item no Dired, o arquivo é aberto na outra janela, deixando seu “workflow” como planejado, inalterado, com uma janela de acesso rápido e uma janela de conteúdo. Para tornar seu workflow ainda mais rápido, pode ser que você queria usar o mouse aqui, pois o clique do seu botão do meio tem o mesmo resultado.
    • Ao pressionar “i”, o diretório representado pelo item atual é “aberto in situ“, tendo como resultado final que os dois diretórios (anterior e novo) são mostrados no mesmo buffer.
    • Ao pressionar “$”, o item atual é escondido.

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/.

Yet another libdepixelize update

Looks like I’m super creative lately. I’ve had another idea to improve libdepixelize.

The idea is to use the knowledge I got from the compilers course on the Coursera MOOC platform to make libdepixelize implement an abstract machine that can be programmed through image metadata gathered from PNG files to execute arbitrary code to turn libdepixelize into a generic cg framework.

Such extension will allow libdepixelize transform images like the followin one …

Mario pixel art (magnified 16x)

… into the following other one:

In fact, I’m so excited about this idea that I’ll start to work right now and I’ll try to deliver this feature at the end of this very week and you can wait for some extensions in the next week.

In the list of planned extensions, there is support for examining your computer usage, then we can gather general info about our citizens and help the police chase criminals. But don’t worry, we’ll only use this info for the good.

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.

libdepixelize update

Lots of months without updates, I thought it was about time to post something.

Interestingly, this is the post that document the slowest progress, but it was the post that consumed more from my time.

The frogatto game database

frogatto-icon

I found an awesome pixel art database distributed with the Frogatto game and from now on I’ll use it on my research and tests. The license is kind of confuse (you don’t know precisely all the things you can do) and I’d prefer a Creative Commons license, but it’s safer (for me) than use copyrighted graphics from Nintendo or other companies. Not only the license is better, but also the beauty of these graphics is outstanding.

Most of the images don’t have an Alpha channel and use a placeholder color as the removable background, but there are some images where real use of Alpha channel (not only on-off) is there.

I want also to add that I liked the Frogatto game so much that I was thinking about the possibility to join forces with their developers to provide a hi-rez version of the game using the Kopf-Lischinski algorithm. Maybe I can borrow some processing power from some cluster at my university to generate the SVG files.

The Alpha channel heuristic

If you’re unfamiliar with Kopf-Lischinski heuristics, I suggest you to read the “trace pixelart” manual bundled with the very (bzr) latest version of Inkscape.

The frogatto game pixel art database made me realize one simple fact: The alpha channel heuristic to resolve similarity graph ambiguities that I was planning to develop is pointless for most of the cases, because the extra color patch will work against the heuristic. The extra color patch will see different colors and will create square-like pixels. The below image from the Frogatto database (with a red background inserted) sumarize this problem:

glow

Do you know how a good a conversion from current libdepixelize would be? Well, it would generate a similar image as output, but a an alpha channel heuristic wouldn’t help. Also, there aren’t really any cross-connections to resolve here (because the alpha channel + extra color patch turn each one of the white pixels into different colors/shapes). Even if there was an ambiguity in the similarity graph, I don’t see how an alpha channel heuristic would help (mainly because the lack of problem hurts my imagination).

There is, although, one case where I see an improvement/extra-safety-guarantee that could be achieved through an alpha channel heuristic. Look at the magnified image below:

chain

The image is ugly and the reason is because I created it. It’s so ugly that maybe you don’t understand what drawing I tried to achive here, then I need to explain. The drawing is a part of a chain. There were chain images on the Frogatto database, but they weren’t affected by the issue I wanted to mention.

The image squares are pixels and the image was magnified 12x. The Alpha channel information is still there. The other heuristhics (long curve and sparse pixels) will likely vote to keep the chain shape, then the result is already good and there is no need for an Alpha channel heuristic. Also, it’s possible (but very unlikely) that the transparent color has random bits that will create no connections and won’t affect the chain shape.

Well, pretty much an Alpha channel heuristic is useless, but kind of nice to have as an extra safety over the other heuristics. But I won’t create this extra safety guarantee, because the above image is artificial (you won’t find it in any game) and I haven’t find a good Alpha channel database affected by this issue yet. If I do find such database, I can reconsider this issue, because even if the heuristic go wrong for some images, the libdepixelize design allow you to disable or invert any heuristic (neat feature).

Just to be clear for once… I won’t waste my time looking for a pixel art database making good use of alpha channels affected by this issue. I don’t even bother anymore. But… if you do find such database, just share it with me and I’ll see what I can do. In fact, this is one of the changes in libdepixelize where I don’t need to invest much effort or thought (apart from the pixel art database research).

A new idea to keep the shape of optimized splines correct

One of the things that I’m really failing to achieve is to keep the shape of optimized splines correct. I had a new idea that I want to test soon and I’ll describe in the text below.

So, the idea is to create an index of all points that share the same position before the optimization begins. Every time a point is optimized, the position for all points sharing that position change. The problem is, among others, to keep invisible lines invisible.

The approach is simple, but it’s a bunch of code to do. Stay tuned.

A new competitive filter

The post is getting kind of big, then I’ll leave analysis of one possibly interesting algorithm for later.

Correctness (C++ memory-wise) tests

This was a task originally suggested by Nathan. I think he meant to use Valgrind, but I went on a different direction and I went on LLVM suite (clang sanitizers) instead.

First test is simple and it didn’t show much. This was done using clang static analyzer tool and theoretically can be as good as the compiler warnings. The output was “No bugs found.”.

Second test was the combo address sanitizer+leak detector, also using LLVM tools. I fixed some bugs regarding the use of the popt command line arguments parsing library and suppressed another warning (source outside of libdepixelize cannot be fixed within libdepixelize). Looks like the use of RAII helped to keep libdepixelize free of memory leaks and the use of standard containers instead self-made structures helped to keep libdepixelize free of wrong-address errors (although I do some weird pointer arithmetic at some places to try to improve the performance, but the analyzer hasn’t spotted errors).

Third test was the memory sanitizer, that would help to spot the use of non-initialized variables, but this sanitizer aborts on the first error and due to an error within popt I couldn’t go farther. I tried to use the suggested attributes and also the blacklist file, but it didn’t help. In short, I’d need to rewrite the binary without popt to inspect libdepixelize code through the memory sanitizer, then I’m postponing this task. At least the next planned big refactor is more sensible to addresses, which has a sanitizer working fine.

I tested all output modes (voronoi, grouped voronoi, non-smooth and default). The set of images used was chosen to increase the test of code paths executed, including the images that are used as examples in the original paper to describe the heuristics and smoothing techniques and some big images taken from real-world games just to stress the code. Something better would be some unit tests. This set of image was used for all tests described in this post.

Performance tests

This was also a task originally suggested by Nathan. The task was not to find the slowest element in the processing pipeline, because maybe the element is the slowest, because indeed the task is tough and it may be doing the best possible. The task was to find which processing element wasn’t scaling linearly with the size of the input and improve it.

I haven’t measured memory consumption like old Rasterman told us, but memory consumption isn’t my focus with libdepixelize. I use a templated argument to customize the precision and you can “freely” (actually it’s limited by 2geom) use any type (float, double, long double, …) you think fits your application the best. I try to avoid cache misuse and too many allocations and memory usage is just a consequence of this design principle. Thus, don’t expect any changes focused on memory consumption. Memory usage may receive some love, but just as a mean to achieve better performance. Also, this isn’t the kind of application you hope to keep around and you just want to see it finishing fast. A last thought is that structuring packing could decrease memory usage without affecting the algorithm, which can improve the use of the cache and the performance.

You can find the result below (libdepixelize profiling output + zsh + python tricks) and the method at the end of this section. The image was generated using R.

A plot from the measurements taken

Plot

And below, you have a plot of the same data using a logarithmic scale to move away the curves from 0.

A second plot from the measurements taken

Plot with logarithmic scale

I’m sorry for being that n00b, incapable of producing a legend that don’t cover parts of the curves.

Now it’s clear what processing units I need to investigate to improve the performance.

Improving cache usage

One of the ideas to improve the performance was to use a cache oblivious algorithm. This means that I should use a different memory layout to make better use of cache. I wanna know what kind of improvement I should expect and I did a small test converting a large image to a single row and did some measurements (you can find a code snippet below as a proof), but the libdepixelize’s code take different paths and the comparassion is very unfair (to not say useless).

I will do a second approach mentioned in this blog post to measure cache misuse. I’ll have to implement the new memory layout and compare the results to be sure about the improvement. Before comparing the results, I’ll have to rerun the old tests, because my computer will be using newer libraries and newer compilers and the comparassion wouldn’t be fair.

Method

Let’s define a run as the execution of the script below (given that libdepixelize was configured with the option OUTPUT_PROFILE_INFO enabled).

I did 3 runs and aggregated all common values per image (even equal steps in different output modes, like “Tracer::Kopf2011::_disconnect_neighbors_with_dissimilar_colors(Tracer::PixelGraph)”, with exception of “Tracer::Splines construction”, which would be unfair). I discarded the largest (the slowest) value for each field per image, because I was considering it as cold cache effect and it’s more difficult to measure/replicate this condition (I’d need to learn how to clear the cache without rebooting the PC), then I’m more interested in hot cache condition. Then, I computed the arithmetic mean. Now I have a table of values to print for a set of images. I’d like to compare the time taken by some processing element (this is how to interpret each value) as the “difficult” increases. The difficult was related to each image and to rank them I just sorted them by number of pixels.

And in case you want aggregate data like I did, I’m sorry, but I cannot help you. I used at least 3 technologies to do interactive exploration (ZSH + BASH + Python) and I cannot provide scripts that don’t exist to you. And about the other tools used, they were used just because I know how to use them (accidental vs planned) and the communication among them was rather unusual (clipboard text + simple files + json formatted files + MongoDB + CSV). The description of the method given above is just better than the tools by themself. Accept my apologies in the form of an AA cow:

I ran all the tests on this machine and I kept myself from using this machine while the tests were being executed. Yes, not a very “scientific” approach, but I think it’s on the right track and I need to reserve some time to development. The purpose is just to identify the “worst” processing element anyway.

%d blogueiros gostam disto: