El formato matroska tiene una característica (opcional) 'Compressed_Header' que puede traer problemas si intentamos convertir un vídeo desde este formato con mencoder, la forma de crear un archivo sin esta característica es sencilla:

1

mkvmerge -o archivo_para_convertir.mkv archivo_original.mkv

mkvmerge forma parte del paquete mkvtoolnix, así que se puede instalar en los derivados de debian con

1

sudo apt-get install mkvtoolnix

1

head -c 1 /dev/random | od -An -td

• head -c 1 /dev/random: Lee un solo caracter de /dev/random.
• od -An -td: od suele usarse para mostrar los valores octales de un archivo (de ahí octal dump), con -An indicamos que no queremos que se muestre el offset, y con -td hacemos que se muestre en decimal.

Al parecer, a menos que haya entendido mal, el Concurso Universitario de Software Libre de este año toca a su final, ha sido divertido, he aprendido mucho y me haría falta valgrind para recordar todos los leaks de horas de sueño.

Realmente no hay mucho que decir, el proyecto se estancó demasiado (sobretodo cada vez que había que implementar el endemoniado preprocesador de C xD), mucho más atrás de lo esperado. Aún así tengo pensado seguir trabajando, la experiencia no ha hecho más que confirmar que una herramienta para experimentar con estas cosas sería útil, sobretodo si algo muy básico requiere tanto tiempo.

Sobre el desarrollo en sí, el estado actual es bastante penoso (a estas alturas contaba con tener ya orientación a objetos, iluso de mi :P), el intérprete se porta relativamente bien, pero el único parser de C que a duras penas funciona es el de la rama de prototipado (una explicación de el árbol de proyecto, las ramas y tal en el README). Hasta ahora el desarrollo básicamente se producía sobre Git y Gitorious (que funciona en local) para después pasarlo al SVN de la forja, supongo que seguirá así hasta tener una razón para cambiar.

ps: ¿Es obvio que cualquier aporte/apoyo/idea será bien recibido, no?

Saludos

La historia

Año 2012, los habitantes de Internet han desarrollado herramientas para distribuir información entre redes de pares, desde los enormemente extendidos (eDonkey y BitTorrent) a otros algo menos, de los que solo se preocupan de repartir información a los que se centran comprometer lo mínimo a los extremos (GNUnet y Freenet), de los que solo distribuyen archivos a los que conforman una capa sobre la que se pueden erigir otros protocolos (I2P).

Se han llegado a encontrar formas de coordinar toda esa nube de máquinas de forma distribuida, sin puntos centrales, con Tablas hash distribuidas. Incluso se ha conseguido llegar a una forma de identificar la forma de alcanzar la información con la llegada de los enlaces magnéticos que permitian representar un archivo en una de estas redes.

... viendo esto uno no puede dejar de sorprenderse al darse cuenta de que si, todo genial, pero para empezar uno necesita ese enlace y ¡oh! para eso hay que obtenerlo de una fuente, una página web probablemente, toda la red está distribuida menos la entrada.

Nota: bien, esto no es del todo cierto, eDonkey permite realizar búsquedas... pero todos conocemos su fiabilidad, ¿verdad?

La idea

Necesitamos una red para compartir enlaces, debe ser distribuida y a ser posible soportar una red de confianza (Web of trust) para evitar la contaminación de los enlaces sin necesidad de una moderación activa.

El prototipo/experimento

Nota: Vaya por delante que es una idea con muchos defectos pero todos sabemos como van estas cosas, lo importante es arrancar, después ya habrá tiempo de rectificar.

La parte cliente: lnet.zip (requiere pygtk)
El servidor: http://pastebin.com/3RALJEpi
La sentencia para crear la tabla:

1
2
3
4
5
6
7

CREATE TABLE `links` (
    `sent_by` varchar(256) DEFAULT NULL,
    `title` varchar(256) NOT NULL,
    `sent_on` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
    `url` varchar(256) NOT NULL,
    `signature` char(40) DEFAULT NULL
);

