Fix for [#25544] Blender crashes when changing the particles emission amount

* I've getting bad feelings about the point cache index_array for a while (cause for this bug too), so from now on memory cache uses a simple binary search directly on the index data to handle queries to specific data points.
* This is a bit slower than just checking from a dedicated array, but it's much less error prone, uses less memory and makes the code more readable too, so it's not a tough choice.

3 files changed, 51 insertions, 57 deletions

diff --git a/source/blender/blenkernel/BKE_pointcache.h b/source/blender/blenkernel/BKE_pointcache.h
index f3548888168..c7f76c033c8 100644
--- a/source/blender/blenkernel/BKE_pointcache.h
+++ b/source/blender/blenkernel/BKE_pointcache.h
@@ -89,7 +89,7 @@ struct SoftBody;
 
 /* temp structure for read/write */
 typedef struct PTCacheData {
-	int index;
+	uint32_t index;
 	float loc[3];
 	float vel[3];
 	float rot[4];
@@ -270,6 +270,9 @@ void BKE_ptcache_update_info(PTCacheID *pid);
 /* Size of cache data type. */
 int		BKE_ptcache_data_size(int data_type);
 
+/* Is point with indes in memory cache */
+int BKE_ptcache_mem_index_find(struct PTCacheMem *pm, int index);
+
 /* Memory cache read/write helpers. */
 void BKE_ptcache_mem_pointers_init(struct PTCacheMem *pm);
 void BKE_ptcache_mem_pointers_incr(struct PTCacheMem *pm);
diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c
index 018b882f7a2..26f96d0c304 100644
--- a/source/blender/blenkernel/intern/particle.c
+++ b/source/blender/blenkernel/intern/particle.c
@@ -1056,6 +1056,7 @@ typedef struct ParticleInterpolationData {
 static void get_pointcache_keys_for_time(Object *UNUSED(ob), PointCache *cache, PTCacheMem **cur, int index, float t, ParticleKey *key1, ParticleKey *key2)
 {
 	static PTCacheMem *pm = NULL;
+	int index1, index2;
 
 	if(index < 0) { /* initialize */
 		*cur = cache->mem_cache.first;
@@ -1070,15 +1071,19 @@ static void get_pointcache_keys_for_time(Object *UNUSED(ob), PointCache *cache,
 
 			pm = *cur;
 
-			BKE_ptcache_make_particle_key(key2, pm->index_array ? pm->index_array[index] - 1 : index, pm->data, (float)pm->frame);
-			if(pm->prev->index_array && pm->prev->index_array[index] == 0)
+			index2 = BKE_ptcache_mem_index_find(pm, index);
+			index1 = BKE_ptcache_mem_index_find(pm->prev, index);
+
+			BKE_ptcache_make_particle_key(key2, index2, pm->data, (float)pm->frame);
+			if(index1 < 0)
 				copy_particle_key(key1, key2, 1);
 			else
-				BKE_ptcache_make_particle_key(key1, pm->prev->index_array ? pm->prev->index_array[index] - 1 : index, pm->prev->data, (float)pm->prev->frame);
+				BKE_ptcache_make_particle_key(key1, index1, pm->prev->data, (float)pm->prev->frame);
 		}
 		else if(cache->mem_cache.first) {
 			pm = cache->mem_cache.first;
-			BKE_ptcache_make_particle_key(key2, pm->index_array ? pm->index_array[index] - 1 : index, pm->data, (float)pm->frame);
+			index2 = BKE_ptcache_mem_index_find(pm, index);
+			BKE_ptcache_make_particle_key(key2, index2, pm->data, (float)pm->frame);
 			copy_particle_key(key1, key2, 1);
 		}
 	}
@@ -1089,14 +1094,7 @@ static int get_pointcache_times_for_particle(PointCache *cache, int index, float
 	int ret = 0;
 
 	for(pm=cache->mem_cache.first; pm; pm=pm->next) {
-		if(pm->index_array) {
-			if(pm->index_array[index]) {
-				*start = pm->frame;
-				ret++;
-				break;
-			}
-		}
-		else {
+		if(BKE_ptcache_mem_index_find(pm, index) >= 0) {
 			*start = pm->frame;
 			ret++;
 			break;
@@ -1104,14 +1102,7 @@ static int get_pointcache_times_for_particle(PointCache *cache, int index, float
 	}
 
 	for(pm=cache->mem_cache.last; pm; pm=pm->prev) {
-		if(pm->index_array) {
-			if(pm->index_array[index]) {
-				*end = pm->frame;
-				ret++;
-				break;
-			}
-		}
-		else {
+		if(BKE_ptcache_mem_index_find(pm, index) >= 0) {
 			*end = pm->frame;
 			ret++;
 			break;
@@ -1126,13 +1117,8 @@ float psys_get_dietime_from_cache(PointCache *cache, int index) {
 	int dietime = 10000000; /* some max value so that we can default to pa->time+lifetime */
 
 	for(pm=cache->mem_cache.last; pm; pm=pm->prev) {
-		if(pm->index_array) {
-			if(pm->index_array[index])
-				return (float)pm->frame;
-		}
-		else {
+		if(BKE_ptcache_mem_index_find(pm, index) >= 0)
 			return (float)pm->frame;
-		}
 	}
 
 	return (float)dietime;
diff --git a/source/blender/blenkernel/intern/pointcache.c b/source/blender/blenkernel/intern/pointcache.c
index 317723aef7f..1d58f276117 100644
--- a/source/blender/blenkernel/intern/pointcache.c
+++ b/source/blender/blenkernel/intern/pointcache.c
@@ -1161,6 +1161,39 @@ static void ptcache_file_pointers_init(PTCacheFile *pf)
 	pf->cur[BPHYS_DATA_BOIDS] =		(data_types & (1<<BPHYS_DATA_BOIDS))	?		&pf->data.boids	: NULL;
 }
 
+/* Check to see if point number "index" is in pm, uses binary search for index data. */
+int BKE_ptcache_mem_index_find(PTCacheMem *pm, int index)
+{
+	if(pm->data[BPHYS_DATA_INDEX]) {
+		uint32_t key = index;
+		uint32_t *data = pm->data[BPHYS_DATA_INDEX];
+		uint32_t mid, low = 0, high = pm->totpoint - 1;
+
+		if(key < *data || key > *(data+high))
+			return -1;
+
+		/* check simple case for continuous indexes first */
+		if(data[key-*data]==key)
+			return key-*data;
+
+		while(low <= high) {
+			mid= (low + high)/2;
+
+			if(data[mid] > key)
+				high = mid - 1;
+			else if(data[mid] < key)
+				low = mid + 1;
+			else
+				return mid;
+		}
+
+		return -1;
+	}
+	else {
+		return (index < pm->totpoint ? index : -1);
+	}
+}
+
 void BKE_ptcache_mem_pointers_init(PTCacheMem *pm)
 {
 	int data_types = pm->data_types;
@@ -1182,9 +1215,9 @@ void BKE_ptcache_mem_pointers_incr(PTCacheMem *pm)
 int  BKE_ptcache_mem_pointers_seek(int point_index, PTCacheMem *pm)
 {
 	int data_types = pm->data_types;
-	int i, index = pm->index_array ? pm->index_array[point_index] - 1 : point_index;
+	int i, index = BKE_ptcache_mem_index_find(pm, point_index);
 
-	if(index < 0 || point_index >= MEM_allocN_len(pm->index_array)/sizeof(int)) {
+	if(index < 0) {
 		/* Can't give proper location without reallocation, so don't give any location.
 		 * Some points will be cached improperly, but this only happens with simulation
 		 * steps bigger than cache->step, so the cache has to be recalculated anyways
@@ -1218,11 +1251,6 @@ static void ptcache_data_free(PTCacheMem *pm)
 		if(data[i])
 			MEM_freeN(data[i]);
 	}
-
-	if(pm->index_array) {
-		MEM_freeN(pm->index_array);
-		pm->index_array = NULL;
-	}
 }
 static void ptcache_data_copy(void *from[], void *to[])
 {
@@ -1306,24 +1334,6 @@ static void ptcache_find_frames_around(PTCacheID *pid, int frame, int *fra1, int
 		}
 	}
 }
-static void ptcache_make_index_array(PTCacheMem *pm, int totpoint)
-{
-	int i, *index;
-
-	if(pm->index_array) {
-		MEM_freeN(pm->index_array);
-		pm->index_array = NULL;
-	}
-
-	if(!pm->data[BPHYS_DATA_INDEX])
-		return;
-
-	pm->index_array = MEM_callocN(totpoint * sizeof(int), "PTCacheMem index_array");
-	index = pm->data[BPHYS_DATA_INDEX];
-
-	for(i=0; i<pm->totpoint; i++, index++)
-		pm->index_array[*index] = i + 1;
-}
 
 static PTCacheMem *ptcache_disk_frame_to_mem(PTCacheID *pid, int cfra)
 {
@@ -1398,9 +1408,6 @@ static PTCacheMem *ptcache_disk_frame_to_mem(PTCacheID *pid, int cfra)
 		}
 	}
 
-	if(!error)
-		ptcache_make_index_array(pm, pid->totpoint(pid->calldata, pm->frame));
-
 	if(error && pm) {
 		ptcache_data_free(pm);
 		ptcache_extra_free(pm);
@@ -1806,7 +1813,6 @@ static int ptcache_write(PTCacheID *pid, int cfra, int overwrite)
 		}
 	}
 	else {
-		ptcache_make_index_array(pm, pid->totpoint(pid->calldata, cfra));
 		BLI_addtail(&cache->mem_cache, pm);
 	}
 
@@ -2989,7 +2995,6 @@ void BKE_ptcache_update_info(PTCacheID *pid)
 				bytes += sizeof(PTCacheExtra);
 			}
 
-			bytes += MEM_allocN_len(pm->index_array);
 			bytes += sizeof(PTCacheMem);
 			
 			totframes++;