1 c35a7943 2018-07-12 stsp /*
  2 c35a7943 2018-07-12 stsp  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
  3 c35a7943 2018-07-12 stsp  *
  4 c35a7943 2018-07-12 stsp  * Permission to use, copy, modify, and distribute this software for any
  5 c35a7943 2018-07-12 stsp  * purpose with or without fee is hereby granted, provided that the above
  6 c35a7943 2018-07-12 stsp  * copyright notice and this permission notice appear in all copies.
  7 c35a7943 2018-07-12 stsp  *
  8 c35a7943 2018-07-12 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9 c35a7943 2018-07-12 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 10 c35a7943 2018-07-12 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 11 c35a7943 2018-07-12 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 12 c35a7943 2018-07-12 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 13 c35a7943 2018-07-12 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 14 c35a7943 2018-07-12 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 15 c35a7943 2018-07-12 stsp  */
 16 c35a7943 2018-07-12 stsp 
 17 c35a7943 2018-07-12 stsp #include <sys/queue.h>
 18 c35a7943 2018-07-12 stsp #include <sys/stat.h>
 19 c35a7943 2018-07-12 stsp 
 20 c35a7943 2018-07-12 stsp #include <stdio.h>
 21 c35a7943 2018-07-12 stsp #include <stdlib.h>
 22 c35a7943 2018-07-12 stsp #include <sha1.h>
 23 c35a7943 2018-07-12 stsp #include <zlib.h>
 24 c35a7943 2018-07-12 stsp 
 25 c35a7943 2018-07-12 stsp #include "got_object.h"
 26 c35a7943 2018-07-12 stsp 
 27 c35a7943 2018-07-12 stsp #include "got_error.h"
 28 c35a7943 2018-07-12 stsp #include "got_lib_delta.h"
 29 c35a7943 2018-07-12 stsp #include "got_lib_inflate.h"
 30 c35a7943 2018-07-12 stsp #include "got_lib_object.h"
 31 c35a7943 2018-07-12 stsp #include "got_lib_diffoffset.h"
 32 c35a7943 2018-07-12 stsp 
 33 c35a7943 2018-07-12 stsp /*
 34 c35a7943 2018-07-12 stsp  * A line offset between an old file and a new file, derived from diff chunk
 35 c35a7943 2018-07-12 stsp  * header info @@ -old_lineno,old_length +new_lineno,new_length @@ in a diff
 36 c35a7943 2018-07-12 stsp  * with zero context lines (as in diff -U0 old-file new-file).
 37 c35a7943 2018-07-12 stsp  */
 38 c35a7943 2018-07-12 stsp struct got_diffoffset_chunk {
 39 c35a7943 2018-07-12 stsp 	int lineno;	/* first line which has shifted */
 40 c35a7943 2018-07-12 stsp 	int offset;	/* applies to subsequent lines until next chunk */
 41 c35a7943 2018-07-12 stsp 	SIMPLEQ_ENTRY(got_diffoffset_chunk) entry;
 42 c35a7943 2018-07-12 stsp };
 43 c35a7943 2018-07-12 stsp 
 44 c35a7943 2018-07-12 stsp static struct got_diffoffset_chunk *
 45 c35a7943 2018-07-12 stsp alloc_chunk(int lineno, int offset)
 46 c35a7943 2018-07-12 stsp {
 47 c35a7943 2018-07-12 stsp 	struct got_diffoffset_chunk *chunk;
 48 c35a7943 2018-07-12 stsp 
 49 c35a7943 2018-07-12 stsp 	chunk = calloc(1, sizeof(*chunk));
 50 c35a7943 2018-07-12 stsp 	if (chunk == NULL)
 51 c35a7943 2018-07-12 stsp 		return NULL;
 52 c35a7943 2018-07-12 stsp 
 53 c35a7943 2018-07-12 stsp 	chunk->lineno = lineno;
 54 c35a7943 2018-07-12 stsp 	chunk->offset = offset;
 55 c35a7943 2018-07-12 stsp 
 56 c35a7943 2018-07-12 stsp 	return chunk;
 57 c35a7943 2018-07-12 stsp }
 58 c35a7943 2018-07-12 stsp 
 59 c35a7943 2018-07-12 stsp const struct got_error *
 60 c35a7943 2018-07-12 stsp got_diffoffset_alloc(struct got_diffoffset_chunks **chunks)
 61 c35a7943 2018-07-12 stsp {
 62 c35a7943 2018-07-12 stsp 	const struct got_error *err = NULL;
 63 c35a7943 2018-07-12 stsp 
 64 c35a7943 2018-07-12 stsp 	*chunks = calloc(1, sizeof(**chunks));
 65 c35a7943 2018-07-12 stsp 	if (*chunks == NULL) {
 66 638f9024 2019-05-13 stsp 		err = got_error_from_errno("calloc");
 67 c35a7943 2018-07-12 stsp 		return err;
 68 c35a7943 2018-07-12 stsp 	}
 69 c35a7943 2018-07-12 stsp 
 70 c35a7943 2018-07-12 stsp 	SIMPLEQ_INIT(*chunks);
 71 c35a7943 2018-07-12 stsp 	return NULL;
 72 c35a7943 2018-07-12 stsp }
 73 c35a7943 2018-07-12 stsp 
 74 c35a7943 2018-07-12 stsp void
 75 c35a7943 2018-07-12 stsp got_diffoffset_free(struct got_diffoffset_chunks *chunks)
 76 c35a7943 2018-07-12 stsp {
 77 c35a7943 2018-07-12 stsp 	struct got_diffoffset_chunk *chunk;
 78 c35a7943 2018-07-12 stsp 
 79 c35a7943 2018-07-12 stsp 	while (!SIMPLEQ_EMPTY(chunks)) {
 80 c35a7943 2018-07-12 stsp 		chunk = SIMPLEQ_FIRST(chunks);
 81 c35a7943 2018-07-12 stsp 		SIMPLEQ_REMOVE_HEAD(chunks, entry);
 82 c35a7943 2018-07-12 stsp 		free(chunk);
 83 c35a7943 2018-07-12 stsp 	}
 84 c35a7943 2018-07-12 stsp 	free(chunks);
 85 c35a7943 2018-07-12 stsp }
 86 c35a7943 2018-07-12 stsp 
 87 c35a7943 2018-07-12 stsp const struct got_error *
 88 1e45b069 2019-08-19 stsp add_chunk(struct got_diffoffset_chunks *chunks, int lineno, int offset)
 89 c35a7943 2018-07-12 stsp {
 90 1e45b069 2019-08-19 stsp 	struct got_diffoffset_chunk *chunk;
 91 c35a7943 2018-07-12 stsp 
 92 1e45b069 2019-08-19 stsp 	chunk = alloc_chunk(lineno, offset);
 93 1e45b069 2019-08-19 stsp 	if (chunk == NULL)
 94 638f9024 2019-05-13 stsp 		return got_error_from_errno("alloc_chunk");
 95 c35a7943 2018-07-12 stsp 
 96 1e45b069 2019-08-19 stsp 	SIMPLEQ_INSERT_TAIL(chunks, chunk, entry);
 97 1e45b069 2019-08-19 stsp 	return NULL;
 98 1e45b069 2019-08-19 stsp }
 99 1e45b069 2019-08-19 stsp 
