Google Gears para GNU/Linux 64 bits (5.4.2)

He estado peleándome con las fuentes de Google Gears y por fín he conseguido generar una versión de Gears para Linux 64 bits :) . Mal comienzo... "Muchos" (desde luego no más de los que estáis leyendo esto) estaréis pensando... ¿Qué es Gears?

Gears es una extensión creada por google para varios navegadores que permite trabajar con aplicaciones web en modo offline (o acelerar la carga de ciertas partes de la página para mejorar la  experiencia del usuario... que marketinera me ha salido esta última frase... :p) (para Firefox está en forma de extensión/complemento, para otros navegadores.. no sé exactamente que "forma" toma).

Información sobre esta extensión hay a montones por internet, al final del artículo os dejo referencias, así que no me entretendré en explicar lo que otros ya han escrito.. (y mucho mejor de lo que llegaría a hacerlo yo). Entonces.. ¿Por qué escribo esto? Pues bien, resulta que Gears no está disponible oficialmente para las versiones de 64 bits de Linux, sólo hay algunas versiones no oficiales... bastante desactualizadas (en estos momentos tienen hasta la 4.9 y la última versión lanzada por google es la 5.4.2) .

Pero... yo he parcheado un poco el código fuente disponible en los repositorios svn, he compilado y finalmente he conseguido una versión funcional para mi navegador de 64 bits. El problema... la versión que he compilado es la 5.6.0, una versión que no ha sido lanzada todavía, así que es posible que tenga algun bug que otro.

Podeis bajarlo de aquí: Google Gears para Linux 64 bits

En breve modifico este artículo y cuelgo el proceso que he seguido (He hecho unas cuantas trampas... :p) (Me he dejado las notas y hasta que no las recupere no podré describirlo suficientemente bién, aunque había algun que otro post en foros de internet, estos se referían a versiones "antiguas" y tampoco dan explicaciones completas)

Proceso:

Antes que nada me he pasado por los foros de Google y visité una discusión que trataba el tema, en ella se mostraban diferentes (en realidad sólo 2), el parche que apliqué yo está basado en el primero de los que se exponen (modificado, pues el parche se hizo para una versión bastante antigua).

Pues bién, el primer paso consiste en descargar el código del svn con el siguiente comando (yo trabajé con la revisión 3093):
svn checkout http://gears.googlecode.com/svn/trunk/ gears-read-only

Una vez hecho esto modificaremos el fichero gears/tools/config.mk cambiando la línea
ARCH = i386 por
ARCH = x86_64 ,
la línea
 MODE = dbg por
MODE = opt ,
y la línea
COMPILE_FLAGS = -c -o $@ -fPIC -fmessage-length=0 -Wall -Werror $(COMPILE_FLAGS_$(MODE)) por
COMPILE_FLAGS = -c -o $@ -fPIC -fmessage-length=0 -Wall $(COMPILE_FLAGS_$(MODE))
éste último cambio lo hacemos por que si no los warnings no nos dejarán compilar (ya advertí que seguramente tiene algun que otro error escondido la versión que compilé).

Pasemos al siguiente fichero, el cambio se hace por que los punteros en sistemas de 64 bits son más grandes. Abrimos el fichero gears/localserver/firefox/async_task_ff.cc y cambiamos la siguiente línea:
OnListenerEvent(msg_code, reinterpret_cast<int>(msg_param)); por ésta otra:
OnListenerEvent(msg_code, reinterpret_cast<long>(msg_param));

Aquí es donde yo empecé a aplicar mis propios cambios (que son una tontería, pero permitieron que consiguiera compilar).

En los siguientes ficheros:

  • third_party/googleurl/src/url_parser.cc
  • gears/base/common/http_utils.cc
  • gears/geolocation/backoff_manager.cc

añadiremos la línea (al principio de todo):
#include <stdlib.h>

En los siguientes:

  • third_party/jsoncpp/json_reader.cc
  • third_party/jsoncpp/json_value.cc
  • gears/base/common/string16.h
  • gears/base/common/http_utils.cc

añadiremos la línea (al principio de todo):
#include <string.h>

Y por último, en el fichero gears/base/common/str_utils.cc añadiremos la línea:
#include <limits.h>

Para continuar tendremos que instalar los paquetes de desarrollo de Firefox 3 y del Xulrunner 1.9, yo desde mi Ubuntu 8.10 lo hice así:
aptitude install xulrunner-dev firefox-dev

