Um puzzle difícil…

Esse eu vi, já tem um tempo, no famoso URI Online Judge (aqui). Trata-se de um padrão em espiral, como mostrado na figura abaixo (sempre começando em 1 na linha 1 e coluna 1), no entanto, o tamanho do quadrado pode ser qualquer um até um limite de 2^{32}-1 quadrados por linha (e, obviamente, colunas também!), ou seja, podemos ter \left(2^{32}-1\right)^2 quadrados. Só pra você ter uma ideia, isso dá 18446744065119617025 quadrados e, se cada quadrado contiver um long long teremos um grande array de 147573952520956936200 bytes (131071 PiB!)… mais que seu HD e/ou seu processador podem lidar.

Exemplo da montagem do “quadrado”.

Então, o problema é: Dado um valor qualquer dentro do quadrado, localizar a linha e a coluna onde ele se encontra.

Obviamente que soluções que montam um array bidimensional não funciona e mesmo que ele caiba na memória e/ou disco, percorrê-lo sequencialmente pode levar muito tempo (por exemplo, se temos um máximo de 18446744065119617025 posições e gastamos 1 ns para comparar cada uma (que é um tempo bem otimista), no caso mais extremo gastaríamos 18446744 segundos ou cerca de 213 dias, pouco mais de 7 meses!

Assim, outra restrição do problema é que se o seu programa não puder resolvê-lo em alguns milissegundos, você falhou!

Dados de entrada:

  1. Lado do quadrado (unidade em “posições”), com limite de até 2^{32}-1;
  2. O valor a ser encontrado

Resposta: “Valor n está na linha L, coluna C“.

Obviamente que você terá que verificar se o valor n encontra-se no quadrado…

Boa sorte!

Anúncios

free() automático no GCC

Uma das coisas que os amantes de C++ e de linguagens gerenciadas mais gostam é a “limpeza automática” que códigos escritos nessas linguagens parecem fazer. No caso de C++, objetos alocados na pilha são “destruídos” quando há perda do escopo da função. No caso de C# e Java, por exemplo, quando o objeto não é referenciado por nenhum outro, o Garbage Collector tende a livrar-se dele. Em C, aparentemente, não temos esse benefício:

void f( void )
{
  char *bufferp;
  ...

  bufferp = malloc( SIZE );
  ...
  // MEMORY LEAK: O buffer alocado não foi liberado!
}

Nada tema! GCC tem a solução!

Existe um atributo para variáveis que pode ser usado para fazer esse tipo de liberação automática. Tudo o que temos que fazer é criar a função de liberação a atrelá-la à variável:

#define AUTOFREE \
  __attribute__(( cleanup( cleanup_func ) ))

void cleanup_func( void **p ) { free( *p ) }

void f( void )
{
  AUTOFREE char *bufferp;
  ...

  bufferp = malloc( SIZE );
  ...
  // O memory leak sumiu!
}

Graças a esse atributo, a função cleanup_func é chamada, com o argumento correto, sempre que a variável sai do escopo. Isso significa que não só quando a função termina, mas em casos como esse:

void f( void )
{
  ...
  {
    AUTOFREE char *bufferp;

    bufferp = malloc( SIZE );
    ...
    // bufferp é liberado aqui, AUTOMATICAMENTE!
  }
  ...
}

Para não ter que ficar codificando uma função de cleanup (que sempre recebe um ponteiro para um ponteiro), podemos usar a glib e a macro g_autofree:

g_autofree char *bufferp;

É claro, é prudente inicializar o ponteiro com NULL para o caso de nenhuma alocação ter sido feita… A especificação da linguagem C, ISO 9989, nos diz que se passarmos NULL para free, este simplesmente não faz nada (não causa segmentation fault).

ATENÇÃO! O atributo exige que o tipo informado seja um ponteiro para o ponteiro do mesmo tipo. No entanto, (void **) apontará para qualquer tipo e não haverá problema algum, mas o compilador emitirá avisos…

Outro puzzle….

Achar o erro nesse requer algum conhecimento da especificação de C/C++…
O programinha abaixo fica em loop infinito e jamais imprimirá o resultado. Por quê?

#include <stdio.h>

// Conta a quantidado de bits num inteiro.
int no_of_bits ( int n )
{
  int count = 0;

  while ( n )
  {
    if ( n & 1 ) ++count;
    n >>= 1;
  }

  return count;
}

void test ( int n )
{
  printf ( "there are %d 1's in 0x%x\n", 
    no_of_bits ( n ), n );
}

void main( void )
{
  test ( 0xffffffff );
}

Medindo a qualidade de um vídeo

Além do bitrate, existe outra quantidade de pode ser usada para determinar a qualidade do vídeo: quantizadores.

Para entender os quantizadores precisamos entender como o codec h264 funciona (este é o que eu mais uso)… Cada quadro do vídeo modifica um pedaço do quadro anterior. Na imagem abaixo temos um analisador de vídeo comercial mostrando blocos de um quadro que foram modificados:

A área do vídeo é dividida em blocos de 4×4 até 16×16 pixels. Cada um desses blocos pode ser agrupado em áreas quadradas (como mostrada acima). No exemplos, apenas 2 sub-blocos de um grande blocão foram modificados… Cada sub-bloco passa por uma transformação no domínio da frequência muito parecido com o a Transformação de Fourrier (veja aqui – é sobre áudio, mas a parte sobre Fourier também serve para vídeo), chamada DCT (Discrete Cossine Transform), onde um fator numérico é escolhido para indicar a “quantidade” de modificação do sub-bloco transformado (veja sobre Quantização aqui).

A DCT é uma matriz que contém valores correspondentes à distribuição dos pixels em um subbloco. A figura abaixo mostra a distribuição de frequência (X e Y) dos pixels num bloco 8×8:

A figura não tem valores numéricos, mas considere a distribuição como valores entre 0 e 1: 0 sendo a menor frequência (o quadro branco) e 1 o de maior frequência (pixels distribuídos igualmente na matrix 8×8, no canto inferior direito). As áreas mais escuras são pixels não afetados… Bem a coisa é mais complicada que isso, é claro, mas a matriz DCT e o quantizador são usados para remontar um sub-bloco…

No ffmpeg o fator q pode ser entendido como a quantidade de pixels associada a cada uma dessas quantidades. Se q=1 então temos 1 quantizador para um único pixel e, em teoria, muito pouca compressão, mas altíssima qualidade… Um valor empírico máximo para q está em torno de 28 pixels. O valor máximo de 23 pixels por quantizador, empírico, ainda proporciona excelente qualidade. Quanto menos pixels por quantizadores, melhor a qualidade, mas pior a compressão e vice-versa.

Outra estratégia de compressão é a gravação de frames I (Integrais), P (Progressivos) e B (Intermediários)… Os frames P são a diferença do frame atual e o anterior (outro P ou I). Os frames B são diferenças ainda menores e os I são o frame completo. Um vídeo pode conter, no stream, os streams codificados, por exemplo, como IBBPBBPBBPBBI… Os frames I são maiores que os P e estes, maiores que os B. Falo desses frames porque não podemos avaliar a média geral do fator q, mas sim em relação a esses frames…

Vejamos o relatório do ffmpeg para a conversão de um filme de 42 minutos (repare as linhas que marquei de vermelho):

frame=60833 fps= 54 q=-1.0 Lsize=  632155kB time=00:42:17.21 bitrate=2041.1kbits/s    
[libx264 @ 0x1132c00] frame I:834   Avg QP:13.89  size: 60726
[libx264 @ 0x1132c00] frame P:17436 Avg QP:16.35  size: 18645
[libx264 @ 0x1132c00] frame B:42563 Avg QP:18.61  size:  5388
[libx264 @ 0x1132c00] consecutive B-frames:  2.2% 12.8%  2.4% 82.6%
[libx264 @ 0x1132c00] mb I  I16..4: 10.1% 77.6% 12.3%
[libx264 @ 0x1132c00] mb P  I16..4:  5.3% 16.1%  1.2%  P16..4: 41.3% 14.9%  6.4%  0.0%  0.0%    skip:14.8%
[libx264 @ 0x1132c00] mb B  I16..4:  0.6%  1.2%  0.1%  B16..8: 38.7%  4.3%  0.5%  direct: 4.4%  skip:50.2%  L0:45.8% L1:49.9% BI: 4.3%
[libx264 @ 0x1132c00] 8x8 transform intra:71.2% inter:81.3%
[libx264 @ 0x1132c00] coded y,uvDC,uvAC intra: 43.5% 70.5% 36.4% inter: 13.1% 23.3% 1.2%
[libx264 @ 0x1132c00] i16 v,h,dc,p: 38% 21% 15% 25%
[libx264 @ 0x1132c00] i8 v,h,dc,ddl,ddr,vr,hd,vl,hu: 20% 16% 34%  5%  6%  5%  5%  5%  5%
[libx264 @ 0x1132c00] i4 v,h,dc,ddl,ddr,vr,hd,vl,hu: 28% 20% 21%  5%  8%  6%  6%  4%  3%
[libx264 @ 0x1132c00] i8c dc,h,v,p: 57% 19% 19%  5%
[libx264 @ 0x1132c00] Weighted P-Frames: Y:3.0% UV:1.6%
[libx264 @ 0x1132c00] ref P L0: 64.5%  6.9% 19.8%  8.6%  0.2%
[libx264 @ 0x1132c00] ref B L0: 86.1% 11.1%  2.8%
[libx264 @ 0x1132c00] ref B L1: 96.6%  3.4%
[libx264 @ 0x1132c00] kb/s:1907.81

Aqui, temos 834 frames integrais com uma média de 13.89 pixels/quantizador. Os frames P e B tiveram uma degradação para, respectivamente, 16.35 e 18.61 (de novo, em média!). Mas, todos esses valores encontram-se abaixo de 23, que, empiricamente, é um excelente valor máximo.

Note que consegui um bitrate médio de 1907.81 kb/s, mesmo instruindo o ffmpeg a usar o máximo de 2 Mb/s….

Uma outra maneira de codificar um arquivo de vídeo, especialmente no codec h264, é mudando os limites do escalonamento dos quantizadores, usando as opções -qmin e -qmax, ao invés de -minrate e -maxrate. Isso vai meio que garantir a boa qualidade do vídeo (em relação ao vídeo original!), mas o bitrate sai do seu controle. O arquivo final pode, para garantir a máxima quantidade de quantizadores, subir o bitrate para níveis astronômicos que nem todo device está pronto para lidar. Na prática o ffmpeg não costuma passar muito além do bitrate do vídeo original.

Eis o relatório final do ffmpeg na compressão do mesmo vídeo, mas ao invés de usar um bitrate máximo de 2 Mb/s, usei qmax=23:

frame=60833 fps= 51 q=-1.0 Lsize=  826222kB time=00:42:17.21 bitrate=2667.7kbits/s    
[libx264 @ 0x15ddc40] frame I:834   Avg QP:12.15  size: 71139
[libx264 @ 0x15ddc40] frame P:17436 Avg QP:14.91  size: 23733
[libx264 @ 0x15ddc40] frame B:42563 Avg QP:16.92  size:  7769
[libx264 @ 0x15ddc40] consecutive B-frames:  2.2% 12.8%  2.4% 82.6%
[libx264 @ 0x15ddc40] mb I  I16..4:  8.2% 78.3% 13.4%
[libx264 @ 0x15ddc40] mb P  I16..4:  4.5% 17.5%  1.9%  P16..4: 38.9% 18.0%  6.9%  0.0%  0.0%    skip:12.2%
[libx264 @ 0x15ddc40] mb B  I16..4:  0.7%  1.7%  0.1%  B16..8: 39.7%  6.6%  0.9%  direct: 6.5%  skip:43.8%  L0:46.1% L1:47.4% BI: 6.6%
[libx264 @ 0x15ddc40] 8x8 transform intra:72.8% inter:77.3%
[libx264 @ 0x15ddc40] coded y,uvDC,uvAC intra: 50.6% 75.7% 46.3% inter: 16.9% 27.7% 2.3%
[libx264 @ 0x15ddc40] i16 v,h,dc,p: 38% 20% 17% 26%
[libx264 @ 0x15ddc40] i8 v,h,dc,ddl,ddr,vr,hd,vl,hu: 19% 16% 32%  5%  6%  6%  6%  5%  5%
[libx264 @ 0x15ddc40] i4 v,h,dc,ddl,ddr,vr,hd,vl,hu: 29% 20% 21%  5%  7%  6%  5%  4%  3%
[libx264 @ 0x15ddc40] i8c dc,h,v,p: 56% 19% 19%  6%
[libx264 @ 0x15ddc40] Weighted P-Frames: Y:3.0% UV:1.6%
[libx264 @ 0x15ddc40] ref P L0: 63.7%  6.8% 20.3%  8.9%  0.2%
[libx264 @ 0x15ddc40] ref B L0: 85.4% 11.7%  2.9%
[libx264 @ 0x15ddc40] ref B L1: 96.8%  3.2%
[libx264 @ 0x15ddc40] kb/s:2534.40

Em primeiro lugar, tivemos uma degradação do fator q menor para todos os frames (mais importante: para os frames P e B), mas obtivemos um bitrate médio mais alto (2534 kb/s) e o arquivo ficou 30% maior (note, também, que em média o tamanho dos frames ficou maior). Isso é natural já que temos menos pixels por quantizador…

Temos mais uma estratégia de compressão: Ao invés de lidar com pixels no formato RGB, os streams de vídeo lidam com YUV (Y = luminância e U-V crominância – ou seja, Y dá a intensidade do pixel e U-V a cor). Mas, deixo essa discussão para outra oportunidade…

Tamanho versus qualidade

Assim, quando codificar um vídeo você tem algumas escolhas:

  1. Ou estipula um bitrate máximo, mas perde um pouco da qualidade que provavelmente não é perceptível;
  2. Ou estipula um fator q máximo, em torno de 23 ou menos, que faz com que o arquivo aumente (junto com o bitrate).

Note que estou falando de valores máximos aqui. Podemos estipular falores fixos (mais ou menos). Por exemplo, podemos querer codificar um vídeo para que tenha um bitrate mais ou menos fixo de 2 Mb/s. Para isso temos que especificar -minrate e -maxrate (e, por segurança, -b:v) com os mesmos valores de 2000k. Ou podemos especificar a quantidade fixa do fator q através de -qmin e -qmax. Em ambos os casos o arquivo poderá ficar enorme, mas fixar o fator q é a maneira garantida de ocupar muito espaço em disco e fazer com que seu stream de vídeo demore mais para ser transmitido.

Obedecer a especificação empírica que citei no artigo anterior mais ou menos garante um bom balanceamento entre tamanho e qualidade.

Bitrates para conversão de vídeos

Já falei sobre isso aqui. Diversas vezes, mas quero compartilhar com vocês as taxas de bitrate onde obtenho excelentes resultados.

Bitrate é a taxa de transferência de dados do vídeo para o dispositivo que vai “tocá-lo”. Tem alguma relação entre o sample rate e o tamanho final do arquivo e a qualidade do mesmo. Quando menor o bitrate, pior o arquivo fica (embora fique menor). Acontece que usar bitrates muito grandes não melhora, necessariamente, a qualidade e só faz seu arquivo ficar gigantesco…. O Youtube, por exemplo, recomenda as seguintes taxas:

Eu prefiro vídeos no formato 720p porque tenho um problema de visão… a qualidade de um vídeo 1080p ou 2160p não é assim tão perceptível para mim e, acredito, para a maioria das pessoas também. Mas, note, 5 Mb/s (Mega bits por segundo) e até mesmo 7.5 Mb/s me parecem um exagero. Se você usar metade dessa taxa conseguirá resultados muito bons. Por isso, converto meus vídeos com as seguintes opções do ffmpeg:

-maxrate 2000k -bufsize 2000k -b:v 2000k

Isso me dá um bitrate máximo de 2 Mb/s, em 720p, para o stream de vídeo. Também uso o codec h264 com a opção -c:v libx264.

Mas, e quanto ao áudio? De novo, usar uma taxa de 384 kb/s para um áudio stereo me parece exagero… Como regra geral, uso 64 kb/s para cada canal de áudio… Se for stereo, 128 kb/s. Se for Dolby 5.1, sendo 6 canais, 384 kb/s. Isso tem duas vantagens: O áudio fica pequeno, não há grandes perdas de qualidade e, para alguém com ouvidos sensíveis, um pedacinho da faixa de alta frequência é ceifada… Isso normalmente já ocorre, especialmente em áudios codificados no codec MP3 (embora eu use AC3 – que é um pouco melhor):

-c:a ac3 -b:a 128k -ac 2

Ou seja, meus vídeos em HD (mesmo em 1080p) são sempre convertidos com a seguinte linha de comando:

$ ffmpeg -i videoin.mkv -c:v libx264 -maxrate 2000k -bufsize 2000k -b:v 2000k -s hd720 \
                        -c:a ac3 -b:a 128k -ac 2 \
            videoout.mp4

No exemplo, o vídeo videoin.mkv será convertido com o bitrate de 2 Mb/s, no formato 1280×720 usando o codec h264 e o áudio, em 128 kb/s, stereo (fazendo downsampling se for Dolby) com bitrate de 128 kb/s – e o resultado será colocado num arquivo (container) mpeg4 – pode ser um matroska mesmo, se você quiser. A conversão respeitará o aspect ratio do vídeo original.

Uma alternativa ao codec de áudio AC3 é o AAC, que é preferido pelo Youtube e vídeos que você baixa via torrents… No caso do ffmpeg use a opção -strict experimental para usá-lo, se quiser, já que o ffmpeg não o implementa com precisão “em produção”, ou o codec libfdk_aac, se seu ffmpeg tiver sido compilado para suportá-lo… Mas, recomendo o AAC padrão, mesmo que experimental – se precisar que o áudio esteja codificado dessa forma, caso contrário, AC3.

Existe também o EAC3, mas ele não é suportado por muitos devices

strncpy, strncat (e snprintf) versus strlcpy e strlcat…

Well… ultimamente tenho mexido, profissionalmente, com alguns códigos de terceiros feitos para lidam com banco de dados via OCI (Oracle Call Interface). Algumas coisas me chamam a atenção:

  1. A não ser quando lidamos com o tipo externo SQLT_STR no mapeamento de binds e definições de campos de statements, a OCI não lida com strings do tipo ASCIIZ;
  2. O tamanho do buffer, incluindo o ‘\0’ final, no caso de SQLT_STR precisa ser informado para as funções da OCI.

Essas duas restrições torna obrigatório que as strings tenham um tamanho máximo bem definido. Se um campo NOME é definido como VARCHAR2(100), então o buffer, mapeado para SQLT_STR deve ter 101 bytes de tamanho para acomodar o ‘\0’. Mas, o que acontece se um ponteiro apontar para uma string com mais de 100 caracteres (excluindo o ‘\0’)?

Para evitar esse problema podemos lançar mão das funções strncpy() e strncat(). Só que existe uma pegadinha: strncpy() copia n bytes para o destino e só coloca o ‘\0’ final se houver espaço para isso. Algo como:

char d[10];
char *s = "Frederico Lamberti Pissarra";
...
strncat( d, s, sizeof d );

Fará com que o buffer d contenha a sequência “Frederico ” sem o ‘\0’ final!

A coisa piora para strncat(), se precisarmos fazer uma concatenação com tamanho fixo… Essa rotina copia n bytes, no máximo, além do tamanho original da string no buffer destino. O efeito é o mesmo acima, se fizermos:

char d[10] = "Fred";
...
strncat( d, "erico Lamberti Pissarra", 6 );

Note que o n de strcat() não significa o tamanho total do buffer, mas a quantidade máxima que será copiada para o buffer.

Aliás, funções como snprintf() sofrem do mesmo mal de strncpy… Se não tem espaço para o ‘\0’, ele simplesmente não é escrito no buffer.

FreeBSD

No FreeBSD (até onde sei) as funções strlcpy() e strlcat() foram adicionadas para considerar o tamanho máximo do buffer destino. O ‘l’ vem de length. Ou seja, no primeiro caso, strlcpy(), copiará n caracteres incluindo o ‘\0’ final. No segundo, strncat, também fará o mesmo, mas o tamanho a ser considerado é o do buffer final.

A primeira função é simples de implementar, se ela não for nativamente suportada pela libc (não estiver presente no header string.h):

#ifndef __FreeBSD__
char *strlcpy( char * restrict dest,
               char * restrict src,
               size_t n )
{
  if ( n > 1 )
  {
    --n;
    memcpy( dest, src, n );
    dest[n] = '\0';
  }
}
#endif

Repare que fiz uma pequena otimização, onde a cópia é feita apenas se n for maior que 1 byte.

Outro detalhe é que, possivelmente, usar memcpy() será mais rápido do que usar strncpy(). A primeira tende, em algumas arquiteturas, a usar instruções especializadas de cópia de blocos, enquanto a segunda, tende a copia byte por byte (Este é o motivo, em algumas análises, porque strlcpy tende a ser bem mais rápido que strncpy).

strlcat() precisa saber o tamanho da string original antes de fazermos a cópia:

#ifndef __FreeBSD__
char *strlcat( char * restrict dest, 
               char * restrict src, 
               size_t n )
{
  size_t size = strlen( dest );

  // Temos que considere o '\0' final!
  if ( size < n )
    strlcpy( dest + size, src, n - size );

  return dest;
}
#endif

O esquisito formato de Data/Hora do Oracle

Estou brincando com a OCI (Oracle Call Interface) para um projeto grande no meu “trampo”. Eis que topo com o tipo DATE que, parece, é simples. São apenas 7 bytes contendo, na sequência, o “século”, o “ano”, “mês”, “dia”, “hora”, “minutos” e “segundos”; e tudo obtido via o tipo “externo” SQLT_DAT… Bem… parece ser simples, mas a Oracle tinha que fazer suas “oraclices”.

Pra quê diabos eu quero obter a estrutura DATE ao invés de uma simples string do tipo “DD/MM/YYYY HH:MI:SS”? Ora bolas: Eu não gosto de mexer com strings, prefiro os dados inteiros! Isso ai gasta bem mais que 7 bytes, para começo de conversa, e precisa ser manipulado se eu quiser lidar com diferença entre datas/horas. É claro que eu podedia retornar uma string formatada como “YYYYMMDDHHMISS” e interpretá-la como um número inteiro, mas com 14 algarismos isso gastará 8 bytes (um dword ou uint64_t)…

A definição do campo não podedia ser mais simples, para um statement do tipo “SELECT SYSDATE FROM DUAL“:

char oradate[7];
int16_t oradate_ind;
OCIDefine *defp = NULL;
...
OCIDefineByPos(
  stmthp,
  &defp,
  errhp,
  1,
  oradate, sizeof oradate,
  SQLT_DAT,
  &oradate_ind,
  NULL, NULL,
  OCI_DEFAULT );

Acontece que, para que um ano caiba em um byte a Oracle preferiu dividir em dois (nada mais lógico), onde o primeiro é o século (ano, dividido por 100) e o segundo é o resto do ano, dividido por 100… Assim, 2018 seria dividido em 20 e 18. Porém, para suportar anos “negativos” esses dois valores são “polarizados” em 100. Ou seja, a Oracle soma 100 aos valores. 2018 é 120 e 118. A segunda polarização (ou excesso), para mim, não faz sentido, já que a primeira já garante o uso do século -100 até 155 (supostamente do ano -10000 até 15500. que seria somado ao ano. Assim, para decodificar o ano temos que fazer:

int year = (oradate[0] - 100)*100 + (oradate[1] % 100);

A divisão está ai porque assumo que o ano seja sempre positivo e aproveito a multiplicação por 100 feita antes na tentativa que o compilador otimize as operações inversas. O mês e o dia funcionam como devem…

Mas, o mais esquisito não é a data. O horário é fornecido com a adição de 1. Para a Oracle não existe 0:00:00, mas sim 1:01:01. Assim, o dia começa às 1:01:01 e termina às 24:60:60. Yep… existe 60 minutos e 60 segundos…