--- a/toolkit/components/url-classifier/Classifier.cpp
+++ b/toolkit/components/url-classifier/Classifier.cpp
@@ -464,33 +464,19 @@ Classifier::Check(const nsACString& aSpe
       lookupHash.ToHexString(checking);
       LOG(("Checking fragment %s, hash %s (%X)", fragments[i].get(),
            checking.get(), lookupHash.ToUint32()));
     }
 
     for (uint32_t i = 0; i < cacheArray.Length(); i++) {
       LookupCache *cache = cacheArray[i];
       bool has, complete;
+      uint32_t matchLength;
 
-      if (LookupCache::Cast<LookupCacheV4>(cache)) {
-        // TODO Bug 1312339 Return length in LookupCache.Has and support
-        // VariableLengthPrefix in LookupResultArray
-        rv = cache->Has(lookupHash, &has, &complete);
-        if (NS_FAILED(rv)) {
-          LOG(("Failed to lookup fragment %s V4", fragments[i].get()));
-        }
-        if (has) {
-          matchingStatistics |= PrefixMatch::eMatchV4Prefix;
-          // TODO: Bug 1311935 - Implement Safe Browsing v4 caching
-          // Should check cache expired
-        }
-        continue;
-      }
-
-      rv = cache->Has(lookupHash, &has, &complete);
+      rv = cache->Has(lookupHash, &has, &complete, &matchLength);
       NS_ENSURE_SUCCESS(rv, rv);
       if (has) {
         LookupResult *result = aResults.AppendElement();
         if (!result)
           return NS_ERROR_OUT_OF_MEMORY;
 
         int64_t age;
         bool found = mTableFreshness.Get(cache->TableName(), &age);
@@ -505,18 +491,23 @@ Classifier::Check(const nsACString& aSpe
              cache->TableName().get(),
              complete ? "complete." : "Not complete.",
              age));
 
         result->hash.complete = lookupHash;
         result->mComplete = complete;
         result->mFresh = (age < aFreshnessGuarantee);
         result->mTableName.Assign(cache->TableName());
+        result->mPartialHashLength = matchLength;
 
-        matchingStatistics |= PrefixMatch::eMatchV2Prefix;
+        if (LookupCache::Cast<LookupCacheV4>(cache)) {
+          matchingStatistics |= PrefixMatch::eMatchV4Prefix;
+        } else {
+          matchingStatistics |= PrefixMatch::eMatchV2Prefix;
+        }
       }
     }
 
     Telemetry::Accumulate(Telemetry::URLCLASSIFIER_PREFIX_MATCH,
                           static_cast<uint8_t>(matchingStatistics));
   }
 
   return NS_OK;
