CodingStructure.cpp

/* The copyright in this software is being made available under the BSD
* License, included below. This software may be subject to other third party
* and contributor rights, including patent rights, and no such rights are
* granted under this license.
*
* Copyright (c) 2010-2019, ITU/ISO/IEC
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
*  * Redistributions of source code must retain the above copyright notice,
*    this list of conditions and the following disclaimer.
*  * Redistributions in binary form must reproduce the above copyright notice,
*    this list of conditions and the following disclaimer in the documentation
*    and/or other materials provided with the distribution.
*  * Neither the name of the ITU/ISO/IEC nor the names of its contributors may
*    be used to endorse or promote products derived from this software without
*    specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
* THE POSSIBILITY OF SUCH DAMAGE.
*/

/** \file     CodingStructure.h
 *  \brief    A class managing the coding information for a specific image part
 */

#include "CodingStructure.h"

#include "Unit.h"
#include "Slice.h"
#include "Picture.h"
#include "UnitTools.h"
#include "UnitPartitioner.h"


XUCache g_globalUnitCache = XUCache();

const UnitScale UnitScaleArray[NUM_CHROMA_FORMAT][MAX_NUM_COMPONENT] =
{
  { {2,2}, {0,0}, {0,0} },  // 4:0:0
  { {2,2}, {1,1}, {1,1} },  // 4:2:0
  { {2,2}, {1,2}, {1,2} },  // 4:2:2
  { {2,2}, {2,2}, {2,2} }   // 4:4:4
};

// ---------------------------------------------------------------------------
// coding structure method definitions
// ---------------------------------------------------------------------------

CodingStructure::CodingStructure(CUCache& cuCache, PUCache& puCache, TUCache& tuCache)
  : area      ()
  , picture   ( nullptr )
  , parent    ( nullptr )
  , bestCS    ( nullptr )
  , m_isTuEnc ( false )
  , m_cuCache ( cuCache )
  , m_puCache ( puCache )
  , m_tuCache ( tuCache )
#if JVET_O0070_PROF
  , bestParent ( nullptr )
#endif
#if JVET_O1170_CHECK_BV_AT_DECODER
  , resetIBCBuffer (false)
#endif
{
  for( uint32_t i = 0; i < MAX_NUM_COMPONENT; i++ )
  {
    m_coeffs[ i ] = nullptr;
    m_pcmbuf[ i ] = nullptr;
#if JVET_O0119_BASE_PALETTE_444
    m_runType[i]   = nullptr;
    m_runLength[i] = nullptr;
#endif

    m_offsets[ i ] = 0;
  }

  for( uint32_t i = 0; i < MAX_NUM_CHANNEL_TYPE; i++ )
  {
    m_cuIdx   [ i ] = nullptr;
    m_puIdx   [ i ] = nullptr;
    m_tuIdx   [ i ] = nullptr;
    m_isDecomp[ i ] = nullptr;
  }

  m_motionBuf     = nullptr;
  features.resize( NUM_ENC_FEATURES );
#if JVET_O0050_LOCAL_DUAL_TREE
  treeType = TREE_D;
  modeType = MODE_TYPE_ALL;
#endif
}

void CodingStructure::destroy()
{
  picture   = nullptr;
  parent    = nullptr;

  m_pred.destroy();
  m_resi.destroy();
  m_reco.destroy();
  m_orgr.destroy();

  destroyCoeffs();

  for( uint32_t i = 0; i < MAX_NUM_CHANNEL_TYPE; i++ )
  {
    delete[] m_isDecomp[ i ];
    m_isDecomp[ i ] = nullptr;

    delete[] m_cuIdx[ i ];
    m_cuIdx[ i ] = nullptr;

    delete[] m_puIdx[ i ];
    m_puIdx[ i ] = nullptr;

    delete[] m_tuIdx[ i ];
    m_tuIdx[ i ] = nullptr;
  }

  delete[] m_motionBuf;
  m_motionBuf = nullptr;


  m_tuCache.cache( tus );
  m_puCache.cache( pus );
  m_cuCache.cache( cus );
}

void CodingStructure::releaseIntermediateData()
{
  clearTUs();
  clearPUs();
  clearCUs();
}

bool CodingStructure::isDecomp( const Position &pos, const ChannelType effChType )
{
  if( area.blocks[effChType].contains( pos ) )
  {
    return m_isDecomp[effChType][rsAddr( pos, area.blocks[effChType], area.blocks[effChType].width, unitScale[effChType] )];
  }
  else if( parent )
  {
    return parent->isDecomp( pos, effChType );
  }
  else
  {
    return false;
  }
}

