Consegui mais dois autógrafos, dessa vez do Steve Russell e do Peter Samson, criadores do Spacewar!

Para quem não conhece, o Spacewar foi o primeiro videogame a viralizar. Existiram outros videogames antes, mas nenhum fez sucesso como Spacewar. Foi criado em 1962 no MIT e dali os cartões perfurados com o jogo foram parar em todos as universidade que tinham um PDP-1. (Um desses cartões foi parar na mão do Bushnell, e ele criou o primeiro arcade do mundo, Computer Space, que também foi o produto que deu origem à Atari).

O Russell e o Samson estavam ontem no Computer History Museum de Mountain View fazendo uma demonstração do Spacewar no PDP-1 funcional que tem lá. O Russell foi o idealizador do jogo e main programmer, o Samson pegou o jogo original e adicionou as estrelinhas no fundo haha. (Você pode achar que estrelinhas no fundo são meh, mas essas estrelinhas são astronomicamente corretas: ele desenha corretamente o céu do MIT no horário atual. Se você jogar por horas a fio, dá para ver as estrelas mexendo).

Aproveitei, é claro, para matar minhas curiosidades técnicas. A primeira coisa impressionante é que apesar do PDP-1 ter o tamanho de quatro armários grandes, o jogo boota instantaneamente. O segredo é que o PDP-1 usa core memory, e core memory não é volátil. Se deixar desligado por vinte anos, o jogo ainda vai estar na memória quando você ligar. Outra coisa que eu não entendia é como ele tinha um framerate tão alto. Um Z80 iria morrer calculando as equações de Newton nessa velocidade. O truque é que o PDP-1 tem multiplicação e divisão por hardware! (Quando você comprava o PDP-1, podia escolher quais opcodes queria instalar na CPU dele).

Agora, o que me pegou de surpresa na apresentação, e que eu não fazia a menor idéia, é que o Peter Samson foi o autor da primeira música polifônica sintetizada por computador! O PDP-1 tem leds programáveis no gabinete, então o que ele fez foi conectar os fios que iam pros leds num alto-faltante, e ligar e desligar rapidinho o sinal neles. Tcharam: quatro ondas quadradas programáveis por software. E ele tinha alguns cartões originais, então além de jogar ao vivo o primeiro videogame, deu também para ouvir ao vivo a primeira melodias polifônica sintetizada.

(Eu gravei o audio da palestra, depois edito e coloco online em algum canto).

Começando com um mea culpa, infelizmente eu sou responsável por boa parte dessa merda toda. Na década de 90 eu tinha website e fanzine digital, ajudei a criar a cultura brasileira na internet. No começo do século eu trabalhava criando dispositivos de inclusão digital, e depois eu fui desenvolvedor do Orkut, a rede social que ensinou os brasileiros a usar a internet.

Eu fiz tudo isso na inocência, achava de verdade que a internet iria trazer mais informação a todos, e que isso melhoraria o mundo. Hoje vejo que fui ingênuo, subestimei o papel da falsa informação e de como a internet permitiu a manipulação de massa de um jeito muito mais eficiente.

Mas se me permitem, eu acho que sei onde a coisa deu errado e tenho uma sugestão para melhorar. Eu acho que o foco do problema é o *broadcast privado*.

Broadcast nunca fui problema na internet. As pessoas mandavam mensagens em lista de discussão, postavam em comunidade do orkut, e nesses meios o fake news nunca teve esse poder que tem hoje.

O que mudou é que hoje em dia você pode fazer broadcast para grupos fechados (tipo o zap da família). Isso foi o game changer. Quando você postava na lista de discussão ou na comunidade do orkut, você estava aberto à contestação, se você posta X, alguém sempre pode postar não-X logo abaixo. Em termos de evidência acumulada, as coisas se cancelam.

