Diff: CoreMark/core_list_join.c

Revision:

0:b5d3bd64d2dc

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CoreMark/core_list_join.c	Sun Jan 24 15:46:26 2010 +0000
@@ -0,0 +1,496 @@
+/*
+Author : Shay Gal-On, EEMBC
+
+This file is part of  EEMBC(R) and CoreMark(TM), which are Copyright (C) 2009 
+All rights reserved.                            
+
+EEMBC CoreMark Software is a product of EEMBC and is provided under the terms of the
+CoreMark License that is distributed with the official EEMBC COREMARK Software release. 
+If you received this EEMBC CoreMark Software without the accompanying CoreMark License, 
+you must discontinue use and download the official release from www.coremark.org.  
+
+Also, if you are publicly displaying scores generated from the EEMBC CoreMark software, 
+make sure that you are in compliance with Run and Reporting rules specified in the accompanying readme.txt file.
+
+EEMBC 
+4354 Town Center Blvd. Suite 114-200
+El Dorado Hills, CA, 95762 
+*/ 
+
+#include "coremark.h"
+/*
+Topic: Description
+	Benchmark using a linked list.
+
+	Linked list is a common data structure used in many applications.
+	
+	For our purposes, this will excercise the memory units of the processor.
+	In particular, usage of the list pointers to find and alter data.
+	
+	We are not using Malloc since some platforms do not support this library.
+	
+	Instead, the memory block being passed in is used to create a list,
+	and the benchmark takes care not to add more items then can be
+	accomodated by the memory block. The porting layer will make sure
+	that we have a valid memory block.
+	
+	All operations are done in place, without using any extra memory.
+	
+	The list itself contains list pointers and pointers to data items.
+	Data items contain the following:
+	
+	idx - An index that captures the initial order of the list.
+	data - Variable data initialized based on the input parameters. The 16b are divided as follows:
+	o Upper 8b are backup of original data.
+	o Bit 7 indicates if the lower 7 bits are to be used as is or calculated.
+	o Bits 0-2 indicate type of operation to perform to get a 7b value.
+	o Bits 3-6 provide input for the operation.
+	
+*/
+
+/* local functions */
+
+list_head *core_list_find(list_head *list,list_data *info);
+list_head *core_list_reverse(list_head *list);
+list_head *core_list_remove(list_head *item);
+list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified);
+list_head *core_list_insert_new(list_head *insert_point
+	, list_data *info, list_head **memblock, list_data **datablock
+	, list_head *memblock_end, list_data *datablock_end);
+typedef ee_s32(*list_cmp)(list_data *a, list_data *b, core_results *res);
+list_head *core_list_mergesort(list_head *list, list_cmp cmp, core_results *res);
+
+ee_s16 calc_func(ee_s16 *pdata, core_results *res) {
+	ee_s16 data=*pdata;
+	ee_s16 retval;
+	ee_u8 optype=(data>>7) & 1; /* bit 7 indicates if the function result has been cached */
+	if (optype) /* if cached, use cache */
+		return (data & 0x007f);
+	else { /* otherwise calculate and cache the result */
+		ee_s16 flag=data & 0x7; /* bits 0-2 is type of function to perform */
+		ee_s16 dtype=((data>>3) & 0xf); /* bits 3-6 is specific data for the operation */
+		dtype |= dtype << 4; /* replicate the lower 4 bits to get an 8b value */
+		switch (flag) {
+			case 0:
+				if (dtype<0x22) /* set min period for bit corruption */
+					dtype=0x22;
+				retval=core_bench_state(res->size,(ee_u8*) res->memblock[3],res->seed1,res->seed2,dtype,res->crc);
+				if (res->crcstate==0)
+					res->crcstate=retval;
+				break;
+			case 1:
+				retval=core_bench_matrix(&(res->mat),dtype,res->crc);
+				if (res->crcmatrix==0)
+					res->crcmatrix=retval;
+				break;
+			default:
+				retval=data;
+				break;
+		}
+		res->crc=crcu16(retval,res->crc);
+		retval &= 0x007f; 
+		*pdata = (data & 0xff00) | 0x0080 | retval; /* cache the result */
+		return retval;
+	}
+}
+/* Function: cmp_complex
+	Compare the data item in a list cell.
+
+	Can be used by mergesort.
+*/
+ee_s32 cmp_complex(list_data *a, list_data *b, core_results *res) {
+	ee_s16 val1=calc_func(&(a->data16),res);
+	ee_s16 val2=calc_func(&(b->data16),res);
+	return val1 - val2;
+}
+
+/* Function: cmp_idx
+	Compare the idx item in a list cell, and regen the data.
+
+	Can be used by mergesort.
+*/
+ee_s32 cmp_idx(list_data *a, list_data *b, core_results *res) {
+	if (res==NULL) {
+		a->data16 = (a->data16 & 0xff00) | (0x00ff & (a->data16>>8));
+		b->data16 = (b->data16 & 0xff00) | (0x00ff & (b->data16>>8));
+	}
+	return a->idx - b->idx;
+}
+
+void copy_info(list_data *to,list_data *from) {
+	to->data16=from->data16;
+	to->idx=from->idx;
+}
+
+/* Benchmark for linked list:
+	- Try to find multiple data items.
+	- List sort
+	- Operate on data from list (crc)
+	- Single remove/reinsert
+	* At the end of this function, the list is back to original state
+*/
+ee_u16 core_bench_list(core_results *res, ee_s16 finder_idx) {
+	ee_u16 retval=0;
+	ee_u16 found=0,missed=0;
+	list_head *list=res->list;
+	ee_s16 find_num=res->seed3;
+	list_head *this_find;
+	list_head *finder, *remover;
+	list_data info;
+	ee_s16 i;
+
+	info.idx=finder_idx;
+	/* find <find_num> values in the list, and change the list each time (reverse and cache if value found) */
+	for (i=0; i<find_num; i++) {
+		info.data16= (i & 0xff) ;
+		this_find=core_list_find(list,&info);
+		list=core_list_reverse(list);
+		if (this_find==NULL) {
+			missed++;
+			retval+=(list->next->info->data16 >> 8) & 1;
+		}
+		else {
+			found++;
+			if (this_find->info->data16 & 0x1) /* use found value */
+				retval+=(this_find->info->data16 >> 9) & 1;
+			/* and cache next item at the head of the list (if any) */
+			if (this_find->next != NULL) {
+				finder = this_find->next;
+				this_find->next = finder->next;
+				finder->next=list->next;
+				list->next=finder;
+			}
+		}
+		if (info.idx>=0)
+			info.idx++;
+#if CORE_DEBUG
+	ee_printf("List find %d: [%d,%d,%d]\n",i,retval,missed,found);
+#endif
+	}
+	retval+=found*4-missed;
+	/* sort the list by data content and remove one item*/
+	if (finder_idx>0)
+		list=core_list_mergesort(list,cmp_complex,res);
+	remover=core_list_remove(list->next);
+	/* CRC data content of list from location of index N forward, and then undo remove */
+	finder=core_list_find(list,&info);
+	if (!finder)
+		finder=list->next;
+	while (finder) {
+		retval=crc16(list->info->data16,retval);
+		finder=finder->next;
+	}
+#if CORE_DEBUG
+	ee_printf("List sort 1: %04x\n",retval);
+#endif
+	remover=core_list_undo_remove(remover,list->next);
+	/* sort the list by index, in effect returning the list to original state */
+	list=core_list_mergesort(list,cmp_idx,NULL);
+	/* CRC data content of list */
+	finder=list->next;
+	while (finder) {
+		retval=crc16(list->info->data16,retval);
+		finder=finder->next;
+	}
+#if CORE_DEBUG
+	ee_printf("List sort 2: %04x\n",retval);
+#endif
+	return retval;
+}
+/* Function: core_list_init
+	Initialize list with data.
+
+	Parameters:
+	blksize - Size of memory to be initialized.
+	memblock - Pointer to memory block.
+	seed - 	Actual values chosen depend on the seed parameter.
+		The seed parameter MUST be supplied from a source that cannot be determined at compile time
+
+	Returns:
+	Pointer to the head of the list.
+
+*/
+list_head *core_list_init(ee_u32 blksize, list_head *memblock, ee_s16 seed) {
+	/* calculated pointers for the list */
+	ee_u32 per_item=16+sizeof(struct list_data_s);
+	ee_u32 size=(blksize/per_item)-2; /* to accomodate systems with 64b pointers, and make sure same code is executed, set max list elements */
+	list_head *memblock_end=memblock+size;
+	list_data *datablock=(list_data *)(memblock_end);
+	list_data *datablock_end=datablock+size;
+	/* some useful variables */
+	ee_u32 i;
+	list_head *finder,*list=memblock;
+	list_data info;
+
+	/* create a fake items for the list head and tail */
+	list->next=NULL;
+	list->info=datablock;
+	list->info->idx=0x0000;
+	list->info->data16=(ee_s16)0x8080;
+	memblock++;
+	datablock++;
+	info.idx=0x7fff;
+	info.data16=(ee_s16)0xffff;
+	core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
+	
+	/* then insert size items */
+	for (i=0; i<size; i++) {
+		ee_u16 datpat=((ee_u16)(seed^i) & 0xf);
+		ee_u16 dat=(datpat<<3) | (i&0x7); /* alternate between algorithms */
+		info.data16=(dat<<8) | dat;		/* fill the data with actual data and upper bits with rebuild value */
+		core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
+	}
+	/* and now index the list so we know initial seed order of the list */
+	finder=list->next;
+	i=1;
+	while (finder->next!=NULL) {
+		if (i<size/5) /* first 20% of the list in order */
+			finder->info->idx=i++;
+		else { 
+			ee_u16 pat=(ee_u16)(i++ ^ seed); /* get a pseudo random number */
+			finder->info->idx=0x3fff & (((i & 0x07) << 8) | pat); /* make sure the mixed items end up after the ones in sequence */
+		}
+		finder=finder->next;
+	}
+	list = core_list_mergesort(list,cmp_idx,NULL);
+#if CORE_DEBUG
+	ee_printf("Initialized list:\n");
+	finder=list;
+	while (finder) {
+		ee_printf("[%04x,%04x]",finder->info->idx,(ee_u16)finder->info->data16);
+		finder=finder->next;
+	}
+	ee_printf("\n");
+#endif
+	return list;
+}
+
+/* Function: core_list_insert
+	Insert an item to the list
+
+	Parameters:
+	insert_point - where to insert the item.
+	info - data for the cell.
+	memblock - pointer for the list header
+	datablock - pointer for the list data
+	memblock_end - end of region for list headers
+	datablock_end - end of region for list data
+
+	Returns:
+	Pointer to new item.
+*/
+list_head *core_list_insert_new(list_head *insert_point, list_data *info, list_head **memblock, list_data **datablock
+	, list_head *memblock_end, list_data *datablock_end) {
+	list_head *newitem;
+	
+	if ((*memblock+1) >= memblock_end)
+		return NULL;
+	if ((*datablock+1) >= datablock_end)
+		return NULL;
+		
+	newitem=*memblock;
+	(*memblock)++;
+	newitem->next=insert_point->next;
+	insert_point->next=newitem;
+	
+	newitem->info=*datablock;
+	(*datablock)++;
+	copy_info(newitem->info,info);
+	
+	return newitem;
+}
+
+/* Function: core_list_remove
+	Remove an item from the list.
+
+	Operation:
+	For a singly linked list, remove by copying the data from the next item 
+	over to the current cell, and unlinking the next item.
+
+	Note: 
+	since there is always a fake item at the end of the list, no need to check for NULL.
+
+	Returns:
+	Removed item.
+*/
+list_head *core_list_remove(list_head *item) {
+	list_data *tmp;
+	list_head *ret=item->next;
+	/* swap data pointers */
+	tmp=item->info;
+	item->info=ret->info;
+	ret->info=tmp;
+	/* and eliminate item */
+	item->next=item->next->next;
+	ret->next=NULL;
+	return ret;
+}
+
+/* Function: core_list_undo_remove
+	Undo a remove operation.
+
+	Operation:
+	Since we want each iteration of the benchmark to be exactly the same,
+	we need to be able to undo a remove. 
+	Link the removed item back into the list, and switch the info items.
+
+	Parameters:
+	item_removed - Return value from the <core_list_remove>
+	item_modified - List item that was modified during <core_list_remove>
+
+	Returns:
+	The item that was linked back to the list.
+	
+*/
+list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified) {
+	list_data *tmp;
+	/* swap data pointers */
+	tmp=item_removed->info;
+	item_removed->info=item_modified->info;
+	item_modified->info=tmp;
+	/* and insert item */
+	item_removed->next=item_modified->next;
+	item_modified->next=item_removed;
+	return item_removed;
+}
+
+/* Function: core_list_find
+	Find an item in the list
+
+	Operation:
+	Find an item by idx (if not 0) or specific data value
+
+	Parameters:
+	list - list head
+	info - idx or data to find
+
+	Returns:
+	Found item, or NULL if not found.
+*/
+list_head *core_list_find(list_head *list,list_data *info) {
+	if (info->idx>=0) {
+		while (list && (list->info->idx != info->idx))
+			list=list->next;
+		return list;
+	} else {
+		while (list && ((list->info->data16 & 0xff) != info->data16))
+			list=list->next;
+		return list;
+	}
+}
+/* Function: core_list_reverse
+	Reverse a list
+
+	Operation:
+	Rearrange the pointers so the list is reversed.
+
+	Parameters:
+	list - list head
+	info - idx or data to find
+
+	Returns:
+	Found item, or NULL if not found.
+*/
+
+list_head *core_list_reverse(list_head *list) {
+	list_head *next=NULL, *tmp;
+	while (list) {
+		tmp=list->next;
+		list->next=next;
+		next=list;
+		list=tmp;
+	}
+	return next;
+}
+/* Function: core_list_mergesort
+	Sort the list in place without recursion.
+
+	Description:
+	Use mergesort, as for linked list this is a realistic solution. 
+	Also, since this is aimed at embedded, care was taken to use iterative rather then recursive algorithm.
+	The sort can either return the list to original order (by idx) ,
+	or use the data item to invoke other other algorithms and change the order of the list.
+
+	Parameters:
+	list - list to be sorted.
+	cmp - cmp function to use
+
+	Returns:
+	New head of the list.
+
+	Note: 
+	We have a special header for the list that will always be first,
+	but the algorithm could theoretically modify where the list starts.
+
+ */
+list_head *core_list_mergesort(list_head *list, list_cmp cmp, core_results *res) {
+    list_head *p, *q, *e, *tail;
+    ee_s32 insize, nmerges, psize, qsize, i;
+
+    insize = 1;
+
+    while (1) {
+        p = list;
+        list = NULL;
+        tail = NULL;
+
+        nmerges = 0;  /* count number of merges we do in this pass */
+
+        while (p) {
+            nmerges++;  /* there exists a merge to be done */
+            /* step `insize' places along from p */
+            q = p;
+            psize = 0;
+            for (i = 0; i < insize; i++) {
+                psize++;
+			    q = q->next;
+                if (!q) break;
+            }
+
+            /* if q hasn't fallen off end, we have two lists to merge */
+            qsize = insize;
+
+            /* now we have two lists; merge them */
+            while (psize > 0 || (qsize > 0 && q)) {
+
+				/* decide whether next element of merge comes from p or q */
+				if (psize == 0) {
+				    /* p is empty; e must come from q. */
+				    e = q; q = q->next; qsize--;
+				} else if (qsize == 0 || !q) {
+				    /* q is empty; e must come from p. */
+				    e = p; p = p->next; psize--;
+				} else if (cmp(p->info,q->info,res) <= 0) {
+				    /* First element of p is lower (or same); e must come from p. */
+				    e = p; p = p->next; psize--;
+				} else {
+				    /* First element of q is lower; e must come from q. */
+				    e = q; q = q->next; qsize--;
+				}
+
+		        /* add the next element to the merged list */
+				if (tail) {
+				    tail->next = e;
+				} else {
+				    list = e;
+				}
+				tail = e;
+	        }
+
+			/* now p has stepped `insize' places along, and q has too */
+			p = q;
+        }
+		
+	    tail->next = NULL;
+
+        /* If we have done only one merge, we're finished. */
+        if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
+            return list;
+
+        /* Otherwise repeat, merging lists twice the size */
+        insize *= 2;
+    }
+#if COMPILER_REQUIRES_SORT_RETURN
+	return list;
+#endif
+}