bool CodingStructure::isDecomp( const Position &pos, const ChannelType effChType ) const
{
  if( area.blocks[effChType].contains( pos ) )
  {
    return m_isDecomp[effChType][rsAddr( pos, area.blocks[effChType], area.blocks[effChType].width, unitScale[effChType] )];
  }
  else if( parent )
  {
    return parent->isDecomp( pos, effChType );
  }
  else
  {
    return false;
  }
}

void CodingStructure::setDecomp(const CompArea &_area, const bool _isCoded /*= true*/)
{
  const UnitScale& scale = unitScale[_area.compID];

  AreaBuf<bool> isCodedBlk( m_isDecomp[toChannelType( _area.compID )] + rsAddr( _area, area.blocks[_area.compID].pos(), area.blocks[_area.compID].width, scale ),
                            area.blocks[_area.compID].width >> scale.posx,
                            _area.width                     >> scale.posx,
                            _area.height                    >> scale.posy);
  isCodedBlk.fill( _isCoded );
}

void CodingStructure::setDecomp(const UnitArea &_area, const bool _isCoded /*= true*/)
{
  for( uint32_t i = 0; i < _area.blocks.size(); i++ )
  {
    if( _area.blocks[i].valid() ) setDecomp( _area.blocks[i], _isCoded );
  }
}

#if JVET_O0050_LOCAL_DUAL_TREE
const int CodingStructure::signalModeCons( const PartSplit split, Partitioner &partitioner, const ModeType modeTypeParent ) const
{
  if( CS::isDualITree( *this ) || modeTypeParent != MODE_TYPE_ALL || partitioner.currArea().chromaFormat == CHROMA_444 )
    return LDT_MODE_TYPE_INHERIT;

  int width = partitioner.currArea().lwidth();
  int height = partitioner.currArea().lheight();

  if( width * height == 64 )
  {
    if( split == CU_QUAD_SPLIT || split == CU_TRIH_SPLIT || split == CU_TRIV_SPLIT ) // qt or tt
      return LDT_MODE_TYPE_INFER; //only intra mode allowed for child nodes (have 4x4)
    else // bt
      return slice->isIntra() ? LDT_MODE_TYPE_INFER : LDT_MODE_TYPE_SIGNAL;
  }
  else if( width * height == 128 )
  {
    if( split == CU_TRIH_SPLIT || split == CU_TRIV_SPLIT ) // tt
      return slice->isIntra() ? LDT_MODE_TYPE_INFER : LDT_MODE_TYPE_SIGNAL;
    else // bt
      return LDT_MODE_TYPE_INHERIT;
  }
  else
  {
    return LDT_MODE_TYPE_INHERIT;
  }
}

void CodingStructure::clearCuPuTuIdxMap( const UnitArea &_area, uint32_t numCu, uint32_t numPu, uint32_t numTu, uint32_t* pOffset )
{
  UnitArea clippedArea = clipArea( _area, *picture );
  uint32_t numCh = ::getNumberValidChannels( _area.chromaFormat );
  for( uint32_t i = 0; i < numCh; i++ )
  {
    const CompArea &_selfBlk = area.blocks[i];
    const CompArea     &_blk = clippedArea.blocks[i];

    const UnitScale& scale = unitScale[_blk.compID];
    const Area scaledSelf = scale.scale( _selfBlk );
    const Area scaledBlk = scale.scale( _blk );
    const size_t offset = rsAddr( scaledBlk.pos(), scaledSelf.pos(), scaledSelf.width );
    unsigned *idxPtrCU = m_cuIdx[i] + offset;
    AreaBuf<uint32_t>( idxPtrCU, scaledSelf.width, scaledBlk.size() ).fill( 0 );

    unsigned *idxPtrPU = m_puIdx[i] + offset;
    AreaBuf<uint32_t>( idxPtrPU, scaledSelf.width, scaledBlk.size() ).fill( 0 );

    unsigned *idxPtrTU = m_tuIdx[i] + offset;
    AreaBuf<uint32_t>( idxPtrTU, scaledSelf.width, scaledBlk.size() ).fill( 0 );
  }

  //pop cu/pu/tus
  for( int i = m_numTUs; i > numTu; i-- )
  {
    m_tuCache.cache( tus.back() );
    tus.pop_back();
    m_numTUs--;
  }
  for( int i = m_numPUs; i > numPu; i-- )
  {
    m_puCache.cache( pus.back() );
    pus.pop_back();
    m_numPUs--;
  }
  for( int i = m_numCUs; i > numCu; i-- )
  {
    m_cuCache.cache( cus.back() );
    cus.pop_back();
    m_numCUs--;
  }
  for( int i = 0; i < 3; i++ )
  {
    m_offsets[i] = pOffset[i];
  }
}
#endif


