folly/compression/Compression.h

   1 /*
   2  * Copyright 2013-present Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <cstdint>
  20 #include <limits>
  21 #include <memory>
  22 #include <string>
  23 #include <vector>
  24
  25 #include <folly/Optional.h>
  26 #include <folly/Range.h>
  27 #include <folly/io/IOBuf.h>
  28
  29 /**
  30  * Compression / decompression over IOBufs
  31  */
  32
  33 namespace folly {
  34 namespace io {
  35
  36 enum class CodecType {
  37   /**
  38    * This codec type is not defined; getCodec() will throw an exception
  39    * if used. Useful if deriving your own classes from Codec without
  40    * going through the getCodec() interface.
  41    */
  42   USER_DEFINED = 0,
  43
  44   /**
  45    * Use no compression.
  46    * Levels supported: 0
  47    */
  48   NO_COMPRESSION = 1,
  49
  50   /**
  51    * Use LZ4 compression.
  52    * Levels supported: 1 = fast, 2 = best; default = 1
  53    */
  54   LZ4 = 2,
  55
  56   /**
  57    * Use Snappy compression.
  58    * Levels supported: 1
  59    */
  60   SNAPPY = 3,
  61
  62   /**
  63    * Use zlib compression.
  64    * Levels supported: 0 = no compression, 1 = fast, ..., 9 = best; default = 6
  65    */
  66   ZLIB = 4,
  67
  68   /**
  69    * Use LZ4 compression, prefixed with size (as Varint).
  70    */
  71   LZ4_VARINT_SIZE = 5,
  72
  73   /**
  74    * Use LZMA2 compression.
  75    * Levels supported: 0 = no compression, 1 = fast, ..., 9 = best; default = 6
  76    */
  77   LZMA2 = 6,
  78   LZMA2_VARINT_SIZE = 7,
  79
  80   /**
  81    * Use ZSTD compression.
  82    */
  83   ZSTD = 8,
  84
  85   /**
  86    * Use gzip compression.  This is the same compression algorithm as ZLIB but
  87    * gzip-compressed files tend to be easier to work with from the command line.
  88    * Levels supported: 0 = no compression, 1 = fast, ..., 9 = best; default = 6
  89    */
  90   GZIP = 9,
  91
  92   /**
  93    * Use LZ4 frame compression.
  94    * Levels supported: 0 = fast, 16 = best; default = 0
  95    */
  96   LZ4_FRAME = 10,
  97
  98   /**
  99    * Use bzip2 compression.
 100    * Levels supported: 1 = fast, 9 = best; default = 9
 101    */
 102   BZIP2 = 11,
 103
 104   NUM_CODEC_TYPES = 12,
 105 };
 106
 107 class Codec {
 108  public:
 109   virtual ~Codec() { }
 110
 111   static constexpr uint64_t UNLIMITED_UNCOMPRESSED_LENGTH = uint64_t(-1);
 112   /**
 113    * Return the maximum length of data that may be compressed with this codec.
 114    * NO_COMPRESSION and ZLIB support arbitrary lengths;
 115    * LZ4 supports up to 1.9GiB; SNAPPY supports up to 4GiB.
 116    * May return UNLIMITED_UNCOMPRESSED_LENGTH if unlimited.
 117    */
 118   uint64_t maxUncompressedLength() const;
 119
 120   /**
 121    * Return the codec's type.
 122    */
 123   CodecType type() const { return type_; }
 124
 125   /**
 126    * Does this codec need the exact uncompressed length on decompression?
 127    */
 128   bool needsUncompressedLength() const;
 129
 130   /**
 131    * Compress data, returning an IOBuf (which may share storage with data).
 132    * Throws std::invalid_argument if data is larger than
 133    * maxUncompressedLength().
 134    */
 135   std::unique_ptr<IOBuf> compress(const folly::IOBuf* data);
 136
 137   /**
 138    * Compresses data. May involve additional copies compared to the overload
 139    * that takes and returns IOBufs. Has the same error semantics as the IOBuf
 140    * version.
 141    */
 142   std::string compress(StringPiece data);
 143
 144   /**
 145    * Uncompress data. Throws std::runtime_error on decompression error.
 146    *
 147    * Some codecs (LZ4) require the exact uncompressed length; this is indicated
 148    * by needsUncompressedLength().
 149    *
 150    * For other codes (zlib), knowing the exact uncompressed length ahead of
 151    * time might be faster.
 152    *
 153    * Regardless of the behavior of the underlying compressor, uncompressing
 154    * an empty IOBuf chain will return an empty IOBuf chain.
 155    */
 156   std::unique_ptr<IOBuf> uncompress(
 157       const IOBuf* data,
 158       folly::Optional<uint64_t> uncompressedLength = folly::none);
 159
 160   /**
 161    * Uncompresses data. May involve additional copies compared to the overload
 162    * that takes and returns IOBufs. Has the same error semantics as the IOBuf
 163    * version.
 164    */
 165   std::string uncompress(
 166       StringPiece data,
 167       folly::Optional<uint64_t> uncompressedLength = folly::none);
 168
 169   /**
 170    * Returns a bound on the maximum compressed length when compressing data with
 171    * the given uncompressed length.
 172    */
 173   uint64_t maxCompressedLength(uint64_t uncompressedLength) const;
 174
 175   /**
 176    * Extracts the uncompressed length from the compressed data if possible.
 177    * If the codec doesn't store the uncompressed length, or the data is
 178    * corrupted it returns the given uncompressedLength.
 179    * If the uncompressed length is stored in the compressed data and
 180    * uncompressedLength is not none and they do not match a std::runtime_error
 181    * is thrown.
 182    */
 183   folly::Optional<uint64_t> getUncompressedLength(
 184       const folly::IOBuf* data,
 185       folly::Optional<uint64_t> uncompressedLength = folly::none) const;
 186
 187  protected:
 188   explicit Codec(CodecType type);
 189
 190  public:
 191   /**
 192    * Returns a superset of the set of prefixes for which canUncompress() will
 193    * return true. A superset is allowed for optimizations in canUncompress()
 194    * based on other knowledge such as length. None of the prefixes may be empty.
 195    * default: No prefixes.
 196    */
 197   virtual std::vector<std::string> validPrefixes() const;
 198
 199   /**
 200    * Returns true if the codec thinks it can uncompress the data.
 201    * If a codec doesn't have magic bytes at the beginning, like LZ4 and Snappy,
 202    * it can always return false.
 203    * default: Returns false.
 204    */
 205   virtual bool canUncompress(
 206       const folly::IOBuf* data,
 207       folly::Optional<uint64_t> uncompressedLength = folly::none) const;
 208
 209  private:
 210   // default: no limits (save for special value UNKNOWN_UNCOMPRESSED_LENGTH)
 211   virtual uint64_t doMaxUncompressedLength() const;
 212   // default: doesn't need uncompressed length
 213   virtual bool doNeedsUncompressedLength() const;
 214   virtual std::unique_ptr<IOBuf> doCompress(const folly::IOBuf* data) = 0;
 215   virtual std::unique_ptr<IOBuf> doUncompress(
 216       const folly::IOBuf* data,
 217       folly::Optional<uint64_t> uncompressedLength) = 0;
 218   // default: an implementation is provided by default to wrap the strings into
 219   // IOBufs and delegate to the IOBuf methods. This incurs a copy of the output
 220   // from IOBuf to string. Implementers, at their discretion, can override
 221   // these methods to avoid the copy.
 222   virtual std::string doCompressString(StringPiece data);
 223   virtual std::string doUncompressString(
 224       StringPiece data,
 225       folly::Optional<uint64_t> uncompressedLength);
 226
 227   virtual uint64_t doMaxCompressedLength(uint64_t uncompressedLength) const = 0;
 228   // default: returns the passed uncompressedLength.
 229   virtual folly::Optional<uint64_t> doGetUncompressedLength(
 230       const folly::IOBuf* data,
 231       folly::Optional<uint64_t> uncompressedLength) const;
 232
 233   CodecType type_;
 234 };
 235
 236 class StreamCodec : public Codec {
 237  public:
 238   ~StreamCodec() override {}
 239
 240   /**
 241    * Does the codec need the data length before compression streaming?
 242    */
 243   bool needsDataLength() const;
 244
 245   /*****************************************************************************
 246    * Streaming API
 247    *****************************************************************************
 248    * A low-level stateful streaming API.
 249    * Streaming operations can be started in two ways:
 250    *   1. From a clean Codec on which no non-const methods have been called.
 251    *   2. A call to resetStream(), which will reset any codec to a clean state.
 252    * After a streaming operation has begun, either compressStream() or
 253    * uncompressStream() must be called until the streaming operation ends.
 254    * compressStream() ends when it returns true with flushOp END.
 255    * uncompressStream() ends when it returns true. At this point the codec
 256    * may be reused by calling resetStream().
 257    *
 258    * compress() and uncompress() can be called at any time, but they interrupt
 259    * any ongoing streaming operations (state is lost and resetStream() must be
 260    * called before another streaming operation).
 261    */
 262
 263   /**
 264    * Reset the state of the codec, and set the uncompressed length for the next
 265    * streaming operation. If uncompressedLength is not none it must be exactly
 266    * the uncompressed length. compressStream() must be passed exactly
 267    * uncompressedLength input bytes before the stream is ended.
 268    * uncompressStream() must be passed a compressed frame that uncompresses to
 269    * uncompressedLength.
 270    */
 271   void resetStream(folly::Optional<uint64_t> uncompressedLength = folly::none);
 272
 273   enum class FlushOp { NONE, FLUSH, END };
 274
 275   /**
 276    * Compresses some data from the input buffer and writes the compressed data
 277    * into the output buffer. It may read input without producing any output,
 278    * except when forced to flush.
 279    *
 280    * The input buffer is advanced to point to the range of data that hasn't yet
 281    * been read. Compression will resume at this point for the next call to
 282    * compressStream(). The output buffer is advanced one byte past the last byte
 283    * written.
 284    *
 285    * The default flushOp is NONE, which allows compressStream() complete
 286    * discretion in how much data to gather before writing any output.
 287    *
 288    * If flushOp is END, all pending and input data is flushed to the output
 289    * buffer, and the frame is ended. compressStream() must be called with the
 290    * same input and flushOp END until it returns true. At this point the caller
 291    * must call resetStream() to use the codec again.
 292    *
 293    * If flushOp is FLUSH, all pending and input data is flushed to the output
 294    * buffer, but the frame is not ended. compressStream() must be called with
 295    * the same input and flushOp END until it returns true. At this point the
 296    * caller can continue to compressStream() with any input data and flushOp.
 297    * The uncompressor, if passed all the produced output data, will be able to
 298    * uncompress all the input data passed to compressStream() so far. Excessive
 299    * use of flushOp FLUSH will deteriorate compression ratio. This is useful for
 300    * stateful streaming across a network. Most users don't need to use this
 301    * flushOp.
 302    *
 303    * A std::logic_error is thrown on incorrect usage of the API.
 304    * A std::runtime_error is thrown upon error conditions or if no forward
 305    * progress could be made twice in a row.
 306    */
 307   bool compressStream(
 308       folly::ByteRange& input,
 309       folly::MutableByteRange& output,
 310       FlushOp flushOp = StreamCodec::FlushOp::NONE);
 311
 312   /**
 313    * Uncompresses some data from the input buffer and writes the uncompressed
 314    * data into the output buffer. It may read input without producing any
 315    * output.
 316    *
 317    * The input buffer is advanced to point to the range of data that hasn't yet
 318    * been read. Uncompression will resume at this point for the next call to
 319    * uncompressStream(). The output buffer is advanced one byte past the last
 320    * byte written.
 321    *
 322    * The default flushOp is NONE, which allows uncompressStream() complete
 323    * discretion in how much output data to flush. The uncompressor may not make
 324    * maximum forward progress, but will make some forward progress when
 325    * possible.
 326    *
 327    * If flushOp is END, the caller guarantees that no more input will be
 328    * presented to uncompressStream(). uncompressStream() must be called with the
 329    * same input and flushOp END until it returns true. This is not mandatory,
 330    * but if the input is all available in one buffer, and there is enough output
 331    * space to write the entire frame, codecs can uncompress faster.
 332    *
 333    * If flushOp is FLUSH, uncompressStream() is guaranteed to make the maximum
 334    * amount of forward progress possible. When using this flushOp and
 335    * uncompressStream() returns with `!output.empty()` the caller knows that all
 336    * pending output has been flushed. This is useful for stateful streaming
 337    * across a network, and it should be used in conjunction with
 338    * compressStream() with flushOp FLUSH. Most users don't need to use this
 339    * flushOp.
 340    *
 341    * A std::runtime_error is thrown upon error conditions or if no forward
 342    * progress could be made upon two consecutive calls to the function (only the
 343    * second call will throw an exception).
 344    *
 345    * Returns true at the end of a frame. At this point resetStream() must be
 346    * called to reuse the codec.
 347    */
 348   bool uncompressStream(
 349       folly::ByteRange& input,
 350       folly::MutableByteRange& output,
 351       FlushOp flushOp = StreamCodec::FlushOp::NONE);
 352
 353  protected:
 354   explicit StreamCodec(CodecType type) : Codec(type) {}
 355
 356   // Returns the uncompressed length last passed to resetStream() or none if it
 357   // hasn't been called yet.
 358   folly::Optional<uint64_t> uncompressedLength() const {
 359     return uncompressedLength_;
 360   }
 361
 362  private:
 363   // default: Implemented using the streaming API.
 364   std::unique_ptr<IOBuf> doCompress(const folly::IOBuf* data) override;
 365   std::unique_ptr<IOBuf> doUncompress(
 366       const folly::IOBuf* data,
 367       folly::Optional<uint64_t> uncompressedLength) override;
 368
 369   // default: Returns false
 370   virtual bool doNeedsDataLength() const;
 371   virtual void doResetStream() = 0;
 372   virtual bool doCompressStream(
 373       folly::ByteRange& input,
 374       folly::MutableByteRange& output,
 375       FlushOp flushOp) = 0;
 376   virtual bool doUncompressStream(
 377       folly::ByteRange& input,
 378       folly::MutableByteRange& output,
 379       FlushOp flushOp) = 0;
 380
 381   enum class State {
 382     RESET,
 383     COMPRESS,
 384     COMPRESS_FLUSH,
 385     COMPRESS_END,
 386     UNCOMPRESS,
 387     END,
 388   };
 389   void assertStateIs(State expected) const;
 390
 391   State state_{State::RESET};
 392   ByteRange previousInput_{};
 393   folly::Optional<uint64_t> uncompressedLength_{};
 394   bool progressMade_{true};
 395 };
 396
 397 constexpr int COMPRESSION_LEVEL_FASTEST = -1;
 398 constexpr int COMPRESSION_LEVEL_DEFAULT = -2;
 399 constexpr int COMPRESSION_LEVEL_BEST = -3;
 400
 401 /**
 402  * Return a codec for the given type. Throws on error.  The level
 403  * is a non-negative codec-dependent integer indicating the level of
 404  * compression desired, or one of the following constants:
 405  *
 406  * COMPRESSION_LEVEL_FASTEST is fastest (uses least CPU / memory,
 407  *   worst compression)
 408  * COMPRESSION_LEVEL_DEFAULT is the default (likely a tradeoff between
 409  *   FASTEST and BEST)
 410  * COMPRESSION_LEVEL_BEST is the best compression (uses most CPU / memory,
 411  *   best compression)
 412  *
 413  * When decompressing, the compression level is ignored. All codecs will
 414  * decompress all data compressed with the a codec of the same type, regardless
 415  * of compression level.
 416  */
 417 std::unique_ptr<Codec> getCodec(
 418     CodecType type,
 419     int level = COMPRESSION_LEVEL_DEFAULT);
 420
 421 /**
 422  * Return a codec for the given type. Throws on error.  The level
 423  * is a non-negative codec-dependent integer indicating the level of
 424  * compression desired, or one of the following constants:
 425  *
 426  * COMPRESSION_LEVEL_FASTEST is fastest (uses least CPU / memory,
 427  *   worst compression)
 428  * COMPRESSION_LEVEL_DEFAULT is the default (likely a tradeoff between
 429  *   FASTEST and BEST)
 430  * COMPRESSION_LEVEL_BEST is the best compression (uses most CPU / memory,
 431  *   best compression)
 432  *
 433  * When decompressing, the compression level is ignored. All codecs will
 434  * decompress all data compressed with the a codec of the same type, regardless
 435  * of compression level.
 436  */
 437 std::unique_ptr<StreamCodec> getStreamCodec(
 438     CodecType type,
 439     int level = COMPRESSION_LEVEL_DEFAULT);
 440
 441 /**
 442  * Returns a codec that can uncompress any of the given codec types as well as
 443  * {LZ4_FRAME, ZSTD, ZLIB, GZIP, LZMA2, BZIP2}. Appends each default codec to
 444  * customCodecs in order, so long as a codec with the same type() isn't already
 445  * present in customCodecs or as the terminalCodec. When uncompress() is called,
 446  * each codec's canUncompress() is called in the order that they are given.
 447  * Appended default codecs are checked last.  uncompress() is called on the
 448  * first codec whose canUncompress() returns true.
 449  *
 450  * In addition, an optional `terminalCodec` can be provided. This codec's
 451  * uncompress() will be called either when no other codec canUncompress() the
 452  * data or the chosen codec throws an exception on the data. The terminalCodec
 453  * is intended for ambiguous headers, when canUncompress() is false for some
 454  * data it can actually uncompress. The terminalCodec does not need to override
 455  * validPrefixes() or canUncompress() and overriding these functions will have
 456  * no effect on the returned codec's validPrefixes() or canUncompress()
 457  * functions. The terminalCodec's needsUncompressedLength() and
 458  * maxUncompressedLength() will affect the returned codec's respective
 459  * functions. The terminalCodec must not be duplicated in customCodecs.
 460  *
 461  * An exception is thrown if no codec canUncompress() the data and either no
 462  * terminal codec was provided or a terminal codec was provided and it throws on
 463  * the data.
 464  * An exception is thrown if the chosen codec's uncompress() throws on the data
 465  * and either no terminal codec was provided or a terminal codec was provided
 466  * and it also throws on the data.
 467  * An exception is thrown if compress() is called on the returned codec.
 468  *
 469  * Requirements are checked in debug mode and are as follows:
 470  * Let headers be the concatenation of every codec's validPrefixes().
 471  *  1. Each codec must override validPrefixes() and canUncompress().
 472  *  2. No codec's validPrefixes() may be empty.
 473  *  3. No header in headers may be empty.
 474  *  4. headers must not contain any duplicate elements.
 475  *  5. No strict non-empty prefix of any header in headers may be in headers.
 476  *  6. The terminalCodec's type must not be the same as any other codec's type
 477  *     (with USER_DEFINED being the exception).
 478  */
 479 std::unique_ptr<Codec> getAutoUncompressionCodec(
 480     std::vector<std::unique_ptr<Codec>> customCodecs = {},
 481     std::unique_ptr<Codec> terminalCodec = {});
 482
 483 /**
 484  * Check if a specified codec is supported.
 485  */
 486 bool hasCodec(CodecType type);
 487
 488 /**
 489  * Check if a specified codec is supported and supports streaming.
 490  */
 491 bool hasStreamCodec(CodecType type);
 492 } // namespace io
 493 } // namespace folly