1 3b0f3d61 2020-01-22 neels /* Split source by line breaks, and calculate a simplistic checksum. */
3 3b0f3d61 2020-01-22 neels * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
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.
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.
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>
25 e10a628a 2020-09-16 stsp #include <diff/arraylist.h>
26 3b0f3d61 2020-01-22 neels #include <diff/diff_main.h>
27 e4464189 2020-09-20 stsp #include "diff_debug.h"
28 85ab4559 2020-09-22 stsp #include "diff_internal.h"
31 c6eecea3 2020-07-26 stsp diff_data_atomize_text_lines_fd(struct diff_data *d)
33 7a54ad3a 2020-09-20 stsp off_t pos = 0;
34 c6eecea3 2020-07-26 stsp const off_t end = pos + d->len;
35 c6eecea3 2020-07-26 stsp unsigned int array_size_estimate = d->len / 50;
36 c6eecea3 2020-07-26 stsp unsigned int pow2 = 1;
38 c6eecea3 2020-07-26 stsp while (array_size_estimate >>= 1)
41 c6eecea3 2020-07-26 stsp ARRAYLIST_INIT(d->atoms, 1 << pow2);
43 7a54ad3a 2020-09-20 stsp if (fseek(d->root->f, 0L, SEEK_SET) == -1)
44 7a54ad3a 2020-09-20 stsp return errno;
46 c6eecea3 2020-07-26 stsp while (pos < end) {
47 c6eecea3 2020-07-26 stsp off_t line_end = pos;
48 c6eecea3 2020-07-26 stsp unsigned int hash = 0;
49 c6eecea3 2020-07-26 stsp unsigned char buf[512];
50 7a54ad3a 2020-09-20 stsp size_t r, i;
51 c6eecea3 2020-07-26 stsp struct diff_atom *atom;
52 c6eecea3 2020-07-26 stsp int eol = 0;
54 c6eecea3 2020-07-26 stsp while (eol == 0 && line_end < end) {
55 7a54ad3a 2020-09-20 stsp r = fread(buf, sizeof(char), sizeof(buf), d->root->f);
56 7a54ad3a 2020-09-20 stsp if (r == 0 && ferror(d->root->f))
57 c6eecea3 2020-07-26 stsp return errno;
59 c6eecea3 2020-07-26 stsp while (eol == 0 && i < r) {
60 c6eecea3 2020-07-26 stsp if (buf[i] != '\r' && buf[i] != '\n') {
61 c6eecea3 2020-07-26 stsp hash = hash * 23 + buf[i];
64 c6eecea3 2020-07-26 stsp eol = buf[i];
69 c6eecea3 2020-07-26 stsp /* When not at the end of data, the line ending char ('\r' or
70 c6eecea3 2020-07-26 stsp * '\n') must follow */
71 c6eecea3 2020-07-26 stsp if (line_end < end)
73 c6eecea3 2020-07-26 stsp /* If that was an '\r', also pull in any following '\n' */
74 c6eecea3 2020-07-26 stsp if (line_end < end && eol == '\r') {
75 7a54ad3a 2020-09-20 stsp if (fseeko(d->root->f, line_end, SEEK_SET) == -1)
76 c6eecea3 2020-07-26 stsp return errno;
77 7a54ad3a 2020-09-20 stsp r = fread(buf, sizeof(char), sizeof(buf), d->root->f);
78 7a54ad3a 2020-09-20 stsp if (r == 0 && ferror(d->root->f))
79 c6eecea3 2020-07-26 stsp return errno;
80 c6eecea3 2020-07-26 stsp if (r == 1 && buf[0] == '\n' )
84 c6eecea3 2020-07-26 stsp /* Record the found line as diff atom */
85 c6eecea3 2020-07-26 stsp ARRAYLIST_ADD(atom, d->atoms);
87 3e6cba3a 2020-08-13 stsp return ENOMEM;
89 c6eecea3 2020-07-26 stsp *atom = (struct diff_atom){
92 c6eecea3 2020-07-26 stsp .at = NULL, /* atom data is not memory-mapped */
93 c6eecea3 2020-07-26 stsp .len = line_end - pos,
94 c6eecea3 2020-07-26 stsp .hash = hash,
97 c6eecea3 2020-07-26 stsp /* Starting point for next line: */
98 c6eecea3 2020-07-26 stsp pos = line_end;
99 7a54ad3a 2020-09-20 stsp if (fseeko(d->root->f, pos, SEEK_SET) == -1)
100 03f49727 2020-09-20 stsp return errno;
103 c6eecea3 2020-07-26 stsp return DIFF_RC_OK;
107 c6eecea3 2020-07-26 stsp diff_data_atomize_text_lines_mmap(struct diff_data *d)
109 3b0f3d61 2020-01-22 neels const uint8_t *pos = d->data;
110 3b0f3d61 2020-01-22 neels const uint8_t *end = pos + d->len;
112 3b0f3d61 2020-01-22 neels unsigned int array_size_estimate = d->len / 50;
113 3b0f3d61 2020-01-22 neels unsigned int pow2 = 1;
114 3b0f3d61 2020-01-22 neels while (array_size_estimate >>= 1)
117 3b0f3d61 2020-01-22 neels ARRAYLIST_INIT(d->atoms, 1 << pow2);
119 3b0f3d61 2020-01-22 neels while (pos < end) {
120 3b0f3d61 2020-01-22 neels const uint8_t *line_end = pos;
121 3b0f3d61 2020-01-22 neels unsigned int hash = 0;
123 3b0f3d61 2020-01-22 neels while (line_end < end && *line_end != '\r' && *line_end != '\n') {
124 3b0f3d61 2020-01-22 neels hash = hash * 23 + *line_end;
125 3b0f3d61 2020-01-22 neels line_end++;
128 0d27172a 2020-05-06 neels /* When not at the end of data, the line ending char ('\r' or
129 0d27172a 2020-05-06 neels * '\n') must follow */
130 3b0f3d61 2020-01-22 neels if (line_end < end)
131 3b0f3d61 2020-01-22 neels line_end++;
132 3b0f3d61 2020-01-22 neels /* If that was an '\r', also pull in any following '\n' */
133 0d27172a 2020-05-06 neels if (line_end[0] == '\r'
134 0d27172a 2020-05-06 neels && line_end < end && line_end[1] == '\n')
135 3b0f3d61 2020-01-22 neels line_end++;
137 3b0f3d61 2020-01-22 neels /* Record the found line as diff atom */
138 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
139 3b0f3d61 2020-01-22 neels ARRAYLIST_ADD(atom, d->atoms);
140 3b0f3d61 2020-01-22 neels if (!atom)
141 3e6cba3a 2020-08-13 stsp return ENOMEM;
143 3b0f3d61 2020-01-22 neels *atom = (struct diff_atom){
145 c6eecea3 2020-07-26 stsp .pos = (off_t)(pos - d->data),
146 3b0f3d61 2020-01-22 neels .at = pos,
147 3b0f3d61 2020-01-22 neels .len = line_end - pos,
148 3b0f3d61 2020-01-22 neels .hash = hash,
151 3b0f3d61 2020-01-22 neels /* Starting point for next line: */
152 3b0f3d61 2020-01-22 neels pos = line_end;
155 3b0f3d61 2020-01-22 neels return DIFF_RC_OK;
159 c6eecea3 2020-07-26 stsp diff_data_atomize_text_lines(struct diff_data *d)
161 c6eecea3 2020-07-26 stsp if (d->data == NULL)
162 c6eecea3 2020-07-26 stsp return diff_data_atomize_text_lines_fd(d);
164 c6eecea3 2020-07-26 stsp return diff_data_atomize_text_lines_mmap(d);
168 0d27172a 2020-05-06 neels diff_atomize_text_by_line(void *func_data, struct diff_data *left,
169 0d27172a 2020-05-06 neels struct diff_data *right)
172 3b0f3d61 2020-01-22 neels rc = diff_data_atomize_text_lines(left);
173 3b0f3d61 2020-01-22 neels if (rc != DIFF_RC_OK)
174 3b0f3d61 2020-01-22 neels return rc;
175 3b0f3d61 2020-01-22 neels return diff_data_atomize_text_lines(right);