CodingUnit* CodingStructure::getCU( const Position &pos, const ChannelType effChType )
{
  const CompArea &_blk = area.blocks[effChType];

#if JVET_O0050_LOCAL_DUAL_TREE
  if( !_blk.contains( pos ) || (treeType == TREE_C && effChType == CHANNEL_TYPE_LUMA) )
#else
  if( !_blk.contains( pos ) )
#endif
  {
    if (parent)
    {
#if JVET_O0050_LOCAL_DUAL_TREE
      if (treeType == TREE_C && effChType == CHANNEL_TYPE_LUMA)
      {
        CHECK(parent->treeType != TREE_D, "wrong parent treeType ");
      }
#endif
      return parent->getCU(pos, effChType);
    }
    else
    {
      return nullptr;
    }
  }
  else
  {
    const unsigned idx = m_cuIdx[effChType][rsAddr( pos, _blk.pos(), _blk.width, unitScale[effChType] )];

    if( idx != 0 ) return cus[ idx - 1 ];
    else           return nullptr;
  }
}

const CodingUnit* CodingStructure::getCU( const Position &pos, const ChannelType effChType ) const
{
  const CompArea &_blk = area.blocks[effChType];

#if JVET_O0050_LOCAL_DUAL_TREE
  if( !_blk.contains( pos ) || (treeType == TREE_C && effChType == CHANNEL_TYPE_LUMA) )
#else
  if( !_blk.contains( pos ) )
#endif
  {
#if JVET_O0050_LOCAL_DUAL_TREE
    if( treeType == TREE_C && effChType == CHANNEL_TYPE_LUMA )
      CHECK( parent->treeType != TREE_D, "wrong parent treeType" );
#endif
    if( parent ) return parent->getCU( pos, effChType );
    else         return nullptr;
  }
  else
  {
    const unsigned idx = m_cuIdx[effChType][rsAddr( pos, _blk.pos(), _blk.width, unitScale[effChType] )];

    if( idx != 0 ) return cus[ idx - 1 ];
    else           return nullptr;
  }
}

PredictionUnit* CodingStructure::getPU( const Position &pos, const ChannelType effChType )
{
  const CompArea &_blk = area.blocks[effChType];

  if( !_blk.contains( pos ) )
  {
    if( parent ) return parent->getPU( pos, effChType );
    else         return nullptr;
  }
  else
  {
    const unsigned idx = m_puIdx[effChType][rsAddr( pos, _blk.pos(), _blk.width, unitScale[effChType] )];

    if( idx != 0 ) return pus[ idx - 1 ];
    else           return nullptr;
  }
}

const PredictionUnit * CodingStructure::getPU( const Position &pos, const ChannelType effChType ) const
{
  const CompArea &_blk = area.blocks[effChType];

  if( !_blk.contains( pos ) )
  {
    if( parent ) return parent->getPU( pos, effChType );
    else         return nullptr;
  }
  else
  {
    const unsigned idx = m_puIdx[effChType][rsAddr( pos, _blk.pos(), _blk.width, unitScale[effChType] )];

    if( idx != 0 ) return pus[ idx - 1 ];
    else           return nullptr;
  }
}

TransformUnit* CodingStructure::getTU( const Position &pos, const ChannelType effChType, const int subTuIdx )
{
  const CompArea &_blk = area.blocks[effChType];

  if( !_blk.contains( pos ) )
  {
    if( parent ) return parent->getTU( pos, effChType );
    else         return nullptr;
  }
  else
  {
    const unsigned idx = m_tuIdx[effChType][rsAddr( pos, _blk.pos(), _blk.width, unitScale[effChType] )];

    if( idx != 0 )
    {
      unsigned extraIdx = 0;
      if( isLuma( effChType ) )
      {
        const TransformUnit& tu = *tus[idx - 1];

        if( tu.cu->ispMode ) // Intra SubPartitions mode
        {
          //we obtain the offset to index the corresponding sub-partition
          if( subTuIdx != -1 )
          {
            extraIdx = subTuIdx;
          }
          else
          {
            while( !tus[idx - 1 + extraIdx]->blocks[getFirstComponentOfChannel( effChType )].contains( pos ) )
            {
              extraIdx++;
#if JVET_O0050_LOCAL_DUAL_TREE
              CHECK( tus[idx - 1 + extraIdx]->cu->treeType == TREE_C, "tu searched by position points to a chroma tree CU" );
              CHECK( extraIdx > 3, "extraIdx > 3" );
#endif
            }
          }
        }
      }
      return tus[idx - 1 + extraIdx];
    }
    else if( m_isTuEnc ) return parent->getTU( pos, effChType );
    else                 return nullptr;
  }
}

