Edit: this has become a way bigger wall of text than I meant to
TLINGRT(too long I'm not gonna read that): I run a printf("0x%s\n", somePointer) twice and it prints two different results. It may be a bug in my assembly routine, but that is weird because it preserves all registers that need to be preserved.
Hi! A week ago, I was trying to write a bignum library in ASM/C. I got quite far (multiplication and division worked - mostly). Since then, I tried to update my OS, which failed, and I lost the data. In the meanwhile, however, I ran into a very strange bug. I already asked about it on
stackoverflow, but I did not get a satisfying answer (this is probably partly due to the fact that I didn't research the bug for too long before posting on stackoverflow: I recreated the bug with a far smaller source program now). Also, I thought this would be more the domain of OS-developers. I think this is actually the first bug that I can reliably reproduce but do not understand after a long investigation (which says more about my lack of experience than about my deep understanding, but still, for the record
).
The bug is probably introduced by the assembly routine I call. What's going on is:
1. I allocate some space for the big integer representation and fill the data up with some numbers
2. I call the assembly routine for adding the two numbers
3. I allocate space, convert the result of the addition to hex and save the hex representation to the allocated space, and keep a pointer to this.
4. I print the hex representation twice.
Here's the weird part: the two printed lines are different. The first line is "0x0", the second "0x0000000080000004" (which it should be).
5. I free everything.
When I ran valgrind, it states that printf tries to read the data 1 byte before the space I malloc'ed for the hex representation. I don't know why: when I step the opcodes with gdb, the address passed to printf is fine and contains the right ascii ("0000000080000004"), yet the printed result is still wrong. It seems that printf somehow changes the address that is passed to it by one.
I suspect this is due to a register that is messed up somewhere: when I print the address where the hex representation is stored before printing the hex itself, the bug dissappears: the two printed lines are the same and valgrind reports no bugs. But I do preserve ebx, esi and edi (and also esp and ebp, as I never touch them) in my assembly routine.
I included the source here. The C is probably understandable (but may be a little weird, as I just included the parts of the original program which matter in this case). I was testing the case where an overflow occurs in the assembly (so there should not be undefined behaviour as in C) and the size of the big integer needs to be increased. I wouldn't bother with understanding the ASM code.
You can assemble with
nasm -f elf -s test.asm
and (after that) compile the C code with either
gcc test.c test.o -o test -m32 -std=c99 -g
or
clang test.o test.c -m32 -g
(or use another compiler) I included the debug flag so you can use gdb to debug, and the m32 flag so you can compile on 64-bit systems (the assembly code is x86). You might need some extra libs (I think I needed to do sudo apt-get gcc-multilib:i386 before it would compile).
test.c:
Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
extern uint32_t *addHelper(uint32_t *aData, uint32_t *bData, uint32_t smallSize, uint32_t difference);
typedef struct BigInt BigInt;
struct BigInt
{
uint32_t size;
uint32_t *data;
};
char *toHex(BigInt *a);
int main(int argc, char *argv[])
{
char *ap;
BigInt *a = malloc(sizeof(BigInt)), *b = malloc(sizeof(BigInt));
// set a to be a big integer representing 0x7fffffff
a->size = 1;
a->data = malloc(sizeof(uint32_t));
a->data[0] = 0x7fffffff;
// set b to be a big integer representing 5
b->size = 1;
b->data = malloc(sizeof(uint32_t));
b->data[0] = 5;
// call assembly routine, increase size of a to include
// the extra uint32_t caused by the overflow, and store
// the hex representation somewhere pointed to by ap
a->data = addHelper(a->data, b->data, b->size, a->size - b->size);
a->size++;
ap = toHex(a);
// now print the hex representation of ap twice
printf("0x%s\n", ap);
printf("0x%s\n", ap);
// free everything (optional as most OSes do this after prog. exec)
free(a->data);
free(a);
free(b->data);
free(b);
free(ap);
}
char numToHex[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
char *toHex(BigInt *a)
{
char *result, *ptr;
ptr = result = malloc(a->size * 8 + 1);
for (uint32_t i = 0; i < a->size; i++)
for (int32_t j = 28; j >= 0; j -= 4)
*(ptr++) = numToHex[(a->data[i] >> j) & 0xf];
*ptr = 0;
return result;
}
test.asm:
Code:
global addHelper
extern realloc
; addHelper(*aData, *bData, smallSize, difference)
addHelper:
push ebx
push esi
push edi
mov esi, dword [esp + 16]
mov edi, dword [esp + 20]
mov ecx, dword [esp + 24]
mov eax, dword [esp + 28]
lea esi, [esi + 4 * eax]
clc
add_loop:
mov edx, dword [edi + 4 * ecx - 4]
adc dword [esi + 4 * ecx - 4], edx
loop add_loop
mov esi, [esp + 16]
seto cl
test eax, eax
jnz add_decide_carry
test ecx, ecx
jz skip_overflow
jmp overflow
add_decide_carry:
jnc skip_overflow
mov ecx, eax
carry_loop:
adc dword [esi + 4 * ecx - 4], 0
jnc skip_carry_loop
loop carry_loop
skip_carry_loop:
jno skip_overflow
dec ecx
jnz skip_overflow
overflow:
add eax, dword [esp + 24]
mov ebx, eax
inc eax
shl eax, 2
push eax
push esi
call realloc
add esp, 8
mov ecx, ebx
mov esi, eax
mov ebx, dword [esi]
shr ebx, 31
dec ebx
lea esi, [esi + 4 * ecx - 4]
lea edi, [esi + 4]
std
rep movsd
mov dword [edi], ebx
skip_overflow:
pop edi
pop esi
pop ebx
ret
Login
Register
FAQ
Search
