Subida automática de archivos a GMail mediante IMAP

(English version available)

Hace un tiempo había una librería llamada libgmail capaz de comunicarse con GMail usando su protocolo propietario. Sin embargo, los protocolos propietarios tienen un problema muy grave: pueden cambiar en cualquier momento sin previo aviso, y cuando eso ocurre, los que han hecho la ingeniería inversa tienen que averiguar qué cambios se han producido para adaptarlos. Además, hay una norma expresa en los términos de servicio de Google prohibiendo el acceso «por ningún otro medio distinto de la interfaz facilitada por Google». Si se combina eso con el hecho de que libgmail está abandonado desde hace tiempo, puede uno imaginarse el resultado: libgmail ya no se puede utilizar.

Sin embargo, hay otras maneras de usar GMail para subir archivos adjuntos de forma automática. La que probablemente proporcione mayor flexibilidad es usar el protocolo IMAP para realizar las transferencias. El acceso IMAP es proporcionado explícitamente por GMail para que los usuarios no necesiten usar la interfaz web y puedan usar un cliente de email que soporte IMAP para manejar el correo, por lo tanto se puede argumentar que el uso de IMAP es acorde a los términos de servicio. No soy abogado, sin embargo, así que pregunte a uno si quiere una garantía legal.

Por desgracia, no hay actualmente ninguna librería similar a libgmail con soporte IMAP en vez del protocolo propietario de GMail. [Actualización 2011-03-09: Me acabo de enterar de que hay una nueva versión de GMailFS que utiliza el protocolo IMAP. Sin embargo, es un sistema de archivos para Linux, no una utilidad de línea de comandos compatible entre sistemas. No conozco aún una herramienta de línea de comandos que esté disponible para varios sistemas, aparte de la aquí presentada.] He escrito un programa en PHP a modo de prueba de concepto de una herramienta así. Es un ejemplo completo que crea en una cuenta de GMail un mensaje con la etiqueta «ftp» y un archivo adjunto, cuyo tipo MIME es «application/octet-stream». El programa requiere que la extensión IMAP esté instalada en PHP. En Debian Lenny, eso significa instalar el paquete php5-imap.

El acceso IMAP debe estar habilitado en la cuenta destino antes de empezar. La etiqueta 'ftp' debe existir previamente, así que debe ser creada antes de intentar subir ningún archivo. Después de la subida, se puede recuperar el archivo mediante la interfaz web de GMail.

Un inconveniente de este sistema comparado con libgmail es que, puesto que se usa la codificación Base64 para los archivos, el tiempo de subida es cerca de un 33% más. Sería posible en teoría subir archivos usando la codificación Base85, que reduce el tiempo extra a un 25%. Sin embargo, en ese caso la recuperación del archivo requeriría un decodificador Base85 y probablemente no sería posible simplemente hacer clic para descargarlo.

He aquí el código PHP, diseñado para usarse con la versión de línea de comandos. La forma de uso es:
php imap-upload.php <archivo_a_subir>

<?php

/**********************************
 *
 * Configuration section
 *
 */

// User name (full email address)
$usr = 'user@gmail.com';

// Password. Leave unset for being asked (sorry, with echo - yuck!)
unset($pwd);

// IMAP server
$svr = 'imap.gmail.com';

// IMAP port
$prt = 993;

// Folder / Tag (must exist prior to running this)
//$folder = '[Gmail]/Drafts'; // This one would use the actual GMail drafts folder.
                              // NOTE: must be localized, e.g. in spanish the name
                              // is '[Gmail]/Borradores'
$folder = 'ftp';  // Same tag used by gmailftpd.py

// Encoding for the filename string we are passing from the command line
$filename_enc = 'UTF-8';

/*
 *
 * End of configuration section
 *
 ***********************************/


// Encode the subject in MIME quoted-printable format as per RFC 2047
function encode_subject($title, $encoding)
{
  $ret = "=?$encoding?Q?";
  $linelength = 9; // length of "Subject: "

  for ($i = 0; $i < strlen($title); $i++)
  {
    if ($linelength >= 65)
    {
      $ret .= "?=\r\n =?$encoding?Q?";
      $linelength = 1; // length of initial space
    }

    if ($title[$i] >= ' ' and $title[$i] <= '~'
        and $title[$i] != '=' and $title[$i] != '?'
        and $title[$i] != '_')
    {
      if ($title[$i] == ' ')
        $ret .= '_';
      else
        $ret .= $title[$i];
      $linelength++;
    }
    else
    {
      $ret .= '=' . strtoupper(bin2hex($title[$i]));
      $linelength += 3;
    }
  }
  return $ret . '?=';
}

// quoted-string for parameters as per RFC 822
function quoted_string($string)
{
  return '"' . strtr($string, array("\\"=>"\\\\",
                                    "\""=>"\\\"",
                                    "\r"=>"\\\r",
                                    "\n"=>"\\\n")) . '"';
}

// grab 7-11 random lowercase letters
function randword()
{
  $result = '';
  for ($i = 0; $i < 7 + mt_rand(0, 4); $i++)
    $result .= chr(mt_rand(0, 25) + 97);
  return $result;
}

$filepath = $argv[1];

if (! isset($filepath))
  die("No filename specified to upload\n");

$filename = basename($filepath);

if ($prt == 993) $prt = ''; else $prt = ':' . $prt;

if (! isset($pwd))
{
  echo "pwd: ";
  $pwd = substr(fgets(STDIN), 0, -1); // remove extra \n
}

// Open the imap stream
$stream = imap_open("\x7B$svr$prt/ssl}$folder", $usr, $pwd);

// Report all possible errors
print_r(imap_errors());

// Exit on trouble
if ($stream === false) die("\nStopping\n");

$rnd1 = randword();
$rnd2 = randword();
$bndr = "------------" . randword() . randword();

$result = imap_append(
            $stream
            , "\x7B$svr$prt/ssl}$folder"
            , "From: $usr"
              . "\r\nTo: $rnd1@$rnd2.com"
              . "\r\nSubject: " . encode_subject($filename, $filename_enc)
              . "\r\nMIME-Version: 1.0"
              . "\r\nContent-type: multipart/mixed;"
              . "\r\n boundary=\"$bndr\""
              . "\r\n"
              . "\r\nThis is a multi-part message in MIME format."
              . "\r\n--$bndr"
              . "\r\nContent-Type: text/plain; charset=$filename_enc; format=flowed"
              . "\r\nContent-Transfer-Encoding: quoted-printable"
              . "\r\n"
              . "\r\n" . imap_8bit($filename)
              . "\r\n"
              . "\r\n--$bndr"
              . "\r\nContent-Type: application/octet-stream;"
              . "\r\n name=" . quoted_string($filename)
              . "\r\nContent-Transfer-Encoding: base64"
              . "\r\nContent-Disposition: attachment;"
              . "\r\n filename=" . quoted_string($filename)
              . "\r\n"
              . "\r\n" . imap_binary(file_get_contents($filepath))
              . "--$bndr--"
              . "\r\n"
              . "\r\n"
            );

if ($result)
  echo "Succeeded adding file\n";
else
  print_r(imap_errors());

$check = imap_check($stream);
echo "There are now ". $check->Nmsgs . " messages in the $folder folder\n";

print_r(imap_errors());

print_r(imap_alerts());

imap_close($stream);

?>

Y de regalo un pequeño rompecabezas. El generador de letras al azar puede generar entre 7 y 11 caracteres. Suponiendo que el generador genera números enteros uniformemente distribuidos entre 0 y 4 inclusive, ¿cuál es la probabilidad de cada una de las longitudes? Una pista: no es 1/5.

