core_list_join.c

00001 /*
00002 Author : Shay Gal-On, EEMBC
00003 
00004 This file is part of  EEMBC(R) and CoreMark(TM), which are Copyright (C) 2009 
00005 All rights reserved.                            
00006 
00007 EEMBC CoreMark Software is a product of EEMBC and is provided under the terms of the
00008 CoreMark License that is distributed with the official EEMBC COREMARK Software release. 
00009 If you received this EEMBC CoreMark Software without the accompanying CoreMark License, 
00010 you must discontinue use and download the official release from www.coremark.org.  
00011 
00012 Also, if you are publicly displaying scores generated from the EEMBC CoreMark software, 
00013 make sure that you are in compliance with Run and Reporting rules specified in the accompanying readme.txt file.
00014 
00015 EEMBC 
00016 4354 Town Center Blvd. Suite 114-200
00017 El Dorado Hills, CA, 95762 
00018 */ 
00019 
00020 #include "coremark.h"
00021 /*
00022 Topic: Description
00023     Benchmark using a linked list.
00024 
00025     Linked list is a common data structure used in many applications.
00026     
00027     For our purposes, this will excercise the memory units of the processor.
00028     In particular, usage of the list pointers to find and alter data.
00029     
00030     We are not using Malloc since some platforms do not support this library.
00031     
00032     Instead, the memory block being passed in is used to create a list,
00033     and the benchmark takes care not to add more items then can be
00034     accomodated by the memory block. The porting layer will make sure
00035     that we have a valid memory block.
00036     
00037     All operations are done in place, without using any extra memory.
00038     
00039     The list itself contains list pointers and pointers to data items.
00040     Data items contain the following:
00041     
00042     idx - An index that captures the initial order of the list.
00043     data - Variable data initialized based on the input parameters. The 16b are divided as follows:
00044     o Upper 8b are backup of original data.
00045     o Bit 7 indicates if the lower 7 bits are to be used as is or calculated.
00046     o Bits 0-2 indicate type of operation to perform to get a 7b value.
00047     o Bits 3-6 provide input for the operation.
00048     
00049 */
00050 
00051 /* local functions */
00052 
00053 list_head *core_list_find(list_head *list,list_data *info);
00054 list_head *core_list_reverse(list_head *list);
00055 list_head *core_list_remove(list_head *item);
00056 list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified);
00057 list_head *core_list_insert_new(list_head *insert_point
00058     , list_data *info, list_head **memblock, list_data **datablock
00059     , list_head *memblock_end, list_data *datablock_end);
00060 typedef ee_s32(*list_cmp)(list_data *a, list_data *b, core_results *res);
00061 list_head *core_list_mergesort(list_head *list, list_cmp cmp, core_results *res);
00062 
00063 ee_s16 calc_func(ee_s16 *pdata, core_results *res) {
00064     ee_s16 data=*pdata;
00065     ee_s16 retval;
00066     ee_u8 optype=(data>>7) & 1; /* bit 7 indicates if the function result has been cached */
00067     if (optype) /* if cached, use cache */
00068         return (data & 0x007f);
00069     else { /* otherwise calculate and cache the result */
00070         ee_s16 flag=data & 0x7; /* bits 0-2 is type of function to perform */
00071         ee_s16 dtype=((data>>3) & 0xf); /* bits 3-6 is specific data for the operation */
00072         dtype |= dtype << 4; /* replicate the lower 4 bits to get an 8b value */
00073         switch (flag) {
00074             case 0:
00075                 if (dtype<0x22) /* set min period for bit corruption */
00076                     dtype=0x22;
00077                 retval=core_bench_state(res->size,(ee_u8*) res->memblock[3],res->seed1,res->seed2,dtype,res->crc);
00078                 if (res->crcstate==0)
00079                     res->crcstate=retval;
00080                 break;
00081             case 1:
00082                 retval=core_bench_matrix(&(res->mat),dtype,res->crc);
00083                 if (res->crcmatrix==0)
00084                     res->crcmatrix=retval;
00085                 break;
00086             default:
00087                 retval=data;
00088                 break;
00089         }
00090         res->crc=crcu16(retval,res->crc);
00091         retval &= 0x007f; 
00092         *pdata = (data & 0xff00) | 0x0080 | retval; /* cache the result */
00093         return retval;
00094     }
00095 }
00096 /* Function: cmp_complex
00097     Compare the data item in a list cell.
00098 
00099     Can be used by mergesort.
00100 */
00101 ee_s32 cmp_complex(list_data *a, list_data *b, core_results *res) {
00102     ee_s16 val1=calc_func(&(a->data16),res);
00103     ee_s16 val2=calc_func(&(b->data16),res);
00104     return val1 - val2;
00105 }
00106 
00107 /* Function: cmp_idx
00108     Compare the idx item in a list cell, and regen the data.
00109 
00110     Can be used by mergesort.
00111 */
00112 ee_s32 cmp_idx(list_data *a, list_data *b, core_results *res) {
00113     if (res==NULL) {
00114         a->data16 = (a->data16 & 0xff00) | (0x00ff & (a->data16>>8));
00115         b->data16 = (b->data16 & 0xff00) | (0x00ff & (b->data16>>8));
00116     }
00117     return a->idx - b->idx;
00118 }
00119 
00120 void copy_info(list_data *to,list_data *from) {
00121     to->data16=from->data16;
00122     to->idx=from->idx;
00123 }
00124 
00125 /* Benchmark for linked list:
00126     - Try to find multiple data items.
00127     - List sort
00128     - Operate on data from list (crc)
00129     - Single remove/reinsert
00130     * At the end of this function, the list is back to original state
00131 */
00132 ee_u16 core_bench_list(core_results *res, ee_s16 finder_idx) {
00133     ee_u16 retval=0;
00134     ee_u16 found=0,missed=0;
00135     list_head *list=res->list;
00136     ee_s16 find_num=res->seed3;
00137     list_head *this_find;
00138     list_head *finder, *remover;
00139     list_data info;
00140     ee_s16 i;
00141 
00142     info.idx=finder_idx;
00143     /* find <find_num> values in the list, and change the list each time (reverse and cache if value found) */
00144     for (i=0; i<find_num; i++) {
00145         info.data16= (i & 0xff) ;
00146         this_find=core_list_find(list,&info);
00147         list=core_list_reverse(list);
00148         if (this_find==NULL) {
00149             missed++;
00150             retval+=(list->next->info->data16 >> 8) & 1;
00151         }
00152         else {
00153             found++;
00154             if (this_find->info->data16 & 0x1) /* use found value */
00155                 retval+=(this_find->info->data16 >> 9) & 1;
00156             /* and cache next item at the head of the list (if any) */
00157             if (this_find->next != NULL) {
00158                 finder = this_find->next;
00159                 this_find->next = finder->next;
00160                 finder->next=list->next;
00161                 list->next=finder;
00162             }
00163         }
00164         if (info.idx>=0)
00165             info.idx++;
00166 #if CORE_DEBUG
00167     ee_printf("List find %d: [%d,%d,%d]\n",i,retval,missed,found);
00168 #endif
00169     }
00170     retval+=found*4-missed;
00171     /* sort the list by data content and remove one item*/
00172     if (finder_idx>0)
00173         list=core_list_mergesort(list,cmp_complex,res);
00174     remover=core_list_remove(list->next);
00175     /* CRC data content of list from location of index N forward, and then undo remove */
00176     finder=core_list_find(list,&info);
00177     if (!finder)
00178         finder=list->next;
00179     while (finder) {
00180         retval=crc16(list->info->data16,retval);
00181         finder=finder->next;
00182     }
00183 #if CORE_DEBUG
00184     ee_printf("List sort 1: %04x\n",retval);
00185 #endif
00186     remover=core_list_undo_remove(remover,list->next);
00187     /* sort the list by index, in effect returning the list to original state */
00188     list=core_list_mergesort(list,cmp_idx,NULL);
00189     /* CRC data content of list */
00190     finder=list->next;
00191     while (finder) {
00192         retval=crc16(list->info->data16,retval);
00193         finder=finder->next;
00194     }
00195 #if CORE_DEBUG
00196     ee_printf("List sort 2: %04x\n",retval);
00197 #endif
00198     return retval;
00199 }
00200 /* Function: core_list_init
00201     Initialize list with data.
00202 
00203     Parameters:
00204     blksize - Size of memory to be initialized.
00205     memblock - Pointer to memory block.
00206     seed -  Actual values chosen depend on the seed parameter.
00207         The seed parameter MUST be supplied from a source that cannot be determined at compile time
00208 
00209     Returns:
00210     Pointer to the head of the list.
00211 
00212 */
00213 list_head *core_list_init(ee_u32 blksize, list_head *memblock, ee_s16 seed) {
00214     /* calculated pointers for the list */
00215     ee_u32 per_item=16+sizeof(struct list_data_s);
00216     ee_u32 size=(blksize/per_item)-2; /* to accomodate systems with 64b pointers, and make sure same code is executed, set max list elements */
00217     list_head *memblock_end=memblock+size;
00218     list_data *datablock=(list_data *)(memblock_end);
00219     list_data *datablock_end=datablock+size;
00220     /* some useful variables */
00221     ee_u32 i;
00222     list_head *finder,*list=memblock;
00223     list_data info;
00224 
00225     /* create a fake items for the list head and tail */
00226     list->next=NULL;
00227     list->info=datablock;
00228     list->info->idx=0x0000;
00229     list->info->data16=(ee_s16)0x8080;
00230     memblock++;
00231     datablock++;
00232     info.idx=0x7fff;
00233     info.data16=(ee_s16)0xffff;
00234     core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
00235     
00236     /* then insert size items */
00237     for (i=0; i<size; i++) {
00238         ee_u16 datpat=((ee_u16)(seed^i) & 0xf);
00239         ee_u16 dat=(datpat<<3) | (i&0x7); /* alternate between algorithms */
00240         info.data16=(dat<<8) | dat;     /* fill the data with actual data and upper bits with rebuild value */
00241         core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
00242     }
00243     /* and now index the list so we know initial seed order of the list */
00244     finder=list->next;
00245     i=1;
00246     while (finder->next!=NULL) {
00247         if (i<size/5) /* first 20% of the list in order */
00248             finder->info->idx=i++;
00249         else { 
00250             ee_u16 pat=(ee_u16)(i++ ^ seed); /* get a pseudo random number */
00251             finder->info->idx=0x3fff & (((i & 0x07) << 8) | pat); /* make sure the mixed items end up after the ones in sequence */
00252         }
00253         finder=finder->next;
00254     }
00255     list = core_list_mergesort(list,cmp_idx,NULL);
00256 #if CORE_DEBUG
00257     ee_printf("Initialized list:\n");
00258     finder=list;
00259     while (finder) {
00260         ee_printf("[%04x,%04x]",finder->info->idx,(ee_u16)finder->info->data16);
00261         finder=finder->next;
00262     }
00263     ee_printf("\n");
00264 #endif
00265     return list;
00266 }
00267 
00268 /* Function: core_list_insert
00269     Insert an item to the list
00270 
00271     Parameters:
00272     insert_point - where to insert the item.
00273     info - data for the cell.
00274     memblock - pointer for the list header
00275     datablock - pointer for the list data
00276     memblock_end - end of region for list headers
00277     datablock_end - end of region for list data
00278 
00279     Returns:
00280     Pointer to new item.
00281 */
00282 list_head *core_list_insert_new(list_head *insert_point, list_data *info, list_head **memblock, list_data **datablock
00283     , list_head *memblock_end, list_data *datablock_end) {
00284     list_head *newitem;
00285     
00286     if ((*memblock+1) >= memblock_end)
00287         return NULL;
00288     if ((*datablock+1) >= datablock_end)
00289         return NULL;
00290         
00291     newitem=*memblock;
00292     (*memblock)++;
00293     newitem->next=insert_point->next;
00294     insert_point->next=newitem;
00295     
00296     newitem->info=*datablock;
00297     (*datablock)++;
00298     copy_info(newitem->info,info);
00299     
00300     return newitem;
00301 }
00302 
00303 /* Function: core_list_remove
00304     Remove an item from the list.
00305 
00306     Operation:
00307     For a singly linked list, remove by copying the data from the next item 
00308     over to the current cell, and unlinking the next item.
00309 
00310     Note: 
00311     since there is always a fake item at the end of the list, no need to check for NULL.
00312 
00313     Returns:
00314     Removed item.
00315 */
00316 list_head *core_list_remove(list_head *item) {
00317     list_data *tmp;
00318     list_head *ret=item->next;
00319     /* swap data pointers */
00320     tmp=item->info;
00321     item->info=ret->info;
00322     ret->info=tmp;
00323     /* and eliminate item */
00324     item->next=item->next->next;
00325     ret->next=NULL;
00326     return ret;
00327 }
00328 
00329 /* Function: core_list_undo_remove
00330     Undo a remove operation.
00331 
00332     Operation:
00333     Since we want each iteration of the benchmark to be exactly the same,
00334     we need to be able to undo a remove. 
00335     Link the removed item back into the list, and switch the info items.
00336 
00337     Parameters:
00338     item_removed - Return value from the <core_list_remove>
00339     item_modified - List item that was modified during <core_list_remove>
00340 
00341     Returns:
00342     The item that was linked back to the list.
00343     
00344 */
00345 list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified) {
00346     list_data *tmp;
00347     /* swap data pointers */
00348     tmp=item_removed->info;
00349     item_removed->info=item_modified->info;
00350     item_modified->info=tmp;
00351     /* and insert item */
00352     item_removed->next=item_modified->next;
00353     item_modified->next=item_removed;
00354     return item_removed;
00355 }
00356 
00357 /* Function: core_list_find
00358     Find an item in the list
00359 
00360     Operation:
00361     Find an item by idx (if not 0) or specific data value
00362 
00363     Parameters:
00364     list - list head
00365     info - idx or data to find
00366 
00367     Returns:
00368     Found item, or NULL if not found.
00369 */
00370 list_head *core_list_find(list_head *list,list_data *info) {
00371     if (info->idx>=0) {
00372         while (list && (list->info->idx != info->idx))
00373             list=list->next;
00374         return list;
00375     } else {
00376         while (list && ((list->info->data16 & 0xff) != info->data16))
00377             list=list->next;
00378         return list;
00379     }
00380 }
00381 /* Function: core_list_reverse
00382     Reverse a list
00383 
00384     Operation:
00385     Rearrange the pointers so the list is reversed.
00386 
00387     Parameters:
00388     list - list head
00389     info - idx or data to find
00390 
00391     Returns:
00392     Found item, or NULL if not found.
00393 */
00394 
00395 list_head *core_list_reverse(list_head *list) {
00396     list_head *next=NULL, *tmp;
00397     while (list) {
00398         tmp=list->next;
00399         list->next=next;
00400         next=list;
00401         list=tmp;
00402     }
00403     return next;
00404 }
00405 /* Function: core_list_mergesort
00406     Sort the list in place without recursion.
00407 
00408     Description:
00409     Use mergesort, as for linked list this is a realistic solution. 
00410     Also, since this is aimed at embedded, care was taken to use iterative rather then recursive algorithm.
00411     The sort can either return the list to original order (by idx) ,
00412     or use the data item to invoke other other algorithms and change the order of the list.
00413 
00414     Parameters:
00415     list - list to be sorted.
00416     cmp - cmp function to use
00417 
00418     Returns:
00419     New head of the list.
00420 
00421     Note: 
00422     We have a special header for the list that will always be first,
00423     but the algorithm could theoretically modify where the list starts.
00424 
00425  */
00426 list_head *core_list_mergesort(list_head *list, list_cmp cmp, core_results *res) {
00427     list_head *p, *q, *e, *tail;
00428     ee_s32 insize, nmerges, psize, qsize, i;
00429 
00430     insize = 1;
00431 
00432     while (1) {
00433         p = list;
00434         list = NULL;
00435         tail = NULL;
00436 
00437         nmerges = 0;  /* count number of merges we do in this pass */
00438 
00439         while (p) {
00440             nmerges++;  /* there exists a merge to be done */
00441             /* step `insize' places along from p */
00442             q = p;
00443             psize = 0;
00444             for (i = 0; i < insize; i++) {
00445                 psize++;
00446                 q = q->next;
00447                 if (!q) break;
00448             }
00449 
00450             /* if q hasn't fallen off end, we have two lists to merge */
00451             qsize = insize;
00452 
00453             /* now we have two lists; merge them */
00454             while (psize > 0 || (qsize > 0 && q)) {
00455 
00456                 /* decide whether next element of merge comes from p or q */
00457                 if (psize == 0) {
00458                     /* p is empty; e must come from q. */
00459                     e = q; q = q->next; qsize--;
00460                 } else if (qsize == 0 || !q) {
00461                     /* q is empty; e must come from p. */
00462                     e = p; p = p->next; psize--;
00463                 } else if (cmp(p->info,q->info,res) <= 0) {
00464                     /* First element of p is lower (or same); e must come from p. */
00465                     e = p; p = p->next; psize--;
00466                 } else {
00467                     /* First element of q is lower; e must come from q. */
00468                     e = q; q = q->next; qsize--;
00469                 }
00470 
00471                 /* add the next element to the merged list */
00472                 if (tail) {
00473                     tail->next = e;
00474                 } else {
00475                     list = e;
00476                 }
00477                 tail = e;
00478             }
00479 
00480             /* now p has stepped `insize' places along, and q has too */
00481             p = q;
00482         }
00483         
00484         tail->next = NULL;
00485 
00486         /* If we have done only one merge, we're finished. */
00487         if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
00488             return list;
00489 
00490         /* Otherwise repeat, merging lists twice the size */
00491         insize *= 2;
00492     }
00493 #if COMPILER_REQUIRES_SORT_RETURN
00494     return list;
00495 #endif
00496 }