Cache the index ranges at the gl::Buffer and rx::IndexBuffer levels so that ranges do not need to be re-calculated for direct buffers.

Issue #451

Signed-off-by: Jamie Madill
Signed-off-by: Shannon Woods
Author: Geoff Lang

12 files changed, 228 insertions, 73 deletions

diff --git a/src/build_angle.gypi b/src/build_angle.gypi
index 405c6710..c91cce1b 100644
--- a/src/build_angle.gypi
+++ b/src/build_angle.gypi
@@ -293,6 +293,8 @@
             'libGLESv2/renderer/IndexBuffer11.h',
             'libGLESv2/renderer/IndexDataManager.cpp',
             'libGLESv2/renderer/IndexDataManager.h',
+            'libGLESv2/renderer/IndexRangeCache.cpp',
+            'libGLESv2/renderer/IndexRangeCache.h',
             'libGLESv2/renderer/InputLayoutCache.cpp',
             'libGLESv2/renderer/InputLayoutCache.h',
             'libGLESv2/renderer/QueryImpl.h',
diff --git a/src/libGLESv2/Buffer.cpp b/src/libGLESv2/Buffer.cpp
index 8d5b4ef2..a64fbad4 100644
--- a/src/libGLESv2/Buffer.cpp
+++ b/src/libGLESv2/Buffer.cpp
@@ -40,6 +40,7 @@ Buffer::~Buffer()
 void Buffer::bufferData(const void *data, GLsizeiptr size, GLenum usage)
 {
     mBufferStorage->clear();
+    mIndexRangeCache.clear();
     mBufferStorage->setData(data, size, 0);
 
     mUsage = usage;
@@ -56,6 +57,7 @@ void Buffer::bufferData(const void *data, GLsizeiptr size, GLenum usage)
 void Buffer::bufferSubData(const void *data, GLsizeiptr size, GLintptr offset)
 {
     mBufferStorage->setData(data, size, offset);
+    mIndexRangeCache.invalidateRange(offset, size);
 
     if ((mStaticVertexBuffer && mStaticVertexBuffer->getBufferSize() != 0) || (mStaticIndexBuffer && mStaticIndexBuffer->getBufferSize() != 0))
     {
@@ -116,4 +118,9 @@ void Buffer::promoteStaticUsage(int dataSize)
     }
 }
 
+rx::IndexRangeCache *Buffer::getIndexRangeCache()
+{
+    return &mIndexRangeCache;
+}
+
 }
diff --git a/src/libGLESv2/Buffer.h b/src/libGLESv2/Buffer.h
index 4376ada5..3f9fe8f8 100644
--- a/src/libGLESv2/Buffer.h
+++ b/src/libGLESv2/Buffer.h
@@ -13,6 +13,7 @@
 
 #include "common/angleutils.h"
 #include "common/RefCountObject.h"
