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

Subversion Repositories neorv32

[/] [neorv32/] [trunk/] [sw/] [example/] [coremark/] [core_list_join.c] - Blame information for rev 3

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 2 zero_gravi
/*
2
Copyright 2018 Embedded Microprocessor Benchmark Consortium (EEMBC)
3
 
4
Licensed under the Apache License, Version 2.0 (the "License");
5
you may not use this file except in compliance with the License.
6
You may obtain a copy of the License at
7
 
8
    http://www.apache.org/licenses/LICENSE-2.0
9
 
10
Unless required by applicable law or agreed to in writing, software
11
distributed under the License is distributed on an "AS IS" BASIS,
12
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
See the License for the specific language governing permissions and
14
limitations under the License.
15
 
16
Original Author: Shay Gal-on
17
*/
18
 
19
#include "coremark.h"
20
/*
21
Topic: Description
22
        Benchmark using a linked list.
23
 
24
        Linked list is a common data structure used in many applications.
25
 
26
        For our purposes, this will excercise the memory units of the processor.
27
        In particular, usage of the list pointers to find and alter data.
28
 
29
        We are not using Malloc since some platforms do not support this library.
30
 
31
        Instead, the memory block being passed in is used to create a list,
32
        and the benchmark takes care not to add more items then can be
33
        accomodated by the memory block. The porting layer will make sure
34
        that we have a valid memory block.
35
 
36
        All operations are done in place, without using any extra memory.
37
 
38
        The list itself contains list pointers and pointers to data items.
39
        Data items contain the following:
40
 
41
        idx - An index that captures the initial order of the list.
42
        data - Variable data initialized based on the input parameters. The 16b are divided as follows:
43
        o Upper 8b are backup of original data.
44
        o Bit 7 indicates if the lower 7 bits are to be used as is or calculated.
45
        o Bits 0-2 indicate type of operation to perform to get a 7b value.
46
        o Bits 3-6 provide input for the operation.
47
 
48
*/
49
 
50
/* local functions */
51
 
52
list_head *core_list_find(list_head *list,list_data *info);
53
list_head *core_list_reverse(list_head *list);
54
list_head *core_list_remove(list_head *item);
55
list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified);
56
list_head *core_list_insert_new(list_head *insert_point
57
        , list_data *info, list_head **memblock, list_data **datablock
58
        , list_head *memblock_end, list_data *datablock_end);
59
typedef ee_s32(*list_cmp)(list_data *a, list_data *b, core_results *res);
60
list_head *core_list_mergesort(list_head *list, list_cmp cmp, core_results *res);
61
 
62
ee_s16 calc_func(ee_s16 *pdata, core_results *res) {
63
        ee_s16 data=*pdata;
64
        ee_s16 retval;
65
        ee_u8 optype=(data>>7) & 1; /* bit 7 indicates if the function result has been cached */
66
        if (optype) /* if cached, use cache */
67
                return (data & 0x007f);
68
        else { /* otherwise calculate and cache the result */
69
                ee_s16 flag=data & 0x7; /* bits 0-2 is type of function to perform */
70
                ee_s16 dtype=((data>>3) & 0xf); /* bits 3-6 is specific data for the operation */
71
                dtype |= dtype << 4; /* replicate the lower 4 bits to get an 8b value */
72
                switch (flag) {
73
                        case 0:
74
                                if (dtype<0x22) /* set min period for bit corruption */
75
                                        dtype=0x22;
76
                                retval=core_bench_state(res->size,res->memblock[3],res->seed1,res->seed2,dtype,res->crc);
77
                                if (res->crcstate==0)
78
                                        res->crcstate=retval;
79
                                break;
80
                        case 1:
81
                                retval=core_bench_matrix(&(res->mat),dtype,res->crc);
82
                                if (res->crcmatrix==0)
83
                                        res->crcmatrix=retval;
84
                                break;
85
                        default:
86
                                retval=data;
87
                                break;
88
                }
89
                res->crc=crcu16(retval,res->crc);
90
                retval &= 0x007f;
91
                *pdata = (data & 0xff00) | 0x0080 | retval; /* cache the result */
92
                return retval;
93
        }
94
}
95
/* Function: cmp_complex
96
        Compare the data item in a list cell.
97
 
98
        Can be used by mergesort.
99
*/
100
ee_s32 cmp_complex(list_data *a, list_data *b, core_results *res) {
101
        ee_s16 val1=calc_func(&(a->data16),res);
102
        ee_s16 val2=calc_func(&(b->data16),res);
103
        return val1 - val2;
104
}
105
 
