Installing Debian Testing on VirtualPC 2007

image4_thumb-5B4-5D

If you tried installing Debian testing or any other recent flavor of Linux on Microsoft’s VirtualPC 2007 you probably hit the wall with the “An unrecoverable processor error has been encountered. The virtual machine will reset now.” error during the machine’s first boot after installation.

The solution?

Add noreplace-paravirt to the boot options in grub’s kernel entry.

You may also want to add clocksource=pit as well to solve timing issues and vga=791 for a 1024×768 resolution text mode.

 

Booting in a usable terminal

To boot in a usable terminal, select the safe (single-user) mode (just select, do not press enter).

image

Press ‘e’ to edit the command, select the middle line as shown in the picture below then press ‘e’ again. Add the noreplace-paravirt parameter to the end of the line and press enter to go back to the previous screen. Press ‘b’ to boot using the selected kernel entry.

image

 

Once you get into a usable terminal, we need to make those changes permanent. We will have to edit /boot/grub/menu.lst and add noreplace-paravirt in the “default kernel options” and the rest in the “additional options” as shown on the two pictures below.

imageimage

 

Starting X

Well, if you continue booting and end up in X you will certainly get nothing but a garbled screen. This happens because VirtualPC doesn’t support the default 24 bit color depth of X and we will have to edit xorg.conf and tell it to use only 16 (or 32?) bit colors.

Just open /etc/X11/xorg.conf then look for the “Screen” section. Add the line DefaultDepth 16 as in the picture below, save and reboot (or just restart x).

image

 

Conclusion

Ta-daa.

image image

 

I was hoping to see KDE4 here, but it looks like debian development is just too slow. I mean, it actually was debian unstable. Ubuntu has had KDE4 out-of-the-box for months now, and it is pretty stable. Wtf.

 

Edit: Debian 5.0 has just been released. Hopefully KDE4 will move from experimental to unstable soon.

Photoshop CS3: White isn’t actually white

ps-20color-20b-5B5-5D

Perhaps this is one of the oddest issues I’ve ever seen. I just installed Photoshop CS3, opened some pictures to edit and, oddly enough, they were all kind of “warmed up”. I mean, they were more orange or beige than they should. In fact, choosing RGB 255,255,255 (which is pure white) was being displayed as beige!

Photoshop showing beige as white

I know this may be a useful feature for real artists, but I think I’ll pass on that. I think some error occurred when Photoshop was detecting the monitor profile and ended up like this.

 

Well, if you are experiencing this same behavior as me, open Photoshop, click Edit > Color Settings then select “Monitor Color” in the drop-down box. Press Ok.

Photoshop Color Settings

I guess it will be fixed by now.

Essential Software for Windows

Opera-5B1-5D

Here is a list of useful software I usually install whenever I do a fresh Windows (XP) install. Most of them are free or have free versions available, while others do not.

For a list of essential software for linux, click here.

 

 

System Tools

  • ClamWin – The free, open source ClamAV antivirus port for clamwinWindows. It doesn’t have a real time scanner, but who needs one, anyways? Very lightweight and doesn’t get in your way at all.
  • Spybot – Search & Destroy – Third party option for protection agains malware/adware. But I usually leave the TeaTimer (realtime scanner) option disabled.
  • Microsoft Bootvis – Formerly offered on Microsoft’s Website, BootVis is a “is a performance tracing and visualization tool” for helping “identify performance issues for boot/resume timing“. Some says it cannot speed up startup time, but it definitely does for me. All you have to do is install it then click on the “Optimize” button and wait while it does its magic.
  • Macrium Reflect Free – The best backup solution I’ve ever seem. Its worth paying for the full version, but the free one does just as well – it creates images of your entire disk or entire partitions in less than 5 minutes, copying either only the used sectors or making a bitwise copy of your drive, has backup verification, can create Linux or Windows based rescue CDs, backups even your MBR and backups directly from Windows, without needing to reboot using a bootable CD.

    The only regret I have is missing its full version for free when it was available through GiveAwayOfTheDay back in June.

  • WinDirStat – Creates a map of your harddrive so you can see exacly how your disk space is being used. Very useful to discover why your 250GB HD has only 1.7GB free.

 

