bitmapregion2d.hh

来自「Motion JPEG编解码器源代码」· HH 代码 · 共 1,442 行 · 第 1/3 页

				if (a_reStatus != g_kNoError)
					return;

				// Look for another extent.
				bStartedExtent = false;
			}
		}

nextExtent:
		// Move to the next extent.
		++itExtent;

		// If the to-do list needs to be replenished, do so.
		if (itExtent == a_rControl.m_oToDo.End())
		{
			// Replenish the to-do list.
			a_rControl.m_oNextToDo.Subtract (a_reStatus,
				a_rControl.m_oAlreadyDone);
			if (a_reStatus != g_kNoError)
				return;
			a_rControl.m_oToDo.Clear();
			a_rControl.m_oToDo.Merge (a_rControl.m_oNextToDo);
			
			// Start over at the beginning.
			itExtent = a_rControl.m_oToDo.Begin();
		}
	}
}



// Make the current region represent the border of the other
// region, i.e. every pixel that borders the region but isn't
// already in the region.
template <class INDEX, class SIZE>
template <class OTHER>
void
BitmapRegion2D<INDEX,SIZE>::MakeBorder (Status_t &a_reStatus,
	const OTHER &a_rOther)
{
	typename OTHER::ConstIterator itExtent;
		// Used to loop through the other region's extents.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Start with an empty region.
	Clear();

	// For every extent in the other region, add every surrounding
	// extent.  That creates a region that looks like the other region,
	// but also contains the border we're after.
	for (itExtent = a_rOther.Begin();
		 itExtent != a_rOther.End();
		 ++itExtent)
	{
		// Add the surrounding extents.
		UnionSurroundingExtents (a_reStatus, (*itExtent).m_tnY,
			(*itExtent).m_tnXStart, (*itExtent).m_tnXEnd);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Finally, subtract the other region.  That punches a hole in us,
	// and creates the border region we're after.
	Subtract (a_reStatus, a_rOther);
	if (a_reStatus != g_kNoError)
		return;
}



// Add all extents surrounding the given extent.  Used by FloodFill().
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::UnionSurroundingExtents
	(Status_t &a_reStatus, INDEX a_tnY, INDEX a_tnXStart,
	INDEX a_tnXEnd)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Add the extent above this one.
	if (a_tnY > 0)
	{
		Union (a_reStatus, a_tnY - 1, a_tnXStart, a_tnXEnd);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Add the extent to the left.
	if (a_tnXStart > 0)
	{
		Union (a_reStatus, a_tnY, a_tnXStart - 1, a_tnXStart);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Add the extent to the right.
	if (a_tnXEnd < m_tnWidth)
	{
		Union (a_reStatus, a_tnY, a_tnXEnd, a_tnXEnd + 1);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Add the extent below this one.
	if (a_tnY < m_tnWidth - 1)
	{
		Union (a_reStatus, a_tnY + 1, a_tnXStart, a_tnXEnd);
		if (a_reStatus != g_kNoError)
			return;
	}
}



// Move one of our iterators forward.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::IteratorForward
	(ConstIterator &a_ritHere) const
{
	SIZE tnWordIndex, tnBitIndex;
		// The word/bit index that corresponds to the x/y pixel index.
	SIZE tnLastWordIndex, tnLastBitIndex;
		// The word/bit index for the last pixel in the current line.
	unsigned int nWord;
		// A bitmap word being examined.
	unsigned int nMask;
		// A bitmask we generate.

	// We'll start looking for a new extent after the end of the old
	// extent.  Find the word/bit index for that, and the word itself.
	tnBitIndex = SIZE (a_ritHere.m_oExtent.m_tnY) * SIZE (m_tnWidth)
		+ SIZE (a_ritHere.m_oExtent.m_tnXEnd);
	tnWordIndex = tnBitIndex >> Limits<unsigned int>::Log2Bits;
	tnBitIndex -= tnWordIndex << Limits<unsigned int>::Log2Bits;
	nWord = m_pnPoints[tnWordIndex];

	// Skip all clear bits.  First check the current word to see if the
	// rest of its bits are clear, then skip over all all-clear words.
	if ((nWord & ((~0U) << tnBitIndex)) == 0U)
	{
		// The rest of the current word's bits are clear.
		++tnWordIndex;
		tnBitIndex = 0;

		// Skip over all all-clear words.
		while (tnWordIndex < m_tnBitmapInts
				&& m_pnPoints[tnWordIndex] == 0U)
			++tnWordIndex;

		// If we reached the end of the bitmap, let our caller know.
		if (tnWordIndex == m_tnBitmapInts)
		{
			a_ritHere = End();
			return;
		}

		// Get the current word.
		nWord = m_pnPoints[tnWordIndex];
	}

	// Look for the next set bit in the current word.
	tnBitIndex = FindFirstSetBit (nWord, tnBitIndex);

	// Calculate the x/y index of this first set bit, and the word/bit
	// index of the end of the line.
	tnLastBitIndex = tnWordIndex * Limits<unsigned int>::Bits
		+ tnBitIndex;
	a_ritHere.m_oExtent.m_tnY = INDEX (tnLastBitIndex / m_tnWidth);
	a_ritHere.m_oExtent.m_tnXStart = tnLastBitIndex
		- SIZE (a_ritHere.m_oExtent.m_tnY) * SIZE (m_tnWidth);
	tnLastBitIndex = SIZE (a_ritHere.m_oExtent.m_tnY + 1)
		* SIZE (m_tnWidth);
	tnLastWordIndex = tnLastBitIndex >> Limits<unsigned int>::Log2Bits;
	tnLastBitIndex -= tnLastWordIndex << Limits<unsigned int>::Log2Bits;

	// Skip all set bits.  First check the current word to see if the
	// rest of its bits are set, then skip over all all-set words.
	nMask = ((~0U) << tnBitIndex);
	if ((nWord & nMask) == nMask)
	{
		// The rest of the current word's bits are set.
		++tnWordIndex;
		tnBitIndex = 0;

		// Skip over all all-set words.
		while (tnWordIndex <= tnLastWordIndex
				&& tnWordIndex < m_tnBitmapInts
				&& m_pnPoints[tnWordIndex] == (~0U))
			++tnWordIndex;

		// If we reached the end of the line, let our caller know.
		if (tnWordIndex > tnLastWordIndex)
		{
			a_ritHere.m_oExtent.m_tnXEnd = m_tnWidth;
			return;
		}

		// Get the current word.
		nWord = m_pnPoints[tnWordIndex];
	}

	// Look for the next clear bit in the current word.
	tnBitIndex = FindFirstClearBit (nWord, tnBitIndex);

	// Clip it to the end of the line.
	if (tnWordIndex == tnLastWordIndex
			&& tnBitIndex > tnLastBitIndex)
		tnBitIndex = tnLastBitIndex;

	// Calculate the x index of this first clear bit; it becomes the
	// end of the extent.
	tnLastBitIndex = tnWordIndex * Limits<unsigned int>::Bits
		+ tnBitIndex;
	a_ritHere.m_oExtent.m_tnXEnd = tnLastBitIndex
		- SIZE (a_ritHere.m_oExtent.m_tnY) * SIZE (m_tnWidth);
	assert (a_ritHere.m_oExtent.m_tnXEnd <= m_tnWidth);
}



// Move one of our iterators backward.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::IteratorBackward
	(ConstIterator &a_ritHere) const
{
	// Not written yet.
	assert (false);
}



// Find the first set bit.
template <class INDEX, class SIZE>
int
BitmapRegion2D<INDEX,SIZE>::FindFirstSetBit (unsigned int a_nWord,
	int a_nSkip)
{
	int nLow, nHigh;
		// The search range.
	
	// Skip the first a_nSkip bits by clearing them.
	a_nWord &= ((~0U) << a_nSkip);
	
	// Make sure at least one bit is set.
	assert (a_nWord != 0U);

	// Find the range of all-clear LSB bits, i.e. the highest index
	// such that it and all lower-index bits are zero.
	nLow = 0;	// faster than nLow = a_nSkip?
	nHigh = Limits<unsigned int>::Bits - 1;
	while (nLow < nHigh)
	{
		// Look in the middle.
		int nCurrent = (nLow + nHigh) >> 1;

		// Generate a mask where bits 0-nCurrent are all set, and
		// the remaining bits are clear.
		unsigned int nCurrentMask = ~((~0U) << (nCurrent + 1));

		// If the nCurrent LSB bits are all clear, look above nCurrent,
		// otherwise look below nCurrent.
		if ((a_nWord & nCurrentMask) == 0U)
			nLow = nCurrent + 1;
		else
			nHigh = nCurrent;
	}

	// Return the index of the first set bit.
	assert (nLow == nHigh);
	return nLow;
}



// Find the first clear bit.
template <class INDEX, class SIZE>
int
BitmapRegion2D<INDEX,SIZE>::FindFirstClearBit (unsigned int a_nWord,
	int a_nSkip)
{
	int nLow, nHigh;
		// The search range.
	
	// Skip the first a_nSkip bits by setting them.
	a_nWord |= ~((~0U) << a_nSkip);
	
	// Make sure at least one bit is clear.
	assert (a_nWord != (~0U));

	// Find the range of all-set LSB bits.
	nLow = 0;	// faster than nLow = a_nSkip?
	nHigh = Limits<unsigned int>::Bits - 1;
	while (nLow < nHigh)
	{
		// Look in the middle.
		int nCurrent = (nLow + nHigh) >> 1;

		// Generate a mask where bits 0-nCurrent are all set, and
		// the remaining bits are clear.
		unsigned int nCurrentMask = ~((~0U) << (nCurrent + 1));

		// If the nCurrent LSB bits are all set, look above nCurrent,
		// otherwise look below nCurrent.
		if ((a_nWord & nCurrentMask) == nCurrentMask)
			nLow = nCurrent + 1;
		else
			nHigh = nCurrent;
	}

	// Return the index of the first clear bit.
	assert (nLow == nHigh);
	return nLow;
}



// Find the last set bit.
template <class INDEX, class SIZE>
int
BitmapRegion2D<INDEX,SIZE>::FindLastSetBit (unsigned int a_nWord,
	int a_nSkip)
{
	// Not written yet.
	assert (false);
}



// Find the last clear bit.
template <class INDEX, class SIZE>
int
BitmapRegion2D<INDEX,SIZE>::FindLastClearBit (unsigned int a_nWord,
	int a_nSkip)
{
	// Not written yet.
	assert (false);
}



// Get the first extent in the region.
template <class INDEX, class SIZE>
typename BitmapRegion2D<INDEX,SIZE>::ConstIterator
BitmapRegion2D<INDEX,SIZE>::Begin (void) const
{
	ConstIterator itBegin;
		// The iterator we construct.
	
	// Start before the beginning of this region.
	itBegin.m_pThis = this;
	itBegin.m_oExtent.m_tnY = 0;
	itBegin.m_oExtent.m_tnXStart = 0;
	itBegin.m_oExtent.m_tnXEnd = 0;
	
	// Move to the first valid extent & return it.
	return ++itBegin;
}



// Get one past the last extent in the region.
template <class INDEX, class SIZE>
typename BitmapRegion2D<INDEX,SIZE>::ConstIterator
BitmapRegion2D<INDEX,SIZE>::End (void) const
{
	ConstIterator itEnd;
		// The iterator we construct.
	
	// Since extents can't be zero-length, a zero-length extent
	// indicates the end.
	itEnd.m_pThis = this;
	itEnd.m_oExtent.m_tnY = 0;
	itEnd.m_oExtent.m_tnXStart = 0;
	itEnd.m_oExtent.m_tnXEnd = 0;
	return itEnd;
}



// Move forward to the next extent.
template <class INDEX, class SIZE>
typename BitmapRegion2D<INDEX,SIZE>::ConstIterator&
BitmapRegion2D<INDEX,SIZE>::ConstIterator::operator++()
{
	// Make sure we know what region we're iterating through.
	assert (m_pThis != NULL);

	// It does all the work.
	m_pThis->IteratorForward (*this);
	return *this;
}



// Move backward to the previous extent.
template <class INDEX, class SIZE>
typename BitmapRegion2D<INDEX,SIZE>::ConstIterator&
BitmapRegion2D<INDEX,SIZE>::ConstIterator::operator--()
{
	// Make sure we know what region we're iterating through.
	assert (m_pThis != NULL);

	// It does all the work.
	m_pThis->IteratorBackward (*this);
	return *this;
}


	
// The set-bits-per-byte table.
// Used to implement NumberOfPoints().
template <class INDEX, class SIZE>
int8_t BitmapRegion2D<INDEX,SIZE>::m_anSetBitsPerByte[256];
template <class INDEX, class SIZE>
bool BitmapRegion2D<INDEX,SIZE>::m_bSetBitsPerByte = false;



// Default constructor.  Must be followed by a call to Init().
template <class INDEX, class SIZE>
BitmapRegion2D<INDEX,SIZE>::FloodFillControl::FloodFillControl()
{
	// Nothing to do.
}



// Initializing constructor.
template <class INDEX, class SIZE>
BitmapRegion2D<INDEX,SIZE>::FloodFillControl::FloodFillControl
	(Status_t &a_reStatus, INDEX a_tnWidth, INDEX a_tnHeight)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Initialize ourselves.
	Init (a_reStatus, a_tnWidth, a_tnHeight);
	if (a_reStatus != g_kNoError)
		return;
}



// Initializer.  Must be called on default-constructed objects.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::FloodFillControl::Init
	(Status_t &a_reStatus, INDEX a_tnWidth, INDEX a_tnHeight)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Initialize our helper regions.
	BitmapRegion2D<INDEX,SIZE>::FloodFillControl::m_oToDo.Init (a_reStatus, a_tnWidth, a_tnHeight);
	if (a_reStatus != g_kNoError)
		return;
	BitmapRegion2D<INDEX,SIZE>::FloodFillControl::m_oAlreadyDone.Init (a_reStatus, a_tnWidth, a_tnHeight);
	if (a_reStatus != g_kNoError)
		return;
	BitmapRegion2D<INDEX,SIZE>::FloodFillControl::m_oNextToDo.Init (a_reStatus, a_tnWidth, a_tnHeight);
	if (a_reStatus != g_kNoError)
		return;
}



#ifndef NDEBUG
template <class INDEX, class SIZE>
uint32_t BitmapRegion2D<INDEX,SIZE>::sm_ulInstances;
#endif // NDEBUG



#endif // __BITMAPREGION2D_H__