michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set sw=2 ts=8 et tw=80 : */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: // HttpLog.h should generally be included first
michael@0: #include "HttpLog.h"
michael@0: 
michael@0: // Log on level :5, instead of default :4.
michael@0: #undef LOG
michael@0: #define LOG(args) LOG5(args)
michael@0: #undef LOG_ENABLED
michael@0: #define LOG_ENABLED() LOG5_ENABLED()
michael@0: 
michael@0: #include "Http2Compression.h"
michael@0: #include "Http2HuffmanIncoming.h"
michael@0: #include "Http2HuffmanOutgoing.h"
michael@0: 
michael@0: extern PRThread *gSocketThread;
michael@0: 
michael@0: namespace mozilla {
michael@0: namespace net {
michael@0: 
michael@0: static nsDeque *gStaticHeaders = nullptr;
michael@0: 
michael@0: void
michael@0: Http2CompressionCleanup()
michael@0: {
michael@0:   // this happens after the socket thread has been destroyed
michael@0:   delete gStaticHeaders;
michael@0:   gStaticHeaders = nullptr;
michael@0: }
michael@0: 
michael@0: static void
michael@0: AddStaticElement(const nsCString &name, const nsCString &value)
michael@0: {
michael@0:   nvPair *pair = new nvPair(name, value);
michael@0:   gStaticHeaders->Push(pair);
michael@0: }
michael@0: 
michael@0: static void
michael@0: AddStaticElement(const nsCString &name)
michael@0: {
michael@0:   AddStaticElement(name, EmptyCString());
michael@0: }
michael@0: 
michael@0: static void
michael@0: InitializeStaticHeaders()
michael@0: {
michael@0:   MOZ_ASSERT(PR_GetCurrentThread() == gSocketThread);
michael@0:   if (!gStaticHeaders) {
michael@0:     gStaticHeaders = new nsDeque();
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":authority"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":method"), NS_LITERAL_CSTRING("GET"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":method"), NS_LITERAL_CSTRING("POST"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":path"), NS_LITERAL_CSTRING("/"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":path"), NS_LITERAL_CSTRING("/index.html"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":scheme"), NS_LITERAL_CSTRING("http"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":scheme"), NS_LITERAL_CSTRING("https"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("200"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("500"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("404"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("403"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("400"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("401"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("accept-charset"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("accept-encoding"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("accept-language"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("accept-ranges"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("accept"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("access-control-allow-origin"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("age"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("allow"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("authorization"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("cache-control"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("content-disposition"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("content-encoding"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("content-language"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("content-length"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("content-location"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("content-range"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("content-type"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("cookie"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("date"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("etag"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("expect"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("expires"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("from"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("host"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("if-match"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("if-modified-since"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("if-none-match"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("if-range"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("if-unmodified-since"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("last-modified"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("link"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("location"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("max-forwards"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("proxy-authenticate"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("proxy-authorization"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("range"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("referer"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("refresh"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("retry-after"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("server"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("set-cookie"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("strict-transport-security"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("transfer-encoding"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("user-agent"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("vary"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("via"));
michael@0:     AddStaticElement(NS_LITERAL_CSTRING("www-authenticate"));
michael@0:   }
michael@0: }
michael@0: 
michael@0: nvFIFO::nvFIFO()
michael@0:   : mByteCount(0)
michael@0:   , mTable()
michael@0: {
michael@0:   InitializeStaticHeaders();
michael@0: }
michael@0: 
michael@0: nvFIFO::~nvFIFO()
michael@0: {
michael@0:   Clear();
michael@0: }
michael@0: 
michael@0: void
michael@0: nvFIFO::AddElement(const nsCString &name, const nsCString &value)
michael@0: {
michael@0:   mByteCount += name.Length() + value.Length() + 32;
michael@0:   nvPair *pair = new nvPair(name, value);
michael@0:   mTable.PushFront(pair);
michael@0: }
michael@0: 
michael@0: void
michael@0: nvFIFO::AddElement(const nsCString &name)
michael@0: {
michael@0:   AddElement(name, EmptyCString());
michael@0: }
michael@0: 
michael@0: void
michael@0: nvFIFO::RemoveElement()
michael@0: {
michael@0:   nvPair *pair = static_cast<nvPair *>(mTable.Pop());
michael@0:   if (pair) {
michael@0:     mByteCount -= pair->Size();
michael@0:     delete pair;
michael@0:   }
michael@0: }
michael@0: 
michael@0: uint32_t
michael@0: nvFIFO::ByteCount() const
michael@0: {
michael@0:   return mByteCount;
michael@0: }
michael@0: 
michael@0: uint32_t
michael@0: nvFIFO::Length() const
michael@0: {
michael@0:   return mTable.GetSize() + gStaticHeaders->GetSize();
michael@0: }
michael@0: 
michael@0: uint32_t
michael@0: nvFIFO::VariableLength() const
michael@0: {
michael@0:   return mTable.GetSize();
michael@0: }
michael@0: 
michael@0: void
michael@0: nvFIFO::Clear()
michael@0: {
michael@0:   mByteCount = 0;
michael@0:   while (mTable.GetSize())
michael@0:     delete static_cast<nvPair *>(mTable.Pop());
michael@0: }
michael@0: 
michael@0: const nvPair *
michael@0: nvFIFO::operator[] (int32_t index) const
michael@0: {
michael@0:   if (index >= (mTable.GetSize() + gStaticHeaders->GetSize())) {
michael@0:     MOZ_ASSERT(false);
michael@0:     NS_WARNING("nvFIFO Table Out of Range");
michael@0:     return nullptr;
michael@0:   }
michael@0:   if (index >= mTable.GetSize()) {
michael@0:     return static_cast<nvPair *>(gStaticHeaders->ObjectAt(index - mTable.GetSize()));
michael@0:   }
michael@0:   return static_cast<nvPair *>(mTable.ObjectAt(index));
michael@0: }
michael@0: 
michael@0: Http2BaseCompressor::Http2BaseCompressor()
michael@0:   : mOutput(nullptr)
michael@0:   , mMaxBuffer(kDefaultMaxBuffer)
michael@0: {
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2BaseCompressor::ClearHeaderTable()
michael@0: {
michael@0:   uint32_t dynamicCount = mHeaderTable.VariableLength();
michael@0:   mHeaderTable.Clear();
michael@0: 
michael@0:   for (int32_t i = mReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     if (mReferenceSet[i] < dynamicCount) {
michael@0:       mReferenceSet.RemoveElementAt(i);
michael@0:     } else {
michael@0:       mReferenceSet[i] -= dynamicCount;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   for (int32_t i = mAlternateReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     if (mAlternateReferenceSet[i] < dynamicCount) {
michael@0:       mAlternateReferenceSet.RemoveElementAt(i);
michael@0:     } else {
michael@0:       mAlternateReferenceSet[i] -= dynamicCount;
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2BaseCompressor::UpdateReferenceSet(int32_t delta)
michael@0: {
michael@0:   if (!delta)
michael@0:     return;
michael@0: 
michael@0:   uint32_t headerTableSize = mHeaderTable.VariableLength();
michael@0:   uint32_t oldHeaderTableSize = headerTableSize + delta;
michael@0: 
michael@0:   for (int32_t i = mReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     uint32_t indexRef = mReferenceSet[i];
michael@0:     if (indexRef >= headerTableSize) {
michael@0:       if (indexRef < oldHeaderTableSize) {
michael@0:         // This one got dropped
michael@0:         LOG3(("HTTP base compressor reference to index %u removed.\n",
michael@0:               indexRef));
michael@0:         mReferenceSet.RemoveElementAt(i);
michael@0:       } else {
michael@0:         // This pointed to the static table, need to adjust
michael@0:         uint32_t newRef = indexRef - delta;
michael@0:         LOG3(("HTTP base compressor reference to index %u changed to %d (%s)\n",
michael@0:               mReferenceSet[i], newRef, mHeaderTable[newRef]->mName.get()));
michael@0:         mReferenceSet[i] = newRef;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   for (int32_t i = mAlternateReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     uint32_t indexRef = mAlternateReferenceSet[i];
michael@0:     if (indexRef >= headerTableSize) {
michael@0:       if (indexRef < oldHeaderTableSize) {
michael@0:         // This one got dropped
michael@0:         LOG3(("HTTP base compressor new reference to index %u removed.\n",
michael@0:               indexRef));
michael@0:         mAlternateReferenceSet.RemoveElementAt(i);
michael@0:       } else {
michael@0:         // This pointed to the static table, need to adjust
michael@0:         uint32_t newRef = indexRef - delta;
michael@0:         LOG3(("HTTP base compressor new reference to index %u changed to %d (%s)\n",
michael@0:               mAlternateReferenceSet[i], newRef, mHeaderTable[newRef]->mName.get()));
michael@0:         mAlternateReferenceSet[i] = newRef;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2BaseCompressor::IncrementReferenceSetIndices()
michael@0: {
michael@0:   for (int32_t i = mReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     mReferenceSet[i] = mReferenceSet[i] + 1;
michael@0:   }
michael@0: 
michael@0:   for (int32_t i = mAlternateReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     mAlternateReferenceSet[i] = mAlternateReferenceSet[i] + 1;
michael@0:   }
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::DecodeHeaderBlock(const uint8_t *data, uint32_t datalen,
michael@0:                                      nsACString &output)
michael@0: {
michael@0:   mAlternateReferenceSet.Clear();
michael@0:   mOffset = 0;
michael@0:   mData = data;
michael@0:   mDataLen = datalen;
michael@0:   mOutput = &output;
michael@0:   mOutput->Truncate();
michael@0:   mHeaderStatus.Truncate();
michael@0:   mHeaderHost.Truncate();
michael@0:   mHeaderScheme.Truncate();
michael@0:   mHeaderPath.Truncate();
michael@0:   mHeaderMethod.Truncate();
michael@0: 
michael@0:   nsresult rv = NS_OK;
michael@0:   while (NS_SUCCEEDED(rv) && (mOffset < datalen)) {
michael@0:     if (mData[mOffset] & 0x80) {
michael@0:       rv = DoIndexed();
michael@0:     } else if (mData[mOffset] & 0x40) {
michael@0:       rv = DoLiteralWithoutIndex();
michael@0:     } else {
michael@0:       rv = DoLiteralWithIncremental();
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // after processing the input the decompressor comapres the alternate
michael@0:   // set to the inherited reference set and generates headers for
michael@0:   // anything implicit in reference - alternate.
michael@0: 
michael@0:   uint32_t setLen = mReferenceSet.Length();
michael@0:   for (uint32_t index = 0; index < setLen; ++index) {
michael@0:     if (!mAlternateReferenceSet.Contains(mReferenceSet[index])) {
michael@0:       LOG3(("HTTP decompressor carryover in reference set with index %u %s %s\n",
michael@0:             mReferenceSet[index],
michael@0:             mHeaderTable[mReferenceSet[index]]->mName.get(),
michael@0:             mHeaderTable[mReferenceSet[index]]->mValue.get()));
michael@0:       OutputHeader(mReferenceSet[index]);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   mAlternateReferenceSet.Clear();
michael@0:   return rv;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::DecodeInteger(uint32_t prefixLen, uint32_t &accum)
michael@0: {
michael@0:   accum = 0;
michael@0: 
michael@0:   if (prefixLen) {
michael@0:     uint32_t mask = (1 << prefixLen) - 1;
michael@0: 
michael@0:     accum = mData[mOffset] & mask;
michael@0:     ++mOffset;
michael@0: 
michael@0:     if (accum != mask) {
michael@0:       // the simple case for small values
michael@0:       return NS_OK;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   uint32_t factor = 1; // 128 ^ 0
michael@0: 
michael@0:   // we need a series of bytes. The high bit signifies if we need another one.
michael@0:   // The first one is a a factor of 128 ^ 0, the next 128 ^1, the next 128 ^2, ..
michael@0: 
michael@0:   if (mOffset >= mDataLen) {
michael@0:     NS_WARNING("Ran out of data to decode integer");
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0:   bool chainBit = mData[mOffset] & 0x80;
michael@0:   accum += (mData[mOffset] & 0x7f) * factor;
michael@0: 
michael@0:   ++mOffset;
michael@0:   factor = factor * 128;
michael@0: 
michael@0:   while (chainBit) {
michael@0:     // really big offsets are just trawling for overflows
michael@0:     if (accum >= 0x800000) {
michael@0:       NS_WARNING("Decoding integer >= 0x800000");
michael@0:       return NS_ERROR_ILLEGAL_VALUE;
michael@0:     }
michael@0: 
michael@0:     if (mOffset >= mDataLen) {
michael@0:       NS_WARNING("Ran out of data to decode integer");
michael@0:       return NS_ERROR_ILLEGAL_VALUE;
michael@0:     }
michael@0:     chainBit = mData[mOffset] & 0x80;
michael@0:     accum += (mData[mOffset] & 0x7f) * factor;
michael@0:     ++mOffset;
michael@0:     factor = factor * 128;
michael@0:   }
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::OutputHeader(const nsACString &name, const nsACString &value)
michael@0: {
michael@0:     // exclusions
michael@0:   if (name.Equals(NS_LITERAL_CSTRING("connection")) ||
michael@0:       name.Equals(NS_LITERAL_CSTRING("host")) ||
michael@0:       name.Equals(NS_LITERAL_CSTRING("keep-alive")) ||
michael@0:       name.Equals(NS_LITERAL_CSTRING("proxy-connection")) ||
michael@0:       name.Equals(NS_LITERAL_CSTRING("te")) ||
michael@0:       name.Equals(NS_LITERAL_CSTRING("transfer-encoding")) ||
michael@0:       name.Equals(NS_LITERAL_CSTRING("upgrade")) ||
michael@0:       name.Equals(("accept-encoding"))) {
michael@0:     nsCString toLog(name);
michael@0:     LOG3(("HTTP Decompressor illegal response header found : %s",
michael@0:           toLog.get()));
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0: 
michael@0:   // Look for upper case characters in the name.
michael@0:   for (const char *cPtr = name.BeginReading();
michael@0:        cPtr && cPtr < name.EndReading();
michael@0:        ++cPtr) {
michael@0:     if (*cPtr <= 'Z' && *cPtr >= 'A') {
michael@0:       nsCString toLog(name);
michael@0:       LOG3(("HTTP Decompressor upper case response header found. [%s]\n",
michael@0:             toLog.get()));
michael@0:       return NS_ERROR_ILLEGAL_VALUE;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Look for CR OR LF in value - could be smuggling Sec 10.3
michael@0:   // can map to space safely
michael@0:   for (const char *cPtr = value.BeginReading();
michael@0:        cPtr && cPtr < value.EndReading();
michael@0:        ++cPtr) {
michael@0:     if (*cPtr == '\r' || *cPtr== '\n') {
michael@0:       char *wPtr = const_cast<char *>(cPtr);
michael@0:       *wPtr = ' ';
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Status comes first
michael@0:   if (name.Equals(NS_LITERAL_CSTRING(":status"))) {
michael@0:     nsAutoCString status(NS_LITERAL_CSTRING("HTTP/2.0 "));
michael@0:     status.Append(value);
michael@0:     status.Append(NS_LITERAL_CSTRING("\r\n"));
michael@0:     mOutput->Insert(status, 0);
michael@0:     mHeaderStatus = value;
michael@0:   } else if (name.Equals(NS_LITERAL_CSTRING(":authority"))) {
michael@0:     mHeaderHost = value;
michael@0:   } else if (name.Equals(NS_LITERAL_CSTRING(":scheme"))) {
michael@0:     mHeaderScheme = value;
michael@0:   } else if (name.Equals(NS_LITERAL_CSTRING(":path"))) {
michael@0:     mHeaderPath = value;
michael@0:   } else if (name.Equals(NS_LITERAL_CSTRING(":method"))) {
michael@0:     mHeaderMethod = value;
michael@0:   }
michael@0: 
michael@0:   // http/2 transport level headers shouldn't be gatewayed into http/1
michael@0:   if(*(name.BeginReading()) == ':') {
michael@0:     LOG3(("HTTP Decompressor not gatewaying %s into http/1",
michael@0:           name.BeginReading()));
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   mOutput->Append(name);
michael@0:   mOutput->Append(NS_LITERAL_CSTRING(": "));
michael@0:   // Special handling for set-cookie according to the spec
michael@0:   bool isSetCookie = name.Equals(NS_LITERAL_CSTRING("set-cookie"));
michael@0:   int32_t valueLen = value.Length();
michael@0:   for (int32_t i = 0; i < valueLen; ++i) {
michael@0:     if (value[i] == '\0') {
michael@0:       if (isSetCookie) {
michael@0:         mOutput->Append(NS_LITERAL_CSTRING("\r\n"));
michael@0:         mOutput->Append(name);
michael@0:         mOutput->Append(NS_LITERAL_CSTRING(": "));
michael@0:       } else {
michael@0:         mOutput->Append(NS_LITERAL_CSTRING(", "));
michael@0:       }
michael@0:     } else {
michael@0:       mOutput->Append(value[i]);
michael@0:     }
michael@0:   }
michael@0:   mOutput->Append(NS_LITERAL_CSTRING("\r\n"));
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::OutputHeader(uint32_t index)
michael@0: {
michael@0:   // bounds check
michael@0:   if (mHeaderTable.Length() <= index)
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0: 
michael@0:   return OutputHeader(mHeaderTable[index]->mName,
michael@0:                       mHeaderTable[index]->mValue);
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::CopyHeaderString(uint32_t index, nsACString &name)
michael@0: {
michael@0:   // bounds check
michael@0:   if (mHeaderTable.Length() <= index)
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0: 
michael@0:   name = mHeaderTable[index]->mName;
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::CopyStringFromInput(uint32_t bytes, nsACString &val)
michael@0: {
michael@0:   if (mOffset + bytes > mDataLen)
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0: 
michael@0:   val.Assign(reinterpret_cast<const char *>(mData) + mOffset, bytes);
michael@0:   mOffset += bytes;
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::DecodeFinalHuffmanCharacter(HuffmanIncomingTable *table,
michael@0:                                                uint8_t &c, uint8_t &bitsLeft)
michael@0: {
michael@0:   uint8_t mask = (1 << bitsLeft) - 1;
michael@0:   uint8_t idx = mData[mOffset - 1] & mask;
michael@0:   idx <<= (8 - bitsLeft);
michael@0:   // Don't update bitsLeft yet, because we need to check that value against the
michael@0:   // number of bits used by our encoding later on. We'll update when we are sure
michael@0:   // how many bits we've actually used.
michael@0: 
michael@0:   HuffmanIncomingEntry *entry = &(table->mEntries[idx]);
michael@0: 
michael@0:   if (entry->mPtr) {
michael@0:     // Can't chain to another table when we're all out of bits in the encoding
michael@0:     LOG3(("DecodeFinalHuffmanCharacter trying to chain when we're out of bits"));
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0: 
michael@0:   if (bitsLeft < entry->mPrefixLen) {
michael@0:     // We don't have enough bits to actually make a match, this is some sort of
michael@0:     // invalid coding
michael@0:     LOG3(("DecodeFinalHuffmanCharacter does't have enough bits to match"));
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0: 
michael@0:   // This is a character!
michael@0:   if (entry->mValue == 256) {
michael@0:     // EOS
michael@0:     LOG3(("DecodeFinalHuffmanCharacter actually decoded an EOS"));
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0:   c = static_cast<uint8_t>(entry->mValue & 0xFF);
michael@0:   bitsLeft -= entry->mPrefixLen;
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: uint8_t
michael@0: Http2Decompressor::ExtractByte(uint8_t bitsLeft, uint32_t &bytesConsumed)
michael@0: {
michael@0:   uint8_t rv;
michael@0: 
michael@0:   if (bitsLeft) {
michael@0:     // Need to extract bitsLeft bits from the previous byte, and 8 - bitsLeft
michael@0:     // bits from the current byte
michael@0:     uint8_t mask = (1 << bitsLeft) - 1;
michael@0:     rv = (mData[mOffset - 1] & mask) << (8 - bitsLeft);
michael@0:     rv |= (mData[mOffset] & ~mask) >> bitsLeft;
michael@0:   } else {
michael@0:     rv = mData[mOffset];
michael@0:   }
michael@0: 
michael@0:   // We always update these here, under the assumption that all 8 bits we got
michael@0:   // here will be used. These may be re-adjusted later in the case that we don't
michael@0:   // use up all 8 bits of the byte.
michael@0:   ++mOffset;
michael@0:   ++bytesConsumed;
michael@0: 
michael@0:   return rv;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::DecodeHuffmanCharacter(HuffmanIncomingTable *table,
michael@0:                                           uint8_t &c, uint32_t &bytesConsumed,
michael@0:                                           uint8_t &bitsLeft)
michael@0: {
michael@0:   uint8_t idx = ExtractByte(bitsLeft, bytesConsumed);
michael@0:   HuffmanIncomingEntry *entry = &(table->mEntries[idx]);
michael@0: 
michael@0:   if (entry->mPtr) {
michael@0:     if (bytesConsumed >= mDataLen) {
michael@0:       if (!bitsLeft || (bytesConsumed > mDataLen)) {
michael@0:         // TODO - does this get me into trouble in the new world?
michael@0:         // No info left in input to try to consume, we're done
michael@0:         LOG3(("DecodeHuffmanCharacter all out of bits to consume, can't chain"));
michael@0:         return NS_ERROR_ILLEGAL_VALUE;
michael@0:       }
michael@0: 
michael@0:       // We might get lucky here!
michael@0:       return DecodeFinalHuffmanCharacter(entry->mPtr, c, bitsLeft);
michael@0:     }
michael@0: 
michael@0:     // We're sorry, Mario, but your princess is in another castle
michael@0:     return DecodeHuffmanCharacter(entry->mPtr, c, bytesConsumed, bitsLeft);
michael@0:   }
michael@0: 
michael@0:   if (entry->mValue == 256) {
michael@0:     LOG3(("DecodeHuffmanCharacter found an actual EOS"));
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0:   c = static_cast<uint8_t>(entry->mValue & 0xFF);
michael@0: 
michael@0:   // Need to adjust bitsLeft (and possibly other values) because we may not have
michael@0:   // consumed all of the bits of the byte we extracted.
michael@0:   if (entry->mPrefixLen <= bitsLeft) {
michael@0:     bitsLeft -= entry->mPrefixLen;
michael@0:     --mOffset;
michael@0:     --bytesConsumed;
michael@0:   } else {
michael@0:     bitsLeft = 8 - (entry->mPrefixLen - bitsLeft);
michael@0:   }
michael@0:   MOZ_ASSERT(bitsLeft < 8);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::CopyHuffmanStringFromInput(uint32_t bytes, nsACString &val)
michael@0: {
michael@0:   if (mOffset + bytes > mDataLen) {
michael@0:     LOG3(("CopyHuffmanStringFromInput not enough data"));
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0: 
michael@0:   uint32_t bytesRead = 0;
michael@0:   uint8_t bitsLeft = 0;
michael@0:   nsAutoCString buf;
michael@0:   nsresult rv;
michael@0:   uint8_t c;
michael@0: 
michael@0:   while (bytesRead < bytes) {
michael@0:     uint32_t bytesConsumed = 0;
michael@0:     rv = DecodeHuffmanCharacter(&HuffmanIncomingRoot, c, bytesConsumed,
michael@0:                                 bitsLeft);
michael@0:     if (NS_FAILED(rv)) {
michael@0:       LOG3(("CopyHuffmanStringFromInput failed to decode a character"));
michael@0:       return rv;
michael@0:     }
michael@0: 
michael@0:     bytesRead += bytesConsumed;
michael@0:     buf.Append(c);
michael@0:   }
michael@0: 
michael@0:   if (bytesRead > bytes) {
michael@0:     LOG3(("CopyHuffmanStringFromInput read more bytes than was allowed!"));
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0: 
michael@0:   if (bitsLeft) {
michael@0:     // The shortest valid code is 4 bits, so we know there can be at most one
michael@0:     // character left that our loop didn't decode. Check to see if that's the
michael@0:     // case, and if so, add it to our output.
michael@0:     rv = DecodeFinalHuffmanCharacter(&HuffmanIncomingRoot, c, bitsLeft);
michael@0:     if (NS_SUCCEEDED(rv)) {
michael@0:       buf.Append(c);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (bitsLeft) {
michael@0:     // Any bits left at this point must belong to the EOS symbol, so make sure
michael@0:     // they make sense (ie, are all ones)
michael@0:     uint8_t mask = (1 << bitsLeft) - 1;
michael@0:     uint8_t bits = mData[mOffset - 1] & mask;
michael@0:     if (bits != mask) {
michael@0:       LOG3(("CopyHuffmanStringFromInput ran out of data but found possible "
michael@0:             "non-EOS symbol"));
michael@0:       return NS_ERROR_ILLEGAL_VALUE;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   val = buf;
michael@0:   LOG3(("CopyHuffmanStringFromInput decoded a full string!"));
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2Decompressor::MakeRoom(uint32_t amount)
michael@0: {
michael@0:   // make room in the header table
michael@0:   uint32_t removedCount = 0;
michael@0:   while (mHeaderTable.VariableLength() && ((mHeaderTable.ByteCount() + amount) > mMaxBuffer)) {
michael@0:     uint32_t index = mHeaderTable.VariableLength() - 1;
michael@0:     mHeaderTable.RemoveElement();
michael@0:     ++removedCount;
michael@0:     LOG3(("HTTP decompressor header table index %u removed for size.\n",
michael@0:           index));
michael@0:   }
michael@0: 
michael@0:   // adjust references to header table
michael@0:   UpdateReferenceSet(removedCount);
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::DoIndexed()
michael@0: {
michael@0:   // this starts with a 1 bit pattern
michael@0:   MOZ_ASSERT(mData[mOffset] & 0x80);
michael@0: 
michael@0:   // Indexed entries toggle the reference set
michael@0:   // This is a 7 bit prefix
michael@0: 
michael@0:   uint32_t index;
michael@0:   nsresult rv = DecodeInteger(7, index);
michael@0:   if (NS_FAILED(rv))
michael@0:     return rv;
michael@0: 
michael@0:   LOG3(("HTTP decompressor indexed entry %u\n", index));
michael@0: 
michael@0:   if (index == 0) {
michael@0:     // Index 0 is a special case - it has extra data tacked on the end to
michael@0:     // determine what kind of change to make to the encoding context.
michael@0:     //
michael@0:     if (mData[mOffset] & 0x80) {
michael@0:       // This means we have to clear out the reference set
michael@0:       mReferenceSet.Clear();
michael@0:       mAlternateReferenceSet.Clear();
michael@0:       ++mOffset;
michael@0:       return NS_OK;
michael@0:     }
michael@0: 
michael@0:     // Getting here means we have to adjust the max table size
michael@0:     uint32_t newMaxSize;
michael@0:     rv = DecodeInteger(7, newMaxSize);
michael@0:     if (NS_FAILED(rv))
michael@0:       return rv;
michael@0:     return mCompressor->SetMaxBufferSizeInternal(newMaxSize);
michael@0:   }
michael@0:   index--; // Internally, we 0-index everything, since this is, y'know, C++
michael@0: 
michael@0:   // Toggle this in the reference set..
michael@0:   // if its not currently in the reference set then add it and
michael@0:   // also emit it. If it is currently in the reference set then just
michael@0:   // remove it from there.
michael@0:   if (mReferenceSet.RemoveElement(index)) {
michael@0:     mAlternateReferenceSet.RemoveElement(index);
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   rv = OutputHeader(index);
michael@0:   if (index >= mHeaderTable.VariableLength()) {
michael@0:     const nvPair *pair = mHeaderTable[index];
michael@0:     uint32_t room = pair->Size();
michael@0: 
michael@0:     if (room > mMaxBuffer) {
michael@0:       ClearHeaderTable();
michael@0:       LOG3(("HTTP decompressor index not referenced due to size %u %s\n",
michael@0:             room, pair->mName.get()));
michael@0:       return rv;
michael@0:     }
michael@0: 
michael@0:     MakeRoom(room);
michael@0:     mHeaderTable.AddElement(pair->mName, pair->mValue);
michael@0:     IncrementReferenceSetIndices();
michael@0:     index = 0;
michael@0:   }
michael@0: 
michael@0:   mReferenceSet.AppendElement(index);
michael@0:   mAlternateReferenceSet.AppendElement(index);
michael@0:   return rv;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::DoLiteralInternal(nsACString &name, nsACString &value)
michael@0: {
michael@0:   // guts of doliteralwithoutindex and doliteralwithincremental
michael@0:   MOZ_ASSERT(((mData[mOffset] & 0xC0) == 0x40) ||  // withoutindex
michael@0:              ((mData[mOffset] & 0xC0) == 0x00));   // withincremental
michael@0: 
michael@0:   // first let's get the name
michael@0:   uint32_t index;
michael@0:   nsresult rv = DecodeInteger(6, index);
michael@0:   if (NS_FAILED(rv))
michael@0:     return rv;
michael@0: 
michael@0:   bool isHuffmanEncoded;
michael@0: 
michael@0:   if (!index) {
michael@0:     // name is embedded as a literal
michael@0:     uint32_t nameLen;
michael@0:     isHuffmanEncoded = mData[mOffset] & (1 << 7);
michael@0:     rv = DecodeInteger(7, nameLen);
michael@0:     if (NS_SUCCEEDED(rv)) {
michael@0:       if (isHuffmanEncoded) {
michael@0:         rv = CopyHuffmanStringFromInput(nameLen, name);
michael@0:       } else {
michael@0:         rv = CopyStringFromInput(nameLen, name);
michael@0:       }
michael@0:     }
michael@0:   } else {
michael@0:     // name is from headertable
michael@0:     rv = CopyHeaderString(index - 1, name);
michael@0:   }
michael@0:   if (NS_FAILED(rv))
michael@0:     return rv;
michael@0: 
michael@0:   // now the value
michael@0:   uint32_t valueLen;
michael@0:   isHuffmanEncoded = mData[mOffset] & (1 << 7);
michael@0:   rv = DecodeInteger(7, valueLen);
michael@0:   if (NS_SUCCEEDED(rv)) {
michael@0:     if (isHuffmanEncoded) {
michael@0:       rv = CopyHuffmanStringFromInput(valueLen, value);
michael@0:     } else {
michael@0:       rv = CopyStringFromInput(valueLen, value);
michael@0:     }
michael@0:   }
michael@0:   if (NS_FAILED(rv))
michael@0:     return rv;
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::DoLiteralWithoutIndex()
michael@0: {
michael@0:   // this starts with 01 bit pattern
michael@0:   MOZ_ASSERT((mData[mOffset] & 0xC0) == 0x40);
michael@0: 
michael@0:   // This is not indexed so there is no adjustment to the
michael@0:   // persistent reference set
michael@0:   nsAutoCString name, value;
michael@0:   nsresult rv = DoLiteralInternal(name, value);
michael@0: 
michael@0:   LOG3(("HTTP decompressor literal without index %s %s\n",
michael@0:         name.get(), value.get()));
michael@0: 
michael@0:   // Output the header now because we don't keep void
michael@0:   // indicies in the reference set
michael@0:   if (NS_SUCCEEDED(rv))
michael@0:     rv = OutputHeader(name, value);
michael@0:   return rv;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Decompressor::DoLiteralWithIncremental()
michael@0: {
michael@0:   // this starts with 00 bit pattern
michael@0:   MOZ_ASSERT((mData[mOffset] & 0xC0) == 0x00);
michael@0: 
michael@0:   nsAutoCString name, value;
michael@0:   nsresult rv = DoLiteralInternal(name, value);
michael@0:   if (NS_SUCCEEDED(rv))
michael@0:     rv = OutputHeader(name, value);
michael@0:   if (NS_FAILED(rv))
michael@0:     return rv;
michael@0: 
michael@0:   uint32_t room = nvPair(name, value).Size();
michael@0:   if (room > mMaxBuffer) {
michael@0:     ClearHeaderTable();
michael@0:     LOG3(("HTTP decompressor literal with index not referenced due to size %u %s\n",
michael@0:           room, name.get()));
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   MakeRoom(room);
michael@0: 
michael@0:   // Incremental Indexing implicitly adds a row to the header table.
michael@0:   // It also adds the new row to the Reference Set
michael@0:   mHeaderTable.AddElement(name, value);
michael@0:   IncrementReferenceSetIndices();
michael@0:   mReferenceSet.AppendElement(0);
michael@0:   mAlternateReferenceSet.AppendElement(0);
michael@0: 
michael@0:   LOG3(("HTTP decompressor literal with index 0 %s %s\n",
michael@0:         name.get(), value.get()));
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: /////////////////////////////////////////////////////////////////
michael@0: 
michael@0: nsresult
michael@0: Http2Compressor::EncodeHeaderBlock(const nsCString &nvInput,
michael@0:                                    const nsACString &method, const nsACString &path,
michael@0:                                    const nsACString &host, const nsACString &scheme,
michael@0:                                    nsACString &output)
michael@0: {
michael@0:   mAlternateReferenceSet.Clear();
michael@0:   mImpliedReferenceSet.Clear();
michael@0:   mOutput = &output;
michael@0:   output.SetCapacity(1024);
michael@0:   output.Truncate();
michael@0:   mParsedContentLength = -1;
michael@0: 
michael@0:   // colon headers first
michael@0:   ProcessHeader(nvPair(NS_LITERAL_CSTRING(":method"), method));
michael@0:   ProcessHeader(nvPair(NS_LITERAL_CSTRING(":path"), path));
michael@0:   ProcessHeader(nvPair(NS_LITERAL_CSTRING(":authority"), host));
michael@0:   ProcessHeader(nvPair(NS_LITERAL_CSTRING(":scheme"), scheme));
michael@0: 
michael@0:   // now the non colon headers
michael@0:   const char *beginBuffer = nvInput.BeginReading();
michael@0: 
michael@0:   int32_t crlfIndex = nvInput.Find("\r\n");
michael@0:   while (true) {
michael@0:     int32_t startIndex = crlfIndex + 2;
michael@0: 
michael@0:     crlfIndex = nvInput.Find("\r\n", false, startIndex);
michael@0:     if (crlfIndex == -1)
michael@0:       break;
michael@0: 
michael@0:     int32_t colonIndex = nvInput.Find(":", false, startIndex,
michael@0:                                       crlfIndex - startIndex);
michael@0:     if (colonIndex == -1)
michael@0:       break;
michael@0: 
michael@0:     nsDependentCSubstring name = Substring(beginBuffer + startIndex,
michael@0:                                            beginBuffer + colonIndex);
michael@0:     // all header names are lower case in http/2
michael@0:     ToLowerCase(name);
michael@0: 
michael@0:     // exclusions
michael@0:     if (name.Equals("connection") ||
michael@0:         name.Equals("host") ||
michael@0:         name.Equals("keep-alive") ||
michael@0:         name.Equals("proxy-connection") ||
michael@0:         name.Equals("te") ||
michael@0:         name.Equals("transfer-encoding") ||
michael@0:         name.Equals("upgrade") ||
michael@0:         name.Equals("accept-encoding")) {
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     // colon headers are for http/2 and this is http/1 input, so that
michael@0:     // is probably a smuggling attack of some kind
michael@0:     if(*(name.BeginReading()) == ':') {
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     int32_t valueIndex = colonIndex + 1;
michael@0: 
michael@0:     // if we have Expect: *100-continue,*" redact the 100-continue
michael@0:     // as we don't have a good mechanism for clients to make use of it
michael@0:     // anyhow
michael@0:     if (name.Equals("expect")) {
michael@0:       const char *continueHeader =
michael@0:         nsHttp::FindToken(beginBuffer + valueIndex, "100-continue",
michael@0:                           HTTP_HEADER_VALUE_SEPS);
michael@0:       if (continueHeader) {
michael@0:         char *writableVal = const_cast<char *>(continueHeader);
michael@0:         memset(writableVal, 0, 12);
michael@0:         writableVal += 12;
michael@0:         // this will terminate safely because CRLF EOL has been confirmed
michael@0:         while ((*writableVal == ' ') || (*writableVal == '\t') ||
michael@0:                (*writableVal == ',')) {
michael@0:           *writableVal = ' ';
michael@0:           ++writableVal;
michael@0:         }
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     while (valueIndex < crlfIndex && beginBuffer[valueIndex] == ' ')
michael@0:       ++valueIndex;
michael@0: 
michael@0:     nsDependentCSubstring value = Substring(beginBuffer + valueIndex,
michael@0:                                             beginBuffer + crlfIndex);
michael@0: 
michael@0:     if (name.Equals("content-length")) {
michael@0:       int64_t len;
michael@0:       nsCString tmp(value);
michael@0:       if (nsHttp::ParseInt64(tmp.get(), nullptr, &len))
michael@0:         mParsedContentLength = len;
michael@0:     }
michael@0: 
michael@0:     if (name.Equals("cookie")) {
michael@0:       // cookie crumbling
michael@0:       bool haveMoreCookies = true;
michael@0:       int32_t nextCookie = valueIndex;
michael@0:       while (haveMoreCookies) {
michael@0:         int32_t semiSpaceIndex = nvInput.Find("; ", false, nextCookie,
michael@0:                                               crlfIndex - nextCookie);
michael@0:         if (semiSpaceIndex == -1) {
michael@0:           haveMoreCookies = false;
michael@0:           semiSpaceIndex = crlfIndex;
michael@0:         }
michael@0:         nsDependentCSubstring cookie = Substring(beginBuffer + nextCookie,
michael@0:                                                  beginBuffer + semiSpaceIndex);
michael@0:         ProcessHeader(nvPair(name, cookie));
michael@0:         nextCookie = semiSpaceIndex + 2;
michael@0:       }
michael@0:     } else {
michael@0:       ProcessHeader(nvPair(name, value));
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // iterate mreference set and if !alternate.contains(old[i])
michael@0:   // toggle off
michael@0:   uint32_t setLen = mReferenceSet.Length();
michael@0:   for (uint32_t index = 0; index < setLen; ++index) {
michael@0:     if (!mAlternateReferenceSet.Contains(mReferenceSet[index])) {
michael@0:       DoOutput(kToggleOff, mHeaderTable[mReferenceSet[index]],
michael@0:                mReferenceSet[index]);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   mReferenceSet = mAlternateReferenceSet;
michael@0:   mAlternateReferenceSet.Clear();
michael@0:   mImpliedReferenceSet.Clear();
michael@0:   mOutput = nullptr;
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2Compressor::DoOutput(Http2Compressor::outputCode code,
michael@0:                           const class nvPair *pair, uint32_t index)
michael@0: {
michael@0:   // start Byte needs to be calculated from the offset after
michael@0:   // the opcode has been written out in case the output stream
michael@0:   // buffer gets resized/relocated
michael@0:   uint32_t offset = mOutput->Length();
michael@0:   uint8_t *startByte;
michael@0: 
michael@0:   switch (code) {
michael@0:   case kPlainLiteral:
michael@0:     LOG3(("HTTP compressor %p noindex literal with name reference %u %s: %s\n",
michael@0:           this, index, pair->mName.get(), pair->mValue.get()));
michael@0: 
michael@0:     // In this case, the index will have already been adjusted to be 1-based
michael@0:     // instead of 0-based.
michael@0:     EncodeInteger(6, index); // 01 2 bit prefix
michael@0:     startByte = reinterpret_cast<unsigned char *>(mOutput->BeginWriting()) + offset;
michael@0:     *startByte = (*startByte & 0x3f) | 0x40;
michael@0: 
michael@0:     if (!index) {
michael@0:       HuffmanAppend(pair->mName);
michael@0:     }
michael@0: 
michael@0:     HuffmanAppend(pair->mValue);
michael@0:     break;
michael@0: 
michael@0:   case kIndexedLiteral:
michael@0:     LOG3(("HTTP compressor %p literal with name reference %u %s: %s\n",
michael@0:           this, index, pair->mName.get(), pair->mValue.get()));
michael@0: 
michael@0:     // In this case, the index will have already been adjusted to be 1-based
michael@0:     // instead of 0-based.
michael@0:     EncodeInteger(6, index); // 00 2 bit prefix
michael@0:     startByte = reinterpret_cast<unsigned char *>(mOutput->BeginWriting()) + offset;
michael@0:     *startByte = *startByte & 0x3f;
michael@0: 
michael@0:     if (!index) {
michael@0:       HuffmanAppend(pair->mName);
michael@0:     }
michael@0: 
michael@0:     HuffmanAppend(pair->mValue);
michael@0:     break;
michael@0: 
michael@0:   case kToggleOff:
michael@0:   case kToggleOn:
michael@0:     LOG3(("HTTP compressor %p toggle %s index %u %s\n",
michael@0:           this, (code == kToggleOff) ? "off" : "on",
michael@0:           index, pair->mName.get()));
michael@0:     // In this case, we are passed the raw 0-based C index, and need to
michael@0:     // increment to make it 1-based and comply with the spec
michael@0:     EncodeInteger(7, index + 1);
michael@0:     startByte = reinterpret_cast<unsigned char *>(mOutput->BeginWriting()) + offset;
michael@0:     *startByte = *startByte | 0x80; // 1 1 bit prefix
michael@0:     break;
michael@0: 
michael@0:   case kNop:
michael@0:     LOG3(("HTTP compressor %p implied in reference set index %u %s\n",
michael@0:           this, index, pair->mName.get()));
michael@0:     break;
michael@0:   }
michael@0: }
michael@0: 
michael@0: // writes the encoded integer onto the output
michael@0: void
michael@0: Http2Compressor::EncodeInteger(uint32_t prefixLen, uint32_t val)
michael@0: {
michael@0:   uint32_t mask = (1 << prefixLen) - 1;
michael@0:   uint8_t tmp;
michael@0: 
michael@0:   if (val < mask) {
michael@0:     // 1 byte encoding!
michael@0:     tmp = val;
michael@0:     mOutput->Append(reinterpret_cast<char *>(&tmp), 1);
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   if (mask) {
michael@0:     val -= mask;
michael@0:     tmp = mask;
michael@0:     mOutput->Append(reinterpret_cast<char *>(&tmp), 1);
michael@0:   }
michael@0: 
michael@0:   uint32_t q, r;
michael@0:   do {
michael@0:     q = val / 128;
michael@0:     r = val % 128;
michael@0:     tmp = r;
michael@0:     if (q)
michael@0:       tmp |= 0x80; // chain bit
michael@0:     val = q;
michael@0:     mOutput->Append(reinterpret_cast<char *>(&tmp), 1);
michael@0:   } while (q);
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2Compressor::ClearHeaderTable()
michael@0: {
michael@0:   uint32_t dynamicCount = mHeaderTable.VariableLength();
michael@0: 
michael@0:   Http2BaseCompressor::ClearHeaderTable();
michael@0: 
michael@0:   for (int32_t i = mImpliedReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     if (mImpliedReferenceSet[i] < dynamicCount) {
michael@0:       mImpliedReferenceSet.RemoveElementAt(i);
michael@0:     } else {
michael@0:       mImpliedReferenceSet[i] -= dynamicCount;
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: Http2Compressor::UpdateReferenceSet(int32_t delta)
michael@0: {
michael@0:   if (!delta)
michael@0:     return;
michael@0: 
michael@0:   Http2BaseCompressor::UpdateReferenceSet(delta);
michael@0: 
michael@0:   uint32_t headerTableSize = mHeaderTable.VariableLength();
michael@0:   uint32_t oldHeaderTableSize = headerTableSize + delta;
michael@0: 
michael@0:   for (int32_t i = mImpliedReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     uint32_t indexRef = mImpliedReferenceSet[i];
michael@0:     if (indexRef >= headerTableSize) {
michael@0:       if (indexRef < oldHeaderTableSize) {
michael@0:         // This one got dropped
michael@0:         LOG3(("HTTP compressor implied reference to index %u removed.\n",
michael@0:               indexRef));
michael@0:         mImpliedReferenceSet.RemoveElementAt(i);
michael@0:       } else {
michael@0:         // This pointed to the static table, need to adjust
michael@0:         uint32_t newRef = indexRef - delta;
michael@0:         LOG3(("HTTP compressor implied reference to index %u changed to %d (%s)\n",
michael@0:               mImpliedReferenceSet[i], newRef, mHeaderTable[newRef]->mName.get()));
michael@0:         mImpliedReferenceSet[i] = newRef;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2Compressor::IncrementReferenceSetIndices()
michael@0: {
michael@0:   Http2BaseCompressor::IncrementReferenceSetIndices();
michael@0: 
michael@0:   for (int32_t i = mImpliedReferenceSet.Length() - 1; i >= 0; --i) {
michael@0:     mImpliedReferenceSet[i] = mImpliedReferenceSet[i] + 1;
michael@0:   }
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2Compressor::MakeRoom(uint32_t amount)
michael@0: {
michael@0:   // make room in the header table
michael@0:   uint32_t removedCount = 0;
michael@0:   while (mHeaderTable.VariableLength() && ((mHeaderTable.ByteCount() + amount) > mMaxBuffer)) {
michael@0: 
michael@0:     // if there is a reference to removedCount (~0) in the implied reference set we need,
michael@0:     // to toggle it off/on so that the implied reference is not lost when the
michael@0:     // table is trimmed
michael@0:     uint32_t index = mHeaderTable.VariableLength() - 1;
michael@0:     if (mImpliedReferenceSet.Contains(index) ) {
michael@0:       LOG3(("HTTP compressor header table index %u %s about to be "
michael@0:             "removed for size but has an implied reference. Will Toggle.\n",
michael@0:             index, mHeaderTable[index]->mName.get()));
michael@0: 
michael@0:       DoOutput(kToggleOff, mHeaderTable[index], index);
michael@0:       DoOutput(kToggleOn, mHeaderTable[index], index);
michael@0:     }
michael@0: 
michael@0:     LOG3(("HTTP compressor header table index %u %s removed for size.\n",
michael@0:           index, mHeaderTable[index]->mName.get()));
michael@0:     mHeaderTable.RemoveElement();
michael@0:     ++removedCount;
michael@0:   }
michael@0: 
michael@0:   // adjust references to header table
michael@0:   UpdateReferenceSet(removedCount);
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2Compressor::HuffmanAppend(const nsCString &value)
michael@0: {
michael@0:   nsAutoCString buf;
michael@0:   uint8_t bitsLeft = 8;
michael@0:   uint32_t length = value.Length();
michael@0:   uint32_t offset;
michael@0:   uint8_t *startByte;
michael@0: 
michael@0:   for (uint32_t i = 0; i < length; ++i) {
michael@0:     uint8_t idx = static_cast<uint8_t>(value[i]);
michael@0:     uint8_t huffLength = HuffmanOutgoing[idx].mLength;
michael@0:     uint32_t huffValue = HuffmanOutgoing[idx].mValue;
michael@0: 
michael@0:     if (bitsLeft < 8) {
michael@0:       // Fill in the least significant <bitsLeft> bits of the previous byte
michael@0:       // first
michael@0:       uint32_t val;
michael@0:       if (huffLength >= bitsLeft) {
michael@0:         val = huffValue & ~((1 << (huffLength - bitsLeft)) - 1);
michael@0:         val >>= (huffLength - bitsLeft);
michael@0:       } else {
michael@0:         val = huffValue << (bitsLeft - huffLength);
michael@0:       }
michael@0:       val &= ((1 << bitsLeft) - 1);
michael@0:       offset = buf.Length() - 1;
michael@0:       startByte = reinterpret_cast<unsigned char *>(buf.BeginWriting()) + offset;
michael@0:       *startByte = *startByte | static_cast<uint8_t>(val & 0xFF);
michael@0:       if (huffLength >= bitsLeft) {
michael@0:         huffLength -= bitsLeft;
michael@0:         bitsLeft = 8;
michael@0:       } else {
michael@0:         bitsLeft -= huffLength;
michael@0:         huffLength = 0;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     while (huffLength > 8) {
michael@0:       uint32_t mask = ~((1 << (huffLength - 8)) - 1);
michael@0:       uint8_t val = ((huffValue & mask) >> (huffLength - 8)) & 0xFF;
michael@0:       buf.Append(reinterpret_cast<char *>(&val), 1);
michael@0:       huffLength -= 8;
michael@0:     }
michael@0: 
michael@0:     if (huffLength) {
michael@0:       // Fill in the most significant <huffLength> bits of the next byte
michael@0:       bitsLeft = 8 - huffLength;
michael@0:       uint8_t val = (huffValue & ((1 << huffLength) - 1)) << bitsLeft;
michael@0:       buf.Append(reinterpret_cast<char *>(&val), 1);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (bitsLeft != 8) {
michael@0:     // Pad the last <bitsLeft> bits with ones, which corresponds to the EOS
michael@0:     // encoding
michael@0:     uint8_t val = (1 << bitsLeft) - 1;
michael@0:     offset = buf.Length() - 1;
michael@0:     startByte = reinterpret_cast<unsigned char *>(buf.BeginWriting()) + offset;
michael@0:     *startByte = *startByte | val;
michael@0:   }
michael@0: 
michael@0:   // Now we know how long our encoded string is, we can fill in our length
michael@0:   uint32_t bufLength = buf.Length();
michael@0:   offset = mOutput->Length();
michael@0:   EncodeInteger(7, bufLength);
michael@0:   startByte = reinterpret_cast<unsigned char *>(mOutput->BeginWriting()) + offset;
michael@0:   *startByte = *startByte | 0x80;
michael@0: 
michael@0:   // Finally, we can add our REAL data!
michael@0:   mOutput->Append(buf);
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2Compressor::ProcessHeader(const nvPair inputPair)
michael@0: {
michael@0:   uint32_t newSize = inputPair.Size();
michael@0:   uint32_t headerTableSize = mHeaderTable.Length();
michael@0:   uint32_t matchedIndex;
michael@0:   uint32_t nameReference = 0;
michael@0:   bool match = false;
michael@0: 
michael@0:   for (uint32_t index = 0; index < headerTableSize; ++index) {
michael@0:     if (mHeaderTable[index]->mName.Equals(inputPair.mName)) {
michael@0:       nameReference = index + 1;
michael@0:       if (mHeaderTable[index]->mValue.Equals(inputPair.mValue)) {
michael@0:         match = true;
michael@0:         matchedIndex = index;
michael@0:         break;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // We need to emit a new literal
michael@0:   if (!match) {
michael@0:     if ((newSize > (mMaxBuffer / 2)) || (mMaxBuffer < 128)) {
michael@0:       DoOutput(kPlainLiteral, &inputPair, nameReference);
michael@0:       return;
michael@0:     }
michael@0: 
michael@0:     // make sure to makeroom() first so that any implied items
michael@0:     // get preserved.
michael@0:     MakeRoom(newSize);
michael@0:     DoOutput(kIndexedLiteral, &inputPair, nameReference);
michael@0: 
michael@0:     mHeaderTable.AddElement(inputPair.mName, inputPair.mValue);
michael@0:     IncrementReferenceSetIndices();
michael@0:     LOG3(("HTTP compressor %p new literal placed at index 0\n",
michael@0:           this));
michael@0:     mAlternateReferenceSet.AppendElement(0);
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   // It is in the reference set. just check to see if it is
michael@0:   // a duplicate for output purposes
michael@0:   if (mReferenceSet.Contains(matchedIndex)) {
michael@0:     if (mAlternateReferenceSet.Contains(matchedIndex)) {
michael@0:       DoOutput(kToggleOff, &inputPair, matchedIndex);
michael@0:       DoOutput(kToggleOn, &inputPair, matchedIndex);
michael@0:     } else {
michael@0:       DoOutput(kNop, &inputPair, matchedIndex);
michael@0:       if (!mImpliedReferenceSet.Contains(matchedIndex))
michael@0:         mImpliedReferenceSet.AppendElement(matchedIndex);
michael@0:       mAlternateReferenceSet.AppendElement(matchedIndex);
michael@0:     }
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   // emit an index to add to reference set
michael@0:   DoOutput(kToggleOn, &inputPair, matchedIndex);
michael@0:   if (matchedIndex >= mHeaderTable.VariableLength()) {
michael@0:     MakeRoom(newSize);
michael@0:     mHeaderTable.AddElement(inputPair.mName, inputPair.mValue);
michael@0:     IncrementReferenceSetIndices();
michael@0:     mAlternateReferenceSet.AppendElement(0);
michael@0:   } else {
michael@0:     mAlternateReferenceSet.AppendElement(matchedIndex);
michael@0:   }
michael@0:   return;
michael@0: }
michael@0: 
michael@0: void
michael@0: Http2Compressor::SetMaxBufferSize(uint32_t maxBufferSize)
michael@0: {
michael@0:   mMaxBufferSetting = maxBufferSize;
michael@0:   SetMaxBufferSizeInternal(maxBufferSize);
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: Http2Compressor::SetMaxBufferSizeInternal(uint32_t maxBufferSize)
michael@0: {
michael@0:   if (maxBufferSize > mMaxBufferSetting) {
michael@0:     return NS_ERROR_ILLEGAL_VALUE;
michael@0:   }
michael@0: 
michael@0:   uint32_t removedCount = 0;
michael@0: 
michael@0:   LOG3(("Http2Compressor::SetMaxBufferSizeInternal %u called", maxBufferSize));
michael@0: 
michael@0:   while (mHeaderTable.VariableLength() && (mHeaderTable.ByteCount() > maxBufferSize)) {
michael@0:     mHeaderTable.RemoveElement();
michael@0:     ++removedCount;
michael@0:   }
michael@0:   UpdateReferenceSet(removedCount);
michael@0: 
michael@0:   mMaxBuffer = maxBufferSize;
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: } // namespace mozilla::net
michael@0: } // namespace mozilla