Ошибка 0xC0000005 на третьей итерации с++

Question

При третей итерации получаю ошибку 0xC0000005, однако при первых двух итерациях всё работает нормально

#include <iostream>
#include <stdlib.h>

using namespace std;

int arr[1000];

int getRDX (int n, unsigned rdx) {
    return n-n/10/rdx*10-n+n/rdx;
}

void RadixSort (int *ptr, unsigned lenght) {
    //Amount of iterations
    unsigned iter_n = 1;

    //RDX counter
    unsigned rdx_c[10];

    //Auxiliary data
    int *backup = new int[lenght];
    int biggest = ptr[0];
    unsigned rdx_k = 1;

    //Calculating the amount of iterations
    for(unsigned i = 1; i < lenght; i++) {
        if(biggest < ptr[i]) {
            biggest = ptr[i];
        }
    }
    while(true) {
        biggest/=10;
        if(biggest == 0) {
            break;
        }
        iter_n++;
    }
    //Actual Sorting
    for(unsigned iter_c = 0; iter_c < iter_n; iter_c++) {
        //Resetting RDX counter
        for(unsigned i = 0; i < 10; i++) {
            rdx_c[i] = 0;
        }
        for(unsigned i = 0; i < lenght; i++) {
            rdx_c[getRDX(ptr[i], rdx_k)]++;
        }
        //Prefix Sum
        for(unsigned i = 1; i < lenght; i++) {
            rdx_c[i]+=rdx_c[i-1];
        }
        for(int i = lenght-1; i >= 0; i--) {
            backup[--rdx_c[getRDX(ptr[i], rdx_k)]] = ptr[i];
        }
        for(unsigned i = 0; i < lenght; i++) {
            ptr[i] = backup[i];
        }
        rdx_k*=10;
    }
    delete []backup;
}

int main() {
    for(unsigned i = 0; i < 1000; i++) {
        arr[i] = rand()%1000;
        //cout << arr[i] << endl;
    }
    RadixSort(arr, 1000);
    for(unsigned i = 0; i < 1000; i++) {
        //cout << arr[i] << endl;
    }
    return 0;
}

думаю, ошибка происходит где-то тут:

for(int i = lenght-1; i >= 0; i--) {
    backup[--rdx_c[getRDX(ptr[i], rdx_k)]] = ptr[i];
}

Answer 1

Во-первых хочу сказать: я бы давал по рукам за такой "код" - глобальные переменные, куча операций в одной строке, ужасное именование переменных и прочее.

Во-вторых, изучите дебагер.

В-третьих, изучите как располагаются переменные в памяти.

В-четвертых, освойте такие инструменты как valgrind и/или LeakSanitizer

Ну а теперь к проблеме: она выясняется практически сразу при включении санитайзера:

==28663==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffc4466cf08 at pc 0x55de513a9668 bp 0x7ffc4466ce60 sp 0x
7ffc4466ce58
READ of size 4 at 0x7ffc4466cf08 thread T0
    #0 0x55de513a9667 in RadixSort(int*, unsigned int) /home/levkovitch/a.cpp:46
    #1 0x55de513a9ab2 in main /home/levkovitch/a.cpp:67
    #2 0x7f549d74809a in __libc_start_main ../csu/libc-start.c:308
    #3 0x55de513a9169 in _start (/home/levkovitch/a.out+0x1169)

Address 0x7ffc4466cf08 is located in stack of thread T0 at offset 72 in frame
    #0 0x55de513a927c in RadixSort(int*, unsigned int) /home/levkovitch/a.cpp:10

  This frame has 1 object(s):
    [32, 72) 'rdx_c' <== Memory access at offset 72 overflows this variable

Как видим вы вылазите за пределы выделенной памяти при использовании переменной rdx_c в строке 46. Посмотрим что там:

    for (unsigned i = 1; i < lenght; i++) {
      rdx_c[i] += rdx_c[i - 1];
    }

А теперь посмотрим что это за rdx_c:

  unsigned rdx_c[10];

И это при том, что length у вас равно 1000.

БЛОГ НА HUSL

Ошибка 0xC0000005 на третьей итерации с++

Ответы (1 шт):