100 1e45b069 2019-08-19 stsp 
101 1e45b069 2019-08-19 stsp const struct got_error *
102 1e45b069 2019-08-19 stsp got_diffoffset_add(struct got_diffoffset_chunks *chunks,
103 1e45b069 2019-08-19 stsp     int old_lineno, int old_length, int new_lineno, int new_length)
104 1e45b069 2019-08-19 stsp {
105 1e45b069 2019-08-19 stsp 	const struct got_error *err = NULL;
106 1e45b069 2019-08-19 stsp 	int offset;
107 1e45b069 2019-08-19 stsp 
108 548237bc 2019-08-19 stsp 	if (old_length != 0) {
109 548237bc 2019-08-19 stsp 		offset = new_lineno - old_lineno;
110 548237bc 2019-08-19 stsp 		if (offset != 0) {
111 548237bc 2019-08-19 stsp 			err = add_chunk(chunks, old_lineno, offset);
112 548237bc 2019-08-19 stsp 			if (err)
113 548237bc 2019-08-19 stsp 				return err;
114 548237bc 2019-08-19 stsp 		}
115 548237bc 2019-08-19 stsp 	} else {
116 548237bc 2019-08-19 stsp 		offset = new_length;
117 548237bc 2019-08-19 stsp 		if (offset != 0) {
118 548237bc 2019-08-19 stsp 			err = add_chunk(chunks, old_lineno, offset);
119 548237bc 2019-08-19 stsp 			if (err)
120 548237bc 2019-08-19 stsp 				return err;
121 548237bc 2019-08-19 stsp 		}
122 548237bc 2019-08-19 stsp 		if (old_lineno == new_lineno)
123 548237bc 2019-08-19 stsp 			return NULL;
124 c35a7943 2018-07-12 stsp 	}
125 c35a7943 2018-07-12 stsp 
126 1e45b069 2019-08-19 stsp 	offset = new_lineno - old_lineno + new_length - old_length;
127 1e45b069 2019-08-19 stsp 	if (offset != 0)
128 548237bc 2019-08-19 stsp 		err = add_chunk(chunks, old_lineno + new_length, offset);
129 1e45b069 2019-08-19 stsp 
130 1e45b069 2019-08-19 stsp 	return err;
131 c35a7943 2018-07-12 stsp }
132 c35a7943 2018-07-12 stsp 
133 c35a7943 2018-07-12 stsp int
134 c35a7943 2018-07-12 stsp got_diffoffset_get(struct got_diffoffset_chunks *chunks, int lineno)
135 c35a7943 2018-07-12 stsp {
136 548237bc 2019-08-19 stsp 	struct got_diffoffset_chunk *chunk;
137 548237bc 2019-08-19 stsp 	int offset = 0;
138 c35a7943 2018-07-12 stsp 
139 c35a7943 2018-07-12 stsp 	SIMPLEQ_FOREACH(chunk, chunks, entry) {
140 c35a7943 2018-07-12 stsp 		if (chunk->lineno > lineno)
141 c35a7943 2018-07-12 stsp 			break;
142 548237bc 2019-08-19 stsp 		offset += chunk->offset;
143 c35a7943 2018-07-12 stsp 	}
144 c35a7943 2018-07-12 stsp 
145 548237bc 2019-08-19 stsp 	return lineno + offset;
146 c35a7943 2018-07-12 stsp }