Mostrando entradas con la etiqueta programacion. Mostrar todas las entradas
Mostrando entradas con la etiqueta programacion. Mostrar todas las entradas

jueves, 8 de marzo de 2012

Erlang (II) Aprendiendo lo básico

Erlang. Erlang. Erlang. ¿Por dónde empezar a aprender?

Pues por muchos sitios. Hay un montón de documentación disponible, y un montón de tutoriales. Es suficiente con buscar un poquitín, para encontrarse con material de mucha calidad. Hoy recopilaré las fuentes que me han ido ayudando a aprender lo poco que sé de Erlang.

He decicido no hacer otro manual de Erlang mas, ya que toda la informaicón que se puede encontrar en Internet es mas que suficiente, y lo único que estaría haciendo sería repetir contenido.

[¿Qué es erlang?]
Lo explico con mis palabras (seguro que con inexactitudes e imprecisiones) y después pongo un par de enlaces ineresantes y un poco mas serios. Erlang es un lenguaje de programación funcional, de propósito general y altamente enfocado a la concurrencia. Se creó por la compañía Ericsson para ser usado en temas relacionados con la telefonía (programación de PBX, etc). Una de las características de la telefonía es que necesita acceptar mucha concurrenicia (número de llamadas al mismo tiempo), tiene que ser tolerante a fallos (si una llamada ocasiona un problema, las demás llamadas deben continuar), tiene que tener un downtime mínimo por lo que implementa un sistema de cámbio de código "en caliente" (ya que siempre hay llamadas establecidas, y una parada de sistema significa dejara sin servicio a los clientes), no existen datos comparitos, ( de este modo se eliminan muchos problemas de concurrencia y bloqueos ), los procesos, también llamados Agentes o Actores, son partes de código que se ejecutan de modo independiente, y que se comunica entre otros procesos mediante mensajes (no son procesos de Sistema, estos "procesos" son gestionados por la máquina virtual de Erlang ). Crear Actores (o procesos) de Erlang es *muy* barato computacionalmente, o sea 1µs. En C# o Java crear un proceso (de sistema) tarda unos 300µs. En erlang se pueden crear literalmente millones de procesos, mientras que en Java/C# no se puede crear mas que unos 2.000. Otra característica muy chula del lenguaje es que estos Procesos-Erlang (o también llamados Agentes o Actores) se pueden ejecutar en cualquier Core o CPU de tu ordenador. De hecho, se pueden ejecutar en otra máquina especificando un parámetro adicional. Esto nos dá la libertad de poder escalar horizontalmente de una manera increíble. Normalmente el mismo Erlang ya hará uso de toda la capacidad de procesamiento de un mismo ordenador (usando todos sus cores), de manera transparente para el usuario y sin tener que programar un línea de código adicional. Pero si se añade una máquina más, es tan simple como decirle a Erlang "'ei! Te he añadido mas recursos. ¡Úsalos!".... y punto :)

Bueno, vayamos con las definiciones mas serias.

Obviamente tenemos la web de wikipedia, pero la vamos a usar sólo para echarle un vistazo general a las definiciones de qué es Erlang y ver un poquito cómo se vé el código en este lenguaje. Erlang es un lenguaje funcional, lo que quiere decir que hace uso intensivo de recursividad y demás. Las variables solo pueden ser asignadas una vez (sisi, literalmente. Solo una vez. Divertido, ¿verdad?). Que estos conceptos no te asusten. Es simplemente cambiar el chip. En uno de los manuales que enlazaré mas adelante se explica todo, y queda todo muy claro.

Después lo mejor será que el mismo Joe Armstrong, uno de los creadores principales de Erlang, nos cuente sus bondades (las de Erlang, no las suyas). Hay otra charla exactamente igual en contenido pero para un publico mas senior (o mas enterprise, no lo tengo muy claro) y por lo tanto menos divertida. Esta está muy chula.

[Empezando a jugar]
Para ir metiéndonos en tarea, podemos echarle un vistazo al curso de la web oficial de Erlang, que dicen que está un poco desfasado, pero está muy bien explicado cómo usar las features claves del lenguaje. Todo muy escueto, pero bastante útil para entender los conceptos básicos y saber qué nos vamos a encontrar. Hay cinco módulos: History, Sequential Programming, Concurrent Programming, Error handling y Advanced Topics. Recomiendo que se lean con calma e intentando entender todo lo que se pueda. También hay un apartado de ejercicios para practicar lo aprendido. Muy útil.

Y aquí viene el punto fuerte. La guía definitiva. Learn you some Erlang[1]. La polla en bicicleta. Cuando acabe de leerme la guía entera me voy a poner en contacto con el tío y le mandaré 50€ para que se vaya a tomar unas cervecitas al bar, porque la verdad que se lo ha currado. Son 30 capítulos. Cada uno explica una parte de Erlang. Empieza primero con la história, cómo instalar el intérprete de erlang, tipos de datos, los módulos, la sintaxis de las funciones y los pattern matching, recursividad, funciones de alto nivel, errores y excepciones, concurrencia, multiprocesos, y un laaaaaaargo etc. Una pasada, oye.

Ya en la introducción el autor dice que es necesario unos conocimientos básicos de programación en lenguajes imperativos (Python, C/C++, Java, Ruby...) y que no hace falta tener conocimientos de lenguajes funcionales (Scala, Haskel, CLisp, Clojure....). Vamos, que empieza des de cero y es muy fácil de ir siguiendo. Todo está con ejemplos de código que podemos ir siguiendo nosotros mismos ( y debemos hacerlo ), y hasta te dá los códigos fuente de todos los programillas que se van creando durante el curso/libro.

Otra cosa muy buena que tiene el autor es que te cuenta lo que es Erlang, y no te lo intenta vender. Te cuenta sus cosas buenas, y sus cosas malas. Para lo que sirve, y para lo que no sirve. Normalmente las guías siempre te dicen: "aprende a programar en el mejor leguaje de programación del mundo" ( yo almenos tengo dos libros en casa que en la portada aparece este lema, siendo lenguajes de programación distintos ). El autor siempre intenta explicarte las bondades del lenguaje, pero te dice cuáles son sus limitaciones. Muy chulo, la verdad.

[Otra información interesante]
Hay una pregunta en Stack Overflow sobre por qué los procesos de Erlang son mas eficientes que los Threads del SO que es muy interesante. También tenemos otra entrada (que sinceramente todavía no he probado[2]) sobre plugins de Erlang para el Vim (resaltado de sintaxis, introspección en los módulos, completion... lo típico, vamos).

Hay otra página, de un tal Richard Jones co-fundador de Last.fm, en donde explica cómo construir una aplicación de un millón de usuarios en Erlang. Son tres entradas muy muy interesantes. Yo me lo leí cuando empezaba con Erlang y me fascinó, aunque sinceramente me enteré de poco. Ahora cada vez lo entiendo mas, y lo utilizo como referéncia para ir cogiendo ideas y ver cómo ha solucionado algunos problemas.

Otro artículo interesante, aunque mucho mas específico, es un ejemplo práctico de cómo usar el framework web MochiWeb. Si quieres crear un servidor web, MochiWeb te puede solucionar la papeleta. Es muy ligero, y te dá todos los recursos necesarios para manejar los request/responses. En éste artículo te explican cómo crear un pequeño dispacher de los requests que llegan, y un modo de devolver las respuestas de manera simple.

Y nada, de momento esto es todo. Te animo a que le des una oportunidad. No es difícil: Es diferente. Pero muy divertido, y con el que se pueden hacer cosas realmente chulas. Yo estoy difrutando un montón. Para cualquier cosa, dudas, preguntas o aclaraciones, no dudes en dejar tu comentario.

Un saludo, Jan.

Edit: Añado otro vídeo muy chulo de Joe Armstrong.
Edit[2]: Vale, ya he probado el pluguin para el Vim y aquí están mis impresiones.
Siguiente post: Erlang (III) Semana 1
Post anterior: Erlang y WebChats (I)
[1] Hay un grupo en argentina que está traduciendo este magnífico trabajo, para al que no le vaya demasiado bien esto del inglés.

domingo, 20 de noviembre de 2011

Clase de buceo

En el post anterior[1] comentaba cómo configurar las PAM para desactivar el tiempo de espera en caso de haberte equivocado escribiendo un password. Este post explica el proceso que seguí para saber que no es posible establecer un tiempo de espera personalizado. Siempre te tienes que esperar dos segundos en caso de haberte equivocado de password, o puedes desactivar el tiempo de espera. Lo que no puedes hacer es decir, "espérate 5 segundos en caso de que me haya equivocado de password antes de volver a preguntarme".. También se puede ver lo bonito que es el OpenSource, y la de que el código fuente sea público.

