Re: BSDiff for cache objects

#!/bin/sh

BSPATCH=bspatch
#BSPATCH=~/build/bsdiff-4.3/bspatch

cd patches

for f in `find .ccache -type f`; do
	gunzip -c ~/$f > ../a.o
	$BSPATCH ../a.o /dev/null $f
done

rm ../a.o

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <errno.h>
#include <dirent.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <ctype.h>

const char *BSDIFF = "bsdiff";
//const char *BSDIFF = "~/build/bsdiff-4.3/bsdiff";

struct Func {
	Func *next;

	char *name;
};

struct Obj {
	Obj *next;

	char *name;
	char *expanded;
	int nfuncs;
	Func *funcs;
	
	Obj *match;
	int score;
};

const int HASH_SIZE = 19031;
Obj *objs[HASH_SIZE] = {};
#define NAME_HASH(name) ((*(int *)(name)) % HASH_SIZE)

Obj *read_obj(const char *strbase, int a, int b, const char *namesuff)
{
	Obj *o = new Obj;
	o->next = 0;
	o->name = new char[64];
	o->expanded = new char[128];
	o->nfuncs = 0;
	o->funcs = 0;
	o->match = 0;
	o->score = 0;
	
	o->name = strdup(namesuff);

	int nc = snprintf(o->expanded, 128, "%x/%x/%s", a, b, namesuff);
	if (nc <= 0 || nc >= 64) abort();
	
	char strpath[PATH_MAX];
	sprintf(strpath, "%s/%s", strbase, namesuff);

	FILE *f = fopen(strpath, "rb");
	if (!f) {
		printf("open %s\n", namesuff);
		abort();
	}

	for (;;) {
		static char line[PATH_MAX];
		if (!fgets(line, PATH_MAX, f))
			break;

		for (int l=strlen(line); l && isspace(line[l-1]); line[--l]=0);


		Func **h = &o->funcs;
		
		Func *fn = new Func;
		fn->name = strdup(line);
		
		fn->next = *h;
		*h = fn;

		o->nfuncs++;
	}

	fclose(f);

	return o;
}

#define max(a,b) (((a) > (b)) ? (a) : (b))

void compare(Obj *o1, Obj *o2)
{
	/*
	if (strcmp(o1->name, "978911edd002afb6ecb9611659327e3e-3475537") ||
		strcmp(o2->name, "4794bbcacf3bc42cdf1a44cf89523949-3429991"))
		return;
	*/

	if (o1->nfuncs < 4 || o2->nfuncs < 4) return;
	int r = 100*o1->nfuncs/o2->nfuncs;
	if (r < 80 || r > 125) return;
	if (!strcmp(o1->name, o2->name)) return;

	Func *f1 = o2->funcs;
	Func *f2 = o1->funcs;
	
	int m=0;
	while (f1) {
		int r = 0;
		while (f2 && (r = strcmp(f1->name, f2->name)) < 0) // reversed since we pushed fns at the head
			f2 = f2->next;

		if (f2 && r==0) // match
			m++;

		f1 = f1->next;
	}
	
	int score = 1000*m/max(o1->nfuncs, o2->nfuncs);
	if (score > 800 && score > o1->score) {
		o1->score = score;
		o1->match = o2;
	}
}

int mk_file_dirs(char *file)
{
	char *ptr = file;

	for (;;) {
		ptr = strchr(ptr, '/');
		if (!ptr) return 0;

		*ptr = 0;
		int ret = mkdir(file, 0750);
		*ptr = '/';

		if (ret < 0 && errno != EEXIST) {
			fprintf(stderr, "%s: errno=%s (%d)\n", file, strerror(errno), errno);
			return -1;
		}

		ptr++;
	}
}

