Anrokku, un videojuego tipo puzzle

Anrokku es un juego de puzles que he programado estas semanas. Las reglas son simples, somos una ambulancia y tenemos que salir del parking debido a una emergencia. Desafortunadamente el parking es un caos y los coches bloquean la salida. Tu labor es ir moviendo los coches para lograr que la ambulancia salga del parking. Y cuantos menos movimientos hagas mejor.

En el menú principal podremos seleccionar a cuál de los 20 niveles queremos jugar. No podremos jugar a todos a la vez, es necesario habernos pasado los niveles anteriores para desbloquear el siguiente.

Ya en el juego tenemos que ir arrastrando los coches con el ratón para que la ambulancia pueda irse por la derecha. El juego está programando en Python 2.7 usando GTK. El renderizado está hecho en un GtkDrawingArea donde he usado Cairo. ¿Quiéres jugar? El juego completo es gratuito y open source bajo la liencia MIT en GitHub. No obstante, puedes descargar el archivo ZIP con el juego desde este enlace.

Descargar Anrokku

Después de descargar y descomprimir el archivo. Ejecuta el fichero main.py haciendo doble click o desde la terminal:

python2 main.py

¡Quiero ver muchas pantallas como esta!

 El juego almacena los récords obtenidos en cada nivel. Puede ser interesante repetir los niveles para hacerlo en el menor número posible de movimientos. En el primer nivel he conseguido ganar en 32 movimientos, ¿alguien se atreve a superarme?

loading...

Mandando paquetes ICMP ECHO personalizados con Python

Estos días he estado experimentando un poco con una característica de las redes. En concreto he intentando ver si era posible lanzar un paquete a la red cuyo origen es una dirección broadcast y el receptor, al mandar la respuesta, lo hiciera sin darse cuenta a todos los equipos de la red. Esto en efecto podría usarse para inutilizar una red por Denial of Service.

ICMP ECHO

La prueba la he hecho con un ICMP ECHO pero podría hacerse con otros protocolos también, como DHCP.

Un ICMP ECHO es lo que hace el famoso comando pingping6 (en IPv6). Se trata de un protocolo de la capa de red (capa 3 en TCP/IP). ICMP dispone de varias operaciones para funcionar correctamente (Internet Control Message Protocol, controlar la red) pero la mayoría de ellas no se utilizan. Una que sí se usa es el ECHO, que permite mandar una información a un host y el host nos tiene que devolver lo mismo.

¿Cómo sabe a donde tiene que enviar la respuesta? A la IP de origen del primer paquete claro, pero ¿y si mentimos? ¿Y si le ponemos que la IP de origen es la IP de broadcast? Supuestamente, enviaría la respuesta a todos los demás hosts de la subred.

Script en Python

Para poder hacer los datagramas IP personalizados y poder mentir, usé raw sockets. Estos solo me han funcionado en Linux. El código es muy simple, la parte que más me costó fue el checksum pues las operaciones con bytes en Python son un poco curiosas, no existiendo el tipo byte pero si bytes.

import socket
import struct
import random
import binascii
import sys
import functools

ICMP_CODE = socket.getprotobyname("icmp")
ICMP_ECHO = 8
IP_SRC = "192.168.0.255"
IP_DST = "192.168.0.255"

def main():
    s = socket.socket(socket.AF_INET,socket.SOCK_RAW,socket.IPPROTO_ICMP)
    s.setsockopt(socket.SOL_IP,socket.IP_HDRINCL,1)
    s.setsockopt(socket.SOL_SOCKET, socket.SO_BROADCAST, 1)
    packet_id = int((100000* random.random()) % 65535)
    packet = create_packet(packet_id)
    #print ("Size of packet: "+str(sys.getsizeof(packet)))
    s.sendto(packet,(IP_DST,0))

def create_header(data):
    version = 4 # IP version
    ihl = 5 # Numero de Bytes
    DF = 0
    Tlen = sys.getsizeof(data) + 20 # Longitud del datagrama
    ID = 1774 # ID de paquete
    Flag = 0 # Opciones
    Fragment = 0 # Numero de fragmento
    TTL = 128 # Tiempo de vida
    Proto = socket.IPPROTO_ICMP # Protocolo de los datos
    ip_checksum = checksum(data) # Checksum de los datos
    SIP = socket.inet_aton(IP_SRC) # Source IP address
    DIP = socket.inet_aton(IP_DST) # Destination IP address
    ver_ihl = (version << 4) + ihl
    f_f = (Flag << 13) + Fragment
    ip_hdr =  struct.pack("!BBHHHBBH4s4s", ver_ihl,DF,Tlen,ID,f_f,TTL,Proto,ip_checksum,SIP,DIP)
    return ip_hdr

