/*
 * minimal freestanding C library
 * 
 * works for IA-32 and Linux, uses old INT 80h software interrupts
 * for system calls.
 * 
 */

#include <stdarg.h>
#include <stddef.h>

/* string */

int strcmp( const char *s1, const char *s2 )
{
	while( *s1 && *s2 && *s1 == *s2 ) {
		s1++;
		s2++;
	}

	return *s1 - *s2;
}

int strlen( const char *s )
{
	int len;
	const char *p = s;
	
	for( len = 0; *p; len++, p++ );
	
	return len;
}

int strlcpy( char *d, const char *s, int n )
{
	int len = 0;
	
	while( len < n && s[len] != '\0' ) {
		d[len] = s[len];
		len++;
	}
	d[len] = '\0';
	
	while( s[len] != '\0' ) {
		len++;
	}
	
	if( len >= n ) {
		d[n-1] = '\0';
	}
	
	return len;
}

int strlcat( char *d, const char *s, int n )
{
	int len = 0;
	const char *ss = s;
	char *dd = d;
	
	while( len < n && *dd != '\0' ) {
		len++;
		dd++;
	}
	
	if( len == n ) {
		return len + strlen( s );
	}
	
	while( len + 1 < n && ( *dd++ = *ss++ ) ) {
		len++;
	}
	
	*dd = '\0';
	
	return len;
}	

void *memcpy( void *d, const void *s, int len )
{
	const char *p = s;
	char *q = d;
		
	while( len-- ) {
		*q = *p;
		q++;
		p++;
	}
	
	return d;
}

/* errno */

int errno;

enum {
	ENOMEM = 1
};

/* stdlib */

enum {
	EXIT_SUCCESS = 0,
	EXIT_FAILURE = 1
};

enum {
	SYSCALL_EXIT = 1,
	SYSCALL_READ = 3,
	SYSCALL_WRITE = 4,
	SYSCALL_BRK = 45
};

enum {
	STDIN_FILENO = 0,
	STDOUT_FILENO = 1,
	STDERR_FILENO = 2
};

static __attribute__((noinline)) int syscall1( int id, int arg0 )
{
	int retval;
   
	__asm__ volatile( "\
		push %%ebx\n\
		mov %1, %%eax\n\
		mov %2, %%ebx\n\
		int $0x80\n\
		mov %%eax, %0\n\
		pop %%ebx\n" : "=m"( retval ) : "m"( id ), "m"( arg0 ) );

	if( retval < 0 ) {
		errno = -retval;
		return -1;
	}

	return retval;
}

static __attribute__((noinline)) int syscall3( int id, int arg0, int arg1, int arg2 )
{
	int retval;
   
	__asm__ volatile( "\
		push %%ebx\n\
		push %%ecx\n\
		push %%edx\n\
		mov %1, %%eax\n\
		mov %2, %%ebx\n\
		mov %3, %%ecx\n\
		mov %4, %%edx\n\
		int $0x80\n\
		mov %%eax, %0\n\
		pop %%edx\n\
		pop %%ecx\n\
		pop %%ebx\n" : "=m"( retval ) : "m"( id ), "m"( arg0 ), "m"( arg1 ), "m"( arg2 ) );

	if( retval < 0 ) {
		errno = -retval;
		return -1;
	}
	
	return retval;
}

void exit( int status )
{
	syscall1( SYSCALL_EXIT, status );
}

static void strreverse( char *s )
{
	char *end = s + strlen( s ) - 1;
	
	while( s < end ) {
		*s ^= *end;
		*end ^= *s;
		*s ^= *end;
		s++;
		end--;
	}
}
    
char *itoa( int v, char *s, int base )
{
	static char digit[] = "0123456789ABCDEF";
	int sign = 0;
	char *p = s;
	
	if( base < 2 || base > 16 ) {
		return NULL;
	}
	
	if( v < 0 ) {
		v = -v;
		sign = 1;
	} 
	
	do {
		*p++ = digit[v % base];
	} while( ( v /= base ) > 0 );

	if( sign ) {
		*p++ = '-';
	}
	*p = '\0';
	
	strreverse( s );
	
	return s;
}

static int system_brk( void *addr )
{
	return syscall1( SYSCALL_BRK, (int )addr );
}

static void *current_brk = 0;

int brk( void *addr )
{
	void *p;
	
	p = (void *)system_brk( addr );
	if( (int)p < 0 ) {
		return -1;
	}
	if( p == current_brk ) {
		errno = ENOMEM;
		return -1;
	}

	current_brk = p;
	
	return 0;
}

