Merge branch 'microdesc'

6 files changed, 202 insertions, 5 deletions

diff --git a/src/common/container.c b/src/common/container.c
index 12ac2527e..4fb94d3f7 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -459,6 +459,42 @@ smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
         (int (*)(const void *,const void*))compare);
 }
 
+/** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>,
+ * return the most frequent member in the list.  Break ties in favor of
+ * later elements.  If the list is empty, return NULL.
+ */
+void *
+smartlist_get_most_frequent(const smartlist_t *sl,
+                            int (*compare)(const void **a, const void **b))
+{
+  const void *most_frequent = NULL;
+  int most_frequent_count = 0;
+
+  const void **cur = NULL;
+  int i, count=0;
+
+  if (!sl->num_used)
+    return NULL;
+  for (i = 0; i < sl->num_used; ++i) {
+    const void *item = sl->list[i];
+    if (cur && 0 == compare(cur, &item)) {
+      ++count;
+    } else {
+      if (cur && count >= most_frequent_count) {
+        most_frequent = *cur;
+        most_frequent_count = count;
+      }
+      cur = &item;
+      count = 1;
+    }
+  }
+  if (cur && count >= most_frequent_count) {
+    most_frequent = *cur;
+    most_frequent_count = count;
+  }
+  return (void*)most_frequent;
+}
+
 /** Given a sorted smartlist <b>sl</b> and the comparison function used to
  * sort it, remove all duplicate members.  If free_fn is provided, calls
  * free_fn on each duplicate.  Otherwise, just removes them.  Preserves order.
@@ -550,6 +586,13 @@ smartlist_sort_strings(smartlist_t *sl)
   smartlist_sort(sl, _compare_string_ptrs);
 }
 
+/** Return the most frequent string in the sorted list <b>sl</b> */
+char *
+smartlist_get_most_frequent_string(smartlist_t *sl)
+{
+  return smartlist_get_most_frequent(sl, _compare_string_ptrs);
+}
+
 /** Remove duplicate strings from a sorted list, and free them with tor_free().
  */
 void
@@ -681,6 +724,37 @@ smartlist_uniq_digests(smartlist_t *sl)
   smartlist_uniq(sl, _compare_digests, _tor_free);
 }
 
