1 /*
2  * Copyright (c) 2016 Maxim Sobolev <sobomax@FreeBSD.org>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  */
26 
27 #include <sys/cdefs.h>
28 __FBSDID("$FreeBSD: stable/12/usr.bin/mkuzip/mkuz_blockcache.c 298504 2016-04-23 07:23:43Z sobomax $");
29 
30 #include <err.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <unistd.h>
35 
36 #if defined(MKUZ_DEBUG)
37 # include <assert.h>
38 # include <stdio.h>
39 #endif
40 
41 #include "mkuz_blockcache.h"
42 #include "mkuz_blk.h"
43 
44 struct mkuz_blkcache_itm {
45     struct mkuz_blk_info hit;
46     struct mkuz_blkcache_itm *next;
47 };
48 
49 static struct mkuz_blkcache {
50     struct mkuz_blkcache_itm first[256];
51 } blkcache;
52 
53 static int
verify_match(int fd,const struct mkuz_blk * cbp,struct mkuz_blkcache_itm * bcep)54 verify_match(int fd, const struct mkuz_blk *cbp, struct mkuz_blkcache_itm *bcep)
55 {
56     void *vbuf;
57     ssize_t rlen;
58     int rval;
59 
60     rval = -1;
61     vbuf = malloc(cbp->info.len);
62     if (vbuf == NULL) {
63         goto e0;
64     }
65     if (lseek(fd, bcep->hit.offset, SEEK_SET) < 0) {
66         goto e1;
67     }
68     rlen = read(fd, vbuf, cbp->info.len);
69     if (rlen < 0 || (unsigned)rlen != cbp->info.len) {
70         goto e2;
71     }
72     rval = (memcmp(cbp->data, vbuf, cbp->info.len) == 0) ? 1 : 0;
73 e2:
74     lseek(fd, cbp->info.offset, SEEK_SET);
75 e1:
76     free(vbuf);
77 e0:
78     return (rval);
79 }
80 
81 #define I2J(x)	((intmax_t)(x))
82 #define U2J(x)	((uintmax_t)(x))
83 
84 static unsigned char
digest_fold(const unsigned char * mdigest)85 digest_fold(const unsigned char *mdigest)
86 {
87     int i;
88     unsigned char rval;
89 
90     rval = mdigest[0];
91     for (i = 1; i < 16; i++) {
92         rval = rval ^ mdigest[i];
93     }
94     return (rval);
95 }
96 
97 struct mkuz_blk_info *
mkuz_blkcache_regblock(int fd,const struct mkuz_blk * bp)98 mkuz_blkcache_regblock(int fd, const struct mkuz_blk *bp)
99 {
100     struct mkuz_blkcache_itm *bcep;
101     int rval;
102     unsigned char h;
103 
104 #if defined(MKUZ_DEBUG)
105     assert((unsigned)lseek(fd, 0, SEEK_CUR) == bp->info.offset);
106 #endif
107     h = digest_fold(bp->info.digest);
108     if (blkcache.first[h].hit.len == 0) {
109         bcep = &blkcache.first[h];
110     } else {
111         for (bcep = &blkcache.first[h]; bcep != NULL; bcep = bcep->next) {
112             if (bcep->hit.len != bp->info.len)
113                 continue;
114             if (memcmp(bp->info.digest, bcep->hit.digest,
115               sizeof(bp->info.digest)) == 0) {
116                 break;
117             }
118         }
119         if (bcep != NULL) {
120             rval = verify_match(fd, bp, bcep);
121             if (rval == 1) {
122 #if defined(MKUZ_DEBUG)
123                 fprintf(stderr, "cache hit %jd, %jd, %jd, %jd\n",
124                   I2J(bcep->hit.blkno), I2J(bcep->hit.offset),
125                   I2J(bp->info.offset), I2J(bp->info.len));
126 #endif
127                 return (&bcep->hit);
128             }
129             if (rval == 0) {
130 #if defined(MKUZ_DEBUG)
131                 fprintf(stderr, "block MD5 collision, you should try lottery, "
132                   "man!\n");
133 #endif
134                 return (NULL);
135             }
136             warn("verify_match");
137             return (NULL);
138         }
139         bcep = malloc(sizeof(struct mkuz_blkcache_itm));
140         if (bcep == NULL)
141             return (NULL);
142         memset(bcep, '\0', sizeof(struct mkuz_blkcache_itm));
143         bcep->next = blkcache.first[h].next;
144         blkcache.first[h].next = bcep;
145     }
146     bcep->hit = bp->info;
147     return (NULL);
148 }
149