Bien, antes de seguir reconozco que separar cliente y servidor en una supuesta red P2P tiene mala pinta (ya no solo el proceso, sinó el lenguaje y que uno funcione con GUI y otro como una página de un servidor web :/. Y que estén a medio acabar solo lo deja peor (ninguno de los dos comprueba la firma de los links que recibe).

El "protocolo" es bien sencillo, funciona sobre HTTP, y definiría dos tipos de interacción, la petición de cambios y la adición de un cambio. Para hacer una petición de cambios un par se conecta a otro (supongamos que ejemplo.com/links.php) y hace una petición HTTP activando el parámetro changes y (opcionalmente) ajusta since como el momento UNIX a partir del cual se quieren los cambios, por ejemplo si es la primera vez que se hace la petición (todos los cambios, desde 0) se traduciría en ejemplo.com/ links.php?changes&since=0.

Como respuesta el servidor devolvería un conjunto de cambios, que podrían ser la adición de un enlace:

1
2
3
4
5
6
7

ADD  
title: <título>  
url: <enlace>  
sent_on: <momento de emisión>  
sent_by: <emisor, "none" si no está firmado>  
signature: <firma de "$title\n$url\n$sent_by\n$sent_on", o "none">  
.

La eliminación de un enlace (el efecto práctico sería el retiro de la firma):

1
2
3
4
5
6
7

DEL  
sent_on: <momento de emisión de la orden de eliminación>  
title: <título>  
url: <enlace>  
sent_by: <emisor de la orden>  
signature: <firma de "DEL\n$title\n$url\n$sent_by\n$sent_on">  
.

La firma de una clave por parte de otra (X firma/confía en Y):

1
2
3
4
5

SIGN  
signed_key: <clave firmada>  
signer_key: <clave que firma>  
signature: <firma de "SIGN\n$signed_key\n$signer_key">  
.

La revocación de una firma de una clave (X ya no firma/confía en Y): lo mismo que la firma (sign/unsign).

Como decía antes, también se podría enviar cambios a un nodo pero como con lo anterior solo está implementado la adición de enlaces, enviando a ejemplo.com/links.php?add por POST los parámetros

1
2
3
4

sender: <emisor o "none">  
link: <enlace>  
timestamp: <momento de emisión>  
signature: <firma como se definió en cambios `ADD`>

Esta última parte está especialemente descuidada, como mínimo habría que normalizar los nombres de los campos con los de los cambios :/.

Ventajas e inconvenientes de esta aproximación

El basar el protocolo en HTTP tiene sus ventajas, hay librerías para aburrir, de servidor o de cliente, todo el mundo lo conoce, se ríe de los firewall y no requiere un entorno especifico, cualquier servidor web podría ser un nodo.

Sin embargo otras cosas no son tan bonitas, aunque ya no sea por culpa de HTTP, este modelo lo que hace es que cada nodo tenga toda la colección de enlaces (bueno, o si se limitan a los en que confía menos), es bastante resistente, pero parece poco escalable a la larga. Por esto creo que sería interesante buscar la forma de distribuir los enlaces en una especie de DHT y después permitir a los pares hacer búsquedas sobre la red mandando una petición.

EOF

Enfin, hasta ahí he llegado, supongo que no es necesario decir que cualquier idea y/o ayuda sería muy de agradecer :)

Saludos

En cierto tablón de discusión, de cuyo nombre no quiero acordarme se hablaba sobre la optimización de switches en SBCL (un intérprete/compilador de common lisp), que hacía una serie de CMP, JMP en vez de usar una table, alguien daba como motivo el "branch prediction", parecía poco probable pero algo entretenido de probar.

Nota: mi experiencia con ensamblador es bastante limitada, así que lo que resulte de esto creételo lo justo ;)

Leer más…

Últimamente he estado trasteando con Common Lisp, y ya que tengo la constumbre de escribir una implementación de ARC4 como prueba de un lenguaje, ahí va una (está comentada de más precisamente para servir como ejemplo):

Leer más…

La mente es algo bien curioso, intenta obligarla a prestar atención durante un rato largo a algo tan estimulante como el crecer de la hierba y divagará y divagará... hasta darse de morros con algo sin saber como llegó allí. Hará como un par de semanas estaba yo en esta situación y sin saber como se me ocurrió tirar de cierto código para intentar dar "marcha atrás" en el juego de la vida de Conway, algo que por lo que parece solo sería posible por fuerza bruta (quizá que sea Turing completa tenga algo que ver :P).

Y aunque queda mucho pulir aquí y allá (solo puede obligar a las celulas vivas a mantenerse vivas, el código para las demás está escrito pero no acaba de funcionar así que hay que revisarlo), creo que puede ser interesante.

Los códigos son estos:

• bool_solve.py (tiene unas cuantas optimizaciones con respecto al anterior)
• life.py (el estado inicial se define con la variable state, hay ejemplos a partir de la línea 43)

Por ejemplo, figura objetivo:

Tiene estas "soluciones": coloreado_para_terminal texto plano

Si damos un paso más, por ejemplo en esta:

Llegamos a un punto donde las que estaban vivas lo estarán, las demás... depende (las que deben estar vivas están en verde):