Ésto lo hacemos para tener las librerías de 64 bits que utilizaremos para reemplazar las de 32 bits que hay en el código que nos hemos bajado y así poder enlazar correctamente los binarios que deseamos obtener. Estos ficheros los sustituiremos por la versión instalada en nuestro sistema:

  • third_party/gecko_1.9/linux/gecko_sdk/lib/libxpcom.so
  • third_party/gecko_1.9/linux/gecko_sdk/lib/libxpcomglue.a
  • third_party/gecko_1.9/linux/gecko_sdk/lib/libxpcomglue_s.a
  • third_party/gecko_1.9/linux/gecko_sdk/lib/libnspr4.so
  • third_party/gecko_1.9/linux/gecko_sdk/bin/xpidl
  • third_party/gecko_1.9/linux/gecko_sdk/bin/xpt_link

Pero el trabajo no se acaba aquí, continuemos. Nos movemos al siguiente directorio:
third_party/gecko_1.9/linux/gecko_sdk/bin
y ejecutamos los siguientes comandos:
chmod +x xpidl
chmod +x xpt_link

El siguiente paso es el más lento de todos (y el más sencillo), tecleamos en la línea de comandos dentro del directorio gears :
make BROWSER=FF3

Una vez hecho esto ya casi estaremos. Creamos un directorio fuera del que creó svn al descargar las fuentes, le llamaremos XPI . Entramos en él y ejecutamos el siguiente comando para descargar el paquete actual de Gears (para 32 bits):
wget http://dl.google.com/gears/current/gears-linux-opt.xpi

Lo descomprimimos (en realidad es un zip normal y corriente):
unzip gears-linux-opt.xpi

Ahora tendremos que modificar algunos ficheros, sustituir otros, comprimir... y ya estaremos! Abrimos el fichero install.rdf y modificamos las siguientes líneas:
<!-- Prevent this XPI from being installed on the wrong platform. -->
<em:targetPlatform>Linux_x86-gcc3</em:targetPlatform>
<!-- Ubuntu Edgy Eft requires "linux-gnu" for the OS_TARGET prefix. -->
<em:targetPlatform>linux-gnu_x86-gcc3</em:targetPlatform>

por éstas otras:
<!-- Prevent this XPI from being installed on the wrong platform. -->
<em:targetPlatform>Linux_x86_64-gcc3</em:targetPlatform>
<!-- Ubuntu Edgy Eft requires "linux-gnu" for the OS_TARGET prefix. -->
<em:targetPlatform>linux-gnu_x86_64-gcc3</em:targetPlatform>

Entramos en el subdirectorio components . Allí sustituiremos los ficheros gears.xpt y libgears.so (el fichero libgears_ff2.so no lo tocaremos por que no hemos compilado nada para Firefox 2, aun así, si queréis tenerlo, simplemente tenéis que cambiar FF3 por FF2 en el make anterior) por las nuevas versiones que habremos generado, que se encontrarán en el directorio
gears/bin-opt/linux-x86_64/ff3/

Una vez hecho esto comprimimos otra vez el directorio (si os ha quedado el .xpi de google anterior dentro, quitadlo de allí) . Notad que tenéis que comprimirlo con el formato zip (ninguno otro servirá). Al fichero resultante le ponéis la extensión xpi y por fin podréis instalarla y provarla!! ;)

Referencias:

Testeando la velocidad de carga de las libjpeg con un pequeño programa

Buenas, esta mañana he programado un pequeño programa que sirve para comprovar cuanto tarda la librería jpeg en cargar las imágenes jpeg contenidas en un directorio (analizándolo recursivamente). Hace tiempo que no programaba nada, y la verdad es que me ha sentado bién, lo colgaré por si a alguien le interesa. Se puede aprender algo del código.. aunque poco:

  • Como recorrer una estructura de directorios en entornos UNIX-like (por ejemplo GNU/Linux) y distinguir las entradas de éste (para saber si son ficheros normales, directorios, enlaces...)
  • Como cargar en memoria imágenes jpeg con las librerías libjpeg, que por lo general están muy mal documentadas en internet.

Empezemos: para comenzar, deberemos instalar en nuestro sistema las librerías libjpeg (así como los archivos de cabecera para poder incluírlos en nuestro código fuente, en sistemas debian el paquete es algo así como libjpeg-dev, en Ubuntu Hardy el paquete se llama libjpeg62-dev).