[Preámbulo]

Resulta que en el fichero /etc/pam.d/login hay una opción que pone: "auth optional pam_faildelay.so delay=3000000". Un comentario al lado explica claramente lo que hace esto:

"Enforce a minimal delay in case of failure (in microseconds)". O lo que es lo mismo: Fuerza una pequeña espera en caso de fallo en la autenticación. 3 segundos, para ser mas exactos.

Pues parece obvio pensar que si cambio 3000000 a 1000000, el tiempo de espera cuado haga login fallido se reducirá a 1 segundo.

Probemos antes de hacer el cambio:
$ sudo echo 1 # Comando chorra, pero lo importante es que nos pida el password
[sudo] password for inedit: badpassword
--- pasan unos dos segundos, aproximadamente ---

Hacemos el cambio en el fichero, poniendo el parámetro "delay=1000000". Probamos de nuevo:
$ sudo echo 1
[sudo] password for inedit: badpassword
--- pasan unos dos segundos, aproximadamente. Lo mismo que antes... ---


mmmm... mierda, no funciona. Probemos lo propuesto en el post anterior, o sea, poner el parámetro nodelay en el fichero /etc/pam.d/common-auth:
auth [success=2 default=ignore] pam_unix.so nullok_secure nodelay

Probamos de nuevo:

$ sudo echo 1
[sudo] password for inedit: badpassword
--- inmediatamente despues nos dice que la contraseña es incorrecta y que lo intentemos de nuevo. Tiempo de espera: cero segunos ---

Genial. Parece que el parámetro "nodelay" funciona. Pero ¿Por qué no funciona el "delay=3000000"?


[Siguiendo pasos lógicos]
Vale, resulta que el parámetro "nodelay" se lo ponemos como parámetro a un fichero llamado "pam_unix.so". Ni idea de qué coño hace este fichero, pero busquemos a ver si existe ene el sistema:

$ locate pam_unix.so
/lib/x86_64-linux-gnu/security/pam_unix.so

Touché, existe. mmmm..... vale. ¿Ahora qué hacemos con el? Ni idea de que hace realmente el fichero. Lo he abierto y es un binario....mmmm.... Vale, ya lo tengo. Descubramos qué paquete ha creado este fichero:

$ dpkg-query -S /lib/x86_64-linux-gnu/security/pam_unix.so
libpam-modules: /lib/x86_64-linux-gnu/security/pam_unix.so


Con que libpam-modules, eh? Vaaaale, pues mira, estamos siguiendo la pista y no nos va mal. Ahora ¿cuál puede ser el siguiente paso? Pues descargar el código fuente y que hace realmente el código:
$ mkdir ~/killme
$ cd ~/killme
$ apt-get source libpam-modules

Esto nos habrá creado un par de ficheros en el directorio "killme" [2].

[Buceando en el código]
Vale, ahora tenemos el código de la "libpam". ¿Qué hacemos? Lo obvio, aquí sería buscar alguna referéncia a "pam_unix.so". Pero como los ficheros ".so" son compilados y nosotros nos hemos descargado el código fuente, vamos a probar lo siguiente:
$ find -name "pam_unix*"

Oh! Genial, tenemos resultados! Parece que existe una carpeta interesante: "./pam-1.1.3/modules/pam_unix"

Vale, ahora deberíamos buscar algo de utilidad dentro de esta carpeta. Juguemos con "grep", a ver si hay suerte:
$ cd ./pam-1.1.3/modules/pam_unix2
$ grep nodelay -i # -i es para hace "ignore-case". O sea, que no distinga entre mayúsculas y minúsculas.
pam_unix.8:\fBnodelay\fR
pam_unix.8.xml:
README:nodelay
support.c: if (off(UNIX_NODELAY, ctrl)) {
support.h:#define UNIX_NODELAY 16 /* admin does not want a fail-delay */
support.h:/* UNIX_NODELAY */ {"nodelay", _ALL_ON_, 0100000},



Tenemos resultados! Parecen interesantes los ficheros "support.c" y "support.h". Revisado el fichero "support.h" parece que solo hay la declaración del parámetro UNIX_NODELAY.
Veamos el fichero "support.c", a ver que contiene:

[...]
#ifdef HAVE_PAM_FAIL_DELAY
if (off(UNIX_NODELAY, ctrl)) {
D(("setting delay"));
(void) pam_fail_delay(pamh, 2000000); /* 2 sec delay for on failure */
}
#endif
[...]


Eureka! Lo hemos encontrado! Vale, yo no tengo ni idea de C. Nunca he programado nada serio en C, ni mucho menos una librería de sistema para Linux. Pero si hemos llegado hasta este fichero buscando cosas lógicas, ahora no nos va a detener un poco de código en C. Parece que es el código fuente de "pam_unix.so".

Vamos a intentar leer lo que pone este pedacito de código. La condición "if" parece que comprueba lo siguiente:
SI (el parámetretro UNIX_NODELAY és igual a falso) ENTONCES {
Espérate 2 segundos
}


Pues ya lo tenemos, señores. Resulta que no se puede definir un tiempo de espera, ya que el tiempo de espera está puesto de modo estático en el código. En ningún momento el código va a leer la variable "delay=3000000", por lo que si ponemos "delay=5000000" es normal que lo ignore.

[conclusión]
¿Cómo hemos podido sacar todo esto? Pues la respuesta es muy simple: porque es Software Libre y se puede conseguir el código fuente muy facilmente a través de Internet. Inspeccionando el código vemos claramente lo que hace ( y mejor todavía, lo que no hace ). En este punto, y si tuviese los conocimientos de C necesarios, podría reescribir el código fuente para que aceptara un parámetro "delay" y que pudiese ser definido des de la pam.d/login. Una vez hechos los cambios, podría mandarlos al mantenedor del paquete y en caso de gustarle dichos cambios, los incorporaría en el código de la libpam. Y el mundo sería un lugar mejor y lloverían gominolas del cielo :)


[1] Recomiendo que te lo leas, sinó este pot no tiene mucho sentido.
[2] Me gusta bastante crear directorios con el nombre "kill" o "killme" para usos temporales, ya que es un modo de saber si puedo borrar el directorio sin ni tan solo preocuparme de ver que contiene. En cambio, un directorio que llamado "temp" o "temporal".... bueno, si, son datos temporales. Pero hasta cuando? Servirá lo que hay dentro? Es algo lioso. Usando "killme" el tema está claro, puedes borrar la carpeta cuando quieras sin ningun problema, ya que el contenido de la misma no es importante ;)

domingo, 27 de marzo de 2011

El Mínimo Absoluto que Todos los Desarrolladores Deberían Conocer Sobre Unicode y Codificaciones.

Este artículo pretende ser una traducción más o menos fiel [1] de el artículo de Joel Spolsky. Me ha gustado tanto que me he decidido a traducirlo para hacerlo accesible a todos aquellos que no dominan el inglés, o que prefieren leer en castellano. Es un magnífico texto que todavía hoy sigue vigente. Te recomiendo la lectura, ya seas programador, administrador de sistemas, o simplemente un curioso de la informática.


----------------------------------------------------------------------------------------------

El Mínimo Absoluto que Todos los Desarrolladores Deberían Conocer Sobre Unicode y Codificaciones.

Miércoles, 08 de Octubre de 2003 by Joel Spolsky

Alguna vez te has preguntado acerca de la etiqueta misteriosa "Content-Type"? Ya sabes, la que se supone que debes poner en el HTML y que nunca has sabido realmente que poner?

Alguna vez has recibido un correo de tus amigos de Bulgaria con un asunto igual a "???? ??? ?? ????? ??" ?

Me he molestado al descubrir que muchos desarrolladores no saben realmente como funciona el misterioso mundo de las codificaciones de caracteres, Unicode, etc... Unos años atrás un beta tester de FogBUGZ se estaba preguntando si podría recibir correos en Japonés. Japonés? Ellos escriben correos en Japonés? No tenía ni idea. Cuando miré mas de cerca el componente comercial que estábamos desarrollando en ActiveX para parsear las cabeceras MIME de los e-mails, nos dimos cuenta de que lo estábamos haciendo mal con las codificaciones de caracteres, por lo que tuvimos que reescribir el código de conversión. Cuando miré el código de otra aplicación comercial, también tenia una mala implementación en la codificación de caracteres. Mandé un par de e-mails al desarrollador del paquete, pero el dijo algo así como: "no puedo hacer nada al respecto".