Nota: llevó 21:30 minutos calcularlo, para 2^25 estados iniciales posibles equivaldría a probar unos 26011 cada segundo :D.

Y eso es todo lo que he conseguido por ahora, me pregunto hasta donde se podría llegar.

La época de exámenes es algo curioso, de repente todo lo trivial se vuelve interesante: la trayectoria de las moscas, cualquier cosa que uno se pueda encontrar en la Wikipedia...

En estas me hallaba yo ayer, así que tirando de clásicos acabe "enfrentándome" al problema de P contra NP, y para mi sorpresa creo que di con algo interesante (bueno, eso o entendí algo mal, que es lo más probable :P).

Pero no adelantemos acontecimientos, resulta que escojí un problema NP-completo, satisfacción booleana, y me lié a tirar código, este es el resultado (perdón por la escasez de comentarios):

bool_solve.py: Este es el algoritmo en sí.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219

#!/usr/bin/env python
#coding: utf-8

from random import randint
from copy import copy

OR_OP  = 1
AND_OP = 2
NOT_OP = 3

class Operand:
    name = ""
    inverted = False

    def __eq__(self, other):
        return self.__hash__() == other.__hash__()

    def __hash__(self):
        return self.__repr__().__hash__()

    def __init__(self, name, inverted = False):
        assert(not name.startswith('!'))
        self.name = name
        self.inverted = inverted
        self._hash = randint(0, 4294967295)


    def invert(self):
        self.inverted = not self.inverted

    def __str__(self):
        if self.inverted:
            return "!" + self.name
        else:
            return self.name

    def __repr__(self):
        return self.__str__()

# --------------------------------------------
# AND operation functions
# --------------------------------------------

# v is possible under cond ?
def is_acceptable(v, cond):
    if type(cond) == list:
        return all(map(lambda x: is_acceptable(v, x), cond))

    elif type(cond) == set:
        return all(map(lambda x: is_acceptable(v, x), cond))

    else:
        return v.name != cond.name or v.inverted == cond.inverted

# (ow = one way) are src conditions possible under dst ?
def is_ow_acceptable(src, dst):
    if type(src) == list:
        return all(map(lambda x: is_ow_acceptable(x, dst), src))

    elif type(src) == set:
        return all(map(lambda x: is_ow_acceptable(x, dst), src))

    else:
        return is_acceptable(src, dst)

# (tw = two way) are c1 and c2 possible simultaneously
def is_tw_acceptable(c1, c2):
    if c1 == None or c2 == None:
        return False

    ac2 = is_ow_acceptable(c1, c2)
    ac1 = is_ow_acceptable(c2, c1)
    return ac1 and ac2

# --------------------------------------------
# Common operation functions
# --------------------------------------------

# considers the different branches and may output a more compact one
# TODO: actually code the important part :P
def clean_branch_list(bl):
    l = []
    for i in xrange(len(bl)):
        bi = bl[i]

        already_contained = False
        to_delete = []

        le = len(l)
        for j in xrange(len(l)):
            bj = l[j]

            if bi.issubset(bj):
                if len(bj - bi) > 0: # Superset
                    to_delete.append(j)
                else:
                    already_contained = True

            elif bi.issuperset(bj):
                already_contained = True

        if not already_contained:
            l.append(bi)

        offset = 0
        for d in to_delete:
            l.pop(d - offset)
            offset += 1

    return l

# outputs the (con1 or con2) branch list
def rewrite_constraints_or(con1, con2):

    if type(con1) == set:
        con1 = [con1]

    if type(con2) == set:
        con2 = [con2]

    # Null operands?
    if con1 == None:
        if con2 == None:
            return None
        return con2

    elif con2 == None:
        return con1

    return clean_branch_list(con1 + con2)


# outputs the (con1 and con2) branch list
def rewrite_constraints_and(c1, c2):
    if type(c1) == set:
        c1 = [c1]
    elif c1 == None:
        c1 = []

    if type(c2) == set:
        c2 = [c2]
    elif c2 == None:
        c2 = []

    sets = []

    # Some optimization would be great here!! :P
    for x in c1:
        for y in c2:
             if is_tw_acceptable(x, y):
                sets.append(x | y)

    if len(sets) == 0:
        return None
    else:
        return clean_branch_list(sets)


