1/*
2 * Mesa 3-D graphics library
3 *
4 * Copyright 2007-2008 VMware, Inc.
5 * Copyright (C) 2010 LunarG Inc.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a
8 * copy of this software and associated documentation files (the "Software"),
9 * to deal in the Software without restriction, including without limitation
10 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11 * and/or sell copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included
15 * in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
20 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
22 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
23 * DEALINGS IN THE SOFTWARE.
24 */
25
26#include "util/u_math.h"
27#include "util/u_memory.h"
28
29#include "draw/draw_context.h"
30#include "draw/draw_private.h"
31#include "draw/draw_pt.h"
32
33#define SEGMENT_SIZE 1024
34#define MAP_SIZE     256
35
36/* The largest possible index within an index buffer */
37#define MAX_ELT_IDX 0xffffffff
38
39struct vsplit_frontend {
40   struct draw_pt_front_end base;
41   struct draw_context *draw;
42
43   enum pipe_prim_type prim;
44
45   struct draw_pt_middle_end *middle;
46
47   unsigned max_vertices;
48   ushort segment_size;
49
50   /* buffers for splitting */
51   unsigned fetch_elts[SEGMENT_SIZE];
52   ushort draw_elts[SEGMENT_SIZE];
53   ushort identity_draw_elts[SEGMENT_SIZE];
54
55   struct {
56      /* map a fetch element to a draw element */
57      unsigned fetches[MAP_SIZE];
58      ushort draws[MAP_SIZE];
59      boolean has_max_fetch;
60
61      ushort num_fetch_elts;
62      ushort num_draw_elts;
63   } cache;
64};
65
66
67static void
68vsplit_clear_cache(struct vsplit_frontend *vsplit)
69{
70   memset(vsplit->cache.fetches, 0xff, sizeof(vsplit->cache.fetches));
71   vsplit->cache.has_max_fetch = FALSE;
72   vsplit->cache.num_fetch_elts = 0;
73   vsplit->cache.num_draw_elts = 0;
74}
75
76
77static void
78vsplit_flush_cache(struct vsplit_frontend *vsplit, unsigned flags)
79{
80   vsplit->middle->run(vsplit->middle,
81         vsplit->fetch_elts, vsplit->cache.num_fetch_elts,
82         vsplit->draw_elts, vsplit->cache.num_draw_elts, flags);
83}
84
85
86/**
87 * Add a fetch element and add it to the draw elements.
88 */
89static inline void
90vsplit_add_cache(struct vsplit_frontend *vsplit, unsigned fetch)
91{
92   unsigned hash;
93
94   hash = fetch % MAP_SIZE;
95
96   /* If the value isn't in the cache or it's an overflow due to the
97    * element bias */
98   if (vsplit->cache.fetches[hash] != fetch) {
99      /* update cache */
100      vsplit->cache.fetches[hash] = fetch;
101      vsplit->cache.draws[hash] = vsplit->cache.num_fetch_elts;
102
103      /* add fetch */
104      assert(vsplit->cache.num_fetch_elts < vsplit->segment_size);
105      vsplit->fetch_elts[vsplit->cache.num_fetch_elts++] = fetch;
106   }
107
108   vsplit->draw_elts[vsplit->cache.num_draw_elts++] = vsplit->cache.draws[hash];
109}
110
111
112/**
113 * Returns the base index to the elements array.
114 * The value is checked for integer overflow (not sure it can happen?).
115 */
116static inline unsigned
117vsplit_get_base_idx(unsigned start, unsigned fetch)
118{
119   return draw_overflow_uadd(start, fetch, MAX_ELT_IDX);
120}
121
122
123static inline void
124vsplit_add_cache_ubyte(struct vsplit_frontend *vsplit, const ubyte *elts,
125                       unsigned start, unsigned fetch, int elt_bias)
126{
127   struct draw_context *draw = vsplit->draw;
128   unsigned elt_idx;
129   elt_idx = vsplit_get_base_idx(start, fetch);
130   elt_idx = (unsigned)((int)(DRAW_GET_IDX(elts, elt_idx)) + elt_bias);
131   /* unlike the uint case this can only happen with elt_bias */
132   if (elt_bias && elt_idx == DRAW_MAX_FETCH_IDX && !vsplit->cache.has_max_fetch) {
133      unsigned hash = elt_idx % MAP_SIZE;
134      vsplit->cache.fetches[hash] = 0;
135      vsplit->cache.has_max_fetch = TRUE;
136   }
137   vsplit_add_cache(vsplit, elt_idx);
138}
139
140
141static inline void
142vsplit_add_cache_ushort(struct vsplit_frontend *vsplit, const ushort *elts,
143                       unsigned start, unsigned fetch, int elt_bias)
144{
145   struct draw_context *draw = vsplit->draw;
146   unsigned elt_idx;
147   elt_idx = vsplit_get_base_idx(start, fetch);
148   elt_idx = (unsigned)((int)(DRAW_GET_IDX(elts, elt_idx)) + elt_bias);
149   /* unlike the uint case this can only happen with elt_bias */
150   if (elt_bias && elt_idx == DRAW_MAX_FETCH_IDX && !vsplit->cache.has_max_fetch) {
151      unsigned hash = elt_idx % MAP_SIZE;
152      vsplit->cache.fetches[hash] = 0;
153      vsplit->cache.has_max_fetch = TRUE;
154   }
155   vsplit_add_cache(vsplit, elt_idx);
156}
157
158
159/**
160 * Add a fetch element and add it to the draw elements.  The fetch element is
161 * in full range (uint).
162 */
163static inline void
164vsplit_add_cache_uint(struct vsplit_frontend *vsplit, const uint *elts,
165                      unsigned start, unsigned fetch, int elt_bias)
166{
167   struct draw_context *draw = vsplit->draw;
168   unsigned elt_idx;
169   /*
170    * The final element index is just element index plus element bias.
171    */
172   elt_idx = vsplit_get_base_idx(start, fetch);
173   elt_idx = (unsigned)((int)(DRAW_GET_IDX(elts, elt_idx)) + elt_bias);
174   /* Take care for DRAW_MAX_FETCH_IDX (since cache is initialized to -1). */
175   if (elt_idx == DRAW_MAX_FETCH_IDX && !vsplit->cache.has_max_fetch) {
176      unsigned hash = elt_idx % MAP_SIZE;
177      /* force update - any value will do except DRAW_MAX_FETCH_IDX */
178      vsplit->cache.fetches[hash] = 0;
179      vsplit->cache.has_max_fetch = TRUE;
180   }
181   vsplit_add_cache(vsplit, elt_idx);
182}
183
184
185#define FUNC vsplit_run_linear
186#include "draw_pt_vsplit_tmp.h"
187
188#define FUNC vsplit_run_ubyte
189#define ELT_TYPE ubyte
190#define ADD_CACHE(vsplit, ib, start, fetch, bias) vsplit_add_cache_ubyte(vsplit,ib,start,fetch,bias)
191#include "draw_pt_vsplit_tmp.h"
192
193#define FUNC vsplit_run_ushort
194#define ELT_TYPE ushort
195#define ADD_CACHE(vsplit, ib, start, fetch, bias) vsplit_add_cache_ushort(vsplit,ib,start,fetch, bias)
196#include "draw_pt_vsplit_tmp.h"
197
198#define FUNC vsplit_run_uint
199#define ELT_TYPE uint
200#define ADD_CACHE(vsplit, ib, start, fetch, bias) vsplit_add_cache_uint(vsplit, ib, start, fetch, bias)
201#include "draw_pt_vsplit_tmp.h"
202
203
204static void
205vsplit_prepare(struct draw_pt_front_end *frontend,
206               enum pipe_prim_type in_prim,
207               struct draw_pt_middle_end *middle,
208               unsigned opt)
209{
210   struct vsplit_frontend *vsplit = (struct vsplit_frontend *) frontend;
211
212   switch (vsplit->draw->pt.user.eltSize) {
213   case 0:
214      vsplit->base.run = vsplit_run_linear;
215      break;
216   case 1:
217      vsplit->base.run = vsplit_run_ubyte;
218      break;
219   case 2:
220      vsplit->base.run = vsplit_run_ushort;
221      break;
222   case 4:
223      vsplit->base.run = vsplit_run_uint;
224      break;
225   default:
226      assert(0);
227      break;
228   }
229
230   /* split only */
231   vsplit->prim = in_prim;
232
233   vsplit->middle = middle;
234   middle->prepare(middle, vsplit->prim, opt, &vsplit->max_vertices);
235
236   vsplit->segment_size = MIN2(SEGMENT_SIZE, vsplit->max_vertices);
237}
238
239
240static void
241vsplit_flush(struct draw_pt_front_end *frontend, unsigned flags)
242{
243   struct vsplit_frontend *vsplit = (struct vsplit_frontend *) frontend;
244
245   if (flags & DRAW_FLUSH_STATE_CHANGE) {
246      vsplit->middle->finish(vsplit->middle);
247      vsplit->middle = NULL;
248   }
249}
250
251
252static void
253vsplit_destroy(struct draw_pt_front_end *frontend)
254{
255   FREE(frontend);
256}
257
258
259struct draw_pt_front_end *
260draw_pt_vsplit(struct draw_context *draw)
261{
262   struct vsplit_frontend *vsplit = CALLOC_STRUCT(vsplit_frontend);
263
264   if (!vsplit)
265      return NULL;
266
267   vsplit->base.prepare = vsplit_prepare;
268   vsplit->base.run     = NULL;
269   vsplit->base.flush   = vsplit_flush;
270   vsplit->base.destroy = vsplit_destroy;
271   vsplit->draw = draw;
272
273   for (unsigned i = 0; i < SEGMENT_SIZE; i++)
274      vsplit->identity_draw_elts[i] = i;
275
276   return &vsplit->base;
277}
278