Cuando descubrí que en el lenguaje de programación PHP no se habían tenido en cuenta las condificaciones y que usaba tan solo 8 bits para la codificación de caracteres, haciendo prácticamente imposible el desarrollo de buenas aplicaciones internacionales, pensé: ya es suficiente.

Tengo un anuncio que hacer: si eres un programador y no tienes unos conocimientos mínimos sobre caracteres, tabas de caracteres, codificaciones y Unicode, te voy a pillar y te castigaré haciéndote pelar cebollas durante 6 meses en un submarino. Te juro que te pillaré.

Y algo más:
** NO ES TAN DIFÍCIL **

En este artículo voy a explicar exactamente lo que todos los programadores deberían saber. Todo esto de que "texto en claro = ASCII = caracteres de 8 bits" no está solamente mal, sino que está fatal, y si sigues programando de este modo, no eres mucho mejor que un doctor que no cree en los gérmenes. POR FAVOR, no escribas otra línea de código antes de haber acabado de leer este artículo.

Antes de que empiece, debería advertirte de que si eres una de estas raras personas que sabe algo sobre la internacionalización, vas a encontrar todo lo de este posto un poco "simplificado". Yo estoy intentando establecer un mínimo, para que todo el mundo pueda entender de qué va el tema, y pueda escribir código que tenga alguna oportunidad de funcionar en textos escritos en cualquier lenguaje ( o en otro subset de inglés que no incluya palabras acentuadas ¬¬ ). Y debo advertirte que el tratamiento de caracteres es solo una pequeña parte de lo que conlleva crear software que funcione intencionalmente. Me temo que yo solo puedo escribir artículos sobre una cosa a la vez, o sea que hoy tocan codificaciones de caracteres.

Des de la perspectiva histórica
========================

La manera mas fácil de entender todo esto es ir viéndolo de manera cronológica.

Probablemente estarás pensando que voy a hablar sobre antiguas tablas de caracteres como EBCDIC. Bueno, no voy a hacerlo. EBCDIC no es relevante para tu vida. No tenemos que ir tan atrás en el tiempo.


Volviendo atrás en los tiempos semi-antiguos, cuando Unix fue inventado y K&R estaba escribiendo The C Programming Language, todo parecía muy simple. EBCDIC estaba ya de salida. Los únicos caracteres que importaban eran los caracteres del inglés, con letras no acentuadas. Así se creó el ASCII que eran unas tablas capaces de representar todos los caracteres usando números del 32 al 127. El carácter que se correspondía con el espacio era el 32, la letra "A" se correspondía con el 65, etc. Todo esto se podía guardar perfectamente en 7 bits. La mayoría de ordenadores en estos días usan bytes de 8 bits, entonces no solo podrías almacenar todos los caracteres ASCII, sino que tenías un bit adicional que "sobraba" ( no se usaba ) y que, si querías podías utilizar para tus propios ( y maléficos ) fines. Este bit adicional se utilizó en WordStar para indicar la última letra de una palabra, condenando, así, WordStart a que sólo funcionara en inglés. Los códigos por debajo de 32 se llamaban "unprintables" ( que no se pueden escribir ) y se utilizaban para insultar. Estaba bromeando. Realmente se usaban como caracteres de control, como el 7, que hacía que ordenador emitiese un "beep", y el 12, que se interpretaba por las impresoras como un salto de página, por lo que dejaba de imprimir en la hoja actual y cargaba otra hoja.

Todo esto estaba muy bien. Suponiendo, claro, que fueses de habla inglesa.

Como el código ASCII solo ocupaba 7 bits, mucha gente pensó "caramba, puedo utilizar los código 128 hasta el 255 para almacenar mis cosas". El problema fue que MUCHA gente pensó esto en el mismo momento, pero cada uno tuvo su propia idea de qué debería ir en el espacio de 128 a 255. El IBM-PC creó algo que se llegó a conocer como mapa de caracteres OEM, que contenía caracteres acentuados para los lenguajes Europeos, así como muchos caracteres para dibujar líneas.... barras horizontales, barras verticales, etc... así que tu podías usar estas líneas para dibujar caracteres en la pantalla y hacer cuadros y líneas a tu gusto ( era un recurso para embellecer las aplicaciones de línea de comandos ). Asimismo, cuando la gente empezó a comprar ordenadores fuera de EEUU, se diseñaron muchos tipos diferentes de tablás de caracteres OEM. Cada una de ellas usaba los últimos 128 caracteres para sus propios propósitos. Por ejemplo, en algunos ordenadores el código 130 se mostraba como "é", pero en los ordenadores vendidos en Isael se veía la letra Hebrea Gimel (ג), así que si des de Estados Unidos enviaban un documento con la palabra "résumés" los israelitas las recibían como "rגsumגs". En muchos casos, como en Rusia, hubieron muchas ideas sobre qué hacer con los últimos 128 caracteres, por lo que intercambiar documentos en la misma Rusia se convertía en un problema.

Eventualmente, este "libre albedrío" de qué hacer en los últimos 128 caracteres se acabó con el estándar ANSI. En este nuevo estándar, todo el mundo accedió en "qué hacer con estos 128 caracteres". Pero este nuevo método establecía muchos maneras de tratar los últimos 128 caracteres, dependiendo del sitio donde vivieras. Estos sistemas diferentes se llamaron *code pages* (páginas de código). En Israel, por ejemplo, el sistema operativo DOS usaba la página con código 862, mientras que en Grecia usaban la página de códigos 737. O sea, sus tablas de códigos eran igual por debajo de los 128 ( ASCII ), pero eran diferentes por encima de los 128 ( donde se ponían todos aquellos "caracteres divertidos" de cada país o región ). Las versiones de MS-DOS tenían docenas de páginas de códigos, que permitían hacer que un mismo ordenador fuera "multilenguaje", de modo que podían abrir documentos escritos en inglés, islandés o esperanto (usando una tabla de códigos que suportara los tres idiomas al mismo tiempo). Pero qué pasaba si querías usar el hebreo y el griego en el mismo ordenador? Pues que no podías ya que cada uno tenía su tabla de códigos específica, y no había ninguna tabla de códigos "compartida" entre estos dos idiomas.

Mientras tanto en Asia, estaban pasando cosas bastante mas complicadas por el hecho de que los alfabetos asiáticos tienen cientos de carácteres. Ellos lo solucionaron con un sistema muy lioso llamado DBCS, "double byte charse set" en el que _algunas_ letras se guardaban en un byte, otras letras se guardaban en dos bytes. Este sistema te permitía moverte sin problemas hacia "adelante" en un string, pero era realmente complicado moverte "hacia atrás". Por esto los programadores dejaron de usar s++ o s-- y empezaron a usar las funciones de Windows AnsiNext y AnsiPrev para no tener que pelearse con este complicado sistema.

Pero aún así la gente seguía programando de modo que un carácter fuese un byte, y que un carácter tenía 8 bits, lo que significava que "nunca muevas un texto de un ordenador a otro". Pero claro, con la aparición de Internet hubo un sitio muy propicio para intercambiar textos de un ordenador a otro, y todo el tema de las codificaciones se vino abajo. Por suerte se inventó Unicode.


Unicode
=======
Unicode fue el resultado de un gran esfuerzo por crear un solo set de caracteres que incluía cualquier sistema de escritura razonable en el planeta, y algún otro como el Klingon, también. Algunas personas, malentendiendo lo que Unicode es, piensan realmente que es un sistema de 16 bits, donde cada carácter ocupa 16 bits. Esto significaría que con este sistema se podrían escribir hasta 65.536 caracteres. Pero esto no es realmente cierto. Es uno de los mitos mas tontos sobre Unicode, por lo que si creías que que era así, no te sientas mal.

De hecho, Unicode tiene un modo diferente de pensar sobre los caracteres, y tu tienes que entender este modo de pensar, o nada va a tener ningún sentido para ti.

Hasta ahora, hemos asumido que un carácter se guarda en un número determinado de bytes como por ejemplo:

A = 0100 0001

En Unicode, los caracteres se llaman "code point", que son solo un concepto teórico. El cómo un "code point" se representa en memoria o en disco, es otra historia.