# Obtains recursively the solution branches of a operation
def get_solutions(operand, inverted = False):
    if type(operand) == str:
        op = Operand(operand)
        if inverted:
            op.invert()
        return [set([op])]

    assert(type(operand) == tuple)

    if len(operand) == 2:
        op, op1 = operand
        sol = get_solutions(op1, not inverted)

        if op == NOT_OP:
            return sol
        raise Exception("%i operand doesn't apply to two operands" % op)

    else:
        op, op1, op2 = operand
        sol1 = get_solutions(op1, inverted)
        sol2 = get_solutions(op2, inverted)

        if not inverted:
            if   op == OR_OP:
                return rewrite_constraints_or(sol1, sol2)

            elif op == AND_OP:
                return rewrite_constraints_and(sol1, sol2)

        else:
            if   op == OR_OP:
                return rewrite_constraints_and(sol1, sol2)

            elif op == AND_OP:
                return rewrite_constraints_or(sol1, sol2)


        raise Exception("%i operand doesn't apply to two operands" % op)

# TODO: Update this part
def get_solution_string(s):
    if type(s) == list:
        return ', '.join(map(get_solution_string, s))

    elif type(s) == set:
        return ', '.join(map(get_solution_string, s))

    else:
        return str(s)

# Pretty prints the solution branches
def print_solutions(sols):
    if sols == None:
        print "It's impossible!"
        return

    for s in sols:
        print get_solution_string(s)

    print '%i solution(s)' % len(sols)

bool_test.py: Prueba el código anterior con un ejemplo, y después hace una prueba de tiempos.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

#!/usr/bin/env python
#coding: utf-8

from bool_solve import *
from string import lowercase
from random import randint
from time import time

TEST_VARIABLE_NUMBER = 5
TEST_NUMBER = 20
BATCH_NUMBER = 1

plot_file = "plot.dat"

# Examples
# ========

# Operation = (Op_Code, Operand1, Operand2) | (Op_Code, Operand)
# Operand   = '"' <Operand name> '"' | Operation

# A and (B or ((!B or !C) and (C and (!B and ((!A or D) or B)))
#
#   B (1)       !D (0)
#  /           /
# A -> !B -> C -> D (1)
#         \
#          !C (0)
#
# !A (0)
#
# Results:
#
# A, B
# A, !B, C, D
#

# Negated
# -------

# !(A and (B or ((!B or !C) and (C and (!B and ((!A or D) or B))))
#
# !A (1)
#
#    B (0)     !D (1)
#   /         /
# A -> !B -> C -> D (0)
#        \
#         !C (1)
#
# Results
#
# !A
#  A, !B, !C
#  A, !B,  C, !D
#

op = (AND_OP, 'a', # A and
             (OR_OP, 'b', #  ( B or
                    (AND_OP, # ( x and y )
                             (OR_OP, (NOT_OP, 'b'),  # x = ( !B or
                                     (NOT_OP, 'c')), #       !C  )

                             (AND_OP, 'c' ,                   # y = ( C and
                                      (AND_OP, (NOT_OP, 'b'), #      ( !B and
                                               (AND_OP, 'c',  #       !C ))

                                                        (OR_OP, # ( x or y )
                                                                (OR_OP, (NOT_OP, 'a'), # x = (!A or
                                                                        'd'),           #       D )
                                                                'b'  # y = B ))
                                                        )
                                               )
                                      )
                             )
                    )
             )
     )
# Hey! it looks like lisp, let's try to run it xD

test_variables = set(['a', 'b', 'c', 'd'])

forward_solutions = [set([Operand('a'), Operand('b')]),
                     set([Operand('a'), Operand('b', True), Operand('c'), Operand('d')])]

reverse_solutions = [set([Operand('a', True )]),
                     set([Operand('b', True), Operand('c', True )]),
                     set([Operand('a', False), Operand('b', True), Operand('d', True)])]


def check_solutions(sol1, sol2):
    for i in sol1:
        if not i in sol2:
            raise Exception('Calculation error!')

    for j in sol2:
        if not j in sol1:
            raise Exception('Calculation error!')


# Generates a random boolean table
def make_bool_tree(height, variable_num):
    if height == 0:
        x = randint(0, 1)
        if x == 0:
            return lowercase[randint(0, variable_num - 1)]
        else:
            return (NOT_OP, lowercase[randint(0, variable_num - 1)])

    op = randint(1, 2)
    return (op, make_bool_tree(height - 1, variable_num), make_bool_tree(height - 1, variable_num))

def print_time_table(trees):
    i = 1
    l = []
    for tree in trees:
        t = time()
        solutions = get_solutions(tree)
        t2 = time()

        l.append(t2 - t)
        if solutions != None:
            print "%i: %s [%s solution(s)]" % (i, t2 - t, len(solutions))

        else:
            print "%i: %s impossible" % (i, t2 - t)

        i += 1
    return l