def checksum(msg):
    flag = False
    suma = 0
    for byte in msg:
        if not flag:
            suma += (byte << 8)
        else:
            suma += byte
        flag = not flag
    resto = suma & 0xFFFF0000
    resto = resto >> 8
    suma += resto
    check = (~suma) & 0x0000FFFF
    return check

def create_data(id):
    header = struct.pack("bbHHh", ICMP_ECHO, 0, 0, id, 1)
    data = b"42"
    header = struct.pack("bbHHh", ICMP_ECHO, 0, socket.htons(checksum(header+data)), id, 1)
    return header + data

def create_packet(packet_id):
    data = create_data(packet_id)
    header = create_header(data)
    return header+data
while True:
    main()

Espero que a alguien le resulte interesante el código. Es un ejemplo de como generar datagramas sin la ayuda del sistema operativo. Además es importante saber que este tipo de programas solo pueden ejecutarse como root. Yo, por las pruebas que pude hacer, creo que los sistemas operativos actuales no son tontos y este tipo de ataques ya son conocidos. No pude capturar con Wireshark ninguno que fuese respuesta a broadcast, mientras que si la IP, aun siendo falsa, parecía real, sí que podía capturarla.
 

La belleza de MIPS

Todos los ordenadores, móviles y en general, cualquier dispositivo que lleva software necesita un procesador. Los procesadores se agrupan por familias, familias de procesadores que se programan igual, en un lenguaje llamado ensamblador. La más popular es Intel x86, presente en cualquier PC y en algunos móviles, tablets y servidores. Pero no voy a hablaros hoy de x86, ni de ARM, sino de MIPS. El ensamblador hecho bello. Adentrémonos en este mundo. Si nunca has visto ensamblador, este es tu momento. Si ya lo has visto, quizá te apetezca recordar algunas cosas.

MIPS, reinventemos la rueda… pero bien

Los orígenes de la arquitectura MIPS se remontan a 1981 cuando John L. Hennessy y su equipo de la Universidad de Stanford buscan implementar un procesador lo más simple posible. Al contrario que en las arquitecturas de tipo CISC lo que se busca en una de tipo de RISC como MIPS es definir las instrucciones más simples posibles y optimizar estas. ARM es otro ejemplo de arquitectura RISC. Para optimizar aún más, MIPS hace un uso intensivo de la segmentación.

Los procesadores MIPS ganaron popularidad rápidamente. Fueron usados por Silicon Graphics (SGI) para sus workstations con sistema operativo IRIX. Allí fueron usadas en estudios de Hollywood, centros científicos, etc En su máximo esplendor estas máquinas acogieron grandes avances, como la invención de OpenGL y del sistema de archivos XFS.

Esta relación de MIPS con el mundo multimedia le hizo popular entre las consolas. La Nintendo 64, la PlayStation 2 o la PSP llevan procesador MIPS.

Finalmente MIPS ha entrado en cierta decadencia. SGI cerró y las consolas decidieron apostar por otro tipo de procesadores. Sin embargo MIPS sigue vivo. Es usado en routers y algunos móviles. Existe Loongson, una variación de la aquitectura MIPS usada en China. Incluso ha habido placas estilo Raspberry Pi con MIPS, como por ejemplo, la Creator CI20.

Cuatro principios del diseño

Estos principios se aplican en MIPS.

  • La simplicidad favorece la regularidad
    • La regularidad facilita la implementación
    • La simplicidad mejora el rendimiento a menor coste
  • Cuanto más pequeño más rápido
  • Mejorar en lo posible los casos más frecuentes
  • Un buen diseño requiere buenas soluciones de compromiso

Tres tipos de instrucciones

La belleza de MIPS se basa en su diseño, claro, conciso y con pocas excepciones. Empecemos por lo básico, en MIPS todas las instrucciones son de 32 bits y son de una de estas tres categorías:

  • R, operan con tres registros
  • I, operan con dos registros y una constante
  • J, operan con una dirección de memoria

32 registros de 32 bits

