1// Copyright 2014 PDFium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6
7#include "core/fxcodec/jbig2/JBig2_HuffmanTable.h"
8
9#include <algorithm>
10#include <limits>
11#include <vector>
12
13#include "core/fxcodec/jbig2/JBig2_BitStream.h"
14#include "core/fxcodec/jbig2/JBig2_Define.h"
15#include "core/fxcodec/jbig2/JBig2_HuffmanTable_Standard.h"
16#include "core/fxcrt/fx_memory.h"
17#include "third_party/base/numerics/safe_math.h"
18
19CJBig2_HuffmanTable::CJBig2_HuffmanTable(const JBig2TableLine* pTable,
20                                         uint32_t nLines,
21                                         bool bHTOOB)
22    : m_bOK(true), HTOOB(bHTOOB), NTEMP(nLines) {
23  ParseFromStandardTable(pTable);
24}
25
26CJBig2_HuffmanTable::CJBig2_HuffmanTable(CJBig2_BitStream* pStream)
27    : HTOOB(false), NTEMP(0) {
28  m_bOK = ParseFromCodedBuffer(pStream);
29}
30
31CJBig2_HuffmanTable::~CJBig2_HuffmanTable() {}
32
33void CJBig2_HuffmanTable::ParseFromStandardTable(const JBig2TableLine* pTable) {
34  PREFLEN.resize(NTEMP);
35  RANGELEN.resize(NTEMP);
36  RANGELOW.resize(NTEMP);
37  for (uint32_t i = 0; i < NTEMP; ++i) {
38    PREFLEN[i] = pTable[i].PREFLEN;
39    RANGELEN[i] = pTable[i].RANDELEN;
40    RANGELOW[i] = pTable[i].RANGELOW;
41  }
42  InitCodes();
43}
44
45bool CJBig2_HuffmanTable::ParseFromCodedBuffer(CJBig2_BitStream* pStream) {
46  unsigned char cTemp;
47  if (pStream->read1Byte(&cTemp) == -1)
48    return false;
49
50  HTOOB = !!(cTemp & 0x01);
51  unsigned char HTPS = ((cTemp >> 1) & 0x07) + 1;
52  unsigned char HTRS = ((cTemp >> 4) & 0x07) + 1;
53  uint32_t HTLOW;
54  uint32_t HTHIGH;
55  if (pStream->readInteger(&HTLOW) == -1 ||
56      pStream->readInteger(&HTHIGH) == -1 ||
57      HTLOW > static_cast<uint32_t>(std::numeric_limits<int>::max()) ||
58      HTHIGH > static_cast<uint32_t>(std::numeric_limits<int>::max())) {
59    return false;
60  }
61
62  const int low = static_cast<int>(HTLOW);
63  const int high = static_cast<int>(HTHIGH);
64  if (low > high)
65    return false;
66
67  ExtendBuffers(false);
68  pdfium::base::CheckedNumeric<int> cur_low = low;
69  do {
70    if ((pStream->readNBits(HTPS, &PREFLEN[NTEMP]) == -1) ||
71        (pStream->readNBits(HTRS, &RANGELEN[NTEMP]) == -1) ||
72        (static_cast<size_t>(RANGELEN[NTEMP]) >= 8 * sizeof(cur_low))) {
73      return false;
74    }
75    RANGELOW[NTEMP] = cur_low.ValueOrDie();
76
77    if (RANGELEN[NTEMP] >= 32)
78      return false;
79
80    cur_low += (1 << RANGELEN[NTEMP]);
81    if (!cur_low.IsValid())
82      return false;
83    ExtendBuffers(true);
84  } while (cur_low.ValueOrDie() < high);
85
86  if (pStream->readNBits(HTPS, &PREFLEN[NTEMP]) == -1)
87    return false;
88
89  RANGELEN[NTEMP] = 32;
90  RANGELOW[NTEMP] = low - 1;
91  ExtendBuffers(true);
92
93  if (pStream->readNBits(HTPS, &PREFLEN[NTEMP]) == -1)
94    return false;
95
96  RANGELEN[NTEMP] = 32;
97  RANGELOW[NTEMP] = high;
98  ExtendBuffers(true);
99
100  if (HTOOB) {
101    if (pStream->readNBits(HTPS, &PREFLEN[NTEMP]) == -1)
102      return false;
103
104    ++NTEMP;
105  }
106
107  return InitCodes();
108}
109
110bool CJBig2_HuffmanTable::InitCodes() {
111  int lenmax = 0;
112  for (uint32_t i = 0; i < NTEMP; ++i)
113    lenmax = std::max(PREFLEN[i], lenmax);
114
115  CODES.resize(NTEMP);
116  std::vector<int> LENCOUNT(lenmax + 1);
117  std::vector<int> FIRSTCODE(lenmax + 1);
118  for (int len : PREFLEN)
119    ++LENCOUNT[len];
120
121  FIRSTCODE[0] = 0;
122  LENCOUNT[0] = 0;
123  for (int i = 1; i <= lenmax; ++i) {
124    pdfium::base::CheckedNumeric<int> shifted;
125    shifted = FIRSTCODE[i - 1] + LENCOUNT[i - 1];
126    shifted <<= 1;
127    if (!shifted.IsValid())
128      return false;
129
130    FIRSTCODE[i] = shifted.ValueOrDie();
131    int CURCODE = FIRSTCODE[i];
132    for (uint32_t j = 0; j < NTEMP; ++j) {
133      if (PREFLEN[j] == i)
134        CODES[j] = CURCODE++;
135    }
136  }
137
138  return true;
139}
140
141void CJBig2_HuffmanTable::ExtendBuffers(bool increment) {
142  if (increment)
143    ++NTEMP;
144
145  size_t size = PREFLEN.size();
146  if (NTEMP < size)
147    return;
148
149  size += 16;
150  ASSERT(NTEMP < size);
151  PREFLEN.resize(size);
152  RANGELEN.resize(size);
153  RANGELOW.resize(size);
154}
155