Automated upload to GMail via IMAP

Some time ago, there was a Python library called libgmail which was able to communicate with GMail using their proprietary protocol. However, proprietary protocols have a serious drawback: they can be changed at any time without prior notice, and when that happens, those who have reverse-engineered them have to figure out the changes. Furthermore, there's an explicit rule in Google's ToS forbidding access «by any means other than through the interface that is provided by Google». Combine it with the fact that libgmail has now been abandoned for a while, and you can figure out the result: libgmail is no longer usable.

There are, however, other ways of using GMail to do automated attachment uploads. The one that probably provides the most flexibility is to use the IMAP protocol to do the transfers. IMAP access is explicitly provided by GMail so that users do not need to use the web interface and can use an email client that supports IMAP to handle mail, thus it's arguable that using IMAP is in accordance with the ToS. I am not a lawyer, though, so ask one if you want to be sure.

Unfortunately, there's currently no library similar to libgmail which supports IMAP instead of the proprietary GMail protocol. [Update 2011-03-09: I just learned that there's a new version of GMailFS which uses the IMAP protocol. However, it is a filesystem for Linux, not a cross-platform command line utility. I don't know yet of a command line tool that is compatible across systems, besides the one presented here.] I've written a PHP program as a proof-of-concept of such a tool. It's a complete example that creates a message with the tag 'ftp', having an attached file with MIME type 'application/octet-stream', in a GMail account. The program requires the IMAP extension to be installed in PHP. In Debian Lenny, that means to install the package php5-imap.

IMAP access must be enabled in the target GMail account before starting. The files are tagged with the label 'ftp' which must already exist, so create it before trying to upload. After uploading, you can retrieve the file via the GMail web interface.

A drawback when compared to libgmail is that, as it uses Base64 encoding for files, the upload time is about 33% greater. It would be theoretically possible to upload files using Base85 encoding, which reduces the overhead to 25%. However, in that case the retrieval of the file would need a Base85 decoder and it would probably not be possible to just click on the file to download it.

Here's the PHP code, intended for being used with the PHP command line interface. Usage is:
php imap-upload.php <file_to_upload>

<?php

/**********************************
 *
 * Configuration section
 *
 */

// User name (full email address)
$usr = 'user@gmail.com';

// Password. Leave unset for being asked (sorry, with echo - yuck!)
unset($pwd);

// IMAP server
$svr = 'imap.gmail.com';

// IMAP port
$prt = 993;

// Folder / Tag (must exist prior to running this)
//$folder = '[Gmail]/Drafts'; // This one would use the actual GMail drafts folder.
                              // NOTE: must be localized, e.g. in spanish the name
                              // is '[Gmail]/Borradores'
$folder = 'ftp';  // Same tag used by gmailftpd.py

// Encoding for the filename string we are passing from the command line
$filename_enc = 'UTF-8';

/*
 *
 * End of configuration section
 *
 ***********************************/


// Encode the subject in MIME quoted-printable format as per RFC 2047
function encode_subject($title, $encoding)
{
  $ret = "=?$encoding?Q?";
  $linelength = 9; // length of "Subject: "

  for ($i = 0; $i < strlen($title); $i++)
  {
    if ($linelength >= 65)
    {
      $ret .= "?=\r\n =?$encoding?Q?";
      $linelength = 1; // length of initial space
    }

    if ($title[$i] >= ' ' and $title[$i] <= '~'
        and $title[$i] != '=' and $title[$i] != '?'
        and $title[$i] != '_')
    {
      if ($title[$i] == ' ')
        $ret .= '_';
      else
        $ret .= $title[$i];
      $linelength++;
    }
    else
    {
      $ret .= '=' . strtoupper(bin2hex($title[$i]));
      $linelength += 3;
    }
  }
  return $ret . '?=';
}

// quoted-string for parameters as per RFC 822
function quoted_string($string)
{
  return '"' . strtr($string, array("\\"=>"\\\\",
                                    "\""=>"\\\"",
                                    "\r"=>"\\\r",
                                    "\n"=>"\\\n")) . '"';
}

// grab 7-11 random lowercase letters
function randword()
{
  $result = '';
  for ($i = 0; $i < 7 + mt_rand(0, 4); $i++)
    $result .= chr(mt_rand(0, 25) + 97);
  return $result;
}

$filepath = $argv[1];

if (! isset($filepath))
  die("No filename specified to upload\n");

$filename = basename($filepath);

if ($prt == 993) $prt = ''; else $prt = ':' . $prt;

if (! isset($pwd))
{
  echo "pwd: ";
  $pwd = substr(fgets(STDIN), 0, -1); // remove extra \n
}

// Open the imap stream
$stream = imap_open("\x7B$svr$prt/ssl}$folder", $usr, $pwd);

// Report all possible errors
print_r(imap_errors());

// Exit on trouble
if ($stream === false) die("\nStopping\n");

$rnd1 = randword();
$rnd2 = randword();
$bndr = "------------" . randword() . randword();

$result = imap_append(
            $stream
            , "\x7B$svr$prt/ssl}$folder"
            , "From: $usr"
              . "\r\nTo: $rnd1@$rnd2.com"
              . "\r\nSubject: " . encode_subject($filename, $filename_enc)
              . "\r\nMIME-Version: 1.0"
              . "\r\nContent-type: multipart/mixed;"
              . "\r\n boundary=\"$bndr\""
              . "\r\n"
              . "\r\nThis is a multi-part message in MIME format."
              . "\r\n--$bndr"
              . "\r\nContent-Type: text/plain; charset=$filename_enc; format=flowed"
              . "\r\nContent-Transfer-Encoding: quoted-printable"
              . "\r\n"
              . "\r\n" . imap_8bit($filename)
              . "\r\n"
              . "\r\n--$bndr"
              . "\r\nContent-Type: application/octet-stream;"
              . "\r\n name=" . quoted_string($filename)
              . "\r\nContent-Transfer-Encoding: base64"
              . "\r\nContent-Disposition: attachment;"
              . "\r\n filename=" . quoted_string($filename)
              . "\r\n"
              . "\r\n" . imap_binary(file_get_contents($filepath))
              . "--$bndr--"
              . "\r\n"
              . "\r\n"
            );

if ($result)
  echo "Succeeded adding file\n";
else
  print_r(imap_errors());

$check = imap_check($stream);
echo "There are now ". $check->Nmsgs . " messages in the $folder folder\n";

print_r(imap_errors());

print_r(imap_alerts());

imap_close($stream);

?>

Here's a little bonus brainteaser. The generator of random lowercase letters can generate 7 to 11 characters. What's the probability of each length? Hint: it's not 1/5.

Génera y sexa

¿A ustedes no les asombra
que diciendo rico y rica,
majo y maja, chico y chica,
no digamos hombre y hombra?
Y la frase tan oída
del marido y la mujer,
¿por qué no tiene que ser
el marido y la marida?
[...]
El sexo a hablar nos obliga
a cada cual como digo:
si es hombre, me voy contigo;
si es mujer, me voy contiga.
—Melitón González (Pablo Perellada), El idioma castellano (fragmento)

Ya hace mucho que, en el esfuerzo por compensar el machismo tradicional en nuestra sociedad, ciertos grupos están intentando imponer el hembrismo como doctrina. Y no digo feminismo, porque feminismo es otra cosa. El objetivo parece ser la venganza a través del cambio de papeles, así que se trata de sustituir una dominación por la contraria.

