net: add CRL filter infrastructure.

This doesn't plumb anything in yet, it just runs unittests.

BUG=none
TEST=net_unittests

Review URL: http://codereview.chromium.org/6965015

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@87676 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 1176 insertions, 0 deletions

diff --git a/net/base/crl_filter.cc b/net/base/crl_filter.cc
new file mode 100644
index 0000000..82ef8eb
--- /dev/null
+++ b/net/base/crl_filter.cc
@@ -0,0 +1,854 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/base64.h"
+#include "base/json/json_reader.h"
+#include "base/logging.h"
+#include "base/values.h"
+#include "crypto/sha2.h"
+#include "net/base/crl_filter.h"
+
+#if defined(USE_SYSTEM_ZLIB)
+#include <zlib.h>
+#else
+#include "third_party/zlib/zlib.h"
+#endif
+
+namespace net {
+
+// Decompress zlib decompressed |in| into |out|. |out_len| is the number of
+// bytes at |out| and must be exactly equal to the size of the decompressed
+// data. |dict| optionally contains a pre-shared dictionary.
+static bool DecompressZlib(char* out, int out_len, base::StringPiece in,
+                           base::StringPiece dict) {
+  z_stream z;
+  memset(&z, 0, sizeof(z));
+
+  z.next_in = reinterpret_cast<Bytef*>(const_cast<char*>(in.data()));
+  z.avail_in = in.size();
+  z.next_out = reinterpret_cast<Bytef*>(out);
+  z.avail_out = out_len;
+
+  if (inflateInit(&z) != Z_OK)
+    return false;
+  int r = inflate(&z, Z_FINISH);
+  if (r == Z_NEED_DICT) {
+    r = inflateSetDictionary(&z, reinterpret_cast<const Bytef*>(dict.data()),
+                             dict.size());
+    if (r != Z_OK)
+      return false;
+    r = inflate(&z, Z_FINISH);
+  }
+  if (r != Z_STREAM_END)
+    return false;
+  if (z.avail_in || z.avail_out)
+    return false;
+  return true;
+}
+
+/* A RangeDecoder is a type of entropy coder. It is superior to a Huffman
+ * encoder because symbols can use fractions of bits.
+ *
+ * Conceptually a number range is split into regions with one region for each
+ * symbol. The size of the region is proportional to the probability of the
+ * symbol:
+ *
+ * +-----+  <- 2**32 - 1
+ * |     |
+ * |  B  |
+ * |     |
+ * +-----+  <- 2**30
+ * |  A  |
+ * +-----+  <- 0
+ *
+ * Here, symbol B is 3 times more probable than A.
+ *
+ * This pattern is recursive: it repeats inside each region:
+ *
+ * +-----+    /+-----+
+ * |     |   / |     |
+ * |  B  |  /  |  B  |
+ * |     | /   |     |
+ * +-----+/    +-----+
+ * |  A  |     |  A  |
+ * +-----+-----+-----+
+ *
+ * In this implementation, the probabilities are fixed and so are the same at
+ * every level.
+ *
+ * A range coder encodes a series of symbols by specifing a fraction along the
+ * number space such that it hits the correct symbols in order. You have to
+ * know how many symbols to expect from a range coder because it obviously
+ * produces an infinite series of symbols from any input value.
+ *
+ * In order to make the implementation fast on a computer, a high and low point
+ * are maintained that cover the current valid span of the number space.
+ * Whenever the span is small enough to that the most significant 8 bits of the
+ * high and low values are equal, a byte is produced and the current span is
+ * expanded by a factor of 256.
+ *
+ * A decoder reads these bytes and decodes symbols as required. For example,
+ * say that it reads the first byte as 0x80. It knows that the maximum value of
+ * the final span is 0x80fffffff... and the minimum value is 0x8000000...
+ * That's sufficient to figure out that the first symbol is a B.
+ *
+ * In the following, we keep track of these values:
+ *   high_, low_: the high and low values of the current span. This is needed
+ *       to mirror the state of the encoder so that span expansions occur at
+ *       the same point.
+ *
+ *   vhigh_, vlow_: the high and low values of the possible final span.
+ *   vbits_: the number of bits of |vhigh_| and |vlow_| that are from data.
+ *       (The rest of those values is filled with 0xff or 0x00, respectively.)
+ */
+class RangeDecoder {
+ public:
+  // in: the input bytes
+  // spans: the probabilities of the symbols. The sum of these values must
+  //     equal 2**32 - 1.
+  RangeDecoder(base::StringPiece in, const std::vector<uint32> spans)
+      : in_(in),
+        spans_(spans),
+        high_(-1),
+        vhigh_(-1),
+        low_(0),
+        vlow_(0),
+        vbits_(0) {
+  }
+
+  bool Decode(unsigned* out_symbol) {
+    // high_ and low_ mirror the state of the encoder so, when they agree on
+    // the first byte, we have to perform span expansion.
+    while (high_ >> 24 == low_ >> 24) {
+      vhigh_ <<= 8;
+      vhigh_ |= 0xff;
+      vlow_ <<= 8;
+      vbits_ -= 8;
+
+      high_ <<= 8;
+      high_ |= 0xff;
+      low_ <<= 8;
+    }
+
+    // r is the range of the current span, used as a scaling factor.
+    uint64 r = high_ - low_;
+
+    // We consider each symbol in turn and decide if the final span is such
+    // that it must be the next symbol.
+    for (unsigned i = 0; i < spans_.size(); i++) {
+      const uint32 span = spans_[i];
+      const uint32 scaled = (r * span) >> 32;
+
+      // Since our knowledge of the final span is incremental, |vhigh_| and
+      // |vlow_| might be sufficiently far apart that we can't determine the
+      // next symbol. In this case we have to read more data.
+      while (vhigh_ > low_ + scaled && vlow_ <= low_ + scaled) {
+        // We need more information to disambiguate this. Note that 32-bits of
+        // information is always sufficient to disambiguate.
+        uint32 b = 0;
+        if (!in_.empty())
+          b = static_cast<uint8>(in_[0]);
+        in_.remove_prefix(1);
+        vhigh_ &= ~(static_cast<uint32>(0xff) << (24 - vbits_));
+        vhigh_ |= b << (24 - vbits_);
+        vlow_ |= b << (24 - vbits_);
+        vbits_ += 8;
+      }
+
+      // This symbol covers all the possible values for the final span, so this
+      // must be the next symbol.
+      if (vhigh_ <= low_ + scaled) {
+        high_ = low_ + scaled;
+        *out_symbol = i;
+        return true;
+      }
+
+      low_ += scaled + 1;
+    }
+
+    // Since the sum of |spans_| equals 2**32-1, one of the symbols must cover
+    // the current span.
+    NOTREACHED();
+    return false;
+  }
+
+ private:
+  base::StringPiece in_;
+  const std::vector<uint32> spans_;
+
+  uint32 high_, vhigh_, low_, vlow_;
+  unsigned vbits_;
+
+  DISALLOW_COPY_AND_ASSIGN(RangeDecoder);
+};
+
+// A GolombCompressedSet is built from a set of random hash values where each
+// value is less than a pre-agreed limit. Since the hash values are uniform,
+// their differences are geometrically distributed and golomb encoding is the
+// optimal encoding for geometrically distributed values.
+//
+// Thus the set [1, 10, 15] is turned into delta values ([1, 9, 5]) and each
+// delta value is Golomb encoded to make a GCS.
+//
+// Golomb encoding of a value, v, requires knowledge of the geometric
+// parameter, M, and consists of (q, r) where v = qM + r. q is unary encoded
+// and r is binary encoded. In this code M is fixed at 1024.
+//
+// A couple of implementation tricks are used to speed things up:
+//
+// First, the bits are consumed in blocks of 32 and are little endian encoded,
+// thus saving a endianness conversion on most systems. Also, the bits inside
+// each word are ordered such that the first bit is the least-significant bit
+// and the unary encoding is terminated with a 1 rather than the usual 0.
+// This allows us to use a DeBruijn sequence to do unary decoding.
+class GolombCompressedSet {
+ public:
+  class iterator {
+   public:
+    iterator(base::StringPiece data, unsigned num_values)
+        : full_data_(data),
+          num_values_(num_values) {
+      Reset();
+    }
+
+    void Reset() {
+      data_ = full_data_;
+      pending_ = 0;
+      bits_pending_ = 0;
+      current_ = 0;
+    }
+
+    bool Next(uint64* out) {
+      unsigned q, r;
+      if (!ReadUnary(&q))
+        return false;
+      if (!ReadBinary10(&r))
+        return false;
+
+      uint64 step = static_cast<uint64>(q) << 10;
+      step |= r;
+      current_ += step;
+      *out = current_;
+      return true;
+    }
+
+    bool NextDelta(unsigned* out_delta) {
+      unsigned q, r;
+      if (!ReadUnary(&q))
+        return false;
+      if (!ReadBinary10(&r))
+        return false;
+
+      *out_delta = static_cast<unsigned>(q) << 10;
+      *out_delta |= r;
+      return true;
+    }
+
+    bool Contains(uint64 v) {
+      Reset();
+
+      uint64 value;
+      for (unsigned i = 0; i < num_values_; i++) {
+        if (!Next(&value))
+          return false;
+        if (value == v)
+          return true;
+        if (value > v)
+          return false;
+      }
+
+      return false;
+    }
+
+   private:
+    bool ReadUnary(unsigned* out) {
+      *out = 0;
+
+      uint32 w;
+      if (!CurrentWord(&w))
+        return false;
+
+      while (w == 0) {
+        *out += 32;
+        if (!CurrentWord(&w))
+          return false;
+      }
+
+      // A DeBruijn sequence contains all possible subsequences. kDeBruijn is an
+      // example of a 32-bit word that contains all possible 5-bit subsequences.
+      // When decoding Golomb values, we quickly need to find the number of
+      // consequtive zero bits. (w&-w) results in a word with only the
+      // least-significant true bit set. Since this work has only a single bit
+      // set, its value is a power of two and multiplying by it is the same as a
+      // left shift by the position of that bit.
+      //
+      // Thus we multiply (i.e. left-shift) by the DeBruijn value and check the
+      // top 5 bits. Since each 5-bit subsequence in kDeBruijn is unique, we can
+      // determine by how many bits it has been shifted with a lookup table.
+      static const uint32 kDeBruijn = 0x077CB531;
+      static const uint8 kDeBruijnLookup[32] = {
+        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
+      };
+
+      MSVC_SUPPRESS_WARNING(4146);
+      uint8 r = kDeBruijnLookup[((w & -w) * kDeBruijn) >> 27];
+      *out += r;
+      pending_ >>= r + 1;
+      bits_pending_ -= r + 1;
+      return true;
+    }
+
+    bool ReadBinary10(unsigned* out) {
+      uint32 w;
+      if (!CurrentWord(&w))
+        return false;
+      *out = w & 0x3ff;
+      pending_ >>= 10;
+      bits_pending_ -= 10;
+      return true;
+    }
+
+    bool CurrentWord(uint32* out) {
+      if (bits_pending_ < 32) {
+        if (!ReadWord() && bits_pending_ == 0)
+          return false;
+      }
+      *out = static_cast<uint32>(pending_);
+      return true;
+    }
+
+    bool ReadWord() {
+      DCHECK_LE(bits_pending_, 32u);
+
+      uint32 w;
+      if (data_.size() < 4)
+        return false;
+      memcpy(&w, data_.data(), 4);
+      data_.remove_prefix(4);
+
+      uint64 w64 = w;
+      w64 <<= bits_pending_;
+      pending_ |= w64;
+      bits_pending_ += 32;
+      return true;
+    }
+
+    base::StringPiece full_data_;
+    base::StringPiece data_;
+    const unsigned num_values_;
+    uint64 pending_;
+    unsigned bits_pending_;
+    uint32 current_;
+  };
+
+  GolombCompressedSet(base::StringPiece data,
+                      unsigned num_values)
+      : full_data_(data),
+        num_values_(num_values) {
+  }
+
+  iterator begin() const {
+    return iterator(full_data_, num_values_);
+  }
+
+ private:
+
+  base::StringPiece full_data_;
+  const unsigned num_values_;
+
+  DISALLOW_COPY_AND_ASSIGN(GolombCompressedSet);
+};
+
+// BitWriter buffers a number of bits in a format that matches
+// GolombCompressedSet's expectations: the bits are packed least-significant
+// first in little-endian, 32-bit words.
+class BitWriter {
+ public:
+  BitWriter()
+      : buf_(NULL),
+        buf_len_(0),
+        buf_used_(0),
+        current_(0),
+        num_bits_(0) {
+  }
+
+  void WriteBit(bool b) {
+    current_ >>= 1;
+    if (b)
+      current_ |= 0x80000000u;
+    num_bits_++;
+
+    if (num_bits_ == sizeof(current_) * 8)
+      Flush();
+  }
+
+  // WriteGolomb10 outputs v using Golomb encoding with a geometric parameter
+  // of 1024.
+  void WriteGolomb10(unsigned v) {
+    const unsigned q = v >> 10;
+    unsigned r = v & 0x3ff;
+
+    for (unsigned i = 0; i < q; i++)
+      WriteBit(false);
+    WriteBit(true);
+    for (unsigned i = 0; i < 10; i++) {
+      WriteBit((r&1) == 1);
+      r >>= 1;
+    }
+  }
+
+  void Flush() {
+    if (num_bits_ > 0) {
+      current_ >>= 32 - num_bits_;
+    }
+
+    if (buf_len_ < buf_used_ + sizeof(current_)) {
+      if (buf_) {
+        buf_len_ += sizeof(current_);
+        buf_len_ *= 2;
+        buf_ = reinterpret_cast<uint8*>(realloc(buf_, buf_len_));
+      } else {
+        buf_len_ = 1024;
+        buf_ = reinterpret_cast<uint8*>(malloc(buf_len_));
+      }
+    }
+    // assumes little endian
+    memcpy(buf_ + buf_used_, &current_, sizeof(current_));
+    buf_used_ += sizeof(current_);
+
+    current_ = 0;
+    num_bits_ = 0;
+  }
+
+  std::string as_string() {
+    Flush();
+    return std::string(reinterpret_cast<char*>(buf_), buf_used_);
+  }
+
+ private:
+  uint8* buf_;
+  unsigned buf_len_;
+  unsigned buf_used_;
+  uint32 current_;
+  unsigned num_bits_;
+};
+
+CRLFilter::~CRLFilter() {
+}
+
+// CRL filter format:
+//
+// uint16le description_len
+// byte[description_len] description_bytes
+// byte[] compressed_header
+// byte[] gcs_bytes
+//
+// description_bytes consists of a JSON dictionary with the following keys:
+//   Version (int): currently 0
+//   Contents (string): "CRLFilter" or "CRLFilterDelta" (magic value)
+//   DeltaFrom (int); if this is a delta filter (see below), then this contains
+//       the sequence number of the reference filter.
+//   HeaderZLength (int): the number of bytes of compressed header.
+//   HeaderLength (int): the number of bytes of header after decompression.
+//   RangeLength (int): if this is a delta filter then this is the number of
+//       bytes of range coded data.
+//
+// The uncompressed header is also a JSON dictionary with the following keys:
+//   Sequence (int): the sequence number of this filter.
+//   Version (int): currently 0.
+//   NotBefore (int, epoch seconds): the filter is not valid before this time.
+//   NotAfter (int, epoch seconds): the filter is not valid after this time.
+//   MaxRange (int): the limit of the GCS encoded values
+//   NumEntries (int): the number of GCS entries
+//
+//   CRLsIncluded (array): the covered CRLs. Each element in the array is a
+//       dictionary with the following keys:
+//
+//       URL (string): the URL of the CRL
+//       ParentSPKISHA256 (string): base64 encoded, SHA256 hash of the CRL
+//           signer's SPKI.
+//
+// A delta CRL filter is similar to a CRL filter:
+//
+// uint16le description_len
+// byte[description_len] description_bytes
+// byte[] delta_compressed_header
+// uint32le[3] range_probabilities
+// byte[] range_bytes
+// byte[] gcs_bytes
+//
+// A delta CRL filter applies to a specific CRL filter as given in the
+// description's "DeltaFrom" value. The compressed header is compressed with
+// the header bytes of the base CRL filter given as a zlib preshared
+// dictionary.
+//
+// range_probabilities contains the probabilies of the three encoded symbols.
+// The sum of these values must be 0xffffffff. Next are the range encoded
+// bytes, the length of which is given in "RangeLength". There's one symbol for
+// each GCS value in the final filter. (This number is given in the
+// "NumEntries" value of the header.). Each symbol is either SAME (0), INSERT
+// (1) or DELETE (2). SAME values are copied into the new filter, INSERTed
+// values are given as a delta from the last value, GCS encoded in |gcs_bytes|.
+// DELETEed values are omitted from the final filter.
+
+// ReadDescription reads the description (including length prefix) from |data|
+// and updates |data| to remove the description on return. Caller takes
+// ownership of the returned pointer.
+static DictionaryValue* ReadDescription(base::StringPiece* data) {
+  if (data->size() < 2)
+    return NULL;
+  uint16 description_len;
+  memcpy(&description_len, data->data(), 2);  // assumes little-endian.
+  data->remove_prefix(2);
+
+  if (data->size() < description_len)
+    return NULL;
+
+  const base::StringPiece description_bytes(data->data(), description_len);
+  data->remove_prefix(description_len);
+
+  scoped_ptr<Value> description(base::JSONReader::Read(
+      description_bytes.as_string(), true /* allow trailing comma */));
+  if (description.get() == NULL)
+    return NULL;
+
+  if (!description->IsType(Value::TYPE_DICTIONARY))
+    return NULL;
+  return reinterpret_cast<DictionaryValue*>(description.release());
+}
+
+// CRLFilterFromHeader constructs a CRLFilter from the bytes of a header
+// structures. The header is JSON. See above for details of the keys.
+//
+// static
+CRLFilter* CRLFilter::CRLFilterFromHeader(base::StringPiece header_bytes) {
+  scoped_ptr<Value> header(base::JSONReader::Read(
+      header_bytes.as_string(),
+      true /* allow trailing comma */));
+  if (header.get() == NULL)
+    return NULL;
+
+  if (!header->IsType(Value::TYPE_DICTIONARY))
+    return NULL;
+  DictionaryValue* header_dict =
+      reinterpret_cast<DictionaryValue*>(header.get());
+  int version;
+  if (!header_dict->GetInteger("Version", &version) ||
+      version != 0) {
+    return NULL;
+  }
+
+  double not_before, not_after, max_range, num_entries;
+  if (!header_dict->GetDouble("NotBefore", &not_before) ||
+      !header_dict->GetDouble("NotAfter", &not_after) ||
+      !header_dict->GetDouble("NumEntries", &num_entries) ||
+      !header_dict->GetDouble("MaxRange", &max_range)) {
+    return NULL;
+  }
+
+  if (not_before <= 0 || not_after <= 0 || max_range <= 0 || num_entries <= 0)
+    return NULL;
+
+  int sequence;
+  if (!header_dict->GetInteger("Sequence", &sequence) ||
+      sequence <= 0) {
+    // Sequence is assumed to be zero if omitted.
+    sequence = 0;
+  }
+
+  scoped_ptr<CRLFilter> crl_filter(new CRLFilter);
+  crl_filter->sequence_ = sequence;
+  crl_filter->not_before_ = not_before;
+  crl_filter->not_after_ = not_after;
+  crl_filter->max_range_ = max_range;
+  crl_filter->num_entries_ = num_entries;
+  crl_filter->header_bytes_ = header_bytes.as_string();
+
+  ListValue* crls_included;
+  if (!header_dict->GetList("CRLsIncluded", &crls_included))
+    return NULL;
+
+  for (size_t i = 0; i < crls_included->GetSize(); i++) {
+    DictionaryValue* included_crl_dict;
+    if (!crls_included->GetDictionary(i, &included_crl_dict))
+      return NULL;
+    std::string url, parent_spki_sha256_b64;
+    if (!included_crl_dict->GetString("URL", &url) ||
+        !included_crl_dict->GetString("ParentSPKISHA256",
+                                      &parent_spki_sha256_b64)) {
+      return NULL;
+    }
+
+    std::string parent_spki_sha256;
+    if (!base::Base64Decode(parent_spki_sha256_b64,
+                            &parent_spki_sha256)) {
+      return NULL;
+    }
+    crl_filter->crls_included_.insert(
+        std::make_pair<std::string, std::string>(
+          url,
+          parent_spki_sha256));
+  }
+
+  return crl_filter.release();
+}
+
+// kMaxHeaderLengthBytes contains the sanity limit of the size of a CRL
+// filter's decompressed header.
+static const int kMaxHeaderLengthBytes = 1024 * 1024;
+
+// static
+CRLFilter* CRLFilter::Parse(base::StringPiece data) {
+  // Other parts of Chrome assume that we're little endian, so we don't lose
+  // anything by doing this.
+#if defined(__BYTE_ORDER)
+  // Linux check
+  COMPILE_ASSERT(__BYTE_ORDER == __LITTLE_ENDIAN,
+                 datapack_assumes_little_endian);
+#elif defined(__BIG_ENDIAN__)
+  // Mac check
+  #error DataPack assumes little endian
+#endif
+
+  scoped_ptr<DictionaryValue> description_dict(
+      ReadDescription(&data));
+  if (!description_dict.get())
+    return NULL;
+
+  std::string contents;
+  if (!description_dict->GetString("Contents", &contents))
+    return NULL;
+  if (contents != "CRLFilter")
+    return NULL;
+
+  int version;
+  if (!description_dict->GetInteger("Version", &version) ||
+      version != 0) {
+    return NULL;
+  }
+
+  int compressed_header_len;
+  if (!description_dict->GetInteger("HeaderZLength", &compressed_header_len))
+    return NULL;
+
+  if (compressed_header_len <= 0 ||
+      data.size() < static_cast<unsigned>(compressed_header_len)) {
+    return NULL;
+  }
+  const base::StringPiece compressed_header(data.data(), compressed_header_len);
+  data.remove_prefix(compressed_header_len);
+
+  int header_len;
+  if (!description_dict->GetInteger("HeaderLength", &header_len))
+    return NULL;
+  if (header_len < 0 || header_len > kMaxHeaderLengthBytes) {
+    NOTREACHED();
+    return NULL;
+  }
+
+  scoped_array<char> header_bytes(new char[header_len]);
+  base::StringPiece no_dict;
+  if (!DecompressZlib(header_bytes.get(), header_len, compressed_header,
+                      no_dict)) {
+    return NULL;
+  }
+
+  scoped_refptr<CRLFilter> crl_filter(CRLFilterFromHeader(
+        base::StringPiece(header_bytes.get(), header_len)));
+
+  if (!crl_filter.get())
+    return NULL;
+
+  // The remainder is the Golomb Compressed Set.
+  crl_filter->gcs_bytes_ = data.as_string();
+  crl_filter->gcs_.reset(new GolombCompressedSet(crl_filter->gcs_bytes_,
+                                                 crl_filter->num_entries_));
+  return crl_filter.release();
+}
+
+CRLFilter* CRLFilter::ApplyDelta(base::StringPiece data) {
+  scoped_ptr<DictionaryValue> description_dict(
+      ReadDescription(&data));
+  if (!description_dict.get())
+    return NULL;
+
+  int compressed_header_len, header_len, delta_from, version, range_length;
+  std::string contents;
+  if (!description_dict->GetInteger("HeaderZLength", &compressed_header_len) ||
+      !description_dict->GetInteger("HeaderLength", &header_len) ||
+      !description_dict->GetInteger("RangeLength", &range_length) ||
+      !description_dict->GetInteger("DeltaFrom", &delta_from) ||
+      !description_dict->GetInteger("Version", &version) ||
+      !description_dict->GetString("Contents", &contents)) {
+    return NULL;
+  }
+
+  if (version != 0 || contents != "CRLFilterDelta")
+    return NULL;
+
+  if (delta_from < 0 || static_cast<unsigned>(delta_from) != sequence_)
+    return NULL;
+
+  if (compressed_header_len <= 0 ||
+      data.size() < static_cast<unsigned>(compressed_header_len) ||
+      header_len < 0 ||
+      header_len > kMaxHeaderLengthBytes) {
+    return NULL;
+  }
+
+  const base::StringPiece compressed_header(data.data(), compressed_header_len);
+  data.remove_prefix(compressed_header_len);
+
+  scoped_array<char> header_bytes(new char[header_len]);
+  if (!DecompressZlib(header_bytes.get(), header_len, compressed_header,
+                      header_bytes_)) {
+    return NULL;
+  }
+
+  scoped_refptr<CRLFilter> crl_filter(CRLFilterFromHeader(
+        base::StringPiece(header_bytes.get(), header_len)));
+
+  if (!crl_filter.get())
+    return NULL;
+
+  // Next are the three span values.
+  static const unsigned num_span_values = 3;
+  if (data.size() < num_span_values * sizeof(uint32))
+    return NULL;
+
+  std::vector<uint32> spans(num_span_values);
+  memcpy(&spans[0], data.data(), num_span_values * sizeof(uint32));
+  data.remove_prefix(num_span_values * sizeof(uint32));
+
+  if (data.size() < static_cast<unsigned>(range_length))
+    return NULL;
+  RangeDecoder decoder(data.substr(0, range_length), spans);
+  data.remove_prefix(range_length);
+
+  GolombCompressedSet gcs(data, 0 /* no values; we don't know that yet. */);
+  GolombCompressedSet::iterator gcs_deltas(gcs.begin());
+  GolombCompressedSet::iterator gcs_prev(gcs_->begin());
+  BitWriter bitwriter;
+
+  uint64 last = 0, v;
+  for (unsigned i = 0; i < crl_filter->num_entries_;) {
+    unsigned symbol, delta;
+    if (!decoder.Decode(&symbol))
+      return NULL;
+    if (symbol == SYMBOL_SAME) {
+      if (!gcs_prev.Next(&v))
+        return NULL;
+      bitwriter.WriteGolomb10(v - last);
+      last = v;
+      i++;
+    } else if (symbol == SYMBOL_INSERT) {
+      if (!gcs_deltas.NextDelta(&delta))
+        return NULL;
+      bitwriter.WriteGolomb10(delta);
+      last += delta;
+      i++;
+    } else if (symbol == SYMBOL_DELETE) {
+      if (!gcs_prev.Next(&v))
+        return NULL;
+    } else {
+      NOTREACHED();
+      return NULL;
+    }
+  }
+
+  crl_filter->gcs_bytes_ = bitwriter.as_string();
+  crl_filter->gcs_.reset(new GolombCompressedSet(crl_filter->gcs_bytes_,
+                                                 crl_filter->num_entries_));
+  return crl_filter.release();
+}
+
+bool CRLFilter::CRLIsCovered(
+    std::vector<base::StringPiece> crl_urls,
+    const std::string& parent_spki_sha256) {
+  for (std::vector<base::StringPiece>::const_iterator
+       i = crl_urls.begin(); i != crl_urls.end(); i++) {
+    if (crls_included_.count(std::make_pair<std::string, std::string>(
+            i->as_string(), parent_spki_sha256))) {
+      return true;
+    }
+  }
+  return false;
+}
+
+// FNV1a64 computes the FNV1a 64-bit hash of the concatenation of |a| and
+// |b|.
+static uint64 FNV1a64(const std::string& a, const std::string& b) {
+  uint64 x = 14695981039346656037ull;
+  static const uint64 p = 1099511628211ull;
+  for (size_t i = 0; i < a.size(); i++) {
+    x ^= static_cast<uint8>(a[i]);
+    x *= p;
+  }
+  for (size_t i = 0; i < b.size(); i++) {
+    x ^= static_cast<uint8>(b[i]);
+    x *= p;
+  }
+  return x;
+}
+
+CRLFilter::Result CRLFilter::CheckCertificate(
+    base::StringPiece cert_spki,
+    const std::string& serial_number,
+    std::vector<base::StringPiece> crl_urls,
+    base::StringPiece parent_spki) {
+  const std::string parent_spki_sha256 =
+      crypto::SHA256HashString(parent_spki.as_string());
+
+  if (!CRLIsCovered(crl_urls, parent_spki_sha256))
+    return UNKNOWN;
+
+  uint64 h = FNV1a64(serial_number, parent_spki_sha256);
+  h %= max_range_;
+
+  GolombCompressedSet::iterator it(gcs_->begin());
+  if (it.Contains(h))
+    return PROBABLY_REVOKED;
+  return NOT_REVOKED;
+}
+
+int64 CRLFilter::not_before() const {
+  return not_before_;
+}
+
+int64 CRLFilter::not_after() const {
+  return not_after_;
+}
+
+uint64 CRLFilter::max_range() const {
+  return max_range_;
+}
+
+unsigned CRLFilter::num_entries() const {
+  return num_entries_;
+}
+
+std::vector<uint64> CRLFilter::DebugValues() {
+  std::vector<uint64> ret;
+  uint64 v;
+
+  GolombCompressedSet::iterator it(gcs_->begin());
+
+  for (unsigned i = 0; i < num_entries_; i++) {
+    if (!it.Next(&v)) {
+      ret.clear();
+      break;
+    }
+    ret.push_back(v);
+  }
+  return ret;
+}
+
+std::string CRLFilter::SHA256() const {
+  std::string s = header_bytes_;
+  s += gcs_bytes_;
+  return crypto::SHA256HashString(s);
+}
+
+}  // namespace net
diff --git a/net/base/crl_filter.h b/net/base/crl_filter.h
new file mode 100644
index 0000000..020ebfb
--- /dev/null
+++ b/net/base/crl_filter.h
@@ -0,0 +1,110 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_BASE_CRL_FILTER_H_
+#define NET_BASE_CRL_FILTER_H_
+#pragma once
+
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/memory/ref_counted.h>
+#include <base/memory/scoped_ptr.h>
+#include <base/string_piece.h>
+#include <base/synchronization/lock.h>
+
+class DictionaryValue;
+
+namespace net {
+
+class GolombCompressedSet;
+
+// A CRLFilter is a probabilistic data structure for eliminating certificate
+// revocation checks. A CRL filter contains information about some number of
+// globally well known CRLs. Those CRLs are said to be `covered' by the filter.
+//
+// If a certificate specifies a CRL that is covered then the CRLFilter can give
+// a firm "not revoked" answer or a probabilistic "revoked" answer.
+// Additionally, a CRLFilter can contain a list of blocked public keys and, in
+// that case, it can give a firm "revoked" answer.
+class CRLFilter : public base::RefCounted<CRLFilter> {
+ public:
+  enum Result {
+    REVOKED,  // the certificate should be rejected.
+    PROBABLY_REVOKED,  // the certificate should be checked.
+    NOT_REVOKED,  // the certificate is acceptable.
+    UNKNOWN,  // no information available.
+  };
+
+  ~CRLFilter();
+
+  static CRLFilter* Parse(base::StringPiece data);
+
+  // CheckCertificate returns the information contained in the filter for a
+  // given certificate:
+  //   cert_spki: the SubjectPublicKeyInfo for the certificate
+  //   serial_number: the serial number of the certificate
+  //   crl_urls: the URLs for the CRL for the certificate
+  //   parent_spki: the SubjectPublicKeyInfo of the CRL signer
+  //
+  // This does not check that the CRLFilter is timely. See |not_before| and
+  // |not_after|.
+  Result CheckCertificate(
+      base::StringPiece cert_spki,
+      const std::string& serial_number,
+      std::vector<base::StringPiece> crl_urls,
+      base::StringPiece parent_spki);
+
+  // ApplyDelta returns a new CRLFilter that is the result of updating the
+  // current filter with the delta information in |delta_bytes|.
+  CRLFilter* ApplyDelta(base::StringPiece delta_bytes);
+
+  // not_before and not_after return the validity timespan of this filter.
+  // |CheckCertificate| does not check the current time so it's up to the
+  // caller to ensure that the CRLFilter is timely.
+  int64 not_before() const;
+  int64 not_after() const;
+
+  // DebugValues return all GCS values, in order. This should only be used
+  // for testing.
+  std::vector<uint64> DebugValues();
+  // num_entries returns the number of GCS values in the filter. This should
+  // only be used for testing.
+  unsigned num_entries() const;
+  // max_range returns size of the hash range. This should only be used for
+  // testing.
+  uint64 max_range() const;
+  // SHA256 returns a hash over the header and GCS bytes of the filter. This
+  // should only be used for testing.
+  std::string SHA256() const;
+
+ private:
+  // These are the range coder symbols used in delta updates.
+  enum {
+    SYMBOL_SAME = 0,
+    SYMBOL_INSERT = 1,
+    SYMBOL_DELETE = 2,
+  };
+
+  static CRLFilter* CRLFilterFromHeader(base::StringPiece header);
+  bool CRLIsCovered(std::vector<base::StringPiece> crl_urls,
+                    const std::string& parent_spki_sha256);
+
+  int64 not_before_, not_after_;
+  uint64 max_range_;
+  unsigned sequence_;
+  unsigned num_entries_;
+
+  std::string header_bytes_;
+
+  std::set<std::pair<std::string, std::string> > crls_included_;
+  std::string gcs_bytes_;
+  scoped_ptr<GolombCompressedSet> gcs_;
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_CRL_FILTER_H_
diff --git a/net/base/crl_filter_unittest.cc b/net/base/crl_filter_unittest.cc
new file mode 100644
index 0000000..8b3fba1
--- /dev/null
+++ b/net/base/crl_filter_unittest.cc
@@ -0,0 +1,212 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/base/crl_filter.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// These data blocks were generated using a lot of code that is still in
+// development. For now, if you need to update them, you have to contact agl.
+static const uint8 kTestFilter[] = {
+  0xab, 0x00, 0x7b, 0x22, 0x56, 0x65, 0x72, 0x73, 0x69, 0x6f, 0x6e, 0x22, 0x3a,
+  0x30, 0x2c, 0x22, 0x43, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x73, 0x22, 0x3a,
+  0x22, 0x43, 0x52, 0x4c, 0x46, 0x69, 0x6c, 0x74, 0x65, 0x72, 0x22, 0x2c, 0x22,
+  0x53, 0x65, 0x71, 0x75, 0x65, 0x6e, 0x63, 0x65, 0x22, 0x3a, 0x30, 0x2c, 0x22,
+  0x44, 0x65, 0x6c, 0x74, 0x61, 0x46, 0x72, 0x6f, 0x6d, 0x22, 0x3a, 0x30, 0x2c,
+  0x22, 0x48, 0x65, 0x61, 0x64, 0x65, 0x72, 0x5a, 0x4c, 0x65, 0x6e, 0x67, 0x74,
+  0x68, 0x22, 0x3a, 0x32, 0x31, 0x38, 0x2c, 0x22, 0x48, 0x65, 0x61, 0x64, 0x65,
+  0x72, 0x4c, 0x65, 0x6e, 0x67, 0x74, 0x68, 0x22, 0x3a, 0x32, 0x35, 0x39, 0x2c,
+  0x22, 0x53, 0x69, 0x67, 0x6e, 0x69, 0x6e, 0x67, 0x50, 0x75, 0x62, 0x6c, 0x69,
+  0x63, 0x4b, 0x65, 0x79, 0x22, 0x3a, 0x22, 0x22, 0x2c, 0x22, 0x53, 0x69, 0x67,
+  0x6e, 0x69, 0x6e, 0x67, 0x4b, 0x65, 0x79, 0x53, 0x69, 0x67, 0x6e, 0x61, 0x74,
+  0x75, 0x72, 0x65, 0x22, 0x3a, 0x22, 0x22, 0x2c, 0x22, 0x50, 0x61, 0x79, 0x6c,
+  0x6f, 0x61, 0x64, 0x53, 0x69, 0x67, 0x6e, 0x61, 0x74, 0x75, 0x72, 0x65, 0x22,
+  0x3a, 0x22, 0x22, 0x7d, 0x78, 0x9c, 0x74, 0xcd, 0x4d, 0x4f, 0x83, 0x30, 0x18,
+  0x07, 0xf0, 0xef, 0xf2, 0x5c, 0x25, 0xbc, 0xb8, 0x82, 0x4b, 0x13, 0x0f, 0x38,
+  0x8d, 0x36, 0x63, 0xca, 0x98, 0x2c, 0x26, 0xc6, 0x03, 0x76, 0x0f, 0xac, 0x91,
+  0xb5, 0x5a, 0x9e, 0xca, 0xc8, 0xb2, 0xef, 0x2e, 0x18, 0xaf, 0x5e, 0x7f, 0xf9,
+  0xbf, 0x9c, 0x60, 0x8b, 0xb6, 0x53, 0x46, 0x03, 0x0f, 0x3d, 0x78, 0x34, 0x74,
+  0x83, 0xb5, 0xb1, 0x08, 0x3c, 0x9a, 0x85, 0xec, 0x2a, 0x8a, 0x58, 0xcc, 0x7e,
+  0x39, 0xad, 0x09, 0xed, 0x9f, 0xc6, 0x2c, 0x99, 0x74, 0x55, 0x1d, 0x8b, 0x4a,
+  0x37, 0x63, 0x96, 0x25, 0xe1, 0x7c, 0x6a, 0xbb, 0xc3, 0x9d, 0x26, 0xab, 0xb0,
+  0x1b, 0x29, 0xf6, 0x60, 0x51, 0x64, 0x9d, 0xd0, 0xb2, 0x75, 0x3b, 0xdc, 0x01,
+  0x7f, 0x3d, 0x41, 0x59, 0x64, 0xc0, 0x61, 0x4f, 0xf4, 0xc9, 0x83, 0xa0, 0xef,
+  0x7b, 0xbf, 0xe9, 0xa8, 0x22, 0x25, 0x7d, 0x69, 0x0e, 0xc1, 0xbd, 0x31, 0x4d,
+  0x8b, 0x42, 0x8f, 0x3f, 0x1a, 0x29, 0x75, 0xb4, 0x37, 0x56, 0xd1, 0xf0, 0x9f,
+  0xfb, 0xd2, 0xb6, 0xe0, 0x41, 0x5e, 0x59, 0xd4, 0xb4, 0xc9, 0x97, 0x62, 0xf3,
+  0x90, 0x5e, 0xc6, 0xc9, 0xb8, 0x4f, 0xb6, 0x2d, 0x57, 0x5f, 0xce, 0x6d, 0x03,
+  0xb6, 0xb8, 0xcd, 0x96, 0xb3, 0xe7, 0xf0, 0xa2, 0xfe, 0x78, 0xc9, 0xc5, 0xb1,
+  0x57, 0xdf, 0x03, 0xca, 0xc1, 0x3e, 0x89, 0x01, 0xd7, 0xc5, 0xfc, 0x7d, 0x5d,
+  0x5e, 0xc3, 0xf9, 0xed, 0xfc, 0x13, 0x00, 0x00, 0xff, 0xff, 0x8a, 0x9f, 0x55,
+  0x48, 0x43, 0x5d, 0x4a, 0xac, 0xae, 0xd7, 0x88, 0xc4, 0xf7, 0x6e, 0xdc, 0x7c,
+  0x6b, 0x74, 0xd2, 0x1a, 0x22, 0xbf, 0x5b, 0x2e, 0x9f, 0xbd, 0xee, 0x09, 0xe7,
+  0x87, 0x16, 0x17, 0xa2, 0x6b, 0xf1, 0x37, 0x04, 0x61, 0x83, 0xd5, 0xc4, 0x79,
+  0xa4, 0x35, 0xc3, 0xb1, 0x2b, 0x58, 0x9f, 0xc7, 0x0c, 0x2a, 0x7e, 0xf8, 0xd2,
+  0x28, 0x46, 0xb4, 0x4f, 0x99, 0xea, 0xd8, 0x3d, 0x18, 0xd2, 0x69, 0x5a, 0x64,
+  0x3f, 0x00, 0x00, 0x00,
+};
+
+static const unsigned kTestFilterExpectedNumValues = 45;
+static const uint32 kTestFilterExpectedValues[kTestFilterExpectedNumValues] = {
+  673, 838, 1182, 1673, 1743, 2707, 3185, 4066,
+  6481, 6946, 8662, 8934, 10437, 11178, 13945, 14692,
+  15223, 15728, 19590, 19656, 20086, 21102, 22159, 23615,
+  27924, 28748, 29405, 29815, 33754, 34276, 34526, 34725,
+  35046, 35550, 38925, 39006, 39279, 39916, 41272, 41670,
+  41793, 44130, 44341, 44619, 45896,
+};
+
+// kGIASPKI is the DER encoded SubjectPublicKeyInfo of the GIA certificate.
+static const uint8 kGIASPKI[] = {
+  0x30, 0x81, 0x9f, 0x30, 0x0d, 0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d,
+  0x01, 0x01, 0x01, 0x05, 0x00, 0x03, 0x81, 0x8d, 0x00, 0x30, 0x81, 0x89, 0x02,
+  0x81, 0x81, 0x00, 0xc9, 0xed, 0xb7, 0xa4, 0x8b, 0x9c, 0x57, 0xe7, 0x84, 0x3e,
+  0x40, 0x7d, 0x84, 0xf4, 0x8f, 0xd1, 0x71, 0x63, 0x53, 0x99, 0xe7, 0x79, 0x74,
+  0x14, 0xaf, 0x44, 0x99, 0x33, 0x20, 0x92, 0x8d, 0x7b, 0xe5, 0x28, 0x0c, 0xba,
+  0xad, 0x6c, 0x49, 0x7e, 0x83, 0x5f, 0x34, 0x59, 0x4e, 0x0a, 0x7a, 0x30, 0xcd,
+  0xd0, 0xd7, 0xc4, 0x57, 0x45, 0xed, 0xd5, 0xaa, 0xd6, 0x73, 0x26, 0xce, 0xad,
+  0x32, 0x13, 0xb8, 0xd7, 0x0f, 0x1d, 0x3b, 0xdf, 0xdd, 0xdc, 0x08, 0x36, 0xa8,
+  0x6f, 0x51, 0x44, 0x9b, 0xca, 0xd6, 0x20, 0x52, 0x73, 0xb7, 0x26, 0x87, 0x35,
+  0x6a, 0xdb, 0xa9, 0xe5, 0xd4, 0x59, 0xa5, 0x2b, 0xfc, 0x67, 0x19, 0x39, 0xfa,
+  0x93, 0x18, 0x18, 0x6c, 0xde, 0xdd, 0x25, 0x8a, 0x0e, 0x33, 0x14, 0x47, 0xc2,
+  0xef, 0x01, 0x50, 0x79, 0xe4, 0xfd, 0x69, 0xd1, 0xa7, 0xc0, 0xac, 0xe2, 0x57,
+  0x6f, 0x02, 0x03, 0x01, 0x00, 0x01,
+};
+
+static const uint8 kDeltaTestFilter1[] = {
+  0xae, 0x00, 0x7b, 0x22, 0x56, 0x65, 0x72, 0x73, 0x69, 0x6f, 0x6e, 0x22, 0x3a,
+  0x30, 0x2c, 0x22, 0x43, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x73, 0x22, 0x3a,
+  0x22, 0x43, 0x52, 0x4c, 0x46, 0x69, 0x6c, 0x74, 0x65, 0x72, 0x22, 0x2c, 0x22,
+  0x44, 0x65, 0x6c, 0x74, 0x61, 0x46, 0x72, 0x6f, 0x6d, 0x22, 0x3a, 0x30, 0x2c,
+  0x22, 0x48, 0x65, 0x61, 0x64, 0x65, 0x72, 0x5a, 0x4c, 0x65, 0x6e, 0x67, 0x74,
+  0x68, 0x22, 0x3a, 0x32, 0x30, 0x32, 0x2c, 0x22, 0x48, 0x65, 0x61, 0x64, 0x65,
+  0x72, 0x4c, 0x65, 0x6e, 0x67, 0x74, 0x68, 0x22, 0x3a, 0x32, 0x31, 0x37, 0x2c,
+  0x22, 0x52, 0x61, 0x6e, 0x67, 0x65, 0x4c, 0x65, 0x6e, 0x67, 0x74, 0x68, 0x22,
+  0x3a, 0x30, 0x2c, 0x22, 0x53, 0x69, 0x67, 0x6e, 0x69, 0x6e, 0x67, 0x50, 0x75,
+  0x62, 0x6c, 0x69, 0x63, 0x4b, 0x65, 0x79, 0x22, 0x3a, 0x22, 0x22, 0x2c, 0x22,
+  0x53, 0x69, 0x67, 0x6e, 0x69, 0x6e, 0x67, 0x4b, 0x65, 0x79, 0x53, 0x69, 0x67,
+  0x6e, 0x61, 0x74, 0x75, 0x72, 0x65, 0x22, 0x3a, 0x22, 0x22, 0x2c, 0x22, 0x50,
+  0x61, 0x79, 0x6c, 0x6f, 0x61, 0x64, 0x53, 0x69, 0x67, 0x6e, 0x61, 0x74, 0x75,
+  0x72, 0x65, 0x22, 0x3a, 0x22, 0x22, 0x7d, 0x78, 0x9c, 0x24, 0xcb, 0xdf, 0x4a,
+  0xc3, 0x30, 0x14, 0xc7, 0xf1, 0x77, 0x39, 0xd7, 0x95, 0xe4, 0x64, 0xac, 0xd5,
+  0x82, 0x17, 0x5b, 0x11, 0x8c, 0xd6, 0x52, 0x1b, 0x36, 0x64, 0xe2, 0x45, 0xe8,
+  0xce, 0xea, 0xb0, 0x26, 0x36, 0x7f, 0xec, 0x64, 0xcc, 0x67, 0xb7, 0x9b, 0x77,
+  0x87, 0xcf, 0xf9, 0xfe, 0x8e, 0xa0, 0x68, 0x88, 0x64, 0x5a, 0x82, 0x9c, 0x27,
+  0xb0, 0x26, 0xe7, 0xf7, 0xd6, 0x5c, 0xee, 0xca, 0x86, 0x25, 0xed, 0xac, 0x9b,
+  0x3e, 0x38, 0xe3, 0x29, 0x66, 0xd9, 0x8d, 0xc0, 0x0b, 0x2f, 0x76, 0x81, 0xdc,
+  0xbf, 0x0a, 0x81, 0x78, 0xd6, 0x27, 0x7d, 0x68, 0xb4, 0xe9, 0xa6, 0x76, 0x8e,
+  0xe2, 0x3c, 0x8e, 0x9f, 0x77, 0x26, 0xb8, 0x3d, 0xf9, 0x49, 0x12, 0x28, 0x9a,
+  0xd2, 0x4b, 0xd3, 0xf6, 0x71, 0x4b, 0x5b, 0xc8, 0x5f, 0x8f, 0xb0, 0x6a, 0x4a,
+  0xc8, 0xe1, 0x3d, 0x84, 0xaf, 0x9c, 0xb1, 0x71, 0x1c, 0xd9, 0xaf, 0xee, 0x7a,
+  0xd6, 0xba, 0xfe, 0x0a, 0x21, 0x81, 0x5a, 0x3b, 0x32, 0x41, 0xd5, 0x8f, 0x52,
+  0xdd, 0x2f, 0xc4, 0x3c, 0x9d, 0xd2, 0x4d, 0x31, 0xeb, 0x5a, 0x5b, 0xae, 0xb3,
+  0x87, 0x4a, 0xf2, 0x58, 0xf9, 0x1f, 0xfe, 0xb2, 0x19, 0xae, 0xd5, 0xe1, 0x3b,
+  0x43, 0xa9, 0x86, 0xc1, 0x15, 0x69, 0x64, 0xcf, 0xcb, 0x7a, 0xa5, 0x3f, 0xec,
+  0x2d, 0x9c, 0xde, 0x4e, 0x7f, 0x01, 0x00, 0x00, 0xff, 0xff, 0xc1, 0xf9, 0x42,
+  0x93, 0x32, 0x3b, 0x84, 0x52, 0x5d, 0xa6, 0x01, 0x00,
+};
+
+static const uint8 kDeltaTestFilter2[] = {
+  0xb2, 0x00, 0x7b, 0x22, 0x56, 0x65, 0x72, 0x73, 0x69, 0x6f, 0x6e, 0x22, 0x3a,
+  0x30, 0x2c, 0x22, 0x43, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x73, 0x22, 0x3a,
+  0x22, 0x43, 0x52, 0x4c, 0x46, 0x69, 0x6c, 0x74, 0x65, 0x72, 0x44, 0x65, 0x6c,
+  0x74, 0x61, 0x22, 0x2c, 0x22, 0x44, 0x65, 0x6c, 0x74, 0x61, 0x46, 0x72, 0x6f,
+  0x6d, 0x22, 0x3a, 0x30, 0x2c, 0x22, 0x48, 0x65, 0x61, 0x64, 0x65, 0x72, 0x5a,
+  0x4c, 0x65, 0x6e, 0x67, 0x74, 0x68, 0x22, 0x3a, 0x34, 0x30, 0x2c, 0x22, 0x48,
+  0x65, 0x61, 0x64, 0x65, 0x72, 0x4c, 0x65, 0x6e, 0x67, 0x74, 0x68, 0x22, 0x3a,
+  0x32, 0x31, 0x37, 0x2c, 0x22, 0x52, 0x61, 0x6e, 0x67, 0x65, 0x4c, 0x65, 0x6e,
+  0x67, 0x74, 0x68, 0x22, 0x3a, 0x32, 0x2c, 0x22, 0x53, 0x69, 0x67, 0x6e, 0x69,
+  0x6e, 0x67, 0x50, 0x75, 0x62, 0x6c, 0x69, 0x63, 0x4b, 0x65, 0x79, 0x22, 0x3a,
+  0x22, 0x22, 0x2c, 0x22, 0x53, 0x69, 0x67, 0x6e, 0x69, 0x6e, 0x67, 0x4b, 0x65,
+  0x79, 0x53, 0x69, 0x67, 0x6e, 0x61, 0x74, 0x75, 0x72, 0x65, 0x22, 0x3a, 0x22,
+  0x22, 0x2c, 0x22, 0x50, 0x61, 0x79, 0x6c, 0x6f, 0x61, 0x64, 0x53, 0x69, 0x67,
+  0x6e, 0x61, 0x74, 0x75, 0x72, 0x65, 0x22, 0x3a, 0x22, 0x22, 0x7d, 0x78, 0xf9,
+  0xc1, 0xf9, 0x42, 0x93, 0xaa, 0x56, 0x22, 0xda, 0x63, 0x16, 0x06, 0x40, 0x80,
+  0xe9, 0x31, 0x63, 0x23, 0x90, 0x28, 0x3e, 0x8f, 0x99, 0x91, 0xe4, 0x31, 0x23,
+  0xea, 0x78, 0x0c, 0x10, 0x00, 0x00, 0xff, 0xff, 0xb6, 0xa2, 0x42, 0x83, 0x91,
+  0x24, 0x49, 0x92, 0x48, 0x92, 0x24, 0x49, 0x26, 0x49, 0x92, 0x24, 0xd4, 0xb5,
+  0xad, 0xcf, 0x00, 0x00,
+};
+
+// kRevokedCertSerialNumber is the serial number of a certificate that is
+// listed in the GIA CRL.
+static const uint8 kRevokedCertSerialNumber[] = {
+  0x36, 0xa0, 0x42, 0xb4, 0x00, 0x03, 0x00, 0x00, 0x27, 0x86,
+};
+
+static const uint8 kDeltaResultSHA256[] = {
+  0x7d, 0x00, 0xea, 0x3e, 0x58, 0xb6, 0xda, 0x16, 0x6f, 0x3c, 0xae, 0xe1, 0xa3,
+  0x26, 0x39, 0x5b, 0x5c, 0xa5, 0x2f, 0x41, 0xde, 0xd7, 0x81, 0xd6, 0xa4, 0x4c,
+  0x1d, 0x4b, 0xdc, 0x57, 0x62, 0x6f,
+};
+
+TEST(CRLFilterTest, Parse) {
+  base::StringPiece s(reinterpret_cast<const char*>(kTestFilter),
+                      sizeof(kTestFilter));
+  scoped_refptr<net::CRLFilter> filter(net::CRLFilter::Parse(s));
+  ASSERT_TRUE(filter.get() != NULL);
+
+  EXPECT_EQ(filter->num_entries(), kTestFilterExpectedNumValues);
+  EXPECT_EQ(filter->max_range(), kTestFilterExpectedNumValues << 10);
+
+  std::vector<uint64> values(filter->DebugValues());
+  ASSERT_EQ(values.size(), kTestFilterExpectedNumValues);
+
+  for (unsigned i = 0; i < kTestFilterExpectedNumValues; i++) {
+    EXPECT_EQ(kTestFilterExpectedValues[i], values[i]);
+  }
+}
+
+TEST(CRLFilterTest, DeltaUpdates) {
+  base::StringPiece s(reinterpret_cast<const char *>(kDeltaTestFilter1),
+                      sizeof(kDeltaTestFilter1));
+  scoped_refptr<net::CRLFilter> filter(net::CRLFilter::Parse(s));
+  ASSERT_TRUE(filter.get() != NULL);
+
+  base::StringPiece delta_bytes(
+      reinterpret_cast<const char*>(kDeltaTestFilter2),
+      sizeof(kDeltaTestFilter2));
+  scoped_refptr<net::CRLFilter> delta(filter->ApplyDelta(delta_bytes));
+  ASSERT_TRUE(delta.get() != NULL);
+
+  ASSERT_TRUE(delta->SHA256() ==
+              std::string(reinterpret_cast<const char *>(kDeltaResultSHA256),
+                          sizeof(kDeltaResultSHA256)));
+}
+
+TEST(CRLFilterTest, Entries) {
+  base::StringPiece s(reinterpret_cast<const char*>(kTestFilter),
+                      sizeof(kTestFilter));
+  scoped_refptr<net::CRLFilter> filter(net::CRLFilter::Parse(s));
+  ASSERT_TRUE(filter.get() != NULL);
+
+  base::StringPiece cert_spki;
+  std::string serial_number = "1";  // not a real serial number.
+  std::vector<base::StringPiece> crl_urls;
+  static const char kFakeCRLURL[] = "http://example.com/crl";
+  crl_urls.push_back(base::StringPiece(kFakeCRLURL, sizeof(kFakeCRLURL)));
+  base::StringPiece parent_spki;
+
+  ASSERT_EQ(net::CRLFilter::UNKNOWN,
+            filter->CheckCertificate(cert_spki, serial_number, crl_urls,
+                                     parent_spki));
+
+  crl_urls.clear();
+  static const char kGIACRLURL[] =
+      "http://www.gstatic.com/GoogleInternetAuthority/"
+      "GoogleInternetAuthority.crl";
+  crl_urls.push_back(kGIACRLURL);
+
+  parent_spki = base::StringPiece(reinterpret_cast<const char*>(kGIASPKI),
+                                  sizeof(kGIASPKI));
+  ASSERT_EQ(net::CRLFilter::NOT_REVOKED,
+            filter->CheckCertificate(cert_spki, serial_number, crl_urls,
+                                     parent_spki));
+
+  serial_number =
+      std::string(reinterpret_cast<const char*>(kRevokedCertSerialNumber),
+                  sizeof(kRevokedCertSerialNumber));
+  ASSERT_EQ(net::CRLFilter::PROBABLY_REVOKED,
+            filter->CheckCertificate(cert_spki, serial_number, crl_urls,
+                                     parent_spki));
+}