Nota 1: en el código fuente no he incluído comprovación alguna para que se distingan las imágenes jpeg de las imágenes que no lo son, se debería hacer alguna comprovación sobre el nombre, por ejemplo. No lo he hecho porque no me hacía falta (sí, he hecho el programa para algo útil, aunque no lo parezca, era algo así como un benchmark)

Nota 2: no he incluído ninguna comprovación en el código para que trate los archivos que enlazan a otros, no me hacía falta de la misma forma que antes, en todo caso, si buscáis en google el nombre de las funciones que he utilizado para hacer la distinción de ficheros y directorios os aparecerá el nombre de la función que indica si estamos tratando con enlaces. Por otro lado, si imprimimos por pantalla en modo octal el entero que pasamos como argumento a esa función, veremos que corresponde a los permisos del fichero, y nosotros mismos podríamos programar una función que nos indicara que tipo de entrada estamos tratando.

Nota 3: xD, no, no hay nota n . Bueno, ahora en serio, para compilar el código se tiene que pasar el argumento -ljpeg al gcc (bueno, he presupuesto que utilizamos gcc, los que lo quieran hacer con otro compilador se tendrán que espavilar, si es que a alguien le interesa hacer esto, jejeje).

Finalmente os muestro el código :) (puede que en los días siguientes pula un poco el código y los comentarios, que son un poco chapucheros) :

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

#include <sys /types.h> //
#include </sys><sys /stat.h>  // estructura stat
#include <unistd .h>    // mkdir, chdir
#include <dirent .h>    // dirent
 
#include <stdio .h>     // para fopen
#include <stdlib .h>    // para malloc
#include <string .h>    // strcmp
#include <time .h>      // clock
 
#include <setjmp .h>    //libjpeg
#include <jpeglib .h>   //libjpeg
 
/* Defineixo una estructura simple per apilar directoris */
typedef struct s_stack {
    struct s_stack *next;
    DIR  *dir;
} stack;
 
int main() {
    struct  dirent  *dir_entry;
    char    names_buffer[1024];
 
    /* Estructures per manejar la imatge en memòria */
    struct jpeg_decompress_struct cinfo;
    struct jpeg_error_mgr         jerr;
 
    /* Estructures per manejar directoris */
    struct stat                   estat;
    stack                  *dirs, *t_dirs;
 
    /* Punters per manejar la memòria de les imatges */
    unsigned char *image;
    unsigned char *ptr;
 
    /* Manejador de fitxer */
    FILE *f;
 
    /* Variable per comptar el temps emprat per carregar imatges */
    clock_t t, T;
 
    dirs = (stack *)malloc(sizeof(stack));
    if(dirs==NULL) {
        printf("Memoria insuficient!\n");
        exit(-1);
    }
    dirs->next = NULL;
 
    getcwd(names_buffer, 1024);
    dirs->dir = opendir(names_buffer);
 
    T = clock();
    while((dir_entry = readdir(dirs->dir)) != NULL || dirs->next != NULL) {
        if(dir_entry == NULL) {
 
            printf("En aquest directori no hi ha més entrades...\n");
            if(dirs->next == NULL) {
                printf("Sortint de %s...\n", dir_entry->d_name);
                exit(0);
            }
            t_dirs = dirs;
            dirs = dirs->next;
            free(t_dirs);
            chdir("..");
            continue;
        }
 
        if(strcmp(dir_entry->d_name, ".")==0 || strcmp(dir_entry->d_name, "..")==0)
            continue;
 
        if( lstat(dir_entry->d_name, &estat) < 0 ) {
            printf("Error al fer lstat sobre %s!\n", dir_entry->d_name);
            exit(-1);
        }
 
        if(S_ISDIR(estat.st_mode)) {
            printf("Entrant en %s ...\n", dir_entry->d_name);
            t_dirs = (stack *)malloc(sizeof(stack));
            if(t_dirs==NULL) {
                printf("Memoria insuficient!\n");
 
                do {
                    t_dirs = dirs;
                    dirs = dirs->next;
                    free(t_dirs);
                } while(dirs!=NULL);
 
                exit(-1);
            }
 
            t_dirs->next = dirs;
            t_dirs->dir = opendir(dir_entry->d_name);
            chdir(dir_entry->d_name);
            dirs = t_dirs;
 
            continue;
        }
        else if(S_ISREG(estat.st_mode)) {
            /* Obrim el descriptor de fitxer de la imatge */
            printf("\tObrint la imatge %s ... ", dir_entry->d_name);
 
            t = clock();
 
            f = fopen(dir_entry->d_name, "r");
            if(f==NULL) {
                printf("No s'ha pogut obrir el fitxer!\n");
                exit(1);
            }
 
            /* Carreguem la informació de la imatge */
            cinfo.err = jpeg_std_error(&jerr);
            jpeg_create_decompress(&cinfo);
            jpeg_stdio_src(&cinfo, f);
            jpeg_read_header(&cinfo, 1);
            jpeg_start_decompress(&cinfo);
 
            /* Reservem memòria per carregar la imatge */
            image = malloc(cinfo.output_width * cinfo.output_height * 3);
 
            /* Carreguem la imatge en memòria */
            ptr=image;
            while (cinfo.output_scanline < cinfo.output_height) {
                jpeg_read_scanlines(&cinfo, &ptr, 1);
                ptr += 3 * cinfo.output_width;
            }
 
            /* Deixem de manejar la imatge */
            jpeg_finish_decompress(&cinfo);
            jpeg_destroy_decompress(&cinfo);
 
            /*Alliberem memòria reservada*/
            free(image);
 
            /* Tanquem (per si un cas) el descriptor de fitxers */
            fclose(f);
 
            printf("%.16G segons\n", (clock()-t)/(double)CLOCKS_PER_SEC);
        }
    }
 
    closedir(dirs->dir);
 
    printf("---\nTemps total: %.16G segons\n", (clock()-T)/(double)CLOCKS_PER_SEC);
 
    return 0;
}