106
/* Function: cmp_idx
107
        Compare the idx item in a list cell, and regen the data.
108
 
109
        Can be used by mergesort.
110
*/
111
ee_s32 cmp_idx(list_data *a, list_data *b, core_results *res) {
112
        if (res==NULL) {
113
                a->data16 = (a->data16 & 0xff00) | (0x00ff & (a->data16>>8));
114
                b->data16 = (b->data16 & 0xff00) | (0x00ff & (b->data16>>8));
115
        }
116
        return a->idx - b->idx;
117
}
118
 
119
void copy_info(list_data *to,list_data *from) {
120
        to->data16=from->data16;
121
        to->idx=from->idx;
122
}
123
 
124
/* Benchmark for linked list:
125
        - Try to find multiple data items.
126
        - List sort
127
        - Operate on data from list (crc)
128
        - Single remove/reinsert
129
        * At the end of this function, the list is back to original state
130
*/
131
ee_u16 core_bench_list(core_results *res, ee_s16 finder_idx) {
132
        ee_u16 retval=0;
133
        ee_u16 found=0,missed=0;
134
        list_head *list=res->list;
135
        ee_s16 find_num=res->seed3;
136
        list_head *this_find;
137
        list_head *finder, *remover;
138
        list_data info;
139
        ee_s16 i;
140
 
141
        info.idx=finder_idx;
142
        /* find <find_num> values in the list, and change the list each time (reverse and cache if value found) */
143
        for (i=0; i<find_num; i++) {
144
                info.data16= (i & 0xff) ;
145
                this_find=core_list_find(list,&info);
146
                list=core_list_reverse(list);
147
                if (this_find==NULL) {
148
                        missed++;
149
                        retval+=(list->next->info->data16 >> 8) & 1;
150
                }
151
                else {
152
                        found++;
153
                        if (this_find->info->data16 & 0x1) /* use found value */
154
                                retval+=(this_find->info->data16 >> 9) & 1;
155
                        /* and cache next item at the head of the list (if any) */
156
                        if (this_find->next != NULL) {
157
                                finder = this_find->next;
158
                                this_find->next = finder->next;
159
                                finder->next=list->next;
160
                                list->next=finder;
161
                        }
162
                }
163
                if (info.idx>=0)
164
                        info.idx++;
165
#if CORE_DEBUG
166
        ee_printf("List find %d: [%d,%d,%d]\n",i,retval,missed,found);
167
#endif
168
        }
169
        retval+=found*4-missed;
170
        /* sort the list by data content and remove one item*/
171
        if (finder_idx>0)
172
                list=core_list_mergesort(list,cmp_complex,res);
173
        remover=core_list_remove(list->next);
174
        /* CRC data content of list from location of index N forward, and then undo remove */
175
        finder=core_list_find(list,&info);
176
        if (!finder)
177
                finder=list->next;
178
        while (finder) {
179
                retval=crc16(list->info->data16,retval);
180
                finder=finder->next;
181
        }
182
#if CORE_DEBUG
183
        ee_printf("List sort 1: %04x\n",retval);
184
#endif
185
        remover=core_list_undo_remove(remover,list->next);
186
        /* sort the list by index, in effect returning the list to original state */
187
        list=core_list_mergesort(list,cmp_idx,NULL);
188
        /* CRC data content of list */
189
        finder=list->next;
190
        while (finder) {
191
                retval=crc16(list->info->data16,retval);
192
                finder=finder->next;
193
        }
194
#if CORE_DEBUG
195
        ee_printf("List sort 2: %04x\n",retval);
196
#endif
197
        return retval;
198
}
199
/* Function: core_list_init
200
        Initialize list with data.
201
 
202
        Parameters:
203
        blksize - Size of memory to be initialized.
204
        memblock - Pointer to memory block.
205
        seed -  Actual values chosen depend on the seed parameter.
206
                The seed parameter MUST be supplied from a source that cannot be determined at compile time
207
 
208
        Returns:
209
        Pointer to the head of the list.
210
 
211
*/
212
list_head *core_list_init(ee_u32 blksize, list_head *memblock, ee_s16 seed) {
213
        /* calculated pointers for the list */
214
        ee_u32 per_item=16+sizeof(struct list_data_s);
215
        ee_u32 size=(blksize/per_item)-2; /* to accomodate systems with 64b pointers, and make sure same code is executed, set max list elements */
216
        list_head *memblock_end=memblock+size;
217
        list_data *datablock=(list_data *)(memblock_end);
218
        list_data *datablock_end=datablock+size;
219
        /* some useful variables */
220
        ee_u32 i;
221
        list_head *finder,*list=memblock;
222
        list_data info;
223
 
224
        /* create a fake items for the list head and tail */
225
        list->next=NULL;
226
        list->info=datablock;
227
        list->info->idx=0x0000;
228
        list->info->data16=(ee_s16)0x8080;
229
        memblock++;
230
        datablock++;
231
        info.idx=0x7fff;
232
        info.data16=(ee_s16)0xffff;
233
        core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
234
 
235
        /* then insert size items */
236
        for (i=0; i<size; i++) {
237
                ee_u16 datpat=((ee_u16)(seed^i) & 0xf);
238
                ee_u16 dat=(datpat<<3) | (i&0x7); /* alternate between algorithms */
239
                info.data16=(dat<<8) | dat;             /* fill the data with actual data and upper bits with rebuild value */
240
                core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
241
        }
242
        /* and now index the list so we know initial seed order of the list */
243
        finder=list->next;
244
        i=1;
245
        while (finder->next!=NULL) {
246
                if (i<size/5) /* first 20% of the list in order */
247
                        finder->info->idx=i++;
248
                else {
249
                        ee_u16 pat=(ee_u16)(i++ ^ seed); /* get a pseudo random number */
250
                        finder->info->idx=0x3fff & (((i & 0x07) << 8) | pat); /* make sure the mixed items end up after the ones in sequence */
251
                }
252
                finder=finder->next;
253
        }
254
        list = core_list_mergesort(list,cmp_idx,NULL);
255
#if CORE_DEBUG
256
        ee_printf("Initialized list:\n");
257
        finder=list;
258
        while (finder) {
259
                ee_printf("[%04x,%04x]",finder->info->idx,(ee_u16)finder->info->data16);
260
                finder=finder->next;
261
        }
262
        ee_printf("\n");
263
#endif
264
        return list;
265
}
266
 