+#include "libGLESv2/renderer/IndexRangeCache.h"
 
 namespace rx
 {
@@ -45,6 +46,8 @@ class Buffer : public RefCountObject
     void invalidateStaticData();
     void promoteStaticUsage(int dataSize);
 
+    rx::IndexRangeCache *getIndexRangeCache();
+
   private:
     DISALLOW_COPY_AND_ASSIGN(Buffer);
 
@@ -53,6 +56,8 @@ class Buffer : public RefCountObject
 
     rx::BufferStorage *mBufferStorage;
 
+    rx::IndexRangeCache mIndexRangeCache;
+
     rx::StaticVertexBufferInterface *mStaticVertexBuffer;
     rx::StaticIndexBufferInterface *mStaticIndexBuffer;
     unsigned int mUnmodifiedDataUse;
diff --git a/src/libGLESv2/libGLESv2.vcxproj b/src/libGLESv2/libGLESv2.vcxproj
index ca0d6b57..906707c9 100644
--- a/src/libGLESv2/libGLESv2.vcxproj
+++ b/src/libGLESv2/libGLESv2.vcxproj
@@ -273,6 +273,7 @@ copy "$(OutDir)libGLESv2.lib" "$(ProjectDir)..\..\lib\$(Configuration)\"
     <ClCompile Include="renderer\IndexDataManager.cpp" />

     <ClCompile Include="renderer\ImageSSE2.cpp" />

     <ClCompile Include="renderer\Image11.cpp" />

+    <ClCompile Include="renderer\IndexRangeCache.cpp" />

     <ClCompile Include="renderer\InputLayoutCache.cpp" />

     <ClCompile Include="renderer\Query11.cpp" />

     <ClCompile Include="renderer\Query9.cpp" />

@@ -340,6 +341,7 @@ copy "$(OutDir)libGLESv2.lib" "$(ProjectDir)..\..\lib\$(Configuration)\"
     <ClInclude Include="renderer\IndexBuffer11.h" />

     <ClInclude Include="renderer\IndexBuffer9.h" />

     <ClInclude Include="renderer\IndexDataManager.h" />

+    <ClInclude Include="renderer\IndexRangeCache.h" />

     <ClInclude Include="renderer\InputLayoutCache.h" />

     <ClInclude Include="renderer\Query11.h" />

     <ClInclude Include="renderer\QueryImpl.h" />

diff --git a/src/libGLESv2/libGLESv2.vcxproj.filters b/src/libGLESv2/libGLESv2.vcxproj.filters
index 34f97044..187a46a9 100644
--- a/src/libGLESv2/libGLESv2.vcxproj.filters
+++ b/src/libGLESv2/libGLESv2.vcxproj.filters
@@ -218,6 +218,9 @@
     <ClCompile Include="precompiled.cpp">

       <Filter>Source Files</Filter>

     </ClCompile>

+    <ClCompile Include="renderer\IndexRangeCache.cpp">

+      <Filter>Source Files\Renderer</Filter>

+    </ClCompile>

   </ItemGroup>

   <ItemGroup>

     <ClInclude Include="BinaryStream.h">

@@ -484,6 +487,9 @@
     <ClInclude Include="precompiled.h">

       <Filter>Header Files</Filter>

     </ClInclude>

+    <ClInclude Include="renderer\IndexRangeCache.h">

+      <Filter>Header Files\Renderer</Filter>

+    </ClInclude>

   </ItemGroup>

   <ItemGroup>

     <None Include="renderer\shaders\Blit.ps">

diff --git a/src/libGLESv2/renderer/IndexBuffer.cpp b/src/libGLESv2/renderer/IndexBuffer.cpp
index 3d5d7a7c..2ac94466 100644
--- a/src/libGLESv2/renderer/IndexBuffer.cpp
+++ b/src/libGLESv2/renderer/IndexBuffer.cpp
@@ -176,27 +176,9 @@ bool StaticIndexBufferInterface::reserveBufferSpace(unsigned int size, GLenum in
     }
 }
 
-unsigned int StaticIndexBufferInterface::lookupRange(intptr_t offset, GLsizei count, unsigned int *minIndex, unsigned int *maxIndex)
+IndexRangeCache *StaticIndexBufferInterface::getIndexRangeCache()
 {
-    IndexRange range = {offset, count};
-
-    std::map<IndexRange, IndexResult>::iterator res = mCache.find(range);
-
-    if (res == mCache.end())
-    {
-        return -1;
-    }
-
-    *minIndex = res->second.minIndex;
-    *maxIndex = res->second.maxIndex;
-    return res->second.streamOffset;
-}
-
-void StaticIndexBufferInterface::addRange(intptr_t offset, GLsizei count, unsigned int minIndex, unsigned int maxIndex, unsigned int streamOffset)
-{
-    IndexRange indexRange = {offset, count};
-    IndexResult indexResult = {minIndex, maxIndex, streamOffset};
-    mCache[indexRange] = indexResult;
+    return &mIndexRangeCache;
 }
 
 }
