A equação mais bonita de todas!

Dizem que a equação abaixo é a mais linda já descoberta:

\displaystyle e^{i\pi}+1=0

Se é linda ou não, eu não sei… cada um tem lá os seus fetiches, mas que é impressionante, ahhh, isso é… Repare… O valor e (chama-se “neperiano”) é transcendental (ou seja, é uma sequência de números sem fim: e = 2.718281828…), o valor π é outro velho conhecido da mesma laia. e i é uma raiz quadrada de um valor negativo!!! Como é que esse troço pode ser somado a 1 e obter zero como resposta?

Tudo começou com um triângulo

Para começar a história sobre a esquisitice acima, e nosso modelamento de fenômenos físicos, é necessário entender algumas coisas: Principalmente trigonometria (do grego, trigonón [triângulo] e metrós [medida], é a medição das relações de um triângulo retângulo) e logaritmos (também o grego: logos [estudo] e arithmós [número, que é a mesma raiz da palavra aritmética] — o sentido aqui é “o estudo das relações entre números”). A necessidade dos logaritmos ficará evidente logo…

Quanto a trigonometria, as relações entre os lados de um triângulo retângulo podem ser representadas através de outra figurinha geométrica elementar e cíclica. O círculo!.

Círculo trigonométrico, onde o raio é igual a 1...
Círculo trigonométrico, onde o raio é igual a 1…

Temos ai um vetor unitário (tamanho igual a 1, sempre) de coordenadas (\cos t, sen t). Num triângulo retângulo a relação do lado projetado no eixo x (o “cateto adjacente”) e o segmento de reta entre a origem do sistema de coordenadas do plano cartesiano e a borda da circunferência (“hipotenusa”), é chamado de cosseno do ângulo t formado entre o eixo x e o segmento de reta (o raio). A projeção no eixo y (“cateto oposto”) é o seno do ângulo… Se fizermos o ângulo variar de 0 até 2π, o ponto (x,y) ficará girando no trajeto da circunferência e, com isso, podemos obter as “formas de onda” características da variação dessas projeções:

Seno e cosseno.
Seno e cosseno.

Sabemos, há muito tempo, que usando cossenos e senos, podemos escrever, algebricamente, quase todas as equações que envolvem algo cíclico. Este é o motivo da trigonometria ser tão importante…

Uma curiosidade: Os nomes “seno” e “cosseno” são traduções erradas de palavras hindus, traduzidas do árabe. O conceito de “seno” e “cosseno” surgiu graças a necessidade de realizar cálculos astronômicos. Esse tipo de coisa: A adoção de um nome com base em um erro de tradução é mais comum do que você pode supor. O próprio uso da variável x, tradicionalmente usada como variável independente em equações, deve-se a uma adaptação da primeira letra da palavra árabe شيء (que significa “coisa” – a primeira “letra” é ش) para a letra grega Χ (parece um ‘xis’, mas é a letra grega “chi”) — veja essa explicação interessante do professor Terry Moore, num TED Talk.

Logarítmos e a multiplicação de valores “difíceis”:

No século XVII um sujeito chamado John Napier formalizou uma maneira de multiplicarmos valores grandes. De família de nobres, Napier começou seus estudos em alguma universidade, mas largou o curso, dedicando-se aos negócios da família. Essencialmente, ele era um fazendeiro com uma paixão pela matemática. E, como fazendeiro, tinha que lidar com cálculos simples, mas trabalhosos para a época… Já que não existiam calculadoras eletrônicas e computadores, a simples multiplicação de dois valores grandes era um troço meio chato de fazer (ainda é! tente multiplica 513267 \cdot 3241687, manualmente!). Napier formalizou (não, ele não descobriu!… Em certo sentido, logaritmos eram conhecidos desde o século XVI A.C, por povos Babilônicos) um método de usar adições para realizar multiplicações…

Tome os valores 10 mil e 100 mil. Ambos podem ser escritos como 10000 e 100000. Multiplicá-los é trivial, mas fazendo manualmente e usando o algoritmo que todos conhecemos e amamos, teríamos algo assim:

      100000
     × 10000
    --------
      000000
     000000
    000000
   000000
+ 100000
------------
  1000000000

É fácil perceber que podemos fazer essa conta de outra maneira, usando expoentes: 10^5 \cdot 10^4 = 10^{5+4} = 10^9. O que fizemos? Transformamos uma multiplicação em uma adição (dos expoentes), certo? Com valores cujos expoentes são inteiros é fácil, mas e quanto aos dois valores que pedi que você multiplicasse? Ora, tudo o que temos que fazer é achar os expoentes, cuja base é 10, que nos dê os dois valores desejados. Obtido isto, podemos simplesmente somar os expoentes e obteremos o resultado. Aproximadamente assim:

\displaystyle \begin{matrix}513267\cdot3241687&\approx\\  10^{5.710343343}\cdot10^{6.510771079}&\approx\\10^{12.221114422}&\approx\\  1.663850961\cdot10^{12}\end{matrix}

O que Naiper fez foi construir tabelas onde poderia consultar os valores apropriados. Isso também levou à criação da régua de cálculo logarítmica, usada por engenheiros até o início dos anos 70, acelerando um bocado as operações de multiplicação (e divisão) de valores “complicados”. O vídeo abaixo é interessante, se você quer entender como as tabelas funcionavam:

E este, sobre a régua de cálculo:

Eu, obviamente, descobri os valores fracionários dos expoentes usando uma calculadora, mas antes delas, eram usadas tabelas, criadas a partir da descoberta de Napier. E, não! Tabelas de logaritmos e réguas de cálculo não são da minha época (velho é a mãe!).

Um valor que acontece em todo lugar, na natureza

A conversa mole sobre logaritmos só serve de contexto histórico e uma curiosidade para esse texto, já que Napier descobriu outras relações interessantes e o neperiano foi nomeado em homenagem a ele…

O neperiano surge, além de relações matemáticas, como uma comprovação de que esse valor ocorre naturalmente em todo lugar para onde se olha. Ele é um valor tão surpreendente quanto π é, para a trigonometria… A ocorrência abundante na natureza dá o nome do tipo de logaritmo cuja base é e de “logaritmo natural”.

Na época de Isaac Newton (século XVIII) o valor e já era conhecido, graças a um sujeito chamado Jacob Bernoulli (que era tarado por séries infinitas), mas a “popularização” e o nome da constante é creditada a Leonhard Euler (fala-se “Óiler“), dai a letra e.

A equação:

Euler percebeu uma relação interessante entre a constante e e a trigonometria:

\displaystyle e^{ix}= \cos x + i\sin x

Explicar de onde ele tirou isso está além do escopo desse texto introdutório. A equação mais bonita da história da matemática é somente um caso especial onde x é igual a π.

A descoberta de Euler nos deu uma maneira resumida de trabalhar com cossenos e senos e, por isso mesmo, com equações que lidam com coisas cíclicas, facilitando tremendamente o cálculo diferencial e o cálculo vetorial, já que

\displaystyle\int e^{ix} dx = -ie^{ix} + C

Repare só que \small{-ie^{ix}=-i(\cos x + i\sin x)=-i^2\sin x - i\cos x=\sin x -i\cos x}. Que é exatamente a integração de \cos x + i\sin x. Ao invés de trabalharmos com duas integrações, fazemos só uma e quase que diretamente, já que:

\displaystyle\int e^x dx = e^x + C

No caso do cálculo vetorial, além dos senos e cossenos, o uso de números complexos nos da uma notação matemática mais algébrica para a especificação de um vetor. O valor \Theta em e^{i\Theta} é o ângulo (em relação ao eixo x) de um vetor unitário (tamanho, ou raio, igual a 1). Então r\cdot e^{i\Theta} (onde r dará uma escala para o vetor unitário) pode muito bem expressar um vetor qualquer numa equação!

