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

Subversion Repositories steelcore

[/] [coremark/] [core_list_join.c] - Blame information for rev 11

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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