tor  0.4.2.1-alpha-dev
consdiff.c
Go to the documentation of this file.
1 /* Copyright (c) 2014, Daniel Martí
2  * Copyright (c) 2014-2019, The Tor Project, Inc. */
3 /* See LICENSE for licensing information */
4 
39 #define CONSDIFF_PRIVATE
40 
41 #include "core/or/or.h"
42 #include "feature/dircommon/consdiff.h"
43 #include "lib/memarea/memarea.h"
45 
46 static const char* ns_diff_version = "network-status-diff-version 1";
47 static const char* hash_token = "hash";
48 
49 static char *consensus_join_lines(const smartlist_t *inp);
50 
52 STATIC int
53 lines_eq(const cdline_t *a, const cdline_t *b)
54 {
55  return a->len == b->len && fast_memeq(a->s, b->s, a->len);
56 }
57 
59 STATIC int
60 line_str_eq(const cdline_t *a, const char *b)
61 {
62  const size_t len = strlen(b);
63  tor_assert(len <= UINT32_MAX);
64  cdline_t bline = { b, (uint32_t)len };
65  return lines_eq(a, &bline);
66 }
67 
70 static int
71 line_starts_with_str(const cdline_t *a, const char *b)
72 {
73  const size_t len = strlen(b);
74  tor_assert(len <= UINT32_MAX);
75  return a->len >= len && fast_memeq(a->s, b, len);
76 }
77 
80 static cdline_t *
81 cdline_linecpy(memarea_t *area, const char *s)
82 {
83  size_t len = strlen(s);
84  const char *ss = memarea_memdup(area, s, len);
85  cdline_t *line = memarea_alloc(area, sizeof(cdline_t));
86  line->s = ss;
87  line->len = (uint32_t)len;
88  return line;
89 }
90 
93 STATIC void
94 smartlist_add_linecpy(smartlist_t *lst, memarea_t *area, const char *s)
95 {
96  smartlist_add(lst, cdline_linecpy(area, s));
97 }
98 
101 /* This is a separate, mockable function so that we can override it when
102  * fuzzing. */
103 MOCK_IMPL(STATIC int,
104 consensus_compute_digest,(const char *cons, size_t len,
105  consensus_digest_t *digest_out))
106 {
107  int r = crypto_digest256((char*)digest_out->sha3_256,
108  cons, len, DIGEST_SHA3_256);
109  return r;
110 }
111 
114 /* This is a separate, mockable function so that we can override it when
115  * fuzzing. */
116 MOCK_IMPL(STATIC int,
117 consensus_compute_digest_as_signed,(const char *cons, size_t len,
118  consensus_digest_t *digest_out))
119 {
120  return router_get_networkstatus_v3_sha3_as_signed(digest_out->sha3_256,
121  cons, len);
122 }
123 
125 /* This is a separate, mockable function so that we can override it when
126  * fuzzing. */
127 MOCK_IMPL(STATIC int,
128 consensus_digest_eq,(const uint8_t *d1,
129  const uint8_t *d2))
130 {
131  return fast_memeq(d1, d2, DIGEST256_LEN);
132 }
133 
139 STATIC smartlist_slice_t *
140 smartlist_slice(const smartlist_t *list, int start, int end)
141 {
142  int list_len = smartlist_len(list);
143  tor_assert(start >= 0);
144  tor_assert(start <= list_len);
145  if (end == -1) {
146  end = list_len;
147  }
148  tor_assert(start <= end);
149 
150  smartlist_slice_t *slice = tor_malloc(sizeof(smartlist_slice_t));
151  slice->list = list;
152  slice->offset = start;
153  slice->len = end - start;
154  return slice;
155 }
156 
164 STATIC int *
165 lcs_lengths(const smartlist_slice_t *slice1, const smartlist_slice_t *slice2,
166  int direction)
167 {
168  size_t a_size = sizeof(int) * (slice2->len+1);
169 
170  /* Resulting lcs lengths. */
171  int *result = tor_malloc_zero(a_size);
172  /* Copy of the lcs lengths from the last iteration. */
173  int *prev = tor_malloc(a_size);
174 
175  tor_assert(direction == 1 || direction == -1);
176 
177  int si = slice1->offset;
178  if (direction == -1) {
179  si += (slice1->len-1);
180  }
181 
182  for (int i = 0; i < slice1->len; ++i, si+=direction) {
183 
184  const cdline_t *line1 = smartlist_get(slice1->list, si);
185  /* Store the last results. */
186  memcpy(prev, result, a_size);
187 
188  int sj = slice2->offset;
189  if (direction == -1) {
190  sj += (slice2->len-1);
191  }
192 
193  for (int j = 0; j < slice2->len; ++j, sj+=direction) {
194 
195  const cdline_t *line2 = smartlist_get(slice2->list, sj);
196  if (lines_eq(line1, line2)) {
197  /* If the lines are equal, the lcs is one line longer. */
198  result[j + 1] = prev[j] + 1;
199  } else {
200  /* If not, see what lcs parent path is longer. */
201  result[j + 1] = MAX(result[j], prev[j + 1]);
202  }
203  }
204  }
205  tor_free(prev);
206  return result;
207 }
208 
212 STATIC void
213 trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2)
214 {
215  while (slice1->len>0 && slice2->len>0) {
216  const cdline_t *line1 = smartlist_get(slice1->list, slice1->offset);
217  const cdline_t *line2 = smartlist_get(slice2->list, slice2->offset);
218  if (!lines_eq(line1, line2)) {
219  break;
220  }
221  slice1->offset++; slice1->len--;
222  slice2->offset++; slice2->len--;
223  }
224 
225  int i1 = (slice1->offset+slice1->len)-1;
226  int i2 = (slice2->offset+slice2->len)-1;
227 
228  while (slice1->len>0 && slice2->len>0) {
229  const cdline_t *line1 = smartlist_get(slice1->list, i1);
230  const cdline_t *line2 = smartlist_get(slice2->list, i2);
231  if (!lines_eq(line1, line2)) {
232  break;
233  }
234  i1--;
235  slice1->len--;
236  i2--;
237  slice2->len--;
238  }
239 }
240 
244 STATIC int
245 smartlist_slice_string_pos(const smartlist_slice_t *slice,
246  const cdline_t *string)
247 {
248  int end = slice->offset + slice->len;
249  for (int i = slice->offset; i < end; ++i) {
250  const cdline_t *el = smartlist_get(slice->list, i);
251  if (lines_eq(el, string)) {
252  return i;
253  }
254  }
255  return -1;
256 }
257 
263 STATIC void
264 set_changed(bitarray_t *changed1, bitarray_t *changed2,
265  const smartlist_slice_t *slice1, const smartlist_slice_t *slice2)
266 {
267  int toskip = -1;
268  tor_assert(slice1->len == 0 || slice1->len == 1);
269 
270  if (slice1->len == 1) {
271  const cdline_t *line_common = smartlist_get(slice1->list, slice1->offset);
272  toskip = smartlist_slice_string_pos(slice2, line_common);
273  if (toskip == -1) {
274  bitarray_set(changed1, slice1->offset);
275  }
276  }
277  int end = slice2->offset + slice2->len;
278  for (int i = slice2->offset; i < end; ++i) {
279  if (i != toskip) {
280  bitarray_set(changed2, i);
281  }
282  }
283 }
284 
285 /*
286  * Helper: Given that slice1 has been split by half into top and bot, we want
287  * to fetch the column at which to split slice2 so that we are still on track
288  * to the optimal diff solution, i.e. the shortest one. We use lcs_lengths
289  * since the shortest diff is just another way to say the longest common
290  * subsequence.
291  */
292 static int
293 optimal_column_to_split(const smartlist_slice_t *top,
294  const smartlist_slice_t *bot,
295  const smartlist_slice_t *slice2)
296 {
297  int *lens_top = lcs_lengths(top, slice2, 1);
298  int *lens_bot = lcs_lengths(bot, slice2, -1);
299  int column=0, max_sum=-1;
300 
301  for (int i = 0; i < slice2->len+1; ++i) {
302  int sum = lens_top[i] + lens_bot[slice2->len-i];
303  if (sum > max_sum) {
304  column = i;
305  max_sum = sum;
306  }
307  }
308  tor_free(lens_top);
309  tor_free(lens_bot);
310 
311  return column;
312 }
313 
326 STATIC void
327 calc_changes(smartlist_slice_t *slice1,
328  smartlist_slice_t *slice2,
329  bitarray_t *changed1, bitarray_t *changed2)
330 {
331  trim_slices(slice1, slice2);
332 
333  if (slice1->len <= 1) {
334  set_changed(changed1, changed2, slice1, slice2);
335 
336  } else if (slice2->len <= 1) {
337  set_changed(changed2, changed1, slice2, slice1);
338 
339  /* Keep on splitting the slices in two. */
340  } else {
341  smartlist_slice_t *top, *bot, *left, *right;
342 
343  /* Split the first slice in half. */
344  int mid = slice1->len/2;
345  top = smartlist_slice(slice1->list, slice1->offset, slice1->offset+mid);
346  bot = smartlist_slice(slice1->list, slice1->offset+mid,
347  slice1->offset+slice1->len);
348 
349  /* Split the second slice by the optimal column. */
350  int mid2 = optimal_column_to_split(top, bot, slice2);
351  left = smartlist_slice(slice2->list, slice2->offset, slice2->offset+mid2);
352  right = smartlist_slice(slice2->list, slice2->offset+mid2,
353  slice2->offset+slice2->len);
354 
355  calc_changes(top, left, changed1, changed2);
356  calc_changes(bot, right, changed1, changed2);
357  tor_free(top);
358  tor_free(bot);
359  tor_free(left);
360  tor_free(right);
361  }
362 }
363 
364 /* This table is from crypto.c. The SP and PAD defines are different. */
365 #define NOT_VALID_BASE64 255
366 #define X NOT_VALID_BASE64
367 #define SP NOT_VALID_BASE64
368 #define PAD NOT_VALID_BASE64
369 static const uint8_t base64_compare_table[256] = {
370  X, X, X, X, X, X, X, X, X, SP, SP, SP, X, SP, X, X,
371  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
372  SP, X, X, X, X, X, X, X, X, X, X, 62, X, X, X, 63,
373  52, 53, 54, 55, 56, 57, 58, 59, 60, 61, X, X, X, PAD, X, X,
374  X, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
375  15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, X, X, X, X, X,
376  X, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
377  41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, X, X, X, X, X,
378  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
379  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
380  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
381  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
382  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
383  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
384  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
385  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
386 };
387 
394 STATIC int
395 get_id_hash(const cdline_t *line, cdline_t *hash_out)
396 {
397  if (line->len < 2)
398  return -1;
399 
400  /* Skip the router name. */
401  const char *hash = memchr(line->s + 2, ' ', line->len - 2);
402  if (!hash) {
403  return -1;
404  }
405 
406  hash++;
407  const char *hash_end = hash;
408  /* Stop when the first non-base64 character is found. Use unsigned chars to
409  * avoid negative indexes causing crashes.
410  */
411  while (base64_compare_table[*((unsigned char*)hash_end)]
412  != NOT_VALID_BASE64 &&
413  hash_end < line->s + line->len) {
414  hash_end++;
415  }
416 
417  /* Empty hash. */
418  if (hash_end == hash) {
419  return -1;
420  }
421 
422  hash_out->s = hash;
423  /* Always true because lines are limited to this length */
424  tor_assert(hash_end >= hash);
425  tor_assert((size_t)(hash_end - hash) <= UINT32_MAX);
426  hash_out->len = (uint32_t)(hash_end - hash);
427 
428  return 0;
429 }
430 
434 STATIC int
435 is_valid_router_entry(const cdline_t *line)
436 {
437  if (line->len < 2 || fast_memneq(line->s, "r ", 2))
438  return 0;
439  cdline_t tmp;
440  return (get_id_hash(line, &tmp) == 0);
441 }
442 
448 STATIC int
449 next_router(const smartlist_t *cons, int cur)
450 {
451  int len = smartlist_len(cons);
452  tor_assert(cur >= -1 && cur < len);
453 
454  if (++cur >= len) {
455  return len;
456  }
457 
458  const cdline_t *line = smartlist_get(cons, cur);
459  while (!is_valid_router_entry(line)) {
460  if (++cur >= len) {
461  return len;
462  }
463  line = smartlist_get(cons, cur);
464  }
465  return cur;
466 }
467 
471 STATIC int
472 base64cmp(const cdline_t *hash1, const cdline_t *hash2)
473 {
474  /* NULL is always lower, useful for last_hash which starts at NULL. */
475  if (!hash1->s && !hash2->s) {
476  return 0;
477  }
478  if (!hash1->s) {
479  return -1;
480  }
481  if (!hash2->s) {
482  return 1;
483  }
484 
485  /* Don't index with a char; char may be signed. */
486  const unsigned char *a = (unsigned char*)hash1->s;
487  const unsigned char *b = (unsigned char*)hash2->s;
488  const unsigned char *a_end = a + hash1->len;
489  const unsigned char *b_end = b + hash2->len;
490  while (1) {
491  uint8_t av = base64_compare_table[*a];
492  uint8_t bv = base64_compare_table[*b];
493  if (av == NOT_VALID_BASE64) {
494  if (bv == NOT_VALID_BASE64) {
495  /* Both ended with exactly the same characters. */
496  return 0;
497  } else {
498  /* hash2 goes on longer than hash1 and thus hash1 is lower. */
499  return -1;
500  }
501  } else if (bv == NOT_VALID_BASE64) {
502  /* hash1 goes on longer than hash2 and thus hash1 is greater. */
503  return 1;
504  } else if (av < bv) {
505  /* The first difference shows that hash1 is lower. */
506  return -1;
507  } else if (av > bv) {
508  /* The first difference shows that hash1 is greater. */
509  return 1;
510  } else {
511  a++;
512  b++;
513  if (a == a_end) {
514  if (b == b_end) {
515  return 0;
516  } else {
517  return -1;
518  }
519  } else if (b == b_end) {
520  return 1;
521  }
522  }
523  }
524 }
525 
528 typedef struct router_id_iterator_t {
529  cdline_t last_hash;
530  cdline_t hash;
532 
536 #define ROUTER_ID_ITERATOR_INIT { { NULL, 0 }, { NULL, 0 } }
537 
546 static int
548  const char *consname,
549  int *idxp,
550  router_id_iterator_t *iter)
551 {
552  *idxp = next_router(cons, *idxp);
553  if (*idxp < smartlist_len(cons)) {
554  memcpy(&iter->last_hash, &iter->hash, sizeof(cdline_t));
555  if (get_id_hash(smartlist_get(cons, *idxp), &iter->hash) < 0 ||
556  base64cmp(&iter->hash, &iter->last_hash) <= 0) {
557  log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because "
558  "the %s consensus doesn't have its router entries sorted "
559  "properly.", consname);
560  return -1;
561  }
562  }
563  return 0;
564 }
565 
568 #define START_OF_SIGNATURES_SECTION "directory-signature "
569 
578 static cdline_t *
580  smartlist_t *cons)
581 {
582  int idx;
583  int dirsig_idx = -1;
584  for (idx = 0; idx < smartlist_len(cons); ++idx) {
585  cdline_t *line = smartlist_get(cons, idx);
587  dirsig_idx = idx;
588  break;
589  }
590  }
591  if (dirsig_idx >= 0) {
592  char buf[64];
593  while (smartlist_len(cons) > dirsig_idx)
594  smartlist_del(cons, dirsig_idx);
595  tor_snprintf(buf, sizeof(buf), "%d,$d", dirsig_idx+1);
596  return cdline_linecpy(area, buf);
597  } else {
598  return NULL;
599  }
600 }
601 
622 STATIC smartlist_t *
623 gen_ed_diff(const smartlist_t *cons1_orig, const smartlist_t *cons2,
624  memarea_t *area)
625 {
626  smartlist_t *cons1 = smartlist_new();
627  smartlist_add_all(cons1, cons1_orig);
628  cdline_t *remove_trailer = preprocess_consensus(area, cons1);
629 
630  int len1 = smartlist_len(cons1);
631  int len2 = smartlist_len(cons2);
632  smartlist_t *result = smartlist_new();
633 
634  if (remove_trailer) {
635  /* There's a delete-the-trailer line at the end, so add it here. */
636  smartlist_add(result, remove_trailer);
637  }
638 
639  /* Initialize the changed bitarrays to zero, so that calc_changes only needs
640  * to set the ones that matter and leave the rest untouched.
641  */
642  bitarray_t *changed1 = bitarray_init_zero(len1);
643  bitarray_t *changed2 = bitarray_init_zero(len2);
644  int i1=-1, i2=-1;
645  int start1=0, start2=0;
646 
647  /* To check that hashes are ordered properly */
650 
651  /* i1 and i2 are initialized at the first line of each consensus. They never
652  * reach past len1 and len2 respectively, since next_router doesn't let that
653  * happen. i1 and i2 are advanced by at least one line at each iteration as
654  * long as they have not yet reached len1 and len2, so the loop is
655  * guaranteed to end, and each pair of (i1,i2) will be inspected at most
656  * once.
657  */
658  while (i1 < len1 || i2 < len2) {
659 
660  /* Advance each of the two navigation positions by one router entry if not
661  * yet at the end.
662  */
663  if (i1 < len1) {
664  if (find_next_router_line(cons1, "base", &i1, &iter1) < 0) {
665  goto error_cleanup;
666  }
667  }
668 
669  if (i2 < len2) {
670  if (find_next_router_line(cons2, "target", &i2, &iter2) < 0) {
671  goto error_cleanup;
672  }
673  }
674 
675  /* If we have reached the end of both consensuses, there is no need to
676  * compare hashes anymore, since this is the last iteration.
677  */
678  if (i1 < len1 || i2 < len2) {
679 
680  /* Keep on advancing the lower (by identity hash sorting) position until
681  * we have two matching positions. The only other possible outcome is
682  * that a lower position reaches the end of the consensus before it can
683  * reach a hash that is no longer the lower one. Since there will always
684  * be a lower hash for as long as the loop runs, one of the two indexes
685  * will always be incremented, thus assuring that the loop must end
686  * after a finite number of iterations. If that cannot be because said
687  * consensus has already reached the end, both are extended to their
688  * respecting ends since we are done.
689  */
690  int cmp = base64cmp(&iter1.hash, &iter2.hash);
691  while (cmp != 0) {
692  if (i1 < len1 && cmp < 0) {
693  if (find_next_router_line(cons1, "base", &i1, &iter1) < 0) {
694  goto error_cleanup;
695  }
696  if (i1 == len1) {
697  /* We finished the first consensus, so grab all the remaining
698  * lines of the second consensus and finish up.
699  */
700  i2 = len2;
701  break;
702  }
703  } else if (i2 < len2 && cmp > 0) {
704  if (find_next_router_line(cons2, "target", &i2, &iter2) < 0) {
705  goto error_cleanup;
706  }
707  if (i2 == len2) {
708  /* We finished the second consensus, so grab all the remaining
709  * lines of the first consensus and finish up.
710  */
711  i1 = len1;
712  break;
713  }
714  } else {
715  i1 = len1;
716  i2 = len2;
717  break;
718  }
719  cmp = base64cmp(&iter1.hash, &iter2.hash);
720  }
721  }
722 
723  /* Make slices out of these chunks (up to the common router entry) and
724  * calculate the changes for them.
725  * Error if any of the two slices are longer than 10K lines. That should
726  * never happen with any pair of real consensuses. Feeding more than 10K
727  * lines to calc_changes would be very slow anyway.
728  */
729 #define MAX_LINE_COUNT (10000)
730  if (i1-start1 > MAX_LINE_COUNT || i2-start2 > MAX_LINE_COUNT) {
731  log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because "
732  "we found too few common router ids.");
733  goto error_cleanup;
734  }
735 
736  smartlist_slice_t *cons1_sl = smartlist_slice(cons1, start1, i1);
737  smartlist_slice_t *cons2_sl = smartlist_slice(cons2, start2, i2);
738  calc_changes(cons1_sl, cons2_sl, changed1, changed2);
739  tor_free(cons1_sl);
740  tor_free(cons2_sl);
741  start1 = i1, start2 = i2;
742  }
743 
744  /* Navigate the changes in reverse order and generate one ed command for
745  * each chunk of changes.
746  */
747  i1=len1-1, i2=len2-1;
748  char buf[128];
749  while (i1 >= 0 || i2 >= 0) {
750 
751  int start1x, start2x, end1, end2, added, deleted;
752 
753  /* We are at a point were no changed bools are true, so just keep going. */
754  if (!(i1 >= 0 && bitarray_is_set(changed1, i1)) &&
755  !(i2 >= 0 && bitarray_is_set(changed2, i2))) {
756  if (i1 >= 0) {
757  i1--;
758  }
759  if (i2 >= 0) {
760  i2--;
761  }
762  continue;
763  }
764 
765  end1 = i1, end2 = i2;
766 
767  /* Grab all contiguous changed lines */
768  while (i1 >= 0 && bitarray_is_set(changed1, i1)) {
769  i1--;
770  }
771  while (i2 >= 0 && bitarray_is_set(changed2, i2)) {
772  i2--;
773  }
774 
775  start1x = i1+1, start2x = i2+1;
776  added = end2-i2, deleted = end1-i1;
777 
778  if (added == 0) {
779  if (deleted == 1) {
780  tor_snprintf(buf, sizeof(buf), "%id", start1x+1);
781  smartlist_add_linecpy(result, area, buf);
782  } else {
783  tor_snprintf(buf, sizeof(buf), "%i,%id", start1x+1, start1x+deleted);
784  smartlist_add_linecpy(result, area, buf);
785  }
786  } else {
787  int i;
788  if (deleted == 0) {
789  tor_snprintf(buf, sizeof(buf), "%ia", start1x);
790  smartlist_add_linecpy(result, area, buf);
791  } else if (deleted == 1) {
792  tor_snprintf(buf, sizeof(buf), "%ic", start1x+1);
793  smartlist_add_linecpy(result, area, buf);
794  } else {
795  tor_snprintf(buf, sizeof(buf), "%i,%ic", start1x+1, start1x+deleted);
796  smartlist_add_linecpy(result, area, buf);
797  }
798 
799  for (i = start2x; i <= end2; ++i) {
800  cdline_t *line = smartlist_get(cons2, i);
801  if (line_str_eq(line, ".")) {
802  log_warn(LD_CONSDIFF, "Cannot generate consensus diff because "
803  "one of the lines to be added is \".\".");
804  goto error_cleanup;
805  }
806  smartlist_add(result, line);
807  }
808  smartlist_add_linecpy(result, area, ".");
809  }
810  }
811 
812  smartlist_free(cons1);
813  bitarray_free(changed1);
814  bitarray_free(changed2);
815 
816  return result;
817 
818  error_cleanup:
819 
820  smartlist_free(cons1);
821  bitarray_free(changed1);
822  bitarray_free(changed2);
823 
824  smartlist_free(result);
825 
826  return NULL;
827 }
828 
829 /* Helper: Read a base-10 number between 0 and INT32_MAX from <b>s</b> and
830  * store it in <b>num_out</b>. Advance <b>s</b> to the characer immediately
831  * after the number. Return 0 on success, -1 on failure. */
832 static int
833 get_linenum(const char **s, int *num_out)
834 {
835  int ok;
836  char *next;
837  if (!TOR_ISDIGIT(**s)) {
838  return -1;
839  }
840  *num_out = (int) tor_parse_long(*s, 10, 0, INT32_MAX, &ok, &next);
841  if (ok && next) {
842  *s = next;
843  return 0;
844  } else {
845  return -1;
846  }
847 }
848 
856 STATIC smartlist_t *
857 apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff,
858  int diff_starting_line)
859 {
860  int diff_len = smartlist_len(diff);
861  int j = smartlist_len(cons1);
862  smartlist_t *cons2 = smartlist_new();
863 
864  for (int i=diff_starting_line; i<diff_len; ++i) {
865  const cdline_t *diff_cdline = smartlist_get(diff, i);
866  char diff_line[128];
867 
868  if (diff_cdline->len > sizeof(diff_line) - 1) {
869  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
870  "an ed command was far too long");
871  goto error_cleanup;
872  }
873  /* Copy the line to make it nul-terminated. */
874  memcpy(diff_line, diff_cdline->s, diff_cdline->len);
875  diff_line[diff_cdline->len] = 0;
876  const char *ptr = diff_line;
877  int start = 0, end = 0;
878  int had_range = 0;
879  int end_was_eof = 0;
880  if (get_linenum(&ptr, &start) < 0) {
881  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
882  "an ed command was missing a line number.");
883  goto error_cleanup;
884  }
885  if (*ptr == ',') {
886  /* Two-item range */
887  had_range = 1;
888  ++ptr;
889  if (*ptr == '$') {
890  end_was_eof = 1;
891  end = smartlist_len(cons1);
892  ++ptr;
893  } else if (get_linenum(&ptr, &end) < 0) {
894  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
895  "an ed command was missing a range end line number.");
896  goto error_cleanup;
897  }
898  /* Incoherent range. */
899  if (end <= start) {
900  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
901  "an invalid range was found in an ed command.");
902  goto error_cleanup;
903  }
904  } else {
905  /* We'll take <n1> as <n1>,<n1> for simplicity. */
906  end = start;
907  }
908 
909  if (end > j) {
910  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
911  "its commands are not properly sorted in reverse order.");
912  goto error_cleanup;
913  }
914 
915  if (*ptr == '\0') {
916  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
917  "a line with no ed command was found");
918  goto error_cleanup;
919  }
920 
921  if (*(ptr+1) != '\0') {
922  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
923  "an ed command longer than one char was found.");
924  goto error_cleanup;
925  }
926 
927  char action = *ptr;
928 
929  switch (action) {
930  case 'a':
931  case 'c':
932  case 'd':
933  break;
934  default:
935  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
936  "an unrecognised ed command was found.");
937  goto error_cleanup;
938  }
939 
941  if (end_was_eof && action != 'd') {
942  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
943  "it wanted to use $ with a command other than delete");
944  goto error_cleanup;
945  }
946 
947  /* 'a' commands are not allowed to have ranges. */
948  if (had_range && action == 'a') {
949  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
950  "it wanted to add lines after a range.");
951  goto error_cleanup;
952  }
953 
954  /* Add unchanged lines. */
955  for (; j && j > end; --j) {
956  cdline_t *cons_line = smartlist_get(cons1, j-1);
957  smartlist_add(cons2, cons_line);
958  }
959 
960  /* Ignore removed lines. */
961  if (action == 'c' || action == 'd') {
962  while (--j >= start) {
963  /* Skip line */
964  }
965  }
966 
967  /* Add new lines in reverse order, since it will all be reversed at the
968  * end.
969  */
970  if (action == 'a' || action == 'c') {
971  int added_end = i;
972 
973  i++; /* Skip the line with the range and command. */
974  while (i < diff_len) {
975  if (line_str_eq(smartlist_get(diff, i), ".")) {
976  break;
977  }
978  if (++i == diff_len) {
979  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
980  "it has lines to be inserted that don't end with a \".\".");
981  goto error_cleanup;
982  }
983  }
984 
985  int added_i = i-1;
986 
987  /* It would make no sense to add zero new lines. */
988  if (added_i == added_end) {
989  log_warn(LD_CONSDIFF, "Could not apply consensus diff because "
990  "it has an ed command that tries to insert zero lines.");
991  goto error_cleanup;
992  }
993 
994  while (added_i > added_end) {
995  cdline_t *added_line = smartlist_get(diff, added_i--);
996  smartlist_add(cons2, added_line);
997  }
998  }
999  }
1000 
1001  /* Add remaining unchanged lines. */
1002  for (; j > 0; --j) {
1003  cdline_t *cons_line = smartlist_get(cons1, j-1);
1004  smartlist_add(cons2, cons_line);
1005  }
1006 
1007  /* Reverse the whole thing since we did it from the end. */
1008  smartlist_reverse(cons2);
1009  return cons2;
1010 
1011  error_cleanup:
1012 
1013  smartlist_free(cons2);
1014 
1015  return NULL;
1016 }
1017 
1023 smartlist_t *
1025  const smartlist_t *cons2,
1026  const consensus_digest_t *digests1,
1027  const consensus_digest_t *digests2,
1028  memarea_t *area)
1029 {
1030  smartlist_t *ed_diff = gen_ed_diff(cons1, cons2, area);
1031  /* ed diff could not be generated - reason already logged by gen_ed_diff. */
1032  if (!ed_diff) {
1033  goto error_cleanup;
1034  }
1035 
1036  /* See that the script actually produces what we want. */
1037  smartlist_t *ed_cons2 = apply_ed_diff(cons1, ed_diff, 0);
1038  if (!ed_cons2) {
1039  /* LCOV_EXCL_START -- impossible if diff generation is correct */
1040  log_warn(LD_BUG|LD_CONSDIFF, "Refusing to generate consensus diff because "
1041  "the generated ed diff could not be tested to successfully generate "
1042  "the target consensus.");
1043  goto error_cleanup;
1044  /* LCOV_EXCL_STOP */
1045  }
1046 
1047  int cons2_eq = 1;
1048  if (smartlist_len(cons2) == smartlist_len(ed_cons2)) {
1049  SMARTLIST_FOREACH_BEGIN(cons2, const cdline_t *, line1) {
1050  const cdline_t *line2 = smartlist_get(ed_cons2, line1_sl_idx);
1051  if (! lines_eq(line1, line2) ) {
1052  cons2_eq = 0;
1053  break;
1054  }
1055  } SMARTLIST_FOREACH_END(line1);
1056  } else {
1057  cons2_eq = 0;
1058  }
1059  smartlist_free(ed_cons2);
1060  if (!cons2_eq) {
1061  /* LCOV_EXCL_START -- impossible if diff generation is correct. */
1062  log_warn(LD_BUG|LD_CONSDIFF, "Refusing to generate consensus diff because "
1063  "the generated ed diff did not generate the target consensus "
1064  "successfully when tested.");
1065  goto error_cleanup;
1066  /* LCOV_EXCL_STOP */
1067  }
1068 
1069  char cons1_hash_hex[HEX_DIGEST256_LEN+1];
1070  char cons2_hash_hex[HEX_DIGEST256_LEN+1];
1071  base16_encode(cons1_hash_hex, HEX_DIGEST256_LEN+1,
1072  (const char*)digests1->sha3_256, DIGEST256_LEN);
1073  base16_encode(cons2_hash_hex, HEX_DIGEST256_LEN+1,
1074  (const char*)digests2->sha3_256, DIGEST256_LEN);
1075 
1076  /* Create the resulting consensus diff. */
1077  char buf[160];
1078  smartlist_t *result = smartlist_new();
1079  tor_snprintf(buf, sizeof(buf), "%s", ns_diff_version);
1080  smartlist_add_linecpy(result, area, buf);
1081  tor_snprintf(buf, sizeof(buf), "%s %s %s", hash_token,
1082  cons1_hash_hex, cons2_hash_hex);
1083  smartlist_add_linecpy(result, area, buf);
1084  smartlist_add_all(result, ed_diff);
1085  smartlist_free(ed_diff);
1086  return result;
1087 
1088  error_cleanup:
1089 
1090  if (ed_diff) {
1091  /* LCOV_EXCL_START -- ed_diff is NULL except in unreachable cases above */
1092  smartlist_free(ed_diff);
1093  /* LCOV_EXCL_STOP */
1094  }
1095 
1096  return NULL;
1097 }
1098 
1103 int
1105  char *digest1_out,
1106  char *digest2_out)
1107 {
1108  smartlist_t *hash_words = NULL;
1109  const cdline_t *format;
1110  char cons1_hash[DIGEST256_LEN], cons2_hash[DIGEST256_LEN];
1111  char *cons1_hash_hex, *cons2_hash_hex;
1112  if (smartlist_len(diff) < 2) {
1113  log_info(LD_CONSDIFF, "The provided consensus diff is too short.");
1114  goto error_cleanup;
1115  }
1116 
1117  /* Check that it's the format and version we know. */
1118  format = smartlist_get(diff, 0);
1119  if (!line_str_eq(format, ns_diff_version)) {
1120  log_warn(LD_CONSDIFF, "The provided consensus diff format is not known.");
1121  goto error_cleanup;
1122  }
1123 
1124  /* Grab the base16 digests. */
1125  hash_words = smartlist_new();
1126  {
1127  const cdline_t *line2 = smartlist_get(diff, 1);
1128  char *h = tor_memdup_nulterm(line2->s, line2->len);
1129  smartlist_split_string(hash_words, h, " ", 0, 0);
1130  tor_free(h);
1131  }
1132 
1133  /* There have to be three words, the first of which must be hash_token. */
1134  if (smartlist_len(hash_words) != 3 ||
1135  strcmp(smartlist_get(hash_words, 0), hash_token)) {
1136  log_info(LD_CONSDIFF, "The provided consensus diff does not include "
1137  "the necessary digests.");
1138  goto error_cleanup;
1139  }
1140 
1141  /* Expected hashes as found in the consensus diff header. They must be of
1142  * length HEX_DIGEST256_LEN, normally 64 hexadecimal characters.
1143  * If any of the decodings fail, error to make sure that the hashes are
1144  * proper base16-encoded digests.
1145  */
1146  cons1_hash_hex = smartlist_get(hash_words, 1);
1147  cons2_hash_hex = smartlist_get(hash_words, 2);
1148  if (strlen(cons1_hash_hex) != HEX_DIGEST256_LEN ||
1149  strlen(cons2_hash_hex) != HEX_DIGEST256_LEN) {
1150  log_info(LD_CONSDIFF, "The provided consensus diff includes "
1151  "base16-encoded digests of incorrect size.");
1152  goto error_cleanup;
1153  }
1154 
1155  if (base16_decode(cons1_hash, DIGEST256_LEN,
1156  cons1_hash_hex, HEX_DIGEST256_LEN) != DIGEST256_LEN ||
1157  base16_decode(cons2_hash, DIGEST256_LEN,
1158  cons2_hash_hex, HEX_DIGEST256_LEN) != DIGEST256_LEN) {
1159  log_info(LD_CONSDIFF, "The provided consensus diff includes "
1160  "malformed digests.");
1161  goto error_cleanup;
1162  }
1163 
1164  if (digest1_out) {
1165  memcpy(digest1_out, cons1_hash, DIGEST256_LEN);
1166  }
1167  if (digest2_out) {
1168  memcpy(digest2_out, cons2_hash, DIGEST256_LEN);
1169  }
1170 
1171  SMARTLIST_FOREACH(hash_words, char *, cp, tor_free(cp));
1172  smartlist_free(hash_words);
1173  return 0;
1174 
1175  error_cleanup:
1176 
1177  if (hash_words) {
1178  SMARTLIST_FOREACH(hash_words, char *, cp, tor_free(cp));
1179  smartlist_free(hash_words);
1180  }
1181  return 1;
1182 }
1183 
1189 char *
1191  const smartlist_t *diff,
1192  const consensus_digest_t *digests1)
1193 {
1194  smartlist_t *cons2 = NULL;
1195  char *cons2_str = NULL;
1196  char e_cons1_hash[DIGEST256_LEN];
1197  char e_cons2_hash[DIGEST256_LEN];
1198 
1199  if (consdiff_get_digests(diff, e_cons1_hash, e_cons2_hash) != 0) {
1200  goto error_cleanup;
1201  }
1202 
1203  /* See that the consensus that was given to us matches its hash. */
1204  if (!consensus_digest_eq(digests1->sha3_256,
1205  (const uint8_t*)e_cons1_hash)) {
1206  char hex_digest1[HEX_DIGEST256_LEN+1];
1207  char e_hex_digest1[HEX_DIGEST256_LEN+1];
1208  log_warn(LD_CONSDIFF, "Refusing to apply consensus diff because "
1209  "the base consensus doesn't match the digest as found in "
1210  "the consensus diff header.");
1211  base16_encode(hex_digest1, HEX_DIGEST256_LEN+1,
1212  (const char *)digests1->sha3_256, DIGEST256_LEN);
1213  base16_encode(e_hex_digest1, HEX_DIGEST256_LEN+1,
1214  e_cons1_hash, DIGEST256_LEN);
1215  log_warn(LD_CONSDIFF, "Expected: %s; found: %s",
1216  hex_digest1, e_hex_digest1);
1217  goto error_cleanup;
1218  }
1219 
1220  /* Grab the ed diff and calculate the resulting consensus. */
1221  /* Skip the first two lines. */
1222  cons2 = apply_ed_diff(cons1, diff, 2);
1223 
1224  /* ed diff could not be applied - reason already logged by apply_ed_diff. */
1225  if (!cons2) {
1226  goto error_cleanup;
1227  }
1228 
1229  cons2_str = consensus_join_lines(cons2);
1230 
1231  consensus_digest_t cons2_digests;
1232  if (consensus_compute_digest(cons2_str, strlen(cons2_str),
1233  &cons2_digests) < 0) {
1234  /* LCOV_EXCL_START -- digest can't fail */
1235  log_warn(LD_CONSDIFF, "Could not compute digests of the consensus "
1236  "resulting from applying a consensus diff.");
1237  goto error_cleanup;
1238  /* LCOV_EXCL_STOP */
1239  }
1240 
1241  /* See that the resulting consensus matches its hash. */
1242  if (!consensus_digest_eq(cons2_digests.sha3_256,
1243  (const uint8_t*)e_cons2_hash)) {
1244  log_warn(LD_CONSDIFF, "Refusing to apply consensus diff because "
1245  "the resulting consensus doesn't match the digest as found in "
1246  "the consensus diff header.");
1247  char hex_digest2[HEX_DIGEST256_LEN+1];
1248  char e_hex_digest2[HEX_DIGEST256_LEN+1];
1249  base16_encode(hex_digest2, HEX_DIGEST256_LEN+1,
1250  (const char *)cons2_digests.sha3_256, DIGEST256_LEN);
1251  base16_encode(e_hex_digest2, HEX_DIGEST256_LEN+1,
1252  e_cons2_hash, DIGEST256_LEN);
1253  log_warn(LD_CONSDIFF, "Expected: %s; found: %s",
1254  hex_digest2, e_hex_digest2);
1255  goto error_cleanup;
1256  }
1257 
1258  goto done;
1259 
1260  error_cleanup:
1261  tor_free(cons2_str); /* Sets it to NULL */
1262 
1263  done:
1264  if (cons2) {
1265  smartlist_free(cons2);
1266  }
1267 
1268  return cons2_str;
1269 }
1270 
1272 #define CONSENSUS_LINE_MAX_LEN (1<<20)
1273 
1286 STATIC int
1288  const char *s, size_t len,
1289  memarea_t *area)
1290 {
1291  const char *end_of_str = s + len;
1292 
1293  while (s < end_of_str) {
1294  const char *eol = memchr(s, '\n', end_of_str - s);
1295  if (!eol) {
1296  /* File doesn't end with newline. */
1297  return -1;
1298  }
1299  if (eol - s > CONSENSUS_LINE_MAX_LEN) {
1300  /* Line is far too long. */
1301  return -1;
1302  }
1303  cdline_t *line = memarea_alloc(area, sizeof(cdline_t));
1304  line->s = s;
1305  line->len = (uint32_t)(eol - s);
1306  smartlist_add(out, line);
1307  s = eol+1;
1308  }
1309  return 0;
1310 }
1311 
1317 static char *
1319 {
1320  size_t n = 0;
1321  SMARTLIST_FOREACH(inp, const cdline_t *, cdline, n += cdline->len + 1);
1322  n += 1;
1323  char *result = tor_malloc(n);
1324  char *out = result;
1325  SMARTLIST_FOREACH_BEGIN(inp, const cdline_t *, cdline) {
1326  memcpy(out, cdline->s, cdline->len);
1327  out += cdline->len;
1328  *out++ = '\n';
1329  } SMARTLIST_FOREACH_END(cdline);
1330  *out++ = '\0';
1331  tor_assert(out == result+n);
1332  return result;
1333 }
1334 
1338 char *
1339 consensus_diff_generate(const char *cons1, size_t cons1len,
1340  const char *cons2, size_t cons2len)
1341 {
1342  consensus_digest_t d1, d2;
1343  smartlist_t *lines1 = NULL, *lines2 = NULL, *result_lines = NULL;
1344  int r1, r2;
1345  char *result = NULL;
1346 
1347  r1 = consensus_compute_digest_as_signed(cons1, cons1len, &d1);
1348  r2 = consensus_compute_digest(cons2, cons2len, &d2);
1349  if (BUG(r1 < 0 || r2 < 0))
1350  return NULL; // LCOV_EXCL_LINE
1351 
1352  memarea_t *area = memarea_new();
1353  lines1 = smartlist_new();
1354  lines2 = smartlist_new();
1355  if (consensus_split_lines(lines1, cons1, cons1len, area) < 0)
1356  goto done;
1357  if (consensus_split_lines(lines2, cons2, cons2len, area) < 0)
1358  goto done;
1359 
1360  result_lines = consdiff_gen_diff(lines1, lines2, &d1, &d2, area);
1361 
1362  done:
1363  if (result_lines) {
1364  result = consensus_join_lines(result_lines);
1365  smartlist_free(result_lines);
1366  }
1367 
1368  memarea_drop_all(area);
1369  smartlist_free(lines1);
1370  smartlist_free(lines2);
1371 
1372  return result;
1373 }
1374 
1378 char *
1379 consensus_diff_apply(const char *consensus,
1380  size_t consensus_len,
1381  const char *diff,
1382  size_t diff_len)
1383 {
1384  consensus_digest_t d1;
1385  smartlist_t *lines1 = NULL, *lines2 = NULL;
1386  int r1;
1387  char *result = NULL;
1388  memarea_t *area = memarea_new();
1389 
1390  r1 = consensus_compute_digest_as_signed(consensus, consensus_len, &d1);
1391  if (BUG(r1 < 0))
1392  goto done;
1393 
1394  lines1 = smartlist_new();
1395  lines2 = smartlist_new();
1396  if (consensus_split_lines(lines1, consensus, consensus_len, area) < 0)
1397  goto done;
1398  if (consensus_split_lines(lines2, diff, diff_len, area) < 0)
1399  goto done;
1400 
1401  result = consdiff_apply_diff(lines1, lines2, &d1);
1402 
1403  done:
1404  smartlist_free(lines1);
1405  smartlist_free(lines2);
1406  memarea_drop_all(area);
1407 
1408  return result;
1409 }
1410 
1413 int
1414 looks_like_a_consensus_diff(const char *document, size_t len)
1415 {
1416  return (len >= strlen(ns_diff_version) &&
1417  fast_memeq(document, ns_diff_version, strlen(ns_diff_version)));
1418 }
STATIC int is_valid_router_entry(const cdline_t *line)
Definition: consdiff.c:435
STATIC int smartlist_slice_string_pos(const smartlist_slice_t *slice, const cdline_t *string)
Definition: consdiff.c:245
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
unsigned int bitarray_t
Definition: bitarray.h:30
STATIC void set_changed(bitarray_t *changed1, bitarray_t *changed2, const smartlist_slice_t *slice1, const smartlist_slice_t *slice2)
Definition: consdiff.c:264
MOCK_IMPL(STATIC int, consensus_compute_digest,(const char *cons, size_t len, consensus_digest_t *digest_out))
Definition: consdiff.c:103
STATIC void calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, bitarray_t *changed1, bitarray_t *changed2)
Definition: consdiff.c:327
static char * consensus_join_lines(const smartlist_t *inp)
Definition: consdiff.c:1318
char * consdiff_apply_diff(const smartlist_t *cons1, const smartlist_t *diff, const consensus_digest_t *digests1)
Definition: consdiff.c:1190
STATIC smartlist_t * apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, int diff_starting_line)
Definition: consdiff.c:857
void smartlist_add(smartlist_t *sl, void *element)
#define HEX_DIGEST256_LEN
Definition: crypto_digest.h:37
char * consensus_diff_generate(const char *cons1, size_t cons1len, const char *cons2, size_t cons2len)
Definition: consdiff.c:1339
#define CONSENSUS_LINE_MAX_LEN
Definition: consdiff.c:1272
STATIC int next_router(const smartlist_t *cons, int cur)
Definition: consdiff.c:449
#define tor_free(p)
Definition: malloc.h:52
#define ROUTER_ID_ITERATOR_INIT
Definition: consdiff.c:536
#define X
Definition: binascii.c:356
memarea_t * memarea_new(void)
Definition: memarea.c:153
static void bitarray_set(bitarray_t *b, int bit)
Definition: bitarray.h:68
STATIC void trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2)
Definition: consdiff.c:213
#define DIGEST256_LEN
Definition: digest_sizes.h:23
void * memarea_memdup(memarea_t *area, const void *s, size_t n)
Definition: memarea.c:257
STATIC int get_id_hash(const cdline_t *line, cdline_t *hash_out)
Definition: consdiff.c:395
tor_assert(buffer)
Master header file for Tor-specific functionality.
STATIC smartlist_t * gen_ed_diff(const smartlist_t *cons1_orig, const smartlist_t *cons2, memarea_t *area)
Definition: consdiff.c:623
void smartlist_reverse(smartlist_t *sl)
Definition: smartlist.c:59
int router_get_networkstatus_v3_sha3_as_signed(uint8_t *digest_out, const char *s, size_t len)
Definition: ns_parse.c:169
Header for memarea.c.
int consdiff_get_digests(const smartlist_t *diff, char *digest1_out, char *digest2_out)
Definition: consdiff.c:1104
static bitarray_t * bitarray_init_zero(unsigned int n_bits)
Definition: bitarray.h:33
void base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:478
STATIC int consensus_split_lines(smartlist_t *out, const char *s, size_t len, memarea_t *area)
Definition: consdiff.c:1287
struct router_id_iterator_t router_id_iterator_t
void smartlist_del(smartlist_t *sl, int idx)
void * memarea_alloc(memarea_t *area, size_t sz)
Definition: memarea.c:209
static int find_next_router_line(const smartlist_t *cons, const char *consname, int *idxp, router_id_iterator_t *iter)
Definition: consdiff.c:547
STATIC smartlist_slice_t * smartlist_slice(const smartlist_t *list, int start, int end)
Definition: consdiff.c:140
STATIC int line_str_eq(const cdline_t *a, const char *b)
Definition: consdiff.c:60
Header file for ns_parse.c.
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
#define SMARTLIST_FOREACH(sl, type, var, cmd)
#define START_OF_SIGNATURES_SECTION
Definition: consdiff.c:568
STATIC int base64cmp(const cdline_t *hash1, const cdline_t *hash2)
Definition: consdiff.c:472
STATIC int * lcs_lengths(const smartlist_slice_t *slice1, const smartlist_slice_t *slice2, int direction)
Definition: consdiff.c:165
void smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
#define LD_CONSDIFF
Definition: log.h:109
char * consensus_diff_apply(const char *consensus, size_t consensus_len, const char *diff, size_t diff_len)
Definition: consdiff.c:1379
long tor_parse_long(const char *s, int base, long min, long max, int *ok, char **next)
Definition: parse_int.c:56
int base16_decode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:506
#define MAX(a, b)
Definition: cmp.h:22
STATIC int lines_eq(const cdline_t *a, const cdline_t *b)
Definition: consdiff.c:53
int crypto_digest256(char *digest, const char *m, size_t len, digest_algorithm_t algorithm)
int looks_like_a_consensus_diff(const char *document, size_t len)
Definition: consdiff.c:1414
STATIC void smartlist_add_linecpy(smartlist_t *lst, memarea_t *area, const char *s)
Definition: consdiff.c:94
static unsigned int bitarray_is_set(bitarray_t *b, int bit)
Definition: bitarray.h:81
static cdline_t * preprocess_consensus(memarea_t *area, smartlist_t *cons)
Definition: consdiff.c:579
smartlist_t * consdiff_gen_diff(const smartlist_t *cons1, const smartlist_t *cons2, const consensus_digest_t *digests1, const consensus_digest_t *digests2, memarea_t *area)
Definition: consdiff.c:1024
#define LD_BUG
Definition: log.h:84
static cdline_t * cdline_linecpy(memarea_t *area, const char *s)
Definition: consdiff.c:81
int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, int flags, int max)
static int line_starts_with_str(const cdline_t *a, const char *b)
Definition: consdiff.c:71