OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [bootloaders/] [orpmon/] [coremark/] [core_list_join.c] - Diff between revs 355 and 406

Go to most recent revision | Show entire file | Details | Blame | View Log

Rev 355 Rev 406
Line 51... Line 51...
/* local functions */
/* local functions */
 
 
list_head *core_list_find(list_head *list,list_data *info);
list_head *core_list_find(list_head *list,list_data *info);
list_head *core_list_reverse(list_head *list);
list_head *core_list_reverse(list_head *list);
list_head *core_list_remove(list_head *item);
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_undo_remove(list_head * item_removed,
list_head *core_list_insert_new(list_head *insert_point
                                 list_head * item_modified);
        , list_data *info, list_head **memblock, list_data **datablock
list_head *core_list_insert_new(list_head * insert_point, list_data * info,
        , list_head *memblock_end, list_data *datablock_end);
                                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);
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);
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 calc_func(ee_s16 * pdata, core_results * res)
        ee_s16 data=*pdata;
{
 
        ee_s16 data = *pdata;
        ee_s16 retval;
        ee_s16 retval;
        ee_u8 optype=(data>>7) & 1; /* bit 7 indicates if the function result has been cached */
        ee_u8 optype=(data>>7) & 1; /* bit 7 indicates if the function result has been cached */
        if (optype) /* if cached, use cache */
        if (optype) /* if cached, use cache */
                return (data & 0x007f);
                return (data & 0x007f);
        else { /* otherwise calculate and cache the result */
        else { /* otherwise calculate and cache the result */
Line 72... Line 76...
                dtype |= dtype << 4; /* replicate the lower 4 bits to get an 8b value */
                dtype |= dtype << 4; /* replicate the lower 4 bits to get an 8b value */
                switch (flag) {
                switch (flag) {
                        case 0:
                        case 0:
                                if (dtype<0x22) /* set min period for bit corruption */
                                if (dtype<0x22) /* set min period for bit corruption */
                                        dtype=0x22;
                                        dtype=0x22;
                                retval=core_bench_state(res->size,res->memblock[3],res->seed1,res->seed2,dtype,res->crc);
                        retval =
 
                            core_bench_state(res->size, res->memblock[3],
 
                                             res->seed1, res->seed2, dtype,
 
                                             res->crc);
                                if (res->crcstate==0)
                                if (res->crcstate==0)
                                        res->crcstate=retval;
                                        res->crcstate=retval;
                                break;
                                break;
                        case 1:
                        case 1:
                                retval=core_bench_matrix(&(res->mat),dtype,res->crc);
                        retval =
 
                            core_bench_matrix(&(res->mat), dtype, res->crc);
                                if (res->crcmatrix==0)
                                if (res->crcmatrix==0)
                                        res->crcmatrix=retval;
                                        res->crcmatrix=retval;
                                break;
                                break;
                        default:
                        default:
                                retval=data;
                                retval=data;
Line 91... Line 99...
                retval &= 0x007f;
                retval &= 0x007f;
                *pdata = (data & 0xff00) | 0x0080 | retval; /* cache the result */
                *pdata = (data & 0xff00) | 0x0080 | retval; /* cache the result */
                return retval;
                return retval;
        }
        }
}
}
 
 
/* Function: cmp_complex
/* Function: cmp_complex
        Compare the data item in a list cell.
        Compare the data item in a list cell.
 
 
        Can be used by mergesort.
        Can be used by mergesort.
*/
*/
ee_s32 cmp_complex(list_data *a, list_data *b, core_results *res) {
ee_s32 cmp_complex(list_data * a, list_data * b, core_results * res)
 
{
        ee_s16 val1=calc_func(&(a->data16),res);
        ee_s16 val1=calc_func(&(a->data16),res);
        ee_s16 val2=calc_func(&(b->data16),res);
        ee_s16 val2=calc_func(&(b->data16),res);
        return val1 - val2;
        return val1 - val2;
}
}
 
 
/* Function: cmp_idx
/* Function: cmp_idx
        Compare the idx item in a list cell, and regen the data.
        Compare the idx item in a list cell, and regen the data.
 
 
        Can be used by mergesort.
        Can be used by mergesort.
*/
*/
ee_s32 cmp_idx(list_data *a, list_data *b, core_results *res) {
ee_s32 cmp_idx(list_data * a, list_data * b, core_results * res)
 
{
        if (res==NULL) {
        if (res==NULL) {
                a->data16 = (a->data16 & 0xff00) | (0x00ff & (a->data16>>8));
                a->data16 = (a->data16 & 0xff00) | (0x00ff & (a->data16>>8));
                b->data16 = (b->data16 & 0xff00) | (0x00ff & (b->data16>>8));
                b->data16 = (b->data16 & 0xff00) | (0x00ff & (b->data16>>8));
        }
        }
        return a->idx - b->idx;
        return a->idx - b->idx;
}
}
 
 
void copy_info(list_data *to,list_data *from) {
void copy_info(list_data * to, list_data * from)
 
{
        to->data16=from->data16;
        to->data16=from->data16;
        to->idx=from->idx;
        to->idx=from->idx;
}
}
 
 
/* Benchmark for linked list:
/* Benchmark for linked list:
Line 127... Line 139...
        - List sort
        - List sort
        - Operate on data from list (crc)
        - Operate on data from list (crc)
        - Single remove/reinsert
        - Single remove/reinsert
        * At the end of this function, the list is back to original state
        * 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 core_bench_list(core_results * res, ee_s16 finder_idx)
 
{
        ee_u16 retval=0;
        ee_u16 retval=0;
        ee_u16 found=0,missed=0;
        ee_u16 found=0,missed=0;
        list_head *list=res->list;
        list_head *list=res->list;
        ee_s16 find_num=res->seed3;
        ee_s16 find_num=res->seed3;
        list_head *this_find;
        list_head *this_find;
Line 141... Line 154...
 
 
        info.idx=finder_idx;
        info.idx=finder_idx;
        /* find <find_num> values in the list, and change the list each time (reverse and cache if value found) */
        /* 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++) {
        for (i=0; i<find_num; i++) {
                info.data16= (i & 0xff) ;
                info.data16= (i & 0xff) ;
                this_find=core_list_find(list,&info);
                this_find = core_list_find(list, &info);
                list=core_list_reverse(list);
                list=core_list_reverse(list);
                if (this_find==NULL) {
                if (this_find==NULL) {
                        missed++;
                        missed++;
                        retval+=(list->next->info->data16 >> 8) & 1;
                        retval+=(list->next->info->data16 >> 8) & 1;
                }
                } else {
                else {
 
                        found++;
                        found++;
                        if (this_find->info->data16 & 0x1) /* use found value */
                        if (this_find->info->data16 & 0x1) /* use found value */
                                retval+=(this_find->info->data16 >> 9) & 1;
                                retval+=(this_find->info->data16 >> 9) & 1;
                        /* and cache next item at the head of the list (if any) */
                        /* and cache next item at the head of the list (if any) */
                        if (this_find->next != NULL) {
                        if (this_find->next != NULL) {
Line 162... Line 174...
                        }
                        }
                }
                }
                if (info.idx>=0)
                if (info.idx>=0)
                        info.idx++;
                        info.idx++;
