Modify HTTP/2 varint encoder and decoder to support 8-bit prefixes. This is necessary for QPACK for Largest Reference in Header Data Prefix, see https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#rfc.section.4.5.1. Fortunately all the logic trivially handles this case, only DCHECKs need to be relaxed. gfe-relnote: n/a (Relax DCHECKs in production code and modify tests.) PiperOrigin-RevId: 225873577 Change-Id: Ib29268cff712b48bfbb93cfb130b10f58e3532ff
diff --git a/http2/hpack/tools/hpack_block_builder.cc b/http2/hpack/tools/hpack_block_builder.cc index 7a7d348..5a79f78 100644 --- a/http2/hpack/tools/hpack_block_builder.cc +++ b/http2/hpack/tools/hpack_block_builder.cc
@@ -15,7 +15,7 @@ uint8_t prefix_length, uint64_t varint) { EXPECT_LE(3, prefix_length); - EXPECT_LE(prefix_length, 7); + EXPECT_LE(prefix_length, 8); HpackVarintEncoder varint_encoder;
diff --git a/http2/hpack/varint/hpack_varint_decoder.cc b/http2/hpack/varint/hpack_varint_decoder.cc index 1f9b6f6..dd64025 100644 --- a/http2/hpack/varint/hpack_varint_decoder.cc +++ b/http2/hpack/varint/hpack_varint_decoder.cc
@@ -13,7 +13,7 @@ uint8_t prefix_length, DecodeBuffer* db) { DCHECK_LE(3u, prefix_length); - DCHECK_LE(prefix_length, 7u); + DCHECK_LE(prefix_length, 8u); // |prefix_mask| defines the sequence of low-order bits of the first byte // that encode the prefix of the value. It is also the marker in those bits @@ -35,7 +35,7 @@ DecodeStatus HpackVarintDecoder::StartExtended(uint8_t prefix_length, DecodeBuffer* db) { DCHECK_LE(3u, prefix_length); - DCHECK_LE(prefix_length, 7u); + DCHECK_LE(prefix_length, 8u); value_ = (1 << prefix_length) - 1; offset_ = 0;
diff --git a/http2/hpack/varint/hpack_varint_decoder.h b/http2/hpack/varint/hpack_varint_decoder.h index ac8118d..c793500 100644 --- a/http2/hpack/varint/hpack_varint_decoder.h +++ b/http2/hpack/varint/hpack_varint_decoder.h
@@ -74,7 +74,7 @@ DecodeBuffer* db); // The caller has already determined that the encoding requires multiple - // bytes, i.e. that the 3 to 7 low-order bits (the number determined by + // bytes, i.e. that the 3 to 8 low-order bits (the number determined by // |prefix_length|) of the first byte are are all 1. |db| is the rest of the // buffer, that is, not including the first byte. DecodeStatus StartExtended(uint8_t prefix_length, DecodeBuffer* db);
diff --git a/http2/hpack/varint/hpack_varint_decoder_test.cc b/http2/hpack/varint/hpack_varint_decoder_test.cc index 761087b..e36ad07 100644 --- a/http2/hpack/varint/hpack_varint_decoder_test.cc +++ b/http2/hpack/varint/hpack_varint_decoder_test.cc
@@ -157,114 +157,133 @@ {"00", 5, 0}, {"00", 6, 0}, {"00", 7, 0}, + {"00", 8, 0}, // Small values that fit in the prefix. {"06", 3, 6}, {"0d", 4, 13}, {"10", 5, 16}, {"29", 6, 41}, {"56", 7, 86}, + {"bf", 8, 191}, // Values of 2^n-1, which have an all-zero extension byte. {"0700", 3, 7}, {"0f00", 4, 15}, {"1f00", 5, 31}, {"3f00", 6, 63}, {"7f00", 7, 127}, + {"ff00", 8, 255}, // Values of 2^n-1, plus one extra byte of padding. {"078000", 3, 7}, {"0f8000", 4, 15}, {"1f8000", 5, 31}, {"3f8000", 6, 63}, {"7f8000", 7, 127}, + {"ff8000", 8, 255}, // Values requiring one extension byte. {"0760", 3, 103}, {"0f2a", 4, 57}, {"1f7f", 5, 158}, {"3f02", 6, 65}, {"7f49", 7, 200}, + {"ff6f", 8, 366}, // Values requiring one extension byte, plus one byte of padding. {"07e000", 3, 103}, {"0faa00", 4, 57}, {"1fff00", 5, 158}, {"3f8200", 6, 65}, {"7fc900", 7, 200}, + {"ffef00", 8, 366}, // Values requiring one extension byte, plus two bytes of padding. {"07e08000", 3, 103}, {"0faa8000", 4, 57}, {"1fff8000", 5, 158}, {"3f828000", 6, 65}, {"7fc98000", 7, 200}, + {"ffef8000", 8, 366}, // Values requiring one extension byte, plus the maximum amount of padding. {"07e0808080808080808000", 3, 103}, {"0faa808080808080808000", 4, 57}, {"1fff808080808080808000", 5, 158}, {"3f82808080808080808000", 6, 65}, {"7fc9808080808080808000", 7, 200}, + {"ffef808080808080808000", 8, 366}, // Values requiring two extension bytes. {"07b260", 3, 12345}, {"0f8a2a", 4, 5401}, {"1fa87f", 5, 16327}, {"3fd002", 6, 399}, {"7fff49", 7, 9598}, + {"ffe32f", 8, 6370}, // Values requiring two extension bytes, plus one byte of padding. {"07b2e000", 3, 12345}, {"0f8aaa00", 4, 5401}, {"1fa8ff00", 5, 16327}, {"3fd08200", 6, 399}, {"7fffc900", 7, 9598}, + {"ffe3af00", 8, 6370}, // Values requiring two extension bytes, plus the maximum amount of padding. {"07b2e080808080808000", 3, 12345}, {"0f8aaa80808080808000", 4, 5401}, {"1fa8ff80808080808000", 5, 16327}, {"3fd08280808080808000", 6, 399}, {"7fffc980808080808000", 7, 9598}, + {"ffe3af80808080808000", 8, 6370}, // Values requiring three extension bytes. {"078ab260", 3, 1579281}, {"0fc18a2a", 4, 689488}, {"1fada87f", 5, 2085964}, {"3fa0d002", 6, 43103}, {"7ffeff49", 7, 1212541}, + {"ff93de23", 8, 585746}, // Values requiring three extension bytes, plus one byte of padding. {"078ab2e000", 3, 1579281}, {"0fc18aaa00", 4, 689488}, {"1fada8ff00", 5, 2085964}, {"3fa0d08200", 6, 43103}, {"7ffeffc900", 7, 1212541}, + {"ff93dea300", 8, 585746}, // Values requiring four extension bytes. {"079f8ab260", 3, 202147110}, {"0fa2c18a2a", 4, 88252593}, {"1fd0ada87f", 5, 266999535}, {"3ff9a0d002", 6, 5509304}, {"7f9efeff49", 7, 155189149}, + {"ffaa82f404", 8, 10289705}, // Values requiring four extension bytes, plus one byte of padding. {"079f8ab2e000", 3, 202147110}, {"0fa2c18aaa00", 4, 88252593}, {"1fd0ada8ff00", 5, 266999535}, {"3ff9a0d08200", 6, 5509304}, {"7f9efeffc900", 7, 155189149}, + {"ffaa82f48400", 8, 10289705}, // Values requiring six extension bytes. {"0783aa9f8ab260", 3, 3311978140938}, {"0ff0b0a2c18a2a", 4, 1445930244223}, {"1fda84d0ada87f", 5, 4374519874169}, {"3fb5fbf9a0d002", 6, 90263420404}, {"7fcff19efeff49", 7, 2542616951118}, + {"ff9fa486bbc327", 8, 1358138807070}, // Values requiring eight extension bytes. {"07f19883aa9f8ab260", 3, 54263449861016696}, {"0f84fdf0b0a2c18a2a", 4, 23690121121119891}, {"1fa0dfda84d0ada87f", 5, 71672133617889215}, {"3f9ff0b5fbf9a0d002", 6, 1478875878881374}, {"7ffbc1cff19efeff49", 7, 41658236125045114}, + {"ff91b6fb85af99c342", 8, 37450237664484368}, // Values requiring ten extension bytes. {"0794f1f19883aa9f8ab201", 3, 12832019021693745307u}, {"0fa08f84fdf0b0a2c18a01", 4, 9980690937382242223u}, {"1fbfdda0dfda84d0ada801", 5, 12131360551794650846u}, {"3f9dc79ff0b5fbf9a0d001", 6, 15006530362736632796u}, {"7f8790fbc1cff19efeff01", 7, 18445754019193211014u}, + {"fffba8c5b8d3fe9f8c8401", 8, 9518498503615141242u}, // Maximum value: 2^64-1. {"07f8ffffffffffffffff01", 3, 18446744073709551615u}, {"0ff0ffffffffffffffff01", 4, 18446744073709551615u}, {"1fe0ffffffffffffffff01", 5, 18446744073709551615u}, {"3fc0ffffffffffffffff01", 6, 18446744073709551615u}, {"7f80ffffffffffffffff01", 7, 18446744073709551615u}, + {"ff80feffffffffffffff01", 8, 18446744073709551615u}, // Examples from RFC7541 C.1. {"0a", 5, 10}, {"1f9a0a", 5, 1337}, @@ -398,25 +417,28 @@ {"1f80808080808080808080", 5}, {"3f80808080808080808080", 6}, {"7f80808080808080808080", 7}, + {"ff80808080808080808080", 8}, // Too many extension bytes, all 1s. {"07ffffffffffffffffffff", 3}, {"0fffffffffffffffffffff", 4}, {"1fffffffffffffffffffff", 5}, {"3fffffffffffffffffffff", 6}, {"7fffffffffffffffffffff", 7}, + {"ffffffffffffffffffffff", 8}, // Value of 2^64, one higher than maximum of 2^64-1. {"07f9ffffffffffffffff01", 3}, {"0ff1ffffffffffffffff01", 4}, {"1fe1ffffffffffffffff01", 5}, {"3fc1ffffffffffffffff01", 6}, {"7f81ffffffffffffffff01", 7}, + {"ff81feffffffffffffff01", 8}, // Maximum value: 2^64-1, with one byte of padding. {"07f8ffffffffffffffff8100", 3}, {"0ff0ffffffffffffffff8100", 4}, {"1fe0ffffffffffffffff8100", 5}, {"3fc0ffffffffffffffff8100", 6}, {"7f80ffffffffffffffff8100", 7}, -}; + {"ff80feffffffffffffff8100", 8}}; // Test data used when decode_64_bits() == false. // In this mode, HpackVarintDecoder allows at most five extension bytes,
diff --git a/http2/hpack/varint/hpack_varint_encoder.cc b/http2/hpack/varint/hpack_varint_encoder.cc index 5872a0e..d3685d9 100644 --- a/http2/hpack/varint/hpack_varint_encoder.cc +++ b/http2/hpack/varint/hpack_varint_encoder.cc
@@ -17,7 +17,7 @@ DCHECK(!encoding_in_progress_); DCHECK_EQ(0u, varint_); DCHECK_LE(1u, prefix_length); - DCHECK_LE(prefix_length, 7u); + DCHECK_LE(prefix_length, 8u); // prefix_mask defines the sequence of low-order bits of the first byte // that encode the prefix of the value. It is also the marker in those bits
diff --git a/http2/hpack/varint/hpack_varint_encoder_test.cc b/http2/hpack/varint/hpack_varint_encoder_test.cc index d230af3..a6043a0 100644 --- a/http2/hpack/varint/hpack_varint_encoder_test.cc +++ b/http2/hpack/varint/hpack_varint_encoder_test.cc
@@ -147,10 +147,10 @@ uint64_t value; uint8_t expected_encoding_first_byte; } kLastByteIsZeroTestData[] = { - {0b10110010, 1, 1, 0b10110011}, {0b10101100, 2, 3, 0b10101111}, - {0b10101000, 3, 7, 0b10101111}, {0b10110000, 4, 15, 0b10111111}, - {0b10100000, 5, 31, 0b10111111}, {0b11000000, 6, 63, 0b11111111}, - {0b10000000, 7, 127, 0b11111111}}; + {0b10110010, 1, 1, 0b10110011}, {0b10101100, 2, 3, 0b10101111}, + {0b10101000, 3, 7, 0b10101111}, {0b10110000, 4, 15, 0b10111111}, + {0b10100000, 5, 31, 0b10111111}, {0b11000000, 6, 63, 0b11111111}, + {0b10000000, 7, 127, 0b11111111}, {0b00000000, 8, 255, 0b11111111}}; // Make sure that the encoder outputs the last byte even when it is zero. This // happens exactly when encoding the value 2^prefix_length - 1.
diff --git a/http2/hpack/varint/hpack_varint_round_trip_test.cc b/http2/hpack/varint/hpack_varint_round_trip_test.cc index e67b8df..45eaef2 100644 --- a/http2/hpack/varint/hpack_varint_round_trip_test.cc +++ b/http2/hpack/varint/hpack_varint_round_trip_test.cc
@@ -104,7 +104,7 @@ void EncodeNoRandom(uint64_t value, uint8_t prefix_length) { DCHECK_LE(3, prefix_length); - DCHECK_LE(prefix_length, 7); + DCHECK_LE(prefix_length, 8); prefix_length_ = prefix_length; HpackBlockBuilder bb; @@ -275,7 +275,7 @@ // To help me and future debuggers of varint encodings, this LOGs out the // transition points where a new extension byte is added. TEST_P(HpackVarintRoundTripTest, Encode) { - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t a = HiValueOfExtensionBytes(0, prefix_length); const uint64_t b = HiValueOfExtensionBytes(1, prefix_length); const uint64_t c = HiValueOfExtensionBytes(2, prefix_length); @@ -340,7 +340,7 @@ // Test all the values that fit into the prefix (one less than the mask). TEST_P(HpackVarintRoundTripTest, ValidatePrefixOnly) { - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint8_t prefix_mask = (1 << prefix_length) - 1; EncodeAndDecodeValuesInRange(0, prefix_mask, prefix_length, 1); } @@ -348,7 +348,7 @@ // Test all values that require exactly 1 extension byte. TEST_P(HpackVarintRoundTripTest, ValidateOneExtensionByte) { - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(0, prefix_length) + 1; EncodeAndDecodeValuesInRange(start, 128, prefix_length, 2); } @@ -356,7 +356,7 @@ // Test *some* values that require exactly 2 extension bytes. TEST_P(HpackVarintRoundTripTest, ValidateTwoExtensionBytes) { - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(1, prefix_length) + 1; const uint64_t range = 127 << 7; @@ -366,7 +366,7 @@ // Test *some* values that require 3 extension bytes. TEST_P(HpackVarintRoundTripTest, ValidateThreeExtensionBytes) { - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(2, prefix_length) + 1; const uint64_t range = 127 << 14; @@ -376,7 +376,7 @@ // Test *some* values that require 4 extension bytes. TEST_P(HpackVarintRoundTripTest, ValidateFourExtensionBytes) { - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(3, prefix_length) + 1; const uint64_t range = 127 << 21; @@ -390,7 +390,7 @@ return; } - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(4, prefix_length) + 1; const uint64_t range = 127llu << 28; @@ -404,7 +404,7 @@ return; } - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(5, prefix_length) + 1; const uint64_t range = 127llu << 35; @@ -418,7 +418,7 @@ return; } - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(6, prefix_length) + 1; const uint64_t range = 127llu << 42; @@ -432,7 +432,7 @@ return; } - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(7, prefix_length) + 1; const uint64_t range = 127llu << 49; @@ -446,7 +446,7 @@ return; } - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(8, prefix_length) + 1; const uint64_t range = 127llu << 56; @@ -460,7 +460,7 @@ return; } - for (int prefix_length = 3; prefix_length <= 7; ++prefix_length) { + for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) { const uint64_t start = HiValueOfExtensionBytes(9, prefix_length) + 1; const uint64_t range = std::numeric_limits<uint64_t>::max() - start; @@ -476,7 +476,7 @@ return; } - for (prefix_length_ = 3; prefix_length_ <= 7; ++prefix_length_) { + for (prefix_length_ = 3; prefix_length_ <= 8; ++prefix_length_) { const uint64_t too_large = (1 << 28) + (1 << prefix_length_) - 1; const uint32_t expected_offset = 6; HpackBlockBuilder bb;