Me acostumei a usar o legendas.tv para baixar legendas de filmes e acabei nunca me perguntando se haveria um jeito mais fácil de baixá-las. Hoje fui assistir um filme e, ao entrar no navegador para baixar sua legenda, me deparei com a mensagem de que o site estava fora do ar:

A situação me obrigou a procurar outros sites e outras formas de baixar legendas. Minha primeira ideia foi usar o opensubtitles.org, que já havia usado algumas outras vezes. Chegando lá e procurando pelo filme que eu desejava, vi muitas opções e não estava muito claro que legenda baixar para a versão do filme que eu tinha.

Então resolvi dar uma fuçada na pesquisa avançada do site, onde acabei encontrando uma pesquisa por hash. Hash, em computação, é uma função que “resume” uma informação gigante (tipo um arquivo bem grande) numa informação bem pequena (tipo 16 caracteres) que o represente de forma única (ou quase única). A pesquisa por hash, no caso desse site, consiste em procurar uma legenda utilizando esse “ID” do arquivo (ou seja, não importa seu nome).

Achei a possibilidade tão legal que resolvi fazer um programa para nunca mais precisar abrir o navegador quando eu quiser baixar a legenda de um filme. Escrevi um minúsculo programa em C chamado oshash (de OpenSubtitles Hash) para calcular o hash de um filme de acordo com a especificação do site (que não requer nada, a não ser um compilador de C e a biblioteca padrão) e um script (bem tosco, mas funcional) chamado downloadsubtitle que usa o programa oshash (e pequenos programas que todo mundo tem, tipo grep, sed, wget e unzip) para baixar a legenda.

O funcionamento ficou bem fácil: para baixar uma legenda em qualquer língua, basta você digitar downloadsubtitle arquivo.avi para baixar a legenda do “arquivo.avi” (que já vai ser automaticamente nomeada como “arquivo.srt”). Se você quiser especificar uma língua (por exemplo, português do Brasil), é só digitar downloadsubtitle arquivo.avi pob (pob é o código do português do Brasil). Se você quiser baixar uma legenda em inglês ou espanhol, pode usar downloadsubtitle arquivo.avi eng,esp.

Exemplo de funcionamento

$ ls
Amelie [Amélie Poulain].2001.BRRip.x264.AAC[5.1]-VLiS.mkv
$ downloadsubtitle Amelie\ \[Amélie\ Poulain\].2001.BRRip.x264.AAC\[5.1\]-VLiS.mkv pob
Requested language: pob
Movie hash: bcdc90cf4873c09b
Subtitle ID: 4642726
Subtitle: Amelie [Amélie Poulain].2001.BRRip.x264.AAC[5.1]-VLiS.srt
$ ls
Amelie [Amélie Poulain].2001.BRRip.x264.AAC[5.1]-VLiS.mkv  Amelie [Amélie Poulain].2001.BRRip.x264.AAC[5.1]-VLiS.srt
$

E aí o filme está pronto para você assistir com o mplayer ou com o seu programa favorito.

Código

Este é o código inicial. Está aqui para fins históricos. Não será atualizado. Use a próxima seção (Download) para baixar a última versão, com bugs corrigidos, tratamento de erros e possivelmente novas funcionalidades.

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

void usage(char *name) {
    printf("Usage: %s <file>\n", name);
    exit(1);
}

int main(int argc, char *argv[]) {
    unsigned long long buf[16384], c = 0;
    FILE *in;
    int i;
    if (argc != 2) {
        usage(argv[0]);
    }
    in = fopen(argv[1], "rb");
    if (in == NULL) {
        usage(argv[0]);
    }
    fread(buf, 8192, 8, in);
    fseek(in, -65536, SEEK_END);
    fread(&buf[8192], 8192, 8, in);
    for (i = 0; i < 16384; i++) {
        c+= buf[i];
    }
    c+= ftell(in);
    fclose(in);
    printf("%016llx\n", c);
    return 0;
}

#!/bin/bash

usage() {
    echo "Usage: $0 <file> [lang]"
    echo "Examples:"
    echo "$ $0 movie.avi pob         # brazilian portuguese"
    echo "$ $0 movie.avi por,pob     # any portuguese"
    echo "$ $0 movie.avi eng         # english"
    echo "$ $0 movie.avi all         # any language"
    exit
}

