draw: fix overflows in the indexed rendering paths

The semantics for overflow detection are a bit tricky with
indexed rendering. If the base index in the elements array
overflows, then the index of the first element should be used,
if the index with bias overflows then it should be treated
like a normal overflow. Also overflows need to be checked for
in all paths that either the bias, or the starting index location.

Signed-off-by: Zack Rusin <[email protected]>
Reviewed-by: Brian Paul <[email protected]>
Reviewed-by: Roland Scheidegger <[email protected]>

4 files changed, 159 insertions, 43 deletions

diff --git a/src/gallium/auxiliary/draw/draw_private.h b/src/gallium/auxiliary/draw/draw_private.h
index f42cded118a..d8cd8ebdb64 100644
--- a/src/gallium/auxiliary/draw/draw_private.h
+++ b/src/gallium/auxiliary/draw/draw_private.h
@@ -55,6 +55,10 @@ struct gallivm_state;
 /** Sum of frustum planes and user-defined planes */
 #define DRAW_TOTAL_CLIP_PLANES (6 + PIPE_MAX_CLIP_PLANES)
 
+/**
+ * The largest possible index of a vertex that can be fetched.
+ */
+#define DRAW_MAX_FETCH_IDX 0xffffffff
 
 struct pipe_context;
 struct draw_vertex_shader;
@@ -468,14 +472,13 @@ void
 draw_stats_clipper_primitives(struct draw_context *draw,
                               const struct draw_prim_info *prim_info);
 
-
 /** 
  * Return index i from the index buffer.
  * If the index buffer would overflow we return the
- * index of the first element in the vb.
+ * maximum possible index.
  */
 #define DRAW_GET_IDX(_elts, _i)                   \
-   (((_i) >= draw->pt.user.eltMax) ? 0 : (_elts)[_i])
+   (((_i) >= draw->pt.user.eltMax) ? DRAW_MAX_FETCH_IDX : (_elts)[_i])
 
 /**
  * Return index of the given viewport clamping it
@@ -487,5 +490,20 @@ draw_clamp_viewport_idx(int idx)
    return ((PIPE_MAX_VIEWPORTS > idx || idx < 0) ? idx : 0);
 }
 
+/**
+ * Adds two unsigned integers and if the addition
+ * overflows then it returns the value from
+ * from the overflow_value variable.
+ */
+static INLINE unsigned
+draw_overflow_uadd(unsigned a, unsigned b,
+                   unsigned overflow_value)
+{
+   unsigned res = a + b;
+   if (res < a || res < b) {
+      res = overflow_value;
+   }
+   return res;
+}
 
 #endif /* DRAW_PRIVATE_H */