File Tools

  • 7-Zip – Archiver (file compressor) with one of the best compression rates out there. Can employ ultra compression at the cost of extra amounts of memory and processor time, but its normal compression is just fine. Plus it is open-source and free, unlike WinRAR.

 

Browsers

  • OperaOpera – The Fastest Browser on Earth! Has integrated email, chat, BitTorrent support and is incredibly fast! Has other cool features like mouse gestures, popup blocking and password manager already built in. Definitively my browser of choice, be it in Windows, Linux, mobile phones, game consoles, televisions or fridges.

 

  • Google Chrome – Because its always good to keep asimonn alternative browser to your alternative browser lying around.

 

 

Security

  • PuTTY – The best free Secure SHell (SSH) client for Windows.
  • TrueCrypt – Opensource software for transparent, on-the-fly, realtime encryption. Can hide entire drives and even boot partitions making them completely invisible if you don’t know how to reach them.
    • Update: TrueCrypt  was discontinued back in 2014 and has subsequently not been maintained. A number of security flaws have been uncovered and as a result we are reaching out to people to highlight a list of alternatives. Please see this page for more details and for a list of alternatives for TrueCrypt.

 

Multimedia

  • Winamp – Winamp has been my player of choice since 1997 on Windows. The AVS plugin is just fantastic, and together with DFX for Winamp and NowPlaying (for Live Messenger) it is a complete, feature rich and the sexiest player ever to sit docked on the top of my screen.

WinampBetter yet is enabling the AVS video overlay (so you can see it on your TV) and set it to change your desktop to the overlay color. Its an amazing effect. But of course, if you own a Geforce card, only if it is a model prior to the 8000 series, if your Windows is prior to Vista and your video driver is old, because NVIDIA, in its infinite wisdom, has completely disabled video overlay on TV for its newer cards and drivers, AFAIK.

  • Media Player Classic – I like Windows Media Player, but whenever it gets in my way its always good to have this alternative around. Plus it just works with my WinLIRC remote out-of-the-box.
  • ffdshow – The One decoder to rule them all. FFdshow decodes nearly everything, video and audio, from mp3 to AAC, mpeg to XVid. Has support for subtitles, postprocessing filters and more. You don’t have to install bloated codec packs which will just mess your system anymore.
  • Real Alternative – The DirectShow filter for watching Real Media videos without Real Player. Just like with QuickTime Alternative, you can view your videos on your player of choice, be it Windows Media Player or Media Player Classic. You just have to register the extensions with your choosen player the first time you open your media.
  • CDBurnerXP – After many years using Nero, and considering the bloatware is has become, I’ve ditched it in favour of this simpler, cheaper, free as in beer alternative and have not looked back ever since.

 

Development

  • Microsoft Virtual PC – A must have if you like to test neat, cutting edge or just unknown dangerous stuff without risking compromise your main system, or if you need to make tedious testing with different operating systems all in one computer. In my opinion, better than VMWare.
  • .NET Reflector – Apparently, the free software from Lutz Roeder which enables us to peek into CLR assemblies and browse its source code was sold to Red Gate. I can only hope this excellent tool continues as a freeware for us developers.
  • CADSoft Eagle – The Easily Applicable Graphical Layout Editor, or EAGLE for short, is a very complete circuit designer and layout editor, a must have for the electronics hobbyist. The freeware version is enough for most people, but the full version is very worth paying too.
  • Proton DE – The Proton Development Suite for PICBASIC programming (BASIC for Microchip’s PICmicros®).

 

Internet Utils

 

Others

  • Adobe Reader – The Standard Portable Document Format Reader. For some time I ditched Adobe Reader in favour of Foxit as it was becoming completely unusable due to the giant memory footprint and “resource hungryness” of its previous versions. But since it’s last version, it has improved a lot, so I’m giving it another try.
  • components-colorWinLIRC – Control your PC using your any infrared remove control. I’d post about how to craft your receiver but there are many good tutorials available on the internet. I may post about mine later in the future.

    The funny thing is, albeit this was originally a Linux program, I’ve never got it to work under Linux, even if it works great on Windows.