En Unicode, la letra A es una idea platónica. Solo está flotando en el aire:
A
Esta platónica A es diferente de B, y diferente de a, pero igual a A, y A, y A. La es idea que A en el tipo de letra Times Roman es lo mismo que A en el tipo de fuente Helvetica, pero diferente de "a" en minúscula. Esto no parece que tenga que causar mucha controversia, pero en algunos lenguajes, determinar lo que realmente una letra es puede ser complicado. Por ejemplo en Alemán la letra ß es una letra real o es otro modo de escribir ss? Si una letra cambia, por el hecho de estar escrita al final de una palabra, es la misma letra? Los hebreos dicen que si. Los arábigos dicen que no. De todos modos, la gente inteligente de el consorcio de Unicode, se han estado preguntando todo esto durante la última década, acompañado por un gran debate político. Por esto tu no debes preocuparte por todo esto. Ellos ya lo han calculado todo ya.

Cualquier letra platónica ( concepto de letra ) en todos los alfabetos, es un número mágico en el consorcio Unicode, que se escribe tal que así: U+0639. Este número mágico es llamado "code point". El U+ significa Unicode y los números son hexadecimal.

No hay un límite real en el número de letras que Unicode puede definir, aún a pesar de que parezca de que solo se utilicen 2 bytes, y por tanto, solo se pueden definir 65535 letras. Esto es otro mito sobre Unicode.

Bien, aquí tenemos una cadena de texto:
Hello

que, en Unicode, corresponde a estos cinco puntos de código:

U+0048 U+0065 U+006C U+006C U+006F

Solo sólo un montón de puntos de código (codepoints). Números, en realidad. Todavía no hemos hablado de cómo guardar esto en memoria o en disco, o cómo representarlo en un mensaje de correo electrónico.


Econdings
=========
Aquí es donde entran los "encodings" (codificaciones).

La primera idea de las codificaciones en Unicode, que nos deja el mito sobre los dos bytes, fué: "ei! vamos a guardar estos números en dos bytes cada uno". Así que "Hello" se convierte en:
00 48 00 65 00 6C 00 6C 00 6F

Bien? No, demasiado rápido! No podría escribirse como?
48 00 65 00 6C 00 6C 00 6F 00 ?

Bueno, técnicamente, si. Creo que se podría, y de hecho, los primeros programadores querían ser capaces de guardar los "code points" de Unicode en "high-endian" o "low-endian" en función de si su procesador iba mas rápido en un sistema que en el otro. Entonces la gente estuvo forzada a adoptar la convención bizarra de guardar FE FF al principio de cada texto Unicode; esto se llama Unicode Byte Order Mark ( Marca de orden de bytes Unicode ), y, si tu estabas girando el orden tus bytes de mayor y menor peso, esta marca sería FF FE, así la persona que leyera tu texto sabría si tiene que girar el orden de los bytes o no. Ufff. No todos los textos Unicode tendría la marca de orden al principio, o sea que ya os podéis imaginar los problemas que conllevaría esto.

Durante un tiempo, esto parecía que debería suficiente, pero los programadores se estaban quejando y diciendo: "Ei! Mira todos estos ceros!", ya que ellos eran americanos y estaban mirando texto en inglés. El texto en inglés cumplía la propiedad de que rara vez habían "code points"por encima de U+00FF. También estaban los hippies liberales de California que querían conservar (grrr). Si fueran tejanos, no les habría importado el consumo del doble de memoria para guardar un texto en inglés ( chiste americano ). Pero los cobardes de California no podían soportar la idea de duplicar la cantidad de espacio almacenado para guardar textos. De todos modos habían muchos documentos antiguos por ahí almacenados en ANSI y DBCS. Y que iban a hacer, convertirlos todos? Ellos? Solo por esta razón hubo mucha gente que decidió hacer caso omiso a Unicode durante varios años, y por tanto la cosa empeoró.

Así, se inventó el concepto brillante de UTF-8. UTF-8 fue otro sistema para guardar "code points" en Unicode, pero solo usando 8 bits de memoria. En UTF-8, cada "code point" de 0 a 127 solo se guarda en un solo byte". Solo los "code points" de 128 para arriba se guardan en 2, 3, 4, 5 o 6 bytes.

Esto también tuvo un "efecto secundario" muy bueno en los textos escritos inglés. El texto era exactamente igual en UTF-8, que en ASCII, así que los americanos no verían nada extraño. Solo el resto del mundo debía pasar por el aro. Específicamente "Hello", que es: U+0048 U+0065 U+006C U+006C U+006F, se guardaría como: 48 65 6C 6C 6F!! Exactamente igual como se guardaría en ASCII y ANSI, y en todos los grupos de caracteres OEM del planeta! Ahora bien, si eres tan valiente como para utilizar letras acentuadas, o letras griegas o letras Klingon, tendrás que utilizar varios bytes para almacenar un "code point" único, pero los estadounidenses nunca se darán cuenta de eso.

Hasta ahora te he dicho tres formas de codificación Unicode. Los métodos tradicionales guardalo-en-dos-bytes son llamados UCS-2 ( por que tiene 2 bytes ) o UTF-16 ( porque tiene 16 bytes ), y uno todavía tiene que averiguar si se trata de UCS-2 big-endian o UCS-2 low-endian. Y también tenemos el nuevo y popular estándar UTF-8 que tiene la agradable propiedad de funcionar perfectamente bien con el texto en ingles ( tanto ASCII como ANSI ) y con programas que no tienen ni idea de que existan otras cosas que no sean ASCII.

Hoy en día hay un montón de otras formas de codificar Unicode. Hay algo llamado UTF-7, que se parece mucho a UTF-8 pero que garantiza que el mayor bit va a ser siempre cero. Si tienes, por ejemplo, algún tipo de servidor de correo nazi, que cree que 7 bits son "suficientes, gracias", todavía puedes salir ileso y enviar tus e-mails codificándolos con UTF-7. También hay UCS-4, que guarda cada "code point" en 4 bytes, y tiene la bonita propiedad de que cada "code point" puede ser guardado en el mismo número de bytes, pero, caramba! Incluso la gente de Texas no sería tan osada como para gastar tanta memoria.

De hecho, ahora que estás pensando en la idea platónica que representan los "code points" en Unicode, te puedes dar cuenta que estos "code points" se pueden encodear en cualquier encoding de la "vieja escuela". Por ejemplo, podrías encodear "Hello" ( U+0048 U+0065 U+006C U+006C U+006F ) en ASCII, o el OEM de Grecia, o en la codificación ASCII del Hebreo, o con cualquier codificación anteriormente inventada. Solo con una pega: dejarás de ver algunas letras! Si no existe ningún equivalente para el "code point" de Unicode en el encoding en el que lo estas intentando transformar, normalmente vas a ver el símbolo de pregunta, "?", o quizás puedes llegar a ver el símbolo �. Te suena?

Hay cientos de encodings tradicionales, que solo pueden almacenar ALGUNOS de los "code points" de Unicode. Los "code points" que no tienen una representación en el encoding viejo, se cambian por símbolos de interrogación. Algunos encodings populares en inglés son: Windows-1252 ( el estándar Europeo para Windows 9x ), y el ISO 8859-1 ( también llamado Latin-1 ), también usado por los idiomas del oeste Europeo. Pero intenta almacenar Ruso, o Hebreo en estos encodings, y solo vas a ver un montón de símbolos de interrogación. UTF 7, 8, 16 y 32 tienen la propiedad de poder almacenar cualquier "code point" de manera correcta.


La cosa mas importante sobre los encodings
==========================================
Si has olvidado todo lo que te acabo de explicar, por favor aprende una cosa muy importante. No tiene ningún sentido tener una cadena de texto sin saber que encoding usa. Ya no puedes seguir pensando que "texto claro" es ASCII.

El texto claro (plain text) no existe.

Si tu tienes un texto, en memoria, o en un fichero, o en un e-mail DEBES saber en que encoding ha sido guardado, o no serás capaz de mostrar los caracteres correctamente.

Casi todos los problemas estúpidos "mi web parece un galimatías" o "mi amiga no puede leer mi correo electrónico cuando lleva acentos", se reducen a que un programador ingenuo que no comprendía el simple hecho de que si no me dices como has codificado el texto, ya sea en UTF-8, o ASCII, o ISO-8859-1 o Windows 1252 yo SIMPLEMENTE no puedo mostrar correctamente el texto ( ni saber donde el texto termina )!

¿Dónde podemos preservar la información sobre qué codificación usa el texto que mandamos? Bueno, hay maneras estándar para hacer esto. Por ejemplo, para un correo electrónico, uno espera encontrar en la cabecera un string que ponga:

Content-Type: text/plain; charset="UTF-8"

Para una página web, la idea original era que el servidor web devolviese una cabecera (HTTP) con el Content-Type, ( y no en el HTML ). De manera que uno ya sepa la codificación de la página antes de recibir el HTML.

