1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/netwerk/protocol/http/Http2Compression.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1342 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set sw=2 ts=8 et tw=80 : */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +// HttpLog.h should generally be included first
1.11 +#include "HttpLog.h"
1.12 +
1.13 +// Log on level :5, instead of default :4.
1.14 +#undef LOG
1.15 +#define LOG(args) LOG5(args)
1.16 +#undef LOG_ENABLED
1.17 +#define LOG_ENABLED() LOG5_ENABLED()
1.18 +
1.19 +#include "Http2Compression.h"
1.20 +#include "Http2HuffmanIncoming.h"
1.21 +#include "Http2HuffmanOutgoing.h"
1.22 +
1.23 +extern PRThread *gSocketThread;
1.24 +
1.25 +namespace mozilla {
1.26 +namespace net {
1.27 +
1.28 +static nsDeque *gStaticHeaders = nullptr;
1.29 +
1.30 +void
1.31 +Http2CompressionCleanup()
1.32 +{
1.33 + // this happens after the socket thread has been destroyed
1.34 + delete gStaticHeaders;
1.35 + gStaticHeaders = nullptr;
1.36 +}
1.37 +
1.38 +static void
1.39 +AddStaticElement(const nsCString &name, const nsCString &value)
1.40 +{
1.41 + nvPair *pair = new nvPair(name, value);
1.42 + gStaticHeaders->Push(pair);
1.43 +}
1.44 +
1.45 +static void
1.46 +AddStaticElement(const nsCString &name)
1.47 +{
1.48 + AddStaticElement(name, EmptyCString());
1.49 +}
1.50 +
1.51 +static void
1.52 +InitializeStaticHeaders()
1.53 +{
1.54 + MOZ_ASSERT(PR_GetCurrentThread() == gSocketThread);
1.55 + if (!gStaticHeaders) {
1.56 + gStaticHeaders = new nsDeque();
1.57 + AddStaticElement(NS_LITERAL_CSTRING(":authority"));
1.58 + AddStaticElement(NS_LITERAL_CSTRING(":method"), NS_LITERAL_CSTRING("GET"));
1.59 + AddStaticElement(NS_LITERAL_CSTRING(":method"), NS_LITERAL_CSTRING("POST"));
1.60 + AddStaticElement(NS_LITERAL_CSTRING(":path"), NS_LITERAL_CSTRING("/"));
1.61 + AddStaticElement(NS_LITERAL_CSTRING(":path"), NS_LITERAL_CSTRING("/index.html"));
1.62 + AddStaticElement(NS_LITERAL_CSTRING(":scheme"), NS_LITERAL_CSTRING("http"));
1.63 + AddStaticElement(NS_LITERAL_CSTRING(":scheme"), NS_LITERAL_CSTRING("https"));
1.64 + AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("200"));
1.65 + AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("500"));
1.66 + AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("404"));
1.67 + AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("403"));
1.68 + AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("400"));
1.69 + AddStaticElement(NS_LITERAL_CSTRING(":status"), NS_LITERAL_CSTRING("401"));
1.70 + AddStaticElement(NS_LITERAL_CSTRING("accept-charset"));
1.71 + AddStaticElement(NS_LITERAL_CSTRING("accept-encoding"));
1.72 + AddStaticElement(NS_LITERAL_CSTRING("accept-language"));
1.73 + AddStaticElement(NS_LITERAL_CSTRING("accept-ranges"));
1.74 + AddStaticElement(NS_LITERAL_CSTRING("accept"));
1.75 + AddStaticElement(NS_LITERAL_CSTRING("access-control-allow-origin"));
1.76 + AddStaticElement(NS_LITERAL_CSTRING("age"));
1.77 + AddStaticElement(NS_LITERAL_CSTRING("allow"));
1.78 + AddStaticElement(NS_LITERAL_CSTRING("authorization"));
1.79 + AddStaticElement(NS_LITERAL_CSTRING("cache-control"));
1.80 + AddStaticElement(NS_LITERAL_CSTRING("content-disposition"));
1.81 + AddStaticElement(NS_LITERAL_CSTRING("content-encoding"));
1.82 + AddStaticElement(NS_LITERAL_CSTRING("content-language"));
1.83 + AddStaticElement(NS_LITERAL_CSTRING("content-length"));
1.84 + AddStaticElement(NS_LITERAL_CSTRING("content-location"));
1.85 + AddStaticElement(NS_LITERAL_CSTRING("content-range"));
1.86 + AddStaticElement(NS_LITERAL_CSTRING("content-type"));
1.87 + AddStaticElement(NS_LITERAL_CSTRING("cookie"));
1.88 + AddStaticElement(NS_LITERAL_CSTRING("date"));
1.89 + AddStaticElement(NS_LITERAL_CSTRING("etag"));
1.90 + AddStaticElement(NS_LITERAL_CSTRING("expect"));
1.91 + AddStaticElement(NS_LITERAL_CSTRING("expires"));
1.92 + AddStaticElement(NS_LITERAL_CSTRING("from"));
1.93 + AddStaticElement(NS_LITERAL_CSTRING("host"));
1.94 + AddStaticElement(NS_LITERAL_CSTRING("if-match"));
1.95 + AddStaticElement(NS_LITERAL_CSTRING("if-modified-since"));
1.96 + AddStaticElement(NS_LITERAL_CSTRING("if-none-match"));
1.97 + AddStaticElement(NS_LITERAL_CSTRING("if-range"));
1.98 + AddStaticElement(NS_LITERAL_CSTRING("if-unmodified-since"));
1.99 + AddStaticElement(NS_LITERAL_CSTRING("last-modified"));
1.100 + AddStaticElement(NS_LITERAL_CSTRING("link"));
1.101 + AddStaticElement(NS_LITERAL_CSTRING("location"));
1.102 + AddStaticElement(NS_LITERAL_CSTRING("max-forwards"));
1.103 + AddStaticElement(NS_LITERAL_CSTRING("proxy-authenticate"));
1.104 + AddStaticElement(NS_LITERAL_CSTRING("proxy-authorization"));
1.105 + AddStaticElement(NS_LITERAL_CSTRING("range"));
1.106 + AddStaticElement(NS_LITERAL_CSTRING("referer"));
1.107 + AddStaticElement(NS_LITERAL_CSTRING("refresh"));
1.108 + AddStaticElement(NS_LITERAL_CSTRING("retry-after"));
1.109 + AddStaticElement(NS_LITERAL_CSTRING("server"));
1.110 + AddStaticElement(NS_LITERAL_CSTRING("set-cookie"));
1.111 + AddStaticElement(NS_LITERAL_CSTRING("strict-transport-security"));
1.112 + AddStaticElement(NS_LITERAL_CSTRING("transfer-encoding"));
1.113 + AddStaticElement(NS_LITERAL_CSTRING("user-agent"));
1.114 + AddStaticElement(NS_LITERAL_CSTRING("vary"));
1.115 + AddStaticElement(NS_LITERAL_CSTRING("via"));
1.116 + AddStaticElement(NS_LITERAL_CSTRING("www-authenticate"));
1.117 + }
1.118 +}
1.119 +
1.120 +nvFIFO::nvFIFO()
1.121 + : mByteCount(0)
1.122 + , mTable()
1.123 +{
1.124 + InitializeStaticHeaders();
1.125 +}
1.126 +
1.127 +nvFIFO::~nvFIFO()
1.128 +{
1.129 + Clear();
1.130 +}
1.131 +
1.132 +void
1.133 +nvFIFO::AddElement(const nsCString &name, const nsCString &value)
1.134 +{
1.135 + mByteCount += name.Length() + value.Length() + 32;
1.136 + nvPair *pair = new nvPair(name, value);
1.137 + mTable.PushFront(pair);
1.138 +}
1.139 +
1.140 +void
1.141 +nvFIFO::AddElement(const nsCString &name)
1.142 +{
1.143 + AddElement(name, EmptyCString());
1.144 +}
1.145 +
1.146 +void
1.147 +nvFIFO::RemoveElement()
1.148 +{
1.149 + nvPair *pair = static_cast<nvPair *>(mTable.Pop());
1.150 + if (pair) {
1.151 + mByteCount -= pair->Size();
1.152 + delete pair;
1.153 + }
1.154 +}
1.155 +
1.156 +uint32_t
1.157 +nvFIFO::ByteCount() const
1.158 +{
1.159 + return mByteCount;
1.160 +}
1.161 +
1.162 +uint32_t
1.163 +nvFIFO::Length() const
1.164 +{
1.165 + return mTable.GetSize() + gStaticHeaders->GetSize();
1.166 +}
1.167 +
1.168 +uint32_t
1.169 +nvFIFO::VariableLength() const
1.170 +{
1.171 + return mTable.GetSize();
1.172 +}
1.173 +
1.174 +void
1.175 +nvFIFO::Clear()
1.176 +{
1.177 + mByteCount = 0;
1.178 + while (mTable.GetSize())
1.179 + delete static_cast<nvPair *>(mTable.Pop());
1.180 +}
1.181 +
1.182 +const nvPair *
1.183 +nvFIFO::operator[] (int32_t index) const
1.184 +{
1.185 + if (index >= (mTable.GetSize() + gStaticHeaders->GetSize())) {
1.186 + MOZ_ASSERT(false);
1.187 + NS_WARNING("nvFIFO Table Out of Range");
1.188 + return nullptr;
1.189 + }
1.190 + if (index >= mTable.GetSize()) {
1.191 + return static_cast<nvPair *>(gStaticHeaders->ObjectAt(index - mTable.GetSize()));
1.192 + }
1.193 + return static_cast<nvPair *>(mTable.ObjectAt(index));
1.194 +}
1.195 +
1.196 +Http2BaseCompressor::Http2BaseCompressor()
1.197 + : mOutput(nullptr)
1.198 + , mMaxBuffer(kDefaultMaxBuffer)
1.199 +{
1.200 +}
1.201 +
1.202 +void
1.203 +Http2BaseCompressor::ClearHeaderTable()
1.204 +{
1.205 + uint32_t dynamicCount = mHeaderTable.VariableLength();
1.206 + mHeaderTable.Clear();
1.207 +
1.208 + for (int32_t i = mReferenceSet.Length() - 1; i >= 0; --i) {
1.209 + if (mReferenceSet[i] < dynamicCount) {
1.210 + mReferenceSet.RemoveElementAt(i);
1.211 + } else {
1.212 + mReferenceSet[i] -= dynamicCount;
1.213 + }
1.214 + }
1.215 +
1.216 + for (int32_t i = mAlternateReferenceSet.Length() - 1; i >= 0; --i) {
1.217 + if (mAlternateReferenceSet[i] < dynamicCount) {
1.218 + mAlternateReferenceSet.RemoveElementAt(i);
1.219 + } else {
1.220 + mAlternateReferenceSet[i] -= dynamicCount;
1.221 + }
1.222 + }
1.223 +}
1.224 +
1.225 +void
1.226 +Http2BaseCompressor::UpdateReferenceSet(int32_t delta)
1.227 +{
1.228 + if (!delta)
1.229 + return;
1.230 +
1.231 + uint32_t headerTableSize = mHeaderTable.VariableLength();
1.232 + uint32_t oldHeaderTableSize = headerTableSize + delta;
1.233 +
1.234 + for (int32_t i = mReferenceSet.Length() - 1; i >= 0; --i) {
1.235 + uint32_t indexRef = mReferenceSet[i];
1.236 + if (indexRef >= headerTableSize) {
1.237 + if (indexRef < oldHeaderTableSize) {
1.238 + // This one got dropped
1.239 + LOG3(("HTTP base compressor reference to index %u removed.\n",
1.240 + indexRef));
1.241 + mReferenceSet.RemoveElementAt(i);
1.242 + } else {
1.243 + // This pointed to the static table, need to adjust
1.244 + uint32_t newRef = indexRef - delta;
1.245 + LOG3(("HTTP base compressor reference to index %u changed to %d (%s)\n",
1.246 + mReferenceSet[i], newRef, mHeaderTable[newRef]->mName.get()));
1.247 + mReferenceSet[i] = newRef;
1.248 + }
1.249 + }
1.250 + }
1.251 +
1.252 + for (int32_t i = mAlternateReferenceSet.Length() - 1; i >= 0; --i) {
1.253 + uint32_t indexRef = mAlternateReferenceSet[i];
1.254 + if (indexRef >= headerTableSize) {
1.255 + if (indexRef < oldHeaderTableSize) {
1.256 + // This one got dropped
1.257 + LOG3(("HTTP base compressor new reference to index %u removed.\n",
1.258 + indexRef));
1.259 + mAlternateReferenceSet.RemoveElementAt(i);
1.260 + } else {
1.261 + // This pointed to the static table, need to adjust
1.262 + uint32_t newRef = indexRef - delta;
1.263 + LOG3(("HTTP base compressor new reference to index %u changed to %d (%s)\n",
1.264 + mAlternateReferenceSet[i], newRef, mHeaderTable[newRef]->mName.get()));
1.265 + mAlternateReferenceSet[i] = newRef;
1.266 + }
1.267 + }
1.268 + }
1.269 +}
1.270 +
1.271 +void
1.272 +Http2BaseCompressor::IncrementReferenceSetIndices()
1.273 +{
1.274 + for (int32_t i = mReferenceSet.Length() - 1; i >= 0; --i) {
1.275 + mReferenceSet[i] = mReferenceSet[i] + 1;
1.276 + }
1.277 +
1.278 + for (int32_t i = mAlternateReferenceSet.Length() - 1; i >= 0; --i) {
1.279 + mAlternateReferenceSet[i] = mAlternateReferenceSet[i] + 1;
1.280 + }
1.281 +}
1.282 +
1.283 +nsresult
1.284 +Http2Decompressor::DecodeHeaderBlock(const uint8_t *data, uint32_t datalen,
1.285 + nsACString &output)
1.286 +{
1.287 + mAlternateReferenceSet.Clear();
1.288 + mOffset = 0;
1.289 + mData = data;
1.290 + mDataLen = datalen;
1.291 + mOutput = &output;
1.292 + mOutput->Truncate();
1.293 + mHeaderStatus.Truncate();
1.294 + mHeaderHost.Truncate();
1.295 + mHeaderScheme.Truncate();
1.296 + mHeaderPath.Truncate();
1.297 + mHeaderMethod.Truncate();
1.298 +
1.299 + nsresult rv = NS_OK;
1.300 + while (NS_SUCCEEDED(rv) && (mOffset < datalen)) {
1.301 + if (mData[mOffset] & 0x80) {
1.302 + rv = DoIndexed();
1.303 + } else if (mData[mOffset] & 0x40) {
1.304 + rv = DoLiteralWithoutIndex();
1.305 + } else {
1.306 + rv = DoLiteralWithIncremental();
1.307 + }
1.308 + }
1.309 +
1.310 + // after processing the input the decompressor comapres the alternate
1.311 + // set to the inherited reference set and generates headers for
1.312 + // anything implicit in reference - alternate.
1.313 +
1.314 + uint32_t setLen = mReferenceSet.Length();
1.315 + for (uint32_t index = 0; index < setLen; ++index) {
1.316 + if (!mAlternateReferenceSet.Contains(mReferenceSet[index])) {
1.317 + LOG3(("HTTP decompressor carryover in reference set with index %u %s %s\n",
1.318 + mReferenceSet[index],
1.319 + mHeaderTable[mReferenceSet[index]]->mName.get(),
1.320 + mHeaderTable[mReferenceSet[index]]->mValue.get()));
1.321 + OutputHeader(mReferenceSet[index]);
1.322 + }
1.323 + }
1.324 +
1.325 + mAlternateReferenceSet.Clear();
1.326 + return rv;
1.327 +}
1.328 +
1.329 +nsresult
1.330 +Http2Decompressor::DecodeInteger(uint32_t prefixLen, uint32_t &accum)
1.331 +{
1.332 + accum = 0;
1.333 +
1.334 + if (prefixLen) {
1.335 + uint32_t mask = (1 << prefixLen) - 1;
1.336 +
1.337 + accum = mData[mOffset] & mask;
1.338 + ++mOffset;
1.339 +
1.340 + if (accum != mask) {
1.341 + // the simple case for small values
1.342 + return NS_OK;
1.343 + }
1.344 + }
1.345 +
1.346 + uint32_t factor = 1; // 128 ^ 0
1.347 +
1.348 + // we need a series of bytes. The high bit signifies if we need another one.
1.349 + // The first one is a a factor of 128 ^ 0, the next 128 ^1, the next 128 ^2, ..
1.350 +
1.351 + if (mOffset >= mDataLen) {
1.352 + NS_WARNING("Ran out of data to decode integer");
1.353 + return NS_ERROR_ILLEGAL_VALUE;
1.354 + }
1.355 + bool chainBit = mData[mOffset] & 0x80;
1.356 + accum += (mData[mOffset] & 0x7f) * factor;
1.357 +
1.358 + ++mOffset;
1.359 + factor = factor * 128;
1.360 +
1.361 + while (chainBit) {
1.362 + // really big offsets are just trawling for overflows
1.363 + if (accum >= 0x800000) {
1.364 + NS_WARNING("Decoding integer >= 0x800000");
1.365 + return NS_ERROR_ILLEGAL_VALUE;
1.366 + }
1.367 +
1.368 + if (mOffset >= mDataLen) {
1.369 + NS_WARNING("Ran out of data to decode integer");
1.370 + return NS_ERROR_ILLEGAL_VALUE;
1.371 + }
1.372 + chainBit = mData[mOffset] & 0x80;
1.373 + accum += (mData[mOffset] & 0x7f) * factor;
1.374 + ++mOffset;
1.375 + factor = factor * 128;
1.376 + }
1.377 + return NS_OK;
1.378 +}
1.379 +
1.380 +nsresult
1.381 +Http2Decompressor::OutputHeader(const nsACString &name, const nsACString &value)
1.382 +{
1.383 + // exclusions
1.384 + if (name.Equals(NS_LITERAL_CSTRING("connection")) ||
1.385 + name.Equals(NS_LITERAL_CSTRING("host")) ||
1.386 + name.Equals(NS_LITERAL_CSTRING("keep-alive")) ||
1.387 + name.Equals(NS_LITERAL_CSTRING("proxy-connection")) ||
1.388 + name.Equals(NS_LITERAL_CSTRING("te")) ||
1.389 + name.Equals(NS_LITERAL_CSTRING("transfer-encoding")) ||
1.390 + name.Equals(NS_LITERAL_CSTRING("upgrade")) ||
1.391 + name.Equals(("accept-encoding"))) {
1.392 + nsCString toLog(name);
1.393 + LOG3(("HTTP Decompressor illegal response header found : %s",
1.394 + toLog.get()));
1.395 + return NS_ERROR_ILLEGAL_VALUE;
1.396 + }
1.397 +
1.398 + // Look for upper case characters in the name.
1.399 + for (const char *cPtr = name.BeginReading();
1.400 + cPtr && cPtr < name.EndReading();
1.401 + ++cPtr) {
1.402 + if (*cPtr <= 'Z' && *cPtr >= 'A') {
1.403 + nsCString toLog(name);
1.404 + LOG3(("HTTP Decompressor upper case response header found. [%s]\n",
1.405 + toLog.get()));
1.406 + return NS_ERROR_ILLEGAL_VALUE;
1.407 + }
1.408 + }
1.409 +
1.410 + // Look for CR OR LF in value - could be smuggling Sec 10.3
1.411 + // can map to space safely
1.412 + for (const char *cPtr = value.BeginReading();
1.413 + cPtr && cPtr < value.EndReading();
1.414 + ++cPtr) {
1.415 + if (*cPtr == '\r' || *cPtr== '\n') {
1.416 + char *wPtr = const_cast<char *>(cPtr);
1.417 + *wPtr = ' ';
1.418 + }
1.419 + }
1.420 +
1.421 + // Status comes first
1.422 + if (name.Equals(NS_LITERAL_CSTRING(":status"))) {
1.423 + nsAutoCString status(NS_LITERAL_CSTRING("HTTP/2.0 "));
1.424 + status.Append(value);
1.425 + status.Append(NS_LITERAL_CSTRING("\r\n"));
1.426 + mOutput->Insert(status, 0);
1.427 + mHeaderStatus = value;
1.428 + } else if (name.Equals(NS_LITERAL_CSTRING(":authority"))) {
1.429 + mHeaderHost = value;
1.430 + } else if (name.Equals(NS_LITERAL_CSTRING(":scheme"))) {
1.431 + mHeaderScheme = value;
1.432 + } else if (name.Equals(NS_LITERAL_CSTRING(":path"))) {
1.433 + mHeaderPath = value;
1.434 + } else if (name.Equals(NS_LITERAL_CSTRING(":method"))) {
1.435 + mHeaderMethod = value;
1.436 + }
1.437 +
1.438 + // http/2 transport level headers shouldn't be gatewayed into http/1
1.439 + if(*(name.BeginReading()) == ':') {
1.440 + LOG3(("HTTP Decompressor not gatewaying %s into http/1",
1.441 + name.BeginReading()));
1.442 + return NS_OK;
1.443 + }
1.444 +
1.445 + mOutput->Append(name);
1.446 + mOutput->Append(NS_LITERAL_CSTRING(": "));
1.447 + // Special handling for set-cookie according to the spec
1.448 + bool isSetCookie = name.Equals(NS_LITERAL_CSTRING("set-cookie"));
1.449 + int32_t valueLen = value.Length();
1.450 + for (int32_t i = 0; i < valueLen; ++i) {
1.451 + if (value[i] == '\0') {
1.452 + if (isSetCookie) {
1.453 + mOutput->Append(NS_LITERAL_CSTRING("\r\n"));
1.454 + mOutput->Append(name);
1.455 + mOutput->Append(NS_LITERAL_CSTRING(": "));
1.456 + } else {
1.457 + mOutput->Append(NS_LITERAL_CSTRING(", "));
1.458 + }
1.459 + } else {
1.460 + mOutput->Append(value[i]);
1.461 + }
1.462 + }
1.463 + mOutput->Append(NS_LITERAL_CSTRING("\r\n"));
1.464 + return NS_OK;
1.465 +}
1.466 +
1.467 +nsresult
1.468 +Http2Decompressor::OutputHeader(uint32_t index)
1.469 +{
1.470 + // bounds check
1.471 + if (mHeaderTable.Length() <= index)
1.472 + return NS_ERROR_ILLEGAL_VALUE;
1.473 +
1.474 + return OutputHeader(mHeaderTable[index]->mName,
1.475 + mHeaderTable[index]->mValue);
1.476 +}
1.477 +
1.478 +nsresult
1.479 +Http2Decompressor::CopyHeaderString(uint32_t index, nsACString &name)
1.480 +{
1.481 + // bounds check
1.482 + if (mHeaderTable.Length() <= index)
1.483 + return NS_ERROR_ILLEGAL_VALUE;
1.484 +
1.485 + name = mHeaderTable[index]->mName;
1.486 + return NS_OK;
1.487 +}
1.488 +
1.489 +nsresult
1.490 +Http2Decompressor::CopyStringFromInput(uint32_t bytes, nsACString &val)
1.491 +{
1.492 + if (mOffset + bytes > mDataLen)
1.493 + return NS_ERROR_ILLEGAL_VALUE;
1.494 +
1.495 + val.Assign(reinterpret_cast<const char *>(mData) + mOffset, bytes);
1.496 + mOffset += bytes;
1.497 + return NS_OK;
1.498 +}
1.499 +
1.500 +nsresult
1.501 +Http2Decompressor::DecodeFinalHuffmanCharacter(HuffmanIncomingTable *table,
1.502 + uint8_t &c, uint8_t &bitsLeft)
1.503 +{
1.504 + uint8_t mask = (1 << bitsLeft) - 1;
1.505 + uint8_t idx = mData[mOffset - 1] & mask;
1.506 + idx <<= (8 - bitsLeft);
1.507 + // Don't update bitsLeft yet, because we need to check that value against the
1.508 + // number of bits used by our encoding later on. We'll update when we are sure
1.509 + // how many bits we've actually used.
1.510 +
1.511 + HuffmanIncomingEntry *entry = &(table->mEntries[idx]);
1.512 +
1.513 + if (entry->mPtr) {
1.514 + // Can't chain to another table when we're all out of bits in the encoding
1.515 + LOG3(("DecodeFinalHuffmanCharacter trying to chain when we're out of bits"));
1.516 + return NS_ERROR_ILLEGAL_VALUE;
1.517 + }
1.518 +
1.519 + if (bitsLeft < entry->mPrefixLen) {
1.520 + // We don't have enough bits to actually make a match, this is some sort of
1.521 + // invalid coding
1.522 + LOG3(("DecodeFinalHuffmanCharacter does't have enough bits to match"));
1.523 + return NS_ERROR_ILLEGAL_VALUE;
1.524 + }
1.525 +
1.526 + // This is a character!
1.527 + if (entry->mValue == 256) {
1.528 + // EOS
1.529 + LOG3(("DecodeFinalHuffmanCharacter actually decoded an EOS"));
1.530 + return NS_ERROR_ILLEGAL_VALUE;
1.531 + }
1.532 + c = static_cast<uint8_t>(entry->mValue & 0xFF);
1.533 + bitsLeft -= entry->mPrefixLen;
1.534 +
1.535 + return NS_OK;
1.536 +}
1.537 +
1.538 +uint8_t
1.539 +Http2Decompressor::ExtractByte(uint8_t bitsLeft, uint32_t &bytesConsumed)
1.540 +{
1.541 + uint8_t rv;
1.542 +
1.543 + if (bitsLeft) {
1.544 + // Need to extract bitsLeft bits from the previous byte, and 8 - bitsLeft
1.545 + // bits from the current byte
1.546 + uint8_t mask = (1 << bitsLeft) - 1;
1.547 + rv = (mData[mOffset - 1] & mask) << (8 - bitsLeft);
1.548 + rv |= (mData[mOffset] & ~mask) >> bitsLeft;
1.549 + } else {
1.550 + rv = mData[mOffset];
1.551 + }
1.552 +
1.553 + // We always update these here, under the assumption that all 8 bits we got
1.554 + // here will be used. These may be re-adjusted later in the case that we don't
1.555 + // use up all 8 bits of the byte.
1.556 + ++mOffset;
1.557 + ++bytesConsumed;
1.558 +
1.559 + return rv;
1.560 +}
1.561 +
1.562 +nsresult
1.563 +Http2Decompressor::DecodeHuffmanCharacter(HuffmanIncomingTable *table,
1.564 + uint8_t &c, uint32_t &bytesConsumed,
1.565 + uint8_t &bitsLeft)
1.566 +{
1.567 + uint8_t idx = ExtractByte(bitsLeft, bytesConsumed);
1.568 + HuffmanIncomingEntry *entry = &(table->mEntries[idx]);
1.569 +
1.570 + if (entry->mPtr) {
1.571 + if (bytesConsumed >= mDataLen) {
1.572 + if (!bitsLeft || (bytesConsumed > mDataLen)) {
1.573 + // TODO - does this get me into trouble in the new world?
1.574 + // No info left in input to try to consume, we're done
1.575 + LOG3(("DecodeHuffmanCharacter all out of bits to consume, can't chain"));
1.576 + return NS_ERROR_ILLEGAL_VALUE;
1.577 + }
1.578 +
1.579 + // We might get lucky here!
1.580 + return DecodeFinalHuffmanCharacter(entry->mPtr, c, bitsLeft);
1.581 + }
1.582 +
1.583 + // We're sorry, Mario, but your princess is in another castle
1.584 + return DecodeHuffmanCharacter(entry->mPtr, c, bytesConsumed, bitsLeft);
1.585 + }
1.586 +
1.587 + if (entry->mValue == 256) {
1.588 + LOG3(("DecodeHuffmanCharacter found an actual EOS"));
1.589 + return NS_ERROR_ILLEGAL_VALUE;
1.590 + }
1.591 + c = static_cast<uint8_t>(entry->mValue & 0xFF);
1.592 +
1.593 + // Need to adjust bitsLeft (and possibly other values) because we may not have
1.594 + // consumed all of the bits of the byte we extracted.
1.595 + if (entry->mPrefixLen <= bitsLeft) {
1.596 + bitsLeft -= entry->mPrefixLen;
1.597 + --mOffset;
1.598 + --bytesConsumed;
1.599 + } else {
1.600 + bitsLeft = 8 - (entry->mPrefixLen - bitsLeft);
1.601 + }
1.602 + MOZ_ASSERT(bitsLeft < 8);
1.603 +
1.604 + return NS_OK;
1.605 +}
1.606 +
1.607 +nsresult
1.608 +Http2Decompressor::CopyHuffmanStringFromInput(uint32_t bytes, nsACString &val)
1.609 +{
1.610 + if (mOffset + bytes > mDataLen) {
1.611 + LOG3(("CopyHuffmanStringFromInput not enough data"));
1.612 + return NS_ERROR_ILLEGAL_VALUE;
1.613 + }
1.614 +
1.615 + uint32_t bytesRead = 0;
1.616 + uint8_t bitsLeft = 0;
1.617 + nsAutoCString buf;
1.618 + nsresult rv;
1.619 + uint8_t c;
1.620 +
1.621 + while (bytesRead < bytes) {
1.622 + uint32_t bytesConsumed = 0;
1.623 + rv = DecodeHuffmanCharacter(&HuffmanIncomingRoot, c, bytesConsumed,
1.624 + bitsLeft);
1.625 + if (NS_FAILED(rv)) {
1.626 + LOG3(("CopyHuffmanStringFromInput failed to decode a character"));
1.627 + return rv;
1.628 + }
1.629 +
1.630 + bytesRead += bytesConsumed;
1.631 + buf.Append(c);
1.632 + }
1.633 +
1.634 + if (bytesRead > bytes) {
1.635 + LOG3(("CopyHuffmanStringFromInput read more bytes than was allowed!"));
1.636 + return NS_ERROR_ILLEGAL_VALUE;
1.637 + }
1.638 +
1.639 + if (bitsLeft) {
1.640 + // The shortest valid code is 4 bits, so we know there can be at most one
1.641 + // character left that our loop didn't decode. Check to see if that's the
1.642 + // case, and if so, add it to our output.
1.643 + rv = DecodeFinalHuffmanCharacter(&HuffmanIncomingRoot, c, bitsLeft);
1.644 + if (NS_SUCCEEDED(rv)) {
1.645 + buf.Append(c);
1.646 + }
1.647 + }
1.648 +
1.649 + if (bitsLeft) {
1.650 + // Any bits left at this point must belong to the EOS symbol, so make sure
1.651 + // they make sense (ie, are all ones)
1.652 + uint8_t mask = (1 << bitsLeft) - 1;
1.653 + uint8_t bits = mData[mOffset - 1] & mask;
1.654 + if (bits != mask) {
1.655 + LOG3(("CopyHuffmanStringFromInput ran out of data but found possible "
1.656 + "non-EOS symbol"));
1.657 + return NS_ERROR_ILLEGAL_VALUE;
1.658 + }
1.659 + }
1.660 +
1.661 + val = buf;
1.662 + LOG3(("CopyHuffmanStringFromInput decoded a full string!"));
1.663 + return NS_OK;
1.664 +}
1.665 +
1.666 +void
1.667 +Http2Decompressor::MakeRoom(uint32_t amount)
1.668 +{
1.669 + // make room in the header table
1.670 + uint32_t removedCount = 0;
1.671 + while (mHeaderTable.VariableLength() && ((mHeaderTable.ByteCount() + amount) > mMaxBuffer)) {
1.672 + uint32_t index = mHeaderTable.VariableLength() - 1;
1.673 + mHeaderTable.RemoveElement();
1.674 + ++removedCount;
1.675 + LOG3(("HTTP decompressor header table index %u removed for size.\n",
1.676 + index));
1.677 + }
1.678 +
1.679 + // adjust references to header table
1.680 + UpdateReferenceSet(removedCount);
1.681 +}
1.682 +
1.683 +nsresult
1.684 +Http2Decompressor::DoIndexed()
1.685 +{
1.686 + // this starts with a 1 bit pattern
1.687 + MOZ_ASSERT(mData[mOffset] & 0x80);
1.688 +
1.689 + // Indexed entries toggle the reference set
1.690 + // This is a 7 bit prefix
1.691 +
1.692 + uint32_t index;
1.693 + nsresult rv = DecodeInteger(7, index);
1.694 + if (NS_FAILED(rv))
1.695 + return rv;
1.696 +
1.697 + LOG3(("HTTP decompressor indexed entry %u\n", index));
1.698 +
1.699 + if (index == 0) {
1.700 + // Index 0 is a special case - it has extra data tacked on the end to
1.701 + // determine what kind of change to make to the encoding context.
1.702 + //
1.703 + if (mData[mOffset] & 0x80) {
1.704 + // This means we have to clear out the reference set
1.705 + mReferenceSet.Clear();
1.706 + mAlternateReferenceSet.Clear();
1.707 + ++mOffset;
1.708 + return NS_OK;
1.709 + }
1.710 +
1.711 + // Getting here means we have to adjust the max table size
1.712 + uint32_t newMaxSize;
1.713 + rv = DecodeInteger(7, newMaxSize);
1.714 + if (NS_FAILED(rv))
1.715 + return rv;
1.716 + return mCompressor->SetMaxBufferSizeInternal(newMaxSize);
1.717 + }
1.718 + index--; // Internally, we 0-index everything, since this is, y'know, C++
1.719 +
1.720 + // Toggle this in the reference set..
1.721 + // if its not currently in the reference set then add it and
1.722 + // also emit it. If it is currently in the reference set then just
1.723 + // remove it from there.
1.724 + if (mReferenceSet.RemoveElement(index)) {
1.725 + mAlternateReferenceSet.RemoveElement(index);
1.726 + return NS_OK;
1.727 + }
1.728 +
1.729 + rv = OutputHeader(index);
1.730 + if (index >= mHeaderTable.VariableLength()) {
1.731 + const nvPair *pair = mHeaderTable[index];
1.732 + uint32_t room = pair->Size();
1.733 +
1.734 + if (room > mMaxBuffer) {
1.735 + ClearHeaderTable();
1.736 + LOG3(("HTTP decompressor index not referenced due to size %u %s\n",
1.737 + room, pair->mName.get()));
1.738 + return rv;
1.739 + }
1.740 +
1.741 + MakeRoom(room);
1.742 + mHeaderTable.AddElement(pair->mName, pair->mValue);
1.743 + IncrementReferenceSetIndices();
1.744 + index = 0;
1.745 + }
1.746 +
1.747 + mReferenceSet.AppendElement(index);
1.748 + mAlternateReferenceSet.AppendElement(index);
1.749 + return rv;
1.750 +}
1.751 +
1.752 +nsresult
1.753 +Http2Decompressor::DoLiteralInternal(nsACString &name, nsACString &value)
1.754 +{
1.755 + // guts of doliteralwithoutindex and doliteralwithincremental
1.756 + MOZ_ASSERT(((mData[mOffset] & 0xC0) == 0x40) || // withoutindex
1.757 + ((mData[mOffset] & 0xC0) == 0x00)); // withincremental
1.758 +
1.759 + // first let's get the name
1.760 + uint32_t index;
1.761 + nsresult rv = DecodeInteger(6, index);
1.762 + if (NS_FAILED(rv))
1.763 + return rv;
1.764 +
1.765 + bool isHuffmanEncoded;
1.766 +
1.767 + if (!index) {
1.768 + // name is embedded as a literal
1.769 + uint32_t nameLen;
1.770 + isHuffmanEncoded = mData[mOffset] & (1 << 7);
1.771 + rv = DecodeInteger(7, nameLen);
1.772 + if (NS_SUCCEEDED(rv)) {
1.773 + if (isHuffmanEncoded) {
1.774 + rv = CopyHuffmanStringFromInput(nameLen, name);
1.775 + } else {
1.776 + rv = CopyStringFromInput(nameLen, name);
1.777 + }
1.778 + }
1.779 + } else {
1.780 + // name is from headertable
1.781 + rv = CopyHeaderString(index - 1, name);
1.782 + }
1.783 + if (NS_FAILED(rv))
1.784 + return rv;
1.785 +
1.786 + // now the value
1.787 + uint32_t valueLen;
1.788 + isHuffmanEncoded = mData[mOffset] & (1 << 7);
1.789 + rv = DecodeInteger(7, valueLen);
1.790 + if (NS_SUCCEEDED(rv)) {
1.791 + if (isHuffmanEncoded) {
1.792 + rv = CopyHuffmanStringFromInput(valueLen, value);
1.793 + } else {
1.794 + rv = CopyStringFromInput(valueLen, value);
1.795 + }
1.796 + }
1.797 + if (NS_FAILED(rv))
1.798 + return rv;
1.799 + return NS_OK;
1.800 +}
1.801 +
1.802 +nsresult
1.803 +Http2Decompressor::DoLiteralWithoutIndex()
1.804 +{
1.805 + // this starts with 01 bit pattern
1.806 + MOZ_ASSERT((mData[mOffset] & 0xC0) == 0x40);
1.807 +
1.808 + // This is not indexed so there is no adjustment to the
1.809 + // persistent reference set
1.810 + nsAutoCString name, value;
1.811 + nsresult rv = DoLiteralInternal(name, value);
1.812 +
1.813 + LOG3(("HTTP decompressor literal without index %s %s\n",
1.814 + name.get(), value.get()));
1.815 +
1.816 + // Output the header now because we don't keep void
1.817 + // indicies in the reference set
1.818 + if (NS_SUCCEEDED(rv))
1.819 + rv = OutputHeader(name, value);
1.820 + return rv;
1.821 +}
1.822 +
1.823 +nsresult
1.824 +Http2Decompressor::DoLiteralWithIncremental()
1.825 +{
1.826 + // this starts with 00 bit pattern
1.827 + MOZ_ASSERT((mData[mOffset] & 0xC0) == 0x00);
1.828 +
1.829 + nsAutoCString name, value;
1.830 + nsresult rv = DoLiteralInternal(name, value);
1.831 + if (NS_SUCCEEDED(rv))
1.832 + rv = OutputHeader(name, value);
1.833 + if (NS_FAILED(rv))
1.834 + return rv;
1.835 +
1.836 + uint32_t room = nvPair(name, value).Size();
1.837 + if (room > mMaxBuffer) {
1.838 + ClearHeaderTable();
1.839 + LOG3(("HTTP decompressor literal with index not referenced due to size %u %s\n",
1.840 + room, name.get()));
1.841 + return NS_OK;
1.842 + }
1.843 +
1.844 + MakeRoom(room);
1.845 +
1.846 + // Incremental Indexing implicitly adds a row to the header table.
1.847 + // It also adds the new row to the Reference Set
1.848 + mHeaderTable.AddElement(name, value);
1.849 + IncrementReferenceSetIndices();
1.850 + mReferenceSet.AppendElement(0);
1.851 + mAlternateReferenceSet.AppendElement(0);
1.852 +
1.853 + LOG3(("HTTP decompressor literal with index 0 %s %s\n",
1.854 + name.get(), value.get()));
1.855 +
1.856 + return NS_OK;
1.857 +}
1.858 +
1.859 +/////////////////////////////////////////////////////////////////
1.860 +
1.861 +nsresult
1.862 +Http2Compressor::EncodeHeaderBlock(const nsCString &nvInput,
1.863 + const nsACString &method, const nsACString &path,
1.864 + const nsACString &host, const nsACString &scheme,
1.865 + nsACString &output)
1.866 +{
1.867 + mAlternateReferenceSet.Clear();
1.868 + mImpliedReferenceSet.Clear();
1.869 + mOutput = &output;
1.870 + output.SetCapacity(1024);
1.871 + output.Truncate();
1.872 + mParsedContentLength = -1;
1.873 +
1.874 + // colon headers first
1.875 + ProcessHeader(nvPair(NS_LITERAL_CSTRING(":method"), method));
1.876 + ProcessHeader(nvPair(NS_LITERAL_CSTRING(":path"), path));
1.877 + ProcessHeader(nvPair(NS_LITERAL_CSTRING(":authority"), host));
1.878 + ProcessHeader(nvPair(NS_LITERAL_CSTRING(":scheme"), scheme));
1.879 +
1.880 + // now the non colon headers
1.881 + const char *beginBuffer = nvInput.BeginReading();
1.882 +
1.883 + int32_t crlfIndex = nvInput.Find("\r\n");
1.884 + while (true) {
1.885 + int32_t startIndex = crlfIndex + 2;
1.886 +
1.887 + crlfIndex = nvInput.Find("\r\n", false, startIndex);
1.888 + if (crlfIndex == -1)
1.889 + break;
1.890 +
1.891 + int32_t colonIndex = nvInput.Find(":", false, startIndex,
1.892 + crlfIndex - startIndex);
1.893 + if (colonIndex == -1)
1.894 + break;
1.895 +
1.896 + nsDependentCSubstring name = Substring(beginBuffer + startIndex,
1.897 + beginBuffer + colonIndex);
1.898 + // all header names are lower case in http/2
1.899 + ToLowerCase(name);
1.900 +
1.901 + // exclusions
1.902 + if (name.Equals("connection") ||
1.903 + name.Equals("host") ||
1.904 + name.Equals("keep-alive") ||
1.905 + name.Equals("proxy-connection") ||
1.906 + name.Equals("te") ||
1.907 + name.Equals("transfer-encoding") ||
1.908 + name.Equals("upgrade") ||
1.909 + name.Equals("accept-encoding")) {
1.910 + continue;
1.911 + }
1.912 +
1.913 + // colon headers are for http/2 and this is http/1 input, so that
1.914 + // is probably a smuggling attack of some kind
1.915 + if(*(name.BeginReading()) == ':') {
1.916 + continue;
1.917 + }
1.918 +
1.919 + int32_t valueIndex = colonIndex + 1;
1.920 +
1.921 + // if we have Expect: *100-continue,*" redact the 100-continue
1.922 + // as we don't have a good mechanism for clients to make use of it
1.923 + // anyhow
1.924 + if (name.Equals("expect")) {
1.925 + const char *continueHeader =
1.926 + nsHttp::FindToken(beginBuffer + valueIndex, "100-continue",
1.927 + HTTP_HEADER_VALUE_SEPS);
1.928 + if (continueHeader) {
1.929 + char *writableVal = const_cast<char *>(continueHeader);
1.930 + memset(writableVal, 0, 12);
1.931 + writableVal += 12;
1.932 + // this will terminate safely because CRLF EOL has been confirmed
1.933 + while ((*writableVal == ' ') || (*writableVal == '\t') ||
1.934 + (*writableVal == ',')) {
1.935 + *writableVal = ' ';
1.936 + ++writableVal;
1.937 + }
1.938 + }
1.939 + }
1.940 +
1.941 + while (valueIndex < crlfIndex && beginBuffer[valueIndex] == ' ')
1.942 + ++valueIndex;
1.943 +
1.944 + nsDependentCSubstring value = Substring(beginBuffer + valueIndex,
1.945 + beginBuffer + crlfIndex);
1.946 +
1.947 + if (name.Equals("content-length")) {
1.948 + int64_t len;
1.949 + nsCString tmp(value);
1.950 + if (nsHttp::ParseInt64(tmp.get(), nullptr, &len))
1.951 + mParsedContentLength = len;
1.952 + }
1.953 +
1.954 + if (name.Equals("cookie")) {
1.955 + // cookie crumbling
1.956 + bool haveMoreCookies = true;
1.957 + int32_t nextCookie = valueIndex;
1.958 + while (haveMoreCookies) {
1.959 + int32_t semiSpaceIndex = nvInput.Find("; ", false, nextCookie,
1.960 + crlfIndex - nextCookie);
1.961 + if (semiSpaceIndex == -1) {
1.962 + haveMoreCookies = false;
1.963 + semiSpaceIndex = crlfIndex;
1.964 + }
1.965 + nsDependentCSubstring cookie = Substring(beginBuffer + nextCookie,
1.966 + beginBuffer + semiSpaceIndex);
1.967 + ProcessHeader(nvPair(name, cookie));
1.968 + nextCookie = semiSpaceIndex + 2;
1.969 + }
1.970 + } else {
1.971 + ProcessHeader(nvPair(name, value));
1.972 + }
1.973 + }
1.974 +
1.975 + // iterate mreference set and if !alternate.contains(old[i])
1.976 + // toggle off
1.977 + uint32_t setLen = mReferenceSet.Length();
1.978 + for (uint32_t index = 0; index < setLen; ++index) {
1.979 + if (!mAlternateReferenceSet.Contains(mReferenceSet[index])) {
1.980 + DoOutput(kToggleOff, mHeaderTable[mReferenceSet[index]],
1.981 + mReferenceSet[index]);
1.982 + }
1.983 + }
1.984 +
1.985 + mReferenceSet = mAlternateReferenceSet;
1.986 + mAlternateReferenceSet.Clear();
1.987 + mImpliedReferenceSet.Clear();
1.988 + mOutput = nullptr;
1.989 + return NS_OK;
1.990 +}
1.991 +
1.992 +void
1.993 +Http2Compressor::DoOutput(Http2Compressor::outputCode code,
1.994 + const class nvPair *pair, uint32_t index)
1.995 +{
1.996 + // start Byte needs to be calculated from the offset after
1.997 + // the opcode has been written out in case the output stream
1.998 + // buffer gets resized/relocated
1.999 + uint32_t offset = mOutput->Length();
1.1000 + uint8_t *startByte;
1.1001 +
1.1002 + switch (code) {
1.1003 + case kPlainLiteral:
1.1004 + LOG3(("HTTP compressor %p noindex literal with name reference %u %s: %s\n",
1.1005 + this, index, pair->mName.get(), pair->mValue.get()));
1.1006 +
1.1007 + // In this case, the index will have already been adjusted to be 1-based
1.1008 + // instead of 0-based.
1.1009 + EncodeInteger(6, index); // 01 2 bit prefix
1.1010 + startByte = reinterpret_cast<unsigned char *>(mOutput->BeginWriting()) + offset;
1.1011 + *startByte = (*startByte & 0x3f) | 0x40;
1.1012 +
1.1013 + if (!index) {
1.1014 + HuffmanAppend(pair->mName);
1.1015 + }
1.1016 +
1.1017 + HuffmanAppend(pair->mValue);
1.1018 + break;
1.1019 +
1.1020 + case kIndexedLiteral:
1.1021 + LOG3(("HTTP compressor %p literal with name reference %u %s: %s\n",
1.1022 + this, index, pair->mName.get(), pair->mValue.get()));
1.1023 +
1.1024 + // In this case, the index will have already been adjusted to be 1-based
1.1025 + // instead of 0-based.
1.1026 + EncodeInteger(6, index); // 00 2 bit prefix
1.1027 + startByte = reinterpret_cast<unsigned char *>(mOutput->BeginWriting()) + offset;
1.1028 + *startByte = *startByte & 0x3f;
1.1029 +
1.1030 + if (!index) {
1.1031 + HuffmanAppend(pair->mName);
1.1032 + }
1.1033 +
1.1034 + HuffmanAppend(pair->mValue);
1.1035 + break;
1.1036 +
1.1037 + case kToggleOff:
1.1038 + case kToggleOn:
1.1039 + LOG3(("HTTP compressor %p toggle %s index %u %s\n",
1.1040 + this, (code == kToggleOff) ? "off" : "on",
1.1041 + index, pair->mName.get()));
1.1042 + // In this case, we are passed the raw 0-based C index, and need to
1.1043 + // increment to make it 1-based and comply with the spec
1.1044 + EncodeInteger(7, index + 1);
1.1045 + startByte = reinterpret_cast<unsigned char *>(mOutput->BeginWriting()) + offset;
1.1046 + *startByte = *startByte | 0x80; // 1 1 bit prefix
1.1047 + break;
1.1048 +
1.1049 + case kNop:
1.1050 + LOG3(("HTTP compressor %p implied in reference set index %u %s\n",
1.1051 + this, index, pair->mName.get()));
1.1052 + break;
1.1053 + }
1.1054 +}
1.1055 +
1.1056 +// writes the encoded integer onto the output
1.1057 +void
1.1058 +Http2Compressor::EncodeInteger(uint32_t prefixLen, uint32_t val)
1.1059 +{
1.1060 + uint32_t mask = (1 << prefixLen) - 1;
1.1061 + uint8_t tmp;
1.1062 +
1.1063 + if (val < mask) {
1.1064 + // 1 byte encoding!
1.1065 + tmp = val;
1.1066 + mOutput->Append(reinterpret_cast<char *>(&tmp), 1);
1.1067 + return;
1.1068 + }
1.1069 +
1.1070 + if (mask) {
1.1071 + val -= mask;
1.1072 + tmp = mask;
1.1073 + mOutput->Append(reinterpret_cast<char *>(&tmp), 1);
1.1074 + }
1.1075 +
1.1076 + uint32_t q, r;
1.1077 + do {
1.1078 + q = val / 128;
1.1079 + r = val % 128;
1.1080 + tmp = r;
1.1081 + if (q)
1.1082 + tmp |= 0x80; // chain bit
1.1083 + val = q;
1.1084 + mOutput->Append(reinterpret_cast<char *>(&tmp), 1);
1.1085 + } while (q);
1.1086 +}
1.1087 +
1.1088 +void
1.1089 +Http2Compressor::ClearHeaderTable()
1.1090 +{
1.1091 + uint32_t dynamicCount = mHeaderTable.VariableLength();
1.1092 +
1.1093 + Http2BaseCompressor::ClearHeaderTable();
1.1094 +
1.1095 + for (int32_t i = mImpliedReferenceSet.Length() - 1; i >= 0; --i) {
1.1096 + if (mImpliedReferenceSet[i] < dynamicCount) {
1.1097 + mImpliedReferenceSet.RemoveElementAt(i);
1.1098 + } else {
1.1099 + mImpliedReferenceSet[i] -= dynamicCount;
1.1100 + }
1.1101 + }
1.1102 +}
1.1103 +
1.1104 +
1.1105 +void
1.1106 +Http2Compressor::UpdateReferenceSet(int32_t delta)
1.1107 +{
1.1108 + if (!delta)
1.1109 + return;
1.1110 +
1.1111 + Http2BaseCompressor::UpdateReferenceSet(delta);
1.1112 +
1.1113 + uint32_t headerTableSize = mHeaderTable.VariableLength();
1.1114 + uint32_t oldHeaderTableSize = headerTableSize + delta;
1.1115 +
1.1116 + for (int32_t i = mImpliedReferenceSet.Length() - 1; i >= 0; --i) {
1.1117 + uint32_t indexRef = mImpliedReferenceSet[i];
1.1118 + if (indexRef >= headerTableSize) {
1.1119 + if (indexRef < oldHeaderTableSize) {
1.1120 + // This one got dropped
1.1121 + LOG3(("HTTP compressor implied reference to index %u removed.\n",
1.1122 + indexRef));
1.1123 + mImpliedReferenceSet.RemoveElementAt(i);
1.1124 + } else {
1.1125 + // This pointed to the static table, need to adjust
1.1126 + uint32_t newRef = indexRef - delta;
1.1127 + LOG3(("HTTP compressor implied reference to index %u changed to %d (%s)\n",
1.1128 + mImpliedReferenceSet[i], newRef, mHeaderTable[newRef]->mName.get()));
1.1129 + mImpliedReferenceSet[i] = newRef;
1.1130 + }
1.1131 + }
1.1132 + }
1.1133 +}
1.1134 +
1.1135 +void
1.1136 +Http2Compressor::IncrementReferenceSetIndices()
1.1137 +{
1.1138 + Http2BaseCompressor::IncrementReferenceSetIndices();
1.1139 +
1.1140 + for (int32_t i = mImpliedReferenceSet.Length() - 1; i >= 0; --i) {
1.1141 + mImpliedReferenceSet[i] = mImpliedReferenceSet[i] + 1;
1.1142 + }
1.1143 +}
1.1144 +
1.1145 +void
1.1146 +Http2Compressor::MakeRoom(uint32_t amount)
1.1147 +{
1.1148 + // make room in the header table
1.1149 + uint32_t removedCount = 0;
1.1150 + while (mHeaderTable.VariableLength() && ((mHeaderTable.ByteCount() + amount) > mMaxBuffer)) {
1.1151 +
1.1152 + // if there is a reference to removedCount (~0) in the implied reference set we need,
1.1153 + // to toggle it off/on so that the implied reference is not lost when the
1.1154 + // table is trimmed
1.1155 + uint32_t index = mHeaderTable.VariableLength() - 1;
1.1156 + if (mImpliedReferenceSet.Contains(index) ) {
1.1157 + LOG3(("HTTP compressor header table index %u %s about to be "
1.1158 + "removed for size but has an implied reference. Will Toggle.\n",
1.1159 + index, mHeaderTable[index]->mName.get()));
1.1160 +
1.1161 + DoOutput(kToggleOff, mHeaderTable[index], index);
1.1162 + DoOutput(kToggleOn, mHeaderTable[index], index);
1.1163 + }
1.1164 +
1.1165 + LOG3(("HTTP compressor header table index %u %s removed for size.\n",
1.1166 + index, mHeaderTable[index]->mName.get()));
1.1167 + mHeaderTable.RemoveElement();
1.1168 + ++removedCount;
1.1169 + }
1.1170 +
1.1171 + // adjust references to header table
1.1172 + UpdateReferenceSet(removedCount);
1.1173 +}
1.1174 +
1.1175 +void
1.1176 +Http2Compressor::HuffmanAppend(const nsCString &value)
1.1177 +{
1.1178 + nsAutoCString buf;
1.1179 + uint8_t bitsLeft = 8;
1.1180 + uint32_t length = value.Length();
1.1181 + uint32_t offset;
1.1182 + uint8_t *startByte;
1.1183 +
1.1184 + for (uint32_t i = 0; i < length; ++i) {
1.1185 + uint8_t idx = static_cast<uint8_t>(value[i]);
1.1186 + uint8_t huffLength = HuffmanOutgoing[idx].mLength;
1.1187 + uint32_t huffValue = HuffmanOutgoing[idx].mValue;
1.1188 +
1.1189 + if (bitsLeft < 8) {
1.1190 + // Fill in the least significant <bitsLeft> bits of the previous byte
1.1191 + // first
1.1192 + uint32_t val;
1.1193 + if (huffLength >= bitsLeft) {
1.1194 + val = huffValue & ~((1 << (huffLength - bitsLeft)) - 1);
1.1195 + val >>= (huffLength - bitsLeft);
1.1196 + } else {
1.1197 + val = huffValue << (bitsLeft - huffLength);
1.1198 + }
1.1199 + val &= ((1 << bitsLeft) - 1);
1.1200 + offset = buf.Length() - 1;
1.1201 + startByte = reinterpret_cast<unsigned char *>(buf.BeginWriting()) + offset;
1.1202 + *startByte = *startByte | static_cast<uint8_t>(val & 0xFF);
1.1203 + if (huffLength >= bitsLeft) {
1.1204 + huffLength -= bitsLeft;
1.1205 + bitsLeft = 8;
1.1206 + } else {
1.1207 + bitsLeft -= huffLength;
1.1208 + huffLength = 0;
1.1209 + }
1.1210 + }
1.1211 +
1.1212 + while (huffLength > 8) {
1.1213 + uint32_t mask = ~((1 << (huffLength - 8)) - 1);
1.1214 + uint8_t val = ((huffValue & mask) >> (huffLength - 8)) & 0xFF;
1.1215 + buf.Append(reinterpret_cast<char *>(&val), 1);
1.1216 + huffLength -= 8;
1.1217 + }
1.1218 +
1.1219 + if (huffLength) {
1.1220 + // Fill in the most significant <huffLength> bits of the next byte
1.1221 + bitsLeft = 8 - huffLength;
1.1222 + uint8_t val = (huffValue & ((1 << huffLength) - 1)) << bitsLeft;
1.1223 + buf.Append(reinterpret_cast<char *>(&val), 1);
1.1224 + }
1.1225 + }
1.1226 +
1.1227 + if (bitsLeft != 8) {
1.1228 + // Pad the last <bitsLeft> bits with ones, which corresponds to the EOS
1.1229 + // encoding
1.1230 + uint8_t val = (1 << bitsLeft) - 1;
1.1231 + offset = buf.Length() - 1;
1.1232 + startByte = reinterpret_cast<unsigned char *>(buf.BeginWriting()) + offset;
1.1233 + *startByte = *startByte | val;
1.1234 + }
1.1235 +
1.1236 + // Now we know how long our encoded string is, we can fill in our length
1.1237 + uint32_t bufLength = buf.Length();
1.1238 + offset = mOutput->Length();
1.1239 + EncodeInteger(7, bufLength);
1.1240 + startByte = reinterpret_cast<unsigned char *>(mOutput->BeginWriting()) + offset;
1.1241 + *startByte = *startByte | 0x80;
1.1242 +
1.1243 + // Finally, we can add our REAL data!
1.1244 + mOutput->Append(buf);
1.1245 +}
1.1246 +
1.1247 +void
1.1248 +Http2Compressor::ProcessHeader(const nvPair inputPair)
1.1249 +{
1.1250 + uint32_t newSize = inputPair.Size();
1.1251 + uint32_t headerTableSize = mHeaderTable.Length();
1.1252 + uint32_t matchedIndex;
1.1253 + uint32_t nameReference = 0;
1.1254 + bool match = false;
1.1255 +
1.1256 + for (uint32_t index = 0; index < headerTableSize; ++index) {
1.1257 + if (mHeaderTable[index]->mName.Equals(inputPair.mName)) {
1.1258 + nameReference = index + 1;
1.1259 + if (mHeaderTable[index]->mValue.Equals(inputPair.mValue)) {
1.1260 + match = true;
1.1261 + matchedIndex = index;
1.1262 + break;
1.1263 + }
1.1264 + }
1.1265 + }
1.1266 +
1.1267 + // We need to emit a new literal
1.1268 + if (!match) {
1.1269 + if ((newSize > (mMaxBuffer / 2)) || (mMaxBuffer < 128)) {
1.1270 + DoOutput(kPlainLiteral, &inputPair, nameReference);
1.1271 + return;
1.1272 + }
1.1273 +
1.1274 + // make sure to makeroom() first so that any implied items
1.1275 + // get preserved.
1.1276 + MakeRoom(newSize);
1.1277 + DoOutput(kIndexedLiteral, &inputPair, nameReference);
1.1278 +
1.1279 + mHeaderTable.AddElement(inputPair.mName, inputPair.mValue);
1.1280 + IncrementReferenceSetIndices();
1.1281 + LOG3(("HTTP compressor %p new literal placed at index 0\n",
1.1282 + this));
1.1283 + mAlternateReferenceSet.AppendElement(0);
1.1284 + return;
1.1285 + }
1.1286 +
1.1287 + // It is in the reference set. just check to see if it is
1.1288 + // a duplicate for output purposes
1.1289 + if (mReferenceSet.Contains(matchedIndex)) {
1.1290 + if (mAlternateReferenceSet.Contains(matchedIndex)) {
1.1291 + DoOutput(kToggleOff, &inputPair, matchedIndex);
1.1292 + DoOutput(kToggleOn, &inputPair, matchedIndex);
1.1293 + } else {
1.1294 + DoOutput(kNop, &inputPair, matchedIndex);
1.1295 + if (!mImpliedReferenceSet.Contains(matchedIndex))
1.1296 + mImpliedReferenceSet.AppendElement(matchedIndex);
1.1297 + mAlternateReferenceSet.AppendElement(matchedIndex);
1.1298 + }
1.1299 + return;
1.1300 + }
1.1301 +
1.1302 + // emit an index to add to reference set
1.1303 + DoOutput(kToggleOn, &inputPair, matchedIndex);
1.1304 + if (matchedIndex >= mHeaderTable.VariableLength()) {
1.1305 + MakeRoom(newSize);
1.1306 + mHeaderTable.AddElement(inputPair.mName, inputPair.mValue);
1.1307 + IncrementReferenceSetIndices();
1.1308 + mAlternateReferenceSet.AppendElement(0);
1.1309 + } else {
1.1310 + mAlternateReferenceSet.AppendElement(matchedIndex);
1.1311 + }
1.1312 + return;
1.1313 +}
1.1314 +
1.1315 +void
1.1316 +Http2Compressor::SetMaxBufferSize(uint32_t maxBufferSize)
1.1317 +{
1.1318 + mMaxBufferSetting = maxBufferSize;
1.1319 + SetMaxBufferSizeInternal(maxBufferSize);
1.1320 +}
1.1321 +
1.1322 +nsresult
1.1323 +Http2Compressor::SetMaxBufferSizeInternal(uint32_t maxBufferSize)
1.1324 +{
1.1325 + if (maxBufferSize > mMaxBufferSetting) {
1.1326 + return NS_ERROR_ILLEGAL_VALUE;
1.1327 + }
1.1328 +
1.1329 + uint32_t removedCount = 0;
1.1330 +
1.1331 + LOG3(("Http2Compressor::SetMaxBufferSizeInternal %u called", maxBufferSize));
1.1332 +
1.1333 + while (mHeaderTable.VariableLength() && (mHeaderTable.ByteCount() > maxBufferSize)) {
1.1334 + mHeaderTable.RemoveElement();
1.1335 + ++removedCount;
1.1336 + }
1.1337 + UpdateReferenceSet(removedCount);
1.1338 +
1.1339 + mMaxBuffer = maxBufferSize;
1.1340 +
1.1341 + return NS_OK;
1.1342 +}
1.1343 +
1.1344 +} // namespace mozilla::net
1.1345 +} // namespace mozilla