267
/* Function: core_list_insert
268
        Insert an item to the list
269
 
270
        Parameters:
271
        insert_point - where to insert the item.
272
        info - data for the cell.
273
        memblock - pointer for the list header
274
        datablock - pointer for the list data
275
        memblock_end - end of region for list headers
276
        datablock_end - end of region for list data
277
 
278
        Returns:
279
        Pointer to new item.
280
*/
281
list_head *core_list_insert_new(list_head *insert_point, list_data *info, list_head **memblock, list_data **datablock
282
        , list_head *memblock_end, list_data *datablock_end) {
283
        list_head *newitem;
284
 
285
        if ((*memblock+1) >= memblock_end)
286
                return NULL;
287
        if ((*datablock+1) >= datablock_end)
288
                return NULL;
289
 
290
        newitem=*memblock;
291
        (*memblock)++;
292
        newitem->next=insert_point->next;
293
        insert_point->next=newitem;
294
 
295
        newitem->info=*datablock;
296
        (*datablock)++;
297
        copy_info(newitem->info,info);
298
 
299
        return newitem;
300
}
301
 
302
/* Function: core_list_remove
303
        Remove an item from the list.
304
 
305
        Operation:
306
        For a singly linked list, remove by copying the data from the next item
307
        over to the current cell, and unlinking the next item.
308
 
309
        Note:
310
        since there is always a fake item at the end of the list, no need to check for NULL.
311
 
312
        Returns:
313
        Removed item.
314
*/
315
list_head *core_list_remove(list_head *item) {
316
        list_data *tmp;
317
        list_head *ret=item->next;
318
        /* swap data pointers */
319
        tmp=item->info;
320
        item->info=ret->info;
321
        ret->info=tmp;
322
        /* and eliminate item */
323
        item->next=item->next->next;
324
        ret->next=NULL;
325
        return ret;
326
}
327
 
328
/* Function: core_list_undo_remove
329
        Undo a remove operation.
330
 
331
        Operation:
332
        Since we want each iteration of the benchmark to be exactly the same,
333
        we need to be able to undo a remove.
334
        Link the removed item back into the list, and switch the info items.
335
 
336
        Parameters:
337
        item_removed - Return value from the <core_list_remove>
338
        item_modified - List item that was modified during <core_list_remove>
339
 
340
        Returns:
341
        The item that was linked back to the list.
342
 
343
*/
344
list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified) {
345
        list_data *tmp;
346
        /* swap data pointers */
347
        tmp=item_removed->info;
348
        item_removed->info=item_modified->info;
349
        item_modified->info=tmp;
350
        /* and insert item */
351
        item_removed->next=item_modified->next;
352
        item_modified->next=item_removed;
353
        return item_removed;
354
}
355
 
