1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/graphics/m3g/m3gcore11/src/m3g_tcache.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,323 @@
1.4 +/*
1.5 +* Copyright (c) 2005 Nokia Corporation and/or its subsidiary(-ies).
1.6 +* All rights reserved.
1.7 +* This component and the accompanying materials are made available
1.8 +* under the terms of the License "Eclipse Public License v1.0"
1.9 +* which accompanies this distribution, and is available
1.10 +* at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.11 +*
1.12 +* Initial Contributors:
1.13 +* Nokia Corporation - initial contribution.
1.14 +*
1.15 +* Contributors:
1.16 +*
1.17 +* Description: Transformation cache implementation
1.18 +*
1.19 +*/
1.20 +
1.21 +
1.22 +/*!
1.23 + * \internal
1.24 + * \file
1.25 + * \brief Transformation cache implementation
1.26 + */
1.27 +
1.28 +#ifndef M3G_CORE_INCLUDE
1.29 +# error included by m3g_core.c; do not compile separately.
1.30 +#endif
1.31 +
1.32 +#include "m3g_tcache.h"
1.33 +
1.34 +/* NOTE size MUST be a power of two! */
1.35 +#define TCACHE_COMPOSITES 128
1.36 +#define TCACHE_PATHS 128
1.37 +
1.38 +/*----------------------------------------------------------------------
1.39 + * Data structures
1.40 + *--------------------------------------------------------------------*/
1.41 +
1.42 +/*!
1.43 + * \internal
1.44 + * \brief Transformation path cache element
1.45 + */
1.46 +typedef struct
1.47 +{
1.48 + M3Gfloat elem[12]; /* NOTE the bottom row is always 0 0 0 1 */
1.49 + M3Guint mask;
1.50 + M3Guint classified : 1;
1.51 + M3Guint complete : 1;
1.52 +
1.53 + const Node *from, *to;
1.54 +} TCachePath;
1.55 +
1.56 +M3G_CT_ASSERT2(sizeof(TCachePath) == 64);
1.57 +
1.58 +/*!
1.59 + * \internal
1.60 + * \brief Transformation cache data implementation
1.61 + */
1.62 +struct TCacheImpl
1.63 +{
1.64 + Interface *m3g;
1.65 +
1.66 + TCachePath paths[TCACHE_PATHS];
1.67 + Matrix composites[TCACHE_COMPOSITES];
1.68 + const Transformable *compositeObjs[TCACHE_COMPOSITES];
1.69 +
1.70 + M3Gbool pathsInvalid;
1.71 +};
1.72 +
1.73 +/*----------------------------------------------------------------------
1.74 + * Private functions
1.75 + *--------------------------------------------------------------------*/
1.76 +
1.77 +static M3G_INLINE M3Gint m3gTransformableHash(const Transformable *t)
1.78 +{
1.79 + M3Guint a = (M3Guint) t;
1.80 + M3Guint b = (M3Guint) t;
1.81 +
1.82 + a += (a >> 3) + (a >> 9) + (a >> 17);
1.83 + b = (b >> 16) | (b << 16);
1.84 + b += (b >> 5) + (b >> 10) + (b >> 20);
1.85 + return (M3Gint)(a ^ b);
1.86 +}
1.87 +
1.88 +static M3Gint m3gPathHash(const Node *from, const Node *to)
1.89 +{
1.90 + M3Guint a = (M3Guint) from;
1.91 + M3Guint b = (M3Guint) to;
1.92 +
1.93 + a += (a >> 3) + (a >> 9) + (a >> 17);
1.94 + b = (b >> 16) | (b << 16);
1.95 + b += (b >> 5) + (b >> 10) + (b >> 20);
1.96 + return (M3Gint)(a ^ b);
1.97 +}
1.98 +
1.99 +static M3G_INLINE M3Gint m3gGetTransformableSlot(const TCache *tc, const Transformable *t)
1.100 +{
1.101 + M3G_UNREF(tc);
1.102 + return m3gTransformableHash(t) & (TCACHE_COMPOSITES - 1);
1.103 +}
1.104 +
1.105 +static M3G_INLINE M3Gint m3gGetPathSlot(const TCache *tc, const Node *from, const Node *to)
1.106 +{
1.107 + M3G_UNREF(tc);
1.108 + return m3gPathHash(from, to) & (TCACHE_PATHS - 1);
1.109 +}
1.110 +
1.111 +/*----------------------------------------------------------------------
1.112 + * Internal functions
1.113 + *--------------------------------------------------------------------*/
1.114 +
1.115 +/*!
1.116 + * \internal
1.117 + * \brief
1.118 + */
1.119 +static TCache* m3gCreateTransformCache(Interface *m3g)
1.120 +{
1.121 + TCache *cache = m3gAllocZ(m3g, sizeof(TCache));
1.122 + if (cache) {
1.123 + cache->m3g = m3g;
1.124 + cache->pathsInvalid = M3G_TRUE;
1.125 + }
1.126 + return cache;
1.127 +}
1.128 +
1.129 +/*!
1.130 + * \internal
1.131 + * \brief
1.132 + */
1.133 +static void m3gDeleteTransformCache(TCache *cache)
1.134 +{
1.135 + if (cache) {
1.136 + m3gFree(cache->m3g, cache);
1.137 + }
1.138 +}
1.139 +
1.140 +/*!
1.141 + * \internal
1.142 + * \brief
1.143 + */
1.144 +static void m3gCacheComposite(TCache *cache, const Transformable *t, const Matrix *m)
1.145 +{
1.146 + M3Gint idx = m3gGetTransformableSlot(cache, t);
1.147 +
1.148 + /* If the matrix being added already exists in the cache, the
1.149 + * cache is being used sub-optimally */
1.150 +
1.151 + M3G_ASSERT(cache->compositeObjs[idx] != t);
1.152 +
1.153 + /* Just overwrite any existing entries, but keep track of
1.154 + * collisions for profiling */
1.155 +
1.156 + if (cache->compositeObjs[idx]) {
1.157 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_COLLISIONS, 1);
1.158 + }
1.159 + else {
1.160 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_LOAD, 1);
1.161 + }
1.162 + cache->composites[idx] = *m;
1.163 + cache->compositeObjs[idx] = t;
1.164 +
1.165 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_INSERTS, 1);
1.166 +}
1.167 +
1.168 +/*!
1.169 + * \internal
1.170 + * \brief
1.171 + */
1.172 +static void m3gCachePath(TCache *cache, const Node *from, const Node *to, const Matrix *m)
1.173 +{
1.174 + M3G_ASSERT(m3gIsWUnity(m));
1.175 + /* These two asserts are not errors in a strict sense, but imply
1.176 + * sub-optimal cache use */
1.177 + M3G_ASSERT(from || to);
1.178 + M3G_ASSERT(from != to);
1.179 +
1.180 + M3G_BEGIN_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
1.181 +
1.182 + /* If the cache has been invalidated, wipe it clean before
1.183 + * inserting anything */
1.184 +
1.185 + if (cache->pathsInvalid) {
1.186 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_FLUSHES, 1);
1.187 + m3gZero(cache->paths, TCACHE_PATHS * sizeof(cache->paths[0]));
1.188 + cache->pathsInvalid = M3G_FALSE;
1.189 + }
1.190 +
1.191 + /* Hash to the cache, then just overwrite anything previously
1.192 + * there */
1.193 + {
1.194 + M3Gint idx = m3gGetPathSlot(cache, from, to);
1.195 + TCachePath *c = &cache->paths[idx];
1.196 +
1.197 + /* If this assert is hit, the path being added already exists
1.198 + * in the cache; this is not an error per se, but implies
1.199 + * sub-optimal cache usage */
1.200 + M3G_ASSERT(c->from != from || c->to != to);
1.201 +
1.202 + /* Overwrite the matrix data */
1.203 + {
1.204 + const M3Gfloat *src = &m->elem[0];
1.205 + M3Gfloat *dst = &c->elem[0];
1.206 + int row, col;
1.207 + for (col = 0; col < 4; ++col) {
1.208 + for (row = 0; row < 3; ++row) {
1.209 + *dst++ = *src++;
1.210 + }
1.211 + ++src;
1.212 + }
1.213 + c->mask = m->mask;
1.214 + c->classified = m->classified;
1.215 + c->complete = m->complete;
1.216 + }
1.217 +
1.218 + /* Register collisions for bookkeeping */
1.219 +
1.220 + if (c->from || c->to) {
1.221 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_COLLISIONS, 1);
1.222 + }
1.223 + else {
1.224 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_LOAD, 1);
1.225 + }
1.226 +
1.227 + c->from = from;
1.228 + c->to = to;
1.229 + }
1.230 + M3G_END_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
1.231 +
1.232 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_INSERTS, 1);
1.233 +}
1.234 +
1.235 +/*!
1.236 + * \internal
1.237 + * \brief
1.238 + */
1.239 +static M3Gbool m3gGetCachedComposite(const TCache *cache, const Transformable *t, Matrix *m)
1.240 +{
1.241 + M3Gint idx = m3gGetTransformableSlot(cache, t);
1.242 + if (cache->compositeObjs[idx] == t) {
1.243 + *m = cache->composites[idx];
1.244 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_HITS, 1);
1.245 + return M3G_TRUE;
1.246 + }
1.247 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_MISSES, 1);
1.248 + return M3G_FALSE;
1.249 +}
1.250 +
1.251 +/*!
1.252 + * \internal
1.253 + * \brief
1.254 + */
1.255 +static M3Gbool m3gGetCachedPath(const TCache *cache, const Node *from, const Node *to, Matrix *m)
1.256 +{
1.257 + M3G_BEGIN_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
1.258 +
1.259 + if (!cache->pathsInvalid) {
1.260 +
1.261 + /* Hash to the respective cache slot */
1.262 +
1.263 + M3Gint idx = m3gGetPathSlot(cache, from, to);
1.264 + const TCachePath *c = &cache->paths[idx];
1.265 +
1.266 + /* If it matches, copy to the output matrix */
1.267 +
1.268 + if (c->from == from && c->to == to) {
1.269 + const M3Gfloat *src = &c->elem[0];
1.270 + M3Gfloat *dst = &m->elem[0];
1.271 + int col;
1.272 + for (col = 0; col < 4; ++col) {
1.273 + *dst++ = *src++;
1.274 + *dst++ = *src++;
1.275 + *dst++ = *src++;
1.276 + *dst++ = 0.0f;
1.277 + }
1.278 + m->elem[15] = 1.0f;
1.279 + m->mask = c->mask;
1.280 + m->classified = c->classified;
1.281 + m->complete = c->complete;
1.282 +
1.283 + M3G_END_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
1.284 +
1.285 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_HITS, 1);
1.286 + return M3G_TRUE;
1.287 + }
1.288 + }
1.289 + M3G_END_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
1.290 +
1.291 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_MISSES, 1);
1.292 + return M3G_FALSE;
1.293 +}
1.294 +
1.295 +/*!
1.296 + * \internal
1.297 + * \brief
1.298 + */
1.299 +static void m3gInvalidateCachedPaths(TCache *cache, const Node *n)
1.300 +{
1.301 + M3G_UNREF(n);
1.302 + m3gResetStat(cache->m3g, M3G_STAT_TCACHE_PATH_LOAD);
1.303 + cache->pathsInvalid = M3G_TRUE;
1.304 +}
1.305 +
1.306 +/*!
1.307 + * \internal
1.308 + * \brief
1.309 + */
1.310 +static void m3gInvalidateCachedTransforms(TCache *cache, const Transformable *t)
1.311 +{
1.312 + /* Look for a composite entry and wipe if found */
1.313 + {
1.314 + M3Gint idx = m3gGetTransformableSlot(cache, t);
1.315 + if (cache->compositeObjs[idx] == t) {
1.316 + cache->compositeObjs[idx] = NULL;
1.317 + m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_LOAD, -1);
1.318 + }
1.319 + }
1.320 +
1.321 + /* NOTE We just cast the pointer to a Node below -- it's only used
1.322 + * for hashing, and every object will still be unique regardless
1.323 + * of the class */
1.324 +
1.325 + m3gInvalidateCachedPaths(cache, (const Node*) t);
1.326 +}