En MIPS existen 32 registros. Bastantes si los comparamos con x86 de Intel. ¿Qué es un registro? Es donde se guardan los datos que se van a necesitar en las operaciones. Como si fueran cajas donde podemos guardar cosas, las cajas de la CPU. Salvo un par de ellos especiales, en realidad todos son iguales, no obstante, por convenio ciertos registros se usan para unas cosas y otros para otras.

Tomado de Wikipedia

Operaciones básicas

Las operaciones básicas son la suma, la resta, la suma inmediata, los desplazamientos, las operaciones lógicas and, or y nor, las operaciones de carga y guardado en memoria, el comparador menor que, los branch y los saltos. Y ya esta. Todo lo demás se implementa mediante pseudoinstrucciones, es decir, instrucciones que el ensamblador convierte en varias instrucciones básicas. Muchos se habrán sorprendido que no haya operación de multiplicar. O que no haya move. O que solo se pueda comparar con menor que. Todas esas cosas las podemos hacer pero debemos ser conscientes de que son pseudoinstrucciones y MIPS en realidad no tiene esas operaciones registradas. Veamos un ejemplo de código MIPS. Primero tenemos el código en C equivalente, y después el código MIPS.

a =  b + c + 5
# a en $s0, b en $s1, c en $s2
add $s0, $s1, $s2 # Sumamos $s1 + $s2 y ponemos el resultado en $s0
addi $s0, $s0, 5 # Sumamos a $s0 la constante 5 y dejamos el resultado en $s0

Por norma general en MIPS cuando queramos usar una constante en vez de un registro bastará con poner una i (de inmmediato) al final. Así en vez de usar una instrucción de tipo R usaremos una de tipo I.

Branch y jump

La magia de los computadores reside en que son capaces de tomar decisiones. Pueden ejecutar bucles y evaluar condiciones. En ensamblador este tipo de cosas se hacen con saltos. Sin embargo MIPS incluye dos tipos distintos de saltos.

Los branch evalúan condiciones y saltan en caso de que se cumpla a una posición del código N bytes por arriba o por debajo de la dirección de memoria actualmente almacenada en $ra.

Los jump saltan a una dirección de memoria de forma absoluta. Como MIPS es de 32 bits y las instrucciones también son de 32 bits resulta evidente que no es posible saltar a cualquier dirección de memoria, no al menos en una simple instrucción. Los bits que faltan, los más significativos se dejan a los mismos que había en donde se hizo el jump.

Esto parece muy complicado pero veamos que no lo es tanto en la práctica. Como recomendación, usa jumps para saltar a subrutinas y usa branch para hacer ifs y bucles.

int x = 5;
do{
    x--;
}while(x!=0);
# x en $s0
.text
main:
    addi $s0, $zero, 5 # Cargamos 5 a $s0
    # es equivalente a la pseudoinstrucción li $s0, 5
bucle:
    addi $s0, $s0, -1 # las constantes también pueden ser negativas
    bne $s0, $zero, bucle # branch on not equal. Si $s0 != $zero, se salta a bucle. Si no, se sigue para abajo
int double(int x){
    return x*2;
}
...
int y = 5;
y = double(y);
.text
main:
    addi $s0, $zero, 5
    add $a0, $s0, $zero #podriamos usar la pseudoinstruccion move
    jal double
    move $s0, $v0 #pseudoinstruccion para copiar de $v0 a $s0
    li $v0, 10
    syscall # ejecuta una syscall, con código el que hay en $v0 (10 vamos a suponer que es salir del programa)
double:
    sll $v0, $a0, 1
    jr $ra

¿Qué hace jal? Llama a la subrutina double ejecutando un salto y poniendo $ra a la siguiente dirección (para retomar el ciclo de ejecución normal cuando salgamos de la subrutina con jr $ra).

Cargando datos

Hasta ahora hemos trabajado siempre con datos que ya estaban en los registros. ¿Qué pasa si queremos recorrer un array por ejemplo? Un array es un tipo de dato más complejo, que no entra en un registro. Este ejemplo suma los números del array.

int* x = [1,2,3,4,5];
int suma = 0;
for(int i =0;i<4;i++){
    suma = suma + x[i]
}
.data
x: .word 1,2,3,4,5
.text
main:
	li $s0, 0
	li $t9, 5
	la $t0, x