@@ -1206,17 +1197,18 @@ Classifier::GetLookupCache(const nsACStr
 
 nsresult
 Classifier::ReadNoiseEntries(const Prefix& aPrefix,
                              const nsACString& aTableName,
                              uint32_t aCount,
                              PrefixArray* aNoiseEntries)
 {
   // TODO : Bug 1297962, support adding noise for v4
-  LookupCacheV2 *cache = static_cast<LookupCacheV2*>(GetLookupCache(aTableName));
+  LookupCacheV2 *cache =
+    LookupCache::Cast<LookupCacheV2>(GetLookupCache(aTableName));
   if (!cache) {
     return NS_ERROR_FAILURE;
   }
 
   FallibleTArray<uint32_t> prefixes;
   nsresult rv = cache->GetPrefixes(prefixes);
   NS_ENSURE_SUCCESS(rv, rv);
 

--- a/toolkit/components/url-classifier/LookupCache.cpp
+++ b/toolkit/components/url-classifier/LookupCache.cpp
@@ -416,37 +416,41 @@ void
 LookupCacheV2::ClearAll()
 {
   LookupCache::ClearAll();
   mUpdateCompletions.Clear();
 }
 
 nsresult
 LookupCacheV2::Has(const Completion& aCompletion,
-                   bool* aHas, bool* aComplete)
+                   bool* aHas, bool* aComplete,
+                   uint32_t* aMatchLength)
 {
   *aHas = *aComplete = false;
+  *aMatchLength = 0;
 
   uint32_t prefix = aCompletion.ToUint32();
 
   bool found;
   nsresult rv = mPrefixSet->Contains(prefix, &found);
   NS_ENSURE_SUCCESS(rv, rv);
 
   LOG(("Probe in %s: %X, found %d", mTableName.get(), prefix, found));
 
   if (found) {
     *aHas = true;
+    *aMatchLength = PREFIX_SIZE;
   }
 
   if ((mGetHashCache.BinaryIndexOf(aCompletion) != nsTArray<Completion>::NoIndex) ||
       (mUpdateCompletions.BinaryIndexOf(aCompletion) != nsTArray<Completion>::NoIndex)) {
     LOG(("Complete in %s", mTableName.get()));
     *aComplete = true;
     *aHas = true;
+    *aMatchLength = COMPLETE_SIZE;
   }
 
   return NS_OK;
 }
 
 nsresult
 LookupCacheV2::Build(AddPrefixArray& aAddPrefixes,
                      AddCompleteArray& aAddCompletes)

--- a/toolkit/components/url-classifier/LookupCache.h
+++ b/toolkit/components/url-classifier/LookupCache.h
@@ -21,32 +21,43 @@ namespace mozilla {
 namespace safebrowsing {
 
 #define MAX_HOST_COMPONENTS 5
 #define MAX_PATH_COMPONENTS 4
 
 class LookupResult {
 public:
   LookupResult() : mComplete(false), mNoise(false),
-                   mFresh(false), mProtocolConfirmed(false) {}
+                   mFresh(false), mProtocolConfirmed(false),
+                   mPartialHashLength(0) {}
 
   // The fragment that matched in the LookupCache
   union {
-    Prefix prefix;
+    Prefix fixedLengthPrefix;
     Completion complete;
   } hash;
 
-  const Prefix &PrefixHash() {
-    return hash.prefix;
-  }
   const Completion &CompleteHash() {
     MOZ_ASSERT(!mNoise);
     return hash.complete;
   }
 
+  nsCString PartialHash() {
+    MOZ_ASSERT(mPartialHashLength <= COMPLETE_SIZE);
+    return nsCString(reinterpret_cast<char*>(hash.complete.buf), mPartialHashLength);
+  }
+
+  nsCString PartialHashHex() {
+    nsAutoCString hex;
+    for (size_t i = 0; i < mPartialHashLength; i++) {
+      hex.AppendPrintf("%.2X", hash.complete.buf[i]);
+    }
+    return hex;
+  }
+
   bool Confirmed() const { return (mComplete && mFresh) || mProtocolConfirmed; }
   bool Complete() const { return mComplete; }
 
   // True if we have a complete match for this hash in the table.
   bool mComplete;
 
   // True if this is a noise entry, i.e. an extra entry
   // that is inserted to mask the true URL we are requesting.
@@ -56,16 +67,18 @@ public:
   bool mNoise;
 
   // True if we've updated this table recently-enough.
   bool mFresh;
 
   bool mProtocolConfirmed;
 
   nsCString mTableName;
+
+  uint32_t mPartialHashLength;
 };
 
 typedef nsTArray<LookupResult> LookupResultArray;
 
 struct CacheResult {
   AddComplete entry;
   nsCString table;
 
@@ -121,17 +134,18 @@ public:
 #if DEBUG
   void DumpCache();
 #endif
 
   virtual nsresult Open();
   virtual nsresult Init() = 0;
   virtual nsresult ClearPrefixes() = 0;
   virtual nsresult Has(const Completion& aCompletion,
-                       bool* aHas, bool* aComplete) = 0;
+                       bool* aHas, bool* aComplete,
+                       uint32_t* aMatchLength) = 0;
 
   virtual void ClearAll();
 
   template<typename T>
   static T* Cast(LookupCache* aThat) {
     return ((aThat && T::VER == aThat->Ver()) ? reinterpret_cast<T*>(aThat) : nullptr);
   }
 
@@ -167,17 +181,18 @@ public:
                          nsIFile* aStoreFile)
     : LookupCache(aTableName, aProvider, aStoreFile) {}
   ~LookupCacheV2() {}
 
   virtual nsresult Init() override;
   virtual nsresult Open() override;
   virtual void ClearAll() override;
   virtual nsresult Has(const Completion& aCompletion,
-                       bool* aHas, bool* aComplete) override;
+                       bool* aHas, bool* aComplete,
+                       uint32_t* aMatchLength) override;
 
   nsresult Build(AddPrefixArray& aAddPrefixes,
                  AddCompleteArray& aAddCompletes);
 
   nsresult GetPrefixes(FallibleTArray<uint32_t>& aAddPrefixes);
 
 #if DEBUG
   void DumpCompletions();

--- a/toolkit/components/url-classifier/LookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/LookupCacheV4.cpp
@@ -75,29 +75,32 @@ LookupCacheV4::Init()
   nsresult rv = mVLPrefixSet->Init(mTableName);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 LookupCacheV4::Has(const Completion& aCompletion,
-                   bool* aHas, bool* aComplete)
+                   bool* aHas, bool* aComplete,
+                   uint32_t* aMatchLength)
 {
-  *aHas = false;
+  *aHas = *aComplete = false;
+  *aMatchLength = 0;
 
   uint32_t length = 0;
   nsDependentCSubstring fullhash;
   fullhash.Rebind((const char *)aCompletion.buf, COMPLETE_SIZE);
 
   nsresult rv = mVLPrefixSet->Matches(fullhash, &length);
   NS_ENSURE_SUCCESS(rv, rv);
 
   *aHas = length >= PREFIX_SIZE;
   *aComplete = length == COMPLETE_SIZE;
+  *aMatchLength = length;
 
   if (LOG_ENABLED()) {
     uint32_t prefix = aCompletion.ToUint32();
     LOG(("Probe in V4 %s: %X, found %d, complete %d", mTableName.get(),
           prefix, *aHas, *aComplete));
   }
 
   return NS_OK;

--- a/toolkit/components/url-classifier/LookupCacheV4.h
+++ b/toolkit/components/url-classifier/LookupCacheV4.h
@@ -20,17 +20,18 @@ public:
   explicit LookupCacheV4(const nsACString& aTableName,
                          const nsACString& aProvider,
                          nsIFile* aStoreFile)
     : LookupCache(aTableName, aProvider, aStoreFile) {}
   ~LookupCacheV4() {}
 
   virtual nsresult Init() override;
   virtual nsresult Has(const Completion& aCompletion,
-                       bool* aHas, bool* aComplete) override;
+                       bool* aHas, bool* aComplete,
+                       uint32_t* aMatchLength) override;
 
   nsresult Build(PrefixStringMap& aPrefixMap);
 
   nsresult GetPrefixes(PrefixStringMap& aPrefixMap);
 
   // ApplyUpdate will merge data stored in aTableUpdate with prefixes in aInputMap.
   nsresult ApplyUpdate(TableUpdateV4* aTableUpdate,
                        PrefixStringMap& aInputMap,

--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ -268,27 +268,27 @@ nsUrlClassifierDBServiceWorker::DoLookup
     PRIntervalTime clockEnd = PR_IntervalNow();
     LOG(("query took %dms\n",
          PR_IntervalToMilliseconds(clockEnd - clockStart)));
   }
 
   nsAutoPtr<LookupResultArray> completes(new LookupResultArray());
 
   for (uint32_t i = 0; i < results->Length(); i++) {
-    if (!mMissCache.Contains(results->ElementAt(i).hash.prefix)) {
+    if (!mMissCache.Contains(results->ElementAt(i).hash.fixedLengthPrefix)) {
       completes->AppendElement(results->ElementAt(i));
     }
   }
 
   for (uint32_t i = 0; i < completes->Length(); i++) {
     if (!completes->ElementAt(i).Confirmed()) {
       // We're going to be doing a gethash request, add some extra entries.
       // Note that we cannot pass the first two by reference, because we
       // add to completes, whicah can cause completes to reallocate and move.
-      AddNoise(completes->ElementAt(i).hash.prefix,
+      AddNoise(completes->ElementAt(i).hash.fixedLengthPrefix,
                completes->ElementAt(i).mTableName,
                mGethashNoise, *completes);
       break;
     }
   }
 
   // At this point ownership of 'results' is handed to the callback.
   c->LookupComplete(completes.forget());
@@ -338,19 +338,19 @@ nsUrlClassifierDBServiceWorker::AddNoise
                                               aCount, &noiseEntries);
   NS_ENSURE_SUCCESS(rv, rv);
 
   for (uint32_t i = 0; i < noiseEntries.Length(); i++) {
     LookupResult *result = results.AppendElement();
     if (!result)
       return NS_ERROR_OUT_OF_MEMORY;
 
-    result->hash.prefix = noiseEntries[i];
+    result->hash.fixedLengthPrefix = noiseEntries[i];
     result->mNoise = true;
-
+    result->mPartialHashLength = PREFIX_SIZE; // Noise is always 4-byte,
     result->mTableName.Assign(tableName);
   }
 
   return NS_OK;
 }
 
 // Lookup a key in the db.
 NS_IMETHODIMP