const TransformUnit * CodingStructure::getTU( const Position &pos, const ChannelType effChType, const int subTuIdx ) const
{
  const CompArea &_blk = area.blocks[effChType];

  if( !_blk.contains( pos ) )
  {
    if( parent ) return parent->getTU( pos, effChType );
    else         return nullptr;
  }
  else
  {
    const unsigned idx = m_tuIdx[effChType][rsAddr( pos, _blk.pos(), _blk.width, unitScale[effChType] )];
    if( idx != 0 )
    {
      unsigned extraIdx = 0;
      if( isLuma( effChType ) )
      {
        const TransformUnit& tu = *tus[idx - 1];
        if( tu.cu->ispMode ) // Intra SubPartitions mode
        {
          //we obtain the offset to index the corresponding sub-partition
          if( subTuIdx != -1 )
          {
            extraIdx = subTuIdx;
          }
          else
          {
            while ( !tus[idx - 1 + extraIdx]->blocks[getFirstComponentOfChannel( effChType )].contains(pos) )
            {
              extraIdx++;
#if JVET_O0050_LOCAL_DUAL_TREE
              CHECK( tus[idx - 1 + extraIdx]->cu->treeType == TREE_C, "tu searched by position points to a chroma tree CU" );
              CHECK( extraIdx > 3, "extraIdx > 3" );
#endif
            }
          }
        }
      }
      return tus[idx - 1 + extraIdx];
    }
    else if( m_isTuEnc ) return parent->getTU( pos, effChType );
    else                 return nullptr;
  }
}

CodingUnit& CodingStructure::addCU( const UnitArea &unit, const ChannelType chType )
{
  CodingUnit *cu = m_cuCache.get();

  cu->UnitArea::operator=( unit );
  cu->initData();
  cu->cs        = this;
  cu->slice     = nullptr;
  cu->next      = nullptr;
  cu->firstPU   = nullptr;
  cu->lastPU    = nullptr;
  cu->firstTU   = nullptr;
  cu->lastTU    = nullptr;
  cu->chType    = chType;
#if JVET_O0050_LOCAL_DUAL_TREE
  cu->treeType = treeType;
  cu->modeType = modeType;
#endif

  CodingUnit *prevCU = m_numCUs > 0 ? cus.back() : nullptr;

  if( prevCU )
  {
    prevCU->next = cu;
#if ENABLE_SPLIT_PARALLELISM || ENABLE_WPP_PARALLELISM

    CHECK( prevCU->cacheId != cu->cacheId, "Inconsintent cacheId between previous and current CU" );
#endif
  }

  cus.push_back( cu );

  uint32_t idx = ++m_numCUs;
  cu->idx  = idx;

  uint32_t numCh = ::getNumberValidChannels( area.chromaFormat );

  for( uint32_t i = 0; i < numCh; i++ )
  {
    if( !cu->blocks[i].valid() )
    {
      continue;
    }

    const CompArea &_selfBlk = area.blocks[i];
    const CompArea     &_blk = cu-> blocks[i];

    const UnitScale& scale = unitScale[_blk.compID];
    const Area scaledSelf  = scale.scale( _selfBlk );
    const Area scaledBlk   = scale.scale(     _blk );
    unsigned *idxPtr       = m_cuIdx[i] + rsAddr( scaledBlk.pos(), scaledSelf.pos(), scaledSelf.width );
    CHECK( *idxPtr, "Overwriting a pre-existing value, should be '0'!" );
    AreaBuf<uint32_t>( idxPtr, scaledSelf.width, scaledBlk.size() ).fill( idx );
  }

  return *cu;
}