bucle:
	lw $t1, 0($t0)
	add $s0, $s0, $t1
	addi $t0, $t0, 4
	addi $t9, $t9, -1
	bne $zero, $t9, bucle
	li $v0, 10
	syscall

Usamos la cabecera data para registrar datos en el stack que el sistema operativo repartirá como pueda. Le llamamos x y contiene WORDS, que en MIPS son 4 bytes, es decir, 32 bits.

la es una pseudoinstrucción (usa lui y ori internamente) que sirve para cargar direcciones de 32 bits en un registro. En este caso cargamos la posición de donde empieza el vector x en $t0. $t0 es un puntero ahora.

lw es la instrucción importante aquí, significa load word y permite cargar palabras de la memoria a un registro. Le indicamos donde queremos que se guarde ($t1), y donde está el dato en memoria ($t0). Adicionalmente le indicamos el desplazamiento, que digamos es una constante que podemos aplicar para cargar unos bytes antes o después de lo que indique el registro. Esto es muy útil, pero en este ejemplo no tiene sentido usarse y lo he dejado a 0.

¿Por qué sumamos 4 a $t0 en cada pasada? Hemos dicho que los WORD en MIPS ocupan 32 bits, 4 bytes. Pues en esa operación estamos moviendo el puntero 4 bytes más en la memoria, para pasar al siguiente elemento del vector. Esto es aritmética de punteros. ¡Chachi pistachi!

El emulador Mars

¿Ya has visto por qué MIPS es tan bonito? A diferencia de otros ensambladores, la sintaxis de MIPS es muy regular, con comportamientos predecibles aunque no conozcamos exactamente la instrucción. Si quieres probar tus destrezas en MIPS existen varios simuladores. El que uso ahora mismo se llama Mars, está hecho en Java y es bastante completo. Es posible inspeccionar la memoria al completo, ir paso a paso en cada instrucción, insertar breakpoints y observar el valor de los registros en cada momento.

Descargar Mars

También si nos vemos con fuerzas podremos pasar a hardware real con Linux. OpenWrt, presente en routers, o Debian, en la Creator CI20 pueden ser buenas opciones.

Conclusión

Seguro que si habías programado con anterioridad en otro ensamblador esto te ha parecido muy sencillo. Y es que MIPS no es especialmente complejo.

¿Qué pasa con Elixir?

Desde hace un tiempo oigo a bastante gente hablar de Elixir. Elixir es un lenguaje de programación de propósito general que vio la luz en 2011. Con bastantes aspectos de un lenguaje de programación funcional y dinámico, está especificamente diseñado para manejar la concurrencia. Se ejecuta sobre la máquina virtual BEAM, originalmente diseñada para Erlang y es capaz de ejecutar código métodos escritos en Erlang sin ninguna complicación extra. Además dispone de un sistema de compilación llamado mix, un gestor de paquetes llamado hex y la forma de escribir documentación es similar a Python (existe help(método), ¡aleluya!). Elixir además dispone de hot swapping, es decir, permite cambiar el código en ejecución sin necesidad de parar el programa. También le caracteriza tener un buen soporte a operaciones asíncronas.

¿Es Elixir el nuevo Ruby?

Mucha gente ha querido llamar a Elixir el Erlang escrito bonito. Muchos lo comparan con Ruby pues sí que comparten alguna característica común en su sintaxis y una filosofía en general de simplicidad. Además Elixir es mucho más rápido y está mucho mejor diseñado para concurrencia y aplicaciones tolerantes a fallos (como su hermano mayor Erlang).

Sin embargo, ¿es justo comparar Ruby con Elixir?

Entra Phoenix en acción

Mucha de la popularidad de Ruby se la debe a su framework Rails. Usado por una gran cantidad de sitios en la web, supuso para muchos su primer contacto con Ruby y la razón de que se quedasen aprendiendo el lenguaje.

Curiosamente, Elixir también tiene un framework web que atrae a desarrolladores. Se trata de Phoenix.

Phoenix se presenta como un framework para la nueva web. Aplicaciones realtime, tolerantes a fallos y de alto rendimiento sin perder las facilidades y comodidades de frameworks anteriores. La gente que lo ha usado cuenta maravillas. ¿Has usado Phoenix? Cuéntanos tu experiencia en los comentarios.

Probando Elixir con su REPL

Elixir viene con un REPL, es decir, una terminal donde línea a línea podemos ir introduciendo código Elixir. Se ejecuta con el comando iex.

