Programando un bindiff en C++
Hola :), en este articulo voy a tratar de explicar (porque no se si lo lograre) paso a paso como programar un bindiff genérico en C++ (bah lo puedes programar en lo que se te cante, pero el código lo hice en C++). Si hay algo que no se entiende seguramente sea culpa mía porque soy pésimo expresándome, así que no le traten de dar muchas vueltas a algo que no se entienda. Por último como no soy perfecto pueden haber errores, en realidad si soy perfecto pero me gusta tener errores por a propósito, porque quiero ser como tu!. Bueno ahora si, enserio, empecemos…
Seguramente conozcan la utilidad diff en sistemas UNIX, cuando se realiza un diff de dos archivos A y B, se genera C que contiene los cambios que hay que realizarle a A para obtener B. El comando diff esta pensado para trabajar con archivos de texto, en este articulo voy a explicar como implementar un diff genérico que pueda ser usado con cualquier tipo de archivos.
Subsecuencia Común mas Larga
Para implementar nuestro diff, vamos a partir de un algoritmo que se encarga de hallar la subsecuencia común máxima entre dos secuencias. La implementación más simple es algo así:
{
if (!i || !j)
return SubSeq() ;
if (X[i-1] == Y[j-1])
return LCS(i-1, j-1) + (i-1) ;
else
return max(LCS(i, j-1), LCS(i-1, j)) ;
}
X e Y son los dos buffers que queremos comparar, i y j sus respectivos tamaños. SubSeq es el tipo de datos que contiene una subsecuencia, max() compara dos subsecuencias y devuelve la mayor, por ultimo el operador suma (sobrecargado) devuelve la subsecuencia formada por los elementos de la subsecuencia del primer operando mas el elemento del segundo.
Sabiendo todo esto podemos implementar una clase para trabajar con un par de secuencias X, Y:
{
const char *X ;
const char *Y ;
public:
class SubSeq
{
std::list<size_t> elem ;
public:
SubSeq operator+(const size_t &r)
{
SubSeq ret(*this) ;
ret.elem.push_back(r) ;
return ret ;
}
bool operator<(SubSeq &r)
{
return (elem.size() < r.elem.size()) ;
}
void print(const char *buff)
{
for (std::list<size_t>::iterator b = elem.begin(); b != elem.end(); ++b)
std::cout << buff[*b] ;
std::cout << std::endl ;
}
} ;
SeqPair(const char *a, const char *b) : X(a), Y(b) {}
SubSeq LCS(size_t i, size_t j)
{
if (!i || !j)
return SubSeq() ;
if (X[i-1] == Y[j-1])
return LCS(i-1, j-1) + (i-1) ;
else
return max(LCS(i, j-1), LCS(i-1, j)) ;
}
SubSeq max(SubSeq a, SubSeq b)
{
return (a < b) ? b : a ;
}
} ;
Por el momento X e Y van a ser simples buffers de bytes, veamos que tal funciona el algoritmo:
{
char *s1 = "hola el mundo" ;
char *s2 = "hola mundo caca" ;
SeqPair test(s1, s2) ;
test.LCS(strlen(s1),strlen(s2)).print(s1) ;
return 0 ;
}
Corremos el programa:
$ time ./test
hola mundo
7.43user 0.00system 0:07.47elapsed
Pff… ocho segundos para encontrar esa cadena chota, intentemos compilar con -O3.
$ time ./test
hola mundo
2.24user 0.00system 0:02.30elapsed
Bueno esta mejor, pero no vamos a llegar a ningún lado con esa velocidad.
Optimizando la representación de las subsecuencias
Antes de ponernos a optimizar el algoritmo, veamos la implementación del tipo SubSeq. Este es el tipo con el que trabaja nuestro LCS(), va creciendo a medida que se encuentran elementos iguales y tiene que ser copiado cada vez que la función retorna. Hasta ahora solo tenemos una lista enlazada, si logramos reducir el tamaño de la lista no solo vamos a ahorrar memoria sino que también tiempo utilizado en copiar datos.
Una forma muy fácil de reducir el tamaño de SubSeq es juntar elementos consecutivos y almacenarlos como «primer índice + elementos». también necesitamos una variable que indique la cantidad de elementos y que sea actualizada por el operador «+», ya que elem.size() ya no nos sirve y calcular el tamaño recorriendo la lista es trabajo innecesario.
{
struct Elem
{
size_t index ;
size_t n ;
Elem() : index(0), n(0) {}
Elem(size_t a, size_t b) : index(a), n(b) {}
} ;
std::list<elem> elem ;
size_t elems ;
public:
SubSeq() : elems(0) {}
SubSeq operator+(const size_t &r)
{
SubSeq ret(*this) ;
if (elem.empty() || ret.elem.back().index + ret.elem.back().n != r)
ret.elem.push_back(Elem(r,1)) ;
else
++(ret.elem.back().n) ;
++ret.elems ;
return ret ;
}
bool operator<(SubSeq &r)
{
return (elems < r.elems) ;
}
void print(const char *buff)
{
for (std::list<elem>::iterator b = elem.begin(); b != elem.end(); ++b)
for(size_t x = 0; x != (*b).n; ++x)
std::cout << buff[(*b).index+x] ;
std::cout << std::endl ;
}
} ;
Para probar la performance vamos a usar cadenas un poco mas largas, como hay modificaciones al final de la cadena va a ser de los peores casos así que nos va a dar resultados mas claros.
char *s2 = "123 hola mundo caca" ;
$ time ./test
123 hola mundo
683.33user 0.71system 11:58.87elapsed
Ahora con las modificaciones:
$ time ./test
123 hola mundo
509.33user 0.78system 9:01.57elapsed
Hay una pequeña mejora pero el problema aca es el propio algoritmo.
Optimizando el algoritmo
La implementación usada es una función recursiva en la cual se repite el mismo trabajo reiteradas veces (llamadas con mismos pares i,j). Al necesitar solo dos índices de argumentos, nos encontramos con un buen caso para aplicar memoization. Es una optimización muy sencilla que consiste en crear una tabla para que la función recuerde resultados que ya calculo anteriormente. Cada vez que se llama a la función con un par de valores i,j la función se fija en el elemento de la tabla correspondiente a ese par de índices, si no hay un resultado guardado la función hace su trabajo y calcula el resultado, antes de retornar guarda el resultado en la tabla. La próxima vez que la función sea llamada para ese par i,j la función va a encontrar el resultado guardado en la tabla y va a retornar sin hacer mas trabajo.
A nuestra clase SeqPair agregamos dos campos privados:
size_t Col ;
El puntero memo tendrá la dirección de una matriz con elementos SubSeq, y Col indicará el número de columnas de esta. Vamos a manejarnos como si fuese un array simple porque en C++ a menos que usemos boost o alguna otra facilidad el uso de arrays multidimensionales (arrays de arrays realmente) es algo engorroso.
Modificamos el constructor y agregamos un destructor:
X(a), Y(b), Col(n), memo(new SubSeq[m*n]) {}
~SeqPair() { delete [] memo ; }
A partir de ahora, cuando creamos un objeto SeqPair debemos pasarle el largo de cada buffer para que pueda crear la tabla.
Solo queda modificar el LCS para que haga uso de la tabla:
{
if (!i || !j)
return SubSeq() ;
size_t mindex = (i-1)*Col+(j-1) ;
if (memo[mindex].elems)
return memo[(i-1) * Col + (j-1)] ;
if (X[i-1] == Y[j-1])
memo[mindex] = LCS(i-1, j-1) + (i-1) ;
else
memo[mindex] = max(LCS(i, j-1), LCS(i-1, j)) ;
return memo[mindex] ;
}
No hay que olvidar que para poder acceder al miembro «elems» debemos hacer a la clase SeqPair amiga de SubSeq.
Probamos el programa:
$ time ./test
123 hola mundo
0.01user 0.00system 0:00.02elapsed
De nueve minutos a fracciones de segundo, no esta mal!, si, esta mal 🙁 !
Esta solución trae una consecuencia mas grave. El uso de memoria se dispara. Para dos buffers de largo m y n la tabla necesita inicialmente mn*sizeof(SubSeq) bytes, pero mucho peor aun, por cada elemento se guarda una copia de la máxima subsecuencia calculada para ese par i,j.
Una solución mejor para calcular el LCS en O(nm) tiempo y O(nm) espacio es resolver el problema en dos pasos. En el primero se crea una tabla de dimensiones mn y se va llenando con el largo de cada LCS(i,j) partiendo desde 0. El segundo paso es navegar la tabla partiendo del ultimo elemento hasta reconstruir el LCS. Opcionalmente (en el primer paso) se puede crear una segunda tabla de mn con indicaciones para optimizar la navegación de la primer tabla.
Aunque usemos el algoritmo con una sola tabla necesitamos mn*sizeof(size_t) bytes, es mucho para algunos casos. Por ejemplo si comparamos dos archivos de 10mb cada uno, la tabla va a necesitar entre 400 y 800mb (dependiendo de la arquitectura).
El LCS ha sido un problema muy estudiado por lo cual existen algoritmos mejores. Algunos son muy buenos para casos particulares pero en otros casos pueden llegar a comportarse peor que el algoritmo O(nm). Precisamos de un algoritmo que se comporte bien en cualquier caso así que una buena opción es Hirschberg.
A partir del algoritmo que mencione anteriormente el cual resuelve el LSC en O(nm) tiempo y espacio, Hirschberg creo una variante la cual usa una estrategia divide-and-conquer (si no sabes lo que es mira un quicksort) que permite resolver el problema en O(n²) tiempo, y lo más importante, en O(n) espacio.
Hacemos algunas modificaciones a la clase SeqPair:
{
public:
class SubSeq
{
struct Elem
{
size_t index ;
size_t n ;
Elem() : index(0), n(0) {}
Elem(size_t a, size_t b) : index(a), n(b) {}
} ;
std::list<elem> elem ;
size_t elems ;
public:
SubSeq() : elems(0) {}
SubSeq *operator+=(const size_t &r)
{
if (elem.empty() || elem.back().index + elem.back().n != r)
elem.push_back(Elem(r,1)) ;
else
++(elem.back().n) ;
++elems ;
return this ;
}
void print(const char *buff)
{
for (std::list<elem>::iterator b = elem.begin(); b != elem.end(); ++b)
for(size_t x = 0; x != (*b).n; ++x)
std::cout << buff[(*b).index+x] ;
std::cout << std::endl ;
}
} ;
private:
void FindRow(const char *, const char *, size_t, size_t, size_t *) ;
void FindRowR(const char *, const char *, size_t, size_t, size_t *) ;
const char *X ;
const char *Y ;
SubSeq C ;
public:
SeqPair(const char *a, size_t m, const char *b, size_t n) : X(a), Y(b)
{
LCS(a, b, m, n) ;
C.print(a) ;
}
void LCS(const char *, const char *, size_t, size_t) ;
} ;
Y ahora la implementación del algoritmo de Hirschberg:
{
size_t *K(new size_t [n+1]) ;
for (size_t j = 0; j <= n; ++j)
K[j] = 0 ;
for (size_t i = 1; i <= m; i++)
{
for (size_t j = 0; j <= n; ++j)
L[j] = K[j] ;
for (size_t j = 1; j <= n; ++j)
if (x[i-1] == y[j-1])
K[j] = L[j-1] + 1 ;
else
K[j] = std::max(K[j-1], L[j]) ;
}
for (size_t j = 0; j <= n; ++j)
L[j] = K[j] ;
delete [] K ;
}
/*
Para no tener que crear los arreglos invertidos de x e y
mejor hacemos una version de FindRow que lea los elementos
en sentido contrario
*/
void SeqPair::FindRowR(const char *x, const char *y, size_t m, size_t n, size_t *L)
{
size_t *K(new size_t [n+1]) ;
for (size_t j = 0; j <= n; ++j)
K[j] = 0 ;
for (size_t i = 1; i <= m; i++)
{
for (size_t j = 0; j <= n; ++j)
L[j] = K[j] ;
for (size_t j = 1; j <= n; ++j)
if (x[m-i] == y[n-j])
K[j] = L[j-1] + 1 ;
else
K[j] = std::max(K[j-1], L[j]) ;
}
for (size_t j = 0; j <= n; ++j)
L[j] = K[j] ;
delete [] K ;
}
void SeqPair::LCS(const char *x, const char *y, size_t m, size_t n)
{
if (!n)
return ;
if (m == 1)
{
for(size_t j = 0; j <= n; ++j)
if (x[0] == y[j])
{
C += x – X ;
break ;
}
return ;
}
size_t i(m/2), k(0), *L(new size_t [n+1]), *Lr(new size_t [n+1]) ;
FindRow(x, y, i, n, L) ;
FindRowR(&x[i], y, m-i, n, Lr) ;
for (size_t max = 0, l = 0; l <= n; ++l)
if (L[l] + Lr[n-l] > max)
{
max = L[l] + Lr[n-l] ;
k = l ;
}
delete [] L ;
delete [] Lr ;
LCS(x, y, i, k) ;
LCS(&x[i], &y[k], m-i, n-k) ;
}
Optimizaciones practicas
Una técnica usada en muchos algoritmos consiste en aprovechar la unidad de tamaño con la que trabaja el micro para paralelizar el procesamiento de datos. Aplicándola sobre Hirschberg puede hallar el LCS en O(n²/w) tiempo, siendo w el tamaño de una word del micro. Tan solo hay modificar la rutina FindRow para que trabaje con vectores de bits.
Empezamos por implementar una clase BitVec bastante curte, solo con lo necesario para usarla con FindRow.
class BitVec
{
size_t *use, bsz, size ;
ulong *bits ;
public:
BitVec(size_t b) :
bsz(b), size(b/W_BIT+1), bits(new ulong [size]),
use(new size_t(1)) {}
BitVec(size_t b, size_t c) :
bsz(b), size(b/W_BIT+1), bits(new ulong [size]),
use(new size_t(1))
{
size_t x ;
for(x = 0; x < c/W_BIT; ++x)
bits[x] = ~0UL ;
bits[x] = (1UL << c%W_BIT) – 1 ;
while (++x < size)
bits[x] = 0 ;
}
BitVec(const BitVec &i) :
bits(i.bits), bsz(i.bsz), size(i.size),
use(i.use) { ++*use ; }
~BitVec()
{
if (–*use == 0)
{
delete [] bits ;
delete use ;
}
}
BitVec &operator=(const BitVec &r)
{
++*r.use ;
if (–*use == 0)
{
delete [] bits ;
delete use ;
}
bits = r.bits ;
use = r.use ;
return *this ;
}
BitVec operator+(const BitVec &r)
{
BitVec sum(bsz) ;
int cf(0) ;
for (size_t x = 0 ; x < size; ++x)
{
sum.bits[x] = bits[x] + r.bits[x] + cf ;
cf = (~0UL – bits[x] < r.bits[x]) ? 1 : 0 ;
}
sum.bits[0] += cf + (sum.bits[bsz/W_BIT] >> (bsz+1)%W_BIT) ;
return sum ;
}
BitVec operator&(const BitVec &r)
{
BitVec ret(bsz) ;
for (size_t x = 0 ; x < size; ++x)
ret.bits[x] = bits[x] & r.bits[x] ;
return ret ;
}
BitVec operator|(const BitVec &r)
{
BitVec ret(bsz) ;
for (size_t x = 0 ; x < size; ++x)
ret.bits[x] = bits[x] | r.bits[x] ;
return ret ;
}
BitVec operator~()
{
BitVec ret(bsz) ;
for (size_t x = 0 ; x < size; ++x)
ret.bits[x] = ~bits[x] ;
ret.bits[bsz/W_BIT] &= (1UL << bsz%W_BIT) – 1 ;
return ret ;
}
void set(size_t i)
{
bits[i/W_BIT] |= (1UL << i%W_BIT) ;
}
bool carry()
{
if (bits[bsz/W_BIT] & (1UL << bsz%W_BIT))
{
bits[bsz/W_BIT] &= (1UL << bsz%W_BIT) – 1 ;
return true ;
}
return false ;
}
} ;
Ahora las versiones de FindRow y FindRowR:
void SeqPair::FindRow(const char *x,const char *y, size_t m, size_t n, size_t *L)
{
std::vector<bitvec> M (1<<char_bit,>
BitVec S(m, m) ;
for(size_t i = 0; i < m; ++i)
M[((Mindex)x)[i]].set(i) ;
L[0] = 0 ;
for(size_t j = 1; j <= n; ++j)
{
S = (S + (S & M[((Mindex)y)[j-1]])) | (S & ~M[((Mindex)y)[j-1]]) ;
if (S.carry())
L[j] = L[j-1] + 1 ;
else
L[j] = L[j-1] ;
}
}
void SeqPair::FindRowR(const char *x, const char *y, size_t m, size_t n, size_t *L)
{
std::vector<bitvec> M (1<<char_bit,>
BitVec S(m, m) ;
for(size_t i = 0; i < m; ++i)
M[((Mindex)x)[m-i-1]].set(i) ;
L[0] = 0 ;
for(size_t j = 1; j <= n; ++j)
{
S = (S + (S & M[((Mindex)y)[n-j]])) | (S & ~M[((Mindex)y)[n-j]]) ;
if (S.carry())
L[j] = L[j-1] + 1 ;
else
L[j] = L[j-1] ;
}
}
Reduciendo el problema
Antes de llamar a la función que halla el LCS, recorremos el principio y el final del par de secuencias en busca de elementos diferentes. Nos quedan formadas tres subsecuencias.
A: es la subsecuencia que va desde el principio de la secuencia original hasta el primer par de elementos diferentes.
B: es la subsecuencia que va desde el primer par de elementos diferentes hasta el ultimo par de elementos diferentes.
C: es la subsecuencia que va desde el ultimo par de elementos diferentes hasta el final de la secuencia original.
Si no se encontraron diferencias el resultado es A. Si el par de elementos diferentes encontrado por el primer loop es el mismo que el encontrado por el segundo, el resultado es [A, C]. Para el caso restante el resultado es [A, LCS(B), C].
En los dos primeros casos el problema se resuelve en tiempo lineal, para el tercer caso el tiempo depende del tamaño de B, pero en el peor de los casos el tamaño del problema es el mismo por lo tanto el tiempo es el del LCS mas dos comparaciones extra. No voy a mostrar el código que hay que agregar porque es trivial, de todos modos el código aparece en la versión definitiva mas adelante.
Quiero recordar que elegí este algoritmo en particular porque el rendimiento no se ve afectado mas que por el tamaño del problema, en la practica el algoritmo de Hunt es mejor Hirschberg para la mayoría de los casos. A la hora de resolver un problema, mientras más especifico sea, más información tenemos para elegir un buen algoritmo y para aplicar otros tipos de optimizaciones.
Un ejemplo, si se trabaja archivos de texto y la granularidad es por linea (como el comando diff), se puede crear un array con un hash de cada linea y luego aplicar el LCS sobre el array.
Otro caso, comparacion de ejecutables. Cuando se compila un programa, las diferencias en los ejecutables resultantes pueden clasificarse en tres tipos. El en primer tipo está la información que guarda el compilador en el ejecutable, por ejemplo versiones, fecha, etc. Esta información puede cambiar incluso con el mismo código fuente.
Los cambios en desplazamientos y direcciones de memoria pertenecen al segundo tipo. Aunque las modificaciones en el código sean mínimas, estos cambios se propagan por gran parte del ejecutable.
Finalmente las variaciones en el propio código son el tercer tipo.
Podríamos hablar de una cuarta categoría para los cambios en las secciones de datos.
Una manera rápida de comparar ejecutables es desensamblar la(s) sección(es) de código y aplicar el LCS solo sobre las instrucciones (sin tener en cuenta desplazamientos y direcciones de memoria). Los saltos que cambiaron de tamaño compararían como instrucciones diferentes obviamente (después de todo son instrucciones con codificación diferente). Sobre la subsecuencia resultante se podrían resolver en forma lineal las diferencias en direcciones y desplazamientos ya que son sustituciones (no me animo a decir que en todas las arquitecturas sea de esta forma). Para el resto del ejecutable (categorías 1 y 4) aplicar solo LCS.
Modificando el LCS
Ahora que tenemos un algoritmo usable vamos a modificarlo, de forma que podamos hallar las diferencias entre X e Y. Solo añadimos el índice j a la clase Elem.
{
size_t i, j, n ;
Elem() : i(0), j(0), n(0) {}
Elem(size_t a, size_t b, size_t c) : i(a), j(b), n(c) {}
} ;
Tenemos que hacer algunos cambios, como el operador +=:
{
if (elem.empty() || elem.back().i + elem.back().n != r.first
|| elem.back().j + elem.back().n != r.second)
elem.push_back(Elem(r.first, r.second, 1)) ;
else
++(elem.back().n) ;
++elems ;
return this ;
}
Y en el LCS solo queda reemplazar:
por:
Generado el diff
El diff representa la serie de acciones que hay que realizar sobre X para obtener Y. Para generar el diff necesitamos una rutina que recorra la lista C generada por el LCS, y a partir de las diferencias de desplazamientos deduzca que tipo de cambios se realizaron. Cada cambio puede representarse con una clase Edit, el diff sería la lista de elementos Edit.
La clase Edit debe tener: un miembro que represente la acción a realizar (insertar, o eliminar elementos), un contador que indique cuantos elementos se van a añadir o eliminar, un offset sobre el cual aplicar la acción, y un vector que contenga los elementos a añadir en el caso de que la acción sea esa.
struct Edit
{
Action act ;
size_t offset, sz ;
std::vector<char> buff ;
} ;
La rutina que genera el diff tiene que recorrer la lista hallada por el LCS. Por cada elemento se comparan los índices con la suma de índices y tamaños del elemento anterior. Si el índice i es mayor a i+n del elemento anterior, la acción es es REM, si el índice j es mayor a j+n del elemento anterior la acción es INS.
Cuando tenemos una acción REM seguida de una INS y el mismo offset, la acción de menor tamaño (o ambas de ser iguales) se puede cambiar por una nueva acción SUB (sustitución).
Nuestra clase Edit completa:
struct Edit
{
Action act ;
size_t offset, sz ;
std::vector<char> buff ;
Edit(Action a, size_t b, size_t c, const char *d = NULL, const char *e = NULL) :
act(a), offset(b), sz(c)
{
if (d && e)
buff = std::vector<char>(d, e) ;
}
} ;</char></char>
Y nuestra rutina:
{
size_t x(0), y(0), delta(0), tmp(0) ;
for (std::list<subseq::elem>::iterator b = C.elem.begin(); b != C.elem.end(); ++b)
{
if ((*b).i > x && (*b).j > y)
{
size_t n((*b).i-x), m((*b).j-y) ;
if (n == m)
diff.push_back(Edit(SUB, x+delta, (*b).j-y, &Y[y], &Y[(*b).j])) ;
if (n < m)
{
diff.push_back(Edit(SUB, x+delta, n, &Y[y], &Y[y+n])) ;
diff.push_back(Edit(INS, x+delta+n, (*b).j-y-n, &Y[y+n], &Y[(*b).j])) ;
tmp += (*b).j-y-n ;
}
if (n > m)
{
diff.push_back(Edit(SUB, x+delta, m, &Y[y], &Y[(*b).j])) ;
diff.push_back(Edit(REM, x+delta+m, (*b).i-x-m)) ;
tmp -= (*b).i-x-m ;
}
}
else
{
if ((*b).i > x)
{
diff.push_back(Edit(REM, x+delta, (*b).i-x)) ;
tmp -= (*b).i-x ;
}
if ((*b).j > y)
{
diff.push_back(Edit(INS, x+delta, (*b).j-y, &Y[y], &Y[(*b).j])) ;
tmp += (*b).j-y ;
}
}
delta = tmp ;
x = (*b).i + (*b).n ;
y = (*b).j + (*b).n ;
}
}
Si lo que se busca es generar un parche lo más pequeño posible, el diff que generamos podría ser re-procesado. Anteriormente comentaba que en la comparación de ejecutables muchos cambios son direcciones, cuando nos encontramos con este tipo de casos podemos tomar todas las acciones SUB que tengan un tamaño entre 1 byte y el tamaño de un puntero y hallar la diferencia (resta) entre el valor de buff y los bytes originales. Las diferencias iguales podrían agruparse en un multimap usando como key la diferencia y como elementos la lista de offsets. Todos los elementos que se pasaron al multimap se pueden descartar del diff original.
También se puede reducir el diff a cambio de perdida de precisión. Se vuelve a recorrer la lista; si se da la condición de que la acción del elemento actual así como la del anterior son SUB, y la diferencia de offsets entre ambos es menor a sizeof(Edit), podemos fusionar ambos elementos en uno solo con la suma de los tamaños de ambos mas la distancia entre los offsets (al vector buff se le debe concatenar los bytes comprendidos entre los offsets, y los bytes del vector buff del otro elemento). Antes de aplicar este tipo de reducción lo mejor seria disminuir el tamaño de Edit lo mas posible, no usando alineación sobre la estructura, y cambiando el vector buff por alguna alternativa mas pequeña.
Otras estrategias pueden emplearse, pero van más allá del tema de este articulo y pasan al campo de la compresión. Quienes están interesados en el tema deberían leer la tesis del autor del bsdiff.
Comentarios finales
Toda la implementación hasta ahora se puede encontrar en este archivo: bdiff.h
Una ultima idea que me quedo sin implementar (ya estoy hasta las bolas de escribir código), es convertir la clase en un template. En lugar de usar buffers de tipo «const char *», se podrían usar tipos mas abstractos con el operador subíndice sobrecargado (entre otros). Esto puede ser util para trabajar con archivos grandes, en vez de cargarlos completamente en memoria ir leyéndolos por bloques, también se podrían leer pipes, sockets, etc, todo sin modificar el código, simplemente creando nuevos tipos que hagan de wrapper.
Usando el header es muy fácil hacer un bdiff, como no tengo muchas ganas de programar aquí dejo uno muy curte, para linux: bdiff.cpp
Bueno hasta aquí llegué, agur!