quarta-feira, 13 de junho de 2012

O Bug mais Difícil

Essa é uma pergunta clássica em entrevistas: qual foi o bug mais difícil que você já consertou? No meu caso, o bug mais difícil que resolvi deu um trabalhão para encontrar, e por um motivo bastante curioso: o bug não era no programa, mas sim na pecinha entre a cadeira e o teclado!


A história


Essa história se passa em agosto de 1998. Nessa época, eu estava escrevendo um emulador de MSX, e tomando dois cuidados na implementação: o emulador tinha que ser rápido o suficiente para rodar em full speed nas máquinas da época, e tinha que ser preciso o suficiente para ser indistinguível de um MSX real.

O primeiro objetivo eu atingi escrevendo o emulador inteiramente em Assembly, o segundo através de uma metodologia de testes sólida. Na época eu ainda não fazia unit testing, mas, para cada feature adicionada, eu sempre fazia um programa de teste e comparava a execução dele no emulador e na máquina real.

As primeiras versões do emulador eram mudas, eu emulava só a CPU e o chip de vídeo. Quando esses dois ficaram estáveis, eu comecei a escrever a emulação do chip de audio: o AY-3-8912 da General Instrument, também conhecido como PSG. Esse chip tinha capacidade de produzir três canais de som e um canal de ruído, sendo que o ruído era usado para fazer efeitos sonoros (como tiros e explosões), e também para fazer sons de percursão (como baterias).

Para testar se a minha implementação do canal de ruído estava boa, eu fiz o seguinte programinha em MSX BASIC:

10 SOUND 7,183
20 SOUND 8,15
30 FOR I=8 TO 1 STEP -1
40 SOUND 6,I
50 PRINT I
60 FOR J=0 TO 300: NEXT J,I
70 BEEP

Os números mágicos no código assustam, mas o funcionamento é simples: o registro 7 é o mixer, com o valor de 183 eu ligo o gerador de ruído no canal A e desligo todo o resto. O registro 8 é o volume do canal A, que eu setei para 15, ou seja, volume máximo. Por fim, eu faço um loop alterando o valor do registro 6, que é a frequência do ruído.

Portanto, o que se espera desse programinha é que ele toque um barulhinho de volume constante, começando grave e ficando cada vez mais agudo. Isso na teoria. Na prática, aconteceu outra coisa!

O bug


Eu resolvi repetir o experimento da época e filmar. No video abaixo você pode ouvir esse programinha rodando em um MSX real, e depois rodando no meu emulador (eu usei o dosbox para compilar a versão de 1998, antes do bug ser corrigido):




Olha que curioso, embora eu tenha programado o volume para ficar constante, no MSX real o volume abaixa sensivelmente no final. E pior, no emulador isso não acontece!

A diferença é sutil, será que eu estava viajando? Um jeito de confirmar é capturando os dois sinais e jogando no Octave para comparar (quer dizer, na época ainda não tinha o Octave, então eu usava o Matlab mesmo):


De olho parece realmente que o turboR vai diminuindo, mas é difícil comparar. Um jeito mais eficiente é notando que a grandeza que perceptualmente nós sentimos como volume, fisicamente é causada pela potência do sinal. E potência a gente sabe calcular, é a integral do quadrado da forma de onda. Jogando isso no Octave:


Olha lá! Não era viagem não, nos dois últimos passos realmente o volume do turboR fica menor que o do emulador! Mas por que isso acontece? Talvez eu tivesse alguma pista analisando o hardware com cuidado.

O circuito


Para entender o funcionamento do PSG, não adianta usar o esquemático do MSX e nem pegar o datasheet do AY-3-8912, porque nenhum dos dois explica o que acontece dentro do chip. Em teoria daria para abrir o chip e tentar ler a pastilha com um microscópio eletrônico, mas como eu não tinha acesso a um, o jeito foi apelar para engenharia reversa mesmo.

Os canais de som do PSG foram fáceis de modelar. Ele tem três geradores de onda quadrada, e cada um funciona da seguinte forma:


O clock de entrada do contador é o clock do MSX dividido por 16, ou seja, 223506Hz. A cada pulso, o contador incrementa de um, e o resultado é comparado com o valor do registro que determina a frequência. Quando o valor é igual, o contador reseta e um flip-flop tipo T inverte de estado, gerando assim a onda quadrada desejada.