PredictionUnit& CodingStructure::addPU( const UnitArea &unit, const ChannelType chType )
{
  PredictionUnit *pu = m_puCache.get();

  pu->UnitArea::operator=( unit );
  pu->initData();
  pu->next   = nullptr;
  pu->cs     = this;
  pu->cu     = m_isTuEnc ? cus[0] : getCU( unit.blocks[chType].pos(), chType );
  pu->chType = chType;
#if ENABLE_SPLIT_PARALLELISM || ENABLE_WPP_PARALLELISM

  CHECK( pu->cacheId != pu->cu->cacheId, "Inconsintent cacheId between the PU and assigned CU" );
  CHECK( pu->cu->firstPU != nullptr, "Without an RQT the firstPU should be null" );
#endif

  PredictionUnit *prevPU = m_numPUs > 0 ? pus.back() : nullptr;

  if( prevPU && prevPU->cu == pu->cu )
  {
    prevPU->next = pu;
#if ENABLE_SPLIT_PARALLELISM || ENABLE_WPP_PARALLELISM

    CHECK( prevPU->cacheId != pu->cacheId, "Inconsintent cacheId between previous and current PU" );
#endif
  }

  pus.push_back( pu );

  if( pu->cu->firstPU == nullptr )
  {
    pu->cu->firstPU = pu;
  }
  pu->cu->lastPU = pu;

  uint32_t idx = ++m_numPUs;
  pu->idx  = idx;

  uint32_t numCh = ::getNumberValidChannels( area.chromaFormat );
  for( uint32_t i = 0; i < numCh; i++ )
  {
    if( !pu->blocks[i].valid() )
    {
      continue;
    }

    const CompArea &_selfBlk = area.blocks[i];
    const CompArea     &_blk = pu-> blocks[i];

    const UnitScale& scale = unitScale[_blk.compID];
    const Area scaledSelf  = scale.scale( _selfBlk );
    const Area scaledBlk   = scale.scale(     _blk );
    unsigned *idxPtr       = m_puIdx[i] + rsAddr( scaledBlk.pos(), scaledSelf.pos(), scaledSelf.width );
    CHECK( *idxPtr, "Overwriting a pre-existing value, should be '0'!" );
    AreaBuf<uint32_t>( idxPtr, scaledSelf.width, scaledBlk.size() ).fill( idx );
  }

  return *pu;
}

TransformUnit& CodingStructure::addTU( const UnitArea &unit, const ChannelType chType )
{
  TransformUnit *tu = m_tuCache.get();

  tu->UnitArea::operator=( unit );
  tu->initData();
  tu->next   = nullptr;
  tu->prev   = nullptr;
  tu->cs     = this;
  tu->cu     = m_isTuEnc ? cus[0] : getCU( unit.blocks[chType].pos(), chType );
  tu->chType = chType;
#if ENABLE_SPLIT_PARALLELISM || ENABLE_WPP_PARALLELISM

  if( tu->cu )
    CHECK( tu->cacheId != tu->cu->cacheId, "Inconsintent cacheId between the TU and assigned CU" );
#endif


  TransformUnit *prevTU = m_numTUs > 0 ? tus.back() : nullptr;

  if( prevTU && prevTU->cu == tu->cu )
  {
    prevTU->next = tu;
    tu->prev     = prevTU;
#if ENABLE_SPLIT_PARALLELISM || ENABLE_WPP_PARALLELISM

    CHECK( prevTU->cacheId != tu->cacheId, "Inconsintent cacheId between previous and current TU" );
#endif
  }

  tus.push_back( tu );

  if( tu->cu )
  {
    if( tu->cu->firstTU == nullptr )
    {
      tu->cu->firstTU = tu;
    }
    tu->cu->lastTU = tu;
  }

  uint32_t idx = ++m_numTUs;
  tu->idx  = idx;

  TCoeff *coeffs[5] = { nullptr, nullptr, nullptr, nullptr, nullptr };
  Pel    *pcmbuf[5] = { nullptr, nullptr, nullptr, nullptr, nullptr };
#if JVET_O0119_BASE_PALETTE_444
  bool   *runType[5]   = { nullptr, nullptr, nullptr, nullptr, nullptr };
  Pel    *runLength[5] = { nullptr, nullptr, nullptr, nullptr, nullptr };
#endif

  uint32_t numCh = ::getNumberValidComponents( area.chromaFormat );

  for( uint32_t i = 0; i < numCh; i++ )
  {
    if( !tu->blocks[i].valid() )
    {
      continue;
    }

    if (i < ::getNumberValidChannels(area.chromaFormat))
    {
      const CompArea &_selfBlk = area.blocks[i];
      const CompArea     &_blk = tu-> blocks[i];

      bool isIspTu = tu->cu != nullptr && tu->cu->ispMode && isLuma( _blk.compID );

      bool isFirstIspTu = false;
      if( isIspTu )
      {
        isFirstIspTu = CU::isISPFirst( *tu->cu, _blk, getFirstComponentOfChannel( ChannelType( i ) ) );
      }
      if( !isIspTu || isFirstIspTu )
      {
        const UnitScale& scale = unitScale[_blk.compID];

        const Area scaledSelf  = scale.scale( _selfBlk );
        const Area scaledBlk   = isIspTu ? scale.scale( tu->cu->blocks[i] ) : scale.scale( _blk );
        unsigned *idxPtr       = m_tuIdx[i] + rsAddr( scaledBlk.pos(), scaledSelf.pos(), scaledSelf.width );
        CHECK( *idxPtr, "Overwriting a pre-existing value, should be '0'!" );
        AreaBuf<uint32_t>( idxPtr, scaledSelf.width, scaledBlk.size() ).fill( idx );
      }
    }

    coeffs[i] = m_coeffs[i] + m_offsets[i];
    pcmbuf[i] = m_pcmbuf[i] + m_offsets[i];
#if JVET_O0119_BASE_PALETTE_444
    runType[i]   = m_runType[i]   + m_offsets[i];
    runLength[i] = m_runLength[i] + m_offsets[i];
#endif

    unsigned areaSize = tu->blocks[i].area();
    m_offsets[i] += areaSize;
  }

#if JVET_O0119_BASE_PALETTE_444
  tu->init( coeffs, pcmbuf, runLength, runType);
#else
  tu->init( coeffs, pcmbuf );
#endif

  return *tu;
}