Cambiar la MAC de un dispositivo de red

Este es un pequeño post que no pretende aportar mucho a la comunidad.. ya que lo que colgaré se puede encontrar muy fácilmente con Google, pero me importa más bien poco, más que nada lo colgaré para acordarme yo :) .

Primero de todo.. ¿Por qué querríamos cambiar la MAC de nuestro dispositivo de red? Pues porque existen sitios donde sólo se pueden conectar ciertas máquinas autorizadas.. las cuales son distinguidas por los routers a través de su dirección MAC... y a veces nos gustaría conectarnos a dichas redes. Es por eso que tendremos que falsificar la MAC de nuestro dispositivo de alguna manera (por lo general cambiándola por la mac de algun dispositivo que sepamos que está autorizado... y sobretodo, desconectado en el momento de nuestra conexión).

En este post me centraré en sistemas GNU/Linux, utilizando el programa macchanger. Si trabajamos desde Ubuntu o Debian, para instalar el programa será tan fácil como escribir

1

aptitude install macchanger

o bién

1

apt-get install macchanger

Si trabajamos desde cualquier otra distribución... ni idea, yo lo que recomiendo es buscar el típico tarball de código fuente y ejecutar los también típicos comandos make y make install.

A lo que vamos, antes que nada, deberíamos desactivar la red con el comando siguiente:

1

/etc/inid.d/networking stop

o bién con:

1

ifdown dispositivo [el dispositivo puede ser: eth0, eth1, wlan0...]

Después de eso, deberíamos guardar la mac original del dispositivo, por si acaso. Para hacer eso simplemente hace falta ejecutar el comando ifconfig y se nos mostrará la mac asociada a cada dispositivo de red. Dicho todo esto, pasemos a la acción (desde root) con el siguiente comando:

1

macchanger --mac XX:XX:XX:XX:XX:XX dispositivo

donde XX:XX:XX:XX:XX:XX es la mac que queremos establecer para nuestro dispositivo, así de simple :D .

Por si alguien tiene curiosidad sobre por qué he escrito esto, bueno, diremos simplemente que lo estoy utilizando en la universidad para conectarme a través de la red cableada con mi portátil :) . (Espero que no aparezca nadie que me quiera sancionar por esto, xD.

Bueno, hasta otra :) .

Que le den por saco a Debian

Buenas, hace bastante tiempo que no escribo nada... y la verdad, en este tiempo he estado haciendo muchas cosas, jeje, tengo mucho sobre que escribir.

Empecé a trabajar en Newcomputing Netservices el día 15 de Julio, estuve casi unos 15 días de pruebas y cuando me íban a contratar, les tuve que decir que no me interesaba por cuestiones personales (y porque tenía una carga de trabajo que no me gustó nada, tenía que llevarme el trabajo a casa :S ). El caso es que durante esos días me tuve que esforzar bastante y aprendí muchas cosas.