En ese empeño de sobrecompensarla hasta el punto de llevarla al polo opuesto, uno de los más equivocados objetivos es la hembrización del lenguaje. Típicamente, se confunde género con sexo y las palabras de género masculino se fuerzan de forma artificial a una versión femenina inexistente. No digo que ello esté siempre mal; la lengua se rige por la tradición y la inexistencia de ciertas palabras puede deberse a la falta de uso previo, por lo que si surge la necesidad, es lógico que aparezcan.

Veamos unos ejemplos. El que maneja una bomba hidráulica para apagar incendios es un bombero; por tanto, si es ella, es bombera. Sí, puede sonarnos extraño, pero dudo que sea por otra razón que la falta de costumbre, pues es el mismo caso que con cajero y cajera, por decir uno. Otro ejemplo más sencillo: el que aboga es abogado y la que aboga, abogada. Aquí, además, contamos con un verbo cuyo participio ya pertenece a nuestro idioma, de modo que la palabra ya existía; por ejemplo, «la reforma abogada por los grupos...» vendría a significar «la reforma por la que los grupos abogan...». No es preciso agregar un vocablo inexistente para referirse a las que ejercen la abogacía.

El problema del hembrismo está en que arrambla con todo tipo de palabras, pese a los absurdos a los que conduce tal política (como con miembra*). Hasta tal punto llega el empeño, que también se han convertido al femenino palabras neutras. ¿Qué me dicen de jueza? Juez es una palabra de género común que no tiene siquiera una terminación clásicamente asociada al género masculino. ¿De quién fue la feliza* idea de apalear así a nuestro idioma? No me lo digan: de las hembristas.

Otro tanto ocurre con presidenta. Si el o la que preside es presidente, ¿a qué tanto empeño en amplificar las diferencias entre sexos, si lo que persigue el feminismo es la igualdad? ¿Está acaso calienta* la que tiene calores? Lo mismo con capitana, edila, concejala, tenienta, bedela... ¿Qué será lo próximo? ¿Caba*, alféreza*, albañila*? ¿Por qué no otros adjetivos menos agradables? ¿Qué tal incordianta*, atroza*, inútila*, gilipóllasa* o, ya puestos, gilicoños*?

No digo que al revés no haya ocurrido; así, hay casos como modisto, que viene de moda, siendo que ya contamos con la palabra neutra modista, que describe lo mismo. Pocos, muy pocos ejemplos similares se podrán encontrar. Puedo comprenderlo (aunque no compartirlo), pues la profesión de modista ha sido siempre asociada a la mujer y la palabra debió de surgir de que alguien, no necesariamente siquiera un varón (quizá incluso la esposa del interfecto), quería recalcar para evitar confusiones que el modista era de sexo masculino, muy machote él. Déjenme recalcar esto: me parece tan aberrante jueza o presidenta como modisto y tan correcto abogada o bombera como prostituto (y hablo únicamente de la corrección del lenguaje, no de las condiciones laborales).

En general, en cambio, al varón no le importa lo más mínimo que sea adjetivado con una palabra acabada en -a: no hay transportistos* ni ordenanzos* ni guíos* ni falta que hace, porque ni la terminación ni el género determinan el sexo. Nadie presiona por que se use idioto* en vez de idiota para los varones. Son, por tanto, las ganas de marcar las diferencias entre sexos por parte de las talibanas de la lengua las que nos llevan a aberraciones como estas. Es hora de detener esta sinrazón.

Estreno de foro en 11-s.eu.org

En nuestra página web del 11-S no teníamos sección de comentarios. Con este propósito estábamos parasitando el foro de Psicopanadero, porque el soft de wiki usado para la web no soporta comentarios. Es un soft a medida que yo desarrollé usando la idea del Giki pero escribiendo el código desde cero. Sin embargo, la adición de una sección de comentarios con todo lo que ello conlleva parecía demasiado trabajo.

Ahora hemos abierto un foro para discutir sobre el 11-S; dentro de él, uno de los subforos hace de sección de comentarios para que se puedan discutir los artículos individualmente, con lo que queda por fin paliada esa falta.

Y más puzles

La colección de Simon Tatham está echando humo. Ahora son tres nuevos juegos más: Towers, Singles y Magnets.

Towers es un poco raro. Se trata de determinar la altura de unas torres (que son números enteros dispuestos en forma de cuadrado latino, de nuevo), una torre por casilla. Las pistas con las que contamos son unos enteros dispuestos alrededor del cuadrado, que indican el número de torres visibles horizontalmente desde el lado en el que se encuentra la pista en cuestión. Las torres más altas ocultan a las más bajas. Por ejemplo, en un casillero de 5×5, si en el lado izquierdo una de las filas tiene un 5 como pista, eso quiere decir que esa fila están los números del 1 al 5 en escala ascendente. Si pone un 3, hay muchas posibilidades y tendremos que valernos de más información para averiguarlo. Si pone un 1, entonces esa fila empieza por un 5, porque es el único que oculta a todos los demás. No me ha parecido interesante; me parece muy artificioso y poco intuitivo. Aunque eso mismo pensaba de Tents y al final sí que le vi la gracia.

Singles es algo más normal. Se nos muestra un cuadrado de n×n (no latino, esta vez) relleno con enteros de 1 a n, algunos repetidos en ciertas filas y columnas. Se trata de tachar todos los repetidos menos uno y dejar únicamente los no repetidos. Como condiciones adicionales, los números tachados no pueden estar adyacentes (arriba/abajo/izquierda/derecha, pero pueden estar en diagonal) y no puede haber grupos aislados de números sin tachar, es decir, se debe poder ir de cualquier número sin tachar a cualquier otro número mediante repetidos movimientos de una casilla cada uno hacia arriba, abajo, a la izquierda o a la derecha, o lo que es también lo mismo, los números no tachados tienen que formar un área conexa. Tiene su encanto.

Por último, en Magnets nos dan un tablero no necesariamente cuadrado, en el que se han dispuesto de antemano una serie de fichas rectangulares de 2×1. Cada una puede ser bien un imán, bien una ficha neutra. Se trata de colocar todos los imanes con su polaridad, respetando dos reglas básicas: una, que el número de signos positivos y el número de signos negativos de una fila o columna coincidan con las pistas que se nos dan (sin embargo, en algunas variantes no se nos dan todas: los que no tienen número no son cero, sino desconocidos), y otra, que no puede haber dos signos + juntos ni dos signos - juntos. Este es el más entretenido de los tres, a mi gusto.

Están todos disponibles para descarga para varias plataformas (Linux, OS X, Android, Windows, Palm) en el sitio de costumbre: http://www.chiark.greenend.org.uk/~sgtatham/puzzles/.

Mapa del RGB

Una imagen de 4.096×4.096 tiene 16.777.216 píxels. El número de colores RGB representables con 8 bits por componente (24 bits por color) es de 16.777.216. Esto quiere decir que en una imagen de 4.096×4.096 caben exactamente todos los colores posibles RGB de 24 bits.

Hay muchas maneras de distribuir los colores en la imagen. Esta es una, aunque está reducida y por tanto le faltan colores, pero enlaza a la verdadera de 4096×4096:

Aquí el programa PHP que la genera en formato TGA (la que hay para descarga ha sido convertida después a PNG con GIMP):

<?php
  $tgahdr = "\0\0\2\0\0\0\0\0\0\0\0\0\x00\x10\x00\x10\x18\40";
  $f = fopen($argv[1], "wb");
  fwrite($f, $tgahdr);

  for ($gl = 0; $gl < 16; $gl++)
    for ($r = 0; $r < 256; $r++)
    {
      $r2 = ($gl & 1) == 0 ? $r : 255-$r;
      $line = "";
      for ($gh = 0; $gh < 256; $gh += 16)
        for ($b = 0; $b < 256; $b++)
        {
          $b2 = ($gh & 16) == 0 ? $b : 255-$b;
          $line .= chr($b2) . chr($gh+$gl) . chr($r2);
        }
      fwrite($f, $line);
    }

  fclose($f);