@@ -959,19 +959,30 @@ nsUrlClassifierLookupCallback::LookupCom
       // gethashUrls may be empty in 2 cases: test tables, and on startup where
       // we may have found a prefix in an existing table before the listmanager
       // has registered the table. In the second case we should not call
       // complete.
       if ((!gethashUrl.IsEmpty() ||
            StringBeginsWith(result.mTableName, NS_LITERAL_CSTRING("test-"))) &&
           mDBService->GetCompleter(result.mTableName,
                                    getter_AddRefs(completer))) {
+
+        // TODO: Figure out how long the partial hash should be sent
+        //       for completion. See Bug 1323953.
         nsAutoCString partialHash;
-        partialHash.Assign(reinterpret_cast<char*>(&result.hash.prefix),
-                           PREFIX_SIZE);
+        if (StringEndsWith(result.mTableName, NS_LITERAL_CSTRING("-proto"))) {
+          // We send the complete partial hash for v4 at the moment.
+          partialHash = result.PartialHash();
+        } else {
+          // We always send the first 4 bytes of the partial hash for
+          // non-v4 tables. This matters when we have 32-byte prefix
+          // in "test-xxx-simple" test data.
+          partialHash.Assign(reinterpret_cast<char*>(&result.hash.fixedLengthPrefix),
+                             PREFIX_SIZE);
+        }
 
         nsresult rv = completer->Complete(partialHash,
                                           gethashUrl,
                                           result.mTableName,
                                           this);
         if (NS_SUCCEEDED(rv)) {
           mPendingCompletions++;
         }
@@ -1076,43 +1087,43 @@ nsUrlClassifierLookupCallback::HandleRes
   // Build a stringified list of result tables.
   for (uint32_t i = 0; i < mResults->Length(); i++) {
     LookupResult& result = mResults->ElementAt(i);
 
     // Leave out results that weren't confirmed, as their existence on
     // the list can't be verified.  Also leave out randomly-generated
     // noise.
     if (result.mNoise) {
-      LOG(("Skipping result %X from table %s (noise)",
-           result.hash.prefix.ToUint32(), result.mTableName.get()));
+      LOG(("Skipping result %s from table %s (noise)",
+           result.PartialHashHex().get(), result.mTableName.get()));
       continue;
     } else if (!result.Confirmed()) {
       LOG(("Skipping result %X from table %s (not confirmed)",
-           result.hash.prefix.ToUint32(), result.mTableName.get()));
+           result.PartialHashHex().get(), result.mTableName.get()));
       continue;
     }
 
     LOG(("Confirmed result %X from table %s",
-         result.hash.prefix.ToUint32(), result.mTableName.get()));
+         result.PartialHashHex().get(), result.mTableName.get()));
 
     if (tables.IndexOf(result.mTableName) == nsTArray<nsCString>::NoIndex) {
       tables.AppendElement(result.mTableName);
     }
   }
 
   // Some parts of this gethash request generated no hits at all.
   // Prefixes must have been removed from the database since our last update.
   // Save the prefixes we checked to prevent repeated requests
   // until the next update.
   nsAutoPtr<PrefixArray> cacheMisses(new PrefixArray());
   if (cacheMisses) {
     for (uint32_t i = 0; i < mResults->Length(); i++) {
       LookupResult &result = mResults->ElementAt(i);
       if (!result.Confirmed() && !result.mNoise) {
-        cacheMisses->AppendElement(result.PrefixHash());
+        cacheMisses->AppendElement(result.hash.fixedLengthPrefix);
       }
     }
     // Hands ownership of the miss array back to the worker thread.
     mDBService->CacheMisses(cacheMisses.forget());
   }
 
   if (mCacheResults) {
     // This hands ownership of the cache results array back to the worker

--- a/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
@@ -56,17 +56,18 @@ TestHasPrefix(const _Fragment& aFragment
   RunTestInNewThread([&] () -> void {
     UniquePtr<LookupCache> cache = SetupLookupCacheV4(array);
 
     Completion lookupHash;
     nsCOMPtr<nsICryptoHash> cryptoHash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
     lookupHash.FromPlaintext(aFragment, cryptoHash);
 
     bool has, complete;
-    nsresult rv = cache->Has(lookupHash, &has, &complete);
+    uint32_t matchLength;
+    nsresult rv = cache->Has(lookupHash, &has, &complete, &matchLength);
 
     EXPECT_EQ(rv, NS_OK);
     EXPECT_EQ(has, aExpectedHas);
     EXPECT_EQ(complete, aExpectedComplete);
 
     cache->ClearAll();
   });