Exemplos de ocorrência de e em fenômenos:

Tomemos como exemplo um simples circuito resistivo-capacitivo:

330px-RC_switch.svg

A tensão VC, nos terminais do capacitor, pode ser calculada com a equação abaixo:

\displaystyle V_c=V_0(1-e^{-\frac{t}{\tau}})

Onde \tau=RC é chamada constante de tempo. Esse valor é definido como sendo o equivalente ao tempo necessário para o capacitor atingir 63,2% de sua carga. Olhe o gráfico de VC… temos:

345px-Series_RC_capacitor_voltage.svg

Repare que no intervalo entre 0 e τ temos praticamente uma reta. Dai para frente o capacitor está praticamente completamente carregado. Então os valores de RC são escolhidos com base neste valor.

Mas, por enquanto, isso é apenas um detalhe… O importante aqui é o valor e, na equação, não acham?

Além de circuitos elétricos, efeitos térmicos obedecem a mesma regra. Essencialmente a variação térmica de um certo material segue a equação:

\displaystyle \Delta T=T_0e^{-\frac{t}{\tau}}

Onde τ também é uma constante de tempo que depende do material e da resistência da transferência de calor…

Essas potências de e podem ser entendidas como o comportamento natural desses fenômenos, mas, às vezes, usamos e para denotar a característica cíclica ou vetorial da grandeza. É o caso, por exemplo da transformação de Fourier, que falei neste texto:

\displaystyle \hat{f}(\xi)=\displaystyle\int_{-\infty}^{+\infty}f(x)e^{-2\pi ix\xi}dx

A equação acima obtém uma função “em função” da frequência ξ a partir de uma função “em função” do tempo x. A relação disso com senos e cossenos é insinuada pelo valor -2πixξ, no expoente de e. E, não é à toa que transformações de domínio tempo-frequência, e vice-versa, sejam usados na análise de processos, onde o mais comum é usar transformações de Laplace, que, essencialmente, são simplificações da transformação de Fourier:

\displaystyle F(s)=\displaystyle\int_{0}^{+\infty}f(t)e^{-st}dt

Onde s, chamado de “laplaciano”, é uma frequência complexa.

De novo, e está ai… Existem vários exemplos do aparecimento de e na natureza e até mesmo em coisas menos naturais, como finanças, por exemplo!

Entendendo, de vez, o ponto flutuante

Este texto foi motivado tanto pela recente série de artigos que estou postando aqui, na tentativa de mostrar como desenvolver uma aplicação mais “cientificamente correta” para microcontroladores de 8 bits (Atmel ATmega2560, num Arduino), quando pela confusão que continuo vendo por ai com relação ao uso de valores em ponto flutuante.

Já escrevi sobre ponto flutuante por aqui, algumas vezes, e continuarei a insistir no tema… É importante que o leitor entenda, de uma vez por todas, que um valor expressado em ponto flutuante não é um número “real” (no domínio \mathbb{R}), estritamente falando. Ainda: É importante saber que certas operações elementares não seguem as mesmas regras da matemática convencional… Veremos, mais adiante, por exemplo, que adições nem sempre apresentam a propriedade comutativa.

Dividi esse texto em partes onde começo falando da relação entre frações e valores binários, passo pela estrutura da codificação do tipo de ponto flutuante de precisão simples (float) e termino mostrando um código equivalente da instrução FADD (ou, operador ‘+’ envolvendo 2 floats). Há uma observação sobre multiplicação, no final.

Valores binários com frações

A conversão de valores decimais inteiros para binários é velha conhecida de todos nós. É fácil descobrir que 12 pode ser escrito, em binário, como 1100. Mas, e quanto a valores como 0.15625?

Um número no domínio \mathbb{R}, quando expresso na forma literal (ao invés de frações) tem dois componentes separados por um ‘.’ ou uma vírgula: A parte inteira (à esquerda do ponto) e a parte fracionária (à direita). Esse valor pode ser expresso em algarismos isolados multiplicados pela base de numeração, assim como os inteiros. Suponha o valor 11.52. Ele pode ser escrito como:

\displaystyle 11.52=1\cdot10^1+1\cdot10^0+5\cdot10^{-1}+2\cdot10^{-2}

Números binarios com componentes fracionárias podem ser escritos da mesma forma, só que a base será 2.

Qualquer valor com número limitado de algarismos “depois da vírgula” pode ser escrito como um valor inteiro. Em decimal, 0.15625 pode ser escrito como 15625\cdot10^{-5}, por exemplo. Se temos 5 algarismos “depois da vírgula” é como se a deslocássemos 5 posições para a direita, indicando isso no expoente da base multiplicada pelo novo valor.

De novo, em binário é a mesma coisa. É prudente lembrar que, mesmo com aritmética inteira, lidamos com uma quantidade de bits limitada.

A estrutura de codificação de um float:

O tipo float tem 32 bits de tamanho e seus bits são estruturados assim:

Estrtutura de um float.
Estrtutura de um float.

O bit sign diz, é claro, se o valor armazenado é positivo ou negativo (0 é positivo e 1, negativo).

Logo depois temos 8 bits associados ao valor do expoente e da base 2 (explico abaixo).

Os 23 bits seguintes armazenam apenas a parte fracionária do valor binário. Ao invés de tratar as posições desses bits como estão na estrutura do float, gosto de pensar neles como posicionados na parte fracionária, assim:

mantissa

Mais adiante veremos que essa parte fracionária geralmente é adicionada ao valor 1.0 para montar o que é conhecido como “mantissa” ou “significante”. Uma nota para os puristas: Algumas pessoas reclamam do termo “mantissa” porque é usado para expressar o resultado do cálculo de um logarítmo. No entanto, a palavra tem um significado mais amplo: É a parte significativa de um valor.

O conhecimento da estrutura do float é importante porque agora você sabe que:

  1. Não há como representar mais que 24 bits numa mantissa;
  2. A mantissa é sempre positiva. O bit de sinal é que muda o sentido do valor;
  3. Existe um limite de 8 bits para o expoente da base que será multiplicada pela mantissa.

Mais adiante falo sobre o famigerado valor FLT_EPSILON e como ele deve ser usado em comparações entre dois valores float.

Obtendo um número “quebrado” com 23 “casas binárias”:

Para encontrar o valor binário “real” basta multiplicarmos o valor decimal “real” por 2^n., onde n corresponde ao número de bits da parte fracionária. Para 23 bits na fração, por exemplo:

0.5 * (1 << 23) = 0.10000000000000000000000(2)
π * (1 << 23) ≈ 11.00100100001111110110100(2)
0.15625 * (1 << 23) = 0.00101000000000000000000(2)
0.1 * (1 << 23) ≈ 0.00011001100110011001100(2)

Gráficamente coloquei um ponto para separar os 23 bits inferiores do valor inteiro obtido. Mas, não é interessante como esses 23 bits correspondem também à parte fracionária, em binário? É só somar todos os bits das posições n, fazendo 2^n, onde n < 0… Por  exemplo: 0.5=2^{-1}. Realmente o bit setado está na posição -1, não está?

Eis o valor 0.15625, os bits nas posições -3 e -5 estão setados, logo:

\displaystyle 2^{-3}+2^{-5}=\frac{1}{8} + \frac{1}{32}=0.125 + 0.3125=0.15625

Simples, né?

Notação científica

Embora a conversão para valores binários “quebrados” seja simples, nas condificações de ponto flutuante temos apenas o valor fracionário. A parte inteira é omitida, ou menor, é implicita…