if [ $# -lt 1 ]; then
    usage
elif [ $# -gt 2 ]; then
    usage
fi

if [ $# = 2 ]; then
    lang=$2
else
    lang="any"
fi

echo "Requested language: $lang"
output=$(echo "$1" | sed 's/\.[^.]*$/.srt/')
oshash=$(oshash "$1")
echo "Movie hash: $oshash"
subid=$(wget "http://www.opensubtitles.org/en/search/sublanguageid-$lang/moviehash-$oshash/rss_2_00" -q -O - \
    | grep '<link />.*en/subtitles' | sed 's|.*en/subtitles/||; s|/.*||' | head -n1)
echo "Subtitle ID: $subid"
wget "http://www.opensubtitles.org/en/subtitleserve/sub/$subid" -q -O - | gunzip > "$output" 2> /dev/null
echo "Subtitle: $output"

Download

Criei um repositório no Github para colocar o código: github.com/tmadeira/downloadsubtitle

Para quem tem git, é possível baixar com git clone https://github.com/tmadeira/downloadsubtitle.git

Para quem não tem, dá pra baixar em ZIP daqui: github.com/tmadeira/downloadsubtitle/archive/master.zip

O programa ainda não está empacotado bonitinho (não tem nem Makefile ou instruções de instalação). Se futuramente vier a ter, este post será atualizado. Em resumo, basta compilar o código em C (digitando gcc oshash.c -o oshash) e colocar os arquivos oshash e downloadsubtitle numa pasta do seu $PATH (por exemplo, /usr/local/bin).

Sugestões e correções são bem-vindas.

Este post possui intencionalmente apenas imagens e códigos.

Código-fonte (com alguns bugs inofensivos — procure XXX)

/* pascal -- generate colored Pascal's triangles in XPM format

   Copyright (C) 2011 Tiago Madeira <madeira@ime.usp.br>

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You can read a copy of the GNU General Public License at
   http://www.gnu.org/licenses/gpl-3.0.txt */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <getopt.h>
#include <math.h>

#define DEFMOD 2
#define DEFSIZE 300
#define DEFPADDING 8

int mod = DEFMOD;
int size = DEFSIZE;
int padding = DEFPADDING;

char makecolors[6][4] = {
	"001", "010", "100", "110", "101", "001"
};

struct option longopts[] = {
	{"help", 0, 0, 'h'},
	{"padding", 1, 0, 'p'},
	{"size", 1, 0, 's'},
	{"mod", 1, 0, 'm'},
	{0, 0, 0, 0}
};

char *program_name;

void try_help() {
	fprintf(stderr, "Try `%s --help' for more information.\n", program_name);
}

void help() {
	printf("Usage: %s [OPTION]... [FILE]\n", program_name);
	printf("Generate colored Pascal's triangles (XPM format).\n\n");
	printf("Mandatory arguments to long options are mandatory for short options too.\n\n");
	printf("  -h, --help        print this help\n");
	printf("  -m, --mod=M       paint with different colors numbers mod M\n");
	printf("  -p, --padding=SZ  image padding (margin) in pixels\n\n");
	printf("  -s, --size=SZ     generate SZ lines of Pascal's triangle\n\n");
	printf("With no FILE, or when FILE is -, write to standard output.\n\n");
	printf("Report bugs to <madeira@ime.usp.br>.\n");
}

int baselog(int n, int base) {
	return ceil(log(n) / log(base));
}

void *xmalloc(size_t size) {
	void *x = malloc(size);
	if (x == NULL) {
		fprintf(stderr, "There is no enough memory to allocate.\n");
		exit(3);
	}
	return x;
}

int main(int argc, char **argv) {
	int optc, tofile;
	int i, j;
	int width, height, chars;
	char **color, rgb[7];
	int one, pos;
	int *pascal;
	char *line;

	program_name = argv[0];
	while ((optc = getopt_long(argc, argv, "hm:p:s:", longopts, (int *)0)) != -1) {
		switch (optc) {
		case 'h':
			help();
			return 0;
		case 'm':
			mod = atoi(optarg);
			if (mod > 48) { /* XXX */
				fprintf(stderr, "At the moment, this program supports only mod <= 48 (color generation limit).\n");
				return 4;
			}
			if (mod > 26) { /* XXX */
				fprintf(stderr, "At the moment, this program supports only mod <= 26 (bad implementation limit).\n");
				return 5;
			}
			break;
		case 'p':
			padding = atoi(optarg);
			break;
		case 's':
			size = atoi(optarg);
			break;
		default:
			try_help();
			return 1;
		}
	}
	if (optind < argc && strcmp("-", argv[optind])) {
		if (freopen(argv[optind], "w", stdout) == NULL) {
			fprintf(stderr, "Can't open `%s' for writing.\n", argv[optind]);
			return 2;
		}
		tofile = 1;
	} else {
		tofile = 0;
	}

	printf("static char *a_xpm[] = {\n");
	width = size * 2 + padding * 2;
	height = size * 2 + padding * 2;
	chars = baselog(mod, 26);
	printf(""%d %d %d %d",\n", width, height, mod + 1, chars);
	color = xmalloc(sizeof(color[0]) * (mod+1));
	rgb[6] = '�';

	printf("\"");
	color[mod] = xmalloc(sizeof(color[mod][0]) * (chars + 1));
	for (j = 0; j < chars; j++) {
		color[mod][j] = ' ';
	}
	color[mod][chars] = '�';
	printf("%s c #000000\",\n", color[mod]);

	for (i = 0; i < mod; i++) {
		color[i] = xmalloc(sizeof(color[i][0]) * (chars + 1));
		if (i == 0) {
			for (j = 0; j < chars; j++) {
				color[i][j] = 'a';
			}
			color[i][chars] = '�';
		} else {
			strcpy(color[i], color[i-1]);
			for (j = chars-1; j >= 0; j--) {
				if (color[i][j] == 'z') {
					color[i][j] = 'a';
				} else {
					color[i][j]++;
					break;
				}
			}
		}
		one = 255 / pow(2, i / 6);
		sprintf(rgb, "%02x%02x%02x", makecolors[i%6][0] == '1' ? one : 0,
				makecolors[i%6][1] == '1' ? one : 0, makecolors[i%6][2] == '1' ? one : 0);
		printf("\"%s c #%s\",\n", color[i], rgb);
	}

	line = xmalloc(sizeof(line[0]) * (width+1));
	pascal = xmalloc(sizeof(pascal[0]) * size);

	line[width] = '�';
	for (j = 0; j < width; j++) {
		line[j] = ' ';
	}
	for (i = 0; i < padding; i++) {
		printf("\"%s\",\n", line);
	}

	memset(pascal, 0, sizeof(pascal[0]) * size);
	pascal[0] = 1;

	for (i = 0; i < size; i++) {
		for (j = i; j >= 0; j--) {
			if (j != 0) {
				pascal[j] = (pascal[j-1] + pascal[j]) % mod;
			}
			pos = padding + 2*j + (size - 1 - i);
			/* XXX a implementacao de line ficou toda errada e so estou pegando
			 * o primeiro caractere de color aqui. precisa ser reescrito. */
			line[pos] = line[pos+1] = *color[pascal[j]];
		}
		printf("\"%s\",\n\"%s\"%s\n", line, line, i == size-1 && !padding ? "" : ",");
	}

	line[width] = '�';
	for (j = 0; j < width; j++) {
		line[j] = ' ';
	}
	for (i = 0; i < padding; i++) {
		printf("\"%s\"%s\n", line, i == padding-1 ? "" : ",");
	}
	printf("};\n");

	if (tofile) {
		fclose(stdout);
	}
	return 0;
}

(Download – 5kb)

A idéia veio do nada. Na verdade, eu estava fazendo um freelance e procurando uma função pra “ordenar” um vetor aleatoriamente no PHP (no fim usei usort, que recebe uma função de comparação tipo o qsort do C) e me deparei com um comentário lá no PHP.net de um cara que usou geração de números aleatórios para criar um algoritmo de criptografia pra usar no lugar de MD5 e SHA, porque ele não confiava mais no MD5 e no SHA porque segundo ele existem tabelas na internet, o que torna um sistema muito vulnerável (para quem tem acesso ao banco de dados).

Procurei na internet e na verdade eu não encontrei muitos bancos de dados com vários MD5 não, ao menos não visíveis no Google quando se procura por um hash. Só pra strings como “1234”, mas não achei nem pra “060790” (minha data de nascimento). Veja você mesmo: 81811b48cc07432fc550cb42d4ab3e8f

Então pensei: são 31 dias por mês, 12 meses por ano, 100 anos considerando que os anos são representados por dois dígitos. Isso me dá 31 x 12 x 100 = apenas 37200 hashes. O custo pra gerar isso deve ser minúsculo, por que ninguém faz?

A idéia de fazer com essas datas de nascimento veio do fato de vários usuários leigos que conheço utilizarem data de nascimento pra suas senhas (muito também pelo fato de eles usarem essa mesma senha nas senhas de seis dígitos numéricos do banco e esse tipo de coisa). Então lá fui eu pro código. A princípio escrevi em cerca de 30 segundos – 1 minuto o seguinte código em Ruby:

require "md5"

100.times do |ano|
  12.times do |j|
    mes = j+1

    31.times do |i|
      dia = i+1
      string = sprintf("%02d%02d%02d", dia, mes, ano)

      md5 = MD5.new(string).to_s
      puts "#{string}: #{md5}"
    end
  end
end

É funcional e até eficiente…

tiago@flick ~ $ time ruby genmd5.rb > hashes-ruby

real    0m1.662s
user    0m0.620s
sys     0m0.028s

Mas minha geekialidade não permitiu que eu parasse por aqui. Nesse momento eu já nem me lembrava do freelance que estava fazendo e resolvi ver como usar MD5 em C. Meu primeiro chute foi um man md5 no terminal, que já me retornou a resposta da vida, do universo e tudo mais: o cabeçalho openssl/md5.h e sua função MD5:

unsigned char *MD5(const unsigned char *d, unsigned long n,
                 unsigned char *md);

Então lá fui eu pro programa:

#include <stdio.h>
#include <openssl/md5.h>

int main() {
  int dia, mes, ano;
  unsigned char string[STRING_LENGTH], md[MD5_DIGEST_LENGTH];
  for (ano = 0; ano < 100; ano++) {
    for (mes = 0; mes < 12; mes++) {
      for (dia = 0; dia < 31; dia++) {
        sprintf(string, "%02d%02d%02d", dia+1, mes+1, ano);
        printf("%sn", MD5(string, sizeof(string), md));
      }
    }
  }
  return 0;
}

Ao rodar, recebi saídas com caracteres estranhos e nenhum resultado visível. Corri pro Google. Procurei, procurei, e NINGUÉM usa essa maldita função MD5 do C num programa simples e não há exemplos nem howto de como utilizá-la. Depois de uns 30 minutos quebrando a cabeça (pra mais), percebi que alguns códigos que usavam isso na internet usavam %x (é o código pro printf imprimir inteiros hexadecimais) para imprimir caracteres do MD5 na tela. Aí encontrei algo assim:

printf("%x%x...%x%x", md[0], md[1], ..., md[14], md[15]);

(e pior que estou falando sério… tem gente na internet que não conhece for!)

E caiu a ficha. O MD5 tem 16 inteiros hexadecimais de um byte, 32 caracteres. Escrever o código abaixo me tomou bastante tempo, mas uma aprendizagem interessante e um ânimo pra voltar pro meu freelance:

#include <stdio.h>
#include <openssl/md5.h>

#define STRING_LENGTH 6

int main() {
  int dia, ano, mes;
  int i;
  unsigned char md[MD5_DIGEST_LENGTH], string[STRING_LENGTH];

  for (ano = 0; ano < 100; ano++) {
    for (mes = 0; mes < 12; mes++) {
      for (dia = 0; dia < 31; dia++) {
        sprintf(string, "%02d%02d%02d", dia+1, mes+1, ano);
        MD5(string, sizeof(string), md);
        printf("%s: ", string);
        for (i = 0; i < 16; i++) {
          printf("%02x", md[i]); /* Note isso aqui! */
        }
        printf("n");
      }
    }
  }
  return 0;
}

O “Note isso aqui!” ainda foi uma sacanagem incrível, o código que eu disse do cara que imprimia %x%x%x… não funciona na prática, porque quando um dos dígitos é 0X, ele só imprime X.

Enfim compilei meu código com -lssl (importante para C-zeiros de primeira viagem) e voi lá:

tiago@flick ~ $ time ./md5 > hashes-c

real    0m0.397s
user    0m0.136s
sys     0m0.028s

Confesso que é coisa de nerd mesmo querer otimizar um código que só serve pra gerar um arquivo de hashes e já o fez, mas no momento em que terminei esse teste, pensei: preciso postar isso no blog pra documentar o uso da função MD5 no C, antes que mais alguém perca o tempo que eu perdi.

Pra quem se pergunta se eu realmente fiz tudo certo:

tiago@flick ~ $ diff senhas-c senhas-ruby
tiago@flick ~ $

(i.e. ou eu errei nos dois ou eu não errei em nenhum)

Útil, não? Não. Na verdade isso não serve pra absolutamente nada, a não ser que você roube o banco de dados de alguém e esse alguém usa como senha a data de nascimento da sua mãe. Mas aí ele merece mesmo que você pegue sua senha, então isso não muda nada.

Dá pra adaptar o código pra gerar outras tabelas, mas por favor não use isso pra nada maligno, e falo sério. Meus fins foram absolutamente educacionais/acadêmicos (eu queria aprender a trabalhar com a função MD5 da biblioteca OpenSSL, não dominar o mundo) e estou postando aqui para ajudar os que também vão querer usar essa função.

Comentários de crackers serão ignorados.

Como alguns de meus leitores já sabem, meu laptop (Acer Aspire 5050-3205) possui uma Acer Orbicam sem suporte no Linux (tanto com gspcav, quanto com linux-uvc), identificada pelo lsusb como 0c45:6260 (vendor: Microdia).

Além da minha, existem várias webcams desse tipo sem suporte pelo Kernel: 0c45:6027, 0c45:608f, 0c45:60ec, 0c45:60fe, 0c45:60c0, 0c45:613b, 0c45:613c, 0c45:624e, 0c45:624f, 0c45:6242, 0c45:6253, 0c45:6260, 0c45:6270, 0c45:627b, 0c45:8105.

Na lista microdia, surgiu uma iniciativa que pode mudar essa realidade: usando USB sniffs dos drivers de Windows, começamos a desenvolver drivers para webcams Microdia (repositório git).

Gostaria de convidar a comunidade brasileira usuária de Linux que tem webcam Microdia (0c45:XXXX) a também participar, compartilhando as informações de sua câmera para ajudar no desenvolvimento. Quem se interessar, favor entrar na lista ou entrar em contato comigo para mais informações.

Encontrar números primos é um problema comum em olimpíadas e maratonas de programação. Até hoje não existe uma maneira fácil de determinar se um número é ou não primo, mas para resolver estes problemas é indispensável o conhecimento de alguns algoritmos clássicos e simples, como o Crivo de Eratóstenes.

O Crivo de Eratóstenes é um método bastante prático para encontrar os primos de 2 até um valor limite, que pode ser feito a mão e é fácil de implementar.

O algoritmo consiste em:

1. Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
2. Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
3. Criar um vetor (lista) com os números de 2 até o valor limite.
4. Para i=2 até raiz do valor limite, caso o número (i) não esteja riscado insira-o na lista dos primos (ou imprima-o, ou não faça nada, isso depende da utilidade que você quer dar para o crivo) e risque todos os seus múltiplos na lista.

Há várias maneiras de implementar este algoritmo. Eu pseudocodaria (meu pseudocódigo é bem próximo de uma linguagem normal, porque acho que assim é mais fácil de entender e depois implementar) ele assim:

/_ Primeiro passo _/
recebe valorLimite

/_ Segundo passo _/
raiz $\leftarrow$ $\sqrt{valorLimite}$

/_ Terceiro passo /
para _i $\leftarrow$ 2 até valorLimite
 vetor[i] $\leftarrow$ i
fim-para

/_ Quarto passo /
para _i $\leftarrow$ 2 até raiz
 se vetor[i] = i
  imprima “O número ” i ” é primo.”
  para j $\leftarrow$ i+i até valorLimite, de i e i
   vetor[j] $\leftarrow$ 0
  fim-para
 fim-se
fim-para

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include <stdio.h>
#include <math.h> // necessário para raiz

#define NMAX 1000000 // valor máximo para o valor máximo

int main() {
    int i, j, vetor[NMAX];
    int valorMaximo, raiz;

    // Primeiro passo
    scanf("%d", &valorMaximo);

    // Segundo passo
    raiz=sqrt(valorMaximo);

    // Terceiro passo
    for (i=2; i<=valorMaximo; i++) {
        vetor[i]=i;
    }

    // Quarto passo
    for (i=2; i<=raiz; i++) {
        if (vetor[i]==i) {
            printf("%d é primo!n", i);
            for (j=i+i; j<=valorMaximo; j+=i) {
                vetor[j]=0; // removendo da lista
            }
        }
    }

    return 0;
}

No USACO Training Program Gateway (programa de treinamento para olimpíadas dos estado-unidenses) há um problema muito interessante (Prime Palindromes) cujo objetivo é determinar palíndromos primos de X a Y. Uma das melhores situações que já encontrei para usar o Crivo e sem dúvidas é um ótimo treinamento. Além de determinar primos, você terá que determinar palíndromos e é outro ótimo exercício lógico-matemático.

Divirtam-se e qualquer dúvida usem os comentários!