0

Xcode generates an EXC_BAD_ACCESS error. I suppose the problem is that I messed up with the registers accessing arrays' values.

Plain step-by-step explanation would be much appreciated, thanks!

void countingSort(int array[], int length, int digit) {
    int i, count[10] = { };
    int sorted[length];

    // Store number of occurrences in count[].
    // for (i = 0; i < length; i++)
    //     count[ (array[i] / digit) % 10 ]++;

    // Inline assembler loop
    // in place of commented out for loop.
    asm(
        "loopOne: \n\t"
            "movl $0, %%ecx \n\t"
            "cmpl %%ecx, (%[length]) \n\t"
            "je loopTwo \n\t"

            "movl %[array], %%esp \n\t"
            "movl (%%esp, %%ecx, 4), %%eax \n\t"
            "movl (%[digit]), %%ebx \n\t"
            "divl %%ebx \n\t"

            "movl %[count], %%ebp \n\t"
            "movl (%%ebp, %%edx, 4), %%esi \n\t"
            "inc %%esi \n\t"

            "inc %%ecx \n\t"
            "jmp loopOne \n\t"

        "loopTwo: \n\t"
        // ...

        : [array] "=g" (array), [count] "=g" (count)
        : [digit] "r" ((long) digit), [length] "r" ((long) length)
    );
}

void radixSort(int array[], int length) {
    // Maximum number helps later when counting number of digits.
    int max = findMax(array, length);

    // Do Counting sort for every digit.
    for (int digit = 1; max / digit > 0; digit *= 10)
        countingSort(array, length, digit); // Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)
}
Anton Timofeev
  • 21
  • 4
  • Unrelated to your problem (since you can build the program), but C++ doesn't have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array) (like your array `sorted` is in the `countingSort` function). Some compilers add it as an *extension*, but if you want to be portable you should not use them. If you want a variable-length "arrays" use [`std::vector`](http://en.cppreference.com/w/cpp/container/vector) instead. – Some programmer dude Feb 14 '18 at 11:25
  • that's strange format of inline asm, what compiler that is? And doing asm + C++ ...ugh. – Swift - Friday Pie Feb 14 '18 at 11:29
  • You forget to specify clobbers list, so many registers are polluted. – llllllllll Feb 14 '18 at 11:31
  • and shouldn't asm have volatile specifier? Though that's gcc, I'm not aware what kind of compiler this is, – Swift - Friday Pie Feb 14 '18 at 11:34
  • @Swift It is tagged [tag:xcode], so I would assume Apple and clang. – Olaf Dietsche Feb 14 '18 at 13:02
  • 1
    `divl %%eax` is essentially nonsensical, and `edx` hasn't been set to a safe upper-half – harold Feb 14 '18 at 13:30
  • @Someprogrammerdude: GNU C inline asm implies support for VLAs in C++, because both are GNU extensions to ISO C++. If you're going to the trouble of using inline asm, you very likely don't want the overhead of calling `new` / `delete` from `std::vector` when you could just use stack space. Although in this case the asm isn't particularly optimized. (No xor-zeroing, loop branch at the top of the loop, and most importantly using `divl` for some kind of base-10 radix sort instead of using a power-of-2 radix with shift/mask.) – Peter Cordes Feb 14 '18 at 16:22
  • @Swift: clang/llvm implements GNU C extensions, including GNU C inline asm. So yes, this should use `asm volatile` and a `"memory"` clobber, or (better) list the input and output arrays as memory operands (not just pointers to them). Or even better, write a stand-alone function and only provide a C prototype, because GNU C inline asm is the hardest way to learn asm: to get it right (writing correct constraints) you have to understand asm *and* how compilers work. – Peter Cordes Feb 15 '18 at 11:24
  • @PeterCordes Could you please elaborate a bit on the 2nd and 3rd option? What does it mean to list the arrays as memory operands? And last passage on a stand-alone function and a C prototype I didn't get at all. – Anton Timofeev Feb 15 '18 at 12:37
  • @PeterCordes Sorry in advance but I'm really newbie here and realize that using inline isn't the prettiest thing in the world to start learning assembly with. Nevertheless my university assignment is quite specific on that. – Anton Timofeev Feb 15 '18 at 12:39
  • @PeterCordes By the way I added `asm volatile` and a `memory` clobber but that didn't change much, the EXC_BAD_ACCESS error still persists. – Anton Timofeev Feb 15 '18 at 12:41
  • `volatile` is necessary to stop the compiler optimizing away the asm statement, and a `"memory"` makes sure that memory contents reflect the C abstract machine state at that point (i.e. that loads / stores aren't reordered around the inline asm). If you compile with `-O0` (the default), then you don't need either of those, but C code that breaks with optimization enabled is not correct. But if you only care about the asm part of the inline asm, and not about writing correct or optimal constraints, then don't worry about that for now. Anyway, those won't stop broken asm from crashing. – Peter Cordes Feb 15 '18 at 13:33
  • Stand-alone function: you put your function in a separate `.S` file, and just put the prototype `extern "C" void countingSort(int array[], int length, int digit);` in a .h or in your `.cpp`. – Peter Cordes Feb 15 '18 at 13:36
  • Re: memory input operand: https://stackoverflow.com/questions/45649101/get-string-length-in-inline-gnu-assembler/45656087#45656087. Also https://stackoverflow.com/questions/1956379/att-asm-inline-c-problem/47358313?noredirect=1#comment81680441_47358313, and (recently updated in the gcc manual), the clobbers section has examples of using dummy operands to tell the compiler the whole array (of unknown size) is an input or output: https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html#index-asm-clobbers. Again, this only matters for correctness if you enable optimization. – Peter Cordes Feb 15 '18 at 13:43

0 Answers0