Em Física existe uma regra, ou norma, para escrevermos valores chamada notação científica. Todo número deve ser escrito no formato (n+f)\cdot10^e, onde n é um valor inteiro (0<n\leqslant9, ou seja n tem que ter o tamanho de apenas um algarismo e não pode ser zero); f é a parte fracionária e e é a quantidade de vezes que precisaremos deslocar a vírgula para obter o valor original.

O processo de converter um valor qualquer para notação científica chama-se normalização (vem de “colocar na norma”… o que mais seria?). E todo valor que segue essa norma é dito estar normalizado.

Em binário, se usarmos a norma, o valor inteiro terá que ser, necessariamente, igual a 1 (a norma é clara: a parte inteira tem que ser sempre maior que zero e só pode ter um algarismo, portanto…).

Tipos de valores, em ponto flutuante:

Se todo valor binário “quebrado” tem que começar com 1, como é que é codificado 0.0?!

Bem… a norma nos dá a maioria dos números binários codificados num float… Na realidade, temos 3 tipos bem definidos de valores: Os normalizados (que são a maioria), os denormalizados (onde a parte inteira é 0.0) e os que não são números.

Com base na estrutura de um float, a fórmula de conversão de um valor binário para decimal, onde f é o valor decimal resultante, s é o bit de sinal , n é o valor da mantissa (parte inteira e a parte fracionária ‘bbbb…’) e E é o expoente (com base no valor de e, da estrutura acima):

Valores denormalizados, normalizados e "not a number".
Valores denormalizados, normalizados e “not a number”.

Se e=0, temos um valor denormalizado. Isso significa que a mantissa é usada como está e o expoente E será -126. Valores denormalizados são usados para representar números bem pequenos. Esses valores devem ser evitados sempre que possível por dois motivos: O processador penaliza a performance da operação que envolva valores denormalizados, inserindo (no caso da arquitetura Intel) 1 ciclo de máquina extra e, o outro motivo, é que valores denormalizados têm 23 bits de precisão. Um a menos que os valores normalizados (que têm 24: Os 23 da parte fracionária e o valor 1, implícito, da parte inteira).

Existe uma exceção na faixa dos valores denormalizados: Já sabemos que usando valores normalizados não podemos escrever 0.0. Zero é um caso especial, onde n=0e=0. E, por estranho que pareça, existem dois zeros: +0 e -0.

Se tivermos o expoente e entre 1 e 254, temos um valor normalizado. Neste caso, o expoente E é dado pela fórmula E=e-127. É fácil notar que para termos E=0 temos que ter e=127 e que os expoentes mínimo e máximo nesse “fator multiplicativo” está entre -126 e 127.

Um exemplo: o valor 1.0, decimal, pode então ser escrito como:

sinal  expoente  mantissa
0      01111111  00000000000000000000000

O pequeno código abaixo te mostrará isso:

float x = 0.0f;
unsigned int *p = (unsigned int *)&x;

printf("%f -> [%d 0x%02X 0x%07X]\n",
  x, *p >> 31, (*p >> 23) & 0xff, *p & 0x7fffff);

Existe um caso especial, onde e = 255. A mantissa perde o propósito de manter um valor e o número codificado no float passa a ser um não-número. Esse não-número pode ser interpretado como \pm \infty (+inf ou -inf) ou ±NaN. Diferente da aritmética inteira, uma divisão por zero, por exemplo, resulta num NaN ou inf, dependendo do caso. Outro caso é a tentaiva de extrair a raiz quadrada de -1.0, que resulta num NaN, necessariamente.

A diferença entre infinitos e NaN é o conteúdo da mantissa… mantissa zerada nos dá um dos infinitos, mantissa com alguma coisa (qualquer coisa) nos dá NaNs.

Lembre-se que, mesmo na matemática, valores infinitos não são “números”… Assim, somar +1 a -\infty, por exemplo, continuará dando -\infty. Multiplicar +∞ por um número pequenininho, mas válido, continuará dando +\infty (ou -\infty, dependendo do sinal). Da mesma forma, um NaN é um NaN e qualquer operação com um NaN sempre dará um NaN.

Um alerta sobre arredondamentos:

Embora floats tenham precisão de 24 bits para valores normalizados, o processador mantém um 25º bit chamado bit de guarda. Esse bit é usado nas rotinas internas de arredondamento. Para entender como, temos que recorrer ao velho método de arredondamento de valores inteiros…

Se você tem um valor como 1.7 e quer arredondá-lo para um inteiro pode, essencialmente, fazer uma de duas coisas: Ou ignora a parte fracionária (processo chamado de truncamento) ou adiciona 0.5 à parte inteira e depois ignora a parte fracionária do resultado.

O bit extra, escondido, que o processador mantém é usado justamente para manter uma precisão um pouco maior (2^{-24}) e somar esse valor ao resultado de uma operação… O último bit (na posição -23), depois de escalonado por 2^E é chamado de ULP (de Unit in Last Place). Arredondamentos são feito somando o valor de ½ ULP e ignorando o 25º bit do resultado de uma operação aritmética…

O conceito de ULP é diferente de epsilon (letra grega ε). Epsilon é o valor do último bit da mantissa, ou seja, 2^{-23}. O escalonamento por 2^E não é levada em conta… Com isso, o “macete” abaixo não funcionará para valores fora da escala onde E=0:

bool iguais = (fabsf(a - b) >= FLT_EPSILON);

Para ab muito pequenos e com grandezas muito inferiores ao valor de FLT_EPSILON… Outro macete popular é fazer:

float A = fabsf(a), B = fabs(b);
float maior = (B > A) ? B : A;

bool quaseiguais = (fabs(a - b) <= maior * FLT_EPSILON);

Que é um pouco melhor. Ao multiplicarmos o maior valor absoluto por FLT_EPSILON estamos obtendo um valor na grandeza de um ULP (levando em conta o valor do expoente). Assim, se a diferença entre os valores for inferior que esse valor “mínimo”, os valores podem ser considerados “quase” iguais.

Se você precisa comparar dois valores contra a menor exatidão possível, o método correto é obter a escala do maior valor (pode ser obtida via fumção frexpf) e multiplicá-la por FLT_EPSILON para obter o valor de 1 ULP… Parecido com o macete acima:

int e;
float A = fabsf(a), B = fabs(b);
float maior = (B > A) ? B : A;

frexpf(maior, &e);
bool quaseiguais = (fabs(a - b) <= ldexpf(FLT_EPSION, e));

Adição e subtração

Como a mantissa pode ser tratada como se fosse um valor inteiro de 24 bits, bastando adequar o expoente da base 2, as operações elementares podem ser feitas como se esses valores fossem inteiros. Em decimal, 0.5+1.2, por exemplo, pode ser escrito como 5 \cdot 10^{-1} + 12 \cdot 10^{-1}, como temos os mesmos expoentes depois desse ajuste, basta somar os valores inteiros, repetir a potência de 10 e depois normalizar o resultado: 5 \cdot 10^{-1} + 12 \cdot 10^{-1} = 17 \cdot 10^{-1} \rightarrow 1.7 \cdot 10^0.

Existe um detalhe chato: Já que quando tivermos potências diferentes teremos que equalizá-las antes de efetuar a adição (ou subtração) e temos dois valores, qual deles deve ser alterado? Se fizermos isso com o menor valor, precisaremos multiplicá-lo por 2n até que os expoentes sejam iguais. Isso implica em deslocar a mantissa para a direita (aumentando a grandeza do menor valor)… Só que temos apenas 24 bits na mantissa! Os bits inferiores serão perdidos no processo… Do outro lado, se adequarmos o maior valor ao menor manteremos a mesma quantidade de bits na parte fracionária nos dois valores. Assim, sempre devemos adequar o maior dos dois valores.