CUTraverser CodingStructure::traverseCUs( const UnitArea& unit, const ChannelType effChType )
{
  CodingUnit* firstCU = getCU( isLuma( effChType ) ? unit.lumaPos() : unit.chromaPos(), effChType );
  CodingUnit* lastCU = firstCU;
#if JVET_O0050_LOCAL_DUAL_TREE
  if( !CS::isDualITree( *this ) ) //for a more generalized separate tree
  {
    bool bContinue = true;
    CodingUnit* currCU = firstCU;
    while( bContinue )
    {
      if( currCU == nullptr )
      {
        bContinue = false;
        lastCU = currCU;
      }
      else if( currCU->chType != effChType )
      {
        lastCU = currCU;
        currCU = currCU->next;
      }
      else
      {
        if( unit.contains( *currCU ) )
        {
          lastCU = currCU;
          currCU = currCU->next;
        }
        else
        {
          bContinue = false;
          lastCU = currCU;
        }
      }
    }
  }
  else
  {
#endif
  do { } while( lastCU && ( lastCU = lastCU->next ) && unit.contains( *lastCU ) );
#if JVET_O0050_LOCAL_DUAL_TREE
  }
#endif

  return CUTraverser( firstCU, lastCU );
}

PUTraverser CodingStructure::traversePUs( const UnitArea& unit, const ChannelType effChType )
{
  PredictionUnit* firstPU = getPU( isLuma( effChType ) ? unit.lumaPos() : unit.chromaPos(), effChType );
  PredictionUnit* lastPU  = firstPU;

  do { } while( lastPU && ( lastPU = lastPU->next ) && unit.contains( *lastPU ) );

  return PUTraverser( firstPU, lastPU );
}

TUTraverser CodingStructure::traverseTUs( const UnitArea& unit, const ChannelType effChType )
{
  TransformUnit* firstTU = getTU( isLuma( effChType ) ? unit.lumaPos() : unit.chromaPos(), effChType );
  TransformUnit* lastTU  = firstTU;

  do { } while( lastTU && ( lastTU = lastTU->next ) && unit.contains( *lastTU ) );

  return TUTraverser( firstTU, lastTU );
}

cCUTraverser CodingStructure::traverseCUs( const UnitArea& unit, const ChannelType effChType ) const
{
  const CodingUnit* firstCU = getCU( isLuma( effChType ) ? unit.lumaPos() : unit.chromaPos(), effChType );
  const CodingUnit* lastCU  = firstCU;

  do { } while( lastCU && ( lastCU = lastCU->next ) && unit.contains( *lastCU ) );

  return cCUTraverser( firstCU, lastCU );
}

cPUTraverser CodingStructure::traversePUs( const UnitArea& unit, const ChannelType effChType ) const
{
  const PredictionUnit* firstPU = getPU( isLuma( effChType ) ? unit.lumaPos() : unit.chromaPos(), effChType );
  const PredictionUnit* lastPU  = firstPU;

  do { } while( lastPU && ( lastPU = lastPU->next ) && unit.contains( *lastPU ) );

  return cPUTraverser( firstPU, lastPU );
}

cTUTraverser CodingStructure::traverseTUs( const UnitArea& unit, const ChannelType effChType ) const
{
  const TransformUnit* firstTU = getTU( isLuma( effChType ) ? unit.lumaPos() : unit.chromaPos(), effChType );
  const TransformUnit* lastTU  = firstTU;

  do { } while( lastTU && ( lastTU = lastTU->next ) && unit.contains( *lastTU ) );

  return cTUTraverser( firstTU, lastTU );
}

// coding utilities