?>

Respuesta de la FUB sobre las imágenes del Hale

Al poco de publicar la entrada relativa al cráter Hale, envié un email al Dr. Gerhard Neukum para tratar de confirmar la precisión de mis deducciones. Creía que lo más probable era que no recibiera contestación pero, para mi sorpresa, en esa me equivoqué. Hace unas horas tenía en mi programa de correo la respuesta. Este es el mensaje que escribí:

Dear sir,

Sorry to take your time in this matter that will probably sound so frivolous. Maybe you are already aware of the fact that some JPEG compression artifacts are being interpreted by some UFO enthusiasts as signs of civilization on the surface of Crater Hale. They argue that there can't be any JPEG compression in a TIFF image. As ignorant as the argument may sound about the transmission process and the bandwidth restrictions, it's always good in my opinion to debunk those arguments with full detail to avoid them to spread in our society.

I'm friend of skeptic organizations in Spain and I've already written an article in spanish debunking this myth. I'm also considering to translate it into English. The link is here:

http://orden-y-concierto.blogspot.com/2009/12/civilizacion-en-el-crater-hale.html

While working on this article, I noticed that for ellaborating the Hale crater images used as textures for the 3D renders, your team took the images from orbit 533, but only the green and blue channels, as the red channel was basically so dark that the JPEG compression destroyed virtually all detail. However, the image used as texture is showing a red channel with a detail that is obviously not seen in the original orbit 533's red channel.

The reason for writing to you is to ask whether that red channel was recomposed by scaling the nadir view, as I suspect.

I'd also like to ask how other images such as that of Echus Chasma are processed, since they exhibit JPEG artifacts with a size much greater than the image's resolution, and only when looking at the color information. I suspect that the original image was translated to YCbCr or similar, and then the luminance channel substituted with the data from the nadir view and the chrominance channels scaled appropriately. Is that correct?

Finally, I'd like to ask you for your permission to publish your response, in case you decide to reply.

Thanks in advance,

Pedro Gimeno

Me ha respondido Björn Schreiner, miembro del Departamento de Ciencias Planetarias y Teledetección que encabezan los Drs. Neukum y Jaumann. Para consternación mía, pese a que pido expresamente permiso para publicar el mensaje, no me ha dicho ni que sí ni que no, con lo cual no puedo asumir que me otorga permiso para hacerlo, así que únicamente puedo contar lo que me dice.

En su amable respuesta, en primer lugar confirma algo que ya sabíamos gracias a la página que describía la cámara: que los datos son enviados por la sonda a la Tierra comprimidos, debido a limitaciones en el ancho de banda de la transmisión. Dice de la compresión que es similar al JPEG, de lo que deduzco que no es necesariamente el mismo algoritmo exacto pero sí que se basa en la transformada discreta del coseno al igual que éste, y menciona que efectivamente se producen artefactos a consecuencia de dicha compresión. Habla de las imágenes que están disponibles en la página web de la ESA como «productos para la prensa», lo cual debería dejar definitivamente claro que están postprocesadas, y añade que son ofrecidas en formato TIFF para que estén disponibles con la mayor calidad posible, pese a que ya contienen artefactos debidos a la compresión para su transmisión a la Tierra.

Cuando descubrí esos artefactos de tamaño gigantesco en los canales de color del Echus Chasma, ya dije:

Esto nos indica que en esta imagen o se ha hecho un downsampling de crominancia enorme, probablemente de 6×6 u 8×8, o más probablemente, la ESA ha empleado la vista nadir para aportar datos de luminancia, ya que la resolución de dicha vista es sustancialmente mayor.

Schreiner confirma mi sospecha, aunque con un matiz menor. Efectivamente, utilizan la vista nadir para dar datos de iluminación y las vistas en tres colores para dar información de color, pero no usan el espacio de color YCbCr como yo creía, sino el IHS (que es otra forma de decir HSL). Puesto que hay diversas formulaciones incompatibles entre sí de este espacio de color y no me ha especificado la variante exacta que emplean (tampoco se lo he preguntado), no puedo deshacer su transformación para confirmarlo. Me ha intrigado un poco por qué no usan un modelo más ligado a la percepción lumínica del ojo humano como el YCbCr que usa el JPEG; la respuesta probablemente sea la velocidad de proceso. El propio visor de la superficie marciana hace eso mismo en tiempo real, así que parece una buena justificación.

Actualización: En este enlace se menciona precisamente la transformación IHS como herramienta para combinar imágenes pancromáticas de alta resolución con imágenes RGB de menor resolución, es decir, exactamente el proceso realizado por el equipo de la FUB: http://ij.ms3d.de/plugins/ihs_image_fusion.php (fin actualización).

También me comenta que a menudo, sustituyen el canal rojo, que es en realidad cercano al infrarrojo, por el canal nadir. Yo pensaba que eso haría que el color fuera más irreal, pero me aclara que este canal está pasado por un filtro con un color bastante cercano al rojo, con lo cual la pérdida no es muy grande. No me dice que este proceso haya sido aplicado a la imagen del cráter Hale específicamente, probablemente no lo recuerde (la imagen fue tomada en 2004 y supongo que procesada no mucho tiempo después) o no se haya preocupado en comprobarlo. En cualquier caso, sí que confirma que el proceso exacto que conjeturo que fue seguido para obtener esa imagen, sí ha sido utilizado en ocasiones. Sumen ustedes.

Termina con una frase que no creo que le importe que reproduzca aquí: «Certainly the artefacts mentioned above are no sign of civilization», o sea, «ciertamente los artefactos mencionados más arriba no son ningún signo de civilización».

El Wall Hugger de Robot Odyssey

Robot Odyssey es un juego educativo para adultos, sumamente interesante. Fue creado en 1984 por una compañía llamada The Learning Company e hicieron versiones para Apple II, TRS-80 e IBM PC.

La idea del juego es cablear unos robots utilizando circuitos lógicos para resolver rompecabezas. El juego se desarrolla en la ciudad imaginaria futurista de Robotropolis. El objetivo es abrirnos camino a través de las múltiples pantallas con ayuda de tres robots, que más adelante pueden ser cuatro si resolvemos un puzle extra. Los robots cuentan con cuatro detectores de paredes o bumpers, uno en cada dirección, que activan entradas cuando están en contacto con una pared; cuatro propulsores, también uno por dirección, que son activados por salidas; una pinza que tiene una entrada indicadora de que ha cogido algo y una salida con la que le damos la orden de activarse o no, y una antena para comunicarse con los otros robots, con su entrada y su salida. Además hay un interruptor de encendido/apagado, una batería que se va gastando mientras el robot está conectado y un «periscopio» por si queremos ver el exterior mientras el robot se mueve con el jugador en su interior. Las puertas lógicas con que programamos nuestros robots tienen un retardo de propagación de una unidad de tiempo, lo cual tiene que ser tenido en cuenta en algunos diseños.

Pantalla inicial de Robot Odyssey, donde nos encontramos por primera vez a los tres robots que nos ayudarán en la aventura (aquí vemos la versión para Apple II).

Para superar ciertas pantallas, por ejemplo, hay que conseguir que los robots activen sus pinzas en ciertos momentos, para coger un objeto al que no podemos acceder porque un robot centinela impide el paso a humanos. En otras, la estructura de la pantalla es lo bastante sencilla como para que, con un poco de imaginación, podamos diseñar un circuito sencillo para resolverla. Por supuesto, a medida que avanzamos pantallas aumenta la dificultad y pronto necesitamos más de un robot actuando coordinadamente para resolver ciertos puzles.