Microsoft Starts Inviting to WDK Beta for Windows 7

WindowsLogo_256x256_thumb-5B4-5D

WindowsLogo_256x256 I’ve just received an email from Microsoft inviting for the new WDK Beta for Windows 7. The Windows Driver Kit, which includes the kernel-mode driver framework (KMDF) and user-mode driver framework (UMDF), along with the Windows Logo Kit, are the step one for building software which interacts deeply with the OS or with hardware devices, such as device drivers or filesystems.

 

Dear WDK/WLK User:

I would like to invite you to join the WDK Beta program for Windows 7. The PC Ecosystem Connect site will provide you with Windows 7 beta downloads of:

  • The WDK
  • Free and Checked Builds of the OS
  • Symbols
  • The WLK
  • The Windows SDK

The feedback link at the site will create a report that goes directly into the Windows 7 bug database – you will get email as your issue is resolved, so you can track it.

Please join the beta, download the WDK, and make sure all of your drivers build correctly using the new WDK. Also, check out OACR – it runs Prefast for Drivers by default whenever you build a driver.

 

Thank you for your help.
WDK Team

 

Ensuring a smooth transition to Windows 7 is great deal for Microsoft, as compatibility problems with both existing and newer hardware was Vista‘s major issue when it first hit the stores, causing permanent damage to its popularity even if most of those issues are already gone.

Hopefully Microsoft has learned the first impression the public gets about the OS will be the real matter; Vista was certainly ahead of its time but it was needed to make room (and need) for a new, polished and fresh product, which I hope is going to be Seven. I hope Microsoft gets everything right this time.

Árvore B em Arquivo (em C++)

Novamente, outro post ecológico! Após a apresentação da Árvore AVL, porque não agora Árvores B?

Árvore de maior largura do mundo

Árvores B são estrutura de dados bastante utilizadas em sistemas de arquivos e bancos de dados. São geralmente mais densas em informação por nível em comparação com Árvores AVL, o que significa que possuem geralmente uma altura menor mesmo armazenando um mesmo número de elementos.

Em primeiro lugar, devo especificar que este artigo não se destina a explicar o funcionamento das Árvores B em detalhes. Para isto temos uma variedade de fontes e recursos à nossa disposição; descrições sobre o funcionamento de uma Árvore B são facilmente encontradas na internet.

Uma coisa, no entanto, infelizmente não é: Implementações compreensíveis que também sejam, ao mesmo tempo, completas e funcionais.

Como exemplo, não raro encontramos o mesmo problema que tivemos ao encontrar informações sobre Árvores AVL. É dada menos ênfase aos métodos de remoção destas estruturas. Ou então, por vezes encontramos a Árvore B implementada fora de seu contexto: em memória. Árvores B reais servem ao propósito de serem armazenadas em disco; por isso seus nós são geralmente denominados páginas.

Introdução

Imagine que uma Árvore AVL contenha tantos dados que já não caiba mais em memória. Tentando contornar esta situação, podemos definir uma estratégia em que cada nó da Árvore AVL (que armazena no máximo 1 elemento) ocupe uma posição diferente dentro de um mesmo arquivo de dados. Para acessar um filho de um nó, por exemplo, podemos ler em qual posição o filho se encontra, navegar até a posição determinada e o carregarmos em memória. É fácil ver que esta solução resolve o problema da memória, pois a cada vez iremos carregar apenas a informação com o qual queremos trabalhar, e nunca a árvore toda.

Porém, imagine agora que gostaríamos de percorrer a árvore em busca de um elemento qualquer. Imagine também que o elemento em questão não está contido na árvore e que esta árvore tem, em termos gerais, n níveis de altura. Utilizando o algoritmo de busca em árvore binária, teremos de fazer, no mínimo, n leituras em disco para buscar a informação que queremos. Ou melhor, para concluir que não pudemos encontrar a informação que queríamos. Apenas relembrando, não esqueça o fato de que memórias secundárias como o disco rígido são geralmente ordens de magnitude mais lentas do que a memória principal.