Justo después de dejar la empresa me fuí a trabajar de becario en la UAB en un proyecto de Mitsubishi, y aquí estoy todavía. La verdad es que no mandan mucho trabajo, y nos pasamos casi una hora en el bar cada mañana (en teoría yo tengo que trabajar 4 horas diarias), pero aún así intento aprovechar el tiempo.

Actualmente estoy haciendo una LFS (Linux From Scratch) en una pequeña partición de mi máquina de trabajo, es interesante ver como contruir un sistema GNU/Linux desde cero, y supongo que ayuda a entender los entresijos de su funcionamiento :p . Por otro lado, mientras dejo compilando las piezas del sistema me entretengo leyendo artículos, libros o lo que me pase por las manos. Así que bueno, he tenido tiempo para hacer bastantes cosas:

  • mejorar la cutrada del oggtube (he hecho que no requiera Qt, por si alguien no quiere utilizar la interfície gráfica)
  • Hacer una aplicación de seguimiento para mi portátil, en caso de robo, si el ladrón fuese lo suficientemente imbécil como para conectar mi portátil a Internet antes de borrar todo su contenido, ése dejaría un aviso en una aplicación que he hecho en ésta misma página. Le quedan bastantes detalles para que sea una aplicación realmente útil, pero bueno, iré haciendo algo, y ya os colgaré el código. (He aprendido a hacer daemons con esto)
  • Estoy haciendo un pequeño compilador para un lenguaje cutrillo, estoy siguiendo diversos tutoriales combinados con mi imaginación, de momento es capaz de generar código ensamblador para x86 y para x86_64... aunque no tiene mucho mérito, jeje, ¡solo reconoce 4 órdenes, xD!
  • Mandar a tomar por saco Debian (a cambio, he instalado Ubuntu), que es lo que daba nombre a éste artículo. Me encanta trastear con los detalles técnicos de la máquina, solventar pequeños errorcillos de vez en cuando, eso a uno le sube la moral... pero ya estaba harto de tener que retocar tantas cosas para cada tontería... pero sobre todo, de lo que me he hartado es de KDE. Le he cogido manía, sólo se salvan: Amarok, Yakuake, Kate, K3b, Katapult, KDevelop y KOrganizer (aunque yo no lo utilizo). El caso es que K3b lo he cambiado por Brasero, que va muy bién, Katapult lo he cambiado por Gnome-do, que va mucho mejor, y bueno, Yakuake lo cambiaré cuando Guake sea lo suficientemente estable, además, KDevelop no lo utilizo casi nunca y KOrganizer tampoco, definitivamente me he convertido a usuario de Gnome, que és mucho más bonito, aunque sea más pesado. (No he mencionado Konqueror ni Dolphin, porque aunque tienen una cosa que me gusta mucho, las pestañas o la Split View, pronto se hará lo mismo con Nautilus). Por otro lado, en Gnome hay utilidades muy, pero que muy interesantes, como F-Spot o Tracker, que aún no tienen rival claro en KDE.
  • He aprendido cosillas bastante interesantes sobre virtualización de entornos, sobre todo por lo del LFS, que también lo quiero provar en mi máquina, pero también por un proyecto que me mandaron en Newcomputing.
  • He renovado mis conocimientos sobre PHP, MySQL, y he aprendido bastante sobre las GTK y PHP-GTK, en parte por un proyecto que me mandaron en Newcomputing, en parte por experimentos propios...

Muchas cosas, jeje, tengo que liberar bastantes piezas de código, aunque primero creo que las tengo que pulir para que no den pena, son más interesantes por el hecho de que introducen conceptos (para los novatillos, entre los que me encuentro) y por que hay pocas utilidades libres con esos usos que por su calidad.

Añado que me he columpiado bastante en la organización del concurso de programación GNUAB, y a partir de mañana me pondré a hacer todo el trabajo atrasado que tengo... Quiron me va a matar!

P.D.: ¡Fedora es una mierda! Por otra cosa no será... pero.. ¿porque no reconoce ya la gente de Red Hat que apt, aptitude, dpkg y deb (aunque sean mejorables) son clarament superiores a yum, y rpm?

Haciendo extensiones para Python

