• State Resolved
  • Locked Locked
  • Replies 12 replies
  • Subscribers 55 subscribers
  • Views 3628 views
  • Users 0 members are here
Support feedback
Options
Options
Similar topics

This thread has been locked.

If you have a related question, please click the "Ask a related question" button in the top right corner. The newly created question will be automatically linked to this question.

Compiler: Problem of using qsort() on the ARM processer

Peter010
Genius 4165 points
Other Parts Discussed in Thread: AWR1642, SYSBIOS

Tool/software: TI C/C++ Compiler

Hello everyone

I am using the ARM core on the AWR1642, the compiler version is v16.9.1.LTS. I want to sort an array structure as showing below, however, when I run the code, it gives the error. It seems like the qsort want to access to an invalid area. Can you tell me what is the wrong?

Thanks

Xining

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef struct {
    float price;
    float test;
    int id;
} order;
order list[10];
int i = 0;

int compare (const void * a, const void * b)
{

  order *orderA = (order *)a;
  order *orderB = (order *)b;

  return ( (orderA->price > orderB->price) ? 1:-1 );
}

int main ()
{
    srand((unsigned int)time(NULL));

    printf("Before sorting\n");
    for(i=0; i<10; i++){
        list[i].price = (float)rand()/(float)(RAND_MAX) * 10;
        list[i].test = rand()%10;
        list[i].id = i;
        printf ("Order id = %d Price = %f Test = %f\n",list[i].id, list[i].price, list[i].test);
    }
    printf("AFTER sorting\n");
    int n;
    qsort (list, 6, sizeof(order), compare);
    for (n=0; n<10; n++)
         printf ("Order id = %d Price = %f Test = %f\n",list[n].id, list[n].price, list[n].test);
    return 0;
}

The output is:

Before sorting
Order id = 0 Price = 6.347239 Test = 8.000000
Order id = 1 Price = 1.647694 Test = 3.000000
Order id = 2 Price = 5.049898 Test = 5.000000
Order id = 3 Price = 8.674276 Test = 4.000000
Order id = 4 Price = 4.470962 Test = 0.000000
Order id = 5 Price = 6.625263 Test = 6.000000
Order id = 6 Price = 3.482467 Test = 9.000000
Order id = 7 Price = 6.930449 Test = 9.000000
Order id = 8 Price = 5.341044 Test = 6.000000
Order id = 9 Price = 5.465560 Test = 2.000000
AFTER sorting
Exception occurred in ThreadType_Main.
Main handle: 0x0.
Main stack base: 0x8019a40.
Main stack size: 0x1000.
R0 = 0x08040000 R8 = 0x080199fc
R1 = 0x080199e4 R9 = 0x08040000
R2 = 0x0000000c R10 = 0x00008710
R3 = 0x00008710 R11 = 0x00000003
R4 = 0x00000005 R12 = 0x08040000
R5 = 0x00003330 SP(R13) = 0x0801a9e8
R6 = 0x0000000c LR(R14) = 0x000068c3
R7 = 0x00000006 PC(R15) = 0x00008738
PSR = 0x000c01df
DFSR = 0x0000000d IFSR = 0x00000000
DFAR = 0x08040000 IFAR = 0x00000000
ti.sysbios.family.arm.exc.Exception: line 205: E_dataAbort: pc = 0x00008738, lr = 0x000068c3.
xdc.runtime.Error.raise: terminating execution

  • 0
    Guru 35680 points
    Put a printf() (or a breakpoint!) inside compare to see if the crash happens before, during or after the compare - or indeed after several of them.

    (Any reason to only sort 6 of them?)
  • 0 in reply to Keith Barkley
    Genius 4165 points

    Thanks for your reply.

    After adding code line <printf("\nCompare successful.");> inside compare function, the program runs without crashing. But the sorting result is wrong. The output is showing as below.

    Keith Barkley said:
    (Any reason to only sort 6 of them?)

    In my application, I cannot decide how many items would be registered each time. So, in this time there are 6 items, next time would be 7 or 5. ( the number of items depends on the input). The program i pasted here is just an illustration, which is used to show the issue I encountered in my real application.

    Before sorting
    Order id = 0 Price = 8.997162 Test = 5.000000
    Order id = 1 Price = 1.835383 Test = 7.000000
    Order id = 2 Price = 6.288339 Test = 0.000000
    Order id = 3 Price = 8.461562 Test = 0.000000
    Order id = 4 Price = 9.874569 Test = 6.000000
    Order id = 5 Price = 4.933012 Test = 9.000000
    Order id = 6 Price = 3.842585 Test = 6.000000
    Order id = 7 Price = 0.871914 Test = 2.000000
    Order id = 8 Price = 1.196631 Test = 9.000000
    Order id = 9 Price = 0.255745 Test = 2.000000
    AFTER sorting

    Compare successful.
    Compare successful.
    Compare successful.
    .

    .

    <In total 262>

    .

    .

    Compare successful.
    Compare successful.
    Compare successful

    Order id = 31725 Price = 0.000000 Test = 0.000000
    Order id = 134328860 Price = 0.000000 Test = 0.000000
    Order id = -1 Price = 0.000000 Test = 0.000000
    Order id = -1 Price = 0.000000 Test = 0.000000
    Order id = 134323356 Price = 0.000000 Test = 0.000000
    Order id = 46 Price = 0.000000 Test = 0.000000
    Order id = 46 Price = 0.000000 Test = nan
    Order id = 0 Price = 0.000000 Test = 0.000000
    Order id = 0 Price = 0.000000 Test = nan
    Order id = 29463 Price = 0.000000 Test = 0.000000

  • 0 in reply to Peter010
    Guru 35680 points
    This sounds like a stack issue. Can you increase the stack?

    print sizeof(order) and see if it makes sense.

    You can also print the addresses of each element, and make sure the pointers you get in the compare() are the right ones.
  • 0 in reply to Keith Barkley
    Genius 4165 points

    I double the stack size (4K). It does not help.

    In my previous test, there are 262 times comparison. However, there are only 6 elements to be sorted. Don't you think the number of comparison is too large for this size of array?

    Xining Yu

  • 0
    TI__Guru* 84225 points

    Your comparison function returns the wrong values.  It must return 0 if two elements compare equal:

      return ( (orderA->price > orderB->price) ? 1 : 
           (orderA->price < orderB->price) ? -1 : 0);
  • 0 in reply to Archaeologist
    Genius 4165 points

    First, your answer sloves my issue. Thanks for your help.

    Second, as you can see that in my post, there are no element has same value. Why the program goes wrong?

    Third, why the qsort() function runs well with my "return method" on other C programming software?

    Thanks
    Xining

  • 0 in reply to Peter010
    Guru 35680 points
    Yes, it should be about nlog2(n). I googled it, I did not want to drag out Sedgewick. 8^). It looks to me like you are clobbering memory and the keys are changing every time which confuses quicksort. For example, if you have provided a wrong value for the size of the elements, which is why I said to check the value of sizeof(order).

    The other scary thing is that you are clobbering way more than 6 elements. Who knows how much memory qsort() is messing up.

    It really looks like a qsort() bug, though that is hard to believe. The only error in your code is that the compare function cannot return 0.
  • 0 in reply to Keith Barkley
    Genius 4165 points

    Yes, you are right there is a bug as mentioned by TI employee. I check the size of element. It gives the correct value. In this case it is 12. After correcting this bug, the code works. I also raised other questions to TI employee as you can see.

    Thanks for your help.
    Xining

  • 0 in reply to Peter010
    TI__Guru* 84225 points
    Different toolchains implement qsort with slight differences. This is OK as long as the function gets the job done. In particular, it seems the TI implementation tries to compare elements to themselves. I don't want to look too closely at the failure mode, but the function seems to get confused and go into an infinite loop. I suspect that the values aren't actually corrupted, but that printf's ability to correctly show them is corrupted because we ran out of stack.
  • 0 in reply to Peter010
    Guru 35680 points
    Yes, but you have the bug, not TI, as I pointed out.
  • 0 in reply to Keith Barkley
    Genius 4165 points
    That is true.
  • 0 in reply to Peter010
    Guru 35680 points
    Just to beat a dead horse, Sedgewick states that quicksort is not stable and fragile. I think you have found that an incorrect compare function can cause big problems. I actually spotted the error in the compare function when I first read the OP, but like you did not think that it would make the algorithm blow up.