1 /* Split source by line breaks, and calculate a simplistic checksum. */
2 /*
3  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17 
18 #include <errno.h>
19 #include <inttypes.h>
20 #include <stdbool.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <unistd.h>
24 #include <ctype.h>
25 
26 #include <arraylist.h>
27 #include <diff_main.h>
28 
29 #include "diff_internal.h"
30 #include "diff_debug.h"
31 
32 static int
33 diff_data_atomize_text_lines_fd(struct diff_data *d)
34 {
35 	off_t pos = 0;
36 	const off_t end = pos + d->len;
37 	unsigned int array_size_estimate = d->len / 50;
38 	unsigned int pow2 = 1;
39 	bool ignore_whitespace = (d->diff_flags & DIFF_FLAG_IGNORE_WHITESPACE);
40 
41 	while (array_size_estimate >>= 1)
42 		pow2++;
43 
44 	ARRAYLIST_INIT(d->atoms, 1 << pow2);
45 
46 	if (fseek(d->root->f, 0L, SEEK_SET) == -1)
47 		return errno;
48 
49 	while (pos < end) {
50 		off_t line_end = pos;
51 		unsigned int hash = 0;
52 		unsigned char buf[512];
53 		size_t r, i;
54 		struct diff_atom *atom;
55 		int eol = 0;
56 
57 		while (eol == 0 && line_end < end) {
58 			r = fread(buf, sizeof(char), sizeof(buf), d->root->f);
59 			if (r == 0 && ferror(d->root->f))
60 				return errno;
61 			i = 0;
62 			while (eol == 0 && i < r) {
63 				if (buf[i] != '\r' && buf[i] != '\n') {
64 					if (!ignore_whitespace
65 					    || !isspace(buf[i]))
66 						hash = hash * 23 + buf[i];
67 					line_end++;
68 				} else
69 					eol = buf[i];
70 				i++;
71 			}
72 		}
73 
74 		/* When not at the end of data, the line ending char ('\r' or
75 		 * '\n') must follow */
76 		if (line_end < end)
77 			line_end++;
78 		/* If that was an '\r', also pull in any following '\n' */
79 		if (line_end < end && eol == '\r') {
80 			if (fseeko(d->root->f, line_end, SEEK_SET) == -1)
81 				return errno;
82 			r = fread(buf, sizeof(char), sizeof(buf), d->root->f);
83 			if (r == 0 && ferror(d->root->f))
84 				return errno;
85 			if (r == 1 && buf[0] == '\n' )
86 				line_end++;
87 		}
88 
89 		/* Record the found line as diff atom */
90 		ARRAYLIST_ADD(atom, d->atoms);
91 		if (!atom)
92 			return ENOMEM;
93 
94 		*atom = (struct diff_atom){
95 			.root = d,
96 			.pos = pos,
97 			.at = NULL,	/* atom data is not memory-mapped */
98 			.len = line_end - pos,
99 			.hash = hash,
100 		};
101 
102 		/* Starting point for next line: */
103 		pos = line_end;
104 		if (fseeko(d->root->f, pos, SEEK_SET) == -1)
105 			return errno;
106 	}
107 
108 	return DIFF_RC_OK;
109 }
110 
111 static int
112 diff_data_atomize_text_lines_mmap(struct diff_data *d)
113 {
114 	const uint8_t *pos = d->data;
115 	const uint8_t *end = pos + d->len;
116 	bool ignore_whitespace = (d->diff_flags & DIFF_FLAG_IGNORE_WHITESPACE);
117 
118 	unsigned int array_size_estimate = d->len / 50;
119 	unsigned int pow2 = 1;
120 	while (array_size_estimate >>= 1)
121 		pow2++;
122 
123 	ARRAYLIST_INIT(d->atoms, 1 << pow2);
124 
125 	while (pos < end) {
126 		const uint8_t *line_end = pos;
127 		unsigned int hash = 0;
128 
129 		while (line_end < end && *line_end != '\r' && *line_end != '\n') {
130 			if (!ignore_whitespace
131 			    || !isspace(*line_end))
132 				hash = hash * 23 + *line_end;
133 			line_end++;
134 		}
135 
136 		/* When not at the end of data, the line ending char ('\r' or
137 		 * '\n') must follow */
138 		if (line_end < end)
139 			line_end++;
140 		/* If that was an '\r', also pull in any following '\n' */
141 		if (line_end < end - 1 && line_end[0] == '\r' &&
142 		    line_end[1] == '\n')
143 			line_end++;
144 
145 		/* Record the found line as diff atom */
146 		struct diff_atom *atom;
147 		ARRAYLIST_ADD(atom, d->atoms);
148 		if (!atom)
149 			return ENOMEM;
150 
151 		*atom = (struct diff_atom){
152 			.root = d,
153 			.pos = (off_t)(pos - d->data),
154 			.at = pos,
155 			.len = line_end - pos,
156 			.hash = hash,
157 		};
158 
159 		/* Starting point for next line: */
160 		pos = line_end;
161 	}
162 
163 	return DIFF_RC_OK;
164 }
165 
166 static int
167 diff_data_atomize_text_lines(struct diff_data *d)
168 {
169 	if (d->data == NULL)
170 		return diff_data_atomize_text_lines_fd(d);
171 	else
172 		return diff_data_atomize_text_lines_mmap(d);
173 }
174 
175 int
176 diff_atomize_text_by_line(void *func_data, struct diff_data *d)
177 {
178 	return diff_data_atomize_text_lines(d);
179 }