Mas o zap da família é diferente porque é uma rede de contatos confiáveis. Você confia nos seus parentes. Quando chega uma mensagem nesse grupo, você tende a confiar por default na mensagem porque você confia em quem mandou, e essa confiança no emissor transfere para a mensagem.

Aí você forma uma rede de confiança. Não importa que o emissor original seja um bandido na cadeia, escrevendo de um celular que entrou na cela enfiado no cu. Se a mensagem dele passar de grupo em grupo, ela vai ganhando confiança ao longo do trajeto, porque cada broadcast privado aumenta a confiança dela. A confiança vem do caminho, não do conteúdo.

A solução fácil para isso seria banir broadcast privado. Não pode mais ter grupo de zap, ou pelo menos não pode ter botão de share para grupo privado: se você quiser repassar, vai ter que reescrever. Aumentando a fricção no processo de share, a mensagem falsa tem mais dificuldade de propagar.

Outra solução seria fazer tracking da confiança da mensagem. Eu não faço idéia de como implementar isso, mas cada mensagem teria que ter um score que medisse a confiança da origem. Uma mensagem que transitou inalterada de uma fonte primária teria score alto, uma mensagem enviada por celular tirado do cu teria score baixo.

Mas eu não sei se nenhuma dessas alternativas é economicamente viável, dado que os times que implementam esses apps medem sucesso baseado em quantidade de shares. Se alguém tiver uma idéia melhor para atacar o problema eu agradeço.

Programar computadores para mim é mais que uma atividade, é um estilo de vida. Praticamente tudo que eu faço gira em torno disso. Meu trabalho é programar computadores, nas horas vagas eu programo computadores por hobby, até minha esposa eu conheci numa comunidade de computadores.

E quem me ensinou a programar computadores foi meu pai. Quando eu era bem pequeno, nós programávamos BASIC usando papel e lápis. Nos fins de semana ele me levava para o trabalho dele, onde eu treinava nos computadores da empresa. E depois de um tempo nós conseguimos comprar um TK90X que foi o meu primeiro computador.

Estava aqui pensando que meu pai tem muito em comum com o Prometheus da lenda. Prometheus deu a vida aos humanos a partir do barro, e depois roubou a chama do conhecimento para a humanidade. Foi isso que meu pai fez, me deu a vida e o conhecimento da programação. Todo o resto que eu fiz veio disso.

Após roubar a chama do conhecimento, Prometheus foi preso em uma montanha, onde toda noite uma águia comia um pedaço de seu fígado. Infelizmente, meu pai também teve isso em comum com ele. Mas, ao invés de uma águia, foi um câncer que comeu o fígado do meu pai. Desses que crescem muito rápido, e não tem remédio nem Hércules que segure.

Hoje meu pai faleceu. Obrigado por tudo pai, você foi um Titã.

O Sloane publicou uma sequência que eu inventei no OEIS! A sequência é "a quantidade de caminhos de n passos feitos por um rei que começa no canto de um tabuleiro de xadrez infinto". O link é https://oeis.org/A300665

A história da sequência é assim: a gente sabe que o melhor método para resolver puzzles é o exact cover, mas ele só funciona para puzzles tipo sudoku (cada quadrado pode ter só um número), e não funciona em puzzles tipo akari (cada quadrado pode estar iluminado por mais de uma lâmpada).

Mas no começo do ano o Knuth publicou uma variação do exact cover que funciona com todos os puzzles, de fato, funciona com qualquer problema que possa ser descrito como constraint programming.

É claro que a primeira coisa que passou pela minha cabeça foi: "serve para o Torto Reverso?" (*) Quer dizer, é claro que serve, mas é um bom algoritmo na prática? Antes de codificar, eu resolvi estimar qual seria o tamanho da matriz de cover, e de cabeça ela tem que ser mais ou menos da ordem do número de caminhos que um rei por fazer no tabuleiro de xadrez (já que os movimentos do rei são os mesmos movimentos do torto reverso).

