21 #define _XOPEN_SOURCE 500
23 #include <sys/types.h>
37 #define BLOCK_SIZE (65536*1)
38 #if BLOCK_SIZE <= 65536
39 typedef __uint16_t
Ref;
41 typedef __uint32_t
Ref;
91 unsigned char *out,
unsigned int out_len)
98 memset(htab, -1,
sizeof (htab));
99 memset(hnext, -1,
sizeof (hnext));
100 unsigned int litofs = 0;
101 while (io + 2 < in_len)
105 unsigned int hval = in[io] | in[io + 1] << 8 | in[io + 2] << 16;
106 unsigned int try, mlen, mofs, tries;
107 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
108 hval = hval & (
HS - 1);
110 hnext[io] = htab[hval];
115 for (tries = 0;
try != -1 && tries < 12; tries++)
118 && in[
try] == in[io] && in[
try + 1] == in[io + 1])
121 mofs = (io -
try) - 1;
126 for (;
try != -1 && tries < 12; tries++)
135 if (
try < io && in[
try + mlen] == in[io + mlen])
137 unsigned int this_len, this_ofs;
138 if (memcmp(in +
try, in + io, mlen))
143 io + this_len < in_len
144 && in[
try + this_len] == in[io + this_len]; this_len++)
148 for (testi = 0; testi < this_len; testi++)
149 assert(in[
try + testi] == in[io + testi]);
151 this_ofs = (io -
try) - 1;
155 assert(this_len >= 2);
156 assert(this_len >= mlen);
157 assert(this_len > mlen || (this_len == mlen && this_ofs > mofs));
159 mlen = this_len, mofs = this_ofs;
164 if (io + mlen >= in_len)
177 if (mlen == 2 && (litofs || mofs >= 1024))
181 else if (mofs >= 65536)
183 if (mlen >= 2048 + 5)
192 else if (mlen >= 2048 + 19)
198 if (mlen && mlen < (2048 + 5) && io + 3 < in_len)
201 in[io + 1] | in[io + 2] << 8 | in[io + 3] << 16;
203 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
204 hval = hval & (
HS - 1);
207 && in[
try] == in[io + 1] && in[
try + 1] == in[io + 2])
209 unsigned int this_len;
212 io + 1 + this_len < in_len
213 && in[
try + this_len] == in[io + 1 + this_len];
216 if (this_len >= mlen)
232 unsigned litlen = io - litofs;
236 unsigned int easy_sz;
242 easy_sz < litlen && in[litofs + easy_sz] < 0x80;
247 if (oo + easy_sz >= out_len)
249 memcpy(out + oo, in + litofs, easy_sz);
258 if (oo + 1 + litlen >= out_len)
260 out[oo++] = 0x80 | (litlen - 1);
262 out[oo++] = in[litofs++];
268 if (oo + 1 + 32 >= out_len)
270 out[oo++] = 0x80 | 31;
271 memcpy(out + oo, in + litofs, 32);
282 if (mlen >= 2 && mlen <= 9 && mofs < 1024)
284 if (oo + 2 >= out_len)
286 out[oo++] = 0xa0 | ((mofs & 0x300) >> 5) | (mlen - 2);
287 out[oo++] = mofs & 0xff;
289 else if (mlen >= 10 && mlen <= 41 && mofs < 256)
291 if (oo + 2 >= out_len)
293 out[oo++] = 0xc0 | (mlen - 10);
296 else if (mofs >= 65536)
298 assert(mlen >= 5 && mlen < 2048 + 5);
299 if (oo + 5 >= out_len)
301 out[oo++] = 0xf8 | ((mlen - 5) >> 8);
302 out[oo++] = (mlen - 5) & 0xff;
303 out[oo++] = mofs & 0xff;
304 out[oo++] = (mofs >> 8) & 0xff;
305 out[oo++] = mofs >> 16;
307 else if (mlen >= 3 && mlen <= 18)
309 assert(mofs < 65536);
310 if (oo + 3 >= out_len)
312 out[oo++] = 0xe0 | (mlen - 3);
313 out[oo++] = mofs & 0xff;
314 out[oo++] = mofs >> 8;
318 assert(mlen >= 19 && mlen <= 4095 + 19 && mofs < 65536);
319 if (oo + 4 >= out_len)
321 out[oo++] = 0xf0 | ((mlen - 19) >> 8);
322 out[oo++] = (mlen - 19) & 0xff;
323 out[oo++] = mofs & 0xff;
324 out[oo++] = mofs >> 8;
338 in[io] | in[io + 1] << 8 | in[io + 2] << 16;
339 hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
340 hval = hval & (
HS - 1);
341 hnext[io] = htab[hval];
349 if (io < in_len && !litofs)
355 unsigned litlen = io - litofs;
359 unsigned int easy_sz;
364 for (easy_sz = 0; easy_sz < litlen && in[litofs + easy_sz] < 0x80;
369 if (oo + easy_sz >= out_len)
371 memcpy(out + oo, in + litofs, easy_sz);
380 if (oo + 1 + litlen >= out_len)
382 out[oo++] = 0x80 | (litlen - 1);
384 out[oo++] = in[litofs++];
390 if (oo + 1 + 32 >= out_len)
392 out[oo++] = 0x80 | 31;
393 memcpy(out + oo, in + litofs, 32);
409 unsigned char *orig_out = out;
410 const unsigned char *in_end = in + in_len;
413 unsigned int first = *in++;
434 unsigned int l = first & 31;
444 o = first & (3 << 3);
445 o = (o << 5) | *in++;
446 first = (first & 7) + 2;
453 first = (first & 31) + 10;
459 o = in[0] | (in[1] << 8);
473 first = (((first - 8) << 8) | in[0]) + 5;
474 o = in[1] | (in[2] << 8) | (in[3] << 16);
479 first = ((first << 8) | in[0]) + 19;
480 o = in[1] | (in[2] << 8);
501 case 18: *out = *(out + o); out++;
502 case 17: *out = *(out + o); out++;
503 case 16: *out = *(out + o); out++;
504 case 15: *out = *(out + o); out++;
505 case 14: *out = *(out + o); out++;
506 case 13: *out = *(out + o); out++;
507 case 12: *out = *(out + o); out++;
508 case 11: *out = *(out + o); out++;
509 case 10: *out = *(out + o); out++;
510 case 9: *out = *(out + o); out++;
511 case 8: *out = *(out + o); out++;
512 case 7: *out = *(out + o); out++;
513 case 6: *out = *(out + o); out++;
514 case 5: *out = *(out + o); out++;
515 case 4: *out = *(out + o); out++;
516 case 3: *out = *(out + o); out++;
517 case 2: *out = *(out + o); out++;
518 case 1: *out = *(out + o); out++;
526 case 0: *out = *(out + o); out++;
527 case 15: *out = *(out + o); out++;
528 case 14: *out = *(out + o); out++;
529 case 13: *out = *(out + o); out++;
530 case 12: *out = *(out + o); out++;
531 case 11: *out = *(out + o); out++;
532 case 10: *out = *(out + o); out++;
533 case 9: *out = *(out + o); out++;
534 case 8: *out = *(out + o); out++;
535 case 7: *out = *(out + o); out++;
536 case 6: *out = *(out + o); out++;
537 case 5: *out = *(out + o); out++;
538 case 4: *out = *(out + o); out++;
539 case 3: *out = *(out + o); out++;
540 case 2: *out = *(out + o); out++;
541 case 1: *out = *(out + o); out++;
543 while ((
int)(first -= 16) > 0);
549 return out - orig_out;
556 memset(store, 0,
sizeof(*store));
581 for (i = pstart; i <= pend; i++)
594 if (pend - pstart + 1 > store->
ncanmap)
596 unsigned int oldcan = store->
ncanmap;
597 store->
ncanmap = pend - pstart + 1;
604 fprintf(stderr,
"PAGE: can map %d pages\n", store->
ncanmap);
612 unsigned int cost[store->
ncanmap];
613 for (i = 0; i < store->
ncanmap; i++)
615 unsigned int pnum = store->
mapped[i];
623 if (pnum >= pstart && pnum <= pend)
631 unsigned int best_cost = -1;
632 unsigned int best = 0;
633 unsigned int same_cost = 0;
634 for (i = 0; i + pend - pstart < store->
ncanmap; i++)
636 unsigned int c = cost[i];
638 for (j = 0; j < pend - pstart + 1; j++)
641 best_cost = c, best = i;
642 else if (c == best_cost)
650 if (same_cost == store->
ncanmap - pend + pstart - 1)
658 for (i = best; i < best + pend - pstart + 1; i++)
660 unsigned int pnum = store->
mapped[i];
664 && pnum != pstart + i - best)
668 fprintf(stderr,
"PAGE: evict page %d from %d\n", pnum, i);
677 for (i = pstart; i <= pend; i++)
680 unsigned int pnum = i - pstart + best;
684 if (p->
mapped_at != pnum * BLOB_PAGESIZE)
687 fprintf(stderr,
"PAGECOPY: %d to %d\n", i, pnum);
697 unsigned int compressed = in_len & 1;
700 fprintf(stderr,
"PAGEIN: %d to %d", i, pnum);
702 if (pread(store->
pagefd, compressed ? buf : dest, in_len, p->
file_offset) != in_len)
704 perror(
"mapping pread");
709 unsigned int out_len;
711 dest, BLOB_PAGESIZE);
712 if (out_len != BLOB_PAGESIZE && i < store->num_pages - 1)
715 fprintf(stderr,
"can't decompress\n");
720 fprintf(stderr,
" (expand %d to %d)", in_len, out_len);
724 fprintf(stderr,
"\n");
728 store->
mapped[pnum] = i + 1;
739 #define SOLV_ERROR_EOF 3
740 #define SOLV_ERROR_CORRUPT 6
742 static inline unsigned int
748 for (i = 0; i < 4; i++)
766 unsigned int can_seek;
776 if ((cur_file_ofs = ftell(fp)) < 0)
780 store->
pagefd = dup(fileno(fp));
784 fcntl(store->
pagefd, F_SETFD, FD_CLOEXEC);
787 fprintf(stderr,
"can %sseek\n", can_seek ?
"" :
"NOT ");
797 for (i = 0; i < npages; i++)
800 unsigned int compressed = in_len & 1;
804 fprintf(stderr,
"page %d: len %d (%scompressed)\n",
805 i, in_len, compressed ?
"" :
"not ");
813 if (fseek(fp, in_len, SEEK_CUR) < 0)
821 cur_file_ofs += in_len;
825 unsigned int out_len;
831 if (fread(compressed ? buf : dest, in_len, 1, fp) != 1)
839 if (out_len != BLOB_PAGESIZE && i < npages - 1)
859 transfer_file(FILE * from, FILE * to,
int compress)
863 while (!feof (from) && !ferror (from))
865 unsigned int in_len, out_len;
871 unsigned char *b = outb;
872 out_len =
compress_buf(inb, in_len, outb,
sizeof (outb));
874 b = inb, out_len = in_len;
875 if (fwrite(&out_len,
sizeof (out_len), 1, to) != 1)
877 perror(
"write size");
880 if (fwrite(b, out_len, 1, to) != 1)
882 perror(
"write data");
889 if (fread(&in_len,
sizeof(in_len), 1, from) != 1)
893 perror(
"can't read size");
896 if (fread(inb, in_len, 1, from) != 1)
898 perror(
"can't read data");
903 if (fwrite(outb, out_len, 1, to) != 1)
905 perror(
"can't write output");
914 dumb_memcpy(
void *dest,
const void *src,
unsigned int len)
923 benchmark(FILE * from)
927 unsigned int in_len = fread(inb, 1,
BLOCK_SIZE, from);
928 unsigned int out_len;
931 perror(
"can't read from input");
935 unsigned int calib_loop;
936 unsigned int per_loop;
945 while ((clock() - start) < CLOCKS_PER_SEC / 4)
948 for (i = 0; i < calib_loop; i++)
949 dumb_memcpy(outb, inb, in_len);
950 per_loop += calib_loop;
953 fprintf(stderr,
"memcpy:\nCalibrated to %d iterations per loop\n",
957 for (i = 0; i < 10; i++)
958 for (j = 0; j < per_loop; j++)
959 dumb_memcpy(outb, inb, in_len);
961 seconds = (end -
start) / (
float) CLOCKS_PER_SEC;
962 fprintf(stderr,
"%.2f seconds == %.2f MB/s\n", seconds,
963 ((
long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
969 while ((clock() - start) < CLOCKS_PER_SEC / 4)
972 for (i = 0; i < calib_loop; i++)
974 per_loop += calib_loop;
977 fprintf(stderr,
"compression:\nCalibrated to %d iterations per loop\n",
981 for (i = 0; i < 10; i++)
982 for (j = 0; j < per_loop; j++)
985 seconds = (end -
start) / (
float) CLOCKS_PER_SEC;
986 fprintf(stderr,
"%.2f seconds == %.2f MB/s\n", seconds,
987 ((
long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
989 out_len =
compress_buf(inb, in_len, outb,
sizeof(outb));
994 while ((clock() - start) < CLOCKS_PER_SEC / 4)
997 for (i = 0; i < calib_loop; i++)
999 per_loop += calib_loop;
1002 fprintf(stderr,
"decompression:\nCalibrated to %d iterations per loop\n",
1006 for (i = 0; i < 10; i++)
1007 for (j = 0; j < per_loop; j++)
1010 seconds = (end -
start) / (
float) CLOCKS_PER_SEC;
1011 fprintf(stderr,
"%.2f seconds == %.2f MB/s\n", seconds,
1012 ((
long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
1016 main(
int argc,
char *argv[])
1019 if (argc > 1 && !strcmp(argv[1],
"-d"))
1021 if (argc > 1 && !strcmp(argv[1],
"-b"))
1024 transfer_file(stdin, stdout, compress);