diff --git a/src/libGLESv2/renderer/IndexBuffer.h b/src/libGLESv2/renderer/IndexBuffer.h
index 1afbd626..98fa5fe3 100644
--- a/src/libGLESv2/renderer/IndexBuffer.h
+++ b/src/libGLESv2/renderer/IndexBuffer.h
@@ -11,6 +11,7 @@
 #define LIBGLESV2_RENDERER_INDEXBUFFER_H_
 
 #include "common/angleutils.h"
+#include "libGLESv2/renderer/IndexRangeCache.h"
 
 namespace rx
 {
@@ -99,37 +100,10 @@ class StaticIndexBufferInterface : public IndexBufferInterface
 
     virtual bool reserveBufferSpace(unsigned int size, GLenum indexType);
 
-    unsigned int lookupRange(intptr_t offset, GLsizei count, unsigned int *minIndex, unsigned int *maxIndex);   // Returns the offset into the index buffer, or -1 if not found
-    void addRange(intptr_t offset, GLsizei count, unsigned int minIndex, unsigned int maxIndex, unsigned int streamOffset);
+    IndexRangeCache *getIndexRangeCache();
 
   private:
-    struct IndexRange
-    {
-        intptr_t offset;
-        GLsizei count;
-
-        bool operator<(const IndexRange& rhs) const
-        {
-            if (offset != rhs.offset)
-            {
-                return offset < rhs.offset;
-            }
-            if (count != rhs.count)
-            {
-                return count < rhs.count;
-            }
-            return false;
-        }
-    };
-
-    struct IndexResult
-    {
-        unsigned int minIndex;
-        unsigned int maxIndex;
-        unsigned int streamOffset;
-    };
-
-    std::map<IndexRange, IndexResult> mCache;
+    IndexRangeCache mIndexRangeCache;
 };
 
 }
diff --git a/src/libGLESv2/renderer/IndexDataManager.cpp b/src/libGLESv2/renderer/IndexDataManager.cpp
index 84b79b41..752d1fb4 100644
--- a/src/libGLESv2/renderer/IndexDataManager.cpp
+++ b/src/libGLESv2/renderer/IndexDataManager.cpp
@@ -13,6 +13,7 @@
 
 #include "libGLESv2/Buffer.h"
 #include "libGLESv2/main.h"
+#include "libGLESv2/utilities.h"
 #include "libGLESv2/renderer/IndexBuffer.h"
 
 namespace rx
@@ -53,17 +54,6 @@ IndexDataManager::~IndexDataManager()
     delete mCountingBuffer;
 }
 