Para n pequeno, é evidente que isto não faz diferença – o tempo de acesso a um disco rígido é, geralmente, de alguns milisegundos. Mas lembrando que como estamos falando de árvores realmente grandes, o acesso ao disco pode tornar-se um gargalo considerável.

Nesse contexto, a estrutura AVL torna-se bastante ineficiente. Como então solucionar este problema?

R: Diminuindo o número de seeks necessários para se alcançar uma informação.

A Árvore B (ou B-Tree) emprega uma estrutura paginada ideal para minimizar o acesso em disco. Cada um de seus nós contem não um elemento, mas vários; quantos seu desenvolvedor quiser. A cada acesso, várias, e não apenas uma informação, são lidas de cada vez. Desta maneira a informação torna-se muito mais condensada nos primeiros níveis, e altura da árvore diminui consideravelmente.

 

Citando a Wikipedia:

Em ciência da computação, Árvore B ou B-Tree é uma estrutura de dados árvores que são muito utilizadas em banco de dados e sistema de arquivos.

Para inserir ou remover variáveis de um nó, o nó não poderá ultrapassar sua ordem e nem ser menor que sua ordem dividida por dois. Árvores B não precisam ser rebalanceadas como são freqüentemente as árvores de busca binária com Árvore AVL. Árvores B têm vantagens substanciais em relação a outros tipos de implementações quanto ao tempo de acesso e pesquisa aos nós.

 

Esta é uma apresentação bastante razoável. No entanto, certa cautela precisa ser tomada pois autores diferentes tratam a ordem da Árvore B de maneiras diferentes, como por exemplo no livro Algoritmos – Teoria e Prática. Neste livro, os autores se referem não à ordem da Árvore, mas à seu grau t, definido como o número mínimo de filhos que um nó não-raiz pode possuir. Como consequência, o número mínimo de elementos de uma Árvore poderá ser tomado como t-1 e o máximo como 2t-1. Com isso, acabam efetivamente definindo a ordem da árvore (a que me refiro como sendo o número máximo de filhos de um nó) como 2t e o número máximo de elementos como 2t-1. Apesar de se enquadrar dentro das regras enunciadas acima na definição da Wikipedia, a apresentação de Árvores B desta forma inclui um pequeno problema.

A ordem de das árvores ficará restrita a termos pares (que estejam na forma 2t), o que simplifica os algorítmos de inserção e remoção, mas acabam por não mais descrever à uma Árvore B de ordem geral.

Por esta razão, o código que apresentaremos e documentaremos a seguir se adequa à Árvores B de qualquer ordem.

Propósito

Como bem sabemos, o propósito de uma Árvore B é otimizar o acesso e a manipulação da informação armazenada em discos, servindo geralmente como estrutura de índice à outros arquivos de registros no qual o índice pode se tornar muito grande para caber em memória. Neste contexto, atuando como índice, a árvore armazenará uma chave e a posição relativa em arquivo (relative record number ou byte offset) em que o registro se encontra no arquivo de registros.

Definições

Antes de prosseguirmos, enunciaremos primeiro algumas definições para que não haja confusão no decorrer deste artigo:

A ordem m da árvore está definida como o número máximo de filhos que um único nó pode possuir;

Logo, o número máximo de elementos num nó e dado por m-1 e o máximo de filhos por m. Já o número mínimo de elementos que um nó pode possuir é dado pela fórmula floor((m-1) / 2).

A Árvore B está implementada em arquivo, então definimos “Offset” como um typedef para long int. Para representar o equivalente em arquivo para o ponteiro nulo (NULL) utilizaremos o valor constante NULLOFFSET como -1L (menos-um na forma de long int). Esta é uma prática comum pois a posição 0, em arquivo, é uma posição válida, ao contrário de seu equivalente em memória.

Implementação

O código que apresentamos e documentamos a seguir se adequa à Árvores B de quaisquer ordens. A implementação foi feita em C++ no Microsoft Visual Studio, sem utilizar as extensões .NET/CLI (apesar da solução, em si, possuir código misto pois estava atrelada à uma interface gráfica em WinForms).

