Merge branch 'ahf_prop278_21662_squashed'

32 files changed, 2469 insertions, 416 deletions

diff --git a/Makefile.am b/Makefile.am
index aeac0b85c4..be1dc7f7ef 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -16,7 +16,7 @@ noinst_PROGRAMS=
 DISTCLEANFILES=
 bin_SCRIPTS=
 AM_CPPFLAGS=
-AM_CFLAGS=@TOR_SYSTEMD_CFLAGS@ @CFLAGS_BUGTRAP@
+AM_CFLAGS=@TOR_SYSTEMD_CFLAGS@ @CFLAGS_BUGTRAP@ @TOR_LZMA_CFLAGS@ @TOR_ZSTD_CFLAGS@
 SHELL=@SHELL@
 
 if COVERAGE_ENABLED
diff --git a/configure.ac b/configure.ac
index 0d4fa9838b..c7960fa4ed 100644
--- a/configure.ac
+++ b/configure.ac
@@ -732,6 +732,70 @@ else
 fi
 AC_SUBST(TOR_ZLIB_LIBS)
 
+dnl ------------------------------------------------------
+dnl Where we do we find lzma?
+
+AC_ARG_ENABLE(lzma,
+      AS_HELP_STRING(--enable-lzma, [enable support for the Zstandard compression scheme.]),
+      [case "${enableval}" in
+        "yes") lzma=true ;;
+        "no")  lzma=false ;;
+        * ) AC_MSG_ERROR(bad value for --enable-lzma) ;;
+      esac], [lzma=auto])
+
+if test "x$enable_lzma" = "xno"; then
+    have_lzma=no;
+else
+    PKG_CHECK_MODULES([LZMA],
+                      [liblzma],
+                      have_lzma=yes,
+                      have_lzma=no)
+
+    if test "x$have_lzma" = "xno" ; then
+        AC_MSG_WARN([Unable to find liblzma.])
+    fi
+fi
+
+if test "x$have_lzma" = "xyes"; then
+    AC_DEFINE(HAVE_LZMA,1,[Have LZMA])
+    TOR_LZMA_CFLAGS="${LZMA_CFLAGS}"
+    TOR_LZMA_LIBS="${LZMA_LIBS}"
+fi
+AC_SUBST(TOR_LZMA_CFLAGS)
+AC_SUBST(TOR_LZMA_LIBS)
+
+dnl ------------------------------------------------------
+dnl Where we do we find zstd?
+
+AC_ARG_ENABLE(zstd,
+      AS_HELP_STRING(--enable-zstd, [enable support for the Zstandard compression scheme.]),
+      [case "${enableval}" in
+        "yes") zstd=true ;;
+        "no")  zstd=false ;;
+        * ) AC_MSG_ERROR(bad value for --enable-zstd) ;;
+      esac], [zstd=auto])
+
+if test "x$enable_zstd" = "xno"; then
+    have_zstd=no;
+else
+    PKG_CHECK_MODULES([ZSTD],
+                      [libzstd],
+                      have_zstd=yes,
+                      have_zstd=no)
+
+    if test "x$have_zstd" = "xno" ; then
+        AC_MSG_WARN([Unable to find libzstd.])
+    fi
+fi
+
+if test "x$have_zstd" = "xyes"; then
+    AC_DEFINE(HAVE_ZSTD,1,[Have Zstd])
+    TOR_ZSTD_CFLAGS="${ZSTD_CFLAGS}"
+    TOR_ZSTD_LIBS="${ZSTD_LIBS}"
+fi
+AC_SUBST(TOR_ZSTD_CFLAGS)
+AC_SUBST(TOR_ZSTD_LIBS)
+
 dnl ----------------------------------------------------------------------
 dnl Check if libcap is available for capabilities.
 
diff --git a/src/common/Makefile.nmake b/src/common/Makefile.nmake
index b8c5dd4fea..a1c819fffa 100644
--- a/src/common/Makefile.nmake
+++ b/src/common/Makefile.nmake
@@ -7,8 +7,8 @@ LIBOR_OBJECTS = address.obj backtrace.obj compat.obj container.obj di_ops.obj \
 	log.obj memarea.obj mempool.obj procmon.obj sandbox.obj util.obj \
 	util_codedigest.obj
 
-LIBOR_CRYPTO_OBJECTS = aes.obj crypto.obj crypto_format.obj torgzip.obj tortls.obj \
-	crypto_curve25519.obj curve25519-donna.obj
+LIBOR_CRYPTO_OBJECTS = aes.obj crypto.obj crypto_format.obj compress.obj compress_zlib.obj \
+	tortls.obj crypto_curve25519.obj curve25519-donna.obj
 
 LIBOR_EVENT_OBJECTS = compat_libevent.obj
 