diff --git a/src/gallium/auxiliary/draw/draw_pt.c b/src/gallium/auxiliary/draw/draw_pt.c
index e89ccd25401..d2fe0025bfc 100644
--- a/src/gallium/auxiliary/draw/draw_pt.c
+++ b/src/gallium/auxiliary/draw/draw_pt.c
@@ -345,7 +345,8 @@ draw_print_arrays(struct draw_context *draw, uint prim, int start, uint count)
 /** Helper code for below */
 #define PRIM_RESTART_LOOP(elements) \
    do { \
-      for (i = start; i < end; i++) { \
+      for (j = 0; j < count; j++) {               \
+         i = draw_overflow_uadd(start, j, MAX_LOOP_IDX);  \
          if (i < elt_max && elements[i] == info->restart_index) { \
             if (cur_count > 0) { \
                /* draw elts up to prev pos */ \
@@ -377,9 +378,11 @@ draw_pt_arrays_restart(struct draw_context *draw,
    const unsigned prim = info->mode;
    const unsigned start = info->start;
    const unsigned count = info->count;
-   const unsigned end = start + count;
    const unsigned elt_max = draw->pt.user.eltMax;
-   unsigned i, cur_start, cur_count;
+   unsigned i, j, cur_start, cur_count;
+   /* The largest index within a loop using the i variable as the index.
+    * Used for overflow detection */
+   const unsigned MAX_LOOP_IDX = 0xffffffff;
 
    assert(info->primitive_restart);
 
diff --git a/src/gallium/auxiliary/draw/draw_pt_vsplit.c b/src/gallium/auxiliary/draw/draw_pt_vsplit.c
index 114c89c1e9c..625505d1efd 100644
--- a/src/gallium/auxiliary/draw/draw_pt_vsplit.c
+++ b/src/gallium/auxiliary/draw/draw_pt_vsplit.c
@@ -33,6 +33,9 @@
 #define SEGMENT_SIZE 1024
 #define MAP_SIZE     256
 
+/* The largest possible index withing an index buffer */
+#define MAX_ELT_IDX 0xffffffff
+
 struct vsplit_frontend {
    struct draw_pt_front_end base;
    struct draw_context *draw;
@@ -82,16 +85,15 @@ vsplit_flush_cache(struct vsplit_frontend *vsplit, unsigned flags)
  * Add a fetch element and add it to the draw elements.
  */
 static INLINE void
-vsplit_add_cache(struct vsplit_frontend *vsplit, unsigned fetch)
+vsplit_add_cache(struct vsplit_frontend *vsplit, unsigned fetch, unsigned ofbias)
 {
-   struct draw_context *draw = vsplit->draw;
    unsigned hash;
 
-   fetch = MIN2(fetch, draw->pt.max_index);
-
    hash = fetch % MAP_SIZE;
 
-   if (vsplit->cache.fetches[hash] != fetch) {
+   /* If the value isn't in the cache of it's an overflow due to the
+    * element bias */
+   if (vsplit->cache.fetches[hash] != fetch || ofbias) {
       /* update cache */
       vsplit->cache.fetches[hash] = fetch;
       vsplit->cache.draws[hash] = vsplit->cache.num_fetch_elts;
@@ -104,22 +106,109 @@ vsplit_add_cache(struct vsplit_frontend *vsplit, unsigned fetch)
    vsplit->draw_elts[vsplit->cache.num_draw_elts++] = vsplit->cache.draws[hash];
 }
 
+/**
+ * Returns the base index to the elements array.
+ * The value is checked for overflows (both integer overflows
+ * and the elements array overflow).
+ */
+static INLINE unsigned
+vsplit_get_base_idx(struct vsplit_frontend *vsplit,
+                    unsigned start, unsigned fetch, unsigned *ofbit)
+{
+   struct draw_context *draw = vsplit->draw;
+   unsigned elt_idx = draw_overflow_uadd(start, fetch, MAX_ELT_IDX);
+   if (ofbit)
+      *ofbit = 0;
+
+   /* Overflown indices need to wrap to the first element
+    * in the index buffer */
+   if (elt_idx >= draw->pt.user.eltMax) {
+      if (ofbit)
+         *ofbit = 1;
+      elt_idx = 0;
+   }
+
+   return elt_idx;
+}
+
+/**
+ * Returns the element index adjust for the element bias.
+ * The final element index is created from the actual element
+ * index, plus the element bias, clamped to maximum elememt
+ * index if that addition overflows.
+ */
+static INLINE unsigned
+vsplit_get_bias_idx(struct vsplit_frontend *vsplit,
+                    int idx, int bias, unsigned *ofbias)
+{
+   int res = idx + bias;
+
+   if (ofbias)
+      *ofbias = 0;
+
+   if (idx > 0 && bias > 0) {
+      if (res < idx || res < bias) {
+         res = DRAW_MAX_FETCH_IDX;
+         if (ofbias)
+            *ofbias = 1;
+      }
+   } else if (idx < 0 && bias < 0) {
+      if (res > idx || res > bias) {
+         res = DRAW_MAX_FETCH_IDX;
+         if (ofbias)
+            *ofbias = 1;
+      }
+   }
+
+   return res;
+}
+
+#define VSPLIT_CREATE_IDX(elts, start, fetch, elt_bias)    \
+   unsigned elt_idx;                                       \
+   unsigned ofbit;                                         \
+   unsigned ofbias;                                        \
+   elt_idx = vsplit_get_base_idx(vsplit, start, fetch, &ofbit);          \
+   elt_idx = vsplit_get_bias_idx(vsplit, ofbit ? 0 : DRAW_GET_IDX(elts, elt_idx), elt_bias, &ofbias)
+
+static INLINE void
+vsplit_add_cache_ubyte(struct vsplit_frontend *vsplit, const ubyte *elts,
+                       unsigned start, unsigned fetch, int elt_bias)
+{
+   struct draw_context *draw = vsplit->draw;
+   VSPLIT_CREATE_IDX(elts, start, fetch, elt_bias);
+   vsplit_add_cache(vsplit, elt_idx, ofbias);
+}
+
+static INLINE void
+vsplit_add_cache_ushort(struct vsplit_frontend *vsplit, const ushort *elts,
+                       unsigned start, unsigned fetch, int elt_bias)
+{
+   struct draw_context *draw = vsplit->draw;
+   VSPLIT_CREATE_IDX(elts, start, fetch, elt_bias);
+   vsplit_add_cache(vsplit, elt_idx, ofbias);
+}
+
 
 /**
  * Add a fetch element and add it to the draw elements.  The fetch element is
  * in full range (uint).
  */
 static INLINE void
-vsplit_add_cache_uint(struct vsplit_frontend *vsplit, unsigned fetch)
+vsplit_add_cache_uint(struct vsplit_frontend *vsplit, const uint *elts,
+                      unsigned start, unsigned fetch, int elt_bias)
 {
-   /* special care for 0xffffffff */
-   if (fetch == 0xffffffff && !vsplit->cache.has_max_fetch) {
+   struct draw_context *draw = vsplit->draw;
+   unsigned raw_elem_idx = start + fetch + elt_bias;
+   VSPLIT_CREATE_IDX(elts, start, fetch, elt_bias);
+
+   /* special care for DRAW_MAX_FETCH_IDX */
+   if (raw_elem_idx == DRAW_MAX_FETCH_IDX && !vsplit->cache.has_max_fetch) {
       unsigned hash = fetch % MAP_SIZE;
-      vsplit->cache.fetches[hash] = fetch - 1; /* force update */
+      vsplit->cache.fetches[hash] = raw_elem_idx - 1; /* force update */
       vsplit->cache.has_max_fetch = TRUE;
    }
 
-   vsplit_add_cache(vsplit, fetch);
+   vsplit_add_cache(vsplit, elt_idx, ofbias);
 }
 
 
@@ -128,17 +217,17 @@ vsplit_add_cache_uint(struct vsplit_frontend *vsplit, unsigned fetch)
 
 #define FUNC vsplit_run_ubyte
 #define ELT_TYPE ubyte
-#define ADD_CACHE(vsplit, fetch) vsplit_add_cache(vsplit, fetch)
+#define ADD_CACHE(vsplit, ib, start, fetch, bias) vsplit_add_cache_ubyte(vsplit,ib,start,fetch,bias)
 #include "draw_pt_vsplit_tmp.h"
 
 #define FUNC vsplit_run_ushort
 #define ELT_TYPE ushort
-#define ADD_CACHE(vsplit, fetch) vsplit_add_cache(vsplit, fetch)
+#define ADD_CACHE(vsplit, ib, start, fetch, bias) vsplit_add_cache_ushort(vsplit,ib,start,fetch, bias)
 #include "draw_pt_vsplit_tmp.h"
 
 #define FUNC vsplit_run_uint
 #define ELT_TYPE uint
-#define ADD_CACHE(vsplit, fetch) vsplit_add_cache_uint(vsplit, fetch)
+#define ADD_CACHE(vsplit, ib, start, fetch, bias) vsplit_add_cache_uint(vsplit, ib, start, fetch, bias)
 #include "draw_pt_vsplit_tmp.h"
 
 
diff --git a/src/gallium/auxiliary/draw/draw_pt_vsplit_tmp.h b/src/gallium/auxiliary/draw/draw_pt_vsplit_tmp.h
index 34c210c8a43..5d72ac60924 100644
--- a/src/gallium/auxiliary/draw/draw_pt_vsplit_tmp.h
+++ b/src/gallium/auxiliary/draw/draw_pt_vsplit_tmp.h
@@ -47,13 +47,20 @@ CONCAT(vsplit_primitive_, ELT_TYPE)(struct vsplit_frontend *vsplit,
    const unsigned start = istart;
    const unsigned end = istart + icount;
 
+   /* If the index buffer overflows we'll need to run
+    * through the normal paths */
+   if (start >= draw->pt.user.eltMax ||
+       end > draw->pt.user.eltMax ||
+       end < istart || end < icount)
+      return FALSE;
+
    /* use the ib directly */
    if (min_index == 0 && sizeof(ib[0]) == sizeof(draw_elts[0])) {
       if (icount > vsplit->max_vertices)
          return FALSE;
 
-      for (i = start; i < end; i++) {
-         ELT_TYPE idx = DRAW_GET_IDX(ib, i);
+      for (i = 0; i < icount; i++) {
+         ELT_TYPE idx = DRAW_GET_IDX(ib, start + i);
          if (idx < min_index || idx > max_index) {
             debug_printf("warning: index out of range\n");
          }
@@ -82,25 +89,29 @@ CONCAT(vsplit_primitive_, ELT_TYPE)(struct vsplit_frontend *vsplit,
    fetch_start = min_index + elt_bias;
    fetch_count = max_index - min_index + 1;
 
+   /* Check for overflow in the fetch_start */
+   if (fetch_start < min_index || fetch_start < elt_bias)
+      return FALSE;
+
    if (!draw_elts) {
       if (min_index == 0) {
-         for (i = start; i < end; i++) {
-            ELT_TYPE idx = DRAW_GET_IDX(ib, i);
+         for (i = 0; i < icount; i++) {
+            ELT_TYPE idx = DRAW_GET_IDX(ib, i + start);
 
             if (idx < min_index || idx > max_index) {
                debug_printf("warning: index out of range\n");
             }
-            vsplit->draw_elts[i - start] = (ushort) idx;
+            vsplit->draw_elts[i] = (ushort) idx;
          }
       }
       else {
-         for (i = start; i < end; i++) {
-            ELT_TYPE idx = DRAW_GET_IDX(ib, i);
+         for (i = 0; i < icount; i++) {
+            ELT_TYPE idx = DRAW_GET_IDX(ib, i + start);
 
             if (idx < min_index || idx > max_index) {
                debug_printf("warning: index out of range\n");
             }
-            vsplit->draw_elts[i - start] = (ushort) (idx - min_index);
+            vsplit->draw_elts[i] = (ushort) (idx - min_index);
          }
       }
 
@@ -137,41 +148,36 @@ CONCAT(vsplit_segment_cache_, ELT_TYPE)(struct vsplit_frontend *vsplit,
    spoken = !!spoken;
    if (ibias == 0) {
       if (spoken)
-         ADD_CACHE(vsplit, DRAW_GET_IDX(ib, ispoken));
+         ADD_CACHE(vsplit, ib, 0, ispoken, 0);
 
-      for (i = spoken; i < icount; i++)
-         ADD_CACHE(vsplit, DRAW_GET_IDX(ib, istart + i));
+      for (i = spoken; i < icount; i++) {
+         ADD_CACHE(vsplit, ib, istart, i, 0);
+      }
 
       if (close)
-         ADD_CACHE(vsplit, DRAW_GET_IDX(ib, iclose));
+         ADD_CACHE(vsplit, ib, 0, iclose, 0);
    }
    else if (ibias > 0) {
       if (spoken)
-         ADD_CACHE(vsplit, (uint) DRAW_GET_IDX(ib, ispoken) + ibias);
+         ADD_CACHE(vsplit, ib, 0, ispoken, ibias);
 
       for (i = spoken; i < icount; i++)
-         ADD_CACHE(vsplit, (uint) DRAW_GET_IDX(ib, istart + i) + ibias);
+         ADD_CACHE(vsplit, ib, istart, i, ibias);
 
       if (close)
-         ADD_CACHE(vsplit, (uint) DRAW_GET_IDX(ib, iclose) + ibias);
+         ADD_CACHE(vsplit, ib, 0, iclose, ibias);
    }
    else {
       if (spoken) {
-         if ((int) ib[ispoken] < -ibias)
-            return;
-         ADD_CACHE(vsplit, DRAW_GET_IDX(ib, ispoken) + ibias);
+         ADD_CACHE(vsplit, ib, 0, ispoken, ibias);
       }
 
       for (i = spoken; i < icount; i++) {
-         if ((int) DRAW_GET_IDX(ib, istart + i) < -ibias)
-            return;
-         ADD_CACHE(vsplit, DRAW_GET_IDX(ib, istart + i) + ibias);
+         ADD_CACHE(vsplit, ib, istart, i, ibias);
       }
 
       if (close) {
-         if ((int) DRAW_GET_IDX(ib, iclose) < -ibias)
-            return;
-         ADD_CACHE(vsplit, DRAW_GET_IDX(ib, iclose) + ibias);
+         ADD_CACHE(vsplit, ib, 0, iclose, ibias);
       }
    }