El otro día me planteé la cuestión de cómo crear un módulo para Python que fuera más eficiente que el propio Python, es decir, sin escribirlo en Python. Me puse a mirar la documentación oficial y lo encontré fácilmente, la verdad es que Python está muy bien documentado (cambiaría algunas cosillas, pero más por gustos personales que por que crea que están mal). La principal forma de crear módulos eficientes para Python es hacerlos en C o C++, y ésta es la forma que seguí yo. Antes de continuar, os preguntaréis... ¿Por qué querías hacer un módulo eficiente para Python? Pues... ni idea, jeje, por experimentar, y por ver si con mis conocimientos recién adquiridos (sí, realmente recién adquiridos) de métodos numéricos soy capaz de hacer una buena librería de cálculo científico (en particular para aplicar técnicas de interpolación) para Python. Sólo he visto la PyGMP, pero es posible que sea demasiado general, y no incluye algoritmos de interpolación (que es, en definitiva, lo que yo quiero hacer).

Por ahora sólo he incluido dos algoritmos muy sencillos, el de Neville para evaluar polinomios en un punto (de momento sólo real), y el método de las diferencias divididas de Newton, que nos da las diferencias divididas con las que podemos construir un polinomio interpolatorio. De momento he hecho sólo éstos dos porque he estado haciendo pruebas, y entre ellas han habido pruebas de rendimiento... la verdad es que me quedé pasmado al ver la diferencia entre C y Python (sí, ya sabía que Python era más lento, pero no tanto). El algoritmo de Neville llega a ser un 862% más rápido escrito en C que en Python (tarda sólo un 11.5% de lo que tardaría si estuviera escrito en Python), además, aunque no lo he comprobado, creo que a medida que aumentamos los puntos de soporte, el margen de tiempo aumenta todavía más (supongo que habrá un límite).

Ahora pasaré a explicar brevemente como lo he hecho, aunque para el que quiera profundizar, tendría que leer la documentación de Python directamente, esto debería ser sólo un ejemplo. Lo primero que debemos hacer es crear el código que queremos transformar en un módulo python (ya desde el principio tenemos que empezar utilizando los tipos de la API de Python):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298

#include <Python.h>
 
static PyObject *interpolation_iaval(PyObject *self, PyObject *args)
{
    double x;
    PyObject *a, *fa;
    PyObject *tmp;
    
    unsigned n, i, j;
    
    double *da, *dfa;
    
    if (!PyArg_ParseTuple(args, "dOO", &x, &a, &fa))
        return PyExc_AttributeError;
    if(!(PyList_Check(a) || PyList_Check(fa)))
        return PyExc_AttributeError;
    n = PyList_Size(a);
    if(n!=PyList_Size(fa))
        return PyExc_IndexError;
    
    da  = (double *)malloc(n*sizeof(double));
    dfa = (double *)malloc(n*sizeof(double));
    
    if(da==NULL || dfa==NULL)
    {
        if(da)  free(da);
        if(dfa) free(dfa);
        return PyErr_NoMemory();
    }
    
    for(i=0; i<n; i++)
    {
        tmp = PyList_GetItem(a, i);
        if(!PyFloat_Check(tmp))
        {
            free(da);
            free(dfa);
            return PyExc_AttributeError;
        }
        da[i] = PyFloat_AsDouble(tmp);
        
        tmp = PyList_GetItem(fa, i);
        if(!PyFloat_Check(tmp))
        {
            free(da);
            free(dfa);
            return PyExc_AttributeError;
        }
        dfa[i] = PyFloat_AsDouble(tmp);
    }
    
    n--;
    for(i=1; i<=n; i++)
        for(j=n; j>=i; j--)
            dfa[j] = ((x-da[j-i])*dfa[j]-(x-da[j])*dfa[j-1])/(da[j]-da[j-i]);
    
    x = dfa[n];
    
    free(da);
    free(dfa);
    
    return Py_BuildValue("d", x);
}
 
