ref: b05d2f5ffcdbff21c31a7c9a902a0d1053066fe1
parent: 31e912ac95f8c315916cb9d6a8bc59026a6d28b2
author: Jacob Moody <moody@posixcafe.org>
date: Sat May 6 21:09:44 EDT 2023
ipsdiff: smaller diff generation with better use of RLE
--- a/ipsdiff.c
+++ b/ipsdiff.c
@@ -62,6 +62,34 @@
}
static void
+RLEpass(u32int base, uchar *p, uchar *e)
+{+ uchar *u, *uu;
+ uchar *start;
+ uchar v;
+
+ if(e - p <= 8){+ emit(base, p, e - p);
+ return;
+ }
+
+ start = p;
+ for(u = p; u < e; u = uu){+ v = *u;
+ for(uu = u+1; uu < e && *uu == v; uu++)
+ ;
+ if(uu - u < 8)
+ continue;
+ if(u > p)
+ emit(base + (p - start), p, u - p);
+ emit(base + (u - start), u, uu - u);
+ p = uu;
+ }
+ if(u > p)
+ emit(base + (p - start), p, u - p);
+}
+
+static void
diff(Bin *a, Bin *b)
{uchar *ap, *bp;
@@ -83,16 +111,20 @@
bc = bp+1;
continue;
}
- x = 2;
+ x = 4;
for(ac = ap, bc = bp; ac < ae && bc < be; ac++, bc++){if(*ac == *bc)
x--;
else
- x = 2;
+ x = 4;
if(x == 0)
break;
}
- emit(a->dot + (ap - a->data), bp, bc - bp);
+ for(; ac > ap && bc > bp && *ac == *bc; ac--, bc--)
+ ;
+ bc++;
+ ac++;
+ RLEpass(a->dot + (ap - a->data), bp, bc);
}
a->dot += a->n;
b->dot += b->n;