void *sbrk( int inc )
{
	void *old_brk;
	int res;

	if( current_brk == 0 ) {
		brk( 0 );
	}
	
	if( inc == 0 ) {
		return current_brk;
	}
	
	old_brk = current_brk;
	
	res = brk( ( char *)current_brk + inc );
	if( res == -1 ) {
		return (void *)-1;
	}
	
	return old_brk;
}

typedef struct mem_header {
	int size;
	int used;
	struct mem_header *next;
	int align;
} mem_header;

static mem_header *mem_head = NULL;
static mem_header *mem_tail = NULL;
static void *initial_brk = NULL;
static int mem_total_use = 0;
static int mem_in_use = 0;
static int mem_max_use = 0;
static int mem_nof_mallocs = 0;
static int mem_nof_frees = 0;

int mem_align( int n )
{
	return ( n + sizeof( int ) - 1 ) & ~( sizeof( int ) - 1 );
}

void malloc_stats( void );

void *malloc( int size )
{
	int total_size;
	void *ptr;
	mem_header *header;
	
	total_size = mem_align( sizeof( mem_header ) + size );
	
	header = mem_head;
	while( header != NULL ) {
		if( !header->used && header->size >= size ) {
			header->used = 1;
			mem_in_use += header->size;
			mem_total_use += header->size;
			mem_nof_mallocs++;
			return (void *)( header + 1 );
		}
		header = header->next;
	}
	
	if( initial_brk == NULL ) {
		initial_brk = sbrk( 0 );
	}
	
	ptr = sbrk( total_size );
	if( ptr == (void *)-1 ) {
		return NULL;
	}
	
	header = ptr;
	header->size = size;
	header->used = 1;
	header->next = NULL;
	
	if( mem_head == NULL ) {
		mem_head = header;
	}
	if( mem_tail != NULL ) {
		mem_tail->next = header;
	}
	mem_tail = header;
	
	mem_max_use += size;
	mem_total_use += size;
	mem_in_use += size;
	mem_nof_mallocs++;
	
	return (void *)( header + 1 );
}

static void print_string( int fd, const char *s );

void free( void *ptr )
{
	mem_header *header, *tmp;
	void *actual_brk;
	
	if( ptr == NULL ) {
		print_string( 2, "warning: freeing a NULL pointer\n" );
		return;
	}
	
	header = (mem_header *)ptr - 1;
	if( !header->used ) {
		print_string( 2, "warning: double free in linked list detected\n" );
		return;
	}
	header->used = 0;
	mem_in_use -= header->size;
	mem_nof_frees++;
	
	actual_brk = sbrk( 0 );
	if( (char *)ptr + header->size == actual_brk ) {
		tmp = mem_head;
		while( tmp != NULL ) {
			if( tmp->next == mem_tail ) {
				tmp->next = NULL;
				mem_tail = tmp;
			}
			tmp = tmp->next;
		}
		if( mem_head == mem_tail ) {
			mem_head = NULL;
			mem_tail = NULL;
		}
		sbrk( - header->size - sizeof( mem_header ) );
	}
}

/* stdio */

static void print_char( int fd, int c )
{
	char s[1];
	s[0] = c;
	syscall3( SYSCALL_WRITE, fd, (int)s, 1 );
}

static void print_string( int fd, const char *s )
{
	syscall3( SYSCALL_WRITE, fd, (int)s, strlen( s ) );
}

static int read_string( int fd, char *buf, int size )
{
	return syscall3( SYSCALL_READ, fd, (int)buf, size );
}

enum {
	INTERNAL_STDIO_BUFSIZE = 512
};

typedef struct {
	int fileno;
	int readpos;
	int size;
	char buf[INTERNAL_STDIO_BUFSIZE];
	int pushback;
} FILE;

static FILE fds[3] = { { STDIN_FILENO, 0, 0, "", 0 }, { STDOUT_FILENO, 0, 0, "", 0 }, { STDERR_FILENO, 0, 0, "", 0 } };

FILE *stdin = &fds[0];
FILE *stdout = &fds[1];
FILE *stderr = &fds[2];

enum {
	EOF = -1
};

int fputc( int c, FILE *stream )
{
	print_char( stream->fileno, c );
	
	return 0;
}

int fputs( const char *s, FILE *stream )
{
	print_string( stream->fileno, s );

	return 0;
}

int puts( const char *s )
{
	return fputs( s, stdout );
}

