53  * @dst:
61 static __inline__ void ntfs_rl_mm(runlist_element *base, int dst, int src,
64 	if ((dst != src) && (size > 0))
65 		memmove(base + dst, base + src, size * sizeof(*base));
71  * @dst:
80 static __inline__ void ntfs_rl_mc(runlist_element *dstbase, int dst,
84 		memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
115  * @dst:	original runlist
116  * @src:	new runlist to test for mergeability with @dst
124 static BOOL ntfs_rl_are_mergeable(runlist_element *dst,
127 	if (!dst || !src) {
134 	if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
137 	if ((dst->vcn + dst->length) != src->vcn)
140 	if ((dst->lcn >= 0) && (src->lcn >= 0) &&
141 		((dst->lcn + dst->length) == src->lcn))
144 	if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
152  * @dst:	original, destination runlist
153  * @src:	new runlist to merge with @dst
155  * Merge the two runlists, writing into the destination runlist @dst. The
159 static __inline__ void __ntfs_rl_merge(runlist_element *dst,
162 	dst->length += src->length;
167  * @dst:	original runlist to be worked on
168  * @dsize:	number of elements in @dst (including end marker)
169  * @src:	runlist to be inserted into @dst
171  * @loc:	append the new runlist @src after this element in @dst
173  * Append the runlist @src after element @loc in @dst.  Merge the right end of
178  * runlists @dst and @src are deallocated before returning so you cannot use
180  * may be the same as @dst but this is irrelevant.)
185 static runlist_element *ntfs_rl_append(runlist_element *dst,
191 	if (!dst || !src) {
200 		right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
202 	/* Space required: @dst size + @src size, less one if we merged. */
203 	dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
204 	if (!dst)
213 		__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
218 	/* Move the tail of @dst out of the way, then copy in @src. */
219 	ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - loc - 1 - right);
220 	ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
223 	dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
226 	if (dst[marker].lcn == LCN_ENOENT)
227 		dst[marker].vcn = dst[marker-1].vcn + dst[marker-1].length;
229 	return dst;
234  * @dst:	original runlist to be worked on
235  * @dsize:	number of elements in @dst (including end marker)
238  * @loc:	insert the new runlist @src before this element in @dst
240  * Insert the runlist @src before element @loc in the runlist @dst. Merge the
245  * runlists @dst and @src are deallocated before returning so you cannot use
247  * may be the same as @dst but this is irrelevant.)
252 static runlist_element *ntfs_rl_insert(runlist_element *dst,
256 	BOOL disc = FALSE;	/* Discontinuity between @dst and @src */
259 	if (!dst || !src) {
266 	/* disc => Discontinuity between the end of @dst and the start of @src.
274 		left = ntfs_rl_are_mergeable(dst + loc - 1, src);
276 		merged_length = dst[loc - 1].length;
280 		disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
283 	/* Space required: @dst size + @src size, less one if we merged, plus
286 	dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
287 	if (!dst)
295 		__ntfs_rl_merge(dst + loc - 1, src);
300 	 * If "left", then the first run in @src has been merged with one in @dst.
301 	 * If "disc", then @dst and @src don't meet and we need an extra run to fill the gap.
305 	/* Move the tail of @dst out of the way, then copy in @src. */
306 	ntfs_rl_mm(dst, marker, loc, dsize - loc);
307 	ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
310 	dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
312 	if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
313 		dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;
318 			dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
319 			dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
321 			dst[loc].vcn = 0;
322 			dst[loc].length = dst[loc + 1].vcn;
324 		dst[loc].lcn = LCN_RL_NOT_MAPPED;
326 	return dst;
331  * @dst:	original runlist to be worked on
332  * @dsize:	number of elements in @dst (including end marker)
335  * @loc:	index in runlist @dst to overwrite with @src
337  * Replace the runlist element @dst at @loc with @src. Merge the left and
341  * runlists @dst and @src are deallocated before returning so you cannot use
343  * may be the same as @dst but this is irrelevant.)
348 static runlist_element *ntfs_rl_replace(runlist_element *dst,
354 	int tail;		/* Start of tail of @dst */
357 	if (!dst || !src) {
366 		right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
368 		left = ntfs_rl_are_mergeable(dst + loc - 1, src);
375 		dst = ntfs_rl_realloc(dst, dsize, dsize + delta);
376 		if (!dst)
386 		__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
388 		__ntfs_rl_merge(dst + loc - 1, src);
391 	 * tail - Offset of the tail of @dst
393 	 * If "right", then one of @dst's runs is already merged into @src.
400 	 * If "left", then the first run in @src has been merged with one in @dst.
404 	/* Move the tail of @dst out of the way, then copy in @src. */
405 	ntfs_rl_mm(dst, marker, tail, dsize - tail);
406 	ntfs_rl_mc(dst, loc, src, left, ssize - left);
409 	if (((dsize - tail) > 0) && (dst[marker].lcn == LCN_ENOENT))
410 		dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
412 	return dst;
417  * @dst:	original runlist to be worked on
418  * @dsize:	number of elements in @dst (including end marker)
421  * @loc:	index in runlist @dst at which to split and insert @src
423  * Split the runlist @dst at @loc into two and insert @new in between the two
428  * runlists @dst and @src are deallocated before returning so you cannot use
430  * may be the same as @dst but this is irrelevant.)
435 static runlist_element *ntfs_rl_split(runlist_element *dst,
438 	if (!dst || !src) {
444 	/* Space required: @dst size + @src size + one new hole. */
445 	dst = ntfs_rl_realloc(dst, dsize, dsize + ssize + 1);
446 	if (!dst)
447 		return dst;
453 	/* Move the tail of @dst out of the way, then copy in @src. */
454 	ntfs_rl_mm(dst, loc + 1 + ssize, loc, dsize - loc);
455 	ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
458 	dst[loc].length		= dst[loc+1].vcn       - dst[loc].vcn;
459 	dst[loc+ssize+1].vcn	= dst[loc+ssize].vcn   + dst[loc+ssize].length;
460 	dst[loc+ssize+1].length	= dst[loc+ssize+2].vcn - dst[loc+ssize+1].vcn;
462 	return dst;
490  * may be the same as @dst but this is irrelevant.)
510 	ntfs_log_debug("dst:\n");
1393  * @dst:	destination buffer to write to
1397  * Store in @dst, the minimum bytes of the number @n which are required to
1399  * @dest_max, the maximum position within @dst to which we are allowed to
1407  * destination buffer @dst is too small, return -1 with errno set ENOSPC.
1409 int ntfs_write_significant_bytes(u8 *dst, const u8 *dst_max, const s64 n)
1417 		if (dst > dst_max)
1419 		*dst++ = l & 0xffLL;
1426 		if (dst > dst_max)
1429 		*dst = (u8)-1;
1431 		if (dst > dst_max)
1434 		*dst = 0;
1445  * @dst:	destination buffer to which to write the mapping pairs array
1446  * @dst_len:	size of destination buffer @dst in bytes
1452  * @start_vcn and save the array in @dst.  @dst_len is the size of @dst in
1456  * If @rl is NULL, just write a single terminator byte to @dst.
1459  * the first vcn outside the destination buffer. Note that on error @dst has
1473 int ntfs_mapping_pairs_build(const ntfs_volume *vol, u8 *dst,
1493 		*dst = 0;
1505 	dst_max = dst + dst_len - 1;
1516 		len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1534 			lcn_len = ntfs_write_significant_bytes(dst + 1 +
1540 		dst_next = dst + len_len + lcn_len + 1;
1544 		*dst = lcn_len << 4 | len_len;
1546 		dst = dst_next;
1555 		len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1570 			lcn_len = ntfs_write_significant_bytes(dst + 1 +
1577 		dst_next = dst + len_len + lcn_len + 1;
1581 		*dst = lcn_len << 4 | len_len;
1583 		dst += 1 + len_len + lcn_len;
1589 	*dst = 0;
1596 	*dst = 0;
1814 	printf("dst:\n");
1911 	runlist_element *dst;
1915 	dst = malloc(4096);
1917 	memcpy(dst, file, size);
1920 	res = test_rl_runlists_merge(dst, src);

Indexes created Tue Jul 24 14:28:13 CEST 2018