static PyObject *interpolation_divdif(PyObject *self, PyObject *args)
{
    PyObject *a, *fa;
    PyObject *tmp;
    
    unsigned n, i, j;
    
    double *da, *dfa;
    
    if (!PyArg_ParseTuple(args, "OO", &a, &fa))
        return PyExc_AttributeError;
    if(!(PyList_Check(a) || PyList_Check(fa)))
        return PyExc_AttributeError;
    n = PyList_Size(a);
    if(n!=PyList_Size(fa))
        return PyExc_IndexError;
    
    da  = (double *)malloc(n*sizeof(double));
    dfa = (double *)malloc(n*sizeof(double));
    
    if(da==NULL || dfa==NULL)
    {
        if(da)  free(da);
        if(dfa) free(dfa);
        return PyErr_NoMemory();
    }
    
    for(i=0; i<n; i++)
    {
        tmp = PyList_GetItem(a, i);
        if(!PyFloat_Check(tmp))
        {
            free(da);
            free(dfa);
            return PyExc_AttributeError;
        }
        da[i] = PyFloat_AsDouble(tmp);
        
        tmp = PyList_GetItem(fa, i);
        if(!PyFloat_Check(tmp))
        {
            free(da);
            free(dfa);
            return PyExc_AttributeError;
        }
        dfa[i] = PyFloat_AsDouble(tmp);
    }
    
    n--;
    for(i=1; i<=n; i++)
        for(j=n; j>=i; j--)
            dfa[j] = (dfa[j]-dfa[j-1])/(da[j]-da[j-i]);
    n++;
    tmp = PyList_New((Py_ssize_t)(n));
    for(i=0; i<n; i++)
        PyList_SetItem(tmp, (Py_ssize_t)i, PyFloat_FromDouble(dfa[i]));
    
    return tmp;
}
 
 
static PyObject *interpolation_hermite(PyObject *self, PyObject *args)
{
    PyObject *pa, *pfa;
    PyObject *t1, *t2;
    
    unsigned n, m, i, j, k, s;
    
    double   *a, **dfa, *dd, t;
    unsigned *nf;
    
    /* Codi de preparació pel còmput i de comprovacions */
    // printf("Inici de les preparacions...\n");
    if (!PyArg_ParseTuple(args, "OO", &pa, &pfa))
        return PyExc_AttributeError;
    if(!(PyList_Check(pa) || PyList_Check(pfa)))
        return PyExc_AttributeError;
    n = PyList_Size(pa);
    if(n!=PyList_Size(pfa))
        return PyExc_IndexError;
    
    nf  = (unsigned *)malloc(n*sizeof(unsigned));
    dfa = (double  **)malloc(n*sizeof(double*));
    
    if(dfa==NULL || nf ==NULL)
    {
        if(dfa) free(dfa);
        if(nf)  free(nf);
        return PyErr_NoMemory();
    }
    
    m = 0;
    for(i=0; i<n; i++)
    {
        t1 = PyList_GetItem(pfa, i);
        if(!PyList_Check(t1))
        {
            free(dfa);
            free(nf);
            
            return PyExc_AttributeError;
        }
        
        nf[i]  = (unsigned)PyList_Size(t1);
        m += nf[i];
        dfa[i] = (double *)malloc(sizeof(double)*nf[i]);
        if(dfa[i]==NULL)
        {
            for(k=0; k<=i; k++)
                free(dfa[k]);
            free(dfa);
            free(nf);
            
            return PyErr_NoMemory();
        }
        for(j=0; j<nf[i]; j++)
        {
            t2 = PyList_GetItem(t1, j);
            if(!PyFloat_Check(t2))
            {
                for(k=0; k<=i; k++)
                    free(dfa[k]);
                free(dfa);
                free(nf);
                return PyExc_AttributeError;
            }
            dfa[i][j] = PyFloat_AsDouble(t2);
        }
    }
    
    dd = (double *)malloc(sizeof(double)*m);
    a  = (double *)malloc(sizeof(double)*m);
    
    if(a == NULL || dd == NULL)
    {
        if(a)  free(a);
        if(dd) free(dd);
        for(i=0; i<n; i++)
            free(dfa[i]);
        free(dfa);
        free(nf);
        
        return PyErr_NoMemory();
    }
    
    for(k=0, i=0; i<n; i++)
    {
        t2 = PyList_GetItem(pa, i);
        if(!PyFloat_Check(t2))
        {
            if(a)  free(a);
            if(dd) free(dd);
            for(i=0; i<n; i++)
                free(dfa[i]);
            free(dfa);
            free(nf);
            
            return PyExc_AttributeError;
        }
        t = PyFloat_AsDouble(t2);
        
        for(j=0; j<nf[i]; j++, k++)
        {    
            a[k]  = t;
            dd[k] = dfa[i][0];
        }
    }
    /* Final de les comprovacions i de la preparació del còmput */
    // printf("Final de les comprovacions...\n");
    
    // printf("Inici del còmput...\n");
    /* Inici del còmput */
    m--;
    for(i=1; i<=m; i++)
        for(j=m; j>=i; j--)
        {
            if(a[j]!=a[j-i])
                dd[j] = (dd[j]-dd[j-1])/(a[j]-a[j-i]);
            else
            {
                t = a[0];
                for(s=k=0; k<n; k++)
                {
                    if(a[k]==a[j])
                        break;
                    if(a[k]!=t)
                    {
                        t = a[k];
                        s++;
                    }
                }
                dd[j] = dfa[s][i]/((double)fact(i));
            }
        }
    // printf("Final del comput...\n");
    
    // printf("Conversio de tipus...\n");
    m++;
    t1 = PyList_New((Py_ssize_t)(m));
    for(i=0; i<m; i++)
        PyList_SetItem(t1, (Py_ssize_t)i, PyFloat_FromDouble(dd[i]));
    // printf("Conversio realitzada...\n");
    
    // printf("Alliberant memòria...\n");
    free(nf);
    free(dd);
    for(i=0; i<n; i++)
        free(dfa[i]);
    free(dfa);
    // printf("Memoria alliberada...\n");
 
    return t1;
}
 
