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