Esto da problemas. Imagina que tienes un gran servidor web con muchos sitios, y con cientos de páginas con contribuciones de gente de todo el mundo, en diferentes idiomas. Y que todas utilizan la codificación que quiera que use el Microsfot FrontPage. El servidor web no nunca sabrá realmente qué encoding tiene cada archivo, por lo que no podrá mandar una cabecera con el Content-Type.

Sería conveniente que pudieses poner un Content-Type en el HTML donde va el fichero mismo, utilizando algún tipo de tag especial. Por supuesto esto llevó a la locura a los puristas... "¿Cómo se puede leer un fichero HTML hasta que no sepas que codificación lleva?!" Por suerte, casi cada encoding común usa los mismos caracteres entre 32 y 127, entonces siempre podemos empezar a leer HTML sin ver caracteres estaños:


<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">


Por lo que el meta tag tiene que estar estar justo después de declarar la sección head ya que, tan pronto como el navegador web vea este tag, va a parar de interpretar la página y volverá a empezar reinterpretando toda la página con el encoding que has especificado.

¿Que hacen los navegadores si no encuentran ningún Content-Type y ningún tag en el header HTML? Internet Exploiter hace algo bastante interesante: intenta adivinar, basado en la frecuencia en la que aparecen algunos bytes en los típicos encodings en diferentes idiomas. Ya que varios encodings de 8 bits intentaban poner sus letras de su idioma nativo entre el rango entre 128 y 255, y ya que todos los idiomas tienen diferentes características de frecuencia en el uso de determinadas letras en texto escrito, se podía adivinar mas o menos el encoding en el que ha sido escrito el texto. Es bastante raro, pero parece funcionar bastante bien para las páginas programadas por ingenuos programadores que necesitarían echarle un vistazo a lo que es el Content-Type de su página web. ¿ Que pasa? Que si no se ajusta bien el encoding ( la detección falla ), y si Internet Exploiter decide que el idioma es coreano, pues el usuario que ha cargado la página no puede entender nada. Esto prueba, creo, la Ley de Postel sobre: "conservador en lo que dices y liberal en lo que aceptas" no es un principio bueno para un trabajo de ingeniería. De todos modos, ¿Qué hace el pobre lector que entra en una página escrita en búlgaro y la ve en coreano? Va al menú View>Encoding y prueba diferentes codificaciones (hay varias docenas de codificaciones en el Este de Europa ), hasta que ve bien el texto. Esto si sabe que puede hacerlo, claro, y mucha gente ni lo sabe.

Para la última versión de CityDesk un sitio de administración web publicado por mi compañía, decidimos internamente utilizar Unicode UCS-2 (dos bytes), que es el tipo nativo de Visual Basic, COM y Windows NT/2000/XP para los tipos de datos string. En C++, declarábamos los strings como wchar_t, en vez de char, y usábamos la función wcs en vez de str. Para crear un literal UCS-2 en C, simplemente poníamos un L antes, así quedaba algo como: L"Hello".

Cuando CityDesk publicó su página, se convirtió todo en UTF-8, que siempre ha sido una codificación muy bien soportada por todos los navegadores. Aquí tenemos el muro de las 29 versiones en las que está ecodeada la página de "Joel on Software", y yo nunca he escuchado a ninguna persona que haya tenido algún problema al visitar mi página.

Este artículo se está haciendo demasiado largo, y me es imposible explicar todo lo relacionado con la codificación de caracteres en Unicode, pero creo que si has leído hasta aquí, has aprendido suficiente como para volver a programar, y usar antibióticos, en vez de sanguijuelas y hechizos.



--------------------------------------------------------------------------------------------------------



[1]: Teniendo en cuenta que mi nivel de inglés es bastante.... humilde. Aún así he hecho un gran esfuerzo para traducir del mejor modo que he podido el artículo. Se aceptan correcciones.

Nota: Se ha usado “cadena de texto” como sinónimo de “string”.
Nota2: Se ha cambiado intencionadamente “Internet Explorer(tm)(r)” por “Internet Exploiter”. Seguramente el autor no estaría de acuerdo con esto. Es un chiste fácil.
Nota 3: Si te ha gustado el artículo y eres un blogger, agradecería que creases un post mencionando el al artículo original ( o hacia esta traducción, o ambos ). Un mundo con mejor comprensión sobre el Unicode, es un mundo mejor. Gracias. ;)

viernes, 9 de abril de 2010

CUDA [II] Instalación de toolkit y SDK para CUDA

Buenooo. Ahora nos dejamos ya de palabras y empezamos haciendo algo interesante. Pero antes quiero hacer un par de notitas:
  1. Vamos a instalar drivers nuevos. Lo más fácil es que los drivers nuevos no funcionarán a la primera o vete a saber tu qué. Entiendase que se puede liar la cosa.
  2. Hay gente que ha conseguido instalar todo el SDK y todo en Ubuntu 9.10. Yo no puede/supe. Lo he probado en Ubuntu 9.04 y ha funcionado perfectamente. El soporte de nVidia llega hasta 9.04.
  3. AVISO. El material que voy a poner aqui, en su mayoría van a ser cópido de otras páginas. Como podeis imaginar hay mucha gente que ha hablado hasta ahora del proceso de instalación, lo que la información está un poco "separada". Yo os pondré lo que me ha funcionado a mi, a modo de recopilación/traducción. No dejen de visitar las fuentes originales.
  4. Comprueben que sus tarjetas sean compatibles con CUDA.
Dados estos avisos, empezemos.

[INSTALANDO 9.04]
Tuve muchos problemas en Ubuntu 9.10. Como nVidia da soporte a Ubuntu 9.04 me dije, pues instalalo. Y esto hice. He creado una partición en mi disco y he instalado 9.04. Os recomiendo que hagais igual, si os quereis ahorrar problemas. Además, así podeis hacer las pruebas que querais sin miedo a perder datos ni nada. La instalación tiene que ser nativa! No virtualizeis!

[INSTALANDO DRIVERS][1]
Una vez tenemos nuestro 9.04 funcionando y operativo, debemos instalar los últimos drivers de nVidia, los 195. Para ello seguiremos estos pasos:
$ sudo su
$ echo DRIVERS NVIDIA 195 >> /etc/apt/sources.list
$ echo deb http://ppa.launchpad.net/nvidia-vdpau/ppa/ubuntu jaunty main >> /etc/apt/sources.list
$ echo deb-src http://ppa.launchpad.net/nvidia-vdpau/ppa/ubuntu jaunty main >> /etc/apt/sources.list
$ apt-key adv --keyserver keyserver.ubuntu.com --recv-keys CEC06767
$ aptitude update
$ aptitude install nvidia-195-modaliases nvidia-glx-195

[DESCARGANDO PAQUETES]
Tenemos que ir a la pagina web de CUDA, a descargas. Los paquetes que necesitamos son:
  • CUDA Toolkit for Ubuntu Linux 9.04
  • GPU Computing SDK code samples and more
La versión 32bits o 64 bits. Como corresponda. Los descargamos en el escritorio.

[INSTALANDO TOOLKIT] [2]
Para ello damos permisos de ejecución con el comando:
$ chmod +x ~/Escritorio/cudatoolkit_3.0_linux_32_ubuntu9.04.run

Y ahora lo instalaremos. Pero resulta que al instalarlo, si tenemos GDM iniciado, da un error. Para esto utilizaremos una consola tty1. Apunta los pasos ya que cerraremos GDM y te vas a quedar sin gestor de ventanas. Será solo un momento.
  • Pulsamos Control+Alt+F1
  • Entramos con un usuarios que tenga privilegios administrativos
  • $ sudo service gdm stop
  • $ cd /home/nombre_del_usuario/Escritorio
  • $ sudo ./cudatoolkit_3.0_linux_32_ubuntu9.04.run
  • $ sudo service gdm start
  • Pulsamos Control+Alt+F7, iniciamos sesion normalmente y seguimos el proceso
Ahora tenemos que añadir los directorios de nvidia a PATH. Abrimos un terminal:
  • $ sudo vim /etc/bash.bash.rc #Si no sabes usar vim, pon "gedit" en lugar de "vim"
  • Al final del fichero incluiremos dos líneas:
export PATH=${PATH}:/usr/local/cuda/bin
export LD_LIBRARY_PATH=${LD_LIBRARY_PATH}:/usr/local/cuda/lib64

Si tenemos un sistema de 32 bits, cambiamos "lib64" por "lib". Guardamos el fichero y Toolkit instalado.

