+++ /dev/null
-//////////////////////////////////////////////////////////////////////////////\r
-//\r
-// Copyright (C) Microsoft Corporation. All Rights Reserved.\r
-//\r
-// File: D3DXGlobal.h\r
-// Content: D3DX11 Effects helper defines and data structures\r
-//\r
-//////////////////////////////////////////////////////////////////////////////\r
-\r
-#pragma once\r
-\r
-#pragma warning(disable : 4100 4127 4189 4201 4245 4389 4505 4701 4706)\r
-\r
-namespace D3DX11Debug\r
-{\r
-}\r
-\r
-using namespace D3DX11Debug;\r
-\r
-#include "d3dx11dbg.h"\r
-\r
-#define SAFE_RELEASE(p) { if (p) { (p)->Release(); (p) = NULL; } }\r
-#define SAFE_ADDREF(p) { if (p) { (p)->AddRef(); } }\r
-\r
-#define SAFE_DELETE_ARRAY(p) { delete [](p); p = NULL; }\r
-#define SAFE_DELETE(p) { delete (p); p = NULL; }\r
-\r
-#if FXDEBUG\r
-#define __BREAK_ON_FAIL { __debugbreak(); }\r
-#else\r
-#define __BREAK_ON_FAIL \r
-#endif\r
-\r
-#define VA(x, action) { hr = (x); if (FAILED(hr)) { action; __BREAK_ON_FAIL; return hr; } }\r
-#define VNA(x,action) { if (!(x)) { action; __BREAK_ON_FAIL; hr = E_OUTOFMEMORY; goto lExit; } }\r
-#define VBA(x,action) { if (!(x)) { action; __BREAK_ON_FAIL; hr = E_FAIL; goto lExit; } }\r
-#define VHA(x,action) { hr = (x); if (FAILED(hr)) { action; __BREAK_ON_FAIL; goto lExit; } }\r
-\r
-#define V(x) { VA (x, 0) }\r
-#define VN(x) { VNA(x, 0) }\r
-#define VB(x) { VBA(x, 0) }\r
-#define VH(x) { VHA(x, 0) }\r
-\r
-#define VBD(x,str) { VBA(x, DPF(1,str)) }\r
-#define VHD(x,str) { VHA(x, DPF(1,str)) }\r
-\r
-#define VEASSERT(x) { hr = (x); if (FAILED(hr)) { __BREAK_ON_FAIL; D3DXASSERT(!#x); goto lExit; } }\r
-#define VNASSERT(x) { if (!(x)) { __BREAK_ON_FAIL; D3DXASSERT(!#x); hr = E_OUTOFMEMORY; goto lExit; } }\r
-\r
-#define ANALYSIS_ASSUME(x) { D3DXASSERT(x); __analysis_assume(x); __assume(x); }\r
-\r
-#define D3DX11FLTASSIGN(a,b) { *reinterpret_cast< UINT32* >(&(a)) = *reinterpret_cast< UINT32* >(&(b)); }\r
-\r
-// Preferred data alignment -- must be a power of 2!\r
-static const UINT c_DataAlignment = sizeof(UINT_PTR);\r
-\r
-D3DX11INLINE UINT AlignToPowerOf2(UINT Value, UINT Alignment)\r
-{\r
- D3DXASSERT((Alignment & (Alignment - 1)) == 0);\r
- // to align to 2^N, add 2^N - 1 and AND with all but lowest N bits set\r
- ANALYSIS_ASSUME(Alignment > 0 && Value < MAXDWORD - Alignment);\r
- return (Value + Alignment - 1) & (~(Alignment - 1));\r
-}\r
-\r
-D3DX11INLINE void * AlignToPowerOf2(void *pValue, UINT_PTR Alignment)\r
-{\r
- D3DXASSERT((Alignment & (Alignment - 1)) == 0);\r
- // to align to 2^N, add 2^N - 1 and AND with all but lowest N bits set\r
- return (void *)(((UINT_PTR)pValue + Alignment - 1) & (~((UINT_PTR)Alignment - 1)));\r
-}\r
-\r
-\r
-// Fast memcpy\r
-D3DX11INLINE void dwordMemcpy( __out_bcount(uByteCount) void * __restrict pDest, __in_bcount(uByteCount) CONST void * __restrict pSource, UINT uByteCount)\r
-{\r
- UINT i;\r
- D3DXASSERT(uByteCount % 4 == 0);\r
-#ifdef _AMD64_\r
- const UINT qwordCount = uByteCount >> 3;\r
-\r
- __int64* src64 = (__int64*) pSource;\r
- __int64* dst64 = (__int64*) pDest;\r
-\r
- for (i=0; i<(qwordCount & 0x3); i++)\r
- {\r
- *(dst64) = *(src64);\r
- dst64++;\r
- src64++;\r
- }\r
-\r
- for (; i<qwordCount; i+= 4)\r
- {\r
- *(dst64 ) = *(src64 );\r
- *(dst64 + 1 ) = *(src64 + 1 );\r
- *(dst64 + 2 ) = *(src64 + 2 );\r
- *(dst64 + 3 ) = *(src64 + 3 );\r
- dst64 += 4;\r
- src64 += 4;\r
- }\r
-\r
- ANALYSIS_ASSUME( dst64 - static_cast< __int64* >(pDest) <= uByteCount - 4 );\r
- ANALYSIS_ASSUME( src64 - static_cast< const __int64* >(pSource) <= uByteCount - 4 );\r
- if( uByteCount & 0x4 )\r
- {\r
- *((UINT*)dst64) = *((UINT*)src64);\r
- }\r
-#else\r
- const UINT dwordCount = uByteCount >> 2;\r
-\r
- for (i=0; i<(dwordCount & 0x3); i++)\r
- {\r
-#pragma prefast(suppress: __WARNING_UNRELATED_LOOP_TERMINATION, "(dwordCount & 03) < dwordCount")\r
- ((UINT*)pDest)[i ] = ((UINT*)pSource)[i ];\r
- }\r
- for (; i<dwordCount; i+= 4)\r
- {\r
- ((UINT*)pDest)[i ] = ((UINT*)pSource)[i ];\r
- ((UINT*)pDest)[i+1] = ((UINT*)pSource)[i+1];\r
- ((UINT*)pDest)[i+2] = ((UINT*)pSource)[i+2];\r
- ((UINT*)pDest)[i+3] = ((UINT*)pSource)[i+3];\r
- }\r
-#endif\r
-}\r
-\r
-\r
-namespace D3DX11Core\r
-{\r
-\r
-//////////////////////////////////////////////////////////////////////////\r
-// CMemoryStream - A class to simplify reading binary data\r
-//////////////////////////////////////////////////////////////////////////\r
-class CMemoryStream\r
-{\r
- BYTE *m_pData;\r
- SIZE_T m_cbData;\r
- SIZE_T m_readPtr;\r
-\r
-public:\r
- HRESULT SetData(const void *pData, SIZE_T size);\r
-\r
- HRESULT Read(UINT *pUint);\r
- HRESULT Read(void **ppData, SIZE_T size);\r
- HRESULT Read(LPCSTR *ppString);\r
-\r
- HRESULT ReadAtOffset(SIZE_T offset, SIZE_T size, void **ppData);\r
- HRESULT ReadAtOffset(SIZE_T offset, LPCSTR *ppString);\r
-\r
- SIZE_T GetPosition();\r
- HRESULT Seek(SIZE_T offset);\r
-\r
- CMemoryStream();\r
- ~CMemoryStream();\r
-};\r
-\r
-}\r
-\r
-#if FXDEBUG\r
-\r
-namespace D3DX11Debug\r
-{\r
-\r
-// This variable indicates how many ticks to go before rolling over\r
-// all of the timer variables in the FX system.\r
-// It is read from the system registry in debug builds; in retail the high bit is simply tested.\r
-\r
-_declspec(selectany) unsigned int g_TimerRolloverCount = 0x80000000;\r
-}\r
-\r
-#endif // FXDEBUG\r
-\r
-\r
-//////////////////////////////////////////////////////////////////////////\r
-// CEffectVector - A vector implementation\r
-//////////////////////////////////////////////////////////////////////////\r
-\r
-template<class T> class CEffectVector\r
-{\r
-protected:\r
-#if _DEBUG\r
- T *m_pCastData; // makes debugging easier to have a casted version of the data\r
-#endif // _DEBUG\r
-\r
- BYTE *m_pData;\r
- UINT m_MaxSize;\r
- UINT m_CurSize;\r
-\r
- HRESULT Grow()\r
- {\r
- return Reserve(m_CurSize + 1);\r
- }\r
-\r
- HRESULT Reserve(UINT DesiredSize)\r
- {\r
- if (DesiredSize > m_MaxSize)\r
- {\r
- BYTE *pNewData;\r
- UINT newSize = max(m_MaxSize * 2, DesiredSize);\r
-\r
- if (newSize < 16)\r
- newSize = 16;\r
-\r
- if ((newSize < m_MaxSize) || (newSize < m_CurSize) || (newSize >= UINT_MAX / sizeof(T)))\r
- {\r
- m_hLastError = E_OUTOFMEMORY;\r
- return m_hLastError;\r
- }\r
-\r
- pNewData = NEW BYTE[newSize * sizeof(T)];\r
- if (pNewData == NULL)\r
- {\r
- m_hLastError = E_OUTOFMEMORY;\r
- return m_hLastError;\r
- }\r
-\r
- if (m_pData)\r
- {\r
- memcpy(pNewData, m_pData, m_CurSize * sizeof(T));\r
- delete []m_pData;\r
- }\r
-\r
- m_pData = pNewData;\r
- m_MaxSize = newSize;\r
- }\r
-#if _DEBUG\r
- m_pCastData = (T*) m_pData;\r
-#endif // _DEBUG\r
- return S_OK;\r
- }\r
-\r
-public:\r
- HRESULT m_hLastError;\r
-\r
- CEffectVector<T>()\r
- {\r
- m_hLastError = S_OK;\r
-#if _DEBUG\r
- m_pCastData = NULL;\r
-#endif // _DEBUG\r
- m_pData = NULL;\r
- m_CurSize = m_MaxSize = 0;\r
- }\r
-\r
- ~CEffectVector<T>()\r
- {\r
- Clear();\r
- }\r
-\r
- // cleanly swaps two vectors -- useful for when you want\r
- // to reallocate a vector and copy data over, then swap them back\r
- void SwapVector(CEffectVector<T> &vOther)\r
- {\r
- BYTE tempData[sizeof(*this)];\r
-\r
- memcpy(tempData, this, sizeof(*this));\r
- memcpy(this, &vOther, sizeof(*this));\r
- memcpy(&vOther, tempData, sizeof(*this));\r
- }\r
-\r
- HRESULT CopyFrom(CEffectVector<T> &vOther)\r
- {\r
- HRESULT hr = S_OK;\r
- Clear();\r
- VN( m_pData = NEW BYTE[vOther.m_MaxSize * sizeof(T)] );\r
- \r
- m_CurSize = vOther.m_CurSize;\r
- m_MaxSize = vOther.m_MaxSize;\r
- m_hLastError = vOther.m_hLastError;\r
-\r
- UINT i;\r
- for (i = 0; i < m_CurSize; ++ i)\r
- {\r
- ((T*)m_pData)[i] = ((T*)vOther.m_pData)[i];\r
- }\r
-\r
-lExit:\r
-\r
-#if _DEBUG\r
- m_pCastData = (T*) m_pData;\r
-#endif // _DEBUG\r
-\r
- return hr;\r
- }\r
-\r
- void Clear()\r
- {\r
- Empty();\r
- SAFE_DELETE_ARRAY(m_pData);\r
- m_MaxSize = 0;\r
-#if _DEBUG\r
- m_pCastData = NULL;\r
-#endif // _DEBUG\r
- }\r
-\r
- void ClearWithoutDestructor()\r
- {\r
- m_CurSize = 0;\r
- m_hLastError = S_OK;\r
- SAFE_DELETE_ARRAY(m_pData);\r
- m_MaxSize = 0;\r
-\r
-#if _DEBUG\r
- m_pCastData = NULL;\r
-#endif // _DEBUG\r
- }\r
-\r
- void Empty()\r
- {\r
- UINT i;\r
- \r
- // manually invoke destructor on all elements\r
- for (i = 0; i < m_CurSize; ++ i)\r
- { \r
- ((T*)m_pData + i)->~T();\r
- }\r
- m_CurSize = 0;\r
- m_hLastError = S_OK;\r
- }\r
-\r
- T* Add()\r
- {\r
- if (FAILED(Grow()))\r
- return NULL;\r
-\r
- // placement new\r
- return new((T*)m_pData + (m_CurSize ++)) T;\r
- }\r
-\r
- T* AddRange(UINT count)\r
- {\r
- if (m_CurSize + count < m_CurSize)\r
- {\r
- m_hLastError = E_OUTOFMEMORY;\r
- return NULL;\r
- }\r
-\r
- if (FAILED(Reserve(m_CurSize + count)))\r
- return NULL;\r
-\r
- T *pData = (T*)m_pData + m_CurSize;\r
- UINT i;\r
- for (i = 0; i < count; ++ i)\r
- {\r
- new(pData + i) T;\r
- }\r
- m_CurSize += count;\r
- return pData;\r
- }\r
-\r
- HRESULT Add(const T& var)\r
- {\r
- if (FAILED(Grow()))\r
- return m_hLastError;\r
-\r
- memcpy((T*)m_pData + m_CurSize, &var, sizeof(T));\r
- m_CurSize++;\r
-\r
- return S_OK;\r
- }\r
-\r
- HRESULT AddRange(const T *pVar, UINT count)\r
- {\r
- if (m_CurSize + count < m_CurSize)\r
- {\r
- m_hLastError = E_OUTOFMEMORY;\r
- return m_hLastError;\r
- }\r
-\r
- if (FAILED(Reserve(m_CurSize + count)))\r
- return m_hLastError;\r
-\r
- memcpy((T*)m_pData + m_CurSize, pVar, count * sizeof(T));\r
- m_CurSize += count;\r
-\r
- return S_OK;\r
- }\r
-\r
- HRESULT Insert(const T& var, UINT index)\r
- {\r
- D3DXASSERT(index < m_CurSize);\r
- \r
- if (FAILED(Grow()))\r
- return m_hLastError;\r
-\r
- memmove((T*)m_pData + index + 1, (T*)m_pData + index, (m_CurSize - index) * sizeof(T));\r
- memcpy((T*)m_pData + index, &var, sizeof(T));\r
- m_CurSize++;\r
-\r
- return S_OK;\r
- }\r
-\r
- HRESULT InsertRange(const T *pVar, UINT index, UINT count)\r
- {\r
- D3DXASSERT(index < m_CurSize);\r
- \r
- if (m_CurSize + count < m_CurSize)\r
- {\r
- m_hLastError = E_OUTOFMEMORY;\r
- return m_hLastError;\r
- }\r
-\r
- if (FAILED(Reserve(m_CurSize + count)))\r
- return m_hLastError;\r
-\r
- memmove((T*)m_pData + index + count, (T*)m_pData + index, (m_CurSize - index) * sizeof(T));\r
- memcpy((T*)m_pData + index, pVar, count * sizeof(T));\r
- m_CurSize += count;\r
-\r
- return S_OK;\r
- }\r
-\r
- inline T& operator[](UINT index)\r
- {\r
- D3DXASSERT(index < m_CurSize);\r
- return ((T*)m_pData)[index];\r
- }\r
-\r
- // Deletes element at index and shifts all other values down\r
- void Delete(UINT index)\r
- {\r
- D3DXASSERT(index < m_CurSize);\r
-\r
- -- m_CurSize;\r
- memmove((T*)m_pData + index, (T*)m_pData + index + 1, (m_CurSize - index) * sizeof(T));\r
- }\r
-\r
- // Deletes element at index and moves the last element into its place\r
- void QuickDelete(UINT index)\r
- {\r
- D3DXASSERT(index < m_CurSize);\r
-\r
- -- m_CurSize;\r
- memcpy((T*)m_pData + index, (T*)m_pData + m_CurSize, sizeof(T));\r
- }\r
-\r
- inline UINT GetSize() const\r
- {\r
- return m_CurSize;\r
- }\r
-\r
- inline T* GetData() const\r
- {\r
- return (T*)m_pData;\r
- }\r
-\r
- UINT FindIndexOf(void *pEntry) const\r
- {\r
- UINT i;\r
-\r
- for (i = 0; i < m_CurSize; ++ i)\r
- { \r
- if (((T*)m_pData + i) == pEntry)\r
- return i;\r
- }\r
-\r
- return -1;\r
- }\r
-\r
- void Sort(int (__cdecl *pfnCompare)(const void *pElem1, const void *pElem2))\r
- {\r
- qsort(m_pData, m_CurSize, sizeof(T), pfnCompare);\r
- }\r
-};\r
-\r
-//////////////////////////////////////////////////////////////////////////\r
-// CEffectVectorOwner - implements a vector of ptrs to objects. The vector owns the objects.\r
-//////////////////////////////////////////////////////////////////////////\r
-template<class T> class CEffectVectorOwner : public CEffectVector<T*>\r
-{\r
-public:\r
- ~CEffectVectorOwner<T>()\r
- {\r
- Clear();\r
- UINT i;\r
-\r
- for (i=0; i<m_CurSize; i++)\r
- SAFE_DELETE(((T**)m_pData)[i]);\r
-\r
- SAFE_DELETE_ARRAY(m_pData);\r
- }\r
-\r
- void Clear()\r
- {\r
- Empty();\r
- SAFE_DELETE_ARRAY(m_pData);\r
- m_MaxSize = 0;\r
- }\r
-\r
- void Empty()\r
- {\r
- UINT i;\r
-\r
- // manually invoke destructor on all elements\r
- for (i = 0; i < m_CurSize; ++ i)\r
- {\r
- SAFE_DELETE(((T**)m_pData)[i]);\r
- }\r
- m_CurSize = 0;\r
- m_hLastError = S_OK;\r
- }\r
-\r
- void Delete(UINT index)\r
- {\r
- D3DXASSERT(index < m_CurSize);\r
-\r
- SAFE_DELETE(((T**)m_pData)[index]);\r
-\r
- CEffectVector<T*>::Delete(index);\r
- }\r
-};\r
-\r
-\r
-//////////////////////////////////////////////////////////////////////////\r
-// Checked UINT, DWORD64\r
-// Use CheckedNumber only with UINT and DWORD64\r
-//////////////////////////////////////////////////////////////////////////\r
-template <class T, T MaxValue> class CheckedNumber\r
-{\r
- T m_Value;\r
- BOOL m_bValid;\r
-\r
-public:\r
- CheckedNumber<T, MaxValue>()\r
- {\r
- m_Value = 0;\r
- m_bValid = TRUE;\r
- }\r
-\r
- CheckedNumber<T, MaxValue>(const T &value)\r
- {\r
- m_Value = value;\r
- m_bValid = TRUE;\r
- }\r
-\r
- CheckedNumber<T, MaxValue>(const CheckedNumber<T, MaxValue> &value)\r
- {\r
- m_bValid = value.m_bValid;\r
- m_Value = value.m_Value;\r
- }\r
-\r
- CheckedNumber<T, MaxValue> &operator+(const CheckedNumber<T, MaxValue> &other)\r
- {\r
- CheckedNumber<T, MaxValue> Res(*this);\r
- return Res+=other;\r
- }\r
-\r
- CheckedNumber<T, MaxValue> &operator+=(const CheckedNumber<T, MaxValue> &other)\r
- {\r
- if (!other.m_bValid)\r
- {\r
- m_bValid = FALSE;\r
- }\r
- else\r
- {\r
- m_Value += other.m_Value;\r
-\r
- if (m_Value < other.m_Value)\r
- m_bValid = FALSE;\r
- }\r
-\r
- return *this;\r
- }\r
-\r
- CheckedNumber<T, MaxValue> &operator*(const CheckedNumber<T, MaxValue> &other)\r
- {\r
- CheckedNumber<T, MaxValue> Res(*this);\r
- return Res*=other;\r
- }\r
-\r
- CheckedNumber<T, MaxValue> &operator*=(const CheckedNumber<T, MaxValue> &other)\r
- {\r
- if (!other.m_bValid)\r
- {\r
- m_bValid = FALSE;\r
- }\r
- else\r
- {\r
- if (other.m_Value != 0)\r
- {\r
- if (m_Value > MaxValue / other.m_Value)\r
- {\r
- m_bValid = FALSE;\r
- }\r
- }\r
- m_Value *= other.m_Value;\r
- }\r
-\r
- return *this;\r
- }\r
-\r
- HRESULT GetValue(T *pValue)\r
- {\r
- if (!m_bValid)\r
- {\r
- *pValue = -1;\r
- return E_FAIL;\r
- }\r
-\r
- *pValue = m_Value;\r
- return S_OK;\r
- }\r
-};\r
-\r
-typedef CheckedNumber<UINT, _UI32_MAX> CCheckedDword;\r
-typedef CheckedNumber<DWORD64, _UI64_MAX> CCheckedDword64;\r
-\r
-\r
-//////////////////////////////////////////////////////////////////////////\r
-// Data Block Store - A linked list of allocations\r
-//////////////////////////////////////////////////////////////////////////\r
-\r
-class CDataBlock\r
-{\r
-protected:\r
- UINT m_size;\r
- UINT m_maxSize;\r
- BYTE *m_pData;\r
- CDataBlock *m_pNext;\r
-\r
- BOOL m_IsAligned; // Whether or not to align the data to c_DataAlignment\r
-\r
-public:\r
- // AddData appends an existing use buffer to the data block\r
- HRESULT AddData(const void *pNewData, UINT bufferSize, CDataBlock **ppBlock);\r
-\r
- // Allocate reserves bufferSize bytes of contiguous memory and returns a pointer to the user\r
- void* Allocate(UINT bufferSize, CDataBlock **ppBlock);\r
-\r
- void EnableAlignment();\r
-\r
- CDataBlock();\r
- ~CDataBlock();\r
-\r
- friend class CDataBlockStore;\r
-};\r
-\r
-\r
-class CDataBlockStore\r
-{\r
-protected:\r
- CDataBlock *m_pFirst;\r
- CDataBlock *m_pLast;\r
- UINT m_Size;\r
- UINT m_Offset; // m_Offset gets added to offsets returned from AddData & AddString. Use this to set a global for the entire string block\r
- BOOL m_IsAligned; // Whether or not to align the data to c_DataAlignment\r
-\r
-public:\r
-#if _DEBUG\r
- UINT m_cAllocations;\r
-#endif\r
-\r
-public:\r
- HRESULT AddString(LPCSTR pString, UINT *pOffset); // Writes a null-terminated string to buffer\r
- HRESULT AddData(const void *pNewData, UINT bufferSize, UINT *pOffset); // Writes data block to buffer\r
-\r
- void* Allocate(UINT buffferSize); // Memory allocator support\r
- UINT GetSize();\r
- void EnableAlignment();\r
-\r
- CDataBlockStore();\r
- ~CDataBlockStore();\r
-};\r
-\r
-// Custom allocator that uses CDataBlockStore\r
-// The trick is that we never free, so we don't have to keep as much state around\r
-// Use PRIVATENEW in CEffectLoader\r
-\r
-static void* __cdecl operator new(size_t s, CDataBlockStore &pAllocator)\r
-{\r
- D3DXASSERT( s <= 0xffffffff );\r
- return pAllocator.Allocate( (UINT)s );\r
-}\r
-\r
-static void __cdecl operator delete(void* p, CDataBlockStore &pAllocator)\r
-{\r
-}\r
-\r
-\r
-//////////////////////////////////////////////////////////////////////////\r
-// Hash table\r
-//////////////////////////////////////////////////////////////////////////\r
-\r
-#define HASH_MIX(a,b,c) \\r
-{ \\r
- a -= b; a -= c; a ^= (c>>13); \\r
- b -= c; b -= a; b ^= (a<<8); \\r
- c -= a; c -= b; c ^= (b>>13); \\r
- a -= b; a -= c; a ^= (c>>12); \\r
- b -= c; b -= a; b ^= (a<<16); \\r
- c -= a; c -= b; c ^= (b>>5); \\r
- a -= b; a -= c; a ^= (c>>3); \\r
- b -= c; b -= a; b ^= (a<<10); \\r
- c -= a; c -= b; c ^= (b>>15); \\r
-}\r
-\r
-static UINT ComputeHash(BYTE *pb, UINT cbToHash)\r
-{\r
- UINT a;\r
- UINT b;\r
- UINT c;\r
- UINT cbLeft;\r
-\r
- cbLeft = cbToHash;\r
-\r
- a = b = 0x9e3779b9; // the golden ratio; an arbitrary value\r
- c = 0;\r
-\r
- while (cbLeft >= 12)\r
- {\r
- UINT *pdw = reinterpret_cast<UINT *>(pb);\r
-\r
- a += pdw[0];\r
- b += pdw[1];\r
- c += pdw[2];\r
-\r
- HASH_MIX(a,b,c);\r
- pb += 12; \r
- cbLeft -= 12;\r
- }\r
-\r
- c += cbToHash;\r
-\r
- switch(cbLeft) // all the case statements fall through\r
- {\r
- case 11: c+=((UINT) pb[10] << 24);\r
- case 10: c+=((UINT) pb[9] << 16);\r
- case 9 : c+=((UINT) pb[8] << 8);\r
- // the first byte of c is reserved for the length\r
- case 8 : b+=((UINT) pb[7] << 24);\r
- case 7 : b+=((UINT) pb[6] << 16);\r
- case 6 : b+=((UINT) pb[5] << 8);\r
- case 5 : b+=pb[4];\r
- case 4 : a+=((UINT) pb[3] << 24);\r
- case 3 : a+=((UINT) pb[2] << 16);\r
- case 2 : a+=((UINT) pb[1] << 8);\r
- case 1 : a+=pb[0];\r
- }\r
-\r
- HASH_MIX(a,b,c);\r
-\r
- return c;\r
-}\r
-\r
-static UINT ComputeHashLower(BYTE *pb, UINT cbToHash)\r
-{\r
- UINT a;\r
- UINT b;\r
- UINT c;\r
- UINT cbLeft;\r
-\r
- cbLeft = cbToHash;\r
-\r
- a = b = 0x9e3779b9; // the golden ratio; an arbitrary value\r
- c = 0;\r
-\r
- while (cbLeft >= 12)\r
- {\r
- BYTE pbT[12];\r
- for( UINT i = 0; i < 12; i++ )\r
- pbT[i] = (BYTE)tolower(pb[i]);\r
-\r
- UINT *pdw = reinterpret_cast<UINT *>(pbT);\r
-\r
- a += pdw[0];\r
- b += pdw[1];\r
- c += pdw[2];\r
-\r
- HASH_MIX(a,b,c);\r
- pb += 12; \r
- cbLeft -= 12;\r
- }\r
-\r
- c += cbToHash;\r
-\r
- BYTE pbT[12];\r
- for( UINT i = 0; i < cbLeft; i++ )\r
- pbT[i] = (BYTE)tolower(pb[i]);\r
-\r
- switch(cbLeft) // all the case statements fall through\r
- {\r
- case 11: c+=((UINT) pbT[10] << 24);\r
- case 10: c+=((UINT) pbT[9] << 16);\r
- case 9 : c+=((UINT) pbT[8] << 8);\r
- // the first byte of c is reserved for the length\r
- case 8 : b+=((UINT) pbT[7] << 24);\r
- case 7 : b+=((UINT) pbT[6] << 16);\r
- case 6 : b+=((UINT) pbT[5] << 8);\r
- case 5 : b+=pbT[4];\r
- case 4 : a+=((UINT) pbT[3] << 24);\r
- case 3 : a+=((UINT) pbT[2] << 16);\r
- case 2 : a+=((UINT) pbT[1] << 8);\r
- case 1 : a+=pbT[0];\r
- }\r
-\r
- HASH_MIX(a,b,c);\r
-\r
- return c;\r
-}\r
-\r
-\r
-static UINT ComputeHash(LPCSTR pString)\r
-{\r
- return ComputeHash((BYTE*) pString, (UINT)strlen(pString));\r
-}\r
-\r
-\r
-// 1) these numbers are prime\r
-// 2) each is slightly less than double the last\r
-// 4) each is roughly in between two powers of 2;\r
-// (2^n hash table sizes are VERY BAD; they effectively truncate your\r
-// precision down to the n least significant bits of the hash)\r
-static const UINT c_PrimeSizes[] = \r
-{\r
- 11,\r
- 23,\r
- 53,\r
- 97,\r
- 193,\r
- 389,\r
- 769,\r
- 1543,\r
- 3079,\r
- 6151,\r
- 12289,\r
- 24593,\r
- 49157,\r
- 98317,\r
- 196613,\r
- 393241,\r
- 786433,\r
- 1572869,\r
- 3145739,\r
- 6291469,\r
- 12582917,\r
- 25165843,\r
- 50331653,\r
- 100663319,\r
- 201326611,\r
- 402653189,\r
- 805306457,\r
- 1610612741,\r
-};\r
-\r
-static const UINT c_NumPrimes = sizeof(c_PrimeSizes) / sizeof(UINT);\r
-\r
-template<typename T, BOOL (*pfnIsEqual)(const T &Data1, const T &Data2)>\r
-class CEffectHashTable\r
-{\r
-protected:\r
-\r
- struct SHashEntry\r
- {\r
- UINT Hash;\r
- T Data;\r
- SHashEntry *pNext;\r
- };\r
-\r
- // Array of hash entries\r
- SHashEntry **m_rgpHashEntries;\r
- UINT m_NumHashSlots;\r
- UINT m_NumEntries;\r
- bool m_bOwnHashEntryArray;\r
-\r
-public:\r
- class CIterator\r
- {\r
- friend class CEffectHashTable;\r
-\r
- protected:\r
- SHashEntry **ppHashSlot;\r
- SHashEntry *pHashEntry;\r
-\r
- public:\r
- T GetData()\r
- {\r
- D3DXASSERT(NULL != pHashEntry);\r
- return pHashEntry->Data;\r
- }\r
-\r
- UINT GetHash()\r
- {\r
- D3DXASSERT(NULL != pHashEntry);\r
- return pHashEntry->Hash;\r
- }\r
- };\r
-\r
- CEffectHashTable()\r
- {\r
- m_rgpHashEntries = NULL;\r
- m_NumHashSlots = 0;\r
- m_NumEntries = 0;\r
- m_bOwnHashEntryArray = false;\r
- }\r
-\r
- HRESULT Initialize(CEffectHashTable *pOther)\r
- {\r
- HRESULT hr = S_OK;\r
- SHashEntry **rgpNewHashEntries = NULL;\r
- SHashEntry ***rgppListEnds = NULL;\r
- UINT i;\r
- UINT valuesMigrated = 0;\r
- UINT actualSize;\r
-\r
- Cleanup();\r
-\r
- actualSize = pOther->m_NumHashSlots;\r
- VN( rgpNewHashEntries = NEW SHashEntry*[actualSize] );\r
-\r
- ZeroMemory(rgpNewHashEntries, sizeof(SHashEntry*) * actualSize);\r
-\r
- // Expensive operation: rebuild the hash table\r
- CIterator iter, nextIter;\r
- pOther->GetFirstEntry(&iter);\r
- while (!pOther->PastEnd(&iter))\r
- {\r
- UINT index = iter.GetHash() % actualSize;\r
-\r
- // we need to advance to the next element\r
- // before we seize control of this element and move\r
- // it to the new table\r
- nextIter = iter;\r
- pOther->GetNextEntry(&nextIter);\r
-\r
- // seize this hash entry, migrate it to the new table\r
- SHashEntry *pNewEntry;\r
- VN( pNewEntry = NEW SHashEntry );\r
- \r
- pNewEntry->pNext = rgpNewHashEntries[index];\r
- pNewEntry->Data = iter.pHashEntry->Data;\r
- pNewEntry->Hash = iter.pHashEntry->Hash;\r
- rgpNewHashEntries[index] = pNewEntry;\r
-\r
- iter = nextIter;\r
- ++ valuesMigrated;\r
- }\r
-\r
- D3DXASSERT(valuesMigrated == pOther->m_NumEntries);\r
-\r
- m_rgpHashEntries = rgpNewHashEntries;\r
- m_NumHashSlots = actualSize;\r
- m_NumEntries = pOther->m_NumEntries;\r
- m_bOwnHashEntryArray = true;\r
- rgpNewHashEntries = NULL;\r
-\r
-lExit:\r
- SAFE_DELETE_ARRAY( rgpNewHashEntries );\r
- return hr;\r
- }\r
-\r
-protected:\r
- void CleanArray()\r
- {\r
- if (m_bOwnHashEntryArray)\r
- {\r
- SAFE_DELETE_ARRAY(m_rgpHashEntries);\r
- m_bOwnHashEntryArray = false;\r
- }\r
- }\r
-\r
-public:\r
- void Cleanup()\r
- {\r
- UINT i;\r
- for (i = 0; i < m_NumHashSlots; ++ i)\r
- {\r
- SHashEntry *pCurrentEntry = m_rgpHashEntries[i];\r
- SHashEntry *pTempEntry;\r
- while (NULL != pCurrentEntry)\r
- {\r
- pTempEntry = pCurrentEntry->pNext;\r
- SAFE_DELETE(pCurrentEntry);\r
- pCurrentEntry = pTempEntry;\r
- -- m_NumEntries;\r
- }\r
- }\r
- CleanArray();\r
- m_NumHashSlots = 0;\r
- D3DXASSERT(m_NumEntries == 0);\r
- }\r
-\r
- ~CEffectHashTable()\r
- {\r
- Cleanup();\r
- }\r
-\r
- static UINT GetNextHashTableSize(__in UINT DesiredSize)\r
- {\r
- // figure out the next logical size to use\r
- for (UINT i = 0; i < c_NumPrimes; ++ i)\r
- {\r
- if (c_PrimeSizes[i] >= DesiredSize)\r
- {\r
- return c_PrimeSizes[i];\r
- }\r
- }\r
-\r
- return DesiredSize;\r
- }\r
- \r
- // O(n) function\r
- // Grows to the next suitable size (based off of the prime number table)\r
- // DesiredSize is merely a suggestion\r
- HRESULT Grow(__in UINT DesiredSize,\r
- __in UINT ProvidedArraySize = 0,\r
- __in_ecount_opt(ProvidedArraySize)\r
- void** ProvidedArray = NULL,\r
- __in bool OwnProvidedArray = false)\r
- {\r
- HRESULT hr = S_OK;\r
- SHashEntry **rgpNewHashEntries = NULL;\r
- SHashEntry ***rgppListEnds = NULL;\r
- UINT valuesMigrated = 0;\r
- UINT actualSize;\r
-\r
- VB( DesiredSize > m_NumHashSlots );\r
-\r
- actualSize = GetNextHashTableSize(DesiredSize);\r
-\r
- if (ProvidedArray &&\r
- ProvidedArraySize >= actualSize)\r
- {\r
- rgpNewHashEntries = reinterpret_cast<SHashEntry**>(ProvidedArray);\r
- }\r
- else\r
- {\r
- OwnProvidedArray = true;\r
- \r
- VN( rgpNewHashEntries = NEW SHashEntry*[actualSize] );\r
- }\r
- \r
- ZeroMemory(rgpNewHashEntries, sizeof(SHashEntry*) * actualSize);\r
-\r
- // Expensive operation: rebuild the hash table\r
- CIterator iter, nextIter;\r
- GetFirstEntry(&iter);\r
- while (!PastEnd(&iter))\r
- {\r
- UINT index = iter.GetHash() % actualSize;\r
-\r
- // we need to advance to the next element\r
- // before we seize control of this element and move\r
- // it to the new table\r
- nextIter = iter;\r
- GetNextEntry(&nextIter);\r
-\r
- // seize this hash entry, migrate it to the new table\r
- iter.pHashEntry->pNext = rgpNewHashEntries[index];\r
- rgpNewHashEntries[index] = iter.pHashEntry;\r
-\r
- iter = nextIter;\r
- ++ valuesMigrated;\r
- }\r
-\r
- D3DXASSERT(valuesMigrated == m_NumEntries);\r
-\r
- CleanArray();\r
- m_rgpHashEntries = rgpNewHashEntries;\r
- m_NumHashSlots = actualSize;\r
- m_bOwnHashEntryArray = OwnProvidedArray;\r
-\r
-lExit:\r
- return hr;\r
- }\r
-\r
- HRESULT AutoGrow()\r
- {\r
- // arbitrary heuristic -- grow if 1:1\r
- if (m_NumEntries >= m_NumHashSlots)\r
- {\r
- // grows this hash table so that it is roughly 50% full\r
- return Grow(m_NumEntries * 2 + 1);\r
- }\r
- return S_OK;\r
- }\r
-\r
-#if _DEBUG\r
- void PrintHashTableStats()\r
- {\r
- if (m_NumHashSlots == 0)\r
- {\r
- DPF(0, "Uninitialized hash table!");\r
- return;\r
- }\r
- \r
- UINT i;\r
- float variance = 0.0f;\r
- float mean = (float)m_NumEntries / (float)m_NumHashSlots;\r
- UINT unusedSlots = 0;\r
-\r
- DPF(0, "Hash table slots: %d, Entries in table: %d", m_NumHashSlots, m_NumEntries);\r
-\r
- for (i = 0; i < m_NumHashSlots; ++ i)\r
- {\r
- UINT entries = 0;\r
- SHashEntry *pCurrentEntry = m_rgpHashEntries[i];\r
-\r
- while (NULL != pCurrentEntry)\r
- {\r
- SHashEntry *pCurrentEntry2 = m_rgpHashEntries[i];\r
- \r
- // check other hash entries in this slot for hash collisions or duplications\r
- while (pCurrentEntry2 != pCurrentEntry)\r
- {\r
- if (pCurrentEntry->Hash == pCurrentEntry2->Hash)\r
- {\r
- if (pfnIsEqual(pCurrentEntry->Data, pCurrentEntry2->Data))\r
- {\r
- D3DXASSERT(0);\r
- DPF(0, "Duplicate entry (identical hash, identical data) found!");\r
- }\r
- else\r
- {\r
- DPF(0, "Hash collision (hash: %d)", pCurrentEntry->Hash);\r
- }\r
- }\r
- pCurrentEntry2 = pCurrentEntry2->pNext;\r
- }\r
-\r
- pCurrentEntry = pCurrentEntry->pNext;\r
- ++ entries;\r
- }\r
-\r
- if (0 == entries)\r
- {\r
- ++ unusedSlots;\r
- }\r
- \r
- // mean must be greater than 0 at this point\r
- variance += (float)entries * (float)entries / mean;\r
- }\r
-\r
- variance /= max(1.0f, (m_NumHashSlots - 1));\r
- variance -= (mean * mean);\r
-\r
- DPF(0, "Mean number of entries per slot: %f, Standard deviation: %f, Unused slots; %d", mean, variance, unusedSlots);\r
- }\r
-#endif // _DEBUG\r
-\r
- // S_OK if element is found, E_FAIL otherwise\r
- HRESULT FindValueWithHash(T Data, UINT Hash, CIterator *pIterator)\r
- {\r
- D3DXASSERT(m_NumHashSlots > 0);\r
-\r
- UINT index = Hash % m_NumHashSlots;\r
- SHashEntry *pEntry = m_rgpHashEntries[index];\r
- while (NULL != pEntry)\r
- {\r
- if (Hash == pEntry->Hash && pfnIsEqual(pEntry->Data, Data))\r
- {\r
- pIterator->ppHashSlot = m_rgpHashEntries + index;\r
- pIterator->pHashEntry = pEntry;\r
- return S_OK;\r
- }\r
- pEntry = pEntry->pNext;\r
- }\r
- return E_FAIL;\r
- }\r
-\r
- // S_OK if element is found, E_FAIL otherwise\r
- HRESULT FindFirstMatchingValue(UINT Hash, CIterator *pIterator)\r
- {\r
- D3DXASSERT(m_NumHashSlots > 0);\r
-\r
- UINT index = Hash % m_NumHashSlots;\r
- SHashEntry *pEntry = m_rgpHashEntries[index];\r
- while (NULL != pEntry)\r
- {\r
- if (Hash == pEntry->Hash)\r
- {\r
- pIterator->ppHashSlot = m_rgpHashEntries + index;\r
- pIterator->pHashEntry = pEntry;\r
- return S_OK;\r
- }\r
- pEntry = pEntry->pNext;\r
- }\r
- return E_FAIL;\r
- }\r
-\r
- // Adds data at the specified hash slot without checking for existence\r
- HRESULT AddValueWithHash(T Data, UINT Hash)\r
- {\r
- HRESULT hr = S_OK;\r
-\r
- D3DXASSERT(m_NumHashSlots > 0);\r
-\r
- SHashEntry *pHashEntry;\r
- UINT index = Hash % m_NumHashSlots;\r
-\r
- VN( pHashEntry = NEW SHashEntry );\r
- pHashEntry->pNext = m_rgpHashEntries[index];\r
- pHashEntry->Data = Data;\r
- pHashEntry->Hash = Hash;\r
- m_rgpHashEntries[index] = pHashEntry;\r
-\r
- ++ m_NumEntries;\r
-\r
-lExit:\r
- return hr;\r
- }\r
-\r
- // Iterator code:\r
- //\r
- // CMyHashTable::CIterator myIt;\r
- // for (myTable.GetFirstEntry(&myIt); !myTable.PastEnd(&myIt); myTable.GetNextEntry(&myIt)\r
- // { myTable.GetData(&myIt); }\r
- void GetFirstEntry(CIterator *pIterator)\r
- {\r
- SHashEntry **ppEnd = m_rgpHashEntries + m_NumHashSlots;\r
- pIterator->ppHashSlot = m_rgpHashEntries;\r
- while (pIterator->ppHashSlot < ppEnd)\r
- {\r
- if (NULL != *(pIterator->ppHashSlot))\r
- {\r
- pIterator->pHashEntry = *(pIterator->ppHashSlot);\r
- return;\r
- }\r
- ++ pIterator->ppHashSlot;\r
- }\r
- }\r
-\r
- BOOL PastEnd(CIterator *pIterator)\r
- {\r
- SHashEntry **ppEnd = m_rgpHashEntries + m_NumHashSlots;\r
- D3DXASSERT(pIterator->ppHashSlot >= m_rgpHashEntries && pIterator->ppHashSlot <= ppEnd);\r
- return (pIterator->ppHashSlot == ppEnd);\r
- }\r
-\r
- void GetNextEntry(CIterator *pIterator)\r
- {\r
- SHashEntry **ppEnd = m_rgpHashEntries + m_NumHashSlots;\r
- D3DXASSERT(pIterator->ppHashSlot >= m_rgpHashEntries && pIterator->ppHashSlot <= ppEnd);\r
- D3DXASSERT(NULL != pIterator->pHashEntry);\r
-\r
- pIterator->pHashEntry = pIterator->pHashEntry->pNext;\r
- if (NULL != pIterator->pHashEntry)\r
- {\r
- return;\r
- }\r
-\r
- ++ pIterator->ppHashSlot;\r
- while (pIterator->ppHashSlot < ppEnd)\r
- {\r
- pIterator->pHashEntry = *(pIterator->ppHashSlot);\r
- if (NULL != pIterator->pHashEntry)\r
- {\r
- return;\r
- }\r
- ++ pIterator->ppHashSlot;\r
- }\r
- // hit the end of the list, ppHashSlot == ppEnd\r
- }\r
-\r
- void RemoveEntry(CIterator *pIterator)\r
- {\r
- SHashEntry *pTemp;\r
- SHashEntry **ppPrev;\r
- SHashEntry **ppEnd = m_rgpHashEntries + m_NumHashSlots;\r
-\r
- D3DXASSERT(pIterator && !PastEnd(pIterator));\r
- ppPrev = pIterator->ppHashSlot;\r
- pTemp = *ppPrev;\r
- while (pTemp)\r
- {\r
- if (pTemp == pIterator->pHashEntry)\r
- {\r
- *ppPrev = pTemp->pNext;\r
- pIterator->ppHashSlot = ppEnd;\r
- delete pTemp;\r
- return;\r
- }\r
- ppPrev = &pTemp->pNext;\r
- pTemp = pTemp->pNext;\r
- }\r
-\r
- // Should never get here\r
- D3DXASSERT(0);\r
- }\r
-\r
-};\r
-\r
-// Allocates the hash slots on the regular heap (since the\r
-// hash table can grow), but all hash entries are allocated on\r
-// a private heap\r
-\r
-template<typename T, BOOL (*pfnIsEqual)(const T &Data1, const T &Data2)>\r
-class CEffectHashTableWithPrivateHeap : public CEffectHashTable<T, pfnIsEqual>\r
-{\r
-protected:\r
- CDataBlockStore *m_pPrivateHeap;\r
-\r
-public:\r
- CEffectHashTableWithPrivateHeap()\r
- {\r
- m_pPrivateHeap = NULL;\r
- }\r
-\r
- void Cleanup()\r
- {\r
- CleanArray();\r
- m_NumHashSlots = 0;\r
- m_NumEntries = 0;\r
- }\r
-\r
- ~CEffectHashTableWithPrivateHeap()\r
- {\r
- Cleanup();\r
- }\r
-\r
- // Call this only once\r
- void SetPrivateHeap(CDataBlockStore *pPrivateHeap)\r
- {\r
- D3DXASSERT(NULL == m_pPrivateHeap);\r
- m_pPrivateHeap = pPrivateHeap;\r
- }\r
-\r
- // Adds data at the specified hash slot without checking for existence\r
- HRESULT AddValueWithHash(T Data, UINT Hash)\r
- {\r
- HRESULT hr = S_OK;\r
-\r
- D3DXASSERT(NULL != m_pPrivateHeap);\r
- D3DXASSERT(m_NumHashSlots > 0);\r
-\r
- SHashEntry *pHashEntry;\r
- UINT index = Hash % m_NumHashSlots;\r
-\r
- VN( pHashEntry = new(*m_pPrivateHeap) SHashEntry );\r
- pHashEntry->pNext = m_rgpHashEntries[index];\r
- pHashEntry->Data = Data;\r
- pHashEntry->Hash = Hash;\r
- m_rgpHashEntries[index] = pHashEntry;\r
-\r
- ++ m_NumEntries;\r
-\r
-lExit:\r
- return hr;\r
- }\r
-};\r
OSDN Git Service