int main()
{
	int nobjs=0;

	for (int a=0; a<0x10; a++)
		for (int b=0; b<0x10; b++) {
			char strbase[PATH_MAX];
			sprintf(strbase, "strings/.ccache/%x/%x", a, b);

			DIR *dh = opendir(strbase);
			if (!dh) continue;

			for (;;) {
				struct dirent *de = readdir(dh);
				if (!de)
					break;
				if (strchr(de->d_name, '.'))
					continue;
				
				Obj *o = read_obj(strbase, a, b, de->d_name);
				
				Obj **h = &objs[NAME_HASH(o->name)];
				o->next = *h;
				*h = o;

				nobjs++;
			}

			closedir(dh);
		}
	
	long long total_raw=0;
	long long total_bsd=0;
	int nbsd=0;

	for (int h1=0; h1<HASH_SIZE; h1++) {
		fprintf(stderr, "\r%d%%", h1*100/HASH_SIZE);
		fflush(stderr);

		for (Obj *o1=objs[h1]; o1; o1=o1->next) {
			// Look for a match in all the objects that are after it in our hash.
			// If we get a match, it means we can store o1 as a delta from o2.

			for (int h2=h1; h2<HASH_SIZE; h2++) {
				Obj *o2 = (h2==h1) ? o1 : objs[h2];
				
				for (; o2; o2=o2->next)
					compare(o1, o2);
			}

			if (o1->match) {
				char bin1[PATH_MAX];
				char bin2[PATH_MAX];
				sprintf(bin1, "%s/.ccache/%s", getenv("HOME"), o1->expanded);
				sprintf(bin2, "%s/.ccache/%s", getenv("HOME"), o1->match->expanded);

				char cmd[PATH_MAX];

				sprintf(cmd, "gunzip -c %s > a.o", bin1);
				if (system(cmd)) { printf("%s\n", cmd); abort(); }

				sprintf(cmd, "gunzip -c %s > b.o", bin2);
				if (system(cmd)) { printf("%s\n", cmd); abort(); }
				
				char patch[PATH_MAX];
				sprintf(patch, "patches/.ccache/%s", o1->expanded);

				if (mk_file_dirs(patch))
					abort();

				snprintf(cmd, PATH_MAX, "%s a.o b.o %s", BSDIFF, patch);
				if (system(cmd)) { printf("%s\n", cmd); abort(); }
				
				struct stat st;

				if (stat(bin1, &st))
					{ printf("stat %s\n", bin1); abort(); }
				off_t s1 = st.st_size;

				if (stat(patch, &st))
					{ printf("%s\n", patch); abort(); }
				off_t sd = st.st_size;
			
				/*if (stat(bin2, &st))
					{ printf("stat %s\n", bin2); abort(); }
				off_t s2 = st.st_size;

				printf("r %ld \tsc %d\tn1 %d\tn2 %d\ts1 %ld\ts2 %ld\tsd %ld\t%s %s\n", 
						sd*100/max(s1, s2),
						o1->score, o1->nfuncs, o1->match->nfuncs, 
						s1, s2, sd,
						o1->expanded, o1->match->expanded);*/

				total_raw += s1;
				total_bsd += sd;
	
				nbsd++;
			}
		}
	}

	remove("a.o");
	remove("b.o");

	fprintf(stderr, "\n%d files compressed (%lld -> %lld bytes, %lld%%) \n", nbsd, total_raw, total_bsd, 100*total_bsd/total_raw);
	
	return 0;
}

#!/bin/bash

MYDIR=$PWD


cd ~

N=`find .ccache -name '*-*.stderr' | wc -l`
I=0

export LC_ALL=C # for sort

for f in `find .ccache -name '*-*.stderr' | cut -d . -f 1-2`; do
	let I+=1
	echo -en "\r$I/$N"
	mkdir -p $MYDIR/strings/`dirname $f`
	gunzip -c $f > tmp.o
	objdump -t tmp.o | grep " g " | awk '{print $NF}' | sort | uniq > $MYDIR/strings/$f
done

rm tmp.o
echo