Outro detalhe: Se na equalização de expoentes o deslocamento necessário for maior que 23 bits, o menor valor pode ser seguramente ignorado, encarado como se fosse 0.0, já que sua significância é inferior a 2^{-23}. Este é o motivo pelo qual as duas operações abaixo dão valores diferentes:

float a = 1e30, b = 1.0f;
float c, d;

c = a + b - a;   // isso é 0.0f
d = a - a + b;   // isso é 1.0f

Ao somar 10^{30} com 1.0 (a + b) temos mais de 23 bits de diferença entre os expoentes de ambos os argumentos, assim, prevalece o maior. No segundo caso teremos a adição de 0.0 (a – a) com 1.0 (b).

Aprendam isso: Em muitos casos a adição (e subtração) não é comutativa! Isso significa que a ordem com que as adições são feitas é importante!

A listagem à seguir mostra um código de emulação da instrução fadd, quase em conformidade com a especificação IEEE 754 (falta o detalhe de arredondamento!) usando tudo o que expliquei acima:

/*
 * fp.c
 *
 * Rotinas que emulam o processo de adição realizado pela
 * ALU do microprocessador. A única coisa que parece estar
 * faltando são as rotinas de arredondamento e o bit
 * de guarda. A rotina funciona para toda a faixa dos floats.
 *
 * ---------------------
 * A estrutura de um float é (do MSB para o LSB):
 *
 * 1 bit: sinal;
 * 8 bits: expoente;
 * 23 bits: mantissa.
 * ---------------------
 */
#include <stdio.h>
#include <stdint.h>

/* Protótipos das rotinas auxiliares.
   _join e _split juntam e separam as partes de um float.
   _fswap troca dois floats de lugar.

   Elas têm o atributo noinline para que fadd() não fique muito
   grande. Assim, o código em assembly, gerado pelo compilador
   poderá ficar um pouco mais compreensível.

   Internamente, o processador separa e junta os componentes de
   um float através de circuitos lógicos. É provável que ele tenha
   "registradores" internos de 23 bits para a parte fracionária,
   registradores de 8 bits para o expoente e um único bit para o sinal.

   _join e _split servem apenas para adequar os tipos acessíveis
   a nós para a emulação. _fswap poderia ser inline...
 */
float _join(int, uint8_t, uint32_t)
  __attribute__((noinline));
void  _split(float, int *, uint8_t *, uint32_t *)
  __attribute__((noinline));
void  _fswap(int *, uint8_t *, uint32_t *,
             int *, uint8_t *, uint32_t *)
  __attribute__((noinline));

/* Rotina que faz a+b, com floats normalizados. */
float fadd(float a, float b)
{
  int sa, sb, sub_flag;
  uint8_t ea, eb;
  short et;         /* NOTA: O expoente temporário precisa de
                             mais que 8 bits. */
  uint32_t ma, mb;
  uint64_t mt;      /* NOTA: mt tem 64 bits de tamanho
                             para permitir o shift para a
                             esquerda. */

  /* Separa os floats em suas partes. */
  _split(a, &sa, &ea, &ma);
  _split(b, &sb, &eb, &mb);

  /* Ordena os valores de forma que 'a' será sempre maior
     que 'b'. */
  if (eb > ea || mb > ma)
    _fswap(&sa, &ea, &ma, &sb, &eb, &mb);

  /* Sinais opostos significa subtração! */
  sub_flag = sa ^ sb;

  /* Trata casos especiais (inf e NaN). */
  if (!ea && !ma) return b; /* FIX: Se a==0, retorna b. */
  if (!eb && !mb) return a; /* FIX: Se b==0, retorna a. */
  if (ea == 255)
  {
    /* Se ambos os valores forem inifinitos com sinais
       opostos, volta 0.0, senão retorna o inifinito com o
       sinal de a. */
    if (ma == 0 && (eb == 255 && mb == 0) && sub_flag)
      return _join(0, 0, 0);
    else
      return _join(sa, 255, 0);

    /* Se um dos valores for NaN, retorna NaN. */
    if (ma || (eb == 255 && mb))
      return _join(sa, 255, ma | mb);
  }

  /* Coloca o bit implícito nas mantissas.
     Faz isso apenas se o expoente não for 0,
     ou seja, se o valor for normalizado. */
  if (ea) ma |= 0x800000;
  if (eb) mb |= 0x800000;

  /* Copia a mantissa e expoente do maior valor
     para variáveis maiores! */
  mt = ma;
  et = ea;

  /* Se os valores têm expoentes diferentes, temos que
     equalizá-los. */
  if (ea != eb)
  {
    int diff;

    /* Calcula a diferença de expoentes.
       Se for muito grande, ignora b. */
    if ((diff = ea - eb) > 24)
      return _join(sa, ea, ma);

    /* Caso contrário, adequa os expoentes, e
       faz p shift de 'a'. */
    mt = (uint64_t)ma << diff;
    et -= diff;

    /* Neste ponto os valores estão com os expoentes
       equalizados. */
  }

  /* Realiza a adição. */
  if (!sub_flag)
  {
    /* Ao adicionar dois valores normalizados, teremos,
       na parte inteira, em binário: 1+1 = 10. O que torna
       necessário o deslocamento de 1 bit para a direita! */
    mt = (mt + mb) >> 1;
    et++;   /* Ajusta expoente. */
  }
  else
    mt -= mb;

  /* Normaliza o resultado. */
  while (mt & 0xff000000)
  {
    mt >>= 1;
    et++;
  }

  /* Se o expoente final é muito grande, retorna Inf ou -Inf.
     Acredito que o expoente jamais será 0 depois da
     normalização. Tenho que testar isso! */
  if (et > 254)
  {
    sa = (et < 0);
    et = 255;
    mt = 0;
  }

  /* Junta o float em suas partes. */
  return _join(sa, et, mt);
}

/* ------------ As rotinas auxiliares ---------------- */
/* Separa um float em suas partes. */
void _split(float x, int *sign, uint8_t *exp,
            uint32_t *mantissa)
{
  uint32_t *p = (uint32_t *)&amp;x;

  *sign = *p >> 31;           /* Pega o sinal. */
  *exp = (*p >> 23) & 0xff;   /* Pega o expoente. */
  *mantissa = *p & 0x7fffff;  /* Pega a fração. */
}

/* Junta as partes de um float. */
float _join(int sign, uint8_t exp, uint32_t mantissa)
{
  float x;
  uint32_t *p = (uint32_t *)&x;

  *p = sign ? 0x80000000 : 0; /* Ajusta sinal. */
  *p |= (uint32_t)exp << 23;  /* Posiciona o expoente. */
  *p |= mantissa & 0x7fffff;  /* Ajusta a fração. */

  return x;
}

/* É a mesma coisa que:
  void _fswap(float *a, float *b)
    { float t=*a; *a=*b; *b=t; }
*/
void  _fswap(int *sa, uint8_t *ea, uint32_t *ma,
             int *sb, uint8_t *eb, uint32_t *mb)
{
  int stmp;
  uint8_t etmp;
  uint32_t mtmp;

  mtmp = *ma;
  etmp = *ea;
  stmp = *sa;
  *ma = *mb;
  *ea = *eb;
  *sa = *sb;
  *mb = mtmp;
  *eb = etmp;
  *sb = stmp;
}

Um aviso: O código acima ainda pode ter erros com relação a valores de-normalizados. Não tive paciência de fazer testes exaustivos. No entanto ele ilustra as complexidades de uma simples adição (ou subtração) de dois valores do tipo float.

Multiplicações e divisões:

Por incrível que pareça, multiplicar e dividir é bem mais simples que somar e subtrair. Isso vem do fato de que podemos multiplicar as mantissas e depois somar os expoentes, seguido de normalização e obteremos o resultado desejado. Na divisão os expoentes são subtraídos… Geralmente essas operações são mais lentas que a adição porque multiplicação e divisão inteira são implementadas em função de adições e subtrações (multiplicação é uma sucessão de adições e divisões é uma sucessão de subtrações). Mesmo que o algoritmo seja bem otimizado ou use algum macete esotérico, os algoritmos ainda usarão adições e subtrações…

Diferente das adições, a exatidão do resultado não está atrelada à precisão do maior valor. O ULP de um valor como 1.0 é de 2^{-23}, mas de 2.0 é 2^{-22}, no entanto, 1.0/2.0 resulta num ULP de 2^{-24}! Neste caso, para esses valores escolhidos, a exatidão do resultado é maior que o de ambos dividendo e divisor. O mesmo pode acontecer com a multiplicação, é claro… Se fizermos 0.5 vezes 0.5 obteremos um valor com ULP menor… Note, a precisão depende da escolha dos valores aqui… Na adição, depende do maior valor.

O que deixei de fora?

Sinto que a coisa mais importante que deixei de fora desse texto foi o cálculo de estabilidade de equações usando ponto flutuante. É um assunto interessante… Mas, é o tipo de análise que exige algum nível de abstração matemática acima da média. Gastaria MUITO tempo e esforço (já reescrevi este artigo umas 5 vezes, por exemplo). Em outra opotunidade mostro como isso deve ser feito… Aconselho a leitura de um dos materiais que considero essenciais, chamado “What every computer scientist should know about floating point”, de David Goldberg, disponível para download aqui. E este livro aqui também é muito bom…

DJ’s não sabem de nada!

Tenho um amigo que se diz DJ só porque tem um amplificador, um pick-up e umas caixas de som boazinhas… e vive de colocar musiquinhas da Xuxa pra criançada se divertir em festinhas de aniversários (as mamães são dessa época – as crianças, é claro, acham uma merda!). Bem… o sujeito faz questão de encher o meu já velho e enrugado saquinho com a ladaínha de que “discos de vinil são melhores que CDs ou esse tal de MP3″… Haja paciência!

Desde o começo dessa briguinha boba, o argumento dos entendidos é sobre a faixa de baixa frequẽncia… é a chamada “loudness wars”. Se vocẽ fizer uma análise espectral de uma música que foi gravada em vinil e a mesma música, num CD, poderá observar uma pequena diferença (se existir alguma!). Especialmente na faixa do infra-som (abaixo dos 20 Hz) – que, aliás, é uma faixa que nós, humanos, não ouvimos de jeito nenhum (mas podemos sentir). Acontece que isso nada tem haver com a maneira como o áudio foi gravado… bem… até tem, o que quero dizer é que não é por causa da “tecnologia digital”…

O que acontece é que, por causa da qualidade superior, os CDs são equalizados de forma diferente do que nas gravações em vinil. Vale aqui explicar o que significa “equalizar”, antes de continuar: A gravação de qualquer mídia (CD o vinil) passa por estágios onde existem perdas no sinal original. Um cantor se esforça para soltar a voz de forma afinada, que é captada por um microfone que, por sua vez, atenua certas frequências e amplifica outras, além de adicionar um pequeno ruído (por ser um transdutor mecânico – transforma a vibração do ar em eletricidade). Do microfone o sinal, já alterado, vai para amplificadores que fazem a mesma coisa: Adicionam ruido, “comem” certas frequẽncias e “melhoram” outras, agora, graças ao seu circuito e à temperatura (os componentes esquentam!)… Dos amplificadores o sinal passa por uma mesa de mixagem… etc… etc… etc… No fim das contas o sinal estará distorcido, em relação ao sinal original. Mas, isso não é o mais importante, porque os técnicos de som compensarão essas perdas e granhos através do processo chamado EQUALIZAÇÂO.

“Equalizar” significa “tornar igual”. Ou seja, aquelas faixas de frequeência que foram perdidas precisam ser amplificadas e as que foram amplificadas precisam ser atenuadas para que o sinal final fique “igual” ao sinal original. Um dos meios de fazer isso é através de um circuito chamado (adivinhem só!): “Equalizador”.

Equalizador Gráfico semi-profissional.
Equalizador Gráfico semi-profissional.

A figura acima mostra um “Equalizador Gráfico” de dois canais (estéreo). Cada potenciômetro amplifica ou atenua uma faixa de frequências. Provavelmente você não conseguirá ler (porque tive que degradar a imagem para caber direito no WordPress), mas a escala horizontal é logarítmica, entre 20 Hz e 20 kHz e cada potenciômetro tem escala, vertical, entre +12 e -12 dB. Valores positivos amplificam a faixa e valores negativos a atenuam. Nos ajustes acima, as frequências inferiores a 60 Hz foram ateunuadas e as na faixa de, digamos, 10 kHz para cima foram amplificadas. Provavelmente para compensar perdas em altas frequẽncias e amplificações do sinal, em baixas.

O equalizador serve para isso! Compensar distorções no sinal, no sentido de tornar a saída IGUAL à forma de onda original!

Tanto do ponto de vista da gravação em estúdio, quando do ponto de vista do ouvinte, o som deve ser equalizado em algum ponto. No caso do ouvinte, deve-se levar em conta não apenas as perdas do sinal causadas pela transformações ocorrida no aparelho de som, mas também em relação ao ambiente onde o som vai ser apreciado… A mesma música pode ser ouvida num headphone, dentro de um carro, em casa, sentado no sofá ou num show ao vivo, em espaços abertos… Cada ambiente desses têm lá suas características de reverberação e interferências. Reverberação é o que ocorre quando uma onda sonora encontra um obstáculo (uma quina da parede, um sofá macio, etc) e, como resultado, deforma algumas frequências da onda original (seja na intensidade ou na “fase”). Interferência é o que acontece quando duas ondas se encontram… Elas podem se anular, atenuar ou amplificar uma à outra… Nesses casos o equalizador também é usado para “equalizar”, sempre no sentido de obter a forma de onda original.

No caso de equalização ambiental o método mais simples é usar um “analizador de espectro de áudio” e alguma fonte de áudio confiável, padronizada. Existem CDs com trilhas contendo frequências e padrões de teste… E também pode-se usar um gerador de “ruido rosa”, que é um método rápido e menos confiável… O “ruído rosa” é um ruido que contém todas as frequências do espectro audível, de maneira aleatória. Usando essas fontes de áudio podemos desenhar um gráfico mostrando quais frequências foram atenuadas e quais foram amplificadas e, “rebater” essas amplitudes no equalizador…

Voltando ao motivo do “loudness wars”: Como a qualidade dos CDs é superior ao do vinil, a industria estipulou padrões de equalização de baixas frequências para gravações em CD que não existiam antes… Fizeram isso por vários motivos: Havia o receio de que, graças a qualidade superior de áudio, sem ruídos e perdas mecânicas, o sinal de baixa frequẽncia poderia causar danos, não apenas ao equipamento eletrônico do usuário, mas danos desastrosos, como “sem querer” obter a frequẽncia de ressonância de certos materiais e causar desabamentos… Hoje, sabemos que isso não é lá muito provável… Suspeito que o motivo principal seja garantir a qualidade de todo o resto do espectro de áudio, melhorando a experiência do ouvinte. Não que sejamos particularmente sensíveis a ruídos de baixa frequência, mas alto-falantes o são, como é o caso dos woofers (aqueles alto-falantes grandões numa caixa de som vintage).