356
/* Function: core_list_find
357
        Find an item in the list
358
 
359
        Operation:
360
        Find an item by idx (if not 0) or specific data value
361
 
362
        Parameters:
363
        list - list head
364
        info - idx or data to find
365
 
366
        Returns:
367
        Found item, or NULL if not found.
368
*/
369
list_head *core_list_find(list_head *list,list_data *info) {
370
        if (info->idx>=0) {
371
                while (list && (list->info->idx != info->idx))
372
                        list=list->next;
373
                return list;
374
        } else {
375
                while (list && ((list->info->data16 & 0xff) != info->data16))
376
                        list=list->next;
377
                return list;
378
        }
379
}
380
/* Function: core_list_reverse
381
        Reverse a list
382
 
383
        Operation:
384
        Rearrange the pointers so the list is reversed.
385
 
386
        Parameters:
387
        list - list head
388
        info - idx or data to find
389
 
390
        Returns:
391
        Found item, or NULL if not found.
392
*/
393
 
394
list_head *core_list_reverse(list_head *list) {
395
        list_head *next=NULL, *tmp;
396
        while (list) {
397
                tmp=list->next;
398
                list->next=next;
399
                next=list;
400
                list=tmp;
401
        }
402
        return next;
403
}
404
/* Function: core_list_mergesort
405
        Sort the list in place without recursion.
406
 
407
        Description:
408
        Use mergesort, as for linked list this is a realistic solution.
409
        Also, since this is aimed at embedded, care was taken to use iterative rather then recursive algorithm.
410
        The sort can either return the list to original order (by idx) ,
411
        or use the data item to invoke other other algorithms and change the order of the list.
412
 
413
        Parameters:
414
        list - list to be sorted.
415
        cmp - cmp function to use
416
 
417
        Returns:
418
        New head of the list.
419
 
420
        Note:
421
        We have a special header for the list that will always be first,
422
        but the algorithm could theoretically modify where the list starts.
423
 
424
 */
425
list_head *core_list_mergesort(list_head *list, list_cmp cmp, core_results *res) {
426
    list_head *p, *q, *e, *tail;
427
    ee_s32 insize, nmerges, psize, qsize, i;
428
 
429
    insize = 1;
430
 
431
    while (1) {
432
        p = list;
433
        list = NULL;
434
        tail = NULL;
435
 
436
        nmerges = 0;  /* count number of merges we do in this pass */
437
 
438
        while (p) {
439
            nmerges++;  /* there exists a merge to be done */
440
            /* step `insize' places along from p */
441
            q = p;
442
            psize = 0;
443
            for (i = 0; i < insize; i++) {
444
                psize++;
445
                            q = q->next;
446
                if (!q) break;
447
            }
448
 
449
            /* if q hasn't fallen off end, we have two lists to merge */
450
            qsize = insize;
451
 
452
            /* now we have two lists; merge them */
453
            while (psize > 0 || (qsize > 0 && q)) {
454
 
455
                                /* decide whether next element of merge comes from p or q */
456
                                if (psize == 0) {
457
                                    /* p is empty; e must come from q. */
458
                                    e = q; q = q->next; qsize--;
459
                                } else if (qsize == 0 || !q) {
460
                                    /* q is empty; e must come from p. */
461
                                    e = p; p = p->next; psize--;
462
                                } else if (cmp(p->info,q->info,res) <= 0) {
463
                                    /* First element of p is lower (or same); e must come from p. */
464
                                    e = p; p = p->next; psize--;
465
                                } else {
466
                                    /* First element of q is lower; e must come from q. */
467
                                    e = q; q = q->next; qsize--;
468
                                }
469
 
470
                        /* add the next element to the merged list */
471
                                if (tail) {
472
                                    tail->next = e;
473
                                } else {
474
                                    list = e;
475
                                }
476
                                tail = e;
477
                }
478
 
479
                        /* now p has stepped `insize' places along, and q has too */
480
                        p = q;
481
        }
482
 
483
            tail->next = NULL;
484
 
485
        /* If we have done only one merge, we're finished. */
486
        if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
487
            return list;
488
 
489
        /* Otherwise repeat, merging lists twice the size */
490
        insize *= 2;
491
    }
492
#if COMPILER_REQUIRES_SORT_RETURN
493
        return list;
494
#endif
495
}

powered by: WebSVN 2.1.0

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