diff --git a/src/common/compress.c b/src/common/compress.c
new file mode 100644
index 0000000000..38b8184573
--- /dev/null
+++ b/src/common/compress.c
@@ -0,0 +1,377 @@
+/* Copyright (c) 2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2017, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file compress.c
+ * \brief Common compression API.
+ **/
+
+#include "orconfig.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+#include "torint.h"
+
+#ifdef HAVE_NETINET_IN_H
+#include <netinet/in.h>
+#endif
+
+#include "util.h"
+#include "torlog.h"
+#include "compress.h"
+#include "compress_lzma.h"
+#include "compress_zlib.h"
+#include "compress_zstd.h"
+
+/** @{ */
+/* These macros define the maximum allowable compression factor.  Anything of
+ * size greater than CHECK_FOR_COMPRESSION_BOMB_AFTER is not allowed to
+ * have an uncompression factor (uncompressed size:compressed size ratio) of
+ * any greater than MAX_UNCOMPRESSION_FACTOR.
+ *
+ * Picking a value for MAX_UNCOMPRESSION_FACTOR is a trade-off: we want it to
+ * be small to limit the attack multiplier, but we also want it to be large
+ * enough so that no legitimate document --even ones we might invent in the
+ * future -- ever compresses by a factor of greater than
+ * MAX_UNCOMPRESSION_FACTOR. Within those parameters, there's a reasonably
+ * large range of possible values. IMO, anything over 8 is probably safe; IMO
+ * anything under 50 is probably sufficient.
+ */
+#define MAX_UNCOMPRESSION_FACTOR 25
+#define CHECK_FOR_COMPRESSION_BOMB_AFTER (1024*64)
+/** @} */
+
+/** Return true if uncompressing an input of size <b>in_size</b> to an input of
+ * size at least <b>size_out</b> looks like a compression bomb. */
+int
+tor_compress_is_compression_bomb(size_t size_in, size_t size_out)
+{
+  if (size_in == 0 || size_out < CHECK_FOR_COMPRESSION_BOMB_AFTER)
+    return 0;
+
+  return (size_out / size_in > MAX_UNCOMPRESSION_FACTOR);
+}
+
+/** Given <b>in_len</b> bytes at <b>in</b>, compress them into a newly
+ * allocated buffer, using the method described in <b>method</b>.  Store the
+ * compressed string in *<b>out</b>, and its length in *<b>out_len</b>.
+ * Return 0 on success, -1 on failure.
+ */
+int
+tor_compress(char **out, size_t *out_len,
+             const char *in, size_t in_len,
+             compress_method_t method)
+{
+  switch (method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD:
+      return tor_zlib_compress(out, out_len, in, in_len, method);
+    case LZMA_METHOD:
+      return tor_lzma_compress(out, out_len, in, in_len, method);
+    case ZSTD_METHOD:
+      return tor_zstd_compress(out, out_len, in, in_len, method);
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+    default:
+      return -1;
+  }
+}
+
+/** Given zero or more zlib-compressed or gzip-compressed strings of
+ * total length
+ * <b>in_len</b> bytes at <b>in</b>, uncompress them into a newly allocated
+ * buffer, using the method described in <b>method</b>.  Store the uncompressed
+ * string in *<b>out</b>, and its length in *<b>out_len</b>.  Return 0 on
+ * success, -1 on failure.
+ *
+ * If <b>complete_only</b> is true, we consider a truncated input as a
+ * failure; otherwise we decompress as much as we can.  Warn about truncated
+ * or corrupt inputs at <b>protocol_warn_level</b>.
+ */
+int
+tor_uncompress(char **out, size_t *out_len,
+               const char *in, size_t in_len,
+               compress_method_t method,
+               int complete_only,
+               int protocol_warn_level)
+{
+  switch (method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD:
+      return tor_zlib_uncompress(out, out_len, in, in_len,
+                                 method,
+                                 complete_only,
+                                 protocol_warn_level);
+    case LZMA_METHOD:
+      return tor_lzma_uncompress(out, out_len, in, in_len,
+                                 method,
+                                 complete_only,
+                                 protocol_warn_level);
+    case ZSTD_METHOD:
+      return tor_zstd_uncompress(out, out_len, in, in_len,
+                                 method,
+                                 complete_only,
+                                 protocol_warn_level);
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+    default:
+      return -1;
+  }
+}
+
+/** Try to tell whether the <b>in_len</b>-byte string in <b>in</b> is likely
+ * to be compressed or not.  If it is, return the likeliest compression method.
+ * Otherwise, return UNKNOWN_METHOD.
+ */
+compress_method_t
+detect_compression_method(const char *in, size_t in_len)
+{
+  if (in_len > 2 && fast_memeq(in, "\x1f\x8b", 2)) {
+    return GZIP_METHOD;
+  } else if (in_len > 2 && (in[0] & 0x0f) == 8 &&
+             (ntohs(get_uint16(in)) % 31) == 0) {
+    return ZLIB_METHOD;
+  } else if (in_len > 3 &&
+             fast_memeq(in, "\x5d\x00\x00\x00", 4)) {
+    return LZMA_METHOD;
+  } else if (in_len > 3 &&
+             fast_memeq(in, "\x28\xb5\x2f\xfd", 4)) {
+    return ZSTD_METHOD;
+  } else {
+    return UNKNOWN_METHOD;
+  }
+}
+
+/** Return 1 if a given <b>method</b> is supported; otherwise 0. */
+int
+tor_compress_supports_method(compress_method_t method)
+{
+  switch (method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD:
+      return tor_zlib_method_supported();
+    case LZMA_METHOD:
+      return tor_lzma_method_supported();
+    case ZSTD_METHOD:
+      return tor_zstd_method_supported();
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+    default:
+      return 0;
+  }
+}
+
+/** Return a string representation of the version of the library providing the
+ * compression method given in <b>method</b>. Returns NULL if <b>method</b> is
+ * unknown or unsupported. */
+const char *
+tor_compress_version_str(compress_method_t method)
+{
+  switch (method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD:
+      return tor_zlib_get_version_str();
+    case LZMA_METHOD:
+      return tor_lzma_get_version_str();
+    case ZSTD_METHOD:
+      return tor_zstd_get_version_str();
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+    default:
+      return NULL;
+  }
+}
+
+/** Return a string representation of the version of the library, found at
+ * compile time, providing the compression method given in <b>method</b>.
+ * Returns NULL if <b>method</b> is unknown or unsupported. */
+const char *
+tor_compress_header_version_str(compress_method_t method)
+{
+  switch (method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD:
+      return tor_zlib_get_header_version_str();
+    case LZMA_METHOD:
+      return tor_lzma_get_header_version_str();
+    case ZSTD_METHOD:
+      return tor_zstd_get_header_version_str();
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+    default:
+      return NULL;
+  }
+}
+
+/** Return the approximate number of bytes allocated for all
+ * supported compression schemas. */
+size_t
+tor_compress_get_total_allocation(void)
+{
+  return tor_zlib_get_total_allocation() +
+         tor_lzma_get_total_allocation() +
+         tor_zstd_get_total_allocation();
+}
+
+/** Internal state for an incremental compression/decompression.  The body of
+ * this struct is not exposed. */
+struct tor_compress_state_t {
+  compress_method_t method; /**< The compression method. */
+
+  union {
+    tor_zlib_compress_state_t *zlib_state;
+    tor_lzma_compress_state_t *lzma_state;
+    tor_zstd_compress_state_t *zstd_state;
+  } u; /**< Compression backend state. */
+};
+
+/** Construct and return a tor_compress_state_t object using <b>method</b>.  If
+ * <b>compress</b>, it's for compression; otherwise it's for decompression. */
+tor_compress_state_t *
+tor_compress_new(int compress, compress_method_t method,
+                 compression_level_t compression_level)
+{
+  tor_compress_state_t *state;
+
+  state = tor_malloc_zero(sizeof(tor_compress_state_t));
+  state->method = method;
+
+  switch (method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD: {
+      tor_zlib_compress_state_t *zlib_state =
+        tor_zlib_compress_new(compress, method, compression_level);
+
+      if (zlib_state == NULL)
+        goto err;
+
+      state->u.zlib_state = zlib_state;
+      break;
+    }
+    case LZMA_METHOD: {
+      tor_lzma_compress_state_t *lzma_state =
+        tor_lzma_compress_new(compress, method, compression_level);
+
+      if (lzma_state == NULL)
+        goto err;
+
+      state->u.lzma_state = lzma_state;
+      break;
+    }
+    case ZSTD_METHOD: {
+      tor_zstd_compress_state_t *zstd_state =
+        tor_zstd_compress_new(compress, method, compression_level);
+
+      if (zstd_state == NULL)
+        goto err;
+
+      state->u.zstd_state = zstd_state;
+      break;
+    }
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+      goto err;
+  }
+
+  return state;
+
+ err:
+  tor_free(state);
+  return NULL;
+}
+
+/** Compress/decompress some bytes using <b>state</b>.  Read up to
+ * *<b>in_len</b> bytes from *<b>in</b>, and write up to *<b>out_len</b> bytes
+ * to *<b>out</b>, adjusting the values as we go.  If <b>finish</b> is true,
+ * we've reached the end of the input.
+ *
+ * Return TOR_COMPRESS_DONE if we've finished the entire
+ * compression/decompression.
+ * Return TOR_COMPRESS_OK if we're processed everything from the input.
+ * Return TOR_COMPRESS_BUFFER_FULL if we're out of space on <b>out</b>.
+ * Return TOR_COMPRESS_ERROR if the stream is corrupt.
+ */
+tor_compress_output_t
+tor_compress_process(tor_compress_state_t *state,
+                     char **out, size_t *out_len,
+                     const char **in, size_t *in_len,
+                     int finish)
+{
+  tor_assert(state != NULL);
+
+  switch (state->method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD:
+      return tor_zlib_compress_process(state->u.zlib_state,
+                                       out, out_len, in, in_len,
+                                       finish);
+    case LZMA_METHOD:
+      return tor_lzma_compress_process(state->u.lzma_state,
+                                       out, out_len, in, in_len,
+                                       finish);
+    case ZSTD_METHOD:
+      return tor_zstd_compress_process(state->u.zstd_state,
+                                       out, out_len, in, in_len,
+                                       finish);
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+      goto err;
+  }
+
+ err:
+  return TOR_COMPRESS_ERROR;
+}
+
+/** Deallocate <b>state</b>. */
+void
+tor_compress_free(tor_compress_state_t *state)
+{
+  if (state == NULL)
+    return;
+
+  switch (state->method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD:
+      tor_zlib_compress_free(state->u.zlib_state);
+      break;
+    case LZMA_METHOD:
+      tor_lzma_compress_free(state->u.lzma_state);
+      break;
+    case ZSTD_METHOD:
+      tor_zstd_compress_free(state->u.zstd_state);
+      break;
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+      break;
+  }
+
+  tor_free(state);
+}
+
+/** Return the approximate number of bytes allocated for <b>state</b>. */
+size_t
+tor_compress_state_size(const tor_compress_state_t *state)
+{
+  tor_assert(state != NULL);
+
+  switch (state->method) {
+    case GZIP_METHOD:
+    case ZLIB_METHOD:
+      return tor_zlib_compress_state_size(state->u.zlib_state);
+    case LZMA_METHOD:
+      return tor_lzma_compress_state_size(state->u.lzma_state);
+    case ZSTD_METHOD:
+      return tor_zstd_compress_state_size(state->u.zstd_state);
+    case NO_METHOD:
+    case UNKNOWN_METHOD:
+      goto err;
+  }
+
+ err:
+  return 0;
+}
+
diff --git a/src/common/compress.h b/src/common/compress.h
new file mode 100644
index 0000000000..2d812e4430
--- /dev/null
+++ b/src/common/compress.h
@@ -0,0 +1,83 @@
+/* Copyright (c) 2003, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2017, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file compress.h
+ * \brief Headers for compress.c
+ **/
+
+#ifndef TOR_COMPRESS_H
+#define TOR_COMPRESS_H
+
+/** Enumeration of what kind of compression to use.  Only ZLIB_METHOD and
+ * GZIP_METHOD is guaranteed to be supported by the compress/uncompress
+ * functions here. Call tor_compress_supports_method() to check if a given
+ * compression schema is supported by Tor. */
+typedef enum {
+  NO_METHOD=0,
+  GZIP_METHOD=1,
+  ZLIB_METHOD=2,
+  LZMA_METHOD=3,
+  ZSTD_METHOD=4,
+  UNKNOWN_METHOD=5
+} compress_method_t;
+
+/**
+ * Enumeration to define tradeoffs between memory usage and compression level.
+ * HIGH_COMPRESSION saves the most bandwidth; LOW_COMPRESSION saves the most
+ * memory.
+ **/
+typedef enum {
+  HIGH_COMPRESSION, MEDIUM_COMPRESSION, LOW_COMPRESSION
+} compression_level_t;
+
+int tor_compress(char **out, size_t *out_len,
+                 const char *in, size_t in_len,
+                 compress_method_t method);
+
+int tor_uncompress(char **out, size_t *out_len,
+                   const char *in, size_t in_len,
+                   compress_method_t method,
+                   int complete_only,
+                   int protocol_warn_level);
+
+compress_method_t detect_compression_method(const char *in, size_t in_len);
+
+int tor_compress_is_compression_bomb(size_t size_in, size_t size_out);
+
+int tor_compress_supports_method(compress_method_t method);
+
+const char *tor_compress_version_str(compress_method_t method);
+
+const char *tor_compress_header_version_str(compress_method_t method);
+
+size_t tor_compress_get_total_allocation(void);
+
+/** Return values from tor_compress_process; see that function's documentation
+ * for details. */
+typedef enum {
+  TOR_COMPRESS_OK,
+  TOR_COMPRESS_DONE,
+  TOR_COMPRESS_BUFFER_FULL,
+  TOR_COMPRESS_ERROR
+} tor_compress_output_t;
+
+/** Internal state for an incremental compression/decompression. */
+typedef struct tor_compress_state_t tor_compress_state_t;
+
+tor_compress_state_t *tor_compress_new(int compress,
+                                       compress_method_t method,
+                                       compression_level_t level);
+
+tor_compress_output_t tor_compress_process(tor_compress_state_t *state,
+                                           char **out, size_t *out_len,
+                                           const char **in, size_t *in_len,
+                                           int finish);
+void tor_compress_free(tor_compress_state_t *state);
+
+size_t tor_compress_state_size(const tor_compress_state_t *state);
+
+#endif // TOR_COMPRESS_H.
+
diff --git a/src/common/compress_lzma.c b/src/common/compress_lzma.c
new file mode 100644
index 0000000000..ae0327f581
--- /dev/null
+++ b/src/common/compress_lzma.c
@@ -0,0 +1,605 @@
+/* Copyright (c) 2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2017, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file compress_lzma.c
+ * \brief Compression backend for LZMA.
+ *
+ * This module should never be invoked directly. Use the compress module
+ * instead.
+ **/
+
+#include "orconfig.h"
+
+#include "util.h"
+#include "torlog.h"
+#include "compress.h"
+#include "compress_lzma.h"
+
+#ifdef HAVE_LZMA
+#include <lzma.h>
+#endif
+
+/** Total number of bytes allocated for LZMA state. */
+static size_t total_lzma_allocation = 0;
+
+#ifdef HAVE_LZMA
+/** Given <b>level</b> return the memory level. */
+static int
+memory_level(compression_level_t level)
+{
+  switch (level) {
+    default:
+    case HIGH_COMPRESSION: return 9;
+    case MEDIUM_COMPRESSION: return 6;
+    case LOW_COMPRESSION: return 3;
+  }
+}
+
+/** Convert a given <b>error</b> to a human readable error string. */
+static const char *
+lzma_error_str(lzma_ret error)
+{
+  switch (error) {
+    case LZMA_OK:
+      return "Operation completed successfully";
+    case LZMA_STREAM_END:
+      return "End of stream";
+    case LZMA_NO_CHECK:
+      return "Input stream lacks integrity check";
+    case LZMA_UNSUPPORTED_CHECK:
+      return "Unable to calculate integrity check";
+    case LZMA_GET_CHECK:
+      return "Integrity check available";
+    case LZMA_MEM_ERROR:
+      return "Unable to allocate memory";
+    case LZMA_MEMLIMIT_ERROR:
+      return "Memory limit reached";
+    case LZMA_FORMAT_ERROR:
+      return "Unknown file format";
+    case LZMA_OPTIONS_ERROR:
+      return "Unsupported options";
+    case LZMA_DATA_ERROR:
+      return "Corrupt input data";
+    case LZMA_BUF_ERROR:
+      return "Unable to progress";
+    case LZMA_PROG_ERROR:
+      return "Programming error";
+    default:
+      return "Unknown LZMA error";
+  }
+}
+#endif // HAVE_LZMA.
+
+/** Return 1 if LZMA compression is supported; otherwise 0. */
+int
+tor_lzma_method_supported(void)
+{
+#ifdef HAVE_LZMA
+  return 1;
+#else
+  return 0;
+#endif
+}
+
+/** Return a string representation of the version of the currently running
+ * version of liblzma. Returns NULL if LZMA is unsupported. */
+const char *
+tor_lzma_get_version_str(void)
+{
+#ifdef HAVE_LZMA
+  return lzma_version_string();
+#else
+  return NULL;
+#endif
+}
+
+/** Return a string representation of the version of liblzma used at
+ * compilation time. Returns NULL if LZMA is unsupported. */
+const char *
+tor_lzma_get_header_version_str(void)
+{
+#ifdef HAVE_LZMA
+  return LZMA_VERSION_STRING;
+#else
+  return NULL;
+#endif
+}
+
+/** Given <b>in_len</b> bytes at <b>in</b>, compress them into a newly
+ * allocated buffer, using the LZMA method.  Store the compressed string in
+ * *<b>out</b>, and its length in *<b>out_len</b>.  Return 0 on success, -1 on
+ * failure.
+ */
+int
+tor_lzma_compress(char **out, size_t *out_len,
+                  const char *in, size_t in_len,
+                  compress_method_t method)
+{
+#ifdef HAVE_LZMA
+  lzma_stream stream = LZMA_STREAM_INIT;
+  lzma_options_lzma stream_options;
+  lzma_ret retval;
+  lzma_action action;
+  size_t out_size, old_size;
+  off_t offset;
+
+  tor_assert(out);
+  tor_assert(out_len);
+  tor_assert(in);
+  tor_assert(in_len < UINT_MAX);
+  tor_assert(method == LZMA_METHOD);
+
+  stream.next_in = (unsigned char *)in;
+  stream.avail_in = in_len;
+
+  lzma_lzma_preset(&stream_options,
+                   memory_level(HIGH_COMPRESSION));
+
+  retval = lzma_alone_encoder(&stream, &stream_options);
+
+  if (retval != LZMA_OK) {
+    log_warn(LD_GENERAL, "Error from LZMA encoder: %s (%u).",
+             lzma_error_str(retval), retval);
+    goto err;
+  }
+
+  out_size = in_len / 2;
+  if (out_size < 1024)
+    out_size = 1024;
+
+  *out = tor_malloc(out_size);
+
+  stream.next_out = (unsigned char *)*out;
+  stream.avail_out = out_size;
+
+  action = LZMA_RUN;
+
+  while (1) {
+    retval = lzma_code(&stream, action);
+    switch (retval) {
+      case LZMA_OK:
+        action = LZMA_FINISH;
+        break;
+      case LZMA_STREAM_END:
+        goto done;
+      case LZMA_BUF_ERROR:
+        offset = stream.next_out - ((unsigned char *)*out);
+        old_size = out_size;
+        out_size *= 2;
+
+        if (out_size < old_size) {
+          log_warn(LD_GENERAL, "Size overflow in LZMA compression.");
+          goto err;
+        }
+
+        *out = tor_realloc(*out, out_size);
+        stream.next_out = (unsigned char *)(*out + offset);
+        if (out_size - offset > UINT_MAX) {
+          log_warn(LD_BUG, "Ran over unsigned int limit of LZMA while "
+                           "compressing.");
+          goto err;
+        }
+        stream.avail_out = (unsigned int)(out_size - offset);
+        break;
+
+      // We list all the possible values of `lzma_ret` here to silence the
+      // `switch-enum` warning and to detect if a new member was added.
+      case LZMA_NO_CHECK:
+      case LZMA_UNSUPPORTED_CHECK:
+      case LZMA_GET_CHECK:
+      case LZMA_MEM_ERROR:
+      case LZMA_MEMLIMIT_ERROR:
+      case LZMA_FORMAT_ERROR:
+      case LZMA_OPTIONS_ERROR:
+      case LZMA_DATA_ERROR:
+      case LZMA_PROG_ERROR:
+      default:
+        log_warn(LD_GENERAL, "LZMA compression didn't finish: %s.",
+                 lzma_error_str(retval));
+        goto err;
+    }
+  }
+
+ done:
+  *out_len = stream.total_out;
+  lzma_end(&stream);
+
+  if (tor_compress_is_compression_bomb(*out_len, in_len)) {
+    log_warn(LD_BUG, "We compressed something and got an insanely high "
+                     "compression factor; other Tor instances would think "
+                     "this is a compression bomb.");
+    goto err;
+  }
+
+  return 0;
+
+ err:
+  lzma_end(&stream);
+  tor_free(*out);
+  return -1;
+#else // HAVE_LZMA.
+  (void)out;
+  (void)out_len;
+  (void)in;
+  (void)in_len;
+  (void)method;
+
+  return -1;
+#endif // HAVE_LZMA.
+}
+
+/** Given an LZMA compressed string of total length <b>in_len</b> bytes at
+ * <b>in</b>, uncompress them into a newly allocated buffer.  Store the
+ * uncompressed string in *<b>out</b>, and its length in *<b>out_len</b>.
+ * Return 0 on success, -1 on failure.
+ *
+ * If <b>complete_only</b> is true, we consider a truncated input as a failure;
+ * otherwise we decompress as much as we can.  Warn about truncated or corrupt
+ * inputs at <b>protocol_warn_level</b>.
+ */
+int
+tor_lzma_uncompress(char **out, size_t *out_len,
+                    const char *in, size_t in_len,
+                    compress_method_t method,
+                    int complete_only,
+                    int protocol_warn_level)
+{
+#ifdef HAVE_LZMA
+  lzma_stream stream = LZMA_STREAM_INIT;
+  lzma_ret retval;
+  lzma_action action;
+  size_t out_size, old_size;
+  off_t offset;
+
+  tor_assert(out);
+  tor_assert(out_len);
+  tor_assert(in);
+  tor_assert(in_len < UINT_MAX);
+  tor_assert(method == LZMA_METHOD);
+
+  stream.next_in = (unsigned char *)in;
+  stream.avail_in = in_len;
+
+  // FIXME(ahf): This should be something more sensible than
+  // UINT64_MAX: See #21665.
+  retval = lzma_alone_decoder(&stream, UINT64_MAX);
+
+  if (retval != LZMA_OK) {
+    log_warn(LD_GENERAL, "Error from LZMA decoder: %s (%u).",
+             lzma_error_str(retval), retval);
+    goto err;
+  }
+
+  out_size = in_len * 2;
+  if (out_size < 1024)
+    out_size = 1024;
+
+  if (out_size >= SIZE_T_CEILING || out_size > UINT_MAX)
+    goto err;
+
+  *out = tor_malloc(out_size);
+  stream.next_out = (unsigned char *)*out;
+  stream.avail_out = out_size;
+
+  // FIXME(ahf): We should figure out how to use LZMA_FULL_FLUSH to
+  // make the partial string read tests.
+  //   action = complete_only ? LZMA_FINISH : LZMA_SYNC_FLUSH.  // To do this,
+  // it seems like we have to use LZMA using their "xz" encoder instead of just
+  // regular LZMA.
+  (void)complete_only;
+  action = LZMA_FINISH;
+
+  while (1) {
+    retval = lzma_code(&stream, action);
+    switch (retval) {
+      case LZMA_STREAM_END:
+        if (stream.avail_in == 0)
+          goto done;
+
+        // We might have more data here. Reset our stream.
+        lzma_end(&stream);
+
+        retval = lzma_alone_decoder(&stream, UINT64_MAX);
+
+        if (retval != LZMA_OK) {
+          log_warn(LD_GENERAL, "Error from LZMA decoder: %s (%u).",
+                   lzma_error_str(retval), retval);
+          goto err;
+        }
+        break;
+      case LZMA_OK:
+        break;
+      case LZMA_BUF_ERROR:
+        if (stream.avail_out > 0) {
+          log_fn(protocol_warn_level, LD_PROTOCOL,
+                 "possible truncated or corrupt LZMA data.");
+          goto err;
+        }
+
+        offset = stream.next_out - (unsigned char *)*out;
+        old_size = out_size;
+        out_size *= 2;
+
+        if (out_size < old_size) {
+          log_warn(LD_GENERAL, "Size overflow in LZMA uncompression.");
+          goto err;
+        }
+
+        if (tor_compress_is_compression_bomb(in_len, out_size)) {
+          log_warn(LD_GENERAL, "Input looks like a possible LZMA compression "
+                               "bomb. Not proceeding.");
+          goto err;
+        }
+
+        if (out_size >= SIZE_T_CEILING) {
+          log_warn(LD_BUG, "Hit SIZE_T_CEILING limit while uncompressing "
+                           "LZMA data.");
+          goto err;
+        }
+
+        *out = tor_realloc(*out, out_size);
+        stream.next_out = (unsigned char *)(*out + offset);
+
+        if (out_size - offset > UINT_MAX) {
+          log_warn(LD_BUG, "Ran over unsigned int limit of LZMA while "
+                           "uncompressing.");
+          goto err;
+        }
+
+        stream.avail_out = (unsigned int)(out_size - offset);
+        break;
+
+      // We list all the possible values of `lzma_ret` here to silence the
+      // `switch-enum` warning and to detect if a new member was added.
+      case LZMA_NO_CHECK:
+      case LZMA_UNSUPPORTED_CHECK:
+      case LZMA_GET_CHECK:
+      case LZMA_MEM_ERROR:
+      case LZMA_MEMLIMIT_ERROR:
+      case LZMA_FORMAT_ERROR:
+      case LZMA_OPTIONS_ERROR:
+      case LZMA_DATA_ERROR:
+      case LZMA_PROG_ERROR:
+      default:
+        log_warn(LD_GENERAL, "LZMA decompression didn't finish: %s.",
+                 lzma_error_str(retval));
+        goto err;
+    }
+  }
+
+ done:
+  *out_len = stream.next_out - (unsigned char*)*out;
+  lzma_end(&stream);
+
+  // NUL-terminate our output.
+  if (out_size == *out_len)
+    *out = tor_realloc(*out, out_size + 1);
+  (*out)[*out_len] = '\0';
+
+  return 0;
+
+ err:
+  lzma_end(&stream);
+  tor_free(*out);
+  return -1;
+#else // HAVE_LZMA.
+  (void)out;
+  (void)out_len;
+  (void)in;
+  (void)in_len;
+  (void)method;
+  (void)complete_only;
+  (void)protocol_warn_level;
+
+  return -1;
+#endif // HAVE_LZMA.
+}
+
+/** Internal LZMA state for incremental compression/decompression.
+ * The body of this struct is not exposed. */
+struct tor_lzma_compress_state_t {
+#ifdef HAVE_LZMA
+  lzma_stream stream; /**< The LZMA stream. */
+#endif
+
+  int compress; /**< True if we are compressing; false if we are inflating */
+
+  /** Number of bytes read so far.  Used to detect compression bombs. */
+  size_t input_so_far;
+  /** Number of bytes written so far.  Used to detect compression bombs. */
+  size_t output_so_far;
+
+  /** Approximate number of bytes allocated for this object. */
+  size_t allocation;
+};
+
+/** Construct and return a tor_lzma_compress_state_t object using
+ * <b>method</b>. If <b>compress</b>, it's for compression; otherwise it's for
+ * decompression. */
+tor_lzma_compress_state_t *
+tor_lzma_compress_new(int compress,
+                      compress_method_t method,
+                      compression_level_t compression_level)
+{
+  tor_assert(method == LZMA_METHOD);
+
+#ifdef HAVE_LZMA
+  tor_lzma_compress_state_t *result;
+  lzma_ret retval;
+  lzma_options_lzma stream_options;
+
+  // Note that we do not explicitly initialize the lzma_stream object here,
+  // since the LZMA_STREAM_INIT "just" initializes all members to 0, which is
+  // also what `tor_malloc_zero()` does.
+  result = tor_malloc_zero(sizeof(tor_lzma_compress_state_t));
+  result->compress = compress;
+
+  // FIXME(ahf): We should either try to do the pre-calculation that is done
+  // with the zlib backend or use a custom allocator here where we pass our
+  // tor_lzma_compress_state_t as the opaque value.
+  result->allocation = 0;
+
+  if (compress) {
+    lzma_lzma_preset(&stream_options,
+                     memory_level(compression_level));
+
+    retval = lzma_alone_encoder(&result->stream, &stream_options);
+
+    if (retval != LZMA_OK) {
+      log_warn(LD_GENERAL, "Error from LZMA encoder: %s (%u).",
+               lzma_error_str(retval), retval);
+      goto err;
+    }
+  } else {
+    // FIXME(ahf): This should be something more sensible than
+    // UINT64_MAX: See #21665.
+    retval = lzma_alone_decoder(&result->stream, UINT64_MAX);
+
+    if (retval != LZMA_OK) {
+      log_warn(LD_GENERAL, "Error from LZMA decoder: %s (%u).",
+               lzma_error_str(retval), retval);
+      goto err;
+    }
+  }
+
+  return result;
+
+ err:
+  tor_free(result);
+  return NULL;
+#else // HAVE_LZMA.
+  (void)compress;
+  (void)method;
+  (void)compression_level;
+
+  return NULL;
+#endif // HAVE_LZMA.
+}
+
+/** Compress/decompress some bytes using <b>state</b>.  Read up to
+ * *<b>in_len</b> bytes from *<b>in</b>, and write up to *<b>out_len</b> bytes
+ * to *<b>out</b>, adjusting the values as we go.  If <b>finish</b> is true,
+ * we've reached the end of the input.
+ *
+ * Return TOR_COMPRESS_DONE if we've finished the entire
+ * compression/decompression.
+ * Return TOR_COMPRESS_OK if we're processed everything from the input.
+ * Return TOR_COMPRESS_BUFFER_FULL if we're out of space on <b>out</b>.
+ * Return TOR_COMPRESS_ERROR if the stream is corrupt.
+ */
+tor_compress_output_t
+tor_lzma_compress_process(tor_lzma_compress_state_t *state,
+                          char **out, size_t *out_len,
+                          const char **in, size_t *in_len,
+                          int finish)
+{
+#ifdef HAVE_LZMA
+  lzma_ret retval;
+  lzma_action action;
+
+  tor_assert(state != NULL);
+  tor_assert(*in_len <= UINT_MAX);
+  tor_assert(*out_len <= UINT_MAX);
+
+  state->stream.next_in = (unsigned char *)*in;
+  state->stream.avail_in = *in_len;
+  state->stream.next_out = (unsigned char *)*out;
+  state->stream.avail_out = *out_len;
+
+  action = finish ? LZMA_FINISH : LZMA_RUN;
+
+  retval = lzma_code(&state->stream, action);
+
+  state->input_so_far += state->stream.next_in - ((unsigned char *)*in);
+  state->output_so_far += state->stream.next_out - ((unsigned char *)*out);
+
+  *out = (char *)state->stream.next_out;
+  *out_len = state->stream.avail_out;
+  *in = (const char *)state->stream.next_in;
+  *in_len = state->stream.avail_in;
+
+  if (! state->compress &&
+      tor_compress_is_compression_bomb(state->input_so_far,
+                                       state->output_so_far)) {
+    log_warn(LD_DIR, "Possible compression bomb; abandoning stream.");
+    return TOR_COMPRESS_ERROR;
+  }
+
+  switch (retval) {
+    case LZMA_OK:
+      if (state->stream.avail_out == 0 || finish)
+        return TOR_COMPRESS_BUFFER_FULL;
+
+      return TOR_COMPRESS_OK;
+
+    case LZMA_BUF_ERROR:
+      if (state->stream.avail_in == 0 && !finish)
+        return TOR_COMPRESS_OK;
+
+      return TOR_COMPRESS_BUFFER_FULL;
+
+    case LZMA_STREAM_END:
+      return TOR_COMPRESS_DONE;
+
+    // We list all the possible values of `lzma_ret` here to silence the
+    // `switch-enum` warning and to detect if a new member was added.
+    case LZMA_NO_CHECK:
+    case LZMA_UNSUPPORTED_CHECK:
+    case LZMA_GET_CHECK:
+    case LZMA_MEM_ERROR:
+    case LZMA_MEMLIMIT_ERROR:
+    case LZMA_FORMAT_ERROR:
+    case LZMA_OPTIONS_ERROR:
+    case LZMA_DATA_ERROR:
+    case LZMA_PROG_ERROR:
+    default:
+      log_warn(LD_GENERAL, "LZMA %s didn't finish: %s.",
+               state->compress ? "compression" : "decompression",
+               lzma_error_str(retval));
+      return TOR_COMPRESS_ERROR;
+  }
+#else // HAVE_LZMA.
+  (void)state;
+  (void)out;
+  (void)out_len;
+  (void)in;
+  (void)in_len;
+  (void)finish;
+  return TOR_COMPRESS_ERROR;
+#endif // HAVE_LZMA.
+}
+
+/** Deallocate <b>state</b>. */
+void
+tor_lzma_compress_free(tor_lzma_compress_state_t *state)
+{
+  if (state == NULL)
+    return;
+
+  total_lzma_allocation -= state->allocation;
+
+#ifdef HAVE_LZMA
+  lzma_end(&state->stream);
+#endif
+
+  tor_free(state);
+}
+
+/** Return the approximate number of bytes allocated for <b>state</b>. */
+size_t
+tor_lzma_compress_state_size(const tor_lzma_compress_state_t *state)
+{
+  tor_assert(state != NULL);
+  return state->allocation;
+}
+
+/** Return the approximate number of bytes allocated for all LZMA states. */
+size_t
+tor_lzma_get_total_allocation(void)
+{
+  return total_lzma_allocation;
+}
+
diff --git a/src/common/compress_lzma.h b/src/common/compress_lzma.h
new file mode 100644
index 0000000000..71de56a1c6
--- /dev/null
+++ b/src/common/compress_lzma.h
@@ -0,0 +1,51 @@
+/* Copyright (c) 2003, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2017, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file compress_lzma.h
+ * \brief Header for compress_lzma.c
+ **/
+
+#ifndef TOR_COMPRESS_LZMA_H
+#define TOR_COMPRESS_LZMA_H
+
+int tor_lzma_method_supported(void);
+
+const char *tor_lzma_get_version_str(void);
+
+const char *tor_lzma_get_header_version_str(void);
+
+int tor_lzma_compress(char **out, size_t *out_len,
+                      const char *in, size_t in_len,
+                      compress_method_t method);
+
+int tor_lzma_uncompress(char **out, size_t *out_len,
+                        const char *in, size_t in_len,
+                        compress_method_t method,
+                        int complete_only,
+                        int protocol_warn_level);
+
+/** Internal state for an incremental LZMA compression/decompression. */
+typedef struct tor_lzma_compress_state_t tor_lzma_compress_state_t;
+
+tor_lzma_compress_state_t *
+tor_lzma_compress_new(int compress,
+                      compress_method_t method,
+                      compression_level_t compression_level);
+
+tor_compress_output_t
+tor_lzma_compress_process(tor_lzma_compress_state_t *state,
+                          char **out, size_t *out_len,
+                          const char **in, size_t *in_len,
+                          int finish);
+
+void tor_lzma_compress_free(tor_lzma_compress_state_t *state);
+
+size_t tor_lzma_compress_state_size(const tor_lzma_compress_state_t *state);
+
+size_t tor_lzma_get_total_allocation(void);
+
+#endif // TOR_COMPRESS_LZMA_H.
+
diff --git a/src/common/torgzip.c b/src/common/compress_zlib.c
index 223cd307a7..50bdf9ece1 100644
--- a/src/common/torgzip.c
+++ b/src/common/compress_zlib.c
@@ -4,25 +4,19 @@
 /* See LICENSE for licensing information */
 
 /**
- * \file torgzip.c
- * \brief A simple in-memory gzip implementation.
+ * \file compress_zlib.c
+ * \brief Compression backend for gzip and zlib.
+ *
+ * This module should never be invoked directly. Use the compress module
+ * instead.
  **/
 
 #include "orconfig.h"
 
