The problem I tried to solve is the longest palindrome substring problem on LeetCode.
When I run my code on DEVC++ it works perfectly fine, but when I try to run on leetcode it gives this "AddressSanitizer: heap-buffer-overflow on address" runtime error. I asked Chat-GPT to correct my code but it seems like he didn't change anything but still his code works on leetcode (I will add it too). What I am doing wrong?
char* longestPalindrome(char* s) {
int i = 0;
int j = 0;
int high_i = 0;
int high_j = 0;
int maxlen = 0;
int leng = strlen(s);
for(i = 0; i < strlen(s); i++)
{
for(j = 0; s[i - j] == s[i + j] && (i - j) >= 0 && i + j < leng ; j++) // for odd number length palindromes
{// checking index is not out of range
if(((j >= high_j)))
{
high_j = j;
high_i = i;
maxlen = (2 * high_j) + 1;
}
}
}
for(i = 0; i < leng; i++)
{
for(j = 0; s[i - j] == s[i + j + 1] && (i - j) >= 0 && i + j < leng - 1; j++) // for even number length substrings
{ // making sure index is not out of range
if((j + 1) * 2 > maxlen) // compare palindrome length
{
high_j = j;
high_i = i;
maxlen = (1 + j) * 2;
}
}
}
char* result = malloc(sizeof(char) * (maxlen + 1)); // allocate memory for return string
strncpy(result, s + high_i - high_j, maxlen); // start copying (i - j) to maxlen to result string
result[maxlen] = '\0'; // end null end of string
return result;
}
And this one is Chat-GPT's
char* longestPalindrome(char* s) {
int i = 0;
int j = 0;
int high_i = 0;
int high_j = 0;
int maxlen = 0;
int leng = strlen(s);
for (i = 0; i < leng; i++) {
for (j = 0; (i - j) >= 0 && (i + j) < leng && s[i - j] == s[i + j]; j++) {
if (j >= high_j) {
high_j = j;
high_i = i;
maxlen = (2 * high_j) + 1;
}
}
}
for (i = 0; i < leng; i++) {
for (j = 0; (i - j) >= 0 && (i + j + 1) < leng && s[i - j] == s[i + j + 1]; j++) {
if ((j + 1) * 2 > maxlen) {
high_j = j;
high_i = i;
maxlen = (j + 1) * 2;
}
}
}
char* result = (char*)malloc(sizeof(char) * (maxlen + 1));
strncpy(result, s + high_i - high_j, maxlen);
result[maxlen] = '\0';
return result;
}
Full error code is
=================================================================
==22==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000000f at pc 0x55de54d7590e bp 0x7ffea23781a0 sp 0x7ffea2378190
READ of size 1 at 0x60200000000f thread T0
#2 0x7f8076b44082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x60200000000f is located 1 bytes to the left of 6-byte region [0x602000000010,0x602000000016)
allocated by thread T0 here:
#0 0x7f807778c808 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:144
#3 0x7f8076b44082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
Shadow bytes around the buggy address:
0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa[fa]06 fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==22==ABORTING
It seems that you misunderstand how short-circuiting works. When C evaluates the expression
s[i - j] == s[i + j] && (i - j) >= 0
It first looks at s[i - j] == s[i + j] and if this evaluates to false then it stops evaluating and skips to the else portion of the condition. To correctly use short-circuiting you want to put your edge case checking at the far left, so that it is checked first and so the evaluation is aborted prior to looking at the rest of the expression.
For this reason you want to put (i - j) >= 0 in front of the rest of the expression. So it should look like this:
(i - j) >= 0 && s[i - j] == s[i + j]
This way if (i - j) >= 0 evaluates to false then the conditional part of the expression is skipped so that the invalid memory access doesn't happen.
Here's a good article on short circuiting from wikipedia https://en.wikipedia.org/wiki/Short-circuit_evaluation
and as a supplement, here is the operator precedence for C https://en.cppreference.com/w/c/language/operator_precedence (the important thing to look at here isn't the precedence, though that is really important, it's the association, that will tell you the direction that expressions are evaluated)