# A simple test
if __name__ == "__main__":

    print "Testing correctness..."
    print '"Forward"'
    solutions = get_solutions(op)
    print_solutions(solutions)
    check_solutions(solutions, forward_solutions)
    print "OK"

    print '\n"Reverse"'
    solutions_n = get_solutions((NOT_OP, op))
    print_solutions(solutions_n)
    check_solutions(solutions_n, reverse_solutions)
    print "OK"

    print "\n\nTesting times..."
    times = []
    for i in xrange(BATCH_NUMBER):
        print "Batch %i of %i" % (i + 1, BATCH_NUMBER)
        trees = map(lambda x: make_bool_tree(x, TEST_VARIABLE_NUMBER), xrange(TEST_NUMBER))
        times.append(print_time_table(trees))

    if plot_file != None:
        f = open(plot_file, 'wt')
        means = []
        for i in xrange(len(times[0])):
            means.append(sum(map(lambda x: x[i], times)) / float(len(times)))

        i = 1
        for m in means:
            print >> f, i, m
            i += 1

Si se lanza el bool_test.py hace sus pruebas y genera un archivo "plot.dat" con los datos de los tiempos, pasados por el Gnuplot sale esto:

Y ahi quedo el tema... eso sí, quedé medio mosca por que no entendía como un algoritmo que solo pasa una vez por cada elemento podía generar tiempos tan claramente exponenciales pero en fin...

Esta mañana me di cuenta de por que era así, el problema era que lo que crecía exponencialmente no era el algoritmo, sinó los árboles que se generan para las pruebas, al ser binarios completos el número de nodos es 2^altura, así que reinterpretando los datos...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

input = "plot.dat"
output = "plot_number.dat"
fin = open(input, "rt")
f = open(output, "wt")

for x in fin.read().split("\n"):
    if len(x.strip()) > 0:
        height, time = x.split(" ", 2)
        print >>f, (1<<(int(height) - 1)), time

f.close()
fin.close()

Sale algo hermosamente lineal:

En resumen, hay distintas posibilidades:

• La pifié interpretando el problema, y eso no es lo que se supone que había que hacer.
• La pifié en el código y el ejemplo funciona por pura casualidad. (Creo que esto es lo más probable, realmente no se por que demonios funciona :P)

Nota: Irónicamente, el servidor de multiupload ya no responde.

Ayer cayó megaupload y no tiene pinta de que se vuelva a levantar, dejando de lado las implicaciones éticas que eso ha tenido, la guerra que declaró anonymous y demás, hay algo que está claro: es una perrada que chapen el servidor donde tenias las cosas subidas.

Y si, hay quien realmente usaba estos servicios para compartir archivos sin copyright por internet!, por ejemplo para reemplazar el dropbox que usa un demonio privativo, así que si bien en ese sentido lo de megaupload no es especialmente grave, es un buen aviso para tomar precauciones. De ahora en adelante a subir todo a varios servidores.

Script: http://pastebin.com/rNA0Sps3

Resultado: http://www.multiupload.com/WBF5NQ6E1Y

Me enteré por javibc de que hay un portal del ministerio de haciendo con los datos de los concejales de toda españa disponibles [ http://ssweb.mpt.es/portalEELL/consulta_alcaldes ] (hay que entrar dos veces, una para que dea la cookie y la siguiente ya deja pasar :P), después no pocos dolores de cabeza ahí va el parser y la base de datos. [ cargos.zip ]

Nota: Hay información en #Freesoftwareando, de hecho al principio los parsers usaban su base de datos de municipios pero ahora generan otra para evitar salirse de las librerías estándar de python.

Para parsearlas de nuevo, primero hay que preparar y lanzar get_provincias.py, para ponerlo a punto hay que editar las cookies (línea 20) con las que la web te haya asignado, al lanzar el script este preparará una base de datos con los municipios de cada provincia.

El siguiente paso es preparar el get_cargos.py, de nuevo hay que editar las cookies (línea 8) y esta vez además ajustar el csrf_token (línea 128) que se puede encontrar en la página buscando esto:

1
2
3

<input type="hidden" name="consulta_alcalde[_csrf_token]"
       value="717f8d1f38ba8e586a2fcbc5ca2b840c" id="consulta_alcalde__csrf_token" />
('717f8d1f38ba8e586a2fcbc5ca2b840c')

La base de datos obtenida debería ser algo así [ cargos.sqlite3.gz ] (aunque sin el .gz :P)

Y ya que estamos, ahí van convertidas a un par de formatos:

• sqlite2

• CSV para las hojas de cálculo (una tabla con provincia, municipio, nombre, apellidos, lista, cargo)

__EOF__