void CodingStructure::allocateVectorsAtPicLevel()
{
  const int  twice = ( !pcv->ISingleTree && slice->isIRAP() && pcv->chrFormat != CHROMA_400 ) ? 2 : 1;
  size_t allocSize = twice * unitScale[0].scale( area.blocks[0].size() ).area();

  cus.reserve( allocSize );
  pus.reserve( allocSize );
  tus.reserve( allocSize );
}



void CodingStructure::create(const ChromaFormat &_chromaFormat, const Area& _area, const bool isTopLayer)
{
  createInternals( UnitArea( _chromaFormat, _area ), isTopLayer );

  if( isTopLayer ) return;

  m_reco.create( area );
  m_pred.create( area );
  m_resi.create( area );
  m_orgr.create( area );
}

void CodingStructure::create(const UnitArea& _unit, const bool isTopLayer)
{
  createInternals( _unit, isTopLayer );

  if( isTopLayer ) return;

  m_reco.create( area );
  m_pred.create( area );
  m_resi.create( area );
  m_orgr.create( area );
}

void CodingStructure::createInternals( const UnitArea& _unit, const bool isTopLayer )
{
  area = _unit;

  memcpy( unitScale, UnitScaleArray[area.chromaFormat], sizeof( unitScale ) );

  picture = nullptr;
  parent  = nullptr;

  unsigned numCh = ::getNumberValidChannels(area.chromaFormat);

  for (unsigned i = 0; i < numCh; i++)
  {
    unsigned _area = unitScale[i].scale( area.blocks[i].size() ).area();

    m_cuIdx[i]    = _area > 0 ? new unsigned[_area] : nullptr;
    m_puIdx[i]    = _area > 0 ? new unsigned[_area] : nullptr;
    m_tuIdx[i]    = _area > 0 ? new unsigned[_area] : nullptr;
    m_isDecomp[i] = _area > 0 ? new bool    [_area] : nullptr;
  }

  numCh = getNumberValidComponents(area.chromaFormat);

  for (unsigned i = 0; i < numCh; i++)
  {
    m_offsets[i] = 0;
  }

  if( !isTopLayer ) createCoeffs();

  unsigned _lumaAreaScaled = g_miScaling.scale( area.lumaSize() ).area();
  m_motionBuf       = new MotionInfo[_lumaAreaScaled];
  initStructData();
}

void CodingStructure::addMiToLut(static_vector<MotionInfo, MAX_NUM_HMVP_CANDS> &lut, const MotionInfo &mi)
{
  size_t currCnt = lut.size();

  bool pruned      = false;
  int  sameCandIdx = 0;

  for (int idx = 0; idx < currCnt; idx++)
  {
    if (lut[idx] == mi)
    {
      sameCandIdx = idx;
      pruned      = true;
      break;
    }
  }

  if (pruned || currCnt == lut.capacity())
  {
    lut.erase(lut.begin() + sameCandIdx);
  }

  lut.push_back(mi);
}

#if JVET_O0119_BASE_PALETTE_444
void CodingStructure::resetPrevPLT(PLTBuf& prevPLT)
{
  for (int comp = 0; comp < MAX_NUM_COMPONENT; comp++)
  {
    prevPLT.curPLTSize[comp] = 0;
    memset(prevPLT.curPLT[comp], 0, MAXPLTPREDSIZE * sizeof(Pel));
  }
}

void CodingStructure::reorderPrevPLT(PLTBuf& prevPLT, uint32_t curPLTSize[MAX_NUM_COMPONENT], Pel curPLT[MAX_NUM_COMPONENT][MAXPLTSIZE], bool reuseflag[MAX_NUM_COMPONENT][MAXPLTPREDSIZE], uint32_t compBegin, uint32_t numComp, bool jointPLT)
{
  Pel stuffedPLT[MAX_NUM_COMPONENT][MAXPLTPREDSIZE];
  uint32_t tempCurPLTsize[MAX_NUM_COMPONENT];
  uint32_t stuffPLTsize[MAX_NUM_COMPONENT];

  for (int i = compBegin; i < (compBegin + numComp); i++)
  {
    ComponentID comID = jointPLT ? (ComponentID)compBegin : ((i > 0) ? COMPONENT_Cb : COMPONENT_Y);
    tempCurPLTsize[comID] = curPLTSize[comID];
    stuffPLTsize[i] = 0;
    memcpy(stuffedPLT[i], curPLT[i], curPLTSize[comID] * sizeof(Pel));
  }

  for (int ch = compBegin; ch < (compBegin + numComp); ch++)
  {
    ComponentID comID = jointPLT ? (ComponentID)compBegin : ((ch > 0) ? COMPONENT_Cb : COMPONENT_Y);
    if (ch > 1) break;
    for (int i = 0; i < prevPLT.curPLTSize[comID]; i++)
    {
      if (tempCurPLTsize[comID] + stuffPLTsize[ch] >= MAXPLTPREDSIZE)
        break;

      if (!reuseflag[comID][i])
      {
        if (ch == COMPONENT_Y)
        {
          stuffedPLT[0][tempCurPLTsize[comID] + stuffPLTsize[ch]] = prevPLT.curPLT[0][i];
        }
        else
        {
          stuffedPLT[1][tempCurPLTsize[comID] + stuffPLTsize[ch]] = prevPLT.curPLT[1][i];
          stuffedPLT[2][tempCurPLTsize[comID] + stuffPLTsize[ch]] = prevPLT.curPLT[2][i];
        }
        stuffPLTsize[ch]++;
      }
    }
  }

  for (int i = compBegin; i < (compBegin + numComp); i++)
  {
    ComponentID comID = jointPLT ? (ComponentID)compBegin : ((i > 0) ? COMPONENT_Cb : COMPONENT_Y);
    prevPLT.curPLTSize[comID] = curPLTSize[comID] + stuffPLTsize[comID];
    memcpy(prevPLT.curPLT[i], stuffedPLT[i], prevPLT.curPLTSize[comID] * sizeof(Pel));
  }
}
#endif