Mas e o gerador de ruído? Na época ninguém sabia como funcionava, uns chutavam que era ruído térmico de resistor, outros que era shot noise na junção de algum semicondutor.

Mas a verdade era muito mais simples, o PSG tinha um gerador pseudo-aleatório! Para ser mais exato, tinha um gerador de onda quadrada igual ao descrito acima, e a cada transição na saída ele fazia uma iteração em um Linear Feedback Shift Register.


Nós sabemos que todo LFSR gera um sinal periódico, então, capturando um período inteiro do gerador, dá para deduzir qual é o polinômio característico dele. Fazendo o experimento, o polinômio era o maximal de tamanho 17, ou seja, x17+x14+1.

Eu conhecia a forma de onda gerada, e conhecia até o exato LFSR que era usado. Ainda assim, isso não explicava por que o volume abaixava. Será que eu tinha implementado errado?

A implementação


Um dos meus requisitos era rodar o emulador a toda velocidade nas máquinas da época. Em 1998, isso significava emular esse circuito inteiro em um Pentium 1, e ainda sobrar tempo para emular a CPU e o VDP. A coisa era tão apertada que simplesmente escrever em Assembly não era suficiente, eu tinha que garantir que o inner loop rodasse inteiramente em registros.

O problema é que os meros 7 registros de uso geral do x86 não eram suficientes. Minha primeira solução foi apelar feio: durante a emulação do PSG, eu desligava as interrupções e usava o stack pointer como registro! Na minha casa isso funcionava bem, mas em casa eu usava DOS. A maioria dos meus usuários à época usava Windows 95, e aí essa abordagem de mexer no esp fazia a máquina travar.

Vamos para a solução dois então. Tinha um monte de variáveis que mudavam a cada nota tocada pelo PSG, mas eram constantes durante o inner loop. Sendo assim, era uma boa oportunidade para usar código auto-modificável: eu "recompilava" o inner loop cada vez que alguém mudasse um registro do PSG. Essa solução funcionava até no Windows e era rápida o suficiente.

Porém, ela era rápida, mas bastante complexa. Você pode ver esse código no github, não é a coisa mais legível do mundo, nem a mais fácil de entender. Então, seria de se esperar que o volume não estivesse abaixando por conta de algum erro de implementação.

Mas após pensar um pouco, eu concluí que a minha implementação deveria estar correta. Se ela estivesse errada, então esse erro deveria aparecer só no meu emulador. Mas na época exisitiam outros emuladores, e em todos os outros esse mesmo problema aparecia.

Se várias implementações diferentes tinham o mesmo problema, então o erro não era no código, tinha que ser conceitual. E se é conceitual, então talvez eu conseguisse alguma pista analisando matematicamente o sinal.

A transformada


Hora de fazer a modelagem do sinal então! Vamos considerar que os bits de saída do LFSR formam uma sequência discreta {di}, e que a cada bit 1 na entrada nós mandamos para saída uma forma de onda s(t). Dessa maneira, se a largura do pulso for T, então o ruído do PSG pode ser computado como:


Da teoria de processos estocásticos, nós sabemos que a densidade espectral de potência do sinal, nesse caso, vale:


...onde Gd(f) é a densidade espectral de potência da sequência {di}, e S(f) é a transformada de Fourier de s(t). Se admitirmos que o ruído em questão seja ruído branco, então o Gd(f) é uma constante. Já a forma de onda s(t) é um pulso retangular, cuja transformada é a função sinc. Portanto, a d.e.p. do sinal tem a forma de um sinc ao quadrado. 

O caso que dá problema no emulador é quando o registro 6 vale 1, ou seja, quando T=8.98µs. Assim, a densidade espectral de potência da saída é a abaixo:


Novamente, aquilo que perceptualmente nós percebemos como volume é a potência do sinal, e, pelo teorema de Parseval, a potência é a área abaixo do gráfico acima.

Depois de olhar um tempo para esse gráfico, finalmente caiu a ficha!


A solução