static PyMethodDef interpolationmethods[] = {
    {"iaval", interpolation_iaval, METH_VARARGS,
     "float iaval(x,[x1,x2,...,xn], [f(x1),f(x2),..,f(xn)])\n"
     "Neville's method for Lagrange's interpolation\n"
     "This function returns the value of the interpolation polynomial on the given point (x)." },
    {"divdif", interpolation_divdif, METH_VARARGS,
     "divdif([x1,x2,...,xn], [f(x1),f(x2),...,f(xn)])\n"
     "Newton's Divided differences method for Lagrange's Interpolation\n"
     "This function returns the divided differences of the Newton's divided differences interpolation polynomial."},
    {"hermite", interpolation_hermite, METH_VARARGS,
     "hermite([x1,x2,...,xn], [[f(x1),f'(x1),...,f(m1)(x1)],...,[f(xn),f'(xn),...,f(mn)(xn)]])\n"
     "Hermite's method for Lagrange's Interpolation\n"
     "This function returns the divided differences of the Hermite's divided differences interpolation polynomial."},
    {NULL, NULL}             /* sentinel */
};
 
DL_EXPORT(void) initinterpolation()
{
    Py_InitModule("interpolation", interpolationmethods);
}

Una vez escrito el código tendría que explicarlo... pero en serio, da pereza explicarlo, :p, mirad la referencia de Python online http://docs.python.org/ext/ext.html (Extendiendo Python, en inglés), http://docs.python.org/api/api.html (Python/C API Reference Manual). Después de entender lo que hemos escrito, tenemos que hacer que sea accesible desde el intérprete Python. Desde al versión 2.3 tenemos un método muy sencillo. Este se basa en crear una especie de "instalador" en un pequeño archivo Python que cuando es interpretado construye e instala el módulo para que pueda ser utilizado sin ningún problema.

1
2
3
4
5
6
7
8
9

from distutils.core import setup, Extension
 
module1 = Extension('interpolation',
                    sources = ['interpolationmodule.c'])
 
setup (name = 'interpolation',
       version = '0.1',
       description = 'Interpolation Package',
       ext_modules = [module1])

Por cierto, el fichero C lo llamé interpolationmodule.c, y a éste fichero Python lo llamaremos setup.py. Para construir el módulo escribimos python setup.py build . Para instalarlo debemos entrar en modo administrador y escribir lo siguiente: python setup.py install . Y con esto finaliza la instalación del módulo. Si queréis probarlo sólo hace falta escribir import interpolation en el intérprete, las funciones disponibles son iaval (método de Neville) y divdif (método de las diferencias divididas). Para los que queráis probar las diferecias de rendimiento, podéis importar el módulo timeit, que se utiliza como sigue.

Asignamos a una variable un objeto Timer:
t = timeit.Timer("interpolation.iaval(3.0, [2.0, 4.0], [5.0, 6.0])", "import interpolation")
Luego ejecutamos la función timeit() del objeto que hemos creado. Ésta función lo que hará será llamar a la función que le hemos indicado un millón de veces dentro del entorno que le indicamos en el segundo parámetro. Una vez acabe su trabajo, nos indicará el tiempo transcurrido. Si creamos una función en Python que haga el mismo trabajo y le damos los mismos datos, veremos con timeit la gran diferencia de rendimiento que hay entre ambas.

Bueno, acabo este artículo nada reflexivo, aunque espero, entretenido para frikis como yo.