diff options
Diffstat (limited to 'src/tile/bitstream/palette.cc')
| -rw-r--r-- | src/tile/bitstream/palette.cc | 319 |
1 files changed, 319 insertions, 0 deletions
diff --git a/src/tile/bitstream/palette.cc b/src/tile/bitstream/palette.cc new file mode 100644 index 0000000..674d210 --- /dev/null +++ b/src/tile/bitstream/palette.cc @@ -0,0 +1,319 @@ +// Copyright 2019 The libgav1 Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <cstring> +#include <iterator> +#include <memory> + +#include "src/obu_parser.h" +#include "src/symbol_decoder_context.h" +#include "src/tile.h" +#include "src/utils/bit_mask_set.h" +#include "src/utils/common.h" +#include "src/utils/constants.h" +#include "src/utils/entropy_decoder.h" +#include "src/utils/memory.h" +#include "src/utils/types.h" + +namespace libgav1 { + +int Tile::GetPaletteCache(const Block& block, PlaneType plane_type, + uint16_t* const cache) { + const int top_size = + (block.top_available[kPlaneY] && Mod64(MultiplyBy4(block.row4x4)) != 0) + ? block.bp_top->palette_mode_info.size[plane_type] + : 0; + const int left_size = block.left_available[kPlaneY] + ? block.bp_left->palette_mode_info.size[plane_type] + : 0; + if (left_size == 0 && top_size == 0) return 0; + // Merge the left and top colors in sorted order and store them in |cache|. + uint16_t dummy[1]; + const uint16_t* top = (top_size > 0) + ? block.bp_top->palette_mode_info.color[plane_type] + : dummy; + const uint16_t* left = + (left_size > 0) ? block.bp_left->palette_mode_info.color[plane_type] + : dummy; + std::merge(top, top + top_size, left, left + left_size, cache); + // Deduplicate the entries in |cache| and return the number of unique + // entries. + return static_cast<int>( + std::distance(cache, std::unique(cache, cache + left_size + top_size))); +} + +void Tile::ReadPaletteColors(const Block& block, Plane plane) { + const PlaneType plane_type = GetPlaneType(plane); + uint16_t cache[2 * kMaxPaletteSize]; + const int n = GetPaletteCache(block, plane_type, cache); + BlockParameters& bp = *block.bp; + const uint8_t palette_size = bp.palette_mode_info.size[plane_type]; + uint16_t* const palette_color = bp.palette_mode_info.color[plane]; + const int8_t bitdepth = sequence_header_.color_config.bitdepth; + int index = 0; + for (int i = 0; i < n && index < palette_size; ++i) { + if (reader_.ReadBit() != 0) { // use_palette_color_cache. + palette_color[index++] = cache[i]; + } + } + const int merge_pivot = index; + if (index < palette_size) { + palette_color[index++] = + static_cast<uint16_t>(reader_.ReadLiteral(bitdepth)); + } + const int max_value = (1 << bitdepth) - 1; + if (index < palette_size) { + int bits = bitdepth - 3 + static_cast<int>(reader_.ReadLiteral(2)); + do { + const int delta = static_cast<int>(reader_.ReadLiteral(bits)) + + (plane_type == kPlaneTypeY ? 1 : 0); + palette_color[index] = + std::min(palette_color[index - 1] + delta, max_value); + if (palette_color[index] + (plane_type == kPlaneTypeY ? 1 : 0) >= + max_value) { + // Once the color exceeds max_value, all others can be set to max_value + // (since they are computed as a delta on top of the current color and + // then clipped). + Memset(&palette_color[index + 1], max_value, palette_size - index - 1); + break; + } + const int range = (1 << bitdepth) - palette_color[index] - + (plane_type == kPlaneTypeY ? 1 : 0); + bits = std::min(bits, CeilLog2(range)); + } while (++index < palette_size); + } + // Palette colors are generated using two ascending arrays. So sorting them is + // simply a matter of merging the two sorted portions of the array. + std::inplace_merge(palette_color, palette_color + merge_pivot, + palette_color + palette_size); + if (plane_type == kPlaneTypeUV) { + uint16_t* const palette_color_v = bp.palette_mode_info.color[kPlaneV]; + if (reader_.ReadBit() != 0) { // delta_encode_palette_colors_v. + const int bits = bitdepth - 4 + static_cast<int>(reader_.ReadLiteral(2)); + palette_color_v[0] = reader_.ReadLiteral(bitdepth); + for (int i = 1; i < palette_size; ++i) { + int delta = static_cast<int>(reader_.ReadLiteral(bits)); + if (delta != 0 && reader_.ReadBit() != 0) delta = -delta; + // This line is equivalent to the following lines in the spec: + // val = palette_colors_v[ idx - 1 ] + palette_delta_v + // if ( val < 0 ) val += maxVal + // if ( val >= maxVal ) val -= maxVal + // palette_colors_v[ idx ] = Clip1( val ) + // + // The difference is that in the code, max_value is (1 << bitdepth) - 1. + // So "& max_value" has the desired effect of computing both the "if" + // conditions and the Clip. + palette_color_v[i] = (palette_color_v[i - 1] + delta) & max_value; + } + } else { + for (int i = 0; i < palette_size; ++i) { + palette_color_v[i] = + static_cast<uint16_t>(reader_.ReadLiteral(bitdepth)); + } + } + } +} + +void Tile::ReadPaletteModeInfo(const Block& block) { + BlockParameters& bp = *block.bp; + if (IsBlockSmallerThan8x8(block.size) || block.size > kBlock64x64 || + !frame_header_.allow_screen_content_tools) { + bp.palette_mode_info.size[kPlaneTypeY] = 0; + bp.palette_mode_info.size[kPlaneTypeUV] = 0; + return; + } + const int block_size_context = + k4x4WidthLog2[block.size] + k4x4HeightLog2[block.size] - 2; + if (bp.y_mode == kPredictionModeDc) { + const int context = + static_cast<int>(block.top_available[kPlaneY] && + block.bp_top->palette_mode_info.size[kPlaneTypeY] > + 0) + + static_cast<int>(block.left_available[kPlaneY] && + block.bp_left->palette_mode_info.size[kPlaneTypeY] > + 0); + const bool has_palette_y = reader_.ReadSymbol( + symbol_decoder_context_.has_palette_y_cdf[block_size_context][context]); + if (has_palette_y) { + bp.palette_mode_info.size[kPlaneTypeY] = + kMinPaletteSize + + reader_.ReadSymbol<kPaletteSizeSymbolCount>( + symbol_decoder_context_.palette_y_size_cdf[block_size_context]); + ReadPaletteColors(block, kPlaneY); + } + } + if (bp.uv_mode == kPredictionModeDc && block.HasChroma()) { + const int context = + static_cast<int>(bp.palette_mode_info.size[kPlaneTypeY] > 0); + const bool has_palette_uv = + reader_.ReadSymbol(symbol_decoder_context_.has_palette_uv_cdf[context]); + if (has_palette_uv) { + bp.palette_mode_info.size[kPlaneTypeUV] = + kMinPaletteSize + + reader_.ReadSymbol<kPaletteSizeSymbolCount>( + symbol_decoder_context_.palette_uv_size_cdf[block_size_context]); + ReadPaletteColors(block, kPlaneU); + } + } +} + +void Tile::PopulatePaletteColorContexts( + const Block& block, PlaneType plane_type, int i, int start, int end, + uint8_t color_order[kMaxPaletteSquare][kMaxPaletteSize], + uint8_t color_context[kMaxPaletteSquare]) { + const PredictionParameters& prediction_parameters = + *block.bp->prediction_parameters; + for (int column = start, counter = 0; column >= end; --column, ++counter) { + const int row = i - column; + assert(row > 0 || column > 0); + const uint8_t top = + (row > 0) + ? prediction_parameters.color_index_map[plane_type][row - 1][column] + : 0; + const uint8_t left = + (column > 0) + ? prediction_parameters.color_index_map[plane_type][row][column - 1] + : 0; + uint8_t index_mask; + static_assert(kMaxPaletteSize <= 8, ""); + int index; + if (column <= 0) { + color_context[counter] = 0; + color_order[counter][0] = top; + index_mask = 1 << top; + index = 1; + } else if (row <= 0) { + color_context[counter] = 0; + color_order[counter][0] = left; + index_mask = 1 << left; + index = 1; + } else { + const uint8_t top_left = + prediction_parameters + .color_index_map[plane_type][row - 1][column - 1]; + index_mask = (1 << top) | (1 << left) | (1 << top_left); + if (top == left && top == top_left) { + color_context[counter] = 4; + color_order[counter][0] = top; + index = 1; + } else if (top == left) { + color_context[counter] = 3; + color_order[counter][0] = top; + color_order[counter][1] = top_left; + index = 2; + } else if (top == top_left) { + color_context[counter] = 2; + color_order[counter][0] = top_left; + color_order[counter][1] = left; + index = 2; + } else if (left == top_left) { + color_context[counter] = 2; + color_order[counter][0] = top_left; + color_order[counter][1] = top; + index = 2; + } else { + color_context[counter] = 1; + color_order[counter][0] = std::min(top, left); + color_order[counter][1] = std::max(top, left); + color_order[counter][2] = top_left; + index = 3; + } + } + // Even though only the first |palette_size| entries of this array are ever + // used, it is faster to populate all 8 because of the vectorization of the + // constant sized loop. + for (uint8_t j = 0; j < kMaxPaletteSize; ++j) { + if (BitMaskSet::MaskContainsValue(index_mask, j)) continue; + color_order[counter][index++] = j; + } + } +} + +bool Tile::ReadPaletteTokens(const Block& block) { + const PaletteModeInfo& palette_mode_info = block.bp->palette_mode_info; + PredictionParameters& prediction_parameters = + *block.bp->prediction_parameters; + for (int plane_type = kPlaneTypeY; + plane_type < (block.HasChroma() ? kNumPlaneTypes : kPlaneTypeUV); + ++plane_type) { + const int palette_size = palette_mode_info.size[plane_type]; + if (palette_size == 0) continue; + int block_height = block.height; + int block_width = block.width; + int screen_height = std::min( + block_height, MultiplyBy4(frame_header_.rows4x4 - block.row4x4)); + int screen_width = std::min( + block_width, MultiplyBy4(frame_header_.columns4x4 - block.column4x4)); + if (plane_type == kPlaneTypeUV) { + block_height >>= sequence_header_.color_config.subsampling_y; + block_width >>= sequence_header_.color_config.subsampling_x; + screen_height >>= sequence_header_.color_config.subsampling_y; + screen_width >>= sequence_header_.color_config.subsampling_x; + if (block_height < 4) { + block_height += 2; + screen_height += 2; + } + if (block_width < 4) { + block_width += 2; + screen_width += 2; + } + } + if (!prediction_parameters.color_index_map[plane_type].Reset( + block_height, block_width, /*zero_initialize=*/false)) { + return false; + } + int first_value = 0; + reader_.DecodeUniform(palette_size, &first_value); + prediction_parameters.color_index_map[plane_type][0][0] = first_value; + for (int i = 1; i < screen_height + screen_width - 1; ++i) { + const int start = std::min(i, screen_width - 1); + const int end = std::max(0, i - screen_height + 1); + uint8_t color_order[kMaxPaletteSquare][kMaxPaletteSize]; + uint8_t color_context[kMaxPaletteSquare]; + PopulatePaletteColorContexts(block, static_cast<PlaneType>(plane_type), i, + start, end, color_order, color_context); + for (int j = start, counter = 0; j >= end; --j, ++counter) { + uint16_t* const cdf = + symbol_decoder_context_ + .palette_color_index_cdf[plane_type] + [palette_size - kMinPaletteSize] + [color_context[counter]]; + const int color_order_index = reader_.ReadSymbol(cdf, palette_size); + prediction_parameters.color_index_map[plane_type][i - j][j] = + color_order[counter][color_order_index]; + } + } + if (screen_width < block_width) { + for (int i = 0; i < screen_height; ++i) { + memset( + &prediction_parameters.color_index_map[plane_type][i][screen_width], + prediction_parameters + .color_index_map[plane_type][i][screen_width - 1], + block_width - screen_width); + } + } + for (int i = screen_height; i < block_height; ++i) { + memcpy( + prediction_parameters.color_index_map[plane_type][i], + prediction_parameters.color_index_map[plane_type][screen_height - 1], + block_width); + } + } + return true; +} + +} // namespace libgav1 |