-#include <stdlib.h>
-#include <stdio.h>
-#include <assert.h>
-#include <string.h>
-#include "torint.h"
-
-#ifdef HAVE_NETINET_IN_H
-#include <netinet/in.h>
-#endif
-
 #include "util.h"
 #include "torlog.h"
-#include "torgzip.h"
+#include "compress.h"
+#include "compress_zlib.h"
 
 /* zlib 1.2.4 and 1.2.5 do some "clever" things with macros.  Instead of
    saying "(defined(FOO) ? FOO : 0)" they like to say "FOO-0", on the theory
@@ -56,25 +50,21 @@ static size_t tor_zlib_state_size_precalc(int inflate,
 /** Total number of bytes allocated for zlib state */
 static size_t total_zlib_allocation = 0;
 
-/** Return a string representation of the version of the currently running
- * version of zlib. */
-const char *
-tor_zlib_get_version_str(void)
-{
-  return zlibVersion();
-}
-
-/** Return a string representation of the version of the version of zlib
-* used at compilation. */
-const char *
-tor_zlib_get_header_version_str(void)
+/** Given <b>level</b> return the memory level. */
+static int
+memory_level(compression_level_t level)
 {
-  return ZLIB_VERSION;
+  switch (level) {
+    default:
+    case HIGH_COMPRESSION: return 8;
+    case MEDIUM_COMPRESSION: return 7;
+    case LOW_COMPRESSION: return 6;
+  }
 }
 
 /** Return the 'bits' value to tell zlib to use <b>method</b>.*/
 static inline int
-method_bits(compress_method_t method, zlib_compression_level_t level)
+method_bits(compress_method_t method, compression_level_t level)
 {
   /* Bits+16 means "use gzip" in zlib >= 1.2 */
   const int flag = method == GZIP_METHOD ? 16 : 0;
@@ -86,53 +76,39 @@ method_bits(compress_method_t method, zlib_compression_level_t level)
   }
 }
 
-static inline int
-get_memlevel(zlib_compression_level_t level)
+/** Return 1 if zlib/gzip compression is supported; otherwise 0. */
+int
+tor_zlib_method_supported(void)
 {
-  switch (level) {
-    default:
-    case HIGH_COMPRESSION: return 8;
-    case MEDIUM_COMPRESSION: return 7;
-    case LOW_COMPRESSION: return 6;
-  }
+  /* We currently always support zlib/gzip, but we keep this function around in
+   * case we some day decide to deprecate zlib/gzip support.
+   */
+  return 1;
 }
 
-/** @{ */
-/* These macros define the maximum allowable compression factor.  Anything of
- * size greater than CHECK_FOR_COMPRESSION_BOMB_AFTER is not allowed to
- * have an uncompression factor (uncompressed size:compressed size ratio) of
- * any greater than MAX_UNCOMPRESSION_FACTOR.
- *
- * Picking a value for MAX_UNCOMPRESSION_FACTOR is a trade-off: we want it to
- * be small to limit the attack multiplier, but we also want it to be large
- * enough so that no legitimate document --even ones we might invent in the
- * future -- ever compresses by a factor of greater than
- * MAX_UNCOMPRESSION_FACTOR. Within those parameters, there's a reasonably
- * large range of possible values. IMO, anything over 8 is probably safe; IMO
- * anything under 50 is probably sufficient.
- */
-#define MAX_UNCOMPRESSION_FACTOR 25
-#define CHECK_FOR_COMPRESSION_BOMB_AFTER (1024*64)
-/** @} */
-
-/** Return true if uncompressing an input of size <b>in_size</b> to an input
- * of size at least <b>size_out</b> looks like a compression bomb. */
-static int
-is_compression_bomb(size_t size_in, size_t size_out)
+/** Return a string representation of the version of the currently running
+ * version of zlib. */
+const char *
+tor_zlib_get_version_str(void)
 {
-  if (size_in == 0 || size_out < CHECK_FOR_COMPRESSION_BOMB_AFTER)
-    return 0;
+  return zlibVersion();
+}
 
-  return (size_out / size_in > MAX_UNCOMPRESSION_FACTOR);
+/** Return a string representation of the version of the version of zlib
+* used at compilation. */
+const char *
+tor_zlib_get_header_version_str(void)
+{
+  return ZLIB_VERSION;
 }
 
 /** Given <b>in_len</b> bytes at <b>in</b>, compress them into a newly
  * allocated buffer, using the method described in <b>method</b>.  Store the
- * compressed string in *<b>out</b>, and its length in *<b>out_len</b>.
- * Return 0 on success, -1 on failure.
+ * compressed string in *<b>out</b>, and its length in *<b>out_len</b>.  Return
+ * 0 on success, -1 on failure.
  */
 int