Usar os métodos do post de ontem (**) não funciona porque os caminhos não podem repetir casas. Então tem que ser a força bruta mesmo. Fiz um scriptinho em python e damn, a(7)=60215, isso não vai convergir nunca, a matriz é muito grande.

De curiosidade, eu peguei a sequência e coloquei no OEIS para ver se tinha assintótico, e uepa! ninguém tinha calculado essa sequência ainda! Fiz uma implementação em Mathematica para conferir as contas e submeti a sequência.

O povo do OEIS adorou, mas achou pouco. Com o python eu consigo ir até a(12) só e eles queriam mais. Então eu apelei e reimplementei em C++, aí deu para ir até a(15). Mesmo com a cpu em 100% não dá para ir muito além.

Mas eu não me preciso me limitar a 100% de cpu né? Reimplementei em Go e usando 800% de cpu eu consegui o a(16). Depois eu reparei as sequencias são simétricas em relação ao eixo de 45 graus, então só preciso calcular metade delas. Aí cheguei no a(17). Depois disso todas as minhas heurísticas falharam, mas eu ainda não desisti. (Quer dizer, é só deixar o computador ligado uma semana direto que eu pego mais números, mas eu queria um jeito que dê para computar rapidamente).

(*) Se você não conhece o torto reverso, o prêmio ainda não teve ganhadores -> http://blog.ricbit.com/2011/05/torto-reverso.html
(**) Se você perdeu o post de ontem sobre otimização em grafos, ainda dá tempo -> http://blog.ricbit.com/2018/03/a-marcha-dos-lemmings.html

Estava lendo agora sobre a vulnerabilidade nova que estão exploitando, e é bem legal!

Funciona assim: primeiro você executa um código desse jeito:

If (bigvalue < a.length) { value = a[bigvalue]; }

Se bigvalue for um valor maior que o tamanho do array, voce faria uma leitura fora de bounds, o que te permitiria ler qualquer valor da memória. Mas isso não deveria acontecer, por dois motivos: primeiro o if garante que você nunca executa aquele trecho; segundo mesmo que permitisse a cpu iria estourar um page fault porque você não tem permissão de ler aquele endereço.

SÓ QUE sua cpu tem execução especulativa. Se o a.length estiver fora do cache, a cpu precisa esperar uns 100 ciclos até o valor chegar. Para não ficar parada, ela sai executando o interior do if, e descarta essa execução quando o valor chega.

Em princípio isso não deveria ser acessível para o usuário, mas olha a pegadinha: como ele executou especulativamente o if, então agora o a[bigvalue] está no cache!

Agora você pode usar o seguinte código:

If (bigvalue < a.length) { value = a[bigvalue];
If (value&1 > 0) { x = a[100]; } else { x= a[200];}
}

Você controla o array a, então suponha que você forçou o array inteiro para fora do cache. Quando você executar esse código, a cpu vai tentar ler o a.length e travar (já que está fora do cache). Ela vai tentar executar especulativamente o if interno, e ela consegue (nesse ponto o a[bigvalue] está no cache e a cpu está executando especulativamente, então não checa as permissões). Dependendo do bit 0 do a[bigvalue] ela vai tentar ler o a[100] ou o a[200]. Eventualmente o valor de a.length chega e a cpu rebobina tudo porque o primeiro if falhou.

Agora vem a malandragem, você mede o tempo que leva para ler a[100] e a[200]. Só um deles foi parar no cache, aquele que ler mais rápido indica qual o valor do bit 0 de a[bigvalue]! Você acabou de ler um bit que não tinha permissão! Repete isso para os outros bits e você consegue ler qualquer valor da memória, até a senha do banco que está no outro tab do seu browser!

Para matar isso é fácil, só desligar o cache na bios. Mas aí seu computador de 2018 vai ficar mais lento que 386 rodando Windows 10, então ninguém vai fazer isso. Sacada muito boa, kudos para quem inventou a técnica.