Indo a extremos para evitar usar ponto flutuante. Você deveria fazer isso também!

Eis um problema que preciso resolver para o meu mais novo projeto de brinquedo: Preciso determinar se uma imagem (stream de vídeo) tem aspecto mais próximo do aspect ratio \frac{4}{3} ou do \frac{16}{9}. A solução mais “simples” é simplesmente dividir o comprimento (width) pela altura (height) e comparar o resultado com uma fração de ‘meio termo”. O “meio termo”, é claro, é a média aritmética simples dos dois aspectos:

\displaystyle \frac{\frac{16}{9} + \frac{4}{3}}{2}=\frac{16+12}{9}\cdot\frac{1}{2}=\frac{28}{18}=\frac{14}{9}

Por que a fração de “meio termo”? É que o vídeo pode ter resolução não padronizada e, neste caso, colocarei “barras pretas” horizontais ou verticais, dependendo do aspecto. Assim, temos:

int is_letterbox(unsigned int width, unsigned int height)
{
  double ratio = ( double )width / height;

  return ratio <= 14.0 / 9.0;
}

Nada mais simples, né? Se o aspecto for menor ou igual a \frac{14}{9}, então encaro o vídeo como candidato para ser convertido para letterbox, ao invés de widescreen. Ahhh… sim… note que o operador de comparação (<=) tem menor precedência que o de divisão (/)… Por isso a expressão intera faz o que queremos!

O problema é que nem a divisão de \frac{width}{height}, nem a divisão \frac{14}{9} são exatas. Bem… a primeira até pode resultar num valor exato, mas o quociente constante de \frac{14}{9} não! Isso poderia causar um “falso positivo” no caso de teste por “menor que” e um “falso negativo” no caso do teste de igualdade… Mas, aqui temos um outro problema: Imagine que o vídeo tenha resolução de 1400×901. Isso dará um aspecto de \frac{1400}{901}, necessariamente, que é muito próximo de \frac{14}{9}.

Falei “necessariamente” porque para obter a manor fração possível podemos usar o “máximo divisor comum” para fazer a divisão do dividendo e divisor (inteiras), obtendo os menores valores. Por exemplo:

#include <stdio.h>
#include <stdlib.h>

static unsigned int gcd( unsigned int, unsigned int );

int main( int argc, char *argv[] )
{
  unsigned int w, h, d;

  if ( argc != 3 )
  {
    fputs( "ERROR\n", stderr );
    return EXIT_FAILURE;
  }

  w = atoi( argv[1] );
  h = atoi( argv[2] );

  d = gcd( w, h );

  printf( "%u/%u -> %u/%u\n",
          w, h, w / d, h / d );

  return EXIT_SUCCESS;
}

unsigned int gcd( unsigned int a, unsigned int b )
{
  unsigned int t;

  if ( a < b )
  {
    t = a;
    a = b;
    b = t;
  }

  if ( ! b )
    return 1;

  while ( b )
  {
    t = b;
    b = a % b;
    a = t;
  }

  return a;
}

Compilando e testando:

$ cc -o test test.c
$ ./test 1280 720
1280/720 -> 16/9
$ ./test 1400 901
1400/901 -> 1400/901
$ ./test 1400 920
1400/920 -> 35/23

Se formos comparar o numerador e o denominador isoladamente a coisa vai complicar um bocado. Note que mesmo numa resolução maluca diferente (1400×920) o aspecto ainda tem o dividendo e divisor bem diferentes (\frac{35}{23}).

De volta ao ensino fundamental:

Como sabemos que, por exemplo, \frac{2}{3} é maior que \frac{3}{5}? A solução que você aprendeu lá no ensino fundamental é converter ambas as frações ao mesmo denominador. Daí podemos comparar diretamente os numeradores, certo? Basta multiplicar ambos o numerador e o denominador de ambas as frações pelo denominador da outra fração:

\displaystyle\frac{2}{3}\,\texttt{e}\,\frac{3}{5}\rightarrow\frac{2\cdot5}{3\cdot5}\,\texttt{e}\,\frac{3\cdot3}{5\cdot3}\rightarrow\frac{10}{15}\,\texttt{e}\,\frac{9}{15}

Agora, com ambas as frações “normalizadas”, podemos comparar diretamente os numeradores. No caso, 10 é maior que 9 e, por isso, \frac{2}{3} é maior que \frac{3}{5}

Vocẽ reparou que não precisamos mais nos preocupar com os denominadores se simplesmente multiplicarmos um numerador pelo denominador da outra fração, né? Isso facilita um bocado a nossa rotina is_letterbox(), evitando o uso de ponto flutuante:

int is_letterbox( unsigned int width, unsigned int height )
{
  unsigned int n1, n2;

  /* Não precisamos calcular os denominadores! */
  n1 = width * 9;   // 9 de 14/9
  n2 = 14 * height; // height de width/height

  return n1 <= n2;
}

Comparando as duas rotinas:

Compilando com otimizações e gerando o código em assembly:

$ cc -O2 -mtune=native -S -masm=intel test.c

Olhem só isso, com ambos os códigos lado a lado:

is_letterbox_fp:                  is_letterbox_int:      
  mov edi, edi                      imul  esi, esi, 14
  mov esi, esi                      lea eax, [rdi+rdi*8]
  pxor  xmm0, xmm0                  cmp eax, esi
  xor eax, eax                      setbe al
  pxor  xmm1, xmm1                  movzx eax, al
  cvtsi2sdq xmm0, rdi               ret
  cvtsi2sdq xmm1, rsi
  divsd xmm0, xmm1
  movsd xmm1, [rip+.LC0]
  ucomisd xmm1, xmm0
  setnb al
  ret

.LC0:
  dq 14.0 / 9.0  ; funciona no NASM.

Pra começar, a segunda rotina não tem divisões (que são LERDAS!). Ainda, a segunda rotina, além de ser menor, é melhor otimizada pelo processador (fusões, reordenações, etc). Outra vantagem é que, na primeira rotina, se height for zero, ela nos causará problemas porque a divisão resultará em NaN, que sempre retornará falso na comparação em ponto flutuante! Mais uma: A comparação, na segunda rotina, é sempre exata!

O único problema da segunda rotina poderia ser o caso de ocorrência de overflows, mas, como as resoluções gráficas que usaremos não resultam em frações com componentes muito grandes (pelo menos, não o suficiente para, quando multiplicados por 9 e 14 causem overflows), então a rotina é bem segura. Se, mesmo assim, você quer evitar a possibilidade de overflows, mude os tipos de n1 e n2 para unsigned long int ou unsigned long long. É prudente colocar um ‘UL‘ depois das constantes ou fazer um casting das variáveis nas multiplicações:

;  int is_letterbox( unsigned int width, 
;                    unsigned int height )
;  {
;    unsigned long n1, n2;
;  
;    n1 = width * 9UL;
;    n2 = 14UL * height;
;  
;    return n1 <= n2;
;  }
is_letterbox:
  mov esi, esi         ; Apenas para zeras os 32 bits
  mov edi, edi         ; superiores dos argumentos.

  lea rax, [rsi*8]     ; RAX = height*8
  lea rdx, [rdi+rdi*8] ; RDX = width*9
  sub rax, rsi         ; RAX = height*7
  add rax, rax         ; RAX = height*14

  cmp rdx, rax
  setbe al
  movzx eax, al
  ret

Mesmo assim o código ainda é melhor que o equivalente em ponto flutuante.

Siga o conselho do Tio Fred: Fuja de ponto flutuante sempre que puder.