Se você tem ou já teve um daqueles aparelhos de com com caixas de som enormes, e teve a curiosidade de retirar a malha de proteção frontal para ver os alto-falantes, depois de um tempo, deve ter reparado numa película de líquido acumulada na borda desses alto-falantes grandões…. Aquilo ali é água mesmo! O que ocorre é que as bordas desses alto-falantes – que são grandes porque são os responsáveis pelo audio de baixa frequência – vibram menos que o centro. Isso faz com que as bordas vibrem numa frequência próxima da frequẽncia de ressonância das moleculas de água, alterando essas bordas quimicamente, tornando-as mas fracas e, com o tempo, fazendo com que elas rasguem. Os bons woofers têm uma proteçãozinha para evitar isso, mas não os da época em que essas caixas de som gigantes eram comuns. Hoje temos os sub-woofers, responsáveis pelos infra-sons (que, de novo, podemos sentir, mas não ouvir).

Superífie de um disco de vinil, sendo tocado.
Superífie de um disco de vinil, sendo tocado.

Essas restrições de equalização não existiam nas gravações de vinil…

É claro, discos de vinil têm outras desvantagens em relação ao CD: O atrito mecânico é um deles. Graças a isso, você nunca obterá a mesma forma de onda na saída de um alto-falante se tocar o disco duas ou mais vezes… Na figura ao lado você pode observar que a agulha (de quartzo) passa pelo sulco que é bastante irregular. Dá pra imaginar que esse sulco se desgastando toda vez que a agulha passar por ali, não dá?

O vinil funciona assim: O cristal de quartzo é pressionado pelos sulcos que causam uma deformação microscópica no crital, criando uma diferença de potencial (tensão), que será amplificada, de alguma forma, e colocada num ou mais alto-falantes. Na figura ao lado, ao que parece, vemos um daqueles aparelhos de som antigos, monofônicos, já que não temos DUAS agulhas (haveria um rasgo no meio, se fosse o caso!).

Além de não obter a mesma forma de onda toda vez que tocar um disco, pelo desgaste do vinil (e também do cristal de quartzo) devido ao atrito, temos um pequenino aumento de temperatura, que é traduzido em ruído… Além do ruído térmico, temos o ruído do próprio arraste da agulha contra o vinil e, já que o braço de leitura não pode ser rígido, temos também ruído causado por desbalanceamento. Ou seja, uns 20% do áudio de saída é ruído…

Outra desvantagem é relativa aos danos à mídia… Já ouviu um disco arranhado? Pois é…. E olha que eu nem estou falando de tentar ouvir Bolero de Ravel, inteiro, em vinil… que é impossível

Deixemos o meu amigo “DJ” e sua paixão de lado e vamos nos concentrar no que interessa: MPEG-1 Layer III, ou o famigerado MP3.

Num artigo anterior falei que áudio digital normalmente é uma sequência de valores de 16 bits disponibilizados de tal forma que a sequência é enviada para o canal esquerdo e direito, nessa ordem, em intervalos aproximados de 15 μs, entre um par de valores e outro. Ou seja, são 44100 valores colocados na saída a cada segundo. Quando uma quantidade de coisas ocorre em um segundo é costumeiro expressar isso na unidade Hz (Hertz). Assim a frequẽncia de amostragem é de 44.1 kHz. Esse sampling rate continua válido para áudio digital codificado no formato MP3.

Forma de onda decomposta em senoides.
Forma de onda decomposta em senoides.

Acontece que MP3 não armazena os valores das amplitudes das ondas dos canais esquerdo e direito, para cada par de amostra. Ele armazena as variações de um conjunto de frequências do espetro de áudio.

Toda forma de onda pode ser expressa como o somatório de senóides. A figura ao lado mostra uma onda quase quadrada decomposta em diversas senóides com intensidades diferentes. Assim, ao invés de armazenar toda a forma de onda, podemos armazenar apenas as senóides que se sobressaem, quando formam a onda. Isso é feito através de uma manipulação matemática chamada de Transormada de Fourier. É uma “trasformada” porque transforma um conjunto de valores em um domínio (tempo) em outro (frequências).

Na animação ao lado podemos dizer que, para armazenar dois períodos da forma de onda quase quadrada teríamos que armazenar as amplitudes de sabe-se-lá quantas amostras (milhares, talvez). Mas, no domínio da frequẽncia, precisaríamos armazenar, talvez, apenas as 3 primeiras intensidades (ou “quantidades”) de faixas de frequências previamente conhecidas. Isso nos daria uma forma de onda final que se aproxima muito da onda original… Note que milhares de quantidades foram reduzidas apenas a 3. E é assim que o MPEG “comprime” o áudio.

Claro que isso é uma super-simplificação… Os quantizadores (as quantidades que citei acima) não são apenas 3 e eles variam no decorrer do tempo, de acordo com a variação da saída de áudio. Mas, acho que você pegou a idéia… E para aqueles que querem ver algum cálculo, a equação abaixo é usada para obter os quantizadores:

\hat{f}(\xi)=\displaystyle\int_{-\infty}^{+\infty}f(x)e^{-2\pi ix\xi}dx

Do ponto de vista matemárico, ξ é uma frequência em radianos por segundo e x é o tempo em segundos da forma de onda original. A equação pode ser adaptada para frequência em Hz, facilmente e, é claro, os limites inferior e superior da integração não serão infinitos (estarão, provavelmente, na faixa da frequência fundamental desejada ± Δξ, que seria a faixa desejada). Ou seja, para cada faixa de frequências correspondente a um quantizador, podemos escolher um ξ fundamental e obter a “força” do sinal neste ponto. No ato da decodificação tudo o que temos que fazer é inverter a equação:

f(x)=\displaystyle\int_{-\infty}^{+\infty}\hat{f}(\xi)e^{2\pi i\xi x}d\xi

No caso, os limites de integração correspondem às frequências fundamentais atribuídas aos quantizadores… De novo, isso ai é só para dar uma idéia do processo… existem considerações que não falei aqui.

Reparou que, anteriormente, eu disse que precisamos guardar apenas as frequências que “sobressaem”? MP3 é um método que contém perdas no áudio graças a essas transformação e também a outros fatores… Por exemplo: Nossos ouvidos e cérebros estão ajustados para prestar mais atenção nas faixas de frequência perto dos 4 kHz (a frequência da fala e ruídos feitos por outros animais). É uma característica evolutiva. Ao mesmo tempo, frequências altas são ignoradas, bem como frequências muito baixas… E não conseguimos perceber variações rápidas de amplitude (intensidade) sonora, bem como mudanças de amplitude lineares, mas conseguimos perceber bem variações bruscas de frequência. Existem outras características fisiológicas relativas à percepção do som que a turma do MPEG adota no algorítmo de codificação e decodificação de áudio, na hora de selecionar os quantizadores…

Além dos aspectos fisiológicos, temos aspectos psicológicos… certos sons tem a capacidade de nos deixar alegres, tristes, zangados, com medo, etc… Não acredita?! Assista esse vídeo para ver se você sente a mesma emoção que sentiu quando viu o vídeo original, note como a ausência da música de fundo faz toda a diferença! Tudo isso é levado em conta na hora de escolher os quantizadores… quero dizer: Não que o software saiba qual emoção o áudio quer passar, mas certas frequências são inóquas e podem muito bem ser desconsideradas. Assista ao vídeo nesta página para ter uma idéia do que o MP3 deixa de fora (a música do vídeo é, como a página diz, “Tom’s Diner” com Suzanne Vega).