A. K. Dewdney ya habló de este juego en su sección Juegos de Ordenador de la revista Investigación y ciencia. Cuando leí el artículo, se me caía la baba y me quedé con unas ganas tremendas de verlo. Hoy, gracias a las maravillas del software libre e internet, existe una versión rehecha en Java llamada DroidQuest, disponible para descarga, escrita por Thomas Foote, en http://www.droidquest.com/. Por añadidura, el autor también ofrece la versión original de Apple II para descarga, así que quien disponga de un emulador puede también experimentar la sensación de jugar al juego original tal y como Dewdney lo mostró en su sección. Huelga decir que no lo solté hasta completarlo, superando así esa «cuenta pendiente».

Una característica interesante del juego es que hay unos chips disponibles, unos circuitos integrados que podemos programar para combinar varias operaciones en un solo circuito, simplificando con ello los diseños y ahorrando así puertas lógicas, lo cual es más interesante si tenemos en cuenta que hay un número limitado de ellas disponible. Algunos de los chips vienen ya preprogramados.

Interior de uno de los robots, con un cableado predefinido que incluye un chip preprogramado, en este caso el chip Wallhugger. También está a la vista uno de los objetos del juego, una llave.

El Wallhugger en particular es un chip que, al cablearlo como se ve en la figura, consigue que el robot vaya pegado a las paredes de una habitación, recorriéndolas en sentido antihorario. Tiene algunas limitaciones y, debido a ellas, en el juego tenemos pocas ocasiones para usarlo, pero su interés radica en la dificultad de su elaboración. De acuerdo con la documentación, el chip contiene 16 puertas lógicas y un chip más en su interior. El autor de DroidQuest dice en una página dedicada al chip:

El chip Wallhugger parece ser el Santo Grial del Robot Odyssey. De acuerdo con el juego original, fue diseñado con «16 puertas lógicas y un chip anidado». No tengo ni idea de cómo el Wallhugger fue creado solo con eso. Me encantaría averiguar cómo funciona. [1]

A mí también me dejó con el gusanillo, pero como siempre he sido de naturaleza curiosa, finalmente agarré el original de la versión de Apple y me puse a destriparlo.

El proceso requirió bastantes pasos. Primero, tenía que averiguar en qué posiciones del archivo .dsk se guardaban los datos de los chips. En esta parte encontré tanto facilidades como dificultades que lo hicieron laborioso, pero básicamente rutinario. Lo siguiente era realizar la ingeniería inversa del formato con el que se almacenan los circuitos del chip.

Esta parte fue, por supuesto, la más interesante. Mediante la creación de diversos chips, averigüé cómo se codificaban las entradas y salidas del chip, así como las puertas empleadas. Cuando alcancé una comprensión aceptable del formato, me lancé en pos del Wallhugger.

De esa manera, constaté que lo que decía la documentación era perfectamente correcto: efectivamente, en su interior contenía 16 puertas lógicas y un chip anidado. Aquí está el circuito principal, dibujado con el programa libre de diseño y simulación de circuitos TkGate (sí, ya sé que pronunciado en español suena muy mal), concretamente con la versión 1.8:

Esquema del circuito principal del chip Wallhugger (clic para ampliar)

Y a continuación, el esquema del chip anidado:

Esquema del chip anidado dentro del chip Wallhugger (clic para ampliar). En los flip-flops (FF) no está dibujada la salida derecha. Los LEDs a la salida de los flip-flops están solo como referencia.

Para poder realizar la simulación y probar el diseño en funcionamiento, tuve que crear un flip-flop R-S en TkGate que fuera compatible con el de Robot Odyssey. La idea era que cuando ambas entradas tuvieran un 1 lógico simultáneamente, el estado no variara, pues es la forma en que se comporta el RO. Aquí está el diseño que empleé:

Esquema del flip-flop usado para la simulación con TkGate (clic para ampliar)

¿Cuál es el principio de funcionamiento de este curioso chip? Lo primero que hay que observar es que, si conectamos el bumper izquierdo al propulsor superior, el bumper superior al propulsor derecho, el bumper derecho al propulsor inferior, y el bumper inferior al propulsor izquierdo, tendremos un robot que casi funciona, pues al menos es capaz de moverse en círculos en habitaciones con paredes convexas. El problema radica en que cuando nuestro robot recorre una pared con un ángulo cóncavo (de 270°), al terminarse ésta pierde el contacto y deja de propulsarse, quedándose parado. El chip incorpora la circuitería necesaria para actuar en ese caso y resolver el inconveniente.

Efectivamente, los cuatro bumpers están conectados a los cuatro propulsores a través de sendas puertas OR, es decir, que mientras la otra entrada de cada una de las puertas OR sea cero, nuestro robot se comportará igual que el robot seguidor de paredes convexas recién descrito.

Ahora, ¿cuándo ha de actuar y qué ha de hacer para poder salvar también ángulos cóncavos? Si el problema es que se queda parado, lógicamente lo que tendrá que hacer es moverse. La condición es simplemente que no haya ningún bumper activo, que es lo que provoca que nuestro seguidor de paredes convexas se pare. Esa condición es detectada por las tres puertas OR en cascada de la parte superior que van seguidas de un inversor. Cuando la salida del inversor se activa, quiere decir que no hay ningún bumper tocando una pared. Con esto se activan cuatro puertas AND que dan paso a la señal que moverá el robot. Veamos cómo.

Ahora que sabemos que en ese caso hay que moverse, queda la duda de hacia adónde. Puesto que se trata de continuar siguiendo la pared de la esquina que acabamos de dejar, habrá que moverse hacia ella. Nos interesa que el siguiente bumper entre en contacto con la siguiente pared, para que la parte seguidora de paredes convexas pueda seguir actuando. Por suerte, gracias a los retardos de propagación de las puertas, tras perderse el contacto con la pared anterior el propulsor habrá estado en marcha el tiempo suficiente como para que el robot haya sobrepasado la esquina, habiendo recorrido la distancia suficiente como para que, si vamos directamente 45° en diagonal en dirección a la esquina que acabamos de dejar, acabemos tocando la nueva pared y no la antigua de la que venimos.

Por tanto, se trata de moverse en diagonal hacia la esquina que acabamos de dejar. ¿Cómo conseguimos eso? Ahí es donde entra en juego el chip anidado.

El esquema de este chip está diseñado de la siguiente forma. Hay cuatro flip-flops, cuatro entradas y cuatro salidas. Las cuatro entradas vienen directamente de los bumpers. Cada bumper activa un flip-flop y pone a cero los otros tres (si no hay conflictos, claro). Es decir, el set del primer flip-flop viene del primer bumper y el reset es el OR de los otros tres, y lo mismo con los demás. En resumen, el chip está diseñado para recordar cuál fue el último bumper activo. Cuando estamos tratando de doblar una esquina de 270° y perdemos el contacto, tenemos la garantía (o eso presumimos) de que en el último instante justo antes de perderse el contacto solo había un bumper activo, por lo tanto no hay que preocuparse de los conflictos. (Cuando hay paredes muy próximas, esto podría no cumplirse, y esa es una de las limitaciones de Wallhugger: debe tener suficiente espacio para moverse sin que, por ejemplo, dos bumpers opuestos toquen dos paredes a la vez).