No fim, o problema todo estava entre a cadeira e o teclado! Mais especificamente, no fato de que tinha um ser humano entre a cadeira e o teclado! O sistema auditivo humano só consegue ouvir freqüências até 20kHz, e esse sinal estava espalhando potência para faixas inaudíveis! De fato, um humano só consegue perceber como volume essa parcela da potência:


A integral do sinc ao quadrado não dá para resolver analiticamente, mas dá para calcular numericamente. Eu posso, por exemplo, fazer uma tabela com a potência audível dividida pela potência total, para cada um dos valores de frequência que eu usei no programinha em BASIC:


Registro 6Porcentagem da potência audível
80.99
70.99
60.99
50.99
40.99
30.96
20.83
10.50


Se você comparar com o gráfico de potência do emulador versus turboR, dá pra notar que a porcentagem acima é exatamente o que falta para tornar a volume do emulador igual à máquina real! Adicionando essa atenuação no emulador, ele finalmente ficou fiel ao original como eu queria.

Leitores que estejam prestando atenção, a essa altura devem estar se perguntando: "Mas peraí, se o problema é puramente sensorial, então porque o gráfico de potência medido no Octave mostra a perda de volume?". A resposta é que isso também é um artefato do sistema auditivo humano, mas indiretamente.

Quando eu pluguei o turboR na entrada de microfone do meu notebook, a placa de som fez a captura do audio em qualidade de CD, ou seja, com amostragem de 44100Hz. E os projetistas da placa de som são espertos, eles sabem que antes de amostrar você precisa passar o sinal em um filtro passa-baixas com corte na frequência de Nyquist, para evitar o aliasing. E essa frequência foi calculada exatamente para jogar fora o que os humanos não ouvem, gerando o mesmo problema.

Se você quiser refazer o experimento, coloquei no github os scripts em Octave que usei para gerar as imagens e tabelas do post:

Scripts em Octave para análise de ruído

Por fim, esse bug deu um trabalhão para resolver, e no final desconfio que a diferença era tão sutil que ninguém além de mim notou a diferença :)

