mem.c (5393B)
1 /* See LICENSE file for copyright and license details. */ 2 3 #include "proto.h" 4 5 /* In this file a simplified version of the rsync 6 * algorithm is implemented. The idea is to diff 7 * two memory regions and pack the differences in 8 * a diff structure. */ 9 10 /* Increase this for more verbose output */ 11 static int verbose = 0; 12 13 /* This is a simple rolling sum taken from 14 * the core rsync algorithm */ 15 uint32_t 16 weak_sum(const void *buf, size_t len) 17 { 18 size_t i; 19 uint32_t s1, s2; 20 const unsigned char *p = buf; 21 22 s1 = s2 = 0; 23 for (i = 0; i < len; i++) { 24 s1 += p[i]; 25 s2 += s1; 26 } 27 return (s1 & 0xffff) + (s2 << 16); 28 } 29 30 void 31 strong_sum(const void *buf, size_t len, void *digest) 32 { 33 MD5_CTX md5_ctx; 34 const uint8_t *p = (const uint8_t *)buf; 35 36 MD5Init(&md5_ctx); 37 MD5Update(&md5_ctx, p, len); 38 MD5Final(digest, &md5_ctx); 39 } 40 41 void 42 dump_mem_blk(struct mem_blk *mb) 43 { 44 int i; 45 46 if (!mb) 47 return; 48 49 printf("weak sum: %08x\n", mb->weak_sum); 50 printf("MD5 hash: "); 51 for (i = 0; i < MD5_DIGEST_LENGTH; i++) 52 printf("%02x", mb->digest[i]); 53 putchar('\n'); 54 printf("offset: %jd\n", (intmax_t)mb->offset); 55 printf("len: %zu\n", mb->len); 56 57 } 58 59 /* Given a buffer, build a region that describes it. 60 * NOTE: The passed in `buf' is bound to this memory 61 * region and *cannot* be freed until after the call 62 * to free_memory_region(). */ 63 struct mem_region * 64 build_mem_region(unsigned char *buf, size_t len) 65 { 66 struct mem_blk *mb; 67 struct mem_region *mr; 68 size_t offset = 0; 69 size_t i; 70 size_t n; 71 72 if (!buf || !len) 73 return NULL; 74 75 mr = xmalloc(sizeof(*mr)); 76 memset(mr, 0, sizeof(*mr)); 77 mr->rsize = len; 78 mr->nblocks = num_blocks(len); 79 mr->rem = len % BLKSIZE; 80 mr->blksize = BLKSIZE; 81 mr->mblks = xmalloc(sizeof(struct mem_blk) * mr->nblocks); 82 83 if (verbose > 0) 84 fprintf(stderr, "%s: blksize: %d, rsize: %zu, nblocks: %zu, rem: %zu\n", 85 __func__, BLKSIZE, mr->rsize, mr->nblocks, mr->rem); 86 87 for (i = 0; i < mr->nblocks; i++) { 88 n = min(len, BLKSIZE); 89 mb = &mr->mblks[i]; 90 mb->buf = buf; 91 mb->weak_sum = weak_sum(buf, n); 92 strong_sum(buf, n, mb->digest); 93 mb->offset = offset; 94 mb->len = n; 95 if (verbose > 1) { 96 fprintf(stderr, "%s: adding node with weak sum: %08x", 97 __func__, mb->weak_sum); 98 fprintf(stderr, " at offset: %jd of len: %zu\n", 99 (intmax_t)mb->offset, mb->len); 100 } 101 len -= n; 102 buf += n; 103 offset += n; 104 } 105 return mr; 106 } 107 108 void 109 dump_mem_region(struct mem_region *mr) 110 { 111 size_t i; 112 113 if (!mr) 114 return; 115 116 for (i = 0; i < mr->nblocks; i++) 117 dump_mem_blk(&mr->mblks[i]); 118 } 119 120 void 121 free_mem_region(struct mem_region *mr) 122 { 123 if (!mr) 124 return; 125 126 free(mr->mblks); 127 free(mr); 128 } 129 130 /* Diff the two memory regions and return a 131 * a diff structure. In fact `dst' describes 132 * the *old* memory region and `src' is the 133 * *new* and updated copy */ 134 struct mem_region_diff * 135 diff_mem_region(struct mem_region *dst, 136 struct mem_region *src) 137 { 138 struct mem_blk *mb_src, *mb_dst; 139 struct mem_diff *mdiff; 140 struct mem_region_diff *rdiff; 141 size_t i; 142 bool found; 143 size_t size; 144 145 if (!dst || !src) 146 return NULL; 147 148 rdiff = xmalloc(sizeof(*rdiff)); 149 rdiff->mrdiffs = NULL; 150 rdiff->nmrdiffs = 0; 151 152 /* We can only diff regions of the same size */ 153 if (dst->rsize != src->rsize) 154 errx(1, "dst->rsize != src->rsize"); 155 156 for (i = 0; i < src->nblocks; i++) { 157 found = false; 158 /* We diff block by block, the memory regions 159 * contain rsize / blksize number of memory blocks */ 160 mb_src = &src->mblks[i]; 161 mb_dst = &dst->mblks[i]; 162 if (mb_src->weak_sum == mb_dst->weak_sum) { 163 if (mb_src->offset != mb_dst->offset) 164 errx(1, "mb_src->offset != mb_dst->offset"); 165 if (!memcmp(mb_src->digest, 166 mb_dst->digest, 167 MD5_DIGEST_LENGTH)) { 168 found = true; 169 } 170 } 171 if (!found) { 172 size = (rdiff->nmrdiffs + 1) * sizeof(*rdiff->mrdiffs); 173 rdiff->mrdiffs = xrealloc(rdiff->mrdiffs, size); 174 mdiff = &rdiff->mrdiffs[rdiff->nmrdiffs]; 175 mdiff->buf = xmalloc(mb_src->len); 176 memcpy(mdiff->buf, mb_src->buf, mb_src->len); 177 mdiff->offset = mb_src->offset; 178 mdiff->len = mb_src->len; 179 mdiff->index = i; 180 rdiff->nmrdiffs++; 181 } 182 } 183 return rdiff; 184 } 185 186 /* Apply the diff on `dst'. We return the same 187 * memory region as was passed in. */ 188 struct mem_region * 189 apply_diff(struct mem_region *dst, 190 struct mem_region_diff *rdiff) 191 { 192 size_t i; 193 struct mem_diff *mdiff; 194 struct mem_blk *mb; 195 196 if (!dst || !rdiff) 197 return NULL; 198 199 if (!rdiff->nmrdiffs) 200 return NULL; 201 202 for (i = 0; i < rdiff->nmrdiffs; i++) { 203 mdiff = &rdiff->mrdiffs[i]; 204 mb = &dst->mblks[mdiff->index]; 205 if (verbose > 1) 206 fprintf(stderr, "patching block %d\n", 207 mdiff->index); 208 if (mdiff->len != mb->len) 209 errx(1, "mdiff->len != mb->len"); 210 /* Patch it! */ 211 memcpy(mb->buf, mdiff->buf, mb->len); 212 } 213 return dst; 214 } 215 216 void 217 dump_mem_region_diff(struct mem_region_diff *rdiff) 218 { 219 struct mem_diff *mdiff; 220 char *p; 221 size_t i, j; 222 223 if (!rdiff) 224 return; 225 226 for (i = 0; i < rdiff->nmrdiffs; i++) { 227 mdiff = &rdiff->mrdiffs[i]; 228 printf("buf: %p: ", mdiff->buf); 229 p = mdiff->buf; 230 for (j = 0; j < 64 && j < mdiff->len; j++) 231 putchar(p[j]); 232 putchar('\n'); 233 printf("offset: %jd\n", (intmax_t)mdiff->offset); 234 printf("len: %zu\n", mdiff->len); 235 } 236 } 237 238 void 239 free_mem_region_diff(struct mem_region_diff *rdiff) 240 { 241 struct mem_diff *mdiff; 242 size_t i; 243 244 if (!rdiff) 245 return; 246 247 for (i = 0; i < rdiff->nmrdiffs; i++) { 248 mdiff = &rdiff->mrdiffs[i]; 249 free(mdiff->buf); 250 } 251 free(rdiff->mrdiffs); 252 free(rdiff); 253 }