static void append_char( char *buf, int size, int *len, char c )
{
	if( *len < size ) {
		*buf = c;
		buf++;
		*buf = '\0';
		(*len)++;
	}
}

static void append_string( char *s, int size, int *len, char *s2 )
{
	strlcat( s, s2, size - *len );
	*len += strlen( s2 );
	if( *len > size ) {
		*s = '\0';
	}
	s += strlen( s2 );
}

int vsnprintf( char *buf, int n, const char *format, va_list args )
{
	const char *s = format;
	int len = 0;

	*buf = '\0';	
	while( *s != '\0' && len < n ) {
		switch( *s ) {
			case '%':
				s++;
				if( *s == '\0' ) {
					strlcpy( buf, "<truncated % found at end of format string>", n - len );
					strlcat( buf, "\n", n - len - 1 );
					return -1;
				}
				
				switch( *s ) {
					case '%':
						append_char( buf, n, &len, '%' );
						break;
						
					case 'X': {
						char buf2[19];
						itoa( va_arg( args, int ), (char *)buf2, 16 );
						append_string( buf, n, &len, buf2 );
						}
						break;
					
					case 'd': {
						char buf2[19];
						itoa( va_arg( args, int ), (char *)buf2, 10 );
						append_string( buf, n, &len, buf2 );
						}
						break;

					case 'c': {
						char buf2[2];
						buf2[0] = (char)va_arg( args, int );
						buf2[1] = '\0';
						append_string( buf, n, &len, buf2 );
						}
						break;
						
					case 's': {
						char *s = va_arg( args, char * );
						append_string( buf, n, &len, s );
						}
						break;

					default: {
						char buf2[2];
						append_string( buf, n, &len, "<illegal format string %" );
						buf2[0] = (char)( *s );
						buf2[1] = '\0';
						append_string( buf, n, &len, buf2 );
						buf2[0] = '\n';
						append_string( buf, n, &len, buf2 );
						}
				}
				
				break;				
			
			default: {
				char buf2[2];
				buf2[0] = (char)( *s );
				buf2[1] = '\0';
				append_string( buf, n, &len, buf2 );
				}
		}
		s++;
	}
	
	return len;
}

int vfprintf( FILE *stream, const char *format, va_list args )
{
	int res;
	
	res = vsnprintf( stream->buf, INTERNAL_STDIO_BUFSIZE, format, args );
	print_string( stream->fileno, stream->buf );
	
	return res;
}

int vprintf( const char *format, va_list args )
{
	return vfprintf( stdout, format, args );
}

int fprintf( FILE *stream, const char *format, ... )
{
	va_list args;
	int res;
	
	va_start( args, format );
	res = vfprintf( stream, format, args );
	va_end( args );
	
	return res;
}

int printf( const char *format, ... )
{
	va_list args;
	int res;
	
	va_start( args, format );
	res = vprintf( format, args );
	va_end( args );
	
	return res;	
}

int snprintf( char *buf, int n, const char *format, ... )
{
	va_list args;
	int res;
	
	va_start( args, format );
	res = vsnprintf( buf, n, format, args );
	va_end( args );
	
	return res;
}

int fflush( FILE *stream )
{
	/* TODO: currently streams are unbuffered, so there is nothing to do */
	return 0;
}

int fgetc( FILE *stream )
{	
	int c;
	
	if( stream->pushback != 0 ) {
		c = stream->pushback;
		stream->pushback = 0;
		return c;
	}
	
	if( stream->size == 0 ) {
		int n = read_string( stream->fileno, stream->buf, INTERNAL_STDIO_BUFSIZE );
		if( n < 0 ) {
			return EOF;
		}
		stream->size = n;
		stream->readpos = 0;
	}
	
	if( stream->size == 0 ) {
		return EOF;
	}
	
	c = (char)stream->buf[stream->readpos];
	stream->size--;
	stream->readpos++;
	
	return c;
}

int ungetc( int c, FILE *stream )
{
	stream->pushback = c;

	return c;
}

int getchar( void )
{
	return fgetc( stdin );
}

void malloc_stats( void )
{
	void *actual_brk = sbrk( 0 );
	
	fprintf( stderr, "Total %d bytes allocated, %d bytes peak allocation, %d bytes in use, brked memory %d bytes\n", 
		mem_total_use, mem_max_use, mem_in_use, (int)actual_brk - (int)initial_brk );
	fprintf( stderr, "Total %d mallocs, %d frees\n", mem_nof_mallocs, mem_nof_frees );
}