21 comentários:

  1. Excelente análise, Ricardo! Eu acho que muita gente nota a diferença, mas não consegue chegar à uma conclusão. As pessoas simplesmente assumem que "não tem como a emulação ser exatamente igual ao real"... :)
    Talvez alguns possam argumentar que "não vale a pena o esforço", mas quando é feito por diversão... o prazer que este tipo de descoberta causa não tem paralelos. :D
    Um grande abraço,
    DJC

    ResponderExcluir
  2. Clap clap clap! Excelente post, Ric.
    A explicação ficou 10 e a aventura em si é sensacional.

    ResponderExcluir
  3. Ricardo, já te achava muito louco em 2000/2001 quando conheci o BrMSX e o BrSMS... agora ao ler seu post explicando o bug mais difícil tenho mais certeza ainda!!
    Espero que um dia vc tenha tempo livre para atualizar o BrMSX...
    Hoje em dia uso o BlueMSX no meu PC, mas volta e meia eu recorro para o meu velho P133 pra lá de amarelado para utilizar o BrMSX, pois é como se fosse um MSX de verdade!

    ResponderExcluir
  4. Vc vai ficar bravo se eu disser que tem uma coisa que eu não entendi?

    Se o problema não era do PSG mas sim do que o ser humano pode ouvir, como eu consigo ouvir o ruído agudo do emulador sem perda de volume?

    ResponderExcluir
    Respostas
    1. Esse que era o problema, no emulador não tinha perda de volume, só na máquina real.

      O emulador gerava a saída diretamente em 44100Hz, que era o máximo que a SoundBlaster da época suportava. Para a perda ser perceptível, ou o emulador tinha que atenuar diretamente o sinal (que foi o que eu fiz), ou então eu teria que gerar a onda em 220kHz e depois filtrar (que seria o mais correto, mas os Pentiums da época não davam conta).

      Excluir
    2. Entendi! Toda a potência do ruído no emulador era audível, mas de toda a potência do PSG, só uma parte ficava na faixa de audição! :-) Legal, excelente texto!

      Isso me fez lembrar do dia em que o DOS me pregou uma peça, imperdível! rs.

      Excluir
  5. Hehehe, eu me lembro de quando você lançou a versão com código auto-modificável, no README.TXT, em inglês, você mencionava "a Brazilian programming technique known as GAMBIARRA". :-D

    ResponderExcluir
    Respostas
    1. Zoar gringo era metade da diversão :)

      Pena que o archive.org só tem o site do BrMSX a partir de novembro de 98, perdeu esse release da gambiarra (mas tinha o link pro seu emu de arcade já) -> http://web.archive.org/web/19981205073159/http://www.lsi.usp.br/~ricardo/brmsx.htm

      Excluir
    2. E isto me fez lembrar do recurso mais esperado de todos os tempos: a rebimboca da parafuseta!

      Excluir
  6. RicBit,

    Gostei da explicação. Parabéns pela descoberta.

    Aceite meu abraço,

    Fernando Tollendal - Brasília

    ResponderExcluir
  7. RicBit, a análise e explicação ficaram show! Parabéns! :D

    ResponderExcluir
  8. Pois é, "primo"... Doeu minha cabeça na parte das fórmulas, mas deu para entender bem o conceito...

    Parabéns, excelente post!

    ResponderExcluir
    Respostas
    1. Tem um ditado conhecido na literatura de divulgação científica, "cada fórmula que você coloca diminui o número de leitores pela metade" :)

      Excluir
    2. Eu tenho um "macete" (outra técnica Brasileira) ao ler artigos científicos: pulo as fórmulas e só depois de ver se o artigo é realmente interessante eu procuro entendê-las ;).

      Excluir
  9. Nossa Ricbit, nunca imaginei que o que aprendi (e já esqueci) de processos estocásticos na faculdade foi aplicado num problema do BrMSX!
    O que eu lembro da época era que a emulação era perfeita, e joguei muita coisa com ele no meu Pentium 133Mhz e 16Mb de memória.

    ResponderExcluir
  10. Oi, Ricardo. Belíssimo post. Um amigo indicou teu blog para mim há algumas semanas e tenho apreciado os teus posts. Muito bons. Ainda tenho uma curiosidade que o Google não me ajudou a esclarecer: qual a tua idade ? Um grande abraço!

    ResponderExcluir
    Respostas
    1. Tem um post no blog da minha esposa sobre isso!

      http://www.ilafox.com/2010/09/ricbit-idade.html

      Excluir
    2. Jóia. Isso bate com a minha intuição e agora teus posts fazem mais sentido. Tive o prazer de conhecer pessoas muito precoces e que tinham muito êxito ao desenvolver raciocínios mais elaborados e também por terem curiosidade incomum para a normal daquela faixa etária (capacidade cognitiva X faixa etária). Eis o motivo da minha curiosidade. Isso foi ressaltado com o teu post sobre o "bug mais difícil". Bacana! Fiquei muito satisfeito com a resposta. Muito obrigado pela gentileza em fornecer a resposta e, mais ainda, por compartilhar idéias tão interessantes. Identifico-me bastante com teus posts. Tenho 30 anos agora e um bom background em literatura e lingüística, física, matemática, computação e eletrônica (ufa!). Às vezes me arrependo de estar preso a uma corporação grande como a que tu estás. Trabalho, atualmente, com APM (Application Performance Management) e mantenho outros projetos pessoais/estudos em paralelo.

      Parabéns! Agora fico sempre ansioso pelo próximo post! risos

      Abração!

      Excluir
  11. Muito legal o post! Eu consegui perceber que um som termina primeiro. Eu gostei desse sistema de análise de sinal com o Octave. Muito inteligente essa ideia! Eu tenho vontade de escrever um simulador do Nestor (um computador com display de 7 segmentos e um teclado horrível!!) utilizando a porta paralela pra fazer a parte de interfaceamento. Ele utiliza o mesmo processador do MSX.
    Gosto mto desse blog pela grande qualidade dos artigos! Obrigado por compartilhar esse tipo de informação. E Bugzinho do hell esse!

    ResponderExcluir
    Respostas
    1. No emulador termina primeiro mesmo, mas aí não é bug. É que o emulador está usando a ROM do MSX-1, e essa ROM tem menos overhead que a ROM do MSX turboR (se você notar, o tom do BEEP no final é diferente também, por causa disso). Se fossem duas ROMs iguais, elas teriam a mesma duração.

      Excluir