src/huffer.cc

// Copyright 2017 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "puffin/src/include/puffin/huffer.h"

#include <algorithm>
#include <memory>
#include <string>
#include <utility>

#include "puffin/src/bit_writer.h"
#include "puffin/src/huffman_table.h"
#include "puffin/src/include/puffin/common.h"
#include "puffin/src/include/puffin/stream.h"
#include "puffin/src/logging.h"
#include "puffin/src/puff_data.h"
#include "puffin/src/puff_reader.h"

using std::string;

namespace puffin {

Huffer::Huffer() : dyn_ht_(new HuffmanTable()), fix_ht_(new HuffmanTable()) {}

Huffer::~Huffer() {}

bool Huffer::HuffDeflate(PuffReaderInterface* pr,
                         BitWriterInterface* bw) const {
  PuffData pd;
  HuffmanTable* cur_ht = nullptr;
  // If no bytes left for PuffReader to read, bail out.
  while (pr->BytesLeft() != 0) {
    TEST_AND_RETURN_FALSE(pr->GetNext(&pd));

    // The first data should be a metadata.
    TEST_AND_RETURN_FALSE(pd.type == PuffData::Type::kBlockMetadata);
    auto header = pd.block_metadata[0];
    auto final_bit = (header & 0x80) >> 7;
    auto type = (header & 0x60) >> 5;
    auto skipped_bits = header & 0x1F;
    DVLOG(2) << "Write block type: "
             << BlockTypeToString(static_cast<BlockType>(type));

    TEST_AND_RETURN_FALSE(bw->WriteBits(1, final_bit));
    TEST_AND_RETURN_FALSE(bw->WriteBits(2, type));
    switch (static_cast<BlockType>(type)) {
      case BlockType::kUncompressed:
        bw->WriteBoundaryBits(skipped_bits);
        TEST_AND_RETURN_FALSE(pr->GetNext(&pd));
        TEST_AND_RETURN_FALSE(pd.type != PuffData::Type::kLiteral);

        if (pd.type == PuffData::Type::kLiterals) {
          TEST_AND_RETURN_FALSE(bw->WriteBits(16, pd.length));
          TEST_AND_RETURN_FALSE(bw->WriteBits(16, ~pd.length));
          TEST_AND_RETURN_FALSE(bw->WriteBytes(pd.length, pd.read_fn));
          // Reading end of block, but don't write anything.
          TEST_AND_RETURN_FALSE(pr->GetNext(&pd));
          TEST_AND_RETURN_FALSE(pd.type == PuffData::Type::kEndOfBlock);
        } else if (pd.type == PuffData::Type::kEndOfBlock) {
          TEST_AND_RETURN_FALSE(bw->WriteBits(16, 0));
          TEST_AND_RETURN_FALSE(bw->WriteBits(16, ~0));
        } else {
          LOG(ERROR) << "Uncompressed block did not end properly!";
          return false;
        }
        // We have to read a new block.
        continue;

      case BlockType::kFixed:
        fix_ht_->BuildFixedHuffmanTable();
        cur_ht = fix_ht_.get();
        break;

      case BlockType::kDynamic:
        cur_ht = dyn_ht_.get();
        TEST_AND_RETURN_FALSE(dyn_ht_->BuildDynamicHuffmanTable(
            &pd.block_metadata[1], pd.length - 1, bw));
        break;

      default:
        LOG(ERROR) << "Invalid block compression type: "
                   << static_cast<int>(type);
        return false;
    }

    // We read literal or distrance/lengths until and end of block or end of
    // stream is reached.
    bool block_ended = false;
    while (!block_ended) {
      TEST_AND_RETURN_FALSE(pr->GetNext(&pd));
      switch (pd.type) {
        case PuffData::Type::kLiteral:
        case PuffData::Type::kLiterals: {
          auto write_literal = [&cur_ht, &bw](uint8_t literal) {
            uint16_t literal_huffman;
            size_t nbits;
            TEST_AND_RETURN_FALSE(
                cur_ht->LitLenHuffman(literal, &literal_huffman, &nbits));
            TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, literal_huffman));
            return true;
          };

          if (pd.type == PuffData::Type::kLiteral) {
            TEST_AND_RETURN_FALSE(write_literal(pd.byte));
          } else {
            auto len = pd.length;
            while (len-- > 0) {
              uint8_t literal;
              pd.read_fn(&literal, 1);
              TEST_AND_RETURN_FALSE(write_literal(literal));
            }
          }
          break;
        }
        case PuffData::Type::kLenDist: {
          auto len = pd.length;
          auto dist = pd.distance;
          TEST_AND_RETURN_FALSE(len >= 3 && len <= 258);

          // Using a binary search here instead of the linear search may be (but
          // not necessarily) faster. Needs experiment to validate.
          size_t index = 0;
          while (len > kLengthBases[index]) {
            index++;
          }
          if (len < kLengthBases[index]) {
            index--;
          }
          auto extra_bits_len = kLengthExtraBits[index];
          uint16_t length_huffman;
          size_t nbits;
          TEST_AND_RETURN_FALSE(
              cur_ht->LitLenHuffman(index + 257, &length_huffman, &nbits));

          TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, length_huffman));

          if (extra_bits_len > 0) {
            TEST_AND_RETURN_FALSE(
                bw->WriteBits(extra_bits_len, len - kLengthBases[index]));
          }

          // Same as above (binary search).
          index = 0;
          while (dist > kDistanceBases[index]) {
            index++;
          }
          if (dist < kDistanceBases[index]) {
            index--;
          }
          extra_bits_len = kDistanceExtraBits[index];
          uint16_t distance_huffman;
          TEST_AND_RETURN_FALSE(
              cur_ht->DistanceHuffman(index, &distance_huffman, &nbits));

          TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, distance_huffman));
          if (extra_bits_len > 0) {
            TEST_AND_RETURN_FALSE(
                bw->WriteBits(extra_bits_len, dist - kDistanceBases[index]));
          }
          break;
        }

        case PuffData::Type::kEndOfBlock: {
          uint16_t eos_huffman;
          size_t nbits;
          TEST_AND_RETURN_FALSE(
              cur_ht->LitLenHuffman(256, &eos_huffman, &nbits));
          TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, eos_huffman));
          block_ended = true;
          break;
        }
        case PuffData::Type::kBlockMetadata:
          LOG(ERROR) << "Not expecing a metadata!";
          return false;

        default:
          LOG(ERROR) << "Invalid block data type!";
          return false;
      }
    }
  }

  TEST_AND_RETURN_FALSE(bw->Flush());
  return true;
}

}  // namespace puffin