[INSTALANDO EL SDK][2]
Hacemos el fichero ejecutable con:
$ chmod +x ~/Escritorio/gpucomputingsdk_3.0_linux.run
No hace falta que se instale con privilegios de ROOT. Instalar con el usuario que va a usar el SDK.
$ ./gpucomputingsdk_3.0_linux.run
Las preguntas que nos hace las contestamos con un "enter". El default ya nos sirve. Una vez instalado entramos en la carpeta del SDK:
$ cd ~/NVIDIA_GPU_Computing_SDK/C
Instalamos dependencias:
$ sudo aptitude install freeglut3 freeglut3-dev libx11-dev mesa-common-dev libxmu6 libxi-dev libxmu-dev
Y compilamos los codigos:
$ make

[EJECUTANDO EJEMPLOS][2]
Si todo ha funcionado correctamente, ahora podremos ejecutar los siguientes comandos:
$ cd ~/NVIDIA_GPU_Computing_SDK/C/bin/linux/released
$ ./deviceQuery
$ ./fluidsGL
$ ./smokeParticles
$ ./particles

[POSIBLES PROBLEMAS]
  • El compilador gcc tiene que ser verión 4.3 ( en mi caso 4.3.3 ). El compilador 4.4 no funciona directamente. Diríganse a [2] para ver como se puede "arreglar" el problema.
  • Es muy importante tener instalado ( y funcionando ) los últimos drivers de nVidia. El SDK funciona solo con los drivers más nuevos.
  • Links dónde encontré respuestas que ayudaron a aclararme: [3] [4]
  • De dependencias. Pero siguiendo los pasos anteriores deberían quedar todas cubiertas.

[1] Via: dame-linux. Un post simple, fácil y para toda la familia. No dejen de hecharle un vistazo.
[2] Vía stealthcopter Fué el mejor post que encontré. Lo instalan en 9.10, pero a mi no me llegó a funcionar. Yo lo he traducido y adaptado a 9.04, pero es una copia de este post.
[3] Foro de nVidia. Problemas a la ejecución de algunas demos.
[4] Foro de nVidia. Error con ficheros gl.h glu.h

CUDA [I] Introducción sobre tarjetas gráficas

[Sobre que me voy a enrollar hoy]
Hace tiempo ya, me picó el gusanillo de la programación de GPU's [1]. Es por todos conocido que las tarjetas gráficas tienen una alta capacidad de procesamiento y que se necesitan para jugar a los juegos de nueva generación. Pero, por que son tan potentes?

[Explicación]
Resulta que este tipo de hardware ha sido pensado para trabajar con mucha paralelización, es decir, muchos cálculos hechos al mismo tiempo.
Para ello, las tarjetas gráficas tienen un reloj relativamente bajo como 500MHz, o 1GHz. Y vosotros me direis: "Si ya! Pero mi PC tiene un procesador de 2.5GHz, esto es más rapido!" Y es cierto, la única diferencia es que lo más seguro es que tu procesador solo tenga un core. Y en el mejor de los casos va a tener dos o cuatro cores.

La diferencia fundamental es que las tarjetas gráficas tienen 64, 128, 256 o incluso 480 cores! Esto significa que cada uno de los 64 cores, por ejemplo, tiene una velocidad de 500MHz. Lo que una simple multiplicación (0.5GHz por 64 cores ) nos da una asombrosa velocidad de reloj de 32GHz. Eso, señores, es bastante mas que 2.5GHz. Se pueden imaginar las últimas tarjetas gráficas como la GTX 480: 480 cores a 1,401GHz = 672 GHz!!

Bien, pero no nos dejemos engañar por las cifras. 672GHz es la capacidad que puede desarrollar una tarjeta haciendo CÁLCULOS PARALELIZABLES! Osea, esto incluye toda una metodología de programación diferente a la "programación tradicional", y no todos los cálculos són paralelizables, claro! Por este motivo tenemos un procesador y una tarjeta gráfica. El procesador se encarga de los programas "unicore" ( no es una afirmación del todo cierta, ahora os lo cuento) y tiene una velociad de reloj relativamente alta, por otra parte la tarjeta gráfica se encarga de ejecutar aplicaciones que pueden ser altamente paralelizables como, [surprise surpriseee], la renderización de imágenes que es lo que se usa en los juegos. Para ello usa velocidades de reloj bajas, pero muchos cores.

Aprovechando que hablo del tema: los procesadores convencionales, a su vez, también disponen de varios cores, osea que realmente también podemos echar las mismas cuentas: Si el procesador es de 2.5GHz y tenemos 4 cores, el procesador tendrá una potencia de 10GHz para procesos paralelizables. Muy importante destacar esto último. La mayoría de programas no utilizan los diferentes cores de un procesador. Por lo que los programas pensados del modo "tradicional" trabajarían a una velocidad de reloj de 2.5GHz, mientras que los que han sido pensados para ser paralelizados trabajarían a una velocidad de 10GHz como máximo ( insisto en esto ).

[Ejemplo serializable]
Vamos a poner un ejemplo: Imaginemos que tenemos 128 números ( vamos a hacer números "redondos" 2^7 ) y queremos comprobar si son números primos o no. Nosotros programamos en un lenguaje convencional como C, por ejemplo, una función de es_primo(numero). Esta función recibe un número determinado, y devuelve verdadero o falso dependiendo si es primo o no. Bien. Pues si tenemos 128 números a comprobar lo que hará el programa será algo así:
Procesador1:
  • es_primo(1)
  • es_primo(2)
  • es_primo(3)
  • es_primo(...)
  • es_primo(127)
  • es_primo(128)
Bien! Entonces, cada llamada a la función es_primo() tardará 1 unidad de tiempo ( es un ejemplo ). Con lo que si llamamos 128 veces a la función tardaremos 128 unidades de tiempo. ok?

Imaginamos que hemos hecho el programa de modo que nosotros utilizamos una tarjeta gráfica que *casualmente* tiene 128 cores. Lo que podemos hacer es asignar a cada uno de los cores un trabajo concreto. Solo le asignamos el trabajo, todavía no lo ejecutamos! Vean:
  • Core1: es_primo(1)
  • Core2: es_primo(2)
  • Core3: es_primo(3)
  • CoreN: es_primo(N)
  • Core128: es_primo(128)
Y ahora, una vez le hemos asignado el trabajo a cada uno de los cores, les decimos a cada uno de ellos: ejecutad. Y todos, a la vez, van a hacer el cálculo. A la vez. Lo que significa que vamos a estar 1 unidad de tiempo para hacer todos los cálculos. Asombroso, verdad? Pero claro, ahora estaréis pensando. Justamente has hecho un ejemplo donde el número de cores són iguales a los números que queremos comprobar!! Vaaaale. Cierto, veamos un último ejemplo. Imaginemos que tenemos una gráfica con solo 64 cores. Seguimos queriendo calcular 128 números. Entonces asignamos dos números a cada core, de modo que queda algo así:
  • Core1: es_primo(1) es_primo(2)
  • Core2: es_primo(3) es_primo(4)
  • Core3: es_primo(5) es_primo(5)
  • CoreN: es_primo(n) es_primo(n+1)
  • Core128: es_primo(127) es_primo(128)
De este modo, cuando el Core1 acabe de ejecutar "es_primo(1)", empezará a ejecutar "es_primo(2)". Cuando demos la orden a todos los cores de que empiezen su trabajo, tardarán 2 unidades de tiempo en realizar el trabajo, ya que cada uno tiene que hacer dos cálculos, pero todos harán sus dos cálculos a la vez. Interesante, verdad?

**Nota: en el ejemplo se considera que el coste de comprobar es_primo(1) es igual a es_primo(128), aunque en realidad no tiene el mismo coste computacional. Es solo para que el ejemplo se entienda.

[Ejemplo no serializable]
Calcular los decimales del número PI. PI no puede calcularse en "partes". No le puedo decir al Core1, cálculame los decimales de PI de 1 a 100 y al Core2 que me calcule los decimales de 101 hasta 200 ya que para calcular los decimales de 101 al 200 se necesita haber encontrado los decimales de 1 a 100. Este cálculo lo hará mejor el procesador, ya que trabaja a una velocidad de reloj más alta.

[Tecnología]
Pues al tener una gráfica de nvidia ( 9600GT ), me ha apetecido probar de programarla. Para ello hay un lenguaje de programación, CUDA. Este lenguaje, que es muy parecido a C, nos permite programar y compilar los programas para que se ejecuten el la/las gráficas que tengamos instaladas. Para ello usaré ubuntu 9.04 ( ya explicaré por qué ) los drivers 195 de nVidia y el SDK que dan en su pagina web.