La línea de puesta a uno de cada flip-flop es retardada mediante tres puertas OR, por un motivo que no he llegado a entender. Quizá sea porque de lo contrario, pulsos muy cortos del bumper podrían perderse antes de que la señal de puesta a cero de otro bumper la desactive, aunque no le acabo de ver el sentido. Parece, en cualquier caso, que el número de retardos es uno más que los que se producen en la señal reset, por lo que la intención parece en todo caso que el set llegue siempre en último lugar.

Tenemos entonces un chip que recuerda el último bumper activo antes de perderse el contacto y queremos usarlo para, cuando se pierde el contacto, movernos hacia la esquina que queremos doblar. Veamos cómo. Si el bumper derecho era el último activo cuando se perdió el contacto, entonces estaba en marcha el propulsor inferior, por tanto la esquina que acabamos de dejar queda debajo y a la derecha del robot, y es hacia ahí donde queremos movernos, por lo cual tendremos que activar los propulsores izquierdo y superior. Extendiendo el razonamiento a las cuatro direcciones, el bumper superior activará los propulsores inferior e izquierdo, el izquierdo los propulsores inferior y derecho, y el inferior los propulsores derecho y superior.

Visto desde el lado de los propulsores, en ausencia de señal de bumpers, el izquierdo se activará cuando el último bumper activo fue el superior OR el derecho, etcétera. Esto justifica las cuatro puertas OR restantes, lo que concluye la totalidad del chip.

Si alguien quiere conocer el formato de los chips del Robot Odyssey y la forma de almacenarse en los archivos .dsk, aquí hay un enlace donde pueden consultarlo (en inglés): [2]. Está en inglés porque lo escribí para los miembros del grupo de Yahoo de DroidQuest. También incluye una explicación del funcionamiento, aunque más somera que la dada aquí, y el archivo TkGate con los esquemas aquí presentados listos para usar en la simulación. Aviso de que el enlace está en un directorio temporal, que puede ser movido cuando actualice mi página personal y lo coloque en la que será su ubicación definitiva. Cuando así lo haga, procuraré recordar actualizar esta entrada en consonancia, pero si alguien enlaza a ese directorio temporal directamente, debe tenerlo en cuenta.

Referencias

[1] http://mysite.verizon.net/thomasfoote/DQ/id60.htm
[2] http://www.formauri.es/personal/pgimeno/temp/RO/wallhugger.php

Unequal Adjacent y Keen agregados a la colección de Simon Tatham

Han salido hace muy pocos días dos nuevos juegos de la colección de puzzles de Simon Tatham. Ambos están basados en la misma idea de los cuadrados latinos en que se basan el Sudoku y el Futoshiki. Uno de ellos es un nuevo programa: se llama Keen y es un clónico de un juego conocido como KenKen, en el que además de cumplir la restricción de que se ha de componer un cuadrado latino, hay que cumplir que la operación aritmética indicada realizada entre los números contenidos en los rectángulos coincida con el número indicado; por ejemplo, 3- quiere decir que la diferencia de los números de ese rectángulo debe ser 3, y 24× que el producto debe ser 24. He jugado, pero no me ha enganchado mucho. El otro es una variante que se ha añadido a uno ya existente, el Unequal, clónico del Futoshiki. La variante consiste en que en vez de signos de desigualdad, hay unas barras entre algunos de los números, que indican que la diferencia entre las casillas es una unidad. A diferencia del Unequal convencional, las casillas que no tienen barra no son desconocidas, sino que se sabe que tienen una diferencia mayor que una unidad. Este sí que engancha, aviso.

Para quien no conozca la colección, advierto de que es peligrosa. Vicia demasiado. En particular, contiene un buscaminas cuyos tableros son siempre resolubles (no dependemos sólo de la suerte, como sucede en el convencional). Es el único buscaminas donde he visto un 8. Hay otras joyas que invito a descubrir, como el frustrante y divertido Inertia, el Net con sus conexiones, el Untangle con sus nudos o el Map, basado en el teorema del mapa de cuatro colores. La colección se caracteriza por una propiedad: todos los juegos generados son resolubles y en muchos (digamos en los que es posible) la solución es única.

Ya no me siento tan solo. Bueno, corrijo, me siento más solo. http://www.perspicalia.com/post/admito-mi-derrota. Todavía resisto a ambas cosas: móvil y féisbuc. Y también a tuíter.

Autómatas celulares

Es un tema tan fascinante como inevitable. Como siempre habrá lectores que no hayan oído hablar del tema, este artículo será la preceptiva introducción.

Un autómata celular consiste en un casillero en el que cada casilla (también llamada celda o célula) puede estar en un estado determinado, y una regla de transición que determina cuál será el próximo estado de cada casilla en función de su estado actual y del estado de las casillas vecinas. No está limitado a retículas cuadriculadas ni bidimensionales, pero son las más comunes. Así, los píxels de una pantalla pueden servir para representar un autómata celular, representando el estado de cada casilla como el color de un píxel (o varios, si hacemos zoom). Normalmente se parte de un casillero previamente relleno de alguna forma, ya que los casilleros en que todas las casillas tienen el mismo estado suelen ser muy monótonos.

En los autómatas celulares, es importante que toda la transición del estado suceda «de golpe», esto es, para programarlo debemos tener en cuenta que no podemos modificar el estado de una celda y después usar la versión modificada como vecina de la siguiente para calcular su estado, sino que la vecina debe tomar el estado original. Una forma sencilla de implementar esta regla es usar una matriz con el mismo tamaño que la matriz donde guardamos los estados e ir depositando los nuevos estados en esa otra matriz. Cuando acabamos de calcularlos todos, trasladamos los nuevos estados a la matriz original y/o a la pantalla. A cada transición de estados se le suele llamar «tick» o «tic», porque es como el tic-tac de un reloj figurado. También se emplea el término «generación» en el mismo sentido, como si las casillas o células fueran organismos que van teniendo descendencia.

Los autómatas celulares lineales (de una dimensión) se suelen dibujar en dos dimensiones, usando la segunda de histórico. Esto es, en cada línea se dibuja el estado completo de todas las casillas, en la inmediatamente inferior se dibuja el tick siguiente, y así sucesivamente.

Las reglas de transición pueden ser cualesquiera que tengan en cuenta las casillas vecinas. Hay quien no considera autómatas celulares los que tienen reglas asimétricas, es decir, las que producen resultados diferentes según la orientación en la que esté el dibujo original. Lo sean o no, hay conjuntos de reglas asimétricas interesantes, aunque no las vamos a tratar aquí, al menos por ahora. Hay algunos casos de autómatas en los que se analizan bloques completos de varias casillas a la vez, produciendo cambios simultáneos en varias casillas a la vez. De nuevo, hay quien no los considera autómatas per se, pero también son interesantes.

Los casos más comunes de reglas de transición son los que se rigen por el estado de las cuatro (arriba, abajo, izquierda, derecha) u ocho (incluyendo diagonales) casillas vecinas a una dada, a veces incluyendo a la casilla misma, en una retícula cuadriculada. Entre los autómatas de dos estados, es común contar el número de casillas vecinas que hay en uno de dichos estados y determinar el siguiente en función de dicho número.

Veamos un par de ejemplos. El autómata de Edward Fredkin considera un entorno de nueve casillas y la regla de transición es la siguiente: el nuevo estado será un 1 si el estado actual es 1 y el número de casillas que rodean a la actual que están en estado 1 es par, o bien si está a 0 y el número de casillas que estan a 1 es impar; será 0 en caso contrario. La regla equivale a sumar los valores de las nueve casillas incluyendo la central, asignando un 1 si la suma es impar y 0 si no lo es. Curiosamente, con esta regla, cada figura acaba multiplicada por 9 al cabo de unos cuantos ticks. Aquí vemos el estado inicial y 32 estados posteriores del autómata de Fredkin:

Autómata de Fredkin en acción, tomando como estado inicial un rótulo con la palabra Fredkin. Al cabo de 32 iteraciones, se ha multiplicado por 9.

El otro ejemplo que vamos a considerar es el llamado Juego de la vida de J.H. Conway. La regla de transición es: si una célula está «muerta» (estado 0), estará «viva» (estado 1) en la generación siguiente si tiene a su alrededor (sin contarse a sí misma) exactamente tres casillas «vivas». Si está «viva», entonces estará «viva» en la próxima generación únicamente si tiene dos o tres vecinas «vivas». En otro caso, «morirá». Esto se suele indicar con la notación B3/S23 (la B, de Born, indica el número de vecinos necesario para que la casilla pase a estado 1 cuando es 0, en este caso 3, y la S, de Survive, el número de vecinos necesario para que la casilla pase a estado 1 cuando es 1, en este caso 2 y 3).

Con esas sencillas reglas basta para que se plantee todo un abanico de cuestiones con respuestas complicadas. Típicamente, a partir de una configuración cualquiera al azar no muy grande, la población fluctúa durante bastantes generaciones y termina en un estado estable en el que se ven patrones estáticos y otros oscilantes con periodo 2, y ocasionalmente algún otro. Por ejemplo, la siguiente configuración:

que tiene inicialmente 58 celdas «vivas», tras 1.235 generaciones evoluciona a la siguiente figura (clic para versión completa):

con una «población» de 228 celdas que ya permanece constante durante el resto de generaciones. En el curso de esas 1.235 generaciones, ha liberado cuatro «deslizadores». Un deslizador es una configuración cíclica que va cambiando de manera que tras cierto número de generaciones, se repite la misma forma pero está desplazada. El más común, en cuanto a que aparece espontáneamente con facilidad, es este de cuatro estados y que en todo momento tiene cinco células «vivas»:

Por supuesto, puede aparecer en cualquier posición, ya que el Juego de la Vida es simétrico. Obsérvese cómo tras cuatro generaciones, tiene la misma forma original pero está una casilla desplazado, hacia arriba y hacia la derecha en este caso.

Esta tendencia de las configuraciones al azar a alcanzar la estabilidad poblacional con el tiempo, le hizo a Conway conjeturar que no existía ninguna configuración que creciera indefinidamente, y ofreció un premio de 50 dólares a quien encontrara una que lo hiciera. El premio fue ganado por Bill Gosper, quien encontró una configuración cíclica que emitía un deslizador cada 30 generaciones y, por tanto, la población del conjunto siempre crecía, demostrando así falsa la conjetura de Conway. El cañón lanza-deslizadores, como se le conoció, tenía este aspecto:

Cañón lanza-deslizadores de Bill Gosper, en pleno proceso (se muestran dos deslizadores ya generados).

Hoy en día se conocen muchas configuraciones que crecen siempre. También se sabe que el Juego de la Vida es Turing-completo, es decir, que es posible crear una configuración tal que emule cualquier cálculo que un ordenador es capaz de realizar (otra cosa es la velocidad). El Juego de la Vida ha sido profusamente estudiado y hay muchas webs recomendables a quien quiera profundizar sobre él; valgan como ejemplo [1] (un léxico) y [2] (la entrada de la Wikipedia inglesa sobre este autómata).

Hay otro tipo de regla que tiene como caso particular el Juego de la Vida. Se trata de Generations. La idea es la misma, pero en lugar de morir inmediatamente, las células se hacen «viejas». Para definir la regla hace falta especificar, además de los supervivientes y neonatos, el número total de estados del autómata. Por ejemplo, 345/2/4 indica que hay cuatro estados. Si una célula está en el estado 1 y el número de células vecinas de una dada, sin contar ella misma, en el estado 1 es de 3, 4 ó 5, entonces esa celda continuará en el estado 1 en el siguiente tick. Si está en el estado 0 y está rodeada exactamente de dos células en el estado 1, entonces pasará al estado 1. En cualquier otro caso, si su estado es 1 pasará a ser 2 (envejecerá). Si es 2, independientemente de las células que la rodeen, pasará a 3 en el tick siguiente, y si es 3, pasará a 0 (muerte final). Si ya era 0, se quedará igual. La regla recién descrita recibe el nombre de Star Wars y fue creada por Mirek Wojtowicz. Obviamente, el Juego de la Vida se escribiría 23/3/2 en notación Generations. El autómata de Fredkin se escribiría 02468/1357/2 en esta notación.

La regla /2/3 de Generations es digna de mención. Tiene tres estados; toda célula en el estado 1 pasará a 2 en la generación siguiente, ya que no hay indicación de ningún número de estados con el que sobrevivir (mantenerse en 1), y después a 0. Si una célula muerta está rodeada de dos células en estado 1, pasará al estado 1 en la próxima generación. Al autómata recién descrito se le llama Brian's Brain, descubierto por Brian Silverman, y es muy entretenido contemplarlo cual si se tratara de una pecera. Aquí hay una versión animada, cortesía de Wikipedia: [3].

Por supuesto, Generations no es la única familia de reglas existente. Hay un autómata celular llamado Wireworld, descubierto también por Silverman, que modela el comportamiento de los circuitos electrónicos. Sus reglas, aun siendo muy parecidas a las de Generations, contienen un estado extra que permanece siempre inmutable. Digamos que es un Generations con máscara.

Así, Wireworld es un conjunto de reglas con cuatro estados. El primer estado, el 0, permanece siempre inalterado. Al estado 1 se le llama «cable». Al estado 2 se le llama «cabeza de electrón», y al 3 «cola de electrón». Las reglas son las siguientes: si una célula cable tiene a su alrededor exactamente 1 ó 2 cabezas de electrón, entonces pasará a ser cabeza de electrón en la generación siguiente; de lo contrario permanecerá cable. La cabeza de electrón pasará siempre a ser cola de electrón, y la cola de electrón pasará siempre a ser cable. Es, por tanto, el equivalente a la regla /12/3 en Generations, con la adición de un estado inmutable.

Hay otros juegos de reglas en los que se realizan operaciones aritméticas con los estados. Uno de los más llamativos es la máquina Hodge Podge (que fue traducida por la revista Investigación y Ciencia como «máquina batiburrillo»), diseñada por M. Gerhard y H. Schuster. Pese a que se le llame máquina, es un autómata celular. En realidad, es toda una familia de reglas, ya que se rigen por cuatro parámetros: el número de estados y varios «niveles de infección». Si n es el número de estados, se define una célula como «sana» si está en el estado 0, como «enferma» si está en el estado n-1, y como «infectada» si está en cualquiera de los estados intermedios. La regla para una célula «sana» es pasar a un estado dado por ⌊E/r_e⌋ + ⌊I/r_i⌋, donde ⌊x⌋ indica la parte entera de x, E es el número de células enfermas que rodean a la actual, e I es el número de células infectadas. r_e y r_i son dos de los parámetros que definen el autómata.

Para una célula «infectada», la regla es la siguiente: su próximo estado será la parte entera de la media de los estados de las células infectadas que la rodean incluyéndose a sí misma, más un parámetro de infección g. El valor se trunca para que no exceda de n-1. La regla para una célula «enferma» es la más sencilla: pasará siempre al estado «sana» en la siguiente generación. Los cuatro parámetros son, pues, n (número de estados), r_e (relación de infección para células enfermas), r_i (relación de infección para células infectadas) y g (velocidad de progreso de la enfermedad). Esos parámetros, junto con el tipo de entorno, que no necesariamente es de ocho células, determinan una máquina concreta.