Para garantir precisão nas mudanças de frequência, o MP3 armazena seu conteúdo em pacotes pequenos, chamados de frames. Cada frame é composto de um cabeçalho de 32 bits, contendo informações sobre o bloco de dados que segue esse valor… O bloco de dados pode ter 192 bytes ou 556 bytes de tamanho. Assim, cada frame pode ter de 196 ou 560 bytes de tamanho, que cabe perfeitamente no payload de num pacote TCP ou UDP, por exemplo. O protocolo MPEG é streaming porque cada um desses pacotes é independente e devem ser interpretados sequencialmente. O pacote nº 1 nos dá um pedaço de uma forma de onda, seguido pelo pacote nº 2, etc…

O header (os primeiros 32 bits) de um frame contém a seguinte estrutura:

struct mp3_header {
  unsigned int sync:12;        /* Deve ser 0xfff */
  unsigned int version:1;      /* 1 = MPEG */
  unsigned int layer:2;        /* 01 = Layer III */
  unsigned int error:1;        /* 1 = no error protection. */
  unsigned int bitrate:4;
  unsigned int samplingrate:2; /* 00 = 44100 Hz */
  unsigned int padding:1;
  unsigned int priv:1;
  unsigned int mode:2;         /* 00 = stereo, 01 = joint stereo. */
  unsigned int ex_mode:2;      /* usado pelo joint stereo. */
  unsigned int copywrited:1;
  unsigned int original:1;
  unsigned int emphasis:2;
};

Note os campos bit rate e sampling rate. O primeiro suporta 16 opções possíveis, de 32 kbps até 320 kbps, mas apenas 13 são padronizadas: 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 256 e 320 kbps. Esses bit rates estão disponíveis para sampling rate de 44.1 kHz. É importante não confundir as duas taxas… Bit Rate diz respeito a quantidade de bits que serão transmitidos no stream a cada segundo. Quanto maior o bit rate, maior a quantidade de frames contidas no arquivo MP3 e maior será a quantidade de quantizadores transmitidos, usados para remontar a forma de onda original. O Sampling rate, por sua vez, diz quantas amostras por segundo devem ser enviadas ao conversor digital-analógico, para obtermos a forma de onda no alto-falante…

É por isso que, quando você tem um bit rate baixo, mas um sampling rate ideal (44.1 kHz) o som soa como se tivesse uma qualidade infeior: A forma de onda obtida está longe de ser parecida com a original, porque temos o somatório de menos senóides que a compõe, em cada segundo.

É bom dizer aqui, também, que o bit rate médio de um CD gira em torno de 1.4 Mbps… É só fazer as contas: Se temos 16 bits por amostra e temos duas amostras para cada canal, numa frequência de amostragem de 44100 pares por segundo, temos: 16*2*44100 = 1411200 bits por segundo. Ou seja, 1.4 Mbps… Mas, MP3 não lida com amostras, lembra? Uma taxa de 128 kbps é suficiente para “carregar” quantizadores suficientes para remontar a onda original numa qualidade superior a de um CD, no caso de sons estéreo. Qualquer coisa acima disso te dará um áudio mais fiel ao original, mas a diferença de qualidade não pode ser distinguida por nós…

Como regra geral, costumo usar, em minhas conversões de áudio, o valor padrão de 64 kbps por canal… Isso não te dará um áudio perfeito. Segundo minhas experiências, esse bit rate recorta o áudio em frequências superiores a 17 kHz. Acontece que, quanto mais velho você fica, menor é a capacidade de ouvir frequências altas… Desse jeito, consigo containers de áudio com tamanho pequeno e consigo ouvir muito bem, obrigado… Mas, se você ainda é jovem e adora estourar seus tímpanos, use bit rates maiores: 320 kbps por canal, por exemplo, só recorta frequências superiores a 22.1 kHz, ou seja, ultrasom..

Assim, se tenho um vídeo contendo áudio em 6 canais (Dolby 5.1), uso uma taxa de 384 kbps (64 kbps vezes 6 canais). Infelizmente MP3 não suporta nem mais que dois canais e nem bit rates mais altos que 320 kbps… Para isso existem outros formatos como FLAC (lossless), AAC e AC3 (lossy, mas suportam Dolby e melhor qualidade),

Uma vantagem do MP3 ser um container streaming é que, se você quiser concatenar dois arquivos de áudio em um só, basta fazer:

$ cat audio1.mp3 audio2.mp3 > concatenado.mp3

Claro, isso só pode ser feito se os arquivos audio1.mp3 e audio2.mp3 não contiverem um header ID3.

Opcionalmente, os arquivos MP3 podem ter um header especial de identificação, que possui o nome da trilha, autor e até mesmo uma imagem atachada ao arquivo. Você pode observar os efeitos do ID3 neste grab do nautilus, aqui na minha máquina:

Alguns arquivos MP3 com ID3 contendo figuras.
Alguns arquivos MP3 com ID3 contendo figuras.

Os arquivos MP3 “puros” têm apenas um ícone com duas colcheias… Os arquivos do “Nerdcast” e do “Elo Perdido” (Jurassicast), tem imagens. Se eu clicar com o botão direito e perdir as propriedades dos MP3 do Nerdcast, obterei algumas informações extras… Mas, não terei informações semelhantes do “Bamiga Sector One – Grand Prix Circuit.mp3”, por exemplo.

Vale outra explicação sobre quantizadores aqui: Em vídeo, você pode ter lido em algum lugar que quanto menos, melhor… De fato: No caso de vídeos MPEG, todo quadro é dividido em blocos de 64 cores, ou seja, blocos de 8×8 pixels (e este é o motivo de softwares como o ffmpeg reclamarem se o tamanho do vídeo não for múltiplo de 8!). Cada pixel é uma codificação do somatório da intensidade de três frequência visíveis (Vermelho, verde e azul). Ao invés de codificar todo o bloco, o algorítimo atribui quantizadores para cada bloco, determinando a variação das frequências, de acordo com o quadro anterior. Como temos 64 pixels por bloco, podemos ter de 1 até 64 quantizadores para cada bloco… A quantidade de quantizadores é medida de forma inversamente proporcional a quantidade de pixels. Se tivermos 1 quantizador por pixel, teremos 64 quantizadores por bloco, o que dá uma qualidade excelente, mas uma baixa compresssão… Um valor empírico máximo de quantizadores, para o caso de codificação de vídeo, é de 23 por bloco. Isso nos dá, em teoria, um vídeo com 35% do tamanho que ele teria se armazenássemos os pixels individualmente.

No caso de áudio a coisa é diferente… áudio é uma grandeza típicamnete unidimensional (enquando o vídeo é bidimensional). O que nos força a pensar em quantizadores por n amostras, num intervalo de tempo δt. Isso significa que quanto mais quantizadores, melhor! Mas, não podemos ter tantos quantizadores que não valha a pena usar o envoltório do áudio original, não é?

Minha observação final é quanto ao método de codificação: Não estou bem certo de que transformações de Fourier sejam usadas no algorítmo… De fato, temos outras métodos de obter os quantizadores. A transformada de cossenos discreta é uma delas (DCT). Eu sei que esse método alternativo é usado na codificação de JPEGs e vídeos. Ela é rápida, mas exige que uma matriz seja gravada junto com o vídeo, para ser usada como base para filtragem de frequências… Não é o caso de arquivos MP3. Aparentemente apenas quantizadores são mantidos nos MP3, o que sugere a FFT (Fast Foutier Transform)…

Ahhhh… não tem nenhum código de exemplo aqui, certo? Depois mostro a biblioteca “maluca” (MAD = MPEG Audio Decoder)…

WebServices: XML vs JSON-RPC

RPC é a sigla de Remote Procedure Call, ou seja, “chamada a procedimento remoto”. A coisa funciona mais ou menos assim: De um lado temos um programa tentando fazer uma chamada a uma rotina que não se encontra na própria máquina, mas em outra, diferente. Do outro lado temos um conjunto de funções que podem ser executadas por alguém que têm “assinaturas” pré-definidas.