[Resumiendo...]
CUDA mola. Aprendamos a programar. En la próxima entrega os explico como instalar todo el SDK para programar en CUDA (ardua tarea). Espero no haberles aburrido mucho!

viernes, 26 de marzo de 2010

Criba de Eratóstenes

[Estoy de vacaciones.... y claro, me aburro. Lo mío es ir haciendo cositas, y ahora me encuentro con demasiadas horas por delante vacías]

Bueno, hoy quiero hablar de la Criba de Eratóstenes. Más información en su wiki. De manera resumida es algo así:
Explicación
La criba de Eratóstenes consiste en calcular los números primos menores que N. Este algoritmo es muy eficiente para calcular números primos pequeños ( menores de 10M ).
Para ello utilizaremos un vector de booleanos. Si una celda vale 1, es primo, si vale cero, no lo es. Bien. Al principio ponemos a 1 todos el vector, de modo que, en todos los números sean "primos". Ahora empezamos con el 2 ( ya que todos los números son divisibles entre 1 ). Por cada numero divisible entre 2 menor que N, lo tachamos (4, 6, 8, 10, .... ). Después hacemos lo mismo con el número 3 (6, 9 12...) . Cuando llegamos al número 4, vemos que está tachado ya que es múltiplo de 2, entonces lo ignoramos. Llegamos al 5, y tachamos todos los múltiplos de 5 menores que N. Y así... si llegamos a un número tachado, pasamos al siguiente. Si llegamos a un número que no está tachado, vamos tachando todos sus múltiplos. Al final, los números NO tachados ( con un 1 ), son los números primos. Vean su wiki para ver la representación visual.

Qué he hecho
Bien, pues he hecho un código en C ( estoy aprendiendo a programar ) para calcular los números primos entre 2 y N, siendo N=10.000.000 y que guarda los resultados en un fichero. En mi PC tarda aproximadamente 1.45 segundos. Me he complicado un poco la vida y lo he que uno pueda . Al final he conseguido poner el valor de N tan grande como quiera ( en realidad no es así, ya que estamos limitados por la memória RAM del sistema )calcular los números primos entre 2 y 450.000.000. El fichero resultante pesa unos 400MB.

Compilación
Para compilar el código fuente, lo grabamos en un fichero "criba.c" y lo compilamos así:
$ gcc criba.c -o criba -lm
Y para ejecutar el código tan solo tenemos que escribir:
$ ./criba
Esto nos creará un ficherito "primos.txt" con los resultados.

Configuración
Pues básicamente jugaremos con las constantes N y M. N es el tamaño del bloque y M en número de bloques. Osea, que se van a calcular los números primos que vayan desde 2 hasta N*M. En mi PC N=1M funciona, pero en otro PC igual podría dar fallo. Disminuyese esta cantidad y auméntese en numero de iteraciones ( M ). Recuerden que el algoritmo se vuelve ineficiente a partir de 10M!


Codigo

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
// Each size block
#define N 1000000
// Iterations
#define M 10
//Memory that will be used for store all primes( must be aviable )
#define memory_size M*N*sizeof(long int)*0.08

// Put all values to zero
void initialization(unsigned long int * primes_numbers[]){
int i;
for (i=0;i<memory_size;i++)
(*primes_numbers)[i] = 0;
}

// Save all primes calculated in a file
void save_in_file(unsigned long int * primes_numbers[]){
FILE * fp;
unsigned long long int i;
fp = fopen("primos.txt", "w");
for (i=0;(*primes_numbers)[i];i++)
fprintf(fp, "%ld\n", (*primes_numbers)[i]);
fclose(fp);
}

// Count all the primes calculated
void count(unsigned long int * primes_numbers[]){
unsigned long long int i,j;
j = 0;
for (i=0;(* primes_numbers)[i];i++)
j++;

printf("Total primos encontrados: %lld\n", j);

}

// Check that in the list of prime numbers all are primes
// alert: very slow in very large amount of numbers
void check(unsigned long int * primes_numbers[]){
unsigned long long int i;
for (i=1; (*primes_numbers)[i] != 0; i++){
if ( is_prime((*primes_numbers)[i]) != 1)
printf("FUckkk! %ld\n", (*primes_numbers)[i] );
}
}

// Print all primes calculated
void imprime(unsigned long int * datos[]){
unsigned long long int i;
printf("Llistat:\n");
for (i=0;(*datos)[i]!=0;i++)
printf("%ld\n", (*datos)[i]);
}



int sieve_of_eratosthenes(unsigned long int * primes[], long long int * last_prime_inserted){
char list[N];
unsigned long long int i, j, max;
list[0] = 0;
for (i=2;i<N;i++)
list[i] = 1;

max = sqrt(N)+1;

for (i=2;i<max;i++){
if (list[i])
for (j=2; i*j<N;j++)
list[i*j] = 0;
}
j = 0;
for (i=0;i<N;i++)
if (list[i]){
(*primes)[j] = i;
j++;
}
*last_prime_inserted = j - 1;
return 0;
}

// Calculate the next block of primes
int next(unsigned long int * prime[], unsigned long long int block_number, long long int * last_prime_inserted){
char list[N];
unsigned long long int i, j, min, max;
min = (block_number-1)*N;
max = block_number*N;

//Set all numbers as primes
for (i=0;i<N;i++)
list[i] = 1;
list[0] = 0;

// Mark all numbers alredy calculated
for (i=0;(*prime)[i];i++){
for (j=min/(*prime)[i]; (*prime)[i]*j<max; j++){
if ((*prime)[i]*j>min){
list[((*prime)[i]*j)%N] = 0;
}
}
}

j = *last_prime_inserted;
// Save the new primes
for (i=0;i<N;i++){
if (list[i]){
// printf("%ld j:%ld\n", i+min, j);
(*prime)[j] = i+min;
j++;
}
}
*last_prime_inserted = j - 1;
}

// Calculate all the primes
int calc(int n){
unsigned long long int position_last_prime;
unsigned long int * primes_numbers;
primes_numbers = malloc(memory_size * sizeof(unsigned long int));
initialization(&primes_numbers);
sieve_of_eratosthenes(&primes_numbers, &position_last_prime);
int j;
for (j=2; j<=n; j++){
printf("Calculando %d...\n", j);
next(&primes_numbers, j, &position_last_prime);
}
//imprime(numeros_primos);
printf("Guardando...\n");
save_in_file(&primes_numbers);
//check(&numeros_primos);
count(&primes_numbers);
printf("Done!\n");
free(primes_numbers);
return 0;
}

int main(void){
calc(M);
return 0;
}

int is_prime(int n){
int i, j, prime;
prime = 1;
for (j=2; j<n/2; j++)
if (n % j == 0){
prime = 0;
break;
}
return prime;
}

Fin Codigo

Pues esto es todo, señores. Espero no haberles aburrido demasiado.

lunes, 22 de marzo de 2010

Jugando con MongoDB y Python

Bien, siguiendo el post anterior, vamos a cargar de GeoNames todos los datos sobre España en una base de datos MongoDB. Aqui no se va a explicar como instalar un servidor de Mongo. Se pueden encontrar todas las indicaciones en su pagina web oficial si no sabes que es Mongo, visita esta página. No es nada complicado. Bien, al lío.

Primero tenemos que ir a GeoNames ir a la parte de "descargas" y bajarnos algún país. En mi caso me he descargado ES.txt, documento que contiene todos los todos sobre España. Descomprimido, el fichero pesa unos 6.8MiB. Bien, ahora tenemos que "meterlo" en la base de datos. Lo podemos hacer así:


#! /usr/bin/env python
# -*- coding: utf-8 -*-
#Filename: buscar.py
#Filename: cargar_datos.py
from pymongo.connection import Connection
#Abrimos una conexión con la BBDD de mongo y creamos una colección llamada ES.
connection = Connection()
db = connection.ES
collection = db.ES
#Estos son los campos que contiene el fichero
fields = [
"geonameid",
"name",
"asciiname",
"alternatenames",
"latitude",
"longitude",
"feature_class",
"feature_code",
"country_code",
"cc2",
"admin1_code",
"admin2_code",
"admin3_code",
"admin4_code",
"population",
"elevation",
"gtopo30",
"timezone",
"modification_date"
]