Podemos hacer un hola mundo con IO.puts.

Podemos probar a definir un módulo de suma:

defmodule Adder do
    def add(a,b) do
        a+b
    end
end

Adder.add 42,15

Lo que se ve en amarillo es el bytecode compilado para BEAM del módulo Adder

Aunque llegado el momento quizá nos interese crear alguna función anónima.

add = fn a,b -> a+b end
x = 42
IO.puts add.(x,15)

Es fácil encontrar documentación en español sobre Elixir si deseas investigar más sobre el tema.

Sin duda Elixir parece interesante. ¿Será un mero hype o dentro de unos años Elixir será uno de los lenguajes más populares? Ciertas webs han empezado a recomendar echar un vistazo a Elixir y Phoenix si queremos crear una nueva aplicación web.

Polvo

“Polvo eres y en polvo te convertirás” pensaba Félix. Y lo cierto es que en ese momento estaba hecho polvo.  Su trabajo era estresante. ¡Fax! ¿Habéis hablado con los inversores japoneses? ¡Rápido, que se acaba el plazo de entrega! ¡Fotocópiame este dossier! ¡Lleva a las niñas a la fotocopiadora! Espera, espera, ¿por qué tenía que llevar a las niñas a la fotocopiadora? Estaba delirando de nuevo. Una visita rutinaria a la máquina de café le despertaría momentáneamente.

¡Pero si no hay café! Me han traído una máquina de chucherías. ¿Qué clase broma es esta? Si tiene hasta condones, como si fuese a echar un polvo aquí en la oficina. El disgusto de Félix era tal que fue a hablar con su jefe. Un asunto que él consideraba de máxima prioridad. ¡Voy a ir al jefe a hablarle de este asunto, es de vital importancia tener una máquina de café! Al llegar al despacho descubrió que sí que había gente en la oficina que usaba los condones. Fingió no haber visto nada y fue a la planta de arriba. Quizá allí tendrían néctar negro.

Al subir se encontró con Emma. Era la típica persona superficial e interesada. Ella fue quien le dijo que no cobraría paga extra en navidad por su baja productividad. Esta vez, y por primera vez en mucho tiempo, dijo algo interesante para Félix. Arriba han quitado la máquina de café. ¿Por qué lo primero que me ha dicho al verme es sobre el café? ¿Está insinuando que no hago nada más que tomar café? Instintivamente le propinó un golpe a Emma que la dejó inconsciente en el suelo. ¡Cómo puede pensar que soy un cafeinómano! ¡Y como se atrevió a decirme que mis niñas estarían mejor sin su padre! ¡Por fin muerde el polvo! Al poco tiempo recapacitó. ¡Dios! ¿Qué he hecho? ¿La habré matado? Tenía tanto miedo que no se paró a comprobarlo. Miremos el lado positivo, nadie me ha visto. Podría hacer pasar que fue un accidente. ¿Pero y si cuando recupera la consciencia me acusa a mí? ¿Y si me despiden? ¡Perderé todo lo que tengo!

Ahora Félix no quería perder los faxes, los gritos y el estrés. En cierta parte empezó a sentir nostalgia. Son parte de mí. Si me despiden, ¿qué seré? ¡Tengo derecho a quedarme con mis problemas! Tengo que deshacerme de ella sin levantar sospechas. Entró en una sala vacía con cuidado de que nadie le viese. Dentro de la sala repleta de polvo, destacaba una máquina de café. Esa máquina no tenía polvo, ¡era la que estaba antes en su planta!

Se apresuró a acabar con lo que quedaba de Emma. Cortó. Descuartizó. Aplastó. Ya no era él. Pero hacía mucho tiempo que ya no era él. Se empezó a dar cuenta que el cuerpo muerto de Emma sangraba y podía delatarle. Una bombilla se le iluminó y decidió escurrir la sangre en el tanque de la máquina de café.

A la mañana siguiente volvió a aparecer la máquina de café. Al parecer había habido quejas. Como todos los días fue a por su café. Tenía un tono más rojo que de costumbre, pero estaba delicioso. Un compañero le comentó a Félix que Emma había desaparecido sin dejar rastro. Seguramente no andará muy lejos. Miró el café, sonrió y siguió trabajando. De todos modos nadie distingue el polvo en el viento y Emma ha volado.