Pese a lo complicado de las reglas, es todo un placer verlas actuar, generando unos bellos patrones en espiral característicos de una reacción catalítica heterogénea (el autómata fue diseñado con el fin de emular dicha reacción). Aquí hay una versión en Flash: [4]. Hace falta algo de paciencia para ver las espirales formarse; a veces se desvanecen antes de cobrar fuerza. Aquí se ilustran versiones ya desarrolladas de patrones al azar usando diferentes entornos: [5]

Hay muchos otros conjuntos de reglas posibles, pero no vamos a detenernos en más. En vez de eso, vamos a presentar dos programas que reconocen muchos juegos de reglas y nos permiten dibujar patrones iniciales o probar patrones al azar. Uno de ellos es Mirek's Java Cellebration, MJCell (versión 1.51 a fecha de escritura de este artículo), escrito en Java, como su nombre indica, que es una versión del Mirek's Cellebration (MCell) para Windows. Una ventaja de la versión Java es que se puede ejecutar en línea; otra, que el código fuente está disponible, aunque la licencia es incierta. El otro programa es Golly, con unos pocos algoritmos y patrones menos que MJCell, pero con una velocidad realmente pasmosa. Golly hace uso de un algoritmo que utiliza tablas «hash» para reconocer patrones ya visitados, y hacerlos evolucionar a muchas veces la velocidad normal. Las tablas requieren gran cantidad de memoria para conseguir su velocidad; he llegado a llenar los 3 Gb de memoria que permiten las aplicaciones de 32 bits en Linux (algún día antes de 2038 migraré mi Debian a 64 bits, ¡lo prometo!). Esa memoria sólo hace falta para conseguir la velocidad máxima, pero no hace falta tanta para ver los patrones a una velocidad de vértigo, pudiendo ver pasar literalmente trillones de generaciones en segundos para autómatas simples, o miles de millones en minutos para otros no tan simples. Por ejemplo, podemos ver recrearse la Esfinge de William R. Buckley, una máquina autorreplicante basada en el complejo autómata original de 29 estados de John von Neumann, al que lleva unos 40 minutos completar las 261.903.042.739 generaciones que requiere construir una copia e insuflarle vida. O podemos ver la computadora de primos diseñada en Wireworld de Mark Owen, mostrando primo tras primo en su flamante display. O podemos ver en funcionamiento la máquina de Turing de tres estados de Paul Rendell, implementada mediante un patrón del Juego de la Vida.

Otra ventaja de Golly en comparación con MJCell es su universo virtualmente ilimitado. En MJCell hemos de definir de antemano el tamaño de la cuadrícula y no se le dan bien las cuadrículas muy grandes, pero en Golly, los patrones se extienden «hasta el infinito y más allá», por lo que no tenemos que sufrir por si el patrón llega al borde. La licencia es GPL y está también disponible en versión binaria para Linux, Mac y Windows.

Referencias

[1] http://www.bitstorm.org/gameoflife/lexicon/
[2] http://en.wikipedia.org/wiki/Conway's_Game_of_Life
[3] http://upload.wikimedia.org/wikipedia/en/a/a7/Brian's_brain.gif
[4] http://www.galaxygoo.org/blogs/2006/07/hodgepodge_machine.html
[5] http://www.vbaccelerator.com/home/VB/Code/vbMedia/Algorithmic_Images/Hodge_Podge/article.asp

El Hexadecimal ha sido patentado - Quiero más

(English version below)

Recientemente, la lista de correo de GMP recibió una invitación a los desarrolladores para contribuir en el recientemente creado proyecto Peer-To-Patent Australia, porque Hewlett-Packard ha enviado una solicitud de patente que podría estar relacionada con el proyecto.

Al buscar en Google el título de la patente (Binary representation of number based on processor word size), me he encontrado, para mi sorpresa, con que ya estaba concedida en Europa y EE.UU. Pero mi sorpresa ha sido aún mayor tras leer la patente.

El «invento» cubre el almacenamiento de números que se pretende representar en base B, como números en base Bⁿ, a razón de un dígito por palabra, donde Bⁿ es la mayor potencia entera de B que cabe en una palabra de procesador. Por ejemplo, para almacenar un número que se pretende representar en decimal en un procesador de 16 bits, la idea es guardar el número en base 10.000, ya que 10⁴ es la mayor potencia entera de 10 que puede representarse en una palabra de 16 bits (10⁵=100.000 se sale de rango).

Esa resulta ser la misma idea que usé por simplicidad para el contador de ciclos de mi depurador de BF (brfd 1.0) en 2001, al que le llamé «Petradecimal» (búsquense las apariciones de «Petra» en el código). En realidad, sólo puedo demostrar 2006 como fecha inferior, porque esa es la fecha en la que está archivado en la Wayback Machine, que recientemente fue admitida como prueba por un tribunal de EE.UU. Aquí está el enlace a la Wayback Machine: [1]. En la lista de correo de GMP dije por error que fue en 2005 cuando lo usé, pero esa era en realidad la fecha de una versión posterior, la 1.0.1, presentada en la entrada anterior. El tiempo pasa tan rápido...

Lo peor es que se puede argumentar que la patente cubre la conversión de/a hexadecimal en procesadores de 8, 16, 32 y 64 bits, cuando dicha conversión se realiza en bloques de una palabra de procesador cada uno.

Sin embargo, lo que quiero decir no es que esta patente no debería haber sido concedida.

Lo que está haciendo Peer-To-Patent es evitar que se patenten ciertos inventos que cuentan con precedentes, de manera que la calidad general de las patentes concedidas mejore, pero no protege contra la trivialidad. Sin embargo, el mundo no necesita patentes de software de mejor calidad. Eso es simplemente un paso que disfraza a las patentes como algo marginalmente aceptable, disimulando el verdadero problema. El mundo necesita llenarse de patentes triviales y de baja calidad, para que más y más gente se dé cuenta de cuán ridículo es el sistema de patentes aplicado al software y por qué las patentes y el software necesitan divorciarse, y así todos juntos pidamos ese divorcio a gritos.

El proyecto Peer-To-Patent está ahí para ayudar a los de la oficina de patentes, gente dedicada a tiempo completo a investigar patentes, porque incluso con su dedicación a tiempo completo, fácilmente se les puede escapar identificar algo que ya está inventado. Esto por sí mismo expone una buena parte de lo que está mal con las patentes de software. Si los investigadores dedicados a tiempo completo no pueden saber con seguridad si un invento ya está inventado, ¿cómo puede, digamos, un programador de software libre estar seguro de no pisar una mina en forma de patente mientras está haciendo su trabajo creativo diario? Y al margen de si el programador hace o no un trabajo de investigación todavía más cuidadoso que los de la oficina de patentes, hay una posibilidad de que la idea sea patentada después de todas formas, como ha sido mi caso. Tengo suerte en esta ocasión de ser capaz de demostrar que 2006 es la fecha de mi «invento». ¿Qué pasaría si no pudiera?

La existencia de Peer-To-Patent es, por tanto, un síntoma de que el sistema de patentes no funciona cuando se aplica al software, pero no el único. La existencia de la Open Invention Network para desarrollar una biblioteca de patentes encaminadas a la defensa contra los juicios por patentes, y la propuesta de un seguro contra patentes, significan que estamos en una situación en la que estamos defendiéndonos de la ley en lugar de ser protegidos por ella. Mejorar la calidad de las patentes NO es la solución. Acabar con las patentes de software, por otro lado, sí lo es. Las patentes de software deben ser eliminadas, no mejoradas.

Referencias

[1] http://web.archive.org/web/*/http://www.formauri.es/personal/pgimeno/prog/brfd10.zip