-tor_gzip_compress(char **out, size_t *out_len,
+tor_zlib_compress(char **out, size_t *out_len,
                   const char *in, size_t in_len,
                   compress_method_t method)
 {
@@ -156,7 +132,7 @@ tor_gzip_compress(char **out, size_t *out_len,
 
   if (deflateInit2(stream, Z_BEST_COMPRESSION, Z_DEFLATED,
                    method_bits(method, HIGH_COMPRESSION),
-                   get_memlevel(HIGH_COMPRESSION),
+                   memory_level(HIGH_COMPRESSION),
                    Z_DEFAULT_STRATEGY) != Z_OK) {
     //LCOV_EXCL_START -- we can only provoke failure by giving junk arguments.
     log_warn(LD_GENERAL, "Error from deflateInit2: %s",
@@ -224,7 +200,7 @@ tor_gzip_compress(char **out, size_t *out_len,
   }
   tor_free(stream);
 
-  if (is_compression_bomb(*out_len, in_len)) {
+  if (tor_compress_is_compression_bomb(*out_len, in_len)) {
     log_warn(LD_BUG, "We compressed something and got an insanely high "
           "compression factor; other Tors would think this was a zlib bomb.");
     goto err;
@@ -240,19 +216,17 @@ tor_gzip_compress(char **out, size_t *out_len,
   return -1;
 }
 
-/** Given zero or more zlib-compressed or gzip-compressed strings of
- * total length
- * <b>in_len</b> bytes at <b>in</b>, uncompress them into a newly allocated
- * buffer, using the method described in <b>method</b>.  Store the uncompressed
- * string in *<b>out</b>, and its length in *<b>out_len</b>.  Return 0 on
- * success, -1 on failure.
+/** Given an Zlib/Gzip compressed string of total length <b>in_len</b> bytes
+ * at <b>in</b>, uncompress them into a newly allocated buffer.  Store the
+ * uncompressed string in *<b>out</b>, and its length in *<b>out_len</b>.
+ * Return 0 on success, -1 on failure.
  *
- * If <b>complete_only</b> is true, we consider a truncated input as a
- * failure; otherwise we decompress as much as we can.  Warn about truncated
- * or corrupt inputs at <b>protocol_warn_level</b>.
+ * If <b>complete_only</b> is true, we consider a truncated input as a failure;
+ * otherwise we decompress as much as we can.  Warn about truncated or corrupt
+ * inputs at <b>protocol_warn_level</b>.
  */
 int
-tor_gzip_uncompress(char **out, size_t *out_len,
+tor_zlib_uncompress(char **out, size_t *out_len,
                     const char *in, size_t in_len,
                     compress_method_t method,
                     int complete_only,
@@ -332,7 +306,7 @@ tor_gzip_uncompress(char **out, size_t *out_len,
           log_warn(LD_GENERAL, "Size overflow in uncompression.");
           goto err;
         }
-        if (is_compression_bomb(in_len, out_size)) {
+        if (tor_compress_is_compression_bomb(in_len, out_size)) {
           log_warn(LD_GENERAL, "Input looks like a possible zlib bomb; "
                    "not proceeding.");
           goto err;
@@ -382,26 +356,9 @@ tor_gzip_uncompress(char **out, size_t *out_len,
   return -1;
 }
 
-/** Try to tell whether the <b>in_len</b>-byte string in <b>in</b> is likely
- * to be compressed or not.  If it is, return the likeliest compression method.
- * Otherwise, return UNKNOWN_METHOD.
- */
-compress_method_t
-detect_compression_method(const char *in, size_t in_len)
-{
-  if (in_len > 2 && fast_memeq(in, "\x1f\x8b", 2)) {
-    return GZIP_METHOD;
-  } else if (in_len > 2 && (in[0] & 0x0f) == 8 &&
-             (ntohs(get_uint16(in)) % 31) == 0) {
-    return ZLIB_METHOD;
-  } else {
-    return UNKNOWN_METHOD;
-  }
-}
-
-/** Internal state for an incremental zlib compression/decompression.  The
- * body of this struct is not exposed. */
-struct tor_zlib_state_t {
+/** Internal zlib state for an incremental compression/decompression.
+ * The body of this struct is not exposed. */
+struct tor_zlib_compress_state_t {
   struct z_stream_s stream; /**< The zlib stream */
   int compress; /**< True if we are compressing; false if we are inflating */
 
@@ -414,47 +371,79 @@ struct tor_zlib_state_t {
   size_t allocation;
 };
 
-/** Construct and return a tor_zlib_state_t object using <b>method</b>.  If
- * <b>compress</b>, it's for compression; otherwise it's for
+/** Return an approximate number of bytes used in RAM to hold a state with
+ * window bits <b>windowBits</b> and compression level 'memlevel' */
+static size_t
+tor_zlib_state_size_precalc(int inflate_, int windowbits, int memlevel)
+{
+  windowbits &= 15;
+
+#define A_FEW_KILOBYTES 2048
+
+  if (inflate_) {
+    /* From zconf.h:
+
+       "The memory requirements for inflate are (in bytes) 1 << windowBits
+       that is, 32K for windowBits=15 (default value) plus a few kilobytes
+       for small objects."
+    */
+    return sizeof(tor_zlib_compress_state_t) + sizeof(struct z_stream_s) +
+      (1 << 15) + A_FEW_KILOBYTES;
+  } else {
+    /* Also from zconf.h:
+
+       "The memory requirements for deflate are (in bytes):
+            (1 << (windowBits+2)) +  (1 << (memLevel+9))
+        ... plus a few kilobytes for small objects."
+    */
+    return sizeof(tor_zlib_compress_state_t) + sizeof(struct z_stream_s) +
+      (1 << (windowbits + 2)) + (1 << (memlevel + 9)) + A_FEW_KILOBYTES;
+  }
+#undef A_FEW_KILOBYTES
+}
+
+/** Construct and return a tor_zlib_compress_state_t object using
+ * <b>method</b>. If <b>compress</b>, it's for compression; otherwise it's for
  * decompression. */
-tor_zlib_state_t *
-tor_zlib_new(int compress_, compress_method_t method,
-             zlib_compression_level_t compression_level)
+tor_zlib_compress_state_t *
+tor_zlib_compress_new(int compress,
+                      compress_method_t method,
+                      compression_level_t compression_level)
 {
-  tor_zlib_state_t *out;
+  tor_zlib_compress_state_t *out;
   int bits, memlevel;
 
- if (! compress_) {
-   /* use this setting for decompression, since we might have the
-    * max number of window bits */
-   compression_level = HIGH_COMPRESSION;
- }
-
- out = tor_malloc_zero(sizeof(tor_zlib_state_t));
- out->stream.zalloc = Z_NULL;
- out->stream.zfree = Z_NULL;
- out->stream.opaque = NULL;
- out->compress = compress_;
- bits = method_bits(method, compression_level);
- memlevel = get_memlevel(compression_level);
- if (compress_) {
-   if (deflateInit2(&out->stream, Z_BEST_COMPRESSION, Z_DEFLATED,
-                    bits, memlevel,
-                    Z_DEFAULT_STRATEGY) != Z_OK)
-     goto err; // LCOV_EXCL_LINE
- } else {
-   if (inflateInit2(&out->stream, bits) != Z_OK)
-     goto err; // LCOV_EXCL_LINE
- }
- out->allocation = tor_zlib_state_size_precalc(!compress_, bits, memlevel);
-
- total_zlib_allocation += out->allocation;
-
- return out;
+  if (! compress) {
+    /* use this setting for decompression, since we might have the
+     * max number of window bits */
+    compression_level = HIGH_COMPRESSION;
+  }
+
+  out = tor_malloc_zero(sizeof(tor_zlib_compress_state_t));
+  out->stream.zalloc = Z_NULL;
+  out->stream.zfree = Z_NULL;
+  out->stream.opaque = NULL;
+  out->compress = compress;
+  bits = method_bits(method, compression_level);
+  memlevel = memory_level(compression_level);
+  if (compress) {
+    if (deflateInit2(&out->stream, Z_BEST_COMPRESSION, Z_DEFLATED,
+                     bits, memlevel,
+                     Z_DEFAULT_STRATEGY) != Z_OK)
+    goto err; // LCOV_EXCL_LINE
+  } else {
+    if (inflateInit2(&out->stream, bits) != Z_OK)
+      goto err; // LCOV_EXCL_LINE
+  }
+  out->allocation = tor_zlib_state_size_precalc(!compress, bits, memlevel);
+
+  total_zlib_allocation += out->allocation;
+
+  return out;
 
  err:
- tor_free(out);
- return NULL;
+  tor_free(out);
+  return NULL;
 }
 
 /** Compress/decompress some bytes using <b>state</b>.  Read up to
@@ -462,18 +451,20 @@ tor_zlib_new(int compress_, compress_method_t method,
  * to *<b>out</b>, adjusting the values as we go.  If <b>finish</b> is true,
  * we've reached the end of the input.
  *
- * Return TOR_ZLIB_DONE if we've finished the entire compression/decompression.
- * Return TOR_ZLIB_OK if we're processed everything from the input.
- * Return TOR_ZLIB_BUF_FULL if we're out of space on <b>out</b>.
- * Return TOR_ZLIB_ERR if the stream is corrupt.
+ * Return TOR_COMPRESS_DONE if we've finished the entire
+ * compression/decompression.
+ * Return TOR_COMPRESS_OK if we're processed everything from the input.
+ * Return TOR_COMPRESS_BUFFER_FULL if we're out of space on <b>out</b>.
+ * Return TOR_COMPRESS_ERROR if the stream is corrupt.
  */
-tor_zlib_output_t
-tor_zlib_process(tor_zlib_state_t *state,
-                 char **out, size_t *out_len,
-                 const char **in, size_t *in_len,
-                 int finish)
+tor_compress_output_t
+tor_zlib_compress_process(tor_zlib_compress_state_t *state,
+                          char **out, size_t *out_len,
+                          const char **in, size_t *in_len,
+                          int finish)
 {
   int err;
+  tor_assert(state != NULL);
   tor_assert(*in_len <= UINT_MAX);
   tor_assert(*out_len <= UINT_MAX);
   state->stream.next_in = (unsigned char*) *in;
@@ -496,38 +487,39 @@ tor_zlib_process(tor_zlib_state_t *state,
   *in_len = state->stream.avail_in;
 
   if (! state->compress &&
-      is_compression_bomb(state->input_so_far, state->output_so_far)) {
+      tor_compress_is_compression_bomb(state->input_so_far,
+                                       state->output_so_far)) {
     log_warn(LD_DIR, "Possible zlib bomb; abandoning stream.");
-    return TOR_ZLIB_ERR;
+    return TOR_COMPRESS_ERROR;
   }
 
   switch (err)
     {
     case Z_STREAM_END:
-      return TOR_ZLIB_DONE;
+      return TOR_COMPRESS_DONE;
     case Z_BUF_ERROR:
       if (state->stream.avail_in == 0 && !finish)
-        return TOR_ZLIB_OK;
-      return TOR_ZLIB_BUF_FULL;
+        return TOR_COMPRESS_OK;
+      return TOR_COMPRESS_BUFFER_FULL;
     case Z_OK:
       if (state->stream.avail_out == 0 || finish)
-        return TOR_ZLIB_BUF_FULL;
-      return TOR_ZLIB_OK;
+        return TOR_COMPRESS_BUFFER_FULL;
+      return TOR_COMPRESS_OK;
     default:
       log_warn(LD_GENERAL, "Gzip returned an error: %s",
                state->stream.msg ? state->stream.msg : "<no message>");
-      return TOR_ZLIB_ERR;
+      return TOR_COMPRESS_ERROR;
     }
 }
 
 /** Deallocate <b>state</b>. */
 void
-tor_zlib_free(tor_zlib_state_t *state)
+tor_zlib_compress_free(tor_zlib_compress_state_t *state)
 {
-  if (!state)
+  if (state == NULL)
     return;
 
- total_zlib_allocation -= state->allocation;
+  total_zlib_allocation -= state->allocation;
 
   if (state->compress)
     deflateEnd(&state->stream);
@@ -537,41 +529,11 @@ tor_zlib_free(tor_zlib_state_t *state)
   tor_free(state);
 }
 
-/** Return an approximate number of bytes used in RAM to hold a state with
- * window bits <b>windowBits</b> and compression level 'memlevel' */
-static size_t
-tor_zlib_state_size_precalc(int inflate_, int windowbits, int memlevel)
-{
-  windowbits &= 15;
-
-#define A_FEW_KILOBYTES 2048
-
-  if (inflate_) {
-    /* From zconf.h:
-
-       "The memory requirements for inflate are (in bytes) 1 << windowBits
-       that is, 32K for windowBits=15 (default value) plus a few kilobytes
-       for small objects."
-    */
-    return sizeof(tor_zlib_state_t) + sizeof(struct z_stream_s) +
-      (1 << 15) + A_FEW_KILOBYTES;
-  } else {
-    /* Also from zconf.h:
-
-       "The memory requirements for deflate are (in bytes):
-            (1 << (windowBits+2)) +  (1 << (memLevel+9))
-        ... plus a few kilobytes for small objects."
-    */
-    return sizeof(tor_zlib_state_t) + sizeof(struct z_stream_s) +
-      (1 << (windowbits + 2)) + (1 << (memlevel + 9)) + A_FEW_KILOBYTES;
-  }
-#undef A_FEW_KILOBYTES
-}
-
 /** Return the approximate number of bytes allocated for <b>state</b>. */
 size_t
-tor_zlib_state_size(const tor_zlib_state_t *state)
+tor_zlib_compress_state_size(const tor_zlib_compress_state_t *state)
 {
+  tor_assert(state != NULL);
   return state->allocation;
 }
 
diff --git a/src/common/compress_zlib.h b/src/common/compress_zlib.h
new file mode 100644
index 0000000000..6e8e5c5136
--- /dev/null
+++ b/src/common/compress_zlib.h
@@ -0,0 +1,51 @@
+/* Copyright (c) 2003, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2017, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file compress_zlib.h
+ * \brief Header for compress_zlib.c
+ **/
+
+#ifndef TOR_COMPRESS_ZLIB_H
+#define TOR_COMPRESS_ZLIB_H
+
+int tor_zlib_method_supported(void);
+
+const char *tor_zlib_get_version_str(void);
+
+const char *tor_zlib_get_header_version_str(void);
+
+int tor_zlib_compress(char **out, size_t *out_len,
+                      const char *in, size_t in_len,
+                      compress_method_t method);
+
+int tor_zlib_uncompress(char **out, size_t *out_len,
+                        const char *in, size_t in_len,
+                        compress_method_t method,
+                        int complete_only,
+                        int protocol_warn_level);
+
+/** Internal state for an incremental zlib/gzip compression/decompression. */
+typedef struct tor_zlib_compress_state_t tor_zlib_compress_state_t;
+
+tor_zlib_compress_state_t *
+tor_zlib_compress_new(int compress,
+                      compress_method_t method,
+                      compression_level_t compression_level);
+
+tor_compress_output_t
+tor_zlib_compress_process(tor_zlib_compress_state_t *state,
+                          char **out, size_t *out_len,
+                          const char **in, size_t *in_len,
+                          int finish);
+
+void tor_zlib_compress_free(tor_zlib_compress_state_t *state);
+
+size_t tor_zlib_compress_state_size(const tor_zlib_compress_state_t *state);
+
+size_t tor_zlib_get_total_allocation(void);
+
+#endif // TOR_COMPRESS_ZLIB_H.
+
diff --git a/src/common/compress_zstd.c b/src/common/compress_zstd.c
new file mode 100644
index 0000000000..664cce1700
--- /dev/null
+++ b/src/common/compress_zstd.c
@@ -0,0 +1,609 @@
+/* Copyright (c) 2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2017, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file compress_zstd.c
+ * \brief Compression backend for Zstandard.
+ *
+ * This module should never be invoked directly. Use the compress module
+ * instead.
+ **/
+
+#include "orconfig.h"
+
+#include "util.h"
+#include "torlog.h"
+#include "compress.h"
+#include "compress_zstd.h"
+
+#ifdef HAVE_ZSTD
+#include <zstd.h>
+#include <zstd_errors.h>
+#endif
+
+/** Total number of bytes allocated for Zstandard state. */
+static size_t total_zstd_allocation = 0;
+
+#ifdef HAVE_ZSTD
+/** Given <b>level</b> return the memory level. */
+static int
+memory_level(compression_level_t level)
+{
+  switch (level) {
+    default:
+    case HIGH_COMPRESSION: return 9;
+    case MEDIUM_COMPRESSION: return 8;
+    case LOW_COMPRESSION: return 7;
+  }
+}
+#endif // HAVE_ZSTD.
+
+/** Return 1 if Zstandard compression is supported; otherwise 0. */
+int
+tor_zstd_method_supported(void)
+{
+#ifdef HAVE_ZSTD
+  return 1;
+#else
+  return 0;
+#endif
+}
+
+/** Return a string representation of the version of the currently running
+ * version of libzstd. Returns NULL if Zstandard is unsupported. */
+const char *
+tor_zstd_get_version_str(void)
+{
+#ifdef HAVE_ZSTD
+  static char version_str[16];
+  size_t version_number;
+
+  version_number = ZSTD_versionNumber();
+  tor_snprintf(version_str, sizeof(version_str),
+               "%lu.%lu.%lu",
+               version_number / 10000 % 100,
+               version_number / 100 % 100,
+               version_number % 100);
+
+  return version_str;
+#else
+  return NULL;
+#endif
+}
+
+/** Return a string representation of the version of the version of libzstd
+ * used at compilation time. Returns NULL if Zstandard is unsupported. */
+const char *
+tor_zstd_get_header_version_str(void)
+{
+#ifdef HAVE_ZSTD
+  return ZSTD_VERSION_STRING;
+#else
+  return NULL;
+#endif
+}
+
+/** Given <b>in_len</b> bytes at <b>in</b>, compress them into a newly
+ * allocated buffer, using the Zstandard method.  Store the compressed string
+ * in *<b>out</b>, and its length in *<b>out_len</b>.  Return 0 on success, -1
+ * on failure.
+ */
+int
+tor_zstd_compress(char **out, size_t *out_len,
+                  const char *in, size_t in_len,
+                  compress_method_t method)
+{
+#ifdef HAVE_ZSTD
+  ZSTD_CStream *stream = NULL;
+  size_t out_size, old_size;
+  size_t retval;
+
+  tor_assert(out);
+  tor_assert(out_len);
+  tor_assert(in);
+  tor_assert(in_len < UINT_MAX);
+  tor_assert(method == ZSTD_METHOD);
+
+  *out = NULL;
+
+  stream = ZSTD_createCStream();
+
+  if (stream == NULL) {
+    // Zstandard does not give us any useful error message to why this
+    // happened. See https://github.com/facebook/zstd/issues/398
+    log_warn(LD_GENERAL, "Error while creating Zstandard stream");
+    goto err;
+  }
+
+  retval = ZSTD_initCStream(stream,
+                            memory_level(HIGH_COMPRESSION));
+
+  if (ZSTD_isError(retval)) {
+    log_warn(LD_GENERAL, "Zstandard stream initialization error: %s",
+             ZSTD_getErrorName(retval));
+    goto err;
+  }
+
+  // Assume 50% compression and update our buffer in case we need to.
+  out_size = in_len / 2;
+  if (out_size < 1024)
+    out_size = 1024;
+
+  *out = tor_malloc(out_size);
+  *out_len = 0;
+
+  ZSTD_inBuffer input = { in, in_len, 0 };
+  ZSTD_outBuffer output = { *out, out_size, 0 };
+
+  while (input.pos < input.size) {
+    retval = ZSTD_compressStream(stream, &output, &input);
+
+    if (ZSTD_isError(retval)) {
+      log_warn(LD_GENERAL, "Zstandard stream compression error: %s",
+               ZSTD_getErrorName(retval));
+      goto err;
+    }
+
+    if (input.pos < input.size && output.pos == output.size) {
+      old_size = out_size;
+      out_size *= 2;
+
+      if (out_size < old_size) {
+        log_warn(LD_GENERAL, "Size overflow in Zstandard compression.");
+        goto err;
+      }
+
+      if (out_size - output.pos > UINT_MAX) {
+        log_warn(LD_BUG,  "Ran over unsigned int limit of Zstandard while "
+                          "compressing.");
+        goto err;
+      }
+
+      output.dst = *out = tor_realloc(*out, out_size);
+      output.size = out_size;
+    }
+  }
+
+  while (1) {
+    retval = ZSTD_endStream(stream, &output);
+
+    if (retval == 0)
+      break;
+
+    if (ZSTD_isError(retval)) {
+      log_warn(LD_GENERAL, "Zstandard stream error: %s",
+               ZSTD_getErrorName(retval));
+      goto err;
+    }
+
+    if (output.pos == output.size) {
+      old_size = out_size;
+      out_size *= 2;
+
+      if (out_size < old_size) {
+        log_warn(LD_GENERAL, "Size overflow in Zstandard compression.");
+        goto err;
+      }
+
+      if (out_size - output.pos > UINT_MAX) {
+        log_warn(LD_BUG,  "Ran over unsigned int limit of Zstandard while "
+                          "compressing.");
+        goto err;
+      }
+
+      output.dst = *out = tor_realloc(*out, out_size);
+      output.size = out_size;
+    }
+  }
+
+  *out_len = output.pos;
+
+  if (tor_compress_is_compression_bomb(*out_len, in_len)) {
+    log_warn(LD_BUG, "We compressed something and got an insanely high "
+                     "compression factor; other Tor instances would think "
+                     "this is a compression bomb.");
+    goto err;
+  }
+
+  if (stream != NULL) {
+    ZSTD_freeCStream(stream);
+  }
+
+  return 0;
+
+ err:
+  if (stream != NULL) {
+    ZSTD_freeCStream(stream);
+  }
+
+  tor_free(*out);
+  return -1;
+#else // HAVE_ZSTD.
+  (void)out;
+  (void)out_len;
+  (void)in;
+  (void)in_len;
+  (void)method;
+
+  return -1;
+#endif // HAVE_ZSTD.
+}
+
+/** Given a Zstandard compressed string of total length <b>in_len</b> bytes at
+ * <b>in</b>, uncompress them into a newly allocated buffer.  Store the
+ * uncompressed string in *<b>out</b>, and its length in *<b>out_len</b>.
+ * Return 0 on success, -1 on failure.
+ *
+ * If <b>complete_only</b> is true, we consider a truncated input as a failure;
+ * otherwise we decompress as much as we can.  Warn about truncated or corrupt
+ * inputs at <b>protocol_warn_level</b>.
+ */
+int
+tor_zstd_uncompress(char **out, size_t *out_len,
+                    const char *in, size_t in_len,
+                    compress_method_t method,
+                    int complete_only,
+                    int protocol_warn_level)
+{
+#ifdef HAVE_ZSTD
+  ZSTD_DStream *stream = NULL;
+  size_t retval;
+  size_t out_size, old_size;
+
+  tor_assert(out);
+  tor_assert(out_len);
+  tor_assert(in);
+  tor_assert(in_len < UINT_MAX);
+  tor_assert(method == ZSTD_METHOD);
+
+  // FIXME(ahf): Handle this?
+  (void)complete_only;
+  (void)protocol_warn_level;
+
+  *out = NULL;
+
+  stream = ZSTD_createDStream();
+
+  if (stream == NULL) {
+    // Zstandard does not give us any useful error message to why this
+    // happened. See https://github.com/facebook/zstd/issues/398
+    log_warn(LD_GENERAL, "Error while creating Zstandard stream");
+    goto err;
+  }
+
+  retval = ZSTD_initDStream(stream);
+
+  if (ZSTD_isError(retval)) {
+    log_warn(LD_GENERAL, "Zstandard stream initialization error: %s",
+             ZSTD_getErrorName(retval));
+    goto err;
+  }
+
+  out_size = in_len * 2;
+  if (out_size < 1024)
+    out_size = 1024;
+
+  if (out_size >= SIZE_T_CEILING || out_size > UINT_MAX)
+    goto err;
+
+  *out = tor_malloc(out_size);
+  *out_len = 0;
+
+  ZSTD_inBuffer input = { in, in_len, 0 };
+  ZSTD_outBuffer output = { *out, out_size, 0 };
+
+  while (input.pos < input.size) {
+    retval = ZSTD_decompressStream(stream, &output, &input);
+
+    if (ZSTD_isError(retval)) {
+      log_warn(LD_GENERAL, "Zstandard stream decompression error: %s",
+               ZSTD_getErrorName(retval));
+      goto err;
+    }
+
+    if (input.pos < input.size && output.pos == output.size) {
+      old_size = out_size;
+      out_size *= 2;
+
+      if (out_size < old_size) {
+        log_warn(LD_GENERAL, "Size overflow in Zstandard compression.");
+        goto err;
+      }
+
+      if (tor_compress_is_compression_bomb(in_len, out_size)) {
+        log_warn(LD_GENERAL, "Input looks like a possible Zstandard "
+                 "compression bomb. Not proceeding.");
+        goto err;
+      }
+
+      if (out_size >= SIZE_T_CEILING) {
+        log_warn(LD_BUG, "Hit SIZE_T_CEILING limit while uncompressing "
+                         "Zstandard data.");
+        goto err;
+      }
+
+      if (out_size - output.pos > UINT_MAX) {
+        log_warn(LD_BUG,  "Ran over unsigned int limit of Zstandard while "
+                          "decompressing.");
+        goto err;
+      }
+
+      output.dst = *out = tor_realloc(*out, out_size);
+      output.size = out_size;
+    }
+  }
+
+  *out_len = output.pos;
+
+  if (stream != NULL) {
+    ZSTD_freeDStream(stream);
+  }
+
+  // NUL-terminate our output.
+  if (out_size == *out_len)
+    *out = tor_realloc(*out, out_size + 1);
+  (*out)[*out_len] = '\0';
+
+  return 0;
+
+ err:
+  if (stream != NULL) {
+    ZSTD_freeDStream(stream);
+  }
+
+  tor_free(*out);
+  return -1;
+#else // HAVE_ZSTD.
+  (void)out;
+  (void)out_len;
+  (void)in;
+  (void)in_len;
+  (void)method;
+  (void)complete_only;
+  (void)protocol_warn_level;
+
+  return -1;
+#endif // HAVE_ZSTD.
+}
+
+/** Internal Zstandard state for incremental compression/decompression.
+ * The body of this struct is not exposed. */
+struct tor_zstd_compress_state_t {
+#ifdef HAVE_ZSTD
+  union {
+    /** Compression stream. Used when <b>compress</b> is true. */
+    ZSTD_CStream *compress_stream;
+    /** Decompression stream. Used when <b>compress</b> is false. */
+    ZSTD_DStream *decompress_stream;
+  } u; /**< Zstandard stream objects. */
+#endif // HAVE_ZSTD.
+
+  int compress; /**< True if we are compressing; false if we are inflating */
+
+  /** Number of bytes read so far.  Used to detect compression bombs. */
+  size_t input_so_far;
+  /** Number of bytes written so far.  Used to detect compression bombs. */
+  size_t output_so_far;
+
+  /** Approximate number of bytes allocated for this object. */
+  size_t allocation;
+};
+
+/** Construct and return a tor_zstd_compress_state_t object using
+ * <b>method</b>. If <b>compress</b>, it's for compression; otherwise it's for
+ * decompression. */
+tor_zstd_compress_state_t *
+tor_zstd_compress_new(int compress,
+                      compress_method_t method,
+                      compression_level_t compression_level)
+{
+  tor_assert(method == ZSTD_METHOD);
+
+#ifdef HAVE_ZSTD
+  tor_zstd_compress_state_t *result;
+  size_t retval;
+
+  result = tor_malloc_zero(sizeof(tor_zstd_compress_state_t));
+  result->compress = compress;
+
+  // FIXME(ahf): We should either try to do the pre-calculation that is done
+  // with the zlib backend or use a custom allocator here where we pass our
+  // tor_zstd_compress_state_t as the opaque value.
+  result->allocation = 0;
+
+  if (compress) {
+    result->u.compress_stream = ZSTD_createCStream();
+
+    if (result->u.compress_stream == NULL) {
+      log_warn(LD_GENERAL, "Error while creating Zstandard stream");
+      goto err;
+    }
+
+    retval = ZSTD_initCStream(result->u.compress_stream,
+                              memory_level(compression_level));
+
+    if (ZSTD_isError(retval)) {
+      log_warn(LD_GENERAL, "Zstandard stream initialization error: %s",
+               ZSTD_getErrorName(retval));
+      goto err;
+    }
+  } else {
+    result->u.decompress_stream = ZSTD_createDStream();
+
+    if (result->u.decompress_stream == NULL) {
+      log_warn(LD_GENERAL, "Error while creating Zstandard stream");
+      goto err;
+    }
+
+    retval = ZSTD_initDStream(result->u.decompress_stream);
+
+    if (ZSTD_isError(retval)) {
+      log_warn(LD_GENERAL, "Zstandard stream initialization error: %s",
+               ZSTD_getErrorName(retval));
+      goto err;
+    }
+  }
+
+  return result;
+
+ err:
+  if (compress) {
+    ZSTD_freeCStream(result->u.compress_stream);
+  } else {
+    ZSTD_freeDStream(result->u.decompress_stream);
+  }
+
+  tor_free(result);
+  return NULL;
+#else // HAVE_ZSTD.
+  (void)compress;
+  (void)method;
+  (void)compression_level;
+
+  return NULL;
+#endif // HAVE_ZSTD.
+}
+
+/** Compress/decompress some bytes using <b>state</b>.  Read up to
+ * *<b>in_len</b> bytes from *<b>in</b>, and write up to *<b>out_len</b> bytes
+ * to *<b>out</b>, adjusting the values as we go.  If <b>finish</b> is true,
+ * we've reached the end of the input.
+ *
+ * Return TOR_COMPRESS_DONE if we've finished the entire
+ * compression/decompression.
+ * Return TOR_COMPRESS_OK if we're processed everything from the input.
+ * Return TOR_COMPRESS_BUFFER_FULL if we're out of space on <b>out</b>.
+ * Return TOR_COMPRESS_ERROR if the stream is corrupt.
+ */
+tor_compress_output_t
+tor_zstd_compress_process(tor_zstd_compress_state_t *state,
+                          char **out, size_t *out_len,
+                          const char **in, size_t *in_len,
+                          int finish)
+{
+#ifdef HAVE_ZSTD
+  size_t retval;
+
+  tor_assert(state != NULL);
+  tor_assert(*in_len <= UINT_MAX);
+  tor_assert(*out_len <= UINT_MAX);
+
+  ZSTD_inBuffer input = { *in, *in_len, 0 };
+  ZSTD_outBuffer output = { *out, *out_len, 0 };
+
+  if (state->compress) {
+    retval = ZSTD_compressStream(state->u.compress_stream,
+                                 &output, &input);
+  } else {
+    retval = ZSTD_decompressStream(state->u.decompress_stream,
+                                   &output, &input);
+  }
+
+  state->input_so_far += input.pos;
+  state->output_so_far += output.pos;
+
+  *out = (char *)output.dst + output.pos;
+  *out_len = output.size - output.pos;
+  *in = (char *)input.src + input.pos;
+  *in_len = input.size - input.pos;
+
+  if (! state->compress &&
+      tor_compress_is_compression_bomb(state->input_so_far,
+                                       state->output_so_far)) {
+    log_warn(LD_DIR, "Possible compression bomb; abandoning stream.");
+    return TOR_COMPRESS_ERROR;
+  }
+
+  if (ZSTD_isError(retval)) {
+    log_warn(LD_GENERAL, "Zstandard %s didn't finish: %s.",
+             state->compress ? "compression" : "decompression",
+             ZSTD_getErrorName(retval));
+    return TOR_COMPRESS_ERROR;
+  }
+
+  if (state->compress && !finish) {
+    retval = ZSTD_flushStream(state->u.compress_stream, &output);
+
+    *out = (char *)output.dst + output.pos;
+    *out_len = output.size - output.pos;
+
+    if (ZSTD_isError(retval)) {
+      log_warn(LD_GENERAL, "Zstandard compression unable to flush: %s.",
+               ZSTD_getErrorName(retval));
+      return TOR_COMPRESS_ERROR;
+    }
+
+    if (retval > 0)
+      return TOR_COMPRESS_BUFFER_FULL;
+  }
+
+  if (state->compress && finish) {
+    retval = ZSTD_endStream(state->u.compress_stream, &output);
+
+    *out = (char *)output.dst + output.pos;
+    *out_len = output.size - output.pos;
+
+    if (ZSTD_isError(retval)) {
+      log_warn(LD_GENERAL, "Zstandard compression unable to write "
+               "epilogue: %s.",
+               ZSTD_getErrorName(retval));
+      return TOR_COMPRESS_ERROR;
+    }
+
+    // endStream returns the number of bytes that is needed to write the
+    // epilogue.
+    if (retval > 0)
+      return TOR_COMPRESS_BUFFER_FULL;
+  }
+
+  return finish ? TOR_COMPRESS_DONE : TOR_COMPRESS_OK;
+#else // HAVE_ZSTD.
+  (void)state;
+  (void)out;
+  (void)out_len;
+  (void)in;
+  (void)in_len;
+  (void)finish;
+
+  return TOR_COMPRESS_ERROR;
+#endif // HAVE_ZSTD.
+}
+
+/** Deallocate <b>state</b>. */
+void
+tor_zstd_compress_free(tor_zstd_compress_state_t *state)
+{
+  if (state == NULL)
+    return;
+
+  total_zstd_allocation -= state->allocation;
+
+#ifdef HAVE_ZSTD
+  if (state->compress) {
+    ZSTD_freeCStream(state->u.compress_stream);
+  } else {
+    ZSTD_freeDStream(state->u.decompress_stream);
+  }
+#endif // HAVE_ZSTD.
+
+  tor_free(state);
+}
+
+/** Return the approximate number of bytes allocated for <b>state</b>. */
+size_t
+tor_zstd_compress_state_size(const tor_zstd_compress_state_t *state)
+{
+  tor_assert(state != NULL);
+  return state->allocation;
+}
+
+/** Return the approximate number of bytes allocated for all Zstandard
+ * states. */
+size_t
+tor_zstd_get_total_allocation(void)
+{
+  return total_zstd_allocation;
+}
+
diff --git a/src/common/compress_zstd.h b/src/common/compress_zstd.h
new file mode 100644
index 0000000000..663cbdd2ff
--- /dev/null
+++ b/src/common/compress_zstd.h
@@ -0,0 +1,51 @@
+/* Copyright (c) 2003, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2017, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file compress_zstd.h
+ * \brief Header for compress_zstd.c
+ **/
+
+#ifndef TOR_COMPRESS_ZSTD_H
+#define TOR_COMPRESS_ZSTD_H
+
+int tor_zstd_method_supported(void);
+
+const char *tor_zstd_get_version_str(void);
+
+const char *tor_zstd_get_header_version_str(void);
+
+int tor_zstd_compress(char **out, size_t *out_len,
+                      const char *in, size_t in_len,
+                      compress_method_t method);
+
+int tor_zstd_uncompress(char **out, size_t *out_len,
+                        const char *in, size_t in_len,
+                        compress_method_t method,
+                        int complete_only,
+                        int protocol_warn_level);
+
+/** Internal state for an incremental Zstandard compression/decompression. */
+typedef struct tor_zstd_compress_state_t tor_zstd_compress_state_t;
+
+tor_zstd_compress_state_t *
+tor_zstd_compress_new(int compress,
+                      compress_method_t method,
+                      compression_level_t compression_level);
+
+tor_compress_output_t
+tor_zstd_compress_process(tor_zstd_compress_state_t *state,
+                          char **out, size_t *out_len,
+                          const char **in, size_t *in_len,
+                          int finish);
+
+void tor_zstd_compress_free(tor_zstd_compress_state_t *state);
+
+size_t tor_zstd_compress_state_size(const tor_zstd_compress_state_t *state);
+
+size_t tor_zstd_get_total_allocation(void);
+
+#endif // TOR_COMPRESS_ZSTD_H.
+
diff --git a/src/common/include.am b/src/common/include.am
index d6504c7466..e285ef5f86 100644
--- a/src/common/include.am
+++ b/src/common/include.am
@@ -105,11 +105,14 @@ src/common/src_common_libor_testing_a-log.$(OBJEXT) \
 
 LIBOR_CRYPTO_A_SRC = \
   src/common/aes.c		\
+  src/common/compress.c	\
+  src/common/compress_lzma.c	\
+  src/common/compress_zlib.c	\
+  src/common/compress_zstd.c	\
   src/common/crypto.c		\
   src/common/crypto_pwbox.c     \
   src/common/crypto_s2k.c	\
   src/common/crypto_format.c	\
-  src/common/torgzip.c		\
   src/common/tortls.c		\
   src/common/crypto_curve25519.c \
   src/common/crypto_ed25519.c
@@ -145,6 +148,10 @@ COMMONHEADERS = \
   src/common/compat_openssl.h			\
   src/common/compat_threads.h			\
   src/common/compat_time.h			\
+  src/common/compress.h			\
+  src/common/compress_lzma.h			\
+  src/common/compress_zlib.h			\
+  src/common/compress_zstd.h			\
   src/common/confline.h				\
   src/common/container.h			\
   src/common/crypto.h				\
@@ -163,7 +170,6 @@ COMMONHEADERS = \
   src/common/storagedir.h			\
   src/common/testsupport.h			\
   src/common/timers.h				\
-  src/common/torgzip.h				\
   src/common/torint.h				\
   src/common/torlog.h				\
   src/common/tortls.h				\
diff --git a/src/common/torgzip.h b/src/common/torgzip.h
deleted file mode 100644
index 430b152fe4..0000000000
--- a/src/common/torgzip.h
+++ /dev/null
@@ -1,72 +0,0 @@
-/* Copyright (c) 2003, Roger Dingledine
- * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2017, The Tor Project, Inc. */
-/* See LICENSE for licensing information */
-
-/**
- * \file torgzip.h
- * \brief Headers for torgzip.h
- **/
-
-#ifndef TOR_TORGZIP_H
-#define TOR_TORGZIP_H
-
-/** Enumeration of what kind of compression to use.  Only ZLIB_METHOD is
- * guaranteed to be supported by the compress/uncompress functions here;
- * GZIP_METHOD may be supported if we built against zlib version 1.2 or later
- * and is_gzip_supported() returns true. */
-typedef enum {
-  NO_METHOD=0, GZIP_METHOD=1, ZLIB_METHOD=2, UNKNOWN_METHOD=3
-} compress_method_t;
-
-/**
- * Enumeration to define tradeoffs between memory usage and compression level.
- * HIGH_COMPRESSION saves the most bandwidth; LOW_COMPRESSION saves the most
- * memory.
- **/
-typedef enum {
-  HIGH_COMPRESSION, MEDIUM_COMPRESSION, LOW_COMPRESSION
-} zlib_compression_level_t;
-
-int
-tor_gzip_compress(char **out, size_t *out_len,
-                  const char *in, size_t in_len,
-                  compress_method_t method);
-int
-tor_gzip_uncompress(char **out, size_t *out_len,
-                    const char *in, size_t in_len,
-                    compress_method_t method,
-                    int complete_only,
-                    int protocol_warn_level);
-
-int is_gzip_supported(void);
-
-const char *
-tor_zlib_get_version_str(void);
-
-const char *
-tor_zlib_get_header_version_str(void);
-
-compress_method_t detect_compression_method(const char *in, size_t in_len);
-
-/** Return values from tor_zlib_process; see that function's documentation for
- * details. */
-typedef enum {
-  TOR_ZLIB_OK, TOR_ZLIB_DONE, TOR_ZLIB_BUF_FULL, TOR_ZLIB_ERR
-} tor_zlib_output_t;
-/** Internal state for an incremental zlib compression/decompression. */
-typedef struct tor_zlib_state_t tor_zlib_state_t;
-tor_zlib_state_t *tor_zlib_new(int compress, compress_method_t method,
-                               zlib_compression_level_t level);
-
-tor_zlib_output_t tor_zlib_process(tor_zlib_state_t *state,
-                                   char **out, size_t *out_len,
-                                   const char **in, size_t *in_len,
-                                   int finish);
-void tor_zlib_free(tor_zlib_state_t *state);
-
-size_t tor_zlib_state_size(const tor_zlib_state_t *state);
-size_t tor_zlib_get_total_allocation(void);
-
-#endif
-
diff --git a/src/or/buffers.c b/src/or/buffers.c
index e559f80a1e..4f22935d26 100644
--- a/src/or/buffers.c
+++ b/src/or/buffers.c
@@ -2088,13 +2088,13 @@ fetch_from_buf_line(buf_t *buf, char *data_out, size_t *data_len)
 }
 
 /** Compress on uncompress the <b>data_len</b> bytes in <b>data</b> using the
- * zlib state <b>state</b>, appending the result to <b>buf</b>.  If
+ * compression state <b>state</b>, appending the result to <b>buf</b>.  If
  * <b>done</b> is true, flush the data in the state and finish the
  * compression/uncompression.  Return -1 on failure, 0 on success. */
 int
-write_to_buf_zlib(buf_t *buf, tor_zlib_state_t *state,
-                  const char *data, size_t data_len,
-                  int done)
+write_to_buf_compress(buf_t *buf, tor_compress_state_t *state,
+                      const char *data, size_t data_len,
+                      int done)
 {
   char *next;
   size_t old_avail, avail;
@@ -2108,20 +2108,22 @@ write_to_buf_zlib(buf_t *buf, tor_zlib_state_t *state,
     }
     next = CHUNK_WRITE_PTR(buf->tail);
     avail = old_avail = CHUNK_REMAINING_CAPACITY(buf->tail);
-    switch (tor_zlib_process(state, &next, &avail, &data, &data_len, done)) {
-      case TOR_ZLIB_DONE:
+    switch (tor_compress_process(state, &next, &avail,
+                                 &data, &data_len, done)) {
+      case TOR_COMPRESS_DONE:
         over = 1;
         break;
-      case TOR_ZLIB_ERR:
+      case TOR_COMPRESS_ERROR:
         return -1;
-      case TOR_ZLIB_OK:
+      case TOR_COMPRESS_OK:
         if (data_len == 0)
           over = 1;
         break;
-      case TOR_ZLIB_BUF_FULL:
+      case TOR_COMPRESS_BUFFER_FULL:
         if (avail) {
-          /* Zlib says we need more room (ZLIB_BUF_FULL).  Start a new chunk
-           * automatically, whether were going to or not. */
+          /* The compression module says we need more room
+           * (TOR_COMPRESS_BUFFER_FULL).  Start a new chunk automatically,
+           * whether were going to or not. */
           need_new_chunk = 1;
         }
         break;
diff --git a/src/or/buffers.h b/src/or/buffers.h
index c6a5ffaad5..23b58a571a 100644
--- a/src/or/buffers.h
+++ b/src/or/buffers.h
@@ -36,8 +36,8 @@ int flush_buf(tor_socket_t s, buf_t *buf, size_t sz, size_t *buf_flushlen);
 int flush_buf_tls(tor_tls_t *tls, buf_t *buf, size_t sz, size_t *buf_flushlen);
 
 int write_to_buf(const char *string, size_t string_len, buf_t *buf);
-int write_to_buf_zlib(buf_t *buf, tor_zlib_state_t *state,
-                      const char *data, size_t data_len, int done);
+int write_to_buf_compress(buf_t *buf, tor_compress_state_t *state,
+                          const char *data, size_t data_len, int done);
 int move_buf_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen);
 int fetch_from_buf(char *string, size_t string_len, buf_t *buf);
 int fetch_var_cell_from_buf(buf_t *buf, var_cell_t **out, int linkproto);
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 80bb7f69f3..365e5b2f89 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -1990,10 +1990,10 @@ single_conn_free_bytes(connection_t *conn)
   }
   if (conn->type == CONN_TYPE_DIR) {
     dir_connection_t *dir_conn = TO_DIR_CONN(conn);
-    if (dir_conn->zlib_state) {
-      result += tor_zlib_state_size(dir_conn->zlib_state);
-      tor_zlib_free(dir_conn->zlib_state);
-      dir_conn->zlib_state = NULL;
+    if (dir_conn->compress_state) {
+      result += tor_compress_state_size(dir_conn->compress_state);
+      tor_compress_free(dir_conn->compress_state);
+      dir_conn->compress_state = NULL;
     }
   }
   return result;
diff --git a/src/or/config.c b/src/or/config.c
index 809ff499fc..a73f397073 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -69,6 +69,7 @@
 #include "circuitmux.h"
 #include "circuitmux_ewma.h"
 #include "circuitstats.h"
+#include "compress.h"
 #include "config.h"
 #include "connection.h"
 #include "connection_edge.h"
@@ -99,7 +100,6 @@
 #include "statefile.h"
 #include "transports.h"
 #include "ext_orport.h"
-#include "torgzip.h"
 #ifdef _WIN32
 #include <shlobj.h>
 #endif
@@ -4949,9 +4949,21 @@ options_init_from_torrc(int argc, char **argv)
     printf("OpenSSL \t\t%-15s\t\t%s\n",
                       crypto_openssl_get_header_version_str(),
                       crypto_openssl_get_version_str());
-    printf("Zlib    \t\t%-15s\t\t%s\n",
-                      tor_zlib_get_header_version_str(),
-                      tor_zlib_get_version_str());
+    if (tor_compress_supports_method(ZLIB_METHOD)) {
+      printf("Zlib    \t\t%-15s\t\t%s\n",
+                        tor_compress_version_str(ZLIB_METHOD),
+                        tor_compress_header_version_str(ZLIB_METHOD));
+    }
+    if (tor_compress_supports_method(LZMA_METHOD)) {
+      printf("Liblzma \t\t%-15s\t\t%s\n",
+                        tor_compress_version_str(LZMA_METHOD),
+                        tor_compress_header_version_str(LZMA_METHOD));
+    }
+    if (tor_compress_supports_method(ZSTD_METHOD)) {
+      printf("Libzstd \t\t%-15s\t\t%s\n",
+                        tor_compress_version_str(ZSTD_METHOD),
+                        tor_compress_header_version_str(ZSTD_METHOD));
+    }
     //TODO: Hex versions?
     exit(0);
   }
diff --git a/src/or/connection.c b/src/or/connection.c
index 09e316d214..5fb2c53677 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -628,7 +628,7 @@ connection_free_(connection_t *conn)
     dir_connection_t *dir_conn = TO_DIR_CONN(conn);
     tor_free(dir_conn->requested_resource);
 
-    tor_zlib_free(dir_conn->zlib_state);
+    tor_compress_free(dir_conn->compress_state);
     if (dir_conn->spool) {
       SMARTLIST_FOREACH(dir_conn->spool, spooled_resource_t *, spooled,
                         spooled_resource_free(spooled));
@@ -4060,9 +4060,9 @@ connection_write_to_buf_impl_,(const char *string, size_t len,
   if (zlib) {
     dir_connection_t *dir_conn = TO_DIR_CONN(conn);
     int done = zlib < 0;
-    CONN_LOG_PROTECT(conn, r = write_to_buf_zlib(conn->outbuf,
-                                                 dir_conn->zlib_state,
-                                                 string, len, done));
+    CONN_LOG_PROTECT(conn, r = write_to_buf_compress(conn->outbuf,
+                                                     dir_conn->compress_state,
+                                                     string, len, done));
   } else {
     CONN_LOG_PROTECT(conn, r = write_to_buf(string, len, conn->outbuf));
   }
diff --git a/src/or/connection.h b/src/or/connection.h
index df6fc64709..36e45aef38 100644
--- a/src/or/connection.h
+++ b/src/or/connection.h
@@ -141,17 +141,17 @@ MOCK_DECL(void, connection_write_to_buf_impl_,
 /* DOCDOC connection_write_to_buf */
 static void connection_write_to_buf(const char *string, size_t len,
                                     connection_t *conn);
-/* DOCDOC connection_write_to_buf_zlib */
-static void connection_write_to_buf_zlib(const char *string, size_t len,
-                                         dir_connection_t *conn, int done);
+/* DOCDOC connection_write_to_buf_compress */
+static void connection_write_to_buf_compress(const char *string, size_t len,
+                                             dir_connection_t *conn, int done);
 static inline void
 connection_write_to_buf(const char *string, size_t len, connection_t *conn)
 {
   connection_write_to_buf_impl_(string, len, conn, 0);
 }
 static inline void
-connection_write_to_buf_zlib(const char *string, size_t len,
-                             dir_connection_t *conn, int done)
+connection_write_to_buf_compress(const char *string, size_t len,
+                                 dir_connection_t *conn, int done)
 {
   connection_write_to_buf_impl_(string, len, TO_CONN(conn), done ? -1 : 1);
 }
diff --git a/src/or/directory.c b/src/or/directory.c
index 1b999ee7c3..e0409e2021 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -2096,15 +2096,15 @@ connection_dir_client_reached_eof(dir_connection_t *conn)
     }
     /* Try declared compression first if we can. */
     if (compression == GZIP_METHOD  || compression == ZLIB_METHOD)
-      tor_gzip_uncompress(&new_body, &new_len, body, body_len, compression,
-                          !allow_partial, LOG_PROTOCOL_WARN);
+      tor_uncompress(&new_body, &new_len, body, body_len, compression,
+                     !allow_partial, LOG_PROTOCOL_WARN);
     /* Okay, if that didn't work, and we think that it was compressed
      * differently, try that. */
     if (!new_body &&
         (guessed == GZIP_METHOD || guessed == ZLIB_METHOD) &&
         compression != guessed)
-      tor_gzip_uncompress(&new_body, &new_len, body, body_len, guessed,
-                          !allow_partial, LOG_PROTOCOL_WARN);
+      tor_uncompress(&new_body, &new_len, body, body_len, guessed,
+                     !allow_partial, LOG_PROTOCOL_WARN);
     /* If we're pretty sure that we have a compressed directory, and
      * we didn't manage to uncompress it, then warn and bail. */
     if (!plausible && !new_body) {
@@ -2845,7 +2845,7 @@ client_likes_consensus(networkstatus_t *v, const char *want_url)
 
 /** Return the compression level we should use for sending a compressed
  * response of size <b>n_bytes</b>. */
-STATIC zlib_compression_level_t
+STATIC compression_level_t
 choose_compression_level(ssize_t n_bytes)
 {
   if (! have_been_under_memory_pressure()) {
@@ -3178,7 +3178,8 @@ handle_get_current_consensus(dir_connection_t *conn,
     write_http_response_header(conn, -1, compressed,
                                smartlist_len(conn->spool) == 1 ? lifetime : 0);
     if (! compressed)
-      conn->zlib_state = tor_zlib_new(0, ZLIB_METHOD, HIGH_COMPRESSION);
+      conn->compress_state = tor_compress_new(0, ZLIB_METHOD,
+                                              HIGH_COMPRESSION);
 
     /* Prime the connection with some data. */
     const int initial_flush_result = connection_dirserv_flushed_some(conn);
@@ -3276,11 +3277,11 @@ handle_get_status_vote(dir_connection_t *conn, const get_handler_args_t *args)
 
     if (smartlist_len(items)) {
       if (compressed) {
-        conn->zlib_state = tor_zlib_new(1, ZLIB_METHOD,
-                                    choose_compression_level(estimated_len));
+        conn->compress_state = tor_compress_new(1, ZLIB_METHOD,
+                           choose_compression_level(estimated_len));
         SMARTLIST_FOREACH(items, const char *, c,
-                 connection_write_to_buf_zlib(c, strlen(c), conn, 0));
-        connection_write_to_buf_zlib("", 0, conn, 1);
+                 connection_write_to_buf_compress(c, strlen(c), conn, 0));
+        connection_write_to_buf_compress("", 0, conn, 1);
       } else {
         SMARTLIST_FOREACH(items, const char *, c,
                          connection_write_to_buf(c, strlen(c), TO_CONN(conn)));
@@ -3335,7 +3336,7 @@ handle_get_microdesc(dir_connection_t *conn, const get_handler_args_t *args)
     write_http_response_header(conn, -1, compressed, MICRODESC_CACHE_LIFETIME);
 
     if (compressed)
-      conn->zlib_state = tor_zlib_new(1, ZLIB_METHOD,
+      conn->compress_state = tor_compress_new(1, ZLIB_METHOD,
                                       choose_compression_level(size_guess));
 
     const int initial_flush_result = connection_dirserv_flushed_some(conn);
@@ -3428,7 +3429,7 @@ handle_get_descriptor(dir_connection_t *conn, const get_handler_args_t *args)
       }
       write_http_response_header(conn, -1, compressed, cache_lifetime);
       if (compressed)
-        conn->zlib_state = tor_zlib_new(1, ZLIB_METHOD,
+        conn->compress_state = tor_compress_new(1, ZLIB_METHOD,
                                         choose_compression_level(size_guess));
       clear_spool = 0;
       /* Prime the connection with some data. */
@@ -3519,13 +3520,14 @@ handle_get_keys(dir_connection_t *conn, const get_handler_args_t *args)
 
     write_http_response_header(conn, compressed?-1:len, compressed, 60*60);
     if (compressed) {
-      conn->zlib_state = tor_zlib_new(1, ZLIB_METHOD,
-                                      choose_compression_level(len));
+      conn->compress_state = tor_compress_new(1, ZLIB_METHOD,
+                                              choose_compression_level(len));
       SMARTLIST_FOREACH(certs, authority_cert_t *, c,
-            connection_write_to_buf_zlib(c->cache_info.signed_descriptor_body,
-                                         c->cache_info.signed_descriptor_len,
-                                         conn, 0));
-      connection_write_to_buf_zlib("", 0, conn, 1);
+            connection_write_to_buf_compress(
+                c->cache_info.signed_descriptor_body,
+                c->cache_info.signed_descriptor_len,
+                conn, 0));
+      connection_write_to_buf_compress("", 0, conn, 1);
     } else {
       SMARTLIST_FOREACH(certs, authority_cert_t *, c,
             connection_write_to_buf(c->cache_info.signed_descriptor_body,
diff --git a/src/or/directory.h b/src/or/directory.h
index 0c5db3e070..4c52c24049 100644
--- a/src/or/directory.h
+++ b/src/or/directory.h
@@ -181,7 +181,7 @@ STATIC int handle_post_hs_descriptor(const char *url, const char *body);
 STATIC char* authdir_type_to_string(dirinfo_type_t auth);
 STATIC const char * dir_conn_purpose_to_string(int purpose);
 STATIC int should_use_directory_guards(const or_options_t *options);
-STATIC zlib_compression_level_t choose_compression_level(ssize_t n_bytes);
+STATIC compression_level_t choose_compression_level(ssize_t n_bytes);
 STATIC const smartlist_t *find_dl_schedule(download_status_t *dls,
                                            const or_options_t *options);
 STATIC void find_dl_min_and_max_delay(download_status_t *dls,
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 70b0b22f25..e76fd932ca 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -1176,8 +1176,8 @@ new_cached_dir(char *s, time_t published)
   d->dir = s;
   d->dir_len = strlen(s);
   d->published = published;
-  if (tor_gzip_compress(&(d->dir_z), &(d->dir_z_len), d->dir, d->dir_len,
-                        ZLIB_METHOD)) {
+  if (tor_compress(&(d->dir_z), &(d->dir_z_len), d->dir, d->dir_len,
+                   ZLIB_METHOD)) {
     log_warn(LD_BUG, "Error compressing directory");
   }
   return d;
@@ -3497,8 +3497,8 @@ spooled_resource_flush_some(spooled_resource_t *spooled,
       /* Absent objects count as "done". */
       return SRFS_DONE;
     }
-    if (conn->zlib_state) {
-      connection_write_to_buf_zlib((const char*)body, bodylen, conn, 0);
+    if (conn->compress_state) {
+      connection_write_to_buf_compress((const char*)body, bodylen, conn, 0);
     } else {
       connection_write_to_buf((const char*)body, bodylen, TO_CONN(conn));
     }
@@ -3523,9 +3523,10 @@ spooled_resource_flush_some(spooled_resource_t *spooled,
     if (BUG(remaining < 0))
       return SRFS_ERR;
     ssize_t bytes = (ssize_t) MIN(DIRSERV_CACHED_DIR_CHUNK_SIZE, remaining);
-    if (conn->zlib_state) {
-      connection_write_to_buf_zlib(cached->dir_z + spooled->cached_dir_offset,
-                                   bytes, conn, 0);
+    if (conn->compress_state) {
+      connection_write_to_buf_compress(
+              cached->dir_z + spooled->cached_dir_offset,
+              bytes, conn, 0);
     } else {
       connection_write_to_buf(cached->dir_z + spooled->cached_dir_offset,
                               bytes, TO_CONN(conn));
@@ -3788,12 +3789,12 @@ connection_dirserv_flushed_some(dir_connection_t *conn)
   /* If we get here, we're done. */
   smartlist_free(conn->spool);
   conn->spool = NULL;
-  if (conn->zlib_state) {
-    /* Flush the zlib state: there could be more bytes pending in there, and
-     * we don't want to omit bytes. */
-    connection_write_to_buf_zlib("", 0, conn, 1);
-    tor_zlib_free(conn->zlib_state);
-    conn->zlib_state = NULL;
+  if (conn->compress_state) {
+    /* Flush the compression state: there could be more bytes pending in there,
+     * and we don't want to omit bytes. */
+    connection_write_to_buf_compress("", 0, conn, 1);
+    tor_compress_free(conn->compress_state);
+    conn->compress_state = NULL;
   }
   return 0;
 }
diff --git a/src/or/include.am b/src/or/include.am
index dd27bc8411..483ea2f2aa 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -121,7 +121,8 @@ src_or_tor_LDADD = src/or/libtor.a src/common/libor.a src/common/libor-ctime.a \
 	src/common/libor-crypto.a $(LIBKECCAK_TINY) $(LIBDONNA) \
 	src/common/libor-event.a src/trunnel/libor-trunnel.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
-	@TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@
+	@TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@ \
+	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@
 
 if COVERAGE_ENABLED
 src_or_tor_cov_SOURCES = src/or/tor_main.c
@@ -133,7 +134,8 @@ src_or_tor_cov_LDADD = src/or/libtor-testing.a src/common/libor-testing.a \
 	src/common/libor-crypto-testing.a $(LIBKECCAK_TINY) $(LIBDONNA) \
 	src/common/libor-event-testing.a src/trunnel/libor-trunnel-testing.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
-	@TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@
+	@TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@ \
+	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@
 endif
 
 ORHEADERS = \
diff --git a/src/or/main.c b/src/or/main.c
index 4505879adc..1ba6554d3e 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -58,6 +58,7 @@
 #include "circuitlist.h"
 #include "circuituse.h"
 #include "command.h"
+#include "compress.h"
 #include "config.h"
 #include "confparse.h"
 #include "connection.h"
@@ -2998,11 +2999,16 @@ tor_init(int argc, char *argv[])
     const char *version = get_version();
 
     log_notice(LD_GENERAL, "Tor %s running on %s with Libevent %s, "
-               "OpenSSL %s and Zlib %s.", version,
+               "OpenSSL %s, Zlib %s, Liblzma %s, and Libzstd %s.", version,
                get_uname(),
                tor_libevent_get_version_str(),
                crypto_openssl_get_version_str(),
-               tor_zlib_get_version_str());
+               tor_compress_supports_method(ZLIB_METHOD) ?
+                 tor_compress_version_str(ZLIB_METHOD) : "N/A",
+               tor_compress_supports_method(LZMA_METHOD) ?
+                 tor_compress_version_str(LZMA_METHOD) : "N/A",
+               tor_compress_supports_method(ZSTD_METHOD) ?
+                 tor_compress_version_str(ZSTD_METHOD) : "N/A");
 
     log_notice(LD_GENERAL, "Tor can't help you if you use it wrong! "
                "Learn how to be safe at "
diff --git a/src/or/or.h b/src/or/or.h
index a7b3a66561..9e3e409af9 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -71,7 +71,7 @@
 #include "tortls.h"
 #include "torlog.h"
 #include "container.h"
-#include "torgzip.h"
+#include "compress.h"
 #include "address.h"
 #include "compat_libevent.h"
 #include "ht.h"
@@ -1773,8 +1773,8 @@ typedef struct dir_connection_t {
   /** List of spooled_resource_t for objects that we're spooling. We use
    * it from back to front. */
   smartlist_t *spool;
-  /** The zlib object doing on-the-fly compression for spooled data. */
-  tor_zlib_state_t *zlib_state;
+  /** The compression object doing on-the-fly compression for spooled data. */
+  tor_compress_state_t *compress_state;
 
   /** What rendezvous service are we querying for? */
   rend_data_t *rend_data;
diff --git a/src/or/relay.c b/src/or/relay.c
index 5139036327..8524080939 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -54,6 +54,7 @@
 #include "circuitbuild.h"
 #include "circuitlist.h"
 #include "circuituse.h"
+#include "compress.h"
 #include "config.h"
 #include "connection.h"
 #include "connection_edge.h"
@@ -2453,7 +2454,7 @@ cell_queues_check_size(void)
 {
   size_t alloc = cell_queues_get_total_allocation();
   alloc += buf_get_total_allocation();
-  alloc += tor_zlib_get_total_allocation();
+  alloc += tor_compress_get_total_allocation();
   const size_t rend_cache_total = rend_cache_get_total_allocation();
   alloc += rend_cache_total;
   if (alloc >= get_options()->MaxMemInQueues_low_threshold) {
diff --git a/src/test/fuzz/include.am b/src/test/fuzz/include.am
index 1b608c6885..500377f6d7 100644
--- a/src/test/fuzz/include.am
+++ b/src/test/fuzz/include.am
@@ -18,7 +18,9 @@ FUZZING_LIBS = \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ \
 	@TOR_LIBEVENT_LIBS@ \
 	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ \
-	@TOR_SYSTEMD_LIBS@
+	@TOR_SYSTEMD_LIBS@ \
+	@TOR_LZMA_LIBS@ \
+	@TOR_ZSTD_LIBS@
 
 oss-fuzz-prereqs: \
 	src/or/libtor-testing.a \
diff --git a/src/test/include.am b/src/test/include.am
index 1b16d0f1a2..653adad300 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -180,7 +180,8 @@ src_test_test_switch_id_LDFLAGS = @TOR_LDFLAGS_zlib@
 src_test_test_switch_id_LDADD = \
 	src/common/libor-testing.a \
 	src/common/libor-ctime-testing.a \
-	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@
+	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ \
+	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@
 
 src_test_test_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ \
         @TOR_LDFLAGS_libevent@
@@ -194,7 +195,7 @@ src_test_test_LDADD = src/or/libtor-testing.a \
 	src/trunnel/libor-trunnel-testing.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \
 	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ \
-	@TOR_SYSTEMD_LIBS@
+	@TOR_SYSTEMD_LIBS@ @TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@
 
 src_test_test_slow_CPPFLAGS = $(src_test_test_CPPFLAGS)
 src_test_test_slow_CFLAGS = $(src_test_test_CFLAGS)
@@ -217,7 +218,7 @@ src_test_bench_LDADD = src/or/libtor.a src/common/libor.a \
 	src/common/libor-event.a src/trunnel/libor-trunnel.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \
 	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ \
-	@TOR_SYSTEMD_LIBS@
+	@TOR_SYSTEMD_LIBS@ @TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@
 
 src_test_test_workqueue_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ \
         @TOR_LDFLAGS_libevent@
@@ -227,7 +228,8 @@ src_test_test_workqueue_LDADD = src/or/libtor-testing.a \
 	src/common/libor-crypto-testing.a $(LIBKECCAK_TINY) $(LIBDONNA) \
 	src/common/libor-event-testing.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \
-	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@
+	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ \
+	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@
 
 src_test_test_timers_CPPFLAGS = $(src_test_test_CPPFLAGS)
 src_test_test_timers_CFLAGS = $(src_test_test_CFLAGS)
@@ -237,7 +239,8 @@ src_test_test_timers_LDADD = \
 	src/common/libor-event-testing.a \
 	src/common/libor-crypto-testing.a $(LIBKECCAK_TINY) $(LIBDONNA) \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \
-	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@
+	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ \
+	@TOR_LZMA_LIBS@
 src_test_test_timers_LDFLAGS = $(src_test_test_LDFLAGS)
 
 noinst_HEADERS+= \
@@ -262,7 +265,8 @@ src_test_test_ntor_cl_LDADD = src/or/libtor.a src/common/libor.a \
 	src/common/libor-ctime.a \
 	src/common/libor-crypto.a $(LIBKECCAK_TINY) $(LIBDONNA) \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ \
-	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@
+	@TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ \
+	@TOR_LZMA_LIBS@
 src_test_test_ntor_cl_AM_CPPFLAGS =	       \
 	-I"$(top_srcdir)/src/or"
 
diff --git a/src/test/test.c b/src/test/test.c
index 90e3d02f93..4d2cf1536b 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -44,13 +44,13 @@ double fabs(double x);
 #include "buffers.h"
 #include "circuitlist.h"
 #include "circuitstats.h"
+#include "compress.h"
 #include "config.h"
 #include "connection_edge.h"
 #include "geoip.h"
 #include "rendcommon.h"
 #include "rendcache.h"
 #include "test.h"
-#include "torgzip.h"
 #include "main.h"
 #include "memarea.h"
 #include "onion.h"
diff --git a/src/test/test_buffers.c b/src/test/test_buffers.c
index d14165c45c..43582d1b7a 100644
--- a/src/test/test_buffers.c
+++ b/src/test/test_buffers.c
@@ -584,22 +584,26 @@ test_buffers_zlib_impl(int finalize_with_nil)
   char *contents = NULL;
   char *expanded = NULL;
   buf_t *buf = NULL;
-  tor_zlib_state_t *zlib_state = NULL;
+  tor_compress_state_t *compress_state = NULL;
   size_t out_len, in_len;
   int done;
 
   buf = buf_new_with_capacity(128); /* will round up */
-  zlib_state = tor_zlib_new(1, ZLIB_METHOD, HIGH_COMPRESSION);
+  compress_state = tor_compress_new(1, ZLIB_METHOD, HIGH_COMPRESSION);
 
   msg = tor_malloc(512);
   crypto_rand(msg, 512);
-  tt_int_op(write_to_buf_zlib(buf, zlib_state, msg, 128, 0), OP_EQ, 0);
-  tt_int_op(write_to_buf_zlib(buf, zlib_state, msg+128, 128, 0), OP_EQ, 0);
-  tt_int_op(write_to_buf_zlib(buf, zlib_state, msg+256, 256, 0), OP_EQ, 0);
+  tt_int_op(write_to_buf_compress(buf, compress_state,
+                                  msg, 128, 0), OP_EQ, 0);
+  tt_int_op(write_to_buf_compress(buf, compress_state,
+                                  msg+128, 128, 0), OP_EQ, 0);
+  tt_int_op(write_to_buf_compress(buf, compress_state,
+                                  msg+256, 256, 0), OP_EQ, 0);
   done = !finalize_with_nil;
-  tt_int_op(write_to_buf_zlib(buf, zlib_state, "all done", 9, done), OP_EQ, 0);
+  tt_int_op(write_to_buf_compress(buf, compress_state,
+                                  "all done", 9, done), OP_EQ, 0);
   if (finalize_with_nil) {
-    tt_int_op(write_to_buf_zlib(buf, zlib_state, "", 0, 1), OP_EQ, 0);
+    tt_int_op(write_to_buf_compress(buf, compress_state, "", 0, 1), OP_EQ, 0);
   }
 
   in_len = buf_datalen(buf);
@@ -607,10 +611,10 @@ test_buffers_zlib_impl(int finalize_with_nil)
 
   tt_int_op(fetch_from_buf(contents, in_len, buf), OP_EQ, 0);
 
-  tt_int_op(0, OP_EQ, tor_gzip_uncompress(&expanded, &out_len,
-                                       contents, in_len,
-                                       ZLIB_METHOD, 1,
-                                       LOG_WARN));
+  tt_int_op(0, OP_EQ, tor_uncompress(&expanded, &out_len,
+                                     contents, in_len,
+                                     ZLIB_METHOD, 1,
+                                     LOG_WARN));
 
   tt_int_op(out_len, OP_GE, 128);
   tt_mem_op(msg, OP_EQ, expanded, 128);
@@ -621,7 +625,7 @@ test_buffers_zlib_impl(int finalize_with_nil)
 
  done:
   buf_free(buf);
-  tor_zlib_free(zlib_state);
+  tor_compress_free(compress_state);
   tor_free(contents);
   tor_free(expanded);
   tor_free(msg);
@@ -647,7 +651,7 @@ test_buffers_zlib_fin_at_chunk_end(void *arg)
   char *contents = NULL;
   char *expanded = NULL;
   buf_t *buf = NULL;
-  tor_zlib_state_t *zlib_state = NULL;
+  tor_compress_state_t *compress_state = NULL;
   size_t out_len, in_len;
   size_t sz, headerjunk;
   (void) arg;
@@ -666,8 +670,8 @@ test_buffers_zlib_fin_at_chunk_end(void *arg)
   tt_uint_op(buf->head->datalen, OP_EQ, headerjunk);
   tt_uint_op(buf_datalen(buf), OP_EQ, headerjunk);
   /* Write an empty string, with finalization on. */
-  zlib_state = tor_zlib_new(1, ZLIB_METHOD, HIGH_COMPRESSION);
-  tt_int_op(write_to_buf_zlib(buf, zlib_state, "", 0, 1), OP_EQ, 0);
+  compress_state = tor_compress_new(1, ZLIB_METHOD, HIGH_COMPRESSION);
+  tt_int_op(write_to_buf_compress(buf, compress_state, "", 0, 1), OP_EQ, 0);
 
   in_len = buf_datalen(buf);
   contents = tor_malloc(in_len);
@@ -676,17 +680,18 @@ test_buffers_zlib_fin_at_chunk_end(void *arg)
 
   tt_uint_op(in_len, OP_GT, headerjunk);
 
-  tt_int_op(0, OP_EQ, tor_gzip_uncompress(&expanded, &out_len,
-                                  contents + headerjunk, in_len - headerjunk,
-                                  ZLIB_METHOD, 1,
-                                  LOG_WARN));
+  tt_int_op(0, OP_EQ, tor_uncompress(&expanded, &out_len,
+                                     contents + headerjunk,
+                                     in_len - headerjunk,
+                                     ZLIB_METHOD, 1,
+                                     LOG_WARN));
 
   tt_int_op(out_len, OP_EQ, 0);
   tt_assert(expanded);
 
  done:
   buf_free(buf);
-  tor_zlib_free(zlib_state);
+  tor_compress_free(compress_state);
   tor_free(contents);
   tor_free(expanded);
   tor_free(msg);
diff --git a/src/test/test_dir_handle_get.c b/src/test/test_dir_handle_get.c
index cfda314693..392fa4dde0 100644
--- a/src/test/test_dir_handle_get.c
+++ b/src/test/test_dir_handle_get.c
@@ -14,6 +14,7 @@
 #include "connection.h"
 #include "directory.h"
 #include "test.h"
+#include "compress.h"
 #include "connection.h"
 #include "rendcommon.h"
 #include "rendcache.h"
@@ -28,7 +29,6 @@
 #include "networkstatus.h"
 #include "geoip.h"
 #include "dirserv.h"
-#include "torgzip.h"
 #include "dirvote.h"
 #include "log_test_helpers.h"
 
@@ -1832,8 +1832,8 @@ test_dir_handle_get_status_vote_current_consensus_ns(void* data)
                                                             comp_body_used);
   tt_int_op(ZLIB_METHOD, OP_EQ, compression);
 
-  tor_gzip_uncompress(&body, &body_used, comp_body, comp_body_used,
-                      compression, 0, LOG_PROTOCOL_WARN);
+  tor_uncompress(&body, &body_used, comp_body, comp_body_used,
+                 compression, 0, LOG_PROTOCOL_WARN);
 
   tt_str_op(NETWORK_STATUS, OP_EQ, body);
   tt_int_op(strlen(NETWORK_STATUS), OP_EQ, body_used);
diff --git a/src/test/test_util.c b/src/test/test_util.c
index 203f9dd1c4..1e33de82ae 100644
--- a/src/test/test_util.c
+++ b/src/test/test_util.c
@@ -2249,46 +2249,49 @@ test_util_gzip(void *arg)
   char *buf1=NULL, *buf2=NULL, *buf3=NULL, *cp1, *cp2;
   const char *ccp2;
   size_t len1, len2;
-  tor_zlib_state_t *state = NULL;
+  tor_compress_state_t *state = NULL;
 
   (void)arg;
+  tt_assert(tor_compress_supports_method(GZIP_METHOD));
+  tt_assert(tor_compress_supports_method(ZLIB_METHOD));
+
   buf1 = tor_strdup("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ");
   tt_assert(detect_compression_method(buf1, strlen(buf1)) == UNKNOWN_METHOD);
 
-  tt_assert(!tor_gzip_compress(&buf2, &len1, buf1, strlen(buf1)+1,
-                               GZIP_METHOD));
-  tt_assert(buf2);
-  tt_assert(len1 < strlen(buf1));
-  tt_assert(detect_compression_method(buf2, len1) == GZIP_METHOD);
+  tt_assert(!tor_compress(&buf2, &len1, buf1, strlen(buf1)+1,
+                          GZIP_METHOD));
+  tt_assert(buf2 != NULL);
+  tt_int_op(len1, OP_LT, strlen(buf1));
+  tt_int_op(detect_compression_method(buf2, len1), OP_EQ, GZIP_METHOD);
 
-  tt_assert(!tor_gzip_uncompress(&buf3, &len2, buf2, len1,
-                                 GZIP_METHOD, 1, LOG_INFO));
-  tt_assert(buf3);
-  tt_int_op(strlen(buf1) + 1,OP_EQ, len2);
-  tt_str_op(buf1,OP_EQ, buf3);
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1,
+                            GZIP_METHOD, 1, LOG_INFO));
+  tt_assert(buf3 != NULL);
+  tt_int_op(strlen(buf1) + 1, OP_EQ, len2);
+  tt_str_op(buf1, OP_EQ, buf3);
 
   tor_free(buf2);
   tor_free(buf3);
 
-  tt_assert(!tor_gzip_compress(&buf2, &len1, buf1, strlen(buf1)+1,
-                                 ZLIB_METHOD));
+  tt_assert(!tor_compress(&buf2, &len1, buf1, strlen(buf1)+1,
+                          ZLIB_METHOD));
   tt_assert(buf2);
-  tt_assert(detect_compression_method(buf2, len1) == ZLIB_METHOD);
+  tt_int_op(detect_compression_method(buf2, len1), OP_EQ, ZLIB_METHOD);
 
-  tt_assert(!tor_gzip_uncompress(&buf3, &len2, buf2, len1,
-                                   ZLIB_METHOD, 1, LOG_INFO));
-  tt_assert(buf3);
-  tt_int_op(strlen(buf1) + 1,OP_EQ, len2);
-  tt_str_op(buf1,OP_EQ, buf3);
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1,
+                            ZLIB_METHOD, 1, LOG_INFO));
+  tt_assert(buf3 != NULL);
+  tt_int_op(strlen(buf1) + 1, OP_EQ, len2);
+  tt_str_op(buf1, OP_EQ, buf3);
 
   /* Check whether we can uncompress concatenated, compressed strings. */
   tor_free(buf3);
   buf2 = tor_reallocarray(buf2, len1, 2);
   memcpy(buf2+len1, buf2, len1);
-  tt_assert(!tor_gzip_uncompress(&buf3, &len2, buf2, len1*2,
-                                   ZLIB_METHOD, 1, LOG_INFO));
-  tt_int_op((strlen(buf1)+1)*2,OP_EQ, len2);
-  tt_mem_op(buf3,OP_EQ,
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1*2,
+                            ZLIB_METHOD, 1, LOG_INFO));
+  tt_int_op((strlen(buf1)+1)*2, OP_EQ, len2);
+  tt_mem_op(buf3, OP_EQ,
              "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ\0"
              "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ\0",
              (strlen(buf1)+1)*2);
@@ -2300,53 +2303,53 @@ test_util_gzip(void *arg)
   /* Check whether we can uncompress partial strings. */
   buf1 =
     tor_strdup("String with low redundancy that won't be compressed much.");
-  tt_assert(!tor_gzip_compress(&buf2, &len1, buf1, strlen(buf1)+1,
-                                 ZLIB_METHOD));
-  tt_assert(len1>16);
+  tt_assert(!tor_compress(&buf2, &len1, buf1, strlen(buf1)+1,
+                          ZLIB_METHOD));
+  tt_int_op(len1, OP_GT, 16);
   /* when we allow an incomplete string, we should succeed.*/
-  tt_assert(!tor_gzip_uncompress(&buf3, &len2, buf2, len1-16,
-                                  ZLIB_METHOD, 0, LOG_INFO));
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1-16,
+                            ZLIB_METHOD, 0, LOG_INFO));
   tt_assert(len2 > 5);
   buf3[len2]='\0';
   tt_assert(!strcmpstart(buf1, buf3));
 
   /* when we demand a complete string, this must fail. */
   tor_free(buf3);
-  tt_assert(tor_gzip_uncompress(&buf3, &len2, buf2, len1-16,
-                                 ZLIB_METHOD, 1, LOG_INFO));
-  tt_assert(!buf3);
+  tt_assert(tor_uncompress(&buf3, &len2, buf2, len1-16,
+                           ZLIB_METHOD, 1, LOG_INFO));
+  tt_assert(buf3 == NULL);
 
   /* Now, try streaming compression. */
   tor_free(buf1);
   tor_free(buf2);
   tor_free(buf3);
-  state = tor_zlib_new(1, ZLIB_METHOD, HIGH_COMPRESSION);
+  state = tor_compress_new(1, ZLIB_METHOD, HIGH_COMPRESSION);
   tt_assert(state);
   cp1 = buf1 = tor_malloc(1024);
   len1 = 1024;
   ccp2 = "ABCDEFGHIJABCDEFGHIJ";
   len2 = 21;
-  tt_assert(tor_zlib_process(state, &cp1, &len1, &ccp2, &len2, 0)
-              == TOR_ZLIB_OK);
-  tt_int_op(0,OP_EQ, len2); /* Make sure we compressed it all. */
+  tt_int_op(tor_compress_process(state, &cp1, &len1, &ccp2, &len2, 0),
+            OP_EQ, TOR_COMPRESS_OK);
+  tt_int_op(0, OP_EQ, len2); /* Make sure we compressed it all. */
   tt_assert(cp1 > buf1);
 
   len2 = 0;
   cp2 = cp1;
-  tt_assert(tor_zlib_process(state, &cp1, &len1, &ccp2, &len2, 1)
-              == TOR_ZLIB_DONE);
-  tt_int_op(0,OP_EQ, len2);
+  tt_int_op(tor_compress_process(state, &cp1, &len1, &ccp2, &len2, 1),
+            OP_EQ, TOR_COMPRESS_DONE);
+  tt_int_op(0, OP_EQ, len2);
   tt_assert(cp1 > cp2); /* Make sure we really added something. */
 
-  tt_assert(!tor_gzip_uncompress(&buf3, &len2, buf1, 1024-len1,
-                                  ZLIB_METHOD, 1, LOG_WARN));
+  tt_assert(!tor_uncompress(&buf3, &len2, buf1, 1024-len1,
+                            ZLIB_METHOD, 1, LOG_WARN));
   /* Make sure it compressed right. */
   tt_str_op(buf3, OP_EQ, "ABCDEFGHIJABCDEFGHIJ");
-  tt_int_op(21,OP_EQ, len2);
+  tt_int_op(21, OP_EQ, len2);
 
  done:
   if (state)
-    tor_zlib_free(state);
+    tor_compress_free(state);
   tor_free(buf2);
   tor_free(buf3);
   tor_free(buf1);
@@ -2364,13 +2367,13 @@ test_util_gzip_compression_bomb(void *arg)
   char *one_mb = tor_malloc_zero(one_million);
   char *result = NULL;
   size_t result_len = 0;
-  tor_zlib_state_t *state = NULL;
+  tor_compress_state_t *state = NULL;
 
   /* Make sure we can't produce a compression bomb */
   setup_full_capture_of_logs(LOG_WARN);
-  tt_int_op(-1, OP_EQ, tor_gzip_compress(&result, &result_len,
-                                         one_mb, one_million,
-                                         ZLIB_METHOD));
+  tt_int_op(-1, OP_EQ, tor_compress(&result, &result_len,
+                                    one_mb, one_million,
+                                    ZLIB_METHOD));
   expect_single_log_msg_containing(
          "We compressed something and got an insanely high "
          "compression factor; other Tors would think this "
@@ -2381,27 +2384,251 @@ test_util_gzip_compression_bomb(void *arg)
   const char compression_bomb[1039] =
     { 0x78, 0xDA, 0xED, 0xC1, 0x31, 0x01, 0x00, 0x00, 0x00, 0xC2,
       0xA0, 0xF5, 0x4F, 0x6D, 0x08, 0x5F, 0xA0 /* .... */ };
-  tt_int_op(-1, OP_EQ, tor_gzip_uncompress(&result, &result_len,
-                                           compression_bomb, 1039,
-                                           ZLIB_METHOD, 0, LOG_WARN));
+  tt_int_op(-1, OP_EQ, tor_uncompress(&result, &result_len,
+                                      compression_bomb, 1039,
+                                      ZLIB_METHOD, 0, LOG_WARN));
 
   /* Now try streaming that. */
-  state = tor_zlib_new(0, ZLIB_METHOD, HIGH_COMPRESSION);
-  tor_zlib_output_t r;
+  state = tor_compress_new(0, ZLIB_METHOD, HIGH_COMPRESSION);
+  tor_compress_output_t r;
   const char *inp = compression_bomb;
   size_t inlen = 1039;
   do {
     char *outp = one_mb;
     size_t outleft = 4096; /* small on purpose */
-    r = tor_zlib_process(state, &outp, &outleft, &inp, &inlen, 0);
+    r = tor_compress_process(state, &outp, &outleft, &inp, &inlen, 0);
     tt_int_op(inlen, OP_NE, 0);
-  } while (r == TOR_ZLIB_BUF_FULL);
+  } while (r == TOR_COMPRESS_BUFFER_FULL);
 
-  tt_int_op(r, OP_EQ, TOR_ZLIB_ERR);
+  tt_int_op(r, OP_EQ, TOR_COMPRESS_ERROR);
 
  done:
   tor_free(one_mb);
-  tor_zlib_free(state);
+  tor_compress_free(state);
+}
+
+static void
+test_util_lzma(void *arg)
+{
+#ifdef HAVE_LZMA
+  char *buf1=NULL, *buf2=NULL, *buf3=NULL, *cp1, *cp2;
+  const char *ccp2;
+  size_t len1, len2;
+  tor_compress_state_t *state = NULL;
+
+  (void)arg;
+  tt_assert(tor_compress_supports_method(LZMA_METHOD));
+
+  buf1 = tor_strdup("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ");
+  tt_assert(detect_compression_method(buf1, strlen(buf1)) == UNKNOWN_METHOD);
+
+  tt_assert(!tor_compress(&buf2, &len1, buf1, strlen(buf1)+1,
+                          LZMA_METHOD));
+  tt_assert(buf2 != NULL);
+  tt_int_op(len1, OP_LT, strlen(buf1));
+  tt_int_op(detect_compression_method(buf2, len1), OP_EQ, LZMA_METHOD);
+
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1,
+                            LZMA_METHOD, 1, LOG_INFO));
+  tt_assert(buf3 != NULL);
+  tt_int_op(strlen(buf1) + 1, OP_EQ, len2);
+  tt_str_op(buf1, OP_EQ, buf3);
+
+  tor_free(buf1);
+  tor_free(buf2);
+  tor_free(buf3);
+
+#if 0
+  /* Check whether we can uncompress concatenated, compressed strings. */
+  tor_free(buf3);
+  buf2 = tor_reallocarray(buf2, len1, 2);
+  memcpy(buf2+len1, buf2, len1);
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1*2,
+                            LZMA_METHOD, 1, LOG_INFO));
+  tt_int_op((strlen(buf1)+1)*2, OP_EQ, len2);
+  tt_mem_op(buf3, OP_EQ,
+             "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ\0"
+             "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ\0",
+             (strlen(buf1)+1)*2);
+
+  tor_free(buf1);
+  tor_free(buf2);
+  tor_free(buf3);
+
+  /* Check whether we can uncompress partial strings. */
+  buf1 =
+    tor_strdup("String with low redundancy that won't be compressed much.");
+  tt_assert(!tor_compress(&buf2, &len1, buf1, strlen(buf1)+1,
+                          LZMA_METHOD));
+  tt_int_op(len1, OP_GT, 16);
+  /* when we allow an incomplete string, we should succeed.*/
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1-16,
+                            LZMA_METHOD, 0, LOG_INFO));
+  tt_assert(len2 > 5);
+  buf3[len2]='\0';
+  tt_assert(!strcmpstart(buf1, buf3));
+
+  /* when we demand a complete string, this must fail. */
+  tor_free(buf3);
+  tt_assert(tor_uncompress(&buf3, &len2, buf2, len1-16,
+                           LZMA_METHOD, 1, LOG_INFO));
+  tt_assert(buf3 == NULL);
+
+  tor_free(buf1);
+  tor_free(buf2);
+  tor_free(buf3);
+#endif
+
+  /* Now, try streaming compression. */
+  state = tor_compress_new(1, LZMA_METHOD, HIGH_COMPRESSION);
+  tt_assert(state);
+  cp1 = buf1 = tor_malloc(1024);
+  len1 = 1024;
+  ccp2 = "ABCDEFGHIJABCDEFGHIJ";
+  len2 = 21;
+  tt_int_op(tor_compress_process(state, &cp1, &len1, &ccp2, &len2, 0),
+            OP_EQ, TOR_COMPRESS_OK);
+  tt_int_op(0, OP_EQ, len2); /* Make sure we compressed it all. */
+  tt_assert(cp1 > buf1);
+
+  len2 = 0;
+  cp2 = cp1;
+  tt_int_op(tor_compress_process(state, &cp1, &len1, &ccp2, &len2, 1),
+            OP_EQ, TOR_COMPRESS_DONE);
+  tt_int_op(0, OP_EQ, len2);
+  tt_assert(cp1 > cp2); /* Make sure we really added something. */
+
+  tt_assert(!tor_uncompress(&buf3, &len2, buf1, 1024-len1,
+                            LZMA_METHOD, 1, LOG_WARN));
+  /* Make sure it compressed right. */
+  tt_str_op(buf3, OP_EQ, "ABCDEFGHIJABCDEFGHIJ");
+  tt_int_op(21, OP_EQ, len2);
+
+ done:
+  if (state)
+    tor_compress_free(state);
+  tor_free(buf2);
+  tor_free(buf3);
+  tor_free(buf1);
+#else
+  (void)arg;
+  tt_assert(! tor_compress_supports_method(LZMA_METHOD));
+
+ done:
+  ;
+#endif // HAVE_LZMA.
+}
+
+static void
+test_util_zstd(void *arg)
+{
+#ifdef HAVE_ZSTD
+  char *buf1=NULL, *buf2=NULL, *buf3=NULL, *cp1, *cp2;
+  const char *ccp2;
+  size_t len1, len2;
+  tor_compress_state_t *state = NULL;
+
+  (void)arg;
+  tt_assert(tor_compress_supports_method(ZSTD_METHOD));
+
+  buf1 = tor_strdup("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ");
+  tt_assert(detect_compression_method(buf1, strlen(buf1)) == UNKNOWN_METHOD);
+
+  tt_assert(!tor_compress(&buf2, &len1, buf1, strlen(buf1)+1,
+                          ZSTD_METHOD));
+  tt_assert(buf2 != NULL);
+  tt_int_op(len1, OP_LT, strlen(buf1));
+  tt_int_op(detect_compression_method(buf2, len1), OP_EQ, ZSTD_METHOD);
+
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1,
+                            ZSTD_METHOD, 1, LOG_INFO));
+  tt_assert(buf3 != NULL);
+  tt_int_op(strlen(buf1) + 1, OP_EQ, len2);
+  tt_str_op(buf1, OP_EQ, buf3);
+
+  tor_free(buf1);
+  tor_free(buf2);
+  tor_free(buf3);
+
+#if 0
+  /* Check whether we can uncompress concatenated, compressed strings. */
+  tor_free(buf3);
+  buf2 = tor_reallocarray(buf2, len1, 2);
+  memcpy(buf2+len1, buf2, len1);
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1*2,
+                            ZSTD_METHOD, 1, LOG_INFO));
+  tt_int_op((strlen(buf1)+1)*2, OP_EQ, len2);
+  tt_mem_op(buf3, OP_EQ,
+             "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ\0"
+             "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZAAAAAAAAAAAAAAAAAAAZ\0",
+             (strlen(buf1)+1)*2);
+
+  tor_free(buf1);
+  tor_free(buf2);
+  tor_free(buf3);
+
+  /* Check whether we can uncompress partial strings. */
+  buf1 =
+    tor_strdup("String with low redundancy that won't be compressed much.");
+  tt_assert(!tor_compress(&buf2, &len1, buf1, strlen(buf1)+1,
+                          ZSTD_METHOD));
+  tt_int_op(len1, OP_GT, 16);
+  /* when we allow an incomplete string, we should succeed.*/
+  tt_assert(!tor_uncompress(&buf3, &len2, buf2, len1-16,
+                            ZSTD_METHOD, 0, LOG_INFO));
+  tt_assert(len2 > 5);
+  buf3[len2]='\0';
+  tt_assert(!strcmpstart(buf1, buf3));
+
+  /* when we demand a complete string, this must fail. */
+  tor_free(buf3);
+  tt_assert(tor_uncompress(&buf3, &len2, buf2, len1-16,
+                           ZSTD_METHOD, 1, LOG_INFO));
+  tt_assert(buf3 == NULL);
+
+  tor_free(buf1);
+  tor_free(buf2);
+  tor_free(buf3);
+#endif
+
+  /* Now, try streaming compression. */
+  state = tor_compress_new(1, ZSTD_METHOD, HIGH_COMPRESSION);
+  tt_assert(state);
+  cp1 = buf1 = tor_malloc(1024);
+  len1 = 1024;
+  ccp2 = "ABCDEFGHIJABCDEFGHIJ";
+  len2 = 21;
+  tt_int_op(tor_compress_process(state, &cp1, &len1, &ccp2, &len2, 0),
+            OP_EQ, TOR_COMPRESS_OK);
+  tt_int_op(0, OP_EQ, len2); /* Make sure we compressed it all. */
+//  tt_assert(cp1 > buf1);
+
+  len2 = 0;
+  cp2 = cp1;
+  tt_int_op(tor_compress_process(state, &cp1, &len1, &ccp2, &len2, 1),
+            OP_EQ, TOR_COMPRESS_DONE);
+  tt_int_op(0, OP_EQ, len2);
+  tt_assert(cp1 > cp2); /* Make sure we really added something. */
+
+  tt_assert(!tor_uncompress(&buf3, &len2, buf1, 1024-len1,
+                            ZSTD_METHOD, 1, LOG_WARN));
+  /* Make sure it compressed right. */
+  tt_str_op(buf3, OP_EQ, "ABCDEFGHIJABCDEFGHIJ");
+  tt_int_op(21, OP_EQ, len2);
+
+ done:
+  if (state)
+    tor_compress_free(state);
+  tor_free(buf2);
+  tor_free(buf3);
+  tor_free(buf1);
+#else
+  (void)arg;
+  tt_assert(! tor_compress_supports_method(ZSTD_METHOD));
+
+ done:
+  ;
+#endif // HAVE_ZSTD.
 }
 
 /** Run unit tests for mmap() wrapper functionality. */
@@ -5717,6 +5944,8 @@ struct testcase_t util_tests[] = {
   UTIL_LEGACY(pow2),
   UTIL_LEGACY(gzip),
   UTIL_TEST(gzip_compression_bomb, TT_FORK),
+  UTIL_LEGACY(lzma),
+  UTIL_LEGACY(zstd),
   UTIL_LEGACY(datadir),
   UTIL_LEGACY(memarea),
   UTIL_LEGACY(control_formats),