+/** Helper: compare two DIGEST256_LEN digests. */
+static int
+_compare_digests256(const void **_a, const void **_b)
+{
+  return memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
+}
+
+/** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
+void
+smartlist_sort_digests256(smartlist_t *sl)
+{
+  smartlist_sort(sl, _compare_digests256);
+}
+
+/** Return the most frequent member of the sorted list of DIGEST256_LEN
+ * digests in <b>sl</b> */
+char *
+smartlist_get_most_frequent_digest256(smartlist_t *sl)
+{
+  return smartlist_get_most_frequent(sl, _compare_digests256);
+}
+
+/** Remove duplicate 256-bit digests from a sorted list, and free them with
+ * tor_free().
+ */
+void
+smartlist_uniq_digests256(smartlist_t *sl)
+{
+  smartlist_uniq(sl, _compare_digests256, _tor_free);
+}
+
 /** Helper: Declare an entry type and a map type to implement a mapping using
  * ht.h.  The map type will be called <b>maptype</b>.  The key part of each
  * entry is declared using the C declaration <b>keydecl</b>.  All functions
diff --git a/src/common/container.h b/src/common/container.h
index 4495a7a27..41c0c6870 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -93,13 +93,22 @@ void smartlist_del_keeporder(smartlist_t *sl, int idx);
 void smartlist_insert(smartlist_t *sl, int idx, void *val);
 void smartlist_sort(smartlist_t *sl,
                     int (*compare)(const void **a, const void **b));
+void *smartlist_get_most_frequent(const smartlist_t *sl,
+                    int (*compare)(const void **a, const void **b));
 void smartlist_uniq(smartlist_t *sl,
                     int (*compare)(const void **a, const void **b),
                     void (*free_fn)(void *elt));
+
 void smartlist_sort_strings(smartlist_t *sl);
 void smartlist_sort_digests(smartlist_t *sl);
+void smartlist_sort_digests256(smartlist_t *sl);
+
+char *smartlist_get_most_frequent_string(smartlist_t *sl);
+char *smartlist_get_most_frequent_digest256(smartlist_t *sl);
+
 void smartlist_uniq_strings(smartlist_t *sl);
 void smartlist_uniq_digests(smartlist_t *sl);
+void smartlist_uniq_digests256(smartlist_t *sl);
 void *smartlist_bsearch(smartlist_t *sl, const void *key,
                         int (*compare)(const void *key, const void **member))
   ATTR_PURE;
diff --git a/src/common/crypto.c b/src/common/crypto.c
index 581d1ba5a..4ea449289 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -1448,6 +1448,52 @@ crypto_digest256(char *digest, const char *m, size_t len,
   return (SHA256((const unsigned char*)m,len,(unsigned char*)digest) == NULL);
 }
 
+/** Set the digests_t in <b>ds_out</b> to contain every digest on the
+ * <b>len</b> bytes in <b>m</b> that we know how to compute.  Return 0 on
+ * success, -1 on failure. */
+int
+crypto_digest_all(digests_t *ds_out, const char *m, size_t len)
+{
+  digest_algorithm_t i;
+  tor_assert(ds_out);
+  memset(ds_out, 0, sizeof(*ds_out));
+  if (crypto_digest(ds_out->d[DIGEST_SHA1], m, len) < 0)
+    return -1;
+  for (i = DIGEST_SHA256; i < N_DIGEST_ALGORITHMS; ++i) {
+    if (crypto_digest256(ds_out->d[i], m, len, i) < 0)
+      return -1;
+  }
+  return 0;
+}
+
+/** Return the name of an algorithm, as used in directory documents. */
+const char *
+crypto_digest_algorithm_get_name(digest_algorithm_t alg)
+{
+  switch (alg) {
+    case DIGEST_SHA1:
+      return "sha1";
+    case DIGEST_SHA256:
+      return "sha256";
+    default:
+      tor_fragile_assert();
+      return "??unknown_digest??";
+  }
+}
+
+/** Given the name of a digest algorithm, return its integer value, or -1 if
+ * the name is not recognized. */
+int
+crypto_digest_algorithm_parse_name(const char *name)
+{
+  if (!strcmp(name, "sha1"))
+    return DIGEST_SHA1;
+  else if (!strcmp(name, "sha256"))
+    return DIGEST_SHA256;
+  else
+    return -1;
+}
+
 /** Intermediate information about the digest of a stream of data. */
 struct crypto_digest_env_t {
   union {
@@ -2274,6 +2320,44 @@ digest_from_base64(char *digest, const char *d64)
 #endif
 }
 
+/** Base-64 encode DIGEST256_LINE bytes from <b>digest</b>, remove the
+ * trailing = and newline characters, and store the nul-terminated result in
+ * the first BASE64_DIGEST256_LEN+1 bytes of <b>d64</b>.  */
+int
+digest256_to_base64(char *d64, const char *digest)
+{
+  char buf[256];
+  base64_encode(buf, sizeof(buf), digest, DIGEST256_LEN);
+  buf[BASE64_DIGEST256_LEN] = '\0';
+  memcpy(d64, buf, BASE64_DIGEST256_LEN+1);
+  return 0;
+}
+
+/** Given a base-64 encoded, nul-terminated digest in <b>d64</b> (without
+ * trailing newline or = characters), decode it and store the result in the
+ * first DIGEST256_LEN bytes at <b>digest</b>. */
+int
+digest256_from_base64(char *digest, const char *d64)
+{
+#ifdef USE_OPENSSL_BASE64
+  char buf_in[BASE64_DIGEST256_LEN+3];
+  char buf[256];
+  if (strlen(d64) != BASE64_DIGEST256_LEN)
+    return -1;
+  memcpy(buf_in, d64, BASE64_DIGEST256_LEN);
+  memcpy(buf_in+BASE64_DIGEST256_LEN, "=\n\0", 3);
+  if (base64_decode(buf, sizeof(buf), buf_in, strlen(buf_in)) != DIGEST256_LEN)
+    return -1;
+  memcpy(digest, buf, DIGEST256_LEN);
+  return 0;
+#else
+  if (base64_decode(digest, DIGEST256_LEN, d64, strlen(d64)) == DIGEST256_LEN)
+    return 0;
+  else
+    return -1;
+#endif
+}
+
 /** Implements base32 encoding as in rfc3548.  Limitation: Requires
  * that srclen*8 is a multiple of 5.
  */
diff --git a/src/common/crypto.h b/src/common/crypto.h
index f0958a807..c0a452625 100644
--- a/src/common/crypto.h
+++ b/src/common/crypto.h
@@ -58,9 +58,22 @@
 #define HEX_DIGEST256_LEN 64
 
 typedef enum {
-  DIGEST_SHA1,
-  DIGEST_SHA256,
+  DIGEST_SHA1 = 0,
+  DIGEST_SHA256 = 1,
 } digest_algorithm_t;
+#define  N_DIGEST_ALGORITHMS (DIGEST_SHA256+1)
+
+/** A set of all the digests we know how to compute, taken on a single
+ * string.  Any digests that are shorter than 256 bits are right-padded
+ * with 0 bits.
+ *
+ * Note that this representation wastes 12 bytes for the SHA1 case, so
+ * don't use it for anything where we need to allocate a whole bunch at
+ * once.
+ **/
+typedef struct {
+  char d[N_DIGEST_ALGORITHMS][DIGEST256_LEN];
+} digests_t;
 
 typedef struct crypto_pk_env_t crypto_pk_env_t;
 typedef struct crypto_cipher_env_t crypto_cipher_env_t;
@@ -158,10 +171,13 @@ int crypto_cipher_decrypt_with_iv(crypto_cipher_env_t *env,
                                   char *to, size_t tolen,
                                   const char *from, size_t fromlen);
 
-/* SHA-1 */
+/* SHA-1 and other digests. */
 int crypto_digest(char *digest, const char *m, size_t len);
 int crypto_digest256(char *digest, const char *m, size_t len,
                      digest_algorithm_t algorithm);
+int crypto_digest_all(digests_t *ds_out, const char *m, size_t len);
+const char *crypto_digest_algorithm_get_name(digest_algorithm_t alg);
+int crypto_digest_algorithm_parse_name(const char *name);
 crypto_digest_env_t *crypto_new_digest_env(void);
 crypto_digest_env_t *crypto_new_digest256_env(digest_algorithm_t algorithm);
 void crypto_free_digest_env(crypto_digest_env_t *digest);
@@ -211,6 +227,8 @@ int base32_decode(char *dest, size_t destlen, const char *src, size_t srclen);
 
 int digest_to_base64(char *d64, const char *digest);
 int digest_from_base64(char *digest, const char *d64);
+int digest256_to_base64(char *d64, const char *digest);
+int digest256_from_base64(char *digest, const char *d64);
 
 /** Length of RFC2440-style S2K specifier: the first 8 bytes are a salt, the
  * 9th describes how much iteration to do. */
diff --git a/src/common/util.c b/src/common/util.c
index 8f10d2175..989efd958 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -684,6 +684,13 @@ tor_digest_is_zero(const char *digest)
   return tor_mem_is_zero(digest, DIGEST_LEN);
 }
 