Clique aqui para ver o código e a documentação completos da Árvore B (BTree) em Arquivo (em C++) gerados pela ferramenta Doxygen. O código é, claro, livre para quaisquer adaptações desde que permaneça sob a Licença MIT e suas informações autorais sejam mantidas. Mas lembre-se de que o código tem fins meramente educativos e não deve ser utilizado num ambiente onde a performance é um fator crítico. Ou, melhor, não deve ser utilizado em outro lugar fora um trabalho acadêmico simples.

Diagrama de Classes

 

O Nó (BTreeNode)

O nó da Árvore B, aqui chamado de BTreeNode, pode conter vários elementos, em contraste com a Árvore AVL, em que pode haver apenas um. A Árvore B pode ser vista como uma generalização da Árvore AVL para ordens superiores, ou a Árvore AVL como uma especialização da Árvore B para ordem 2 (m=2).

Assim, o nó deve conter um vetor de elementos e um vetor de filhos, onde estes filhos, ao invés de conter ponteiros em memória, contem ponteiros em arquivo (Offsets) para os próximos nós.

Representação de uma Árvore B [Wikipedia]

É nesta classe que estão contidos os métodos split() e merge(), que divide um nó em dois e intercala dois nós em um único nó, respectivamente. Estes métodos são chamados durante a operação de Inserção ou de Remoção pela classe principal BTree, que é a classe gerenciadora dos nós. Mais informações serão apresentadas à seguir.

A Lista de Disponíveis (DStack)

Como a estrutura da Árvore B é mantida em arquivo, não basta alocarmos/desalocarmos nós em memória utilizando new e delete como fazíamos na Árvore AVL. Temos que alocar uma posição no arquivo que acomoda a árvore e armazenar o nó nesta posição; ao deletarmos um nó temos que, de algum modo, avisar que a posição que antes acomodava o nó agora está vaga. Para isto, utilizamos outra estrutura em arquivo denominada lista de disponíveis, que é responsável por registrar, na forma de uma lista encadeada, onde estão os registros disponíveis e assim indicar qual a próxima posição vaga no arquivo. Para simplificação, esta lista é, na verdade, geralmente implementada como uma pilha.

Assim, suponha que a pilha está vazia (a posição inicial registrada é NULLOFFSET) e a posição 241 foi desocupada. Então ao chamar o método push(241) a lista de disponíveis deverá caminhar até a posição 241, escrever NULLOFFSET e então registrar que 241 é o começo da pilha.

Agora suponha que 340 foi desocupada. Então o método push(340) irá caminhar até a posição 340, escrever 240, que é o endereço do nó que antes era começo da pilha, e registrar que a pilha começa agora na posição 340. Assim por diante, push(500) caminhará até a posição 500, escreverá o endereço do começo anterior (340) e registrará que a posição inicial é, agora, 500. Assim, os nós vão se encadeando – cada posição disponível carrega uma referência a próxima posição disponível ou a NULLOFFSET se não há nada mais além daquele ponto.

Para remover, pop() simplesmente deverá ler quem é a posição inicial, e, caso seja diferente de NULLOFFSET, caminhar até esta posição, ler qual é o endereço do próximo nó (ou NULLOFFSET, caso não haja mais nós) e então registrar esta posição como a nova posição inicial.

Clique aqui para visualizar a implementação da lista de disponíveis em C++.

 

A Árvore (BTree)

A classe BTree, ou Árvore B, deve ser responsável por gerenciar seus nós, alocando, dealocando, carregando e descarregando, tentando o máximo possível minimizar a quantidade de nós carregados em memória de cada vez. É nela que estão contidos os métodos de inserção e remoção, que em nossa implementação são recursivos.

Abaixo está uma pequena descrição sobre o funcionamento da inserção e remoção, porém note que seus códigos correspondentes são, na verdade, bem mais elaborados que esta pequena introdução. Felizmente, há comentários no decorrer do código para auxiliar em seu entendimento.

Inserção / Split

