Remove one duplicated jbig2 huffman code reading loop The motivation is that I'd like to optimize the huffman symbol reading loop that's currently repeated in 1. CJBig2_HuffmanDecoder::DecodeAValue() 2. CJBig2_Context::DecodeSymbolIDHuffmanTable() (for reading `runcode`) 3. CJBig2_TRDProc::DecodeHuffman() (for reading `IDI`) I mostly care about optimizing the last one, but it seems nicer to dedupe them first. This implements the 2nd in terms of the 1st; the 3rd is for a future CL. * ParseFromStandardTable() becomes ParseFromTable() and receives a HuffmanTable instead of an index. This simplifies the CJBig2_HuffmanTable(int) constructor a bit, which used to load each built-in table in the ctor, and then again in ParseFromStandardTable(). This requires moving `struct HuffmanTable` to the header. (It's still an internal type, but as it's used by private functions, we have to move it over. If we wanted, we could put it inside the class, in the `private:` section.) * Add a constructor that builds a CJBig2_HuffmanTable from just code lengths. * Call that from CJBig2_Context::DecodeSymbolIDHuffmanTable() While here, add a comment over `lines`, and fix `RANDELEN` -> `RANGELEN` typo. No intended behavior change. (Linked bug vaguely related: I want to bump some limit, but things are currently very slow with high symbol count, even with the current limit.) Bug: 555145149 Change-Id: If29d5d11951a47cf7b32f61d6147054f3fffd684 Reviewed-on: https://pdfium-review.googlesource.com/c/pdfium/+/156810 Commit-Queue: Nico Weber <thakis@chromium.org> Reviewed-by: Nico Weber <thakis@google.com> Reviewed-by: Tom Sepez <tsepez@chromium.org>
diff --git a/core/fxcodec/jbig2/jbig2_context.cpp b/core/fxcodec/jbig2/jbig2_context.cpp index 219946e..a731247 100644 --- a/core/fxcodec/jbig2/jbig2_context.cpp +++ b/core/fxcodec/jbig2/jbig2_context.cpp
@@ -18,6 +18,7 @@ #include "core/fxcodec/jbig2/jbig2_grd_proc.h" #include "core/fxcodec/jbig2/jbig2_grrd_proc.h" #include "core/fxcodec/jbig2/jbig2_htrd_proc.h" +#include "core/fxcodec/jbig2/jbig2_huffman_decoder.h" #include "core/fxcodec/jbig2/jbig2_pdd_proc.h" #include "core/fxcodec/jbig2/jbig2_sdd_proc.h" #include "core/fxcodec/jbig2/jbig2_trd_proc.h" @@ -1212,49 +1213,31 @@ std::vector<JBig2HuffmanCode> CJBig2_Context::DecodeSymbolIDHuffmanTable( uint32_t SBNUMSYMS) { - const size_t kRunCodesSize = 35; - std::array<JBig2HuffmanCode, kRunCodesSize> huffman_codes; - for (size_t i = 0; i < kRunCodesSize; ++i) { - if (stream_->readNBits(4, &huffman_codes[i].codelen) != 0) { + std::array<uint8_t, 35> runcode_lengths; + for (uint8_t& runcode_length : runcode_lengths) { + uint32_t code_length; + if (stream_->readNBits(4, &code_length) != 0) { return std::vector<JBig2HuffmanCode>(); } + runcode_length = code_length; } - if (!HuffmanAssignCode(huffman_codes)) { + + CJBig2_HuffmanTable runcode_table(runcode_lengths); + if (!runcode_table.IsOK()) { return std::vector<JBig2HuffmanCode>(); } + CJBig2_HuffmanDecoder runcode_decoder(stream_.get()); + std::vector<JBig2HuffmanCode> SBSYMCODES(SBNUMSYMS); int32_t run = 0; int32_t i = 0; while (i < static_cast<int>(SBNUMSYMS)) { - size_t j; - FX_SAFE_INT32 nSafeVal = 0; - int32_t nBits = 0; - uint32_t nTemp; - while (true) { - if (stream_->read1Bit(&nTemp) != 0) { - return std::vector<JBig2HuffmanCode>(); - } - - nSafeVal <<= 1; - if (!nSafeVal.IsValid()) { - return std::vector<JBig2HuffmanCode>(); - } - - nSafeVal |= nTemp; - ++nBits; - const int32_t nVal = nSafeVal.ValueOrDie(); - for (j = 0; j < kRunCodesSize; ++j) { - if (nBits == huffman_codes[j].codelen && - nVal == huffman_codes[j].code) { - break; - } - } - if (j < kRunCodesSize) { - break; - } + int32_t runcode; + if (runcode_decoder.DecodeAValue(&runcode_table, &runcode) != 0) { + return std::vector<JBig2HuffmanCode>(); } - int32_t runcode = static_cast<int32_t>(j); + uint32_t nTemp; if (runcode < 32) { SBSYMCODES[i].codelen = runcode; run = 0;
diff --git a/core/fxcodec/jbig2/jbig2_huffman_table.cpp b/core/fxcodec/jbig2/jbig2_huffman_table.cpp index f040a09..2cdf63d 100644 --- a/core/fxcodec/jbig2/jbig2_huffman_table.cpp +++ b/core/fxcodec/jbig2/jbig2_huffman_table.cpp
@@ -15,21 +15,9 @@ #include "core/fxcrt/check.h" #include "core/fxcrt/check_op.h" #include "core/fxcrt/fx_safe_types.h" -#include "core/fxcrt/raw_span.h" namespace { -struct JBig2TableLine { - uint8_t PREFLEN; - uint8_t RANDELEN; - int32_t RANGELOW; -}; - -struct HuffmanTable { - bool HTOOB; - pdfium::raw_span<const JBig2TableLine> lines; -}; - constexpr JBig2TableLine kTableLine1[] = {{1, 4, 0}, {2, 8, 16}, {3, 16, 272}, @@ -133,10 +121,7 @@ } // namespace CJBig2_HuffmanTable::CJBig2_HuffmanTable(size_t idx) { - const HuffmanTable& table = kHuffmanTables[idx]; - HTOOB = table.HTOOB; - NTEMP = static_cast<uint32_t>(table.lines.size()); - ok_ = ParseFromStandardTable(idx); + ok_ = ParseFromTable(kHuffmanTables[idx]); DCHECK(ok_); } @@ -145,17 +130,33 @@ ok_ = ParseFromCodedBuffer(pStream); } +CJBig2_HuffmanTable::CJBig2_HuffmanTable(pdfium::span<uint8_t> prefix_lengths) { + std::vector<JBig2TableLine> lines(prefix_lengths.size() + 2); + for (size_t i = 0; const auto& length : prefix_lengths) { + lines[i].PREFLEN = length; + lines[i].RANGELEN = 0; + lines[i].RANGELOW = static_cast<int>(i); + ++i; + } + // Dummy open-ended intervals: + lines[prefix_lengths.size()] = {0, 0, 0}; + lines[prefix_lengths.size() + 1] = {0, 0, 0}; + + ok_ = ParseFromTable({.HTOOB = false, .lines = lines}); +} + CJBig2_HuffmanTable::~CJBig2_HuffmanTable() = default; -bool CJBig2_HuffmanTable::ParseFromStandardTable(size_t idx) { - pdfium::span<const JBig2TableLine> lines = - kHuffmanTables[idx].lines.first(NTEMP); +bool CJBig2_HuffmanTable::ParseFromTable(const HuffmanTable& table) { + HTOOB = table.HTOOB; + NTEMP = static_cast<uint32_t>(table.lines.size()); + pdfium::span<const JBig2TableLine> lines = table.lines; CODES.resize(lines.size()); RANGELEN.resize(lines.size()); RANGELOW.resize(lines.size()); for (size_t i = 0; const auto& line : lines) { CODES[i].codelen = line.PREFLEN; - RANGELEN[i] = line.RANDELEN; + RANGELEN[i] = line.RANGELEN; RANGELOW[i] = line.RANGELOW; ++i; }
diff --git a/core/fxcodec/jbig2/jbig2_huffman_table.h b/core/fxcodec/jbig2/jbig2_huffman_table.h index 7f5d5a0..9a5723f 100644 --- a/core/fxcodec/jbig2/jbig2_huffman_table.h +++ b/core/fxcodec/jbig2/jbig2_huffman_table.h
@@ -13,13 +13,35 @@ #include <vector> #include "core/fxcodec/jbig2/jbig2_define.h" +#include "core/fxcrt/raw_span.h" class CJBig2_BitStream; +struct JBig2TableLine { + uint8_t PREFLEN; + uint8_t RANGELEN; + int32_t RANGELOW; +}; + +struct HuffmanTable { + bool HTOOB; + + // If HTOOB is set: The last line is for the OOB symbol. + // Its RANGELEN and RANGELOW are ignored. + // The last two lines (before the OOB symbol line, if present) + // are for the -infinity...value range and the value...infinity range. + // If this table has no -infinity...value range, set its PREFLEN to 0. + pdfium::raw_span<const JBig2TableLine> lines; +}; + class CJBig2_HuffmanTable { public: explicit CJBig2_HuffmanTable(size_t idx); explicit CJBig2_HuffmanTable(CJBig2_BitStream* pStream); + + // Creates a huffman table that maps a canonical code with length + // prefix_lengths[i] to i. + explicit CJBig2_HuffmanTable(pdfium::span<uint8_t> prefix_lengths); ~CJBig2_HuffmanTable(); bool IsHTOOB() const { return HTOOB; } @@ -32,7 +54,7 @@ static constexpr size_t kNumHuffmanTables = 16; private: - bool ParseFromStandardTable(size_t table_idx); + bool ParseFromTable(const HuffmanTable& table); bool ParseFromCodedBuffer(CJBig2_BitStream* pStream); void ExtendBuffers(bool increment);