O lado do chamador “empacota” os parâmetros que vai usar na chamada da rotina remota, envia esse pacote para a outra máquina que desempacota a requisição, a interpreta e só então executa a função correta…. O ato de “empacotar” os parâmetros chama-se Marshalling e o de “desempacotar”, UnMarshalling.

WebServices, no modelo RPC tradicional, chamado SOAP (Simple Object Access Protocol, que de “simples” não tem nada, hoje em dia) usa XML (eXtenssible Markup Language) para publicar um conjunto de “interfaces” que o chamador pode usar. Esse XML é chamado de WSDL (Web Service Definition Language). O chamador usa essa informação para fazer o Marshalling de acordo com o que o “serviço” espera receber…

Se você já mexeu com XML e com Web Services sabe como é trabalhoso lidar com esses detalhes e, provavelmente, deixa isso a cargo de alguma biblioteca pré-empacotada. Especialmente porque os WSDL lidam com XSDs (XML Schema Definitions)… E a coisa só complica mais e mais…

Há tempos tenho observado um esquema de marshalling mais simples, usado especialmente com o AJAX (Assynchonous Javascript And XML). A turma do Javascript resolveu que um objeto pode ser “empacotado” sob forma de uma string simples… Um objeto pode ser empacotado entre os caracteres ‘{‘ e ‘}’, contendo os pares key:value de cada atributo ou membro de dados… Ainda, podemos ter arrays, delineados entre ‘[‘ e ‘]’. Cada “campo” é separado por ‘,’. O nome desse esquema de marshalling é JSON (JavaScript Ohject Notation) e é tremendamente mais simples de se trabalhar do que XML.

Ora, pra quê usar SOAP como RPC se podemos usar JSON? É muito mais simples e o empacotamento fica menor, trafegando mais rapidamente pelos fios… Tudo o que precisamos é de um padrão de marshalling pelo JSON… E ele existe: chama-se JSON-RPC. Funciona assim:

Suponha que você queira chamar uma função, no lado servidor, chamada “calc” e tenha que passar dois valores inteiros. Para isso você só precisa montar a requisição:

{"jsonrpc":"2.0", "method":"calc", "params":[3,4], "id":1}

O primeiro item diz que o JSON-RPC está sendo usado e a versão mais recente (publicada e padronizada) é a “2.0”. Em seguida temos o nome do método que será chamado. Depois, os parâmetros… Neste ponto vale observar que os parãmetros podem ser um número, uma string, um array ou um objeto JSON… E, por fim, um identificador da requisição, que pode ser um número, uma string ou null (sendo que null não deve ser usado, segundo a especificação).

Compare essa requisição com toda a necessidade de namespaces, schemas e a formatação esquisita do XML! É bem mais simples e menor!

Isso não significa que não se possa “embelezar” o pacote JSON:

{
  "jsonrpc":"2.0",
  "method":"calc",
  "params":[1,
            2],
  "id":1
}

Obtida a string JSON que forma a requisição, a enviamos junto com o protocolo HTTP (ou HTTPS):

GET myserver.com/service.py HTTP/1.1
Host: http://myserver.com/
Content-Type: application/json-rpc
Content-Length: 57

{"jsonrpc":"2.0", "method":"calc", "params":[3,4], "id":1}

Obs: O Content-Length está com 57 bytes porque o protocolo HTTP exige que o par “\r\n” termine a última string.

O processador exemplificado aqui como service.py (em Python!) vai simplesmente obter a linha passada por HTTP, e decodificá-la (pode até usar um Javascript para isso!). Depois de processar a chamada, vai reponder com outra linha JSON:

{"jsonrpc":"2.0", "result":7, "id":1}

Da mesma forma, “result” pode ser um número, uma string ou outro objeto JSON. O detalhe é que o “id” é o mesmo que mandamos na requisição, informando ao chamador que essa resposta é para ele (caso tenham sido feitas ‘n’ chamadas por chamadores diferentes no mesmo programa!).

Em caso de erro, a resposta é um pouquinho diferente. Por exemplo:

{"jsonrpc":"2.0", "error":{"code":-32600, "message":"Invalid Request"}, "id":1}

Isso ai vêm como resposta num bloco response do HTTP…

Existem alguns códigos de retorno padronizados e algumas respostas para circunstâncias específicas de erro (veja o padrão aqui).

Convenhamos: Criar um parser para JSON é extremamente mais simples do que um parser para XML… E JSON, pela sua característica, suporta a estrutura de árvore tão bem quanto XML… Ele facilita a nossa vida porque os dados só podem ser de um dos sete tipos:

  • Números Inteiros (long long);
  • Númeoros em ponto-flutuante (double);
  • true ou false;
  • Strings, delimitadas por ” e ” (aceitando sequências de escape no estilo de C);
  • Objetos JSON, delineados entre ‘{‘ e ‘}’;
  • Arrays, delineados por ‘[‘ e ‘]’;
  • null.

Suponha, por exemplo, que vocẽ queira receber como resposta o conteúdo de um arquivo… Basta codificá-lo em BASE-64 e colocá-lo dentro de uma string de um objeto JSON, por exemplo! Ou, melhor ainda, trafegar pedaços (chunks) de um arquivo em um objeto JSON, para não correr o risco de estourar a capacidade de alocação do webserver ou do cliente! As possibilidades são ilimitadas… e bem simples de implementar!!

Cuidado com funções recursivas!!!

Eis um exemplo e uma pergunta: Se cada chamada à função ack() leva ‘n’ microsegundos, quanto tempo você acha que o programa abaixo leva para ser executado?

#include <stdio.h>

/* A função abaixo é claramente recursiva, mas não é uma recursividade 'infinita'!
   Ela claramente tem uma condição de saida e, em cada chamada recursiva, os valores de
   'm' e/ou 'n' são decrementados! */
int ack(int m, int n)
{
  int ans;

  if (m == 0)
    ans = n + 1;
  else if (n == 0)
    ans = ack(m - 1, 1);
  else
    ans = ack(m - 1, ack(m, n - 1));

  return ans;
}

int main(int argc, char **argv)
{
  int i, j;

  /* Tenta listar apenas os 36 primeiros resultados! Só 36! */
  for (i = 0; i &amp;lt. 6; i++)
    for (j = 0; j &amp;lt. 6; j++)
      printf("ack(%d, %d) = %d\n", i, j, ack(i,j));

  return 0;
}

Se você não encontrar uma resposta facilmente, dê uma olhada em Ackermann function e descubra!

Dica: Nem adianta executar e medir o tempo!

Outra pergunta: Dá para transformar a função recursiva ack() em um simples loop “for”, acabando com a recursividade?

The cake is not a lie!

Outra linguagem esotérica (ou “maluca”, em minha opinião) é Chef (eis um “Hello world”):

Hello World Souffle.

Ingredients.
72 g haricot beans
101 eggs
108 g lard
111 cups oil
32 zucchinis
119 ml water
114 g red salmon
100 g dijon mustard
33 potatoes

Method.
Put potatoes into the mixing bowl.
Put dijon mustard into the mixing bowl.
Put lard into the mixing bowl.
Put red salmon into the mixing bowl.
Put oil into the mixing bowl.
Put water into the mixing bowl.
Put zucchinis into the mixing bowl.
Put oil into the mixing bowl.
Put lard into the mixing bowl.
Put lard into the mixing bowl.
Put eggs into the mixing bowl.
Put haricot beans into the mixing bowl.
Liquefy contents of the mixing bowl.
Pour contents of the mixing bowl into the baking dish.

Serves 1.
See?! It’s not a lie!

E, aliás, se quiser fazer um, eis a receita