+/** Return true iff the DIGEST256_LEN bytes in digest are all zero. */
+int
+tor_digest256_is_zero(const char *digest)
+{
+  return tor_mem_is_zero(digest, DIGEST256_LEN);
+}
+
 /* Helper: common code to check whether the result of a strtol or strtoul or
  * strtoll is correct. */
 #define CHECK_STRTOX_RESULT()                           \
@@ -1729,7 +1736,8 @@ write_str_to_file(const char *fname, const char *str, int bin)
 struct open_file_t {
   char *tempname; /**< Name of the temporary file. */
   char *filename; /**< Name of the original file. */
-  int rename_on_close; /**< Are we using the temporary file or not? */
+  unsigned rename_on_close:1; /**< Are we using the temporary file or not? */
+  unsigned binary:1; /**< Did we open in binary mode? */
   int fd; /**< fd for the open file. */
   FILE *stdio_file; /**< stdio wrapper for <b>fd</b>. */
 };
@@ -1785,6 +1793,8 @@ start_writing_to_file(const char *fname, int open_flags, int mode,
     open_flags &= ~O_EXCL;
     new_file->rename_on_close = 1;
   }
+  if (open_flags & O_BINARY)
+    new_file->binary = 1;
 
   if ((new_file->fd = open(open_name, open_flags, mode)) < 0) {
     log(LOG_WARN, LD_FS, "Couldn't open \"%s\" (%s) for writing: %s",
@@ -1823,7 +1833,8 @@ fdopen_file(open_file_t *file_data)
   if (file_data->stdio_file)
     return file_data->stdio_file;
   tor_assert(file_data->fd >= 0);
-  if (!(file_data->stdio_file = fdopen(file_data->fd, "a"))) {
+  if (!(file_data->stdio_file = fdopen(file_data->fd,
+                                       file_data->binary?"ab":"a"))) {
     log_warn(LD_FS, "Couldn't fdopen \"%s\" [%d]: %s", file_data->filename,
              file_data->fd, strerror(errno));
   }
diff --git a/src/common/util.h b/src/common/util.h
index 28ea8a048..85234f515 100644
--- a/src/common/util.h
+++ b/src/common/util.h
@@ -195,6 +195,7 @@ const char *find_whitespace(const char *s) ATTR_PURE;
 const char *find_whitespace_eos(const char *s, const char *eos) ATTR_PURE;
 int tor_mem_is_zero(const char *mem, size_t len) ATTR_PURE;
 int tor_digest_is_zero(const char *digest) ATTR_PURE;
+int tor_digest256_is_zero(const char *digest) ATTR_PURE;
 char *esc_for_log(const char *string) ATTR_MALLOC;
 const char *escaped(const char *string);
 struct smartlist_t;