void CodingStructure::rebindPicBufs()
{
  CHECK( parent, "rebindPicBufs can only be used for the top level CodingStructure" );

  if( !picture->M_BUFS( 0, PIC_RECONSTRUCTION ).bufs.empty() ) m_reco.createFromBuf( picture->M_BUFS( 0, PIC_RECONSTRUCTION ) );
  else                                                         m_reco.destroy();
  if( !picture->M_BUFS( 0, PIC_PREDICTION     ).bufs.empty() ) m_pred.createFromBuf( picture->M_BUFS( 0, PIC_PREDICTION ) );
  else                                                         m_pred.destroy();
  if( !picture->M_BUFS( 0, PIC_RESIDUAL       ).bufs.empty() ) m_resi.createFromBuf( picture->M_BUFS( 0, PIC_RESIDUAL ) );
  else                                                         m_resi.destroy();
  if( pcv->isEncoder )
  {
    if( !picture->M_BUFS( 0, PIC_RESIDUAL     ).bufs.empty() ) m_orgr.create( area.chromaFormat, area.blocks[0], pcv->maxCUWidth );
    else                                                       m_orgr.destroy();
  }
}

void CodingStructure::createCoeffs()
{
  const unsigned numCh = getNumberValidComponents( area.chromaFormat );

  for( unsigned i = 0; i < numCh; i++ )
  {
    unsigned _area = area.blocks[i].area();

    m_coeffs[i] = _area > 0 ? ( TCoeff* ) xMalloc( TCoeff, _area ) : nullptr;
    m_pcmbuf[i] = _area > 0 ? ( Pel*    ) xMalloc( Pel,    _area ) : nullptr;
#if JVET_O0119_BASE_PALETTE_444
    m_runType[i]   = _area > 0 ? ( bool*  ) xMalloc( bool, _area ) : nullptr;
    m_runLength[i] = _area > 0 ? ( Pel*   ) xMalloc( Pel,  _area ) : nullptr;
#endif
  }
}

void CodingStructure::destroyCoeffs()
{
  for( uint32_t i = 0; i < MAX_NUM_COMPONENT; i++ )
  {
    if( m_coeffs[i] ) { xFree( m_coeffs[i] ); m_coeffs[i] = nullptr; }
    if( m_pcmbuf[i] ) { xFree( m_pcmbuf[i] ); m_pcmbuf[i] = nullptr; }
#if JVET_O0119_BASE_PALETTE_444
    if (m_runType[i])   { xFree(m_runType[i]);   m_runType[i]   = nullptr; }
    if (m_runLength[i]) { xFree(m_runLength[i]); m_runLength[i] = nullptr; }
#endif
  }
}

void CodingStructure::initSubStructure( CodingStructure& subStruct, const ChannelType _chType, const UnitArea &subArea, const bool &isTuEnc )
{
  CHECK( this == &subStruct, "Trying to init self as sub-structure" );

  subStruct.useDbCost = false;
  subStruct.costDbOffset = 0;

  for( uint32_t i = 0; i < subStruct.area.blocks.size(); i++ )
  {
    CHECKD( subStruct.area.blocks[i].size() != subArea.blocks[i].size(), "Trying to init sub-structure of incompatible size" );

    subStruct.area.blocks[i].pos() = subArea.blocks[i].pos();
  }