-static unsigned int indexTypeSize(GLenum type)
-{
-    switch (type)
-    {
-      case GL_UNSIGNED_INT:   return sizeof(GLuint);
-      case GL_UNSIGNED_SHORT: return sizeof(GLushort);
-      case GL_UNSIGNED_BYTE:  return sizeof(GLubyte);
-      default: UNREACHABLE(); return sizeof(GLushort);
-    }
-}
-
 static void convertIndices(GLenum type, const void *input, GLsizei count, void *output)
 {
     if (type == GL_UNSIGNED_BYTE)
@@ -142,7 +132,7 @@ GLenum IndexDataManager::prepareIndexData(GLenum type, GLsizei count, gl::Buffer
           default: UNREACHABLE(); alignedOffset = false;
         }
 
-        if (indexTypeSize(type) * count + offset > storage->getSize())
+        if (gl::ComputeTypeSize(type) * count + offset > static_cast<GLsizei>(storage->getSize()))
         {
             return GL_INVALID_OPERATION;
         }
@@ -163,18 +153,25 @@ GLenum IndexDataManager::prepareIndexData(GLenum type, GLsizei count, gl::Buffer
         indexBuffer = streamingBuffer;
         streamOffset = offset;
         storage->markBufferUsage();
-        computeRange(type, indices, count, &translated->minIndex, &translated->maxIndex);
+
+        if (!buffer->getIndexRangeCache()->findRange(type, offset, count, &translated->minIndex,
+                                                     &translated->maxIndex, NULL))
+        {
+            computeRange(type, indices, count, &translated->minIndex, &translated->maxIndex);
+            buffer->getIndexRangeCache()->addRange(type, offset, count, translated->minIndex,
+                                                   translated->maxIndex, offset);
+        }
     }
     else if (staticBuffer && staticBuffer->getBufferSize() != 0 && staticBuffer->getIndexType() == type && alignedOffset)
     {
         indexBuffer = staticBuffer;
-        streamOffset = staticBuffer->lookupRange(offset, count, &translated->minIndex, &translated->maxIndex);
-
-        if (streamOffset == -1)
+        if (!staticBuffer->getIndexRangeCache()->findRange(type, offset, count, &translated->minIndex,
+                                                           &translated->maxIndex, &streamOffset))
         {
-            streamOffset = (offset / indexTypeSize(type)) * indexTypeSize(destinationIndexType);
+            streamOffset = (offset / gl::ComputeTypeSize(type)) * gl::ComputeTypeSize(destinationIndexType);
             computeRange(type, indices, count, &translated->minIndex, &translated->maxIndex);
-            staticBuffer->addRange(offset, count, translated->minIndex, translated->maxIndex, streamOffset);
+            staticBuffer->getIndexRangeCache()->addRange(type, offset, count, translated->minIndex,
+                                                         translated->maxIndex, streamOffset);
         }
     }
     else
@@ -186,7 +183,7 @@ GLenum IndexDataManager::prepareIndexData(GLenum type, GLsizei count, gl::Buffer
             if (staticBuffer->getBufferSize() == 0 && alignedOffset)
             {
                 indexBuffer = staticBuffer;
-                convertCount = storage->getSize() / indexTypeSize(type);
+                convertCount = storage->getSize() / gl::ComputeTypeSize(type);
             }
             else
             {
@@ -201,7 +198,7 @@ GLenum IndexDataManager::prepareIndexData(GLenum type, GLsizei count, gl::Buffer
             return GL_INVALID_OPERATION;
         }
 
-        unsigned int bufferSizeRequired = convertCount * indexTypeSize(destinationIndexType);
+        unsigned int bufferSizeRequired = convertCount * gl::ComputeTypeSize(destinationIndexType);
         indexBuffer->reserveBufferSpace(bufferSizeRequired, type);
 
         void* output = NULL;
@@ -224,20 +221,21 @@ GLenum IndexDataManager::prepareIndexData(GLenum type, GLsizei count, gl::Buffer
 
         if (staticBuffer)
         {
-            streamOffset = (offset / indexTypeSize(type)) * indexTypeSize(destinationIndexType);
-            staticBuffer->addRange(offset, count, translated->minIndex, translated->maxIndex, streamOffset);
+            streamOffset = (offset / gl::ComputeTypeSize(type)) * gl::ComputeTypeSize(destinationIndexType);
+            staticBuffer->getIndexRangeCache()->addRange(type, offset, count, translated->minIndex,
+                                                         translated->maxIndex, streamOffset);
         }
     }
 
     translated->storage = directStorage ? storage : NULL;
     translated->indexBuffer = indexBuffer->getIndexBuffer();
     translated->serial = directStorage ? storage->getSerial() : indexBuffer->getSerial();
-    translated->startIndex = streamOffset / indexTypeSize(destinationIndexType);
+    translated->startIndex = streamOffset / gl::ComputeTypeSize(destinationIndexType);
     translated->startOffset = streamOffset;
 
     if (buffer)
     {
-        buffer->promoteStaticUsage(count * indexTypeSize(type));
+        buffer->promoteStaticUsage(count * gl::ComputeTypeSize(type));
     }
 
     return GL_NO_ERROR;
diff --git a/src/libGLESv2/renderer/IndexRangeCache.cpp b/src/libGLESv2/renderer/IndexRangeCache.cpp
new file mode 100644
index 00000000..7630934a
--- /dev/null
+++ b/src/libGLESv2/renderer/IndexRangeCache.cpp
@@ -0,0 +1,97 @@
+#include "precompiled.h"
+//
+// Copyright (c) 2013 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+
+// IndexRangeCache.cpp: Defines the rx::IndexRangeCache class which stores information about
+// ranges of indices.
+
+#include "libGLESv2/renderer/IndexRangeCache.h"
+#include "common/debug.h"
+#include "libGLESv2/utilities.h"
+#include <tuple>
+
+namespace rx
+{
+
+void IndexRangeCache::addRange(GLenum type, intptr_t offset, GLsizei count, unsigned int minIdx, unsigned int maxIdx, 
+                               unsigned int streamOffset)
+{
+    mIndexRangeCache[IndexRange(type, offset, count)] = IndexBounds(minIdx, maxIdx, streamOffset);
+}
+
+void IndexRangeCache::invalidateRange(unsigned int offset, unsigned int size)
+{
+    unsigned int invalidateStart = offset;
+    unsigned int invalidateEnd = offset + size;
+
+    IndexRangeMap::iterator i = mIndexRangeCache.begin();
+    while (i != mIndexRangeCache.end())
+    {
+        unsigned int rangeStart = i->second.streamOffset;
+        unsigned int rangeEnd = i->second.streamOffset + (gl::ComputeTypeSize(i->first.type) * i->first.count);
+
+        if (invalidateEnd < rangeStart || invalidateStart > rangeEnd)
+        {
+            ++i;
+        }
+        else
+        {
+            i = mIndexRangeCache.erase(i);
+        }
+    }
+}
+
+bool IndexRangeCache::findRange(GLenum type, intptr_t offset, GLsizei count, unsigned int *outMinIndex,
+                                unsigned int *outMaxIndex, unsigned int *outStreamOffset) const
+{
+    IndexRangeMap::const_iterator i = mIndexRangeCache.find(IndexRange(type, offset, count));
+    if (i != mIndexRangeCache.end())
+    {
+        if (outMinIndex)     *outMinIndex = i->second.minIndex;
+        if (outMaxIndex)     *outMaxIndex = i->second.maxIndex;
+        if (outStreamOffset) *outStreamOffset = i->second.streamOffset;
+        return true;
+    }
+    else
+    {
+        if (outMinIndex)     *outMinIndex = 0;
+        if (outMaxIndex)     *outMaxIndex = 0;
+        if (outStreamOffset) *outStreamOffset = 0;
+        return false;
+    }
+}
+
+void IndexRangeCache::clear()
+{
+    mIndexRangeCache.clear();
+}
+
+IndexRangeCache::IndexRange::IndexRange()
+    : type(GL_NONE), offset(0), count(0)
+{
+}
+
+IndexRangeCache::IndexRange::IndexRange(GLenum typ, intptr_t off, GLsizei c)
+    : type(typ), offset(off), count(c)
+{
+}
+
+bool IndexRangeCache::IndexRange::operator<(const IndexRange& rhs) const
+{
+    return std::make_tuple(type, offset, count) < std::make_tuple(rhs.type, rhs.offset, rhs.count);
+}
+
+IndexRangeCache::IndexBounds::IndexBounds()
+    : minIndex(0), maxIndex(0), streamOffset(0)
+{
+}
+
+IndexRangeCache::IndexBounds::IndexBounds(unsigned int minIdx, unsigned int maxIdx, unsigned int offset)
+    : minIndex(minIdx), maxIndex(maxIdx), streamOffset(offset)
+{
+}
+
+}
diff --git a/src/libGLESv2/renderer/IndexRangeCache.h b/src/libGLESv2/renderer/IndexRangeCache.h
new file mode 100644
index 00000000..5a5ade10
--- /dev/null
+++ b/src/libGLESv2/renderer/IndexRangeCache.h
@@ -0,0 +1,58 @@
+//
+// Copyright (c) 2013 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+
+// IndexRangeCache.h: Defines the rx::IndexRangeCache class which stores information about
+// ranges of indices.
+
+#ifndef LIBGLESV2_RENDERER_INDEXRANGECACHE_H_
+#define LIBGLESV2_RENDERER_INDEXRANGECACHE_H_
+
+#include "common/angleutils.h"
+
+namespace rx
+{
+
+class IndexRangeCache
+{
+  public:
+    void addRange(GLenum type, intptr_t offset, GLsizei count, unsigned int minIdx, unsigned int maxIdx, 
+                  unsigned int streamOffset);
+    bool findRange(GLenum type, intptr_t offset, GLsizei count, unsigned int *outMinIndex,
+                   unsigned int *outMaxIndex, unsigned int *outStreamOffset) const;
+
+    void invalidateRange(unsigned int offset, unsigned int size);
+    void clear();
+
+  private:
+    struct IndexRange
+    {
+        GLenum type;
+        intptr_t offset;
+        GLsizei count;
+
+        IndexRange();
+        IndexRange(GLenum type, intptr_t offset, GLsizei count);
+
+        bool operator<(const IndexRange& rhs) const;
+    };
+
+    struct IndexBounds
+    {
+        unsigned int minIndex;
+        unsigned int maxIndex;
+        unsigned int streamOffset;
+
+        IndexBounds();
+        IndexBounds(unsigned int minIdx, unsigned int maxIdx, unsigned int offset);
+    };
+
+    typedef std::map<IndexRange, IndexBounds> IndexRangeMap;
+    IndexRangeMap mIndexRangeCache;
+};
+
+}
+
+#endif LIBGLESV2_RENDERER_INDEXRANGECACHE_H
diff --git a/src/libGLESv2/utilities.cpp b/src/libGLESv2/utilities.cpp
index 9809b9d8..32df49e6 100644
--- a/src/libGLESv2/utilities.cpp
+++ b/src/libGLESv2/utilities.cpp
@@ -218,6 +218,29 @@ GLsizei ComputeCompressedSize(GLsizei width, GLsizei height, GLenum internalform
     }
 }
 
+GLsizei ComputeTypeSize(GLenum type)
+{
+    switch (type)
+    {
+      case GL_BYTE:                            return 1;
+      case GL_UNSIGNED_BYTE:                   return 1;
+      case GL_SHORT:                           return 2;
+      case GL_UNSIGNED_SHORT:                  return 2;
+      case GL_INT:                             return 4;
+      case GL_UNSIGNED_INT:                    return 4;
+      case GL_FLOAT:                           return 4;
+      case GL_HALF_FLOAT_OES:                  return 2;
+      case GL_UNSIGNED_SHORT_5_6_5:            return 2;
+      case GL_UNSIGNED_SHORT_4_4_4_4:          return 2;
+      case GL_UNSIGNED_SHORT_5_5_5_1:          return 2;
+      case GL_UNSIGNED_SHORT_4_4_4_4_REV_EXT:  return 2;
+      case GL_UNSIGNED_SHORT_1_5_5_5_REV_EXT:  return 2;
+      case GL_UNSIGNED_INT_2_10_10_10_REV_EXT: return 4;
+      case GL_UNSIGNED_INT_24_8_OES:           return 4;
+      default: UNREACHABLE();                  return 0;
+    }
+}
+
 bool IsCompressed(GLenum format)
 {
     if(format == GL_COMPRESSED_RGB_S3TC_DXT1_EXT ||
diff --git a/src/libGLESv2/utilities.h b/src/libGLESv2/utilities.h
index 7a107670..ed663ebc 100644
--- a/src/libGLESv2/utilities.h
+++ b/src/libGLESv2/utilities.h
@@ -34,6 +34,7 @@ int ComputePixelSize(GLint internalformat);
 GLsizei ComputePitch(GLsizei width, GLint internalformat, GLint alignment);
 GLsizei ComputeCompressedPitch(GLsizei width, GLenum format);
 GLsizei ComputeCompressedSize(GLsizei width, GLsizei height, GLenum format);
+GLsizei ComputeTypeSize(GLenum type);
 bool IsCompressed(GLenum format);
 bool IsDepthTexture(GLenum format);
 bool IsStencilTexture(GLenum format);