#Abrimos el fichero de datos
file = open('ES.txt', 'r')
#Insertamos todos los datos en la BBDD. Simple y llanamente.
for data in file:
collection.insert(dict(zip(fields, data.split('\t'))))
print 'Done! =)'
#Cerramos el fichero y la conexión.
file.close()
connection.disconnect()

Bien, señores. Ahora solo queda ejecutar el comando con un simple "python cargar_datos.py". En mi ordenador, el proceso tarda unos 25 segundos, aproximadamente. Carga 58.317 registros ( llamados documentos, en la jerga de Mongo ).
Y ya tenemos todos los datos en la BBDD!!

Pero claro, ahora con todos estos datos que hacemos? Pues vamos a crear un pequeño codigo para hacer consultas:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import pymongo

import re
import sys
#Nos conectamos a la BBDD, a la colección ES
db = pymongo.Connection().ES
collection = db.ES

#Cogemos el primer argumentos que nos han pasado como parámetro
busca = sys.argv[1]
#Compilamos una expresión regular para la búsqueda
regex = re.compile(busca)
#Buscamos en la base de datos la expresión regular en el campo "alternatenames". Los resultados los guardamos en una lista.
resultados = [ n for n in collection.find({"alternatenames":regex})]
#Por cada elemento de la lista pintamos los siguientes datos.
for tupla in resultados:
print ">Nombre:",tupla["name"]
print "Nombres comunes:",tupla["alternatenames"]
print "Coordenadas [Longitud][Latitud]:", tupla["latitude"], tupla["longitude"]
print "Link:", "http://maps.google.com/?ie=UTF8&ll=" + str(tupla["latitude"]) + "," + str(tupla["longitude"]) + "&spn=0.047113,0.109863&t=h&z=12"
print "Resultados encontrados:", len(resultados)
print ""


Como funciona el programa? Muy simple:
$ python buscar.py Pollença
Y esto nos va a dar los resultados. Si usamos una terminal Bash, podemos hacer clic con Control pulsado sobre el link y automáticamente se abrirá en Google Maps el la posición exacta del lugar buscado. Espero que se haya entendido algo =). No dejen de postear sus dudas/mejoras. Gracias!

domingo, 14 de febrero de 2010

Borrado seguro de ficheros TrueCrypt con Python [II]

Jugando, he ido mejorando el cachito de codigo que había creado hace poco. De las 15 lineas y aparente inutilidad, ahora tenemos 10 vezes más líenas y es igual de inútil. Pero hace más cosas!! =)

Para ver mas o menos para que sirve el programa, revisar el el primer link, aún así hago un poquito de resumen: Tenemos ficheros TrueCrypt con datos cifrados. Si queremos borrar todos los datos del volúmen, no hace falta sobreescribir todo el volumen varias veces, solo necesitamos borrar los primeros 65.536 bytes de manera segura para dejar inútil el volumen. Os muestro un poquito como funciona el programilla, que por cierto lo he llamado tcrm (TrueCryptReMover). Original? no. Facil de recordar? si ;)

Para descargar programa, click aqui.

Primero tenemos que crear un fichero donde guardaremos las rutas de nuestros containers truecrypt. Cuando ejecutemos el programa tcrm, estos ficheros serán borrados. El fichero, llamado "lista.list" puede ser como el siguiente:
# Check
./tc_container
./tc_container2
./tc_con
./tc_con1
Vale, tenemos lo siguiente. La primera línea "# Check", sirve como control del programa para ver si está cifrado o los datos están en claro. Siempre se debe incluir en el fichero. La palabra en cuestión es facilmente configurable desde el programa tcrm.

Después hay un listado de volúmenes TrueCrypt. Les he puesto estos nombres, pero podrían ser cualquier otros. Aqui puede venir una ruta absoluta o relativa, como se desee. Estos ficheros serán machacados, si se ejecuta el programa. (si algún usuario "windows" me lee, aquí no hay un Control+Z... cuando digo que se borran, no bromeo :P)

Ahora ya tenemos creado nuestro ficherito que apunta a cada uno de los volúmenes que queremos borrar de manera segura. Vamos a ver el ejecutable:
$ ./tcrm --help
-h --help Imprime esta ayuda
-c --cipher Cifra el fichero pasado como parámetro
-d --decipher Descifra el fichero pasado como parámetro
-t --try Comprueba que los volúmenes especificados pueden borrarse
-k --kill Ejecuta el algoritmo de borrado

Pues básicamente tenemos 4 opciones:
  • --cipher: para cifrar el fichero "lista.list", de modo que no se vea la ruta donde nosotros guardamos cada uno de nuestros ficheros TrueCrypt
  • --decipher: para descifrar un fichero ya cifrado. Por si queremos añadir volúmenes adicionales o quitar volúmenes ya existentes en la lista.
  • --kill: abre la "lista.list" y por cada ruta de volúmen, le aplica un borrado Gutmann sobre los primeros 65.536 bytes. Los volúmenes serán imposibles de recuperar.
  • --try: hace un simulacro de borrado. Descifra el fichero "lista.list" y intenta leer cada uno de los volúmenes. Útil para comprobar tema de permisos, etc...
Un ejemplo: Imaginemos que tenemos el fichero "lista.list de antes.
$ ./tcrm --decipher lista.list
> Password: [ponemos nuestra password]

Así ya tenemos nuestra lista cifrada y nadie puede saber dónde guardamos nuestros volúmenes TrueCrypt. Ahora vamos a borrar:
$ ./tcrm --kill lista.list
> Password: [ponemos el password anterior]
> Procesando el fichero "./tc_container"...
> Procesando el fichero "./tc_container2"...
> Procesando el fichero "./tc_con"...
> Procesando el fichero "./tc_con1"...

Amén. Nadie volverá a acceder a los datos de los containers.

Seguridad? Si, dejadme que os cuente un poco.
Cuando introducimos nuestra clave, hacemos un hash SHA512. Diez mil vezes. Para que? Bueeeno, tiene una explicación. Esto no hace más seguro nuestro sistema, sinó que simplemente dificulta 10.000 veces, el posible ataque por fuerza bruta, que serviría para descifrar nuestro fichero y conocer la clave con la que lo hemos cifrado. Para poner un ejemplo fácil: si en un ataque de fuerza bruta se pudiese sacar el password en 10 segundos, con este "inventito" retrasaríamos el ataque hasta 27 horas, para conseguir lo mismo. Una ataque de una hora, ahora duraría un año y un par de meses. Hay que decir que para romer un solo hash de 512 bits se pueden necesitar varios miles de años.

Y después está el cifrado del fichero, que se hace con criptografía simétrica, utilizando el algorítmo AES con una clave de 256 bits (clave resultante de la función de hash mencionada). Para poner otro ejemplo AES256 es el nivel de seguridad que utilizan deteminados gobiernos para sus documentos clasificados y top-secret. Si es bueno para ellos, también lo será para nosotros ^^

Un fallo tremendamente grande, es que el programa está hecho en python, y en texto claro. Por esto es facilmente modificable. Pero bueno, así ya se que tengo que ir mejorando para la próxima entrega del algorítmo.

Nota: sería estupendo recibir críticas a saco: buenas o malas. Si me he dejado algo en la seguridad del programa, si la implementación no es buena, si las notas en inglés estan demasiado mal o cualquier cosa que os parezca que se tiene que cambiar/mejorar.

Saludos!

domingo, 20 de diciembre de 2009

Problema de las N Reinas

Bueno, hecho el post anterior, quiero subir un poquito de código sobre GA. El algorítmo es para solucionar el problema de las N Reinas. El enunciado es el siguiente:
Dado un tablero de ajedrez de NxX colocar N reinas sin que se maten entre ellas.

En principio N és igual a 8, ya que así representamos un tablero de ajedrez normal. Éste problema puede ser resuelto mediante backtracking, y es tremendamente más eficaz que con los GA, pero como la intención es practicar con los algoritmos genéticos, en problema de las N Reinas es suficientemente fácil para empezar. Hay 92 posibles soluciones posibles al problema dado, pero tansolo 12 soluciones únicas ( lo que significa que las otras són combinaciones de éstas mismas )

Implementación en Python del problema de las N Reinas

Disclaimer: Esto lo hago en mi tiempo libre, no tengo a nadie que me instruya ni nadie que me corrija mis fallos. Por esto mismo, seguro que hay mejores implementaciones del código. Pero invito ( o reto ) a que alguien corrija el código, lo modifique a su gusto y lo mejore, y haber si entre todos aprendemos algo =)

Si conces algún sitio donde se pueda encontrar buena documentación o datos relacionados sobre los GA, deja tu comentario please.