#if CORE_DEBUG
#if CORE_DEBUG
        ee_printf("List find %d: [%d,%d,%d]\n",i,retval,missed,found);
                ee_printf("List find %d: [%d,%d,%d]\n", i, retval, missed,
 
                          found);
#endif
#endif
        }
        }
        retval+=found*4-missed;
        retval+=found*4-missed;
        /* sort the list by data content and remove one item*/
        /* sort the list by data content and remove one item*/
        if (finder_idx>0)
        if (finder_idx>0)
                list=core_list_mergesort(list,cmp_complex,res);
                list=core_list_mergesort(list,cmp_complex,res);
        remover=core_list_remove(list->next);
        remover=core_list_remove(list->next);
        /* CRC data content of list from location of index N forward, and then undo remove */
        /* CRC data content of list from location of index N forward, and then undo remove */
        finder=core_list_find(list,&info);
        finder = core_list_find(list, &info);
        if (!finder)
        if (!finder)
                finder=list->next;
                finder=list->next;
        while (finder) {
        while (finder) {
                retval=crc16(list->info->data16,retval);
                retval=crc16(list->info->data16,retval);
                finder=finder->next;
                finder=finder->next;
Line 195... Line 208...
#if CORE_DEBUG
#if CORE_DEBUG
        ee_printf("List sort 2: %04x\n",retval);
        ee_printf("List sort 2: %04x\n",retval);
#endif
#endif
        return retval;
        return retval;
}
}
 
 
/* Function: core_list_init
/* Function: core_list_init
        Initialize list with data.
        Initialize list with data.
 
 
        Parameters:
        Parameters:
        blksize - Size of memory to be initialized.
        blksize - Size of memory to be initialized.
Line 208... Line 222...
 
 
        Returns:
        Returns:
        Pointer to the head of the list.
        Pointer to the head of the list.
 
 
*/
*/
list_head *core_list_init(ee_u32 blksize, list_head *memblock, ee_s16 seed) {
list_head *core_list_init(ee_u32 blksize, list_head * memblock, ee_s16 seed)
 
{
        /* calculated pointers for the list */
        /* calculated pointers for the list */
        ee_u32 per_item=16+sizeof(struct list_data_s);
        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 */
        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_head *memblock_end=memblock+size;
        list_data *datablock=(list_data *)(memblock_end);
        list_data *datablock=(list_data *)(memblock_end);
        list_data *datablock_end=datablock+size;
        list_data *datablock_end=datablock+size;
        /* some useful variables */
        /* some useful variables */
        ee_u32 i;
        ee_u32 i;
        list_head *finder,*list=memblock;
        list_head *finder, *list = memblock;
        list_data info;
        list_data info;
 
 
        /* create a fake items for the list head and tail */
        /* create a fake items for the list head and tail */
        list->next=NULL;
        list->next=NULL;
        list->info=datablock;
        list->info=datablock;
Line 229... Line 244...
        list->info->data16=(ee_s16)0x8080;
        list->info->data16=(ee_s16)0x8080;
        memblock++;
        memblock++;
        datablock++;
        datablock++;
        info.idx=0x7fff;
        info.idx=0x7fff;
        info.data16=(ee_s16)0xffff;
        info.data16=(ee_s16)0xffff;
        core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
        core_list_insert_new(list, &info, &memblock, &datablock, memblock_end,
 
                             datablock_end);
 
 
        /* then insert size items */
        /* then insert size items */
        for (i=0; i<size; i++) {
        for (i=0; i<size; i++) {
                ee_u16 datpat=((ee_u16)(seed^i) & 0xf);
                ee_u16 datpat=((ee_u16)(seed^i) & 0xf);
                ee_u16 dat=(datpat<<3) | (i&0x7); /* alternate between algorithms */
                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 */
                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);
                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 */
        /* and now index the list so we know initial seed order of the list */
        finder=list->next;
        finder=list->next;
        i=1;
        i=1;
        while (finder->next!=NULL) {
        while (finder->next!=NULL) {
Line 255... Line 272...
        list = core_list_mergesort(list,cmp_idx,NULL);
        list = core_list_mergesort(list,cmp_idx,NULL);
#if CORE_DEBUG
#if CORE_DEBUG
        ee_printf("Initialized list:\n");
        ee_printf("Initialized list:\n");
        finder=list;
        finder=list;
        while (finder) {
        while (finder) {
                ee_printf("[%04x,%04x]",finder->info->idx,(ee_u16)finder->info->data16);
                ee_printf("[%04x,%04x]", finder->info->idx,
 
                          (ee_u16) finder->info->data16);
                finder=finder->next;
                finder=finder->next;
        }
        }
        ee_printf("\n");
        ee_printf("\n");
#endif
#endif
        return list;
        return list;
Line 277... Line 295...
        datablock_end - end of region for list data
        datablock_end - end of region for list data
 
 
        Returns:
        Returns:
        Pointer to new item.
        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 *core_list_insert_new(list_head * insert_point, list_data * info,
        , list_head *memblock_end, list_data *datablock_end) {
                                list_head ** memblock, list_data ** datablock,
 
                                list_head * memblock_end,
 
                                list_data * datablock_end)
 
{
        list_head *newitem;
        list_head *newitem;
 
 
        if ((*memblock+1) >= memblock_end)
        if ((*memblock+1) >= memblock_end)
                return NULL;
                return NULL;
        if ((*datablock+1) >= datablock_end)
        if ((*datablock+1) >= datablock_end)
                return NULL;
                return NULL;
 
 
        newitem=*memblock;
        newitem = *memblock;
        (*memblock)++;
        (*memblock)++;
        newitem->next=insert_point->next;
        newitem->next=insert_point->next;
        insert_point->next=newitem;
        insert_point->next=newitem;
 
 
        newitem->info=*datablock;
        newitem->info = *datablock;
        (*datablock)++;
        (*datablock)++;
        copy_info(newitem->info,info);
        copy_info(newitem->info,info);
 
 
        return newitem;
        return newitem;
}
}
Line 311... Line 332...
        since there is always a fake item at the end of the list, no need to check for NULL.
        since there is always a fake item at the end of the list, no need to check for NULL.
 
 
        Returns:
        Returns:
        Removed item.
        Removed item.
*/
*/
list_head *core_list_remove(list_head *item) {
list_head *core_list_remove(list_head * item)
 
{
        list_data *tmp;
        list_data *tmp;
        list_head *ret=item->next;
        list_head *ret=item->next;
        /* swap data pointers */
        /* swap data pointers */
        tmp=item->info;
        tmp=item->info;
        item->info=ret->info;
        item->info=ret->info;
Line 340... Line 362...
 
 
        Returns:
        Returns:
        The item that was linked back to the list.
        The item that was linked back to the list.
 
 
*/
*/
list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified) {
list_head *core_list_undo_remove(list_head * item_removed,
 
                                 list_head * item_modified)
 
{
        list_data *tmp;
        list_data *tmp;
        /* swap data pointers */
        /* swap data pointers */
        tmp=item_removed->info;
        tmp=item_removed->info;
        item_removed->info=item_modified->info;
        item_removed->info=item_modified->info;
        item_modified->info=tmp;
        item_modified->info=tmp;
Line 365... Line 389...
        info - idx or data to find
        info - idx or data to find
 
 
        Returns:
        Returns:
        Found item, or NULL if not found.
        Found item, or NULL if not found.
*/
*/
list_head *core_list_find(list_head *list,list_data *info) {
list_head *core_list_find(list_head * list, list_data * info)
 
{
        if (info->idx>=0) {
        if (info->idx>=0) {
                while (list && (list->info->idx != info->idx))
                while (list && (list->info->idx != info->idx))
                        list=list->next;
                        list=list->next;
                return list;
                return list;
        } else {
        } else {
                while (list && ((list->info->data16 & 0xff) != info->data16))
                while (list && ((list->info->data16 & 0xff) != info->data16))
                        list=list->next;
                        list=list->next;
                return list;
                return list;
        }
        }
}
}
 
 
/* Function: core_list_reverse
/* Function: core_list_reverse
        Reverse a list
        Reverse a list
 
 
        Operation:
        Operation:
        Rearrange the pointers so the list is reversed.
        Rearrange the pointers so the list is reversed.
Line 390... Line 416...
 
 
        Returns:
        Returns:
        Found item, or NULL if not found.
        Found item, or NULL if not found.
*/
*/
 
 
list_head *core_list_reverse(list_head *list) {
list_head *core_list_reverse(list_head * list)
 
{
        list_head *next=NULL, *tmp;
        list_head *next=NULL, *tmp;
        while (list) {
        while (list) {
                tmp=list->next;
                tmp=list->next;
                list->next=next;
                list->next=next;
                next=list;
                next=list;
                list=tmp;
                list=tmp;
        }
        }
        return next;
        return next;
}
}
 
 
/* Function: core_list_mergesort
/* Function: core_list_mergesort
        Sort the list in place without recursion.
        Sort the list in place without recursion.
 
 
        Description:
        Description:
        Use mergesort, as for linked list this is a realistic solution.
        Use mergesort, as for linked list this is a realistic solution.
Line 421... Line 449...
        Note:
        Note:
        We have a special header for the list that will always be first,
        We have a special header for the list that will always be first,
        but the algorithm could theoretically modify where the list starts.
        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 *core_list_mergesort(list_head * list, list_cmp cmp,
 
                               core_results * res)
 
{
    list_head *p, *q, *e, *tail;
    list_head *p, *q, *e, *tail;
    ee_s32 insize, nmerges, psize, qsize, i;
    ee_s32 insize, nmerges, psize, qsize, i;
 
 
    insize = 1;
    insize = 1;
 
 
Line 442... Line 472...
            q = p;
            q = p;
            psize = 0;
            psize = 0;
            for (i = 0; i < insize; i++) {
            for (i = 0; i < insize; i++) {
                psize++;
                psize++;
                            q = q->next;
                            q = q->next;
                if (!q) break;
                                if (!q)
 
                                        break;
            }
            }
 
 
            /* if q hasn't fallen off end, we have two lists to merge */
            /* if q hasn't fallen off end, we have two lists to merge */
            qsize = insize;
            qsize = insize;
 
 
Line 454... Line 485...
            while (psize > 0 || (qsize > 0 && q)) {
            while (psize > 0 || (qsize > 0 && q)) {
 
 
                                /* decide whether next element of merge comes from p or q */
                                /* decide whether next element of merge comes from p or q */
                                if (psize == 0) {
                                if (psize == 0) {
                                    /* p is empty; e must come from q. */
                                    /* p is empty; e must come from q. */
                                    e = q; q = q->next; qsize--;
                                        e = q;
 
                                        q = q->next;
 
                                        qsize--;
                                } else if (qsize == 0 || !q) {
                                } else if (qsize == 0 || !q) {
                                    /* q is empty; e must come from p. */
                                    /* q is empty; e must come from p. */
                                    e = p; p = p->next; psize--;
                                        e = p;
 
                                        p = p->next;
 
                                        psize--;
                                } else if (cmp(p->info,q->info,res) <= 0) {
                                } else if (cmp(p->info,q->info,res) <= 0) {
                                    /* First element of p is lower (or same); e must come from p. */
                                    /* First element of p is lower (or same); e must come from p. */
                                    e = p; p = p->next; psize--;
                                        e = p;
 
                                        p = p->next;
 
                                        psize--;
                                } else {
                                } else {
                                    /* First element of q is lower; e must come from q. */
                                    /* First element of q is lower; e must come from q. */
                                    e = q; q = q->next; qsize--;
                                        e = q;
 
                                        q = q->next;
 
                                        qsize--;
                                }
                                }
 
 
                        /* add the next element to the merged list */
                        /* add the next element to the merged list */
                                if (tail) {
                                if (tail) {
                                    tail->next = e;
                                    tail->next = e;

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.