From 1e6cb63d77090ddc6aa19c755d7066f66e9ff87e Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Thu, 28 Nov 2013 16:27:29 +0000 Subject: Delta-encoding of mapping tables. Both PC offsets and dalvik offsets are delta-encoded. Since PC offsets are increasing, the deltas are then compressed as unsigned LEB128. Dalvik offsets are not monotonic, so their deltas are compressed as signed LEB128. This reduces the size of the mapping tables by about 30% on average, 25% from the PC offset and 5% from the dalvik offset delta encoding. Bug: 9437697 Change-Id: I600ab9c22dec178088d4947a811cca3bc8bd4cf4 --- compiler/leb128_encoder_test.cc | 102 ++++++++++++++++++++++++++++++++++++---- 1 file changed, 94 insertions(+), 8 deletions(-) (limited to 'compiler/leb128_encoder_test.cc') diff --git a/compiler/leb128_encoder_test.cc b/compiler/leb128_encoder_test.cc index 4fa80757c5..3162ca5f46 100644 --- a/compiler/leb128_encoder_test.cc +++ b/compiler/leb128_encoder_test.cc @@ -42,11 +42,61 @@ static DecodeUnsignedLeb128TestCase uleb128_tests[] = { {0xFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xF}}, }; -TEST_F(Leb128Test, Singles) { +struct DecodeSignedLeb128TestCase { + int32_t decoded; + uint8_t leb128_data[5]; +}; + +static DecodeSignedLeb128TestCase sleb128_tests[] = { + {0, {0, 0, 0, 0, 0}}, + {1, {1, 0, 0, 0, 0}}, + {0x3F, {0x3F, 0, 0, 0, 0}}, + {0x40, {0xC0, 0 /* sign bit */, 0, 0, 0}}, + {0x41, {0xC1, 0 /* sign bit */, 0, 0, 0}}, + {0x80, {0x80, 1, 0, 0, 0}}, + {0xFF, {0xFF, 1, 0, 0, 0}}, + {0x1FFF, {0xFF, 0x3F, 0, 0, 0}}, + {0x2000, {0x80, 0xC0, 0 /* sign bit */, 0, 0}}, + {0x2001, {0x81, 0xC0, 0 /* sign bit */, 0, 0}}, + {0x2081, {0x81, 0xC1, 0 /* sign bit */, 0, 0}}, + {0x4000, {0x80, 0x80, 1, 0, 0}}, + {0x0FFFFF, {0xFF, 0xFF, 0x3F, 0, 0}}, + {0x100000, {0x80, 0x80, 0xC0, 0 /* sign bit */, 0}}, + {0x100001, {0x81, 0x80, 0xC0, 0 /* sign bit */, 0}}, + {0x100081, {0x81, 0x81, 0xC0, 0 /* sign bit */, 0}}, + {0x104081, {0x81, 0x81, 0xC1, 0 /* sign bit */, 0}}, + {0x200000, {0x80, 0x80, 0x80, 1, 0}}, + {0x7FFFFFF, {0xFF, 0xFF, 0xFF, 0x3F, 0}}, + {0x8000000, {0x80, 0x80, 0x80, 0xC0, 0 /* sign bit */}}, + {0x8000001, {0x81, 0x80, 0x80, 0xC0, 0 /* sign bit */}}, + {0x8000081, {0x81, 0x81, 0x80, 0xC0, 0 /* sign bit */}}, + {0x8004081, {0x81, 0x81, 0x81, 0xC0, 0 /* sign bit */}}, + {0x8204081, {0x81, 0x81, 0x81, 0xC1, 0 /* sign bit */}}, + {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0 /* sign bit */}}, + {0x10000000, {0x80, 0x80, 0x80, 0x80, 1}}, + {0x7FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x7}}, + {-1, {0x7F, 0, 0, 0, 0}}, + {-2, {0x7E, 0, 0, 0, 0}}, + {-0x3F, {0x41, 0, 0, 0, 0}}, + {-0x40, {0x40, 0, 0, 0, 0}}, + {-0x41, {0xBF, 0x7F, 0, 0, 0}}, + {-0x80, {0x80, 0x7F, 0, 0, 0}}, + {-0x81, {0xFF, 0x7E, 0, 0, 0}}, + {-0x00002000, {0x80, 0x40, 0, 0, 0}}, + {-0x00002001, {0xFF, 0xBF, 0x7F, 0, 0}}, + {-0x00100000, {0x80, 0x80, 0x40, 0, 0}}, + {-0x00100001, {0xFF, 0xFF, 0xBF, 0x7F, 0}}, + {-0x08000000, {0x80, 0x80, 0x80, 0x40, 0}}, + {-0x08000001, {0xFF, 0xFF, 0xFF, 0xBF, 0x7F}}, + {-0x20000000, {0x80, 0x80, 0x80, 0x80, 0x7E}}, + {(-1) << 31, {0x80, 0x80, 0x80, 0x80, 0x78}}, +}; + +TEST_F(Leb128Test, UnsignedSingles) { // Test individual encodings. for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { - UnsignedLeb128EncodingVector builder; - builder.PushBack(uleb128_tests[i].decoded); + Leb128EncodingVector builder; + builder.PushBackUnsigned(uleb128_tests[i].decoded); const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0]; const uint8_t* encoded_data_ptr = &builder.GetData()[0]; for (size_t j = 0; j < 5; ++j) { @@ -60,11 +110,11 @@ TEST_F(Leb128Test, Singles) { } } -TEST_F(Leb128Test, Stream) { +TEST_F(Leb128Test, UnsignedStream) { // Encode a number of entries. - UnsignedLeb128EncodingVector builder; + Leb128EncodingVector builder; for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { - builder.PushBack(uleb128_tests[i].decoded); + builder.PushBackUnsigned(uleb128_tests[i].decoded); } const uint8_t* encoded_data_ptr = &builder.GetData()[0]; for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { @@ -78,15 +128,51 @@ TEST_F(Leb128Test, Stream) { } } +TEST_F(Leb128Test, SignedSingles) { + // Test individual encodings. + for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { + Leb128EncodingVector builder; + builder.PushBackSigned(sleb128_tests[i].decoded); + const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0]; + const uint8_t* encoded_data_ptr = &builder.GetData()[0]; + for (size_t j = 0; j < 5; ++j) { + if (j < builder.GetData().size()) { + EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j; + } else { + EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j; + } + } + EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i; + } +} + +TEST_F(Leb128Test, SignedStream) { + // Encode a number of entries. + Leb128EncodingVector builder; + for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { + builder.PushBackSigned(sleb128_tests[i].decoded); + } + const uint8_t* encoded_data_ptr = &builder.GetData()[0]; + for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { + const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0]; + for (size_t j = 0; j < 5; ++j) { + if (data_ptr[j] != 0) { + EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j; + } + } + EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i; + } +} + TEST_F(Leb128Test, Speed) { UniquePtr > enc_hist(new Histogram("Leb128EncodeSpeedTest", 5)); UniquePtr > dec_hist(new Histogram("Leb128DecodeSpeedTest", 5)); - UnsignedLeb128EncodingVector builder; + Leb128EncodingVector builder; // Push back 1024 chunks of 1024 values measuring encoding speed. uint64_t last_time = NanoTime(); for (size_t i = 0; i < 1024; i++) { for (size_t j = 0; j < 1024; j++) { - builder.PushBack((i * 1024) + j); + builder.PushBackUnsigned((i * 1024) + j); } uint64_t cur_time = NanoTime(); enc_hist->AddValue(cur_time - last_time); -- cgit v1.2.3-59-g8ed1b