flate

commit c4c8fd422936440a24e5972a115be1b253076d0a
parent 90fedb5f0d237852abae0b14dd48522b317b74ca
Author: nsz <nszabolcs@gmail.com>
Date:   Tue, 18 Aug 2009 23:49:20 +0200

+crc +adler +flatez (zlib+gz)
Diffstat:
adler.c
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
crc.c
 | 
25
+++++++++++++++++++++++++
flatez.c
 | 
132
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 218 insertions(+), 0 deletions(-)
diff --git a/adler.c b/adler.c
@@ -0,0 +1,61 @@
+enum {
+	AdlerBase = 65521, /* largest 16bit prime */
+	AdlerN    = 5552   /* max iters before 32bit overflow */
+};
+
+uint adlersum(uchar *p, int n, uint adler) {
+	uint s1 = adler & 0xffff;
+	uint s2 = (adler >> 16) & 0xffff;
+	uchar *ep;
+	int k;
+
+	for (; n >= 16; n -= k) {
+		k = n < AdlerN ? n : AdlerN;
+		k &= ~0xf;
+		for (ep = p + k; p < ep; p += 16) {
+			s1 += p[0];
+			s2 += s1;
+			s1 += p[1];
+			s2 += s1;
+			s1 += p[2];
+			s2 += s1;
+			s1 += p[3];
+			s2 += s1;
+			s1 += p[4];
+			s2 += s1;
+			s1 += p[5];
+			s2 += s1;
+			s1 += p[6];
+			s2 += s1;
+			s1 += p[7];
+			s2 += s1;
+			s1 += p[8];
+			s2 += s1;
+			s1 += p[9];
+			s2 += s1;
+			s1 += p[10];
+			s2 += s1;
+			s1 += p[11];
+			s2 += s1;
+			s1 += p[12];
+			s2 += s1;
+			s1 += p[13];
+			s2 += s1;
+			s1 += p[14];
+			s2 += s1;
+			s1 += p[15];
+			s2 += s1;
+		}
+		s1 %= AdlerBase;
+		s2 %= AdlerBase;
+	}
+	if (n) {
+		for (ep = p + n; p < ep; p++) {
+			s1 += p[0];
+			s2 += s1;
+		}
+		s1 %= AdlerBase;
+		s2 %= AdlerBase;
+	}
+	return (s2 << 16) + s1;
+}
diff --git a/crc.c b/crc.c
@@ -0,0 +1,25 @@
+uint crctab[256];
+
+void crcinit(void) {
+	static const uint poly = 0xEDB88320;
+
+	for (i = 0; i < 256; ++i) {
+		crc = i;
+		for (j = 0; j < 8; j++) {
+			if (crc & 1)
+				crc = (crc >> 1) ^ poly;
+			else
+				crc >>= 1;
+		}
+		crctab[i] = crc;
+	}
+}
+
+uint crcsum(uchar *p, int n, uint crc) {
+	uchar *ep = p + n;
+
+	crc ^= 0xffffffff;
+	while (p < ep)
+		crc = crctab[(crc & 0xff) ^ *buf++] ^ (crc >> 8);
+	return crc ^ 0xffffffff;
+}
diff --git a/flatez.c b/flatez.c
@@ -0,0 +1,132 @@
+
+static int checkfooter(uchar *p, uint sum) {
+	return sum == ((p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3]);
+}
+
+enum {
+	ZlibCM    = 7 << 4,
+	ZlibCINFO = 8,
+	ZlibFLEV  = 3 << 6,
+	ZlibFDICT = 1 << 5,
+	ZlibFCHK  = 31 - (((ZlibCM | ZlibCINFO) << 8) | ZlibFLEV) % 31,
+};
+
+int deflate_zlib_header(uchar *p, int n) {
+	if (n < 2)
+		return FlateErr;
+	p[0] = ZlibCM | ZlibCINFO;  /* deflate method, 32K window size */
+	p[1] = ZlibFLEV | ZlibFCHK; /* highest compression */
+	return 2;
+}
+
+int deflate_zlib_footer(uchar *p, int n, uint sum) {
+	if (n < 4)
+		return FlateErr;
+	p[0] = sum >> 24;
+	p[1] = sum >> 16;
+	p[2] = sum >> 8;
+	p[3] = sum;
+	return 4;
+}
+
+int inflate_zlib_header(uchar *p, int n) {
+	if (n < 2)
+		return FlateErr;
+	if (((p[0] << 8) | p[1]) % 31)
+		return FlateErr;
+	if ((p[0] & 0xf0) != ZlibCM || (p[0] & 0x0f) > ZlibCINFO)
+		return FlateErr;
+	if (p[1] & ZlibFDICT)
+		return FlateErr;
+	return 2;
+}
+
+int inflate_zlib_footer(uchar *p, int n, uint sum) {
+	if (n < 4 || !checkfooter(p, sum))
+		return FlateErr;
+	return 4;
+}
+
+
+enum {
+	GZipID1    = 0x1f,
+	GZipID2    = 0x8b,
+	GZipCM     = 8,
+	GZipFHCRC  = 1 << 1,
+	GZipFEXTRA = 1 << 2,
+	GZipFNAME  = 1 << 3,
+	GZipFCOMM  = 1 << 4,
+	GZipXFL    = 2,
+	GZipOS     = 255
+};
+
+int deflate_gzip_header(uchar *p, int n) {
+	int k;
+
+	if (n < 10)
+		return FlateErr;
+	for (k = 0; k < n; k++)
+		p[k] = 0;
+	p[0] = GZipID1;
+	p[1] = GZipID2;
+	p[2] = GZipCM;
+	p[8] = GZipXFL;
+	p[9] = GZipOS;
+	return 10;
+}
+
+int deflate_gzip_footer(uchar *p, int n, uint sum, uint len) {
+	if (n < 8)
+		return FlateErr;
+	p[0] = sum >> 24;
+	p[1] = sum >> 16;
+	p[2] = sum >> 8;
+	p[3] = sum;
+	p[4] = len >> 24;
+	p[5] = len >> 16;
+	p[6] = len >> 8;
+	p[7] = len;
+	return 8;
+}
+
+int inflate_gzip_header(uchar *p, int n) {
+	int k = 10;
+
+	if (k > n)
+		return FlateErr;
+	if (p[0] != GZipID1 || p[1] != GZipID2 || p[2] != GZipCM)
+		return FlateErr;
+	if (p[3] & GZipFEXTRA) {
+		k += 2 + ((p[k] << 8) | p[k+1]);
+		if (k > n)
+			return FlateErr;
+	}
+	if (p[3] & GZipFNAME) {
+		for (; k < n; k++)
+			if (p[k] == 0)
+				break;
+		k++;
+		if (k > n)
+			return FlateErr;
+	}
+	if (p[3] & GZipFCOMM) {
+		for (; k < n; k++)
+			if (p[k] == 0)
+				break;
+		k++;
+		if (k > n)
+			return FlateErr;
+	}
+	if (p[3] & GZipFHCRC) {
+		k += 2;
+		if (k > n)
+			return FlateErr;
+	}
+	return k;
+}
+
+int inflate_gzip_footer(uchar *p, int n, uint sum, uint len) {
+	if (n < 8 || !checkfooter(p, sum) || !checkfooter(p+4, len))
+		return FlateErr;
+	return 8;
+}