O método de inserção da classe BTree pode cair no caso em que não é mais possível armazenar informação num nó pois este está cheio. Quando isto acontece, chama-se o método-membro Split do nó que está cheio, que dividirá o nó em dois e retornará uma referência em arquivo (Offset) ao novo nó criado durante a divisão. O método que controla a inserção está presente na classe BTree, enquanto o split pertence ao BTreeNode.

Remoção / Merge

Analogamente a inserção, o método de remoção da classe BTree poderá cair no caso em que seja necessário remover um elemento de um nó mas efetuar esta operação violaria a regra sobre o número mínimo de elementos que um nó deve conter. Neste caso, a árvore pode encontrar o elemento sucessor (imediatamente seguinte) ao elemento que estamos tentando remover, trocar os dois e então remover o substituto recursivamente, ou, caso não seja possível emprestar de ninguem, realizar uma intercalação entre dois nós mínimos formando um novo nó completo. Esta intercalação é conhecida como merge. O método que controla a remoção está presente na classe BTree, enquanto o merge pertence ao BTreeNode.

 

Código fonte em C++

O código fonte pode ser navegado na íntegra clicando-se aqui. Para fazer download de uma solução Visual Studio 2008 contendo o fonte, clique aqui.

Google Desktop on Windows x64

google-desktop

Google Desktop now offers a command line flag to force installation on 64 bit machines. Just install with

 googledesktopsetup.exe /force

If you don’t wanna deal with the command line, just right click the setup executable, then click “Create Shortcut“. Right-click the newly created shortcut, select properties, then add the /force to the end of the target path text box. Hit ok and finally double click it. Voilà!

Google Desktop used to work on 64 bit Windows (like Windows XP x64 Edition and Windows Vista 64 bit), but ceased installing some months ago. I have used Google Desktop normally on my desktop before, but I got surprised when a newer version went out simply telling me it wouldn’t install because Google Desktop wasn’t anymore supported on my platform, leaving me with no software at all. I don’t know exactly to which extent the “not supported” definition goes, but, for now, the software has been running just well. The Google Desktop Help Center reports that certain features may not work correctly, so you have been warned.

Software Licenses’ Legal Notices

800px-Gpl_auto
When releasing software it is always good to release under a suitable license. Licensing policies were created to protect you and your code, restricting what others can do using your code, and not what you can do with your own code. The copyright holder (the author, e.g. you) is able to change licensing policies anytime, but, depending on the license you choose, only as long as every author and every person who has ever contributed to your project also agree.

Wikipedia offers a list of popular licenses and a comparison of free software licenses you can use in your projects. But no matter which one you choose, a common practice is to include a license notice header in all your source files to enforce the restrictions you have chosen. Here is a list of common headers for the most common available software licenses. Comparison between its different implications is beyond the scope of this post, but more information is available on the Additional Information section below.


GPL – GNU Public License (details)

LGPL – Lesser GNU Public License (details)

MPL – Mozilla Public License (details)

BSD License (details)

MIT License (details)

Apache License (details)

CC – Creative Commons (details)

Creative Commons licenses are not intended to apply to, and should not be used for software. I’ve included it here just to remember you.

Public Domain (details)

This is only a suggestion as there is no common sense on how to dedicate your work for the public domain. This excerpt was borrowed from the SQLite site, a popular software that is itself dedicated to the public domain.

WARNING: Please pay attention that the Public Domain Dedication is not a license. By using it, you do not simply carve out exceptions to your copyright; you grant your entire copyright to the public without condition. This grant is permanent and irreversible. You’ve been warned.


Additional Information


For a nice comparison of different licenses, implications and more useful information, please check:

Comparison of Source Code Licenses

Also, before blindly adopting the GPLv3, please be sure you have completely and correctly understood everything it says. For more info about the GPL and the GPLv2 vs GPLv3 debate, see:

The GPL for Dummies
The GPLv2 vs. GPLv3 Debate
What the kernel guys are and aren’t (and really should be) saying about GPLv3
The Dangers and Problems with GPLv3
The GPLv2 vs. GPLv3 Chart

Personally, I would rather go with the GPL v2 instead.