Hi! The following C code will trigger undefined behaviour in libsais' unbwt code:
unsigned char arr[] = { 0xFB, 0xB7, 0x46, 0xA8, 0x13, 0xBC, 0x88, 0xC8, 0x9B, 0xBC, 0x97, 0xCB, 0x1A, 0xA6, 0xAE, 0x96, 0xBC, 0xBD, 0x13, 0xB7, 0xA3, 0xE2, 0x95, 0x88, 0x9B, 0xB6, 0xC2, 0x87, 0x65, 0x77, 0xF7, 0xB8, 0x8E, 0xCE, 0xE1, 0xCB, 0x9F, 0x63, 0x9B, 0xF3, 0xCB, 0x63, 0x42, 0x26, 0x14, 0x2F, 0xC4, 0xCE, 0x43 };
int size = 49; int bwt_idx = 1;
int main(void) {
s32 * A = (s32 *) malloc(sizeof(s32) * (size + 1));
libsais_unbwt(arr, arr, A, size, NULL, bwt_idx);
printf("%d\n", arr[0]);
}
==2044781== Use of uninitialised value of size 8
==2044781== at 0x11D5C2: libsais_unbwt_decode_1 (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x11F638: libsais_unbwt_decode (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12016F: libsais_unbwt_decode_omp (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120205: libsais_unbwt_core (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12031E: libsais_unbwt_main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120601: libsais_unbwt_aux (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120489: libsais_unbwt (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x10927E: main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781==
==2044781== Use of uninitialised value of size 8
==2044781== at 0x11D5EA: libsais_unbwt_decode_1 (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x11F638: libsais_unbwt_decode (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12016F: libsais_unbwt_decode_omp (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120205: libsais_unbwt_core (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12031E: libsais_unbwt_main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120601: libsais_unbwt_aux (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120489: libsais_unbwt (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x10927E: main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781==
==2044781== Use of uninitialised value of size 8
==2044781== at 0x11D5A8: libsais_unbwt_decode_1 (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x11F638: libsais_unbwt_decode (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12016F: libsais_unbwt_decode_omp (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120205: libsais_unbwt_core (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12031E: libsais_unbwt_main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120601: libsais_unbwt_aux (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120489: libsais_unbwt (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x10927E: main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781==
==2044781== Conditional jump or move depends on uninitialised value(s)
==2044781== at 0x11D5CA: libsais_unbwt_decode_1 (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x11F638: libsais_unbwt_decode (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12016F: libsais_unbwt_decode_omp (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120205: libsais_unbwt_core (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12031E: libsais_unbwt_main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120601: libsais_unbwt_aux (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120489: libsais_unbwt (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x10927E: main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781==
==2044781== Use of uninitialised value of size 8
==2044781== at 0x11D607: libsais_unbwt_decode_1 (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x11F638: libsais_unbwt_decode (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12016F: libsais_unbwt_decode_omp (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120205: libsais_unbwt_core (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x12031E: libsais_unbwt_main (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120601: libsais_unbwt_aux (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x120489: libsais_unbwt (in /home/palaiologos/Desktop/bzip3/unit)
==2044781== by 0x10927E: main (in /home/palaiologos/Desktop/bzip3/unit)
static void libsais_unbwt_decode_1(u8 * RESTRICT U, sa_uint_t * RESTRICT P, sa_uint_t * RESTRICT bucket2,
u16 * RESTRICT fastbits, fast_uint_t shift, fast_uint_t * i0, fast_uint_t k) {
u16 * RESTRICT U0 = (u16 *)(void *)U;
fast_uint_t i, p0 = *i0;
for (i = 0; i != k; ++i) {
u16 c0 = fastbits[p0 >> shift];
if (bucket2[c0] <= p0) {
do {
c0++;
} while (bucket2[c0] <= p0);
}
p0 = P[p0];
U0[i] = libsais_bswap16(c0);
}
*i0 = p0;
}